Fast Polar Fourier Transform
August 13th, 2002
FoCM - Image & Signal Proc. Workshop - Invited Talk

In a wide range of applied problems of 2D and 3D imaging – including Tomography, image rotation, image registration and more – a common continuum 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 modern digital data sampled on a Cartesian grid is problematic. It is widely believed that “there is no Polar Fast Fourier Transform” and that for practical work, continuum ideas are at best a source of inspiration rather than a practical tool.

In this talk we describe a fast and highly accurate Polar-FFT. A special feature of the proposed approach is that it involves only 1D equi-spaced FFT’s. In particular, there is no role for notions like “re-gridding” and “scattered-data-interpolation”, as might have been supposed from the existing literature in related applications fields such as Tomography. A central tool in our approach is the Pseudo-Polar FFT, an FFT where the evaluation frequencies lie in an oversampled set of non-angularly equispaced points. In the talk we describe the concept of Pseudo-Polar domain (proposed originally by Averbuch, Coifman, Donoho, Israeli and Walden at 1998), including fast forward and inverse transform, a quasi-Parseval relation, and provide empirical and theoretical analysis of the Gram operator of the Pseudo-Polar FFT. For those interested primarily in Polar FFT’s, Pseudo-Polar FFT’s play the role of a halfway point – a nearly polar system from which conversion to Polar Coordinates uses processes relying purely on 1D operations. We illustrate a number of applications of our Polar and Pseudo-Polar FFT’s.

Joint work with David Donoho, Statistics- Stanford University, Amir Averbuch, Mathematics Department - Tel-Aviv University, Ronald Coifman, Mathematics Department - Yale, and Moshe Israeli - CS department - The Technion.