基于改進(jìn)Criminisi算法的圖像修復(fù)

李愛菊，鈕文良

北京聯(lián)合大學(xué)，北京 102200

基于改進(jìn)Criminisi算法的圖像修復(fù)

李愛菊，鈕文良

北京聯(lián)合大學(xué)，北京 102200

1 引言

隨著計(jì)算機(jī)圖像技術(shù)的迅速發(fā)展，其在生物醫(yī)學(xué)、工業(yè)生產(chǎn)、遙感測(cè)繪等領(lǐng)域得到了成功的應(yīng)用。但是在圖像拍攝和采集過(guò)程中，由于受到外界因素的干擾，不可避免會(huì)丟失部分信息，一些區(qū)域缺失，影響圖像質(zhì)量[1]。圖像修復(fù)技術(shù)是指根據(jù)已知信息，對(duì)修復(fù)區(qū)域內(nèi)丟失信息進(jìn)行補(bǔ)充，提高圖像在視覺(jué)上的真實(shí)性，已經(jīng)成為圖像處理領(lǐng)域的研究熱點(diǎn)和重點(diǎn)[2]。

針對(duì)圖像修復(fù)問(wèn)題，學(xué)者們投入了大量的時(shí)間和精力進(jìn)行相關(guān)研究，提出了一些圖像修復(fù)算法，當(dāng)前主要分為兩類方法：基于非紋理圖像修復(fù)和基于紋理修復(fù)方法[3]?；诜羌y理的圖像修復(fù)方法主要是利用待修復(fù)區(qū)域附近的已知信息，按一定的規(guī)則向待修復(fù)區(qū)域蔓延，如文獻(xiàn)[4]提出的基于高階偏微分的圖像修復(fù)算法，文獻(xiàn)[5]提出的基于整體變分（TV）模型的圖像修復(fù)算法等，它們適合于小區(qū)域的圖像修復(fù)，但如果待修復(fù)的區(qū)域比較大，難以獲得比較理想的修復(fù)效果。文獻(xiàn)[6]提出基于先驗(yàn)?zāi)Ｐ偷膱D像修復(fù)算法，對(duì)于結(jié)構(gòu)信息的圖像，可以得到較好的修復(fù)效果，但是對(duì)于含有豐富紋理圖像，修復(fù)效果較差?；诩y理綜合的修復(fù)方法指利用塊匹配選取合適的紋理塊來(lái)修復(fù)，其中Criminisi算法是最為經(jīng)典的紋理圖像修復(fù)算法[7]，其首先從圖像完好區(qū)域中尋找與待修復(fù)區(qū)域最匹配的像素塊，然后將其填充到受損區(qū)域，修復(fù)效果較好。然而在實(shí)際應(yīng)用過(guò)程，Criminisi算法存在一些不足，如出現(xiàn)馬賽克效應(yīng)和紋理混亂現(xiàn)象。為了克服Criminisi算法的不足，國(guó)內(nèi)外一些學(xué)者在該算法的基礎(chǔ)上，提出了一些改進(jìn)Criminisi圖像修復(fù)算法[8-11]，但是這些算法都存在各自的缺陷，如何提高圖像修復(fù)效果，值得進(jìn)一步研究。

為了獲得理想的修復(fù)效果，針對(duì)Criminisi算法存在的不足，提出一種改進(jìn)Criminisi算法的圖像修復(fù)算法，并通過(guò)仿真實(shí)驗(yàn)測(cè)試算法的可行性和優(yōu)越性。首先改進(jìn)優(yōu)先權(quán)計(jì)算方式找到最優(yōu)待修復(fù)塊，然后完善最優(yōu)匹配塊搜索策略，并找到最優(yōu)匹配塊，最后采用新的置信值更新方式以獲得更為理想的修復(fù)效果，并通過(guò)仿真實(shí)驗(yàn)測(cè)試算法性能。結(jié)果表明，相對(duì)于Criminisi算法，改進(jìn)Criminisi算法不僅得到了理想的圖像修復(fù)效果，而且大幅度減少了修復(fù)時(shí)間，提高了圖像的修復(fù)效率。

2 Criminisi算法

2.1 基本工作原理

Criminisi算法的工作原理如圖1所示，其中，Ω表示破損區(qū)域，I是待修復(fù)圖像，?Ω表示破損區(qū)域的邊界，點(diǎn)p為目標(biāo)像素點(diǎn)，Φ表示樣本區(qū)域，▽Ip是等照度線的切線方向，np是受損邊界切線的法向量，φp是以p中心的目標(biāo)塊[12]。

