參照四鄰域裁剪樣本的圖像修復算法

孟紅月,翟東海,李夢雪,曹大命

(1.西南交通大學 信息科學與技術學院,成都 610097; 2.西藏大學 工學院,拉薩 850000)(*通信作者電子郵箱849490096@qq.com)

0 引言

圖像修復是指對圖像中的缺失區域進行填充的過程,使得修復后的圖像能夠保持結構信息的連續性以及紋理信息的一致性,是當前計算機圖形學、計算機視覺和圖像處理領域的重要研究課題。

目前,數字圖像修復技術主要分為兩大類:

1)基于偏微分方程(Partial Differential Equation, PDE)的圖像修補(inpainting)技術,主要適用于修復破損區域狹小的圖像。

基于PDE的圖像修補算法起始于Bertalmio 等[1]2000年提出的BSCB(Bertalmio-Sapiro-Caselles-Ballester)圖像修復模型,之后的基于總體變分(Total Variation, TV)[2]的圖像修復模型以及曲率驅動擴散(Curvature-Driven Diffusion, CDD)[3]的圖像修復模型等均是基于該思想的改進。

2)基于樣本的紋理合成圖像補全(completion)技術,可用于修復破損區域尺度較大的圖像。該類修復技術目前主要包括基于圖像分解的修復技術以及采用塊的紋理合成技術兩種方法，以填充目標區域的方法考目標塊中已知信息,從樣本中選取最佳樣本塊進行修復[1-4]。

基于樣本的紋理合成圖像補全技術,由Drori等[5]將基于塊級別的紋理合成方法引入圖像修復領域,其后,Criminisi等[6]提出采樣復制的樣本思想將結構信息考慮進圖像修復過程中,利用缺失區域的邊緣結構信息,計算待修復塊優先級,依此由外向內補全圖像。該算法對結構信息簡單、紋理信息平滑的大面積破損圖像,修復速度快,修復效果也較好,但是該類算法是以貪婪的方式進行塊的匹配,有時會造成誤差累積,引發修復效果的結構不一致、視覺不連續、模糊等情況。Sun等[7]通過手工方式很好地解決了結構重建的難題,避開了計算機對圖像復雜信息的學習過程,以結構傳播的形式首先對重構的結構區域進行修復,然后利用置信傳播思想對圖像進行分區域修復?；谥眯艂鞑?Belief Propagation, BP)的圖像修復思想基于MRF(Markov Random Field)模型的近鄰相關性,把推斷局部化和分布化,把全局的求和變成局部的消息傳遞,利用節點與節點之間相互傳遞信息而更新當前整個MRF的標記狀態,是基于MRF的一種近似計算[8]。優先置信傳播(Priority Belief Propagation, Priority-BP)算法由Komodakis等[9]在BP算法的基礎上提出了兩個重要的擴充:按優先級遍歷節點和標號裁剪思想,很大程度上提高了置信傳播算法的效率。Yang等[10]提出基于結構優先置信傳播(Structure Priority Belief Propagation, SPBP)的圖像修復方法優先修復結構信息。Hsin等[11]在Priority-BP算法的基礎上提出利用結構指導對算法改進,著重考慮了結構信息對修復算法的影響,以及通過物理變換擴大標簽集合以充分利用圖像已知信息,但同時大大增加了算法的復雜度。Tang等[12]在塊的紋理合成技術基礎上提出了基于參照圖像的修復方法,對于特征區域的大尺度圖像修復提供了新的可行思路。翟東海等[13]通過自適應擴散模型區分圖像平坦區域以及特征區域,利用平均梯度矩陣及其特征向量控制方向,在不同的區域自適應地選擇不同的擴散方向與速度,從而在加速修復的同時很好地保持了圖像特征。王猛等[14]利用鄰域窗口總變分和內在變分構造出權重變分,通過對Criminisi算法中的優先級測度進行加權、引入整體結構差異算子,改進了優先級公式并提高了匹配精度。He等[15]提出了一種利用圖像中相似塊的匹配信息統計相似塊之間的相對偏移量,利用具有稀疏分布特征的偏移量完成圖像修復的方法,該算法對特征區域重復的圖像修復效果較佳。

針對幾何結構信息以及紋理信息比較豐富的圖像修復問題進行研究，為提高算法修復效率，同時保證圖像修復效果可靠性,本文提出了基于參照四鄰域裁剪樣本的圖像修復算法。主要改進了優先級計算公式以及像素塊的相似性計算方法;并在計算鄰域參照優先級的基礎上,參照具有可靠信息的鄰域塊裁剪并篩選樣本集合,提高了塊的匹配準確度和對最佳樣本的搜索效率。

