by Bram Vermeer
CT scans are set to become far more efficient. That is the outcome of a study conducted at CWI by Joost Batenburg, who obtained his PhD in 2006 with a thesis on algorithms for computer tomography. The results of Batenburg's research offer new prospects for medical diagnosis, but are also of interest to diamond cutters. It also allowed him to capture images of individual atoms in small crystals from electron microscopy data.
A CT scan consists of hundreds of X-ray images, each of which is made at a slightly different angle. Individually, these are little more than two-dimensional images, but together they provide enough data to reconstruct a three-dimensional image. Over the years, various algorithms have been developed for the computation of such three-dimensional images. The more X-ray images used to reconstruct the three-dimensional image, the more detailed it will be. The opposite also applies. If too few images are available, only a vague image is produced.
Existing reconstruction algorithms for tomography produce unsatisfactory results if fewer than ten X-ray images are available. However, this problem can be solved if the reconstruction process incorporates additional knowledge. In industry, for example, many products are scanned to check whether they contain hidden cracks or cavities. In such instances, not all greyscale values have to be computed to produce a 3-D image. Black and white are sufficient. The material is either present or absent. This type of reconstruction, using only a limited range of greys, is known as 'discrete tomography'.
Sharper Reconstruction with fewer Images
Algorithms for discrete tomography produce much sharper 3-D reconstruction using fewer X-ray images, because a priori information is incorporated into the computation. However, this does not necessarily imply that such images can be computed more quickly. Reconstructions of images based on a continuum of greyscale values are easier to compute than when only a limited number of such values are available. When Joost Batenburg started his research, reconstruction algorithms in discrete tomography were limited to images no bigger than 50 by 50 pixels. That is rather small, in this age of megapixels. In practice, it was impossible to make use of a priori information to produce sharper images. It is therefore customary to simply produce extra images during CT scans to ensure sharper images, even though this results in higher radiation levels and higher costs.
In collaboration with Robert Tijdeman (Universiteit Leiden, the Netherlands) and Herman te Riele (CWI), Joost Batenburg devised a new computation procedure. The trick is to ensure that the X-ray images are not all evaluated simultaneously. Instead, the computer evaluates the images in pairs. Based on just two X-ray images, it produces a rough three-dimensional reconstruction. This rough image is subsequently used as prior information for the evaluation of the next pair of images. In this way, the computer repeatedly reconstructs a three-dimensional image using two X-ray images. As computation progresses, the reconstruction becomes more precise. Even very tiny, single-pixel details are eventually reconstructed with great accuracy.
Because only two images are used in each instance, the required computation is much less complex. In fact, the computation has much in common with the so-called minimum-cost flow problem, a notorious computational challenge in the field of operations research. The problem in question is all about calculating the most efficient way of pumping a fluid through a flow network. This problem has been studied extensively, resulting in a wide range of efficient algorithms.
Megapixel Scan
Batenburg's computer program required the integration of knowledge from three diverse fields - mathematics, computer science and physics. Fortunately, Batenburg graduated cum laude in two of these fields. Insight into coding theory was required to adjust for noisy data; insight into number theory and numerical mathematics was required for the systems of linear equations with natural numbers; and he also applied knowledge from the fields of evolutionary algorithms and operations research.
The program Batenburg developed produces images of about one megapixel. That is large enough to ensure the feasibility of this approach, which was subsequently used to study osteoporosis in mice, in collaboration with the University of Antwerp. In bone scans of this kind, only a limited range of greyscale values are required, because osteoporosis causes cavities in the bones: in other words, bone material is either present or absent.
Another application is computing images of individual atoms in nanocrystals: miniscule crystals consisting of several hundred atoms, which are used in LEDs and catalysts. Here, electron microscopy images are used instead of X-rays. With these images the production methods can be improved. The enhanced CT scans can also be used in the diamond industry, since having the ability to detect flaws in a stone enables the cutter to reduce wastage. With discrete tomography fewer x-ray images are needed, leading to increased efficiency and decreased cost.
These are but a few of the many possibilities. Batenburgs research team now aims to develop a stronger theoretical foundation for the newly developed algorithms. They are currently considering generalizations of the algorithm to other areas of interest, such as the reconstruction of images using more than two greyscale values, or the reconstruction of three-dimensional images. Other potential areas of application include medical imaging and tomography of industrial objects, such as nanosize electronics and critical parts for aircraft.
Joost Batenburg's research was awarded the Philips Mathematics Prize for PhD students in March 2006, and the C. J. Kok Prize of the Universiteit Leiden in January 2007.
Link:
http://visielab.ua.ac.be/staff/batenburg/
Please contact:
Joost Batenburg
Vision Lab, University of Antwerp, Belgium
Tel: +32 3 820 24 49
E-mail: joost.batenburg
ua.ac.be
