Algorithms

Until the beginning of this century, the mathematical community produced almost no algorithms that served the purpose of geometric tomography. Some algorithms of this type were developed in a program run mainly in the 1980's and 1990's by the electrical engineer Alan Willsky. During the last decade, however, several geometric tomography algorithms have been proposed by mathematicians. Several of these fit into the following general approach:

(i) For any particular type of data, take measurements of an unknown set \(K\) in a class \(\mathcal{E}\) of sets in R\(^n\) in a situation for which a full set of exact data determines \(K\) uniquely among all the sets in \(\mathcal{E}\). The measurements should however be realistic: There are available only finitely many noisy measurements, i.e., measurements taken with errors, modeled by the addition of independent random variables with zero mean and fixed variance \(\sigma^2\).

(ii) The task is to design an algorithm that takes \(k\) noisy measurements as input and outputs a set \(P_k\) that approximates \(K\).

(iii) The algorithm should come with a proof of convergence that under suitable, hopefully weak, assumptions, for each fixed \(\sigma\) the distance from \(P_k\) to \(K\) converges to 0, almost surely, as \(k\rightarrow\infty\), in an appropriate metric. If possible, rates of convergence should be obtained.

(iv) The algorithm should be implemented and tested.

Some examples of such algorithms are listed below. They can be tried out by clicking on the corresponding button at the right of the main Geometric Tomography page.

Reconstruction from X-rays. The reconstruction aspect of Hammer's X-ray problem is solved by Gardner and Kiderlen [11]. Here, algorithms are given for reconstructing a planar convex body \(K\) from possibly noisy measurements of either its parallel X-rays taken in a fixed finite set of directions or its point X-rays taken at a fixed finite set of points, in known situations that guarantee a unique solution when the data is exact. The algorithms construct a convex polygon \(P_k\) whose X-rays approximate (in the least squares sense) \(k\) equally spaced noisy X-ray measurements of \(K\) in each of the directions or at each of the points. It is shown that these procedures are strongly consistent, meaning that, almost surely, \(P_k\) tends to \(K\) in the Hausdorff metric as \(k\to\infty\).

Reconstruction from brightness functions. Aleksandrov's projection theorem [9, Theorem 3.3.1] states that an origin-symmetric convex body \(K\) in R\(^n\) is uniquely determined, among all such bodies, by its brightness function. Aleksandrov proved this remarkable result - which assumes nothing is known about the shape of the shadows of \(K\), only their areas - in 1937, developing a good deal of the machinery of modern convex geometry in the process. But the theorem does not help with the task of actually reconstructing an origin-symmetric convex body from its brightness function.

Gardner and Milanfar [16], [17] employ a two-stage procedure to effect the reconstruction. By inverting the cosine transform, the first stage reconstructs the surface area measure of \(K\) from its brightness function. The second stage then reconstructs \(K\) from its surface area measure. Suppose that \((u_i)\) is a sequence of directions dense in \(S^{n-1}\). The algorithm takes as input the brightness function values of \(K\) in the directions \(u_1,\dots,u_k\) and outputs a convex polytope \(P_k\) such that \(P_k\) converges to \(K\) in the Hausdorff metric as \(k\rightarrow\infty\). Though the theoretical results in [17] require exact data, the implemented algorithms already work with noisy data. Gardner, Kiderlen, and Milanfar [13] show that under a weak extra assumption on the sequence \((u_i)\), \(P_k\) still converges, almost surely, to \(K\) as \(k\rightarrow\infty\), even providing bounds for rates of convergence.

Reconstruction from support functions. The support function of a convex body \(K\) in R\(^n\) gives for each direction \(u\in S^{n-1}\) the signed distance from \(o\) to the supporting (tangent) hyperplane to \(K\) orthogonal to \(u\). One of the first algorithms arising from Willsky's program was one proposed by Prince and Willsky [31] that reconstructs an approximation to an unknown planar convex body \(K\) from noisy measurements of its support function. There is a very wide multi-disciplinary interest in reconstruction from support functions. See [13] for a long list of references detailing applications to computer tomography, target reconstruction from laser-radar data, and projection magnetic resonance imaging. In view of this, it is surprising that the first convergence proof for the Prince-Willsky algorithm was obtained by Gardner, Kiderlen, and Milanfar [13]. This proof also works for the natural extension of the Prince-Willsky algorithm to higher dimensions.

The approach taken by Prince and Willsky encounters obstacles in higher dimensions due to the difficulty in implementing the constraint in their least-squares problem. Gardner and Kiderlen [12] resolve this by a change of variable and develop the first fully satisfactory algorithm for reconstructing 3-dimensional (or higher-dimensional) convex bodies from their support functions.

Reconstruction from covariograms. The covariogram of a convex body \(K\) in R\(^n\) is the function \(g_K\) defined by \(g_K(x)=V_n\left(K\cap (K+x)\right)\), for \(x\in \)R\(^n\), where \(K+x\) is the translate of \(K\) by the vector \(x\). In short, it gives the volumes of the intersections of \(K\) with its translates. It was introduced around 1975 by G. Matheron , who showed that for a fixed \(u\in S^{n-1}\), the directional derivatives \(\partial g_K(tu)/\partial t\), for all \(t>0\), yield the distribution of the lengths of all chords of \(K\) parallel to \(u\). This explains its relevance to geometric tomography and its utility in fields such as stereology, pattern recognition, and mathematical morphology, where information about an unknown object is to be retrieved from chord length measurements. The covariogram is also important in analytic convex geometry.

Simple to define, the covariogram is notoriously difficult to work with. In 1986, Matheron himself conjectured that planar convex bodies are determined (for the covariogram, the term will always mean up to translation and reflection in the origin) by their covariograms, but this was only recently confirmed by Averkov and Bianchi [1]. Bianchi [2], [3] proved that three-dimensional convex polytopes are determined by their covariograms but in general higher-dimensional ones are not. The uniqueness problem is still open for convex bodies in R\(^3\).

Bianchi, Gardner, and Kiderlen [4] describe an algorithm for reconstructing convex bodies from their covariograms. The proof of convergence is difficult, depending both on the earlier proof for brightness function reconstruction and new arguments.