SCE Carleton Logo
  Carleton > Engineering > SCE > Faculty > A. Adler > Courses > Directed Studies

 

Directed Studies: Inverse Problems

Description

Inverse problems techniques are used to solve problems in image processing, medial imaging, geophysics, and many other fields in which we need to "reconstruct" the parameters we're interested in, based on measurements which relate to those parameters in some complicated way. The Hadamard (inverse) definition of inverse problem is: a problem is not an inverse problem if: 1) a solution exists, 2) is unique, and 3) the solution depends continuously on the data.

This directed studies course covers: Inverse problems for such diciplines as image enhancement, medical imaging, geophysics, and nondestructive testing. Nonlinearity, ill-conditioning and ill-posedness. Tikhonov Regularization. Bayes theorum. Bayesian Regularization. Maximum a posteriori estimation. Maximum Likelyhood techniques. Hyperparameter estimation. Edge preserving regularization techniques.

Instructor

Andy Adler ,
Email: adler@site.uottawa.ca ,
Office: CBY A610 ,
Phone: 562-5800 x 6218

Marks

Work  Value
 
Presentation #1    15 %
Presentation #2    15 %
Assignments (Part 1&2)    30 %
Project Report
− Project Proposal
− Project Report 		   40 %
− 3 %
− 37 %

Schedule

No.  Assignment  Due Date  Place/Time
 
-    Meeting: Initial course meeting    May 2    CBY B202
13h30−15h00
-    Meeting: Discussion Meeting    May 16    CBY B202
14h00−15h30
1    Presentation #1: covering one aspect of basic inverse problem theory. Students are encouraged to discuss amongst themselves to select various topics to cover the field.
− Camille: Hyperparameter choice for Regularization
− Chris : Edge Preserving Regularization
− Mike: Comparison of CT backprojection and regularization
− Ran: Measures of Model Validity
− Saeed: Total Variation Regularization
− Tao: Adaptive Filtering and Regularization 		   May 30    CBY B202
14h00−17h00
2    Assignment (Part 1)
− Tikhonov Regularization
− Code to imlement one technique to estimate the hyperparameter value, such as GCV, L-curve 		   June 6   
-    Meeting: Discussion Meeting    June 13    CBY B202
14h00−15h30
3    Project Proposals Due:    June 15   
4    Assignment (Part 2)
− One advanced regularization technique, such as: MAP, ML, etc. 		   June 27 (Extended)   
5    Presentation #2:    July 25    CBY B202
14h00−18h00
6    Project Reports Due:    July 25   

Assignments, Presentations, and Project

  • Presentations:
      Presentations will be in English and last approx. 20-25 minutes followed by questions. Marks are based on technical content, clarity of presentation, and ability to answer questions.
  • Project Proposal:
      Proposal is 1-2 pages (double spaced). Include problem description, proposed techniques, and references.
  • Project Report:
      The report will be 20−40 pages (double spaced) and written in English or French. The project will involve reading and explanation of algorithms for a broad range of inverse problem litterature. If possible, an implementation of an advanced algorithm will be developed. Include an introduction, methods, results and discussion. Ensure that the report synthesizes and discusses the material. Do not simply restate existing work. Marks are based on the technical content, and report clarity.
  • Assignment:
      Consider the backprojection algorithm for forward and inverse Computed Tomography (CT) scanning shown here. Develop code to implement an inverse solution for backprojection for the following regularization schemes:
      • Tikhonov Regularization (Part 1)
      • Code to imlement one technique to estimate the hyperparameter value: eg. GCV (Part 1)
      • One advanced regularization technique, such as: MAP, ML, etc. (Part 2)
      Hint: Unfiltered backprojection may be formulated as using the transpose of the sensitivity matrix as the inverse. This Matlab/octave code will implement that function, using the function makeproj.m. (Increase spc to use less memory or run faster) 
      spc=.05; rlim=1;
[x,y]= meshgrid(-rlim:spc:rlim,-rlim:spc:rlim);
plen= size(x,1);
img = (x.^2 + y.^2) > rlim;
img( x >.45 & x<.65 & y>-.05 & y<.45) =1;
img( x >-.55 & x<-.25 & y>.45 & y<.65) =1;
angls= [0:15:179.9];

H= []; % create sensitivity matrix H
for ang= angls
  H= [H ; makeproj(ang*(pi/180),x,y) ];
end
H= sparse(H);

proj = H* img(:); % simulate measurements

