Thread Subject: Ellipsoid estimation - algorithms?

Hi all.

A set of (x,y) data form ellipsoid segments in the sense that a
chain of (x,y) points describe parts of an ellipsoid curve.

The major and minor axes of the ellipse are oriented arbitrarily
in space, and the data are constrained such that they are single-
valued with respect to some possibly rotated axis: That *either*
the (possibly rotated) y = +sqrt(...) *or* the y = -sqrt(...)
solution
describes the segment, but not both.

Could somebody please suggest a closed-form LMS or TLS
algorithm for estimating both the parameters of the ellipsoid
and the goodness of fit of the data?

Rune

On 2009-11-12 13:52:52 -0400, Rune Allnor <allnor@tele.ntnu.no> said:

> Hi all.
>
> A set of (x,y) data form ellipsoid segments in the sense that a
> chain of (x,y) points describe parts of an ellipsoid curve.
>
> The major and minor axes of the ellipse are oriented arbitrarily
> in space, and the data are constrained such that they are single-
> valued with respect to some possibly rotated axis: That *either*
> the (possibly rotated) y = +sqrt(...) *or* the y = -sqrt(...)
> solution
> describes the segment, but not both.
>
> Could somebody please suggest a closed-form LMS or TLS
> algorithm for estimating both the parameters of the ellipsoid
> and the goodness of fit of the data?
>
> Rune

Look up ODRPack on netlib. It even includes a nice paper on the methods.

ODRPack does Orthogonal Distance Regression with a code that permits
general models. The folks who wrote it are with a NIST lab in Colarado.

Rune Allnor <allnor@tele.ntnu.no> wrote in message <f13a8c21-e938-4d03-a474-abe8aeb017eb@n35g2000yqm.googlegroups.com>...
> Hi all.
>
> A set of (x,y) data form ellipsoid segments in the sense that a
> chain of (x,y) points describe parts of an ellipsoid curve.
>
> The major and minor axes of the ellipse are oriented arbitrarily
> in space, and the data are constrained such that they are single-
> valued with respect to some possibly rotated axis: That *either*
> the (possibly rotated) y = +sqrt(...) *or* the y = -sqrt(...)
> solution
> describes the segment, but not both.
>
> Could somebody please suggest a closed-form LMS or TLS
> algorithm for estimating both the parameters of the ellipsoid
> and the goodness of fit of the data?
>
> Rune

You might download & try "ellipse fit" form the MATLAB FEX at:

http://www.mathworks.com/matlabcentral/fileexchange/22684-ellipse-fit-direct-method

http://www.mathworks.com/matlabcentral/fileexchange/22683-ellipse-fit-taubin-method

(There are at least two different versions.)

On Nov 12, 12:52 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> Hi all.
>
> A set of (x,y) data form ellipsoid segments in the sense that a
> chain of (x,y) points describe parts of an ellipsoid curve.
>
> The major and minor axes of the ellipse are oriented arbitrarily
> in space, and the data are constrained such that they are single-
> valued with respect to some possibly rotated axis: That *either*
> the (possibly rotated) y = +sqrt(...) *or* the y = -sqrt(...)
> solution
> describes the segment, but not both.
>
> Could somebody please suggest a closed-form LMS or TLS
> algorithm for estimating both the parameters of the ellipsoid
> and the goodness of fit of the data?
>
> Rune

Use differential correction. See a related example here:

http://www.claysturner.com/dsp/gps%20eqn%20solve.pdf

While this is a MathCad workseet, I think I put enough notes in there
so you can follow it. This method works like a champ for fitting
ellipses to data. I first learned about this method when I had to fit
orbits of binary stars to observational data. Binary Stars orbit each
other in elliptical paths. This method uses iteration with LSQR on
each iteration.

IHTH,
Clay

On Nov 13, 10:03 am, Clay <c...@claysturner.com> wrote:
> On Nov 12, 12:52 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
>
>
> > Hi all.
>
> > A set of (x,y) data form ellipsoid segments in the sense that a
> > chain of (x,y) points describe parts of an ellipsoid curve.
>
> > The major and minor axes of the ellipse are oriented arbitrarily
> > in space, and the data are constrained such that they are single-
> > valued with respect to some possibly rotated axis: That *either*
> > the (possibly rotated) y = +sqrt(...) *or* the y = -sqrt(...)
> > solution
> > describes the segment, but not both.
>
> > Could somebody please suggest a closed-form LMS or TLS
> > algorithm for estimating both the parameters of the ellipsoid
> > and the goodness of fit of the data?
>
> > Rune
>
> Use differential correction. See a related example here:
>
> http://www.claysturner.com/dsp/gps%20eqn%20solve.pdf
>
> While this is a MathCad workseet, I think I put enough notes in there
> so you can follow it. This method works like a champ for fitting
> ellipses to data. I first learned about this method when I had to fit
> orbits of binary stars to observational data. Binary Stars orbit each
> other in elliptical paths. This method uses iteration with LSQR on
> each iteration.
>
> IHTH,
> Clay- Hide quoted text -
>
> - Show quoted text -

