陳少利，楊 敏

(南京郵電大學 自動化學院，江蘇 南京 210023)

改進變步長快速迭代收縮閾值算法

陳少利，楊 敏

(南京郵電大學 自動化學院，江蘇 南京 210023)

圖像復原問題是圖像處理中的一項重要研究內(nèi)容，解決圖像復原問題，往往涉及到大量的數(shù)據(jù)集和未知信息。為了解決此類高維數(shù)據(jù)優(yōu)化問題，前向后向算法提供了簡潔、實用的方法?？焖俚湛s閾值算法是在前向后向算法的基礎上加入了全局加速算子，一定程度上提高了算法的收斂速率。但是，快速迭代收縮閾值算法在解決最小值優(yōu)化問題時，采用的是固定步長因子，限制了算法的收斂速率。針對該問題，結合Barzilai-Borwein算子提出一種改進的變步長算法。改進算法在每次迭代中利用前兩步的迭代信息更新步長因子，加快了算法的收斂。將該算法應用于壓縮感知和圖像去噪中，數(shù)值實驗結果表明：該算法改進了原算法的收斂速率。因此,改進變步長快速迭代收縮閾值算法不僅提高了算法的效率，同時提高了信號復原的信噪比。

快速迭代收縮閾值算法；Barzilai-Borwein算子；全變分模型；壓縮感知;圖像去噪

0 引 言

圖像去噪問題[1]是圖像復原處理中的一個關鍵問題。在傳感器設備獲取圖像的過程中，由于傳感器缺陷、環(huán)境變化以及人為因素等原因，使得圖像不可避免地引入噪聲。研究圖像去噪問題時，一般情況下，針對圖像建立去噪模型，然后利用優(yōu)化理論中逆問題的求解，獲取更加容易分析和處理的圖像。其中逆問題就是從直接觀察到的參數(shù)出發(fā)，通過迭代計算找到目標函數(shù)的一個可行解，使得目標函數(shù)值最優(yōu)。該問題在光學、雷達、聲學、通信理論、信號處理、醫(yī)療圖像、計算機視覺、機器學習[2]、壓縮感知[3]等領域均有廣泛的應用。

壓縮感知(或稱壓縮采樣、稀疏采樣)[3]，是一種新的高效獲取和恢復信號的信息理論。它突破了香農(nóng)理論中，當采樣頻率不低于信號頻率的兩倍時，就可以無失真地恢復原始信號的理論。壓縮感知的核心思想是，若高維信號是可以壓縮的或其在某一個變換域中具有稀疏性，則可用一個與變換基不相關的測量矩陣將該信號投影到一個低維空間上，同時這種投影保持了重構信號[4]所需要的信息，然后通過求解一個最優(yōu)問題，以較高的概率從這些少量的投影中重構出原始信號。其優(yōu)點是以較少的采樣資源，較高的采樣速度和較低的軟硬件復雜度獲得原始信號的測量值。

快速迭代收縮閾值算法(FISTA)[5]是由Beck等提出的一種優(yōu)化近似分裂算法。該算法將全局加速算子應用于分裂算法，利用函數(shù)的前項梯度映射[6]和后項近似映射[7-8]得到問題的近似解。但是在迭代過程中，采用的是固定步長，限制了算法對一般凸優(yōu)化問題的求解速率。

針對該問題，提出一種變步長的快速迭代收縮閾值算法，并應用于圖像的去噪和壓縮感知問題中，并進行了實驗驗證。

1 逆問題及其求解算法

一般問題模型為：

b=Au+n

(1)

其中，A,b,n是已知矩陣，當矩陣A為單位矩陣時，從已知的矩陣b中恢復未知的信號u，則得到如下的逆問題：

(2)

若式(2)中約束項為L1模型，則此時的解是估計壓縮信號u的最優(yōu)解。

故針對文中的壓縮感知算例，應用L1正則化模型求解。L1正則化模型為：

(3)

對于圖像處理問題，文獻[9]提出利用全變分模型(Total Variation,TV)求解圖像復原。該模型由Rudin等于1992年提出，用以代替L1模型，可以更好地保存圖像的邊緣信息。因此針對文中圖像去噪算例，應用TV模型進行重構求解[10]。