% simple CT backprojection 
imbp= reshape( H' * proj, plen, plen);
imbp = imbp + max(imbp(:))*(  x.^2 + y.^2 > rlim );

imagesc(imbp); % show reconstructed image

Texts and Materials

The following list represents a selection of inverse problem litterature. Students should read at least 1 book and/or 5-10 papers from this list during the completion of the project.

Note, if you have suggestions for this list, please send them to me; it is hard to keep such a list up to date.

  • Web
  • Books
    • M Beretro and P Boccacci, (1998) Introduction to Inverse Problems in Imaging, Institute of Physics Publishing ISBN 0750304391
    • Albert Tarantola, (2004) Inverse Problem Theory, Elsevier Science. ISBN 0444427651
    • Albert Tarantola, (2004) Inverse Problem Theory and Methods for Model Parameter Estimation SIAM
    • Per Christian Hansen, (1998) Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion, Society for Industrial and Applied Mathematics. ISBN 0898714036
    • Heinz W. Engl, Martin Hanke, Andreas Neubauer, (1996) Regularization of Inverse Problems, Kluwer Academic Publishers. ISBN 0792341570
    • Curtis Vogel, (2002) Computational methods for inverse problems Society for Industrial and Applied Mathematics. ISBN 0898715075
    • Richard Aster, Brian Borchers, and Cliff Thurber, (2004) Parameter Estimation and Inverse Problems Academic Press, ISBN 0120656043
    • Frank Natterer and Frank Wubbeling, (2001) Mathematical Methods in Image Reconstruction, Society for Industrial and Applied Mathematics. ISBN 0898714729
  • Journals
  • Papers of interest
    • Tikhonov, A.N. and Arsenin, V.A. (1977) Solutions of Ill-posed Problems. Washington: Winston & Sons.
    • Engl, H.W., Hanke, M., Neubauer, A., Regularization of Inverse Problems, Kluwer, Dordrecht, 1996. (referred by these documents)
    • Andia BI, Sauer KD, Bouman CA. Nonlinear backprojection for tomographic reconstruction. [Journal Paper] IEEE Transactions on Nuclear Science, vol.49, no.1, pt.1, Feb. 2002, pp.61-8. Publisher: IEEE, USA.
    • Zheng J, Saquib SS, Sauer K, Bouman CA. Parallelizable Bayesian tomography algorithms with rapid, guaranteed convergence. [Journal Paper] IEEE Transactions of Image Processing, vol.9, no.10, Oct. 2000, pp.1745-59. Publisher: IEEE, USA.
    • Bouman C, Sauer K. A generalized Gaussian image model for edge-preserving MAP estimation. [Journal Paper] IEEE Transactions of Image Processing, vol.2, no.3, July 1993, pp.296-310. USA.
    • Chan T, Marquina A, Mulet P. High-order total variation-based image restoration. [Journal Paper] SIAM Journal on Scientific Computing, vol.22, no.2, 2000, pp.503-16. Publisher: SIAM, USA.
    • A.Dalaney and Y.Bresler. Globally convergent edge-preserving regularization: An application to limited-angle tomography. IEEE Trans. on Image Processing, 7(2):204--221, 1998.
    • S. Geman and D. Geman, "Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-6, no. 6, pp. 721-741, November 1984.
    • D. Geman and C. Yang, Nonlinear image recovery with half-quadratic regularization, IEEE Trans. Image Processing, 4(7):932--946, July 1995.
  • Material from Per Christian Hansen, Dept. of Mathematical Modelling, Technical Univ. of Denmark.
  • A Reading List in Inverse Problems, Brian Borchers
    • Johann Baumeister. Stable Solution of Inverse Problems. Vieweg, Braunschweig, 1987.
      M3. Theory of ill-posed problems, singular value decomposition. Tikhonov regularization, least squares solution of systems of linear equations, convolution equations, final value problems, parameter identification. No exercises.
    • James G. Berryman. Lecture notes on nonlinear inversion and tomography: I. borehole siesmic tomography.
      http://sepwww.stanford.edu/sep/berryman/NOTES/lecture notes.html, October 1991. M2. Seismic inversion, traveltime inversion, tomography. Exercises.
    • G. Backus and F. Gilbert. Uniqueness in the inversion of inaccurate gross earth data. Philosophical Transactions of the Royal Society A, 266:123-192, 1970.
      M2.5. This is a classic paper introducing the method of Backus and Gilbert for linear inverse problems.
    • Philip Carrion. Inverse Problems and Tomography in Acoustics and Seismology. Penn Publishing Company, Atlanta, Georgia, 1987.
      M2.5. Seismic inversion and tomography. No exercises.
    • Jon F. Claebourt. Imaging the Earth's Interior. Blackwell Scientific Publications, Palo Alto, CA, 1985. Out of print, but available on the web. See http://sepwww.stanford.edu/sep/prof/index.html.
      M2. Seismic Inversion. No exercises. Claerbout has several other books available from the same web site.
    • Steven C. Constable, Robert L. Parker, and Catherine G. Constable. Occam's inversion: A practical algorithm for generating smooth models from electromagnetic sounding data. Geophysics, 52(3):289-300, 1987.
      M2. This paper describes an iterative method for solving a nonlinear discrete inverse problem by linearizing the problem and using the discrepancy principle.
    • Heinz W. Engl, Martin Hanke, and Andreas Neubauer. Regularization of Inverse Problems. Kluwer Academic Publishers, Dordrecht, 1996.
      M3. Examples, ill-posed linear operator equations, Tikhonov regularization, iterative regularization methods, the conjugate gradient method, numerical implementation, nonlinear problems. No exercises.
    • Heinz W. Engl. Regularization methods for the stable solution of inverse problems. Surveys on Mathematics for Industry, 3:71-143, 1993.
      M2.5. A broad survey of regularization methods with lots of examples.
    • Charles W. Groetsch. Inverse Problems in the Mathematical Sciences. Vieweg, Bruanschweig; Wiesbaden, 1993.
      M2. An introduction to the mathematics of inverse problems, requiring only undergraduate mathematics. Integral equations of the first kind, parameter estimation in differentional equations, regularization, iterative methods, the maximum entropy method, the Backus-Gilbert method. Exercises.
    • Per Christian Hansen. Analysis of discrete ill-posed problems by means of the L-curve. SIAM Review, 34(4):561-580, December 1992.
      M2. This paper discusses the use of the L-curve criteria for selecting a regularization parameter and compares it with generalized cross validation.
    • Per Christian Hansen. Regularization tools: A MATLAB package for analysis and solution of discrete ill{posed problems. Numerical Algorithms, 6:1-35, 1994.
      http://www.imm.dtu.dk/documents/users/pch/Regutools/regutools.html. M2. The regularization toolbox provides a variety of functions for solving inverse problems, including the SVD and generalized SVD, truncated SVD solutions, Tikhonov regularization, maximum entropy regularization, and a variety of examples.
    • Per Christian Hansen. Rank-Deficient and Discrete Ill-Posed Problems. SIAM, Philadelphia, 1998.
      M2. Numerical methods for discretized inverse problems, including basic theory, direct and iterative methods for regularization, and methods for picking the regularization parameter. Examples drawn from the author's regularization toolbox. No Exercises.
    • Martin Hanke and Per Christian Hansen. Regularization methods for large-scale problems. Surveys on Mathematics for Industry, 3:253- 315, 1993.
      M2.5. Another survey paper, with special emphasis on iterative methods for large scale problems. Contains a good discussion of methods for selecting the regularization parameter.
    • Andreas Kirsch. An Introduction to the Mathematical Theory of Inverse Problems. Springer Verlag, New York, 1996.
      M3. Regularization theory, Tikhonov regularization, regularization by discretization, the method of Backus and Gilbert, inverse eigenvalue problems, inverse scattering problems. Includes exercises.
    • C. L. Lawson and R. J. Hanson. Solving Least Squares Problems. Prentice-Hall, Englewood Cliffs, New Jersey, 1974.
      M2. A classic book on the solution of linear least squares problems. Contains an early discussion of the L-curve. This book has recently been republished by SIAM. Exercises.
    • Laurence R. Lines, editor. Inversion of Geophysical Data. Society of Exploration Geophysicists, 1988.
      M2. A collection of reprints of tutorial/survey papers on inversion. Linearized inversion techniques, seismic inversion, inversion of electromagnetic and potential field data. No exercises
    • William Menke. Geophysical Data Analysis: Revised Edition, volume 45 of International Geophysics Series. Academic Press, San Diego, 1989.
      M2. Generalized inverses, maximum likelihood methods, the method of Backus and Gilbert, nonlinear inverse problems, numerical algorithms, applications. No exercises.
    • V. A. Morozov. Methods for Solving Incorrectly Posed Problems. Springer-Verlag, New York, 1984.
      M3. Pseudoinverses, regularization, methods for picking the regularization parameter, nonlinear problems. No exercises.
    • Robert L. Parker. Geophysical Inverse Theory. Princeton University Press, Princeton, NJ, 1994.
      M2. Mathematical background, examples from geophsyics, Tikhonov regularization, resolution, nonlinear problems. Exercises.
    • Dilip N. Ghosh Roy. Methods of Inverse Problems in Physics. CRC Press, Boca Raton, 1991.
      M2.5. Inverse problems in physics, the Povzner-Levitan transform, the Gelfand-Levitan Equation, Jost Functions, the Marcenko integral equation, the Radon transform. No exercises.
    • P.C. Sabatier, editor. Inverse Problems: An Interdisciplinary Study. Academic Press, London, 1987.
      M2.5. A collection of papers, mostly applications in tomography, electromagnetic inverse scattering, quantum mechanics, and other areas. No exercises.
    • John Scales. Theory of seismic imaging.
      http://landau.Mines.EDU/samizdat/imaging/index.html, 1997. M2. Seismic inversion, Kirchoff migration, ray tracing, finite difference methods. Exercises.
    • John Scales and Martin Smith. DRAFT: Geophysical inverse theory.
      http://landau.Mines.EDU/ samizdat/inverse theory/, 1997. M2. Presents a Bayesian approach to inverse theory. Exercises.
    • Gilbert Strang. Linear Algebra and its Applications. Harcourt Brace Jovanovich Inc., Fort Worth, third edition, 1988.
      M1. This is a textbook on linear algebra at a slightly higher level than the typical introductory course. Contains a good discussion of the SVD. Exercises.
    • A. N. Tikhonov and V. Y. Arsenin. Solutions of Ill-Posed Problems. John Wiley, New York, 1977.
      M3. The definitive treatment of the theory of Tikhonov regularization.
    • Albert Tarantola. Inverse Problem Theory: Methods for Data Fitting
      and Model Parameter Estimation. Elsevier, New York, 1987. M3. This book describes a Bayesian approach to discrete and continuous inverse problems.
    • S. Twomey. Introduction to the Mathematics of Inversion in Remote
      Sensing and Indirect Measurements. Elsevier, Amsterdam, 1977. M1.5. Mathematical background, quadrature, Tikhonov regularization, examples. No exercises. This book has recently been republished by Dover.
    • J. M. Varah. A practical examination of some numerical methods for
      linear discrete ill-posed problems. SIAM Review, 21:100-111, 1979. M2. This paper compares a variety of methods for solving discrete linear inverse problems.
    • Grace Wahba. Spline Models for Observational Data. SIAM, Philadelphia, 1990.
      M3. Although this book is largely about fitting splines to data, it also contains a very useful discuss of cross validation. No exercises.
    • G. Milton Wing. A Primer on Integeral Equations of the First Kind. SIAM, Philadelphia, 1991.
      M2. This book provides an introduction to theory and methods for the practical solution of integral equations of the first kind.
  • A Reading list in inverse problems
  • Material from Numerical Recipes in C : The Art of Scientific Computing (1993) by William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling
    • Craig, I.J.D., and Brown, J.C. 1986, Inverse Problems in Astronomy(Bristol, U.K.: Adam Hilger).
    • Twomey, S. 1977, Introduction to the Mathematics of Inversion in Remote Sensing and Indirect
    • Measurements (Amsterdam: Elsevier).
    • Tikhonov, A.N., and Arsenin, V.Y. 1977, Solutions of Ill-Posed Problems(New York: Wiley).
    • Tikhonov, A.N., and Goncharsky, A.V. (eds.) 1987, Ill-Posed Problems in the Natural Sciences (Moscow: MIR).
    • Parker, R.L. 1977, Annual Review of Earth and Planetary Science, vol. 5, pp. 35-64.
    • Frieden, B.R. 1975, in Picture Processing and Digital Filtering, T.S. Huang, ed. (New York: Springer-Verlag).
    • Tarantola, A. 1987, Inverse Problem Theory (Amsterdam: Elsevier).
    • Baumeister, J. 1987, Stable Solution of Inverse Problems(Braunschweig, Germany: Friedr. Vieweg & Sohn) [mathematically oriented].
    • Titterington, D.M. 1985, Astronomy and Astrophysics, vol. 144, pp. 381-387.
    • Jeffrey, W., and Rosner, R. 1986, Astrophysical Journal, vol. 310, pp. 463-472.
    • 18.5 Linear Regularization Methods

Last Updated: $Date: 2024/01/18 19:43:04 $