基于幾何距離的Criminisi圖像修復(fù)算法

王新年，王 哲，王 演

（大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連116026）

0 引 言

圖像修復(fù)的目的是恢復(fù)圖像丟失或者損壞的區(qū)域［1］，主要應(yīng)用于文物保護(hù)以及老照片修復(fù)等方面。數(shù)字圖像修復(fù)算法根據(jù)破損區(qū)域大小可以分為小區(qū)域破損修復(fù)算法和大區(qū)域破損修復(fù)算法。小區(qū)域破損修復(fù)算法主要包括基于擴(kuò)散的圖像修復(fù)算法［2－4］和基于稀疏表示的圖像修復(fù)算法［5］，該類算法對于劃痕以及文字覆蓋的破損圖像修復(fù)效果較好，對于大區(qū)域破損圖像通常會引入模糊；大區(qū)域破損修復(fù)算法主要包括基于矩陣補(bǔ)全的圖像修復(fù)算法［6］和基于樣本塊的圖像修復(fù)算法［7－9］，該類算法對于解決紋理延續(xù)問題有著很好的效果。

基于矩陣補(bǔ)全的算法是近年來提出的大區(qū)域圖像修復(fù)算法，該算法的主要思想是將破損圖像看作缺少對應(yīng)元素的矩陣，然后應(yīng)用矩陣補(bǔ)全算法對圖像進(jìn)行修復(fù)。Ji等［6］對基于矩陣補(bǔ)全的圖像修復(fù)算法進(jìn)行了相關(guān)研究，通過已知數(shù)據(jù)的張量來估計丟失的數(shù)據(jù)，將低秩矩陣補(bǔ)全方法擴(kuò)展為低秩張量補(bǔ)全方法，并且通過矩陣跡范數(shù)來解決圖像修復(fù)問題。

大區(qū)域破損圖像修復(fù)算法中，基于樣本塊的圖像修復(fù)算法最具代表性的是Criminisi算法［7］，該算法通過計算優(yōu)先權(quán)值確定修復(fù)順序，通過計算塊之間的距離來確定最優(yōu)匹配塊。然而，如果在修復(fù)的過程中，優(yōu)先權(quán)順序以及塊之間的距離計算不準(zhǔn)確，就會導(dǎo)致紋理的錯誤延續(xù)、紋理斷層等，造成不好的視覺效果。因此，有眾多學(xué)者針對這兩方面進(jìn)行了相關(guān)的工作。

在塊優(yōu)先權(quán)計算方面，研究者主要通過對優(yōu)先權(quán)函數(shù)的修改優(yōu)化原算法。Xu等［8］定義了塊結(jié)構(gòu)稀疏度，通過當(dāng)前塊與鄰域塊的非零相似稀疏性來衡量圖像塊結(jié)構(gòu)的可信度，并決定各塊的修復(fù)順序，將候選塊的線性組合作為最終的塊填補(bǔ)到破損圖像上；Anamandra等［10］將梯度與其對應(yīng)的對數(shù)值相加作為優(yōu)先權(quán)函數(shù)，該方法取得了較好的效果；Zhou等［11］在原始Criminisi算法優(yōu)先權(quán)函數(shù)上疊加了數(shù)據(jù)項的加權(quán)值，加強(qiáng)了結(jié)構(gòu)信息強(qiáng)度對于優(yōu)先權(quán)的影響，該算法對結(jié)構(gòu)邊緣圖像表現(xiàn)出良好的效果；Meur等［12］使用結(jié)構(gòu)張量定義了決定修復(fù)順序的優(yōu)先權(quán)函數(shù)，并綜合了基于PDE （partial differential equations）的方法的適合傳播結(jié)構(gòu)的優(yōu)點(diǎn)和基于樣本塊修復(fù)算法能夠延續(xù)紋理的優(yōu)點(diǎn)，取得了良好的效果。

在塊匹配策略方面，研究者主要通過修改填充方法和匹配準(zhǔn)則進(jìn)行算法優(yōu)化。Bugeau等［9］指出，原始的相似性度量函數(shù)SSD （sum of squared differences）在進(jìn)行相似性度量時會引入偏差，也就是說SSD 易于從平坦的區(qū)域復(fù)制像素，針對這一缺點(diǎn)，作者引入加權(quán)Bhattacharya 距離，將一個改進(jìn)的Bhattacharya距離與原始的SSD 相乘，但若兩個塊的分布相同時，改進(jìn)的Bhattacharya距離就會為0，Meur等［13］又對其進(jìn)行了改進(jìn)；Jemi等［14］將邊緣信息融入到匹配準(zhǔn)則中，據(jù)此尋找更合適的匹配塊。

