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.

Discrete Tomography: Reconstruction under periodicity constraints / A.Del Lungo; A.Frosini; M.Nivat; L.Vuillon. - STAMPA. - 2380:(2002), pp. 38-56. (Intervento presentato al convegno Automata, Languages and Programming, 29th International Colloquium, ICALP 2002) [10.1007/3-540-45465-9_5].

Discrete Tomography: Reconstruction under periodicity constraints

FROSINI, ANDREA;
2002

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.
2002
Automata, Languages and Programming
Automata, Languages and Programming, 29th International Colloquium, ICALP 2002
A.Del Lungo; A.Frosini; M.Nivat; L.Vuillon
File in questo prodotto:
File Dimensione Formato  
[3]congr.pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: Tutti i diritti riservati
Dimensione 212.44 kB
Formato Adobe PDF
212.44 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/397407
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 4
social impact