鄭玉婷，吳 謹

?

基于蟻群算法的Criminisi圖像修復

鄭玉婷，吳 謹

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

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

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

0 引言

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

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

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

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

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

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

1 基于蟻群算法的Criminisi修復

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

1.1 優(yōu)先權的計算

優(yōu)先權是Criminisi經典圖像修復算法第1步，處于核心地位，決定了修補的先后次序。假設修補前的圖像如圖1所示。

圖1 Criminisi經典算法

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

點優(yōu)先權Priority()計算如式(1)所示。

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

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

本文引用文獻[7]重新定義數據項()，如下式：

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

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

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

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

式中：￠為待修復目標塊；為完好區(qū)域內樣本塊；d(￠,)為兩個像素塊對應像素點灰度差值的平方和，SSD匹配原則表示為當目標塊￠與樣本塊的像素點灰度差值平方和距離最小時，樣本塊便替代目標塊￠，即為最佳匹配模塊。

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

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

蟻群算法數學模型如下：

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

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

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

(＋)＝×D(7)

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

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

式中：是一個常數；L是螞蟻在本次路徑中所爬行距離。

基于上述原則及數學模型，蟻群算法的步驟如下：

Step1：＝0（為迭代步數或搜索次數），和D初始化；將個螞蟻置于條路徑的起點；

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

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

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

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

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

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

1.3 置信度的更新

最高優(yōu)先權的目標塊修補完成后，塊中原來的邊界變?yōu)橐阎c，區(qū)域內中的點變?yōu)橐阎c或者邊界點，這時需要重新計算已知點的置信度，以及邊界點的優(yōu)先權。置信度更新公式如下：

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

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

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

Step1：標記待修復區(qū)域；

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

Step3：計算優(yōu)先權；

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

Step5：更新置信度；

Step6：重復Step2，直到待修復區(qū)域為空集，即修復完成。

2 仿真實驗結果分析

本文實驗仿真平臺是MATLAB7.0和VC＋＋6.0。并采用峰值信噪比PSNR評價圖像的修復質量，其函數表達式如下：

式中：MSE為原圖像與處理圖像之間均方誤差，PSNR值越大，代表失真越少；2－1為信號最大值；為每個采樣值的比特數。

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

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

圖2 移除圖像修復結果

Fig.2 Image inpainting of the little girl removal

圖3 行人移除圖像修復結果

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

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

由表1看出，本文改進算法PSNR數值最大，耗時最短，即修復效果最好。文獻[8]改進算法之所以PSNR數值較大是因為該算法重新定義最佳模板匹配原則，有利于填充模塊與原模塊保持一致性。本文改進算法之所以PSNR最大、耗時最短是因為蟻群算法采用釋放信息素尋找最佳路徑方式使搜索最佳匹配模板不易陷入局部最優(yōu)，優(yōu)先選擇最佳模板，即修復質量高；引入文獻[7]重新定義數據項，使優(yōu)先權計算同時從梯度和等照度線兩個方向同時進行，即耗時短。

綜上，針對目標移除這一類圖像修復，本文引入的蟻群算法魯棒性較強具有一定實用性。

3 結論

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

[1] 林云莉, 趙俊紅, 朱學峰, 等. 基于圖像分解的圖像修復技術[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] 魏琳, 陳秀宏. 基于紋理方向的圖像修復算法[J]. 計算機應用, 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] 胡文瑾, 王維蘭, 劉仲民. 一種基于樣本塊的快速圖像修復算法[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]. 計算機工程與應用, 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] 陳龍, 熊輝, 汪繼文. 基于樣本塊的圖像修復方法的改進[J]. 計算機應用, 2011(6):47-50.

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

[9] 李尊, 吳謹, 劉勁, 等. 數學形態(tài)學在Criminisi圖像修復算法中的應用[J]. 紅外技術, 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-），女，湖北孝感人，碩士，主要從事圖像修復方面的研究。E-mail：525514824@qq.com。

國家自然科學基金青年項目（61502358)；湖北省自然科學基金（2013CFB333）。