Iterative relaxation methods for image reconstruction

ABSTRACT

The problem of recovering an image (a function of two variables) from experimentally available integrals of its grayness over thin strips is of great importance in a large number of scientific areas. An important version of the problem in medicine is that of obtaining the exact density distribution within the human body from X-ray projections. One approach that has been taken to solve this problem consists of translating the available information into a system of linear inequalities. The size and the sparsity of the resulting system of inequalities (typically, 25,000 inequalities with less than 1% of the coefficients nonzero) makes methods using successive relaxations computationally attractive. A variety of such methods have been proposed with differing relaxation parameters.

REFERENCES

• 1: S. Agmon, The relaxation method for linear inequalities, Can. J. Math., 6, 382-392, 1954.
• 2: D. Boyd, J. Coonrod, J. Dehnert, D. Chu, C. Lim, B. Macdonald and V. Perez-Mendez, A high pressure Xenon proportional chamber for X-ray laminographic reconstruction using fan beam geometry, IEEE Trans. Nuc. Sc., v. 21, no. 1, 184-187,Feb. 1974.
• 3: R.N. Bracewell and A.C. Riddle, Inversion of fan-beam scans in radio astronomy, The Astrophysical J., v. 150, 427-434, Nov. 1967.
• 4: R. Gordon, R. Bender and G.T. Herman, Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography, J. Theor. Biol., v. 29, 471-481, 1970.
• 5: G.T. Herman, A relaxation method for reconstructing objects from noisy X-rays, Mathematical Programming, v. 8, 1-19, 1975.
• 6: G.T. Herman, A.V. Lakshminarayanan and S.W. Rowland, The reconstruction of objects from shadowgraphs with high contrasts, Pattern Recognition, to appear.
• 7: G.T. Herman, A. Lent and S.W. Rowland, ART: Mathematics and Applications. A report on the mathematical foundations and on the applicability to real data of the algebraic reconstruction techniques, J. Theor. Biol., v. 42, 1-32, 1973.
• 8: G.T. Herman and S.W. Rowland, Three methods for reconstructing objects from X-rays: a comparative study, Comp. Graphics and Image Proc., v. 2, 151-178, 1973.
• 9: G.N. Ramachandran and A.V. Lakshminarayanan, Three-dimensional reconstruction from radiographs and electron micrographs: application of convolutions instead of Fourier transforms, Proc. Nat. Acad. Sci. U.S.A., v. 68, no. 9, 2236-2240, 1971.
• 10: L.A. Sheep and B.F. Logan, The Fourier reconstruction of a head section, IEEE Trans. Nuc. Sci., v. 21, no. 3, 21-43, June 1974.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.5 Reconstruction

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming

General Terms:
Design, Languages, Management