基于加權優(yōu)先級和分類匹配的圖像修復方法

曹燕，金煒，符冉迪

（寧波大學信息科學與工程學院，浙江 寧波 315211）

基于加權優(yōu)先級和分類匹配的圖像修復方法

曹燕，金煒，符冉迪

（寧波大學信息科學與工程學院，浙江 寧波 315211）

待修復像素優(yōu)先級的計算及最佳匹配塊的確定是基于紋理合成圖像修復方法的兩個基本環(huán)節(jié)，傳統(tǒng)方法不僅難于確定優(yōu)先級計算中的置信度，而且難于搜索到最佳匹配塊。提出了一種基于加權優(yōu)先級和分類匹配的圖像修復方法，該方法在優(yōu)先級模型中，引入指數(shù)函數(shù)和正規(guī)化函數(shù)分別優(yōu)化置信度和數(shù)據(jù)項，使得計算的優(yōu)先級更加客觀，從而使修復順序更加合理。基于此，將結構信息作為搜索匹配塊的一個度量因子，采用分類篩選方式，選取最佳匹配塊。實驗結果表明，所提方法在獲得良好修復效果的前提下縮短了修復時間。

紋理合成；圖像修復；優(yōu)先級；匹配方式

1 引言

隨著互聯(lián)網技術的不斷發(fā)展，信息的交流和互動也越來越頻繁，圖像、語音以及視頻等多媒體信息已成為人們生活不可或缺的部分。然而，由于帶寬的限制，多媒體信息在傳輸前往往需要經過壓縮處理，這使得所傳輸?shù)男畔⒏资艿叫诺栏蓴_，從而造成接收端所獲得的往往是破損或缺失的信息。因此，在接收端對破損或缺失的圖像、語音和視頻信息進行修復是十分重要的。

圖像修復（image inpainting）技術[1]是針對圖像破損區(qū)域，利用已知區(qū)域的圖像信息及特定的修復算法，填充破損區(qū)域內的缺損信息，使得填充后的圖像在視覺效果上連續(xù)、光滑、自然，且不為人眼所察覺其修復痕跡的一種圖像處理技術。目前的圖像修復技術主要分為兩大類，一類是適用于小區(qū)域破損類型的圖像修復技術，如Bertalmio等人[1]提出的基于 BSCB（bertalmio sapiro caselles bellester）模型的修復算法，Chan等人[2]提出的基于整體變分（total variation，TV）模型的修復算法及基于曲率驅動擴散（curvature-driven diffusion，CDD）模型的修復算法，參考文獻[3]提出的基于稀疏表示的圖像修復算法。該類方法在修復小區(qū)域破損圖像時有較好的修復效果，但當破損區(qū)域較大時，往往會產生模糊的現(xiàn)象。另一類是基于紋理合成的圖像修復方法，該類方法適用于修復存在大區(qū)域破損的圖像，代表方法為Criminisi算法[4]，該算法將圖像中已知區(qū)域的內容復制到破損區(qū)域，實現(xiàn)修復處理，但該算法存在的主要問題是修復順序及最佳匹配塊難于確定。為解決此問題，研究者提出了若干改進方案，參考文獻[5]考慮到確定修復順序時置信度趨于零的情況，將置信度減去一個常數(shù)，以保證優(yōu)先級總能發(fā)揮作用，但沒有考慮到最佳匹配塊的選??；參考文獻[6]將平方差之和（sum of squared difference，SSD）和歸一化互相關函數(shù)（normalized cross correlation，NCC）相結合來搜素最佳匹配塊，使得所選取的最佳匹配塊更為準確，但忽略了優(yōu)先級的問題；參考文獻[7]增強了優(yōu)先權模型中的結構信息并將顏色特征和空間距離相結合來搜素最佳匹配塊，獲得了良好的修復效果，但運行速度較慢；參考文獻[8]利用Curvelet變換提取圖像的方向特征來構造匹配準則，采用稀疏表示技術將待修復塊表示成多個匹配塊的稀疏線性組合，獲得更優(yōu)的修復效果。

