Iterative tomographic image reconstruction using Fourier-based forward and back-projectors

Iterative image reconstruction algorithms play an increasingly important role in modern tomographic systems, especially in emission tomography. With the fast increase of the sizes of the tomographic data, reduction of the computation demands of the reconstruction algorithms is of great importance. Fourier-based forward and back-projection methods have the potential to considerably reduce the computation time in iterative reconstruction. Additional substantial speed-up of those approaches can be obtained utilizing powerful and cheap off-the-shelf fast Fourier transform (FFT) processing hardware. The Fourier reconstruction approaches are based on the relationship between the Fourier transform of the image and Fourier transformation of the parallel-ray projections. The critical two steps are the estimations of the samples of the projection transform, on the central section through the origin of Fourier space, from the samples of the transform of the image, and vice versa for back-projection. Interpolation errors are a limitation of Fourier-based reconstruction methods. We have applied min-max optimized Kaiser-Bessel interpolation within the nonuniform FFT (NUFFT) framework and devised ways of incorporation of resolution models into the Fourier-based iterative approaches. Numerical and computer simulation results show that the min-max NUFFT approach provides substantially lower approximation errors in tomographic forward and back-projection than conventional interpolation methods. Our studies have further confirmed that Fourier-based projectors using the NUFFT approach provide accurate approximations to their space-based counterparts but with about ten times faster computation, and that they are viable candidates for fast iterative image reconstruction.     

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.     

Exact and approximate Fourier rebinning algorithms for the solution of the data truncation problem in 3-D PET

This paper presents an extended 3-D exact rebinning formula in the Fourier space that leads to an iterative reprojection algorithm (iterative FOREPROJ), which enables the estimation of unmeasured oblique projection data on the basis of the whole set of measured data. In first approximation, this analytical formula also leads to an extended Fourier rebinning equation that is the basis for an approximate reprojection algorithm (extended FORE). These algorithms were evaluated on numerically simulated 3-D positron emission tomography (PET) data for the solution of the truncation problem, i.e., the estimation of the missing portions in the oblique projection data, before the application of algorithms that require complete projection data such as some rebinning methods (FOREX) or 3-D reconstruction algorithms (3DRP or direct Fourier methods). By taking advantage of all the 3-D data statistics, the iterative FOREPROJ reprojection provides a reliable alternative to the classical FOREPROJ method, which only exploits the low-statistics nonoblique data. It significantly improves the quality of the external reconstructed slices without loss of spatial resolution. As for the approximate extended FORE algorithm, it clearly exhibits limitations due to axial interpolations, but will require clinical studies with more realistic measured data in order to decide on its pertinence.     

Iterative image reconstruction using inverse Fourier rebinning for fully 3-D PET

We describe a fast forward and back projector pair based on inverse Fourier rebinning for use in iterative image reconstruction for fully 3-D positron emission tomography (PET). The projector pair is used as part of a factored system matrix that takes into account detector-pair response by using shift-variant sinogram blur kernels, thereby combining the computational advantages of Fourier rebinning with iterative reconstruction using accurate system models. The forward projector consists of a 2-D projector, which maps 3-D images into 2-D direct sinograms, followed by exact inverse rebinning which maps the 2-D into fully 3-D sinograms. The back projector is implemented as the transpose of the forward projector and differs from the true exact rebinning operator in the sense that it does not require reprojection to compute missing lines of response (LORs). We compensate for two types of inaccuracies that arise in a cylindrical PET scanner when using inverse Fourier rebinning: 1) nonuniform radial sampling and 2) nonconstant oblique angles in the radial direction in a single oblique sinogram. We examine the effects of these corrections on sinogram accuracy and reconstructed image quality. We evaluate performance of the new projector pair for maximum a posteriori (MAP) reconstruction of simulated and in vivo data. The new projector results in only a small loss in resolution towards the edge of the field-of-view when compared to the fully 3-D geometric projector and requires an order of magnitude less computation.     

An efficient Fourier method for 3-D radon inversion in exactcone-beam CT reconstruction

