Explainable bilevel optimization: An application to the Helsinki deblur challenge

Silvia Bonettini; Giorgia Franchini; Danilo Pezzi; Marco Prato

doi:10.3934/ipi.2022055

Article Contents

2023, Volume 17, Issue 5: 925-950. Doi: 10.3934/ipi.2022055

This issue Previous Article In Focus - hybrid deep learning approaches to the HDC2021 challenge Next Article Improving image deblurring

Explainable bilevel optimization: An application to the Helsinki deblur challenge

1.
Dipartimento di Scienze Fisiche, Informatiche e Matematiche, Università di Modena e Reggio Emilia, Via Campi 213/b - 41125 Modena (MO), Italy

^*Corresponding author: Silvia Bonettini
^*Corresponding author: Silvia Bonettini

Received: June 2022

Revised: October 2022

Early access: October 2022

Published: October 2023

All the authors are members of the INdAM research group GNCS

Abstract / Introduction Full Text(HTML) Figure(6) / Table(3) Related Papers Cited by

Abstract

In this paper we present a bilevel optimization scheme for the solution of a general image deblurring problem, in which a parametric variational-like approach is encapsulated within a machine learning scheme to provide a high quality reconstructed image with automatically learned parameters. The ingredients of the variational lower level and the machine learning upper one are specifically chosen for the Helsinki Deblur Challenge 2021, in which sequences of letters are asked to be recovered from out-of-focus photographs with increasing levels of blur. Our proposed procedure for the reconstructed image consists in a fixed number of FISTA iterations applied to the minimization of an edge preserving and binarization enforcing regularized least-squares functional. The parameters defining the variational model and the optimization steps, which, unlike most deep learning approaches, all have a precise and interpretable meaning, are learned via either a similarity index or a support vector machine strategy. Numerical experiments on the test images provided by the challenge authors show significant gains with respect to a standard variational approach and performances comparable with those of some of the proposed deep learning based algorithms which require the optimization of millions of parameters.

Keywords:

Mathematics Subject Classification: Primary: 65K10, 47A52; Secondary: 90C30.

Citation:

Full Text(HTML)

Figure 1. Projection-like function: plot of the function (10) for different choices of the parameters $ \epsilon $. The dashed line represents the Euclidean projector, while the dash-dot line is for the interior barrier projection proposed in [7] with parameter $ 10^{-4} $

Download: Full-size image PowerPoint slide

Figure 2. Dataset definition for the SSIM loss function. Upper row: original HDC data from step 10, Times New Roman, image n.51, CAM1 (a) and CAM2 (b). Middle row: estimated background, represented as an image (c) and as a surface (d). Bottom row: estimated distortion. Panel (e) shows the binarized reconstruction (light blue) of image (b) obtained with a variational method and the edges of the binarized version of (a) (red). The white lines correspond to the pixels where the two images are superimposed. In panel (f), the red edges are obtained after applying the estimated radial distortion to (a)

Download: Full-size image PowerPoint slide

Figure 3. Samples from the SVR training dataset. (A) Noisy image from the step 4 of the Helsinki dataset (OCR score = 52); (B) Synthetic image blurred with a disc PSF of radius 9 (OCR score = 84); (C) Reconstruction with wrong parameters for the variational model (OCR score = 11)

Download: Full-size image PowerPoint slide

Figure 4. For each row, from left to right: ground truth, noisy sample and reconstruction using the SVR merit function with $ K = 70 $ inner iterations. From top to bottom, two images, one per font, are selected for the steps 6 and 8. The corresponding scores are shown in Table 3

Download: Full-size image PowerPoint slide

Figure 5. For each row, from left to right: ground truth, noisy sample and reconstruction using the SVR merit function with $ K = 70 $ inner iterations. From top to bottom, two images, one per font, are selected for the steps10 and 12. The corresponding scores are shown in Table 3

Download: Full-size image PowerPoint slide

Figure 6. Results of Algorithm 1 with the SSIM loss function and 60 unrolled iterations applied to some of the test images employed for the sanity check (step 6)

Download: Full-size image PowerPoint slide

Table 1. Results of the HDC published in November 2021, with our original placement. We are team number 04

Team	Step 6	Step 8	Step 10	Step 12	$ \# $parameters