為了克服待修復像素優(yōu)先級計算錯誤和最佳匹配塊選取不佳等缺陷，提出了一種基于加權優(yōu)先級和分類匹配的圖像修復方法。在優(yōu)先級模型中，引入指數(shù)函數(shù)和正規(guī)化函數(shù)分別優(yōu)化置信度和數(shù)據(jù)項，且將優(yōu)先級改為加權形式；待修復塊分為平滑塊和非平滑塊，采用不同的匹配準則來局部搜索最佳匹配塊，將最佳匹配塊中的像素賦值到待修復塊中來修復該塊；通過更新置信度，沿等照度線方向實現(xiàn)整個破損區(qū)域的修復。該方法能夠很好地改善圖像所存在的瑕疵和紋理延伸的問題，具有良好的修復效果，且縮短了修復時間。

2 Criminisi算法

Criminisi算法[4]的核心是分別計算邊界 Ω?上各像素的優(yōu)先權值，選取優(yōu)先權值最大的像素p所在的塊為待修復塊ψp，然后根據(jù)匹配準則在已知區(qū)域Φ中選擇最佳匹配塊ψq，將相應的像素值填充到待修復塊中，并更新邊界 Ω? ，重復以上的步驟，直到圖像完全被修復為止。

Criminisi算法示意如圖1所示，其中I為待修復的破損圖像，Ω為待修復區(qū)域，Φ為已知信息區(qū)域（陰影區(qū)域）， Ω? 為已知信息區(qū)域和待修復區(qū)域的邊界，p為邊界上的像素，以像素p為中心構成n×n大小的待修復塊ψp。

像素p的優(yōu)先權為：

圖1 Criminisi算法示意

其中，pC為置信度，表示待修復塊中已知信息占待修復塊的比值，其值越大，則表示所包含的已知信息越多。表示待修復塊ψp的面積，在初始化過程中，若待修復塊ψp內的像素點p Ω∈ ，則若pΦ∈ ，則為數(shù)據(jù)項，表示待修復塊的結構信息，其值越大，則具有較強的結構信息。表示像素p的等照度線矢量，pn表示像素p的單位法向量，即為歸一化因子，對于灰度圖像而言，α=255。

在已知信息區(qū)域Φ中搜索待修復塊ψp的最佳匹配塊ψq，引入SSD距離計算待修復塊ψp與匹配塊之間的相似度：

將最佳匹配塊ψq中的像素來填充待修復塊ψp中的未知像素點，這些像素點的置信度更新為：

由式（4）可知，未知像素點 p'的置信度更新為 ψp的置信度 Cp。對于下一個待修復塊來說，未知像素點 p'就變成已知像素點，而此時式（4）賦值得到的根據(jù)式（2）得到的置信度就會偏小。因此，隨著修復次數(shù)的增多，置信度會逐漸變小。

3 基于加權優(yōu)先級和分類匹配的圖像修復方法

為更準確地計算待修復像素的優(yōu)先級及搜索得到更加精確的最佳匹配塊，提出了一種基于加權優(yōu)先級和分類匹配的圖像修復方法。

3.1 優(yōu)先級的改進

隨著修復的進行，置信度會逐漸變小趨向于零，即使數(shù)據(jù)項增大，優(yōu)先權值仍隨著置信度的減小而減小，導致優(yōu)先權的計算錯誤，甚至出現(xiàn)隨機選擇待修復塊進行修復的情況；對于單一顏色的待修復塊而言，數(shù)據(jù)項為零，即使置信度很大，待修復塊也不能及時得到修復，從而影響最終的修復效果。

Criminisi算法的優(yōu)先權是采用相乘的形式，從數(shù)學意義上來講，乘法對于因子趨于零的情況較為敏感，而加法則相對更加穩(wěn)定。因此，采用如下的優(yōu)先權計算式[9]：

因此，本文的優(yōu)先權計算式為：

3.2 匹配準則的改進

匹配準則是影響圖像修復效果的重要因素，若搜索到的匹配塊不是最佳匹配塊，則會影響最終的修復效果，從而造成視覺上的誤差。

一般一幅圖像可以分為平滑區(qū)域和非平滑區(qū)域兩部分。對于平滑區(qū)域而言，像素值變化較小，可以通過周圍的像素值進行判斷；而對于非平滑區(qū)域，像素值變化較大，直接采用周圍的像素值判斷會產生誤差?；诖耍疚睦锰荻刃畔砼袛嘣搮^(qū)域是平滑區(qū)域還是非平滑區(qū)域；然后，根據(jù)不同區(qū)域采用不同的匹配準則來得到最佳匹配塊。該方法在有效地尋找最佳匹配塊的同時，能夠提高運行速度。

