How to fit an ellipsoid to 3D data

[Bram Borkent]

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

[Justin Abbott]

"Bram Borkent" <bramb...@hotmail.com> wrote in message
<fb1clb$h86$1...@fred.mathworks.com>...

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

[Richard Brown]

On Aug 29, 12:36 pm, "Justin Abbott" <jjabbott.NOS...@gmail.com>
wrote:
> "Bram Borkent" <brambork...@hotmail.com> wrote in message
>
> <fb1clb$h8...@fred.mathworks.com>...

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

[TB]

> 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
>

This paper discusses the 3-D case:

Feddema, J. T., and Little, C. Q., 1997, &#8216;&#8216;Rapid World
Modeling: Fitting Range Data to Geometric Primitives,&#8217;&#8217;
Proceedings of the IEEE International Conference on Robotics
and Automation, 4, pp. 2807 &#8211; 2812.

[John]

To do least squares you have an input matrix X and a single column output Y.
like this:
Y= bX

I'm fitting to this equation:

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

So I take each data point (x,y,z) and make 10 columns to input into my least squares program. The out put is the right side of the equation and is just 0 every time. So here's the setup:

X = [x^2 y^2 z^2 xy yz xz x y z 1]
Y= [0]
b=[A;B;C;D;E;F;G;H;I;J]

I punch it through my least squares program and I get A=B=C=D=E=F=G=H=I=J = 0

Didn't work. What's the right way to set this up?

[John]

Oh. I just answered my own question. You go like this:

X = [x^2 y^2 z^2 xy yz xz x y z]
Y= [1]
b=[A;B;C;D;E;F;G;H;I]