吳長(zhǎng)勤，王亞軍，王傳安

安徽科技學(xué)院數(shù)理與信息工程學(xué)院，安徽 鳳陽(yáng) 233100

結(jié)合顏色向量角和灰度熵的圖像修復(fù)

吳長(zhǎng)勤，王亞軍，王傳安

安徽科技學(xué)院數(shù)理與信息工程學(xué)院，安徽 鳳陽(yáng) 233100

針對(duì)現(xiàn)有圖像修復(fù)算法效率低下的問(wèn)題，提出一種結(jié)合顏色向量角和灰度熵的圖像修復(fù)改進(jìn)算法．根據(jù)顏色向量角能夠衡量圖像中不同顏色之間的差異特性，算法先構(gòu)造邊緣項(xiàng)來(lái)代替Criminisi算法中的數(shù)據(jù)項(xiàng)，并改進(jìn)優(yōu)先級(jí)計(jì)算方式；然后根據(jù)圖像局部灰度均值的一維信息熵來(lái)度量圖像中待修復(fù)塊周圍圖像，進(jìn)而采用局部平均灰度熵確定搜索區(qū)域的大小，以減少搜索最佳匹配塊的搜索時(shí)間．實(shí)驗(yàn)結(jié)果表明，與Criminisi算法相比無(wú)論從速度上還是修復(fù)的質(zhì)量上文中所提算法都占有優(yōu)勢(shì)．

圖像修復(fù)；顏色向量角；灰度熵；Criminisi算法

0 引言

數(shù)字圖像修復(fù)是圖像處理領(lǐng)域的一個(gè)分支，也是目前計(jì)算機(jī)視覺(jué)方面的研究熱點(diǎn)之一．?dāng)?shù)字圖像修復(fù)的本質(zhì)是利用其周圍的有用信息，按照一定的規(guī)則對(duì)圖像受損區(qū)域進(jìn)行填充，使修復(fù)后的圖像可以達(dá)到或接近人們所要求的視覺(jué)效果［1］．根據(jù)待修復(fù)區(qū)域的大小，圖像修復(fù)方法可分為兩類：一類是基于變分和偏微分方程的圖像修復(fù)［2－4］，其基本思想是根據(jù)信息擴(kuò)散原理來(lái)完成圖像受損區(qū)域的修復(fù)，當(dāng)圖像受損區(qū)域較小時(shí)，修復(fù)效果很好，幾乎沒(méi)有任何痕跡，但當(dāng)圖像受損區(qū)域較大時(shí)，修復(fù)時(shí)會(huì)出現(xiàn)模糊效應(yīng)；另一類是基于紋理的圖像修復(fù)，該類算法幾乎不受圖像受損區(qū)域大小的影響，能取得較好的修復(fù)效果，其逐漸成為圖像修復(fù)領(lǐng)域的主流算法，吸引眾多國(guó)內(nèi)外學(xué)者進(jìn)行研究［5－7］．

1 Criminisi算法思想

先介紹算法中用到的幾個(gè)變量，I表示需要修復(fù)的圖像，Ω為受損區(qū)域，即待修復(fù)區(qū)域，Φ為未受損區(qū)域，?Ω為區(qū)域邊界，p為邊界?Ω上優(yōu)先級(jí)最高的像素點(diǎn)，如圖1所示．

Criminisi算法提出采用優(yōu)先級(jí)進(jìn)行修復(fù)的思路，并以每次匹配時(shí)的最優(yōu)作為全局最優(yōu)，其修復(fù)步驟可概括如下：

a.首先確定待修復(fù)區(qū)域，并標(biāo)記出其邊界?Ω，若?Ω為空，則退出．

圖1 Criminisi算法變量示意圖Fig.1 The related variables in Criminisi algorithm

b.計(jì)算修復(fù)優(yōu)先級(jí)：選取邊界?Ω上的任意一點(diǎn)p，計(jì)算其優(yōu)先級(jí)P（p），并以p為中心，確定一個(gè)矩形塊ψp.P（p）計(jì)算公式為：

