Fourier-based forward and back-projectors in iterative fan-beam tomographic image reconstruction

Fourier-based forward and back-projection methods can reduce computation in iterative tomographic image reconstruction. Recently, an optimized nonuniform fast Fourier transform (NUFFT) approach was shown to yield accurate parallel-beam projections. In this paper, we extend the NUFFT approach to describe an O (N2 log N) projector/backprojector pair for fan-beam transmission tomography. Simulations and experiments with real CT data show that fan-beam Fourier-based forward and back-projection methods can reduce computation for iterative reconstruction while still providing accuracy comparable to their O (N3) space-based counterparts.     

Fourier-based reconstruction for fully 3-D PET: optimization of interpolation parameters

Fourier-based approaches for three-dimensional (3-D) reconstruction are based on the relationship between the 3-D Fourier transform (FT) of the volume and the two-dimensional (2-D) FT of a parallel-ray projection of the volume. The critical step in the Fourier-based methods is the estimation of the samples of the 3-D transform of the image from the samples of the 2-D transforms of the projections on the planes through the origin of Fourier space, and vice versa for forward-projection (reprojection). The Fourier-based approaches have the potential for very fast reconstruction, but their straightforward implementation might lead to unsatisfactory results if careful attention is not paid to interpolation and weighting functions. In our previous work, we have investigated optimal interpolation parameters for the Fourier-based forward and back-projectors for iterative image reconstruction. The optimized interpolation kernels were shown to provide excellent quality comparable to the ideal sinc interpolator. This work presents an optimization of interpolation parameters of the 3-D direct Fourier method with Fourier reprojection (3D-FRP) for fully 3-D positron emission tomography (PET) data with incomplete oblique projections. The reprojection step is needed for the estimation (from an initial image) of the missing portions of the oblique data. In the 3D-FRP implementation, we use the gridding interpolation strategy, combined with proper weighting approaches in the transform and image domains. We have found that while the 3-D reprojection step requires similar optimal interpolation parameters as found in our previous studies on Fourier-based iterative approaches, the optimal interpolation parameters for the main 3D-FRP reconstruction stage are quite different. Our experimental results confirm that for the optimal interpolation parameters a very good image accuracy can be achieved even without any extra spectral oversampling, which is a common practice to decrease errors caused by interpolation in Fourier reconstruction.     

Fast,iterative image reconstruction for MRI in the presence of field inhomogeneities

In magnetic resonance imaging, magnetic field inhomogeneities cause distortions in images that are reconstructed by conventional fast Fourier trasform (FFT) methods. Several noniterative image reconstruction methods are used currently to compensate for field inhomogeneities, but these methods assume that the field map that characterizes the off-resonance frequencies is spatially smooth. Recently, iterative methods have been proposed that can circumvent this assumption and provide improved compensation for off-resonance effects. However, straightforward implementations of such iterative methods suffer from inconveniently long computation times. This paper describes a tool for accelerating iterative reconstruction of field-corrected MR images: a novel time-segmented approximation to the MR signal equation. We use a min-max formulation to derive the temporal interpolator. Speedups of around 60 were achieved by combining this temporal interpolator with a nonuniform fast Fourier transform with normalized root mean squared approximation errors of 0.07%. The proposed method provides fast, accurate, field-corrected image reconstruction even when the field map is not smooth.     

Combining triangle Gaussian integration and modified NUFFT for evaluating two-dimensional Fourier transform integrals

The regular fast Fourier transform (FFT) requires a uniform Cartesian orthogonal grid which has considerable stair-casing errors when dealing with the function having an arbitrary shape boundary. The recently proposed two-dimensional discontinuous fast Fourier transform (2D-DFFT) can overcome this problem by using triangle mesh discretization and Gaussian numerical integration. However, the interpolation is used for the function data in the original 2D-DFFT, which reduces the accuracy performance especially for the case of oscillating functions. This work presents a useful modification of the original 2D-DFFT by removing the requirement of function interpolation to obtain significant accuracy improvement. In addition, the modified 2D nonuniform fast Fourier transform (NUFFT) with real-valued least-square interpolation coefficients are developed to speed up the computation of numerical Fourier transform over the triangle mesh. Numerical experiments are conducted to demonstrate the effectiveness and advantages of the proposed algorithms.     

Nonuniform fast Fourier transforms using min-max interpolation

