Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have data points from a half circle and I already know the approximate radius. I want to find the circle which best fits the points using a fixed radius. How can I do this? If I solve the problem using a typical circle fit algorithm the radius is too unstable due to noise.

share|improve this question
    
What sort of noise is there? Is each point supposedly on the boundary perturbed in a direction that need not move it along an arc of the circle? Are you trying to estimate both the center and the radius? Or estimate the center when the radius is known? –  Michael Hardy Dec 1 '10 at 19:52
    
The "noise" is quite predictable in its positions but is not always present for each measurement. Maybe it would help if I explain the problem a little better. I have about 50 data points in a semicircle, which have been extracted from edges in an image. Let's say the semi-circle ranges from 10-170 degrees. In the middle of the arc, i.e. at about 90 degrees there are some noisy data points in the shape of a bigger circle which has some influence on the final radius. –  user11230 Dec 1 '10 at 20:39
    
I don't need to estimate the radius. Only the circle center. I would imagine that finding the circle with a fixed radius that best fits the data set is the most robust solution. However I was not able to work out the math for this problem. –  user11230 Dec 1 '10 at 20:49
1  
There is a big literature on this. Typing 'circle fitting' into google with give you a lot of resources. Most of the approaches I know of deal with estimating both the center and the radius, but they could easily be adapted to estimate just the center if that is what you want. Your question is probably more appropriate for CrossValidated stats.stackexchange.com/questions. You might have better luck there. –  Robby McKilliam Dec 1 '10 at 21:06
    
Thanks for the link Robby. I will check that out. –  user11230 Dec 1 '10 at 21:33
add comment

3 Answers

I discovered the Hough Circle Transform method and have tested it now. It works really well so I will use it to find the optimal circle center for a given radius.

share|improve this answer
add comment

Here is one approach. First find a line $L$ that passes through two points of your set and has all points on $L$ or to one side. Then reflect your point set over $L$. Finally, fit a full circle to the doubled set of points.

You might need a more careful approach, depending on how noisy is your data. You could check the result against the center of gravity of your points. I assume your points are from the semicircle boundary (as opposed to points from a half-disk). Then I calculate that the center of gravity is $2 r/\pi$ to one side of the diameter. If your fit circle's radius $r$ does not closely match this distance to the c.g., then adjustment of $L$ is indicated.

share|improve this answer
    
That's a reasonable approach. However I also have missing data points, which means the center of gravity is not useful. I'm much more interested in finding the circle center (for a given r) than the actual "optimal" circle radius. First I set the line L as you said. Then if I iteratively move the line L in the direction of its normal and reflecting the points to the other side for each iteration, I could find the circle solution which minimizes my objective function. –  user11230 Dec 1 '10 at 21:25
1  
@unk: Yes, that is reasonable, and equivalent in spirit to my suggestion. –  Joseph O'Rourke Dec 1 '10 at 21:36
add comment

I have read about Hough Transfrom, it is good.
If you have like me just a few points (<10) and you are looking for the center of the best fitting circle (with fixed radius) you could:
take a pair of points
use them as the centers of two circles (of fixed radius)
find the apropriate intersection (on the right side)
repeat with all pairs
then the center of the best cicle is the mean point of all intersections.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.