On the Detection of Robust Curves

R. Cole, U. Vishkin

Research output: Contribution to journalArticlepeer-review


Given m points in the plane and a threshold t, a curve is defined to be robust if at least t points lie on it. Efficient algorithms for detecting robust curves are given; the key contribution is to use randomized sampling. In addition, an approximate version of the problem is introduced. 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 fragments: given a set of curve segments, a curve σ is defined to be robust if curve segments of total length at least l lie on σ. Again, both an exact and an approximate version of the problem are considered. The problems and solutions are closely related to the well-investigated Hough transform technique.

Original languageEnglish (US)
Pages (from-to)189-204
Number of pages16
JournalCVGIP: Graphical Models and Image Processing
Issue number3
StatePublished - May 1994

ASJC Scopus subject areas

  • General Environmental Science
  • General Engineering
  • General Earth and Planetary Sciences


Dive into the research topics of 'On the Detection of Robust Curves'. Together they form a unique fingerprint.

Cite this