一種應(yīng)用博弈和L0約束的盲圖像修復(fù)方法

馮象初，王 萍，何瑞強(qiáng)

(西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西 西安 710126)

圖像在獲取或處理的過(guò)程中，會(huì)受到采集設(shè)備或傳輸設(shè)備的影響，使得部分信息丟失或者毀壞[1-2]。為了解決這一類的退化問(wèn)題，需要使用圖像修復(fù)技術(shù)。目前圖像修復(fù)主要應(yīng)用于場(chǎng)景元素的去除、文物藝術(shù)品的保護(hù)、天文及遙感等領(lǐng)域[3-7]，具有重要的學(xué)術(shù)價(jià)值和應(yīng)用價(jià)值。

圖像修復(fù)[8-10]主要是利用某種規(guī)則或方法，根據(jù)圖像中已知區(qū)域的信息來(lái)推斷缺失區(qū)域內(nèi)容并將其修復(fù)的技術(shù)。修復(fù)質(zhì)量在很大程度上取決于對(duì)退化過(guò)程的掌握和原始圖像先驗(yàn)信息的了解程度。大多數(shù)圖像修復(fù)模型假定已知圖像缺失區(qū)域，但在實(shí)際中，圖像缺失區(qū)域也是未知的。由觀測(cè)圖出發(fā)，對(duì)缺失區(qū)域和原始圖像同時(shí)進(jìn)行估計(jì)，這類問(wèn)題稱為盲圖像修復(fù)[11-13]。在修復(fù)的過(guò)程中，不僅要保持圖像結(jié)構(gòu)的連續(xù)性，而且要盡可能達(dá)到或接近原始圖像的效果，同時(shí)盡量使得修復(fù)后的圖像真實(shí)自然，修補(bǔ)的痕跡不易被觀察者察覺(jué)，符合人們的視覺(jué)連貫性。

在無(wú)噪聲環(huán)境下的圖像退化[11-15]模型為

(1)

其中，f是原始圖像u的退化圖像，K是線性算子，Λ是圖像中特定像素集標(biāo)簽，隨機(jī)值v是被其他原因退化的像素值。圖像修復(fù)的主要目標(biāo)就是根據(jù)觀測(cè)圖像f估計(jì)出原始圖像u。像素集標(biāo)簽Λc表示需要恢復(fù)的區(qū)域，在一般情況下假定是已知的。但在實(shí)際應(yīng)用中，修復(fù)區(qū)域很難直接獲得。盲修復(fù)就是在修復(fù)區(qū)域Λc和原始圖像u都是未知的情況下，根據(jù)實(shí)際觀測(cè)圖像f的部分信息，對(duì)原始圖像u進(jìn)行估計(jì)的過(guò)程。圖像修復(fù)是一個(gè)非適定的逆問(wèn)題，為了解決該問(wèn)題的非適定性，需要在最小化模型的基礎(chǔ)上增加對(duì)原始圖像u和修復(fù)區(qū)域Λc適當(dāng)?shù)恼齽t項(xiàng)。

通過(guò)引入二值掩膜O(當(dāng)i∈Λ時(shí)，O等于1；當(dāng)i∈Λc時(shí)，O等于0)將退化模型進(jìn)行轉(zhuǎn)化，利用L0范數(shù)及其等價(jià)形式對(duì)數(shù)據(jù)項(xiàng)和修復(fù)區(qū)域進(jìn)行稀疏性約束，對(duì)原始圖像u采用TV[16](Total Variation)約束。根據(jù)修復(fù)區(qū)域的不同信息(已知或未知)，分別建立了非盲和盲圖像修復(fù)模型；利用增廣拉格朗日函數(shù)和博弈理論，建立了數(shù)值求解算法并進(jìn)行仿真。

1 模型的建立

基于正則化的圖像修復(fù)模型可表示為下面的最優(yōu)化問(wèn)題：

(2)

