基于乘子交替方向法改進的圖像恢復方法

唐崇偉 黨亞崢 曹思琪

摘 要：為了改善圖像模糊給生活帶來的不便，基于乘子交替方向法（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.

（責任編輯：黃 健）