Segmentation Methodology

The normalized segmentation method described by Shi and Malik (2000) is designed to look for clusters of pixels with similar intensity. To do this, a weight matrix is created that relates each pixel to every other pixel within a local neighborhood. The strongest weights are given to pixels of similar intensity and close proximity. The method then seeks to partition the image into two groups, A and B, by minimizing the normalized cut:  

$${\rm N_{cut} =\ {cut\over total_A } + {cut\over total_B} },$$ (1)

where cut is the sum of the weights cut by the partition. total_A is the sum of all weights in Group A, and total_B is the sum of all weights in Group B. Normalizing the cut by the sum of all the weights in each group prevents the partition from selecting overly small groups of nodes.

The minimum of N_cut can be found by solving the generalized eigensystem:  

$$({\bf D} - {\bf W})\bf y =\lambda {\bf D}\bf y,$$ (2)

created from weight matrix (${\bf W}$) and a diagonal matrix (${\bf D}$), with each value on the diagonal being the sum of each column of ${\bf W}$. The eigenvector (${\bf y}$) with the second smallest eigenvalue ${\lambda}$) is used to partition the image by taking all values greater than zero to be in one group, and its complement to be in the other.