為了方便敘述，定義二值掩膜O(當(dāng)像素屬于Λ時(shí)，O等于1，否則等于0)，式(1)轉(zhuǎn)化為

OΛf=OΛ(Ku+ε)=Ku+ε，OΛcf=OΛc(v)=0 。

(3)

假設(shè)圖像像素值的動(dòng)態(tài)范圍為[umin，umax]，其中umin=0，umax=1，根據(jù)O建立不同的修復(fù)模型。

非盲圖像修復(fù)模型(O已知)：由于L0范數(shù)在優(yōu)化過(guò)程中能夠保留圖像邊緣并具有較好的稀疏性，將L0范數(shù)應(yīng)用到數(shù)據(jù)項(xiàng)，使得修復(fù)的結(jié)果圖和原始圖像之間的相似度較高，并且不易出現(xiàn)邊緣模糊的現(xiàn)象。對(duì)原始圖像u選用TV[16]進(jìn)行約束，保證修復(fù)后的圖像盡可能的光滑，則修復(fù)模型為

(4)

盲圖像修復(fù)模型(O未知)：盲圖像修復(fù)是在原始圖像u和二值掩膜O都是未知的情況下，根據(jù)觀測(cè)圖像的部分信息進(jìn)行修復(fù)。在修復(fù)的過(guò)程中不僅修復(fù)出原始圖像，還需要估計(jì)出二值掩膜。因此，在模型式(4)的基礎(chǔ)上增加L0范數(shù)對(duì)二值掩膜O的約束，以模擬丟失的像素是稀疏的，則盲修復(fù)模型為

(5)

其中，λ1和λ2是正參數(shù)，0<λ2<1。

式(4)和式(5)都選用了L0范數(shù)，為了便于求解，需要將其進(jìn)一步轉(zhuǎn)化。

2 模型(4)的轉(zhuǎn)化與求解

2.1 模型(4)的轉(zhuǎn)化

利用引理1[17](Mathematical Program with Equilibrium Constraints，MPEC)對(duì)L0范數(shù)進(jìn)行替換。

引理1對(duì)于任給的向量w∈Rn，有以下結(jié)論成立：

(6)

其中，〈，〉表示內(nèi)積；向量v中的元素vi∈[0，1]。v*=1-sign(|w|)，是式(6)最小化問(wèn)題的惟一最優(yōu)解。

根據(jù)引理1，引入輔助變量v，將非盲圖像修復(fù)模型式(4)轉(zhuǎn)化為：

(7)

如果u*是式(4)的全局最優(yōu)解，則(u*，1-sign(|Ku*-f|))是式(7)的全局最優(yōu)解；相反，如果(u*，v*)是式(7)的全局最優(yōu)解，則u*是式(4)的全局最優(yōu)解。雖然式(7)中的帶平衡約束的數(shù)字規(guī)劃(MPEC)問(wèn)題是在式(4)的基礎(chǔ)上增加L0范數(shù)的維度得到的，但它并沒(méi)有產(chǎn)生額外的局部最優(yōu)解。相比于式(4)，式(7)是一個(gè)非凸非光滑的最小值問(wèn)題，它的非凸性是由于增加了v⊙|O⊙(Ku-f)|=0的約束而導(dǎo)致的。下面給出模型式(7)的求解方法。

2.2 PADMM算法

式(7)中的L0范數(shù)不顯式存在，但由于它的非凸非光滑性，很難進(jìn)行求解。筆者在proximal ADMM[18]算法的基礎(chǔ)上，通過(guò)不斷迭代地更新式(7)的增廣拉格朗日函數(shù)中的原始變量和對(duì)偶變量得到最優(yōu)解。

首先，引入兩個(gè)輔助變量x，y，將式(7)轉(zhuǎn)化為

(8)

式(8)是關(guān)于兩個(gè)變量的優(yōu)化問(wèn)題，且目標(biāo)函數(shù)是兩塊可分的凸問(wèn)題。ADMM算法[19]能夠利用目標(biāo)函數(shù)的可分性，將其分解成幾個(gè)子問(wèn)題。

然后，并行求解每個(gè)子問(wèn)題，提高算法的運(yùn)行速度。主要解決可分解的凸優(yōu)化問(wèn)題，在弱條件下的收斂性仍成立。并在實(shí)際應(yīng)用中，ADMM較原始的對(duì)偶方法(如對(duì)偶下降法，乘子法)收斂速度更快，則式(8)的增廣拉格朗日函數(shù)為

(9)

其中，ξ，ζ，π分別是?u=x，Ku-f=y和v⊙O⊙|y|=0約束的增廣拉格朗日乘子(對(duì)偶變量)；β>0，是懲罰參數(shù)。ADMM更新是通過(guò)固定其他原始變量和對(duì)偶變量，每次只優(yōu)化一組變量，對(duì)偶變量采用梯度上升法進(jìn)行更新的。在算法1中，為了方便敘述，將第t次迭代的增廣拉格朗日函數(shù)記為L(zhǎng)t(·)。變量更新時(shí)，除了當(dāng)前變量外，其他原始和對(duì)偶變量都保持當(dāng)前估計(jì)值。

算法1具有可分結(jié)構(gòu)的凸優(yōu)化問(wèn)題式(8)的proximal ADMM。其主要步驟為：

(10)

(11)

(12)

步驟3 更新增廣拉格朗日乘子：

ξt+1=ξt+β(?ut-xt) ，

(13)

ζt+1=ζt+β(Kut-f-yt) ，

(14)

πt+1=πt+β(vt⊙O⊙|yt|) 。

(15)

步驟4 迭代停止條件：如果t>30且‖?ut-xt‖+‖Kut-f-yt‖+‖vt⊙O⊙|yt|‖<1/255。

步驟6 令t=t+1，重復(fù)計(jì)算步驟1～步驟5。

步驟7 輸出最優(yōu)估計(jì)值u。

下面詳細(xì)討論式(10)～(12)的求解。

(16)

因此，式(10)的解為

ut+1=min(1，max(0，gt)) 。

(17)

ct=1-O⊙πt⊙|yt|，st=O⊙yt。

通過(guò)計(jì)算，式(11)的解為

(18)

通過(guò)計(jì)算，變量x的解為

(19)

qt=Kut-f+ζt/β，wt=O⊙vt+1。

通過(guò)計(jì)算，變量y的解為

(20)

算法1在實(shí)踐中有很好的收斂性，但式(7)是一個(gè)非凸的優(yōu)化問(wèn)題，因此必須加入額外的條件保證其收斂到KKT(Karush-Kuhn-Tucker)點(diǎn)。

下面給出算法1 的收斂性。

定理1算法1的收斂性[17]。

2.3 非盲圖像修復(fù)模型的求解

非盲修復(fù)模型式(4)利用L0范數(shù)的等價(jià)形式，轉(zhuǎn)化為式(7)，其目標(biāo)函數(shù)是帶有等式約束的兩塊可分的凸問(wèn)題，可利用算法1求出最優(yōu)解。

算法2非盲修復(fù)模型式(4)的求解。其主要步驟為：

步驟1 輸入觀測(cè)圖像f；

步驟2 設(shè)置初始參數(shù)λ；

3 模型(5)的轉(zhuǎn)化與求解

3.1 模型(5)的轉(zhuǎn)化

盲圖像修復(fù)模型式(5)：

其中，λ1和λ2是正參數(shù)，0<λ2<1。

