Saving lives: the mathematics of tomographyIssue 47
Inverting and calculating the Radon transform using the Fourier transform
You might also want to listen to our podcast on the Fourier transform.
This section is much more mathematically sophisticated than the main article. Most of the mathematics is at university level. If you want to look at examples of how tomography is used in practice, return to the main article. However, if you are feeling brave, then read on as this section contains some really lovely mathematical ideas.
One of the most useful mathematical techniques ever invented is called the Fourier transform. To motivate this, imagine that you are listening to a concert, and that you record the intensity of the sound of the orchestra as a function of the time . The orchestra is composed of instruments that all make sounds of a frequency with each such sound having an intensity . A sound of frequency has the mathematical expression
The reason is that it links the intensity of a function to the waves that make it up, and as so much of what we do involves sound or light waves, its applications are universal. It is so important that calculating the Fourier transform was one of the first tasks given to the early computers in use in the 1960s. However, these implementations had a lot of difficulties in calculating the Fourier transform and were so slow that they were absorbing a huge amount of computing time. Roughly speaking, if you wanted to find the values of the Fourier transform at points, you had to do calculations. Unfortunately for accuracy you have to take large values of , which means that is very large indeed; too large to be calculated easily.
However, in 1965 there was a remarkable breakthrough when a technique called the fast Fourier transform, or FFT was invented. This was much faster, taking a time proportional to , which is a lot smaller than . With the FFT available to calculate the Fourier transform quickly, its applications became almost unlimited. One application, of great importance to us, is the way in which it can be used to analyse images. A typical image is represented by pixels, with a pixel at the point having intensity . Just as music is characterised by waves of different frequencies, so an image can be characterised by repeating patterns - "waves" - in the two directions and , with repetition frequency and respectively. The Fourier transform of such an image is then given by the double-integral
To find this link we need to fix and find the Fourier transform of the Radon transform. This is given by
There are many ways that we can use this formula. Firstly, it gives us a quick way to calculate the Radon transform of the function . Of course, in medical imaging the Radon transform is "calculated" automatically by measuring the attenuation of the X-rays through the body. However, in other applications, such as the detection of land-mines described later on in the main article, it is vital to calculate the Radon transform as quickly as possible. We can do this by using a combination of the FFT and the Fourier slice theorem as follows:
- Calculate the Fourier transform of using the FFT;
- Set and use the FFT to calculate the inverse Fourier transform of the function to find .
As each stage of this method uses the FFT, it is a lot quicker than calculating R directly by solving a lot of integrals.
The second important application is that the Fourier slice theorem gives us a way of inverting the Radon transform, so that we can find the function if we know . In particular, substituting the formula for the inverse Fourier transform into the Fourier slice theorem and applying a change of variable formula we obtain
Well, not quite. Like all inverse problems in tomography and other applications, the formula only works well if we know very accurately and there is not too much noise in the results. Furthermore, there is quite a lot of work to do in calculating all of the terms in this integral, and errors can accumulate quite easily. In practice, this formula can be a bit unstable, and it is hard to implement accurately. However, it gives the basis for all other formulae used to find from . Indeed, one way to interpret the inversion formula is to note that