[Reading] Normalized Cuts and Image Segmentation

The approach of this paper aims at extracting the global impression of an image and provides a hierarchical description of it. It is most related to the graph theoretic formulation of grouping. By treating the grouping problem (image segmentation) as a graph partitioning problem, this paper proposed the normalized cut criteria for segmenting the graph.

Normalized cut is an unbiased measure of disassociation between subgroups of a graph and it has the nice property that minimizing normalized cut leads directly to maximizing the normalized association, which is an unbiased measure for
total association within the subgroups. it also avoids the problem that unnatural bias for partitioning out small sets of points.

minimizing normalized cut exactly is NP-complete. This paper shows that, when it embed the normalized cut problem in the real value domain, an approximate
discrete solution can be found efficiently. it is formulated as a
generalized eigenvalue problem.