Dw. Jacobs, ROBUST AND EFFICIENT DETECTION OF SALIENT CONVEX GROUPS, IEEE transactions on pattern analysis and machine intelligence, 18(1), 1996, pp. 23-37
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.