Fast and Accurate Polar Fourier Transform
(September 2006)Abstract
In a wide range of applied problems of 2D and 3D imaging a continuous
formulation of the problem places great emphasis on obtaining and
manipulating the Fourier transform in Polar coordinates. However,
the translation of continuum ideas into practical work with data
sampled on a Cartesian grid is problematic. In this article we develop
a fast high accuracy Polar FFT. For a given two-dimensional signal
of size NxN, the proposed algorithm's complexity is O(N2logN), just
like in a Cartesian 2D-FFT. A special feature of our approach is
that it involves only 1D equispaced FFT's and 1D interpolations.
A central tool in our method is the pseudo-Polar FFT, an FFT where
the evaluation frequencies lie in an oversampled set of nonangularly
equispaced points. We describe the concept of pseudo-Polar domain,
including fast forward and inverse transforms. For those interested
primarily in Polar FFT's, the pseudo-Polar FFT plays the role of
a halfway point--a nearly-Polar system from which conversion to Polar
coordinates uses processes relying purely on 1D FFT's and interpolation
operations. We describe the conversion process, and give an error
analysis of it. We compare accuracy results obtained by a Cartesian-based
unequally-sampled FFT method to ours, both algorithms using a small-support
interpolation and no pre-compensating, and show marked advantage
to the use of the pseudo-Polar initial grid.