基于乘子交替方向法改进的图像恢复方法

唐崇伟 党亚峥 曹思琪

摘 要：为了改善图像模糊给生活带来的不便，基于乘子交替方向法（ADMM）对图像恢复问题进行研究。图像作为一种重要的信息载体，在生活各个方面都显得尤为重要，但图像退化导致的模糊问题始终是困扰其正常发挥作用的重要因素。ADMM在处理线性逆问题方面有着良好效果，然而在很多实际应用中，无法保证算法能够高效且高质量地恢复图像。为此，提出一种改进ADMM算法，在[x]子问题和[z]子问题中引入新的松弛参数，使得每次迭代步长大于1，从而提高算法收敛性。最后，图像恢复数值实验结果表明，该算法迭代次数减少了40%，显著提高了运算效率。采用改进ADMM算法不仅能够准确、高效地恢复图像，同时也能提高计算机运算效率。

关键词：乘子交替方向法;最小二乘问题;松弛算子;图像恢复

DOI：10. 11907/rjdk. 192610 开放科学（资源服务）标识码（OSID）：

中图分类号：TP317.4 文献标识码：A 文章编号：1672-7800（2020）005-0217-04

0 引言

在图像产生、传输与处理过程中，由于受到信号干扰，或成像设备及其它因素的综合影响，无法避免的一个问题便是图像失真，最为直观的表现就是图像变得模糊。图像作为重要的信息载体，在人们的生活、工作、科研等方面发挥着重要作用，而受损的图像可能会给个人、社会造成巨大损失。为了满足生活及科研的需要，对受损图像进行恢复成为了很多学者研究的主题[1-3]。

其中，[A，B∈Rm×n]，且[mn]，[b，d∈Rm]，[λ∈R]。在图像模糊问题的模型中，[A]是模糊算子，[B]是正则化算子，当[d=0]时，问题（2）则成为Tikhonov正则化问题，[b]为观测到的图像，[x]是被还原的图像。此外，问题（2）也是Huang等[4]研究分裂算法中的一个子问题，采用TV正则化完成了图像恢复，此时[B]为单位矩阵，[d]是[x]的近似值。

对于此类问题，Chan等[3]针对问题（2）设计了利用A和B属性的加速算法。用于求解问题（2）的算法本质上是内点法背景下的牛顿型方法，例如有学者提出将其用于解决非负最小二乘问题[10-11]。内点法同样非常适用于图像重建问题中的不适定问题[12-13]。Bellavia等[14]通过将Karush-Kuhn-Tucker条件转化为非线性方程组，提出一种牛顿型方法求解非负最小二乘问题，在图像去模糊问题上，简化牛顿法优于投影法及某些内点牛顿法。

本文采用ADMM法[16-17]处理问题（2），该类问题大量出现在图像处理、机器学习等系数优化领域[19]，而ADMM法近年来被公认为求解具有可分离结构凸问题的有效方法，因而受到了广泛重视。如Cai等[20]将ADMM算法延伸为“邻近点型”交替方向法;He等[21-22]引入两次校正乘子，生成“对称性”交替方向法，随后又提出扩展步长的算法，并针对算法的不精确性进行研究[24];接着Gu等[23]又对其作了进一步研究。针对3个和3个以上问题的研究[25]，直接应用ADMM算法是不能保证其收敛的，因此He等[26-27]提出一些理论上可保证收敛的求解多个可分离算子的分裂算法，即带高斯回代的交替方向法与部分平行的正则化方法。

注意到目标函数是由共同变量[x]组合在一起的两个最小二乘项之和，通过辅助变量将两个最小二乘项分离，并直接应用ADMM法。ADMM将问题（2）分解为两个更简单的子问题，每个子问题都是最小二乘问题，目标函数中只有一个二次项。但如果问题（2）中的矩阵A或B都不是单位矩阵，ADMM子问题则无法得到封闭解，也通常很难取得最优解。因此，引入线性化思想可使求解ADMM子问题的封闭解变得更加容易。本文还在线性化ADMM法基础上引入一组松弛算子[18]，将新的松弛参数引入到[x]子问题和[z]子问题中，在取值恰当的情况下，使得每次迭代步长大于1。图像恢复数值实验结果表明，在同样条件下，改进后算法较原算法的图像恢复质量有所提高，且缩短了運算时间，大幅减少了迭代次数。

1 算法

为了应用ADMM算法，首先将问题（2）变量拆分为：

2 数值实验

本节将A-ADMM算法应用于图像模糊问题，所有代码均由Matlab 2016a 编写，处理器为 Intel Core i5 3.0GHz ，内存16Gb，并在Windows 10上运行。

实验中设置[λ=2×10-5]，[τ=1.05ρ（ATA）]，[γ=0.1]，[t=1.9]，[ω=0.7]进行验证。表1为A-ADMM算法与LADMM算法处理结果对比。从表1可以清晰看出，A-ADMM算法在迭代次数上具有明显优势，相较于LADMM算法减少了40%的迭代次数，同时运算时间与信噪比也得到了保障。

通过对两种算法的比较，可以看出A-ADMM算法具有明显优势，在迭代初始阶段即明显表现出更好的收敛效果，最终结果也证实了改进后算法具有更好的性能。本文算法在不牺牲运算速度与图像质量的同时，减少了迭代次数，取得了符合预期的效果。

3 结语

