×

Fast and accurate polar Fourier transform. (English) Zbl 1107.65127

A fast high accuracy polar fast Fourier transform (FFT) is developed.
Consider a polar grid of frequencies \( \xi_{p,q} = \{\xi_x [p,q], \xi_y [p,q]\}\) in the circle inscribed in the fundamental region \(\xi \in [-\pi, \pi)^2 ,\) \[ \begin{cases} \xi_x [p,q]= {\pi p\over N}\cos (\pi q/2N) \\ & \text{ for }-N \leq p \leq N-1,\quad 0 \leq q \leq 2N-1 \\ \xi_y [p,q]= {\pi p\over N} \sin (\pi q/2N) \end{cases}. \] Given digital Cartesian data \( f [i_1, i_2], \; i_1, i_2 = 0, \ldots , N-1, \) the polar FT is defined to be the collection of samples \(\{F(\xi_{p,q})\}\), where \[ F(\xi_{p,q}) = \sum^{N-1}_{i_1=0}\;\sum^{N-1}_{i_2 =0} f[i_1,i_2]\;\exp(-i(i_1 \xi_x [p,q]-i_2 \;\xi_y ]p,q])). \] The proposed method for the fast evaluation of \(\{F (\xi_{p,q} ) \}\) factors the problem into two steps. First, a pseudo-polar FFT is applied, in which a pseudo-polar sampling set is used, and second, a conversion from pseudo-polar to polar FT is performed by univariate polynomial interpolations. The pseudo-polar FFT is an FFT where the evaluation frequencies lie in an oversampled set of nonangularly equispaced points.
For a given \(N \times N\) signal the proposed algorithm has an arithmetical complexity of \({\mathcal O} (N^2 \log N)\).
Further, the conversion process is described and an error analysis is given.

MSC:

65T50 Numerical methods for discrete and fast Fourier transforms
68U10 Computing methodologies for image processing
41A05 Interpolation in approximation theory

Software:

