Page 312 -

Section 9.4 Segmentation, Clustering, and Graphs 280

Start with a set of clusters C i , one cluster per pixel.
Sort the edges in order of non-decreasing edge weight, so that
w(e 1 ) ≥ w(e 2 ) ≥ ... ≥ w(e r ).

For i =1 to r
If the edge e i lies inside a cluster
do nothing
Else
One end is in cluster C l and the other is in cluster C m
If diff(C l, C m ) ≤ MInt(C l , C m )
Merge C l and C m to produce a new set of clusters.

Report the remaining set of clusters.

Algorithm 9.8: Agglomerative Clustering with Graphs.

local texture representations of Section 6.1), then use the length of the difference
vector; or we could use a weighted sum of all these distances.
We will start with every pixel forming a cluster, then merge clusters until
there is no need to continue. To do this, we need some notion of the distance
between two clusters. Each cluster is a component of the graph, formed from all
the vertices (pixels) in the cluster, and all the edges that start and end inside the
cluster. Then the difference between two components is the minimum weight edge
connecting two components. Write C 1 , C 2 for the two components, E for the edges,
and w(v 1 ,v 2 ) for the weight of the edge joining v 1 and v 2 . Then, we have

diff(C 1 , C 2 )= min w(v1,v2).
v 1 ∈C 1 ,v 2 ∈C 2 ,(v 1 ,v 2 )∈E
It is also helpful to know how coherent a particular cluster is. This will help us
stop clustering. We define the internal difference of a component to be the largest
weight in the minimum spanning tree of the component. Write M(C)= {V C ,E M }
for the minimum spanning tree of C. Then, we have

int(C)= max w(e).
e∈M(C)
We will start with a set of clusters (or segments) that consists of all the pixels,
one cluster per pixel. We then merge clusters iteratively. We do so by sorting
all edges in order of non-decreasing edge weight. For each edge, starting with the
smallest, we consider the clusters at either end of the edge. If both ends of the
edge lie in the same cluster, there is nothing to do. If there are distinct clusters
at each end, then we could merge them. We do so when the edge weight is small
compared to the internal difference of each of the clusters (this requires some care
for small clusters; details below). We now proceed through all the edges, merging
as necessary. The final segmentation is the set of clusters once the last edge has
been visited (Algorithm 9.8).