基于多尺度分解的k鄰域隨機查找快速圖像修復

廖 斌 蘇 濤 劉 斌

1 引言

圖像修復是指利用破損圖像中完好區域的像素信息對破損區域進行修復處理，得到符合人類視覺要求的修復結果的過程[13]-。其在虛擬現實、游戲、影視、產品設計等領域有廣泛的應用，是圖像處理領域的一個研究熱點。

Criminisi等人[4]提出基于樣本塊和優先級函數修復破損圖像。通過計算破損區域邊界上待修復像素點的優先級，確定像素點的修復順序，達到增強修復效果的目的。但是，該方法使用乘積來定義優先級函數，導致其會出現突然降為零的現象，無法得到魯棒的修復結果。Sun等人[5]通過用戶交互指定未知區域的結構曲線信息，使之更好地傳播，取得很好的修復效果。但是，該方法需要大量的人工交互，非常耗時。Wexler等人[6]提出一種基于樣本塊的多尺度[7]全局性時空修復方法。取出視頻的單幀圖像，并對其進行金字塔分層。從最粗糙層開始進行修復，并將像素信息映射到下一層直至取得最終的效果圖。該方法中的塊匹配過程采用暴力搜索，計算量很大，修復效果也不十分精確。為了加速塊匹配計算，PatchMatch方法[810]-通過傳播和隨機查找以獲取最佳的匹配塊。相較于KD樹[11,12]以及ANN（Approximate Nearest Neighbor）[13]，該方法有更好的加速比和更少的內存占用量。但是，其在查找匹配塊的過程中會產生檢索到冗余塊的問題。

本文提出一種基于多尺度分解的k鄰域隨機查找快速圖像修復方法。首先，基于雙邊濾波的下采樣圖像分解算法，對破損圖像進行多尺度分解，得到一系列粗糙層。從最粗糙層開始，對當前層進行圖像修復。然后，基于雙邊濾波上采樣重建下一層。基于 k鄰域（k-Nearest-Neighbor-Field, k-NNF）隨機查找算法，對每一粗糙層查找與待修復塊最相似的塊。構建最小堆來存儲k-NNF信息，有效避免檢索到冗余塊，提高查找速度。并且，采用一種魯棒的優先級函數精確地獲取塊的修復順序。

2 本文方法

設圖像的完好區域為Φ，破損區域為Ω，破損邊界為δΩ，邊界的像素集合為S。首先，對破損圖像I進行多尺度分解，得到一系列不同尺度的圖像J[ i]（ i = 0,1,… ,l -1）。其中，原始圖像為J[0]，最粗糙層為 J [ l - 1 ]。然后，使用k-NNF算法查找與S中任一點p為中心的待修復塊Ψp的k個最相似塊，進而從中計算出最佳匹配塊。修復完成每一塊后，都要更新優先級函數的置信因子，計算δΩ上像素點的優先級，確定需要修復的下一塊。同時，更新Ω和S，直至 J [ i]中沒有需要修復的Ω為止。最后，將修復結果的信息映射至下一層，重復上述修復過程，直至獲得最終的結果。

2.1 圖像的多尺度分解和重建

文獻[14,15]中提到利用高斯金字塔對圖像分解，獲得其一系列粗糙層。但是，高斯濾波會造成圖像邊緣和細節信息的大量丟失，導致不能由分解得到的信息精確重建原始信息。從盡量減少信息丟失的角度考慮，本文提出一種基于雙邊濾波的下采樣算子來對圖像進行分解。雙邊濾波[16]是一種非線性的濾波方法，其綜合考慮圖像的空間域和范圍域相似度，能夠達到保邊的效果，定義為

其中，（x, y）表示像素點的空間位置，（i, j）表示像素點（x, y）鄰域 Δx,y內的像素點空間位置，BF （ x, y）表示濾波后的輸出強度，IN（i, j）表示（i, j）的強度。w（i, j） 是雙邊濾波權， w （i, j ） = ws（i, j） wr（i, j ） ，其中，ws（i, j）為空間權，wr（i, j）為范圍權，其表達式分別為

其中，δs表示空間域的標準差，δr表示范圍域的標準差。

使用基于雙邊濾波的下采樣算子對 J [ 0]進行濾波，然后隔行隔列下采樣得到一個較粗糙的 J [ 1]。J [ 1]的尺寸變為 J [ 0]的1 4。如果對 J [ 0]作累進濾波，則會得到一系列不同尺度的粗糙層 J [ i]（ i= 1,2,…,l-1），如式（4）所示。