1 算法基礎

圖像修復解決的問題就是利用圖像中已知區域內的樣本信息來補全目標區域,使得補全后的圖像效果自然、連續,能夠滿足人們視覺上的一致連貫性。

如圖1所示,介紹了基于樣本塊的區域劃分圖像修復思想,為本文算法的初始化提供算法基礎。在圖1中,待修復圖像I包含目標區域Ω以及已知區域Ф,Ψp表示以像素點p為中心的目標塊,即待修復的圖像塊。Rn表示經過預處理中的Meanshift圖像分割步驟得到的若干個子區域,分別從各子區域Rn內采集樣本塊,生成樣本集合{RSn},即{RSn}={Lpi|?pix∈Lp, ?pix∈Rn},其中n是表示子區域個數的正整數,用來標記不同的區域,在圖1的情況中,n=1,2,3。Lpi表示目標塊Ψp的第i個樣本塊,其中i的范圍為[1,{RSn}]。目標集合是有目標塊構成的集合,分為待修復優先級較高的邊緣目標集合及優先級較低且待更新的內部目標集合,在圖1的情況中,根據像素p的位置信息可以知道目標塊Ψp的初始樣本集合為{RS1}。通過gapx、gapy設置圖像塊(區塊)patch的大小size(如式(1)所示),以保證相鄰塊之間始終有重疊區域,從而滿足圖像修復結果的平滑約束。

size=w*h=(2×gapx+1)(2×gapy+1)

(1)

圖1 區域劃分圖像修復示意圖

另外,下文出現的{LSx}表示以像素x為中心的目標塊的初始樣本集合,通過像素x的位置信息判斷其所在區域Rn,從而得到初始樣本集合,也就是說,任一目標塊的初始樣本集合只可能是{RSn}中的一個。{CSx}表示以像素x為中心的目標塊的候選樣本集合。從{CSx}中得到最優樣本塊,最優樣本塊用來填補目標塊。ST(I)表示待修復圖像I的結構二值模板圖像,其中表示結構的像素其值為255,其他像素值為0。

2 本文算法

2.1 算法流程

本文算法流程如圖2所示,算法詳細步驟如下:

第1步 圖像預處理。1)利用邊緣檢測Canny算子提取圖像的主要結構信息,得到結構子圖。2)利用Meanshift對圖像進行區域劃分,得到子區域圖像,如圖1的情況所示,區域劃分得到3個子區域,使得不同區域內的目標塊僅從其所在區域局部搜索樣本塊,減小了最佳樣本塊的檢索區間。3)通過標識圖像中的已知像素和未知像素，得到掩模圖像。

第2步 塊的相似性計算。利用結構子圖提出結構對稱匹配約束(Structure Symmetry Matching, SSM),結合傳統的塊的相似性計算方法——離差平方和(Sum of Squares of Deviations, SSD),改進塊的相似性度量函數(Energy of XOR Matching, EM),提高塊匹配精度。

第3步 計算目標塊的待修復優先級(簡稱目標塊優先級)。在傳統優先權公式計算方法以及分析影響目標塊優先級的因素基礎之上,引入結構因子和置信度,根據預處理得到的三個子圖分別計算結構項、置信度項、數據項,改進了待修復優先級公式。置信度的計算過程也實現了對目標塊的初始樣本集合的第一次裁剪,得到了目標塊的候選樣本集合。

第4步 參照四鄰域裁剪樣本。首先計算待修復優先級最高的目標塊的四鄰域參照優先級。由于在目標塊和其四鄰域的重疊區域的半個patch塊中包含著重要的圖像平滑信息,因此通過計算四鄰域參照優先級,有序地參照四鄰域,根據鄰域塊與其候選樣本塊之間的重疊區域半塊的相似度,從該鄰域塊的樣本集合中得到其最匹配樣本塊,以此作為裁剪目標塊的候選樣本集合的參照信息,通過塊的相似計算方法以及平滑約束函數(Energy of Smoothness, ES)完成候選樣本的裁剪以及最佳樣本塊的搜索過程。如圖2所示,用count來記錄參照的四鄰域情況,初始化為4,表示待修復目標塊的四個鄰域塊均待參照的狀態。若參照的鄰域塊中無已知像素信息,則刪除該鄰域塊,即count--；否則，參照鄰域塊的參照優先級高低順序，裁剪掉目標塊中的可靠度較低的樣本塊。每參照完畢一鄰域塊，同樣執行count--。當count=1,說明只剩下一個待參考鄰域塊，接著參照該鄰域塊，通過平滑約束函數的最小化得到最優樣本塊，用來填補對應的目標塊。直到count=0,修復下一個具有最高待修復優先級的邊緣目標塊，直到目標集合為空，完成修復。

