Least square approximation of an ellipse with fixed center

Question

I was thinking about the problem of fitting scattered data to an ellipse with a fixed center (i.e. the center is given in advance) using least square. I found a paper by Fittzgibbon et al. which approximate an ellipse using least square but the center is not fixed in advance. I was wondering if it is possible to modify the method for a constrained center. Any other reference paper for a solution is also welcomed.

Answer 1

The implicit equation of an ellipse is

$ (r - r_0)^T Q (r - r_0) = 1$

where $r_0= (r_{01}, r_{02})$ is the center, and $Q$ is a symmetric positive definite matrix. Since $r_0$ is given in advance, we will shift all the coordinates of the given points, by adding the negative of $r_0$, i.e. we define $ r' = r - r_0 $, then the equation of the ellipse to be identified will be,

$ r'^T Q r' = 1 $

After completing the shift, let $ r'_i = (x_i, y_i) $, then the above equation expands to

$ \epsilon_i = A x_i^2 + B y_i^2 + C x_i y_i + D $

We have to add an additional constraint to the unknowns $A,B,C,D$ that will guarantee that they are NOT all zero. A convenient condition is that $A + B = 1$

Note that the least squares function (to be minimized) is

$ J = \displaystyle \sum_i \epsilon_i^2 $

Substituting the condition on $A$ and $B$, we get

$ J = \displaystyle \sum_i \left( x_i^2 + B ( y_i^2 - x_i^2 ) + C x_i y_i + D \right)^2 $

Next we find $\dfrac{\partial J}{\partial B}$, $\dfrac{\partial J}{\partial C}$, $\dfrac{\partial J}{\partial D}$ and this will give the so-called normal equations for the least squares regression. These are given by

$\dfrac{\partial J}{\partial B}= 2 \displaystyle \sum_i (y_i^2 - x_i^2) \left( x_i^2 + B ( y_i^2 - x_i^2 ) + C x_i y_i + D \right) =0$

$\dfrac{\partial J}{\partial C}= 2 \displaystyle \sum_i (x_i y_i) \left( x_i^2 + B ( y_i^2 - x_i^2 ) + C x_i y_i + D \right) =0$

$\dfrac{\partial J}{\partial D}= 2 \displaystyle \sum_i \left( x_i^2 + B ( y_i^2 - x_i^2 ) + C x_i y_i + D \right) =0$

We now have a linear system of three equation in the three unknowns $B, C, D$, which is straight forward to solve numerically. Once $B,C,D$ are found, then $A = 1 - B $ is now known.

What is left is to find $Q$, and for that, note that

$ A = t Q_{11} $

$ B = t Q_{22} $

$ C = 2 t Q_{12} $

$ D = -t $

The last equation gives us the value of the multiplier $t$. So that $Q$ is now determined.

The final form of the ellipse is obtained by shifting the found ellipse so that its center is at $r_0$, and this will make its equation:

$ (r - r_0)^T Q (r - r_0) = 1 $