Search

There exists an elegant correspondence between the problem of reconstructing a 0-1 lattice image from two of its projections and the problem of finding a maximum flow in a certain graph. In this chapter we describe how network flow algorithms can be used to solve a variety of problems from discrete tomography. First, we describe the network flow approach for two projections and several of its generalizations. Subsequently, we present an algorithm for reconstructing 0-1 images from more than two projections. The approach is extended to the reconstruction of 3D images and images that do not have an intrinsic lattice structure. [ABSTRACT FROM AUTHOR]

Linear programming is used in discrete tomography to solve the relaxed problem of reconstructing a function f with values in the interval [0,1]. The linear program minimizes the uniform norm Ax - 6∞ or the 1-norm ∞∞Ax - b∞∞1 of the error on the projections. We can add to this objective function a linear penalty function p(x) for trying to obtain smooth solutions. The same approach can be used in computerized tomography. The question is if it can provide better images than the classical methods of computerized tomography. The aim of this chapter is to provide a tentative answer. We present a preliminary study on real acquisitions from a phantom and provide reconstructions from a few projections, with qualities similar to the traditional methods. [ABSTRACT FROM AUTHOR]

We study the reconstruction of special lattice sets from X-rays when some convexity constraints are imposed on the sets. Two aspects are relevant for a satisfactory reconstruction: the unique determination of the set by its X-rays and the existence of a polynomial-time algorithm reconstructing the set from its X-rays. For this purpose we present the notion of Q-convex lattice sets for which there are unique determination by X-rays in suitable directions, and a polynomial-time reconstruction algorithm. After discussing these results, we show that many reconstructions of sets with convexity and connectivity constraints can be seen as particular cases of the algorithm reconstructing Q-convex lattice sets. [ABSTRACT FROM AUTHOR]

Three problems of emission discrete tomography (EDT) are presented. The first problem is the reconstruction of measurable plane sets from two absorbed projections. It is shown that Lorentz theorems can be generalized to this case. The second is the reconstruction of binary matrices from their absorbed row and columns sums if the absorption coefficient is μ0 = log((1+v/5)/2). It is proved that the reconstruction in this case can be done in polynomial time. Finally, a possible application of EDT in single photon emission computed tomography (SPECT) is presented: Dynamic structures are reconstructed after factor analysis. [ABSTRACT FROM AUTHOR]

Our aim is to produce a tessellation of space into small voxels and, based on only a few tomographic projections of an object, assign to each voxel a label that indicates one of the components of interest constituting the object. Examples of application are in the areas of electron microscopy, industrial nondestructive testing, cardiac imaging, etc. Current approaches first reconstruct the density distribution from the projections and then segment (label) this distribution. We instead postulate a low-level prior knowledge regarding the underlying distribution of label images and then directly estimate the label image based on the prior and the projections. In particular, we show, in the binary (i.e., two labels) case, that the marginal posterior mode estimator outperforms the widely known maximum a posteriori probability estimator. As measured by label misclassification in the reconstructions, our direct labeling method was experimentally proved (in the binary case) to be superior to current approaches. However, when a detectability measure was used, its relative performance was less satisfactory. We discuss possible improvements. [ABSTRACT FROM AUTHOR]

We present an approach to binary tomography by variational reconstruction and difference-of-convex-functions (DC) programming. Because we use a standard functional comprising a reconstruction error and a smoothness prior, the integer conditions are relaxed to convex box constraints. Complementing the functional with a concave penalty term allows a gradual enforcement of binary solutions. A DC-programming approach leads to an iterative reconstruction algorithm that is also applicable to large-scale problems. We show that hidden parameters, which model uncertainties of the imaging process, can be estimated as part of the variational reconstruction. Besides presenting a concise overview over recent results, we also include novel results concerning the optimization performance of our approach. [ABSTRACT FROM AUTHOR]

A convex programming approach to discrete tomographic image reconstruction in noisy environments is proposed. Conventional constraints are mixed with noise-based constraints on the sinogram and a binariness-promoting total variation constraint. The noise-based constraints are modeled as confidence regions that are constructed under a Poisson noise assumption. A convex objective is then minimized over the resulting feasibility set via a parallel block-iterative method. Applications to binary tomographic reconstruction are demonstrated. [ABSTRACT FROM AUTHOR]

The industrial nondestructive testing (NDT) of objects seems to be an ideal application of discrete tomography. In many cases, the objects consist of known materials, and a lot of a priori information is available (e.g., the description of an ideal object, which is similar to the actual one under investigation). One of the frequently used methods in NDT is to take projection images of the objects by some transmitting ray (e.g., X- or neutron-ray) and reconstruct the cross sections. But it can happen that only a few number of projections can be collected, because of long and/or expensive data acquisition, or the projections can be collected only from a limited range of directions. The chapter describes two DT reconstruction methods used in NDT experiments, shows the results of a DT procedure applied in the reconstruction of oblong objects having projections only from a limited range of angles, and, finally, suggests a few further possible NDT applications of DT. [ABSTRACT FROM AUTHOR]