式（1）中，C（p）為置信項(xiàng)，D（p）為數(shù)據(jù)項(xiàng)，定義分別如下：

等照度線即為灰度值相同的一條曲線，故該曲線方向的顏色變化值最?。?/p>

c.以優(yōu)先級(jí)最大的像素點(diǎn)p為中心形成待修復(fù)塊ψp，并在圖像未受損區(qū)域內(nèi)搜索最佳匹配塊ψq，即與ψp距離最小的模塊：

式（4）中d為感知距離，對(duì)于灰度圖是兩模塊對(duì)應(yīng)各點(diǎn)的灰度值平方差之和，而彩色圖像則是對(duì)應(yīng)各點(diǎn)的RGB值平方差之和．

d.復(fù)制最佳匹配塊ψq中相應(yīng)的像素點(diǎn)到ψp中．

e.更新ψp模塊中像素點(diǎn)的邊界和置信度等信息．根據(jù)置信度的定義，其更新方式如下：

2 改進(jìn)的算法

Criminisi算法屬于一種典型的貪心算法，它充分考慮了圖像本身的梯度和結(jié)構(gòu)等信息，其修復(fù)效果相比其他算法在速度和修復(fù)質(zhì)量上都有很大提升，屬于圖像修復(fù)領(lǐng)域中的里程碑，但也存在值得改進(jìn)的地方［8］．

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

Criminisi算法在優(yōu)先級(jí)計(jì)算中采用等照度線到達(dá)邊緣的強(qiáng)度來(lái)計(jì)算數(shù)據(jù)項(xiàng)D（p），以保證處在強(qiáng)邊緣的像素塊獲得更高的優(yōu)先級(jí)，而這種優(yōu)先級(jí)計(jì)算公式不僅計(jì)算量大，且不能保證準(zhǔn)確地反映圖像邊緣結(jié)構(gòu)信息，同時(shí)在修復(fù)過(guò)程中，置信項(xiàng)C（p）和數(shù)據(jù)項(xiàng)D（p）有可能出現(xiàn)一大一小兩個(gè)極端，從而導(dǎo)致優(yōu)先級(jí)極小，這不符合實(shí)際情況［9］．顏色向量角能夠檢測(cè)數(shù)字圖像邊緣的特性［10］，因此，提出采用構(gòu)造邊緣項(xiàng)來(lái)代替Criminisi算法中的數(shù)據(jù)項(xiàng)，從而能更準(zhǔn)確地反映圖像邊緣特性，同時(shí)提高修復(fù)效率．

先將待修復(fù)圖像向外擴(kuò)充一個(gè)像素，以保證后續(xù)能夠?qū)吘壪袼丶捌渌袼刈鐾瑯拥奶幚恚赗GB顏色空間中，以圖像中某一像素點(diǎn)為中心P0，選取其四周3×3鄰域范圍內(nèi)的8個(gè)像素點(diǎn)P1、P2，…、P7、P8，并計(jì)算P0與鄰域八像素點(diǎn)的顏色向量角正弦值：

根據(jù)式（6）可得到8個(gè)顏色向量角正弦值，然后其中最大的正弦值來(lái)表征像素間的色差：

對(duì)整個(gè)待修復(fù)圖像所有像素進(jìn)行上述計(jì)算后，將結(jié)果組合在一起，得到邊緣圖像IM：

式（8）中m，n表示待修復(fù)圖像大小為m×n．接下來(lái)，進(jìn)行優(yōu)先級(jí)計(jì)算：

式（9）中C（p）仍為置信項(xiàng)，而E（p）為邊緣項(xiàng)：