圖2 參照四鄰域裁剪樣本的圖像修復算法流程

2.2 塊的相似性計算方法的改進

塊的相似性用來衡量目標塊與樣本塊之間的相似性,作為樣本裁剪的度量標準,傳統的像素離差平方和匹配方法忽略了圖像結構信息的匹配,容易造成塊的誤匹配。為提高塊匹配精度,提出結構對稱匹配約束ssm,公式如下:

(2)

其中：Ψp是待修復的目標塊；Lpi是下標為i的樣本塊；Ψp(x,y)和Lpi(x,y)分別表示在(x,y)處的目標塊及其對應的第i個樣本塊的像素值；size表示圖像塊patch的大小。通過式(2)可以看出，相等的像素數量越多，則ssm值越小；反之，ssm值越大。如圖3所示， (a)、(b)分別表示來自結構二值模板圖像ST(I)的目標塊Ψp與樣本塊Lpi，其中白色像素點表示結構信息,灰色像素點表示非結構信息。對圖3(a)和(b)兩圖像塊中的所有像素點一一對應進行異或邏輯累加運算,統計出對應位置相同而像素值不同的像素點數,從而判斷兩個圖像塊的結構匹配度。對應位置相同而像素值不同的像素點越少，說明兩圖像塊的結構匹配度越高;反之,匹配度越低,從而提高了塊匹配精度。

結合像素離差平方和，引入結構對稱匹配約束得到改進的塊間相似性度量函數:

(3)

圖3 結構對稱匹配約束示意圖

2.3 改進的優先級公式

基于文獻[6，9]中的優先級計算,可以了解到:

1)結構信息越豐富則待修復優先級越高。

2)包含已知數據越多則待修復優先級越高。

3)目標塊對應的候選樣本塊數量越少,意味著該目標塊包含的結構信息越豐富,即結構稀疏性越大,與之匹配的樣本塊數量越少。僅通過目標塊中的結構及已知像素信息或者僅以候選樣本集的大小無法保證擁有特征信息以及特征信息豐富的目標塊優先被修復,為了提升特征信息的優先傳遞性,使得當前的修復結果為后續的修復過程提供更可靠的信息,保證圖像修復效果的結構連續性以及視覺連通性，引入了結構因子和置信度。改進了待修復優先級公式如下:

(4)

其中:D(·)、S(·)、conf(·)分別表示目標塊Ψp的數據項、結構項、置信度項；ω代表目標塊的結構因子。

優先級的結構項衡量了目標塊中結構信息的占比,目標塊中結構像素數量越多,則結構信息越豐富,結構項越大,即

(5)

結構因子實際描述了目標塊Ψp中表示結構像素的數量對Ψp的優先級的影響作用,結構像素個數越多,則其結構因子越大,對待修復優先級的影響越大。本文以目標塊的大小與該塊中的結構像素數量的乘積衡量結構因子的大小,計算公式如下:

(6)

結構因子保證了含有結構信息的目標塊總是比不含結構信息的目標塊優先被修復。

數據項表示目標塊中已知區域像素的占分比,目標塊中的已知像素點越多,則包含的可靠信息越多,可信度越大,數據項就越大,即

(7)

其中:q表示邊緣目標塊中的已知像素點,通過標記了已知、未知像素信息的掩模圖像進行統計得到;MI(q)表示掩模圖像中像素點的值，當q取值255時MI(q)=1，q取其他值時MI(q)=0。

圖4 已知數據約束示意圖

本文置信度是目標塊的候選樣本集合大小,待修復目標塊包含的結構紋理越豐富,即約束樣本的條件就越多,則候選樣本集合越小。它實際代表了圖像已知數據對樣本裁剪的貢獻,即已知數據約束(如圖4所示),對目標塊Ψp中的已知區域和其樣本塊Lpi中與Ψp中已知區域位置對應的區域進行相似性測量,從而裁剪掉初始樣本集合中可靠性低的樣本。以計算目標塊Ψp的置信度為例。首先,運用塊間似性度量,利用式(3)測量Ψp與其初始樣本集中樣本塊的匹配度。然后,設置裁剪閾值bconf將相似性度量函數值大于等于bconf的樣本塊裁剪出集合,保留匹配度較高的樣本塊,得到候選樣本集合{CSP},即

Cpk∈{CSp},EM(Ψp,Lpi)

(8)

