Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

I have data points from a half circle and I already know the 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
add comment

1 Answer

up vote 3 down vote accepted

It depends on how the points might depart from the circle. If they do so through measurement error, a natural model is that their locations are binormally distributed with the coordinates $x$ and $y$ uncorrelated, of equal variances. This leads to a difficult model to fit, but if the errors are not too great compared to the radius, we can approximate it closely as a normal distribution in the radial direction only (because tangential displacements do not move a point off the circle, to first order). This suggests a model of the form

Distance($(x_i, y_i)$, $(\alpha, \beta)$) = $r + \epsilon_i$

where $r$ is given, the $(x_i, y_i)$ are the data, $(\alpha, \beta)$ are coordinates of the center (to be estimated), and the $\epsilon_i$ are identically and independently distributed with zero mean.

To estimate the parameters you could use least squares or maximum likelihood (among other approaches). For example, least squares would seek values of $\alpha$ and $\beta$ minimizing

$\sum_i \left( \sqrt{(x_i - \alpha)^2 + (y_i - \beta)^2} - r \right)^2 \text{.}$

This problem has no closed-form solution but can readily be solved numerically.

There is a clever approach in the image processing world: create an image of the boundaries of the circles of radius $r$ centered at the data points. In so doing, add the intensities of the boundaries wherever they overlap. Any grid point of greatest intensity is a reasonable solution. (In effect this is a kernel density estimate. You are using a kernel of the form $K(x,y)$ that is zero except for values of $(x,y)$ for which $x^2+y^2$ is close to $r^2$ and you are convolving that kernel with the data.)

share|improve this answer
    
The errors I have are not that far away from the true circle, however they are shaped as a circle with greater radius. Therefore they have a big influence on the solution. The errors does not have a normal distribution. –  Björn Dec 2 '10 at 8:46
    
The image processing approach is really a great idea. I will definately try it. Thanks a lot! –  Björn Dec 2 '10 at 8:48
    
I discovered that this is really the Hough Circle Transform and have tested it now. It works really well! –  Björn Dec 2 '10 at 10:41
    
@Björn Thank you for reminding me of the name: that provides a useful way for readers to learn more about the procedure. –  whuber Dec 2 '10 at 13:37
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.