在改進(jìn)后的優(yōu)先級(jí)計(jì)算中，使用邊緣項(xiàng)取代了數(shù)據(jù)項(xiàng)，避免了原先計(jì)算中的等照度線和正交法向量等復(fù)雜運(yùn)算，且可以統(tǒng)一表征圖像的邊緣強(qiáng)弱．同時(shí)，改進(jìn)后的優(yōu)先級(jí)為兩項(xiàng)和的形式，以消除因置信項(xiàng)迅速衰減造成的優(yōu)先級(jí)的極小值問(wèn)題，從而避免誤差過(guò)度傳播．

2.2 基于灰度熵的匹配搜索

Criminisi算法采用全局搜索方式搜索最佳匹配模塊，該方式不僅十分耗時(shí)，且沒(méi)有考慮到圖像的局部自相似性．實(shí)際上，待修復(fù)圖像上某一位置的像素值與其周圍鄰域的像素值有密切的關(guān)系，對(duì)于圖像修復(fù)問(wèn)題而言，熵是一種圖像特征的統(tǒng)計(jì)形式，它可以反應(yīng)圖像中信息的多少［11－12］．

基于結(jié)構(gòu)紋理圖像的局部性和穩(wěn)定性原理，筆者對(duì)局部平均灰度的信息熵進(jìn)行統(tǒng)計(jì)，從中發(fā)現(xiàn)，在待修復(fù)圖像中像素值變化相對(duì)平緩的區(qū)域，如圖像中天空、河流等，其修復(fù)塊與鄰域塊之間的平均灰度值較為接近，所以局部平均灰度熵值較?。粗?，在越是復(fù)雜的圖像區(qū)域，其像素變化劇烈且無(wú)規(guī)則，局部平均灰度熵越大，因此可利用局部平均灰度熵確定搜索區(qū)域的大小．首先定義待修復(fù)像素點(diǎn)p的鄰域像素集合TS（P）：

式（11）中T（p）為像素點(diǎn)p的鄰域矩形塊，且要求該鄰域塊要盡可能大于待修復(fù)矩形塊的大?。?/p>

令Numi表示像素點(diǎn)p的鄰域矩形塊內(nèi)平均灰度值為i的樣本塊的個(gè)數(shù)，Pi表示平均灰度值為i的樣本塊所占比例：

則待修復(fù)塊鄰域矩形塊的局部平均灰度熵為：

在局部平均灰度熵大于給定熵閾值的待修復(fù)塊處，由于多種紋理交錯(cuò)產(chǎn)生圖像的邊緣結(jié)構(gòu)，需要較為細(xì)致的操作，選擇相對(duì)較大的搜索區(qū)域完成匹配模塊搜索操作；而在小于熵閾值的待修復(fù)塊處，其紋理基元與基元之間具有統(tǒng)計(jì)相似性和重復(fù)性，因此，圖像塊與塊之間的紋理具有統(tǒng)計(jì)相似性，選擇較小的搜索區(qū)域，以加快搜索速度，從而提高修復(fù)效率．

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

對(duì)Criminisi算法和文中提出的改進(jìn)算法的圖像修復(fù)效果進(jìn)行實(shí)驗(yàn)比較，實(shí)驗(yàn)用的PC配置為corei5四核處理器，內(nèi)存為4 G，安裝64位windows 7操作系統(tǒng)，算法編寫(xiě)語(yǔ)言為C＋＋及開(kāi)源庫(kù)OpenCV2．4．2．實(shí)驗(yàn)結(jié)果如圖2、圖3所示，圖2是利用本文算法和Criminisi算法修復(fù)破損圖像過(guò)程中得到的置信項(xiàng)、邊緣項(xiàng)以及優(yōu)先級(jí)曲線的對(duì)比圖，圖3為兩算法修復(fù)圖像效果的對(duì)比圖．

圖2 兩算法參數(shù)曲線對(duì)比圖Fig.2 Comparison of parameter curves of two algorithms

圖3 圖像修復(fù)對(duì)比Fig.3 Comparison of image restoration effects of two algorithms