圖1 Criminisi算法原理

2.2 Criminisi算法的工作步驟

（1）計(jì)算優(yōu)先權(quán)。先標(biāo)記出待修復(fù)區(qū)域Ω，那么Φ=I-Ω，取以受損邊緣上像素點(diǎn)p為中心的模版φp，計(jì)算受損邊緣每個(gè)像素點(diǎn)的優(yōu)先權(quán)，并按優(yōu)先權(quán)排序，則優(yōu)先權(quán)P(p)計(jì)算為：

其中，D(p)為數(shù)據(jù)項(xiàng)，C(p)為置信度，它們定義為：

（2）尋找最佳匹配塊。計(jì)算當(dāng)前邊緣所有像素塊的優(yōu)先權(quán)，找出優(yōu)先權(quán)最大的塊φp作為當(dāng)前的目標(biāo)塊，采用全局搜索的方法，將SSD作為匹配準(zhǔn)則在未破損區(qū)域內(nèi)搜索與待修補(bǔ)塊相似度最高的匹配塊。SSD匹配準(zhǔn)則定義如下：

式中，d(φp，φq)是φp，φq對(duì)應(yīng)已知像素點(diǎn)顏色RGB。

（3）更新置信度。每次修復(fù)的塊都在待修復(fù)區(qū)域邊緣上，修復(fù)區(qū)域邊緣總是處在不斷的變化中，因此有必要每完成一個(gè)紋理塊的修復(fù)就對(duì)邊緣進(jìn)行更新。最高優(yōu)先級(jí)的目標(biāo)塊被填充后，剛剛填充的像素點(diǎn)由受損區(qū)域變?yōu)闃颖緟^(qū)，置信度發(fā)生了變化，因此需要更新像素點(diǎn)的置信度，置信度更新為：

更新置信度得到一個(gè)新的邊緣，圖像的待修復(fù)區(qū)域發(fā)生了變化，邊緣像素點(diǎn)的置信度也就發(fā)生了變化。重復(fù)上述三個(gè)步驟直到待修復(fù)區(qū)域Ω為空，則修復(fù)完畢。

綜合上述可知，基于Criminisi算法的圖像修復(fù)流程圖具體如圖2所示。

圖2 Criminisi算法流程圖

3 改進(jìn)Criminisi算法

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

作為Criminisi算法的第一步，待修復(fù)塊優(yōu)先權(quán)的判定至關(guān)重要，根據(jù)文獻(xiàn)[13]中的實(shí)驗(yàn)結(jié)果，對(duì)式（1）改進(jìn)，具體做法如下：

3.2 最佳匹配塊搜索算法完善

在Criminisi算法中，由上至下、左到右的最優(yōu)匹配塊的搜索順序，最終找到最優(yōu)匹配塊，然而在圖像修復(fù)塊的匹配過(guò)程中，會(huì)產(chǎn)生大量候選塊，若找到最優(yōu)匹配塊與相差較遠(yuǎn)待修復(fù)塊，那么對(duì)待修復(fù)塊的已知像素點(diǎn)進(jìn)行較好修復(fù)，其他部分修復(fù)效果差。為此，提出一種改進(jìn)最優(yōu)匹配塊搜索策略，具體為：

（1）根據(jù)優(yōu)先權(quán)值確定的當(dāng)前待修復(fù)點(diǎn)。

（2）以當(dāng)前待修復(fù)點(diǎn)為中心，順序搜索到與其距離為n的匹配點(diǎn)。

（3）以這些匹配點(diǎn)為中心，生成候選塊與待修復(fù)塊做SSD計(jì)算。

（4）不斷重復(fù)上述步驟，直到搜索完匹配區(qū)域?yàn)橹埂?/p>

3.3 置信值更新的改進(jìn)

在Criminisi算法修改過(guò)程中，同等對(duì)待修補(bǔ)后的像素點(diǎn)和非破損區(qū)域的像素點(diǎn)，這與實(shí)際情況不相符，這樣可能會(huì)破壞圖像模板，對(duì)圖像的修復(fù)結(jié)果產(chǎn)生不利影響。為了解決該難題，先設(shè)定一顏色閾值th，該閾值根據(jù)圖像修復(fù)模板對(duì)應(yīng)的SSD的值確定，具體改進(jìn)方式為：

4 仿真實(shí)驗(yàn)

4.1 仿真環(huán)境

