Bilevel optimization for calibrating point spread functions in blind deconvolution

Michael  Hintermüller; Tao  Wu

doi:10.3934/ipi.2015.9.1139

Article Contents

2015, Volume 9, Issue 4: 1139-1169. Doi: 10.3934/ipi.2015.9.1139

This issue Previous Article Locally sparse reconstruction using the $l^{1,\infty}$-norm Next Article Iterative choice of the optimal regularization parameter in TV image restoration

Bilevel optimization for calibrating point spread functions in blind deconvolution

Michael Hintermüller^1, and
Tao Wu^1,

1.
Department of Mathematics, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin

Received: September 30, 2014

Revised: February 28, 2015

Published: October 2015

Abstract Related Papers Cited by

Abstract

Blind deconvolution problems arise in many imaging modalities, where both the underlying point spread function, which parameterizes the convolution operator, and the source image need to be identified. In this work, a novel bilevel optimization approach to blind deconvolution is proposed. The lower-level problem refers to the minimization of a total-variation model, as is typically done in non-blind image deconvolution. The upper-level objective takes into account additional statistical information depending on the particular imaging modality. Bilevel problems of such type are investigated systematically. Analytical properties of the lower-level solution mapping are established based on Robinson's strong regularity condition. Furthermore, several stationarity conditions are derived from the variational geometry induced by the lower-level problem. Numerically, a projected-gradient-type method is employed to obtain a Clarke-type stationary point and its convergence properties are analyzed. We also implement an efficient version of the proposed algorithm and test it through the experiments on point spread function calibration and multiframe blind deconvolution.

Keywords:

Image processing,
blind deconvolution,
bilevel optimization,
mathematical programs with equilibrium constraints,
projected gradient method.

Mathematics Subject Classification: 49J53, 65K10, 90C30, 94A08.

Citation:

Related Papers

Cited by

References

