Transport Phenomena - Delft University of Technology

Research Pages Robert F. Mudde


Computed Tomography

Computed Tomography is the technique by which a slice through the object of study is made visible via multiple X-ray viewing angles. There are many algorithms for reconstructing an image from the different measured views. Some are fast but in accurate, other methods are slow but generate much sharper images. There are direct methods and iterative ones. The choice depends on what the aim of the tomographic image is and on the number of independent measurements compared to the number of pixels of the image. Generally, the higher the ratio of measured data over images pixels, the better the reconstructed image.

List of algorithms

    Direct Methods
  • Linear Back Projection
  • Single Value Decomposition
  • Tikhonov regularization>
    Iterative Methods
  • Project Landweber
  • Algebraic Reconstruction
  • Genetics
  • Genetic Algorithm

Lambert-Beer Law

The basic idea of CT is to measure over a large number of different lines or 'tubes' the transmission of X-rays. The transmission for mono-chromatic X-rays is governed by the Lambert-Beer law. It describes the X-ray intensity when a X-ray beam with intensity I0 travels through a homogeneous medium of thickness x:
   I(x) = I0 exp (- μ x )
with μ the absorption coefficient. Via a proper calibration is the measured transmission transformed into the amount of material on the measured line. For a fluidized bed, this means the amount of powder that is distributed in an unknown way on the line: only the total amount is know from the data point. A data point is usually refered to as the ray-sum.


Reconstruction Problem

All measured ray-sums needs to be coupled to the powder distribution in the imaging plain. After the transformation from measured intensity to amount of powder, a direct connection between the fraction of powder in the pixels traveled through by the x-ray and the ray-sum can be made:
   pi = Σj=1..N Wijαj
with Wij the weighing factor of the jth pixel to the ith ray. In many cases just the length of the ray through the pixel can be taken. The powder fraction in the pixel is denoted by αj. Note that here all pixels are stored as a vector with N components.

The reconstruction thus boils down to solving the above equation, which can be written in vector/matrix form.
   p = W . α
The main problem is, that the number of measured ray sums M is in many cases much smaller than the number of unknown pixel values. The inverse of W does not exist en direct inversion of the equation is not possible.

Linear Back Projection

A simple and fast algorithm to find an approximate solution to the above equation is the so-called linear back projection. Here, the inverse of W is estimated by taking its transpose WT. A disadvantage of this approach is that it excessively blurs the reconstructions.

An example of the performance of LBP is given in the figures to the right. The first figure shows the set-up: the small circle in the middle is the fluid bed with three X-ray sources around it. The red lines indicate the measuring rays from source to detectors.

The next figure shows the original 'bubbles' cut by the measuring plane: one big bubble and one small one. Also, the discretized version of the bubbles is shown: air is black, powder is white. From the discretize version, the ray-sums (i.e. measured signals) are calculated. These data are used in the LBP-reconstruction. A 45*45 grid has been used for both the discretization and the reconstruction. The result is seen in the next figure, showing that LBP produces poor images.

Algebraic Reconstruction Technique

Alternatively, images can be reconstructed using the Algebraic reconstruction Technique (ART). It uses an iterative scheme to find the best solution. In essence it tries to find the point in the multi-dimensional reconstruction space, that is closed to all hyper-planes defined by p = W . α.

It is easily explained for a 2-by-2 grid. Then the above equation can be written as
W11 α1+W12 α2=p1
W21 α1+W22 α2=p2
These two equations are two lines in a 2D-plane. Obviously, finding the solution is easy by algebraically solving these two equations to find the intersection point. However, in a multi-dimensional case, the hyper-planes do not intersect in a single point and a different approach is needed. The idea is illustrated in the figure to the right: a initial point is 'guessed'. Then from that point a projection on line one is made, from the new point a projection on line two is made, and back on line 1, etc. Finally, the intersection of the two lines is found. In the multi-dimensional case the same procedure is followed. Each time a new point is found. With this point (image) the new ray-sums are computed and compared to the measured ray-sums. This is repeated until the measured ray-sums and the computed ones are the same within a prescribed convergence criterion. The third figure in the row above shows the reconstructied image using SART (a variation on ART). It is obvious that this image is much closer to the real image than the one from LBP.

Genetic Algorithm

A completely different approach to reconstruction of the images is taken by the so-called Genetic Algorithms. The idea behind the genetic algorithms is to mimic nature and its evolution. Rather than solving a set of mathematical equations that describe the relation between the measured data and the object, it works with a large set of potential solutions that are seen as parents that have children. These children are genetic combinations of their parents with a survival of the fittest that steers the subsequent generation toward the best reconstructed image.

The image is represented by a long vector of pixel values. In the genetic algorithm such a vector is seen as a chromosome, with the pixel values representing the genes. Every new generation is formed by crossing the genes of two parents. Parents are selected based on how well they already fit the measured data: the better the fit the more likely that such a gene will be chosen as parent. To avoid trapping in a local minimum, the children undergo mutation. Strange as it may sound, this procedure will eventually arive at a good image reconstruction.

A simple example of a genetic algorithm in action can be seen on this page.