Image Segmentation

Spectral Graph Cut from a Filtering Point of View

Chengxi Ye Yuxu Lin Mingli Song Chun Chen David W. Jacobs

University of Maryland Zhejiang University

We analyze spectral graph theory based image segmentation algorithms and show there is a natural connection with edge preserving filtering. Based on this connection we show that the normalized cut algorithm is equivalent to repeated application of bilateral filtering. Then, using this interpretation we present and implement a fast normalized cut algorithm. Experiments show that our implementation can solve the original optimization problem with a 10x-100x speedup. Furthermore, we show this connection makes possible a new model for segmentation called conditioned normalized cut that easily incorporates image patches in color and demonstrate how this problem can be solved with edge preserving filtering.

Full manuscript: http://arxiv.org/abs/1205.4450v2

The manuscript was submitted to PAMI in 2012/10.