WaveLab; BEAMLAB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dongarra, J.; Sullivan, F., Introduction the top 10 algorithms, Comput. Sci. Eng., 2, 1, 22-79 (2000), Special issue
[2] Briggs, B.; Henson, E., The FFT: An Owner’s Manual for the Discrete Fourier Transform (1995), SIAM: SIAM Philadelphia · Zbl 0827.65147
[3] A. Averbuch, R.R. Coifman, D.L. Donoho, M. Elad, M. Israeli, Accurate and fast Polar Fourier transform, in: The 37th Asilomar on Signals, Systems and Computers, Pacific Grove, CA, 2003; A. Averbuch, R.R. Coifman, D.L. Donoho, M. Elad, M. Israeli, Accurate and fast Polar Fourier transform, in: The 37th Asilomar on Signals, Systems and Computers, Pacific Grove, CA, 2003 · Zbl 1107.65127
[4] Natterer, F., The Mathematics of Computerized Tomography (1986), John Wiley & Sons: John Wiley & Sons New York · Zbl 0617.92001
[5] Stark, H.; Woods, J. W.; Paul, I.; Hingorani, R., Direct Fourier reconstruction in computer tomography, IEEE Trans. Acoust., Speech Signal Process., 29, 2, 237-245 (1981)
[6] Fan, H.; Sanz, J. L.C., Comments on ‘Direct Fourier reconstruction in computer tomography’, IEEE Trans. Acoust., Speech Signal Process., 33, 2, 446-449 (1985)
[7] Matej, S.; Vajtersic, M., Parallel implementation of the direct Fourier reconstruction method in tomography, Comput. Artificial Intelligence, 9, 4, 379-393 (1990)
[8] K.J. Moraski, D.C. Munson Jr., Fast tomographic reconstruction using Chirp-Z interpolation, in: Proc. 25th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, IEEE Comput. Soc. Press, Los Alamitos, CA, 1991, pp. 1052-1056; K.J. Moraski, D.C. Munson Jr., Fast tomographic reconstruction using Chirp-Z interpolation, in: Proc. 25th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, IEEE Comput. Soc. Press, Los Alamitos, CA, 1991, pp. 1052-1056
[9] Delaney, A. H.; Bresler, Y., A fast and accurate Fourier algorithm for iterative parallel-beam tomography, IEEE Trans. Image Process., 5, 5, 740-753 (1996)
[10] Choi, H.; Munson, D. C., Direct-Fourier reconstruction in tomography and synthetic aperture radar, Int. J. Imaging Systems Technol., 9, 1, 1-13 (1998)
[11] Walden, J., Analysis of the direct Fourier method for computer tomography, IEEE Trans. Medical Imaging, 19, 3, 211-222 (2000)
[12] Gottleib, D.; Gustafsson, B.; Forssen, P., On the direct Fourier method for computer tomography, IEEE Trans. Medical Imaging, 19, 3, 223-232 (2000)
[13] Natterer, F.; Wübbeling, F., Mathematical Methods in Image Reconstruction (2000), SIAM: SIAM Philadelphia
[14] Basu, S.; Bresler, Y., An \(O(n^2 \log n)\) filtered backprojection reconstruction algorithm for tomography, IEEE Trans. Image Process., 9, 10, 1769-1773 (2000) · Zbl 0970.92014
[15] Fourmont, K., Non-equispaced fast Fourier transforms with applications to tomography, J. Fourier Anal. Appl., 9, 431-450 (2003) · Zbl 1073.65151
[16] Matej, S.; Fessler, J. A.; Kazantsev, I. G., Iterative tomographic image reconstruction using Fourier-based forward and back-projectors, IEEE Trans. Medical Imaging, 23, 4, 401-412 (2004)
[17] Suli, E.; Ware, A., A spectral method of characteristics for hyperbolic problems, SIAM J. Numer. Anal., 28, 2, 423-445 (1991) · Zbl 0743.65080
[18] Boyd, J. P., Multipole expansions and pseudospectral cardinal functions: A new generalization of the fast Fourier transform, J. Comput. Phys., 103, 2, 184-186 (1992) · Zbl 0765.65022
[19] Boyd, J. P., A fast algorithm for Chebyshev, Fourier, and sinc interpolation onto an irregular grid, J. Comput. Phys., 103, 2, 243-257 (1992) · Zbl 0768.65001
[20] Beylkin, G., On the fast Fourier transform of functions with singularities, Appl. Comput. Harmon., 2, 263-381 (1995) · Zbl 0838.65142
[21] Anderson, C.; Dahleh, M. D., Rapid computation of the discrete Fourier transform, SIAM J. Sci. Comput., 17, 913-919 (1998) · Zbl 0858.65144
[22] Dutt, A.; Rokhlin, V., Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Comput., 14, 1368-1393 (1993) · Zbl 0791.65108
[23] Dutt, A.; Rokhlin, V., Fast Fourier transforms for nonequispaced data II, Appl. Comput. Harmon. Anal., 2, 85-100 (1995) · Zbl 0822.65130
[24] Ware, A. F., Fast approximate Fourier transform for irregularly spaced data, SIAM Rev., 40, 4, 838-856 (1998) · Zbl 0917.65122
[25] Potts, D.; Steidl, G.; Tasche, M., Fast Fourier transforms for nonequispaced data: A tutorial, (Benedetto, J. J.; Ferreira, P., Modern Sampling Theory: Mathematics and Application (2000), Birkhäuser), 253-274, ch. 12
[26] Duijndam, A. J.W.; Schonewille, M. A., Nonuniform fast Fourier transform, Geophysics, 64, 2, 539-551 (1999)
[27] Nguyen, N.; Liu, Q. H., The regular Fourier matrices and nonuniform fast Fourier transforms, SIAM J. Sci. Comput., 21, 1, 283-293 (1999) · Zbl 0941.65152
[28] Fessler, J. A.; Sutton, B. P., Nonuniform fast Fourier transforms using min-max interpolation, IEEE Trans. Signal Process., 51, 2, 560-574 (2003) · Zbl 1369.94048
[29] Greengard, L.; Lee, J. Y., Accelerating the nonuniform fast Fourier transform, SIAM Rev., 46, 443-454 (2004) · Zbl 1064.65156
[30] A. Averbuch, R. Coifman, D.L. Donoho, M. Israeli, Fast Slant Stack: A notion of Radon transform for data in a Cartesian grid which is rapidly computible, algebraically exact, geometrically faithful and invertible, Technical Report, Statistics Department, Stanford University, 2003; A. Averbuch, R. Coifman, D.L. Donoho, M. Israeli, Fast Slant Stack: A notion of Radon transform for data in a Cartesian grid which is rapidly computible, algebraically exact, geometrically faithful and invertible, Technical Report, Statistics Department, Stanford University, 2003
[31] Mersereau, R. M.; Oppenheim, A. V., Digital reconstruction of multidimensional signals from their projections, Proc. IEEE, 62, 10, 1319-1338 (1974)
[32] J.E. Pasciak, A note on the Fourier algorithm for image reconstruction, Preprint AMD 896, Applied Mathematics Department, Brookhaven National Laboratory, Upton, NY, 1981; J.E. Pasciak, A note on the Fourier algorithm for image reconstruction, Preprint AMD 896, Applied Mathematics Department, Brookhaven National Laboratory, Upton, NY, 1981
[33] Edholm, P.; Herman, G. T., Linograms in image reconstruction from projections, IEEE Trans. Medical Imaging, MI-6, 4, 301-307 (1987)
[34] Lawton, W., A new Polar Fourier-transform for computer-aided tomography and spotlight synthetic aperture radar, IEEE Trans. Acoust., Speech Signal Process., 36, 6, 931-933 (1988) · Zbl 0709.68567
[35] Averbuch, A.; Shkolnisky, Y., 3D Fourier based discrete Radon transform, Appl. Comput. Harmon. Anal., 15, 1, 33-69 (2003) · Zbl 1035.65158
[36] Keller, Y.; Averbuch, A.; Israeli, M., A pseudoPolar FFT technique for translation, rotation and scale-invariant image registration, IEEE Trans. Image Process., 14, 1, 12-22 (2005)
[37] Rabiner, L. R.; Schafer, R. W.; Rader, C. M., The Chirp Z-transform algorithm and its application, Bell System Tech. J., 48, 1249-1292 (1969)
[38] Bailey, D. H.; Swarztrauber, P. N., The fractional Fourier transform and applications, SIAM Rev., 33, 3, 389-404 (1991) · Zbl 0734.65104
[39] Strang, G., Introduction to Applied Mathematics (1986), Wellesley/Cambridge Press · Zbl 0618.00015
[40] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), John Hopkins Univ. Press · Zbl 0865.65009
[41] Buckheit, J.; Donoho, D. L., WaveLab and Reproducible Research, Wavelets and Statistics (1995), Springer-Verlag: Springer-Verlag Berlin · Zbl 0828.62001
[42] Choi, C. S.; Donoho, D. L.; Flesia, A. G.; Huo, X.; Levi, O.; Shi, D., About BeamLab a Toolbox for New Multiscale Methodologies (2002), Stanford University—Statistics Department Technical Report
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.