由于盲圖像修復(fù)是關(guān)于原始圖像u和二值掩膜O的最小化問(wèn)題，是兩個(gè)不同的目標(biāo)，而博弈論是分析多個(gè)參與者之間決策相互影響的數(shù)學(xué)理論，其3個(gè)要素為參與者、決策集、目標(biāo)函數(shù)，一個(gè)參與者在自己的決策集中確定的決策方案不僅影響到自己的目標(biāo)函數(shù)值，也影響到其他參與者的決策選擇。因此，假設(shè)參與者A修復(fù)原始圖像，參與者B估計(jì)二值掩膜，A要在所有可能的圖像中找到最優(yōu)的恢復(fù)圖像，B要在所有的可能中找到最優(yōu)的缺失區(qū)域信息，在求解過(guò)程中，關(guān)鍵是雙方目標(biāo)函數(shù)的選擇。A的目標(biāo)函數(shù)為

(21)

式(21)的極小值對(duì)應(yīng)恢復(fù)的結(jié)果圖，O作為參數(shù)。B的目標(biāo)函數(shù)為

(22)

式(22)的極小值對(duì)應(yīng)缺失區(qū)域的信息，u作為參數(shù)。

式(21)意味著如果給定O，參與者A可以利用能量泛函恢復(fù)出干凈圖像u。對(duì)B來(lái)說(shuō)，如果有干凈圖像u，則可以利用式(22)得到最優(yōu)的缺失區(qū)域。二值博弈，達(dá)到納什均衡點(diǎn)(u*，O*)。因此，利用博弈理論對(duì)u和O交替迭代。

由于式(21)中的數(shù)據(jù)項(xiàng)選用了L0范數(shù)，使其計(jì)算困難。與非盲問(wèn)題類似，利用引理1，通過(guò)引入輔助變量v，將其進(jìn)一步轉(zhuǎn)化為

(23)

盡管式(22)中有兩個(gè)L0范數(shù)，但其解可直接給出，所以保持其形式不變。最終的迭代公式為

3.2 盲圖像修復(fù)模型的求解

盲修復(fù)要得到干凈圖像和缺失區(qū)域，這兩個(gè)目標(biāo)相互影響，符合博弈的性質(zhì)。根據(jù)博弈論將盲修復(fù)模型式(5)分解成兩個(gè)目標(biāo)的交替迭代，在此過(guò)程中，干凈圖像的估計(jì)和非盲修復(fù)模型類似，用算法2求得，然后與缺失區(qū)域交替迭代。

算法3盲修復(fù)模型式(5)的基于博弈的兩個(gè)變量的交替迭代方法。其主要步驟為：

步驟1 輸入觀測(cè)圖像f。

步驟2 設(shè)置初始參數(shù)λ1和初始估計(jì)值O。

步驟3 交替求解子問(wèn)題：① 給定Ot通過(guò)式(23)求解出ut+1；

② 將ut+1代入式(22)求解出Ot+1。

步驟4 迭代停止條件：max|ut+1-ut|<1e-4或max|Ot+1-Ot|=0。

步驟5 令t=t+1，重復(fù)計(jì)算步驟3～步驟4。

下面詳細(xì)敘述式(23)和式(22)的求解。

①u子問(wèn)題式(23)的求解：

在二值掩膜O給定的情況下，式(23)和非盲圖像修復(fù)模型式(7)相似，可根據(jù)算法2求出最優(yōu)的u。

②O子問(wèn)題式(22)為

因?yàn)?<λ2<1，通過(guò)計(jì)算，式(22)的解為

(24)

如果有干凈圖像u，則可根據(jù)式(24)求出最優(yōu)的O。

4 實(shí)驗(yàn)結(jié)果

4.1 實(shí)驗(yàn)環(huán)境

在Windows10下，使用8GB內(nèi)存Inter(R)Core(TM)i5-8250U CPU @1.60Hz 1.80GHZ.PC及MATLAB2018軟件。

4.2 模型測(cè)試

該部分主要對(duì)上面提出的修復(fù)模型進(jìn)行測(cè)試。根據(jù)退化算子是單位算子(單位矩陣)或模糊算子(標(biāo)準(zhǔn)差為0.5，大小為3×3的高斯濾波)、二值掩膜的已知和未知及其不同比例(圖像丟失像素的個(gè)數(shù)占整個(gè)圖像像素個(gè)數(shù)的比例)4種情況進(jìn)行測(cè)試，采用峰值信噪比(Peak Signal to Noise Ratios，PSNR)對(duì)修復(fù)圖像進(jìn)行客觀評(píng)價(jià)。

