| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Normalized Cuts and Image Segmentation
August 2000 (vol. 22 no. 8)
pp. 888-905
Abstract—We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, our approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and propose a novel global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. We have applied this approach to segmenting static images, as well as motion sequences, and found the results to be very encouraging.
[1] N. Alon, “Eigenvalues and Expanders,” Combinatorica, vol. 6, no. 2, pp. 83-96, 1986.
[2] A. Blake and A. Zisserman, Visual Reconstruction. MIT Press, 1987.
[3] R.B. Boppana, “Eigenvalues and Graph Bisection: An Average-Case Analysis,” Proc. 28th Symp. Foundations of Computer Science, pp. 280-285, 1987.
[4] J. Cheeger, “A Lower Bound for the Smallest Eigenvalue of the Laplacian,” Problems in Analysis, R.C. Gunning, ed., pp. 195-199, Princeton Univ. Press, 1970.
[5] F.R.K. Chung, Spectral Graph Theory. Am. Math. Soc., 1997.
[6] I.J. Cox, S.B. Rao, and Y. Zhong, “Ratio Regions: A Technique for Image Segmentation,” Proc. Int'l Conf. Pattern Recognition, vol. 2, pp. 557-564, 1996.
[7] W.E. Donath and A.J. Hoffman, “Lower Bounds for the Partitioning of Graphs,” IBM J. Research and Development, pp. 420-425, 1973.
[8] R. Van Driessche and D. Roose, "An Improved Spectral Bisection Algorithm and Its Application to Dynamic Load Balancing," Parallel Computing, vol. 21, pp. 29-48, 1995.
[9] M. Fiedler, “A Property of Eigenvectors of Nonnegative Symmetric Matrices and Its Applications to Graph Theory,” Czech. Math. J., vol. 25, no. 100, pp. 619-633, 1975.
[10] S. Geman and D. Geman, “Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 6, pp. 721-741, Nov. 1984.
[11] G.H. Golub and C.F. Van Loan, Matrix Computations. John Hopkins Press, 1989.
[12] A.K. Jain and R.C. Dubes, Algorithms for Clustering Data. Englewood Cliffs, N.J.: Prentice Hall, 1988.
[13] K. Fukunaga, S. Yamada, H.S. Stone, and T. Kasai, “A Representation of Hypergraphs in the Euclidean Space,” IEEE Trans. Computers, vol. 33, no. 4, pp. 364-367, Apr. 1984.
[14] Y.G. Leclerc, “Constructing Simple Stable Descriptions for Image Partitioning,” Int'l J. Computer Vision, vol. 3, pp. 73-102, 1989.
[15] J. Malik, S. Belongie, J. Shi, and T. Leung, “Textons, Contours and Regions: Cue Combination in Image Segmentation,” Proc. Int'l Conf. Computer Vision, 1999.
[16] J. Malik and P. Perona, “Preattentive Texture Discrimination with Early Vision Mechanisms,” J. Optical Soc. Am., vol. 7, no. 2, pp. 923-932, May 1990.
[17] D. Mumford and J. Shah, “Optimal Approximations by Piecewise Smooth Functions, and Associated Variational Problems,” Comm. Pure Math., pp. 577-684, 1989.
[18] A. Pothen, H. Simon, and K. Liou, "Partitioning Sparse Matrices with Eigenvectors of Graphs," SIAM J. Matrix Analysis and Application, vol. 11, pp. 430-352, July 1990.
[19] S. Sarkar and K.L. Boyer, “Quantitative Measures of Change Based on Feature Organization: Eigenvalues and Eigenvectors,” Proc. IEEE CS Conf. Computer Vision and Pattern Recognition, pp. 478-483, June 1996.
[20] J. Shi and J. Malik, “Normalized Cuts and Image Segmenation,” Proc. IEEE CS Conf. Computer Vision and Pattern Recognition, pp. 731-737, June 1997.
[21] J. Shi and J. Malik, “Motion Segmentation and Tracking Using Normalized Cuts,” Proc. Int'l Conf. Computer Vision, 1998.
[22] A.J. Sinclair and M.R. Jerrum, “Approximative Counting, Uniform Generation and Rapidly Mixing Markov Chains,” Information and Computation, vol. 82, pp. 93-133, 1989.
[23] D.A. Spielman and S.H. Teng, “Disk Packings and Planar Separators,” Proc. 12th ACM Symp. Computational Geometry, May 1996.
[24] M. Wertheimer, “Laws of Organization in Perceptual Forms (partial translation),” A Sourcebook of Gestalt Psycychology, W.B. Ellis, ed., pp. 71-88, Harcourt, Brace, 1938.
[25] Z. Wu and R. Leahy, “An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, no. 11, pp. 1,101-1,113, Nov. 1993.
Index Terms:
Grouping, image segmentation, graph partitioning.
Citation:
Jianbo Shi, Jitendra Malik, "Normalized Cuts and Image Segmentation," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, Aug. 2000, doi:10.1109/34.868688
