An iterative algorithm for signal reconstruction from bispectrum

The author presents a procedure to reconstruct a (minimum or nonminimum phase) discrete-time signal from its bispectrum. The algorithm is iterative and based on using the method of projections onto convex sets (POCS) in an inner product space in which the vector space consists of real sequences, and vector addition, is defined in terms of the convolution operation. Prior information, such as an energy bound on the signal, can be incorporated into this algorithm. An algorithm that employs energy information was found to produce better results in simulation than one that ignores energy constraints     

An iterative cutting procedure for determining the optimal waferexposure pattern

Conventionally, people focus on defect reduction to improve yield rate. Little research has been done to deal with the problem of optimizing wafer exposure patterns. This paper develops a computer-based procedure to maximize the number of dies possibly produced from a wafer. A program has been developed and implemented in a 6-in wafer fabrication factory in Taiwan. The results validate the practical viability of the proposed procedure     

An iterative algorithm for optimal design of non-frequency-selective FIR digital filters

This paper proposes a novel iterative algorithm for optimal design of non-frequency-selective Finite Impulse Response （FIR） digital filters based on the windowing method. Different from the traditional optimization concept of adjusting the window or the filter order in the windowing design of an FIR digital filter, the key idea of the algorithm is minimizing the approximation error by successively modifying the design result through an iterative procedure under the condition of a fixed window length. In the iterative procedure, the known deviation of the designed frequency response in each iteration from the ideal frequency response is used as a reference for the next iteration. Because the approximation error can be specified variably, the algorithm is applicable for the design of FIR digital filters with different technical requirements in the frequency domain. A design example is employed to illustrate the efficiency of the algorithm.     

An iterative method for optical reconstruction of graded indexprofiles in planar dielectric waveguides

A nondestructive technique for the reconstruction of refractive index profiles in planar waveguides is presented and analyzed. The approach is based on the integral scattering equations, which permit one to relate the refractive index of an inhomogeneous layer to the reflected field intensity at different incidence angles. From this formulation, an iterative algorithm is developed, such as at each iteration step the problem is formulated as the minimization of a functional representing the error between the measurements and the model data. The recovered profile is then used to improve the validity of the approximation in performing the next step. In this approach, the unknown index profile is represented as the sum of a finite series of basis functions avoiding to select a priori the particular functional form (e.g., Gaussian function, complementary error function, etc). The practical effectiveness of this approach is demonstrated by numerically simulating the measurements for different planar waveguides. The influence of measurement uncertainty and noise on the stability of the technique is also evaluated     

一种基于压缩传感和SART的图像重建迭代算法

滤波反投影算法已被广泛应用到CT图像重建领域,但由于算法需要大量的投影数据,会延长扫描时间和累积高剂量的辐射。为了降低辐射的剂量,文中提出一种基于压缩传感和联合代数重建方法 (SART)的迭代算法,将图像的梯度稀疏性与SART图像重建相结合,减小梯度图像的l1范数直至算法迭代结束。实验结果表明,文中算法能利用少量的投影数据准确地重建出图像,减少了由于投影数据不充分而造成的条状伪影。     

Convergence studies on iterative algorithms for image reconstruction

We introduce a general iterative scheme for image reconstruction based on Landweber's method. In our configuration, a sequential block-iterative (SeqBI) version can be readily formulated from a simultaneous block-iterative (SimBI) version, and vice versa. This provides a mechanism to derive new algorithms from known ones. It is shown that some widely used iterative algorithms, such as the algebraic reconstruction technique (ART), simultaneous ART (SART), Cimmino's, and the recently designed diagonal weighting and component averaging algorithms, are special examples of the general scheme. We prove convergence of the general scheme under conditions more general than assumed in earlier studies, for its SeqBI and SimBI versions in the consistent and inconsistent cases, respectively. Our results suggest automatic relaxation strategies for the SeqBI and SimBI versions and characterize the dependence of the limit image on the initial guess. It is found that in all cases the limit is the sum of the minimum norm solution of a weighted least-squares problem and an oblique projection of the initial image onto the null space of the system matrix.     

A local update strategy for iterative reconstruction fromprojections

A method for Bayesian reconstruction which relies on updates of single pixel values, rather than the entire image, at each iteration is presented. The technique is similar to Gauss-Seidel (GS) iteration for the solution of differential equations on finite grids. The computational cost per iteration of the GS approach is found to be approximately equal to that of gradient methods. For continuously valued images, GS is found to have significantly better convergence at modes representing high spatial frequencies. In addition, GS is well suited to segmentation when the image is constrained to be discretely valued. It is shown that Bayesian segmentation using GS iteration produces useful estimates at much lower signal-to-noise ratios than required for continuously valued reconstruction. The convergence properties of gradient ascent and GS for reconstruction from integral projections are analyzed, and simulations of both maximum-likelihood and maximum a posteriori cases are included     

An iterative algorithm for single-frequency estimation

An algorithm for the estimation of the frequency of a complex sinusoid in noise is proposed. The estimator consists of multiple applications of lowpass filtering and decimation, frequency estimation by linear prediction, and digital heterodyning. The estimator has a significantly reduced threshold relative to existing phase-based algorithms and performance close to that of maximum likelihood estimation. In addition, the mean-squared error performance is within 0.7 dB of the Cramer-Rao bound (CRB) at signal-to-noise ratios (SNRs) above threshold. Unlike many autocorrelation and phase-based methods, the proposed algorithm's performance is uniform across a frequency range of -/spl pi/ to /spl pi/. The computational complexity of the algorithm is shown to be favorable compared with maximum likelihood estimation via the fast Fourier transform (FFT) algorithm when significant zero-padding is required.     

An iterative algorithm for delay-constrained minimum-costmulticasting

The bounded shortest multicast algorithm (BSMA) is presented for constructing minimum-cost multicast trees with delay constraints. The BSMA can handle asymmetric link characteristics and variable delay bounds on destinations, specified as real values, and minimizes the total cost of a multicast routing tree. Instead of the single-pass tree construction approach used in most previous heuristics, the new algorithm is based on a feasible-search optimization strategy that starts with the minimum-delay multicast tree and monotonically decreases the cost by iterative improvement of the delay-bounded multicast tree. The BSMA's expected time complexity is analyzed, and simulation results are provided showing that BSMA can achieve near-optimal cost reduction with fast execution     

A splitting-based iterative algorithm for accelerated statistical X-ray CT reconstruction

Statistical image reconstruction using penalized weighted least-squares (PWLS) criteria can improve image-quality in X-ray computed tomography (CT). However, the huge dynamic range of the statistical weights leads to a highly shift-variant inverse problem making it difficult to precondition and accelerate existing iterative algorithms that attack the statistical model directly. We propose to alleviate the problem by using a variable-splitting scheme that separates the shift-variant and ("nearly") invariant components of the statistical data model and also decouples the regularization term. This leads to an equivalent constrained problem that we tackle using the classical method-of-multipliers framework with alternating minimization. The specific form of our splitting yields an alternating direction method of multipliers (ADMM) algorithm with an inner-step involving a "nearly" shift-invariant linear system that is suitable for FFT-based preconditioning using cone-type filters. The proposed method can efficiently handle a variety of convex regularization criteria including smooth edge-preserving regularizers and nonsmooth sparsity-promoting ones based on the l(1)-norm and total variation. Numerical experiments with synthetic and real in vivo human data illustrate that cone-filter preconditioners accelerate the proposed ADMM resulting in fast convergence of ADMM compared to conventional (nonlinear conjugate gradient, ordered subsets) and state-of-the-art (MFISTA, split-Bregman) algorithms that are applicable for CT.     

On the iterative approximation of optimal joint source-channeldecoding

Joint source-channel decoding is formulated as an estimation problem. The optimal solution is stated and it is shown that it is not feasible in many practical systems due to its complexity. Therefore, a novel iterative procedure for the approximation of the optimal solution is introduced, which is based on the principle of iterative decoding of turbo codes. New analytical expressions for different types of information in the optimal algorithm are used to derive the iterative approximation. A direct comparison of the performance of the optimal algorithm and its iterative approximation is given for a simple transmission system with “short” channel codewords. Furthermore, the performance of iterative joint source-channel decoding is investigated for a more realistic system     

An iterative multiuser decoder for near-capacity communications

The combination of forward error correction (FEC) coding and random interleaving is shown to overcome the limitations of multiuser detectors/decoders when the user cross correlations are high. In particular, one can asymptotically achieve single-user performance in a highly correlated multiuser system. In addition, an optimal iterative multiuser detector is derived from iterative techniques for cross-entropy minimization. A practical suboptimal implementation of this algorithm is presented, and simulations demonstrate that, even with highly correlated users, it achieves optimal asymptotic efficiency. The effects of the theoretical limits on channel capacity are evident in many of the simulation results. The complexity of the suboptimal algorithm is approximately (O(2^K)+O(2^κ)) per bit per iteration where K is the number of users and κ is the code constraint length     

An iterative method for solving electrostatic problems

The method of steepest descent is applied to the solution of electrostatic problems. The relation between this method and the Rayleigh-Ritz, Galerkin's, and the method of least squares is outlined. Also, explicit error formulas are given for the rate of convergence for this method. It is shown that this method is also suitable for solving singular operator equations. In that case this method monotonically converges to the solution with minimum norm. Finally, it is shown that the technique yields as a by-product the smallest eigenvalue of the operator in the finite dimensional space in which the problem is solved. Numerical results are presented only for the electrostatic case to illustrate the validity of this procedure which show excellent agreement with other available data.     

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.     

An iterative maximum-likelihood polychromatic algorithm for CT

A new iterative maximum-likelihood reconstruction algorithm for X-ray computed tomography is presented. The algorithm prevents beam hardening artifacts by incorporating a polychromatic acquisition model. The continuous spectrum of the X-ray tube is modeled as a number of discrete energies. The energy dependence of the attenuation is taken into account by decomposing the linear attenuation coefficient into a photoelectric component and a Compton scatter component. The relative weight of these components is constrained based on prior material assumptions. Excellent results are obtained for simulations and for phantom measurements. Beam-hardening artifacts are effectively eliminated. The relation with existing algorithms is discussed. The results confirm that improving the acquisition model assumed by the reconstruction algorithm results in reduced artifacts. Preliminary results indicate that metal artifact reduction is a very promising application for this new algorithm.     

An iterative algorithm for X-ray CT fluoroscopy

X-ray computed tomography fluoroscopy (CTF) enables image guidance of interventions, synchronization of scanning with contrast bolus arrival, and motion analysis. However, filtered backprojection (FB), the current method for CTF image reconstruction, is subject to motion and metal artifacts from implants, needles, or other surgical instruments. Reduced target lesion conspicuity may result from increased image noise associated with reduced tube current. In this report, the authors adapt the row-action expectation-maximization (EM) algorithm for CTF. Because time-dependent variation in images is localized during CTF, the row-action EM-like algorithm allows rapid convergence. More importantly, this iterative CTF algorithm has fewer metal artifacts and better low-contrast performance than FB     

An iterative method for solving scattering problems

An iterative method is developed for computing the current induced by plane wave excitation on conducting bodies of arbitrary shape. In this method, the scattering body is divided into lit- and shadow-side regions separated by the geometric optics boundary. The induced current at any point on the surface of the scatterer is expressed as the sum of an approximate optics current and a correction current. Both of these currents are computed by iteration for the lit and shadow regions separately. The general theory is presented and applied to the problems of scattering from a two-dimensional cylinder of circular and square cross sections. The results are compared with the method of moments and good agreement is obtained. This method does not give erroneous results at internal resonances of the scatterer, does not suffer from computer storage problems and can be extended to nonperfect conductors as well as to three-dimensional bodies.     

An iterative measured equation technique for electromagneticproblems

An iterative measured equation technique (IMET) is presented for a numerical solution of electromagnetic problems. This technique is an extension and improvement of the method of measured equation of invariance (MEI). In this technique, an iterative scheme is designed in such away that a new set of metrons used to generate the measured equations is formed in each iteration based on the solution of the previous iteration. The new metrons are more meaningful in that they converge to the physical quantity of interest such as the surface current density for electrodynamic problems and the surface charge density for electrostatic problems. The IMET offers several advantages over the MEI method because it requires only two mesh layers, resulting in a significant reduction in the memory requirement and computing time. More importantly, it provides a means for a systematic improvement of the accuracy of solution. The IMET is applied successfully to two-dimensional (2-D) electrodynamic and three-dimensional (3-D) electrostatic problems. Numerical results show that the technique is highly accurate and the iterative process converges very quickly, usually within two iterations     

Constrained iterative reconstruction by the conjugate gradient method

The conjugate gradient method incorporating the object-extent constraint is applied to image reconstruction of a three-dimensional object using an incomplete projection-data set. The missing information is recovered by constraining the solution with the knowledge of the outer boundary of the object-extent which may be a priori measured or known. The algorithm is derived from the least-squares criterion as an advanced version of conventional iterative reconstruction algorithms such as SIRT (Simultaneous Iterative Reconstruction Technique) and ILST (Iterative Least Squares Technique). In the case of reconstruction from noisy projection data, a method based on the minimum mean-square error criterion is also proposed. Computer simulated reconstruction images of a phantom using limited angle and number of views are presented. The result shows that the conjugate gradient method incorporating the object-extent constraining provides the fastest convergence and the least error.