鄭玉婷，吳 謹(jǐn)

?

基于蟻群算法的Criminisi圖像修復(fù)

鄭玉婷，吳 謹(jǐn)

（武漢科技大學(xué)信息科學(xué)與工程學(xué)院，湖北 武漢 430081)

提出了一種基于蟻群算法的Criminisi圖像修復(fù)算法，將蟻群算法應(yīng)用到Criminisi圖像修復(fù)算法的最佳匹配模板搜索中。首先計(jì)算待修復(fù)區(qū)域優(yōu)先權(quán)；然后蟻群尋找搜索路徑中留下的信息素，沿著信息素最多的路徑尋找到最佳匹配模板；最后更新置信度，直到修復(fù)結(jié)束。實(shí)驗(yàn)結(jié)果表明，修復(fù)后的圖像PSNR較高不易陷入局部最優(yōu)，能較快速地搜索到最佳匹配模板。

蟻群算法；Criminisi算法；最佳匹配模板

0 引言

圖像修復(fù)是利用圖像中已知的有效信息，按照一定規(guī)則對破損的圖像進(jìn)行信息填充，得到連續(xù)、完整、自然的圖像視覺效果。主要應(yīng)用于文物保護(hù)、老照片的修復(fù)、圖像中文本信息以及障礙物的去除、影視特技制作等領(lǐng)域。

目前圖像修復(fù)算法主要分為兩大類：基于偏微分方程的圖像修復(fù)法[1]和基于紋理的圖像修復(fù)法[2]。

BSCB模型算法[3]、TV模型算法[4]是對圖像中的像素點(diǎn)進(jìn)行修復(fù)，屬于偏微分方程的圖像修復(fù)法，主要適用于小區(qū)域信息缺失的圖像修復(fù)。

Criminisi經(jīng)典算法[5]是對圖像中的像素塊進(jìn)行修復(fù)，屬于基于紋理的圖像修復(fù)法，主要適用于大區(qū)域信息缺失的圖像修復(fù)。

Criminisi經(jīng)典算法是Criminisi等于2004年提出的一種基于樣本塊的修復(fù)方法，該算法采用SSD搜索最優(yōu)匹配塊。其修復(fù)過程由待修復(fù)區(qū)域標(biāo)記、優(yōu)先權(quán)計(jì)算、最佳匹配模板搜索與填充、更新置信度組成。該算法的改進(jìn)主要是針對優(yōu)先權(quán)、最佳匹配模板搜索進(jìn)行的。文獻(xiàn)[6]重新定義了數(shù)據(jù)項(xiàng)，引入新的度量函數(shù)以更新置信度，使優(yōu)先權(quán)的計(jì)算更加準(zhǔn)確；文獻(xiàn)[7]將P-M方程引入數(shù)據(jù)項(xiàng)進(jìn)行梯度和等照度線兩個(gè)方向同時(shí)修補(bǔ)，以提高修復(fù)效率；文獻(xiàn)[8]重新定義了模板匹配準(zhǔn)則，以提高匹配準(zhǔn)確率；文獻(xiàn)[9]引入數(shù)學(xué)形態(tài)學(xué)對待修復(fù)圖像進(jìn)行預(yù)處理，進(jìn)而提高圖像修復(fù)質(zhì)量。

針對Criminisi經(jīng)典算法中最佳匹配塊搜索易陷入局部最優(yōu)的問題，引入蟻群算法[10]，減少誤差累積傳遞，以提高修復(fù)質(zhì)量；同時(shí)引用文獻(xiàn)[7]重新定義數(shù)據(jù)項(xiàng)，以提高修復(fù)效率。

1 基于蟻群算法的Criminisi修復(fù)

基于蟻群算法的Criminisi圖像修復(fù)方法包括優(yōu)先權(quán)計(jì)算、蟻群算法搜索最佳匹配模板、更新置信度。

1.1 優(yōu)先權(quán)的計(jì)算

優(yōu)先權(quán)是Criminisi經(jīng)典圖像修復(fù)算法第1步，處于核心地位，決定了修補(bǔ)的先后次序。假設(shè)修補(bǔ)前的圖像如圖1所示。

圖1 Criminisi經(jīng)典算法

圖1中，為完好區(qū)域，即未標(biāo)記的區(qū)域；為破損區(qū)域，也稱待修復(fù)區(qū)域；d為待修復(fù)區(qū)域的域邊界，在填充過程中，邊界d會(huì)向待修補(bǔ)目標(biāo)區(qū)域不斷收縮，又稱填充邊緣；點(diǎn)為目標(biāo)像素點(diǎn)；?I^為點(diǎn)的等照度線方向；n為點(diǎn)的法向量；為以點(diǎn)為中心確定的矩形塊。

點(diǎn)優(yōu)先權(quán)Priority()計(jì)算如式(1)所示。

Priority()＝()*() (1)

式中：||為面積；()為置信度，表示的是中完好信息所占的比重，()越高，單位面積內(nèi)已知像素就越多，能為最佳匹配塊的選擇提供更多可靠信息，即越早被修復(fù)，()保證了圖像的修復(fù)由待修復(fù)區(qū)域外向內(nèi)進(jìn)行；()為數(shù)據(jù)項(xiàng)，表示?I^與法向量n的模。夾角越小，()的值就越大，即線性結(jié)構(gòu)強(qiáng)度高的部分優(yōu)先得到填充；在灰度圖中通常取255。

本文引用文獻(xiàn)[7]重新定義數(shù)據(jù)項(xiàng)()，如下式：

()＝|(|?|)|＋|(|?|)|(4)

式中：為等照度線的切線方向；為等照度線的法線方向；(|?|)是邊緣停止函數(shù)。重新定義的數(shù)據(jù)項(xiàng)使優(yōu)先權(quán)計(jì)算從梯度和等照度線兩個(gè)方向同時(shí)進(jìn)行，以提高修復(fù)效率。該式采用P-M方程約束的填充算法，將平滑去噪P-M方程按梯度和等照度線兩個(gè)方向分解進(jìn)而獲得可靠的填充順序和信息進(jìn)化方向。

1.2 最佳匹配模板的搜索與填充

通過優(yōu)先權(quán)的計(jì)算，確定最大優(yōu)先權(quán)待修補(bǔ)塊后，在完好區(qū)域進(jìn)行最佳匹配模板的搜索與填充，匹配原則為：

式中：￠為待修復(fù)目標(biāo)塊；為完好區(qū)域內(nèi)樣本塊；d(￠,)為兩個(gè)像素塊對應(yīng)像素點(diǎn)灰度差值的平方和，SSD匹配原則表示為當(dāng)目標(biāo)塊￠與樣本塊的像素點(diǎn)灰度差值平方和距離最小時(shí)，樣本塊便替代目標(biāo)塊￠，即為最佳匹配模塊。

本文將采用蟻群算法進(jìn)行最佳匹配模板的搜索。蟻群算法是一種源于生物世界的仿生類進(jìn)化算法。它由Marco Dorigo于1992年提出，靈感來源于蟻群在尋找食物過程中釋放信息素發(fā)現(xiàn)最佳路徑的行為。

蟻群算法優(yōu)化過程的本質(zhì)基于3個(gè)原則：①信息素越大的路徑，被選擇的概率越大；②信息素會(huì)隨著螞蟻的經(jīng)過而增多，同時(shí)也會(huì)隨著時(shí)間的推移而減小，即信息素的更新；③螞蟻之間是通過信息素來互相通信、協(xié)同工作的，這種方式使得蟻群算法具有很強(qiáng)的發(fā)現(xiàn)路徑能力，即協(xié)調(diào)性。

蟻群算法數(shù)學(xué)模型如下：

