Page 309 -

Section 9.4 Segmentation, Clustering, and Graphs 277

r
d s and represents the location of the pixel and x , which has dimension d r and
i
represents everything else. Now we use two kernels and two smoothing parameters
in the density estimation procedure, writing
- (−d s/2) s . - (−d r /2) r .
(2π) x (2π) x
K(x; h s ,h r )= k k .
d s d r
h s h s h r h r
This means that we can balance spatial and appearance clustering and require, for
example, spatially tight clusters with a wide range of appearances, and so on. In
this case, the mean shift update equation changes slightly (Exercises).

s
r
For each pixel, p i , compute a feature vector x i =(x , x ) representing
i
i
spatial and appearance components, respectively.
Choose h s , h r the spatial (resp. appearance) scale of the smoothing kernel.
Cluster the x i using this data and mean shift clustering (Algorithm 9.6).

(Optional) Merge clusters with fewer than t min pixels with a neighbor;
the choice of neighbor is not significant, because the cluster is tiny.

The i’th pixel belongs to the segment corresponding to its cluster center
(for example, one could label the cluster centers 1 ...r,and then
identify segments by computing a map of the labels corresponding to pixels).

Algorithm 9.7: Mean Shift Segmentation.

9.4 SEGMENTATION, CLUSTERING, AND GRAPHS
Clustering algorithms deal with similarity between data items. Some algorithms
may summarize data items (for example, the cluster centers in the k-means algo-
rithm), but the core issue is similarity between data items. It might not be useful
to compare all pairs of data items; for example, there might be little real advantage
in comparing very distant image pixels directly. All this rather naturally suggests a
graph. Each data item would be a vertex. There would be a weighted edge between
all pairs of data items that could usefully be compared. The process of clustering
the data then becomes one of segmenting the graph into connected components.

9.4.1 Terminology and Facts for Graphs
We review terminology here very briefly, as it’s quite easy to forget.
• A graph is a set of vertices V and edges E that connect various pairs of
vertices. A graph can be written G = {V, E}. Each edge can be represented
by a pair of vertices—that is, E ⊂ V × V . Graphs are often drawn as a set
of points with curves connecting the points.

• The degree of a vertex is the number of edges incident on that vertex.