Binary matrices under the microscope: A tomographical problem

DOI10.1016/J.TCS.2006.10.030MaRDI QIDQ868951zbMATHOpenAlexFDO

Authors Andrea Frosini, M. Nivat

Publication date 26 February 2007

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

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)

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.

Recommendations

• Combinatorial Image Analysis
• Binary 3D-Matrices Under the Microscope: A Tomographical Problem
• Scanning integer matrices by means of two rectangular windows
• Reconstructing binary matrices under window constraints from their row and column sums
• Reconstruction of binary matrices under fixed size neighborhood constraints

Cites work

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

Cited in

(16)

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

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)