基于結(jié)構(gòu)的圖像補全算法研究

黃梓珊，田秀云

（廣東海洋大學(xué)電信學(xué)院，廣東湛江 524088）

0 引言

早期由于技術(shù)有限，很多照片、圖片都無法很好地保存，特別是古畫古文和一些珍貴的老照片，如果這些文物因為時間的流逝而逐漸銷毀，那么也許會是整個世界的一大遺憾，于是圖像補全技術(shù)應(yīng)運而生。圖像補全技術(shù)早在20 世紀(jì)末到21 世紀(jì)初，甚至更早，就有學(xué)者在研究。以前比較經(jīng)典的圖像補全算法是基于偏微分方程PDE 的圖像補全算法BSCB[1]，原理是利用未知區(qū)域的邊緣信息估計等照度線方向，采用熱擴散方程將已知區(qū)域的信息傳播到未知區(qū)域，從而獲得目標(biāo)圖像[2]，該算法曾經(jīng)一度成為國際上比較熱門的研究課題，所以基于PDE/泛函的圖像補全技術(shù)在早年發(fā)展地很快，但是PDE 圖像補全技術(shù)仍然存在比較明顯的不足。PDE圖像補全技術(shù)不足的根源主要是忽略了圖像修復(fù)過程的先后順序，從而使得圖像中的顯著結(jié)構(gòu)發(fā)生模糊、扭曲、消失的概率大大提升。修復(fù)先后順序之所以重要，是因為后面要修復(fù)的補丁信息一定是在前面補丁的信息基礎(chǔ)上進行的，也就是這里存在著信息傳遞，如果一開始修復(fù)的是無關(guān)緊要的信息，那么如果信息傳遞到后面補丁，那么這些信息也其實作用也不大。

本文主要針對PDE 圖像補全技術(shù)的缺點和不足，結(jié)合結(jié)構(gòu)傳播和紋理合成等方法作為研究內(nèi)容，對PDE 補全技術(shù)進行優(yōu)化，使得圖像補全更為真實、自然。

1 用戶交互

因為該項目是基于結(jié)構(gòu)的圖像補全，而結(jié)構(gòu)其實就是用戶給的，所以需要用戶交互界面讓用戶可以繪制掩模和定義結(jié)構(gòu)線。

1.1 選擇圖片

用戶通過鍵盤按鍵選擇“[”或者“]”來切換上一張或下一張圖像，最后選擇好目標(biāo)圖像按“ESC”確認(rèn)選擇，在切換圖像時，運用了循環(huán)加減算法保證在切換的時候不會溢出，圖1 所示為本文選擇用于圖像補全的圖片。

圖1 用戶界面顯示

1.2 獲取用戶鼠標(biāo)輸入

回調(diào)函數(shù)是一個在框架設(shè)計之初留下的一個還未實現(xiàn)的接口，專門給編程者實現(xiàn)的[3]，通過這個函數(shù)獲取鼠標(biāo)終端的坐標(biāo)和行為，從而繪制出的掩模和結(jié)構(gòu)線，如圖2所示。

圖2 通過鼠標(biāo)回調(diào)函數(shù)繪制的掩模和結(jié)構(gòu)

2 結(jié)構(gòu)傳播

2.1 原理分析

用戶指定的結(jié)構(gòu)線會貫穿未知區(qū)域，延伸到已知區(qū)域，沿著這條結(jié)構(gòu)線以一定的步長進行采樣，可以得到一系列錨點，每一個錨點代表了一個塊的中心。結(jié)構(gòu)傳播的任務(wù)就是從已知區(qū)域的塊中選取最合適的去填補未知區(qū)域的每個塊，以恢復(fù)出完整連貫的結(jié)構(gòu)。這樣的任務(wù)可以被抽象成一個圖的貼標(biāo)簽問題[4]。

未知區(qū)域的目標(biāo)塊源自于已知區(qū)域patch以及已知區(qū)域衍生的patch，所以待填充的塊的選擇是很多的，那么該如何選擇最優(yōu)塊就正好是該算法需要考慮的重要問題之一，對于如何選取最合適的塊，有如下3個標(biāo)準(zhǔn)：（1）結(jié)構(gòu)相似性，每個未知塊與對應(yīng)已知塊的結(jié)構(gòu)線走向的相似性；（2）完整性，處在邊緣的未知塊與已知區(qū)域會有重疊，重疊部分像素與已知區(qū)域像素的相似性；（3）連貫性，在未知區(qū)域中，算法補上去的兩個相鄰的塊的重疊部分對應(yīng)位置像素的相似性。綜合上述3 個標(biāo)準(zhǔn)并進行量化，可以得到圖的能量函數(shù)（損失函數(shù)）：

