I'll pay for a math solution. - Page 2

mathceleb · #16 $Old$ April 7th, 2008, 09:30 PM

Quote:

Originally Posted by Dirlewanger $View Post$

Well, I want a numerical method to efficiently find a good enough fit of ellispes to points. Much like this code does in Matlab:
MATLAB Central File Exchange - fit_ellipse
But for multiple related ellipses at once.

I'll solve the geometry and provide the equations, yes!

I see, you need 7 entry points, a,b,c,d,e and a 2D point. But you want to fit more than 1 ellipse at once. Got it.

Let's talk tomorrow when you are back online.

CaptainBlack · #17 $Old$ April 8th, 2008, 04:19 AM

Quote:

Originally Posted by Dirlewanger $View Post$

Oh, I don't want to cheat! I don't study or anything. But I now realize that this suspicion and misunderstanding is natural given my brief post.

I'd need some code that solves a specific kind of problem. It includes curve fitting and probably requires numerical methods. Also, it needs to be a bit efficient, nothing extreme but it shouldn't waste computational power. Matlab M-code would be fine if it compiles well. I've looked at it and just might work my way through it in M-code, but it'd take me quite some time and effort. While I like math, I'm not very good at it...
:P

The code could be completely open source if someone else ever has some use for it. I leave that to the author. I just want to be able to use it myself, w/o commercial interests.

The problem is probably not very hard or time consuming at all for someone with more than rudimetnary math education. But it's a bit more than I'd ask someone to do for free, and the purpose is to get a piece of working code, rather than learning math.

I'll take a look at the problem again before I try to specify it.

You should be aware that if this is done in Matlab it will probably use a library
optimiser, and so not easily translated into another language. Though You
could probably produce something that could be called from another language
using the compiler.

RonL

Dirlewanger · #18 $Old$ April 8th, 2008, 07:38 AM

Quote:

Originally Posted by CaptainBlack $View Post$

You should be aware that if this is done in Matlab it will probably use a library optimiser, and so not easily translated into another language.

But I can compile Matlab code and run it as a free standing program, right? If I get VBA source code that solves the problem, I'll look at it and try to write M-code that does the same thing.

Dirlewanger · #19 $Old$ April 8th, 2008, 08:34 AM

I am on the way to formulate the restrictions which connect the ellipses which I want to fit simultaneously. Now I stumble on a part of that problem. Please consider this problem in isolation, which certainly must have a solution:

(Let C be the origo of a 3D coordinate system.)

V is constrained to the big circle with center M and known radius R = MB = MS = MV.
A is constrained to the small circle with center C and known radius r = CS = CA.
E is the intersection of lines CS and VB.
Angle AVE is known
What are the coordinates of point V?

M, C and B lie on a straight line.
Distances MC and CB are known.
Big circle and small circle intersect in point S (and a corresponing point one diameter away).
Big circle and small circle stand at a right angle to each other (angle MCS = pi/2).
Angle AEC = AES = AEV = pi/2.

The complication is, that as V is moved around its big circle, then not only does the distance VE change, but so does the distance AE too! For example, if V is placed in line with BCM, then AE = radius of the small circle.

Can someone crack the algebra of it? Or else I have to use a numerical method to find the coordinates of V, which must be done (twice) inside the iteration loop of the larger multi-ellipse fitting problem.

mathceleb · #20 $Old$ April 8th, 2008, 11:00 AM

Dirlewanger,

I'm at work now, but I'll take a look at this during the week and see what I can do on Excel/VBA. I'll check back periodically to see if anybody else has answered this as well.

Dirlewanger · #21 $Old$ April 9th, 2008, 09:36 AM

I think I have a working numerical solution for the 3D geometry problem I posted above. But if someone sees an algebraic solution, it'd help.

Would this be an apropriate "flow chart" for the multi-ellipse fitting problem:

1) Guess the (five) parameters of one ellipse.
I have a way to make a pretty good initial guess. The horisontal distance between the points most to the right and most to the left, will be close to the long axis length, and the short axis will normally be about half as long. The tilt will normaly be modest.

2) Calculate the parameters of the other ellipses.
Given one ellipse, the parameters of all the other ellipses can be calculated. This is where the 3D-stuff with circles comes in. In 3D the relationship between the circles is easy. But the same relationships formulated it in terms of ellipse parameters in the 2D plane, i more complicated. However, this I am almost finished with, using a numerical method.

3) Calculate the degree of fit of the ellipses to the observed points belonging to each of them.
This is done using the method of least squares or something like that.

4) Calculate a new guess for the five parameters of one of the ellipses.
This is what is tricky to me, but probably straight forward for the experienced math user. Unless we can find a nice algebraic solution to the 3D-problem above, there will be no way get the derivatives required by Newton-Raphson or Levenberg-Marquardt. But the secant method should work fine. However, I'm a bit confused about changing all 5 ellipse parameters simultanously. I use the secant method for the 3D-problem above, but it only involves one single variable to change, the location of V on its big circle.

5) Go to step 2.