Given a set of $n$ two-dimensional points $\{(x_i, y_i), i=1,.., n\}$ I would like to find the ellipse that best fits them. The easiest approach I found was what is called the "Equation Error Model", in which we are trying to fit the points to the conic section model:
$$ A x^2 + B xy + C y^2 + D x + E y + F = 0 $$
The coefficients $A,B,C,D,E,F$ are not unique because they can be scaled by any real non-zero number. Also, for an ellipse, $A$ cannot be zero. Therefore, we can choose to fix $A = 1$, then we would have to determine the other $5$ coefficients.
Accumulating the data from every point, we will have the linear system
$ G a = b $
where $ a = [B, C, D, E, F]^T$, and
$ G = \begin{bmatrix} x_1 y_1 && y_1^2 && x_1 && y_1 && 1 \\
x_2 y_2 && y_2^2 && x_2 && y_2 && 1 \\
x_3 y_3 && y_3^2 && x_3 && y_3 && 1 \\
\vdots \\
x_n y_n && y_n^2 && x_n && y_n && 1 \end{bmatrix}\hspace{5pt}, \hspace{25pt} b = \begin{bmatrix} – x_1^2 \\ – x_2^2 \\ – x_3^2 \\ \vdots \\ – x_n^2 \end{bmatrix} $
To solve this linear system for $a$, pre-multiply by $G^T$, you get
$ G^T G a = G^T b $
and finally,
$ a = (G^T G)^{-1} G^T b $
I simulated the above method, and it gave excellent results. My question is whether there are alternative methods to approach this best fitting ellipse problem. Your hints, suggestions, and solutions are much appreciated.
Best Answer
It’s better to fix $A + C = 1$ rather than $A = 1$, for reasons I explained in Least square fit of ellipse worsens with increasing border thickness: $A + C$ is invariant under isometries of $(x, y)$, while $A$ is not.
Here’s a diagram using the same data from that question, comparing the ellipse correctly computed with $A + C = 1$ in red vs. incorrectly computed with $A = 1$ in orange. If you rotated the points, you’d find that the red ellipse matches their rotation exactly, while the orange ellipse wobbles around a bit.