第一步：計算待修復塊的梯度。假設待修復塊ψp中任意像素的像素值為 f(x ,y)，分別計算該像素上、下、左、右4個方向的梯度值，比較這4個方向的梯度值，將其中最大的梯度值作為該像素的權重 g(x ,y)，對待修復塊ψp內的所有像素求平均，其值為：

設定一個界限值T，該值為常數(shù)。當u≤ T 時，代表該修復塊ψp為平滑區(qū)域，反之，則為非平滑區(qū)域。

第二步：進行相似性的度量。待修復塊ψp為平滑塊時，則利用局部搜索方法代替全局搜索，將待修復塊 ψp向外延伸 m× m(m ＞ n)的搜索區(qū)域，再在搜索區(qū)域內尋找最佳匹配塊，該匹配準則的計算方法如式（3）所示；反之，待修復塊ψp為非平滑塊時，也采用局部搜索方法，但在搜索區(qū)域內尋找最佳匹配塊時，需要考慮紋理和結構信息，因此，對此時的匹配準則進行改進。Wang等人[10]提出的基于人眼視覺特性的結構相似度（structural similarity index measurement system，SSIM）圖像質量評價系統(tǒng)，將圖像分為亮度信息、對比度信息、結構信息。本文引入SSIM中的結構信息作為匹配準則的因素，將式（3）改進為：

因此，基于加權優(yōu)先級和分類匹配的圖像修復方法實現(xiàn)步驟如下。

步驟 1 檢測已知信息區(qū)域和待修復區(qū)域的邊界 ?Ω ，通過式（6）計算邊界像素的優(yōu)先權值，找到優(yōu)先權值最大的像素p，將其作為起始修復點。

步驟2 以 p為中心選取9dpi× 9dpi大小的待修復塊ψp，并以p為中心取81dpi× 81dpi大小作為搜索區(qū)域，進行可重疊的9dpi× 9dpi分塊處理，得到各個匹配塊ψq'。

步驟 3 通過式（7）計算待修復塊ψp的梯度，若該梯度小于或等于界限值 T，則該修復塊為平滑塊，通過式（3）計算各個匹配塊與待修復塊的相似度，選取相似度最大的匹配塊，作為該修復塊的最佳匹配塊；若該梯度大于界限值 T，則該修復塊為非平滑塊，采用引入結構信息的式（8）計算相似度，獲得最佳匹配塊。

步驟 4 將獲得的最佳匹配塊賦值到待修復塊中，更新置信度。

步驟 5 重復步驟1～4，直到破損區(qū)域修復完整。

4 實驗結果與分析

通過實驗來驗證本文所提圖像修復方法的有效性，采用不同破損情況的圖像，在3.30 GHz、4 GB內存、64位Windows 7的計算機系統(tǒng)下進行實驗，并將本文方法與其他方法進行對比。實驗中相應參數(shù)設置為：優(yōu)先權函數(shù)中置信度的系數(shù)β=0.3，數(shù)據(jù)項的系數(shù)γ=0.7，式（7）中的界限值 T=100。在對圖像修復效果評價時，除了采用主觀評價外，還可以采用峰值信噪比（peak signal to noise ratio，PSNR）進行客觀評價[11]，PSNR值越高，則表示所獲得的圖像失真越小，即修復效果越好。

4.1 受損圖像修復

為說明本文方法能夠較好地修復圖像，選擇包含不同破損情況的圖像作為測試圖像。下面給出兩種不同受損情況下的圖像修復實驗，并與Criminisi算法[4]、參考文獻[6]算法進行對比分析，其修復結果分別如圖2和圖3所示。

圖2 劃痕圖像修復結果對比

圖3 破損塊圖像修復結果對比

由圖2的修復結果可知，Criminisi算法在手臂處出現(xiàn)嚴重的瑕疵，手掌處產生了紋理延伸問題，破壞了手掌的結構；雖然參考文獻[6]算法消除了手臂處的瑕疵，但是對于手掌處并沒有得到較好的修復，沒有解決Criminisi算法所存在的紋理延伸問題；本文方法既解決了手掌處紋理延伸的問題，又消除了瑕疵，具有較好的視覺效果。

