Abstract: Object proposals have recently fueled the progress in detection performance. These proposals aim to provide category-agnostic localizations for all objects in an image. One way to generate proposals is to perform parametric min-cuts over seed locations. This paper demonstrates that standard parametric-cut models are ineffective in obtaining medium-sized objects, which we refer to as the middle child problem. We propose a new energy minimization framework incorporating geodesic distances between segments which solves this problem. In addition, we introduce a new superpixel merging algorithm which can generate a small set of seeds that reliably cover a large number of objects of all sizes. We call our method POISE - "Proposals for Objects from Improved Seeds and Energies." POISE enables parametric min-cuts to reach their full potential. On PASCAL VOC it generates ~2,640 segments with an average overlap of 0.81, whereas the closest competing methods require more than 4,200 proposals to reach the same accuracy. We show detailed quantitative comparisons against 5 state-of-the-art methods on PASCAL VOC and Microsoft COCO segmentation challenges.
Introduction: The Middle Child Problem
In computer vision, "object proposals" are candidate regions likely to contain an object. Generating a small, high-quality set of these regions is a crucial first step for many detection and segmentation pipelines.
A popular technique for this is Parametric Min-Cut (PMC), which treats an image as a graph and finds optimal "cuts" to separate foreground from background. However, the authors observe a systematic failure: PMC often produces a "nested" sequence of segments that jump from tiny regions (near the starting seed) directly to the entire image. The salient, medium-sized objects in between—the "middle children"—are frequently ignored. This isn't a matter of bad parameter tuning; it's an intrinsic property of the standard energy functions used in these models.
Methodology: The POISE Framework
The authors propose two main innovations to solve this, collectively called POISE (Proposals for Objects from Improved Seeds and Energies):
- Geodesically Guided PMC: To prevent the algorithm from skipping medium sizes, they modify the energy function. After finding a segment at a certain parameter level, they calculate the geodesic distance (distance following image contours) from that segment to the rest of the image. They then "bias" the next optimization step to favor regions that are geodesically close to the previous cut. This ensures the sequence of segments grows incrementally and captures objects of all scales.
- Adaptive Superpixel Merging: Good proposals start with good "seeds" (starting points). The authors developed a new merging algorithm based on the classic Felzenszwalb-Huttenlocher method but added an adaptive thresholding strategy. This ensures that more seeds are generated in complex, high-variation regions and fewer in uniform areas, leading to a more efficient and diverse set of starting points.
Key Insights and Results
The "Middle Child Problem" exists because standard energy landscapes have "steep" transitions. Once the algorithm decides to expand beyond a small seed, the lowest energy state often involves swallowing the entire image unless the object boundaries are exceptionally strong. By modifying the unaries (pixel-wise costs) using geodesic distances, the authors maintain the "nesting property" while forcing the algorithm to explore the middle ground.
Performance Benchmarks
The authors evaluated POISE on PASCAL VOC 2012 and Microsoft COCO. Key findings include:
- Superior Recall: On PASCAL VOC, POISE generates ~2,640 segments with an average overlap of 0.81. The closest competitors required over 4,200 proposals to reach the same level of accuracy.
- Middle-Size Mastery: Quantitative analysis shows that POISE significantly outperforms all other methods specifically for objects between 400 and 4,000 pixels in size.
- Efficiency: The algorithm is efficient, with a multi-threaded run-time of approximately 3.5 seconds to generate 1,000 proposals.
- Generalization: POISE outperformed early CNN-based proposal methods (like Pinheiro et al.'s DeepMask) in terms of boundary quality and spatial accuracy, despite not being explicitly trained on the target categories.
Conclusion and Limitations
While POISE dominates the medium-size regime, it is slightly less effective than the "RIGOR" method for extremely large objects (>60,000 pixels). Additionally, the method relies on high-quality probabilistic boundary maps; if the boundary detector fails, the geodesic distance calculation may "leak," leading to poor segments. However, POISE demonstrates that guiding optimization with geodesic distances enables parametric min-cuts to reach their full potential. The authors suggest that integrating these energies into deep learning frameworks could be a promising future direction.
Summary updated