其中，“2↓”表示采樣率為2的下采樣操作。值得注意的是，雖然分解的層數越多，修復結果的細節越豐富，但是分解層數過多仍然會導致最粗糙層修復時損失大量信息，這在圖像重建時無法恢復。因此，不宜選取過多的層數。本文取 5l= （即分解為4層）可以得到好的結果。為了可以實時地獲取圖像多尺度分解的結果，采用Yang等人[16]提出的快速雙邊濾波算法。該算法具有（）1O的時間復雜度，并可以采用GPU進一步加速。圖1給出了一個圖像分解示例。

圖1 圖像分解示例

從 [ ]1J l- 開始，根據后文提出的修復算法對每個 []J i進行修復。利用雙邊濾波的上采樣算子對修復后的 []J i進行重建，把當前層的像素信息映射到重建層，如式（5）所示。

其中，“↑2”表示采樣率為2的上采樣操作。L（i）是第i層的高頻因子，L（i）= J [ i] - Z * （ J[ i + 1 ] ）,i =

（↑2）0,1,…,l-1，其中，Z是一個模板。圖2給出一個圖像重建示例。

2.2 最佳匹配塊搜索

圖2 圖像重建示例

在修復 []J i的過程中，關鍵是要獲得高質量的樣本塊去覆蓋待修復的塊。首先，基于k-NNF算法在Φ中查找與pΨ相似度最高的k個匹配塊，加速查找最相似塊。同時，構造最小堆用于存儲Ω中每一個Ψp的k-NNF信息，其包含k個匹配塊中心像素點的空間位置和各匹配塊與Ψp的相似度函數值。然后，利用最小堆的性質得出最佳匹配塊以完成修復。

由此，定義映射函數為fi: gS（ Ψp） → gΦ（Ψq）,i=

1,2,…,k。該公式表示在S中任意一點p為中心的Ψp都將映射到Φ中與之相似的樣本塊Ψq，映射關系為

,δ是歸一化因子。 D ist（ M , N）為兩個尺寸同為w×w的塊的顏色距離：

基于上述定義的映射函數，k-NNF由初始化、傳播和隨機查找3個步驟組成，如圖3所示。

為圖 3（a）中的初始化過程構建最小堆，如圖 4所示。最小堆由k個結點組成，分別存儲隨機選取的k個塊 Ψqi（A,B,C,…）的k-NNF信息（塊中心像素點的空間信息和塊間相似度）。建堆原則為父結點存儲的塊間相似度小于其兩個子節點，如Sim（A, Ψp）≤Sim（B,Ψp） 且Sim（A,Ψp）≤ Sim（C,Ψp） 。其余結點依此類推。

圖3 最佳匹配塊搜索

圖4 初始化最小堆

初始化對應的k個塊并不一定是相似度最好的候選塊。為了找到相似度最高的k個塊，執行傳播過程如下。若當前處理以像素點（x, y）為中心的塊Ψp，其相似塊為fi（x, y），利用其相鄰塊 fi（ x - 1 ,y）和fi（ x, y -1）來優化修復 Ψp。由此，計算Sim（fi（ x, y ）,Ψp）, Sim（fi（x - 1,y ）, Ψp）, Sim（fi（x, y-1）,Ψp）來確定相似度最高的塊，并用其空間位置信息更新fi（x, y），如圖 3（b）所示。

根據 S im（fi（ x, y ）,Ψp） 與結點A所存儲的塊間相似度的大小關系來調整最小堆。如果前者小于后者，堆保持不變。否則，用fi（x, y）的k-NNF信息來更新A。然后，依據建堆原則調整堆，使其仍然保持為一個最小堆。該過程中，堆結點移動次數為logk。由此，可以最大程度地減少比較操作，同時可以減少內存訪問，有助于提高運算速度。

在上述過程中，為了進一步提高搜索的準確度，得到更高相似度的匹配塊，如圖 3（c）所示，查找范圍將呈指數級衰減，其計算如式（8）所示。

其中，ξ為最大查找半徑， Rj是一個均勻分布于尺寸為[- 1, 1] ×[- 1,1]的窗口中的隨機變量。α是固定衰減率，α=0.5。取j=1,2,…，直至ξαj衰減為一個像素。重復該過程，可以為Ψp快速收斂計算出更高相似度的匹配塊。同時，在該過程中也要不斷更新最小堆。