綜上所述，Criminisi改進(jìn)算法在修復(fù)順序和匹配策略上均針對原算法的缺點(diǎn)進(jìn)行了相關(guān)的改進(jìn)，取得了較好的效果。但均未考慮幾何距離因素對尋找最佳匹配塊的影響。所以，本文針對Criminisi算法的缺點(diǎn)，對其進(jìn)行改進(jìn)：通過改進(jìn)優(yōu)先權(quán)值計算方式，避免了錯誤的修復(fù)順序；通過引入距離修正因子，使得兩塊之間的相似度接近時，幾何距離因素起決定性作用。

1 Criminisi修復(fù)算法

Criminisi算法是一種基于樣本塊的修復(fù)算法，其目的是去除數(shù)字圖像中的大區(qū)域目標(biāo)，并在缺損區(qū)域填充符合視覺效果的背景。其主要過程包括優(yōu)先權(quán)計算、最佳匹配塊搜索以及邊界和邊界置信度的更新。

為便于后續(xù)說明，圖1給出了基于Criminisi算法圖像修復(fù)的各變量的示意說明。設(shè)圖像I為待修復(fù)圖像，Φ為完好區(qū)域，Ω為破損區(qū)域，δΩ為破損的邊界。np為在點(diǎn)p處與破損區(qū)域的邊界垂直的單位向量，即邊緣法線方向；▽I⊥p為與梯度垂直的方向，即等照度線方向，表示紋理延續(xù)的方向。

1.1 計算優(yōu)先權(quán)

圖1 Criminisi算法

目標(biāo)塊優(yōu)先權(quán)的計算是Criminisi算法的核心和關(guān)鍵所在，應(yīng)使具有較多已知信息和較強(qiáng)結(jié)構(gòu)的目標(biāo)塊先被填充，以保證填充準(zhǔn)確有序地進(jìn)行［15］。

首先通過識別用戶標(biāo)記出破損區(qū)域Ω，計算受損邊界δΩ的每一點(diǎn)的優(yōu)先權(quán)，并找出優(yōu)先權(quán)最大的點(diǎn)p，并且確定p 點(diǎn)所在的塊Ψp，定義優(yōu)先權(quán)為

式中：│Ψp│是Ψp的面積，也就是Ψp內(nèi)像素點(diǎn)的總個數(shù)，C（q）是像素點(diǎn)q的置信度值，滿足初始條件

式中：np是在點(diǎn)p 處正交于邊界的單位正交向量。▽I⊥p是點(diǎn)p 的等照度線方向。α是一個規(guī)范化因子，通常取255。D（p）是像素點(diǎn)p 的數(shù)據(jù)項值，反應(yīng)了待修復(fù)點(diǎn)處邊緣方向與破損邊界方向的一致性。

1.2 搜索最佳匹配塊

確定好待匹配塊后，根據(jù)相似度函數(shù)SSD 在完好區(qū)域Φ中搜索出最佳匹配塊Ψq，然后用最佳匹配塊Ψq替代Ψp，其中最佳匹配塊的搜索方法為

式中：SSD（Ψp，Ψq）是相似度函數(shù)，R（·）、G（·）、B（·）分別表示兩個圖像塊像素的R、G、B分量。

1.3 更新邊界和邊界置信度

最后更新邊界和當(dāng)前塊的置信度。其中置信度為

重復(fù)上述3 個步驟，直至破損區(qū)域修復(fù)完成，即Ω為空。

1.4 Criminisi算法優(yōu)缺點(diǎn)

Criminisi算法充分地考慮了圖像的紋理特征與結(jié)構(gòu)特性，同時保證了結(jié)構(gòu)的完整性和紋理的延續(xù)性，對破損區(qū)域較大的圖像有很好的修復(fù)效果。

另外，Criminisi也有很多不足：①當(dāng)?shù)日斩染€與單位正交向量垂直時，數(shù)據(jù)項D （p）為0，這樣會使具有很高置信度的塊無法優(yōu)先修復(fù)，造成錯誤的優(yōu)先級順序；②算法的匹配策略沒有考慮到除圖像顏色信息以外的任何信息，所以算法確定的匹配塊并不一定是最佳匹配塊，比較容易造成錯誤修復(fù)，并將錯誤延續(xù)下去。對此，本文進(jìn)行了如下兩部分的改進(jìn)。

2 對Criminisi算法的改進(jìn)

2.1 優(yōu)先權(quán)的改進(jìn)

