×

On some optimization techniques in image reconstruction from projections. (English) Zbl 0655.65140

This is an expository paper on optimization techniques in computerized tomography. Besides a general introduction into the subject it covers quadratic minimization, entropy maximization, and likelihood maximization.
Reviewer: F.Natterer

MSC:

65R10 Numerical methods for integral transforms
44A15 Special integral transforms (Legendre, Hilbert, etc.)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Agmon, S., The relaxation method for linear inequalities, Canad. J. math., 6, 382-392, (1954) · Zbl 0055.35001
[2] Aharoni, R.; Berman, A.; Censor, Y., An interior points algorithm for the convex feasibility problem, Adv. appl. math., 4, 479-489, (1983) · Zbl 0489.52005
[3] Altschuler, M.D.; Censor, Y.; Powlis, W.D., Contributions to radiation therapy treatment planning, Tech. rept. #87, (1984), Mathematics Publication Series, University of Haifa Haifa, Israel
[4] Anderson, D.L.; Dziewonski, A.M., Seismic tomography, Sci. amer., 251, 58-66, (1984)
[5] Ansorge, R., Connections between the cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations, Computing, 33, 367-375, (1984) · Zbl 0537.65027
[6] Artzy, E.; Elfving, T.; Herman, G.T., Quadratic optimization for image reconstruction, II, Comput. graph. image process., 11, 242-261, (1979)
[7] Auslender, A., Optimisation: methodes numériques, (1976), Masson Paris · Zbl 0326.90057
[8] Bacharach, M., Biproportional matrices and input-output change, (1970), Cambridge University Press Cambridge, MA · Zbl 0195.49705
[9] Ben-Tal, A.; Teboulle, M.; Charnes, A., The role of duality in optimization problems involving entropy functionals, with applications to information theory, Research rept. CCS497, (1984), Center for Cybernetic Studies, The University of Texas at Austin Austin, TX, J. Optim. Theory Appl., to appear · Zbl 0631.49007
[10] Bohmer, K.; Stetter, H.J., Computing supplementum, 5, (1984), Springer Wien, Defect Correction Methods: Theory and Applications
[11] Bregman, L.M., The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, U.S.S.R. comput. math. and math. phys., 7, 3, 200-217, (1967) · Zbl 0186.23807
[12] Burg, J.P., Maximum entropy spectral analysis, Proceedings 37th annual meeting of the society of exploration geophysicists, (1967), Oklahoma City, OK
[13] Censor, Y., An automatic relaxation method for solving interval linear inequalities, J. math. anal. appl., 106, 19-25, (1985) · Zbl 0568.65022
[14] Censor, Y., Entropy optimization via entropy projections, (), 450-454, Lecture Notes in Control and Information Science
[15] Censor, Y., Finite series-expansion reconstruction methods, Proc. IEEE, 71, 409-419, (1983)
[16] Censor, Y., Intervals in linear and nonlinear problems of image reconstruction, (), 152-159, Lecture Notes in Medical Informatics
[17] Censor, Y., Iterative methods for the convex feasibility problem, Ann. discrete math., 20, 83-91, (1983)
[18] Censor, Y., Row-action methods for huge and sparse systems and their applications, SIAM rev., 23, 444-466, (1981) · Zbl 0469.65037
[19] Censor, Y.; Altschuler, M.D.; Powlis, W.D., A computational solution of the inverse problem in radiation therapy treatment planning, Tech. rept. #91, (April 1985), Mathematics Publication Series, University of Haifa Haifa, Israel, Appl. Math. Comput., to appear
[20] Censor, Y.; Eggermont, P.P.B.; Gordon, D., Strong underrelaxation in Kaczmarz’s method for inconsistent systems, Numer. math., 41, 83-92, (1983) · Zbl 0489.65023
[21] Censor, Y.; Elfving, T., New methods for linear inequalities, Linear algebra appl., 42, 199-211, (1982) · Zbl 0479.65039
[22] Censor, Y.; Elfving, T.; Herman, G.T., A method of iterative data refinement and its applications, Mathematical methods appl. sci., 7, 108-123, (1985) · Zbl 0561.92002
[23] Censor, Y.; Elfving, T.; Herman, G.T., Methods for entropy maximization with applications in image processing, (), 296-300
[24] Censor, Y.; Elfving, T.; Herman, G.T., Special-purpose algorithms for linearly constrained entropy maximization, Tech. rept. MIPG90, (1984), Medical Image Processing Group, Department of Radiology, Hospital of the University of Pennsylavania Philadelphia, PA · Zbl 0626.65055
[25] Censor, Y.; Lent, A., An iterative row-action method for interval convex programming, J. optim. theory appl., 34, 321-353, (1981) · Zbl 0431.49042
[26] Censor, Y.; Lent, A., Cyclic subgradient projections, Math. programming, 24, 233-235, (1982) · Zbl 0491.90077
[27] Censor, Y.; Lent, A., Optimization of “log x”-entropy over linear equality constraints, SIAM J. control optim., 25, (1987) · Zbl 0631.90050
[28] Chu, W.P., Convergence of Chahine’s nonlinear relaxation inversion method used for limb viewing remote sensing, Appl. optics, 24, 445-447, (1985)
[29] Cimmino, G., Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari, Ricerca sci. (roma), ser. II, anno IX, 1, 326-333, (1938) · JFM 64.1244.02
[30] D’Addario, L.R., Maximum entropy imaging: theory and philosophy, (), 221-225
[31] Darroch, J.N.; Ratcliff, D., Generalized iterative scaling for log linear models, Ann. math. statist., 43, 1470-1480, (1972) · Zbl 0251.62020
[32] Dempster, A.P.; Laird, N.M.; Rubin, D.B., Maximum likehood from incomplete data via the EM algorithm, J. roy. statist. soc., 39, 1-38, (1977) · Zbl 0364.62022
[33] De Pierro, A.R.; Iusem, A.N., A relaxed version of Bregman’s method for convex programming, J. optim. theory appl., 51, 421-440, (1986) · Zbl 0581.90069
[34] De Pierro, A.R.; Iusem, A.N., A simultaneous projection method for linear inequalities, Linear algebra appl., 64, 243-253, (1985) · Zbl 0552.65051
[35] Duffin, R.J.; Peterson, E.L.; Zener, C., Geometric programming—theory and applications, (1967), Wiley New York · Zbl 0171.17601
[36] Ecker, J.G., Geometric programming: methods, computations and applications, SIAM rev., 22, 338-362, (1980) · Zbl 0438.90088
[37] Eggermont, P.P.B.; Herman, G.T.; Lent, A., Iterative algorithms for large partitioned linear systems with applications to image reconstruction, Linear algebra appl., 40, 37-67, (1981) · Zbl 0466.65021
[38] Elfving, T., On some methods for entropy maximization and matrix scaling, Linear algebra appl., 34, 321-339, (1980) · Zbl 0458.65052
[39] Eremin, I.I., Fejer mappings and convex programming, Siberian math. J., 10, 762-772, (1969) · Zbl 0196.23004
[40] Erlander, S., Entropy in linear programs, Math. programming, 21, 137-151, (1981) · Zbl 0461.90049
[41] Fleming, H.E., Satellite remote sensing by the technique of computed tomography, J. appl. meteorology, 21, 1538-1549, (1982)
[42] Frieden, B.R., Image enhancement and restoration, (), 177-248, Topics in Applied Physics
[43] Frieden, B.R., Maximum information data processing: application to optical signals, J. optical soc. amer., 71, 294-303, (1981)
[44] Frieden, B.R., Probability, statistical optics, and data testing, (1983), Springer Berlin · Zbl 0495.62002
[45] Frieden, B.R., Statistical models for the image restoration problem, Comput. graph. image process., 12, 40-59, (1980)
[46] Frieden, B.R., Unified theory for estimating frequency-of-occurence laws and optical objects, J. optical soc. amer., 73, 927-938, (1983)
[47] Gastinel, N., Linear numerical analysis, (1970), Hermann Paris · Zbl 0318.65006
[48] Gilbert, P.F.C., Iterative methods for the three-dimensional reconstruction of an object from projections, J. theoret. biol., 36, 105-117, (1972)
[49] Goffin, J.L., The relaxation method for solving systems of linear inequalities, Math. oper. res., 5, 388-414, (1980) · Zbl 0442.90051
[50] Gordon, R.; Bender, R.; Herman, G.T., Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography, J. theoret. biol., 29, 471-481, (1970)
[51] Gubin, L.G.; Polyak, B.T.; Raik, E.V., The method of projections for finding the common point of convex sets, U.S.S.R. comput. math. and math. phys., 7, 1-24, (1967)
[52] Han, S.P., Least-squares solution of linear inequalities, Tech. rept. 2141, (1980), Mathematics Research Center, University of Wisconsin Madison, WI
[53] Helgason, S., The Radon transform, (1980), Birkhauser Boston, MA · Zbl 0453.43011
[54] Herman, G.T., Application of maximum entropy and Bayesian optimization methods to image reconstruction from projections, (), 319-338
[55] Herman, G.T., Image reconstruction from projections: the fundamentals of computerized tomography, (1980), Academic Press New York · Zbl 0538.92005
[56] Herman, G.T., Image reconstruction from projections: implementation and applications, Topics in applied physics, 32, (1979), Springer Berlin
[57] Herman, G.T., Mathematical optimization versus practical performance: A case study based on the maximum entropy criterion in image reconstruction, Math. programming study, 20, 96-112, (1982) · Zbl 0487.92002
[58] Herman, G.T., A relaxation method for reconstructing objects from noisy X-rays, Math. programming, 8, 1-19, (1975) · Zbl 0298.65028
[59] (), 291-435
[60] Herman, G.T.; Censor, Y.; Gordon, D.; Lewitt, R.M., Comments on a statistical model for positron emission tomography, J. amer. statist. assoc., 80, 22-25, (1985)
[61] Herman, G.T.; Lent, A., A family of iterative quadratic optimization algorithms for pairs of inequalities, with application in diagnostic radiology, Math. programming study, 9, 15-29, (1978) · Zbl 0389.90078
[62] Herman, G.T.; Lent, A., Iterative reconstruction algorithms, Comput. biol. medicine, 6, 273-294, (1976)
[63] Herman, G.T.; Lent, A., Quadratic optimization for image reconstruction, I, Comput. graph. image process., 5, 319-332, (1976)
[64] Herman, G.T.; Lent, A.; Lutz, P.H., Iterative relaxation methods for image reconstruction, Commun. ACM, 21, 152-158, (1978) · Zbl 0367.68065
[65] Herman, G.T.; Levkowitz, H.; Tuy, H.K.; McCormick, S., Multilevel image reconstruction, (), 121-135
[66] Hildreth, C.; Hildreth, C., Erratum, Naval res. logist. quart., Naval res. logist. quart., 4, 361-85, (1977)
[67] Hinshaw, W.S.; Lent, A.H., An introduction to NMR imaging: from the Bloch equation to the imaging equation, Proc. IEEE, 71, 338-350, (1983)
[68] Jain, A.K.; Ranganath, S., Two dimensional spectral estimation, (), 151-157
[69] Jaynes, E.T., On the rationale of maximum-entropy methods, Proc. IEEE, 70, 939-952, (1982)
[70] Johnson, R.; Shore, J.E., Which is the better entropy expression for speech processing: - S log S or log S?, IEEE trans. acoust. speech signal process., 32, 129-136, (1984)
[71] Joseph, P.M., An improved algorithm for reprojecting rays through pixel images, IEEE trans. medical imaging, 1, 191-196, (1982)
[72] Kaczmarz, S., Angenäherte auflösung von systemen linearer gleichungen, Bull. internat. acad. polon. sci. lett. A., 35, 355-357, (1937) · JFM 63.0524.02
[73] Kapur, J.N., Twenty-five years of maximum-entropy principle, J. math. phys. sci., 17, 103-156, (1983) · Zbl 0516.94001
[74] Kruithof, J., Telefoonverkeersrekening, De ingenieur, 52, E15-E25, (1937), in Dutch
[75] Krupp, R.S., Properties of Kruithof’s projection method, Bell syst. tech. J., 58, 517-538, (1979) · Zbl 0402.90095
[76] Lamond, B.; Stewart, N.P., Bregman’s balancing method, Transportation res. B, 15, 239-248, (1981)
[77] Lange, K.; Carson, R., EM reconstruction algorithms for emission and transmission tomography, J. comput. assisted tomography, 8, 306-316, (1984)
[78] Lent, A., A convergent algorithm for maximum entropy image restoration with a medical X-ray application, (), 249-257
[79] Lent, A.; Censor, Y., Extensions of Hildreth’s row-action method for quadratic programming, SIAM J. control optim., 18, 444-454, (1980) · Zbl 0444.49025
[80] Levine, R.D.; Tribus, M., The maximum entropy formalism, (1978), MIT Press Cambridge, MA
[81] Lewitt, R.M., Reconstruction algorithms: transform methods, Proc. IEEE, 71, 390-408, (1983)
[82] Louis, A.K.; Natterer, F., Mathematical problems of computerized tomography, Proc. IEEE, 71, 379-389, (1983)
[83] Mandel, J., Convergence of the cyclical relaxation method for linear inequalities, Math. programming, 30, 218-228, (1984) · Zbl 0545.90068
[84] Marti, J.T., On the convergence of the discrete ART algorithm for the reconstruction of digital pictures from their projections, Computing, 21, 105-111, (1979) · Zbl 0394.68031
[85] McCormick, S.F., The method of Kaczmarz and row orthogonalization for solving linear equations and least squares problems in hilberts spaces, Indiana univ. math. J., 26, 1137-1150, (1977) · Zbl 0341.65046
[86] Meyer, S.L., Data analysis for scientists and engineers, (1975), Wiley New York
[87] Meyn, K.-H., Solution of underdetermined nonlinear equations by stationary iteration methods, Numer. math., 42, 161-172, (1983) · Zbl 0497.65026
[88] Minerbo, G.N., MENT: A maximum entropy algorithm for reconstructing a source from projection data, Comput graph. image process., 10, 48-68, (1979)
[89] Motzkin, T.S.; Schoenberg, I.J., The relaxation method for linear inequalities, Canad. J. math., 6, 393-404, (1954) · Zbl 0055.35002
[90] Nashed, M.Z., Continuous and semicontinuous analogues of iterative methods of cimmino and Kaczmarz with applications to the inverse Radon transform, (), 160-178, Lecture Notes in Medical Informatics · Zbl 0544.65090
[91] Norton, S.J., Iterative reconstruction algorithms: convergence as a function of spatial frequency, J. optical soc. amer., 2, 6-13, (1985)
[92] Oettli, W., Symmetric duality and a convergent subgradient method for discrete, linear, constrained approximation problems with arbitrary norms appearing in the o bjective function and in the constraints, J. approx. theory, 14, 43-50, (1975) · Zbl 0297.41015
[93] Ortega, J.M.; Rheinboldt, W.C., Iterative solution of nonlinear equations in several variables, (1970), Academic Press New York · Zbl 0241.65046
[94] Peters, W., Lösung linearer gleichungssysteme durch projektion auf schnitträume von hyperebenen und berechnung einer verallgemeinerten inversen, Beiträge numer. math., 5, 129-146, (1976) · Zbl 0359.65024
[95] Pierra, G., Decomposition through formalization in a product space, Math. programming, 28, 96-115, (1984) · Zbl 0523.49022
[96] Radon, J., Uber die bestimmung von funktionen durch ihre integralwerte langs gewisser mannigfaltigkeiten, Ber. verb. saechs. akad. wiss., Leipzig, math. phys. kl., 69, 262-277, (1917) · JFM 46.0436.02
[97] Raviv, J.; Greenleaf, J.F.; Herman, G.T., Computer aided tomography and ultrasonics in medicine, (1979), North-Holland Amsterdam
[98] Reimers, P.; Gilboy, W.B.; Goebbels, J., Recent developments in the industrial application of computerized tomography with ionizing radiation, Nondestructive testing internat., 17, 197-207, (1984)
[99] Rockmore, A.J.; Macovski, A., A maximum likelihood approach to emission image reconstruction from projections, IEEE trans. nucl. sci., 23, 1428-1432, (1976)
[100] Shepp, L.A.; Vardi, Y., Maximum likelihood reconstruction in positron emission tomography, IEEE trans. medical imaging, 1, 113-122, (1982)
[101] Smith, C.R.; Grandy, W.T., Maximum-entropy and Bayesian methods in inverse problems, (1985), Reidel Dordrecht
[102] Smith, K.T.; Solmon, D.C.; Wagner, S.L., Practical and mathematical aspects of the problem of reconstructing objects from radiographs, Bull. amer. math. soc., 83, 1227-1270, (1977) · Zbl 0521.65090
[103] Solmon, D.C., The x-ray transform, J. math. anal. appl., 56, 61-83, (1976) · Zbl 0334.44007
[104] Spingarn, J.E., Partial inverse of a monotone operator, Appl. math. optim., 10, 247-265, (1983) · Zbl 0524.90072
[105] Stetter, H.J., The defect correction principle and discretization methods, Numer. math., 29, 425-443, (1978) · Zbl 0362.65052
[106] Tanabe, K., Projection method for solving a singular system of linear equations and its applications, Numer. math., 17, 203-214, (1971) · Zbl 0228.65032
[107] Trummer, M.r., A note of the ART of relaxation, Computing, 33, 349-352, (1984) · Zbl 0569.65032
[108] Trummer, M.R., Reconstructing pictures from projections: on the convergence of the ART algorithm with relaxation, Computing, 26, 189-195, (1981) · Zbl 0444.68079
[109] Trummer, M.R., SMART—an algorithm for reconstructing pictures from projections, J. appl. math. phys., 34, 746-753, (1983) · Zbl 0528.65071
[110] Vardi, Y.; Shepp, L.A.; Kaufman, L., A statistical model for positron emission tomography, J. amer. statist. assoc., 80, 8-20, (1985) · Zbl 0561.62094
[111] Vardi, Y.; Shepp, L.A.; Kaufman, L., Reply to herman, censor, Gordon and lewitt, J. amer. statist. assoc., 80, 34-35, (1985)
[112] Wernecke, S.J., Maximum entropy techniques for digital image reconstruction, (), 238-243
[113] Wong, D.S., Maximum likelihood, entropy maximization, and the geometric programming approaches to the calibration of trip distribution models, Transportation res. B, 15, 329-343, (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.