改進(jìn)優(yōu)先級(jí)的分步匹配圖像修復(fù)算法

朱曉臨， 王傳奇， 范承凱

（合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，安徽 合肥 230009）

改進(jìn)優(yōu)先級(jí)的分步匹配圖像修復(fù)算法

朱曉臨， 王傳奇， 范承凱

（合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，安徽 合肥 230009）

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

分步匹配；優(yōu)先級(jí)；亮度；方差；1范數(shù)

圖像修復(fù)是利用圖像中的已知部分修復(fù)圖像中丟失或損壞的部分，其目的是使修復(fù)后的圖像達(dá)到人眼無(wú)法識(shí)別的效果。圖像修復(fù)在破損圖像的修補(bǔ)，珍貴文物的復(fù)原，以及影視特技制作等方面有著廣泛的應(yīng)用。目前圖像修復(fù)方法主要有結(jié)構(gòu)修復(fù)方法和紋理合成修復(fù)方法。

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

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

1 Criminisi算法簡(jiǎn)介

1.1 計(jì)算待修補(bǔ)塊的優(yōu)先權(quán)

目標(biāo)塊優(yōu)先權(quán)的計(jì)算是Criminisi算法的核心和關(guān)鍵所在，它使具有較多已知信息和較強(qiáng)結(jié)構(gòu)的目標(biāo)塊先被填充以保證填充準(zhǔn)確有序地進(jìn)行。如圖1所示，I表示整幅圖像，Ω表示待修復(fù)區(qū)域，δΩ代表其邊界，Φ表示已知區(qū)域，Ψp為以p∈δΩ為中心點(diǎn)的待修復(fù)塊。

圖1 Criminisi算法示意圖

對(duì)于以邊界線δΩ上的點(diǎn)p為中心的目標(biāo)塊，Criminisi算法定義的優(yōu)先級(jí)為：

其中：

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

D（p）稱為數(shù)據(jù)項(xiàng)，表示每次通過邊界線δΩ的等照度強(qiáng)度。np是待修復(fù)區(qū)域Ω的邊界δΩ在點(diǎn)p處的法向量，是已知區(qū)域Φ的邊界的梯度向量的垂直向量，α是標(biāo)準(zhǔn)化因子(α=255)。

1.2 搜索最佳匹配塊

計(jì)算出最大優(yōu)先級(jí)的目標(biāo)塊Ψ后，就要在已知區(qū)域內(nèi)搜索此目標(biāo)塊的最佳匹配塊Ψ，目標(biāo)塊與最佳匹配塊有如下匹配準(zhǔn)則：

其中，d（Ψ,Ψq）表示目標(biāo)塊Ψ和樣本塊Ψq中對(duì)應(yīng)已知像素的顏色差的平方和，稱為相似性度量函數(shù)。

1.3 置信度的更新

在找到最佳匹配塊Ψ后，將塊Ψ中的像素拷貝到目標(biāo)塊Ψ中的未知像素點(diǎn)，該目標(biāo)塊內(nèi)未知像素點(diǎn)轉(zhuǎn)變?yōu)橐阎袼攸c(diǎn)，因此這些點(diǎn)的置信度需要重新更新為：

重復(fù)1.1～1.3步驟，直至待修復(fù)區(qū)域被填完為止。

1.4 Criminisi算法中存在的問題

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

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

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

2 本文算法

2.1 優(yōu)先級(jí)改進(jìn)

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

其中：

稱為亮度的局部方差，K是待修復(fù)塊Ψp中的已知像素，是待修復(fù)塊Ψp中所有已知像素的平均值，LΨp是待修復(fù)塊Ψp中已知像素的個(gè)數(shù)；α,β,γ為各項(xiàng)權(quán)重，且α+β+γ=1。

2.2 相似性度量函數(shù)的改進(jìn)

根據(jù)文獻(xiàn)[19]的結(jié)論，在誤差估計(jì)時(shí)，當(dāng)數(shù)據(jù)誤差較大時(shí)，1范數(shù)具有較好的抗差性；而當(dāng)數(shù)據(jù)誤差不明顯時(shí)，最小二乘法對(duì)數(shù)據(jù)更敏感。因?yàn)閳D像修復(fù)在開始搜索最佳匹配塊時(shí)，多數(shù)匹配塊和待修復(fù)塊存在較大誤差，所以先利用1范數(shù)較好的抗差性進(jìn)行粗略篩選；然后對(duì)篩選出的結(jié)果利用最小二乘法對(duì)數(shù)據(jù)的敏感性找到最佳匹配塊。因此，本文將匹配過程分為兩步進(jìn)行：

第1步. 使用1范數(shù)，相應(yīng)的相似性度量函數(shù)改為：

獲取初始匹配結(jié)果；其中II ′,分別對(duì)應(yīng)塊Ψ和Ψq中的已知像素點(diǎn)。

第2步. 從第1步初始匹配結(jié)果中選取的若干個(gè)誤差最小的目標(biāo)塊（實(shí)驗(yàn)證明n通常取5比較適當(dāng)），再使用最小二乘法，相似性度量函數(shù)為：

進(jìn)行二次匹配，獲取最佳匹配塊；其中 ,II′分別對(duì)應(yīng)塊Ψ,中的已知像素點(diǎn)。

實(shí)驗(yàn)證明：經(jīng)過兩次選取不僅增加了匹配的準(zhǔn)確性同時(shí)也使程序具有非常好的魯棒性。

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

2.3 算法的步驟

步驟 1. 確定待修復(fù)區(qū)域的邊界，通過改進(jìn)的優(yōu)先級(jí)式(5)計(jì)算邊界點(diǎn)上各待修復(fù)點(diǎn)的優(yōu)先級(jí)，選取出最大優(yōu)先級(jí)的待修復(fù)點(diǎn)；

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

圖2 本文算法與其他算法修復(fù)結(jié)果對(duì)比

圖3 本文算法與其他算法修復(fù)結(jié)果對(duì)比

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

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

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

圖4 本文算法與其他算法修復(fù)結(jié)果對(duì)比

表1 各種算法修復(fù)時(shí)間比較(s)

4 結(jié) 論

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

[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ìn)的基于紋理合成的圖像修復(fù)算法[J]. 合肥工業(yè)大學(xué)學(xué)報(bào): 自然科學(xué)版, 2011, 34(2): 313-316.

[9] 劉麗萍. 基于加權(quán)匹配塊的圖像修復(fù)方法[D]. 上海:華東師范大學(xué), 2009.

[10] 江 平, 張 錦. 一種結(jié)合CDD模型和Criminisi算法的圖像修復(fù)算法[J]. 圖學(xué)學(xué)報(bào), 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] 彭坤楊, 董蘭芳. 一種基于圖像平均灰度值的快速圖像修復(fù)算法[J]. 中國(guó)圖象圖形學(xué)報(bào), 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] 朱曉臨, 陳曉冬, 朱園珠, 等. 基于顯著結(jié)構(gòu)重構(gòu)與紋理合成的圖像修復(fù)算法[J]. 圖學(xué)學(xué)報(bào), 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] 王宇慶. 局部方差在圖像質(zhì)量評(píng)價(jià)中的應(yīng)用[J]. 中國(guó)光學(xué), 2011, 4(5): 532-536.

[19] 白會(huì)人, 李維仁. 測(cè)量平差中粗差的一次范數(shù)最小的處理方法[J]. 吉林建筑工程學(xué)院學(xué)報(bào), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272024)

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