On some optimization techniques in image reconstruction from projections
Applied Numerical MathematicsPublished 1 October 1987
Yair Censor, Gábor T. Herman
Citations109
SJR quartileQ1
SJR score0.94
SNIP1.31
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Several special-purpose optimization techniques which have been recently developed as reconstruction algorithms which have revolutionized diagnostic radiology in the last decade are presented.
Abstract
Image reconstruction from projections is a procedure of extreme usefulness in many scientific and medical fields. In particular, it has revolutionized diagnostic radiology in the last decade. The mathematical essence of the procedure is the estimation and presentation of a real-valued function of several variables from approximate values of a finite number of its line integrals. In this paper we present several special-purpose optimization techniques which have been recently developed as reconstruction algorithms. The emphasis of the discussion is on recent developments and open problems.
Keywords
Computer ScienceMedicine
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
IEEE Transactions on Medical ImagingMaximum Likelihood Reconstruction for Emission Tomography
4,341 Citations1982L. A. Shepp, Y. Vardi
Journal of Theoretical BiologyAlgebraic Reconstruction Techniques (ART) for three-dimensional electron microscopy and X-ray photography
2,741 Citations1970Richard Gordon, Robert Bender +1 more
The method works for totally asymmetric objects, and requires little computer time or storage, and is also applicable to X-ray photography, and may greatly reduce the exposure compared to current methods of body-section radiography.
USSR Computational Mathematics and Mathematical PhysicsThe relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming
2,659 Citations1967L.M. Bregman
This method can be regarded as a generalization of the methods discussed in [1–4] and applied to the approximate solution of problems in linear and convex programming.
PubMedEM reconstruction algorithms for emission and transmission tomography.
1,781 Citations1984Kenneth Lange, Richard E. Carson
The general principles behind all EM algorithms are discussed and in detail the specific algorithms for emission and transmission tomography are derived and the specification of necessary physical features such as source and detector geometries are discussed.
Proceedings of the IEEEOn the rationale of maximum-entropy methods
1,648 Citations1982E. T. Jaynes
The relations between maximum-entropy (MAXENT) and other methods of spectral analysis such as the Schuster, Blackman-Tukey, maximum-likelihood, Bayesian, and Autoregressive models are discussed, emphasizing that they are not in conflict, but rather are appropriate in different problems.
Journal of Theoretical BiologyIterative methods for the three-dimensional reconstruction of an object from projections
1,369 Citations1972P.F.C. Gilbert
It is shown that in general ART produces erroneous reconstructions, and an alternative iterative method is proposed which will give correct reconstructions under certain conditions.
The Annals of Mathematical StatisticsGeneralized Iterative Scaling for Log-Linear Models
1,203 Citations1972J. N. Darroch, D. Ratcliff
Journal of the American Statistical AssociationA Statistical Model for Positron Emission Tomography
806 Citations1985Y. Vardi, L. A. Shepp +1 more
This article tailor a mathematical model to the physics of positron emissions, and it is used to describe the basic image reconstruction problem of PET as a standard problem in statistical estimation from incomplete data.
USSR Computational Mathematics and Mathematical PhysicsThe method of projections for finding the common point of convex sets
732 Citations1967L.G. Gubin, B. T. Polyak +1 more
Various methods of finding points from the intersection of sets, using projection on to a separate set as an elementary operation are considered, and the strong convergence of the sequences obtained is proved.
Springer series in information sciencesMultiresolution Image Processing and Analysis
660 Citations1984Azriel Rosenfeld
A Hierarchical Image Analysis System Based Upon Oriented Zero Crossings of Bandpassed Images and a Tutorial on Quadtree Research.
Canadian Journal of MathematicsThe Relaxation Method for Linear Inequalities
560 Citations1954Shmuel Agmon
Journal of Optimization Theory and ApplicationsAn iterative row-action method for interval convex programming
502 Citations1981Yair Censor, Arnold Lent
The iterative primal-dual method of Bregman for solving linearly constrained convex programming problems, which utilizes nonorthogonal projections onto hyperplanes, is represented in a compact form, and a complete proof of convergence is given for an almost cyclic control of the method.
SIAM ReviewRow-Action Methods for Huge and Sparse Systems and Their Applications
480 Citations1981Yair Censor
Canadian Journal of MathematicsThe Relaxation Method for Linear Inequalities
465 Citations1954T. S. Motzkin, I. J. Schoenberg
Computers in Biology and MedicineIterative reconstruction algorithms
452 Citations1976Gábor T. Herman, Arnold Lent
A set of optimization criteria and a number of iterative reconstruction algorithms are stated, together with theorems on the convergence of the algorithms to optimum images and the efficacy of the algorithm is compared to that of the convolution method.
Numerische MathematikProjection method for solving a singular system of linear equations and its applications
444 Citations1971Kunio Tanabe
Proceedings of the IEEEFinite series-expansion reconstruction methods
437 Citations1983Yair Censor
These methods are based on the discretization of the image domain prior to any mathematical analysis and thus are rooted in a completely different branch of mathematics than the transform methods which are discussed in this issue.
Proceedings of the IEEEReconstruction algorithms: Transform methods
385 Citations1983R.M. Lewitt
In this tutorial paper, the inversion formula for the case of two-dimensional (2-D) reconstruction from line integrals is manipulated into a number of different forms, each of which may be discretized to obtain different algorithms for reconstruction from sampled data.
Bulletin of the American Mathematical SocietyPractical and mathematical aspects of the problem of reconstructing objects from radiographs
358 Citations1977Kennan T. Smith, Donald C. Solmon +1 more
IEEE Transactions on Medical ImagingAn Improved Algorithm for Reprojecting Rays through Pixel Images
358 Citations1982Peter M. Joseph
Maximum-Entropy and Bayesian Methods in Inverse Problems
340 Citations1985C. Ray Smith, W. T. GrandyJr.
Journal of the American Statistical AssociationA Statistical Model for Positron Emission Tomography
300 Citations1985Y. Vardi, L. A. Shepp +1 more
Numerische MathematikThe defect correction principle and discretization methods
279 Citations1978Hans J. Stetter
This article exposes the common structural principle of all these techniques for error estimation and iterative improvement in discretization algorithms and exhibits the principal modes of its implementation in a discretized context.
Linear Algebra and its ApplicationsIterative algorithms for large partitioned linear systems, with applications to image reconstruction
271 Citations1981P. P. B. Eggermont, Gábor T. Herman +1 more
It is shown that some well-known iterative methods of image reconstruction fall into the class of algorithms under consideration, and are thus covered by the convergence theory, and a novel application to truly three-dimensional image reconstruction is described.
Mathematical ProgrammingDecomposition through formalization in a product space
257 Citations1984Guy Pierra
By associating systematically to this problem an equivalent one posed in ann-fold cartesian product space, by decomposition of the latter both a splitting of operators and a desintegration of constraints for the former are obtained.
Springer series in information sciencesProbability, Statistical Optics, and Data Testing
237 Citations1983B. Roy Frieden
Numerische MathematikStrong underrelaxation in Kaczmarz's method for inconsistent systems
221 Citations1983Yair Censor, P. P. B. Eggermont +1 more
Computer Graphics and Image ProcessingMENT: A maximum entropy algorithm for reconstructing a source from projection data
213 Citations1979Gerald Minerbo
An iterative algorithm, MENT, which produces a maximum entropy solution to the problem of reconstructing a source from a discrete set of projection data, and is compared with regard to convergence rates, artifact formation, and stability against noise errors in the data.
IEEE Transactions on Nuclear ScienceA Maximum Likelihood Approach to Emission Image Reconstruction from Projections
211 Citations1976A. J. Rockmore, Albert Macovski
This algorithm is shown to yield an image which is unbiased, which has the minimum variance of any estimator using the same measurements, and which will perform better than any current reconstruction technique, where the performance measures are the bias and viariance.
Proceedings of the IEEEAn introduction to NMR imaging: From the Bloch equation to the imaging equation
208 Citations1983W. S. Hinshaw, Arnold Lent
How selected families of signals may be input into the system ("system," in this case, is almost synonymous with "patient") in order that the system's responses to these inputs may be directly interpreted in terms of the system parameters is shown.
Applied Mathematics & OptimizationPartial inverse of a monotone operator
193 Citations1983Jonathan E. Spingarn
SIAM ReviewGeometric Programming: Methods, Computations and Applications
185 Citations1980J. G. Ecker
An applications-oriented survey of geometric programming, providing an understanding of the basic results in posynomial and signomial programming that have played a crucial role in applications.
Mathematics of Operations ResearchThe Relaxation Method for Solving Systems of Linear Inequalities
161 Citations1980Jean‐Louis Goffin
The relaxation method for solving systems of inequalities is related both to subgradient optimization and to the relaxation methods used in numerical analysis.
Transportation Research Part B MethodologicalBregman's balancing method
146 Citations1981Bernard F. Lamond, Nathaniel Stewart
Communications of the ACMRelaxation methods for image reconstruction
136 Citations1978Gábor T. Herman, Arnold Lent +1 more
It is shown that, for a consistent system of linear inequalities, any sequence of relaxation parameters lying strictly between 0 and 2 generates a sequence of vectors which converges to a solution.
Journal of Mathematical Analysis and ApplicationsThe X-ray transform
124 Citations1976Donald C. Solmon
Proceedings of the IEEEMathematical problems of computerized tomography
122 Citations1983Alfred K. Louis, Frank Natterer
This paper is concerned with the description of the integral transforms modeling the different techniques in computerized tomography, and the following questions are treated.
Mathematical ProgrammingA relaxation method for reconstructing objects from noisy X-rays
122 Citations1975Gábor T. Herman
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, and a finite convergence result is proved.
Applied Mathematics and ComputationA computational solution of the inverse problem in radiation-therapy treatment planning
109 Citations1988Yair Censor, Martin D. Altschuler +1 more
A discretized model is set up in which both patient section and radiation field are finely discretization, which leads to a linear feasibility problem, which is solved by a relaxation method.
Mathematical ProgrammingCyclic subgradient projections
106 Citations1982Yair Censor, Arnold Lent
A cyclically controlled method of subgradient projections (CSP) for the convex feasibility problem of solving convex inequalities is presented and a particular application to an image reconstruction problem of emission computerized tomography is mentioned.
IEEE Transactions on Acoustics Speech and Signal ProcessingWhich is the better entropy expression for speech processing: -S log S or log S?
102 Citations1984Ryan F. Johnson, John E. Shore
Although both estimates lead to intelligible speech, speech based on the MESA estimate is qualitatively superior, and the empirical investigation is based on speech synthesized using the different spectral estimates.
Journal of Optimization Theory and ApplicationsA relaxed version of Bregman's method for convex programming
102 Citations1986A.R. De Pierro, A. N. Iusem
It is shown that the new relaxation procedure generalizes the usual concept of relaxation and preserves the convergence properties of Bregman's algorithm for a suitable choice of the relaxation parameters.
SIAM Journal on Control and OptimizationExtensions of Hildreth’s Row-Action Method for Quadratic Programming
83 Citations1980Arnold Lent, Yair Censor
An extended version of Hildreth’s iterative quadratic programming algorithm is presented, geometrically interpreted, and proved to produce a sequence of iterates that converges to the solution, and has an important intermediate optimality property.
Mathematical ProgrammingEntropy in linear programs
80 Citations1981Sven Erlander
The optimal solutions to linear programs with one additional entropy constraint are expressed in terms of Lagrange-multipliers using the Newton—Kantorovich method for locally convergent iterative procedure.
IEEE Transactions on Acoustics Speech and Signal ProcessingTwo-dimensional spectral estimation
79 Citations1981J.A. Cadzow, Koji Ogino
Effective methods for generating two-dimensional quarter-plane causal autoregressive (AR) and Autoregressive moving average (ARMA) spectral estimation models are developed to provide super resolution capabilities when compared to other more classical methods such as the Fourier transform.
Linear Algebra and its ApplicationsA simultaneous projections method for linear inequalities
78 Citations1985Alvaro R. De Pierro, Alfredo N. Iusem
Computer Graphics and Image ProcessingQuadratic optimization for image reconstruction. I
74 Citations1976Gábor T. Herman, Arnold Lent
Alternative iterative algorithms for quadratic optimization for image reconstruction are discussed and their performance in image reconstruction with the previously used methods are compared.
Computer Graphics and Image ProcessingStatistical models for the image restoration problem
70 Citations1980B. Roy Frieden
A survey of statistical models that have led to restoration methods which overcome to various degrees the ill-conditioned nature of the Inversion of the image formation equation.
Linear Algebra and its ApplicationsNew methods for linear inequalities
68 Citations1982Yair Censor, Tommy Elfving
Linear Algebra and its ApplicationsOn some methods for entropy maximization and matrix scaling
65 Citations1980Tommy Elfving
It is shown how the iteration parameters can be chosen in an optimal way for the trip distribution problem in transportation planning and the equivalent problem of scaling a positive matrix to achieve a priori given row and column sums.
Mathematical programming studiesA family of iterative quadratic optimization algorithms for pairs of inequalities, with application in diagnostic radiology
64 Citations1978Gábor T. Herman, Arnold Lent
This work presents and proves the convergence of a family of iterative algorithms for finding the feasible y with minimum norm, based on Hildreth's quadratic optimization procedure for inequality constraints, that exploit the special form of the feasible region to reduce significantly both computer time and storage.
Optica Acta International Journal of OpticsImage Analysis and Evaluation
55 Citations1978L. Norton–Wayne
ComputingConnections between the Cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations
54 Citations1984Rainer Ansorge
A modification of the Cimmino-method is presented which makes it as interesting as the Kaczmarzmethod and in certain cases, the new method is even faster.
NDT InternationalRecent developments in the industrial application of computerized tomography with ionizing radiation
45 Citations1984P. Reimers, W.B. Gilboy +1 more
Journal of the Optical Society of AmericaUnified theory for estimating frequency-of-occurrence laws and optical objects
44 Citations1983B. Roy Frieden
Advances in Applied MathematicsAn interior points algorithm for the convex feasibility problem
43 Citations1983Ron Aharoni, Abraham Berman +1 more
Numerische MathematikSolution of underdetermined nonlinear equations by stationary iteration methods
43 Citations1983Klaus-hermann Meyn
Journal of Optimization Theory and ApplicationsThe role of duality in optimization problems involving entropy functionals with applications to information theory
40 Citations1988Aharon Ben‐Tal, Marc Teboulle +1 more
A duality theory is developed for infinite-dimensional optimization problems involving entropy-type functionals in the objective function as well as as in the constraints and applied to the reliability rate function problem in information theory.
SIAM Journal on Control and OptimizationOptimization of “$\log x$” Entropy over Linear Equality Constraints
38 Citations1987Yair Censor, Arnold Lent
A special-purpose iterative algorithm, of the row-action type, for solving the problem of maximizing the “$\log x$” entropy functional over linear equality constraints, employing “projections” onto hyperplanes which are called entropy projections.
Computer Graphics and Image ProcessingQuadratic optimization for image reconstruction, II
38 Citations1979Ehud Artzy, Tommy Elfving +1 more
North-Holland mathematics studiesIterative Methods for the Convex Feasibility Problem
37 Citations1984Yair Censor
ComputingReconstructing pictures from projections: On the convergence of the ART algorithm with relaxation
36 Citations1981Manfred R. Trummer
The convergence of the additive and linear ART algorithm with relaxation is proved in a new way and under weaker assumptions on the sequence of the relaation parameters than in earlier works.
Mathematical ProgrammingConvergence of the cyclical relaxation method for linear inequalities
34 Citations1984Jan Mandel
The relaxation method for linear inequalities is studied and new bounds on convergence obtained and an asymptotically tight estimate is given for the case when the inequalities are processed in a cyclical order.
Application of Maximum Entropy and Bayesian Optimization Methods to Image Reconstruction from Projections
27 Citations1985Gábor T. Herman
Algebraic reconstruction techniques (ART) are given that converge to different optimizers for image reconstruction from projections, including unconstrained regularized least squares estimation based on Bayesian optimization, and constrained norm minimization and entropy maximization.
Journal of Mathematical Analysis and ApplicationsAn automatic relaxation method for solving interval linear inequalities
24 Citations1985Yair Censor
An algorithm of the row-action type is proposed which, in each iterative step, effectively takes account of a pair of inequalities describing a single interval inequality.
Mathematical programming studiesMathematical optimization versus practical performance: A case study based on the maximum entropy criterion in image reconstruction
24 Citations1982Gábor T. Herman
Practical problems are often translated into problems of mathematical optimization by a process of abstraction, simplification and assumption making which leaves one to wonder whether solving the mathematical optimization problem will help us in any way with the authors' original practical problem.
Lecture notes in medical informaticsContinuous and Semicontinuous Analogues of Iterative Methods of Cimmino and Kaczmarz with Applications to the Inverse Radon Transform
23 Citations1981M. Zuhair Nashed
Journal of applied meteorologySatellite Remote Sensing by the Technique of Computed Tomography
21 Citations1982H. Fleming
Mathematical Methods in the Applied SciencesA method of iterative data refinement and its applications
21 Citations1985Yair Censor, Tommy Elfving +2 more
IDR provides a common framework within which a number of originally different looking procedures are presented and discussed, and it is shown that a standard method of numerical mathematics as well as a whole family of constrained iterative restoration algorithms are special cases of it.
Transportation Research Part B MethodologicalMaximum likelihood, entropy maximization, and the geometric programming approaches to the calibration of trip distribution models
21 Citations1981Danny Wong
Journal of Approximation TheorySymmetric duality, and a convergent subgradient method for discrete, linear, constrained approximation problems with arbitrary norms appearing in the objective function and in the constraints
19 Citations1975W. Oettli
A method is described for solving certain dual pairs of constrained approximation problems and its application to discrete-time approximation problems is described.
ComputingA note on the ART of relaxation
18 Citations1984Manfred R. Trummer
The ART algorithm, an iterative technique for solving large systems of linear equations, is shown to converge even for inconsistent systems, provided the relaxation parameters are chosen appropriately, and the limit is a weighted least squares solution.
Springer series in information sciencesMultilevel Image Reconstruction
15 Citations1984Gábor T. Herman, Haim Levkowitz +2 more
In image reconstruction from projections, one attempts to estimate values of an unknown function f of two variables at points of a finite grid from a finite number of (measured) line integrals of f.
Iterative relaxation methods for image reconstruction
15 Citations1975Gábor T. Herman, Arnold Lent +1 more
The problem of recovering an image from experimentally available integrals of its grayness over thin strips is of great importance in a large number of scientific areas and a variety of methods have been proposed with differing relaxation parameters.
ComputingOn the convergence of the discrete ART algorithm for the reconstruction of digital pictures from their projections
13 Citations1979Jürg T. Marti
New Proofs are given for the known convergence of the additive and linear ART algorithms, which belong to a class of methods for the reconstruction of digitized pictures from one-dimensional views which are used e.
Journal of the Optical Society of AmericaMaximum-information data processing: application to optical signals
12 Citations1981B. Roy Frieden
The MI principle is shown to be applicable to optical problems when enough photons are present to characterize the optical signals as probability laws and the image-restoration, image- or signal-smoothing, and missing-phase problems are addressed.
Applied OpticsConvergence of Chahine's nonlinear relaxation inversion method used for limb viewing remote sensing
11 Citations1985William Chu
It is demonstrated that the Chahine inversion technique always converges, provided the diagonal elements of the kernel matrix are nonzero.
Zeitschrift für angewandte Mathematik und PhysikSMART ? An algorithm for reconstructing pictures from projections
10 Citations1983Manfred R. Trummer
Journal of the Optical Society of America AIterative reconstruction algorithms: convergence as a function of spatial frequency
8 Citations1985Stephen J. Norton
An analysis of two well-known iterative reconstruction-from-projections algorithms, ART and SIRT, that demonstrates how individual spatial-frequency components in the image converge at different rates to their respective object components.
Special-Purpose Algorithms for Linearly Constrained Entropy Maximization
7 Citations1987Yair Censor, Tommy Elfving +1 more
A family of algorithms of the row-action type that are suitable for solving large and sparse entropy maximization problems with linear constraints, designed to handle equality constraints, in-equality constraints, or interval constraints.
Lecture notes in medical informaticsIntervals in Linear and Nonlinear Problems of Image Reconstruction
3 Citations1981Yair Censor
In the “series expansion” approach to image reconstruction, the mathematical formulation takes the form of a system of equations, linear or nonlinear, which describes the real problem only approximately because discretization takes place at the very beginning of the series expansion approach.
…