##### Department of Mathematics,

University of California San Diego

****************************

### Mathematics 278 - Computational and Applied Mathematics

## Ofer Levi

#### Ben-Gurion University of the Negev, Israel

## Direct and exact PPFFT and radon transforms using orthogonalizing weights

##### Abstract:

The Pseudo-Polar FFT (PPFFT), which was developed and presented by Averbuch et. al, computes Discrete Fourier Transform coefficients on a nearly polar grid. The special structural properties of the Pseudo-Polar grid allow a computational complexity of $O(n^2\log(n))$ for an $n$ by $n$ image (as opposed to $O(n^4)$ in the polar case). Averbuch et. al. also presented a weighted version of the PPFFT that is nearly orthogonal and can be used for the application of an extremely fast iterative inverse solver. The PPFFT is directly related to a highly accurate and fast version of the Discrete Radon Transform that possesses the same desirable computational properties as the PPFFT, the Fast Slant-Stack Transform. In many instances and applications the PPFFT can be a very good substitute for the Polar FT and its superior computational properties can speed up many related algorithms by several orders of magnitude. Classical applications of the Polar FFT include rotational registration of images and reconstruction in medical and biological imaging. The preliminary part of this talk will introduce the basics of 2D DFTs in Cartesian, Polar and PP grids using matrices and vectors notation. Later, a new direct an exact inverse PPFFT will be presented, the algorithm is based on a preprocessing step in which an optimal set of weights is computed for the given image size, these weights perfectly orthogonalize the columns of the transform's matrix so that the inverse problem can be solved exactly by a single application of the Adjoint PPFFT which can be computed as well in $O(n^2\log(n))$ complexity. The results will be generalized to 3D as well as to Radon Transforms in 2D and 3D.

Host: Ery Arias-Castro

### October 6, 2005

### 11:00 AM

### AP&M 7321

****************************