Segmentation Given Partial Grouping Constraints
|
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] 173 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, pp. 884-900, 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, pp. 125-131, 1998.
[8] S. Roy and I. Cox, A Maximum-Flow Formulation of the N-Camera Stereo Correspondence Problem IEEE Proc. Int'l Conf. Computer Vision, pp. 492-499, 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. Eighth Int'l Conf. Computer Vision, pp. 416-424, 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] T. Hofmann, J. Puzicha, and J.M. Buhmann, “Unsupervised Texture Segmentation in a Deterministic Annealing Framework,” IEEE Trans. Pattern Analysis and Machince Intelligence, vol. 20, pp. 803-818, 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 CS Conf. Computer Vision and Pattern Recognition, 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, pp. 648-655, 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 ConvexPriors IEEE 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 Tran. Pattern Analysis and Machine Intelligence, vol. 20, no. 2, pp. 168-185, Feb. 1998.
Index Terms:
Grouping, image segmentation, graph partitioning, bias, spatial attention, semisupervised clustering, partially labeled classification.
Citation:
Stella X. Yu, Jianbo Shi, "Segmentation Given Partial Grouping Constraints," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 2, pp. 173-183, Jan. 2004, doi:10.1109/TPAMI.2004.1262179
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb