基于幾何距離的Criminisi圖像修復算法

王新年，王 哲，王 演

（大連海事大學 信息科學技術學院，遼寧 大連116026）

0 引 言

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

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

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

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

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

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

1 Criminisi修復算法

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

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

1.1 計算優先權

圖1 Criminisi算法

目標塊優先權的計算是Criminisi算法的核心和關鍵所在，應使具有較多已知信息和較強結構的目標塊先被填充，以保證填充準確有序地進行［15］。

首先通過識別用戶標記出破損區域Ω，計算受損邊界δΩ的每一點的優先權，并找出優先權最大的點p，并且確定p 點所在的塊Ψp，定義優先權為

式中：│Ψp│是Ψp的面積，也就是Ψp內像素點的總個數，C（q）是像素點q的置信度值，滿足初始條件

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

1.2 搜索最佳匹配塊

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

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

1.3 更新邊界和邊界置信度

最后更新邊界和當前塊的置信度。其中置信度為

重復上述3 個步驟，直至破損區域修復完成，即Ω為空。

1.4 Criminisi算法優缺點

Criminisi算法充分地考慮了圖像的紋理特征與結構特性，同時保證了結構的完整性和紋理的延續性，對破損區域較大的圖像有很好的修復效果。

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

2 對Criminisi算法的改進

2.1 優先權的改進

Criminisi算法的核心思想就是考慮了破損邊緣的優先權，確定了修復的先后順序，從而使得修復有序的進行，確保了紋理信息的延續。隨著破損區域修復過程的進行，置信度C（p）逐漸變化，當等照度線向量 ▽I⊥p與p 點的法線向量np垂直時，數據項D（p）卻為0，這使得當C（p）相對很大時，與D（p）相乘后的結果卻趨近于0，這就造成擁有較高置信度的待匹配塊得不到優先修復，最終造成紋理紊亂的情況。

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

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

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

通常，情況一、二、四應該為被優先修復的情況，而情況三則處于中間狀態，為防止極端情況出現，特對數據項算法進行修改，將與np兩向量點乘后取模改為先分別取模，再相乘，最后與權函數W（，np）相乘，數學描述為

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

圖3 權函數對比

通過修改優先權，錯誤傳播的概率極大地降低，紋理得到正確的修復。

2.2 匹配策略的改進

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

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

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

2.3 算法步驟

算法的輸入為標記破損區域的圖像，輸出為完成修復的結果圖，參數是匹配塊窗口大小w 和搜索區域 （本文默認為整幅圖）。

步驟1 根據標定的破損區域，提取破損區域的邊緣δΩ；

步驟2 根據式 （1），式 （2），式 （3），式 （8），式（9）確定破損邊緣優先權最大的兩點，并確定其所在的破損塊；

步驟3 以上兩個破損塊同時根據式 （5），式 （6），式（10），式 （11）在指定區域內搜尋各自的最佳匹配塊，并將其對應點的像素值復制到目標塊的相應像素點；

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

步驟5 重復執行步驟1～步驟4，循環往復直至破損區域為空，修復完成。

3 實驗結果與分析

為驗證本文算法的性能，進行了4 組實驗。實驗一、二、三是本文算法與Criminisi算法修復結果的比較，實驗四是本文算法同文獻 ［5，6］修復結果的比較。

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

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

3.1 實驗一

圖4所示的是對結構簡單的破損圖像修復結果。可以看出，Criminisi算法的修復結果有著明顯的誤匹配以及紋理錯誤延續現象，而本文的算法克服了以上錯誤，算法效果明顯優于Criminisi算法。

3.2 實驗二

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

圖4 結構簡單的破損圖像修復效果比較

圖5 蹦極人修復效果比較

3.3 實驗三

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

圖6 海邊女孩修復效果比較

3.4 實驗四

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

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

文獻 ［6］是基于低秩張量補全的圖像修復算法。由實驗結果可以看出，無論破損區域的粗細如何，對于橫條紋破損，文獻 ［6］都不能進行有效地修復，修復結果產生模糊的現象。

而本文方法始終能從破損圖像的完好區域找到匹配的塊，從而對圖像進行有效地修復。

圖7 海邊小鳥修復效果比較

4 結束語

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

［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，FANG Baolong.An improved Criminisi algorithm for image inpainting ［J］.Computer Applications and Software，2012，29 （9）：240－242 （in Chinese）.［常晨，尹立新，方寶龍.一種改進的Criminisi圖像修復算法［J］.計算機應用與軟件，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.