
Segmentation Given Partial Grouping Constraints

Stella X. Yu and Jianbo Shi

IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):17383, 2004

Paper

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 RayleighRitz theorem to projected matrices, we find the global optimum in the relaxed continuous domain by eigendecomposition, from which a nearglobal 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.

Keywords

grouping, image segmentation, graph partitioning, bias, spatial attention, semisupervised clustering, partially labeled classification
