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.     

Analysis of nearly cylindrical antennas and scattering problemsusing a spectrum of two-dimensional solutions

This paper presents a powerful method for analysing antennas which can be considered principally two-dimensional (2-D) or cylindrical, except for some three-dimensional (3-D) physical or equivalent sources, e.g., dipoles or slots. It is shown by Fourier transform techniques that such antennas can be analyzed as 2-D problems with harmonic longitudinal field variation. The radiation pattern can often be determined directly from a finite set of such 2-D solutions, each one obtained by any method, e.g., the moment method. The mutual interaction between the cylindrical scatterer and the sources must be calculated to determine the exact current distribution on the sources and their impedances or admittances. This is facilitated by performing an inverse Fourier transform of an infinite spectrum of the numerical 2-D solutions followed by a moment method solution in the spatial domain to satisfy the boundary conditions on the 3-D equivalent sources themselves. The inverse Fourier transform is simplified by the use of asymptote extraction. The method is in itself a hybrid technique as one method is used to solve the harmonic 2-D problem, and the other to solve for the source currents     

A nonseparable VLSI architecture for two-dimensional discreteperiodized wavelet transform

A modified two-dimensional (2-D) discrete periodized wavelet transform (DPWT) based on the homeomorphic high-pass filter and the 2-D operator correlation algorithm is developed in this paper. The advantages of this modified 2-D DPWT are that it can reduce the multiplication counts and the complexity of boundary data processing in comparison to other conventional 2-D DPWT for perfect reconstruction. In addition, a parallel-pipeline architecture of the nonseparable computation algorithm is also proposed to implement this modified 2-D DPWT. This architecture has properties of noninterleaving input data, short bus width request, and short latency. The analysis of the finite precision performance shows that nearly half of the bit length can be saved by using this nonseparable computation algorithm. The operation of the boundary data processing is also described in detail. In the three-stage decomposition of an N×N image, the latency is found to be N²+2N+18     

Discretized Boundary Equation Method for Two-Dimensional Scattering Problems

A unified approach, named discretized boundary equation (DBE) method, is introduced for two-dimensional (2-D) scattering problems. It is based on the discretization of field expressions for one or two components of the scattered field. The DBEs can be used either on the object surface to obtain the solution directly or on the truncation boundary of a finite difference (FD) or finite element (FE) mesh as termination conditions. This paper describes the general theory of the DBE method and key points or limitations for its implementation. A new on-surface formulation for the solution of scattering by perfectly conducting cylinders is presented as an application of the two-component version of the DBE method and validated through numerical examples. Mesh termination conditions for the FD or FE method are derived based on the one-component formulation of the DBE method and their equivalence and difference to the measured equation of invariance are discussed. In particular, the DBE obtained with the minimum norm least squares solution is investigated thoroughly and its validity and features are demonstrated through numerical results, generated together with the FD method, for scattering by cylinders with various material properties.     

Topology-graph Directed Separating Boundary Surfaces Approximation of Nonmanifold Neuroanatomical Structures: Application to Mouse Brain Olfactory Bulb

Boundary surface approximation of 3-D neuroanatomical regions from sparse 2-D images (e.g., mouse brain olfactory bulb structures from a 2-D brain atlas) has proven to be difficult due to the presence of abutting, shared boundary surfaces that are not handled by traditional boundary-representation data structures and surfaces-from-contours algorithms. We describe a data structure and an algorithm to reconstruct separating surfaces among multiple regions from sparse cross-sectional contours. We define a topology graph for each region, that describes the topological skeleton of the region's boundary surface and that shows between which contours the surface patches should be generated. We provide a graph-directed triangulation algorithm to reconstruct surface patches between contours. We combine our graph-directed triangulation algorithm together with a piecewise parametric curve fitting technique to ensure that abutting or shared surface patches are precisely coincident. We show that our method overcomes limitations in 1) traditional contours-from-surfaces algorithms that assume binary, not multiple, regionalization of space, and in 2) few existing separating surfaces algorithms that assume conversion of input into a regular volumetric grid, which is not possible with sparse interplanar resolution.      

Fast modeling of microspherically focused log in a horizontallylayered formation

A microspherically focused log is a focused microresistivity device used for evaluation of the electrical property of the subsurface rock formation for oil and gas exploration. The electrodes are mounted on a flexible rubber pad that is applied against the borehole wall to be in close proximity to the formation. Unlike other nonpad-focused electrode tools that are centered in the borehole such as Dual-Laterolog, the modeling of the microspherically focused log is much more complex and requires three-dimensional (3-D) code in general because the electric field is no longer axially symmetric. However, in a horizontally layered medium, the axial symmetry of the earth formation makes the problem two-and-a-half-dimensional (2.5-D), which is much simpler. In this paper, the authors apply the semi-analytic method to tackle this 2.5-D problem and establish a fast-modeling algorithm. First, they expand the Green's function as a Fourier series in order to transform the 2.5-D problem into a sequence of the axially symmetric (2-D) problems. The semi-analytic method is used to obtain the expression of the Green's function. Applying the focusing conditions of the tool and the solution of the Green's function, we then establish the boundary integral equation with respect to the current density, currents, and potentials on the electrode surfaces, and study its numerical solutions. Then, they compare results computed from the semi-analytical method with those from the finite element method (FEM) to verify its accuracy. Finally, they study the response characteristics of the tool in several different environments by the semi-analytical method     

Exact and approximate rebinning algorithms for 3-D PET data

This paper presents two new rebinning algorithms for the reconstruction of three-dimensional (3-D) positron emission tomography (PET) data. A rebinning algorithm is one that first sorts the 3-D data into an ordinary two-dimensional (2-D) data set containing one sinogram for each transaxial slice to be reconstructed; the 3-D image is then recovered by applying to each slice a 2-D reconstruction method such as filtered-backprojection. This approach allows a significant speedup of 3-D reconstruction, which is particularly useful for applications involving dynamic acquisitions or whole-body imaging. The first new algorithm is obtained by discretizing an exact analytical inversion formula. The second algorithm, called the Fourier rebinning algorithm (FORE), is approximate but allows an efficient implementation based on taking 2-D Fourier transforms of the data. This second algorithm was implemented and applied to data acquired with the new generation of PET systems and also to simulated data for a scanner with an 18° axial aperture. The reconstructed images were compared to those obtained with the 3-D reprojection algorithm (3DRP) which is the standard “exact” 3-D filtered-backprojection method. Results demonstrate that FORE provides a reliable alternative to 3DRP, while at the same time achieving an order of magnitude reduction in processing time     

Improved Bidirectional-Mode Expansion Propagation Algorithm Based on Fourier Series

In this paper, an improved version of a 2-D bidirectional eigenmode expansion propagation algorithm based on Fourier series expansion for modeling optical field distribution in waveguide devices is presented. The algorithm is very simple, numerically robust, and inherently reciprocal. It does not require root searching in the complex plane. Proper truncation rules are used to ensure good convergence properties for TM-polarized waves. Perfectly matched layers as absorbing boundary conditions can be implemented in a very simple way using complex coordinate stretching. The approach represents a transition between purely modal and Fourier expansion methods for modeling guided-wave photonic structures.     

An efficient algorithm to compute the complete set of discreteGabor coefficients

The discrete Gabor (1946) transform algorithm is introduced that provides an efficient method of calculating the complete set of discrete Gabor coefficients of a finite-duration discrete signal from finite summations and to reconstruct the original signal exactly from the computed expansion coefficients. The similarity of the formulas between the discrete Gabor transform and the discrete Fourier transform enables one to employ the FFT algorithms in the computation. The discrete 1-D Gabor transform algorithm can be extended to 2-D as well.     

Accurate analysis of two-dimensional electromagnetic scattering from multilayered periodic arrays of circular cylinders using lattice sums technique

A very efficient and accurate method to characterize two-dimensional (2-D) electromagnetic scattering from multilayered periodic arrays of parallel circular cylinders is presented, using the lattice sums technique, the aggregate T-matrix algorithm, and the generalized reflection and transmission matrices for a layered system. The method is quite general and applies to various configurations of 2-D periodic arrays. The unit cell of the array can contain two or more cylinders, which may be dielectric, conductor, gyrotropic medium, or their mixture with different sizes. The periodic spacing of cylinders along each array plane should be the same over all layers, but otherwise the cylinders in different layers may be different in material properties and dimensions. The numerical examples validate the usefulness and accuracy of the proposed method.     

2.5-D simultaneous multislice reconstruction by series expansion methods from Fourier-rebinned PET data

True three-dimensional (3-D) volume reconstruction from fully 3-D data in positron emission tomography (PET) has only a limited clinical use because of its large computational burden. Fourier rebinning (FORE) of the fully 3-D data into a set of 2-D sinogram data decomposes the 3-D reconstruction process into multiple 2-D reconstructions of decoupled 2-D image slices, thus substantially decreasing the computational burden even in the case when the 2-D reconstructions are performed by an iterative reconstruction algorithm. On the other hand, the approximations involved in the rebinning combined with the decoupling of the image slices cause a certain reduction of image quality, especially when the signal-to-noise ratio of the data is low. We propose a 2.5-D Simultaneous Multislice Reconstruction approach, based on the series expansion principle, where the volume is represented by the superposition of 3-D spherically symmetric bell-shaped basis functions. It takes advantage of the time reduction due to the use of the FORE (2-D) data, instead of the original fully 3-D data, but at the same time uses a 3-D iterative reconstruction approach with 3-D basis functions. The same general approach can be applied to any reconstruction algorithm belonging to the class of series expansion methods (iterative or noniterative) using 3-D basis functions that span multiple slices, and can be used for any multislice sinogram or list mode data whether obtained by a special rebinning scheme or acquired directly by a PET scanner in the 2-D mode using septa. Our studies confirm that the proposed 2.5-D approach provides a considerable improvement in reconstruction quality, as compared to the standard 2-D reconstruction approach, while the reconstruction time is of the same order as that of the 2-D approach and is clinically practical even on a general-purpose computer.     

Analysis of two dimensions sparse multicylinder scattering problem using DD-FDTD method

An algorithm of two-dimensional (2-D) domain decomposition finite-difference time-domain (DD-FDTD) using in sparse multicylinders scattering problem is proposed in this paper. The idea of domain decomposition is introduced to divide the sparse problem domain into several subdomains. All of subdomains are connected by means of the 2-D time domain Green's function. As a result, a great deal of meshes memory between cylinders is removed, especially when the distances between cylinders become large. Furthermore, the coupling between cylinders can be regarded as the equivalent cylindrical wave irradiations. The incident signals of the equivalent cylindrical waves are expressed as cylindrical wave input field array (CWIFA) according to Huygens principle. Then the calculation time is significantly reduced. The near-field to far-field transformation is used to obtain the equivalent cylindrical wave; as a result, the calculation time can be reduced further. The new method has been demonstrated in 2-D multicylinders scattering problem. Numerical results are in good agreement with the results obtained using classical FDTD method and moment of methods (MM).     

A Hybrid SIM-SEM Method for 3-D Electromagnetic Scattering Problems

A new method combining the spectral integral method and spectral element method (SIM-SEM) is proposed to simulate 3-D electromagnetic scattering from inhomogeneous objects. In this hybrid technique (a special case of the finite element boundary integral (FEM-BI) combination), the SEM with the mixed-order curl conforming vector Gauss-Lobatto-Legendre (GLL) basis functions are used to represent the interior electric field with high accuracy, while the SIM on a cuboid surface is used as an exact radiation boundary condition. The Toeplitz property of the SIM matrix is utilized to reduce the memory and CPU time costs in an iterative solver by using the fast Fourier transform algorithm. Unlike the traditional FEM-BI combination where the BI portion usually dominates the computational complexity, the computational costs are much lower in the SIM-SEM method. Numerical results verify the accuracy and capability of this method, confirming that the SIM-SEM method is a good alternative for solving scattering problems from inhomogeneous objects.      

A fast time-domain finite element-boundary integral method forelectromagnetic analysis

A time-domain, finite element-boundary integral (FE-BI) method is presented for analyzing electromagnetic (EM) scattering from two-dimensional (2-D) inhomogeneous objects. The scheme's finite-element component expands transverse fields in terms of a pair of orthogonal vector basis functions and is coupled to its boundary integral component in such a way that the resultant finite element mass matrix is diagonal, and more importantly, the method delivers solutions that are free of spurious modes. The boundary integrals are computed using the multilevel plane-wave time-domain algorithm to enable the simulation of large-scale scattering phenomena. Numerical results demonstrate the capabilities and accuracy of the proposed hybrid scheme     

Two-dimensional Fourier series-based model for nonminimum-phaselinear shift-invariant systems and texture image classification

In this paper, Chi's (1997, 1999) real one-dimensional (1-D) parametric nonminimum-phase Fourier series-based model (FSBM) is extended to two-dimensional (2-D) FSBM for a 2-D nonminimum-phase linear shift-invariant system by using finite 2-D Fourier series approximations to its amplitude response and phase response, respectively. The proposed 2-D FSBM is guaranteed stable, and its complex cepstrum can be obtained from its amplitude and phase parameters through a closed-form formula without involving complicated 2-D phase unwrapping and polynomial rooting. A consistent estimator is proposed for the amplitude estimation of the 2-D FSBM using a 2-D half plane causal minimum-phase linear prediction error filter (modeled by a 2-D minimum-phase FSBM), and then, two consistent estimators are proposed for the phase estimation of the 2-D FSBM using the Chien et al. (1997) 2-D phase equalizer (modeled by a 2-D all-pass FSBM). The estimated 2-D FSBM can be applied to modeling of 2-D non-Gaussian random signals and 2-D signal classification using complex cepstra. Some simulation results are presented to support the efficacy of the three proposed estimators. Furthermore, classification of texture images (2-D non-Gaussian signals) using the estimated FSBM, second-, and higher order statistics is presented together with some experimental results. Finally, we draw some conclusions     

Three-dimensional semi-vectorial wide-angle beam propagation method

A wide-angle Beam Propagation Method (BPM) based on the series expansion technique is proposed. The method employs a finite difference approach and allows extremely dense discretizations. A theoretical analysis supporting this numerical technique is demonstrated. Semi-vectorial formulations are included in this BPM algorithm. It is easily applicable to 3-D simulations. Following an accuracy test with a 2-D problem, several 3-D examples for quasi-TE and -TM modes are demonstrated     

An FDTD algorithm with perfectly matched layers for generaldispersive media

A three-dimensional (3-D) finite difference time domain (FDTD) algorithm with perfectly matched layer (PML) absorbing boundary condition (ABC) is presented for general inhomogeneous, dispersive, conductive media. The modified time-domain Maxwell's equations for dispersive media are expressed in terms of coordinate-stretching variables. We extend the recursive convolution (RC) and piecewise linear recursive convolution (PLRC) approaches to arbitrary dispersive media in a more general form. The algorithm is tested for homogeneous and inhomogeneous media with three typical kinds of dispersive media, i.e., Lorentz medium, unmagnetized plasma, and Debye medium. Excellent agreement between the FDTD results and analytical solutions is obtained for all testing cases with both RC and PLRC approaches. We demonstrate the applications of the algorithm with several examples in subsurface radar detection of mine-like objects, cylinders, and spheres buried in a dispersive half-space and the mapping of a curved interface. Because of their generality, the algorithm and computer program can be used to model biological materials, artificial dielectrics, optical materials, and other dispersive media     

2-D validation of a formulation for the analysis of 3-D bodies thatare periodic in one direction and finite sized in the others

A numerical scheme to analyze three-dimensional bodies that are periodic in one direction (z) and finite sized in the other ones (x, y) is presented. The geometry and material composition of the body can be arbitrary. A new formulation using the conjugate gradient-fast Fourier transform method (CG-FFT) has been developed. The formulation is based on the discretization and resolution of the electric field integral equation (EFIE) in both the real and spectral domains and leads to an efficient and accurate numerical procedure. Results are presented for RCS, equivalent currents and fields inside 3-D periodic structures (infinitely long cylinders with arbitrary shape and material composition). These results are compared with analytical solutions and the agreement is found to be good     

Finite-Element Solutions within Curved Boundaries

The paper shows that a curved boundary need not be approximated by a small number of finite-element sides, resulting in a coarse polygonal approximation to the shape of the region and consequent inaccuracies, but may be defined as accurately as desired. An algorithm and associated mathematics are presented for locating the stationary point of a functional by the Rayleigh-Ritz method with a two-variable power series as a trial function. As a particular example, the functional employed is one that is made stationary by the solution of Poisson's equation under mixed, Dirichlet, or Neumann boundary conditions. The technique is based on the fact that the three boundary conditions are natural ones. Results are presented for a problem involving curved boundaries under mixed and Neumann conditions and for the capacitance calculations of a pair of noncoaxial cylinders having specified potentials. Comparisons are made with the finite-difference method. It is concluded that the finite-element method is, in nearly all aspects, superior to finite differences--particularly when curved boundary modeling errors are reduced. It is expected that the method described will be equally useful for, and quite simple to adapt to, the solution of the Helmholtz equation in an enclosed region.     

Parametric cumulant based phase estimation of 1-D and 2-Dnonminimum phase systems by allpass filtering

This paper proposes a parametric cumulant-based phase-estimation method for one-dimensional (1-D) and two-dimensional (2-D) linear time-invariant (LTI) systems with only non-Gaussian measurements corrupted by additive Gaussian noise. The given measurements are processed by an optimum allpass filter such that a single Mth-order (M⩾3) cumulant of the allpass filter output is maximum in absolute value. It can be shown that the phase of the unknown system of interest is equal to the negative of the phase of the optimum allpass filter except for a linear phase term (a time delay). For the phase estimation of 1-D LTI systems, an iterative 1-D algorithm is proposed to find the optimum allpass filter modeled either by an autoregressive moving average (ARMA) model or by a Fourier series-based model. For the phase estimation of 2-D LTI systems, an iterative 2-D algorithm is proposed that only uses the Fourier series-based allpass model. A performance analysis is then presented for the proposed cumulant-based 1-D and 2-D phase estimation algorithms followed by some simulation results and experimental results with real speech data to justify their efficacy and the analytic results on their performance. Finally, the paper concludes with a discussion and some conclusions