Incremental backprojection algorithm: modification of the searching flow scheme and utilization of the relationship among projection views

A two-dimensional (2-D) search flow scheme is proposed for the incremental backprojection algorithm. In this scheme, the searching direction in a beam is determined only by the distance from the current pixel to the corresponding ray; no pixels outside the beam are involved in the procedure. In addition, the geometrical relationships between the image grids and the projection rays in different views are fully exploited to further reduce the search operations. It is found that backprojection of four views can be performed at the same time, and the search operation is only required for one of them if the number of views is even. Thus, backprojection is accomplished on a quartet-by-quartet of views basis as well as on beam-by-beam basis. These approaches not only minimize the number of search operations but also possess a simple algorithm structure. Implementation results obtained with an AST-386 computer for the incremental backprojection algorithm using this search flow scheme and the relationship among projection views show that the processing time can be reduced by a factor of about 2.     

聚束SAR快速卷积反投影成像算法的研究

对应用于聚束合成孔径雷达成像的卷积反投影(CBP)算法进行了研究,提出了一种新的快速反投影算法,在分割图像及角度降采样基础上,采用递归调用方法,降低了CBP算法的计算量,相对于直接反投影的计算量O(N3),快速反投影算法的计算复杂度可降低为O(N21bN)。同时讨论了递归参数和角过采样参数的选择对算法的影响,仿真了四种插值方法对运算性能的影响,从而分析了计算复杂度和精确度的关系,并且通过与直接反投影算法仿真结果的比较,验证了快速卷积反投影算法在较小均方根误差水平下可以显著减小计算量。     

Characterization of the modulation transfer function of discrete filtered backprojection

A mathematical expression for the modulation transfer function (MTF) of image reconstruction by discrete filtered backprojection (DFBP) is derived. A simulation study is used to investigate the dependence of the MTF of DFBP on: (1) the number of projection views; (2) the type of ramp filter used; (3) the interpolation method used during backprojection; and (4) the position of the object. These results were compared to MTFs calculated from point-source single-photon-emission computed tomographic (SPECT) acquisitions in air. The experimentally obtained MTFs contained much of the same structure as the MTFs of DFBP obtained through simulation. It is shown that the discretization of the filtered backprojection process can cause the tomographic transfer function to be anisotropic and nonstationary. However, through proper selection of the methods used in reconstruction, a nearly isotropic and stationary MTF can be obtained.     

On intermediate view estimation in computed tomography

In many applications in computed tomography, practical limitations in data acquisition restrict the number of projections (views). The use of the standard convolution backprojection algorithm for reconstruction from an inadequate number of projections results in view aliasing artifacts. One approach to alleviating the effects of such artifacts consists of artificially increasing the number of views, by estimating a set of intermediate views. Two possible methods of estimating the intermediate views are interpolation and reprojection. In this paper, a study of the two is considered. Based on the merits and demerits of the two methods, a combination of the two methods is investigated. Specifically, a reconstruction from the available sinogram augmented by intermediate view reprojections, and the projections interpolated from the original views and the reprojections, provide an additional improvement with respect to view aliasing artifacts. The advantage of computing reprojections over smaller regions of interest is discussed. When the number of available projections is reasonably high but not adequate to produce an artifact-free reconstruction, estimating the intermediate views by interpolation provides an improvement without much additional degradation, at minimal computational cost.This work was supported by Siemens Medical Systems and by the Medical Research Council of Canada (through grant no. MT-13356). The work of Dr. Holdsworth was supported in part by a Research Scholarship from the Heart and Stroke Foundation of Canada.     

Convolution backprojection image reconstruction for spotlight modesynthetic aperture radar

Convolution backprojection (CBP) image reconstruction has been proposed as a means of producing high-resolution synthetic-aperture radar (SAR) images by processing data directly in the polar recording format which is the conventional recording format for spotlight mode SAR. The CBP algorithm filters each projection as it is recorded and then backprojects the ensemble of filtered projections to create the final image in a pixel-by-pixel format. CBP reconstruction produces high-quality images by handling the recorded data directly in polar format. The CBP algorithm requires only 1-D interpolation along the filtered projections to determine the precise values that must be contributed to the backprojection summation from each projection. The algorithm is thus able to produce higher quality images by eliminating the inaccuracies of 2-D interpolation, as well as using all the data recorded in the spectral domain annular sector more effectively. The computational complexity of the CBP algorithm is O(N (3)).     

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.      

Incremental algorithm-a new fast backprojection scheme for parallel beam geometries

A fast backprojection scheme for parallel beam geometries is proposed. Known as the incremental algorithm, it performs backprojection on a ray-by-ray (beam-by-beam) basis rather than the pixel-by-pixel backprojection in the conventional algorithm. By restructuring a conventional backprojection algorithm, the interdependency of pixel computations (position and value) is transformed to a set of incremental relations for a beam, where a beam is a set of pixels enclosed by two adjacent rays in 2-D computed tomography (CT), and a set of voxels enclosed by four adjacent rays in 3-D CT. To minimize the overhead of searching for the next pixels, a searching flow technique has been developed to implement the first-order and second-order incremental relations for 2-D and 3-D CTs, respectively. The values of all the pixels in each beam (except the first pixel) are computed with additions only, the key idea of the proposed backprojection scheme. The incremental algorithm has been implemented on two different machines and compared to B.F. Shepp and L.A. Logan's (1974) algorithm. The present implementation results show the superiority of this approach over the conventional algorithm.     

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.     

Emission Spectral Tomography Reconstruction Based on Maximum Entropy Interpolation

To improve the performance of optical computed tomography (OpCT) reconstruction in the case of limited projection views, maximum entropy (ME) algorithms were proposed and can achieve better results than traditional ones. However, in the discrete iterative process of ME, the variables of the iterative function are continuous. Hence, interpolation methods ought to be used to improve the precision of the iterative function values. Here, a sinc function interpolation approach was adopted in ME algorithm (SINCME) and its reconstruction results for OpCT with limited views were studied using four typical phantoms. Compared results with ME without interpolation, traditional medical CT back-projection algorithm (BP), and iterative algorithm algebraic reconstruction technique (ART) showed that the SINCME algorithm achieved the best reconstruction results. In an experiment of emission spectral tomography reconstruction, SINCME was also adopted to calculate the three-dimensional distribution of physical parameters of a candle flame. The studies of both algorithm and experiment demonstrated that SINCME met the demand of limited-view OpCT reconstruction.     

O(N2log2N) filtered backprojectionreconstruction algorithm for tomography

We present a new fast reconstruction algorithm for parallel beam tomography. The new algorithm is an accelerated version of the standard filtered backprojection (FBP) reconstruction, and uses a hierarchical decomposition of the backprojection operation to reduce the computational cost from O(N(3)) to O(N(2)log(2 )N). We discuss the choice of the various parameters that affect the behavior of the algorithm, and present numerical studies that demonstrate the cost versus distortion tradeoff. Comparisons with Fourier reconstruction algorithms and a multilevel inversion algorithm by Brandt et al., both of which also have O(N(2)log(2)N) cost, suggest that the proposed hierarchical scheme has a superior cost versus distortion performance. It offers RMS reconstruction errors comparable to the FBP with considerable speedup. For an example with a 512x512-pixel image and 1024 views, the speedup achieved with a particular implementation is over 40 fold, with reconstructions visually indistinguishable from the FBP.     

代数迭代法在激光反射断层成像目标重构中的应用

为了提高激光反射断层成像目标重构的图像质量,在目前激光反射断层成像普遍采用反投影算法重构图像的基础上,将CT成像中常用的迭代重建算法引入到激光反射断层成像的图像重构过程中。分析了反投影算法中的直接反投影、R-L和S-L滤波反投影以及迭代重建算法在图像重构中的性能特性。进行了仿真和外场实验,结果表明:在直接反投影基础上添加了滤波器的反投影算法在减小误差和抑噪能力上都明显提高;另外相比于反投影算法,代数迭代重建算法表现出更好的重建质量,且具有更强的抑噪性能。     

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 Computer Simulation Study of Diffraction Tomography

The filtered backprojection algorithm of X-ray tomography and the filtered backpropagation algorithm developed recently by the author for diffraction tomography are tested in computer simulations of ultrasonic tomography of two-dimensional objects for which the Rytov approximation is valid. It is found that the filtered backprojection algorithm gives unsatisfactory results even for wavelengths much smaller than the smallest scale over which the object varies. The filtered back-propogation algorithm yields, in all cases studied, high-quality reconstructions which are simply low-pass filtered versions of the actual object profile. It is shown that the filtered backpropagation algorithm can be approximated by a modified backprojection algorithm having essentially the same computation requirements as filtered backprojection, but yielding considerably higher quality object reconstructions.     

Algebraic reconstruction in CT from limited views

The author presents an algebraic reconstruction technique (ART) as a viable alternative in computerized tomography (CT) from limited views. Recently, algorithms of iterative reconstruction-reprojection (IRR) based on the method of convolution-backprojection have been proposed for application in limited-view CT. Reprojection was used in an iterative fashion alternating with backprojection as a means of estimating projection values within the sector of missing views. In algebraic methods of reconstruction for CT, only those projections corresponding to known data are required. Reprojection along missing views would merely serve to introduce redundant equations. Computer simulation studies are presented which demonstrate significantly improved reconstructed images achieved by an ART algorithm as compared to IRR methods.     

一种改进的窄带算法在彩色序列图像人脸跟踪中的应用

该文提出了一种基于几何主动轮廓模型的人脸跟踪方法.通过直方图反向投影,使人脸区域表现为一个一致性区域与背景相区别.研究了一种改进的窄带算法实现曲线演化:以等间隔分布的节点表示运动曲线,只在这些节点上计算Level set函数的变化值,窄带区内其余点的Level set值的更新通过插值和查表的方法实现;根据节点的局部图像信息决定节点的运动方向和时间步长值.实验表明该算法能在满足一定精度的前提下,快速地对运动人脸进行跟踪.     

Four-dimensional spectral-spatial imaging using projection reconstruction

An n-dimensional (n-D) filtered backprojection image reconstruction algorithm has been developed and used in the reconstruction of 4-D spectral-spatial magnetic resonance imaging (MRI) data. The algorithm uses n-1 successive stages of 2-D filtered backprojection to reconstruct an n-D image. This approach results in a reduction in computational time on the order of N(n-2) relative to the single-stage technique, where N(n) is the number of elements in an n-D image. The authors describe implementation of the algorithm, including digital filtering and sampling requirements. Images obtained from simulated data are presented to illustrate the accuracy and potential utility of the technique.     

Directional View Interpolation for Compensation of Sparse Angular Sampling in Cone-Beam CT

In flat detector cone-beam computed tomography and related applications, sparse angular sampling frequently leads to characteristic streak artifacts. To overcome this problem, it has been suggested to generate additional views by means of interpolation. The practicality of this approach is investigated in combination with a dedicated method for angular interpolation of 3-D sinogram data. For this purpose, a novel dedicated shape-driven directional interpolation algorithm based on a structure tensor approach is developed. Quantitative evaluation shows that this method clearly outperforms conventional scene-based interpolation schemes. Furthermore, the image quality trade-offs associated with the use of interpolated intermediate views are systematically evaluated for simulated and clinical cone-beam computed tomography data sets of the human head. It is found that utilization of directionally interpolated views significantly reduces streak artifacts and noise, at the expense of small introduced image blur.      

CT扇形束滤波反投影图像重建算法优化

基于等距扇形束滤波反投影(FBP)算法推导了一种新的算法——求导-希尔伯特反投影(DHB)算法,研究了DHB算法在频域对投影的滤波特性。通过理论分析和实验验证,指出由于DHB滤波函数在高频段对于锐截止特性的改善,很大程度上消除了重建图像的抖动现象。并且算法中去掉了反投影算子中的距离加权运算,使计算速度进一步提高。     

Weighted backprojection approach to cone beam 3D projection reconstruction for truncated spherical detection geometry

A new analytical three-dimensional cone beam reconstruction algorithm is presented for truncated spherical detection geometry. The basic idea of the proposed algorithm is the formation of spatially invariant 3D blurred back-projected volumetric image by the use of the weighted backprojection of cone beam projection data and subsequent 3D filtering using an acceptance angle dependent rho filter. The backprojection weighting function is calculated on the basis of each given geometrical condition, i.e. detection geometry or degree of truncation, position of cone beam apex, and backprojection point. The proposed algorithm is derived analytically and is computationally efficient. Performance of the algorithm is evaluated by the reconstruction of 3D volumetric images using simulated data from arbitrarily truncated spherical detector geometries.     

A harmonic decomposition reconstruction algorithm for spatially varying focal length collimators

Spatially varying focal length fan-beam collimators can be used in single photon emission computed tomography to improve detection efficiency and to reduce reconstruction artifacts resulting from the truncation of projection data. It has been proven that there exists no convolution backprojection algorithm for this type of collimator, so a complicated interpolation between two nonparallel projection rays is necessary for existing algorithms. The interpolation may generate blurring and artifacts in the reconstructed images. Based on a harmonic decomposition technique and the translation property of Fourier series, a semifrequency resampling technique is proposed to avoid the above mentioned interpolations. By this technique, the harmonic decomposition of projection data for spatially varying focal length fan beam collimators has the same form as that for parallel-beam collimators in the semifrequency domain (Fourier transform with respect to angular variables only). An alternative version of the inverse Cormack transform is then proposed to reconstruct the images. The derived reconstruction algorithm was implemented in a Pentium II/266 PC computer. Numerical simulations demonstrated its efficiency (3 s for 128×128 reconstruction arrays) and its robust performance (compared to the existing algorithms)