Geometric or Trigonometric way to fit a circle to series of points

Question

I'm working on a computer vision project where I'm trying to detect a moving colored circle (doughnut actually). After some work I'm able to get it working pretty well except for these two edge cases. My results are always a small set of approximately 5-10 points that describe a circle. Then I can calculate the "center of mass" of the object. When this comes out right like a circle I get the center coordinates correctly. But when it comes out like the sketches below the center point is off.

The first image is the result of a little extra object being detected, and the second case is usually the camera occluding part of the image or sometimes an aggressive light source. A lot of my error cases have part of a circle in them.

So I've been trying to think if there is a neat mathematical way to identify each edge case, and then solve it, by figuring out where the real center would be of a circle that fit to it. I can see how to approach this from a trial and error convergence sort of approach. But I thought there might be something smarter I hadn't thought of.

I do know I could solve the problem on the right with an existing function if I had to, but I don't have a solution for the left. I don't want the circle that surrounds all the points on the left, I'm after what the circle would be if that little nub didn't exits. And I'd love to have a good understanding of solving both edge cases.

Any advice is always appreciated it.

Answer 1

One way to fit points to a circle is to do linear regression on the equation in the form $x^2 + a x + y^2 + b y + c = 0$. Writing this as $(x+a/2)^2 + (y+b/2)^2 = (a^2 + b^2)/4 - c$, this corresponds to a circle of centre $(-a/2, -b/2)$ and radius $\sqrt{(a^2+b^2)/4 - c}$.

Answer 2

If I properly uunderstand, you have $n$ data points $(x_i,y_i)$ $(i=1,2,\cdots,n)$ and you want to find the coordinates $(a,b)$ and the radius $r$ of the circle.

Before speaking about the function you could minimize, you can have reasonable estimates writing for each data point $i$ $$f_i=(x_i-a)^2+(y_i-b)^2-r^2=0$$ Now, write for all possible $\frac {n(n-1)}2$ combinations [$i=1,2,\cdots,n)$ and $j=i+1,\cdots,n-1)$] $$f_j-f_i=0 \implies 2(x_i-x_j)a+2(y_i-y_j)b=(x_i^2+y_i^2)-(x_j^2+y_j^2)$$ and a linear regression will give $(a_*,b_*)$. These being known, an estimate of $r$ could be obtained using $$r^2_*=\frac 1 n\sum_{i=1}^n \big[(x_i-a_*)^2+(y_i-b_*)^2\big]$$ Now, comes the problem of the objective function $\Phi(a,b,r)$ that you really want to minimize. It could be $$\Phi_1(a,b,r)=\sum_{i=1}^n\big[(x_i-a)^2+(y_i-b)^2-r^2\big]^2$$ $$\Phi_2(a,b,r)=\sum_{i=1}^n\big[\sqrt{(x_i-a)^2+(y_i-b)^2}-r \big]^2$$ This can easily be done using nonlinear regression or optimization; since you have good estimates, the calculations would converge quite fast. You could even use Newton-Raphson method for solving the equations $$\frac{\partial \Phi} {\partial a}=0 \qquad \qquad\frac{\partial \Phi} {\partial b}=0 \qquad\qquad\frac{\partial \Phi} {\partial r}=0 $$

Answer 3

If I understand correctly, you have the coordinates of some points, all of them (or nearly so) lying on a circle, and you want to find the center of that circle.

A possible approach is the following:

1. choose at random a triplet of points and find their circumcenter using this formula;

2. repeat step 1. a certain number of times (10 times, for instance); if all points lie on the circle then you should always obtain the same result;

3. choose as center of the circle the most obtained result in step 2.

Of course you must take into account numerical accuracy issues to decide if two results are the same or not.