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 (line sums) 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 (DIMACS Mini-Symposium on Discrete Tomography, September 19, 1994, Rutgers University).
Theory
Discrete tomography has strong connections with other mathematical fields, such as number theory,[3][4][5]discrete mathematics,[6][7][8]computational complexity theory[9][10] and combinatorics.[11][12][13] 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.[14] 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 (finite) planar lattice sets from their 1-dimensional X-rays is an NP-hard problem if the X-rays are taken from lattice directions (for the problem is in P).[9]
The reconstruction problem is highly unstable for (meaning that a small perturbation of the X-rays may lead to completely different reconstructions)[15] and stable for , see.[15][16][17]
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.[10]
A form of discrete tomography also forms the basis of nonograms, a type of logic puzzle in which information about the rows and columns of a digital image is used to reconstruct the image.[27]
A. Alpers, P. Gritzmann, On Stability, Error Correction, and Noise Compensation in Discrete Tomography, SIAM Journal on Discrete Mathematics 20 (1), pp. 227-239, 2006
P. Gritzmann, B. Langfeld, On the index of Siegel grids and its application to the tomography of quasicrystals. European J. Combin. 29 (2008), no. 8, 1894-1909.
A. Alpers, P. Gritzmann, L. Thorens, Stability and Instability in Discrete Tomography, Lecture Notes in Computer Science 2243; Digital and Image Geometry (Advanced Lectures), G. Bertrand, A. Imiya, R. Klette (Eds.), pp. 175-186, Springer-Verlag, 2001.
Batenburg, Joost; Sijbers, Jan - DART: A practical reconstruction algorithm for discrete tomography - In: IEEE transactions on image processing, Vol. 20, Nr. 9, p. 2542-2553, (2011). doi:10.1109/TIP.2011.2131661
W. van Aarle, K J. Batenburg, and J. Sijbers, Automatic parameter estimation for the Discrete Algebraic Reconstruction Technique (DART), IEEE Transactions on Image Processing, 2012
K. J. Batenburg, and J. Sijbers, "Generic iterative subset algorithms for discrete tomography", Discrete Applied Mathematics, vol. 157, no. 3, pp. 438-451, 2009
A. Alpers, H.F. Poulsen, E. Knudsen, G.T. Herman, A Discrete Tomography Algorithm for Improving the Quality of 3DXRD Grain Maps, Journal of Applied Crystallography 39, pp. 582-588, 2006 .
S. Bals, K. J. Batenburg, J. Verbeeck, J. Sijbers and G. Van Tendeloo, "Quantitative 3D reconstruction of catalyst particles for bamboo-like carbon-nanotubes", Nano Letters, Vol. 7, Nr. 12, p. 3669-3674, (2007) doi:10.1021/nl071899m
Batenburg J., S. Bals, Sijbers J., C. Kubel, P.A. Midgley, J.C. Hernandez, U. Kaiser, E.R. Encina, E.A. Coronado and G. Van Tendeloo, "3D imaging of nanomaterials by discrete tomography", Ultramicroscopy, Vol. 109, p. 730-740, (2009) doi:10.1016/j.ultramic.2009.01.009
K. J. Batenburg, J. Sijbers, H. F. Poulsen, and E. Knudsen, "DART: A Robust Algorithm for Fast Reconstruction of 3D Grain Maps", Journal of Applied Crystallography, vol. 43, pp. 1464-1473, 2010
This article uses material from the Wikipedia article Discrete_tomography, and is written by contributors.
Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.