從圖2可看出，本文算法修復(fù)過(guò)程中獲得的參數(shù)曲線不管是邊緣項(xiàng)還是置信項(xiàng)或數(shù)據(jù)項(xiàng)，不會(huì)隨著修復(fù)過(guò)程的累積而迅速下降，相比Criminisi算法取得較好的曲線效果.改進(jìn)優(yōu)先級(jí)計(jì)算方式所得的優(yōu)先級(jí)曲線相比Criminisi算法更穩(wěn)定，不會(huì)出現(xiàn)驟降情況.而圖3表明文中提出的修復(fù)方法修復(fù)后的圖像跟原始圖很接近，基本上修復(fù)了破損圖像部分，相比Criminisi算法取得了更好的修復(fù)效果.

為更直觀明了的驗(yàn)證文中所提算法的修復(fù)效果，實(shí)驗(yàn)采用客觀評(píng)價(jià)方法做為修復(fù)圖像質(zhì)量評(píng)估的客觀標(biāo)準(zhǔn)，表1展示了兩種修復(fù)算法在均方誤差（MSE）、峰值信噪比（PSNR）和算法執(zhí)行時(shí)間方面的客觀度量．

表1 兩種修復(fù)算法的客觀度量Table 1 The comparison results of other parameters of two algorithms

從表1可以看出，本文提出的算法相對(duì)Criminisi算法來(lái)說(shuō)均方誤差比較小，峰值信噪比更大，失真較小，修復(fù)效果更好，更接近原圖，且計(jì)算量大大減少．因此與Criminisi算法相比無(wú)論從速度上還是修復(fù)的質(zhì)量上文中所提算法都占有優(yōu)勢(shì)．

4 結(jié)語(yǔ)

本文簡(jiǎn)單介紹了經(jīng)典的Criminisi算法的基本思想，分析了該算法在修復(fù)過(guò)程中存在的不足．針對(duì)優(yōu)先級(jí)極小值問(wèn)題，使用邊緣項(xiàng)取代數(shù)據(jù)項(xiàng)，并優(yōu)先級(jí)改為兩項(xiàng)和的形式．Criminisi算法采用全局搜索方式搜索最佳匹配模塊，且沒(méi)有考慮到圖像的局部自相似性，導(dǎo)致執(zhí)行時(shí)十分耗時(shí)，針對(duì)此問(wèn)題，在達(dá)到與Criminisi算法相當(dāng)?shù)男迯?fù)質(zhì)量的前提下，提出了采用局部平均灰度熵確定搜索區(qū)域的大小，以減少搜索最佳匹配塊的搜索時(shí)間．

致謝

安徽科技學(xué)院計(jì)算中心對(duì)本文實(shí)驗(yàn)和測(cè)試等提供幫助和支持，葛華老師在研究過(guò)程中提供了指導(dǎo)和幫助，在此表示感謝！

［1］BERTALMIO M，SAPlRO G，CASELLES V，et al．Image inpainting［C］//Proceedings of the International Confer-ence on Computer Graphics and Interactive Techniques．New Orleans Louisiana USA，2000，1：417－424．

［2］CHAN T F，SHEN J．Mathematical models for local nontexture inpainting［J］．SIAM Journal on Applied Mathematics，2002，62（3）：1019－1043．

［3］ESEDOGLU S，SHEN J．Digital image inpainting by the Muxnford－Shah－Euler image model［J］．European Journal of Applied Mathematics，2002，13（4）：353－370．

［4］葉學(xué)義，王靖，趙知?jiǎng)?，等．魯棒的梯度?qū)動(dòng)圖像修復(fù)算法［J］．中國(guó)圖像圖形學(xué)報(bào)，2012，17（6）：630－635．

YE Xue-yi，WANG Jing，ZHAO Zhi－jin，et al．Robust gradient driving image inpainting method［J］.Journal of Image and Graphics，2012，17（6）：630－635．（in Chinese）