設(shè)有個(gè)樣本塊，只螞蟻，d(,＝1, 2, …,)表示節(jié)點(diǎn)和間的距離，()為時(shí)刻塊和之間的信息素濃度，設(shè)初始時(shí)刻各條路徑上的信息素濃度均為（常數(shù)）。則在時(shí)刻螞蟻（1≤≤）在節(jié)點(diǎn)選擇節(jié)點(diǎn)的轉(zhuǎn)移概率為：

式中：U為螞蟻下一步允許選擇的塊；為信息啟發(fā)式因子，反映了螞蟻在路徑d所積累的信息素在蟻群運(yùn)動(dòng)時(shí)所起的作用，其值越大，蟻群之間協(xié)作性越強(qiáng)；為期望啟發(fā)式因子，反映了啟發(fā)信息對螞蟻選擇轉(zhuǎn)移方向時(shí)的影響權(quán)重，一般取＝1/d。

經(jīng)過個(gè)時(shí)刻，蟻群完成一次循環(huán)。這時(shí)蟻群所經(jīng)過的每條路徑上的信息素需要進(jìn)行一次更新：

(＋)＝×D(7)

式中：為信息素的揮發(fā)程度；D為整個(gè)蟻群在此次路徑d上信息素的增量：

D為螞蟻留在路徑d上的信息素：

式中：是一個(gè)常數(shù)；L是螞蟻在本次路徑中所爬行距離。

基于上述原則及數(shù)學(xué)模型，蟻群算法的步驟如下：

Step1：＝0（為迭代步數(shù)或搜索次數(shù)），和D初始化；將個(gè)螞蟻置于條路徑的起點(diǎn)；

Step2：將蟻群的初始出發(fā)點(diǎn)置于當(dāng)前解集中；對每個(gè)螞蟻(＝1,2,…,)計(jì)算概率P()，將螞蟻移到下一個(gè)節(jié)點(diǎn)，將置于當(dāng)前解集；

Step3：計(jì)算各螞蟻的路徑長度L（＝1,2,…,）；記錄當(dāng)前最優(yōu)解；

Step4：按式(7)更新最佳路徑，修改軌跡強(qiáng)度；

Step5：對各邊弧(,)，置D＝0，＝＋1；

Step6：若＜預(yù)定的迭代次數(shù)且無退化行為（即找到的都是相同解或進(jìn)化趨勢相差明顯），則重復(fù)Step2；

Step7：輸出當(dāng)前最優(yōu)解。

1.3 置信度的更新

最高優(yōu)先權(quán)的目標(biāo)塊修補(bǔ)完成后，塊中原來的邊界變?yōu)橐阎c(diǎn)，區(qū)域內(nèi)中的點(diǎn)變?yōu)橐阎c(diǎn)或者邊界點(diǎn)，這時(shí)需要重新計(jì)算已知點(diǎn)的置信度，以及邊界點(diǎn)的優(yōu)先權(quán)。置信度更新公式如下：

(￠)＝(),"?￠?(10)

通過不斷重復(fù)計(jì)算優(yōu)先權(quán)、搜索與填充最佳匹配模板、更新置信度，直至待修復(fù)區(qū)域為空集，則修復(fù)完成。

綜上所述，基于蟻群算法的Criminisi圖像修復(fù)流程如下：

Step1：標(biāo)記待修復(fù)區(qū)域；

Step2：待修復(fù)區(qū)域是否為空集，若是空集則輸出圖像；若不是空集進(jìn)行下一步；

Step3：計(jì)算優(yōu)先權(quán)；

Step4：基于蟻群算法的最佳匹配模板搜索填充（即蟻群在運(yùn)動(dòng)路徑上留下信息素，信息素最大的路徑為匹配模塊）；

Step5：更新置信度；

Step6：重復(fù)Step2，直到待修復(fù)區(qū)域?yàn)榭占?，即修?fù)完成。

2 仿真實(shí)驗(yàn)結(jié)果分析

