Binary matrices under the microscope: A tomographical problem

DOI10.1016/J.TCS.2006.10.030zbMATH Open1113.68107arXivmath/0609792OpenAlexW2021085416MaRDI QIDQ868951FDOQ868951

M. Nivat, Andrea Frosini

Publication date: 26 February 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: A binary matrix can be scanned by moving a fixed rectangular window (submatrix) 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 smooth m x n binary matrix, it canbe 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.

Full work available at URL: https://arxiv.org/abs/math/0609792

zbMATH Keywords

computational complexityprojectionreconstruction algorithmdiscrete tomographyrectangular scan

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies for image processing (68U10) Matrices of integers (15B36)

Cites Work

• Discrete tomography. Foundations, algorithms, and applications
• Reconstructing \(hv\)-convex polyominoes from orthogonal projections
• Reconstructing convex polyominoes from horizontal and vertical projections
• Combinatorial Properties of Matrices of Zeros and Ones
• Homogeneous subsets of \(\mathbb Z^2\) and plane tilings
• An introduction to periodical discrete sets from a tomographical perspective

Cited In (15)

• On the decomposability of homogeneous binary planar configurations with respect to a given exact polyomino
• Enumeration of two dimensional palindromes
• Weighted microscopic image reconstruction
• Weighted microscopic image reconstruction
• Scanning integer matrices by means of two rectangular windows
• Relaxed and approximate graph realizations
• Generic iterative subset algorithms for discrete tomography
• Binary image reconstruction based on prescribed numerical information
• The generalized microscopic image reconstruction problem
• \textsc{Minimum Surgical Probing} with convexity constraints
• Vertex-weighted realizations of graphs
• An inverse problem for the collapsing sum
• Planar Configurations Induced by Exact Polyominoes
• The generalized microscopic image reconstruction problem for hypergraphs
• Proving a conjecture on prime double square tiles

This page was built for publication: Binary matrices under the microscope: A tomographical problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868951)