Hello Rune, I don't know if you worked out your problem or not, but I
pulled out my 1935 copy of "The Binary Stars", and in there are some
details of algorithms by Herschel, Innes, and Thiele where they fit an
ellipse to observational data. Early algorithms just fit an ellipse
without regard to time information; later ones actually incorporate
Kepler's equation and derive the obital parameters. Basically the
astronomers have worked this out if you haven't already figured it out
by now. So this could be another avenue of attack.


Clay

On 18 Nov, 17:03, Clay <c...@claysturner.com> wrote:
> On Nov 13, 10:03 am, Clay <c...@claysturner.com> wrote:
>
>
>
>
>
> > On Nov 12, 12:52 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > Hi all.
>
> > > A set of (x,y) data form ellipsoid segments in the sense that a
> > > chain of (x,y) points describe parts of an ellipsoid curve.
>
> > > The major and minor axes of the ellipse are oriented arbitrarily
> > > in space, and the data are constrained such that they are single-
> > > valued with respect to some possibly rotated axis: That *either*
> > > the (possibly rotated) y = +sqrt(...) *or* the y = -sqrt(...)
> > > solution
> > > describes the segment, but not both.
>
> > > Could somebody please suggest a closed-form LMS or TLS
> > > algorithm for estimating both the parameters of the ellipsoid
> > > and the goodness of fit of the data?
>
> > > Rune
>
> > Use differential correction. See a related example here:
>
> >http://www.claysturner.com/dsp/gps%20eqn%20solve.pdf
>
> > While this is a MathCad workseet, I think I put enough notes in there
> > so you can follow it. This method works like a champ for fitting
> > ellipses to data. I first learned about this method when I had to fit
> > orbits of binary stars to observational data. Binary Stars orbit each
> > other in elliptical paths. This method uses iteration with LSQR on
> > each iteration.
>
> > IHTH,
> > Clay- Hide quoted text -
>
> > - Show quoted text -
>
> Hello Rune, I don't know if you worked out your problem or not, but I
> pulled out my 1935 copy of "The Binary Stars", and in there are some
> details of algorithms by Herschel, Innes, and Thiele where they fit an
> ellipse to observational data. Early algorithms just fit an ellipse
> without regard to time information; later ones actually incorporate
> Kepler's equation and derive the obital parameters. Basically the
> astronomers have worked this out if you haven't already figured it out
> by now. So this could be another avenue of attack.

Interesting. The clue Gordon Sande posted lead me to a paper on
a TLS type of solution to curve fitting [*]. The problem with TLS
types of solutions is that they tend to require rather hefty
numerics, like generalized eigenvalue decomposition. Not for
the faint-hearted.

The older, presumably more straight-forward stuff might be
interesting if the numerics of the TLS becomes too cumbersome.

Rune

[*] Boggs & al: A stable and efficient algoirthm for nonlinear
    orthogonal distance regression, SIAM J. Sci. Stat. Comp.,
    1987.

On 2009-11-18 14:57:07 -0400, Rune Allnor <allnor@tele.ntnu.no> said:

> On 18 Nov, 17:03, Clay <c...@claysturner.com> wrote:
>> On Nov 13, 10:03 am, Clay <c...@claysturner.com> wrote:
>>
>>
>>
>>
>>
>>> On Nov 12, 12:52 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>>
>>>> Hi all.
>>
>>>> A set of (x,y) data form ellipsoid segments in the sense that a
>>>> chain of (x,y) points describe parts of an ellipsoid curve.
>>
>>>> The major and minor axes of the ellipse are oriented arbitrarily
>>>> in space, and the data are constrained such that they are single-
>>>> valued with respect to some possibly rotated axis: That *either*
>>>> the (possibly rotated) y = +sqrt(...) *or* the y = -sqrt(...)
>>>> solution
>>>> describes the segment, but not both.
>>
>>>> Could somebody please suggest a closed-form LMS or TLS
>>>> algorithm for estimating both the parameters of the ellipsoid
>>>> and the goodness of fit of the data?
>>
>>>> Rune
>>
>>> Use differential correction. See a related example here:
>>
>>> http://www.claysturner.com/dsp/gps%20eqn%20solve.pdf
>>
>>> While this is a MathCad workseet, I think I put enough notes in there
>>> so you can follow it. This method works like a champ for fitting
>>> ellipses to data. I first learned about this method when I had to fit
>>> orbits of binary stars to observational data. Binary Stars orbit each
>>> other in elliptical paths. This method uses iteration with LSQR on
>>> each iteration.
>>
>>> IHTH,
>>> Clay- Hide quoted text -
>>
>>> - Show quoted text -
>>
>> Hello Rune, I don't know if you worked out your problem or not, but I
>> pulled out my 1935 copy of "The Binary Stars", and in there are some
>> details of algorithms by Herschel, Innes, and Thiele where they fit an
>> ellipse to observational data. Early algorithms just fit an ellipse
>> without regard to time information; later ones actually incorporate
>> Kepler's equation and derive the obital parameters. Basically the
>> astronomers have worked this out if you haven't already figured it out
>> by now. So this could be another avenue of attack.
>
> Interesting. The clue Gordon Sande posted lead me to a paper on
> a TLS type of solution to curve fitting [*]. The problem with TLS
> types of solutions is that they tend to require rather hefty
> numerics, like generalized eigenvalue decomposition. Not for
> the faint-hearted.
>
> The older, presumably more straight-forward stuff might be
> interesting if the numerics of the TLS becomes too cumbersome.