本文實(shí)驗(yàn)仿真平臺(tái)是MATLAB7.0和VC＋＋6.0。并采用峰值信噪比PSNR評價(jià)圖像的修復(fù)質(zhì)量，其函數(shù)表達(dá)式如下：

式中：MSE為原圖像與處理圖像之間均方誤差，PSNR值越大，代表失真越少；2－1為信號(hào)最大值；為每個(gè)采樣值的比特?cái)?shù)。

圖像修復(fù)主要針對冗余目標(biāo)移除修復(fù)，本文將Criminisi經(jīng)典算法、文獻(xiàn)[6]、[8]算法及本文算法對兩百幅圖像進(jìn)行比較，選取圖2、圖3，為了移除小女孩和沙灘上的行人，得到所需的前景圖像。表1為4種算法移除小女孩圖像和行人圖像的PSNR與耗時(shí)比較。

圖2(c)、圖2(d)的修復(fù)結(jié)果中均有錯(cuò)誤信息的累積，無法滿足視覺要求。圖2(c)中出現(xiàn)了大面積錯(cuò)誤的結(jié)構(gòu)紋理修復(fù)信息，將背景山間的信息填充到目標(biāo)移除區(qū)域；圖2(d)處理好了臺(tái)階的邊緣結(jié)構(gòu)信息，但錯(cuò)誤的修復(fù)無法與周圍信息相協(xié)調(diào)；圖2(e)、圖2(f)修復(fù)效果最好，一定程度上區(qū)分了邊緣結(jié)構(gòu)信息，且錯(cuò)誤信息累積較少，圖像修復(fù)質(zhì)量較好。

圖2 移除圖像修復(fù)結(jié)果

Fig.2 Image inpainting of the little girl removal

圖3 行人移除圖像修復(fù)結(jié)果

表1 種算法移除小女孩和行人圖像PSNR與耗時(shí)

針對圖3仿真結(jié)果：(c)圖將樹葉部分信息填充到目標(biāo)移除區(qū)域，得不到理想修復(fù)結(jié)果；(d)圖仍然是將樹葉部分信息填充到目標(biāo)移除區(qū)域，錯(cuò)誤結(jié)構(gòu)紋理修復(fù)信息相比(c)圖較少，但仍然無法滿足視覺需求；(e)、(f)邊緣結(jié)構(gòu)信息處理較好，基本滿足人的視覺需求。

由表1看出，本文改進(jìn)算法PSNR數(shù)值最大，耗時(shí)最短，即修復(fù)效果最好。文獻(xiàn)[8]改進(jìn)算法之所以PSNR數(shù)值較大是因?yàn)樵撍惴ㄖ匦露x最佳模板匹配原則，有利于填充模塊與原模塊保持一致性。本文改進(jìn)算法之所以PSNR最大、耗時(shí)最短是因?yàn)橄伻核惴ú捎冕尫判畔⑺貙ふ易罴崖窂椒绞绞顾阉髯罴哑ヅ淠０宀灰紫萑刖植孔顑?yōu)，優(yōu)先選擇最佳模板，即修復(fù)質(zhì)量高；引入文獻(xiàn)[7]重新定義數(shù)據(jù)項(xiàng)，使優(yōu)先權(quán)計(jì)算同時(shí)從梯度和等照度線兩個(gè)方向同時(shí)進(jìn)行，即耗時(shí)短。

綜上，針對目標(biāo)移除這一類圖像修復(fù)，本文引入的蟻群算法魯棒性較強(qiáng)具有一定實(shí)用性。

3 結(jié)論

本文引入蟻群算法對Criminsi經(jīng)典算法中最佳匹配模板的全局搜索方式進(jìn)行優(yōu)化。優(yōu)化后的算法通過個(gè)體間的信息交流與相互協(xié)作不易陷入局部最優(yōu)，易搜索到最佳匹配模板，進(jìn)而減少錯(cuò)誤信息積累。實(shí)驗(yàn)結(jié)果表明，修復(fù)后的圖像在一定程度上質(zhì)量、效率有所提高，相比Criminisi經(jīng)典算法更滿足視覺需求，具有實(shí)用價(jià)值。

