廖 斌 蘇 濤 劉 斌

1 引言

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

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

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

2 本文方法

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

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

文獻[14,15]中提到利用高斯金字塔對圖像分解，獲得其一系列粗糙層。但是，高斯濾波會造成圖像邊緣和細節(jié)信息的大量丟失，導致不能由分解得到的信息精確重建原始信息。從盡量減少信息丟失的角度考慮，本文提出一種基于雙邊濾波的下采樣算子來對圖像進行分解。雙邊濾波[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]的尺寸變?yōu)?J [ 0]的1 4。如果對 J [ 0]作累進濾波，則會得到一系列不同尺度的粗糙層 J [ i]（ i= 1,2,…,l-1），如式（4）所示。

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

圖1 圖像分解示例

從 [ ]1J l- 開始，根據(jù)后文提出的修復算法對每個 []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的相似度函數(shù)值。然后，利用最小堆的性質得出最佳匹配塊以完成修復。

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

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

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

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

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

圖3 最佳匹配塊搜索

圖4 初始化最小堆

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

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

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

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

2.3 基于優(yōu)先級函數(shù)的塊選擇

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

（1）塊的優(yōu)先級函數(shù)定義。設以p點為中心的塊的優(yōu)先級為（）Pp，則

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

圖5 置信因子比較

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

（2）塊修復。根據(jù)2.2節(jié)最佳匹配塊搜索算法來修復當前塊。

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

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

3 實驗結果與分析

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

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

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

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

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

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

圖6 修復結果比較

4 結束語

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

圖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.