由圖3的修復結果可知，Criminisi算法在對花瓣處進行修復時，出現(xiàn)了“斷裂”和花瓣延伸的現(xiàn)象；而參考文獻[6]算法雖修補了“斷裂”現(xiàn)象，但是仍然存在瑕疵和紋理延伸的問題；本文方法克服了上述所存在的缺陷，具有較好的視覺效果。

為了更好地評價圖像的修復效果，本文采用PSNR作為圖像修復的客觀評價指標。將3種方法的PSNR值進行比較，具體數(shù)據(jù)見表1。

表1 3種修復算法的PSNR（單位為dB）

由表1可知，對于不同破損情況的圖像，本文提出的圖像修復方法都能夠獲得較好的修復效果。由于圖2的破損區(qū)域相對圖3較小，因此無論采用哪種方法進行修復，圖2修復結果的PSNR值都高于圖 3。Criminisi算法存在難于確定優(yōu)先級計算中的置信度且難于搜索到最佳匹配塊的情況，使得該算法修復結果的PSNR值最低；參考文獻[6]算法雖改善了最佳匹配塊的選取，但仍存在優(yōu)先級計算的問題，使得該算法修復結果的PSNR值有所提高；而本文方法既改善了優(yōu)先權計算的問題，又加強了最佳匹配塊的選取，從而本文方法修復結果的PSNR值最高。

4.2 目標移除

為進一步說明本文方法的有效性，對目標移除的圖像進行修補，同樣與Criminisi算法[4]、參考文獻[6]算法進行分析對比，其修復結果如圖 4所示。

圖4 人物移除的結果對比

表2 3種圖像修復方法運行時間比較

由圖4的修復結果可知，Criminisi算法在對房屋進行修復時，破壞了房屋的結構，使樹木的紋理延伸，不符合人眼的視覺效果；參考文獻[6]算法修復效果有所提高，但是屋頂仍存在著不連續(xù)的現(xiàn)象；而本文方法對屋頂?shù)男迯筒坏３至宋蓓數(shù)耐暾?，使得樹木的紋理不再延伸到湖面上，且屋頂上方的樹木與周圍樹木相融合，具有較好的視覺效果。

為了驗證本文方法的修復時間，將其與Criminisi算法[4]、參考文獻[6]算法的修復時間相比較，見表2。

由表2可知，修復方法的運行時間與圖像大小及破損區(qū)域像素多少有關。在對圖2進行修復時，雖然破損像素較小，但圖像尺寸較大，由于Criminisi算法采用全局搜索，所以耗費的時間較長，而本文提出的圖像修復方法采用局部搜索，在保證匹配塊在搜索范圍內的情況下，加快了修復速率；在對圖3進行修復時，由于其破損區(qū)域和圖像尺寸都相對較小，使得本文方法的修復時間較短；在對圖4中人物進行移除時，由于圖像破損區(qū)域較大，且紋理細節(jié)較復雜，相比圖2和圖3所需的修復時間更長。與Criminisi算法和參考文獻[6]算法相比，本文方法復雜度更低，且速度更快。

5 結束語

本文提出了一種基于加權優(yōu)先級和分類匹配的圖像修復方法，該方法對優(yōu)先級模型進行了修改，通過引入指數(shù)函數(shù)和正規(guī)化函數(shù)，采用加權求和的形式，使修復順序更加合理。此外，調整了在修復過程中匹配塊的搜索方式，采用分類篩選來得到最佳匹配塊。實驗結果表明，本文方法不僅能夠抑制紋理延伸，還能去除修復過程中存在的瑕疵，相比于原算法和其他算法而言，修復結果不僅具有良好的視覺效果，且縮短了修復時間。

[1] BERTALMIO M, SAPIRO G, CASELLES V, et al. Image inpainting[C]//The 27th Annual Conference on Computer Graphics and Interactive Techniques, July 23?28, 2002, New Orleans, USA. [S.l.:s.n.], 2002: 417-424.

