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.
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.
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