本文从线性ADMM算法中获得启发，提出一种加速ADMM算法。通过对改进ADMM算法的研究发现，在[x]子问题和[z]子问题中引入松弛算子，使得算法每一步子问题的迭代步长都能大于1，可使算法能够更高效地收敛，在确保其具有更高效率的同时，提高了图像恢复质量。本文数值实验验证了松弛算子能提高算法性能的猜想，A-ADMM算法相对于LADMM具有明显优势，可减少40%的迭代步骤，从而节省了大量计算资源。在接下来的工作中，针对如何在提升迭代次数的同时，提高图像恢复质量，并大幅减少运行时间，还需作进一步研究。

参考文献：

[1] 王守觉， 谢美芬，曹文明. 图像恢复的一种新方法[C]. 中国控制与决策学术年会论文集，2006.

[2] 吳越，曾向荣，周典乐，等. 图像恢复中的稳健交替方向乘子法[J].国防科技大学学报， 2018， 40（2）：115-121.

[3] CHAN R H. Linearized alternating direction method of multipliers for constrained linear least-squares problem[J]. East Asian Journal on Applied Mathematics， 2012， 2（4）：326-341.

[4] HUANG Y M， NG M K，WEN Y W. A fast total variational minimization method for image restoration[J]. SIAM Multi. Modeling Simul.， 2008， 7： 774-795.

[5] COLEMAN T F， LI Y. An interior， trust region approach for nonlinear minimization subject to bounds[J].  SIAM Journal on Optimization， 1996， 6（2）：418-445.

[6] CENSOR Y， ELFVING T. A multiprojection algorithm using Bregman projections in a product space [J].  Numerical Algorithms， 1994， 8（2）： 221-239.

[7] HE H， LING C， XU H K. An implementable splitting algorithm for the l1-norm regularized split feasibility problem[M]. New York：Plenum Press， 2016.

[8] POTTER L C，ARUN K S. A dual approach to linear inverse problems with convex constraints[J].  SIAM Journal on Control and Optimization， 1993， 31（4）：1080-1092.

[9] SABHARWAL A. Convexly constrained linear inverse problems： iterative least-squares and regularization[J].  IEEE Transactions on Signal Processing， 1998， 46（9）：2345-2352.

[10] COLEMAN T F ， LI Y .  An interior， trust region approach for nonlinear minimization subject to bounds[J].  SIAM Journal on Optimization， 1996， 6（2）：418-445.

[11] LUíS F P， JOAQUIM J J，LUíS N V. A comparison of block pivoting and interior-point algorithms for linear least squares problems with nonnegative variables[J].  Mathematics of Computation，1994， 63（208）：625-643.

[12] CALVETTI D， LANDI G，REICHEL L， et al. Non-negativity and iterative methods for ill-posed problems[J].  Inverse Problems， 2004， 20（6）：1747.

[13] ROJAS M，STEIHAUG T. An interior-point trust-region-based method for large-scale non-negative regularization[J].  Inverse Problems， 2002， 18（5）：1291-1307.

[14] BELLAVIA S， MACCONI M， MORINI B. An interior Newton-like method for nonnegative least-squares problems with degenerate solution[J].  Numerical Linear Algebra with Applications， 2005， 13（10）：825-846.

[15] CHAN R H，MORINI B，PORCELLI M. Affine scaling methods for image deblurring problems[J].  AIP Conference Proceedings ，2010.

[16] DANIEL G， BERTRAND M.A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J]. Computers & Mathematics with Applications， 1976（1）：17-40.

[17] GLOWINSKI R，MARROCO A.  Sur l'approximation， par éléments finis d'ordre un， et la résolution， par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires[J].  ESAIM： Mathematical Modelling and Numerical Analysis， 1975， 9（R2）：41-76.

[18] ECKSTEIN J，BERTSEKAS D P. On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators[J]. Mathematical Programming，1992，55（1-3）：293-318.

[19] BENKER H. Mathematische optimierung[M]. Berlin：Springer，1975.

[20] CAI X J，GU G Y，HE B S，et al. A proximal point algorithm revisit on the alternating direction method of multipliers[J].  Science China Mathematics， 2013， 56（10）：2179-2186.

[21] HE B，LIU H，WANG Z，et al. A strictly contractive peaceman-rachford splitting method for convex programming[J].  SIAM Journal on Optimization， 2014， 24（3）：1011-1040.

[22] HE B，MA F，YUAN X ， et al. Convergence study on the symmetric version of ADMM with larger step sizes[J].  SIAM Journal on Imaging Sciences， 2016， 9（3）：1467-1501.

[23] GU G，YANG J，HE B.  Inexact alternating-direction-based contraction methods for separable linearly constrained convex optimization[J].  Journal of Optimization Theory and Applications， 2014， 163（1）：105-129.

[24] HE B，LIAO L Z，HAN D，et al. A new inexact alternating directions method for monotone variational inequalities[J].  Mathematical Programming， 2002， 92（1）：103-118.

[25] CHEN C，HE B，YE Y，et al. The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent[J].  Mathematical Programming， 2016， 155（1-2）：57-79.

[26] HE B，TAO M，YUAN X. Alternating direction method with Gaussian back substitution for separable convex programming[J].  SIAM Journal on Optimization， 2012， 22（2）：313-340.

[27] HE B，TAO M，YUAN X. A splitting method for separable convex programming[J]. IMA Journal of Numerical Analysis， 2015， 35（1）：394-426.

（責任编辑：黄 健）