Dynamic angle selection in binary tomography

https://doi.org/10.1016/j.cviu.2012.07.005Get rights and content

Abstract

In this paper, we present an algorithm for the dynamic selection of projection angles in binary tomography. Based on the information present in projections that have already been measured, a new projection angle is computed, which aims to maximize the information gained by adding this projection to the set of measurements. The optimization model used for angle selection is based on a characterization of solutions of the binary reconstruction problem, and a related definition of information gain. From this formal model, an algorithm is obtained by several approximation steps. Results from a series of simulation experiments demonstrate that the proposed angle selection scheme is indeed capable of finding angles for which the reconstructed image is much more accurate than for the standard angle selection scheme.

Highlights

► We present an algorithm for dynamic angle selection in binary tomography. ► The selected projection angle maximizes the information gain. ► The algorithm uses several approximation steps, to avoid NP-hardness. ► The results show that our algorithm can choose high quality angles.

Introduction

Tomography deals with the reconstruction of an image from its projections, acquired along a range of angles. The Inverse Radon Transform provides a closed-form inversion formula for this reconstruction problem, provided that projections are available for all angles. Although this assumption is clearly not satisfied in practice, an accurate reconstruction can be computed if a large number of projections are available, for a full angular range, by using the well-known Filtered Backprojection algorithm [1], [2].

In several applications of tomography, only few projections can be acquired. Such reconstruction problems are known as limited-data problems. In electron tomography, for example, the electron beam damages the sample, limiting the number of projections that can be acquired [3]. In industrial tomography for quality assurance, cost considerations impose limitations on the duration of a scan, and thereby on the number of projections.

Applying classical reconstruction algorithms such as Filtered Backprojection to limited-data problems often results in inferior reconstruction quality. Several approaches have been proposed to overcome these problems, by incorporating various forms of prior knowledge about the object in the reconstruction algorithm. Recently, advances in the field of Compressed Sensing have demonstrated high potential in obtaining a reduction of the number of required projection images by exploiting sparsity of the image with respect to a certain set of basis functions [4], [5], [6], [7], [8]. Following a different approach, the field of discrete tomography focuses on the reconstruction of images that consist of a small, discrete set of gray values [9], [10]. By exploiting the knowledge of these gray values in the reconstruction algorithm, it is often possible to compute accurate reconstructions from far fewer projections than required by classical “continuous” tomography algorithms [11], [12].

When reconstructing an image from a small set of projections (i.e., less than 20), the particular set of projection angles can have a large influence on the quality of the reconstruction. In [13], [14], it was shown that the choice of the projection angles can have a crucial influence on the reconstruction quality in binary tomography, i.e., discrete tomography based on just two gray levels. The authors also presented algorithms to identify optimal projection angles based on a blueprint image, which is known to be similar to the scanned object. For more general grayscale tomography, a framework was recently proposed for optimizing the acquisition of projections, based on certain prior knowledge on the object to be scanned [15].

These findings naturally lead to the question if “optimal” angles can also be selected in cases where no blueprint image is available. As the optimal angles depend on the scanned object, they can certainly not be selected prior to the scanning procedure. Instead, we consider an on-line variant of the problem, where projections are measured one-by-one, and the new angle is selected based on the information present in the currently available projections.

In this paper, we present an algorithm for angle selection in binary tomography that is based on a concise model of the available projection information and prior knowledge of the binary character of the unknown object. The algorithm depends on two key ingredients: sampling of the set of images that adhere to the currently available projections, and determining the amount of information that can be gained by adding a particular angle to the set of measurements.

This paper is structured as follows. In Section 2, we introduce a formal model for the tomography problem, as well as several related concepts, which are necessary to define the angle selection problem. Although our formulation of the angle selection problem characterizes the optimal angle, it does not directly lead to an algorithm for computing this angle, which requires several approximations. Section 3 describes how the current set of binary solutions to the reconstruction problem can be approximated by a sampling procedure, leading to so-called surrogate solutions. In Section 4, we describe how the information gain can be approximated for a particular candidate angle. These two approximation steps are then combined into an algorithm for the angle selection problem, which is presented in Section 5. An example is discussed in Section 6, where the concepts involved in the angle estimation algorithm are related to actual images involved in the computations. Section 7 describes a series of simulation experiments that have been performed to investigate how the reconstructions obtained by the proposed angle selection scheme compare to several alternative angle selection strategies. In the experimental results, present in Section 8, it is shown that the proposed method is indeed capable of finding angles for which the reconstructed image is much more accurate than for the standard angle selection scheme. The approach and experimental findings are discussed in Section 9, followed by conclusions in Section 10.

Section snippets

Notation and concepts

Our description is restricted to the reconstruction of two-dimensional images from one-dimensional projections, but can be generalized to higher-dimensional settings in a straightforward manner. The reconstructed image is represented on a rectangular grid of size n = w × h.

For setting up the tomography model, we make the idealized assumption that the unknown original object is a binary image that can also be represented on this grid, even though the proposed algorithm can still be used if the grid

Surrogate solutions

To approximate the evaluation of GS¯W(Θ)(p(Θ)),Θ,θ, we resort to computing the mean information gain for a set of surrogate solutions, which are not necessarily binary. The surrogate solutions are real-valued solutions of the reconstruction problem for which all entries have values in the interval [0, 1]. These surrogate solutions are then used as samples to represent the true set S¯W(Θ)(p(Θ)) of binary solutions.

The starting point for generating a surrogate solution is a gray level template

Computing an upper bound for the diameter

