喬田田,王際朝,李維國(guó),吳勃英

(1.中國(guó)石油大學(xué)理學(xué)院,山東青島 266580；2.哈爾濱工業(yè)大學(xué)數(shù)學(xué)系,黑龍江哈爾濱 150001)

一種基于線性化Bregman迭代的圖像去模糊新方法

喬田田1,2,王際朝1,李維國(guó)1,吳勃英2

(1.中國(guó)石油大學(xué)理學(xué)院,山東青島 266580；2.哈爾濱工業(yè)大學(xué)數(shù)學(xué)系,黑龍江哈爾濱 150001)

基于線性化Bregman迭代法帶有軟閾值算子的A+算法,結(jié)合廣義逆迭代格式,提出一個(gè)新的混亂迭代方法求解圖像的去模糊問(wèn)題。在算法上充分考慮對(duì)細(xì)節(jié)信息的有效利用,以彌補(bǔ)在每步迭代過(guò)程中為了去模糊而過(guò)濾掉的圖像細(xì)節(jié)特征的損失,達(dá)到有效濾波的效果。同時(shí)在計(jì)算時(shí)間和恢復(fù)效果之間取得平衡。數(shù)值試驗(yàn)結(jié)果表明,新方法在提高計(jì)算效率的同時(shí)還能得到很好的圖像恢復(fù)效果,特別是細(xì)節(jié)特征和稀疏紋理的恢復(fù)。

線性化Bregman迭代法；圖像去模糊；混亂迭代法；廣義逆

圖像恢復(fù)是圖像處理的基本問(wèn)題之一。圖像去模糊問(wèn)題主要是沿著模型和算法兩個(gè)方面發(fā)展的。模型的改進(jìn)和建立以變分法[1-2]、正則化方法[2-3]、和PDE方法[4-5]為基礎(chǔ)；而在算法上就較為廣泛,例如原-對(duì)偶方法[6]、混合梯度下降法[7]、求解PDE方程的數(shù)值解法等。近年來(lái)l1-優(yōu)化模型應(yīng)用范圍十分之廣,尤其是在信號(hào)的稀疏優(yōu)化方面[8-10]。將其用于圖像去模糊問(wèn)題,也得到了較好的結(jié)果。Osher等[11-13]將優(yōu)化中的Bregman方法用于圖像處理中l(wèi)1-優(yōu)化模型的求解,得到了快速的具有顯著效果的一系列算法。在Bregman算法的基礎(chǔ)上結(jié)合軟閾值算子,將其應(yīng)用于圖像去模糊處理中的l1-優(yōu)化模型[14-16],取得了突破性的進(jìn)展。筆者以Bregman算法為基礎(chǔ)結(jié)合廣義逆的迭代技術(shù),將其應(yīng)用于求解l1-優(yōu)化模型,提出一個(gè)新的混亂迭代算法來(lái)解決圖像去模糊問(wèn)題。

1 背景介紹

1.1 研究問(wèn)題

設(shè)Ω?R2是有界開(kāi)區(qū)域,u∈Ω表示真實(shí)圖像,觀測(cè)的模糊圖像為

式中,A為線性模糊算子；n為噪音。事實(shí)上,由于線性算子的性質(zhì),這里可以忽略n,而僅考慮Au=f。

從f中將u恢復(fù)出來(lái),最簡(jiǎn)單的方法就是Tikhonov正則化方法[2-3]:

隨之,出現(xiàn)了很多針對(duì)ROF模型的減少“梯子現(xiàn)象”的改進(jìn)模型。而近年來(lái),由于研究者將l1-稀疏優(yōu)化的方法應(yīng)用到圖像處理中取得了較好的效果,以及l(fā)1-范數(shù)本身的特點(diǎn)結(jié)合優(yōu)化思想,使得將其用以解決圖像去模糊問(wèn)題也引起了廣泛的關(guān)注[8]:

本文就是針對(duì)模型(4),提出了新的有效算法來(lái)解決圖像去模糊問(wèn)題。

1.2 廣義逆

定義1:[17]:設(shè)A∈Cm×n,若X∈Cn×m滿足下面性質(zhì),即Moore-Penrose條件:

則稱X為A的偽逆,也稱作Moore-Penrose廣義逆,記作A+。

定義2[18]:設(shè)A,B∈Cn×m,稱

