DISCRETE TOMOGRAPHY

In the following part we outline the state-of-the-art relevant to this project. In particular the focus is on the three main topics related to the reconstruction, uniqueness and stability questions, and on the different approaches for dealing with these problems.

The main problems of Discrete Tomography are the reconstruction and the uniqueness problems. First one consists in the retrieval of an unknown discrete set from the knowledge of its X-rays taken along a given set of directions, while the second problem consists in deciding when a lattice set is uniquely determined by the X-rays corresponding to a given set of directions. An overview of the topics treated in Discrete Tomography and of relevant results in the field are collected in [HK99] and [HK07]. The main application of Discrete Tomography is the reconstruction of three-dimensional crystals from Xrays taken by an electron microscope [SK93,KS95]. The high energy electron beam in the microscope necessary to produce the discrete radiographies of a given crystal can damage the specimen if too many X rays are employed and for this reason only a few X-rays of the structure can be physically taken. This is the case, for instance in industrial non-destructive testing, in order to contain the costs, or in electron microscopy, because of the damage by radiation. Further examples include quality control in semiconductor industry, image processing, data compression and data security [IJ94,JB04,SG82]. In all these applications the conventional techniques of the Computerized Tomography cannot be applied. The research developed since '90 in Discrete Tomography follows different approaches. A first approach is based on image processing, medical imaging techniques and origins by Computerized Tomography (see for an example [MV99]).

A second approach is based on computerized and convex geometry, and optimization for providing the relevant mathematical methods for tomographic reconstruction of crystalline structures. Results in this subject concern the computational complexity of the reconstruction problem. If the data is measured in only two directions, then reconstruction can be done in polynomial time [R57](however, in general reconstruction will not be unique). In contrast, reconstruction from X-rays taken in three or more nonparallel directions is NP-hard [GG96]. The same complexity bound holds for uniqueness. In spite of the hardness in the complexity-theoretic sense, applications demands for algorithms for solving the problem. For this reason, approximation algorithms have been investigated [GdV00] and in case of special structures exact algorithms which exploit particular properties of the objects to be reconstructed [BD03]. There are results in this direction also concerning uniqueness. A main result is that convex subsets of Z2 are uniquely determined by suitable sets of four directions [GG97,GG99]. The same directions distinguish so-called Qconvex sets [D05]. We also mention that the authors of [BD01] obtained several related negative results, based on combinatory and discrete mathematics, in the more general case when the discrete set to be reconstructed is assumed to be a so called horizontally and vertically convex polyomino. This latter approach is geometric since uses geometric properties such as convexity to determine uniqueness results. In the more general case when no such properties are considered, this approach cannot easily be extended to work. Connections between the notion of uniqueness and additivity are studied in [FL96,V]. A different approach is that introduced by Hadju and Tijdeman based on generating functions and divisibility properties of polynomials [HT01]. This algebraic approach has been turned out useful for studying both the reconstruction and the uniqueness problems. They provided an algorithm for solving tomographycal problems and extended their results to the case of emission tomography with absorption [HT03]. Moreover they studied uniqueness when discrete sets have the constraint to belong to a discrete grid of fixed size. In this case there exists a set of four directions depending only on the size of the grid that permits to distinguish any two subsets [H05]. In case of ambiguous reconstruction, different discrete sets yield the same X-rays. The difference of two density functions whose corresponding configurations have equal X-rays is a function with zero line sums along the given directions. This means that ambiguous configurations often appear, and, in general, these are addressed as switching configurations. In the case of row and column sums such switching configurations were already studied by H. Ryser under the name of interchanges, and later extended for more than two directions by several authors.

An algebraic theory of their structure, based on switching components of minimal size, so-called switching atoms, has been developed since 2001 by L. Hajdu and R. Tijdeman. Differently, the study of ambiguous configurations under the convexity constraint has been considered in several papers dealing with the geometric structure of so called U-polygons, both from continuous and from discrete point of view [D08,DP07]. In particular, when a lattice U-polygon exists, it is easy to construct two different convex lattice sets with equal discrete parallel X-rays in the directions in U. In 1997 R. Gardner and P. Gritzmann proved that in fact the non-existence of a lattice U-polygon is necessary and sufficient for the discrete parallel Xrays in the directions in U to determine convex lattice sets (provided U has at least two non-parallel directions). The study of the difference of two discrete sets tomographically equivalent allows to measure in some sense how far from determining uniqueness is the considered set of directions. If data are affected by errors, bounds on the difference of any two discrete sets having bounded difference of their X-rays gives a measure of stability or instability in the reconstruction [AB07,D09A,D09B]. It is worth remarking that questions of stability are relevant for the applications, since noise in the data cannot be avoided. It can be shown that the reconstruction of lattice sets from X-rays taken along more than two directions is highly unstable [AG00,AG06]. This instability persists even when the X-rays uniquely determine the object. In [BD05] the authors proved that, under some extra assumptions, a stability result holds when the error on the data is “small”. In particular, they obtained an upper bound for the symmetric difference of two lattice sets depending on the distance of their X-rays and the maximal size of the sets.

References

[A07] A.Alpers and S.Brunetti, Stability results for the reconstruction of binary pictures from two projections, Image and Vision Computing 25, (2007), pp.1599-608.

[AG06] A.Alpers and P.Gritzmann, On stability, error correction, and noise compensation in discrete tomography, SIAM J. Discrete Math. 20 (2006), pp.227-39.

[AG01] A.Alpers, P.Gritzmann, and L.Thorens, Stability and instability in discrete tomography, in Digital and Image Geometry 2000 , Lecture Notes in Computer Science 2243, Springer. Berlin, 2001, pp.175-86.