2.3 基于優先級函數的塊選擇

待pΨ修復完成后，基于優先級函數來確定下一個需要修復的塊，包含如下3個步驟。

（1）塊的優先級函數定義。設以p點為中心的塊的優先級為（）Pp，則

其中，β是平衡因子。D（p）表示p點處的數據因子D （ p ）= |?np|/γ ，其中，γ 是歸一化因子， ? I⊥p是等照度線向量，np是p點的單位法向量。CR（p）表示p點的置信因子， CR（p ） = （ 1 - t ） T （ p ） + t , 0＜t≤ 1，其中，t是用以控制曲線平滑的規范化因子，Ψp表示Ψp的面積。為了避免產生Criminisi算法中（）C p可能降為零導致優先級計算結果不魯棒的問題，本文算法中（）CRp的值規范化于[ ],1t ，如圖5所示。

圖5 置信因子比較

式（9）的初始化設置為T（p）=0,?p∈Ω; T（ p）=1, ? p ∈I-Ω。同時，由于t控制置信因子曲線的平滑程度。如果t設置過大，則得到置信因子曲線將過于平緩，可能會得到相同的優先級函數值，無法確定一些像素點的修復順序，導致修復質量降低。如果t設置過小，則得到置信因子的曲線變化較大，可能導致優先級函數值趨于零，同樣影響修復質量。根據實驗測算且不失一般性，本文對所有圖像修復都選取 0.7t= 。

（2）塊修復。根據2.2節最佳匹配塊搜索算法來修復當前塊。

（3）更新置信因子。如式（10）所示，

由此，優先級函數的置信因子更加合理，可信度更高。優先級函數的可靠性和有效性也得到了很好保證，能夠得到質量更高的匹配塊。

3 實驗結果與分析

基于2.3 GHz 4核CPU, 4 GB內存的PC機硬件環境，采用 VS2010平臺實現提出的算法。如圖 6所示，給出了本文算法和 Criminisi算法以及Wexler算法的圖像修復結果比較。

圖6第1行 （尺寸為215182×）中，Wexler算法修復的效果不是很好，黑色和白色的邊界線無法保持平滑，黑色和白色相互滲透。Criminisi算法基本上達到了修復效果，但是邊緣信息不能很好地保持，并且白色區域還殘留一些未修復的像素點。本文算法取得了更好的修復結果，很好地保持了邊緣信息和紋理一致性。第2行（尺寸為206308×）中，本文算法修復后可以得到完整的細節。Criminis算法修復結果的小屋中間過渡不平滑，這主要是由于其優先級函數確定修復順序不精確所導致。Wexler算法對該幅圖像處理的效果更不好，未能有效修復破損區域。第3行（尺寸為375300×）中，對于Criminisi算法而言，由于每個小孩靠得的比較近，不能獲取穩定的置信因子，導致了修復時無法得到好的效果。Wexler算法主要是因為暴力搜索得到的結果沒有優化，傳播過程也沒優化，導致其他小孩的像素點干擾傳播過程，所以修復結果也很不理想。本文算法修復結果的質量在整體上要好一些。第4行（尺寸為340508×）中，采用Criminisi算法修復得到的云的紋理不夠自然。本文算法的修復結果更加符合人的視覺感受，修復后的圖像中的云更加接近真實場景。Wexler算法修復后的圖像中可以明顯地看到一個不應該出現的方塊。第5行（尺寸為1024801×）中，所對比的兩種算法的修復結果依然殘留有黑色像素。本文算法的修復效果明顯更好，修復的區域和相鄰的石山顏色保持一致。

為了客觀地體現本文算法的性能，計算了所有待修復塊覆蓋區域的圖像局部方差（Local Variance,LV）。如表1所示，本文算法修復結果的LV值小于其他兩種算法，表明本文算法修復結果的質量更好，和人眼的視覺體驗一致，客觀上說明本文算法的有效性。

由表1可知，本文算法運行時間優于所對比的兩種算法。尤其是破損圖像的尺寸較大時，本文算法的優勢更加明顯。

同時，本文算法在執行效率方面存在場景依賴性。如圖7所示，給出的兩行圖像尺寸大小一致（均為500300×），破損區域大小相同。但是，場景的復雜程度不同，第1行場景相對簡單，而第2行場景較為復雜。通過測算得到第1行的修復時間為52.53 s，第2行的修復時間為112.38 s，可見不同場景對本文算法的執行效率有較大的影響。

