|
[DPRG] fast atan2 approximation, low accuracy requirement
Subject: [DPRG] fast atan2 approximation, low accuracy requirement
From: Chris Jang
cjang at ix.netcom.com
Date: Sat Jan 6 12:37:55 CST 2007
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
More information about the DPRG mailing list
|
