View previous topic :: View next topic 
Author 
Message 
Naib Advocate
Joined: 21 May 2004 Posts: 4258 Location: Removed by Neddy

Posted: Thu Jul 17, 2014 5:09 pm Post subject: determine ellipse parameters 


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 


rudregues Apprentice
Joined: 29 Jan 2013 Posts: 199 Location: Brazil

Posted: Thu Jul 17, 2014 8:47 pm Post subject: Re: determine ellipse parameters 


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 


Naib Advocate
Joined: 21 May 2004 Posts: 4258 Location: Removed by Neddy

Posted: Thu Jul 17, 2014 10:29 pm Post subject: 


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 


Bones McCracker Veteran
Joined: 14 Mar 2006 Posts: 1570 Location: U.S.A.

Posted: Fri Jul 18, 2014 3:56 am Post subject: 


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 


Naib Advocate
Joined: 21 May 2004 Posts: 4258 Location: Removed by Neddy

Posted: Fri Jul 18, 2014 6:57 am Post subject: 


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 


Akkara Administrator
Joined: 28 Mar 2006 Posts: 5372 Location: &akkara

Posted: Fri Jul 18, 2014 8:55 am Post subject: 


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 leastsquares regression sort of way? Similar to leastsquares 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 nonlinear 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 arcsegment, 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 timeseries 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 


Bones McCracker Veteran
Joined: 14 Mar 2006 Posts: 1570 Location: U.S.A.

Posted: Fri Jul 18, 2014 5:02 pm Post subject: 


A circle is merely a special case of an ellipse, which is merely a special case of a conical section. You could use a nonlinear 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 




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