15_A	94.03	93.12	93.75	91.42	$ 2.6 $ millions
12_B	92.62	92.62	85.80	85.95	$ 11 $ millions
01	91.75	91.65	88.67	87.12	$ 0.187 $ millions
11_C	87.78	81.25	79.15	62.80	$ 52 $ millions
06	94.33	85.92	70.17	0.00	$ 2.6 $ millions
13	71.12	67.12	54.38	64.83	$ 2.2 $ millions
16_B	76.45	68.35	4.03	7.42	3
04	68	62.85	24.38	10.70	4
09_B	6.33	2.27	2.62	4.03	4

| Show Table

DownLoad: CSV

Table 2. Average OCR scores obtained on the 40 test images used in Table 1, with the merit functions (14) and (18) (columns SSIM and SVR, respectively)

	$ K = 60 $		$ K = 70 $		$ K = 80 $
	SSIM	SVR	SSIM	SVR	SSIM	SVR
Step 6	85.20	85.60	85.60	82.45	85.08	83.28
Step 8	83.88	82.63	84.15	81.80	82.45	80.13
Step 10	70.88	73.90	71.35	76.30	72.72	73.23
Step 12	60.23	61.53	61.73	48.58	61.90	61.53

| Show Table

DownLoad: CSV

Table 3. Comparison between the SVR prediction and the true OCR score for the images of Figure 4 and 5

	Ground truth		Noisy sample		Reconstruction
	OCR	SVR	OCR	SVR	OCR	SVR
