Page 274 -

5.2 Split and merge 253

(a) (b) (c)

Figure 5.14 Graph-based merging segmentation (Felzenszwalb and Huttenlocher 2004b) c 2004 Springer: (a)
input grayscale image that is successfully segmented into three regions even though the variation inside the smaller
rectangle is larger than the variation across the middle edge; (b) input grayscale image; (c) resulting segmentation
using an N 8 pixel neighborhood.

between these regions is defined as the minimum weight edge connecting the two regions,
Dif (R 1 ,R 2 ) = min w(e). (5.21)
e=(v 1 ,v 2 )|v 1 ∈R 1 ,v 2 ∈R 2
Their algorithm merges any two adjacent regions whose difference is smaller than the mini-
mum internal difference of these two regions,
MInt(R 1 ,R 2 ) = min(Int(R 1 )+ τ(R 1 ), Int(R 2 )+ τ(R 2 )), (5.22)

where τ(R) is a heuristic region penalty that Felzenszwalb and Huttenlocher (2004b) set to
k/|R|, but which can be set to any application-specific measure of region goodness.
By merging regions in decreasing order of the edges separating them (which can be effi-
ciently evaluated using a variant of Kruskal’s minimum spanning tree algorithm), they prov-
ably produce segmentations that are neither too fine (there exist regions that could have been
merged) nor too coarse (there are regions that could be split without being mergeable). For
fixed-size pixel neighborhoods, the running time for this algorithm is O(N log N), where N
is the number of image pixels, which makes it one of the fastest segmentation algorithms
(Paris and Durand 2007). Figure 5.14 shows two examples of images segmented using their
technique.

5.2.5 Probabilistic aggregation
Alpert, Galun, Basri et al. (2007) develop a probabilistic merging algorithm based on two
cues, namely gray-level similarity and texture similarity. The gray-level similarity between
regions R i and R j is based on the minimal external difference from other neighboring regions,
+
+
σ + = min(Δ , Δ ), (5.23)
local i j
+
where Δ = min k |Δ ik | and Δ ik is the difference in average intensities between regions R i
i
and R k . This is compared to the average intensity difference,
−
Δ +Δ −
j
i
σ − = , (5.24)
local
2