The radial derivative of the three-dimensional (3-D) radon transform of an object is an important intermediate result in many analytically exact cone-beam reconstruction algorithms. The authors briefly review Grangeat's (1991) approach for calculating radon derivative data from cone-beam projections and then present a new, efficient method for 3-D radon inversion, i.e., reconstruction of the image from the radial derivative of the 3-D radon transform, called direct Fourier inversion (DFI). The method is based directly on the 3-D Fourier slice theorem. From the 3-D radon derivative data, which is assumed to be sampled on a spherical grid, the 3-D Fourier transform of the object is calculated by performing fast Fourier transforms (FFTs) along radial lines in the radon space. Then, an interpolation is performed from the spherical to a Cartesian grid using a 3-D gridding step in the frequency domain. Finally, this 3-D Fourier transform is transformed back to the spatial domain via 3-D inverse FFT. The algorithm is computationally efficient with complexity in the order of N ³ log N. The authors have done reconstructions of simulated 3-D radon derivative data assuming sampling conditions and image quality requirements similar to those in medical computed tomography (CT)     

Iterative image reconstruction using inverse fourier rebinning for fully 3-D PET

We describe a fast forward and back projector pair based on inverse Fourier rebinning for use in iterative image reconstruction for fully three-dimensional (3-D) positron emission tomography (PET). The projector pair is used as part of a factored system matrix that takes into account detector-pair response by using shift-variant sinogram blur kernels, thereby combining the computational advantages of Fourier rebinning with iterative reconstruction using accurate system models. The forward projector consists of a two-dimensional (2-D) projector, which maps 3-D images into 2-D direct sinograms, followed by exact inverse rebinning which maps the 2-D into fully 3-D sinograms. The back projector is implemented as the transpose of the forward projector and differs from the true exact rebinning operator in the sense that it does not require reprojection to compute missing line of responses (LORs). We compensate for two types of inaccuracies that arise in a cylindrical PET scanner when using inverse Fourier rebinning: 1) nonuniform radial sampling and 2) nonconstant oblique angles in the radial direction in a single oblique sinogram. We examine the effects of these corrections on sinogram accuracy and reconstructed image quality. We evaluate performance of the new projector pair for maximum a posteriori (MAP) reconstruction of simulated and in vivo data. The new projector results in only a small loss in resolution towards the edge of the field-of-view when compared to the fully 3-D geometric projector and requires an order of magnitude less computation.     

Rotate-and-slant projector for fast LOR-based fully-3-D iterative PET reconstruction

One of the greatest challenges facing iterative fully-3-D positron emission tomography (PET) reconstruction is the issue of long reconstruction times due to the large number of measurements for 3-D mode as compared to 2-D mode. A rotate-and-slant projector has been developed that takes advantage of symmetries in the geometry to compute volumetric projections to multiple oblique sinograms in a computationally efficient manner. It is based upon the 2-D rotation-based projector using the three-pass method of shears, and it conserves the 2-D rotator computations for multiple projections to each oblique sinogram set. The projector is equally applicable to both conventional evenly-spaced projections and unevenly-spaced line-of-response (LOR) data. The LOR-based version models the location and orientation of the individual LORs (i.e., the arc-correction), providing an ordinary Poisson reconstruction framework. The projector was implemented in C with several optimizations for speed, exploiting the vertical symmetry of the oblique projection process, depth compression, and array indexing schemes which maximize serial memory access. The new projector was evaluated and compared to ray-driven and distance-driven projectors using both analytical and experimental phantoms, and fully-3-D iterative reconstructions with each projector were also compared to Fourier rebinning with 2-D iterative reconstruction. In terms of spatial resolution, contrast, and background noise measures, 3-D LOR-based iterative reconstruction with the rotate-and-slant projector performed as well as or better than the other methods. Total processing times, measured on a single cpu Linux workstation, were approximately 10x faster for the rotate-and-slant projector than for the other 3-D projectors studied. The new projector provided four iterations fully-3-D ordered-subsets reconstruction in as little as 15 s--approximately the same time as FORE + 2-D reconstruction. We conclude that the rotate-and-slant projector is a viable option for fully-3-D PET, offering quality statistical reconstruction in times only marginally slower than 2-D or rebinning methods.     

3-D discrete analytical ridgelet transform.

In this paper, we propose an implementation of the 3-D Ridgelet transform: the 3-D discrete analytical Ridgelet transform (3-D DART). This transform uses the Fourier strategy for the computation of the associated 3-D discrete Radon transform. The innovative step is the definition of a discrete 3-D transform with the discrete analytical geometry theory by the construction of 3-D discrete analytical lines in the Fourier domain. We propose two types of 3-D discrete lines: 3-D discrete radial lines going through the origin defined from their orthogonal projections and 3-D planes covered with 2-D discrete line segments. These discrete analytical lines have a parameter called arithmetical thickness, allowing us to define a 3-D DART adapted to a specific application. Indeed, the 3-D DART representation is not orthogonal, It is associated with a flexible redundancy factor. The 3-D DART has a very simple forward/inverse algorithm that provides an exact reconstruction without any iterative method. In order to illustrate the potentiality of this new discrete transform, we apply the 3-D DART and its extension to the Local-DART (with smooth windowing) to the denoising of 3-D image and color video. These experimental results show that the simple thresholding of the 3-D DART coefficients is efficient.     

