# Fitting a circle to a point set with gradient descent algorithm

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?

• 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$. – Wouter Aug 11 '16 at 12:19

## 1 Answer

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.