【Normalized Cuts and Image Segmentation】

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

Image segmentation is necessary in many applications. How to do a reasonable segmentation is a problem. Before the publication of this paper, there is a way called min cut. It treats segmentation as graph theory problem. In this view, the image is made up of a weighted undirected graph G=(V,E), where the nodes are points in the feature space, and the weight on the edge is the similarity between two nodes. So what we want is to find a ‘good’ cut of the graph, which means a ‘good’ segmentation. Min cut considers low level features like brightness, color, and texture. But its criteria favors cutting small sets of isolated nodes in the graph, which is not perceptual grouping. In this paper, a new method called normalize cut is published. It computes the cut cost as a fraction of the total edge connections to all the nodes in the graph. In addition, this can be transferred to a problem of solving eigenvalues and eigenvectors.

Given a partition of nodes of a graph, V, into two sets A and B, let x be an N = |V| dimensional indicator vector, x_i = 1 if node i is in A and -1 otherwise.
Let d(i) =Σ_j w(i,j) be the total connection from node i to all other nodes.
D is an N * N diagonal matrix with d on its diagonal, and W is an N * N symmetrical matrix with W(i, j)=w_ij

The problem becomes to solve (D-W)x=λDx for eigenvectors with the smallest eigenvalues. Use the eigenvector with the second smallest eigenvalue to segment the graph. If necessary, recursively do the subdivision.