I am a bit confused about the observations and unknowns when fitting a circle to a $2D$ points set using a gradient descent algorithm.

$R = \sqrt{ (x_i - x_c)² + (y_i - y_c)² }$ where $(x_c, y_c)$ is the center of the circle , $R$ is the radius and $x_i,y_i$ are coordinates of an arbitrary point on the circle.

I want to minimize the sum of squares of the error $e$, which I define as:

$$e = \sqrt{ (x_i - x_c)² + (y_i - y_c)² } - R$$

For the gradient descent algorithm, I need to calculate the first partial derivative of the error with respect to all unknowns, which are $x_c, y_c$ and $R$.

I will calculate an update for each unknown at each iteration step.

Let $\cfrac{de}{dx_c}$ be the partial derivative of error function with respect to the unknown $x_c$. This function rely on my observations, which are $x$ and $y$ coordinate of the point $i$ and an $R$ value for each point.

I measure/observe an $x$ and $y$ coordinate for all points. However, I don't have an observation for the radius at a single point.

In short: I formulated the problem as a minimization of the squared sum of differences between the calculated $R$ value and the observed $R$ value.

Based on this definition, what is my observed $R$ value?

  • $\begingroup$ There is no observed $R$ value. You observe $x_i,y_i$, and you have three unknowns to be determined by your descent algorithm: $x_c,y_c$ and $R$. $\endgroup$ – Wouter Aug 11 '16 at 12:19

For an easier solution, consider that you have $n$ data points $(x_i,y_i)$ and you look for the equation of the circle. So, ideally, $$f_i=(x_i-x_c)^2+(y_i-y_c)^2-r^2$$ Now compute $f_j-f_i$ $$F_{i,j}=f_j-f_i=2(x_i-x_j)x_c+2(y_i-y_j)y_c+(x_j^2+y_j^2)-(x_i^2+y_i^2)$$ which is the form of a linear regression. From it, you will easily compute $(x_c,y_c)$ by a linear regression with no intercept.

Another way is to consider the general equation of conics $$Ax^2+Bxy+Cy^2+Dx+Ey+F=0$$ For a circle $A=C$ and $B=0$ which makes the equation to be $$x^2+y^2+\alpha x+\beta y+\gamma=0$$ Again, a linear regression will give you $\alpha,\beta ,\gamma$ and then the classical transform will provide $x_c,y_c,r$.

At least, these will be good estimates for starting the minimization of any objective function of your choice.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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