Criminisi算法的核心思想就是考慮了破損邊緣的優(yōu)先權(quán)，確定了修復(fù)的先后順序，從而使得修復(fù)有序的進(jìn)行，確保了紋理信息的延續(xù)。隨著破損區(qū)域修復(fù)過程的進(jìn)行，置信度C（p）逐漸變化，當(dāng)?shù)日斩染€向量 ▽I⊥p與p 點(diǎn)的法線向量np垂直時，數(shù)據(jù)項D（p）卻為0，這使得當(dāng)C（p）相對很大時，與D（p）相乘后的結(jié)果卻趨近于0，這就造成擁有較高置信度的待匹配塊得不到優(yōu)先修復(fù)，最終造成紋理紊亂的情況。

破損區(qū)域紋理與等照度線方向 ▽I⊥p和法線方向np的關(guān)系如圖2所示，其中，黑色粗線條表示紋理。

圖2 紋理與等照度線方向以及法線方向

由于置信度C（p）較大的先修復(fù)，圖中修復(fù)的順序應(yīng)該是情況二、情況一、情況四、情況三，但用Criminisi算法計算的順序是情況一、情況四、情況二、情況三。原因在于情況一是法線向量與等照度向量同向的情況，會優(yōu)先修復(fù)；而情況三雖然有著近似相等的置信度，但由于兩向量互相垂直，優(yōu)先權(quán)為0；情況四為中間狀態(tài)；情況二中雖然待匹配塊有較高的置信度，占塊總大小的3／4，但由于向量方向垂直，優(yōu)先權(quán)為0，不被優(yōu)先修復(fù)，造成錯誤的修復(fù)順序。

通常，情況一、二、四應(yīng)該為被優(yōu)先修復(fù)的情況，而情況三則處于中間狀態(tài)，為防止極端情況出現(xiàn)，特對數(shù)據(jù)項算法進(jìn)行修改，將與np兩向量點(diǎn)乘后取模改為先分別取模，再相乘，最后與權(quán)函數(shù)W（，np）相乘，數(shù)學(xué)描述為

圖3是權(quán)函數(shù)修改前后的曲線對比，圖中橫坐標(biāo)表示的是紋理延續(xù)方向與邊緣法線方向的夾角，縱坐標(biāo)表示的是其所對應(yīng)的權(quán)值。通過式 （9）將夾角范圍 ［0，π］分為4個小區(qū)間，每個區(qū)間內(nèi)平滑變化，使得權(quán)函數(shù)舍棄極端取值為0的情況。

圖3 權(quán)函數(shù)對比

通過修改優(yōu)先權(quán)，錯誤傳播的概率極大地降低，紋理得到正確的修復(fù)。

2.2 匹配策略的改進(jìn)

Criminisi算法將相似性度量函數(shù) （SSD）作為匹配策略，來搜尋最佳匹配塊。但是通常在紋理圖像中大區(qū)域破損的情況下，破損的紋理一般是其附近完整紋理的延續(xù)，即待修復(fù)塊與匹配塊之間的幾何距離也是確定最佳匹配塊的一個重要因素，離破損區(qū)域越近的圖像塊與破損區(qū)域的相關(guān)性越強(qiáng)，幾何距離越近的兩個塊，越有可能成為最佳匹配塊，故定義距離修正因子DCF （distance correction factor）

式中：DIS（Ψp，Ψq）為兩個塊之間的幾何距離，兩塊之間的相似性與它們的幾何距離共同決定著其是否為最佳匹配塊。即NSSD 最大的塊為最佳匹配塊

為避免錯誤修復(fù)，采用多塊同時修復(fù)的方法，選取優(yōu)先權(quán)最高的兩個塊進(jìn)行同時修復(fù)，以其中一個破損塊為例，首先，利用式 （5）和式 （6）選出SSD 最小的3個塊作為備選塊，由于SSD 公式的篩選，這3個塊與破損塊之間最具有相似性，而且這3個塊之間的差別很小，此時，幾何距離因素占據(jù)主導(dǎo)地位，由式 （10）計算出3個候選塊同破損塊之間的距離修正因子，根據(jù)式 （11），通過距離因子進(jìn)行修正，確定最佳匹配塊。

2.3 算法步驟

算法的輸入為標(biāo)記破損區(qū)域的圖像，輸出為完成修復(fù)的結(jié)果圖，參數(shù)是匹配塊窗口大小w 和搜索區(qū)域 （本文默認(rèn)為整幅圖）。

步驟1 根據(jù)標(biāo)定的破損區(qū)域，提取破損區(qū)域的邊緣δΩ；