[2] CHAN T F, SHEN J. Non-texture inpainting by curvature-driven diffusions(CDD)[J]. Journal of Visual Communica-tion and Image Representation, 2001, 12(4): 436-449.

[3] XU Z B, SUN J. Image inpainting by patch propagation using patch sparsity[J]. IEEE Transactions on Image Processing, 2010, 19(5): 1153-1165..

[4] CRIMINISI A, PEREA P, TOYAMA K. Region filling and object removal by exemplar-based image inpainting[J]. IEEE Transactions on Image Processing, 2004, 13(9): 1200-1212.

[5] 李旭峰, 王靜, 劉紅敏, 等. 特征優(yōu)先塊匹配圖像修復算法[J].計算機輔助設計與圖形學學報, 2016, 28(7): 1131-1137. LI X F, WANG J, LIU H M, et al. Image inpainting using feature precedence and patch matching[J]. Journal of Computer-Aided Design and Computer Graphics, 2016, 28(7): 1131-1137.

[6] WANG J, LU K, PAN D, et al. Robust object removal with an exemplar based image inpainting approach[J]. Neurocomputing, 2014, 123(10): 150-155.

[7] CHEN Z, DAI C, JIANG L, et al. Structure-aware image inpainting using patch scale optimization[J]. Journal of Visual Communication & Image Representation, 2016(40): 312-323.

[8] 李志丹, 和紅杰, 尹忠科, 等. 基于Curvelet方向特征的樣本塊圖像修復算法[J]. 電子學報, 2016, 44(1): 150-154. LI Z D, HE H J, YIN Z K, et al. Exemplar based image inpainting algorithm using direction features of Curvelet transform[J]. Acta Electronica Sinica, 2016, 44(1): 150-154.

[9] CHENG W H, HSIEH C W, LIN S K, et al. Robust algorithm for exemplar-based image inpainting[C]//The International Conference on Computer Graphics, Imaging and Vision(CGIV), July 26?29, 2005, Beijing, China. New Jersey: IEEE Press, 2005: 64-69.

[10] WANG Z, BOVIK A C, SHEIKH H R, et al. Image quality assessment: from error visibility to structural similarity[J]. IEEE Transactions on Image Processing, 2004, 13(4): 600-612.

[11] SHIH T K, CHANG R C, LU L C, et al. Adaptive digital image inpainting[C]//International Conference on Advanced Information Networking and Applications, March 29?31, 2004, Los Alamitos, USA. New Jersey: IEEE Press, 2004: 71-76.

曹燕（1993?），女，寧波大學信息科學與工程學院碩士生，主要研究方向為數(shù)字圖像處理、模式識別。

金煒（1969?），男，寧波大學信息科學與工程學院副教授、碩士生導師，主要從事壓縮感知、模式識別和數(shù)字圖像處理等方面的研究工作。

符冉迪（1971?），男，寧波大學信息科學與工程學院副教授、碩士生導師，主要從事數(shù)字圖像處理、模式識別等方面的研究工作。

An image inpainting method based on weighted priority and classification matching

CAO Yan, JIN Wei, FU Randi
Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China

The calculation of the priority of the pixel to be repaired and the determination of the best matching block are based on two basic steps of the texture synthesis image inpainting method. The traditional method is not suitable because it is difficult to determine the confidence in the priority calculation, and it is difficult to search for the best matching block. An image inpainting method based on weighted priority and classification matching was proposed. In the priority model, the exponential function and the normalization function were introduced to optimize the confidence and data items separately, the further benefit of which was a more objective priority of calculation and a more reasonable repair order. Based on the proposed functions, the structure information was used as a measure factor of the search matching block, and the best matching block was selected by the classification and screening method. Experimental results show that the proposed method can shorten the repair time under the condition of obtaining good repair effect.

texture synthesis, image inpainting, priority, matching criteria

TP391

A

10.11959/j.issn.1000?0801.2017103

2017?01?19；

2017?04?04

浙江省自然科學基金資助項目（No.LY16F010001）；國家自然科學基金資助項目（No.61471212）；寧波市自然科學基金資助項目（No.2016A610091）

Foundation Items：The Natural Science Foundation of Zhejiang Province of China(No.LY16F010001),The National Natural Science Foundation of China(No.61471212), The Natural Science Foundation of Ningbo of China(No.2016A610091)