Error Correction for Discrete Tomography

Fundamenta Informaticae, vol. Volume 189, Issue 2:...

Abstract

Discrete tomography focuses on the reconstruction of functions $f: A \to \mathbb{R}$ from their line sums in a finite number $d$ of directions, where $A$ is a finite subset of $\mathbb{Z}^2$. Consequently, the techniques of discrete tomography often find application in areas where only a small number of projections are available. In 1978 M.B. Katz gave a necessary and sufficient condition for the uniqueness of the solution. Since then, several reconstruction methods have been introduced. Recently Pagani and Tijdeman developed a fast method to reconstruct $f$ if it is uniquely determined. Subsequently Ceko, Pagani and Tijdeman extended the method to the reconstruction of a function with the same line sums of $f$ in the general case. Up to here we assumed that the line sums are exact. In this paper we investigate the case where a small number of line sums are incorrect as may happen when discrete tomography is applied for data storage or transmission. We show how less than $d/2$ errors can be corrected and that this bound is the best possible. Comment: final version

Authors 3

1. M. Ceko

   Monash University

   Affiliation as printed

   School of Physics and Astronomy Monash University , Melbourne , Australia

2. L. Hajdu

   University of Debrecen

   Affiliation as printed

   Institute of Mathematics , University of Debrecen , Debrecen , Hungary

3. R. Tijdeman Aachen Mathematical Institute

   Leiden University · Monash University

   Affiliation as printed

   Mathematical Institute , Leiden University , Leiden , The Netherlands

   School of Physics and Astronomy Monash University , Melbourne , Australia