We propose a unified approach for bottom-up hierarchical image segmentation and object candidate generation for recognition, called Multiscale Combinatorial Grouping (MCG). The approach consists of three main components: (1) a fast normalized cuts algorithm that significantly accelerates the computation of the segmentation hierarchy, (2) a high-performance hierarchical segmenter that makes effective use of multiscale information, and (3) a grouping strategy that combines multiscale regions into highly-accurate object candidates by exploring efficiently their combinatorial space. We also present Single-scale Combinatorial Grouping (SCG), a faster variant producing competitive proposals in under five seconds per image. Our approach achieves state-of-the-art results on BSDS500, SegVOC12, SBD, and COCO datasets for contours, hierarchical regions, and object proposals.

Object proposal generation has become a critical preprocessing step in modern object detection pipelines. Methods like Selective Search and CPMC generate category-independent proposals that reduce the search space from millions of sliding windows to thousands of candidates. However, existing approaches face a trade-off between proposal quality (recall and localization accuracy) and computational cost. Simultaneously, hierarchical image segmentation has proven valuable for capturing structure at multiple granularities, but single-scale methods miss objects that are best captured at different scales. We propose to unify these two tasks — hierarchical segmentation and object proposal generation — through a multiscale combinatorial grouping strategy that leverages the complementary information provided by different scales.

Object proposal methods can be broadly categorized into grouping-based approaches (e.g., Selective Search, which greedily merges superpixels) and window scoring approaches (e.g., Objectness, EdgeBoxes, which evaluate candidate windows). Grouping-based methods typically produce higher-quality proposals with better boundary adherence, while window scoring methods are generally faster. For hierarchical segmentation, the Ultrametric Contour Map (UCM) framework based on gPb (globalized probability of boundary) is considered the gold standard, but its O(n^1.5) complexity limits scalability. Our work builds upon the UCM framework but introduces a fast normalized cuts algorithm and multiscale fusion that dramatically improves both speed and quality.

The normalized cuts criterion is fundamental to spectral segmentation but requires solving a generalized eigenvector problem that scales poorly with image size. We propose a fast approximation based on a multi-resolution hierarchy: the image is first over-segmented into superpixels at a coarse level, then the normalized cuts eigenvectors are computed on the reduced graph of superpixels rather than on the full pixel graph. This reduces the matrix dimension from millions of pixels to thousands of superpixels, yielding a speedup of orders of magnitude while preserving segmentation quality. The coarse eigenvectors are then interpolated back to the full resolution to produce the final segmentation hierarchy.

Single-scale segmentation inevitably misses structures that are better captured at different resolutions. A small object may be merged into the background at a coarse scale, while fine-grained boundaries may be lost at lower resolutions. Our multiscale hierarchical segmenter addresses this by computing independent segmentation hierarchies at multiple image scales and then aligning and fusing them into a single unified hierarchy. The fusion strategy preserves the strengths of each scale: fine scales contribute precise boundaries, while coarse scales provide better grouping of large regions. The resulting hierarchy captures structure at all granularities — from small parts to entire objects — in a single coherent representation.

Given the multiscale segmentation hierarchy, we generate object proposals by combinatorially grouping adjacent regions from the hierarchy. The naive approach of enumerating all possible region combinations is computationally infeasible due to exponential growth. We address this by designing an efficient search strategy that ranks region combinations using learned features such as shape, size, boundary strength, and region similarity. The top-ranked combinations are retained as object candidates. This approach is fundamentally different from greedy merging (as in Selective Search): by exploring the combinatorial space more thoroughly, we produce proposals with significantly better localization accuracy, particularly for objects with complex shapes that require non-local grouping decisions.

We evaluate MCG comprehensively across four benchmarks. On BSDS500 for boundary detection, MCG achieves the best F-measure among all methods. For hierarchical segmentation on SegVOC12, MCG outperforms gPb-UCM while being significantly faster. For object proposals on PASCAL VOC and SBD, MCG achieves the highest recall at high IoU thresholds (>0.7), demonstrating superior localization accuracy. On COCO, MCG also sets a new state of the art. When integrated into the R-CNN detection pipeline, MCG proposals yield higher detection mAP than Selective Search proposals due to better boundary adherence. The faster SCG variant runs in under 5 seconds per image while maintaining competitive quality, making it suitable for large-scale applications.

We have presented Multiscale Combinatorial Grouping (MCG), a unified framework for bottom-up segmentation and object proposal generation. By combining a fast normalized cuts algorithm, multiscale hierarchical segmentation, and combinatorial grouping, MCG produces object proposals with state-of-the-art localization accuracy while maintaining practical computational cost. The key principle is that leveraging the rich structure of multiscale segmentation hierarchies through combinatorial exploration yields proposals that are fundamentally more accurate than those produced by greedy merging strategies. MCG provides a strong foundation for object detection and semantic segmentation systems that rely on bottom-up region proposals.