• About Us
• Education
• Research
• PhD
• Acta Cybernetica
• Conferences
• Sponsors

• - Applied Informatics
• - Image Processing and Computer Graphics
• - Foundations of Computer Science
• - Computer Algorithms and Artificial Intelligence
• - Software Engineering
• - Research Group on Artificial Intelligence

Aspects of Discrete Tomography and Its Applications

Members: Attila Kuba, Péter Balázs, Antal Nagy, Emese Balogh Funded by Hungarian Research Foundation US National Science Foundation Partners: The Graduate Center, City University of New York (Gabor T. Herman) Related Projects: DIRECT Lifetime: 1999 - 2005

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

1. Gabor T. Herman and Attila Kuba, editors. Advances in Discrete Tomography and Its Applications, Applied and Numerical Harmonic Analysis. Birkhauser, 2007.
2. Gabor T. Herman and Attila Kuba, editors. Proceedings of the Workshop on Discrete Tomography and its Applications, volume 20 of Electronic Notes in Discrete Mathematics. Elsevier, July 2005.
3. Gabor T. Herman and Attila Kuba, editors. Discrete Tomography: Foundations, Algorithms, and Applicationsíy, Applied and Numerical Harmonic Analysis. Birkhauser, December 1999.
4. Péter Balázs, Emese Balogh, and Attila Kuba. Reconstruction of 8-connected but not 4-connected hv-convex discrete sets. Discrete Applied Mathematics, 147:149-168, 2005.
5. Attila Kuba and Maurice Nivat. A sufficient condition for non-uniqueness in binary tomography with absorption. Theoretical Computer Science, 346:335-357, November 2005.
6. Attila Kuba, Antal Nagy, and Emese Balogh. Reconstruction of hv-convex binary matrices from their absorbed projections. Discrete Applied Mathematics, 139:137-148, april 2004.
7. Gábor T. Herman and Attila Kuba. Discrete tomography in medical imaging. Proceedings of the IEEE, 91:1612-1626, October 2003.
8. Attila Kuba and Emese Balogh. Reconstruction of convex 2D discrete sets in polynomial time. Theoretical Computer Science, 283:223-242, June 2002.
9. Emese Balogh, Attila Kuba, Csaba Dévényi, and Alberto Del Lungo. Comparison of algorithms for reconstructing hv-convex discrete sets. Linear Algebra and its Applications, 339:23-35, December 2001.
10. Sara Brunetti, Alberto DelLungo, F. DelRistoro, Attila Kuba, and Maurice Nivat. Reconstruction of 4- and 8-connected convex discrete sets from row and column projections. Linear Algebra and its Applications, 339:37-57, 2001.
11. Attila Kuba and Maurice Nivat. Reconstruction of discrete sets with absorption. Linear Algebra and its Applications, 339:171-194, 2001.