The fast Fourier transform (FFT) is used widely in signal processing for efficient computation of the FT of finite-length signals over a set of uniformly spaced frequency locations. However, in many applications, one requires nonuniform sampling in the frequency domain, i.e., a nonuniform FT. Several papers have described fast approximations for the nonuniform FT based on interpolating an oversampled FFT. This paper presents an interpolation method for the nonuniform FT that is optimal in the min-max sense of minimizing the worst-case approximation error over all signals of unit norm. The proposed method easily generalizes to multidimensional signals. Numerical results show that the min-max approach provides substantially lower approximation errors than conventional interpolation methods. The min-max criterion is also useful for optimizing the parameters of interpolation kernels such as the Kaiser-Bessel function.     

Optimized Least-Square Nonuniform Fast Fourier Transform

The main focus of this paper is to derive a memory efficient approximation to the nonuniform Fourier transform of a support limited sequence. We show that the standard nonuniform fast Fourier transform (NUFFT) scheme is a shift invariant approximation of the exact Fourier transform. Based on the theory of shift-invariant representations, we derive an exact expression for the worst-case mean square approximation error. Using this metric, we evaluate the optimal scale-factors and the interpolator that provides the least approximation error. We also derive the upper-bound for the error component due to the lookup table based evaluation of the interpolator; we use this metric to ensure that this component is not the dominant one. Theoretical and experimental comparisons with standard NUFFT schemes clearly demonstrate the significant improvement in accuracy over conventional schemes, especially when the size of the uniform fast Fourier transform (FFT) is small. Since the memory requirement of the algorithm is dependent on the size of the uniform FFT, the proposed developments can lead to iterative signal reconstruction algorithms with significantly lower memory demands.      

Reconstruction in diffraction ultrasound tomography using nonuniform FFT

We show an iterative reconstruction framework for diffraction ultrasound tomography. The use of broad-band illumination allows significant reduction of the number of projections compared to straight ray tomography. The proposed algorithm makes use of forward nonuniform fast Fourier transform (NUFFT) for iterative Fourier inversion. Incorporation of total variation regularization allows the reduction of noise and Gibbs phenomena while preserving the edges. The complexity of the NUFFT-based reconstruction is comparable to the frequency-domain interpolation (gridding) algorithm, whereas the reconstruction accuracy (in sense of the L2 and the L(infinity) norm) is better.     

Toeplitz-Based Iterative Image Reconstruction for MRI With Correction for Magnetic Field Inhomogeneity

In some types of magnetic resonance (MR) imaging, particularly functional brain scans, the conventional Fourier model for the measurements is inaccurate. Magnetic field inhomogeneities, which are caused by imperfect main fields and by magnetic susceptibility variations, induce distortions in images that are reconstructed by conventional Fourier methods. These artifacts hamper the use of functional MR imaging (fMRI) in brain regions near air/tissue interfaces. Recently, iterative methods that combine the conjugate gradient (CG) algorithm with nonuniform FFT (NUFFT) operations have been shown to provide considerably improved image quality relative to the conjugate-phase method. However, for non-Cartesian k-space trajectories, each CG-NUFFT iteration requires numerous k-space interpolations; these are operations that are computationally expensive and poorly suited to fast hardware implementations. This paper proposes a faster iterative approach to field-corrected MR image reconstruction based on the CG algorithm and certain Toeplitz matrices. This CG-Toeplitz approach requires k-space interpolations only for the initial iteration; thereafter, only fast Fourier transforms (FFTs) are required. Simulation results show that the proposed CG-Toeplitz approach produces equivalent image quality as the CG-NUFFT method with significantly reduced computation time.     

Two-dimensional and three-dimensional NUFFT migration method for landmine detection using ground-penetrating Radar

Ground-penetrating radar (GPR) has been widely used for landmine detection due to its high signal-to-noise ratio (SNR) and superior ability to image nonmetallic landmines. Processing GPR data to obtain better target images and to assist further object detection has been an active research area. Phase-shift migration is a widely used method; however, its wavenumber space is nonuniformly sampled because of the nonlinear relationship between the uniform frequency samples and the wavenumbers. Conventional methods use linear interpolation to obtain uniform wavenumber samples and compute the fast Fourier transform (FFT). This paper develops two- and three-dimensional migration methods that process GPR data to obtain images close to the actual target geometries using a nonuniform fast Fourier transform (NUFFT) algorithm. The proposed method is first compared to the conventional migration approaches on simulated data and then applied to landmine field data sets. Results suggest that the NUFFT migration method is useful in focusing images, estimating landmine structure, and retaining relatively high signal-to-noise ratio in the migrated data. The processed data sets are then fed to the normalized energy and least-mean-square-based anomaly detectors. Receiver operating characteristic curves of data sets processed by different migration methods are compared. The NUFFT migration shows potential improvements on both classifiers with a reduced false alarm rate at most probabilities of detection.     