Reconstruction algorithms: Transform methods

Transform methods for image reconstruction from projections are based on analytic inversion formulas. In this tutorial paper, the inversion formula for the case of two-dimensional (2-D) reconstruction from line integrals is manipulated into a number of different forms, each of which may be discretized to obtain different algorithms for reconstruction from sampled data. For the convolution-backprojection algorithm and the direct Fourier algorithm the emphasis is placed on understanding the relationship between the discrete operations specified by the algorithm and the functional operations expressed by the inversion formula. The performance of the Fourier algorithm may be improved, with negligible extra computation, by interleaving two polar sampling grids in Fourier space. The convolution-backprojection formulas are adapted for the fan-beam geometry, and other reconstruction methods are summarized, including the rho-filtered layergram method, and methods involving expansions in angular harmonics. A standard mathematical process leads to a known formula for iterative reconstruction from projections at a finite number of angles. A new iterative reconstruction algorithm is obtained from this formula by introducing one-dimensional (1-D) and 2-D interpolating functions, applied to sampled projections and images, respectively. These interpolating functions are derived by the same Fourier approach which aids in the development and understanding of the more conventional transform methods.     

Fourier rebinning applied to multiplanar circular-orbit cone-beam SPECT

We study the application of Fourier rebinning methods to dual-planar cone-beam SPECT. Dual-planar cone-beam SPECT involves the use of a pair of dissimilar cone-beam collimators on a dual-camera SPECT system. Each collimator has its focus in a different axial plane. While dual-planar data is best reconstructed with fully three-dimensional (3-D) iterative methods, these methods are slow and have prompted a search for faster reconstruction techniques. Fourier rebinning was developed to estimate equivalent parallel projections from 3-D PET data, but it simply expresses a relationship between oblique projections taken in planes not perpendicular to the axis of rotation and direct projections taken in those that are. We find that it is possible to put cone-beam data in this context as well. The rebinned data can then be reconstructed using either filtered backprojection (FBP) or parallel iterative algorithms such as OS-EM. We compare the Feldkamp algorithm and fully 3-D OSEM reconstruction with Fourier-rebinned reconstructions on realistically-simulated Tc-99m HMPAO brain SPECT data. We find that the Fourier-rebinned reconstructions exhibit much less image noise and lower variance in region-of-interest (ROI) estimates than Feldkamp. Also, Fourier-rebinning followed by OSEM with nonuniform attenuation correction exhibits less bias in ROI estimates than Feldkamp with Chang attenuation correction. The Fourier-rebinned ROI estimates exhibit bias and variance comparable to those from fully 3-D OSEM and require considerably less processing time. However, in areas off the axis of rotation, the axial-direction resolution of FORE-reconstructed images is poorer than that of images reconstructed with 3-D OSEM. We conclude that Fourier rebinning is a practical and potentially useful approach to reconstructing data from dual-planar circular-orbit cone-beam systems.     

Cone-beam reprojection using projection-matrices

This paper addresses reprojection of three-dimensional (3-D) reconstructions obtained from cone-beam scans using a C-arm imaging equipment assisted by a pose-determining system. The emphasis is on reprojecting without decomposing the estimated projection matrix (P-matrix) associated with a pose. Both voxel- and ray-driven methods are considered. The voxel-driven reprojector follows the algorithm for backprojection using a P-matrix. The ray-driven reprojector is derived by extracting from the P-matrix the equation of the line joining a detector-pixel and the X-ray source position. This reprojector can be modified to a ray-driven backprojector. When the geometry is specified explicitly in terms of the physical parameters of the imaging system, the projection matrices can be constructed. The resulting "projection-matrix method" is advantageous, especially when the scanning trajectory is irregular. The algorithms presented are useful in iterative methods of image reconstruction and enhancement procedures, apart from their well-known role in visualization and volume rendering. Reprojections of 3-D patient data compare favorably with the original X-ray projections obtained from a prototype C-arm system. The algorithms for reprojection can be modified to compute perspective maximum intensity projection.     

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.     

A high-speed reconstruction from projections using direct Fourier method with optimized parameters-an experimental analysis

