\documentstyle[12pt]{article}
\setlength{\textwidth}{9.75 in}
\setlength{\evensidemargin}{-0.4 in}
\setlength{\oddsidemargin}{-0.4  in}
\setlength{\textheight}{7.2 in}
\setlength{\topmargin}{-1.05 in}
\setlength{\arraycolsep}{9pt}
\renewcommand{\baselinestretch}{1.0}
\newcommand{\psfuh}    {/u/vision/fuh/document/}
\newcommand{\open}{\mbox{\Large $\circ$}}
\newcommand{\close}{\mbox{\Large $\bullet$}}
\input{psfig}
\newcommand{\epsfig}[1]{\psfig{#1}}
\begin{document}
\bibliographystyle{plain}

\Huge
\begin{center}
Chapter 10 Image Segmentation
\end{center}

\LARGE
10.1 Introduction \\
image segmentation: partition of image into set of nonoverlapping regions \\
image segmentation: union of segmented regions is the entire image \\
segmentation purpose: to decompose image into meaningful parts to application \\
segmentation based on valleys in gray level histogram into 4 regions \\
=====V. S. Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 3.20===== 

\vspace{1cm}
\noindent
rules for general segmentation procedures
\begin{enumerate}
\item region uniform, homogeneous w.r.t. characteristic e.g. gray level, texture
\item region interiors simple and without many small holes
\item adjacent regions with significantly different values on characteristic
\item boundaries simple, not ragged, spatially accurate
\end{enumerate}

\vspace{1cm}
\noindent
clustering: process of partitioning set of pattern vectors into clusters \\
set of points in Euclidean measurement space separated into 3 clusters \\
=====Fig. 10.2===== \\
no full theory of clustering \\
no full theory of image segmentation \\
image segmentation techniques: ad hoc, different in emphasis and compromise 

\vspace{1cm}
10.2 Measurement-Space-Guided Spatial Clustering \\
The technique of measurement-space-guided spatial clustering for image
segmentation uses the measurement-space-clustering process to define a 
partition in measurement space. 

\vspace{1cm}
\noindent
histogram mode seeking: a measurement-space-clustering process \\
histogram mode seeking: homogeneous objects as clusters in histogram \\
histogram mode seeking: one pass, the least computation time \\
pyrite: classic ``Fool's Gold" \\
pyrite: by far the most common and often mistaken for gold \\
enlarged image of a polished mineral ore section \\
=====Fig. 10.3===== \\
3 nonoverlapping modes: black holes, pyrrhotite, pyrite \\
=====Fig. 10.4===== \\
2 valleys in histogram is a virtually perfect (meaningful) segmentation \\
=====Fig. 10.5===== \\
example image not ideal for measurement-space-clustering image segmentation \\
=====Fig. 10.6===== \\
histogram with three modes and two valleys \\
=====Fig. 10.7===== \\
undesirable: many border regions show up as dark segments \\
=====Fig. 10.8===== \\
segmentation into homogeneous regions: not necessarily good solution 

\vspace{1cm}
\noindent
diagram of an F-15 bulkhead \\
=====Fig. 10.9===== \\
image of a section of the F-15 bulkhead \\
=====Fig. 10.10===== \\
histogram of the image \\
=====Fig. 10.11===== \\
five clusters: bad spatial continuation, boundaries noisy and busy \\
=====Fig. 10.12===== \\
three clusters: less boundary noise, but much less detail \\
=====Fig. 10.13=====

\vspace{1cm}
\noindent
recursive histogram-directed spatial clustering \\
=====Fig. 10.14===== \\
applied to the bulkhead image \\
=====Fig. 10.15===== \\
performing morphological opening with $3 \times 3$ square structuring element \\
=====Fig. 10.16===== \\
tiny regions removed, but several long, thin regions lost

\vspace{1cm}
\noindent
a color image \\
=====Fig. 10.17===== \\
recursive histogram-directed spatial clustering using $R,G,B$ bands and other \\
=====Fig. 10.18===== \\
=====Garfield 17:10=====

\vspace{1cm}
10.2.1 Thresholding \\
Kohler defines the set $E(T)$ of edges detected by a threshold $T$ to be the
set of all pairs of neighboring pixels one of whose gray level intensities
is less than or equal to $T$ and one of whose gray level intensities is
greater than $T$
\[
E(T)=\{[(i,j), (k,l)]|
\]
\hspace*{2in} 1. pixels $(i,j)$ and $(k,l)$ are neighbors \\
\hspace*{2in} 2. $\min \{I(i,j), I(k,l)\} \leq T < \max\{I(i,j), I(k,l)\}\}$ \\
The total contrast $C(T)$ of edges detected by threshold $T$ is given by
\[
C(T) = \sum_{[(i,j),(k,l)]\in E(T)} \min\{|I(i,j)-T|,|I(k,l)-T|\}
\]
The average contrast of all edges detected by threshold $T$: 
     $\frac{C(T)}{\#E(T)}$ \\
The best threshold $T_b$ is determined by the value that maximizes
\[
\frac{C(T_b)}{\#E(T_b)}
\]


\vspace{1cm}
\noindent
approach for segmenting white blob against dark background \\
pixel with small gradient: not likely to be an edge \\
if not an edge, then either dark background pixel or bright blob pixel \\
histogram of small gradient pixels: bimodal \\
pixels with small gradients: valley between two modes: threshold point \\
=====Fig. 10.19===== \\
FLIR (Forward Looking Infra-Red) image from NATO database \\
=====Fig. 10.20===== \\
thresholded at gray level intensity 159 and 190 \\
=====Fig. 10.21===== \\
pixels having large gradient magnitude \\
=====Fig. 10.22===== \\
2D gray level intensity---gradient space \\
=====Fig. 10.23===== \\
resulting segmentation: bright object with slightly darker appendage on top \\
=====Fig. 10.24=====

\vspace{1cm}
10.2.2 Multidimensional Measurement-Space Clustering \\
LANDSAT image: consists of seven separate images called bands \\
constraints of reality 
\begin{enumerate}
\item high correlation between band-to-band pixel values
\item large amount of spatial redundancy in image data
\end{enumerate}
=====Gonzalez, {\em Digital Image Processing}, Fig. 3.31=====

\vspace{1cm}
10.3 Region Growing \\
10.3.1 Single-Linkage Region Growing \\
single-linkage region-growing schemes: regard each pixel as node in graph \\
neighboring pixels with similar enough properties: joined by an arc \\
image segments: maximal sets of pixels belonging to same connected component \\
simple image and the corresponding graph \\
=====Fig. 10.25===== \\
two pixels connected by edge: if 4-neighbor and values differ $\leq 5$ 

\vspace{1cm}
10.3.2 Hybrid-Linkage Region Growing \\
hybrid single-linkage techniques: more powerful than simple single-linkage \\
hybrid techniques: assign property vector to each pixel \\
property vector: depends on $K \times K$ neighborhood of the pixel \\
pixels similar: because neighborhoods similar in some special sense \\
$R_1, R_2$: mutually exclusive neighborhoods having $N_1, N_2$ pixels \\
intensity mean:
\[
\bar{X}_i = \frac{1}{N_i} \sum_{x \in R_i} X
\]
intensity scatter:
\[
S_i = \sum_{x \in R_i} {(X-\bar{X}_i)}^2
\]

\vspace{1cm}
\noindent
region cannot be declared segment unless completely surrounded by edge pixels\\
edge image with gaps in the edges can cause problems in segmentation \\
=====Fig. 10.26===== \\
edges from second directional derivative zero-crossing \\
=====Fig. 10.27===== \\
after region-filling \\
=====Fig. 10.28=====

\vspace{1cm}
\noindent
Pong et al. suggest an approach to segmentation based on the facet model \\
one iteration of Pong algorithm \\
=====Fig. 10.29===== \\
second iteration of the Pong algorithm \\
=====Fig. 10.30===== \\
third iteration of the Pong algorithm \\
=====Fig. 10.31===== \\
after removing regions smaller than size 25 \\
=====Fig. 10.32===== \\
=====Oldie 33:21=====

\vspace{1cm}
10.3.3 Centroid-Linkage Region Growing \\
In centroid-linkage region growing, the image is scanned in some predetermined
manner, such as left-right, top-bottom. 
A pixel's value is compared with the mean of an already existing but not 
necessarily completed neighboring segment. 
If its value and the segment's mean value are close enough, then the pixel
is added to the segment and the segment's mean is updated.
If more than one region is close enough, then it is added to the closest
region.
However, if the means of the two competing regions are close enough, the two
regions are merged and the pixel is added to the merged region.
If no neighboring region has a close-enough mean, then a new segment is
established having the given pixel's value as its first member. \\
caption of Fig. 10.33 explains and the figure illustrates the geometry \\
=====Fig. 10.33===== \\
second image of the F-15 bulkhead \\
=====Fig. 10.34===== \\
one-pass centroid-linkage segmentation \\
=====Fig. 10.35===== \\
two-pass centroid segmentation of the bulkhead image \\
=====Fig. 10.36=====

\vspace{1cm}
10.4 Hybrid-Linkage Combinations \\
centroid linkage, hybrid linkage: can be combined to use relative strengths\\
single linkage strength: boundaries are spatially accurate \\
single linkage weakness: edge gaps result in excessive merging \\
centroid linkage strength: to place boundaries in weak gradient area \\
one-pass combined centroid- and hybrid-linkage segmentation of bulkhead \\
=====Fig. 10.37===== \\
two-pass combined centroid- and hybrid-linkage segmentation \\
=====Fig. 10.38=====

\vspace{1cm}
10.5 Spatial Clustering \\
spatial-clustering: combining clustering with spatial region growing \\
spatial-clustering: combine histogram-mode-seeking with region growing or \\
\hspace*{1cm} spatial-linkage technique 

\vspace{1cm}
10.6 Split and Merge \\
A splitting method for segmentation begins with the entire image as the
initial segment.
Then the method successively splits each of its current segments into
quarters if the segment is not homogeneous enough; that is, if the difference
between the largest and smallest gray level intensities is large.
A merging method starts with an initial segmentation and successively
merges regions that are similar enough. \\
segmentation tree: quadtree data structure (nonleaf node each has 4 children) \\
split-and-merge segmentation of the bulkhead image \\
=====Fig. 10.40=====

\vspace{1cm}
\noindent
image, segmentation, reconstruction based on least-squares-error polynomial \\
=====V. S. Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 3.23===== 

\vspace{1cm}
10.7 Rule-Based Segmentation \\
rule-based seg.: easier to try different concepts without reprogramming\\
knowledge in the system: not application domain specific \\
general-purpose, scene-independent knowledge about images, grouping criteria \\
allowable data entry types in the Nazif and Levine rule-based segmentation \\
=====Table 10.1===== \\
numerical descriptive features that can be associated with condition \\
=====Table 10.2===== \\
numerical spatial features that can be associated with condition \\
=====Table 10.3===== \\
logical features that can be associated with condition \\
=====Table 10.4===== \\
area, region, and line analyzer actions \\
=====Table 10.5===== \\
focus-of-attention and supervisor actions \\
=====Table 10.6===== \\
examples of rules from the Nazif and Levine system \\
=====Table 10.7=====

\vspace{1cm}
10.8 Motion-Based Segmentation \\
In time-varying image analysis the data are a sequence of images instead of
a single image.
One paradigm under which such a sequence can arise is with a stationary camera
viewing a scene containing moving objects.
In each frame of the sequence after the first frame, the moving objects appear
in different positions of the image from those in the previous frame.
Thus the motion of the objects creates a change in the images that can be used
to help locate the moving objects. \\
(a) image $t_i$ (b) image $t_j$ (c) difference image \\
=====Gonzalez, {\em Digital Image Processing,} Fig. 7.40=====

\vspace{1cm}
10.9 Summary \\
single-linkage region-growing schemes: simplest and most prone to errors \\
split-and-merge: large memory usage, excessively blocky region boundaries \\
=====joke=====














\vspace{1cm}
Project due Jan. 11, 1994 \\
Write a program to segment images with single-linkage region growing schemes
as in Section 10.3.1 and Figure 10.25. \\
Try values different by less than 5, 10, 20. \\
Scan from left to right, top to bottom, mark each pixel with region number. \\
Superimpose region boundaries on the original image.


\end{document}
