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

Hung Nien, Jeffrey A. Fessler

TL;DR

This paper introduces OS-LALM, a novel algorithm for accelerating X-ray CT image reconstruction. By combining a linearized augmented Lagrangian method with ordered subsets and a deterministic downward continuation strategy, it achieves significantly faster convergence and reduced artifacts compared to existing methods, especially when using many subsets.

What Problem Does This Paper Address?

Reconstructing high-quality X-ray CT images quickly is crucial for reducing patient radiation dose and improving diagnostic accuracy. While statistical methods offer better image quality than traditional filtered back-projection (FBP), they are computationally intensive. Existing methods like the Augmented Lagrangian (AL) method, while powerful for optimization, can be slow for CT reconstruction due to the difficulty of solving the inner least-squares problem. Ordered Subsets (OS) algorithms accelerate convergence by processing data in subsets, but can introduce artifacts, especially with many subsets. This paper aims to bridge this gap by developing a faster, more stable OS-accelerated CT reconstruction algorithm.

Methods

The core of the proposed method, OS-LALM, is a linearized variant of the Augmented Lagrangian (AL) method. Instead of directly solving the complex inner least-squares problem in the standard AL method, OS-LALM uses a separable quadratic surrogate (SQS) function to approximate the penalty term. This simplification allows for efficient integration with Ordered Subsets (OS) acceleration.

To further boost performance and avoid tedious parameter tuning, the authors introduce a "deterministic downward continuation" approach. This strategy, inspired by second-order recursive system analysis, adaptively adjusts a key parameter (the AL penalty parameter) during the reconstruction process. It starts with a more aggressive parameter and gradually reduces it, aiming to balance fast convergence with stability and minimize artifacts.

Datasets

The paper evaluates its proposed algorithm on two real-world 3D X-ray CT datasets:

  • A shoulder region helical CT scan.
  • A GE performance phantom axial CT scan.

These datasets are used to compare the performance of OS-LALM against several state-of-the-art OS-based reconstruction algorithms.

Key Insights and Ideas

  • Linearized AL for CT is a game-changer: By simplifying the inner problem of the AL method, the authors unlock its potential for efficient CT reconstruction, overcoming a major bottleneck.
  • OS acceleration is compatible with linearized AL: The simplified structure of the linearized AL method makes it amenable to ordered subsets, leading to significant speedups.
  • Deterministic downward continuation avoids parameter tuning: This novel approach offers a robust way to achieve fast convergence and artifact reduction without requiring manual adjustment of algorithm parameters, which is a common challenge in optimization-based reconstruction.
  • Improved artifact suppression: The proposed method demonstrates a notable reduction in OS artifacts, particularly when using a large number of subsets, a common issue with other OS algorithms.

Key Results

  • Significant acceleration: The proposed OS-LALM algorithm achieved approximately 5-10x acceleration compared to the standard OS algorithm with p=1 (which represents a baseline). Further acceleration (up to 20x) was observed with smaller p values (0.2, 0.1, 0.05), though this came with a trade-off in early iteration convergence.
  • Reduced OS artifacts: Experimental results showed that OS-LALM produced significantly fewer and less visible artifacts compared to standard OS and relaxed OS+momentum algorithms, especially when using a large number of subsets (e.g., 40 subsets for the shoulder scan).
  • Effective with few inner iterations: The algorithm demonstrated good convergence even with just one FISTA iteration for the inner constrained denoising problem, highlighting its efficiency.
  • Robustness to parameter choices: The deterministic downward continuation approach proved effective without requiring extensive parameter tuning.

Limitations and Future Work

  • Convergence analysis for M > 1: While the paper provides convergence analysis for the one-subset version, a more rigorous analysis for the multi-subset OS version (M > 1) is suggested as future work.
  • High-memory version: For more challenging denoising problems, a "high-memory" version involving an additional split variable for the regularizer might be necessary, which would increase memory requirements.
  • Analysis for non-quadratic cost functions: The current analysis and algorithm are primarily focused on weighted least-squares problems (quadratic cost functions). Extending the analysis to more general non-smooth cost functions and their behavior with the deterministic downward continuation approach is a potential area for future research.
  • Further investigation of downward continuation: While the deterministic downward continuation approach is shown to be effective, further theoretical investigation into its convergence properties and optimal strategies is suggested.

Summary updated

Abstract

The augmented Lagrangian (AL) method that solves convex optimization problems with linear constraints has drawn more attention recently in imaging applications due to its decomposable structure for composite cost functions and empirical fast convergence rate under weak conditions. However, for problems such as X-ray computed tomography (CT) image reconstruction and large-scale sparse regression with "big data", where there is no efficient way to solve the inner least-squares problem, the AL method can be slow due to the inevitable iterative inner updates. In this paper, we focus on solving regularized (weighted) least-squares problems using a linearized variant of the AL method that replaces the quadratic AL penalty term in the scaled augmented Lagrangian with its separable quadratic surrogate (SQS) function, thus leading to a much simpler ordered-subsets (OS) accelerable splitting-based algorithm, OS-LALM, for X-ray CT image reconstruction. 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 greatly reduces the OS artifacts in the reconstructed image when using many subsets for OS acceleration.
BibTeX
@article{nien2015fast,
  author = {Hung Nien and Jeffrey A. Fessler},
  title = {{Fast X-ray CT image reconstruction using the linearized augmented Lagrangian method with ordered subsets}},
  journal = {IEEE Trans. Medical Imaging},
  year = {2015},
  url = {https://openreview.net/forum?id=-oJHJ24TS8a},
}
Figure