其中:Cpk表示候選樣本集中的樣本塊,k=[1,|CSp|]。

候選樣本集的大小,也就是目標塊的置信度,即

conf(p)=|{CSp}|

(9)

2.4 參照四鄰域裁剪樣本

鄰域塊中包含的已知信息越多,可靠性越高,就應越先被參照。由此得到四鄰域的參照優先級公式:

ref(Npj)=D(p)+ω·S(p);j=1,2,3,4

(10)

其中:D(·)、S(·)分別表示圖像塊的數據項與結構項;ω表示結構因子。如圖5所示,塊Np1、Np2、Np3、Np4分別是目標塊Ψp的上、下、上、右4個鄰域,在利用鄰域塊檢索最優樣本塊的過程中,參照鄰域塊的范圍只是它們之間重疊的半個patch塊區域。在圖5的情況中,Np1具有最高的參照優先級,而Np4具有最低的參照優先級。

基于樣本的圖像修復問題可以轉化為樣本裁剪與檢索的過程。對目標塊Ψp的選樣本集{CSP}的裁剪過程如下:

1)計算四鄰域的參考優先級并排序,如圖5所示,ref(Np1)>ref(Np2)>ref(Np3)>ref(Np4),參數count=4用來記錄參考四鄰域的情況,當count=0時，對下一具有最高待修復優先級的目標塊進行樣本集的裁剪過程，執行步驟1)；否則執行步驟2)。

圖5 四鄰域參照優先級示意圖

2)取出參照優先級最高的鄰域塊Npj,并判斷該鄰域塊是否為零已知像素patch塊,即其中不存在任何已知像素信息：若是,刪除該鄰域塊,count=count-1,重復本步驟;若否,執行步驟3)。

5)判斷|{CSp}|與數量閾值Tmax之間的大小,若|{CSp}|>Tmax,裁剪{CSp}中平滑值最小的樣本塊,直到|{CSp}|≤Tmax,然后更新Tmax=Tmax/count。

平滑約束函數由式(3)得到,即

k=1,2,…,|{CSp}|

(11)

圖7 不同算法對不同圖像修復效果比較

3 實例驗證

為驗證本文算法的可行性以及有效性,以Visual Studio 2015為編程環境進行了仿真實驗。首先分別以運行時間和峰值信噪比(Peak Signal-to-Noise Ratio, PSNR)作為評價標準對相關算法進行性能比較,比較結果如表1所示。其中PSNR值越大則表明修復效果越好,計算公式如下:

(12)

其中:U是原圖；U1是修復后的圖像；M、N分別表示圖像的行數和列數。從式(12)可以看出,PSNR值越大說明原圖和修復后的圖像差異越小,即修復越好。

另外,關于實驗的參數設置,本文基于對多組實驗結果的分析,將圖像塊patch的尺度w×h設置在5×5和7×7之間;數量閾值Tmax設置在30～52;裁剪閾值bconf= -SSD0,bdel= -2SSD0,SSD0表示預定義的區塊間的離差平方和均值。

從表1可看出：本文算法的PSNR值都優于對比算法,這是因為最佳樣本塊的搜索范圍由全局變成了局部。另外，本文算法不僅考慮了結構信息對計算相似塊匹配度的影響,還充分利用上下左右4個直接相鄰圖像塊的參考信息,使得在圖像修復中所利用的周圍的先驗信息增多。但這也是本文算法較文獻[13-14]算法耗時較多的緣故。由于文獻[13-14]算法的時間復雜度是同階的,所以這三個算法的時間復雜度是相同的。

表1 四種修復算法的 PSNR 和運行時間比較

對彩色圖像物體的移除效果見圖7中的Sea。參數設置:圖像塊patch尺度w×h設置為7×7,Tmax設置為30?？梢钥闯?文獻[13]算法較好地保持了圖像特征,結構線連續；文獻[14]算法產生了明顯的結構錯位現象；文獻[15]算法的結構修復不連續,上方云朵紋理錯位延伸；本文算法的移除效果較好,紋理清晰,結構線連接自然。

對灰度圖像的修復見圖7中的Lena。圖像塊patch尺度w×h設置為5×5,Tmax設置為40?？梢钥闯?，文獻[13-14]算法在帽子中間對結構線的修復產生了視覺模糊,帽子上的羽毛狀裝飾物產生紋理延伸現象；文獻[15]算法也產生了上述現象,同時對帽子中部環形條紋修復不連續；本文算法結構線的修復更清晰、連續,紋理延伸的問題也得到緩解。

