An Entropic Perturbation Approach to TV-Minimization for Limited-Data Tomography

Andreea Denitiu, Stefania Petra, Claudius Schnörr, Christoph Schnörr

Abstract

Discrete tomography aims to reconstruct 3D objects from a limited number of X-ray projections. While Total Variation (TV) minimization is a powerful framework for this undersampled recovery, its application to high-resolution 3D volumes is often hindered by the computational limits of standard solvers. This paper introduces a scalable optimization strategy that applies an entropic perturbation to the TV-minimization objective. By transforming the constrained problem into a smooth, unconstrained dual problem, the authors enable the use of the memory-efficient L-BFGS algorithm, significantly outperforming commercial solvers in both scalability and noise robustness.

Introduction

In industrial and biological imaging, researchers often face the challenge of reconstructing a 3D object from a highly restricted set of projections. This "undersampled" data environment makes the reconstruction problem ill-posed, as infinitely many images could theoretically fit the observed data. To identify the most plausible reconstruction, Total Variation (TV) minimization is employed. This technique assumes the target object is "blocky" or cosparse—composed of a few homogeneous materials with sharp boundaries.

However, as imaging moves from 2D slices to high-resolution 3D volumes, the resulting optimization problems become massive. Standard interior-point solvers, such as MOSEK, frequently encounter memory bottlenecks or "stall" during convergence when faced with millions of variables. Furthermore, these solvers can be brittle when the input data is corrupted by noise, a common occurrence in real-world laboratory settings.

Methodology: Entropic Perturbation

The authors propose a "Perturbed Linear Programming" approach to overcome these computational hurdles. The method follows a four-step transformation process:

  1. Linear Programming Reformulation: The original TV-minimization problem is first cast as a standard Linear Program (LP).
  2. Entropic Perturbation: Rather than solving the rigid LP, the authors introduce a small nonlinear term—an entropy function $\epsilon \langle x, \log x - \mathbf{1} \rangle$—into the objective function.
  3. Fenchel Duality: By applying Fenchel Duality to this perturbed objective, the authors derive a dual problem that is both unconstrained and twice differentiable.
  4. L-BFGS Optimization: The resulting smooth, unconstrained landscape allows for the use of the Limited-Memory BFGS (L-BFGS) algorithm. L-BFGS is specifically designed for high-dimensional optimization, maintaining a very small memory footprint even with millions of variables.

This approach effectively "softens" the hard constraints of the original TV problem, creating a numerical landscape that is much easier for solvers to navigate quickly.

Experimental Setup

The effectiveness of the entropic approach was evaluated using several synthetic benchmarks designed to simulate difficult tomographic conditions:

  • 2D Ellipsoids: Randomly generated images used to validate "phase transition" curves, which predict the minimum number of measurements required for perfect recovery.
  • 3D Shepp-Logan Phantom: A standard medical imaging benchmark scaled to a $51 \times 51 \times 51$ volume to test 3D reconstruction capabilities.
  • Noise Robustness: To simulate real-world conditions, projections were corrupted with Poisson noise at a Signal-to-Noise Ratio (SNR) of 50dB.

Key Insights and Results

Scalability and Efficiency

The proposed algorithm demonstrated superior scalability compared to commercial alternatives. In 3D reconstruction tasks where MOSEK reached its memory capacity or failed to converge, the entropic approach successfully produced high-quality results. Timing benchmarks indicated that while MOSEK’s computation time grew exponentially with image dimension, the entropic approach scaled gracefully, maintaining efficiency at higher resolutions.

Phase Transitions and Recovery

The authors validated theoretical phase transition curves, confirming the relationship between the number of measurements ($m$) and the object's complexity (cosparsity $\ell$). Notably, the choice of an entropic perturbation proved superior to standard quadratic (Tikhonov) regularization for these integer-valued reconstruction problems.

Robustness to Noise

In noisy scenarios, standard solvers often reported the problem as "infeasible" due to the strictness of the constraints. The entropic approach remained stable, producing reconstructions with an error margin ($||u - u^*||_\infty < 0.5$) low enough to allow for perfect recovery after simple rounding.

Conclusion and Future Work

By slightly modifying the TV-minimization objective with an entropic term, the authors have unlocked the ability to use fast, unconstrained optimization tools for 3D tomography. While the choice of the perturbation parameter $\epsilon$ currently remains fixed, future research may explore adaptive methods for selecting this value to further optimize performance. Additionally, the algorithm's structure is highly suitable for parallelization, suggesting even greater potential for processing massive industrial datasets in real-time.

Summary updated

Abstract

The reconstruction problem of discrete tomography is studied using novel techniques from compressive sensing. Recent theoretical results of the authors enable to predict the number of measurements required for the unique reconstruction of a class of co-sparse dense 2D and 3D signals in severely undersampled scenarios by convex programming. These results extend established `1-related theory based on sparsity of the signal itself to novel scenarios not covered so far, including tomographic projections of 3D solid bodies composed of few different materials. As a consequence, the large-scale optimization task based on total-variation minimization subject to tomographic projection constraints is considerably more complex than basic `1-programming for sparse regularization. We propose an entropic perturbation of the objective that enables to apply efficient methodologies from unconstrained optimization to the perturbed dual program. Numerical results validate the theory for large-scale recovery problems of integer-values functions that exceed the capacity of the commercial MOSEK software. Keywords: discrete tomography, compressed sensing, underdetermined systems of linear equations, cosparsity, phase transitions, total variation, entropic per-turbation, convex duality, convex programming.
BibTeX
@inproceedings{denitiu2014entropic,
  author = {Andreea Denitiu and Stefania Petra and Claudius Schnörr and Christoph Schnörr},
  title = {{An Entropic Perturbation Approach to TV-Minimization for Limited-Data Tomography}},
  booktitle = {DGCI},
  year = {2014},
  doi = {10.1007/978-3-319-09955-2\_22},
}
Figure