Gentoo Forums
Gentoo Forums
Gentoo Forums
Quick Search: in
determine ellipse parameters
View unanswered posts
View posts from last 24 hours

 
Reply to topic    Gentoo Forums Forum Index Off the Wall
View previous topic :: View next topic  
Author Message
Naib
Advocate
Advocate


Joined: 21 May 2004
Posts: 4161
Location: Removed by Neddy

PostPosted: Thu Jul 17, 2014 5:09 pm    Post subject: determine ellipse parameters Reply with quote

Say you have SIN and COS data streaming into an algorithm which produces an ellipse AND you are unable to store a complete cycle (sure a few)
how would you determine the: semimajor axis length,semiminor axis length, x,y of centre
_________________
A free press is the unsleeping guardian of every other right that free men prize; it is the most dangerous foe of tyranny. Where men have the habit of liberty, the Press will continue to be the vigilant guardian of the rights of the ordinary citizen.
Back to top
View user's profile Send private message
rudregues
Apprentice
Apprentice


Joined: 29 Jan 2013
Posts: 198

PostPosted: Thu Jul 17, 2014 8:47 pm    Post subject: Re: determine ellipse parameters Reply with quote

Naib wrote:
Say you have SIN and COS data streaming into an algorithm which produces an ellipse AND you are unable to store a complete cycle (sure a few)
how would you determine the: semimajor axis length,semiminor axis length, x,y of centre


Ok, let's be an ellipsis with semimajor axis a, semiminor axis b, centre (h, k). The parametric form will be:
x = h + a cos t
y = k + b sin t

So, if you have just sin and cos values, you can't determine the system. You need two (x, y) values and the corresponding (cos t, sin t) values.
_________________
Emerging en gentoo
Back to top
View user's profile Send private message
Naib
Advocate
Advocate


Joined: 21 May 2004
Posts: 4161
Location: Removed by Neddy

PostPosted: Thu Jul 17, 2014 10:29 pm    Post subject: Reply with quote

I have x,y and obviously t.

This can be done with eigen vectors but that is because a complete ellipse is stored in RAM. I don't have that luxury, I have an FPGA with not a lot of LUT so much so I cannot burn a 12x(100/ 4.5us) block instantiated as RAM.

I have seen a few iterative heuristic approach method (as ellipses seem to be a fundepental block for image recognition) but none that can provide: a,b,h,k,theta when x,y is given.

I have been thinking about visualising a rectangle around it based upon the mix and Max but that might just give me h,k
_________________
A free press is the unsleeping guardian of every other right that free men prize; it is the most dangerous foe of tyranny. Where men have the habit of liberty, the Press will continue to be the vigilant guardian of the rights of the ordinary citizen.
Back to top
View user's profile Send private message
Bones McCracker
Veteran
Veteran


Joined: 14 Mar 2006
Posts: 1567
Location: U.S.A.

PostPosted: Fri Jul 18, 2014 3:56 am    Post subject: Reply with quote

You should be able to derive all the parameters from as little as four x, y, theta triplets. IF you are working in a known single plane with an already defined set of x and y axes. In that case, an iterative method shouldn't require much storage. Calculate the the line that connects sampled points, then calculate the intersections of perpendicular lines from their midpoints. Since you know the axes, you only need to store the most extreme two points. After a full iteration those will be your locii h and k.

If you're in 3D space and don't already know the plane and origin for the sinusoidal data, then you have to treat the ellipse as a more general form: a conic section.

Ask dmitchell and Akkara.
Back to top
View user's profile Send private message
Naib
Advocate
Advocate


Joined: 21 May 2004
Posts: 4161
Location: Removed by Neddy

PostPosted: Fri Jul 18, 2014 6:57 am    Post subject: Reply with quote

I think I figured it out.
h & k I already derive due to offset compensation on the sin/cos data (ie Max pos - Max neg /2)
I am already determining instantaneous phi via the cordic... So all I need todo is iterate round storing the Max R (which is also kicked out my the cordic but not used). Max R then has a known x,y and phi. That phi is essentially my theta... So pi/4 from that gives the other R of the ellipse.

a,b,h,k would then be known after two complete rotations and thus everything is know to correct the ellipse
I'll do in python to prove the sequential logic before commuting to vhdl
_________________
A free press is the unsleeping guardian of every other right that free men prize; it is the most dangerous foe of tyranny. Where men have the habit of liberty, the Press will continue to be the vigilant guardian of the rights of the ordinary citizen.
Back to top
View user's profile Send private message
Akkara
Administrator
Administrator


Joined: 28 Mar 2006
Posts: 5236
Location: &akkara

PostPosted: Fri Jul 18, 2014 8:55 am    Post subject: Reply with quote

Need a more precise statement of the problem. What do the incoming x,y "look like", how many points are there, and what are you trying to do?

Is it, given a series of (x,y), find the best ellipse that fit the data, in a least-squares regression sort of way? Similar to least-squares linear fit, but looking for an ellipse to fit the data instead of a line? I needed to do something similar a few months ago, but for a circle, not an ellipse. Exceptionally ugly algebra and non-linear equation solving. An ellipse derivation is likely to be harder.

Can they be reasonably expected to be more or less uniformly spaced out on the ellipse? If so that makes it easier.

Or might they be concentrated to an arc-segment, not necessarily span the full ellipse? Such as in astronomy, when a new comet is found and they measure the path for a few weeks then extrapolate its {elliptical,parabolic,hyperbolic} orbit from that?

If it is a ongoing signal, a time-series of x,y's, you could try subtracting out the filtered average ("DC component") then taking the complex logarithm, and performing a linear fit on that. The time derivative of the imaginary part gives the frequency estimate, and the magnitude of the real part gives the geometric average of the major and minor radii. The ratio of diameters would show up as the variance (but that's also where the noise shows up so isn't as reliable). And I think there's also a way of recovering the tilt of the ellipse from this information but i don't recall what it is.

Edit: er, ok, so I type slow and write even slower. Should have refreshed this thread before finishing, seems you're on your way already. Good luck!
_________________
echo 'long long long x;' | gcc -x c -c -
Back to top
View user's profile Send private message
Bones McCracker
Veteran
Veteran


Joined: 14 Mar 2006
Posts: 1567
Location: U.S.A.

PostPosted: Fri Jul 18, 2014 5:02 pm    Post subject: Reply with quote

A circle is merely a special case of an ellipse, which is merely a special case of a conical section. You could use a non-linear programming approach, which might be a good method to identifying any of a variety of possible functional forms, but that's unnecessarily sacrificing the utility of known information. If certain assumptions are valid (such as the function operating only in a given plane, which seems valid since we are being given sinusoidal data in [x,y] form) then there are useful properties of the ellipse (and even moreso of the circle) which can be used to shortcut to a solution. For example, if the plane of the circle is known, the intersection of any two lines perpendicular to any two tangent lines is the center of the circle. A line tangent to a curve can be approximated by a line between any two sufficiently proximate points. Ellipses have similar properties which should be similarly useful in deriving the values of its parametric form (ie., h, k, a, b).
Back to top
View user's profile Send private message
Display posts from previous:   
Reply to topic    Gentoo Forums Forum Index Off the Wall All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum