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.     

A new numerical Fourier transform in d-dimensions

The classical method of numerically computing Fourier transforms of digitized functions in one or in d-dimensions is the so-called discrete Fourier transform (DFT) efficiently implemented as fast Fourier transform (FFT) algorithms. In many cases, the DFT is not an adequate approximation to the continuous Fourier transform, and because the DFT is periodical, spectrum aliasing may occur. The method presented in this contribution provides accurate approximations of the continuous Fourier transform with similar time complexity. The assumption of signal periodicity is no longer posed and allows the computation of numerical Fourier transforms in a broader domain of frequency than the usual half-period of the DFT. In addition, this method yields accurate numerical derivatives of any order and polynomial splines of any odd degree. The numerical error on results is easily estimated. The method is developed in one and in d dimensions, and numerical examples are presented.     

Limitations of Imaging with First-Order Diffraction Tomography

In this paper, the results of computer simulations used to determine the domains of applicability of the first-order Born and Rytov approximations in diffraction tomography for cross-sectional (or three-dimensional) imaging of biosystems are shown. These computer simulations were conducted on single cylinders, since in this case analytical expressions are available for the exact scattered fields. The simulations establish the first-order Born approximation to be valid for objects where the product of the relative refractive index and the diameter of the cylinder is less than 0.35 lambda. The first-order Rytov approximation is valid with essentially no constraint on the size of the cylinders; however, the relative refractive index must be less than a few percent. We have also reviewed the assumptions made in the first-order Born and Rytov approximations for diffraction tomography. Further, we have reviewed the derivation of the Fourier Diffraction projection Theorem, which forms the basis of the first-order reconstruction algorithms. We then show how this derivation points to new FFT-based implementations for the higher order diffraction tomography algorithms that are currently being developed.     

A Convolution and Correlation Theorem for the Linear Canonical Transform and Its Application

As a generalization of the fractional Fourier transform (FRFT), the linear canonical transform (LCT) plays an important role in many fields of optics and signal processing. Many properties for this transform are already known, but the correlation theorem, similar to the version of the Fourier transform (FT), is still to be determined. In this paper, firstly, we introduce a new convolution structure for the LCT, which is expressed by a one dimensional integral and easy to implement in filter design. The convolution theorem in FT domain is shown to be a special case of our achieved results. Then, based on the new convolution structure, the correlation theorem is derived, which is also a one dimensional integral expression. Last, as an application, utilizing the new convolution theorem, we investigate the sampling theorem for the band limited signal in the LCT domain. In particular, the formulas of uniform sampling and low pass reconstruction are obtained.     

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).     

极低频垂直偶极子在地-电离层中场的数值积分算法

针对地-电离层空腔中极低频(ELF)场强问题,提出一种应用于任意复数角v的勒让德函数数值积分算法,并与已有渐近计算法、级数展开法进行比对,结果表明:该方法使用频率范围更广,计算精度、效率更高。利用此数值积分算法,计算了垂直偶极子激励的30Hz以下典型频点的场强分布,所得场强分布符合物理规律,无损耗条件下舒曼谐振频率与前人计算结果完全一致,印证了ELF垂直偶极子在地-电离层腔体中场的数值积分算法的正确性。     

Convolution-Based Trigonometric Interpolation of Band-Limited Signals

This paper presents a method to obtain a trigonometric polynomial that accurately interpolates a given band-limited signal from a finite sequence of samples. The polynomial delivers accurate approximations in the range covered by the sequence, except for a short frame close to the range limits. Besides, its accuracy increases exponentially with the frame width. The method is based on using a band-limited window in order to reduce the truncation error of a convolution series. It is shown that the polynomial can be efficiently constructed and evaluated using algorithms designed for the discrete Fourier transform (DFT). Specifically, two basic procedures are presented, one based on the fast Fourier transform (FFT), and another based on a recursive update algorithm for the short-time FFT. The paper contains three applications. The first is a variable fractional delay (VFD) filter, which consists of a short-time FFT combined with the evaluation of a trigonometric polynomial. This filter has low complexity and can be implemented using CORDIC rotations. The second is the interpolation of nonuniform Fourier summations, where the proposed method eliminates the need to interpolate any kernel sample. Finally, the third can be viewed as a generalization of the FFT convolution algorithm and makes it possible to interpolate the output of an finite-impulse-response (FIR) filter efficiently.      

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.     

Cone-beam reconstruction using the backprojection of locally filtered projections

This paper describes a flexible new methodology for accurate cone beam reconstruction with source positions on a curve (or set of curves). The inversion formulas employed by this methodology are based on first backprojecting a simple derivative in the projection space and then applying a Hilbert transform inversion in the image space. The local nature of the projection space filtering distinguishes this approach from conventional filtered-backprojection methods. This characteristic together with a degree of flexibility in choosing the direction of the Hilbert transform used for inversion offers two important features for the design of data acquisition geometries and reconstruction algorithms. First, the size of the detector necessary to acquire sufficient data for accurate reconstruction of a given region is often smaller than that required by previously documented approaches. In other words, more data truncation is allowed. Second, redundant data can be incorporated for the purpose of noise reduction. The validity of the inversion formulas along with the application of these two properties are illustrated with reconstructions from computer simulated data. In particular, in the helical cone beam geometry, it is shown that 1) intermittent transaxial truncation has no effect on the reconstruction in a central region which means that wider patients can be accommodated on existing scanners, and more importantly that radiation exposure can be reduced for region of interest imaging and 2) at maximum pitch the data outside the Tam-Danielsson window can be used to reduce image noise and thereby improve dose utilization. Furthermore, the degree of axial truncation tolerated by our approach for saddle trajectories is shown to be larger than that of previous methods.     

Sampling and Sampling Rate Conversion of Band Limited Signals in the Fractional Fourier Transform Domain

The fractional Fourier transform (FRFT) has become a very active area in signal processing community in recent years, with many applications in radar, communication, information security, etc., This study carefully investigates the sampling of a continuous-time band limited signal to obtain its discrete-time version, as well as sampling rate conversion, for the FRFT. Firstly, based on product theorem for the FRFT, the sampling theorems and reconstruction formulas are derived, which explain how to sample a continuous-time signal to obtain its discrete-time version for band limited signals in the fractional Fourier domain. Secondly, the formulas and significance of decimation and interpolation are studied in the fractional Fourier domain. Using the results, the sampling rate conversion theory for the FRFT with a rational fraction as conversion factor is deduced, which illustrates how to sample the discrete-time version without aliasing. The theorems proposed in this study are the generalizations of the conventional versions for the Fourier transform. Finally, the theory introduced in this paper is validated by simulations.     

D.F.T. computation by fast polynomial transform algorithms

A new method is introduced for the fast computation of multidimensional discrete Fourier transforms (d.f.t.). We show that some multidimensional d.f.t.s are mapped efficiently into one-dimensional d.f.t.s by using a single polynomial transform and some auxiliary calculations. Since polynomial transforms can be computed without multiplications, this approach reduces significantly the number of operations over the conventional fast Fourier transform (f.f.t.) and is therefore attractive for image-processing applications.     

A unified framework for multi-sensor HDR video reconstruction

One of the most successful approaches to modern high quality HDR-video capture is to use camera setups with multiple sensors imaging the scene through a common optical system. However, such systems pose several challenges for HDR reconstruction algorithms. Previous reconstruction techniques have considered debayering, denoising, resampling (alignment) and exposure fusion as separate problems. In contrast, in this paper we present a unifying approach, performing HDR assembly directly from raw sensor data. Our framework includes a camera noise model adapted to HDR video and an algorithm for spatially adaptive HDR reconstruction based on fitting of local polynomial approximations to observed sensor data. The method is easy to implement and allows reconstruction to an arbitrary resolution and output mapping. We present an implementation in CUDA and show real-time performance for an experimental 4 Mpixel multi-sensor HDR video system. We further show that our algorithm has clear advantages over existing methods, both in terms of flexibility and reconstruction quality.     

特征分解型离散分数阶Fourier变换

分数阶Fourier变换作为Fourier变换的广义形式,广泛应用于科学计算和研究,离散分数阶Fourier变换是其得以应用的关键。特征分解算法是由可交换对角矩阵得到近似连续Hermite-Gaussian函数的特征向量,再对Hermite-Gaussian函数进行加权和运算。对一种基于数特征分解的方法进行了改进,并进行计算机仿真。仿真结果表明所得的Hermite-Gaussian函数与连续函数的近似度更为优异,从而提高了离散分数阶Fourier变换的近似度。     

New approximate formulations for EM scattering by dielectric objects

The extended Born approximation (ExBorn) has been shown an efficient formulation in the electromagnetic (EM) scattering by dielectric objects in both free-space and air-Earth half-space problems. In most cases, ExBorn is much more accurate than the conventional Born approximation at low frequencies. When the frequency is high or the contrast of dielectric objects is large, however, the ExBorn approximation becomes inaccurate. In this paper, new approximations are proposed for the EM scattering by dielectric objects buried in a lossy Earth, which are also suitable for the case of free space. It has been shown that the zeroth-order form of new approximations is completely equivalent to ExBorn. Hence, high-order approximations can be regarded as high-order ExBorn. Closed-form formulations are derived for the new approximations. Using the fast Fourier transform (FFT), these formulations can be implemented efficiently at a cost of CNlogN, where N is the number of unknowns and C is a small number. Numerical simulations show that high-order ExBorn approximations are much more accurate than the ExBorn approximation.     

Accurate design method for optimum gain pyramidal horns

The horn synthesis problem is formulated in terms of a fourth degree polynomial. Explicit analytical formulas are subsequently derived for the accurate design of standard gain pyramidal horn antennas. These formulas do not need the application of iterative techniques, unlike existing methods, are simpler to use, and are not restricted to high-gain horn design     

Taylor series based two-dimensional digital differentiators

A new type of Taylor series based 2-D finite difference approximation is presented, and it is shown that the coefficients of these approximations are not unique. Explicit formulas are presented for one of the possible sets of coefficients for an arbitrary order, by extending the previously presented 1-D approximations. These coefficients are implemented as maximally linear 2-D FIR digital differentiators, and their formulas are modified to narrow the inaccuracy regions on the resultant frequency responses, close to the Nyquist frequencies     

Platelets: a multiscale approach for recovering edges and surfaces in photon-limited medical imaging

The nonparametric multiscale platelet algorithms presented in this paper, unlike traditional wavelet-based methods, are both well suited to photon-limited medical imaging applications involving Poisson data and capable of better approximating edge contours. This paper introduces platelets, localized functions at various scales, locations, and orientations that produce piece-wise linear image approximations, and a new multiscale image decomposition based on these functions. Platelets are well suited for approximating images consisting of smooth regions separated by smooth boundaries. For smoothness measured in certain H?lder classes, it is shown that the error of m-term platelet approximations can decay significantly faster than that of m-term approximations in terms of sinusoids, wavelets, or wedgelets. This suggests that platelets may outperform existing techniques for image denoising and reconstruction. Fast, platelet-based, maximum penalized likelihood methods for photon-limited image denoising, deblurring and tomographic reconstruction problems are developed. Because platelet decompositions of Poisson distributed images are tractable and computationally efficient, existing image reconstruction methods based on expectation-maximization type algorithms can be easily enhanced with platelet techniques. Experimental results suggest that platelet-based methods can outperform standard reconstruction methods currently in use in confocal microscopy, image restoration, and emission tomography.     

Frequency-dependent mutual resistance and inductance formulas for coupled IC interconnects on an Si-SiO2 substrate

A highly accurate closed-form approximation of frequency-dependent mutual impedance per unit length of a lossy silicon substrate coplanar-strip IC interconnects is developed. The derivation is based on a quasi-stationary full-wave analysis and Fourier integral transformation. The derivation shows the mathematical approximations which are needed in obtaining the desired expressions. As a result, for the first time, we present a new simple, yet surprisingly accurate closed-form expression which yield accurate estimates of frequency-dependent mutual resistance and inductance per unit length of coupled interconnects for a wide range of geometrical and technological parameters. The developed formulas describe the mutual line impedance behaviour over the whole frequency range ( i.e. also in the transition region between the skin effect, slow wave, and dielectric quasi-TEM modes). The results have been compared with the reported data obtained by the modified quasi-static spectral domain approach and new CAD-oriented equivalent-circuit model procedure.     

Harmonic analysis of periodic discontinuous functions (new method). Part II—Polynomial functions

A new method to determine Fourier coefficients of periodic discontinuous polynomial functions is presented. A method recently developed for exponential functions can be modified and applied to polynomial functions. Applications of the method is illustrated by example.     

Predictive (un)distortion model and 3-D reconstruction by biplane snakes

This paper is concerned with the three-dimensional (3-D) reconstruction of coronary vessel centerlines and with how distortion of X-ray angiographic images affects it. Angiographies suffer from pincushion and other geometrical distortions, caused by the peripheral concavity of the image intensifier (II) and the nonlinearity of electronic acquisition devices. In routine clinical practice, where a field-of-view (FOV) of 17-23 cm is commonly used for the acquisition of coronary vessels, this distortion introduces a positional error of up to 7 pixels for an image matrix size of 512 x 512 and an FOV of 17 cm. This error increases with the size of the FOV. Geometrical distortions have a significant effect on the validity of the 3-D reconstruction of vessels from these images. We show how this effect can be reduced by integrating a predictive model of (un)distortion into the biplane snakes formulation for 3-D reconstruction. First, we prove that the distortion can be accurately modeled using a polynomial for each view. Also, we show that the estimated polynomial is independent of focal length, but not of changes in anatomical angles, as the II is influenced by the earth's magnetic field. Thus, we decompose the polynomial into two components: the steady and the orientation-dependent component. We determine the optimal polynomial degree for each component, which is empirically determined to be five for the steady component and three for the orientation-dependent component. This fact simplifies the prediction of the orientation-dependent polynomial, since the number of polynomial coefficients to be predicted is lower. The integration of this model into the biplane snakes formulation enables us to avoid image unwarping, which deteriorates image quality and therefore complicates vessel centerline feature extraction. Moreover, we improve the biplane snake behavior when dealing with wavy vessels, by means of using generalized gradient vector flow. Our experiments show that the proposed methods in this paper decrease up to 88% the reconstruction error obtained when geometrical distortion effects are ignored. Tests on imaged phantoms and real cardiac images are presented as well.