這是最為熟悉的優(yōu)化模型。該模型對(duì)于圖像恢復(fù)具有一定的效果,但由于其中l(wèi)2-范數(shù)的光滑性,對(duì)于細(xì)節(jié)和邊界的恢復(fù)欠佳。而總變差模型利用TV范數(shù)克服了l2-范數(shù)過(guò)度光滑的缺點(diǎn),能夠很好地恢復(fù)邊界特征,但卻帶來(lái)了“梯子現(xiàn)象”。TV模型[1]為

是(A,B)的值域。

引理1[18]:設(shè)A∈Cm×n≠0,如果初始值V0∈Cn×m滿足:

這里I是和A同維數(shù)的單位矩陣,則由

產(chǎn)生的序列{Vq}q∈N收斂到A+.

1.3 線性化Bregman迭代法

Osher等將優(yōu)化的經(jīng)典算法用于圖像恢復(fù)TV模型的求解中,得到了Bregman迭代正則化方法、線性化Bregman迭代法和分裂Bregman迭代法,并將其應(yīng)用于公式(4)中的模型。因?yàn)閘1-范數(shù)的非光滑性,導(dǎo)致求解上較為困難。但在實(shí)際算法中,引入了軟閾值算子的線性化Bregman算法就很好地解決了這個(gè)問(wèn)題。模型(4)對(duì)應(yīng)的線性化Bregman方法的迭代格式[8]為

與之相對(duì)應(yīng)的帶有軟閾值算子的迭代算法[9]為

其中u0=v0=0,且軟閾值算子定義為

考慮到A的性質(zhì),約束條件Au=f很難被滿足,就需要利用其最小二乘解。于是,文獻(xiàn)[8]中提出了有關(guān)A是行滿秩情況下的式(11)等價(jià)AT算法:

很顯然,式(14)是滿足約束條件ATAu=ATf,即為Au=f的最小二乘解。同時(shí)考慮到方程條件數(shù)對(duì)計(jì)算的影響,在A是行滿秩情況下等價(jià)的A+算法[8]

的唯一解。因?yàn)?AAT)-21是可逆的,則式(16)等價(jià)于式(10),且當(dāng)μ→∞時(shí),式(15)收斂于式(4)的極小l2-范數(shù)解,而對(duì)于A不僅局限于行滿秩為任意矩陣時(shí),文獻(xiàn)[19]將其推廣為A-算法。從計(jì)算的角度,可以看到式(15)既能夠得到合適的最小二乘解,也充分考慮方程條件數(shù)的作用,使得計(jì)算穩(wěn)定性大大提高；但另一方面,由于A+的存在也使得計(jì)算量加大,如果將其取得平衡,使計(jì)算量不增加(甚至降低計(jì)算量)的情況下能很清楚地將信號(hào)恢復(fù),則是要進(jìn)一步探討的問(wèn)題。在下面的討論中,只考慮被推廣到A為任意矩陣時(shí)的A+算法式(15)。

2 新算法的提出

A為任意矩陣時(shí)的A+算法式(15),在每一步的迭代計(jì)算都是矩陣向量乘法運(yùn)算,但是A+的計(jì)算卻是占了絕大部分的工作量。結(jié)合引理1的迭代思想,可以得到:很明顯,這是個(gè)內(nèi)外層迭代的算法,僅僅是迭代求解A+,理論上顯示出在精度和速度上并沒(méi)有明顯的優(yōu)勢(shì)。通過(guò)結(jié)合以往混亂迭代方法的思想,將內(nèi)外層循環(huán)參數(shù)結(jié)合,提出了下面的新的混亂迭代法:

從式(19)、式(20)可知,式(17)是充分考慮了迭代求解廣義逆和利用更多步的細(xì)節(jié)信息來(lái)恢復(fù)信號(hào),同時(shí)計(jì)算量仍能保持僅有矩陣向量乘積的運(yùn)算。

3 數(shù)值試驗(yàn)

細(xì)節(jié)圖片的試驗(yàn)(圖1)是在Intel(R)Core (TM)2 Duo CPU T8100@2.10GHz 2.10GHz 1.5GB的機(jī)器上進(jìn)行的,而整體圖片(圖2)是在Intel(R)Core(TM)2 Quad CPU Q9500@2.83GHz 2.83GHz 2.0GB的環(huán)境下進(jìn)行的,MATLAB7.1。算法選取相同的初始值:計(jì)算過(guò)程中,除了列出相對(duì)誤差量級(jí)相同情況下的計(jì)算時(shí)間對(duì)比之外,還給出了信噪比,便于更直觀地比較算法的恢復(fù)效果。信噪比(RSN)采用計(jì)算公式如下:

由圖1可以看出,三種方法恢復(fù)的結(jié)果為A+和Chaotic效果較好。圖中能看出新的混亂迭代法能夠清楚的恢復(fù)圖片的細(xì)節(jié)信息,紋理特征保留較好,其去模糊的效果接近A+恢復(fù)的效果,特別是在稀疏紋理部分及細(xì)節(jié)較多部分的恢復(fù)效果更為明顯。同時(shí),在時(shí)間上新的混亂迭代法和AT線性化算法的計(jì)算時(shí)間處于相同量級(jí),遠(yuǎn)遠(yuǎn)快于A+線性化算法(表1)。也就是說(shuō),新的混亂迭代算法的優(yōu)勢(shì)在于平衡了其他兩種方法的優(yōu)勢(shì)。另外,從信噪比的對(duì)比值也可以看出,新的混亂迭代方法具有很好的圖像恢復(fù)能力,具有一定的實(shí)用價(jià)值。

圖1 圖像去模糊效果(細(xì)節(jié))Fig.1 Deblurring results of images(detail)

圖2 圖像去模糊效果(整體)Fig.2 Deblurring results of images(entirety)

由圖2可以看出,新的混亂迭代法的恢復(fù)效果是令人滿意的,特別是在模糊程度大的情況下,其細(xì)節(jié)恢復(fù)效果更佳。而此時(shí)的A+方法沒(méi)有列出恢復(fù)效果圖,是因?yàn)樵谕瑯拥倪\(yùn)行軟硬件條件下,其工作量之大已經(jīng)難以負(fù)荷。很顯然,在計(jì)算效率上A+方法和其他兩種方法不是在一個(gè)量級(jí)上的,在存儲(chǔ)空間和計(jì)算時(shí)間上的要求相對(duì)另外兩種方法苛刻很多。綜上分析,混亂迭代新算法在整體圖片的去模糊過(guò)程中,其恢復(fù)效果和計(jì)算代價(jià)的性價(jià)比是最高的,在很多應(yīng)用領(lǐng)域(雷達(dá)成像后的具體定位等)都需要快速的識(shí)別具體圖片的細(xì)節(jié)目標(biāo)(尤其在圖片的數(shù)據(jù)非常之大,例如遙感圖片壓縮后圖片數(shù)據(jù)存儲(chǔ)的規(guī)模仍然很大),這時(shí)混亂迭代算法就是實(shí)際應(yīng)用的最佳選擇。

表1 計(jì)算時(shí)間和信噪比的對(duì)比Table 1 Comparison of computing time and signal-to-noise ratio

4 結(jié)束語(yǔ)

提出的基于線性化Bregman迭代方法和廣義逆迭代技術(shù)的新算法,對(duì)圖像去模糊問(wèn)題是非常有效的。特別是在圖像模糊程度大且細(xì)節(jié)特征恢復(fù)困難的情況下,更是具有穩(wěn)定快速的性質(zhì),其優(yōu)勢(shì)是十分明顯的。而在計(jì)算耗時(shí)和工作量上面不僅保留了線性化Bregman迭代法的全部?jī)?yōu)點(diǎn),同時(shí)還大大提高了計(jì)算效率。特別適用于大規(guī)模的快速計(jì)算,例如機(jī)載、艦載圖像要求快速恢復(fù)等等。從理論分析可知,該方法是更多的考慮數(shù)據(jù)信息細(xì)節(jié)丟失的影響,

進(jìn)一步說(shuō)明了該方法是在本質(zhì)上增強(qiáng)了圖像的恢復(fù)效果。此外,還可以結(jié)合“剔除”技術(shù)來(lái)提高混亂迭代法的效率,或者考慮A+規(guī)模和工作量的因素而采用并行技術(shù)來(lái)得到更好的算法,將是下一步需要努力的目標(biāo)。

[1] RUDIN L,OSHER S,FATEMI E.Nonlinear total variation based noise removal algorithms[J].Physica D, 1992,60:259-268.

[2] VOGEL C R.Computational methods for inverse problems[M].SIAM Frontiers in Applied Mathematics Series,2002:59-82.

[3] 劉繼軍.不適定問(wèn)題的正則化方法及應(yīng)用[M].北京:科學(xué)出版社,2008:21-57.

[4] 王大凱,侯榆青,彭進(jìn)業(yè).圖像處理的偏微分方程方法[M].北京:科學(xué)出版社,2008:110-141.