這里的算法任務(wù)是能量最小化問題。如果要找出某一個未知區(qū)域目標(biāo)塊，應(yīng)對比其與其他已知塊的損失函數(shù)，找出損失函數(shù)的最小值，將找出來的patch填入未知區(qū)域。

2.2 動態(tài)規(guī)劃（單結(jié)構(gòu)線）

動態(tài)規(guī)劃在數(shù)學(xué)、計算機科學(xué)等各種領(lǐng)域均有廣泛應(yīng)用[5]。動態(tài)規(guī)劃指在解決某些最優(yōu)問題時，可將原問題的過程分解為相對簡單的子問題的方式，從而簡化求解復(fù)雜問題步驟[6]。

通過上面的式子計算出每一個點的損失函數(shù)E后，接下來就需要開始求其最小值，如果是單結(jié)構(gòu)線，那么就說明G是單鏈表，圖中的節(jié)點呈鏈狀排列，符合動態(tài)規(guī)劃操作的條件，所以損失函數(shù)的最小化問題可以使用最短路徑來代替解決，動態(tài)規(guī)劃算法可以理解為在每個節(jié)點處選擇當(dāng)前的最優(yōu)結(jié)果，然后用最短路徑和記錄損失，其中最短路徑和就是Mi(xi)，表示對于一切可能的xi，從節(jié)點1 到節(jié)點i最小路徑和，其定義和初值分別如下式所示：

初始值M1(x1)可以理解為是Mi(xi)的遞推初值，EI指的是邊緣塊與已知區(qū)域重疊部分的相似性，該項可以直接求出，另一項min 值是上一次的求解結(jié)果，是已知量，可以直接加上去，根據(jù)這兩式不斷進行遞推，最終即可將后面的每一個節(jié)點的M值求出。以最后一個節(jié)點L（last anchor）為例，其最優(yōu)標(biāo)簽根據(jù)下式選?。?/p>

式中：argmin 為一種方法，其功能是獲取使后面ML(xL)達到最小值時的變量的取值[12]。

2.3 置信度傳播（多結(jié)構(gòu)線/圖結(jié)構(gòu)）

貝葉斯定理是置信傳播算法的基礎(chǔ)，貝葉斯定理可以完美結(jié)合問題的不確定性和已知知識，轉(zhuǎn)成概率論中的推理問題，從而尋找全局最優(yōu)解。而馬爾科夫隨機場是一種特殊的貝葉斯網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點滿足馬爾科夫性質(zhì)，也就是網(wǎng)絡(luò)中某節(jié)點的概率分布特性只與其領(lǐng)域內(nèi)的點有關(guān)，與領(lǐng)域外的點無關(guān)[7]。而置信傳播的主要思想，就是對于馬爾科夫隨機場中的每一個節(jié)點，通過消息傳播，將其概率分布傳給相鄰節(jié)點，從而影響其他節(jié)點的概率分布情況，經(jīng)過一定次數(shù)的迭代，可以使得所有節(jié)點的概率分布都趨于穩(wěn)態(tài)，所以某點置信度可以理解為是某點的邊緣概率分布[8]。

對于存在多結(jié)構(gòu)線和交叉點的圖像，如果單純使用動態(tài)規(guī)劃算法算最小E（X）是很不劃算的，因為計算成本很高，所以改用置信度傳播來算出最小E（X），那么將會高效許多，因為每個點只需要傳遞給領(lǐng)域內(nèi)的節(jié)點即可，然后不斷往外擴散，而不需要對所有節(jié)點依次傳輸，時間復(fù)雜度驟減，算法輕便很多。

為了實現(xiàn)置信度傳播，本文構(gòu)造一個矩陣M用于存儲當(dāng)前圖中每個節(jié)點對其每個鄰點的信息，如Mij是從i節(jié)點傳給j節(jié)點的消息。該信息反映了一個節(jié)點在多大程度上相信其鄰點獲得了最優(yōu)標(biāo)簽，之后再通過不斷的迭代更新，即可獲取到最優(yōu)塊的信息。

2.4 結(jié)構(gòu)傳播結(jié)果顯示

結(jié)構(gòu)傳播結(jié)果顯示如圖3所示。

圖3 結(jié)構(gòu)傳播之后的南瓜

3 紋理傳播

如圖4 所示，經(jīng)過結(jié)構(gòu)傳播之后，只是將重要結(jié)構(gòu)處的像素值優(yōu)先補全，但是除了結(jié)構(gòu)線區(qū)域，還剩下許多的未知區(qū)域，而這部分的像素值補全就需要用到紋理傳播技術(shù)。

