General convergent expectation maximization (EM)-type algorithms for image reconstruction

Ming Yan; Alex A. T. Bui; Jason Cong; Luminita A. Vese

doi:10.3934/ipi.2013.7.1007

Article Contents

2013, Volume 7, Issue 3: 1007-1029. Doi: 10.3934/ipi.2013.7.1007

This issue Previous Article The single-grid multilevel method and its applications Next Article Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm

General convergent expectation maximization (EM)-type algorithms for image reconstruction

1.
Department of Mathematics, University of California, Los Angeles, Los Angeles, CA 90095
2.
Department of Radiological Sciences, University of California, Los Angeles, Los Angeles, CA 90095
3.
Department of Computer Sciences, University of California, Los Angeles, Los Angeles, CA 90095
4.
Department of Mathematics, University of California, Los Angeles, Los Angeles, CA 90095-1555

Received: July 2012

Revised: May 2013

Published: August 2013

Abstract / Introduction Related Papers Cited by

Abstract

Obtaining high quality images is very important in many areas of applied sciences, such as medical imaging, optical microscopy, and astronomy. Image reconstruction can be considered as solving the ill-posed and inverse problem $y=Ax+n$, where $x$ is the image to be reconstructed and $n$ is the unknown noise. In this paper, we propose general robust expectation maximization (EM)-type algorithms for image reconstruction. Both Poisson noise and Gaussian noise types are considered. The EM-type algorithms are performed using iteratively EM (or SART for weighted Gaussian noise) and regularization in the image domain. The convergence of these algorithms is proved in several ways: EM with a priori information and alternating minimization methods. To show the efficiency of EM-type algorithms, the application in computerized tomography reconstruction is chosen.

Keywords:

Expectation maximization (EM),
Richardson-Lucy,
simultaneous algebraic reconstruction technique (SART),
image reconstruction,
total variation (TV),
computerized tomography.

Mathematics Subject Classification: Primary: 90C30, 94A08; Secondary: 90C26, 92C55.

Citation:

Related Papers

Cited by

References

