基于乘子交替方向法改進(jìn)的圖像恢復(fù)方法

唐崇偉 黨亞崢 曹思琪

摘 要：為了改善圖像模糊給生活帶來的不便，基于乘子交替方向法（ADMM）對(duì)圖像恢復(fù)問題進(jìn)行研究。圖像作為一種重要的信息載體，在生活各個(gè)方面都顯得尤為重要，但圖像退化導(dǎo)致的模糊問題始終是困擾其正常發(fā)揮作用的重要因素。ADMM在處理線性逆問題方面有著良好效果，然而在很多實(shí)際應(yīng)用中，無法保證算法能夠高效且高質(zhì)量地恢復(fù)圖像。為此，提出一種改進(jìn)ADMM算法，在[x]子問題和[z]子問題中引入新的松弛參數(shù)，使得每次迭代步長大于1，從而提高算法收斂性。最后，圖像恢復(fù)數(shù)值實(shí)驗(yàn)結(jié)果表明，該算法迭代次數(shù)減少了40%，顯著提高了運(yùn)算效率。采用改進(jìn)ADMM算法不僅能夠準(zhǔn)確、高效地恢復(fù)圖像，同時(shí)也能提高計(jì)算機(jī)運(yùn)算效率。

關(guān)鍵詞：乘子交替方向法;最小二乘問題;松弛算子;圖像恢復(fù)

DOI：10. 11907/rjdk. 192610 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP317.4 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2020）005-0217-04

0 引言

在圖像產(chǎn)生、傳輸與處理過程中，由于受到信號(hào)干擾，或成像設(shè)備及其它因素的綜合影響，無法避免的一個(gè)問題便是圖像失真，最為直觀的表現(xiàn)就是圖像變得模糊。圖像作為重要的信息載體，在人們的生活、工作、科研等方面發(fā)揮著重要作用，而受損的圖像可能會(huì)給個(gè)人、社會(huì)造成巨大損失。為了滿足生活及科研的需要，對(duì)受損圖像進(jìn)行恢復(fù)成為了很多學(xué)者研究的主題[1-3]。

其中，[A，B∈Rm×n]，且[mn]，[b，d∈Rm]，[λ∈R]。在圖像模糊問題的模型中，[A]是模糊算子，[B]是正則化算子，當(dāng)[d=0]時(shí)，問題（2）則成為Tikhonov正則化問題，[b]為觀測到的圖像，[x]是被還原的圖像。此外，問題（2）也是Huang等[4]研究分裂算法中的一個(gè)子問題，采用TV正則化完成了圖像恢復(fù)，此時(shí)[B]為單位矩陣，[d]是[x]的近似值。

對(duì)于此類問題，Chan等[3]針對(duì)問題（2）設(shè)計(jì)了利用A和B屬性的加速算法。用于求解問題（2）的算法本質(zhì)上是內(nèi)點(diǎn)法背景下的牛頓型方法，例如有學(xué)者提出將其用于解決非負(fù)最小二乘問題[10-11]。內(nèi)點(diǎn)法同樣非常適用于圖像重建問題中的不適定問題[12-13]。Bellavia等[14]通過將Karush-Kuhn-Tucker條件轉(zhuǎn)化為非線性方程組，提出一種牛頓型方法求解非負(fù)最小二乘問題，在圖像去模糊問題上，簡化牛頓法優(yōu)于投影法及某些內(nèi)點(diǎn)牛頓法。

本文采用ADMM法[16-17]處理問題（2），該類問題大量出現(xiàn)在圖像處理、機(jī)器學(xué)習(xí)等系數(shù)優(yōu)化領(lǐng)域[19]，而ADMM法近年來被公認(rèn)為求解具有可分離結(jié)構(gòu)凸問題的有效方法，因而受到了廣泛重視。如Cai等[20]將ADMM算法延伸為“鄰近點(diǎn)型”交替方向法;He等[21-22]引入兩次校正乘子，生成“對(duì)稱性”交替方向法，隨后又提出擴(kuò)展步長的算法，并針對(duì)算法的不精確性進(jìn)行研究[24];接著Gu等[23]又對(duì)其作了進(jìn)一步研究。針對(duì)3個(gè)和3個(gè)以上問題的研究[25]，直接應(yīng)用ADMM算法是不能保證其收斂的，因此He等[26-27]提出一些理論上可保證收斂的求解多個(gè)可分離算子的分裂算法，即帶高斯回代的交替方向法與部分平行的正則化方法。

