
DISCRETE TOMOGRAPHY
In the following part we outline the stateoftheart 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 Xrays taken along a given set of directions, while the second problem consists in deciding when a lattice set is uniquely determined by the Xrays 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 threedimensional 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 Xrays of the structure can be physically taken. This is the case, for instance in industrial nondestructive 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 Xrays taken in three or more nonparallel directions is NPhard [GG96]. The same complexity bound holds for uniqueness. In spite of the hardness in the complexitytheoretic 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 socalled 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 Xrays. The difference of two density functions whose corresponding configurations have equal Xrays 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, socalled 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 Upolygons, both from continuous and from discrete point of view [D08,DP07]. In particular, when a lattice Upolygon exists, it is easy to construct two different convex lattice sets with equal discrete parallel Xrays in the directions in U. In 1997 R. Gardner and P. Gritzmann proved that in fact the nonexistence of a lattice Upolygon 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 nonparallel 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 Xrays 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 Xrays taken along more than two directions is highly unstable [AG00,AG06]. This instability persists even when the Xrays 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 Xrays 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.1599608.
[AG06] A.Alpers and P.Gritzmann, On stability, error correction, and noise compensation in discrete tomography, SIAM J. Discrete Math. 20 (2006), pp.22739.
[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.17586.
[BD01] E. Barcucci, A. Del Lungo, M. Nivat and R. Pinzani, Xray characterizing some classes of discrete sets, LinearAlgebra Appl. 339 (2001), 321.
[BD03] S.Brunetti and A.Daurat, An algorithm reconstructing lattice convex sets, Theoret.Comp. Sci. 304 (2003), pp.3557.
[BD05] S.Brunetti and A.Daurat, Stability in discrete tomography: Some positive results, Discrete Appl. Math 147 (2005), pp.20726.
[D09A] B.E.van Dalen, Stability results for two directions in discrete tomography, Discrete Math. 309 (2009), pp.390516.
[D09B] B.E.van Dalen, On the difference between solutions of discrete tomography problems, Journal of Combinatorics and Number Theory 1 (2009), pp.1529.
[D05] A.Daurat, Determination of Qconvex sets by Xrays, Theoretical Computer Science, 332 (2005) pp.1945.
[D08] P. Dulio, Convex decomposition of Upolygons, Theoretical Computer Science, 406/12, (2008), 8089.
[DP07] P. Dulio. and C. Peri, On the geometric structure of lattice Upolygons, Discrete Math., 307/1920 (2007), 23302340.
[H05] L. Hajdu, Unique reconstruction of bounded sets in discrete tomography, Electron. Notes Discrete Math., 20 (2005) 1525.
[HT01] L. Hajdu and R. Tijdeman, Algebraic aspects of discrete tomography, J. reine angew. Math 534 (2001), 119128.
[HT03] L. Hajdu and R. Tijdeman, Algebraic aspects of emission tomography with absorption, Theoretical Computer Science, 290 (2003), 21692181.
[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), 149159.
[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 Xrays, Trans. Amer. Math. Soc. 349 (1997), pp.22712295.
[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.85113.
[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 PhotoOptical Instrumentation Engineers Proceedings 2826, 1996, pp.121132.
[GdV00]P. Gritzmann, S. de Vries and M. Wiegelmann, Approximating binary images from discrete xrays,
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 highresolution transmission electron microscopy of crystalline materials, Ultramicroscopy 58 (1995), pp.13155.
[IJ94] R.W.Irving and M.R.Jerrum, Threedimensional statistical data security problem, SIAM J. Comput. 23 (1994), pp.17084.
[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.4445. 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, pp191212.
[R57] H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Canad. J. Math. vol. 9 (1957) pp. 371377
[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.41503.
[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.1836.
[V07] E. Vallejo, Uniqueness and additivity for ndimensional binary m atrices with respect to their 1marginals, in Advances in Discrete Tomography and its Applications, G. Herman – A. Kuba eds, Birkhauser Boston, 2007, pp.83112.
[V84] A.Volcic, Wellposedness of the GardnerMcMullen reconstruction problem, Proc. Conf. Measure Theory, Oberwolfach 1983, Lecture Notesin Mathematics 1089, Springer, Berlin, 1984, pp. 199210. 