[BD01] E. Barcucci, A. Del Lungo, M. Nivat and R. Pinzani, X-ray characterizing some classes of discrete sets, LinearAlgebra Appl. 339 (2001), 3-21.

[BD03] S.Brunetti and A.Daurat, An algorithm reconstructing lattice convex sets, Theoret.Comp. Sci. 304 (2003), pp.35-57.

[BD05] S.Brunetti and A.Daurat, Stability in discrete tomography: Some positive results, Discrete Appl. Math 147 (2005), pp.207-26.

[D09A] B.E.van Dalen, Stability results for two directions in discrete tomography, Discrete Math. 309 (2009), pp.3905-16.

[D09B] B.E.van Dalen, On the difference between solutions of discrete tomography problems, Journal of Combinatorics and Number Theory 1 (2009), pp.15-29.

[D05] A.Daurat, Determination of Q-convex sets by X-rays, Theoretical Computer Science, 332 (2005) pp.19-45.

[D08] P. Dulio, Convex decomposition of U-polygons, Theoretical Computer Science, 406/1-2, (2008), 80-89.

[DP07] P. Dulio. and C. Peri, On the geometric structure of lattice U-polygons, Discrete Math., 307/19-20 (2007), 2330-2340.

[H05] L. Hajdu, Unique reconstruction of bounded sets in discrete tomography, Electron. Notes Discrete Math., 20 (2005) 15-25.

[HT01] L. Hajdu and R. Tijdeman, Algebraic aspects of discrete tomography, J. reine angew. Math 534 (2001), 119-128.

[HT03] L. Hajdu and R. Tijdeman, Algebraic aspects of emission tomography with absorption, Theoretical Computer Science, 290 (2003), 2169-2181.

[FL91] Peter C. Fishburn, J. C. Lagarias, James A. Reeds, Larry A. Shepp: Sets uniquely determined by projections on axes II Discrete case. Discrete Mathematics 91(2) (1991), 149-159.

[G] R. J.Gardner, Geometric Tomography, 2nd ed.Cambridge University Press, New York, 2006.

[GG97] R.J. Gardner and P.Gritzmann, Discrete tomography: Determination of finite sets by X-rays, Trans. Amer. Math. Soc. 349 (1997), pp.2271-2295.

[GG99] R.J.Gardner and P.Gritzmann, Uniqueness and complexity in discrete tomography, in: Discrete Tomography:Foundations, Algorithms and Application, ed.by G.T.Herman and A.Kuba, Birkhäuser, Boston, 1999, pp.85-113.

[GG96] R.J.Gardner, P.Gritzmann and P.Prangenberg, On the reconstruction of binary images from their discrete Radon transform, in: Vision Geometry V, ed.by R.A.Melter, A.Y.Wu, and L.Latecki, Society of Photo-Optical Instrumentation Engineers Proceedings 2826, 1996, pp.121-132.

[GdV00]P. Gritzmann, S. de Vries and M. Wiegelmann, Approximating binary images from discrete x-rays,
SIAM J. Optimization 11 (2000) (2), pp. 522–546.

[HK99] G.T.Herman and A.Kuba, Discrete Tomography: Foundations, Algorithms, and Applications, Birkhäuser, Boston, 1999.

[HK07] G.T.Herman and A.Kuba, Advances in Discrete Tomography and its Applications, Birkhäuser, Boston, 2007.

[KS95]C.Kisieloski, P.Schwander, F.H.Baumann, M. Seibt, Y.Kim, and A.Ourmazd, An approach to quantitative high-resolution transmission electron microscopy of crystalline materials, Ultramicroscopy 58 (1995), pp.131-55.

[IJ94] R.W.Irving and M.R.Jerrum, Three-dimensional statistical data security problem, SIAM J. Comput. 23 (1994), pp.170-84.

[JB04] J.R. Jinschek, K.J. Batenburg, H. Calderon, D. Van Dyck, F.R. Chen, C. Kisielowski, Prospects for bright field and dark field electron tomography on a discrete grid, Microscopy Microanal. 10 (Suppl. 3) (2004), pp.44-45. Cambridge Journals Online.

[MV99]S. Matej, A. Vardi, G. Herman, E. Vardi, Binary tomography using Gibbs Priors, in: Discrete Tomography:Foundations, Algorithms and Application, ed.by G.T.Herman and A.Kuba, Birkhäuser, Boston, 1999, pp191-212.

[R57] H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Canad. J. Math. vol. 9 (1957) pp. 371-377

[SK93] P.Schwander, C.Kisielowski, M.Seibt, F.H. Baumann, Y.Kim, and A.Ourmazd, Mapping projected potential, interfacial roughness, and composition in general cyrstalline solids by quantitative transmission electron microscopy, Phys. Rev. Lett. 71 (1993), pp.4150-3.

[SG82] C.H Slump and J.J.Gerbrands, A network flow approach to reconstruction of the left ventricle from two projections, Comput. Graphics Image Processing 18 (1982), pp.18-36.

[V07] E. Vallejo, Uniqueness and additivity for n-dimensional binary m atrices with respect to their 1-marginals, in Advances in Discrete Tomography and its Applications, G. Herman – A. Kuba eds, Birkhauser Boston, 2007, pp.83-112.

[V84] A.Volcic, Well-posedness of the Gardner-McMullen reconstruction problem, Proc. Conf. Measure Theory, Oberwolfach 1983, Lecture Notesin Mathematics 1089, Springer, Berlin, 1984, pp. 199-210.