The determination of crystalline structures is a demanding and fundamental task of crystallography. Most crystalline materials, natural or artificial, are in fact polycrystals, composed of tiny crystals called grains. Every grain has an associated average orientation that determines the spatial configuration of the crystalline lattice. Typically, the structure of a polycrystal is rendered via an orientation map or a grain map, in which individual pixels/voxels are assigned a grain orientation or a grain label. We present two related approaches to reconstructing a 2D grain map of a polycrystal from X-ray diffraction patterns. The first technique makes the assumption that each grain is actually a perfect crystal, i.e., that the specimen is not deformed. The other method can be applied also when the sample has been exposed to moderate levels of deformation. In both cases, the grain map is produced by a Bayesian discrete tomographic algorithm that uses Gibbs priors. The optimization of the objective function is accomplished via the Metropolis algorithm. The efficacy of the techniques is demonstrated by simulation experiments. [ABSTRACT FROM AUTHOR]

We are concerned with binary matrix reconstruction from their orthogonal projections. To the basic problem we add new kinds of constraints. In the first problems we study the ones of the matrix must be isolated: All the neighbors of a one must be a zero. Several types of neighborhoods are studied. In our second problem, every one has to be horizontally not isolated. Moreover, the number of successive zeros in a horizontal rank must be bounded by a fixed parameter. Complexity results and polynomial-time algorithms are given. [ABSTRACT FROM AUTHOR]

In this chapter we deal with the question of when an n-dimensional binary matrix is uniquely determined by its 1-marginals and with the related notion of (0, 1)-additivity. We present a survey of known results; several of them have been considered before only in dimensions 2 and 3. Here, we show how to extend them to any dimension. The main results are characterizations of uniqueness and (0,1) additivity: one, of algebraic nature, involves matrices with integer entries; the other, of geometric nature, uses transportation polytopes and permutohedra. [ABSTRACT FROM AUTHOR]

In this chapter we present an algebraic theory of patterns that can be applied in discrete tomography for any dimension. We use that the difference of two such patterns yields a configuration with vanishing line sums. We show by introducing generating polynomials and applying elementary properties of polynomials that such so-called switching configurations form a linear space. We give a basis of this linear space in terms of the so-called switching atom, the smallest nontrivial switching configuration. We do so both in case that the material does not absorb light and absorbs light homogeneously. In the former case we also show that a configuration can be constructed with the same line sums as the original and with entries of about the same size, and we provide a formula for the number of linear dependencies between the line sums. In the final section we deal with the case that the transmitted light does not follow straight lines. [ABSTRACT FROM AUTHOR]

The reconstruction of discrete sets from their projections is a frequently studied field in discrete tomography with applications in electron microscopy, image processing, radiology, and so on. Several efficient reconstruction algorithms have been developed for certain classes of discrete sets having some good geometrical properties. On the other hand, it has been shown that the reconstruction under certain circumstances can be very time-consuming, even NP-hard. In this chapter we show how prior information that the set to be reconstructed consists of several components can be exploited in order to facilitate the reconstruction. We present some general techniques to decompose a discrete set into components knowing only its projections and thus reduce the reconstruction of a general discrete set to the reconstruction of single components, which is usually a simpler task. [ABSTRACT FROM AUTHOR]

A discrete point X-ray of a finite subset F of Rn at a point p gives the number of points in F lying on each line passing through p. We survey the known results on discrete point X-rays, which mostly concern uniqueness issues for subsets of the integer lattice. [ABSTRACT FROM AUTHOR]

Consider the class AP(R, S) of (0, 1)-matrices with row sum vector R, column sum vector S, and zeros in all positions outside a certain set P. It is assumed that P satisfies a certain monotonicity property. We show the existence of a canonical matrix in this matrix class and give a simple algorithm for finding this matrix. Moreover, a classical interchange result of Ryser is generalized to the class AP(R, S) and the uniqueness question for the class AP(R, S) is discussed. [ABSTRACT FROM AUTHOR]

This chapter discusses the excellent progress made in discrete tomography (DT) during the last seven years and includes a comprehensive bibliography illustrating this progress. It also presents some of the fundamental definitions relevant to DT. [ABSTRACT FROM AUTHOR]

High-level structural information about macromolecules is now being organized into databases. One of the common ways of storing information in such databases is in the form of three-dimensional (3D) electron microscopic (EM) maps, which are 3D arrays of real numbers obtained by a reconstruction algorithm from EM projection data. We propose and demonstrate a method of automatically constructing, from any 3D EM map, a topological descriptor (which we call a history tree) that is amenable to automatic comparison. Keywords: Discrete shape representation, digital topology, macromolecular structures, volume images. [ABSTRACT FROM AUTHOR]

Digital image segmentation is the process of assigning distinct labels to different objects in an image. The level of detail indicated by the labeling is related to the application at hand. To perform object identification in digital or continuous, moving or still images, humans make use of high-level reasoning and knowledge, as well as of different visual cues, such as shadowing, occlusion, parallax motion, and the relative size of objects. Aside from the difficulty of inserting this type of reasoning into a computer program, the task of segmenting out an object from its background in an image becomes particularly hard for a computer when, instead of the brightness values, what distinguishes the object from the background is some textural property, or when the image is corrupted by noise and/or inhomogeneos illumination. [ABSTRACT FROM AUTHOR]