| |
Discrete Tomography with an Eye towards Practice
by Joost Batenburg and Herman te Riele
Discrete Tomography, the reconstruction of binary (black-and-white) images from a small number of their projections, has received considerable attention over the past ten years. In a joint project, researchers at Leiden University and CWI perform research on new reconstruction algorithms and their mathematical background, with an eye towards possible practical applications.
The general discipline of tomography has been used over the past 40 years, particularly in medical imaging (CAT-scanners), for making noninvasive images of patients. When a large number of projections (X-rays) is available, accurate reconstructions can be made by a wide spectrum of available methods. Discrete tomography focuses on the case where only few projections are known and the images contain a small number of different colours (eg black-and-white). In this case, conventional techniques all fail. Yet, several practical applications demand accurate reconstructions under these conditions.
Figure 1 shows a binary image and projections that are measured from two directions. The problem of reconstructing a binary image from only two projections is well understood and fast reconstruction algorithms are known. However, the solution is usually not unique: a huge number of other solutions may exist. When more than two projections are available, the number of solutions becomes much smaller, but they also become more difficult to find.
 |
| Figure 1: A binary image and two of its projections. |
At the start of the project, two years ago, reconstructing binary images of 50x50 pixels from a small number of projections was a major challenge. Since then, a new algorithm has been developed by the research team consisting of Robert Tijdeman (Leiden University), Herman Te Riele (CWI), and Joost Batenburg (CWI/Leiden University). This algorithm is capable of reconstructing images 100 times as large (500x500) with great accuracy.
It repeatedly computes an approximate reconstruction, each time using only two of the projections. In general, there is a huge number of such two-projection solutions. The algorithm chooses one of these solutions based on a weight function. This weight function is constructed in such a way, that the new image satisfies the two prescribed projections completely, while still resembling the image that resulted from the previous iteration.
Assumptions on the image structure, such as a preference for smooth images, can also be incorporated in the weight function. Tests, using a large set of images from which projections were computed, have shown that when a sufficient number of projections is available, the algorithm is very likely to converge to the original image. Even very tiny details, of only one pixel in size, are reconstructed with great accuracy.
The research uses techniques from a wide range of mathematical and computer science areas, including combinatorial optimization, number theory, numerical mathematics, and evolutionary computation. In particular, the subroutine that is computationally most expensive involves solving a minimum cost flow problem in a graph. Since this problem has been studied extensively in operations research, a wide range of efficient algorithms is available.
In the late 1980s, interest in discrete tomography flourished when new research results in material sciences called for the reconstrucion of crystal lattices from several projection images, obtained by electron microscopy (see Figure 2). Since then, mathematical research on discrete tomography and research on new electron microscopy techniques has advanced both fields independently. In the tomography project at CWI/LU, efforts are made to bridge the gap between both fields, by cooperating with leading scientists in the microscopy field. If existing or new algorithms from discrete tomography can be applied successfully to the three-dimensional reconstruction of crystal lattices many open problems in material sciences, on the atomic structure of materials, can be solved.
 |
 |
| Figure 2: A crystal lattice containing two atom types (left) and one of its projections (right). |
Future research goals for the CWI/LU team include the development of a stronger theoretical foundation for the newly developed algorithms. Generalisations of the algorithm to other cases of interest, such as the reconstruction of images using more than two gray-levels, or the reconstruction of three-dimensional images are currently under consideration. From a more practical perspective: in addition to electron microscopy, several other potential application areas such as medical imaging and tomography of industrial objects are considered for future research.
Please contact:
Joost Batenburg, CWI, The Netherlands
Tel: +31 20 592 4176
E-mail: Joost.Batenburg cwi.nl
|