Some issues of the direct Fourier method (DFM) implementation are discussed. A hybrid spline-linear interpolation for the DFM is proposed. The results of comprehensive simulation research are presented. The following reconstruction problems and parameters are emphasized: interpolation, increasing the radial density of the polar raster, filtering, the 2-D inverse Fourier transformation dimension, and considering the cases of noiseless and noisy input data. For the a priori prescribed resolution of the reconstructed image, values of reconstruction parameters have been determined which are optimal with regard to reconstruction quality and computation cost. The computational requirements of the DFM algorithm which correspond to distinct interpolation schemes are compared to one another for CT and MR tomography, respectively. The estimations obtained are compared to computational characteristics of the convolution backprojection method.     

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     

Anti-aliasing weighting functions for single-slice helical CT

Spatially variant longitudinal aliasing plagues most volumes reconstructed from single-slice helical computed tomography data, and its presence can degrade resolution and distort image structures. We have recently developed a Fourier-based approach to longitudinal interpolation in helical computed tomography that can, for scans performed at pitch 1 or lower, essentially eliminate this longitudinal aliasing by exploiting a generalization of the Whittaker-Shannon sampling theorem whose conditions are satisfied by the interlaced pairs of direct and complementary longitudinal samples. However, the algorithm is computationally intensive and cannot be pipelined. In this paper, we address this shortcoming by deriving two spatial-domain, projection-data weighting functions that approximate the application of the Fourier-based approach, and preserve its aliasing suppression properties to some degree, while allowing for a pipelined implementation. The first approach, which we call simply 180AA, for anti-aliasing, is a direct spatial-domain approximation of the 180FT approach. The second approach, which we call 180BSP, is based on an approximate generalized interpolation approach making use of B-splines. Studies of aliasing and resolution properties in reconstructions from simulated data indicate that while the 180AA and 180BSP approaches do not perfectly replicate the favorable aliasing suppression and resolution properties of the 180FT approach, they do represent an improvement over the clinically standard 180LI approach on these fronts.     

A cone-beam reconstruction algorithm for circle-plus-arc data-acquisition geometry

In cone-beam computerized tomography (CT), projections acquired with the focal spot constrained on a planar orbit cannot provide a complete set of data to reconstruct the object function exactly. There are severe distortions in the reconstructed noncentral transverse planes when the cone angle is large. In this work, a new method is proposed which can obtain a complete set of data by acquiring cone-beam projections along a circle-plus-arc orbit. A reconstruction algorithm using this circle-plus-arc orbit is developed, based on the Radon transform and Grangeat's formula. This algorithm first transforms the cone-beam projection data of an object to the first derivative of the three-dimensional (3-D) Radon transform, using Grangeat's formula, and then reconstructs the object using the inverse Radon transform. In order to reduce interpolation errors, new rebinning equations have been derived accurately, which allows one-dimensional (1-D) interpolation to be used in the rebinning process instead of 3-D interpolation. A noise-free Defrise phantom and a Poisson noise-added Shepp-Logan phantom were simulated and reconstructed for algorithm validation. The results from the computer simulation indicate that the new cone-beam data-acquisition scheme can provide a complete set of projection data and the image reconstruction algorithm can achieve exact reconstruction. Potentially, the algorithm can be applied in practice for both a standard CT gantry-based volume tomographic imaging system and a C-arm-based cone-beam tomographic imaging system, with little mechanical modification required.     

Fast fully 3-D image reconstruction in PET using planograms

We present a method of performing fast and accurate three-dimensional (3-D) backprojection using only Fourier transform operations for line-integral data acquired by planar detector arrays in positron emission tomography. This approach is a 3-D extension of the two-dimensional (2-D) linogram technique of Edholm. By using a special choice of parameters to index a line of response (LOR) for a pair of planar detectors, rather than the conventional parameters used to index a LOR for a circular tomograph, all the LORs passing through a point in the field of view (FOV) lie on a 2-D plane in the four-dimensional (4-D) data space. Thus, backprojection of all the LORs passing through a point in the FOV corresponds to integration of a 2-D plane through the 4-D "planogram." The key step is that the integration along a set of parallel 2-D planes through the planogram, that is, backprojection of a plane of points, can be replaced by a 2-D section through the origin of the 4-D Fourier transform of the data. Backprojection can be performed as a sequence of Fourier transform operations, for faster implementation. In addition, we derive the central-section theorem for planogram format data, and also derive a reconstruction filter for both backprojection-filtering and filtered-backprojection reconstruction algorithms. With software-based Fourier transform calculations we provide preliminary comparisons of planogram backprojection to standard 3-D backprojection and demonstrate a reduction in computation time by a factor of approximately 15.     

