Normalized Cuts and Image Segmentation

"Normalized Cuts and Image Segmentation", Jianbo Shi and Jitendra Malik, Trans. PAMI 2000

The paper proposes a general framework for image segmentation. Generally, the result of each partition method is affected by the coherence of brightness, color, texture, or motion, and the hierarchical partition should form a tree structure. Therefore, the authors generate a graph theoretic formulation of grouping.

The grouping algorithm consists of several steps:
1.Given an image, set up a weighted graph, and set the weight on the edge according to the similarity.
2.solve the equation for eigenvectors with the smaller eigenvalues.
3.Here they use the eigenvector with the second smallest eigenvalue to bipartition the graph and solve the normalized cut problem.
4.Recursively partition if necessary.

If necessary, one can use all of the to eigenvectors to obtain a K-way partition and follow the modified algorithm.
The computational approach that they have developed uses matrix theory and linear algebra which are based on the concepts from spectral graph theory.