Algorithms for linear time reconstruction by discrete tomography. II

DOI10.1016/J.DAM.2021.03.008zbMATH Open1465.94009arXiv2010.07862OpenAlexW4206409392MaRDI QIDQ2028077FDOQ2028077

Authors: Matthew Ceko, Silvia M. C. Pagani, R. Tijdeman 

Publication date: 31 May 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: The reconstruction of an unknown function $f$ from its line sums is the aim of discrete tomography. However, two main aspects prevent reconstruction from being an easy task. In general, many solutions are allowed due to the presence of the switching functions. Even when uniqueness conditions are available, results about the NP-hardness of reconstruction algorithms make their implementation inefficient when the values of $f$ are in certain sets. We show that this is not the case when $f$ takes values in a field or a unique factorization domain, such as $R$ or $$. We present a linear time reconstruction algorithm (in the number of directions and in the size of the grid), which outputs the original function values for all points outside of the switching domains. Freely chosen values are assigned to the other points, namely, those with ambiguities. Examples are provided.

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

Recommendations

• Algorithms for linear time reconstruction by discrete tomography
• An algorithm for discrete tomography
• scientific article; zbMATH DE number 2086609
• Analysis and optimization of an algorithm for discrete tomography
• scientific article; zbMATH DE number 1551782
• Discrete tomography. Foundations, algorithms, and applications
• Fast Approximation of Algebraic Reconstruction Methods for Tomography
• An algebraic framework for discrete tomography: revealing the structure of dependencies
• scientific article; zbMATH DE number 869701
• Algebraic discrete tomography

zbMATH Keywords

reconstruction algorithmdiscrete tomographyghostswitching functionlattice direction

Mathematics Subject Classification ID

Biomedical imaging and signal processing (92C55) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Computing methodologies for image processing (68U10)

Cites Work

• Fundamentals of Computerized Tomography
• Title not available (Why is that?)
• The mathematics of computerized tomography
• Sets uniquely determined by projections on axes. II: Discrete case
• Algebraic aspects of discrete tomography
• Uniqueness regions under sets of generic projections in discrete tomography
• Unique reconstruction of bounded sets in discrete tomography
• Discrete tomography determination of bounded lattice sets from four X-rays
• DART: A Practical Reconstruction Algorithm for Discrete Tomography
• Combinatorial Properties of Matrices of Zeros and Ones
• On the computational complexity of reconstructing lattice sets from their \(X\)-rays
• Discrete tomography: Determination of finite sets by X-rays
• On the computational complexity of determining polyatomic structures by X-rays
• Title not available (Why is that?)
• A rounding theorem for unique binary tomographic reconstruction
• Fast Approximation of Algebraic Reconstruction Methods for Tomography
• Bounds for discrete tomography solutions
• Algorithms for linear time reconstruction by discrete tomography
• A geometrical characterization of regions of uniqueness and applications to discrete tomography
• Regions of uniqueness quickly reconstructed by three directions in discrete tomography
• Geometrical characterization of the uniqueness regions under special sets of three directions in discrete tomography

Cited In (8)

• Discrete tomography in four directions
• Algorithms for linear time reconstruction by discrete tomography
• Boundary ghosts for discrete tomography
• A linear time approach to three-dimensional reconstruction by discrete tomography
• Algebraic aspects of discrete tomography
• Three-dimensional maximal and boundary ghosts
• Error Correction for Discrete Tomography
• An algorithm for discrete tomography

Uses Software

• TVR-DART

This page was built for publication: Algorithms for linear time reconstruction by discrete tomography. II

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