A fast and accurate Fourier algorithm for iterative parallel-beamtomography

We use a series-expansion approach and an operator framework to derive a new, fast, and accurate Fourier algorithm for iterative tomographic reconstruction. This algorithm is applicable for parallel-ray projections collected at a finite number of arbitrary view angles and radially sampled at a rate high enough that aliasing errors are small. The conjugate gradient (CG) algorithm is used to minimize a regularized, spectrally weighted least-squares criterion, and we prove that the main step in each iteration is equivalent to a 2-D discrete convolution, which can be cheaply and exactly implemented via the fast Fourier transform (FFT). The proposed algorithm requires O(N²logN) floating-point operations per iteration to reconstruct an N×N image from P view angles, as compared to O(N ²P) floating-point operations per iteration for iterative convolution-backprojection algorithms or general algebraic algorithms that are based on a matrix formulation of the tomography problem. Numerical examples using simulated data demonstrate the effectiveness of the algorithm for sparse- and limited-angle tomography under realistic sampling scenarios. Although the proposed algorithm cannot explicitly account for noise with nonstationary statistics, additional simulations demonstrate that for low to moderate levels of nonstationary noise, the quality of reconstruction is almost unaffected by assuming that the noise is stationary     

Regularization in tomographic reconstruction using thresholding estimators

In tomographic medical devices such as single photon emission computed tomography or positron emission tomography cameras, image reconstruction is an unstable inverse problem, due to the presence of additive noise. A new family of regularization methods for reconstruction, based on a thresholding procedure in wavelet and wavelet packet (WP) decompositions, is studied. This approach is based on the fact that the decompositions provide a near-diagonalization of the inverse Radon transform and of prior information in medical images. A WP decomposition is adaptively chosen for the specific image to be restored. Corresponding algorithms have been developed for both two-dimensional and full three-dimensional reconstruction. These procedures are fast, noniterative, and flexible. Numerical results suggest that they outperform filtered back-projection and iterative procedures such as ordered-subset-expectation-maximization.     

超分辨率图像重构算法的研究

图像重构是数字图像处理的一个重要分支。文章在图像配准的基础之上，采用后向投影迭代算法对图像序列进行了高分辨率重构，并给出了其中详细的算法和实现过程。实验仿真结果表明该算法运算量小，收敛速度较快．具有良好重构效果。     

Backprojection by upsampled Fourier series expansion andinterpolated FFT

A fast backprojection method through the use of interpolated fast Fourier transform (FFT) is presented. The computerized tomography (CT) reconstruction by the convolution backprojection (CBP) method has produced precise images. However, the backprojection part of the conventional CBP method is not very efficient. The authors propose an alternative approach to interpolating and backprojecting the convolved projections onto the image frame. First, the upsampled Fourier series expansion of the convolved projection is calculated. Then, using a Gaussian function, it is projected by the aliasing-free interpolation of FFT bins onto a rectangular grid in the frequency domain. The total amount of computation in this procedure for a 512x512 image is 1/5 of the conventional backprojection method with linear interpolation. This technique also allows the arbitrary control of the frequency characteristics.     

A Reconstruction Algorithm for Photoacoustic Imaging Based on the Nonuniform FFT

Fourier reconstruction algorithms significantly outperform conventional backprojection algorithms in terms of computation time. In photoacoustic imaging, these methods require interpolation in the Fourier space domain, which creates artifacts in reconstructed images. We propose a novel reconstruction algorithm that applies the one-dimensional nonuniform fast Fourier transform to photoacoustic imaging. It is shown theoretically and numerically that our algorithm avoids artifacts while preserving the computational effectiveness of Fourier reconstruction.      

基于非均匀FFT的压缩感知雷达信号快速重构方法

雷达处理是压缩感知理论重要的应用方向之一,基于压缩感知的雷达处理可以降低对回波信号的采样速率要求,并且在部分应用中也可改善处理性能。然而,压缩感知重构算法的计算复杂性限制了压缩感知理论在实际雷达信号处理中的应用,尤其是大尺度雷达数据的处理。本文提出了一种基于压缩感知的雷达信号快速重构方法,利用均匀和非均匀快速傅里叶变换运算实现了常规压缩感知重构算法中的矩阵-向量乘法运算,有效降低了重构算法的计算复杂度,加快了压缩感知雷达信号的重构速度。同时,由于引入了快速傅里叶变换运算,该方法消除了大多数常规重构算法对感知矩阵的存储需求。仿真实验验证了该方法的可行性和高效性。      

