ROBUST AND EFFICIENT DETECTION OF SALIENT CONVEX GROUPS

This paper describes an algorithm that robustly locates salient convex collections of line segments in an image. The algorithm is guaranteed to find all convex sets of line segments in which the length of the g aps between segments is smaller than some fixed proportion of the tota l length of the lines. This enables the algorithm to find convex group s whose contours are partially occluded or missing due to noise. We gi ve an expected case analysis of the algorithm's performance. This demo nstrates that salient convexity is unlikely to occur at random, and he nce is a strong clue that grouped line segments reflect underlying str ucture in the scene. We also show that our algorithm's run time is O(n (2)log(n) + nm), when we wish to find the in most salient groups in an image with n line segments. We support this analysis with experiments on real data, and demonstrate the grouping system as part of a comple te recognition system.