[5] 張亶,陳剛.基于偏微分方程的圖像處理[M].北京:高等教育出版社,2004:40-59.

[6] CHAN T F,GOLUB G H,MULET P.A nonlinear primal-dual method for total variation-based image restoration[J].SIAM J Sci Comput,1999,20:1964-1977.

[7] ZHU M.Fast Numerical algorithms for total variation based image restoration[D].Los Angeles:University of California,Los Angeles,2008:15-50.

[8] YIN W,OSHER S,DONALD G,et al.Bregman iterative algorithms for l1-minimization with applications to compressed sensing[J].SIAM Journal of Imaging Science,2008(1):143-168.

[9] CAI J,OSHER S,SHEN Z.Linearized Bregman iterations for compressed sensing[J].Mathematics of Computation,2009,78(267):1515-1536.

[10] TSAIG Y,DONOHO D L.Extensions of compresssed sensing[J].Signal Processing,2005,86:533-548.

[11] CAI J,OSHER S,SHEN Z.Linear Bregman iterations for compressed sensing,UCLA-CAM-Report 2008-06 [R/OL].[2010-03-10].

[12] OSHER S,BURGER M,GOLDFARB D,et al.An iterative regularization method for total variation-based image restoration[J].SIAM Multiscale Model Simul, 2005,4:460-489.

[13] OSHER S,MAO Y,DONG B,et al.Fast linearized Bregman iteration for compressed sensing and sparse denoising,UCLA-CAM-Report2008-37[R/OL]. [2010-03-20].http://www.math.ucla.edu/applied/ cam/index.shtml.

[14] YANG Y,M?LLER M,OSHER S.A dual split Bregman method for fast minimization,UCLA-CAM-Report 2011-57[R/OL].[2012-01-09].http://www.math. ucla.edu/applied/cam/index.shtml.

[15] BENNING M,BRUNE C,BURGER M,et al.Higerorder TV methods-enhancement via Bregman iteration, UCLA-CAM-Report 2012-04[R/OL].[2012-03-01]. http://www.math.ucla.edu/applied/cam/index.shtml.

[16] YIN W,OSHER S.Error forgetting of Bregman iteration,UCLA-CAM-Report 2012-08[R/OL].[2012-03-18].http://www.math.ucla.edu/applied/cam/index. shtml.

[17] WANG G,WEI Y,QIAO S.Generalized inverses:theory and computations[M].Beijing:Science Press, 2004:16-37.

[18] 王松桂,楊振海.廣義逆矩陣及其應(yīng)用[M].北京:北京工業(yè)大學(xué)出版社,1996:1-5,202-205.

[19] 張慧,成禮智.A-線性Bregman迭代算法[J].計(jì)算數(shù)學(xué),2010,32:97-104.

ZHANG Hui,CHENG Li-zhi.A-linearized Bregman iteration algorithm[J].Mathmatica Numerica Sinica, 2010,32:97-104.

(編輯 修榮榮)

A new algorithm based on linearized Bregman iteration for image deblurring

QIAO Tian-tian1,2,WANG Ji-chao1,LI Wei-guo1,WU Bo-ying2
(1.College of Science in China University of Petroleum,Qingdao 266580,China；
2.Department of Mathematics,Harbin Institute of Technology,Harbin 150001,China)

A new chaotic iteration for image deblurring was proposed.The algorithm was obtained based on A+linearized Bregman iteration with soft thresholding operator,and combined with generalized inverse iterative formula.Taking full consideration of the effective use of detail information,the algorithm can compensate for the loss of image detail features which is filtered to deblur in each iteration,and achieve effectively filtering.At the same time,a balance between computation time and the recovery effect is considered.The numerical experiments furtherly show that the method can improve computation efficiency and image recovery effect,especially the recovery of the detail features and sparse texture.

linearized Bregman iteration；image deblurring；chaotic iteration；generalized inverse

TN 911

A

1673-5005(2013)02-0176-05

10.3969/j.issn.1673-5005.2013.02.029

2012-06-20

國(guó)家海洋局海洋遙測(cè)工程技術(shù)研究中心創(chuàng)新青年基金；國(guó)家自然科學(xué)基金( 60971132； 11126085；61101208)

喬田田(1983-),女,講師,博士研究生,研究方向?yàn)閳D像處理、數(shù)值計(jì)算。E-mail:qtthsnxf@126.com。