


A new Algorithm for Discrete Tomographyby Rob Tijdeman and Herman te Riele Discrete tomography concerns the problem of recovering binary images from their projections. Recently, Tijdeman (University of Leiden, The Netherlands) and Hajdu (University of Debrecen, Hungary) have made a new mathematical analysis of this problem. In a joint project starting this summer, researchers at Leiden University and CWI will implement an algorithm based on this analysis, such that it can handle large problems, and apply it to the recovery of crystalline structures and the reconstruction of the shape of heart chambers from orthogonal biplane cardiac angiograms. Discrete tomography has its origin in the analysis of crystalline structures with the help of electron miscroscopy. In particular, one wishes to determine the presence or absence of atoms in a crystal lattice, a twovalued situation (ie, a binary image). Electron rays, transmitted through the material, yield projections of the atom structure of the crystal. The number of projections is limited because the material may get damaged by the transmitted rays. A binary image is a rectangular array of pixels, each of which is either black (value 0) or white (value 1). A projection of a binary image is defined as a data set which for every line in some direction counts how may white pixels are intersected by that line (the transmitted ray in electron microscopy). This leads to a linear system of equations which, in general, is underdetermined and allows many solutions when only a few projections are available. It turns out, however, that discrete tomography may be quite useful in the case of convex objects such as layers and tumors. In such cases, the solution may well be unique or almost unique. In the case of tumors, the line sums are not exact in general, and socalled noise may affect the correctness of the data set.
The mathematical analysis by Tijdeman and Hajdu of the discrete tomography problem has been published in 2001 in the ‘Journal für die reine und angewandte Mathematik’. Here they study the problem of reconstructing a function which maps a finite lattice of integer pairs in the plane to a subset of the integers. The sums of the function values along a finite set of lines, the projections, are given. It is shown that the possible solution functions form a grid on a linear manifold, and that the solutions with only function values equal to 0 and 1 correspond to points in the grid which have the smallest distance to the origin. It is shown further that there is a basic structure, the socalled switching component, whose translates generate the grid. A simple device is provided to derive the switching element from the set of directions. In a sequel paper, which has appeared in the journal ‘Linear Algebra and its Applications’, Tijdeman and Hajdu apply their theory to the special case of four directions, viz., along rows, columns, diagonals, and antidiagonals. The resulting algorithm finds a function with exactly the prescribed line sums and with integer pixel values which are small in absolute value. From this, a 01 solution with approximately correct line sums is easily obtained. It turns out that for convex patterns of 1’s perfect reconstruction is possible. Please contact: 