Step 6 Times	100	81.84	0	42.17	100	71.71
Step 6 Verdana	100	81.91	0	45.64	100	74.18
Step 8 Times	100	81.91	0	34.44	90	70.1
Step 8 Verdana	100	81.98	0	37.68	86	75.48
Step 10 Times	100	81.92	0	31.22	90	66.32
Step 10 Verdana	100	81.96	0	30.67	100	68.44
Step 12 Times	100	82.03	0	24.07	76	67.42
Step 12 Verdana	100	82.03	0	29.05	70	71.53

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Arridge, P. Maass, O. Öktem and C.-B. Schoenlieb, Solving Inverse Problems using data driven methods, Acta Numer., 28 (2019), 1-74. doi: 10.1017/S0962492919000059.
[2]	A. Auslender and M. Teboulle, Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational inequalities, Math. Prog. Series B, 120 (2009), 27-48. doi: 10.1007/s10107-007-0147-z.
[3]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), 183-202. doi: 10.1137/080716542.
[4]	M. Bertero, P. Boccacci and C. De Mol, Introduction to Inverse Problems in Imaging - 2nd edition, CRC Press, Boca Raton, 2022. doi: 10.1201/9781003032755.
[5]	M. Bertero, P. Boccacci and V. Ruggiero, Inverse Imaging with Poisson Data, IOP Publishing, Bristol, 2006.
[6]	M. Bertero, H. Lantéri and L. Zanni, Iterative image reconstruction: A point of view, in Mathematical Methods in Biomedical Imaging and Intensity-Modulated Radiation Therapy (IMRT) (eds. Y. Censor, M. Jiang and A. K. Louis), Birkhauser-Verlag, (2008), 37-63.
[7]	C. Bertocchi, E. Chouzenoux, M.-C. Courbineau, J.-C. Pesquet and M. Prato, Deep unfolding of a proximal interior point method for image restoration, Inverse Probl., 36 (2020), 034005. doi: 10.1088/1361-6420/ab460a.
[8]	S. Bonettini, F. Porta, M. Prato, S. Rebegoldi, V. Ruggiero and L. Zanni, Recent advances in variable metric first-order methods, in Computational Methods for Inverse Problems in Imaging, M. Donatelli and S. Serra-Capizzano eds., Springer INdAM Series 36 (2019), 1-31. doi: 10.1007/978-3-030-32882-5_1.
[9]	S. Bonettini and M. Prato, New convergence results for the scaled gradient projection method, Inverse Probl., 31 (2015), 095008. doi: 10.1088/0266-5611/31/9/095008.
[10]	S. Bonettini, S. Rebegoldi and V. Ruggiero, Inertial variable metric techniques for the inexact forward-backward algorithm, SIAM J. Sci. Comput., 40 (2018), A3180-A3210. doi: 10.1137/17M116001X.
[11]	S. Bonettini, R. Zanella and L. Zanni, A scaled gradient projection method for constrained image deblurring, Inverse Probl., 25 (2009), 015002. doi: 10.1088/0266-5611/25/1/015002.
[12]	A. Chambolle and Ch. Dossal, On the convergence of the iterates of the "Fast Iterative Shrinkage/Thresholding Algorithm", J. Optim. Theory Appl., 166 (2015), 968-982. doi: 10.1007/s10957-015-0746-4.
[13]	Y. Chen and T. Pock, Trainable nonlinear reaction diffusion: A flexible framework for fast and effective image restoration, IEEE Trans. Pattern Anal. Mach. Intell., 39 (2017), 1256-1272. doi: 10.1109/TPAMI.2016.2596743.
[14]	Y. Chen, R. Ranftl and T. Pock, Insights into analysis operator learning: From patch-based sparse models to higher order MRFs, IEEE Trans. Image Process., 23 (2014), 1060-1072. doi: 10.1109/TIP.2014.2299065.
[15]	J. C. Christou, D. Bonnacini, N. Ageorges and F. Marchis, Myopic deconvolution of adaptive optics images, Messenger, 97 (1999), 14-22.
[16]	J.-M. Conan, L. M. Mugnier, T. Fusco, V. Michau and G. Rousset, Myopic deconvolution of adaptive optics images by use of object and point-spread function power spectra, Appl. Optics, 37 (1998), 4614-4622. doi: 10.1364/AO.37.004614.
[17]	N. Cristianini and J. Shawe-Taylor, An Introduction to Support Vector Machines and Other Kernel-based Learning Methods, Cambridge University Press, Cambridge, 2000. doi: 10.1017/CBO9780511801389.
[18]	H. Drucker, C. J. Burges, L. Kaufman, A. Smola and V. Vapnik, Support vector regression machines, in Advances in Neural Information Processing Systems, M.C. Mozer, M. Jordan and T. Petsche eds., 9, MIT press, Boston, 1996.
[19]	F.-L. Fan, J. Xiong, M. Li and G. Wang, On interpretability of artificial neural networks: A survey, IEEE Trans. Radiat. Plasma Med. Sci., 5 (2021), 741-760. doi: 10.1109/TRPMS.2021.3066428.
[20]	M. Forte and F. Pitié, F, B, Alpha Matting, preprint, 2012, arXiv: 2003.07711.
[21]	L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi and M. Pontil, Bilevel programming for hyperparameter optimization and meta-learning, Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research, 80, PMLR, 2018, 1568-1577.
[22]	G. Franchini, V. Ruggiero, F. Porta and L. Zanni, Neural architecture search via standard machine learning methodologies, Math. Eng., 5 (2023), 1-21. doi: 10.3934/mine.2023012.
[23]	G. Franchini, V. Ruggiero and L. Zanni, Ritz-like values in steplength selections for stochastic gradient methods, Soft Computing, 24 (2020), 17573-17588. doi: 10.1007/s00500-020-05219-6.
[24]	G. Franchini, V. Ruggiero and L. Zanni, Steplength and mini-batch size selection in stochastic gradient methods, LNCS, 12566 (2020), 259-263. doi: 10.1007/978-3-030-64580-9_22.
[25]	T. Germer, T Uelwer and S. Harmeling, Deblurring Photographs of Characters Using Deep Neural Networks, preprint, 2022, arXiv: 2205.15053.
[26]	K. Gregor and Y. LeCun, Learning fast approximations of sparse coding, Proceedings of the 27th International Conference on International Conference on Machine Learning, Haifa, Israel, 2010,399-406.
[27]	J. R. Hershey, J. Le Roux and F. Weninger, Deep unfolding: Model-based inspiration of novel deep architectures, preprint, 2014, arXiv: 1409.2574.
[28]	E. Kobler, A. Effland, K. Kunisch and T. Pock, Total deep variation for linear inverse problems, in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, Seattle, WA, 2020, 7549-7558 doi: 10.1109/CVPR42600.2020.00757.
[29]	E. Kobler, A. Effland, K. Kunisch and T. Pock, Total deep variation: A stable regularization method for inverse problems, to appear, IEEE Trans. Pattern Anal. Mach. Intell. doi: 10.1109/TPAMI.2021.3124086.
[30]	B. Kosko, Noise, Viking Press, New York, 2006.
[31]	O. Kupyn, T. Martyniuk, J. Wu and Z. Wan, DeblurGAN-v2: Deblurring (orders-of-magnitude) faster and better, preprint, 2019, arXiv: 1908.03826.
[32]	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.
[33]	A. Levin, Y. Weiss, F. Durand and W. T. Freeman, Understanding blind deconvolution algorithms, IEEE Trans. Pattern Anal. Mach. Intell., 33 (2011), 2354-2367. doi: 10.1109/TPAMI.2011.148.
[34]	L. Li, Y. Yan, Z. Lu, J. Wu, K. Gu and S. Wang, No-reference quality assessment of deblurred images based on natural scene statistics, IEEE Access, 5 (2017), 2163-2171. doi: 10.1109/ACCESS.2017.2661858.
[35]	V. Monga, Y. Li and Y. C. Eldar, Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing, IEEE Signal Process. Mag., 38 (2021), 18-44. doi: 10.1109/MSP.2020.3016905.
[36]	Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program., 103 (2005), 127-152. doi: 10.1007/s10107-004-0552-5.
[37]	P. Ochs and T. Pock, Adaptive FISTA for nonconvex optimization, SIAM J. Optim., 29 (2019), 2482-2503. doi: 10.1137/17M1156678.
[38]	P. Ochs, R. Ranftl, T. Brox and T. Pock, Bilevel optimization with nonsmooth lower level problems, Scale Space and Variational Methods in Computer Vision, 2015, Lecture Notes in Computer Science, 9087, Springer, 2015,654-665. doi: 10.1007/978-3-319-18461-6_52.
[39]	R. Olaf, P. Fischer and T. Brox, U-net: Convolutional networks for biomedical image segmentation, Medical Image Computing and Computer-Assisted Intervention, 2015, Lecture Notes in Computer Science, 9351, Springer, 2015,234-241. doi: 10.1007/978-3-319-24574-4_28.
[40]	D. M. Pelt and J. A. Sethian, A mixed-scale dense convolutional neural network for image analysis, Proc. Natl. Acad. Sci. U.S.A., 115 (2018), 254-259. doi: 10.1073/pnas.1715832114.
[41]	N. A. B. Riis, Y. Dong and P. C. Hansen, Computed tomography with view angle estimation using uncertainty quantification, Inverse Probl., 37 (2021), 065007. doi: 10.1088/1361-6420/abf5ba.
[42]	Y. Romano, M. Elad and P. Milanfar, The little engine that could: Regularization by denoising (RED), SIAM J. Imaging Sci., 10 (2017), 1804-1844. doi: 10.1137/16M1102884.
[43]	S. Roth and M. J. Black, Fields of experts, Int. J. Comput. Vision, 82 (2009), 205-229. doi: 10.1007/s11263-008-0197-6.
[44]	B. Schölkopf and A. J. Smola, Learning with Kernels, MIT Press, Cambridge, 2002.
[45]	R. Schwartz, J. Dodge, N. A. Smith and O. Etzioni, Green AI, Commun. ACM, 63 (2020), 54-63. doi: 10.1145/3381831.
[46]	D. Ulyanov, A. Vedaldi and V. Lempitsky, Deep image prior, Int. J. Comput. Vision, 128 (2020), 1867-1888. doi: 10.1007/s11263-020-01303-4.
[47]	Z. Wang, A. C. Bovik, H. R. Sheikh and E. P. Simoncelli, Image quality assessment: From error visibility to structural similarity, IEEE Trans. Image Process., 13 (2004), 600-612. doi: 10.1109/TIP.2003.819861.
[48]	J. Xiang, Y Dong and Y. Yang, FISTA-Net: Learning a Fast Iterative Shrinkage Thresholding network for inverse problems in imaging, IEEE Trans. Med. Imaging, 40 (2021), 1329-1339. doi: 10.1109/TMI.2021.3054167.
[49]	R. Zanella, P. Boccacci, L. Zanni and M. Bertero, Efficient gradient projection methods for edge-preserving removal of Poisson noise, Inverse Probl., 25 (2009), 045010. doi: 10.1088/0266-5611/25/4/045010.