基于改进型快速双线性参数估计的复杂运动目标ISAR成像

针对复杂运动目标的逆合成孔径雷达(ISAR)成像中多普勒扩散导致的成像质量下降,该文在建立方位回波信号为立方相位信号(CPS)的基础上,提出一种基于改进型快速双线性参数估计的复杂运动目标ISAR成像方法。该方法通过利用双线性立方相位函数,非均匀快速傅里叶变换(NUFFT),基于Chirp-z的尺度变换以及快速傅里叶变换(FFT)等操作,能够快速实现CPS参数估计和复杂运动目标的ISAR成像。由于实现过程均采用NUFFT和FFT快速实现,该方法计算量小,并且双线性操作可以保证其具有较好的抗噪声性能和交叉项抑制性能。理论分析和仿真结果验证了该ISAR成像算法的有效性。     

Fast predictions of variance images for fan-beam transmission tomography with quadratic regularization

Accurate predictions of image variances can be useful for reconstruction algorithm analysis and for the design of regularization methods. Computing the predicted variance at every pixel using matrix-based approximations [1] is impractical. Even most recently adopted methods that are based on local discrete Fourier approximations are impractical since they would require a forward and backprojection and two fast Fourier transform (FFT) calculations for every pixel, particularly for shift-variant systems like fan-beam tomography. This paper describes new "analytical" approaches to predicting the approximate variance maps of 2-D images that are reconstructed by penalized-likelihood estimation with quadratic regularization in fan-beam geometries. The simplest of the proposed analytical approaches requires computation equivalent to one backprojection and some summations, so it is computationally practical even for the data sizes in X-ray computed tomography (CT). Simulation results show that it gives accurate predictions of the variance maps. The parallel-beam geometry is a simple special case of the fan-beam analysis. The analysis is also applicable to 2-D positron emission tomography (PET).     

Least-Square NUFFT Methods Applied to 2-D and 3-D Radially Encoded MR Image Reconstruction

Radially encoded MRI has gained increasing attention due to its motion insensitivity and reduced artifacts. However, because its samples are collected nonuniformly in the $k$-space, multidimensional (especially 3-D) radially sampled MRI image reconstruction is challenging. The objective of this paper is to develop a reconstruction technique in high dimensions with on-the-fly kernel calculation. It implements general multidimensional nonuniform fast Fourier transform (NUFFT) algorithms and incorporates them into a $k$-space image reconstruction framework. The method is then applied to reconstruct from the radially encoded $k$-space data, although the method is applicable to any non-Cartesian patterns. Performance comparisons are made against the conventional Kaiser–Bessel (KB) gridding method for 2-D and 3-D radially encoded computer-simulated phantoms and physically scanned phantoms. The results show that the NUFFT reconstruction method has better accuracy–efficiency tradeoff than the KB gridding method when the kernel weights are calculated on the fly. It is found that for a particular conventional kernel function, using its corresponding deapodization function as a scaling factor in the NUFFT framework has the potential to improve accuracy. In particular, when a cosine scaling factor is used, the NUFFT method is faster than KB gridding method since a closed-form solution is available and is less computationally expensive than the KB kernel (KB griding requires computation of Bessel functions). The NUFFT method has been successfully applied to 2-D and 3-D in vivo studies on small animals.      

基于NUFFT 算法的综合孔径辐射计图像反演方法

圆形阵列和旋转阵列排布方式的提出是为进一步降低综合孔径辐射计成像系统的复杂度和成本,然 而其缺陷在于过于复杂的亮温图像反演过程,因为该阵列排布方式下的采样样本不是均匀分布于整个采样平面,常 规的标准傅里叶变换不能直接运用于此反演过程。提出了一种非标准快速傅里叶变换(NUFFT)算法,用于非均匀 采样样本的综合孔径辐射计图像反演计算,该算法结合了高斯栅格算法和对过采样样本的快速傅里叶变换算法,仿 真结果表明该算法能够准确地得到反演图像。     

Iterative algorithm for nonuniform inverse fast Fourier transform(NU-IFFT)

A nonuniform inverse fast Fourier transform (NU-IFFT) for nonuniformly sampled data is realised by combining the conjugate-gradient fast Fourier transform (CG-FFT) method with the newly developed nonuniform fast Fourier transform (NUFFT) algorithms. An example application of the algorithm in computational electromagnetics is presented