Abstract

Polygonal ob jects are prevalent in man-made scenes. Early approaches to detecting them relied mainly on geometry while subse- quent ones also incorporated appearance-based cues. It has recently been shown that this could be done fast by searching for cycles in graphs of line-fragments, provided that the cycle scoring function can be expressed as additive terms attached to individual fragments. In this paper, we pro- pose an approach that eliminates this restriction. Given a weighted line- fragment graph, we use its cyclomatic number to partition the graph into managebly-sized sub-graphs that preserve nodes and edges with a high weight and are most likely to contain ob ject contours. Ob ject contours are then detected as maximally scoring elementary circuits enumerated in each sub-graph. Our approach can be used with any cycle scoring func- tion and multiple candidates that share line fragments can be found. This is unlike in other approaches that rely on a greedy approach to finding candidates. We demonstrate that our approach significantly outperforms the state-of-the-art for the detection of building rooftops in aerial images and polygonal ob ject categories from ImageNet.