|
[DPRG] fast atan2 approximation, low accuracy requirement
Subject: [DPRG] fast atan2 approximation, low accuracy requirement
From: Chris Jang
cjang at ix.netcom.com
Date: Sun Jan 7 00:02:12 CST 2007
> 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)
Thanks Kenneth. If I can't find the original reference, then I'll just
rederive this 2,2 order rational approximation and show that along with a
note about the lost origins.
Here's a nice constructive writeup on the method and how to figure out the
coefficients.
http://mathews.ecs.fullerton.edu/n2003/pade/PadeApproximationProof.pdf
Presently, I don't need much accuracy as I'm just doing polar histograms
for line detection and object recognition. But for localization, accurate
arc tangents become important. So it comes down to this Pade approximation
or a LUT (or a combination - piecewise Pade approximation).
> 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..
I'd probably avoid the recursion as the code duplication is really what we
want anyway. Either the compiler does it as an optimization or it is done
explicitly.
Sometimes, I wonder about the integer/fixed point/floating point
tradeoffs, expecially as hardware changes. EmbedCV does everything now in
integer arithmetic. It is not even using fixed point. But as so much
hardware accelerates floating point, not integer, floating point might
actually be faster on some platforms. I'm thinking especially of GPU
acceleration. In a few years, the GPU will probably move into the CPU
package so will become natural to use. But ... EmbedCV is for now (more
accurately, a few months from now), not the future.
Thanks,
Chris
More information about the DPRG mailing list
|
