Circle Fitting

• Fitting a circle to data points is a non-trivial problem.
• Fitting a circle to data points is well-studied in the literature, with much progress on this problem has been made recently.
  • In particular, an important issue is getting a good fit when the data comprises only a portion of an arc of the circle (as in laser-scan data)
• This can be considered a machine learning problem. We have data and we are learning to make future inferences from it by fitting a circular model

The material on this page is my practical summary of

• A. Al-Sharadqah and N. Chernov, Error Analysis for Circle Fitting Algorithms, Electronic Journal of Statistics (2009), Volume 3 p 886-911
• The paper explains the "why", here I explain the "how".

1. Compute the \((x,y)\) coordinates of the centroid of the \(n\) data points \((\hat{x}_1, \hat{y}_1), \dots (\hat{x}_n, \hat{y}_n)\) (In other words, find the mean of the \(x\) and \(y\) coordinates):

   \begin{align} \hat{x} &= \frac{1}{n}\sum_{i=1}^N \hat{x}_i \\ \hat{y} &= \frac{1}{n}\sum_{i=1}^N \hat{y}_i \\ \end{align}

2. Shift the coordinates so that the centroid is at the origin:

   \begin{align} x_i &= \hat{x}_i - \hat{x} \\ y_i &= \hat{y}_i - \hat{y} \end{align}
3. Compute \(z_i = x_i^2 + y_i^2\)

4. Compute the mean of \(z\)

   \begin{equation} \bar{z} = \frac{1}{n}\sum_{i=1}^{n} z_i. \end{equation}

5. Form the data matrix from the \(n\) data points:

   \begin{equation} Z = \begin{bmatrix} x_1^2 + y_1^2 & x_1 & y_1 & 1 \\ \vdots & \vdots & \vdots & \vdots \\ x_n^2 + y_n^2 & x_n & y_n & 1 \end{bmatrix}, \end{equation}
6. Form the moment matrix \(M = \frac{1}{n}Z^{T} Z\)

7. Form the constraint matrix for the "Hyperaccurate algebraic fit"

   \begin{equation} H = \begin{bmatrix} 8 \bar{z} & 0 & 0 & 2 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 2 & 0 & 0 & 0 \end{bmatrix}, \end{equation}

   where \(\bar{x}\) is the mean of all \(x_i\) (i.e., \(\bar{x} = \frac{1}{n}\sum_{i=1}^{n} x_i)\), \(\bar{y}\) is the mean of all \(y_i\), and \(\bar{z}\) is the mean of all \(x_i^2+y_i^2\).

   • By shifting all the data by the mean \(\bar{x} = 0\) and \(\bar{y} = 0\), which greatly simplifies this matrix.

8. Compute \(H^{-1}\):

   \begin{equation} H^{-1} = \begin{bmatrix} 0 & 0 & 0 & \frac{1}{2} \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \frac{1}{2} & 0 & 0 & -2 \bar{z} \end{bmatrix} \end{equation}

9. Compute the Singular Value Decomposition of \(Z\)

   \begin{equation} Z = U \Sigma V^T \end{equation}
10. If the smallest singular value \(\sigma_4\) is less than \(10^{-12}\), then Let \(A\) be the the 4th column of the \(V\) matrix

11. If \(\sigma_4 > 10^{-12}\) then let

    \begin{equation} Y = V \Sigma V^T \end{equation}
    • Then find the eigenvalues and vectors of \(Q = Y H^{-1} Y\).
    • Let \(A_\ast\) be the eigenvector corresponding to the smallest positive eigenvalue of \(Q\).
    • Solve \(Y A = A_\ast\) for \(A\).

12. Once we have \(A\) then the equation for the circle is

    \begin{equation} (x -a)^2 + (y-b)^2 = R^2, \end{equation}

    with

    \begin{align} a &= \frac{-A_2}{2A_1} \\ b &= \frac{-A_3}{2A_1} \\ R^2 &= \frac{A_2^2+A_3^2 - 4 A_1 A_4}{4A_1^2}, \end{align}

    where \(A_i\) is the $i$-th component of \(A\).

13. We shifted the coordinate system, so the actual center is at \((a + \hat{x}, b + \hat{y})\).

14. Optionally, compute the root-mean-square-error of the fit

    \begin{equation} \sigma^2 = \sqrt{\frac{1}{n}\sum_{i=1}^{n}((x_i -a)^2 + (y_i - b)^2 - R^2)^2} \end{equation}