A Genetic Algorithm for Three-Dimensional Discrete Tomography

Abstract

Discrete tomography is a specific case of computerized tomography that deals with the reconstruction of objects made of a few density values on a discrete lattice of points (integer valued coordinates). In the general case of computerized tomography, several hundreds of projections are required to obtain a single high-resolution slice of the object; in the case of discrete tomography, projections of an object made by just one homogeneous material are sums along very few angles of the pixel values, which can be thought to be 0’s or 1’s without loss of generality. Genetic algorithms are global optimization techniques with an underlying random approach and, therefore, their convergence to a solution is provided in a probabilistic sense. We present here a genetic algorithm able to straightforwardly reconstruct binary objects in the three-dimensional space. To the best of our knowledge, our methodology is the first to require no model of the shape (e.g., periodicity, convexity or symmetry) to reconstruct. Experiments were carried out to test our new approach in terms of computational time and correctness of the solutions. Over the years, discrete tomography has been studied for many interesting applications to computer vision, non-destructive reverse engineering and industrial quality control, electron microscopy, X-rays crystallography, biplane angiography, data coding and compression.

Keywords

• discrete tomography
• three-dimensional reconstruction
• genetic algorithm