Current Issue Cover
二阶变分图像恢复模型的重启动快速ADMM方法

宋田田, 潘振宽, 魏伟波, 李青(青岛大学计算机科学技术学院, 青岛 266071)

摘 要
目的 基于二阶导数的图像恢复变分模型可以同时保持图像边缘与光滑特征,但其规则项的非线性、非光滑性,甚至非凸性制约着其快速算法的设计。针对总拉普拉斯(total Laplacian,TL)与欧拉弹性能(Euler’s elastica,EE)两种图像恢复变分模型,在设计快速交替方向乘子法(fast alternating direction methods of multipliers,fast ADMM)的基础上引入重启动策略,以有效消除解的振荡,从而大幅提高该类模型计算效率,并为其他相近模型的快速算法设计提供借鉴。方法 基于原始ADMM方法设计反映能量泛函变化的残差公式,在设计的快速ADMM方法中根据残差的变化重新设置快速算法的相关参数,以避免计算过程中的能量振荡,达到算法加速目的结果 通过大量实验发现,采用原始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算法的计算效率基本相同。结论 对于两种典型的二阶变分图像恢复模型,本文提出的快速重启动ADMM算法比原始ADMM算法及快速ADMM算法在计算效率方面有较大提高,计算效率对不同惩罚参数组合具有鲁棒性。本文设计的算法对于含其他形式二阶导数规则项的变分图像分析模型的重启动快速算法的设计可提供有益借鉴。
关键词
Restart fast ADMM methods for second-order variational models of image restoration

Song Tiantian, Pan Zhenkuan, Wei Weibo, Li Qing(College of Computer Science and Technology, Qingdao University, Qingdao 266071, China)

Abstract
Objective 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 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 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 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.
Keywords

订阅号|日报