This is a joint work with J. Malik, S. Yu, M. Maila.

I will describe an approach for solving image segmentation and grouping problem with Normalized Cuts, which exploits the connections between graph partitioning, eigen-value system, and Markov Random Walk.

In our approach, image segmentation is formulated as a graph partition problem where the pixels are the graph nodes, and pair-wise similarity measures between pixels are the graph edge weights. A global graph partitioning criteria, called normalized cut, is proposed for finding minimally connected subgroups. This criterion also ensures that within group similarity is maximized. While the Normalized Cut is NP-hard, we show that in the continuous value space, it can be solved exactly by computing a generalized Eigen-value problem. Results of this algorithm on a large number of real images with simple brightness, texture and motion cues have been very encouraging.

In this talk, I will highlight two current research areas where we are building on this equivalence between the normalized graph cuts and generalized eigen-system for solving higher order vision problems. In the first area, we show how more complex pair-wise graph relationships such as directed relationships, which arise from object occlusion for example, can be encoded in this system. We show the solution can be found by solving a eigen-value problem in the complex value domain. In the second area, we have developed a probabilistic interpretation of the Normalized Cuts criterion in terms of Markov Random Walk. We show how this interpretation can lead to an algorithm for supervised learning based image segmentation.