［5］EFROS A A，F(xiàn)REEMAN W T．Image quilting for texture synthesis and transfer［C］//Proeeedings of ACM TransactionsonGraPhics（SIGGRAPH01），USA：ACM，2001．341－346．

［6］朱曉臨，陳曉冬，朱園珠，等．基于顯著結(jié)構(gòu)重構(gòu)與紋理合成的圖像修復(fù)算法［J］．圖形學(xué)報(bào)，2014，35（3）：336－342．

ZHU Xiao－lin，CHEN Xiao－dong，ZHU Yuan－zhu，et al．An image restoration algorithm based on structure and texture synthesis with reconstruction of significant structure of images［J］．Journal of Graphics，2014，35（3）：336－342．（in Chinese）

［7］馬爽，談元鵬，許剛．塊關(guān)聯(lián)匹配與低秩矩陣超分辨融合的圖像修復(fù)［J］．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2015，27（2）：271－278．

MA Shuang，TAN Yuan－peng，XU Gang．Image completion based on fusion of patchassociatedmatching andlow－rank matrix super resolution［J］．Journal of Computer-AidedDesign＆ComputerGraphics，2015，27（2）：271－278．（in Chinese）

［8］趙勝．基于紋理合成的圖像修復(fù)算法研究［D］．成都：電子科技大學(xué)，2014．

ZHAO Sheng．The image restoration algorithm based on texture synthesis［D］．Chengdu：University of Electronic Science and Technology of China，2014．（in Chinese）

［9］陳曉冬，朱曉臨．基于改進(jìn)優(yōu)先級(jí)的加權(quán)匹配圖像修復(fù)算法［J］．合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，36（1）：113－118．

CHEN Xiao－dong，ZHU Xiao－lin．A weighted matching image restoration algorithm based on modified priority［J］．Journal of Hefei University of Technology：Natural Science，2013，36（1）：113－118．（in Chinese）

［10］葉春．?dāng)?shù)字圖像水印及修復(fù)算法研究［D］．桂林：廣西師范大學(xué)，2014．

YE Chun．Research on digital image water marking and repair algorithm［D］．Guilin：Guangxi Normal U-niversity，2014．（in Chinese）

［11］RIVERA M，OCEGUEDA O，MARROQUIN J L．Entropy－controlled quadratic markov measure field models for efficient image segmentation［J］．IEEE Transactions on Image Processing，2007，16（12）：3047－3057．

［12］張晴．基于樣本的數(shù)字圖像修復(fù)技術(shù)研究［D］．上海：華東理工大學(xué)，2012．

ZHANG Qing．Study on exemplar－based image inpainting technologies［D］．Shanghai：East China University of Science and Technology，2012．（in Chinese）

Image inpainting algorithm combining color vector angle with entropy of brightness

WU Chang－qin，WANG Ya－jun，WANG Chuan－an
College of Mathematical and Information，Anhui Science and Technology University，F(xiàn)engyang 233100，China

A new restoration algorithm combining color vector angle with entropy of brightness was proposed to improve low efficiency in image inpainting．First，we measured the different characteristics of colors in the images according to the color vector angle，and redefined the calculation priority on the basis of Criminisi algorithm．Then，we calculated the one－dimensional entropy of local average gray values around the inpainting area，and used the average gray entropy to determine the size of the search area，which could reduce the search time for the best matching block．The experimental results show that the proposed algorithm has better restoration and less time consuming than Criminisi algorithms．

image inpainting；color vector angle；entropy of brightness；Criminisi algorithm

TN911.73

A

10.3969/j.issn.1674-2869.2015.06.011

1674－2869（2015）06－0051－05

本文編輯：苗變

2015－4－20

安徽省教育廳自然科學(xué)基金（KJ2013Z048）項(xiàng)目

吳長(zhǎng)勤（1962－），男，安徽肥東人，副教授．研究方向：圖像處理技術(shù)．