Normalized Cuts and Image Segmentation

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.

REFERENCES

• 1: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 2: Andrew Blake , Andrew Zisserman, Visual reconstruction, MIT Press, Cambridge, MA, 1987
• 3: R.B. Boppana, “Eigenvalues and Graph Bisection: An Average-Case Analysis,” <i>Proc. 28th Symp. Foundations of Computer Science,</i> pp. 280-285, 1987.
• 4: J. Cheeger, “A Lower Bound for the Smallest Eigenvalue of the Laplacian,” <i>Problems in Analysis,</i> R.C. Gunning, ed., pp. 195-199, Princeton Univ. Press, 1970.
• 5: F.R.K. Chung, <i>Spectral Graph Theory.</i> Am. Math. Soc., 1997.
• 6: I.J. Cox S.B. Rao and Y. Zhong, “Ratio Regions: A Technique for Image Segmentation,” <i>Proc. 13th Int'l Conf. Pattern Recognition,</i> 1996.
• 7: W.E. Donath and A.J. Hoffman, “Lower Bounds for the Partitioning of Graphs,” <i>IBM J. Research and Development,</i> pp. 420-425, 1973.
• 8: R. Van Driessche , D. Roose, An improved spectral bisection algorithm and its application to dynamic load balancing, Parallel Computing, v.21 n.1, p.29-48, Jan. 1995 [doi>10.1016/0167-8191(94)00059-J]
• 9: M. Fiedler, “A Property of Eigenvectors of Nonnegative Symmetric Matrices and Its Applications to Graph Theory,” <i>Czech. Math. J.,</i> vol. 25, no. 100, pp. 619-633, 1975.
• 10: S. Geman and D. Geman, “Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images,” <i>IEEE Trans. Pattern Analysis and Machine Intelligence,</i> vol. 6, pp. 721-741, Nov. 1984.
• 11: G.H. Golub and C.F. Van Loan, <i>Matrix Computations.</i> John Hopkins Press, 1989.
• 12: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 13: K. Fukunaga S. Yamada H.S. Stone and T. Kasai, “A Representation of Hypergraphs in the Euclidean Space,” <i>IEEE Trans. Computers,</i> vol. 33, no. 4, pp. 364-367, Apr. 1984.
• 14: Y.G. Leclerc, “Constructing Simple Stable Descriptions for Image Partitioning,” <i>Int'l J. Computer Vision,</i> vol. 3, pp. 73-102, 1989.
• 15: Jitendra Malik , Serge Belongie , Jianbo Shi , Thomas Leung, Textons, Contours and Regions: Cue Integration in Image Segmentation, Proceedings of the International Conference on Computer Vision-Volume 2, p.918, September 20-25, 1999
• 16: J. Malik and P. Perona, “Preattentive Texture Discrimination with Early Vision Mechanisms,” <i>J. Optical Soc. Am.,</i> 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,” <i>Comm. Pure Math.,</i> pp. 577-684, 1989.
• 18: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
• 19: Sudeep Sarkar , Kim L. Boyer, Quantitative Measures of Change based on Feature Organization: Eigenvalues and Eigenvectors, Proceedings of the 1996 Conference on Computer Vision and Pattern Recognition (CVPR '96), p.478, June 18-20, 1996
• 20: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.731, June 17-19, 1997
• 21: Jianbo Shi , Jitendra Malik, Motion Segmentation and Tracking Using Normalized Cuts, Proceedings of the Sixth International Conference on Computer Vision, p.1154, January 04-07, 1998
• 22: Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]
• 23: Daniel A. Spielman , Shang-Hua Teng, Disk packings and planar separators, Proceedings of the twelfth annual symposium on Computational geometry, p.349-358, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237404]
• 24: M. Wertheimer, “Laws of Organization in Perceptual Forms (partial translation),” <i>A Sourcebook of Gestalt Psycychology,</i> W.B. Ellis, ed., pp. 71-88, Harcourt, Brace, 1938.
• 25: Z. Wu , R. Leahy, An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.11, p.1101-1113, November 1993 [doi>10.1109/34.244673]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Experimentation, Human Factors, Measurement, Theory

Keywords:
Grouping, image segmentation, graph partitioning.