A binary matrix can be scanned by moving a fixed rectangular window (sub-matrix) across it, rather like examining it closely under a microscope. With each viewing, a convenient measurement is the number of 1s visible in the window, which might be thought of as the luminosity of the window. The rectangular scan of the binary matrix is then the collection of these luminosities presented in matrix form. We show that, at least in the technical case of a smoothm × n binary matrix, it can be reconstructed from its rectangular scan in polynomial time in the parameters m and n, where the degree of the polynomial depends on the size of the window of inspection. For an arbitrary binary matrix, we then extend this result by determining the entries in its rectangular scan that preclude the smoothness of the matrix.

Binary Matrices under the Microscope: A Tomographical Problem / A.Frosini; M.Nivat. - STAMPA. - 3322:(2004), pp. 1-22. (Intervento presentato al convegno 10th International Workshop on Combinatorial Image Analysis, IWCIA 2004) [10.1007/978-3-540-30503-3_1].

Binary Matrices under the Microscope: A Tomographical Problem

FROSINI, ANDREA;
2004

Abstract

A binary matrix can be scanned by moving a fixed rectangular window (sub-matrix) across it, rather like examining it closely under a microscope. With each viewing, a convenient measurement is the number of 1s visible in the window, which might be thought of as the luminosity of the window. The rectangular scan of the binary matrix is then the collection of these luminosities presented in matrix form. We show that, at least in the technical case of a smoothm × n binary matrix, it can be reconstructed from its rectangular scan in polynomial time in the parameters m and n, where the degree of the polynomial depends on the size of the window of inspection. For an arbitrary binary matrix, we then extend this result by determining the entries in its rectangular scan that preclude the smoothness of the matrix.
2004
Combinatorial Image Analysis
10th International Workshop on Combinatorial Image Analysis, IWCIA 2004
A.Frosini; M.Nivat
File in questo prodotto:
File Dimensione Formato  
[7]congr.pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: Tutti i diritti riservati
Dimensione 259.66 kB
Formato Adobe PDF
259.66 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/397401
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 3
social impact