Discrete Tomography: Reconstruction under periodicity constraints
Preprint
Abstract
This paper studies the problem of reconstructing binary matrices that are only accessible through few evaluations of their discrete X-rays. Such question is prominently motivated by the demand in material science for developing a tool for the reconstruction of crystalline structures from their images obtained by high-resolution transmission electron microscopy. Various approaches have been suggested for solving the general problem of reconstructing binary matrices that are given by their discrete X-rays in a number of directions, but more work have to be done to handle the ill-posedness of the problem. We can tackle this ill-posedness by limiting the set of possible solutions, by using appropriate a priori information, to only those which are reasonably typical of the class of matrices which contains the unknown matrix that we wish to reconstruct. Mathematically, this information is modelled in terms of a class of binary matrices to which the solution must belong. Several papers study the problem on classes of binary matrices on which some connectivity and convexity constraints are imposed. We study the reconstruction problem on some new classes consisting of binary matrices with periodicity properties, and we propose a polynomial-time algorithm for reconstructing these binary matrices from their orthogonal discrete X-rays.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Reconstruction of lattice sets from their horizontal, vertical and diagonal X-raysDiscrete Mathematics, 2001
- On the computational complexity of reconstructing lattice sets from their X-raysDiscrete Mathematics, 1999
- Reconstructing hv-convex polyominoes from orthogonal projectionsInformation Processing Letters, 1999
- Discrete tomography: Determination of finite sets by X-raysTransactions of the American Mathematical Society, 1997
- The discrete Radon transform and its approximate inversion via linear programmingDiscrete Applied Mathematics, 1997
- Reconstructing convex polyominoes from horizontal and vertical projectionsTheoretical Computer Science, 1996
- Invariant sets of arcs in network flow problemsDiscrete Applied Mathematics, 1986
- Matrices of zeros and ones with fixed row and column sum vectorsLinear Algebra and its Applications, 1980
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979
- Switching components and the ambiguity problem in the reconstruction of pictures from their projectionsPattern Recognition, 1978