Multilevel Image Reconstruction with Natural Pixels

Van Emden Henson
Department of Mathematics
Naval Postgraduate School
Monterrey, CA

Mark A. Limber
Auto-trol Technology Corporation
Denver, CO.

Stephen F. McCormick
Program in Applied Mathematics
Campus Box 526
University of Colorado at Boulder
Boulder, CO 80309-0526

Bruce T. Robinson
Accurate Information Systems
Eatontown, NJ


The sampled Radon transform of a 2D function can be represented as a continuous linear map A:L2(W)--> RN, where (Au)j = < u, pj> and pj is the characteristic function of a strip through W approximating the set of line integrals in the sample. The image reconstruction problem is: given a vector b in RN, find an image (or density function) u(x,y) such that Au=b. In general there are infinitely many solutions; we seek the solution with minimal 2-norm, which leads to a matrix equation Bw=b, where B is a square dense matrix with several convenient properties. We analyze the use of Gauss-Seidel iteration applied to the problem, observing that while the iteration formally converges, there exists a near null space into which the error vectors migrate, after which the iteration stalls. The null space and near null space of B are characterized in order to develop a multilevel scheme. Based on the principles of the Multilevel Projection Method (PML), this scheme leads to somewhat improved performance. Its primary utility, however, is that it facilitates the development of a PML-based method for spotlight tomography, that is, local grid refinement over a portion of the image in which features of interest can be resolved at finer scale than is possible globally.