Discrete tomography
Encyclopedia
Discrete Tomography focuses on the problem of reconstruction of binary image
s (or finite subsets of the integer lattice
) from a small number of their projection
s.
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 integral
s 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
).
, discrete mathematics
, complexity theory
and combinatorics
. In fact, a number of discrete
tomography problems were first discussed as combinatorial problems. In 1957,
Herbert John 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 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.
For further results see.
s (e.g., DART), greedy algorithm
s (see for approximation guarantees), and Monte Carlo algorithm
s.
, medicine
,
three-dimensional statistical data security problems, computer
tomograph assisted engineering and design, electron microscopy
, and materials science
.
Binary image
A binary image is a digital image that has only two possible values for each pixel. Typically the two colors used for a binary image are black and white though any two colors can be used. The color used for the object in the image is the foreground color while the rest of the image is the...
s (or finite subsets of the integer lattice
Integer lattice
In mathematics, the n-dimensional integer lattice , denoted Zn, is the lattice in the Euclidean space Rn whose lattice points are n-tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid lattice. Zn is the simplest example of a root lattice...
) from a small number of their projection
Projection
Projection, projector, or projective may refer to:* The display of an image by devices such as:** Movie projector** Video projector** Overhead projector** Slide projector** Camera obscura** Projection screen...
s.
In general, tomography
Tomography
Tomography refers to imaging by sections or sectioning, through the use of any kind of penetrating wave. A device used in tomography is called a tomograph, while the image produced is a tomogram. The method is used in radiology, archaeology, biology, geophysics, oceanography, materials science,...
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
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
and the problem posed is to reconstruct this function from its integral
Integral
Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...
s 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
DIMACS
The Center for Discrete Mathematics and Theoretical Computer Science is a collaboration between Rutgers University, Princeton University, and the research firms AT&T, Bell Labs, Telcordia, and NEC. It was founded in 1989 with money from the National Science Foundation...
Mini-Symposium on Discrete Tomography, September 19, 1994, Rutgers University
Rutgers University
Rutgers, The State University of New Jersey , is the largest institution for higher education in New Jersey, United States. It was originally chartered as Queen's College in 1766. It is the eighth-oldest college in the United States and one of the nine Colonial colleges founded before the American...
).
Theory
Discrete tomography has strong connections with other mathematical fields, such as number theoryNumber theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, discrete mathematics
Discrete mathematics
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...
, complexity theory
Complex systems
Complex systems present problems in mathematical modelling.The equations from which complex system models are developed generally derive from statistical physics, information theory and non-linear dynamics, and represent organized but unpredictable behaviors of systems of nature that are considered...
and combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
. In fact, a number of discrete
tomography problems were first discussed as combinatorial problems. In 1957,
Herbert John Ryser
Herbert John Ryser
Herbert John Ryser was a professor of mathematics, widely regarded as one of the major figures in combinatorics in the 20th century...
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
David Gale
David Gale was a distinguished American mathematician and economist. He was a Professor Emeritus at University of California, Berkeley, affiliated with departments of Mathematics, Economics, and Industrial Engineering and Operations Research...
found
the same consistency conditions, but in connection with the network flow
Network flow
In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...
problem.
Another result of Ryser 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
Binary image
A binary image is a digital image that has only two possible values for each pixel. Typically the two colors used for a binary image are black and white though any two colors can be used. The color used for the object in the image is the foreground color while the rest of the image is the...
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-hardNP-hardNP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
problem if the X-rays are taken from
lattice directions (for 
the problem is in P).
- The reconstruction problem is highly unstable for
(meaning that a small perturbation of the X-rays may lead to completely different reconstructions) and stable for 
, see.
- 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 techniqueAlgebraic Reconstruction Technique
frame|right|Animated sequence of reconstruction steps, one iteration.The Algebraic Reconstruction Technique is an iterative algorithm for the reconstruction of a images from a series of angular projections , used in computed tomography...
s (e.g., DART), greedy algorithm
Greedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
s (see for approximation guarantees), and Monte Carlo algorithm
Monte Carlo algorithm
In computing, a Monte Carlo algorithm is a randomized algorithm whose running time is deterministic, but whose output may be incorrect with a certain probability....
s.
Applications
Various algorithms have been applied in image processingImage processing
In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
, medicine
Medicine
Medicine is the science and art of healing. It encompasses a variety of health care practices evolved to maintain and restore health by the prevention and treatment of illness....
,
three-dimensional statistical data security problems, computer
tomograph assisted engineering and design, electron microscopy
, and materials science
Materials science
Materials science is an interdisciplinary field applying the properties of matter to various areas of science and engineering. This scientific field investigates the relationship between the structure of materials at atomic or molecular scales and their macroscopic properties. It incorporates...
.