Abstract
An algorithm is presented for estimating the density distribution in a cross section of an object from X-ray data, which in practice is unavoidably noisy. The data give rise to a large sparse system of inconsistent equations, not untypically 105 equations with 104 unknowns, with only about 1% of the coefficients non-zero. Using the physical interpretation of the equations, each equality can in principle be replaced by a pair of inequalities, giving us the limits within which we believe the sum must lie. An algorithm is proposed for solving this set of inequalities. The algorithm is basically a relaxation method. A finite convergence result is proved. In spite of the large size of the system, in the application area of interest practical solution on a computer is possible because of the simple geometry of the problem and the redundancy of equations obtained from nearby X-rays. The algorithm has been implemented, and is demonstrated by actual reconstructions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R.N. Bracewell, “Strip integration in radio astronomy”,Australian Journal of Physics 9 (1956) 198–217.
R.N. Bracewell and A.C. Riddle, “Inversion of fanbeam scans in radio astronomy”,Astrophysical Journal 150 (1967) 427–434.
A.M. Cormack, “Representation of a function by its line integrals, with some radiological applications”,Journal of Applied Physics 34 (1963) 2722–2727.
D.J. DeRosier and A. Klug, “Reconstruction of three-dimensional structures from electron micrographs”,Nature 217 (1968) 130–134.
G. Frieder and G.T. Herman, “Resolution in reconstructing objects from electron micrographs”,Journal of Theoretical Biology 33 (1971) 189–211.
N.T. Gaarder and G.T. Herman, “Algorithms for reproducing objects from their X-rays”,Computer Graphics and Image Processing 1 (1972) 97–106.
P.F.C. Gilbert, “Iterative methods for the reconstruction of three-dimensional objects from projections”,Journal of Theoretical Biology 36 (1972) 105–117.
J.L. Goffin, “On the finite convergence of the relaxation method for solving systems of inequalities”, Ph.D. thesis, University of California, Berkeley (1971).
R. Gordon, R. Bender and G.T. Herman, “Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and x-ray photography”,Journal of Theoretical Biology 29 (1970) 471–481.
R. Gordon and G.T. Herman, “Three dimensional reconstruction from projections: a review of algorithms”, in: G.F. Bourne and J.F. Danielli, eds.,International review of cytology (Academic Press, New York, 1974) pp. 111–151.
J.F. Greenleaf, S.A. Johnson, S.L. Lee, G.T. Herman and E.H. Wood, “Algebraic reconstruction of spatial distributions of acoustic absorption within tissue from their two-dimensional acoustic projections”, in: P.S. Green, ed.,Acoustical holography and imaging (Plenum Press, New York, 1973) pp. 591–603.
G.T. Herman, “Two direct methods for reconstructing pictures from their projections: a comparative study”,Computer Graphics and Image Processing 1 (1972) 123–144.
G.T. Herman, “Reconstruction of binary patterns from a few projections”, in: A. Gunther, B. Levrat and H. Lipps, eds.,International computing symposium 1973 (North-Holland, Amsterdam, 1973) pp. 371–380.
G.T. Herman, A. Lent and S. Rowland, “ART: Mathematics and applications (a report on the mathematical foundations and on the applicability to real data of the Algebraic Reconstruction Techniques)”,Journal of Theoretical Biology 42 (1973) 1–32.
G.T. Herman and S. Rowland, “Three methods for reconstructing objects from x-rays: a comparative study”,Computer Graphics and Image Processing 2 (1973) 151–178.
S.A. Johnson, R.A. Robb, J.F. Greenleaf, E.L. Ritman, G.T. Herman, S.L. Lee and E.H. Wood, “Temporal and spatial x-ray projective reconstruction of a beating heart”,Mayo Clinic Proceedings, to appear.
S.A. Johnson, R.A. Robb, J.F. Greenleaf, E.L. Ritman, S.L. Lee, G.T. Herman, R.E. Sturm and E.H. Wood, “The problem of accurate measurement of left ventricular shape and dimensions from multiplane Roentgenographic data”,European Journal of Cardiology 1 (1973) 137–154.
T.S. Motzkin and I.J. Schoenberg, “The relaxation method for linear inequalities”,Canadian Journal of Mathematics 6 (1954) 393–404.
J. Radon, “Über die Bestimmung von Funktionen durch ihre Integralwerte längs gewisser Mannigfaltigkeiten”,Berichte Sächsische Akademie der Wissenschaften (Leipzig) Mathematische-Physische Klasse 69 (1917) 262–277.
G.N. Ramachandran and A.V. Lakshminarayanan, “Three-dimensional reconstruction from radiographs and electron micrographs: application of convolutions instead of Fourier transforms”,Proceedings of the National Academy of Sciences USA 68 (1971) 2236–2240.
R.A. Robb, J.F. Greenleaf, E.L. Ritman, S.A. Johnson, J. Sjostrand, G.T. Herman and E.H. Wood, “Three-dimensional visualization of the intact thorax and contents: A technique for cross-section reconstruction from multiplanar x-ray views”,Computers and Biomedical Research 7 (1974) 395–419.
D. Sweeney, “Interferometric measurement of three-dimensional temperature fields”, Ph. D. Thesis, University of Michigan, Ann Arbor, Mich. (1972).
Author information
Authors and Affiliations
Additional information
This research has been supported by N.S.F. Grant G.J. 998.
Rights and permissions
About this article
Cite this article
Herman, G.T. A relaxation method for reconstructing objects from noisy X-rays. Mathematical Programming 8, 1–19 (1975). https://doi.org/10.1007/BF01580425
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01580425