Bounds on the quality of reconstructed images in binary tomography

Kees Joost Batenburg, Wagner Fortes, Lajos Hajdu, Robert Tijdeman

Abstract

In binary tomography, reconstructing an object from a limited number of projections often results in an underdetermined problem with multiple valid solutions. This paper presents a mathematical framework for establishing guaranteed upper bounds on the reconstruction error. By utilizing the geometric properties of a "central reconstruction"—the minimum-norm real-valued solution—the authors derive bounds on the number of misclassified pixels. These bounds provide a rigorous quality guarantee independent of the specific reconstruction algorithm used.

Introduction

Tomography aims to visualize the internal structure of an object through projections taken at various angles. Binary tomography specifically focuses on objects composed of two distinct materials, represented as 0s and 1s. This is particularly relevant in fields like electron microscopy or low-dose medical imaging, where only a few projections can be acquired.

The primary challenge in these scenarios is that the problem is highly underdetermined; many different binary images may satisfy the same projection data. Without a ground truth, assessing the accuracy of a reconstruction is difficult. This research addresses this gap by providing a mathematical "safety net"—a way to calculate the maximum possible difference between a reconstructed image and the true object.

Theoretical Framework

The core of the proposed method is the central reconstruction ($x^*$), defined as the real-valued solution to the projection equations with the minimum Euclidean norm.

The Hypersphere Property

A key insight of the paper is that all valid binary solutions to a specific tomography problem lie on the surface of a high-dimensional hypersphere centered at $x^*$. The radius ($R$) of this sphere is computable directly from the projection data.

Deriving Error Bounds

Using the triangle inequality on this hypersphere, the authors derive several classes of bounds:

  • $a(i)$ bounds: The maximum possible distance between any two valid binary solutions. If $a(i) < 1$, the binary solution is proven to be unique.
  • $b(i)$ bounds: The distance between a specific reconstruction (from any algorithm) and any other valid solution.
  • $c(i)$ bounds: The distance between the rounded version of the central reconstruction and any valid solution.

These bounds are further refined using combinatorial constraints, such as the total number of '1's in the image, which is typically known from the projections.

Experimental Setup

The framework was evaluated using four simulated "phantom" images of varying complexity: a simple convex object, a complex non-convex object, a mechanical part with internal holes, and a structure derived from a micro-CT scan of bone. These phantoms were tested across resolutions ranging from 32x32 to 512x512.

Comparison of the Grid and Strip projection models used in the study.

The study employed two distinct projection models:

  1. Grid Model: Projections are based on discrete points.
  2. Strip Model: Projections are area-based, accounting for the width of the detector pixels.

Results and Discussion

The experimental results demonstrated several key properties of the proposed bounds:

  • Consistency and Convergence: The behavior of the bounds remained consistent across different phantom shapes. As the number of projection angles increased, the bounds narrowed significantly, providing tighter guarantees.
  • Sharpness: The refined bounds ($a(3), a(4)$) proved to be "sharp," meaning they closely approximate the actual observed error.
  • Algorithm Independence: A significant advantage of this approach is that it is algorithm-agnostic. It provides a mathematical guarantee regardless of whether the reconstruction was achieved via heuristic methods or advanced AI.

Conclusion

While the current framework provides robust guarantees for perfect projection data, future work is needed to extend these bounds to handle noisy real-world data. Additionally, while calculating the central reconstruction is more efficient than finding binary solutions, the computational cost for large 3D datasets remains a consideration. Nonetheless, this work establishes a vital foundation for quantifying uncertainty in binary tomography.

Summary updated

Abstract

Binary tomography deals with the problem of reconstructing a binary image from its projections. In particular, there is a focus on highly underdetermined reconstruction problems for which many solutions may exist. In such cases, it is important to have a quality measure for the reconstruction with respect to the unknown original image.In this article, we derive a series of upper bounds that can be used to guarantee the quality of a reconstructed binary image. The bounds limit the number of pixels that can be incorrect in the reconstructed image with respect to the original image. We provide several versions of these bounds, ranging from bounds on the difference between any two binary solutions of a tomography problem to bounds on the difference between approximate solutions and the original object. The bounds are evaluated experimentally for a range of test images, based on simulated projection data.
BibTeX
@article{batenburg2013bounds,
  author = {Kees Joost Batenburg and Wagner Fortes and Lajos Hajdu and Robert Tijdeman},
  title = {{Bounds on the quality of reconstructed images in binary tomography}},
  journal = {Discret. Appl. Math},
  year = {2013},
  doi = {10.1016/j.dam.2012.11.010},
}
Figure