[1] 林云莉, 趙俊紅, 朱學(xué)峰, 等. 基于圖像分解的圖像修復(fù)技術(shù)[J]. 計(jì)算機(jī)工程, 2010, 36(10): 187-192.

LIN Yunli, ZHAO Junhong, ZHU Xuefeng, et al. Image inpainting technology based on image decomposition[J]., 2010, 36(10): 187-192.

[2] 魏琳, 陳秀宏. 基于紋理方向的圖像修復(fù)算法[J]. 計(jì)算機(jī)應(yīng)用, 2008, 28(9): 2063-2069.

WEI Lin, CHEN Xiuhong. Algorithm of image inpainting based on texture orientation[J]., 2008, 28(9): 128-132.

[3] BERTALMIO M, SAPIRO G, CASELLES V, et al. Image inpainting[C]//, New Orleans, Louisiana, USA, 2000: 417-424.

[4] CHAN T, SHEN J F. Mathematical models for local nontextureinpain- ting[J]., 2001, 62(3): 1019-1043.

[5] CRIMINISI A, PEREZ P, TOYAMA K. Region filling and object removal by exemplar-based inpainting[J]., 2004, 13(9): 1200-1212.

[6] 胡文瑾, 王維蘭, 劉仲民. 一種基于樣本塊的快速圖像修復(fù)算法[J]. 數(shù)據(jù)采集與處理, 2011, 26(6): 626-630.

HU Wenjin, WANG Weilan, LIU Zhongmin. Improcedexemplar-based method for image inpainting[J]., 2011, 26(6): 626-630.

[7] 張申華, 祝軒, 雷文娟, 等. 一種改進(jìn)的基于樣例的目標(biāo)物體移除方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2011, 47(7): 180-182.

ZHANG Shenhua, ZHU Xuan, LEI Wenjuan, et al. An improved exemplar-based method for objet removal[J]., 2011, 47(7): 180-182.

[8] 陳龍, 熊輝, 汪繼文. 基于樣本塊的圖像修復(fù)方法的改進(jìn)[J]. 計(jì)算機(jī)應(yīng)用, 2011(6):47-50.

CHEN Long, XIONG Hui, WANG Jiwen. Improvement of image inpainting based on sample patch[J]., 2011(6): 47-50.

[9] 李尊, 吳謹(jǐn), 劉勁, 等. 數(shù)學(xué)形態(tài)學(xué)在Criminisi圖像修復(fù)算法中的應(yīng)用[J]. 紅外技術(shù), 2015, 37(7):574-578.

LI Zun, WU Jin, LIU Jing, et al. The application of mathematical morphology in the Criminisi algorithm of image inpainting[J]., 2015, 37(7): 574-578.

[10] Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem[J]., 1997, 1(1): 53-66.

The Criminisi Algorithm Based on Ant Colony Optimization for Image Inpainting

ZHENG Yuting，WU Jin

(,,438001,)

An Criminisi image inpaiting algorithm based on ant colony algorithm is proposed, which applies Ant colony algorithm to search the best matching template in Criminisi image inpaiting algorithm. Firstly, the priority area to be inpainted is calculated. Then, ant colony finds the pheromoneleft in searching path, and follows the path with most pheromones to find the best matching template. Finally, the confidence is updated until the end of inpaiting. Experiments show that the PSNR value of the image after inpaiting is higher and local optimum is avoided. The method can more quickly search for the best matching template.

Ant colony optimization，Criminisi algorithm，the best template

TP391.41

A

1001-8891(2017)03-0221-05

2016-03-30；

2016-06-13.

鄭玉婷（1992-），女，湖北孝感人，碩士，主要從事圖像修復(fù)方面的研究。E-mail：525514824@qq.com。

國家自然科學(xué)基金青年項(xiàng)目（61502358)；湖北省自然科學(xué)基金（2013CFB333）。