對彩色圖像的劃痕修復見圖7中的唐卡圖像TangKa。圖像塊patch尺度w×h設置為5×5,Tmax設置為48。可以看出，文獻[13-14]算法修復后的結構線模糊并且修復的環形結構存在紋理延伸現象；文獻[15]算法未對缺失的結構線進行較好的連接；本文算法與上述算法相比，修復的結構線更加連續平滑,具有更好的視覺連通性,但環形結構處的紋理延伸現象仍存在。

對紋理信息較為復雜的圖像修復見圖7中的Baboon。圖像塊patch尺度w×h設置為5×5,Tmax設置為52。文獻[13]算法對結構及紋理的復雜的圖像修復效果較好；文獻[14]算法基本消除了結構不連續的現象；文獻[15]算法對結構的修復不敏感,產生了結構錯位及延伸現象;本文算法對結構線的修復仍存在不連續的問題,但紋理修復效果較佳,整體修復結果較清晰。

4 結語

本文對缺失幾何結構及復雜紋理信息且尺度較大的圖像的修復提出了基于鄰域參照的修復方法。結合Criminisi算法以及Pririty-BP算法中優先權計算對優先級公式進行了改進,通過引入結構因子以及置信度使包含結構信息的目標塊被優先修復。同時,在像素塊的匹配計算中引入結構匹配信息以提高像素塊的匹配精度,有效避免了塊的誤匹配。另外,合理且有序地參照四鄰域的參照信息,完成對樣本集的裁剪和最佳標簽的檢索。實驗結果表明,本文算法在圖像修復效果上更能滿足視覺連續性,在客觀評價準則PSNR值有所提高，但運行時間也有所增加。

參考文獻(References)

[1] BERTALMIO M, SAPIRO G, CASELLES V, et al. Image inpainting [C]// SIGGRAPH 2000: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 2000: 417-424.

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

[3] CHAN T F, SHEN J. Mathematical models for local nontexture inpaintings [J]. SIAM Journal on Applied Mathematics, 2001, 62(3): 1019-1043,.

[4] 張紅英, 彭啟琮.數字圖像修復技術綜述[J]. 中國圖象圖形學報, 2007, 12(1): 1-10.(ZHANG H Y, PENG Q Z. A survey on digital image inpainting [J]. Journal of Image and Graphics, 2007, 12(1): 1-10.)

[5] DRORI I, COHEN-OR D, YESHURUN H. Fragment-based image completion [J]. ACM Transactions on Graphics, 2003, 22(3): 303-312.)

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

[7] SUN J, YUAN L, JIA J, et al. Image completion with structure propagation [J]. ACM Transactions on Graphics, 2005, 24(3): 861-868.

[8] FELZENSZWALB P F, HUTTENLOCHER D P. Efficient belief propagation for early vision [J]. International Journal of Computer Vision, 2006, 70(1): 41-54.

[9] KOMODAKIS N, TZIRITAS G. Image completion using efficient belief propagation via priority scheduling and dynamic pruning [J]. IEEE Transactions on Image Processing, 2007, 16(11): 2649-2661.

[10] YANG Y, ZHU Y, PENG Q. Image completion using structural priority belief propagation [C]// MM 2009: Proceedings of the 17th ACM International Conference on Multimedia. New York: ACM, 2009: 717-720.

[11] HSIN H-F, LEOU J-J, LIN C-S, et al. Image inpainting using structure-guided priority belief propagation and label transformations [C]// ICPR 2010: Proceedings of the 2010 20th International Conference on Pattern Recognition. Washington, DC: IEEE Computer Society, 2010: 4492-4495.

[12] TANG C, HU X, CHEN L, et al. Sample-based image completion using structure synthesis [J]. Journal of Visual Communication & Image Representation, 2013, 24(7): 1115-1123.

[13] 翟東海, 段維夏, 魚江, 等.局部特征分類的自適應擴散模型[J]. 信號處理, 2014, 30(9): 1039-1047.(ZHAI D H, DUAN W X, YU J, et al. Adaptive diffusion model based on local feature classification [J]. Journal of Signal Processing, 2014, 30(9): 1039-1047.)

[14] 王猛, 翟東海, 聶洪玉, 等.鄰域窗口權重變分的圖像修復[J]. 中國圖象圖形學報, 2015, 20(8): 1000-1007.(WANG M, ZHAI D H, NIE H Y, et al. Image inpainting with weight variation of neighborhood window [J]. Journal of Image and Graphics, 2015, 20(8): 1000-1007.)

[15] HE K, SUN J. Image completion approaches using the statistics of similar patches [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2014, 36(12): 2423-2435.

This work is partially supported by the National Natural Science Foundation of China (61461048).