基于結構的圖像補全算法研究

黃梓珊，田秀云

（廣東海洋大學電信學院，廣東湛江 524088）

0 引言

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

本文主要針對PDE 圖像補全技術的缺點和不足，結合結構傳播和紋理合成等方法作為研究內容，對PDE 補全技術進行優化，使得圖像補全更為真實、自然。

1 用戶交互

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

1.1 選擇圖片

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

圖1 用戶界面顯示

1.2 獲取用戶鼠標輸入

回調函數是一個在框架設計之初留下的一個還未實現的接口，專門給編程者實現的[3]，通過這個函數獲取鼠標終端的坐標和行為，從而繪制出的掩模和結構線，如圖2所示。

圖2 通過鼠標回調函數繪制的掩模和結構

2 結構傳播

2.1 原理分析

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

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

這里的算法任務是能量最小化問題。如果要找出某一個未知區域目標塊，應對比其與其他已知塊的損失函數，找出損失函數的最小值，將找出來的patch填入未知區域。

2.2 動態規劃（單結構線）

動態規劃在數學、計算機科學等各種領域均有廣泛應用[5]。動態規劃指在解決某些最優問題時，可將原問題的過程分解為相對簡單的子問題的方式，從而簡化求解復雜問題步驟[6]。

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

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

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

2.3 置信度傳播（多結構線/圖結構）

貝葉斯定理是置信傳播算法的基礎，貝葉斯定理可以完美結合問題的不確定性和已知知識，轉成概率論中的推理問題，從而尋找全局最優解。而馬爾科夫隨機場是一種特殊的貝葉斯網絡，網絡中的節點滿足馬爾科夫性質，也就是網絡中某節點的概率分布特性只與其領域內的點有關，與領域外的點無關[7]。而置信傳播的主要思想，就是對于馬爾科夫隨機場中的每一個節點，通過消息傳播，將其概率分布傳給相鄰節點，從而影響其他節點的概率分布情況，經過一定次數的迭代，可以使得所有節點的概率分布都趨于穩態，所以某點置信度可以理解為是某點的邊緣概率分布[8]。

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

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

2.4 結構傳播結果顯示

結構傳播結果顯示如圖3所示。

圖3 結構傳播之后的南瓜

3 紋理傳播

如圖4 所示，經過結構傳播之后，只是將重要結構處的像素值優先補全，但是除了結構線區域，還剩下許多的未知區域，而這部分的像素值補全就需要用到紋理傳播技術。

圖4 應用Texture-by-numbers技術后的區域編號

3.1 原理分析

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

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

3.2 結果顯示

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

圖5 結構傳播+紋理傳播的效果

圖6 紋理合成的效果

4 光測度一致性調整

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

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

5 結果顯示

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

圖7 整個項目流程以及結果展示

6 結束語

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