These notes are based on Gunther Uhlmann’s lectures for MATH 581 taught at the University of Washington in Autumn 2009.
An index to all of the notes is available here.
The X-Ray transform is particularly interesting because we can use it for tomography. We can send X-Rays through a patient, over many different lines, and measure the accumulated attentuation. Once this is done, we know the X-Ray transform of our object, so we can simply pass this in to the inversion formula and reconstruct a three-dimensional model. There are two substantial problems with this:
- We cannot collect data for every line, we can only sample a finite number of lines.
- Our measurements will have error.
There are in fact even more complications — beam hardening comes to mind — but these two must be dealt with first. Loosely speaking, the solution to the first problem relies on the stability estimates for the X-Ray Transform, and the solution to the second problem depends on the range characterization. In this post we will discuss the first problem, finite sample size, in detail. The second problem is manageable too: the range characterization of the X-Ray Transform lets us find the image function most likely to have produced the error-filled data. It turns out that the filtered backprojection algorithm we introduce below is an important step in this process. The rest of this post is organized as follows: we will start by showing that for an infinite, discrete set of samples we have unique reconstruction. Then we will consider finite sets of samples and see that reconstruction is hopeless without a priori assumptions. From there we will introduce the Filtered Backprojection algorithm and state and Natterer’s theorem about filtered backprojection error estimates.
1. Unique reconstruction for infinite, semi-discrete sample sets
In a practical tomography problem, we are not given the entire X-Ray Transform of a function, instead we just have
for some and , , . Our first result is a bit of good news: even with discrete angular samples we can get a unique reconstruction (at least for distributions with compact support).
Theorem 1 For , if
for an infinite number of , then .
for all and for all . The set has an accumulation point, call it , where we must have in . For we can also find a sequence such that . Since , all derivatives in the direction are zero:
But is identically zero on too, so all of its directional derivatives vanish at . Since has compact support, Paley-Wiener implies that is analytic. An analytic function in several variables whose derivatives all vanish must be identically zero. So , and hence , is zero.
2. Reconstruction is impossible for finite sample sets
If the result in the last section gave us some hope, the theorem we see in this section should disillusion us. It turns out that when we have only a finite number of samples, not only is the reconstruction non-unique (which is clear), but it can be horrendously bad. Behavior on the margins of arbitrary data of interest can cause all of our observed values to vanish.
Theorem 2 (Finite number of X-rays) Let have compact closure and a nonempty interior. Let and Consider a finite number of directions, given by where . Then there exists an and such that on the interior of and
for all .
Proof: We will start with a direct proof of the case of a single line, . We want to construct an that has . Using the Fourier Slice Theorem, we see that need to construct with
To make sure we have this property, we will construct so that
Let’s start by looking at a concrete case, and take . Now we want
But this happens exactly when
where . This suggests that if we can solve the differential equation
on the interior of then we will be done. (Exercise: why can we ignore the constant term?) To do this, let with on the interior of . Then we want to solve the equation
which can be solved by integrating along the direction. Now we can just choose
to complete the proof. For general , use the same approach to solve
General case, . The extension to larger is straightforward. Now we want to find an such that
To do this, we solve
Which we can do by integrating times. Now take
to complete the proof.
So we cannot reconstruct a function from a finite sample of its X-Ray Transform without a priori assumptions. So let’s make those assumptions and reconstruct.
3. Filtered Back-projection
We want to reconstruct a function from a discrete set of samples of its X-Ray Transform. We will just look at the case of practical interest: . Here the X-Ray Transform is the same as the Radon Transform, and we want to compute
given data . We will do this in two steps. First we will cut off the high frequencies, then we will discretize the integrals.
3.1. Step 1: Cut off high frequencies
We start by observing that for any distribution we have the identity
where is the delta function. We can choose a band-limited approximation to the identity, where
- for all
For example, we could take . Now we will modify our goals. High frequency components cannot be sampled properly by a finite set of observations. Roughly, we cannot hope to measure angular frequencies greater than given samples. So instead of trying to reconstruct precisely, we will try to reconstruct, a band-limited approximation of . Observe
Proof: The proof uses the Fourier Transform
Proof: Again, we use the Fourier Transform.
In other words, since the Fourier Transform diagonalizes all of these operators, they commute.
3.2. Step 2: Discretize
If we can compute the quantity in Equation 1 then we are done. But
which is an integral that must be approximated. There are many ways to do this, but for our purposes the trapezoid rule will suffice. Specifically, assume that the support of is a subset of the cube . Then the support of is a subset of the cube . Let where is our discretization step size. Then we will use the following approximation
Which we will call the discretized convolution. We also need to discretize
To do this, pick and define
Putting these together, we can precisely define our reconstruction formula.
Definition 5 (Filtered Backprojection)
3.3. Bounding reconstruction errors: Natterer’s Theorem
Variants of this formula are the standard reconstruction method used in practical tomography. Now we have one pressing question: how good is it? Without making a priori assumptions about , we know we can’t hope for much. In fact Natterer has shown that under reasonable conditions we can get a lot.
Theorem 6 (Natterer) Let have support in the cube . Assume that we have observed samples as indicated above. Then
That is, the first error comes from discretization of the convolution and the second comes from the discretization of . Let , , and . Then we have pointwise estimates
Note that the estimate on is related to control of the Sobolev norm of . We will not prove this theorem here, look at Natterer’s book for details. Instead, we will spend the remaining lectures exploring helical tomography, local tomography, and other related problems. (A pdf version of these notes is available here.)