Regression to a Circle

The regression of a set of points to the equation of a circle (circular regression) can be obtained by minimizing either an algebraic or a geometric distance.

If one wishes to compute the linear regression of a set of data to the equation of a circle centered at $(x_0,y_0)$ with radius $r$, the function to be minimized is

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

where the orthogonal distance between the points and the model is minimized. To solve the problem, it is convenient to perform a change of variables and minimize the algebraic form:

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

where $z_i = x^2_i + y^2_i$ has been introduced for simplicity. The problem is reduced to solving a linear system $3 \times 3$ with equation

$$\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}$$ (4.103)

which is symmetric and easily solved. Once the parameters $B$, $C$, and $D$ have been obtained, the original parameters of the circle can be recovered:

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

The same result can be obtained using the linear solvers introduced 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$$ (4.105)

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

Given a list of noisy points belonging to the circumference, the parameters $(a,b_x,b_y,c)$ describing the circumference are obtained by solving the homogeneous constraint system (4.105). As will be discussed in detail for subsequent problems, it is convenient, for purely computational reasons, to normalize the input data, since the different unknowns are associated with data having very different magnitudes.

The algebraic solution is often used as the 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$. Minimizing this quantity requires a nonlinear least-squares solver, such as Levenberg–Marquardt, and computation of the derivatives of the cost function.

Finally, an alternative is to parameterize the problem in a space other than the Cartesian space. Indeed, using the parametric form of the circle equation

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

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}$$ (4.107)

and are easily differentiated. Each input datum $(x_i,y_i)$ is associated with an additional unknown $\varphi_i$, an auxiliary variable. This creates a nonlinear system with $3+n$ unknowns and $2n$ equations.