Binary matrices under the microscope: A tomographical problem

DOI10.1016/J.TCS.2006.10.030MaRDI QIDQ868951zbMATH OpenOpenAlexFDO

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 complexitydiscrete tomographyprojectionreconstruction algorithmrectangular scan

Mathematics Subject Classification ID

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

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 Z^2 and plane tilings
• Reconstructing \(hv\)-convex polyominoes from orthogonal projections
• Reconstructing convex polyominoes from horizontal and vertical projections

Cited in

(18)

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

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)