全變分模型[9,11]定義式如下：

(4)

其中，‖u‖TV表示u關于點i的離散化梯度。因此，當q=2時，‖u‖TV表示各向同性；q=1時，‖u‖TV各向異性。

針對文中算法，選擇各向同性，得到圖像去噪優(yōu)化問題的新模型為：

(5)

下面描述一階優(yōu)化算法。

對于信號和圖像處理等問題中的凸優(yōu)化求解，通常利用求逆問題，然后選擇有效求解的相關算法，如一階算法[12]。

例如，對于無約束的凸優(yōu)化問題：

min{f(x):x∈Rn}

(6)

f:Rn→R是具有L-Lipschitiz常數(shù)的可微凸函數(shù)。即有：

y)∈RN×RN)

(7)

其中，L(f)>0，它是f的Lipschitiz常量。

一般采用梯度下降法[6]最小化f：

算法1：梯度下降算法。

1：Fork=1,2,3…do

2：xk+1=xk-ρf(xk)

End For

min{F(x)=f(x)+g(x):x∈Rn}

(8)

其中，f(x)和g(x)均為凸函數(shù)。

此時算法1可以改進為前項后項分裂[13-14]算法(Forward-Backward Splitting,FBS)。

算法2：FBS。

1：Fork=1,2,3…do

2：xk+1=prox(xk-ρf(xk))

End For

2 快速迭代收縮閾值算法

隨著對壓縮感知問題研究的興起，一階算法的優(yōu)化問題逐漸成為研究熱點。而快速迭代收縮閾值(FISTA)[5]就是一種優(yōu)化FBS算法。

首先考慮如下問題:

(9)

假設函數(shù)g是任意下半連續(xù)凸函數(shù)，一般情況下，函數(shù)g既是不可微的同時函數(shù)值趨于無窮大，此時函數(shù)g通過計算所謂的近似映射[7-8]的閉合解，同時假設函數(shù)f是凸函數(shù)，有L-Lipschitz梯度f(見式(7))，則問題的一個近似映射為：

(10)

假設當‖x‖→∞時，f(x)+g(x)→∞。則問題(9)至少有一個解。對于任意的ρ>0，該問題有如下形式的解：

x=proxλg(x-ρf(x))

(11)

該等式有如下迭代的等式：

(12)

該方法可以分解成首先利用函數(shù)f求解前向梯度，然后再利用函數(shù)g求解后向近似算子。FISTA算法就是利用映射梯度法和分解法解決變量不等式問題的。當g=0時，式(12)簡化為：xn+1=xn-ρnf(x)，即求解一個Lipschitz可微分方程的最小值；當f=0時，式(12)簡化為：xn+1=proxρnfxn，即求解一個不可微函數(shù)的最小值。因此FISTA算法可以認為是這兩種基本方法的組合。

綜上所述，F(xiàn)ISTA算法可以理解為初始化x0∈RN之后，求解目標函數(shù)的前向梯度映射和后向近似映射問題的解：

xn=proxγng(xn-ρnf(xn))

(13)

當0<ρ<2/L(f)，那么該方法收斂到f+g的最小值。

算法3：FISTA。

1：初始化t1=1,y1=x0∈Rn,ρ<2/L(f)

2：Fork=1,2,3…do

3：xk=prox(yk-ρf(yk))

5：yk+1=xk+(xk-xk-1)(tk-1)/tk+1

End For

由于FISTA算法在求解問題中采用的是加速因子，與原始的ISTA[15]算法相比，搜索速度有所增加。

3 改進快速迭代收縮閾值算法

雖然FISTA算法采用了一階優(yōu)化的方法，同時采用加速算子，但由于該算法中采用的是固定步長因子的搜索迭代方法，使得算法的搜索速度較慢?；诖藛栴}，在FISTA算法的基礎上，采用BB(Barzilai-Borwein)[16]可變步長的快速迭代收縮閾值算法可以加快搜索速度，提高算法的收斂效率。

