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

2020-06-22 13:15唐崇伟党亚峥曹思琪
软件导刊 2020年5期

唐崇伟 党亚峥 曹思琪

摘 要:为了改善图像模糊给生活带来的不便,基于乘子交替方向法(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.

(責任编辑:黄 健)