×

Primal-dual algorithms for total variation based image restoration under Poisson noise. (English) Zbl 1403.65029

Summary: We consider the problem of restoring images corrupted by Poisson noise. Under the framework of maximum a posteriori estimator, the problem can be converted into a minimization problem where the objective function is composed of a Kullback-Leibler (KL)-divergence term for the Poisson noise and a total variation (TV) regularization term. Due to the logarithm function in the KL-divergence term, the non-differentiability of TV term and the positivity constraint on the images, it is not easy to design stable and efficiency algorithm for the problem. Recently, many researchers proposed to solve the problem by alternating direction method of multipliers (ADMM). Since the approach introduces some auxiliary variables and requires the solution of some linear systems, the iterative procedure can be complicated. Here we formulate the problem as two new constrained minimax problems and solve them by Chambolle-Pock’s first order primal-dual approach. The convergence of our approach is guaranteed by their theory. Comparing with ADMM approaches, our approach requires about half of the auxiliary variables and is matrix-inversion free. Numerical results show that our proposed algorithms are efficient and outperform the ADMM approach.

MSC:

65K10 Numerical optimization and variational techniques
68U10 Computing methodologies for image processing
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andrew H, Hunt B. Digital Image Restoration. Englewood Cliffs: Prentice-Hall, 1977 · Zbl 0379.62098
[2] Bardsley J, Goldes J. Regularization parameter selection methods for ill-posed Poisson maximum likelihood estimation. Inverse Probl, 2009, 25: 095005 · Zbl 1176.68225 · doi:10.1088/0266-5611/25/9/095005
[3] Bardsley J, Goldes J. An iterative method for edge-preserving MAP estimation when data-noise is Poisson. SIAM J Sci Comput, 2010, 32: 171-185 · Zbl 1215.65116 · doi:10.1137/080726884
[4] Bertero M, Boccacci P, Desiderà G, et al. Image deblurring with poisson data: From cells to galaxies. Inverse Probl, 2009, 25: 123006 · Zbl 1186.85001 · doi:10.1088/0266-5611/25/12/123006
[5] Bertsekas D. Convex Optimization Theory. Belmont: Athena Scientific, 2009 · Zbl 1242.90001
[6] Blomgren P, Chan T. Color TV: Total variation methods for restoration of vector-valued images. IEEE Trans Image Process, 1998, 7: 304-309 · doi:10.1109/83.661180
[7] Bovik A. Handbook of image and video processing. New York: Academic Press, 2010 · Zbl 0967.68155
[8] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn, 2011, 3: 1-122 · Zbl 1229.90122 · doi:10.1561/2200000016
[9] Brune, C.; Sawatzky, A.; Burger, M., Bregman-EM-TV methods with application to optical nanoscopy, 235-246 (2009), New York · doi:10.1007/978-3-642-02256-2_20
[10] Brune C, Sawatzky A, Burger M. Primal and dual Bregman methods with application to optical nanoscopy. Internat J Comput Vision, 2011, 92: 211-229 · Zbl 1235.94016 · doi:10.1007/s11263-010-0339-5
[11] Chambolle A. An algorithm for total variation minimization and applications. J Math Imaging Vision, 2004, 20: 89-97 · Zbl 1366.94048 · doi:10.1023/B:JMIV.0000011320.81911.38
[12] Chambolle A, Pock T. A first-order primal-dual algorithm for convex problems with applications to imaging. J Math Imaging Vision, 2011, 40: 120-145 · Zbl 1255.68217 · doi:10.1007/s10851-010-0251-1
[13] Chan R, Yang H, Zeng T. A two-stage image segmentation method for blurry images with poisson or multiplicative gamma noise. SIAM J Imaging Sci, 2014, 7: 98-127 · Zbl 1297.65066 · doi:10.1137/130920241
[14] Chan R, Chen K. Multilevel algorithm for a Poisson noise removal model with total-variation regularization. Int J Comput Math, 2007, 84: 1183-1198 · Zbl 1124.65057 · doi:10.1080/00207160701450390
[15] Chen G, Teboulle M. A proximal-based decomposition method for convex minimization problems. Math Program Ser A, 1994, 64: 81-101 · Zbl 0823.90097 · doi:10.1007/BF01582566
[16] Combettes P, Pesquet J. A proximal decomposition method for solving convex variational inverse problems. Inverse Problems, 2008, 24: 065014 · Zbl 1154.49025 · doi:10.1088/0266-5611/24/6/065014
[17] Dupe F, Fadili J, Starck J. A proximal iteration for deconvolving poisson noisy images using sparse representations. IEEE Trans Image Process, 2009, 18: 310-321 · Zbl 1371.94117 · doi:10.1109/TIP.2008.2008223
[18] Eckstein J, Bertsekas D. On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math Program Ser A, 1992, 55: 293-318 · Zbl 0765.90073 · doi:10.1007/BF01581204
[19] Fessler J, Booth S. Conjugate-gradient preconditioning methods for shift-variant pet image reconstruction. Image Process IEEE Trans, 1999, 8: 688-699 · Zbl 1099.94502 · doi:10.1109/83.760336
[20] Fessler J, Lee S, Olafsson V, et al. Toeplitz-based iterative image reconstruction for mri with correction for magnetic field inhomogeneity. Signal Process IEEE Trans, 2005, 53: 3393-3402 · Zbl 1370.94033 · doi:10.1109/TSP.2005.853152
[21] Figueiredo M, Bioucas-Dias J. Restoration of Poissonian images using alternating direction optimization. IEEE Trans Image Process, 2010, 19: 3133-3145 · Zbl 1371.94128 · doi:10.1109/TIP.2010.2053941
[22] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput Math Appl, 1976, 2: 17-40 · Zbl 0352.65034 · doi:10.1016/0898-1221(76)90003-1
[23] Goldstein T, Osher S. The split Bregman method for L1 regularized problems. SIAM J Imaging Sci, 2009, 2: 323-343 · Zbl 1177.65088 · doi:10.1137/080725891
[24] Hansen P. Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion. Philadelphia: SIAM, 1998 · Zbl 0890.65037
[25] He B, Yuan X. On the o(1/n) convergence rate of the Douglas-Rachford alternating direction method. SIAM J Numer Anal, 2012, 50: 700-709 · Zbl 1245.90084 · doi:10.1137/110836936
[26] Le T, Chartrand R, Asaki T J. A variational approach to reconstructing images corrupted by Poisson noise. J Math Imaging Vision, 2007, 27: 257-263 · doi:10.1007/s10851-007-0652-y
[27] Lucy L. An iterative technique for the rectification of observed distributions. Astron J, 1974, 79: 745-754 · doi:10.1086/111605
[28] Murtagh F, Starck J. Astronomical Image and Data Analysis. New York: Springer, 2006 · Zbl 1010.68208
[29] Ng M, Chan R, Tang W. A fast algorithm for deblurring models with Neumann boundary conditions. SIAM J Sci Comput, 1999, 21: 851-866 · Zbl 0951.65038 · doi:10.1137/S1064827598341384
[30] Puetter R, Gosnell T, Yahil A. Digital image reconstruction: Deblurring and denoising. Annu Rev Astron Astrophys, 2005, 43: 139-194 · doi:10.1146/annurev.astro.43.112904.104850
[31] Richarson W. Bayesian-based iterative method of image restoration. J Opt Soc Amer A, 1972, 62: 55-59 · doi:10.1364/JOSA.62.000055
[32] Rockafellar R. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math Oper Res, 1976, 1: 97-116 · Zbl 0402.90076 · doi:10.1287/moor.1.2.97
[33] Rockafellar R. Monotone operators and the proximal point algorithm. SIAM J Control Optim, 1976, 14: 877-898 · Zbl 0358.90053 · doi:10.1137/0314056
[34] Rudin L, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms. Physica D, 1992, 60: 259-268 · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F
[35] Setzer S, Steidl G, Teuber T. Deblurring Poissonian images by split Bregman techniques. J Vis Comm Image Represent, 2010, 21: 193-199 · doi:10.1016/j.jvcir.2009.10.006
[36] Setzer S, Steidl G, Teuber T. Infimal convolution regularizations with discrete l1-type functionals. Comm Math Sci, 2011, 9: 797-872 · Zbl 1269.49063 · doi:10.4310/CMS.2011.v9.n3.a7
[37] Snyder D, Hammoud A, White R. Image recovery from data acquired with a charge-coupled-device camera. JOSA A, 1993, 10: 1014-1023 · doi:10.1364/JOSAA.10.001014
[38] Tai, X.; Wu, C., Augmented Lagrangian method, dual methods and split Bregman iteration for ROF model, 502-513 (2009), New York · Zbl 1371.94362 · doi:10.1007/978-3-642-02256-2_42
[39] Timmermann K, Nowak R. Multiscale modeling and estimation of Poisson processes with application to photon-limited imaging. IEEE Trans Inform Theory, 1999, 45: 846-862 · Zbl 0947.94005 · doi:10.1109/18.761328
[40] Tseng P. Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J Control Optim, 1991, 29: 119-138 · Zbl 0737.90048 · doi:10.1137/0329006
[41] Wernick M, Aarsvold J. Emission Tomography: The Fundamentals of PET and SPECT. New York: Academic Press, 2004 · Zbl 0737.90048
[42] Willett R, Nowak R. Platelets: A multiscale approach for recovering edges and surfaces in photon-limited medical imaging. IEEE Trans Medical Imaging, 2003, 22: 332-350 · doi:10.1109/TMI.2003.809622
[43] Yin W, Osher S, Goldfarb D, et al. Bregman iterative algorithms for ℓ1-minimization with applications to compressed sensing. SIAM J Imaging Sci, 2008, 1: 143-168 · Zbl 1203.90153 · doi:10.1137/070703983
[44] Zanella R, Boccacci P, Zanni L, et al. Efficient gradient projection methods for edge-preserving removal of Poisson noise. Inverse Problems, 2009, 25: 045010 · Zbl 1163.65042 · doi:10.1088/0266-5611/25/4/045010
[45] Zhou W, Bovik A, Sheikh H, et al. Image quality assessment: From error visibility to structural similarity. IEEE Trans Image Process, 2004, 13: 600-612 · doi:10.1109/TIP.2003.819861
[46] Zhu M. Fast Numerical Algorithms for Total Variation Based Image Restoration. PhD thesis. Los Angeles: University of California, 2008 · Zbl 0358.90053
[47] Zhu, M.; Chan, T., An efficient primal-dual hybrid gradient algorithm for total variation image restoration, 08-34 (2007)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.