[1]	R. Acar and C. R. Vogel, Analysis of bounded variation penalty methods for ill-posed problems, Inverse Problems, 10 (1994), 1217-1229.doi: 10.1088/0266-5611/10/6/003.
[2]	R. Alicandro, A. braides and J. Shah, Free-discontinuity problems via functionals involving the $L^1$-norm of the gradient and their approximation, Interfaces and Free Boundaries, 1 (1999), 17-37.doi: 10.4171/IFB/2.
[3]	A. Andersen, Algebraic reconstruction in CT from limited views, IEEE Transactions on Medical Imaging, 8 (1989), 50-55.doi: 10.1109/42.20361.
[4]	A. Andersen and A. Kak, Simultaneous algebraic reconstruction technique (SART): A superior implementation of the ART algorithm, Ultrasonic Imaging, 6 (1984), 81-94.doi: 10.1177/016173468400600107.
[5]	C. Atkinson and J. Soria, An efficient simultaneous reconstruction technique for tomographic particle image velocimetry, Experiments in Fluids, 47 (2009), 553-568.doi: 10.1007/s00348-009-0728-0.
[6]	C. Brune, M. Burger, A. Sawatzky, T. Kosters and F. Wubbeling, Forward-Backward EM-tV methods for inverse problems with poisson noise, Preprint, august 2009.
[7]	C. Brune, A. Sawatzky and M. Burger, Bregman-EM-TV methods with application to optical nanoscopy, Lecture Notes in Computer Science, 5567 (2009), 235-246.doi: 10.1007/978-3-642-02256-2_20.
[8]	C. Brune, A. Sawatzky and M. Burger, Primal and dual Bregman methods with application to optical nanoscopy, International Journal of Computer Vision, 92 (2011), 211-229.doi: 10.1007/s11263-010-0339-5.
[9]	Y. Censor and T. Elfving, Block-iterative algorithms with diagonally scaled oblique projections for the linear feasibility problem, SIAM Journal on Matrix Analysis and Applications, 24 (2002), 40-58.doi: 10.1137/S089547980138705X.
[10]	Y. Censor, D. Gordon and R. Gordon, Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems, Parallel Computing, 27 (2001), 777-808.doi: 10.1016/S0167-8191(00)00100-9.
[11]	J. Chen, J. Cong, L. A. Vese, J. D. Villasenor, M. Yan and Y. Zou, A hybrid architecture for compressive sensing 3-D CT reconstruction, IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2 (2012), 616-625.doi: 10.1109/JETCAS.2012.2221530.
[12]	J. A. Conchello and J. G. McNally, Fast regularization technique for expectation maximization algorithm for optical sectioning microscopy, in "Proceeding of SPIE Symposium on Electronic Imaging Science and Technology," 2655 (1996), 199-208.doi: 10.1117/12.237477.
[13]	A. Dempster, N. Laird and D. Rubin, Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society Series B, 39 (1977), 1-38.
[14]	N. Dey, L. Blanc-Feraud, C. Zimmer, P. Roux, Z. Kam, J. C. Olivo-Marin and J. Zerubia, Richardson-Lucy algorithm with total variation regularization for 3D confocal microscope deconvolution, Microscopy Research and Technique, 69 (2006), 260-266.doi: 10.1002/jemt.20294.
[15]	S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, IEEE Transactions on Pattern Analysis and Machine Intelligence, 6 (1984), 721-741.doi: 10.1109/TPAMI.1984.4767596.
[16]	R. Gordon, R. Bender and G. Herman, Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography, Journal of Theoretical Biology, 29 (1970), 471-481.doi: 10.1016/0022-5193(70)90109-8.
[17]	P. J. Green, On use of the EM algorithm for penalized likelihood estimation, Journal of the Royal Statistical Society Series B, 52 (1990), 443-452.doi: 10.2307/2345668.
[18]	U. Grenander, "Tutorial in Pattern Theory," Lecture Notes Volume, Division of Applied Mathematics, Brown University, 1984.
[19]	Z. T. Harmany, R. F. Marcia and R. M. Willett, Sparse Poisson intensity reconstruction algorithms, in "Proceedings of IEEE/SP 15th Workshop on Statistical Signal Processing,'' (2009), 634-637.doi: 10.1109/SSP.2009.5278495.
[20]	G. Herman, "Fundamentals of Computerized Tomography: Image Reconstruction From Projection," Second edition. Advances in Pattern Recognition. Springer, Dordrecht, 2009.doi: 10.1007/978-1-84628-723-7.
[21]	H. Hurwitz, Entropy reduction in Bayesian analysis of measurements, Physics Review A, 12 (1975), 698-706.doi: 10.1103/PhysRevA.12.698.
[22]	S. Jafarpour, R. Willett, M. Raginsky and R. Calderbank, Performance bounds for expander-based compressed sensing in the presence of Poisson noise, in "Proceedings of the IEEE Forty-Third Asilomar Conference on Signals, Systems and Computers," (2009), 513-517.doi: 10.1109/ACSSC.2009.5469879.
[23]	X. Jia, Y. Lou, R. Li, W. Y. Song and S. B. Jiang, GPU-based fast cone beam CT reconstruction from undersampled and noisy projection data via total variation, Medical Physics, 37 (2010), 1757-1760.doi: 10.1118/1.3371691.
[24]	M. Jiang and G. Wang, Convergence of the simultaneous algebraic reconstruction technique (SART), IEEE Transaction on Image Processing, 12 (2003), 957-961.doi: 10.1109/TIP.2003.815295.
[25]	M. Jiang and G. Wang, Convergence studies on iterative algorithms for image reconstruction, IEEE Transactions on Medical Imaging, 22 (2003), 569-579.doi: 10.1109/TMI.2003.812253.
[26]	S. Joshi and M. I. Miller, Maximum a posteriori estimation with Good's roughness for three-dimensional optical sectioning microscopy, Journal of the Optical Society of America A, 10 (1993), 1078-1085.doi: 10.1364/JOSAA.10.001078.
[27]	M. Jung, E. Resmerita and L. A. Vese, Dual norm based iterative methods for image restoration, Journal of Mathematical Imaging and Vision, 44 (2012), 128-149.doi: 10.1007/s10851-011-0318-7.
[28]	A. Kak and M. Slaney, "Principles of Computerized Tomographic Imaging," Reprint of the 1988 original. Classics in Applied Mathematics, 33. Society of Industrial and Applied Mathematics(SIAM), Philadelphia, PA, 2001.doi: 10.1137/1.9780898719277.
[29]	W. Karush, "Minima of Functions of Several Variables With Inequalities as Side Constraints,'' Master's thesis, Department of Mathematics, University of Chicago, Chicago, Illinois, 1939.
[30]	H. Kuhn and A. Tucker, Nonlinear programming, in "Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability," 1950, pp. 481–492. University of California Press, Berkeley and Los Angeles, 1951.
[31]	T. Le, R. Chartrand and T. J. Asaki, A variational approach to reconstructing images corrupted by Poisson noise, Journal of Mathematical Imaging and Vision, 27 (2007), 257-263.doi: 10.1007/s10851-007-0652-y.
[32]	E. Levitan and G. T. Herman, A maximum a posteriori probability expectation maximization algorithm for image reconstruction in emission tomography, IEEE Transactions on Medial Imaging, 6 (1987), 185-192.doi: 10.1109/TMI.1987.4307826.
[33]	L. B. Lucy, An iterative technique for the rectification of observed distributions, Astronomical Journal, 79 (1974), 745-754.doi: 10.1086/111605.
[34]	J. Markham and J. A. Conchello, Fast maximum-likelihood image-restoration algorithms for three-dimensional fluorescence microscopy, Journal of the Optical Society America A, 18 (2001), 1062-1071.doi: 10.1364/JOSAA.18.001062.
[35]	F. Natterer and F. Wubbeling, "Mathematical Methods in Image Reconstruction," SIAM Monographs on Mathematical Modeling and Computation. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001.doi: 10.1137/1.9780898718324.
[36]	Y. Pan, R. Whitaker, A. Cheryauka and D. Ferguson, Feasibility of GPU-assisted iterative image reconstruction for mobile C-arm CT, in "Proceedings of International Society for Photonics and Optonics,'' SPIE, 7258 (2009), 72585J.doi: 10.1117/12.812162.
[37]	W. H. Richardson, Bayesian-based iterative method of image restoration, Journal of the Optical Society America, 62 (1972), 55-59.doi: 10.1364/JOSA.62.000055.
[38]	L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.doi: 10.1016/0167-2789(92)90242-F.
[39]	S. Setzer, G. Steidl and T. Teuber, Deblurring Poissonian images by split Bregman techniques, Journal of Visual Communication and Image Representation, 21 (2010), 193-199.doi: 10.1016/j.jvcir.2009.10.006.
[40]	H. Shah, A common framework for curve evolution, segmentation and anisotropic diffusion, in "Proceeding of IEEE Conference on Computer Vision and Pattern Recognition," (1996), 136-142.doi: 10.1109/CVPR.1996.517065.
[41]	L. Shepp and B. Logan, The Fourier reconstruction of a head section, IEEE Transaction on Nuclear Science, 21 (1974), 21-34.doi: 10.1109/TNS.1974.6499235.
[42]	L. Shepp and Y. Vardi, Maximum likelihood reconstruction for emission tomography, IEEE Transaction on Medical Imaging, 1 (1982), 113-122.doi: 10.1109/tmi.1982.4307558.
[43]	R. Siddon, Fast calculation of the exact radiological path for a three-dimensional CT array, Medical Physics, 12 (1985), 252-255.doi: 10.1118/1.595715.
[44]	E. Y. Sidky, R. Chartrand and X. Pan, Image reconstruction from few views by non-convex optimization, in "IEEE Nuclear Science Symposium Conference Record,'' 5 (2007), 3526-3530. .doi: 10.1109/NSSMIC.2007.4436889.
[45]	E. Y Sidky, J. H. Jorgensen and X. Pan, Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle-Pock algorithm, Physics in Medicine and Biology, 57 (2012), 3065.doi: 10.1088/0031-9155/57/10/3065.
[46]	A. N. Tychonoff and V. Y. Arsenin, "Solution of Ill-posed Problems," Winston & Sons, Washington, 1977.
[47]	J. Wang and Y. Zheng, On the convergence of generalized simultaneous iterative reconstruction algorithms, IEEE Transaction on Image Processing, 16 (2007), 1-6.doi: 10.1109/TIP.2006.887725.
[48]	R. M. Willett, Z. T. Harmany and R. F. Marcia, Poisson image reconstruction with total variation regularization, Proceedings of 17th IEEE International Conference on Image Processing, (2010), 4177-4180.doi: 10.1109/ICIP.2010.5649600.
[49]	M. Yan and L. A. Vese, Expectation maximization and total variation based model for computed tomography reconstruction from undersampled data, in "Proceeding of SPIE Medical Imaging: Physics of Medical Imaging," 7961 (2011), 79612X.doi: 10.1117/12.878238.
[50]	M. Yan, Convergence analysis of SART: Optimization and statistics, International Journal of Computer Mathematics, 90 (2013), 30-47.doi: 10.1080/00207160.2012.709933.
[51]	M. Yan, J. Chen, L. A. Vese, J. D. Villasenor, A. A. T. Bui and J. Cong, EM+TV based reconstruction for cone-beam CT with reduced radiation, in "Lecture Notes in Computer Science," 6938 (2011), 1-10.doi: 10.1007/978-3-642-24028-7_1.
[52]	H. Yu and G. Wang, SART-type image reconstruction from a limited number of projections with the sparsity constraint, Journal of Biomedical Imaging, 2010 (2010), 1-9.doi: 10.1155/2010/934847.
[53]	H. Zhao and A. J. Reader, Fast ray-tracing technique to calculate line integral paths in voxel arrays, in IEEE Nuclear Science Symposium Conference Record, 4 (2003), 2808-2812.doi: 10.1109/NSSMIC.2003.1352469.
[54]	D. Zhu, M. Razaz and R. Lee, Adaptive penalty likelihood for reconstruction of multi-dimensional confocal microscopy images, Computerized Medical Imaging and Graphics, 29 (2005), 319-331.doi: 10.1016/j.compmedimag.2004.12.004.
[55]	Compressive Sensing Resources, http://dsp.rice.edu/cs.