ON THE DETECTION OF ROBUST CURVES

Given m points in the plane and a threshold t, a curve is defined to b e robust if at least t points lie on it. Efficient algorithms for dete cting robust curves are given; the key contribution is to use randomiz ed sampling. In addition, an approximate version of the problem is int roduced. A geometric solution to this problem is given; it too can be enhanced by randomization. These algorithms are readily generalized to solve the problem of robust curve detection in a scene of curve fragm ents: given a set of curve segments, a curve sigma is defined to be ro bust if curve segments of total length at least 1 lie on sigma. Again, both an exact and an approximate version of the problem are considere d. The problems and solutions are closely related to the well-investig ated Hough transform technique. (C) 1994 Academic Press, Inc.