BB算法的基本思想是利用迭代當前點以及前一點的信息來確定步長因子。在選擇臨近步長時，用ρnI來模擬Hessian矩陣2f(x)。即迭代的公式為：xn+1=xn-ρngn，可以看作xn+1=xn-Dngn。其中Dn=ρnI。計算ρn，得到min‖sn-1-Dnyn-1‖，其中sn-1=xn-xn-1，yn-1=gn-gn-1。這樣做是基于擬牛頓法[17]的提供兩點接近切線方程，從而得到迭代方程：

xn+1=xn-ρngn

(14)

(15)

改進算法(稱之為FBB算法)描述如下：

算法4：FBB。

1：初始化x0,t0,ρ0=1,u0,φ,k=1

2：xk+1=prox(uk-ρkf(uk))

3：令sk-1=xk-xk-1,yk-1=gk-gk-1,gk=f(xk)

7：uk+1=xk+(tk-1)/(tk+1)(xk-xk-1)

8：更新k=k+1

9：如果滿足終止標準，算法停止

4 數(shù)值實驗

實驗測試平臺為Window7系統(tǒng)的筆記本，CPU為AMD A6-3400M APU with Radeon(tm) HD Graphics 1.40 GHz 四核，4 GB內(nèi)存，仿真平臺為MATLAB 7.14(R2012a)。

4.1基于L1模型的壓縮感知

待恢復信號為5 000個，信號壓縮率為5.555 56，分別采用FBB算法和FISTA算法進行信號的恢復。圖1是兩種算法恢復的效果。

從圖中可以看出，兩種算法都能達到恢復信號的目的。

目標函數(shù)的對比如圖2所示。

FBB算法在恢復信號時使得誤差更小，更接近信號最優(yōu)值。信號恢復的信噪比和相對誤差如表1所示。在相同迭代步數(shù)(150步)時，F(xiàn)BB算法對信號恢復的信噪比更高，效果更優(yōu)。

圖1 壓縮感知信號恢復

圖2 目標函數(shù)對比

表1 圖像去噪結果對比

4.2基于TV模型的圖像去噪

為了驗證文中算法，測試圖像為六幅灰度圖像，分別為“Cameraman”(256×256)、“Lena”(512×512)、“Plane”(512×512)、“Barbara” (512×512)、“Mandrill”(512×512)、“Peppers(512×512)”。

以“Cameraman”(256×256)為例，測試圖像去噪，對圖像添加方差為0.01的Gaussian噪聲后，采用FBB和FISTA對圖像進行去噪實驗并作對比分析。

圖3為Cameraman去噪圖像。

圖3 Cameraman去噪圖像

相對誤差對比如圖4所示。

圖4 Cameraman圖像去噪相對誤差對比曲線

從圖4可以看出，F(xiàn)BB最終的相對誤差值要小于FISTA下的相對誤差值，表明圖像去噪效果更好。

圖5是兩算法目標函數(shù)隨迭代次數(shù)的對比及其放大圖。從圖中可以看出，F(xiàn)BB的目標函數(shù)值小于FISTA的目標函數(shù)值。

表2是六幅圖像都添加高斯噪聲后利用兩種算法對圖像去噪運行時間和去噪前后信噪比對比結果。

表2 圖像去噪實驗結果對比

圖5 Cameraman圖像去噪目標函數(shù)值對比曲線

從表2可以看出，F(xiàn)BB比FISTA在去噪后圖像信噪比較高，同時計算機耗時較短，縮短了近一半的計算時間，提高了圖像去噪的速率。

5 結束語

針對傳統(tǒng)定步長的快速迭代收縮閾值算法收斂速率慢的問題，提出了一種采用BB可變步長的改進快速迭代收縮閾值算法。該算法在每次迭代之前對步長因子進行更新，加快了算法的收斂速率。數(shù)值實驗表明：該算法不僅加快了原快速迭代收縮閾值算法的效率，而且提高了恢復圖像的質量。

[1] 劉 文,吳傳生,許 田.自適應全變分圖像去噪模型及其快速求解[J].計算機應用研究,2011,28(12):4797-4800.