圖4 應(yīng)用Texture-by-numbers技術(shù)后的區(qū)域編號

3.1 原理分析

為了保證紋理合成符合視覺一致性，避免紋理合成中利用其他不相關(guān)的區(qū)域信息，因此紋理合成需要使用texture-by-number的技術(shù)[9]，這種技術(shù)的意思就是給結(jié)構(gòu)傳播之后的圖像分區(qū)，如圖4 所示，可以發(fā)現(xiàn)被結(jié)構(gòu)線切斷的區(qū)域與其相鄰的已知區(qū)域編號相同，那么就意味著，這些未知區(qū)域由與其同編號的已知區(qū)域負(fù)責(zé)填補。因為通常不同的區(qū)域會擁有不同類型的紋理，而對于一塊未知區(qū)域，只從與其相同編號的已知區(qū)域去合成紋理，這樣就基本上保證了紋理類型的正確性。

子區(qū)域處理的次序根據(jù)置信圖確定，是一種水平集方法，從最靠近已知區(qū)域的塊開始處理，每次選取優(yōu)先級最高的塊，向內(nèi)擴散。求取邊界上的紋理塊的優(yōu)先級的算法思路是：（1）在需要填充區(qū)域的輪廓上計算權(quán)重，選擇權(quán)重最大的輪廓點作為待填充點；（2）在該點周圍領(lǐng)域取一個固定大小的塊，在圖像其他區(qū)域內(nèi)找該塊的最近鄰的塊；（3）將最近鄰patch塊所對應(yīng)的需要填充的區(qū)域部分復(fù)制到等待填充的區(qū)域；（4）填充完成后，更新confidence 的值。再重復(fù)上述步驟，直至所有點都填充完畢[9-11]。

3.2 結(jié)果顯示

將圖片應(yīng)用Texture-by-numbers 技術(shù)之后，進行紋理合成即可形成圖5 所示效果，雖然交接處有些扭曲，但對比原圖可發(fā)現(xiàn)，該方法確實可以有效地將目標(biāo)區(qū)域去掉并補全。而若不使用結(jié)構(gòu)傳播，對南瓜圖畫好掩模之后直接采取紋理合成，那么結(jié)果圖如圖6 所示，對比一下即可明顯發(fā)現(xiàn)其效果遠遠不及圖5，所需填補的部分模糊且結(jié)構(gòu)不清晰，可以說是亂成一團，因此更加證明了采用結(jié)構(gòu)傳播的重要性。

圖5 結(jié)構(gòu)傳播+紋理傳播的效果

圖6 紋理合成的效果

4 光測度一致性調(diào)整

光測度一致性是專門用于解決塊之間由于重疊而產(chǎn)生的縫隙問題，因為不論是結(jié)構(gòu)傳播亦或是紋理合成都是根據(jù)對比塊，在已知區(qū)域塊的基礎(chǔ)上直接復(fù)制粘貼到未知區(qū)域的，所以不論這個塊性能多好，和原圖相比難免會有些生硬，在重疊處很容易存在鋸齒狀以及不平滑現(xiàn)象，而光測度一致性就是為了解決這一問題的[10]。

通過光測度一致性，可以將像素點之間梯度較大的部分削減，令邊界看起來更加和諧，從而實現(xiàn)圖像間或者像素之間的融合，如此一來即可完成光測度一致性調(diào)整。

5 結(jié)果顯示

圖7 所示為整個算法的過程圖，按照從左到右，從上到下的順序進行。

圖7 整個項目流程以及結(jié)果展示

6 結(jié)束語

隨著時代的發(fā)展，圖像補全技術(shù)已經(jīng)被越來越廣泛地應(yīng)用于深度學(xué)習(xí)、計算機視覺以及現(xiàn)在高速網(wǎng)絡(luò)傳播，本文由以前比較經(jīng)典的圖像補全算法——基于偏微分方程PDE 的圖像補全算法BSCB 出發(fā)，分析他的貢獻與不足，然后根據(jù)其不足引用了其他的方法進行彌補。引用了結(jié)構(gòu)傳播技術(shù)之后，可以優(yōu)先補全重要結(jié)構(gòu)像素點，使得最后的紋理傳播可以得到更好的優(yōu)化結(jié)果，雖然無法滿足百分之百的視覺一致性，但相比于非結(jié)構(gòu)傳播，效果還是好了很多。同時，本文從用戶感知視覺和用戶需求出發(fā)，不僅僅是以修復(fù)圖像為主的補全，而是讓用戶挑選出想要去掉的部分，并且勾勒背景結(jié)構(gòu)，然后算法再專門對該部分進行補全和修復(fù)。