[1]	M. S. C. Almeida and L. B. Almeida, Blind and semi-blind deblurring of natural images, IEEE Trans. Image Process., 19 (2010), 36-52.doi: 10.1109/TIP.2009.2031231.
[2]	G. Aubert and P. Kornprobst, Mathematical Problems in Image Processing, Springer, New York, 2002.
[3]	J. Bardsley, S. Jefferies, J. Nagy and R. Plemmons, A computational method for the restoration of images with an unknown, spatially-varying blur, Opt. Express, 14 (2006), 1767-1782.doi: 10.1364/OE.14.001767.
[4]	M. Burger and O. Scherzer, Regularization methods for blind deconvolution and blind source separation problems, Math. Control Signals Systems, 14 (2001), 358-383.doi: 10.1007/s498-001-8041-y.
[5]	J.-F. Cai, H. Ji, C. Liu and Z. Shen, Blind motion deblurring using multiple images, J. Comput. Phys., 228 (2009), 5057-5071.doi: 10.1016/j.jcp.2009.04.022.
[6]	P. Campisi and K. Egiazarian, eds., Blind image deconvolution: Theory and applications, CRC press, Boca Raton, FL, 2007.doi: 10.1201/9781420007299.
[7]	A. S. Carasso, Direct blind deconvolution, SIAM J. Appl. Math., 61 (2001), 1980-2007.doi: 10.1137/S0036139999362592.
[8]	_________, The APEX method in image sharpening and the use of low exponent Lévy stable laws, SIAM J. Appl. Math., 63 (2002), 593-618.doi: 10.1137/S0036139901389318.
[9]	_________, APEX blind deconvolution of color Hubble space telescope imagery and other astronomical data, Optical Engineering, 45 (2006), 107004.
[10]	_________, False characteristic functions and other pathologies in variational blind deconvolution: A method of recovery, SIAM J. Appl. Math., 70 (2009), 1097-1119.doi: 10.1137/080737769.
[11]	A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40 (2011), 120-145.doi: 10.1007/s10851-010-0251-1.
[12]	T. F. Chan and J. Shen, Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods, SIAM, Philadelphia, 2005.doi: 10.1137/1.9780898717877.
[13]	T. F. Chan and C.-K. Wong, Total variation blind deconvolution, IEEE Trans. Image Process., 7 (1998), 370-375.doi: 10.1109/83.661187.
[14]	R. Chartrand and W. Yin, Iteratively reweighted algorithms for compressive sensing, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 2008, 3869-3872.
[15]	S. Cho, Y. Matsushita and S. Lee, Removing non-uniform motion blur from images, in IEEE 11th International Conference on Computer Vision, 2007, 1-8.doi: 10.1109/ICCV.2007.4408904.
[16]	J. C. De los Reyes and C.-B. Schönlieb, Image denoising: Learning the noise model via nonsmooth PDE-constrained optimization, Inverse Problems and Imaging, 7 (2013), 1183-1214.doi: 10.3934/ipi.2013.7.1183.
[17]	A. L. Dontchev and R. T. Rockafellar, Robinson's implicit function theorem and its extensions, Math. Program., Ser. B, 117 (2009), 129-147.doi: 10.1007/s10107-007-0161-1.
[18]	D. A. Fish, A. M. Brinicombe and E. R. Pike, Blind deconvolution by means of the Richardson-Lucy algorithm, J. Opt. Soc. Am. A, 12 (1995), 58-65.doi: 10.1364/JOSAA.12.000058.
[19]	R. Fletcher, S. Leyffer, D. Ralph and S. Scholtes, Local convergence of SQP methods for mathematical programs with equilibrium constraints, SIAM J. Optim., 17 (2006), 259-286.doi: 10.1137/S1052623402407382.
[20]	R. W. Freund and N. M. Nachtigal, QMR: A quasi-minimal residual method for non-Hermitian linear systems, Numer. Math., 60 (1991), 315-339.doi: 10.1007/BF01385726.
[21]	M. Fukushima, Z.-Q. Luo and J.-S. Pang, A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints, Comput. Optim. Appl., 10 (1998), 5-34.doi: 10.1023/A:1018359900133.
[22]	E. M. Gafni and D. P. Bertsekas, Convergence of a Gradient Projection Method, Laboratory for Information and Decision Systems Report LIDS-P-1201, Massachusetts Institute of Technology, 1982.
[23]	L. He, A. Marquina and S. J. Osher, Blind deconvolution using TV regularization and Bregman iteration, International Journal of Imaging Systems and Technology, 15 (2005), 74-83.doi: 10.1002/ima.20040.
[24]	M. Hintermüller and I. Kopacka, Mathematical programs with complementarity constraints in function space: C- and strong stationarity and a path-following algorithm, SIAM J. Optim., 20 (2009), 868-902.doi: 10.1137/080720681.
[25]	M. Hintermüller and K. Kunisch, Total bounded variation regularization as a bilaterally constrained optimization problem, SIAM J. Appl. Math., 64 (2004), 1311-1333.doi: 10.1137/S0036139903422784.
[26]	M. Hintermüller and G. Stadler, An infeasible primal-dual algorithm for total bounded variation-based inf-convolution-type image restoration, SIAM J. Sci. Comput., 28 (2006), 1-23.doi: 10.1137/040613263.
[27]	M. Hintermüller and T. Surowiec, A bundle-free implicit programming approach for a class of MPECs in function space, preprint, 2014.
[28]	M. Hintermüller and T. Wu, Nonconvex $TV^q$-models in image restoration: Analysis and a trust-region regularization-based superlinearly convergent solver, SIAM J. Imaging Sci., 6 (2013), 1385-1415.doi: 10.1137/110854746.
[29]	_________, A superlinearly convergent $R$-regularized Newton scheme for variational models with concave sparsity-promoting priors, Comput. Optim. Appl., 57 (2014), 1-25.doi: 10.1007/s10589-013-9583-2.
[30]	K. Ito and K. Kunisch, An active set strategy based on the augmented Lagrangian formulation for image restoration, Mathematical Modelling and Numerical Analysis, 33 (1999), 1-21.doi: 10.1051/m2an:1999102.
[31]	L. Justen, Blind Deconvolution: Theory, Regularization and Applications, Ph.D. thesis, University of Bremen, 2006.
[32]	L. Justen and R. Ramlau, A non-iterative regularization approach to blind deconvolution, Inverse Problems, 22 (2006), 771-800.doi: 10.1088/0266-5611/22/3/003.
[33]	D. Kundur and D. Hatzinakos, Blind image deconvolution, IEEE Signal Process. Mag., 13 (1996), 43-64.doi: 10.1109/79.489268.
[34]	________, Blind image deconvolution revisited, IEEE Signal Process. Mag., 13 (1996), 61-63.
[35]	K. Kunisch and T. Pock, A bilevel optimization approach for parameter learning in variational models, SIAM J. Imaging Sci., 6 (2013), 938-983.doi: 10.1137/120882706.
[36]	A. Levin, Blind motion deblurring using image statistics, Advances in Neural Information Processing Systems, 19 (2006), 841-848.
[37]	A. B. Levy, Solution sensitivity from general principles, SIAM J. Control Optim., 40 (2001), 1-38.doi: 10.1137/S036301299935211X.
[38]	Z.-Q. Luo, J.-S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, 1996.doi: 10.1017/CBO9780511983658.
[39]	B. S. Mordukhovich, Variational Analysis and Generalized Differentiation, I: Basic Theory, II: Applications, Springer, 2006.
[40]	J. Nocedal and S. Wright, Numerical optimization, 2nd ed., Springer, New York, 2006.
[41]	J. Outrata, M. Kocvara and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998.doi: 10.1007/978-1-4757-2825-5.
[42]	J. V. Outrata, A generalized mathematical program with equilibrium constraints, SIAM J. Control Optim., 38 (2000), 1623-1638.doi: 10.1137/S0363012999352911.
[43]	S. M. Robinson, Strongly regular generalized equations, Math. Oper. Res., 5 (1980), 43-62.doi: 10.1287/moor.5.1.43.
[44]	________, Local structure of feasible sets in nonlinear programming, Part III: Stability and sensitivity, Math. Programming Stud., 30 (1987), 45-66.
[45]	R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer, New York, 1998.doi: 10.1007/978-3-642-02431-3.
[46]	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.
[47]	H. Scheel and S. Scholtes, Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity, Math. Oper. Res., 25 (2000), 1-22.doi: 10.1287/moor.25.1.1.15213.
[48]	S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim., 11 (2001), 918-936.doi: 10.1137/S1052623499361233.
[49]	Q. Shan, J. Jia and A. Agarwala, High-quality motion deblurring from a single image, ACM T. Graphic, 27 (2008), p73.doi: 10.1145/1399504.1360672.
[50]	A. Shapiro, Sensitivity analysis of parameterized variational inequalities, Math. Oper. Res., 30 (2005), 109-126.doi: 10.1287/moor.1040.0115.
[51]	J. J. Ye, Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints, J. Math. Anal. Appl., 307 (2005), 350-369.doi: 10.1016/j.jmaa.2004.10.032.
[52]	J. J. Ye, D. L. Zhu and Q. J. Zhu, Exact penalization and necessary optimality conditions for generalized bilevel programming problems, SIAM J. Optim., 7 (1997), 481-507.doi: 10.1137/S1052623493257344.
[53]	Y.-L. You and M. Kaveh, A regularization approach to joint blur identification and image restoration, IEEE Trans. Image Process., 5 (1996), 416-428.