|
[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 23:21:46 CST 2007
(Ron Grant)
> If the ranges on x and y are limited, why not use a look up table on at
> least one octant?
(Ed Okerson)
> Why not pre-compute the values and use a lookup table? It doesn't get
> much quicker than
>
> theta = arctan[x];
This got me thinking. I'm using Sobel convolution for edge detection so
-1020 <= dx <= 1020
-1020 <= dy <= 1020
and the first octant (0 to 45 degrees) is
1 <= dx <= 1020
1 <= dy <= dx
That's 520200 possible combinations of dx and dy.
But really, all I need right now is an array index for a rough histogram,
say 64 bins spanning 0 to 180 degrees. Then there are 16 bins from 0 to 45
degrees. Gradient orientation isn't very accurate anyway.
In that case,
((tmp = (dy << 4) / dx + 1) > 16) ? 16 : tmp
gives a number from 1 to 16 with a maximum error of one bin. This is just
a rescaled version of
(45 degrees) * dy / dx + (2.53553 degrees), clamped at 45 degrees
as an approximation to atan2(dy, dx) with maximum error 2.53553 degrees.
I like LUTs (lookup tables). But I'm also worried about cache coherency. I
don't want to trade arithmetic operations for memory bandwidth.
As suggested above, a piecewise linear approximation using a LUT on the dx
ordinate is a good compromise between LUT size, speed and accuracy. My
accuracy requirements are low enough that an integer linear approximation
is (hopefully, will find out) good enough.
Thanks,
Chris
More information about the DPRG mailing list
|
