Accelerated perturbation-resilient block-iterative projection methods with application to image reconstruction.

We study the convergence of a class of accelerated perturbation-resilient block-iterative projection methods for solving systems of linear equations. We prove convergence to a fixed point of an operator even in the presence of summable perturbations of the iterates, irrespective of the consistency of the linear system. For a consistent system, the limit point is a solution of the system. In the inconsistent case, the symmetric version of our method converges to a weighted least squares solution. Perturbation resilience is utilized to approximate the minimum of a convex functional subject to the equations. A main contribution, as compared to previously published approaches to achieving similar aims, is a more than an order of magnitude speed-up, as demonstrated by applying the methods to problems of image reconstruction from projections. In addition, the accelerated algorithms are illustrated to be better, in a strict sense provided by the method of statistical hypothesis testing, than their unaccelerated versions for the task of detecting small tumors in the brain from X-ray CT projection data.

Reconstruction from a Few Projections by ℓ(1)-Minimization of the Haar Transform.

Much recent activity is aimed at reconstructing images from a few projections. Images in any application area are not random samples of all possible images, but have some common attributes. If these attributes are reflected in the smallness of an objective function, then the aim of satisfying the projections can be complemented with the aim of having a small objective value. One widely investigated objective function is total variation (TV), it leads to quite good reconstructions from a few mathematically ideal projections. However, when applied to measured projections that only approximate the mathematical ideal, TV-based reconstructions from a few projections may fail to recover important features in the original images. It has been suggested that this may be due to TV not being the appropriate objective function and that one should use the ℓ(1)-norm of the Haar transform instead. The investigation reported in this paper contradicts this. In experiments simulating computerized tomography (CT) data collection of the head, reconstructions whose Haar transform has a small ℓ(1)-norm are not more efficacious than reconstructions that have a small TV value. The search for an objective function that provides diagnostically efficacious reconstructions from a few CT projections remains open.

Perturbation Resilience and Superiorization of Iterative Algorithms.

Iterative algorithms aimed at solving some problems are discussed. For certain problems, such as finding a common point in the intersection of a finite number of convex sets, there often exist iterative algorithms that impose very little demand on computer resources. For other problems, such as finding that point in the intersection at which the value of a given function is optimal, algorithms tend to need more computer memory and longer execution time. A methodology is presented whose aim is to produce automatically for an iterative algorithm of the first kind a "superiorized version" of it that retains its computational efficiency but nevertheless goes a long way towards solving an optimization problem. This is possible to do if the original algorithm is "perturbation resilient," which is shown to be the case for various projection algorithms for solving the consistent convex feasibility problem. The superiorized versions of such algorithms use perturbations that steer the process in the direction of a superior feasible point, which is not necessarily optimal, with respect to the given function. After presenting these intuitive ideas in a precise mathematical form, they are illustrated in image reconstruction from projections for two different projection algorithms superiorized for the function whose value is the total variation of the image.

Perturbation-resilient block-iterative projection methods with application to image reconstruction from projections.

A block-iterative projection algorithm for solving the consistent convex feasibility problem in a finite-dimensional Euclidean space that is resilient to bounded and summable perturbations (in the sense that convergence to a feasible point is retained even if such perturbations are introduced in each iterative step of the algorithm) is proposed. This resilience can be used to steer the iterative process towards a feasible point that is superior in the sense of some functional on the points in the Euclidean space having a small value. The potential usefulness of this is illustrated in image reconstruction from projections, using both total variation and negative entropy as the functional.

On Image Reconstruction from a Small Number of Projections.

Image reconstruction from projections suffers from an inherent difficulty: there are different images that have identical projections in any finite number of directions. However, by identifying the type of image that is likely to occur in an application area, one can design algorithms that may be efficacious in that area even when the number of projections is small. One such approach uses total variation minimization. We report on an algorithm based on this approach, and show that sometimes it produces medically-desirable reconstructions in computerized tomography (CT) even from a small number of projections. However, we also demonstrate that such a reconstruction is not guaranteed to provide the medically-relevant information: when data are collected by an actually CT scanner for a small number projections, the noise in such data may very well result in a tumor in the brain not being visible in the reconstruction.

Volumetric restrictions in single particle 3DEM reconstruction.

3D electron microsscopy aims at the reconstruction of density volumes corresponding to the electrostatic potential distribution of macro-molecules. There are many factors limiting the resolution achievable when this technique is applied to biological macromolecules: microscope imperfections, molecule flexibility, lack of projections from certain directions, unknown angular distribution, noise, etc. In this communication we explore the quality gain in the reconstruction by including a priori knowledge such as particle symmetry, occupied volume, known surface relief, density nonnegativity and similarity to a known volume in order to improve the quality of the reconstruction. If the reconstruction is represented as a series expansion, such constraints can be expressed by set of equations that the expansion coefficients must satisfy. In this work, these equation sets are specified and combined in a novel way with the ART + blobs reconstruction algorithm. The effect of each one on the reconstruction of a realistic phantom is explored. Finally, the application of these restrictions to 3D reconstructions from experimental data are studied.

Classification of heterogeneous electron microscopic projections into homogeneous subsets.

The co-existence of different states of a macromolecular complex in samples used by three-dimensional electron microscopy (3D-EM) constitutes a serious challenge. The single particle method applied directly to such heterogeneous sets is unable to provide useful information about the encountered conformational diversity and produces reconstructions with severely reduced resolution. One approach to solving this problem is to partition heterogeneous projection set into homogeneous components and apply existing reconstruction techniques to each of them. Due to the nature of the projection images and the high noise level present in them, this classification task is difficult. A method is presented to achieve the desired classification by using a novel image similarity measure and solving the corresponding optimization problem. Unlike the majority of competing approaches, the presented method employs unsupervised classification (it does not require any prior knowledge about the objects being classified) and does not involve a 3D reconstruction procedure. We demonstrate a fast implementation of this method, capable of classifying projection sets that originate from 3D-EM. The method's performance is evaluated on synthetically generated data sets produced by projecting 3D objects that resemble biological structures.

Transfer function restoration in 3D electron microscopy via iterative data refinement.

Three-dimensional electron microscopy (3D-EM) is a powerful tool for visualizing complex biological systems. As with any other imaging device, the electron microscope introduces a transfer function (called in this field the contrast transfer function, CTF) into the image acquisition process that modulates the various frequencies of the signal. Thus, the 3D reconstructions performed with these CTF-affected projections are also affected by an implicit 3D transfer function. For high-resolution electron microscopy, the effect of the CTF is quite dramatic and limits severely the achievable resolution. In this work we make use of the iterative data refinement (IDR) technique to ameliorate the effect of the CTF. It is demonstrated that the approach can be successfully applied to noisy data.

The effect of overabundant projection directions on 3D reconstruction algorithms.

The experimental process of collecting images from macromolecules in an electron microscope is such that it does not allow for prior specification of the angular distribution of the projection images. As a consequence, an uneven distribution of projection directions may occur. Concerns have been raised recently about the behavior of 3D reconstruction algorithms for the case of unevenly distributed projections. It has been illustrated on experimental data that in the case of a heavily uneven distribution of projection directions some algorithms tend to elongate the reconstructed volumes along the overloaded direction so much as to make a quantitative biological analysis impossible. In answer to these concerns we have developed a strategy for quantitative comparison and optimization of 3D reconstruction algorithms. We apply this strategy to quantitatively analyze algebraic reconstruction techniques (ART) with blobs, simultaneous iterative reconstruction techniques (SIRT) with voxels, and weighted backprojection (WBP). We show that the elongation artifacts that had been previously reported can be strongly reduced. With our specific choices for the free parameters of the three algorithms, WBP reconstructions tend to be inferior to those obtained with either SIRT or ART and the results obtained with ART are comparable to those with SIRT, but at a very small fraction of the computational cost of SIRT.

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.

Renal cyst pseudoenhancement: beam-hardening effects on CT numbers.

PURPOSE: To determine if simple renal cysts may be accurately characterized with helical computed tomography (CT) during peak levels of renal enhancement. MATERIALS AND METHODS: Water-filled "cysts" were suspended in varying concentrations of iodine solution, meant to simulate varying levels of renal enhancement, within an abdominal phantom. Volume-averaging effects were minimized by scanning cylindric 5-30-mm cysts with a helical technique (collimation, 5 mm; pitch, 1:1). Axial and helical techniques were then compared, and volume-averaging effects were evaluated by scanning 10- and 20-mm round cysts with 3-, 5-, and 7-mm collimation at background attenuation levels of 100 and 200 HU. RESULTS: Cylindric cyst attenuation increased consistently with increasing background attenuation. As background attenuation increased by 90 HU, attenuation increased by 11-17 HU in small (5- or 10-mm) cysts, and by 7-9 HU in large (15-30-mm) cysts. As background attenuation increased by 180 HU, attenuation increased by 18-28 HU in small cysts and by 10-15 HU in large cysts. Spherical cyst attenuation differences were maximized when smaller cysts were imaged with larger collimation, which is when volume-averaging effects became apparent. Axial and helical CT numbers did not differ substantially. Computer simulation studies showed that the observed effect could not be explained by beam hardening alone. CONCLUSION: Pseudoenhancement of renal cysts may occur if helical CT is performed during peak renal enhancement. CT algorithm modification may be necessary to correct for this effect, which is likely related to an inadequate algorithmic correction for beam hardening.

Prediction of human observer performance by numerical observers: an experimental study.

Numerical observers are investigated for predicting the outcome of a free-response human observer study involving the detection of simulated pulmonary nodules in images reconstructed from low-dose computed tomography projection data by use of several reconstruction algorithms. A new way of calculating the figure of merit of a numerical observer is proposed wherein the detectability of signals in a particular image depends on the noise properties associated with that image and not the other images in the data set. The resulting variants of numerical observers are found to perform better than their traditional counterparts. In particular, the imagewise variant of the region-of-interest observer is found to predict best the rank ordering of algorithms by human observers for the free-response task.

3D reconstruction in electron microscopy using ART with smooth spherically symmetric volume elements (blobs).

Algebraic reconstruction techniques (ART) are iterative procedures for solving systems of linear equations. They have been used in tomography to recover objects from their projections. In this work we apply an ART approach in which the basis functions used to describe the objects are not based on voxels, but are much smoother functions named "blobs". The data collection studied in this work follows the so-called "conical tilt geometry" that is commonly used in many applications of three-dimensional electron microscopy of biological macromolecules. The performance of ART with blobs is carefully compared with a currently well-known three dimensional (3D) reconstruction algorithm (weighted back projection) using a methodology which assigns a level of statistical significance to a claim of relative superiority of one algorithm over another for a particular task. The conclusion we reach is that ART with blobs produces high-quality reconstructions and is, in particular, superior to weighted backprojection in recovering features along the "vertical" direction. For the exact implementation recommended in this paper, the computational costs of ART are almost an order of magnitude smaller than those of WBP.

Boundary tracking in 3-D binary images to produce rhombic faces for a dodecahedral model.

An algorithm is presented for tracking boundaries in three-dimensional binary images based on rhombic dodecahedral voxels. The algorithm produces a list of all the rhombic voxel faces in such a boundary.

Three-dimensional reconstruction from reduced sets of very noisy images acquired following a single-axis tilt schema: application of a new three-dimensional reconstruction algorithm and objective comparison with weighted backprojection.

In this work we propose a reconstruction algorithm (ART with blobs) that has not been previously used in electron Tomography and we compare it with the standard method in the field (weighted back projection, WBP). We assume that only a limited set of very noisy images, collected around a single axis tilt, is available; which is a typical situation in Electron Tomography. In general, the reconstruction problem is underdetermined (due to the limited number of projections) and the data are inconsistent (due to the high level of noise). The evaluation of the results is performed in a rigorous way by a task-oriented approach which makes use of numerical observers. ART with blobs outperforms WBP for a number of key tasks. Results are presented both for simplified line integral data and for realistic simulations of macromolecular structures embedded in amorphous ice.

Relevance of statistically significant differences between reconstruction algorithms.

When comparing reconstruction algorithms, differences in figures of performance merit that are too small to be of any practical relevance may still be statistically significant. We formalize the notion of "relevance" and propose an evaluation methodology in which statistical significance is retained for relevant improvements, but not for irrelevant ones.

A methodology for testing for statistically significant differences between fully 3D PET reconstruction algorithms.

We present a practical methodology for evaluating 3D PET reconstruction methods. It includes generation of random samples from a statistically described ensemble of 3D images resembling those to which PET would be applied in a medical situation, generation of corresponding projection data with noise and detector point spread function simulating those of a 3D PET scanner, assignment of figures of merit appropriate for the intended medical applications, optimization of the reconstruction algorithms on a training set of data, and statistical testing of the validity of hypotheses that say that two reconstruction algorithms perform equally well (from the point of view of a particular figure of merit) as compared to the alternative hypotheses that say that one of the algorithms outperforms the other. Although the methodology was developed with the 3D PET in mind, it can be used, with minor changes, for other 3D data collection methods, such as fully 3D cr or SPECT.

Evaluation of task-oriented performance of several fully 3D PET reconstruction algorithms.

The relative performance of five fully 3D PET reconstruction algorithms is evaluated. The algorithms are a filtered backprojection (FBP) method and two variants each of the EM-ML and ART iterative methods. For each of the iterative methods, one variant makes use of voxels and the other makes use of 'blobs' (spherically symmetric functions smoothly decaying to zero at their boundaries) as basis functions in its discrete reconstruction model. The methods are evaluated from the point of view of the efficacy of the reconstructions produced by them for three typical medical tasks--estimation of the average activity inside specific regions of interest, detection of hot spots, and detection of cold spots. A free parameter is allowed in the description of each of the five algorithms; the parameters are determined by a training process during which a value of the free parameter is selected which (nearly) maximizes a technical figure of merit. Such training and the actual comparative evaluation is done by making use of randomly generated phantoms and their projection data. The methodology allows assignation of levels of statistical significance to claims of the relative superiority of one algorithm over another for a particular task. We find that using blobs as basis functions in the iterative algorithms is definitely advantageous over using voxels. This result has high statistical significance. (We also include a visual illustration of it.) Comparing FBP, EM-ML using blobs, and ART using blobs, we do not find a clear difference in the overall performance of the investigated variants of the methods. If anything, our results suggest that ART using blobs may be the most efficacious of the three.

3D display: a survey from theory to applications.

We survey some of the literature on three-dimensional medical imaging. We report both on technical developments and on medical applications, with a concentration on material that has been published within the years 1990-1992.