Image/Video Segmentation: Current Status, Trends, and Challenges - Video Segmentation and Its Applications - page 9

Fig. 1.3 An example of Ncut-based segmentation. ( a ) Original image flower .( b ) The constructed
graph. ( c ) Segmentation results with N = 2and N = 10

=( , )

(1) Map an image into a weighted graph G with the nodes corresponding

to pixels and weight on the edges setting by the affinity of pairwise pixels.
(2) Construct affinity matrix W and degree matrix D.
(3) Solve the generalized eigenvalue system with the second smallest eigenvector.
(4) Use the eigenvector to partition the graph.
(5) After the stability examination, recursively repartition the segmented parts if
necessary.

V E

Figure 1.3 shows an example of Ncut-based image segmentation. The original
image is shown in Fig. 1.3 a. Since this method is performed in unsupervised manner,
there is no user's input for the known labels. The graph is described in Fig. 1.3 b,
where the dashed line denotes a cut to separate this graph into two parts. Figure 1.3 c
shows the segmentation results when N

= 2and N = 10. It can be seen that the

original image is segmented into many regions.

1.2.1.4 Efficient Graph Segmentation Algorithm

Another graph-based segmentation algorithm can be found in [ 24 ], which computes
image segmentation based on pairwise region comparison in unsupervised manner.
The boundary between two regions is measured by a predicate based on a graph-
based representation of the image. It can be computed using the minimum weight
edge between two regions. Although this algorithm makes greedy decisions, it runs
in time nearly linear to the number of graph edges (e.g., O time for m graph

edges) and is also fast in practice. Different segmentation results can be achieved by

( m log m )