A Multiresolution Approach to Discrete Tomography Using DART

Andrei Dabravolski, Kees Joost Batenburg, Jan SijbersPLoS 2014 · DOI

Abstract

In discrete tomography, a scanned object is assumed to consist of only a few different materials. This prior knowledge can be effectively exploited by a specialized discrete reconstruction algorithm such as the Discrete Algebraic Reconstruction Technique (DART), which is capable of providing more accurate reconstructions from limited data compared to conventional reconstruction algorithms. However, like most iterative reconstruction algorithms, DART suffers from long computation times. To increase the computational efficiency as well as the reconstruction quality of DART, a multiresolution version of DART (MDART) is proposed, in which the reconstruction starts on a coarse grid with big pixel (voxel) size. The resulting reconstruction is then resampled on a finer grid and used as an initial point for a subsequent DART reconstruction. This process continues until the target pixel size is reached. Experiments show that MDART can provide a significant speed-up, reduce missing wedge artefacts and improve feature reconstruction in the object compared with DART within the same time, making its use with large datasets more feasible.

Introduction

Computed Tomography (CT) typically requires a large number of projection images from many angles to produce a high-quality 3D volume. However, in fields like electron microscopy or industrial scanning, acquiring many projections can be impossible due to time constraints, radiation damage, or physical obstructions—a challenge known as the "missing wedge" problem.

Discrete Tomography (DT) addresses this by assuming the object consists of only a few known materials (e.g., bone and air). While the Discrete Algebraic Reconstruction Technique (DART) is a popular tool for DT, it faces challenges with computational expense on high-resolution datasets and sensitivity to initial conditions.

The DART Algorithm

The standard DART algorithm is an iterative process that alternates between continuous algebraic reconstruction and discrete segmentation.

Flowchart of the standard DART algorithm, illustrating the iterative process of segmentation and pixel identification.

As shown in the flowchart, DART segments the reconstruction and identifies "fixed" pixels (those likely to be correct) and "non-fixed" pixels (those near boundaries or with high uncertainty). Subsequent iterations focus on updating only the non-fixed pixels, which helps preserve the discrete nature of the object.

Multiresolution DART (MDART)

To overcome the limitations of standard DART, the authors propose MDART (Multiresolution DART). This "coarse-to-fine" strategy begins the reconstruction on a coarse grid with large pixels. Once a stable reconstruction is reached, the image is upsampled using bilinear interpolation to a finer grid, serving as the starting point for the next level of refinement.

On a coarse grid, the mathematical problem is less ill-posed because there are fewer unknowns for the same amount of projection data. This allows the algorithm to establish the general structural skeleton of the object quickly and reliably, preventing high-resolution iterations from being distracted by noise and artifacts.

Experimental Evaluation

The researchers evaluated MDART using simulated phantoms (such as disks with holes and Siemens stars) and real-world micro-CT data from gypsum models and coral samples. Performance was measured using the RNMP (Relative Number of Misclassified Pixels) metric.

Performance comparison of DART vs. SSIRT on a disk phantom (A), showing the rapid convergence of the discrete approach in terms of RNMP (B).

As illustrated in the comparison above, discrete algorithms like DART already offer significant advantages over conventional methods like SSIRT in terms of both speed and final error rate. MDART further enhances this by reaching high-quality reconstructions even faster than the standard DART implementation.

Key Insights and Results

  • Significant Speedup: MDART achieves lower error rates in a fraction of the time required by standard DART. For example, MDART can often reach a target accuracy in 10 seconds that would take standard DART 50 seconds.
  • Missing Wedge Mitigation: By establishing bulk shape at low resolution, MDART is highly effective at reducing artifacts caused by limited angular ranges. In tests with a 90° missing wedge, MDART 4 achieved an RNMP of 0.013, significantly outperforming standard DART (0.042) and SIRT (0.084).
  • Noise Robustness: The multiresolution approach acts as a natural filter, maintaining structural integrity even under high levels of Poisson noise.

Limitations and Future Work

MDART remains a heuristic without a formal mathematical proof of convergence. Additionally, selecting the optimal starting resolution is crucial; starting too coarse may lose fine details, while starting too fine negates the speed benefits. Future research may explore automated strategies for pixel size transitions to further optimize performance for massive 3D datasets.

Summary updated

Abstract

In discrete tomography, a scanned object is assumed to consist of only a few different materials. This prior knowledge can be effectively exploited by a specialized discrete reconstruction algorithm such as the Discrete Algebraic Reconstruction Technique (DART), which is capable of providing more accurate reconstructions from limited data compared to conventional reconstruction algorithms. However, like most iterative reconstruction algorithms, DART suffers from long computation times. To increase the computational efficiency as well as the reconstruction quality of DART, a multiresolution version of DART (MDART) is proposed, in which the reconstruction starts on a coarse grid with big pixel (voxel) size. The resulting reconstruction is then resampled on a finer grid and used as an initial point for a subsequent DART reconstruction. This process continues until the target pixel size is reached. Experiments show that MDART can provide a significant speed-up, reduce missing wedge artefacts and improve feature reconstruction in the object compared with DART within the same time, making its use with large datasets more feasible.
BibTeX
@inproceedings{dabravolski2014multiresolution,
  author = {Andrei Dabravolski and Kees Joost Batenburg and Jan Sijbers},
  title = {{A Multiresolution Approach to Discrete Tomography Using DART}},
  booktitle = {PLoS},
  year = {2014},
  doi = {10.1371/journal.pone.0106090},
}
Figure