## Fitzgibbon, Pilu, Fisher: Direct Least Squares Fitting of Ellipses

Andrew W. Fitzgibbon, Maurizio Pilu, and Robert B. Fisher

*Direct least-squares fitting of ellipses*,

IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(5),
476--480, May 1999

- Download the paper (PDF, 126K)
- The fabulous java demo
- Matlab code.
This is a more bulletproof version than that in the paper, incorporating
scaling to reduce roundoff error, correction of behaviour when the input
data are on a perfect hyperbola, and returns the geometric parameters
of the ellipse, rather than the coefficients of the quadratic form.
- BibTeX reference
- Matlab code for other ellipse fitters: Gzipped tar file (15K), ZIP file (30K)

Notes since the paper was written:
It's important to scale the image coordinates to be near one before running
the algorithm or you'll get numerical instability. See the improved matlab code for an implementation which includes
this step.

If you're implementing it in a language other than matlab,
there's a better way to solve
the eigenvalue problem than we knew when we wrote the paper, which involves
dividing the matrix into blocks.

[A B] [x] = l [D 0] [x]
[B' C] [y] [0 0] [y]

is the same as the pair of equations
A x + B y = l D x
B' x + C y = 0 ==> y = -inv(C) B' x

so the first eqn is
A x + B (-inv(C) B') x = l D x

or
inv(D) * (A - B*inv(C)*B') x = l x

What this means is that you can solve the system by breaking
the original matrices up into the blocks A,B,C,D and writing
[allx, allD] = eig(inv(D) * (A - B*inv(C)*B'))
x = "column of allx corresponding to the positive eigenvalue";
y = -inv(C) * B' * x;