A. Brandt Department of Applied Math. and Computer Science, Weizmann Institute, Rehovot, 96100, Israel
The Radon Transform measures a property of a two dimensional image along all one dimensional rays in many different angles. This information is then used to reconstruct the two dimensional image (which is not directly accesible). Examples of applications include X-ray tomography, where the interior structure of a two-dimensional slice of a patient (or any other object under study) can be divined by measuring the absorption properties through the slice at many different angles. Another example is in SAR surface imaging. The algorithm we describe here can be used for these applications, but can also be generalized to invert transforms for which no algorithm currently exists. An algorithm which can (among other things) compute the Radon Transform very efficiently (all rays in all directions are computed in O(nlogn) operations, with n the number of pixels in the image) is presented in . This algorithm is at the heart of the inversion algorithm presented here. It performs the computation recursively, first building very short `partial rays' then combining them into longer (double length) pieces until finally the full set of all rays is computed. The inversion algorithm reverses this process. Starting with the complete set of rays, the `partial rays' of half the length are solved for. These, in turn, are used to solved for the `partial rays' of one-quarter length, and so on. The rays of minimal length (2, in our implementation) are used to reconstruct the image. An FMG type algorithm is used to accelerate the reconstruction. The original Radon Transform is `coarsened' to the point where it repesents a Transform of a two by two (coarse) image. This image is then interpolated to a finer (four by four) image, from which the `partial rays' of length two are computed. These serve as an initial guess for the next stage, which uses a finer version of the coarsened Radon Transform, and which results in a four by four image, which, in turn, is interpolated to provide the initial values for the next stage. 1. A. Brandt and J. Dym, ``Fast Calculation of Multiple Line Integrals", to appear in SIAM Jour. on Sci. Comp.