Segmentation-based Object Categorization - Segmentation Using Normalized Cuts - The Ncut Algorithm

The Ncut Algorithm

Let:

Also, let D be an diagonal matrix with on the diagonal, and let be an symmetrical matrix with .

After some algebraic manipulations, we get:

subject to the constraints:

• , for some constant

Minimizing subject to the constraints above is NP-hard. To make the problem tractable, we relax the constraints on, and allow it to take real values. The relaxed problem can be solved by solving the generalized eigenvalue problem for the second smallest generalized eigenvalue.

The partitioning algorithm:

1. Given a set of features, set up a weighted graph, compute the weight of each edge, and summarize the information in and .
2. Solve for eigenvectors with the smallest eigenvalues.
3. Use the eigenvector with the smallest eigenvalue to bipartition the graph (e.g. grouping according to sign).
4. Decide if the current partition should be subdivided.
5. Recursively partition the segmented parts, if necessary.