Fast and accurate Polar Fourier transform
Fast and accurate Polar Fourier transform
复制标题
DOI：
10.1016/j.acha.2005.11.003
复制
发表时间：
2006-09-01
影响因子：
2.5
通讯作者：
Israeli, M.
中科院分区：
文献类型：
--
作者：
Averbuch, A.;Coifman, R. R.;Israeli, M.
在2D和3D成像的广泛应用问题中，问题的连续表述非常强调在极坐标下获得和处理傅里叶变换。然而，用笛卡尔网格上的采样数据将连续统思想转化为实际工作是有问题的。本文提出了一种快速、高精度的极点FFT算法。对于给定的大小为N×N的二维信号，该算法的复杂度为O(N-2logN)，就像笛卡尔2D-FFT一样。我们方法的一个特点是它只涉及一维等间隔的FFT和ID内插。我们方法中的一个中心工具是伪极FFT，这是一种FFT，其中评估频率位于一组过采样的非角度等间距点中。我们描述了伪极值域的概念，包括快进变换和反变换。对于那些主要对极坐标FFT感兴趣的人，伪极坐标FFT扮演着中间点的角色--一种近极坐标系统，从该系统到极坐标的转换使用完全依赖于ID FFT和内插运算的过程。描述了转换过程，并对转换过程进行了误差分析。我们比较了基于笛卡儿的非均匀采样FFT方法和我们的算法的精度结果，这两种算法都使用了小支撑内插和无预补偿，并显示了使用伪极初始网格的显著优势。(C)2005 Elsevier Inc.保留所有权利。
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 N x N, the proposed algorithm's complexity is O(N-2 log N), just like in a Cartesian 2D-FFT. A special feature of our approach is that it involves only 1D equispaced FFT's and ID 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 ID 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. (C) 2005 Elsevier Inc. All rights reserved.