浏览全部资源
扫码关注微信
纸质出版日期： 2022-04-16 ，
录用日期： 2021-01-13
移动端阅览
宋田田, 潘振宽, 魏伟波, 李青. 二阶变分图像恢复模型的重启动快速ADMM方法[J]. 中国图象图形学报, 2022,27(4):1066-1083.
Tiantian Song, Zhenkuan Pan, Weibo Wei, Qing Li. Restart fast ADMM methods for second-order variational models of image restoration[J]. Journal of Image and Graphics, 2022,27(4):1066-1083.
目的
2
基于二阶导数的图像恢复变分模型可以同时保持图像边缘与光滑特征，但其规则项的非线性、非光滑性，甚至非凸性制约着其快速算法的设计。针对总拉普拉斯(total Laplacian，TL)与欧拉弹性能(Euler’s elastica，EE)两种图像恢复变分模型，在设计快速交替方向乘子法(fast alternating direction methods of multipliers，fast ADMM)的基础上引入重启动策略，以有效消除解的振荡，从而大幅提高该类模型计算效率，并为其他相近模型的快速算法设计提供借鉴。
方法
2
基于原始ADMM方法设计反映能量泛函变化的残差公式，在设计的快速ADMM方法中根据残差的变化重新设置快速算法的相关参数，以避免计算过程中的能量振荡，达到算法加速目的。
结果
2
通过大量实验发现，采用原始ADMM、快速ADMM和重启动快速ADMM算法恢复图像的峰值信噪比(peak signal-to-noise ratio，PSNR)基本一致，但计算效率有不同程度的提高。与原始ADMM算法相比，在消除高斯白噪声和椒盐噪声中，对TL模型，其快速ADMM算法分别提高6%~50%和13%~240%；重启动快速ADMM算法提高100%~433%和100%~466%；对EE模型，其快速ADMM算法分别提高14%~54%和10%~83%；重启动快速ADMM算法分别提高100%~900%和66%~800%。此外，对于不同的惩罚参数组合，相同模型的快速ADMM算法的计算效率基本相同。
结论
2
对于两种典型的二阶变分图像恢复模型，本文提出的快速重启动ADMM算法比原始ADMM算法及快速ADMM算法在计算效率方面有较大提高，计算效率对不同惩罚参数组合具有鲁棒性。本文设计的算法对于含其他形式二阶导数规则项的变分图像分析模型的重启动快速算法的设计可提供有益借鉴。
Objective
2
To develop image processing and computer vision
variational models have been widespread used in image de-noising
image segmentation and image restoration. Variational model of image restoration has a fundamental position. Variational model of image restoration can maintain the image edge and smooth features based on the second-order derivative. However
its regular terms are generally non-linear
non-smooth
or even non-convex. These features have their numerical algorithm design difficulty and the low computational efficiency of its numerical method. These features restrict the design of its fast algorithm as well. The designated acceleration method is essential to design optimal inertial parameters. The variational image processing models are often locally strongly convex or completely non-convex
which makes it difficult or time-consuming to estimate the optimal inertial parameters. Its inertial acceleration algorithms can cause ripples and fail to achieve the targeted acceleration effect. The analyzed results of developed monotonic algorithm
backtracking algorithm and restart algorithm can yield ripples phenomenon to keep algorithm convergence rate. Our research facilitates framework-based fast alternating direction methods of multipliers (ADMM) method to explore possibility of the restart fast algorithm in second-order variational models. Total-Laplacian based model (TL-based) and Euler's elastic based model (EE-based) are illustrated to develop testart fast algorithms.
Method
2
Our research demonstrated second-order variational model of image restoration with nonlinear
non-smooth TL regular terms and non-linear
non-smooth
non-convex EE regular terms. The following restart fast ADMM algorithm is developed based on the alternation of direction methods of multipliers
Nesterov's inertial acceleration method and ripples-yielded restart idea. TL model transformed into constrained equivalent convex optimization based on auxiliary variables and linear constraint equations. EE model transformed into equivalent constrained convex optimization based on auxiliary variables
linear constraint equations and relaxed nonlinear constraint equations. Restart fast ADMM algorithm determine the requirement of restarted algorithm based on the integrated residual scale. Our demonstrated restart fast ADMM algorithm can identify a reference for the context fast algorithm models. The number of iterations
total CPU running time and peak signal-to-noise ratio (PSNR) are tracked in our tests. Each of the algorithms described energy change curve and convergence curve respectively.
Result
2
The PSNR of three algorithms shows that de-noising effect of fast algorithm and original ADMM algorithm keeps same in terms of denoising effect. Fast algorithm maintains the quality the original model and image quality of the original ADMM algorithm. In terms of computational efficiency
three algorithms are compared in the TL model and the EE model. Compared with original ADMM algorithm
fast ADMM algorithm improves 6%~50% and 14%~54% each. Compared with original ADMM algorithm
restart fast ADMM algorithm improves 100%~433% and 100%~900% respectively. In addition
the result of iterations to restart the fast ADMM algorithm obtained value 3 all in same scenario
and running time significantly reduced as well. This shows that restart fast ADMM algorithm is very robust. It is obvious from the energy change curve and the convergence curve that the fast ADMM algorithm generated ripples and decreased the restart fast ADMM algorithm. In calculation process
restart fast ADMM algorithm adaptively adjust step size to eliminate ripples and improve computational efficiency in accordance of the scale of the integrated residual.
Conclusion
2
The sub issues of alternate optimization are resolved in each iteration loop via fast Fourier transform method (FFT) or generalized soft thresholding formulas. Numerical experiments show that restart strategy can improve computational efficiency of original ADMM greatly as well as algorithm robustness on penalty parameters. Our contribution provides a qualified reference for fast algorithm of the second-order variational model in context of image restoration. The restart fast algorithm can be extended to variational model of image analysis with second-order derivative regular terms. However
ADMM algorithm and its restart fast algorithm lack sufficient theoretical support for the design of nonlinear
non-smooth
and non-convex variational models with high-order derivatives. Current theoretical research is limited to the optimization issue of objective function composed of two functions. For fast algorithm research of non-smooth and non-convex variational models of high-order derivatives in computer vision
our research is limited to tentative algorithm design and numerical verification.
图像恢复二阶变分模型快速交替方向乘子方法(fast ADMM)重启动总拉普拉斯模型欧拉弹性能模型
image restorationsecond-order variational modelfast alternating direction methods of multipliers (fast ADMM)restarttotal Laplacian modelEuler's elastica model
Aubert G and Kornprobst P. 2006. Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations. 2nd ed. New York: Springer: 1-377
Beck A and Teboulle M. 2009a. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1): 183-202[DOI: 10.1137/080716542]
Beck A and Teboulle M. 2009b. Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE Transactions on Image Processing, 18(11): 2419-2434[DOI: 10.1109/TIP.2009.2028250]
Beck A and Teboulle M. 2014. A fast dual proximal gradient algorithm for convex minimization and applications. Operations Research Letters, 42(1): 1-6[DOI: 10.1016/j.orl.2013.10.007]
Bredies K, Kunisch K and Pock T. 2010. Total generalized variation. SIAM Journal on Imaging Sciences, 3(3): 492-526[DOI: 10.1137/090769521]
Buccini A, Dell'Acqua P and Donatelli M. 2020. A general framework for ADMM acceleration. Numerical Algorithms, 85(3): 829-848[DOI: 10.1007/s11075-019-00839-y]
Calatroni L and Chambolle A. 2019. Backtracking strategies for accelerated descent methods with smooth composite objectives. SIAM Journal on Optimization, 29(3): 1772-1798[DOI: 10.1137/17M1149390]
Chambolle A. 2004. An algorithm for total variation minimization and applications. Journal of Mathematical Imaging and Vision, 20(1-2): 89-97[DOI: 10.1023/B:JMIV.0000011325.36760.1e]
Chambolle A and Pock T. 2011. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision, 40(1): 120-145[DOI: 10.1007/s10851-010-0251-1]
Chan T F, Esedoglu S and Park F. 2010. A fourth order dual method for staircase reduction in texture extraction and image restoration problems//Proceedings of 2010 IEEE International Conference on Image Processing. Hong Kong, China: IEEE, 4137-4140[DOI: 10.1109/ICIP.2010.5653199http://dx.doi.org/10.1109/ICIP.2010.5653199]
Chan T F, Golub G H and Mulet P. 1999. A nonlinear primal-dual method for total variation-based image restoration. SIAM Journal on Scientific Computing, 20(6): 1964-1977[DOI: 10.1137/S1064827596299767]
Chan T F and Shen J. 2005. Image processing and analysis: variational, PDE, wavelet, and stochastic methods. Society for Industrial and Applied Mathematics: 1-400[DOI: 10.1137/1.9780898717877http://dx.doi.org/10.1137/1.9780898717877]
Chen S L. 2017. First-order forward backward algorithm for image restoration based on total variational model. Nanjing: Nanjing University of Posts and Telecommunications
陈少利. 2017. 全变分模型图像复原的一阶前向后向优化算法研究. 南京: 南京邮电大学
Daubechies I, Defrise M and De Mol C. 2004. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Communications on Pure and Applied Mathematics, 57(11): 1413-1457[DOI: 10.1002/cpa.20042]
Glowinski R and Le Tallec P. 1989. Augmented lagrangian and operator-splitting methods in nonlinear mechanics. Society for Industrial and Applied Mathematics: 1-295[DOI: 10.1137/1.9781611970838http://dx.doi.org/10.1137/1.9781611970838]
Glowinski R, Osher S J and Yin W T. 2016. Splitting Methods in Communication, Imaging, Science, and Engineering//Fitter Scientific Computation Cham, Switzerland: Springer: 1-17[DOI: 10.1007/978-3-319-41589-5-1http://dx.doi.org/10.1007/978-3-319-41589-5-1]
Goldstein T and Osher S. 2009. The split bregman method for l1-regularized problems. SIAM Journal on Imaging Sciences, 2(2): 323-343[DOI: 10.1137/080725891]
Goldstein T, O'Donoghue B, Setzer S and Baraniuk R. 2014. Fast alternating direction optimization methods. SIAM Journal on Imaging Sciences, 7(3): 1588-1623[DOI: 10.1137/120896219]
Kang S H, Ta X C and Zhu W. 2019. Survey of fast algorithms for Euler's elastica-based image segmentation. Handbook of Numerical Analysis, 20: 533-552[DOI: 10.1016/bs.hna.2019.05.005]
Kim J and Fessler J A. 2018. Adaptive restart of the optimized gradient method for convex optimization. Journal of Optimization Theory and Applications, 178(1): 240-263[DOI: 10.1007/s10957-018-1287-4]
Kimmel R and Tai X C. 2019. Processing, analyzing and learning of images, shapes, and forms: part 2. Handbook of Numerical Analysis, 20: 1-684
Li Q P. 2018. Research on Fast Iterative Shrinage-Thresholding Algorithm for Non-Smooth Convex Optimization Problems. Xi'an: Xidian University
李启朋. 2018. 非光滑凸优化问题的快速迭代收缩阈值算法研究. 西安: 西安电子科技大学
Li X, Deng K K and Li C. 2019. A fast proximal Barzilai-Borwein gradient method for solving decomposable strongly convex optimization problems. Journal of Wuyi University, 38(3): 12-16
李星, 邓康康, 李超. 2019. 求解可分解强凸优化问题的FISTA-Barzilai-Borwein算法. 武夷学院学报, 38(3): 12-16[DOI: 10.14155/j.cnki.35-1293/g4.2019.03.003
Liu C X, Kong D X and Zhu S F. 2012. A primal-dual hybrid gradient algorithm to solve the LLT model for image denoising. Numerical Mathematics: Theory, Methods and Applications, 5(2): 260-277 [DOI: 10.1017/S1004897900000817]
Lysaker M, Lundervold A and Tai X C. 2003. Noise removal using fourth-order partial differential equation with applications to medical magnetic resonance images in space and time. IEEE Transactions on Image Processing, 12(12): 1579-1590[DOI: 10.1109/TIP.2003.819229]
Masnou S and Morel J M. 1998. Level lines based disocclusion//Proceedings of 1998 International Conference on Image Processing. Chicago, USA: IEEE: 259-263[DOI: 10.1109/ICIP.1998.999016http://dx.doi.org/10.1109/ICIP.1998.999016]
Nesterov Y E. 1983. A method for solving the convex programming problem with convergence rate O(1/k2). Dokl Akad Nauk SSSR, 269(3): 543-547.
Nitzberg M, Mumford D and Shiota T. 1993. Filtering, Segmentation and Depth. Berlin: Springer[DOI: 10.1007/3-540-56484-5]
O'Donoghue B and Candès E. 2015. Adaptive restart for accelerated gradient schemes. Foundations of Computational Mathematics, 15(3): 715-732[DOI: 10.1007/s10208-013-9150-3]
Pan S L, Yan K, Li L Y, Jiang C Y and Shi L G. 2019. Sparse-spike deconvolution based on adaptive step FISTA algorithm. Oil Geophysics, 54(4): 737-743
潘树林, 闫柯, 李凌云, 蒋从元, 石林光. 2019. 自适应步长FISTA算法稀疏脉冲反褶积. 石油地球物理勘探, 54(4): 737-743[DOI: 10.13810/j.cnki.issn.1000-7210.2019.04.002
Paragios N, Chen Y M and Faugeras O. 2006. Handbook of Mathematical Models in Computer Vision. Boston, USA: Springer [DOI: 10.1007/0-387-28831-7]
Rudin L I, Osher S and Fatemi E. 1992. Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena, 60(1/4): 259-268[DOI: 10.1016/0167-2789(92)90242-F]
Scherzer O. 2015. Handbook of Mathematical Methods in Imaging. 2nd ed. New York, USA: Springer[DOI: 10.1007/978-1-4939-0790-8]
Tai X C, Hahn J and Chung G J. 2011. A fast algorithm forEuler's elastica model using augmented Lagrangian method. SIAM Journal on Imaging Sciences, 4(1): 313-344[DOI: 10.1137/100803730]
Vogel C R and Oman M E. 1996. Iterative methods for total variation denoising. Siam Journal on Scientific Computing, 17(1): 227-238[DOI: 10.1137/0917016]
Wu C L and Tai X C. 2010. Augmented lagrangian method, dual methods, and split bregman iteration for ROF, vectorial TV, and high order models. SIAM Journal onImaging Sciences, 3(3): 300-339[DOI: 10.1137/090767558]
Yashtini M and Kang S H. 2016. A fast relaxed normal two split method and an effective weighted TV approach for Euler's elastica image inpainting. SIAM Journal on Imaging Sciences, 9(4): 1552-1581[DOI: 10.1137/16M1063757]
Zhu M and Chan T. 2008. An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration. CAM Reports 08-34. UCLA, Center for Applied Math
Zhu W, Tai X C and Chan T. 2013. Image segmentation using Euler's elastica as the regularization. Journal of Scientific Computing, 57(2): 414-438[DOI: 10.1007/s10915-013-9710-3]
Zhu W, Tai X C and Chan T. 2014. A Fast algorithm for a mean curvature based image denoising model using augmented lagrangian method//Bruhn A, Pock T and Tai X C, eds. Efficient Algorithms for Global Optimization Methods in Computer Vision. Berlin, Germany: Springer, 104-118[DOI: 10.1007/978-3-642-54774-4_5http://dx.doi.org/10.1007/978-3-642-54774-4_5]
相关作者
相关机构
京公网安备11010802024621