You are here

Aspects of Discrete Tomography and Its Applications

Related projects: 
Lifetime from: 
1999
Lifetime to: 
2005
Short description: 
Theoretical aspects of main problems in Discrete Tomography are studied such as existence, consistency, and reconstruction under several assumptions. Efficient reconstruction algorithms are also developed by incorporating prior knowledge into the reconstruction.
Description: 

We assume that there is a domain, which may itself be discrete (such as a set of ordered pairs of integers) or continuous (such as Euclidean space). We further assume that there is an unknown function f whose range is known to be a given discrete set (usually of real numbers). The problems of discrete tomography, as we perceive the field, have to do with determining f (perhaps only partially, perhaps only approximately) from weighted sums over subsets of its domain in the discrete case and from weighted integrals over subspaces of its domain in the continuous case. In many applications these sums or integrals may be known only approximately. From this point of view, the most essential aspect of discrete tomography is that knowing the discrete range of f may allow us to determine its value at points where without this knowledge it could not be determined. Discrete tomography is full of mathematically fascinating questions and it has many interesting applications. Three main theoretical problems are concerned in discrete tomography.

1. CONSISTENCY: Given a set of prescribed projections along certain lattice directions does there exist a discrete set with the given projections?

2. UNIQUENESS: Do the projections uniquely determine the discrete set, or there may be different discrete sets with the same projections?

3. RECONSTRUCTION: Given a set of prescribed projections along certain lattice directions construct a discrete set with the given projections.

In some cases the above tasks are easy, however - depending on the number and the directions of the projections - these problems can also be NP-hard. A commonly used technique to avoid intractability and to reduce ambiguity of the reconstruction is to incorporate some a priori information into the reconstruction process. The most frequently used properties are of geometrical nature, like connectedness, and convexity. In this project we study the three main and other related questions of discrete tomography, always using some prior information.

Publications: 
Herman GT, Kuba A. Proceedings of the Workshop on Discrete Tomography and its Applications. Vol Electronic Notes in Discrete Mathematics. Elsevier; 2005.
Herman GT, Kuba A. Discrete tomography in medical imaging. Proceedings of the IEEE. 2003;91:1612-1626.
Kuba A, Balogh E. Reconstruction of convex 2D discrete sets in polynomial time. Theoretical Computer Science. 2002;283:223-242.
Kuba A, Nivat M. Reconstruction of discrete sets with absorption. Linear Algebra and its Applications. 2001;339:171-194.
Kategória: 
Tomography - Discrete Tomography