Regression to a Circle

The regression of a set of points to the equation of a circle (circular regression) can be achieved by minimizing both an algebraic distance and a geometric distance.

To calculate the linear regression of a dataset towards the equation of a circle centered at $(x_0,y_0)$ with radius $r$, the function to minimize is

$$S = \sum \left( (x_i - x_0)^{2} + (y_i - y_0)^{2} - r^2 \right)^2$$ (3.84)

where the orthogonal distance between the points and the model is minimized.

To solve the problem, it is advisable to perform a change of variables and minimize the algebraic form:

$$S = \sum \left( z_i + Bx_i + Cy_i + D \right)^2$$ (3.85)

where $z_i = x^2_i + y^2_i$ has been introduced for simplicity.

The problem reduces to solving a linear system $3 \times 3$ of equations

$$\begin{array}{lllll} \sum z_i x_i & + B \sum x^{2}_i & + C ... ... + B \sum x_i & + C \sum y_i & + D \sum 1 & = 0 \\ \end{array}$$ (3.86)

which is symmetric and easily solvable.

Once the parameters $B$, $C$, and $D$ are obtained, it is possible to derive the original parameters of the circle:

$$x_0 = - \frac{B}{2} \quad y_0 = -\frac{C}{2} \quad r^2 = x^2_0 + y^2_0 - D$$ (3.87)

The same result can be achieved using the linear solvers discussed earlier. Consider, for example, an algebraic representation of a circle

$$f(\mathbf{x}) = a \mathbf{x}^\top \mathbf{x} + \mathbf{b}^{\top} \mathbf{x} + c = 0$$ (3.88)

where $\mathbf {x}$ is the locus of points on the circumference.

Given a list of points that belong to a noisy circumference, the parameters $(a,b_x,b_y,c)$ that describe the circle are obtained by solving the homogeneous constraint system (3.88). As will be detailed in subsequent problems, for purely computational reasons, it is advantageous to normalize the input data, as the different unknowns are associated with data of significantly varying magnitudes.

The algebraic solution is often used as an initial solution for iterative techniques that minimize a different metric. To perform geometric regression, it is necessary to minimize the distances $d^2_i = \left( \Vert \mathbf{x}_i - (x_0,y_0)^\top \Vert - r \right)^2$. To minimize this quantity, a nonlinear least squares solver is required, such as Levenberg-Marquardt, along with the computation of the derivatives of the cost function.

An alternative is to parameterize the problem in a space different from the Cartesian one. By using the parametric form of the equation of the circle

$$\begin{array}{l} x = x_0 + r \cos \varphi \\ y = y_0 + r \sin \varphi \\ \end{array}$$ (3.89)

the quantities to be minimized become

$$\begin{array}{l} x_i - x_0 + r \cos \varphi_i \approx 0 \\ y_i - y_0 + r \sin \varphi_i \approx 0 \\ \end{array}$$ (3.90)

which can be easily differentiated. To each input data $(x_i,y_i)$ an additional unknown $\varphi_i$, a subsidiary variable, is associated. In this way, a nonlinear system is created with $3+n$ unknowns and $2n$ equations.