用隨機(jī)生成二值矩陣來(lái)模擬圖像的缺失區(qū)域得到退化圖像。在非盲修復(fù)中，圖像缺失信息是已知的，修復(fù)的過(guò)程中用到了缺失區(qū)域的信息；在盲修復(fù)中，圖像缺失區(qū)域的信息是未知的，修復(fù)時(shí)首先任給一個(gè)初始的缺失信息，然后通過(guò)干凈圖像和缺失區(qū)域的交替迭代得到最優(yōu)解。不失一般性，為了對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，采用“l(fā)enna”圖進(jìn)行仿真。圖1和圖2分別是退化算子為單位算子且像素值缺失40%以及模糊算子和像素值缺失20%的情況下，文中修復(fù)算法得到的實(shí)驗(yàn)結(jié)果。在主觀條件下，算法2和算法3的恢復(fù)效果無(wú)明顯差別。

圖1 在單位算子的情況下，“l(fā)enna”圖缺失40%的實(shí)驗(yàn)圖像

圖2 在模糊算子的情況下，“l(fā)enna”圖缺失20%的實(shí)驗(yàn)圖像

下面進(jìn)行客觀質(zhì)量評(píng)價(jià)。當(dāng)“l(fā)enna”圖缺失不同比例時(shí)，兩種算法恢復(fù)出結(jié)果圖的峰值信噪比值如表1和表2所示。在客觀條件下，當(dāng)退化算子相同時(shí)，算法2比算法3恢復(fù)的效果好。當(dāng)模型相同時(shí)，退化算子是模糊算子，相比較單位算子，恢復(fù)出原始圖像的效果要好。

表1 退化算子是單位算子時(shí)的峰值信噪比

表2 退化算子是模糊算子時(shí)的峰值信噪比

4.3 收斂性分析

不失一般性，對(duì)“house”圖像缺失30%且退化算子是模糊算子進(jìn)行收斂性分析，記錄每次迭代時(shí)的目標(biāo)函數(shù)值，得到圖3。

(a) 非盲修復(fù)能量變化

(b) 盲修復(fù)能量變化

在非盲修復(fù)能量變化圖3(a)中，由于目標(biāo)函數(shù)的非凸性和拉格朗日乘子的動(dòng)態(tài)更新(算法1)，目標(biāo)函數(shù)值不一定是單調(diào)下降的；在迭代20次之后目標(biāo)函數(shù)值保持穩(wěn)定，說(shuō)明非盲修復(fù)模型(算法2)是收斂的。在盲修復(fù)能量變化圖3(b)中，迭代次數(shù)較少，因?yàn)樵撃Ｐ褪窃诜敲ば迯?fù)算法得到較好的結(jié)果的基礎(chǔ)上進(jìn)行的交替迭代，在迭代5次以后目標(biāo)函數(shù)值基本不變，表明盲修復(fù)模型(算法3)是收斂的。

4.4 算法對(duì)比

下列的3種修復(fù)算法和文中算法類似，是用來(lái)解決基于正則化建立的修復(fù)模型。采用基于梯度的正則模型，主要區(qū)別是數(shù)據(jù)項(xiàng)或正則項(xiàng)的約束有所不同。① L02TV_AOP[20](The Adaptive Outlier Pursuit)：用L2范數(shù)作為數(shù)據(jù)項(xiàng)約束，L0范數(shù)對(duì)圖像未知缺失區(qū)域進(jìn)行稀疏性約束建立的盲修復(fù)模型，采用自適應(yīng)異常點(diǎn)追蹤算法求解。② L1TV_SBM[21](The Split Bregman Method)：選用L1范數(shù)對(duì)數(shù)據(jù)項(xiàng)約束并用分裂的Bregman方法進(jìn)行求解。③ L0TV_PDA[22](The Penalty Decomposition Algorithm)：采用L0范數(shù)對(duì)數(shù)據(jù)項(xiàng)約束并用懲罰分解算法求解。故選擇它們進(jìn)行實(shí)驗(yàn)結(jié)果對(duì)比。