注意到目標(biāo)函數(shù)是由共同變量[x]組合在一起的兩個(gè)最小二乘項(xiàng)之和，通過輔助變量將兩個(gè)最小二乘項(xiàng)分離，并直接應(yīng)用ADMM法。ADMM將問題（2）分解為兩個(gè)更簡單的子問題，每個(gè)子問題都是最小二乘問題，目標(biāo)函數(shù)中只有一個(gè)二次項(xiàng)。但如果問題（2）中的矩陣A或B都不是單位矩陣，ADMM子問題則無法得到封閉解，也通常很難取得最優(yōu)解。因此，引入線性化思想可使求解ADMM子問題的封閉解變得更加容易。本文還在線性化ADMM法基礎(chǔ)上引入一組松弛算子[18]，將新的松弛參數(shù)引入到[x]子問題和[z]子問題中，在取值恰當(dāng)?shù)那闆r下，使得每次迭代步長大于1。圖像恢復(fù)數(shù)值實(shí)驗(yàn)結(jié)果表明，在同樣條件下，改進(jìn)后算法較原算法的圖像恢復(fù)質(zhì)量有所提高，且縮短了運(yùn)算時(shí)間，大幅減少了迭代次數(shù)。

1 算法

為了應(yīng)用ADMM算法，首先將問題（2）變量拆分為：

2 數(shù)值實(shí)驗(yàn)

本節(jié)將A-ADMM算法應(yīng)用于圖像模糊問題，所有代碼均由Matlab 2016a 編寫，處理器為 Intel Core i5 3.0GHz ，內(nèi)存16Gb，并在Windows 10上運(yùn)行。

實(shí)驗(yàn)中設(shè)置[λ=2×10-5]，[τ=1.05ρ（ATA）]，[γ=0.1]，[t=1.9]，[ω=0.7]進(jìn)行驗(yàn)證。表1為A-ADMM算法與LADMM算法處理結(jié)果對(duì)比。從表1可以清晰看出，A-ADMM算法在迭代次數(shù)上具有明顯優(yōu)勢(shì)，相較于LADMM算法減少了40%的迭代次數(shù)，同時(shí)運(yùn)算時(shí)間與信噪比也得到了保障。

通過對(duì)兩種算法的比較，可以看出A-ADMM算法具有明顯優(yōu)勢(shì)，在迭代初始階段即明顯表現(xiàn)出更好的收斂效果，最終結(jié)果也證實(shí)了改進(jìn)后算法具有更好的性能。本文算法在不犧牲運(yùn)算速度與圖像質(zhì)量的同時(shí)，減少了迭代次數(shù)，取得了符合預(yù)期的效果。

3 結(jié)語

本文從線性ADMM算法中獲得啟發(fā)，提出一種加速ADMM算法。通過對(duì)改進(jìn)ADMM算法的研究發(fā)現(xiàn)，在[x]子問題和[z]子問題中引入松弛算子，使得算法每一步子問題的迭代步長都能大于1，可使算法能夠更高效地收斂，在確保其具有更高效率的同時(shí)，提高了圖像恢復(fù)質(zhì)量。本文數(shù)值實(shí)驗(yàn)驗(yàn)證了松弛算子能提高算法性能的猜想，A-ADMM算法相對(duì)于LADMM具有明顯優(yōu)勢(shì)，可減少40%的迭代步驟，從而節(jié)省了大量計(jì)算資源。在接下來的工作中，針對(duì)如何在提升迭代次數(shù)的同時(shí)，提高圖像恢復(fù)質(zhì)量，并大幅減少運(yùn)行時(shí)間，還需作進(jìn)一步研究。

參考文獻(xiàn)：

[1] 王守覺， 謝美芬，曹文明. 圖像恢復(fù)的一種新方法[C]. 中國控制與決策學(xué)術(shù)年會(huì)論文集，2006.

[2] 吳越，曾向榮，周典樂，等. 圖像恢復(fù)中的穩(wěn)健交替方向乘子法[J].國防科技大學(xué)學(xué)報(bào)， 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.

（責(zé)任編輯：黃 健）