The clue had two parts. One was the paper which you have followed
up on. Good. The other was that there was a complete working code
in netlib. It even has examples of fitting segements of elipses if
memory is correct. No need to roll your own unless your problem is
different than your original description. Making other's code work
with your environment can always be a bother but that is different
issue from working out how to do the indicated arithmentic.

netlib is worth knowing about. It is a class repositry of good numerical
algorithms provided by professionals in various specialities for all
sorts of problems. Numerical recipes is a convenient introduction and
netlib is where you go for production quality code.

> Rune
>
> [*] Boggs & al: A stable and efficient algoirthm for nonlinear
> orthogonal distance regression, SIAM J. Sci. Stat. Comp.,
> 1987.

On 18 Nov, 20:38, Gordon Sande <g.sa...@worldnet.att.net> wrote:
> On 2009-11-18 14:57:07 -0400, Rune Allnor <all...@tele.ntnu.no> said:
>
>
>
>
>
> > On 18 Nov, 17:03, Clay <c...@claysturner.com> wrote:
> >> On Nov 13, 10:03 am, Clay <c...@claysturner.com> wrote:
>
> >>> On Nov 12, 12:52 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> >>>> Hi all.
>
> >>>> A set of (x,y) data form ellipsoid segments in the sense that a
> >>>> chain of (x,y) points describe parts of an ellipsoid curve.
>
> >>>> The major and minor axes of the ellipse are oriented arbitrarily
> >>>> in space, and the data are constrained such that they are single-
> >>>> valued with respect to some possibly rotated axis: That *either*
> >>>> the (possibly rotated) y = +sqrt(...) *or* the y = -sqrt(...)
> >>>> solution
> >>>> describes the segment, but not both.
>
> >>>> Could somebody please suggest a closed-form LMS or TLS
> >>>> algorithm for estimating both the parameters of the ellipsoid
> >>>> and the goodness of fit of the data?
>
> >>>> Rune
>
> >>> Use differential correction. See a related example here:
>
> >>>http://www.claysturner.com/dsp/gps%20eqn%20solve.pdf
>
> >>> While this is a MathCad workseet, I think I put enough notes in there
> >>> so you can follow it. This method works like a champ for fitting
> >>> ellipses to data. I first learned about this method when I had to fit
> >>> orbits of binary stars to observational data. Binary Stars orbit each
> >>> other in elliptical paths. This method uses iteration with LSQR on
> >>> each iteration.
>
> >>> IHTH,
> >>> Clay- Hide quoted text -
>
> >>> - Show quoted text -
>
> >> Hello Rune, I don't know if you worked out your problem or not, but I
> >> pulled out my 1935 copy of "The Binary Stars", and in there are some
> >> details of algorithms by Herschel, Innes, and Thiele where they fit an
> >> ellipse to observational data. Early algorithms just fit an ellipse
> >> without regard to time information; later ones actually incorporate
> >> Kepler's equation and derive the obital parameters. Basically the
> >> astronomers have worked this out if you haven't already figured it out
> >> by now. So this could be another avenue of attack.
>
> > Interesting. The clue Gordon Sande posted lead me to a paper on
> > a TLS type of solution to curve fitting [*]. The problem with TLS
> > types of solutions is that they tend to require rather hefty
> > numerics, like generalized eigenvalue decomposition. Not for
> > the faint-hearted.
>
> > The older, presumably more straight-forward stuff might be
> > interesting if the numerics of the TLS becomes too cumbersome.
>
> The clue had two parts. One was the paper which you have followed
> up on. Good. The other was that there was a complete working code
> in netlib.

There are a number of reasons why I am a bit sceptical about
mixing and matching code. Some have to do with legal / licensing
issues, others have to do with different libraries being organized
differently and thus don't match quite as seamlessly as one
might have appreciated.

Rune