改進優先級的分步匹配圖像修復算法

朱曉臨， 王傳奇， 范承凱

（合肥工業大學數學學院，安徽 合肥 230009）

改進優先級的分步匹配圖像修復算法

朱曉臨， 王傳奇， 范承凱

（合肥工業大學數學學院，安徽 合肥 230009）

首先對Criminisi算法的優先級進行了改進，將圖像的局部亮度方差作為優先級的一個度量因子，使圖像的修復順序更加合理；然后對Criminisi算法最佳匹配塊的獲取過程進行了改進，先后使用1范數和最小二乘法，改進了相似性度量函數，進行分步篩選，獲取最佳匹配塊，使得匹配更為準確，修復效果更加理想。

分步匹配；優先級；亮度；方差；1范數

圖像修復是利用圖像中的已知部分修復圖像中丟失或損壞的部分，其目的是使修復后的圖像達到人眼無法識別的效果。圖像修復在破損圖像的修補，珍貴文物的復原，以及影視特技制作等方面有著廣泛的應用。目前圖像修復方法主要有結構修復方法和紋理合成修復方法。

結構修復[1-3]方法對破損區域較小的圖像修復效果較好。紋理合成修復方法主要針對破損區域較大的圖像進行修復。文獻[4-5]提出的一種基于樣本的圖像修復算法是這類算法中較為典型的方法。一些學者在此基礎上進行了修復效果或者減少修復耗時方面的研究，文獻[6]在Criminisi方法的基礎上提出了一種一致性局部搜索(coherence-based local searching, CBLS)的算法來完成破損圖像的修復。文獻[7]考慮到Criminisi算法中置信度項迅速下降為零的不足，將優先級由乘法改為加法，取得了一定的修復效果。文獻[8]改進了Criminisi算法中的優先級，增加了邊界對修復順序的影響，對部分圖像的修復起到積極的作用。文獻[9]對最佳匹配塊的選取標準作出了改進，考慮到匹配塊與待修復塊的距離，使選取的最佳匹配塊更合理。文獻[10]結合了CDD模型和Criminisi算法的優點，提出了一種新的圖像修復算法，該算法不僅可以處理劃痕，也可以處理圖像中大面積的破損，同時縮短了修復時間。文獻[11]提出了一種新的置信度計算方法，同時提出了修復塊的相鄰區域內的“損傷前”搜索方法來縮小搜索范圍面積，降低運行時間。文獻[12]提出了自適應樣本塊的修復算法，可根據完好區域周圍的結構信息，自適應選取樣本塊的大小，對一些具有復雜背景的圖像能得到較好的修復效果。文獻[13]提出了一種基于圖像平均灰度值的快速圖像匹配算法，在匹配前對平均灰度值進行快速比較，結合閾值控制篩選掉大部分候選紋理塊，然后在進行第二次精確匹配，大幅降低了修復時間，但沒有改進修復效果。文獻[14]通過生成紋理解決丟失過多部分圖像的值，同時使用信心地圖確定順序填寫，提出了統一的框架結構和基于樣本的圖像修復算法。文獻[15-17]均提出了自己的改進方法。

本文首先在計算優先級時考慮到圖像的局部方差信息，使優先級的修復順序更加合理；其次提出分步篩選式匹配法，將匹配過程分為兩步，先使用1范數構造相似性度量函數，進行初步篩選；再對篩選結果使用最小二乘法構造相似性度量函數，進行第二次精確匹配，提高了匹配的準確性和效率，增強了圖像結構的連續性。另外為了降低修復時間，在搜索最佳匹配塊時進行局部搜索。實驗表明改進后的算法能取得更好的效果。

1 Criminisi算法簡介

1.1 計算待修補塊的優先權

目標塊優先權的計算是Criminisi算法的核心和關鍵所在，它使具有較多已知信息和較強結構的目標塊先被填充以保證填充準確有序地進行。如圖1所示，I表示整幅圖像，Ω表示待修復區域，δΩ代表其邊界，Φ表示已知區域，Ψp為以p∈δΩ為中心點的待修復塊。

圖1 Criminisi算法示意圖

對于以邊界線δΩ上的點p為中心的目標塊，Criminisi算法定義的優先級為：

其中：

C（p）稱為置信項，用于表示待修復塊Ψp中已知像素的比例；初始化C（p）為：

D（p）稱為數據項，表示每次通過邊界線δΩ的等照度強度。np是待修復區域Ω的邊界δΩ在點p處的法向量，是已知區域Φ的邊界的梯度向量的垂直向量，α是標準化因子(α=255)。

1.2 搜索最佳匹配塊

計算出最大優先級的目標塊Ψ后，就要在已知區域內搜索此目標塊的最佳匹配塊Ψ，目標塊與最佳匹配塊有如下匹配準則：

其中，d（Ψ,Ψq）表示目標塊Ψ和樣本塊Ψq中對應已知像素的顏色差的平方和，稱為相似性度量函數。

1.3 置信度的更新

在找到最佳匹配塊Ψ后，將塊Ψ中的像素拷貝到目標塊Ψ中的未知像素點，該目標塊內未知像素點轉變為已知像素點，因此這些點的置信度需要重新更新為：

重復1.1～1.3步驟，直至待修復區域被填完為止。

1.4 Criminisi算法中存在的問題

(1) Criminisi算法中計算優先級是采用乘法P（p ）=C（p ）·D（p），這樣的計算方法容易產生錯誤的積累，一旦有一次優先級選擇不合理，容易把錯誤的修復順序放大傳遞下去。且隨著修復的進行，數據項D（p）的值會迅速下降為零，使得修復順序不準確[7]，因此本文將優先級更改為加法。

(2) Criminisi算法只考慮到了置信項C（p）和數據項 D（p）兩個因素，包含的信息有限，修復順序不夠合理，從而導致修復效果不理想。

(3) Criminisi算法在選擇最佳匹配塊時，使用最小二乘法比較圖像的顏色信息，但是目標塊的像素值和待修復塊往往差距比較大，這時只使用最小二乘法進行的匹配不夠準確[12]。

2 本文算法

2.1 優先級改進

針對Criminisi算法，本文提出了一種新的計算優先級的方法。Criminisi算法在計算優先級的置信項C（p）時，只考慮到待修復區域中像素的個數，而忽略了待修復區域中像素所包含的結構信息。一般連續的圖像結構更加符合人眼的視覺信息，因而應使包含更多結構信息的區域優先得到修復，使修復結果更加符合自然。文獻[18]指出圖像的局部方差能夠較好地描述圖像的細節信息，且圖像的局部方差分布包含了圖像的重要結構信息，可以將圖像的局部方差作為分析圖像內容信息的一種方法。本文將圖像的局部方差作為控制填充次序的一個因素引入到優先級中。在RGB顏色空間中方差的計算復雜度高，同時其各分量的變化都會對像素值產生影響，而HSV顏色空間中各分量相對比較獨立，便于計算，所以需首先將RGB顏色空間轉化為HSV空間，在HSV顏色空間中提取圖像的亮度信息，把亮度的局部方差作為表征圖像結構信息的重要特征，使包含更多圖像內容的區域優先得到修復。改進后的優先級為：

其中：

稱為亮度的局部方差，K是待修復塊Ψp中的已知像素，是待修復塊Ψp中所有已知像素的平均值，LΨp是待修復塊Ψp中已知像素的個數；α,β,γ為各項權重，且α+β+γ=1。

2.2 相似性度量函數的改進

根據文獻[19]的結論，在誤差估計時，當數據誤差較大時，1范數具有較好的抗差性；而當數據誤差不明顯時，最小二乘法對數據更敏感。因為圖像修復在開始搜索最佳匹配塊時，多數匹配塊和待修復塊存在較大誤差，所以先利用1范數較好的抗差性進行粗略篩選；然后對篩選出的結果利用最小二乘法對數據的敏感性找到最佳匹配塊。因此，本文將匹配過程分為兩步進行：

第1步. 使用1范數，相應的相似性度量函數改為：

獲取初始匹配結果；其中II ′,分別對應塊Ψ和Ψq中的已知像素點。

第2步. 從第1步初始匹配結果中選取的若干個誤差最小的目標塊（實驗證明n通常取5比較適當），再使用最小二乘法，相似性度量函數為：

進行二次匹配，獲取最佳匹配塊；其中 ,II′分別對應塊Ψ,中的已知像素點。

實驗證明：經過兩次選取不僅增加了匹配的準確性同時也使程序具有非常好的魯棒性。

蘭江比孔老一想象的還要險惡，五月連綿的那幾場暴雨，把江面延伸了差不多三倍寬，兩岸的農田，現在都成了汪洋。想游過湍急的蘭江幾乎是不可能的，唯一可以想想辦法的就是找一條船。

2.3 算法的步驟

步驟 1. 確定待修復區域的邊界，通過改進的優先級式(5)計算邊界點上各待修復點的優先級，選取出最大優先級的待修復點；

步驟 2. 在圖像的已知區域，運用式(6)獲取初始匹配結果；

步驟4. 用獲取最佳匹配塊替換待修復樣本塊；

步驟5. 重復步驟1～4，直到待修復區域的邊界為零停止。

3 實驗結果

本文以MATLAB 7.10為工具，在Intel奔騰雙核處理器(2.2 GHz)、4 G內存的PC機上運行，同時為了減少修復時間，均采用局部搜索。圖2～4為本文算法與Criminisi算法、文獻[7]、文獻[8]和文獻[9]算法的修復結果比較。其中圖2(g)、圖3(g)和圖4(g)是為了說明分步匹配的效果而做的對比圖，這個圖的算法除了匹配函數改為原匹配函數（即只使用2范數）以外，其他步驟與本文算法一樣。

由圖2對比圖可以看出，圖2(c)中修復的屋脊已經嚴重變形，而且將樹木延伸到了水里。圖2(d)的修復效果比圖2(c)有所改善，但是水草向上延伸到了屋脊上方。圖2(e)的屋檐右下角也出現了樹木，一部分湖水修復錯誤。圖2(f)的水與岸接觸的地方出現了多余的石階，屋檐與周圍的實物過度很不自然，屋檐下方出現凌亂的樹木，導致偏差延續。圖2(g)前面屋檐上出現了許多數葉，修復效果不夠理想。這是匹配函數不準確造成的。

圖2(h)是本文算法的修復結果，屋檐連接整齊，屋脊清晰，水與岸過渡的自然，并且房屋上方修復出來的樹木和周圍的環境非常相稱。

圖3(d)和圖3(e)修復結果圖中的右下角草坪與水泥路面接觸的地方過渡得不合理，均將右下角的路面延伸到了草坪里面，尤其是圖3(e)更加明顯。

圖 3(h)是本文算法的修復結果，效果很好。圖3(g)和圖3(h)修復結果并無明顯差別，若將圖片放大看，圖3(h)右下角草坪修復的更加均勻，看起來更加符合人眼視覺。

圖2 本文算法與其他算法修復結果對比

圖3 本文算法與其他算法修復結果對比

如圖4所示，圖4(e)～(g)修復都不是很理想。圖4(d)上半部分草地修復有明顯的填充錯誤，且下部分磚臺過渡不合理。

圖4(h)是本文算法修復效果，可以看出下方磚臺連接整齊，過渡自然，更加符合人眼視覺效果。

本文算法雖然將匹配過程分為兩步進行，增加了算法的復雜度，但是因為1范數的計算復雜度比2范數小，所以在保證修復效果更好的前提下，總修復時間和其他修復時間較短的算法相比并無明顯增加（見表1）。

圖4 本文算法與其他算法修復結果對比

表1 各種算法修復時間比較(s)

4 結 論

本文在Criminisi算法的基礎上，通過引入局部方差，提出了一種更為合理的優先級來決定修復順序。優先權采用各項加權和，不僅可以有效避免因置信度迅速衰減帶來的錯誤填充次序，而且針對不同的圖像采用不同的權系數，使圖像的紋理信息和結構信息得以準確擴散，減少錯誤的積累。在相似性度量函數的計算中，對原匹配函數進行了更改，提出了分步篩選式匹配法，將匹配過程分為兩步，先使用1范數構造相似性度量函數，進行初步篩選；再對篩選結果使用最小二乘法構造相似性度量函數，進行第二次精確匹配，提高了匹配的準確性和效率，增強了圖像結構的連續性。實驗結果證明，本文方法修復的結果更合理。

[1] Bertalmio M, Sapiro G, Caselles V, et al. Image inpainting [C]//Proceedings of International Conference on Computer Graphics and Interactive Techniques, New Orleans, Louisiana, USA, 2000: 417-424.

[2] Chan T F, Shen Jianhong. Mathematical models for local nontexture inpaintings [J]. SIAM Journal on Applied Mathematics, 2002, 62(3): 1019-1043.

[3] Chan T F, Shen Jianhong. Non-texture inpainting by curvature-driven diffusions (CDD) [J]. Journal of Visual Communication and Image Representation, 2001, 12(4): 436-449.

[4] Criminisi A, Perez P, Toyama K. Object removal by exemplar-based inpainting [C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Madison, WI, USA, 2003: 721-728.

[5] 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.

[6] Tang Feng, Ying Yiting, Wang Jin, et al. A novel texture synthesis based algorithm for object removal in photographs [M]. Advances in Computer Science-ASIAN, 2004, Level Decision Making. Berlin Springer, Germany, 2004: 248-258.

[7] Cheng Wenhuang, Hsieh C W, Lin Shengkai, et al. Robust algorithm for exemplar-based image inpainting [C]// Proceedings of the International Conference on Computer Graphics, Imaging and Visualization (CGIV′05), China, 2005: 64-69.

[8] 黃淑兵, 朱曉臨, 許云云, 等. 一種改進的基于紋理合成的圖像修復算法[J]. 合肥工業大學學報: 自然科學版, 2011, 34(2): 313-316.

[9] 劉麗萍. 基于加權匹配塊的圖像修復方法[D]. 上海:華東師范大學, 2009.

[10] 江 平, 張 錦. 一種結合CDD模型和Criminisi算法的圖像修復算法[J]. 圖學學報, 2014, 35(5): 741-746.

[11] Li Zhanming, Hu Wenjin. A novel method for exemplar-based image inpainting [J]. Journal of Information & Computational Science, 2012, 9(3): 761-769.

[12] Zhou Hailing, Zheng Jianmin. Adatptive patch size determination for patch-based image completion [C]// Proceedings of 2010 IEEE 17th International Conference on Image Processing, Hong Kong, China, 2010: 421-424.

[13] 彭坤楊, 董蘭芳. 一種基于圖像平均灰度值的快速圖像修復算法[J]. 中國圖象圖形學報, 2010, 15(1): 50-55.

[14] Sairam V, Sarma R R, Balasubramanian S, et al. A unified framework for geometry and exemplar based image inpainting [C]//Image Information Processing (ICIIP), 2013 IEEE Second International Conference on. IEEE, USA, 2013: 511-515.

[15] Nishihara A. Iterative gradient driven patch-based inpainting [M]. Advances in Image and Video Technology. Berlin Springer, Berlin, 2012: 71-81.

[16] 朱曉臨, 陳曉冬, 朱園珠, 等. 基于顯著結構重構與紋理合成的圖像修復算法[J]. 圖學學報, 2014, 35(3): 336-342.

[17] Tae-o-sot S, Nishihara A. Exemplar-based image inpainting with patch shifting scheme [C]//17th International Conference on Digital Signal Processing, Greece, 2011: 1-5.

[18] 王宇慶. 局部方差在圖像質量評價中的應用[J]. 中國光學, 2011, 4(5): 532-536.

[19] 白會人, 李維仁. 測量平差中粗差的一次范數最小的處理方法[J]. 吉林建筑工程學院學報, 2004, 20(4): 6-8.

Double-Step Matching Image Restoration Algorithm with Improved Priority

Zhu Xiaolin, Wang Chuanqi, Fan Chengkai

(School of Mathematics, Hefei University of Technology, Hefei Anhui 230009, China)

Firstly, the priority in Criminisi algorithm is improved by adding the local luminance variance of the image as one metric factor of the priority, which gives more reasonable repair order to the image restoration. Secondly, the block matching process of the algorithm given in this paper is changed from one-step to double-step by use of 1 norm and the least square method, respectively, to modify the similarity measuring function. This double-step block matching process obtains more accurate matching block and better restoration result.

double-step matching; priority; luminance; variance; 1 norm

TP 751.1

A

2095-302X(2015)03-0407-06

2014-10-08；定稿日期：2014-10-27

國家自然科學基金資助項目(61272024)

朱曉臨(1964-)，男，安徽池州人，教授，博士。主要研究方向為數值逼近、圖形圖像處理、隨機微分方程數值解、CAGD。E-mail：zxl_hfut@126.com