Algorithms for Tomography

Inverse Problems and Scientific Computing

A research activity at IMM's Section for Scientific Computing

Tomography is the science of "seeing through objects." Physical signals - waves, particles, currents - are sent through an object from many different angles, the response of the object to the signal is measured, and an image of the object's interior is reconstructed. Tomography is behind some of the most important and profound scientific discoveries of all times: The internal structure and processes of the Earth, Moon and Sun and the first maps showing the location of simple mental processes in the human brain are notable examples.

       
Medical tomography. Left: the principle - we measure the damping of rays that penetrate the object. Middle: a typical medical scanner. Right: a typical medical scanning image

Ill conditioning. Tomographic imaging is an inverse problem, which means that no matter how the problem is formulated it involves the computation of solutions that are extremely sensitive to data errors, model errors, and rounding errors. Consequently the discretized problems are effectively underdetermined (no matter how many measurements are available), the solutions are ambigous, and we face computational problems that are severely ill conditioned. Useful reconstructions can only be computed by incorporating prior information in order to define unique, stable, and physically meaningful solutions.

Prior information. The prior information about the solution, to be used in a reconstruction method, can take many forms and can be specified in many ways, and it can represent both theoretical and empirical knowledge about the reconstruction in order to dramatically reduce the dimension and complexity of the solution space. Requirements to the smoothness of the reconstruction play an important role in many classical variational methods, and statistical priors about the data and the solution are the fundamental ingredients of Bayesian methods.


Depth profiling. X-rays are sent into an object, say, layers of paing in an image, where they are are partially reflected according to a characteristic material parameter (this technique is known as PIXE). In the above figures, the blue lines are TSVD reconstrunstructions of the true material parameter (red line) for three different truncation (regularization) parameters.

Algorithm Development

We develop computational algorithms for a variety of tomography applications in geophysics, materials science, etc. Our algorithms are targeted to large-scale problems and we seek to incorporate prior information in the best possible way.

Iterative algorithms. Among our activities are iterative regularization methods based on semi-convergence, i.e., the fact that the number of iterations in an iterative (least squares) solver plays the role of a regularization parameter. We also develop subspace or smoothing preconditioners for these iterative methods, that improve the quality of the reconstructions by modifying the signal subspace for the solution. Some recent references:


Tomography in materials science. Reconstruction of an orientation distribution function from X-ray scattering data. Left: the original. Middle: the best reconstruction without preconditioner, with severe noise near the boundaries. Right: the optimal reconstruction with a smoothing preconditioner that also enforces zero boundary conditions.

Inverse models and geostatistics. Other activities include algorithms based on combinations of geostatistics and inverse problem theory, leading to more accurate reconstructions, e.g., in ground water models and oil/gas exploration. Some recent references:

           
Multiple scenario generation. Left: a training image. Right: three posterior realizations using the training image as prior model.

Electrical Impedance Tomography (joint with DTU Mathematics). In electrical impedance tomography we reconstruct the electrical conductivity of an object from measurements of the voltage-to-current map on the surface of the object. This has applications in industrial inspection, medical cadiology, etc. We develop large-scale algorithms based on scattering transforms and solving a boundary integral equation for the complex geometricl optics solutions, and the method is implemented using a Nyström method. Some recent references:


Slices of a 3D phantom reconstruction. The reconstructions are computed by means of three different EIT algorithms based on scattering transforms.

Inverse Problems

Tomography problems belong to a general class of mathematical problems known as inverse problems. These problems generally arise when we wish to compute information about internal or otherwise hidden data from outside (or otherwise accessible) measurements. Inverse problems are ill posed meaning that they violate one or more of Hadamard's requirements for a problem to be well posed:

  • Existence. The problem must have a solution.
  • Uniqueness. There must be only one solution to the problem.
  • Stability. The solution must depend continuously on the data.

The difficulties with existence and/or uniqueness are usually dealt with by reformulations of the solution, e.g., by replacing "exact solution" with "least squares solution" or "minimum-norm solution."

The difficulties with stability, on the other hand, requires the development of regularization methods that enforce additional stability or regularity on the computed solution. Among these methods are Tikhonov regularization, truncated SVD, Wiener filtering, mollifier methods, and various iterative methods. The main goal of these methods is to incorporate additional (prior) information about the reconstruction into the solution process.
Selected works on inverse problems:
Color image deblurring. Left: blurred image with cross-channel mixing. Middle: a Gaussian prior for the spatial correlation gives "freckles" artefacts and blurred edges. Right: a Laplacian prior gives sharp edges and no "freckles."

Research Projects and Collaborations

Software Packages