A hierarchical image clustering cosegmentation framework

Edward Kim, Hongsheng Li, Xiaolei HuangCVPR 2012 · OpenReview

Abstract

Given the knowledge that the same or similar objects appear in a set of images, our goal is to simultaneously segment that object from the set of images. To solve this problem, known as the cosegmentation problem, we present a method based upon hierarchical clustering. Our framework first eliminates intra-class heterogeneity in a dataset by clustering similar images together into smaller groups. Then, from each image, our method extracts multiple levels of segmentation and creates connections between regions across levels to establish intra-image multi-scale constraints. Next, we design an efficient method to create inter-image relationships between image regions across a cluster. Given these connections, we perform a segmentation of the group of images into foreground and background regions. We demonstrate state-of-the-art accuracy on standard datasets and robustness on real-world data.

Introduction

Image segmentation is a fundamental task in computer vision, yet it often falls between the cracks of fully supervised and unsupervised learning. Unsupervised methods frequently fail to identify semantically meaningful objects, while fully supervised methods require labor-intensive pixel-level annotations. Cosegmentation offers a middle ground by utilizing "weakly supervised" data—sets of images known to contain instances of the same object class without explicit location labels.

The primary challenge in cosegmentation is intra-class heterogeneity. Objects within the same category (e.g., "dogs") can vary significantly in appearance due to breed, pose, lighting, and complex backgrounds. This paper introduces a hierarchical framework designed to handle such diversity while maintaining computational efficiency.

Methodology

The proposed framework follows a structured four-stage pipeline to achieve robust cosegmentation.

Overview of the proposed four-stage cosegmentation framework, from initial clustering to final simultaneous segmentation.

1. Clustering for Heterogeneity

To mitigate the noise introduced by diverse image sets, the system first groups the dataset into smaller, homogeneous clusters (typically 10–20 images). This is achieved using global features such as Color pyramids, HOG textures, and SURF descriptors. By comparing only similar images, the algorithm ensures more reliable object matching.

2. Hierarchical Superpixel Representation

Each image is decomposed into a hierarchy of four layers, ranging from fine-grained (300–500 regions) to coarse (5–15 regions). This multi-scale approach allows the model to capture both fine details and high-level object structure.

3. Constrained Graph Construction

A massive graph is constructed to represent the relationships within and between images:

  • Intra-image edges: Connect neighboring superpixels within the same hierarchical layer.
  • Hierarchical constraints: Ensure consistency across scales; if a coarse "parent" region is labeled as foreground, its "child" regions in finer layers are constrained to follow.
  • Inter-image edges: Establish connections between regions in different images. To maintain efficiency, these connections are only formed at the coarsest level of the hierarchy.
Graph construction illustrating the integration of intra-image hierarchical constraints and inter-image connections for spectral optimization.

4. Spectral Optimization

The cosegmentation problem is formulated as a normalized cut on this constrained graph. The authors employ a specialized "projector" matrix ($Q$) to solve the constrained eigenvalue problem efficiently. This allows for the simultaneous determination of the optimal foreground/background split across all images in a cluster.

Experimental Results

The framework was rigorously evaluated on the MSRC and ImageNet benchmarks. Performance was measured using the Jaccard coefficient, which quantifies the overlap between predicted segments and ground truth.

  • MSRC Performance: The multi-image approach significantly outperformed single-image baselines. For the "Sheep" category, the framework achieved a 62.1% overlap score, compared to 41.7% for standard Multiscale Normalized Cut (MNcut).
  • ImageNet Robustness: On challenging real-world images, the method remained competitive with state-of-the-art techniques like CoSand. For instance, it achieved a 52.5% score on the Pineapple category.
  • Efficiency: The hierarchical approach drastically reduces computational complexity. Once features are pre-computed, cosegmenting a group of 10 images takes approximately 30–60 seconds.

Discussion and Conclusion

A key insight from this work is the "Sign Paradox": for highly distinct objects like street signs, single-image segmentation can sometimes outperform cosegmentation, as additional images might introduce more noise than useful context.

While the framework is robust, it relies on computationally expensive offline feature extraction and hierarchical segmentation. Future work could explore extending this binary (foreground/background) model to multi-class cosegmentation and improving the sensitivity of the initial clustering stage. Overall, the hierarchical constraints and coarse-to-fine propagation provide a powerful mechanism for scalable and accurate object discovery in image collections.

Summary updated

Abstract

Given the knowledge that the same or similar objects appear in a set of images, our goal is to simultaneously segment that object from the set of images. To solve this problem, known as the cosegmentation problem, we present a method based upon hierarchical clustering. Our framework first eliminates intra-class heterogeneity in a dataset by clustering similar images together into smaller groups. Then, from each image, our method extracts multiple levels of segmentation and creates connections between regions (e.g. superpixel) across levels to establish intra-image multi-scale constraints. Next we take advantage of the information available from other images in our group. We design and present an efficient method to create inter-image relationships, e.g. connections between image regions from one image to all other images in an image cluster. Given the intra & inter-image connections, we perform a segmentation of the group of images into foreground and background regions. Finally, we compare our segmentation accuracy to several other state-of-the-art segmentation methods on standard datasets, and also demonstrate the robustness of our method on real world data.
BibTeX
@inproceedings{kim2012hierarchical,
  author = {Edward Kim and Hongsheng Li and Xiaolei Huang},
  title = {{A hierarchical image clustering cosegmentation framework}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2012},
  url = {https://openreview.net/forum?id=PKnS6W4wid},
}
Figure