Volume Registration Using the 3-D Pseudopolar Fourier Transform

This paper introduces an algorithm for the registration of rotated and translated volumes using the three-dimensional (3-D) pseudopolar Fourier transform, which accurately computes the Fourier transform of the registered volumes on a near-spherical 3-D domain without using interpolation. We propose a three-step procedure. The first step estimates the rotation axis. The second step computes the planar rotation relative to the rotation axis. The third step recovers the translational displacement. The rotation estimation is based on Euler's theorem, which allows one to represent a 3-D rotation as a planar rotation around a 3-D rotation axis. This axis is accurately recovered by the 3-D pseudopolar Fourier transform using radial integrations. The residual planar rotation is computed by an extension of the angular difference function to cylindrical motion. Experimental results show that the algorithm is accurate and robust to noise.     

Efficient fully 3-D iterative SPECT reconstruction with Monte Carlo-based scatter compensation

Quantitative accuracy of single photon emission computed tomography (SPECT) images is highly dependent on the photon scatter model used for image reconstruction. Monte Carlo simulation (MCS) is the most general method for detailed modeling of scatter, but to date, fully three-dimensional (3-D) MCS-based statistical SPECT reconstruction approaches have not been realized, due to prohibitively long computation times and excessive computer memory requirements. MCS-based reconstruction has previously been restricted to two-dimensional approaches that are vastly inferior to fully 3-D reconstruction. Instead of MCS, scatter calculations based on simplified but less accurate models are sometimes incorporated in fully 3-D SPECT reconstruction algorithms. We developed a computationally efficient fully 3-D MCS-based reconstruction architecture by combining the following methods: 1) a dual matrix ordered subset (DM-OS) reconstruction algorithm to accelerate the reconstruction and avoid massive transition matrix precalculation and storage; 2) a stochastic photon transport calculation in MCS is combined with an analytic detector modeling step to reduce noise in the Monte Carlo (MC)-based reprojection after only a small number of photon histories have been tracked; and 3) the number of photon histories simulated is reduced by an order of magnitude in early iterations, or photon histories calculated in an early iteration are reused. For a 64 x 64 x 64 image array, the reconstruction time required for ten DM-OS iterations is approximately 30 min on a dual processor (AMD 1.4 GHz) PC, in which case the stochastic nature of MCS modeling is found to have a negligible effect on noise in reconstructions. Since MCS can calculate photon transport for any clinically used photon energy and patient attenuation distribution, the proposed methodology is expected to be useful for obtaining highly accurate quantitative SPECT images within clinically acceptable computation times.     

Evaluating performance of reconstruction algorithms for 3-D [15O] water PET using subtraction analysis

Positron emission tomography (PET) [15O] activation studies have benefited significantly from three-dimensional (3-D) data acquisition. However, they have been slow to take advantage of new 3-D reconstruction techniques. Compared with the widely used 3-D reprojection reconstruction (3DRP), the advantage of signal and noise for iterative algorithms has been outweighed by concern about long and complicated reconstruction procedures and inconsistent performance. Most pseudo-3-D algorithms, such as rebinning methods, aim at increasing the speed of reconstruction but lack further resolution improvement or noise control. Although many evaluations have been conducted through simulations and phantom experiments, the spatially varying nature of signal and noise and the complexity of biological effects have complicated the interpretation of real data based on simulation or phantom results. We have taken a different approach and used the analysis of real data directly as a measure with which to compare three reconstruction algorithms: 3DRP, iterative filtered backprojection with median root prior (IFBP-MRP), and Fourier rebinning followed by two-dimensional (2-D) filtered backprojection (FORE-FBP) for [15O] PET. Two subjects, each with 32 scans acquired in four sessions during a finger opposition motor task, are analyzed using subtraction. A fixed volume-of-interest (VOI) measurement in regions related to the task demonstrates that at high resolution, IFBP-MRP has the best signal-to-noise performance followed by 3DRP and FORE-FBP; however, this advantage gradually diminishes as the resolution decreases. For a voxel measurement derived from the image of each reconstruction, all three algorithms are capable of detecting highly activated regions. Although there are some differences in the size, shape, and center location of the activated foci, our preliminary results suggest that IFBP-MRP does offer enhanced signal with some noise control compared with 3DRP for the analysis of high-resolution images. If images are to be analyzed at an intermediate to lower resolution, FORE-FBP provides a significant reduction of reconstruction time compared with 3DRP.