Convergent incremental optimization transfer algorithms: application to tomography

Faster PET reconstruction with non-smooth priors by randomization and preconditioning

Uncompressed clinical data from modern positron emission tomography (PET) scanners are very large, exceeding 350 million data points (projection bins). The last decades have seen tremendous advancements in mathematical imaging tools many of which lead to non-smooth (i.e. non-differentiable) optimization problems which are much harder to solve than smooth optimization problems. Most of these tools have not been translated to clinical PET data, as the state-of-the-art algorithms for non-smooth problems do not scale well to large data. In this work, inspired by big data machine learning applications, we use advanced randomized optimization algorithms to solve the PET reconstruction problem for a very large class of non-smooth priors which includes for example total variation, total generalized variation, directional total variation and various different physical constraints. The proposed algorithm randomly uses subsets of the data and only updates the variables associated with these. While this idea often leads to divergent algorithms, we show that the proposed algorithm does indeed converge for any proper subset selection. Numerically, we show on real PET data (FDG and florbetapir) from a Siemens Biograph mMR that about ten projections and backprojections are sufficient to solve the MAP optimisation problem related to many popular non-smooth priors; thus showing that the proposed algorithm is fast enough to bring these models into routine clinical practice.

Comparison Between Pre-Log and Post-Log Statistical Models in Ultra-Low-Dose CT Reconstruction

X-ray detectors in clinical computed tomography (CT) usually operate in current-integrating mode. Their complicated signal statistics often lead to intractable likelihood functions for practical use in model-based image reconstruction (MBIR). It is therefore desirable to design simplified statistical models without losing the essential factors. Depending on whether the CT transmission data are logarithmically transformed, pre-log and post-log models are two major categories of choices in CT MBIR. Both being approximations, it remains an open question whether one model can notably improve image quality over the other on real scanners. In this study, we develop and compare several pre-log and post-log MBIR algorithms under a unified framework. Their reconstruction accuracy based on simulation and clinical datasets are evaluated. The results show that pre-log MBIR can achieve notably better quantitative accuracy than post-log MBIR in ultra-low-dose CT, although in less extreme cases, post-log MBIR with handcrafted pre-processing remains a competitive alternative. Pre-log MBIR could play a growing role in emerging ultra-low-dose CT applications.

Accelerating an Ordered-Subset Low-Dose X-Ray Cone Beam Computed Tomography Image Reconstruction with a Power Factor and Total Variation Minimization

In recent years, there has been increased interest in low-dose X-ray cone beam computed tomography (CBCT) in many fields, including dentistry, guided radiotherapy and small animal imaging. Despite reducing the radiation dose, low-dose CBCT has not gained widespread acceptance in routine clinical practice. In addition to performing more evaluation studies, developing a fast and high-quality reconstruction algorithm is required. In this work, we propose an iterative reconstruction method that accelerates ordered-subsets (OS) reconstruction using a power factor. Furthermore, we combine it with the total-variation (TV) minimization method. Both simulation and phantom studies were conducted to evaluate the performance of the proposed method. Results show that the proposed method can accelerate conventional OS methods, greatly increase the convergence speed in early iterations. Moreover, applying the TV minimization to the power acceleration scheme can further improve the image quality while preserving the fast convergence rate.

Relaxed Linearized Algorithms for Faster X-Ray CT Image Reconstruction

Statistical image reconstruction (SIR) methods are studied extensively for X-ray computed tomography (CT) due to the potential of acquiring CT scans with reduced X-ray dose while maintaining image quality. However, the longer reconstruction time of SIR methods hinders their use in X-ray CT in practice. To accelerate statistical methods, many optimization techniques have been investigated. Over-relaxation is a common technique to speed up convergence of iterative algorithms. For instance, using a relaxation parameter that is close to two in alternating direction method of multipliers (ADMM) has been shown to speed up convergence significantly. This paper proposes a relaxed linearized augmented Lagrangian (AL) method that shows theoretical faster convergence rate with over-relaxation and applies the proposed relaxed linearized AL method to X-ray CT image reconstruction problems. Experimental results with both simulated and real CT scan data show that the proposed relaxed algorithm (with ordered-subsets [OS] acceleration) is about twice as fast as the existing unrelaxed fast algorithms, with negligible computation and memory overhead.

Noise properties of CT images reconstructed by use of constrained total-variation, data-discrepancy minimization

PURPOSE

The authors develop and investigate iterative image reconstruction algorithms based on data-discrepancy minimization with a total-variation (TV) constraint. The various algorithms are derived with different data-discrepancy measures reflecting the maximum likelihood (ML) principle. Simulations demonstrate the iterative algorithms and the resulting image statistical properties for low-dose CT data acquired with sparse projection view angle sampling. Of particular interest is to quantify improvement of image statistical properties by use of the ML data fidelity term.

METHODS

An incremental algorithm framework is developed for this purpose. The instances of the incremental algorithms are derived for solving optimization problems including a data fidelity objective function combined with a constraint on the image TV. For the data fidelity term the authors, compare application of the maximum likelihood principle, in the form of weighted least-squares (WLSQ) and Poisson-likelihood (PL), with the use of unweighted least-squares (LSQ).

RESULTS

The incremental algorithms are applied to projection data generated by a simulation modeling the breast computed tomography (bCT) imaging application. The only source of data inconsistency in the bCT projections is due to noise, and a Poisson distribution is assumed for the transmitted x-ray photon intensity. In the simulations involving the incremental algorithms an ensemble of images, reconstructed from 1000 noise realizations of the x-ray transmission data, is used to estimate the image statistical properties. The WLSQ and PL incremental algorithms are seen to reduce image variance as compared to that of LSQ without sacrificing image bias. The difference is also seen at few iterations--short of numerical convergence of the corresponding optimization problems.

CONCLUSIONS

The proposed incremental algorithms prove effective and efficient for iterative image reconstruction in low-dose CT applications particularly with sparse-view projection data.

GPU-accelerated regularized iterative reconstruction for few-view cone beam CT

PURPOSE

The present work proposes an iterative reconstruction technique designed for x-ray transmission computed tomography (CT). The main objective is to provide a model-based solution to the cone-beam CT reconstruction problem, yielding accurate low-dose images via few-views acquisitions in clinically acceptable time frames.

METHODS

The proposed technique combines a modified ordered subsets convex (OSC) algorithm and the total variation minimization (TV) regularization technique and is called OSC-TV. The number of subsets of each OSC iteration follows a reduction pattern in order to ensure the best performance of the regularization method. Considering the high computational cost of the algorithm, it is implemented on a graphics processing unit, using parallelization to accelerate computations.

RESULTS

The reconstructions were performed on computer-simulated as well as human pelvic cone-beam CT projection data and image quality was assessed. In terms of convergence and image quality, OSC-TV performs well in reconstruction of low-dose cone-beam CT data obtained via a few-view acquisition protocol. It compares favorably to the few-view TV-regularized projections onto convex sets (POCS-TV) algorithm. It also appears to be a viable alternative to full-dataset filtered backprojection. Execution times are of 1-2 min and are compatible with the typical clinical workflow for nonreal-time applications.

CONCLUSIONS

Considering the image quality and execution times, this method may be useful for reconstruction of low-dose clinical acquisitions. It may be of particular benefit to patients who undergo multiple acquisitions by reducing the overall imaging radiation dose and associated risks.

Fast X-ray CT image reconstruction using a linearized augmented Lagrangian method with ordered subsets

Augmented Lagrangian (AL) methods for solving convex optimization problems with linear constraints are attractive for imaging applications with composite cost functions due to the empirical fast convergence rate under weak conditions. However, for problems such as X-ray computed tomography (CT) image reconstruction, where the inner least-squares problem is challenging and requires iterations, AL methods can be slow. This paper focuses on solving regularized (weighted) least-squares problems using a linearized variant of AL methods that replaces the quadratic AL penalty term in the scaled augmented Lagrangian with its separable quadratic surrogate function, leading to a simpler ordered-subsets (OS) accelerable splitting-based algorithm, OS-LALM. To further accelerate the proposed algorithm, we use a second-order recursive system analysis to design a deterministic downward continuation approach that avoids tedious parameter tuning and provides fast convergence. Experimental results show that the proposed algorithm significantly accelerates the convergence of X-ray CT image reconstruction with negligible overhead and can reduce OS artifacts when using many subsets.

Combining ordered subsets and momentum for accelerated X-ray CT image reconstruction

Statistical X-ray computed tomography (CT) reconstruction can improve image quality from reduced dose scans, but requires very long computation time. Ordered subsets (OS) methods have been widely used for research in X-ray CT statistical image reconstruction (and are used in clinical PET and SPECT reconstruction). In particular, OS methods based on separable quadratic surrogates (OS-SQS) are massively parallelizable and are well suited to modern computing architectures, but the number of iterations required for convergence should be reduced for better practical use. This paper introduces OS-SQS-momentum algorithms that combine Nesterov's momentum techniques with OS-SQS methods, greatly improving convergence speed in early iterations. If the number of subsets is too large, the OS-SQS-momentum methods can be unstable, so we propose diminishing step sizes that stabilize the method while preserving the very fast convergence behavior. Experiments with simulated and real 3D CT scan data illustrate the performance of the proposed algorithms.

Acceleration of MAP-EM algorithm via over-relaxation

To improve the convergence rate of the effective maximum a posteriori expectation-maximization (MAP-EM) algorithm in tomographic reconstructions, this study proposes a modified MAP-EM which uses an over-relaxation factor to accelerate image reconstruction. The proposed method, called MAP-AEM, is evaluated and compared with the results for MAP-EM and for an ordered-subset algorithm, in terms of the convergence rate and noise properties. The results show that the proposed method converges numerically much faster than MAP-EM and with a speed that is comparable to that for an ordered-subset type method. The proposed method is effective in accelerating MAP-EM tomographic reconstruction.

Accelerating ordered subsets image reconstruction for X-ray CT using spatially nonuniform optimization transfer

Statistical image reconstruction algorithms in X-ray computed tomography (CT) provide improved image quality for reduced dose levels but require substantial computation time. Iterative algorithms that converge in few iterations and that are amenable to massive parallelization are favorable in multiprocessor implementations. The separable quadratic surrogate (SQS) algorithm is desirable as it is simple and updates all voxels simultaneously. However, the standard SQS algorithm requires many iterations to converge. This paper proposes an extension of the SQS algorithm that leads to spatially nonuniform updates. The nonuniform (NU) SQS encourages larger step sizes for the voxels that are expected to change more between the current and the final image, accelerating convergence, while the derivation of NU-SQS guarantees monotonic descent. Ordered subsets (OS) algorithms can also accelerate SQS, provided suitable "subset balance" conditions hold. These conditions can fail in 3-D helical cone-beam CT due to incomplete sampling outside the axial region-of-interest (ROI). This paper proposes a modified OS algorithm that is more stable outside the ROI in helical CT. We use CT scans to demonstrate that the proposed NU-OS-SQS algorithm handles the helical geometry better than the conventional OS methods and "converges" in less than half the time of ordinary OS-SQS.

Parameter optimization of relaxed Ordered Subsets Pre-computed Back Projection (BP) based Penalized-Likelihood (OS-PPL) reconstruction in limited-angle X-ray tomography

This paper presents a two-step strategy to provide a quality-predictable image reconstruction. A Pre-computed Back Projection based Penalized-Likelihood (PPL) method is proposed in the strategy to generate consistent image quality. To solve PPL efficiently, relaxed Ordered Subsets (OS) is applied. A training sets based evaluation is performed to quantify the effect of the undetermined parameters in OS, which lets the results as consistent as possible with the theoretical one.

Regularized image reconstruction algorithms for dual-isotope myocardial perfusion SPECT (MPS) imaging using a cross-tracer prior

In simultaneous dual-isotope myocardial perfusion SPECT (MPS) imaging, data are simultaneously acquired to determine the distributions of two radioactive isotopes. The goal of this work was to develop penalized maximum likelihood (PML) algorithms for a novel cross-tracer prior that exploits the fact that the two images reconstructed from simultaneous dual-isotope MPS projection data are perfectly registered in space. We first formulated the simultaneous dual-isotope MPS reconstruction problem as a joint estimation problem. A cross-tracer prior that couples voxel values on both images was then proposed. We developed an iterative algorithm to reconstruct the MPS images that converges to the maximum a posteriori solution for this prior based on separable surrogate functions. To accelerate the convergence, we developed a fast algorithm for the cross-tracer prior based on the complete data OS-EM (COSEM) framework. The proposed algorithm was compared qualitatively and quantitatively to a single-tracer version of the prior that did not include the cross-tracer term. Quantitative evaluations included comparisons of mean and standard deviation images as well as assessment of image fidelity using the mean square error. We also evaluated the cross tracer prior using a three-class observer study with respect to the three-class MPS diagnostic task, i.e., classifying patients as having either no defect, reversible defect, or fixed defects. For this study, a comparison with conventional ordered subsets-expectation maximization (OS-EM) reconstruction with postfiltering was performed. The comparisons to the single-tracer prior demonstrated similar resolution for areas of the image with large intensity changes and reduced noise in uniform regions. The cross-tracer prior was also superior to the single-tracer version in terms of restoring image fidelity. Results of the three-class observer study showed that the proposed cross-tracer prior and the convergent algorithms improved the image quality of dual-isotope MPS images compared to OS-EM.

PET transmission tomography using a novel nonlocal MRF prior

In positron emission tomography, transmission scans can be performed to estimate attenuation correction factors (ACFs) which are in turn used to correct the emission scans. And such an attenuation correction is crucial for quantitatively accurate PET reconstructions. The prior model used in this work was based on our assumption that the attenuation values vary smoothly, with occasional discontinuities at anatomical borders. And on the other hand, long acquisition or scan times, although alleviating the noise effect of the count-limited scans, are blamed for patient uncomfortableness and movements. So, transmission tomography often suffers from the noise effect because of the short scan time. Thus reconstruction which is capable of overcoming the noise effect is highly needed. In this article, we apply the nonlocal prior Bayesian reconstruction method in PET transmission tomography. Resulting experimentations validate that the reconstructions using the nonlocal prior can reconstruct better transmission images and overcome noise effect even when the scan time is relatively short.

Event-by-event image reconstruction from list-mode PET data

This paper adapts the classical list-mode OSEM and the globally convergent list-mode COSEM methods to the special case of singleton subsets. The image estimate is incrementally updated for each coincidence event measured by the PET scanner. Events are used as soon as possible to improve the current image estimate, and, therefore, the convergence speed toward the maximum-likelihood solution is accelerated. An alternative online formulation of the list-mode COSEM algorithm is proposed first. This method saves memory resources by re-computing previous incremental image contributions while processing a new pass over the complete dataset. This online expectation-maximization principle is applied to the list-mode OSEM method, as well. Image reconstructions have been performed from a simulated dataset for the NCAT torso phantom and from a clinical dataset. Results of the classical and event-by-event list-mode algorithms are discussed in a systematic and quantitative way.

Block-iterative Fisher scoring algorithms for maximum penalized likelihood image reconstruction in emission tomography

This paper introduces and evaluates a block-iterative Fisher scoring (BFS) algorithm. The algorithm provides regularized estimation in tomographic models of projection data with Poisson variability. Regularization is achieved by penalized likelihood with a general quadratic penalty. Local convergence of the block-iterative algorithm is proven under conditions that do not require iteration dependent relaxation. We show that, when the algorithm converges, it converges to the unconstrained maximum penalized likelihood (MPL) solution. Simulation studies demonstrate that, with suitable choice of relaxation parameter and restriction of the algorithm to respect nonnegative constraints, the BFS algorithm provides convergence to the constrained MPL solution. Constrained BFS often attains a maximum penalized likelihood faster than other block-iterative algorithms which are designed for nonnegatively constrained penalized reconstruction.

Fast iterative image reconstruction methods for fully 3D multispectral bioluminescence tomography

We investigate fast iterative image reconstruction methods for fully 3D multispectral bioluminescence tomography for applications in small animal imaging. Our forward model uses a diffusion approximation for optically inhomogeneous tissue, which we solve using a finite element method (FEM). We examine two approaches to incorporating the forward model into the solution of the inverse problem. In a conventional direct calculation approach one computes the full forward model by repeated solution of the FEM problem, once for each potential source location. We describe an alternative on-the-fly approach where one does not explicitly solve for the full forward model. Instead, the solution to the forward problem is included implicitly in the formulation of the inverse problem, and the FEM problem is solved at each iteration for the current image estimate. We evaluate the convergence speeds of several representative iterative algorithms. We compare the computation cost of those two approaches, concluding that the on-the-fly approach can lead to substantial reductions in total cost when combined with a rapidly converging iterative algorithm.

Statistical reconstruction for cosmic ray muon tomography

Highly penetrating cosmic ray muons constantly shower the earth at a rate of about 1 muon per cm2 per minute. We have developed a technique which exploits the multiple Coulomb scattering of these particles to perform nondestructive inspection without the use of artificial radiation. In prior work [1]-[3], we have described heuristic methods for processing muon data to create reconstructed images. In this paper, we present a maximum likelihood/expectation maximization tomographic reconstruction algorithm designed for the technique. This algorithm borrows much from techniques used in medical imaging, particularly emission tomography, but the statistics of muon scattering dictates differences. We describe the statistical model for multiple scattering, derive the reconstruction algorithm, and present simulated examples. We also propose methods to improve the robustness of the algorithm to experimental errors and events departing from the statistical model.

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