Abstract—We consider data clustering problems where partial grouping is known a priori. We formulate such biased grouping problems as a constrained optimization problem, where structural properties of the data define the goodness of a grouping and partial grouping cues define the feasibility of a grouping. We enforce grouping smoothness and fairness on labeled data points so that sparse partial grouping information can be effectively propagated to the unlabeled data. Considering the normalized cuts criterion in particular, our formulation leads to a constrained eigenvalue problem. By generalizing the Rayleigh-Ritz theorem to projected matrices, we find the global optimum in the relaxed continuous domain by eigendecomposition, from which a near-global optimum to the discrete labeling problem can be obtained effectively. We apply our method to real image segmentation problems, where partial grouping priors can often be derived based on a crude spatial attentional map that binds places with common salient features or focuses on expected object locations. We demonstrate not only that it is possible to integrate both image structures and priors in a single grouping process, but also that objects can be segregated from the background without specific object knowledge.
1. A. Witkin, and J.M. Tenenbaum, "On the Role of Structure in Vision," Human and Machine Vision, Beck, Hope, and Rosenfeld, eds., pp. 481-543, New York: Academic Press, 1983.
2. C. Xu, D.L. Pham, and J.L. Prince, "Medical Image Segmentation Using Deformable Models," Handbook of Medical Imaging: Progress in Medical Image Processing and Analysis, pp. 129-174, SPIE, 2000.
3. D. Marr, Vision. Freeman, 1982.
4. S.C. Zhu, and A. Yuille, "Region Competition: Unifying Snakes, Region Growing, and Bayes/MDL for Multiband
Image Segmentation," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18,
no. 9, pp. 884-900, Sept. 1996.
5. J. Shi, and J. Malik, "Normalized Cuts and Image Segmentation," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, Aug. 2000.
6. S. Geman, and D. Geman, "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 6, no. 6, pp. 721-741, 1984.
7. H. Ishikawa, and D. Geiger, "Segmentation by Grouping Junctions," Proc. IEEE Conf. Computer Vision and Pattern Recognition, 1998.
8. S. Roy, and I.J. Cox, "A Maximum-Flow Formulation of the
$n\hbox{-}{\rm{Camera}}$ Stereo Correspondence Problem," Proc. Int'l Conf. Computer Vision, 1998.
9. Y. Boykov, O. Veksler, and R. Zabih, "Fast Approximate Energy Minimization via Graph Cuts," Proc. Int'l Conf. Computer Vision, 1999.
10. S. C. Zhu, "Embedding Gestalt Laws in Markov Random Fields," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 21, no. 11, Nov. 1999.
11. S.X. Yu, and J. Shi, "Multiclass Spectral Clustering," Proc. Int'l Conf. Computer Vision, 2003.
12. W. Gander, G.H. Golub, and U. von Matt, "A Constrained Eigenvalue Problem," Linear Algebra and Its Applications, vol. 114/115, pp. 815-839, 1989.
13. M. Meila, and J. Shi, "Learning Segmentation with Random Walk," Neural Information Processing Systems, 2001.
14. J. Malik, S. Belongie, T. Leung, and J. Shi, "Contour and Texture Analysis for Image Segmentation," Int'l J. Computer Vision, 2001.
15. D. Martin, C. Fowlkes, D. Tal, and J. Malik, "A Database of Human Segmented Natural Images and Its Application to Evaluating Segmentation
Algorithms and Measuring Ecological Statistics," Proc. Int'l Conf. Computer Vision, 2001.
16. A. Blake, and A. Zisserman, Visual Reconstruction. Cambridge, Mass. : MIT Press, 1987.
17. D. Mumford, and J. Shah, "Boundary Detection by Minimizing Functionals," Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 22-26, 1985.
18. A. Amir, and M. Lindenbaum, "Quantitative Analysis of Grouping Process," Proc. European Conf. Computer Vision, pp. 371-384, 1996.
19. Y. Gdalyahu, D. Weinshall, and M. Werman, "A Randomized Algorithm for Pairwise Clustering," Neural Information Processing Systems, pp. 424-430, 1998.
20. J. Puzicha, T. Hofmann, and J. Buhmann, "Unsupervised Texture Segmentation in a Deterministic Annealing Framework," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 8, pp. 803-818, Aug. 1998.
21. P. Perona, and W. Freeman, "A Factorization Approach to Grouping," Proc. European Conf. Computer Vision, pp. 655-670, 1998.
22. E. Sharon, A. Brandt, and R. Basri, "Fast Multiscale Image Segmentation," Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 70-77, 2000.
23. A. Robles-Kelly, and E. R. Hancock, "An EM-Like Algorithm for Motion Segmentation via Eigendecomposition," Proc. British Machine Vision Conf., pp. 123-132, 2001.
24. D.M. Greig, B.T. Porteous, and A.H. Seheult, "Exact Maximum A Posteriori Estimation for Binary Images," J. Royal Statistics Soc., Series B, vol. 51, no. 2, pp. 271-279, 1989.
25. P.A. Ferrari, A. Frigessi, and P. Gonzaga De SA, "Fast Approximate Maximum A Posteriori Restoration of Multicolour Images," J. Royal Statistics Soc., Series B, vol. 57, no. 3, pp. 485-500, 1995.
26. Y. Boykov, O. Veksler, and R. Zabih, "Markov Random Fields with Efficient Approximations," Proc. IEEE Conf. Computer Vision and Pattern Recognition, 1998.
27. V. Kolmogorov, and R. Zabih, "What Energy Functions Can Be Minimized via Graph Cuts?" Proc. European Conf. Computer Vision, 2002.
28. H. Ishikawa, "Exact Optimization for Markov Random Fields with Convex Priors," IEEE Proc. Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 10, pp. 1333-1336, Oct. 2003.
29. T. Joachims, "Transductive Inference for Text Classification Using Support Vector Machines," Proc. Int'l Conf. Machine Learning, 1999.
30. T. Jaakkola, M. Meila, and T. Jebara, "Maximum Entropy Discrimination," Neural Information Processing Systems, vol. 12, 1999.
31. K. Nigam, A. Kachites McCallum, S. Thrun, and T. Mitchell, "Text Classification from Labeled and Unlabeled Documents Using EM," Machine Learning, pp. 1-34, 1999.
32. M. Szummer, and T. Jaakkola, "Partially Labeled Classification with Markov Random Walks," Neural Information Processing Systems, vol. 14, 2001.
33. K. Wagstaff, C. Cardie, S. Rogers, and S. Schroedl, "Clustering with Instance-Level Constraints," Proc. Int'l Conf. Machine Learning, 2000.
34. K. Wagstaff, C. Cardie, S. Rogers, and S. Schroedl, "Constrained K-Means Clustering with Background Knowledge," Proc. Int'l Conf. Machine Learning, 2001.
35. S.X. Yu, and J. Shi, "Grouping with Bias," Technical Report CMU-RI-TR-01-22, Robotics Inst., Carnegie Mellon Univ., Pittsburgh,
Pa., July 2001.
36. S.X. Yu, and J. Shi, "Grouping with Bias," Neural Information Processing Systems, 2001.
37. A. Amir, and M. Lindenbaum, "A Generic Grouping Algorithm and Its Quantitative Analysis," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 2, pp. 168-185, Feb. 1998.