15

Given a set of points (2D) i.e., point cloud (PC), the question is about a robust, accurate and computing-friendly method to find circles (or ellipses in advanced version).

The intuitive idea is to use Brute-Force Search on all possible points (as center){infinite!} and radii (again infinite!). This is ultra-extremely slow and inefficient.

As demonstrated bellow each fitted circle would be ranked based on the number of points (nn) positioned on the circle-circumference in a distance shorter than a threshold (t). So there is derr to present an average distance.

In advanced form ellipses are of interest to be fitted.

Any ideas, brain-storming, experiences, comments? enter image description here

Dipan Mehta
  • 5,587
  • 2
  • 30
  • 53
Developer
  • 1,129
  • 1
  • 10
  • 15

1 Answers1

14

The best ideas that exactly tries to solve this problem is Hough Transform .

Basically, the signal in hough space will be r, x, y co-ordinates. Here r stands for radius and x,y stands for center. Every points may belong to one or many circles. So in the Hough plane go through all possible circles where this point could belong to and just do a +1. This is not a search, just collection.

Now, if a real circle exists, so many points will add and the score of such a r, x, y will be much higher than all others. Selecting such a point will allow you pick the right circles.

Here is a classical paper way back in 1971 (before i was born!) that invented this concept.

  1. USE OF THE HOUGH TRASFORMTION TO DETECT LINES AND CURVES IN PICTURES By: Richard O. Duda, Peter E. Hart Tech report Artificial Intelligence Cente April 1971.

For Tutorial i would suggest references below:

  1. HIPR2 -Link
  2. Amos storkey
  3. IDL Reference

Specifically for circle detection, you can refer to this below:

  1. AI Shack
  2. Tech Report from Chicago Univ.
  3. Lecture Notes from Rochester Institute

These methods is very efficient, and very computer friendly.

Dipan Mehta
  • 5,587
  • 2
  • 30
  • 53
  • 1
    I can vouch for the AI Shack articles, they really help grok the more rigorous math you'll read elsewhere. – Ivo Flipse Feb 16 '12 at 07:37
  • 1
    Good answer. I already am familiar with Hough Transform (HT). The one I used was for detection of lines. There was a bit difficulty to determine line-segments. It was recommended so to use Probabilistic Hough Transform (PHT). I didn't get clear idea about the extension. I thought it may be so complex for circles or appear other difficulties. Regarding my experiences HT is good but not perfect. It is also my concern how to extend HT to 3D. I will try to review your provided links. Your answer is fairly good to be candidate as the answer. – Developer Feb 16 '12 at 10:30
  • AI Shack, and Tech Report from Chicaco links are dead – Mehdi Apr 05 '16 at 08:00