Results 1 to 6 of 6

Math Help - Ellipse fitting with eigenvalue: Looking for an error measure in MATLAB

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    3

    Cool 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);
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Elliptic View Post
    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 G=\sum_{i} F(x_i,y_i)^2

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

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Elliptic View Post
    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 F(x_i,y_i) where F(x,y)=0 is the equation of the elliple, this can be coded relativly efficiently using D and A which you have available ( F(x,y)=AD if I recall correctly).

    CB
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2010
    Posts
    3
    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?
    Last edited by Elliptic; July 6th 2010 at 04:40 AM. Reason: Pressed submit instead of preview.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Elliptic View Post
    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 A such that a point (x,y) lies on the ellipse if and only if:

    (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 (x_i,y_i),\ i=1, ..., n and a score:

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: July 10th 2011, 11:57 AM
  2. MATLAB error
    Posted in the Math Software Forum
    Replies: 1
    Last Post: March 31st 2010, 11:39 AM
  3. Which measure of error to use?
    Posted in the Statistics Forum
    Replies: 0
    Last Post: April 20th 2009, 05:12 AM
  4. Fitting a "double ellipse" to points
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: July 4th 2008, 04:47 AM
  5. Replies: 5
    Last Post: March 16th 2008, 04:19 PM

Search Tags


/mathhelpforum @mathhelpforum