步驟2 根據(jù)式 （1），式 （2），式 （3），式 （8），式（9）確定破損邊緣優(yōu)先權(quán)最大的兩點(diǎn)，并確定其所在的破損塊；

步驟3 以上兩個破損塊同時根據(jù)式 （5），式 （6），式（10），式 （11）在指定區(qū)域內(nèi)搜尋各自的最佳匹配塊，并將其對應(yīng)點(diǎn)的像素值復(fù)制到目標(biāo)塊的相應(yīng)像素點(diǎn)；

步驟4 根據(jù)式 （7）更新置信度項；

步驟5 重復(fù)執(zhí)行步驟1～步驟4，循環(huán)往復(fù)直至破損區(qū)域為空，修復(fù)完成。

3 實驗結(jié)果與分析

為驗證本文算法的性能，進(jìn)行了4 組實驗。實驗一、二、三是本文算法與Criminisi算法修復(fù)結(jié)果的比較，實驗四是本文算法同文獻(xiàn) ［5，6］修復(fù)結(jié)果的比較。

其中Criminisi程序源代碼來源于文獻(xiàn) ［16］，文獻(xiàn) ［5］的源代碼來源于文獻(xiàn) ［17，6］的源代碼來源于文獻(xiàn) ［18］。

Criminisi算法所選匹配塊高度與寬度均為9 個像素，文獻(xiàn) ［5］算法使用默認(rèn)參數(shù)，文獻(xiàn) ［6］算法中，迭代次數(shù)設(shè)置為1000，gamma值為 ［100，100，0］，其它參數(shù)為默認(rèn)參數(shù)。

3.1 實驗一

圖4所示的是對結(jié)構(gòu)簡單的破損圖像修復(fù)結(jié)果。可以看出，Criminisi算法的修復(fù)結(jié)果有著明顯的誤匹配以及紋理錯誤延續(xù)現(xiàn)象，而本文的算法克服了以上錯誤，算法效果明顯優(yōu)于Criminisi算法。

3.2 實驗二

圖5是對蹦極人的移除，對比圖5 （c）和圖5 （d）的結(jié)果可知，Criminisi算法的修復(fù)結(jié)果中房頂處有一處明顯的漏洞，而且圖5 （a）圓圈處的紋理并沒有得到很好地延續(xù)，并且造成了錯誤紋理地延續(xù)，而本文修復(fù)算法克服了這兩個問題，并取得良好的視覺效果。

圖4 結(jié)構(gòu)簡單的破損圖像修復(fù)效果比較

圖5 蹦極人修復(fù)效果比較

3.3 實驗三

圖6是對海邊女孩的移除，如圖6 （c）中圓圈所示，由于錯誤的修復(fù)順序以及錯誤的塊匹配，Criminisi算法的錯誤紋理延續(xù)將海里橋梁修復(fù)到了天空中，紋理出現(xiàn)錯誤傳播的現(xiàn)象，不符合實際情況，如圖6 （d）所示，雖然本文算法多修復(fù)出一個橋墩，但橋梁的紋理連接沒有任何問題，取得了較好的視覺效果。

圖6 海邊女孩修復(fù)效果比較

3.4 實驗四

圖7是本文算法與文獻(xiàn) ［5，6］的對比實驗。

文獻(xiàn) ［5］是基于稀疏表示進(jìn)行的圖像修復(fù)。由實驗結(jié)果可以看出，當(dāng)破損區(qū)域較細(xì)時，文獻(xiàn) ［6］可以很好地對圖像進(jìn)行修復(fù)，而當(dāng)破損條增粗到一定程度時，修復(fù)結(jié)果會出現(xiàn)模糊的現(xiàn)象，以及有條狀的斷層，當(dāng)破損條繼續(xù)增大時，由于破損程度過大，稀疏字典原子缺損嚴(yán)重，將不能對圖像進(jìn)行有效地重建。

文獻(xiàn) ［6］是基于低秩張量補(bǔ)全的圖像修復(fù)算法。由實驗結(jié)果可以看出，無論破損區(qū)域的粗細(xì)如何，對于橫條紋破損，文獻(xiàn) ［6］都不能進(jìn)行有效地修復(fù)，修復(fù)結(jié)果產(chǎn)生模糊的現(xiàn)象。

而本文方法始終能從破損圖像的完好區(qū)域找到匹配的塊，從而對圖像進(jìn)行有效地修復(fù)。

圖7 海邊小鳥修復(fù)效果比較

4 結(jié)束語

