# Thread: Ellipse fitting with eigenvalue: Looking for an error measure in MATLAB

1. ## Ellipse fitting with eigenvalue: Looking for an error measure in MATLAB

The six lines of Matlab code below is a nice way to fit an ellipse to a set of points. It is presented in a paper here: Direct Least Square Fitting of Ellipses

But I'm looking for a measure of how good the fit is, how scattered the points are around the fitted ellipse. Something like the mean square error in regression. Can such a measure be derived from this code? If not, how could it be calculated in a computationally efficient way?

(I'm lost because of the magic of eigenvalue, so I don't really understand what the code actually does)

% fitellip gives the 6 parameter vector of the algebraic circle fit
% to a(1)x^2 + a(2)xy + a(3)y^2 + a(4)x + a(5)y + a(6) = 0
% X & Y are lists of point coordinates and must be column vectors.

% Build design matrix
D = [ x.*x x.*y y.*y x y ones(size(x)) ];

% Build scatter matrix
S = D'*D;

% Build 6x6 constraint matrix
C(6,6) = 0; C(1,3) = -2; C(2,2) = 1; C(3,1) = -2;

% Solve eigensystem
[gevec, geval] = eig(S,C);

% Find the negative eigenvalue
[NegR, NegC] = find(geval < 0 & ~isinf(geval));

% Extract eigenvector corresponding to positive eigenvalue
A = gevec(:,NegC);

2. Originally Posted by Elliptic
The six lines of Matlab code below is a nice way to fit an ellipse to a set of points. It is presented in a paper here: Direct Least Square Fitting of Ellipses

But I'm looking for a measure of how good the fit is, how scattered the points are around the fitted ellipse. Something like the mean square error in regression. Can such a measure be derived from this code? If not, how could it be calculated in a computationally efficient way?

(I'm lost because of the magic of eigenvalue, so I don't really understand what the code actually does)

% fitellip gives the 6 parameter vector of the algebraic circle fit
% to a(1)x^2 + a(2)xy + a(3)y^2 + a(4)x + a(5)y + a(6) = 0
% X & Y are lists of point coordinates and must be column vectors.

% Build design matrix
D = [ x.*x x.*y y.*y x y ones(size(x)) ];

% Build scatter matrix
S = D'*D;

% Build 6x6 constraint matrix
C(6,6) = 0; C(1,3) = -2; C(2,2) = 1; C(3,1) = -2;

% Solve eigensystem
[gevec, geval] = eig(S,C);

% Find the negative eigenvalue
[NegR, NegC] = find(geval < 0 & ~isinf(geval));

% Extract eigenvector corresponding to positive eigenvalue
A = gevec(:,NegC);
The simplest measure of goodness of fit here is probably:

$\displaystyle \displaystyle G=\sum_{i} F(x_i,y_i)^2$

where $\displaystyle$$F(x,y)=0$ is the equation of the fitted elliple.

CB

3. Thank you, Captain.

So I need to square the distance of each point from the fitted ellips, and add them up. There is no computational efficient shurtcut available, like some result which the algorithm has already produced?

Another question:

The points available to me only represent one half of the ellips (say, the upper half). This means that errors in points furtherst away from the middle (say, to the right and left) are much more influential on the estimated values of the parameters than are the errors of the points in the middle. (At least I intuitively think so, and trying it out on the interactive graph here seems to confirm it: Direct Least Square Fitting of Ellipses )

Should I weigh the errors of the points depending on their position?

4. Originally Posted by Elliptic
Thank you, Captain.

So I need to square the distance of each point from the fitted ellips, and add them up. There is no computational efficient shurtcut available, like some result which the algorithm has already produced?
That is not what I wrote (it is perhaps the best approach and I had thought of mentioning it). What I did suggest is the sum of the squares of $\displaystyle F(x_i,y_i)$ where $\displaystyle F(x,y)=0$ is the equation of the elliple, this can be coded relativly efficiently using $\displaystyle D$ and $\displaystyle A$ which you have available ($\displaystyle F(x,y)=AD$ if I recall correctly).

CB

5. Thanks again, captain.

I think I'm confused by the matrix notation.

Is it correct that for each point i:
Di = F(xi; yi) = xi^2 + xiyi + yi^2 + xi + yi

While A = F(X,Y) is a vector which contains the estimated parameters a(1..6) in:
a(1)x^2 + a(2)xy + a(3)y^2 + a(4)x + a(5)y + a(6).

So, I should calculate each Di, subtract it (from what?, from ADi?) and square the difference? The sum of all these squared differences is a measure of the goodness of fit. AD over all i equals zero, but of course not for each i. Am I on track now?

6. Originally Posted by Elliptic
Thanks again, captain.

I think I'm confused by the matrix notation.

Is it correct that for each point i:
Di = F(xi; yi) = xi^2 + xiyi + yi^2 + xi + yi

While A = F(X,Y) is a vector which contains the estimated parameters a(1..6) in:
a(1)x^2 + a(2)xy + a(3)y^2 + a(4)x + a(5)y + a(6).

So, I should calculate each Di, subtract it (from what?, from ADi?) and square the difference? The sum of all these squared differences is a measure of the goodness of fit. AD over all i equals zero, but of course not for each i. Am I on track now?
We have an ellipse defined by $\displaystyle A$ such that a point $\displaystyle (x,y)$ lies on the ellipse if and only if:

$\displaystyle (a_1x^2+a_2xy+a_3y^2+a_4x+a_5y+a_6)=A(x^2,xy,y^2,x ,y,1)^t=0$

Now we have data $\displaystyle (x_i,y_i),\ i=1, ..., n$ and a score:

$\displaystyle S=\sum_i (a_1x_i^2+a_2x_iy_i+a_3y_i^2+a_4x_i+a_5y_i+a_6)^2= \sum_i [A(x_i^2,x_iy_i,y_i^2,x_i,y_i,1)^t]^2=\sum_i [AD_i^t]^2$

If all the data points lay on the ellipse this score would be zero. This score is easy to compute but its interpretation is not obvious, I would generate a sampling distribution for this using a boot-strap technique on sets of perturbed points from the ellipse with varying perturbation SDs.

CB

CB