Discrete tomography focuses on the problem of reconstruction of binary images from a small number of their projections. In general, tomography deals with the problem of determining shape and dimensional information of an object from a set of projections. From the mathematical point of view, the object corresponds to a function and the problem posed is to reconstruct this function from its integrals or sums over subsets of its domain. In general, the tomographic inversion problem may be continuous or discrete. In continuous tomography both the domain and the range of the function are continuous and line integrals are used. In discrete tomography the domain of the function may be either discrete or continuous, and the range of the function is a finite set of real, usually nonnegative numbers. In continuous tomography when a large number of projections is available, accurate reconstructions can be made by many different algorithms. It is typical for discrete tomography that only a few projections are used. In this case, conventional techniques all fail. A special case of discrete tomography deals with the problem of the reconstruction of a binary image from a small number of projections. The name discrete tomography is due to Larry Shepp, who organized the first meeting devoted to this topic.
Theory
Discrete tomography has strong connections with other mathematical fields, such as number theory, discrete mathematics, complexity theory and combinatorics. In fact, a number of discrete tomography problems were first discussed as combinatorial problems. In 1957, H. J. Ryser found a necessary and sufficient condition for a pair of vectors being the two orthogonal projections of a discrete set. In the proof of his theorem, Ryser also described a reconstruction algorithm, the very first reconstruction algorithm for a general discrete set from two orthogonal projections. In the same year, David Gale found the same consistency conditions, but in connection with the network flow problem. Another result of Ryser's is the definition of the switching operation by which discrete sets having the same projections can be transformed into each other. The problem of reconstructing a binary image from a small number of projections generally leads to a large number of solutions. It is desirable to limit the class of possible solutions to only those that are typical of the class of the images which contains the image being reconstructed by using a priori information, such as convexity or connectedness.
Theorems
Reconstructing planar lattice sets from their 1-dimensional X-rays is an NP-hard problem if the X-rays are taken from lattice directions.
Coloring a grid using colors with the restriction that each row and each column has a specific number of cells of each color is known as the −atom problem in the discrete tomography community. The problem is NP-hard for, see.
For further results see.
Algorithms
Among the reconstruction methods one can find algebraic reconstruction techniques, greedy algorithms, and Monte Carlo algorithms.