本文通過對Criminisi算法的研究，針對該算法出現(xiàn)的修復(fù)錯誤現(xiàn)象，分析其產(chǎn)生的原因。通過研究紋理延續(xù)方向與邊緣法線方向的夾角和修復(fù)順序的關(guān)系，改進(jìn)了優(yōu)先權(quán)函數(shù)，解決了原算法容易造成錯誤的修復(fù)順序的問題，并通過考慮樣本塊近鄰域的關(guān)系，引入距離修正因子對匹配策略進(jìn)行修正，克服了原算法中紋理錯誤匹配以及錯誤延續(xù)的缺點(diǎn)，提高了修復(fù)質(zhì)量。通過對比實驗，驗證了本文算法具有良好的修復(fù)效果，符合人們的視覺感受。此外，本文的搜索策略是全局搜索，使本算法自動確定最佳匹配塊的搜索范圍是本文下一步的研究內(nèi)容。

［1］Guillemot C，Le Meur O.Image inpainting：Overview and recent advances ［J］.IEEE Signal Processing Magazine，2014，31 （1）：127－144.

［2］Cheng Qing，Shen Huanfeng，Zhang Liangpei，et al.Inpainting for remotely sensed images with multichannel nonlocal total variation model［J］.IEEE Transactions on Geoscience and Remote Sensing，2014，52 （1）：175－187.

［3］Wen Youwei，Chan RH，Yip AM.A primal dual method for total－variation－based wavelet domain inpainting ［J］.IEEE Transactions on Image Processing，2012，21 （1）：106－114.

［4］Jiang Jun，Wang Zhaoxia.The research of Tibet mural digital images inpainting using CDD model［C］／／International Symposium on Instrumentation and Measurement.Toronto：IEEE，2013：805－807.

［5］Elad M，Starck JL，Querre P，et al.Simultaneous cartoon and texture image inpainting using morphological component analysis（MCA） ［J］.Journal on Applied and Computational Harmonic Analysis，2005，19 （3）：340－358.

［6］Liu Ji，Przemyslaw Musialski，Peter Wonka，et al.Tensor completion for estimating missing values in visual data ［J］.IEEE Transactions on Pattern Analysis And Machine Intelligence，2013，35 （1）：208－220.

［7］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.

［8］Xu Zongben，Sun Jian.Image inpainting by patch propagation using patch sparsity ［J］.IEEE Transactions on Image Processing，2010，19 （5）：1153－1165.

［9］Bugeau A，Bertalmio M，Vicent Caselles.A comprehensive framework for image inpainting ［J］.IEEE Transactions on Image Processing，2010，19 （10）：2634－2645.

［10］Anamandra SH，Chandrasekaranv.Exemplar－based color image inpainting using a simple and effective gradient function［C］／／Proceeding of International Conference on Image Processing and Computer Vision.Las Vegas：CSREA Press，2010：140－145.

［11］Zhou Yatong，Li Lin.Research on weighted priority of exemplar－based image inpainting ［J］.Journal of Electronics，2012，29 （1）：166－170.

［12］Meur O.Le，Gautier J.Examplar－based inpainting based on local geometry ［C］／／Proceeding of International Conference on Image Processing.Brussels：IEEE，2011：3401－3404.

［13］Meur O.Le，Guillemot C.Super－resolution－based inpainting［C］／／Proceeding European Conference on Computer Vision.Berlin：Springer，2012：554－567.

［14］Jemi Florinabel D，Ebenezer Juliet S.Combined frequency and spatial domain－based patch propagation for image completion ［J］.Computers＆Graphics，2011，35 （6）：1051－1062.

［15］CHANG Chen，YIN Lixin，F(xiàn)ANG Baolong.An improved Criminisi algorithm for image inpainting ［J］.Computer Applications and Software，2012，29 （9）：240－242 （in Chinese）.［常晨，尹立新，方寶龍.一種改進(jìn)的Criminisi圖像修復(fù)算法［J］.計算機(jī)應(yīng)用與軟件，2012，29 （9）：240－242.］

［16］Sooraj Bhat.Exemplar based inpainting.zip［CP／OL］.［2014－08－30］.http：／／white.stanford.edu／teach／images／5／55／ExemplarBasedInpainting.zip.

［17］Elad M.Problem＿session＿04＿code.zip［CP／OL］.［2013－12－16］.http：／／www.cs.technion.ac.il／～matanpr／GSS／.

［18］Liu Ji.LRTC＿package＿ji.zip［CP／OL］.［2014－09－01］.http：／／pages.cs.wisc.edu／～ji－liu／publications.html.