|
[DPRG] fast atan2 approximation, low accuracy requirement
Subject: [DPRG] fast atan2 approximation, low accuracy requirement
From: Ed Okerson
ed at okerson.com
Date: Sat Jan 6 13:13:21 CST 2007
Chris,
Why not pre-compute the values and use a lookup table? It doesn't get
much quicker than
theta = arctan[x];
Ed
> Hello,
>
> I need a fast atan2 approximation. Accuracy requirements are low. One
> degree accuracy is probably more than good enough.
>
> I am using a least squares approximation for from 0 to 45 degrees
>
> theta = -0.30097 + 0.61955 * x - 0.001659 * x * x
>
> found on
>
> http://www.restena.lu/convict/Jeunes/Math/arctan.htm
>
> As I'm only using integer arithmetic, this becomes
>
> theta = ((649645 * x * y - (1740 * y * y + 315590 * x * x)) / (x *
> x))
> >> 20; /* rescaled by 2 ^ 20 */
>
> where the y/x is the input value that we want to find the arc tangent of.
>
> Is this a good way?
>
> Many people have robot odometry and localization problems which naturally
> lead to computing arc tangents. So I'm hoping that someone can tell me if
> I'm doing this wrong.
>
> Why do I need atan2? Many computer vision algorithms use gradient
> orientation for histogram based methods (i.e. classical line detection
> Hough transform, SIFT object recognition, captcha OCR, etc). The histogram
> bins for angles are typically pretty large, anywhere from 10 to 45
> degrees. So speed is more important than accuracy.
>
> I'm adding an efficient Hough transform to EmbedCV so extended lines like
> walls and tape on the floor can be recognized. This is very useful not
> only for driving and localization - it reduces computation for object
> recognition too by identifying image areas and scales where objects are
> likely to be found. I've seen this used before in a research paper and
> find that it really is necessary.
>
> Chris
> _______________________________________________
> DPRGlist mailing list
> DPRGlist at dprg.org
> http://list.dprg.org/mailman/listinfo/dprglist
>
More information about the DPRG mailing list
|