由于L02TV_AOP是對(duì)盲圖像建立的修復(fù)模型，L1TV_SBM和L0TV_PDA是對(duì)非盲圖像建立的修復(fù)模型，因此對(duì)L1TV_SBM和L0TV_PDA模型進(jìn)行非盲圖像測(cè)試，對(duì)L02TV_AOP模型進(jìn)行盲圖像修復(fù)測(cè)試。實(shí)驗(yàn)中，觀測(cè)圖像與文中算法測(cè)試的處理方法一致，不失一般性，選用“cameraman”圖進(jìn)行測(cè)試。表3和表4分別是當(dāng)退化算子是單位算子和模糊算子的情況下的非盲圖像修復(fù)的結(jié)果，表5和表6分別是當(dāng)退化算子是單位算子和模糊算子的情況下的盲圖像修復(fù)的結(jié)果。

表3 退化算子是單位算子的非盲圖像修復(fù)結(jié)果

表4 退化算子是模糊算子的非盲圖像修復(fù)結(jié)果

表5 退化算子是單位算子的盲圖像修復(fù)結(jié)果

表6 退化算子是模糊算子的盲圖像修復(fù)結(jié)果

通過(guò)對(duì)比表3～6中的峰值信噪比值可知，無(wú)論是盲圖像修復(fù)還是非盲圖像修復(fù)，當(dāng)退化算子相同時(shí)，算法2或算法3中的模型都比現(xiàn)有修復(fù)模型的峰值信噪比值高。在非盲圖像修復(fù)的測(cè)試中，算法2 在L1TV_SBM和L0TV_PDA上有了很大的改進(jìn)。L1TV_SBM與L0TV_PDA和算法2相比，L0范數(shù)稀疏性約束比L1范數(shù)約束的結(jié)果要好一點(diǎn)。L0TV_PDA與算法2對(duì)比，算法2對(duì)L0范數(shù)的求解比L0TV_PDA效果好。在盲圖像修復(fù)的測(cè)試中，由于數(shù)據(jù)項(xiàng)選用了L0范數(shù)的稀疏性先驗(yàn)，算法3的結(jié)果優(yōu)于L02TV_AOP。在相同算法的條件下，模糊算子比單位算子的峰值信噪比值高，恢復(fù)的效果較好。

5 總 結(jié)

筆者利用L0范數(shù)的稀疏性先驗(yàn)和L0范數(shù)的等價(jià)形式，提出了非盲圖像修復(fù)模型和基于博弈的盲圖像修復(fù)模型。模型選用L0范數(shù)對(duì)數(shù)據(jù)項(xiàng)或正則項(xiàng)進(jìn)行約束，使得修復(fù)后的結(jié)果圖與原始圖像盡可能接近，適用于無(wú)噪聲圖中缺失區(qū)域已知和未知兩種情況?；谀Ｐ偷奶匦?，設(shè)計(jì)了臨近交替方向乘子(PADMM)算法和基于博弈的交替算法進(jìn)行求解。通過(guò)與現(xiàn)有修復(fù)模型進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明所提出的模型在視覺(jué)效果和數(shù)值指標(biāo)上都有較好的結(jié)果。

以上主要對(duì)無(wú)噪聲情形設(shè)計(jì)了模型和算法，并用數(shù)值實(shí)驗(yàn)驗(yàn)證了模型的可行性。在以后的研究中，將從理論上討論模型解的性質(zhì)，進(jìn)一步探究在此基礎(chǔ)上對(duì)含有噪聲的圖像進(jìn)行修復(fù)。