A rounding theorem for unique binary tomographic reconstruction

DOI10.1016/J.DAM.2019.05.005MaRDI QIDQ2274077zbMATH OpenOpenAlexWikidataFDO

Authors Paolo Dulio, Silvia M. C. Pagani

Publication date 19 September 2019

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

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

zbMATH Keywords

binary tomographylattice directionlattice gridminimum-norm solutionuniqueness of reconstruction

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies for image processing (68U10)

Abstract: Discrete tomography deals with the reconstruction of images from projections collected along a few given directions. Different approaches can be considered, according to different models. In this paper we adopt the grid model, where pixels are lattice points with integer coordinates, X-rays are discrete lattice lines, and projections are obtained by counting the number of lattice points intercepted by X-rays taken in the assigned directions. We move from a theoretical result that allows uniqueness of reconstruction in the grid with just four suitably selected X-ray directions. In this framework, the structure of the allowed ghosts is studied and described. This leads to a new result, stating that the unique binary solution can be explicitly and exactly retrieved from the minimum Euclidean norm solution by means of a rounding method based on some special entries, which are precisely determined. A corresponding iterative algorithm has been implemented, and tested on a few phantoms having different characteristics and structure.

Review text

A large class of tomographic problems concerns the reconstruction of unknown objects by means of partial data coming from their projections. In order to find an exact solution, in this paper the binary grid model is used in which X-rays are discrete lattice lines. The projections are obtained by counting the number of lattice points intercepted by X-rays taken in the assigned directions. The theoretical considerations presented in this paper are based on a result that allows uniqueness of reconstruction ``in the grid with just four suitably selected X-ray directions. In this framework, the structure of the allowed ghosts is studied and described. This leads to a new result, stating that the unique binary solution can be explicitly and exactly retrieved from the minimum Euclidean norm solution by means of a rounding method based on some special entries, which are precisely determined. The proposed approach was implemented as a recursive Binary Reconstruction Algorithm. From the performed experiments, presented in this paper, one can see that this algorithm, after an appropriately large number of iterations, leads to the unique binary solution.

Recommendations

• scientific article; zbMATH DE number 1551779
• A Network Flow Algorithm for Reconstructing Binary Images from Continuous X-rays
• Discrete tomography by convex--concave regularization and D.C. programming
• scientific article; zbMATH DE number 1551782
• A geometrical characterization of regions of uniqueness and applications to discrete tomography

Cites work

• Algebraic aspects of discrete tomography
• An instance of the cutting stock problem for which the rounding property does not hold
• Analysis on the strip-based projection model for discrete tomography
• Application of a discrete tomography approach to computerized tomography
• Bounds for approximate discrete tomography solutions
• Bounds for discrete tomography solutions
• Bounds on the quality of reconstructed images in binary tomography
• DART: A Practical Reconstruction Algorithm for Discrete Tomography
• Discrete tomography determination of bounded lattice sets from four X-rays
• Discrete tomography determination of bounded sets in \(\mathbb{Z}^n\)
• Discrete tomography: Determination of finite sets by X-rays
• Ghosts in discrete tomography
• Growth of Discrete Projection Ghosts Created by Iteration
• scientific article; zbMATH DE number 3599866 (Why is no real title available?)
• scientific article; zbMATH DE number 2084491 (Why is no real title available?)
• scientific article; zbMATH DE number 1551772 (Why is no real title available?)
• scientific article; zbMATH DE number 1551773 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Integer Rounding for Polymatroid and Branching Optimization Problems
• Maximal N-ghosts and minimal information recovery from N projected views of an array
• Mixed integer linear programming formulation techniques
• Non-additive bounded sets of uniqueness in \(\mathbb Z^{n }\)
• On J-additivity and bounded additivity
• On the computational complexity of reconstructing lattice sets from their X-rays
• On the difference between solutions of discrete tomography problems
• On the difference between solutions of discrete tomography problems. II
• On the Non-additive Sets of Uniqueness in a Finite Grid
• Probabilistic reconstruction of \(hv\)-convex polyominoes from noisy projection data
• Projection selection dependency in binary tomography
• Properties of minimal ghosts
• Sets uniquely determined by projections on axes. II: Discrete case
• Stability results for uniquely determined sets from two directions in discrete tomography
• The cutting stock problem and integer rounding
• The modified integer round-up property of the one-dimensional cutting stock problem
• Uniqueness in discrete tomography: Three remarks and a corollary

Cited in

(14)

• On crossings of hyperplanes on the \(n\)-dimensional torus
• Algorithms for linear time reconstruction by discrete tomography. II
• Boundary ghosts for discrete tomography
• On some geometric aspects of the class of \(hv\)-convex switching components
• Characterization of hv-convex sequences
• Bounds on the Difference between Reconstructions in Binary Tomography
• scientific article; zbMATH DE number 1156687 (Why is no real title available?)
• scientific article; zbMATH DE number 1551779 (Why is no real title available?)
• Regions of uniqueness quickly reconstructed by three directions in discrete tomography
• Energy-minimization based discrete tomography reconstruction method for images on triangular grid
• Error Correction for Discrete Tomography
• Uniqueness and reconstruction of finite lattice sets from their line sums
• Erratum to: ``A rounding theorem for unique binary tomographic reconstruction
• A linear time approach to three-dimensional reconstruction by discrete tomography

Describes a project that uses

Uses Software

• TVR-DART

This page was built for publication: A rounding theorem for unique binary tomographic reconstruction

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