為了測(cè)試改進(jìn)Criminisi算法的圖像修復(fù)性能，在Intel酷睿i5 4570 CPU，RAM 4 GB，Windows XP的計(jì)算機(jī)上，采用VC++編程實(shí)現(xiàn)，為了使改進(jìn)Criminisi算法結(jié)果具有可比性，采用標(biāo)準(zhǔn)Criminisi算法對(duì)比算法的性能，仿真對(duì)象為：Girl、Bungee和Grass圖像[14]，原圖和待修復(fù)圖像具體如圖3和圖4所示。

圖3 原圖

圖4 待修復(fù)圖像

4.2 結(jié)果與分析

4.2.1 主觀評(píng)價(jià)結(jié)果對(duì)比

分別采用改進(jìn)Criminisi算法和Criminisi算法對(duì)圖3的圖像進(jìn)行修復(fù)，結(jié)果如圖5～7所示。

圖5 Girl修復(fù)效果對(duì)比

圖6 Bungee修復(fù)效果對(duì)比圖

圖7 Grass修復(fù)效果對(duì)比圖

從圖5～7可知，從標(biāo)記方框可以明顯看出，標(biāo)準(zhǔn)Criminisi算法修復(fù)后的圖像中出現(xiàn)了嚴(yán)重的結(jié)構(gòu)斷裂以及不連續(xù)現(xiàn)象，但是改進(jìn)Criminisi算法的視覺(jué)效果得到明顯改善，這主要由于改進(jìn)Criminisi算法在圖像修復(fù)過(guò)程中，對(duì)優(yōu)先權(quán)值進(jìn)行改進(jìn)，可以有效地保證結(jié)構(gòu)信息較強(qiáng)的待修復(fù)塊，并完善最優(yōu)匹配塊搜索策略以及置信值更新方式，提高了圖像修復(fù)后的視覺(jué)效果。

4.2.2 客觀評(píng)價(jià)結(jié)果對(duì)比

對(duì)圖像修復(fù)算法性能的評(píng)價(jià)，除了采用主觀評(píng)價(jià)外，通常還采用客觀評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行衡量。為了更進(jìn)一步評(píng)價(jià)圖像的修復(fù)質(zhì)量，采用峰值信噪比（Peak Signal to Noise Ratios，PSNR）和計(jì)算時(shí)間對(duì)圖像修復(fù)質(zhì)量進(jìn)行客觀評(píng)價(jià)，它們結(jié)果分別如圖8，9所示。對(duì)圖8，9進(jìn)行分析，可以得到如下結(jié)論：

（1）相對(duì)于Criminisi算法，改進(jìn)Criminisi算法的計(jì)算時(shí)間相對(duì)減少，計(jì)算復(fù)雜度較低，提高了圖像修復(fù)的效率，對(duì)比結(jié)果表明，改進(jìn)Criminisi算法更加適合于圖像的在線修復(fù)，應(yīng)用范圍更廣，實(shí)用價(jià)值更高。

（2）相對(duì)于Criminisi算法，改進(jìn)Criminisi算法修復(fù)后圖像的信噪比大，修復(fù)效果更佳，這說(shuō)明通過(guò)對(duì)Criminisi算法進(jìn)行改進(jìn)和完善，較好地克服了其不足，可以確保確修復(fù)后圖像的視覺(jué)效果，改進(jìn)Criminisi算法是一種性能優(yōu)異、效率高的圖像修復(fù)算法。

圖8 修復(fù)后圖像信噪比的對(duì)比

圖9 圖像修復(fù)時(shí)間的對(duì)比

5 結(jié)束語(yǔ)

針對(duì)Criminisi算法存在的缺陷，提出了一種改進(jìn)Criminisi的圖像修復(fù)算法，從優(yōu)先權(quán)計(jì)算、最優(yōu)匹配塊搜索策略以及置信值更新等方面進(jìn)行改進(jìn)和完善，并進(jìn)行了仿真對(duì)比實(shí)驗(yàn)。結(jié)果表明，改進(jìn)Criminisi算法不僅能有效確保修復(fù)后圖像的視覺(jué)效果，而且能有效地節(jié)約對(duì)應(yīng)的修復(fù)時(shí)間，是一種性能更為優(yōu)異的圖像修復(fù)算法。

[1]Minh N，Martin V.The contourlet transform：an efficient directional multiresolution image representation[J].IEEE Transactions on Image Processing，2005，14（12）：2091-2106.

[2]林云莉，趙俊紅，朱學(xué)峰，等.改進(jìn)的紋理合成圖像修復(fù)算法[J].計(jì)算機(jī)應(yīng)用與軟件，2010，27（10）：11-12.

[3]屈磊，韋穗，梁棟，等.快速自適應(yīng)模板圖像修復(fù)算法[J].中國(guó)圖象圖形學(xué)報(bào)，2008，13（1）：24-28.

[4]孟春芝，何凱，焦青蘭.自適應(yīng)樣本塊大小的圖像修復(fù)方法[J].中國(guó)圖象圖形學(xué)報(bào)，2012，17（3）：337-341.

[5]Anamandra S H，Chandrasekaran V.Exemplar-based color image inpainting using a simple and effective gradient function[C]//Sargolzaei S.International Conference on Image Processing and Computer Vision，2010：140-145.

[6]Zhou Y T，Li L，Xia K W.Research on weighted priority of exemplar-based image inpainting[J].Journal of Electronics，2012，29（1）：166-170.

[7]代仕梅，張紅英，曾超.一種基于樣例的快速圖像修復(fù)算法[J].圖形、圖像與多媒體，2010，29（22）：34-39.

[8]付紹春，樓順天.基于區(qū)域紋理合成的圖像修補(bǔ)算法[J].電子與信息學(xué)報(bào)，2009，31（6）：1319-1322.

[9]林勝華，汪繼文，沈玉峰，等.利用鄰域相似度的圖像修復(fù)[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（7）：190-191.

[10]吳曉軍，李功清.基于樣本和線性結(jié)構(gòu)信息的大范圍圖像修復(fù)算法[J].電子學(xué)報(bào)，2012，40（8）：1509-1514.

[11]張偉彬.基于修復(fù)順序的圖像修復(fù)算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（22）：195-196.

[12]陳卿，王慧琴，吳萌.基于紋理特征的自適應(yīng)圖像修復(fù)算法[J].計(jì)算機(jī)應(yīng)用，2011，6（6）：1572-1574.

[13]Kwok T H，Sheung H，Charlie C.Fast query for exemplar-basedimagecompletion[J].IEEE Transactionson Image Processing，2010，19（12）：3106-3115.

[14]任澍，唐向宏，康佳倫.利用紋理和邊緣特征的Criminisi改進(jìn)算法[J].中國(guó)圖象圖形學(xué)報(bào)，2012，17（9）：1086-1091.

[15]Xu Z B，Sun J.Image inpainting by patch propagation using patch sparsity[J].IEEE Transactions on Image Processing，2010，19（5）：1153-1165.

LI Aiju,NIU Wenliang

Beijing Union University,Beijing 102200,China

A novel image inpainting method based on improved Criminisi algorithm to solve the defects of Criminisi algorithm which hardly yields unfavorable results and costs much inpainting time is proposed.The priority levels of the blocks are obtained and the optimal inpainted block is selected,and then the optimum matching block in the image is found by improving search method,and the confidence value is updated to obtain good inpainting results.The simulation experiments are carried out to test the performance.The experimental results show that compared with Criminisi algorithm,the proposed algorithm is effective in both guaranteeing the quality of repaired images and saving much more repairing time.

image inpainting;Criminisi algorithm;priority levels;image texture

針對(duì)Criminisi算法難以獲得理想的修復(fù)效果，且存在修復(fù)時(shí)間過(guò)長(zhǎng)等缺陷，提出一種改進(jìn)Criminisi算法的圖像修復(fù)算法。改進(jìn)優(yōu)先權(quán)計(jì)算方式找到最優(yōu)待修復(fù)塊，完善最優(yōu)匹配塊搜索策略，找到最優(yōu)匹配塊，采用新的置信值更新方式以獲得更為理想修復(fù)效果，通過(guò)仿真實(shí)驗(yàn)測(cè)試算法性能，結(jié)果表明，相較于Criminisi算法，改進(jìn)Criminisi算法不僅獲得了較理想的圖像修復(fù)效果，而且大幅度減少了修復(fù)時(shí)間，提高了圖像修復(fù)的效果。

圖像修復(fù)；Criminisi算法；優(yōu)先級(jí)；圖像紋理

A

TP919

10.3778/j.issn.1002-8331.1401-0419

LI Aiju,NIU Wenliang.Image inpainting based on improved Criminisi algorithm.Computer Engineering and Applications,2014,50（18）：167-170.

北京高等學(xué)校青年英才計(jì)劃項(xiàng)目（No.YETP1766）。

李愛菊（1980—），女，講師，主要研究領(lǐng)域：高效計(jì)算、大數(shù)據(jù)、并行處理、圖形圖像等；鈕文良（1958—），男，教授，主要研究領(lǐng)域：網(wǎng)絡(luò)通信、無(wú)線傳感網(wǎng)等。E-mail：50310646@qq.com

2014-01-26

2014-03-21

1002-8331（2014）18-0167-04