DPRG mailing list archives: [DPRG] fast atan2 approximation, low accuracy requirement

Sat Jan 6 13:06:37 CST 2007

Chris,

The following code chunk performs a fixed point atan function.  I feel very
bad as I do not have the lineage of this code.  I believe it comes from one
of the sourceforge 68332 projects, I'm guessing it was motorobots, however I
have lost the linkage.  A bit of searching there should turn it up so that
you can correctly reference the origin.  The approximation used is the pade
approximation:   atan(x) = x(15+4x2)/(15+9x2)

This is quite a bit computationally lighter than the method you referenced
below at the cost of accuracy.  Note, to use this function your compiler
must produce re-entrant code as you can see by the two statements encased in
if constructs.  If your compiler does not produce re-entrant code those two
if blocks can be unrolled with a tiny bit of code duplication.  To make this
more generic for use by more people in embedded robotics it might be best to
stay away from re-entrant code?  I do not know how others deal with it.
Many compilers can handle it easily, and possibly it is a non-issue for
those advanced enough to be playing with embedded vision...   Just thinking
out loud here..

-Kenneth

#define INT_TO_FIXED(x)         ((x) << 16)
#define FIXED_ONE       INT_TO_FIXED(1)
#define FIXED_PIDIV2    102944L

int32 fpatan(int32 x)
{
  register int32 x2;
  register int32 numerator;
  register int32 denominator;
  if (x > FIXED_ONE)
  {
    return FIXED_PIDIV2 - fpatan(fpdiv(FIXED_ONE, x));
  }
  if (x < -FIXED_ONE)
  {
    return -FIXED_PIDIV2 - fpatan(fpdiv(FIXED_ONE, x));
  }
  x2 = fpmul(x, x);
  numerator = fpmul(x, INT_TO_FIXED(15) + fpmul(INT_TO_FIXED(4), x2));
  denominator = INT_TO_FIXED(15) + fpmul(INT_TO_FIXED(9), x2);
  return fpdiv(numerator, denominator);
}

-----Original Message-----
From: dprglist-bounces at dprg.org [mailto:dprglist-bounces at dprg.org]On
Behalf Of Chris Jang
Sent: Saturday, January 06, 2007 12:38 PM
To: dprglist at dprg.org
Subject: [DPRG] fast atan2 approximation, low accuracy requirement

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