[2] 郭亞寧,馮莎莎.機器學習理論研究[J].中國科技信息,2010(14):208-209.

[3] 戴瓊海,付長軍,季向陽.壓縮感知研究[J].計算機學報,2011,34(3):425-434.

[4] 謝志鵬.基于前向后向算子分裂的稀疏信號重構[J].南京大學學報:自然科學版,2012,48(4):475-481.

[5] Beck A,Teboulle M.A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J].SIAM Journal on Imaging Sciences,2009,2(1):183-202.

[6] Chen X, Lin Q, Kim S, et al.Smoothing proximal gradient method for general structured sparse regression[J].Annals of Applied Statistics,2012,6(2):719-752.

[7] Parikh N,Boyd S.Proximal algorithms[J].Foundations and Trends in Optimization,2013,1(3):123-231.

[8] Combettes P L,Pesquet J C.Proximal splitting methods in signal processing[M]//Fixed-point algorithms for inverse problems in science and engineering.New York:Springer,2011:185-212.

[9] Rudin L I,Osher S,Fatemi E.Nonlinear total variation based noise removal algorithms[J].Physica D,1992,60(1-4):259-268.

[10] 李艷紅.基于全變分模型壓縮傳感圖像重構的快速算法[D].鄭州：河南大學,2012.

[11] 余麗紅,馮衍秋,陳武凡.基于自適應正則化的全變分去噪算法[J].中國圖象圖形學報,2009,14(10):1950-1954.

[12] Jensen T L.First-order convex optimization methods for signal and image processing[D].Denmark:Aalborg University,2011.

[13] Tseng P.Applications of a splitting algorithm to decomposition in convex programming and variational inequalities[J].SIAM Journal on Control and Optimization,1991,29(1):119-138.

[14] Combettes P L,Wajs V R.Signal recovery by proximal forward-backward splitting[J].SIAM Journal on Multiscale Modeling & Simulation,2005,4(4):1168-1200.

[15] Bioucas-Dias J M,Figueiredo M A T.A new TwIST:two-step iterative shrinkage/thresholding algorithms for image restoration[J].IEEE Transactions on Image Processing,2007,16(12):2992-3004.

[16] Barzilai J,Borwein J M.Two-point step size gradient methods[J].IMA Journal of Numerical Analysis,1988,8(1):141-148.

[17] 桂勝華,周 巖.拉格朗日-擬牛頓法解約束非線性規(guī)劃問題[J].同濟大學學報:自然科學版,2007,35(4):556-561.

AnImprovedFastIterativeShrinkage-thresholdingAlgorithmwithVariableStepsize

CHEN Shao-li，YANG Min

(College of Automation，Nanjing University of Posts and Telecommunications，Nanjing 210023，China)

Image restoration is an important research in image processing and solving of it involves large databases and many unknowns.The forward-backward splitting method provides a simple,practicable solution to solve the kinds of data optimization with high dimension.The fast iterative shrinkage-thresholding algorithm joins the global acceleration operator and improve its convergence rate based on the forward-backward algorithm.However,the fixed step-size limits its speed of the convergence in minimal optimization solving.To address that,an improved algorithm with variable stepsize by using Barzilai-Borwein (BB) operator is proposed which updates the step size with the iterative information of the first two steps in each iteration to accelerate its convergence.Then it’s applied to image denosing and compressed sensing.The experimental results demonstrate that it is more efficient than the original fast iterative shrinkage-threshold algorithm,not only in the efficiency but also in the signal to noise ratio of signal restoration.

fast iterative shrinkage-threshold algorithm;Barzilai-Borwein operator;total variation model;compressed sensing;image denosing

TP391

A

1673-629X(2017)10-0069-05

2016-08-10

2016-11-16 < class="emphasis_bold">網(wǎng)絡出版時間

時間：2017-07-19

國家自然科學基金資助項目(61271234)

陳少利(1990-)，女，碩士，研究方向為基于全變分模型的圖像復原算法；楊 敏，博士，副教授，研究方向為計算機視覺與圖像理解。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170719.1108.008.html

10.3969/j.issn.1673-629X.2017.10.015