表1 修復圖像的LV值和運行時間（s）

圖6 修復結果比較

4 結束語

本文提出一種基于多尺度分解的快速隨機查找圖像修復方法。基于雙邊濾波下采樣算子分解圖像，對粗糙層采用基于最小堆的k鄰域隨機查找算法以獲取最優匹配塊。基于魯棒的優先級函數確定下一個待修復塊。每一粗糙層修復后，用雙邊濾波上采樣重建圖像。與相關方法比較，本文算法具有更高的修復質量，執行速度快。未來的工作包括如何挖掘圖像完好區域中潛在的圖像信息，解決傳播中誤差積累的問題。

圖7 不同復雜程度場景的圖像修復示例

[1] He Kai-ming and Sun Jian. Image completion approaches using the statistics of similar patches[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36（12）:2423-2435.

[2] 許建樓, 馮象初, 郝巖. 改進的TV-Stokes圖像修復模型及其算法[J]. 電子與信息學報, 2012, 34（5）: 1142-1147.Xu Jian-lou, Feng Xiang-chu, and Hao Yan. Improved TV-Stokes model and algorithm for image inpainting[J].Journal of Electronics & Information Technology, 2012, 34（5）:1142-1147.

[3] Guillemot C and Le Meur O. Image inpainting: overview and recent advances[J]. IEEE Signal Processing Magazine, 2014,31（1）: 127-144.

[4] Criminisi A, Pérez P, and Toyama K. Region filling and object removal by exemplar-based image inpainting[J]. IEEE Transactions on Image Processing, 2004, 13（9）: 1200-1212.

[5] Sun Jian, Yuan Lu, Jia Jia-ya, et al.. Image completion with structure propagation[J]. ACM Transactions on Graphic,2005, 24（3）: 861-868.

[6] Wexler Y, Shechtman E, and Irani M. Space-time completion of video[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29（3）: 463-476.

[7] 白鍵, 馮象初, 王旭東. 圖像分解的多尺度變分模型[J]. 電子與信息學報, 2013, 35（5）: 1190-1195.Bai Jian, Feng Xiang-chu, and Wang Xu-dong. A multiscale variational model for image decomposition[J]. Journal of Electronics & Information Technology, 2013, 35（5）:1190-1195.

[8] Barnes C, Goldman D B, Shechtman E, et al.. The PatchMatch randomized matching algorithm for image manipulation[J]. Communications of the ACM, 2011, 54（11）:103-110.

[9] Zheng E, Dunn E, Jojic V, et al.. PatchMatch based joint view selection and depthmap estimation[C]. Computer Vision and Pattern Recognition （CVPR）, Ohio, 2014: 1510-1517.

[10] Cozzolino D, Poggi G, and Verdoliva L. Copy-move forgery detection based on PatchMatch[C]. IEEE International Conference on Image Processing （ICIP）, Paris, 2014:5312-5316.

[11] He Kai-ming and Sun Jian. Computing nearest-neighbor fields via Propagation-Assisted KD-Trees[C]. IEEE Conference on Computer Vision and Pattern Recognition（CVPR）, Judith, 2012: 111-118.

[12] Gieseke F, Heinermann J, Oancea C, et al.. Buffer k-d trees:processing massive nearest neighbor queries on GPUs[C].Proceedings of the 31st International Conference on Machine Learning, Beijing, 2014: 172-180.

[13] Zhang H, Berg A C, Maire M, et al.. SVM-KNN:discriminative nearest neighbor classification for visual category recognition[C]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, New York,2006: 2126-2136.

[14] Ran Ling-qiang and Meng Xiang-xu. Fast seam carving using Gaussian pyramid[C]. Intelligent Human-Machine Systems and Cybernetics （IHMSC）, Hangzhou, 2014: 59-63.

[15] Ren Shuai, Lei Jing-xiang, Zhang Tao, et al.. Research of high performance information hiding scheme based on Gaussian pyramid and CARDBAL2 multi-wavelet for secret communication[J]. International Journal of Applied Mathematics and Statistics, 2014, 52（6）: 234-251.

[16] Yang Q, Tan K H, and Ahuja N. Real-time O（1） bilateral filtering[C]. IEEE Conference on Computer Vision and Pattern Recognition, Florida, 2009: 557-564.