Re: How to fit an ellipsoid to 3D data

On Aug 29, 12:36 pm, "Justin Abbott" <jjabbott.NOS...@xxxxxxxxx>
wrote:
"Bram Borkent" <brambork...@xxxxxxxxxxx> wrote in message

<fb1clb$h8...@xxxxxxxxxxxxxxxxxx>...

Is there a code which I can use to fit an ellipsoid to 3D
data, using a non-linear least squares algorithm?
If not, how to make one? :-)

I know these codes exist for spheres and cones but cannot
find one for an ellipsoid...

Regards,
Bram

Bram --

The general form for an ellipsoid is

Ax^2 + By^2 + Cz^2 + Dxy + Eyz + Fxz + Gx + Hy + Iz + J = 0

The equation is linear in A,..,J so if you have enough data
points you can estimate them using simple least squares.

Note that J is really unnecessary for this and will just
scale A,...,I. I am also not sure that this general form
is completely necessary, perhaps some other poster that
knows solid geometry better than I can say so.

I will let you figure out how to use A,...,I to calculate
the center and major/minor axes!

-Justin

Note that the linear least squares mentioned doesn't minimize (sum of
squares of) geometric distance from the points to the surface, it
minimizes the algebraic distance (i.e. how nonzero that equation is).
That will be fine if you have sufficient points which are not too
noisy, and is in all likelihood what you want.

For the homogeneous equation above (in Justin's post), simple (not
equivalent) linear least squares formulations would involve one of the
following constraints:
1) Let J = 1 and use Matlab's backslash to solve it
2) Let norm([A B ... I J]) = 1 and use the svd

Writing a nonlinear least squares routine to minimise geometric
distance will be significantly more complicated. It's complex enough
to do it for an ellipse, e.g. see my fitellipse submission on the file
exchange:

http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=15125

You might want to read the paper cited in that submission to get an
idea of what's involved :

"Least-Squares Fitting of Circles and Ellipses", W. Gander, G. H.
Golub, R. Strebel, BIT Numerical Mathematics, Springer 1994

Without ever having done it myself, I'm guessing that the mathematical
formulation of the geometric least squares problem for an ellipsoid
would be similar to the ellipse formulation described therein.

hope that helps,

Richard

.

Relevant Pages

  • Re: factoring using geomerty?
    ... of squares and its relation to geometry? ... > The Elliptic Curve Method definitely relies ...
    (sci.crypt)
  • Re: Sum of squares-
    ... But I would like a symbolic proof without appealing to geometry. ... A prime number p = 4n+1 is the sum of two squares in an essentially unique way. ... A number which is the product of N different prime numbers of the form 4n+1 is the sum of two squares in essentially 2^different ways. ...
    (sci.math)
  • Sum of squares
    ... But I would like a symbolic proof without appealing to geometry. ...
    (sci.math)