Once a surrogate solution v has been computed, the information gain needs to be computed for each of the candidate angles. We recall that the information gain for a candidate angle θ is defined as the difference between the diameter of the current set of binary solutions, and the diameter of the set of binary images that have the same projections as v for all angles in Θ  {θ}. In this section, we derive an upper bound on the diameter of S¯W(Θ)(p(Θ)), which can be used effectively as a substitute

Angle selection algorithm

Combining the ingredients from Sections 3 Surrogate solutions, 4 Computing an upper bound for the diameter, we can now define an algorithm for approximating the mean information gain for a candidate angle θ, over the current set of binary solutions. Fig. 2 shows each of the algorithmic steps. Note that this description is formulated for maximum clarity and includes unnecessary recomputation steps, which can be optimized in the actual implementation.

Based on this algorithm for computing the mean

Example of an angle selection problem

To illustrate the concepts of surrogate solutions and information gain, we now consider an example. Fig. 3(a) shows a binary phantom image x¯ that has two principal orientations. Let us suppose that the projection of this image has already been measured for the horizontal and vertical directions. The central reconstruction x corresponding to these two projections is shown in Fig. 3b. The difference image (x¯-x) is shown in Fig. 3c. The Euclidean norm of this image corresponds with the central

Experiments

Simulation experiments have been performed to assess the ability of the proposed algorithm to select favorable projection angles. Starting with a general description of the methodology of the experiments in Section 7.1, two sets of experiments are described in Sections 7.2 Experiments I: selecting one new angle, 7.3 Experiments II: selecting a series of angles. The results are presented in Section 8.

Results

In this section, we report on the results of the two sets of experiments, described in Sections 7.2 Experiments I: selecting one new angle, 7.3 Experiments II: selecting a series of angles.

Discussion

The experimental results for the four phantom images suggest that the proposed dynamic angle selection strategy is indeed capable of finding angles for which the reconstructed image is substantially more accurate than for the standard angle selection scheme, if the number of angles is not too small. It seems that although the central radius provides an upper bound on the diameter of the set of binary solutions, a strategy that aims to reduce this upper bound also reduces the actual

Conclusions

In this article, we proposed a formal model for the angle selection problem in binary tomography, and an actual algorithm that was obtained by introducing several approximation steps with respect to the idealized model.

It was shown that for a set of phantom images, the proposed dynamic angle selection strategy compares favorably to other strategies that do not take specific properties of the binary reconstruction problem into account.

Although the computational requirements for the dynamic angle

Acknowledgments

This research was partially supported by the TÁMOP-4.2.2/08/1/2008-0008 Program of the Hungarian National Development Agency, the European Union and the European Regional Development Fund under the Grant Agreement TÁMOP-4.2.1/B-09/1/KONV-2010-0005. Part of the research was performed when PB was visiting the ASTRA Group at Vision Lab, University of Antwerp in Belgium. The research was also supported by the János Bolyai Research Scholarship of the Hungarian Academy of Sciences and the Grant

References (19)

There are more references available in the full text version of this article.

Cited by (28)

  • Fast algorithms based on Empirical Interpolation Methods for selecting best projections in Sparse-View X-ray Computed Tomography using a priori information

    2023, NDT and E International
    Citation Excerpt :

    Other numerical criteria have been used. In discrete tomography, Batenburg et al. [10,11] proposed an information gain metric based on algebraic reasoning. The most relevant projections to acquire are those that lower the most the diameter of the space which contains the possible solutions.

  • Advances in the metrological traceability and performance of X-ray computed tomography

    2022, CIRP Annals
    Citation Excerpt :

    Such research concerns, e.g., incomplete circular trajectories comprising only a limited set of projections [36,219,243] or even fully flexible robot XCT scans [124,154,171]. Methods are being proposed that enable task-specific identification of the set of projections for optimal scan results either before [46,97,114] or during the scan [32,70]. The XCT reconstruction step discussed in the previous section yields a 3D grey-value model, where the grey value of each voxel is ideally representing the X-ray attenuation at the voxel position.

  • Inline discrete tomography system: Application to agricultural product inspection

    2017, Computers and Electronics in Agriculture
    Citation Excerpt :

    Those irregular structures that may arise in the reconstruction images are commonly referred to as artifacts. In fact, the reconstruction of CT images from missing projection data is a hot topic in the field (Singh et al., 2008; Lu et al., 2010; Lu et al., 2011; Xu et al., 2012; Batenburg et al., 2013; Bieberle and Hampel, 2015; Kobayashi and Tanaka, 2015; Chen et al., 2015). Prior knowledge about the scanned object is often incorporated to compensate the limited projection data in CT reconstructions.

  • Dynamic angle selection in X-ray computed tomography

    2014, Nuclear Instruments and Methods in Physics Research, Section B: Beam Interactions with Materials and Atoms
    Citation Excerpt :

    For tomography of elliptical objects, a genetic algorithm was proposed [6], which exploits the preferential direction characteristic of the objects and uses reconstructions from available projections to select the next projection directions. In [7], a new strategy was recently proposed for angle selection in binary tomography, which is based on the concept of information gain from adding a particular projection angle to the set of projection directions and does not require specifying prior knowledge about the object. In the present paper, the dynamic angle selection strategy for binary object scanning is adapted for use in grey scale tomography.

  • Local and global uncertainty in binary tomographic reconstruction

    2014, Computer Vision and Image Understanding
    Citation Excerpt :

    An alternative to calculate non-discrete reconstructions is a random sampling of the set of possible reconstructions belonging to the same set of projections, and then averaging the intensity in all those samples, pixelwisely. A similar approach for the random sampling of the space of reconstructions were previously applied in [4], where the authors generated random blobs for initializing continuous SIRT reconstructions. Due to the stochastic nature of this process, with each run of Algorithm 2 we get a random element of the possible reconstructions.

View all citing articles on Scopus
View full text