李 尊，吳 謹(jǐn)，劉 勁，吳秋紅

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

1 引 言

圖像修復(fù)［1］主要是修復(fù)圖像中破損區(qū)域或者移除多余的目標(biāo)。其是計(jì)算機(jī)視覺的研究熱點(diǎn)，廣泛應(yīng)用于文物的修復(fù)，影視特技等方面。主要分為基于偏微分方程算法［2］和基于紋理合成算法［3］兩大類。

Criminisi圖像修復(fù)算法［4］是由Criminisi等人于2004年提出，是紋理合成圖像修復(fù)技術(shù)的代表。算法的思想是在完好區(qū)域進(jìn)行全局搜索，確定最佳匹配塊并填充到待修復(fù)區(qū)域，達(dá)到修復(fù)圖像的目的。此算法步驟由優(yōu)先權(quán)的計(jì)算、最佳模板的搜索與填充和更新置信度構(gòu)成。但在修復(fù)過程中，優(yōu)先權(quán)計(jì)算可信度不高，最佳匹配模板搜索精確度低等問題影響修復(fù)效果，不能滿足視覺需求。

自從Criminisi算法被提出，國內(nèi)外學(xué)者就針對其缺點(diǎn)進(jìn)行改進(jìn)。文獻(xiàn)［5］將優(yōu)先權(quán)中數(shù)據(jù)項(xiàng)和置信度轉(zhuǎn)換成加權(quán)和的形式，一定程度上提升了優(yōu)先權(quán)的可信度；文獻(xiàn)［6］引入曲率到優(yōu)先權(quán)，并將算式改成各項(xiàng)加權(quán)和，增強(qiáng)了圖像結(jié)構(gòu)的連續(xù)性；文獻(xiàn)［7］根據(jù)修復(fù)區(qū)域邊緣的復(fù)雜性，動態(tài)的選擇搜索區(qū)域，降低了時(shí)間成本，且一定程度上改善了修復(fù)質(zhì)量；文獻(xiàn)［8］采用區(qū)域分割的變尺寸樣本塊高效圖像修復(fù)算法，降低了時(shí)耗且改進(jìn)修復(fù)質(zhì)量。

本文針對Criminisi圖像修復(fù)算法中優(yōu)先權(quán)可信度不高，影響修復(fù)順序和采用窮盡方法搜索最佳匹配模板，具有隨機(jī)性大，效率低的缺點(diǎn)進(jìn)行改進(jìn)。引入正規(guī)化函數(shù)，提升優(yōu)先權(quán)計(jì)算的可信度；將螢火蟲算法（FA）引入最佳模板的搜索與填充中，保證修復(fù)質(zhì)量，提高效率。

2 螢火蟲算法

螢火蟲算法［9］是基于種群搜索的隨機(jī)優(yōu)化算法。實(shí)施簡單，并行處理能力強(qiáng)，魯棒性能強(qiáng)。此算法由Yang于2008年提出，核心思想基礎(chǔ)是螢火蟲發(fā)光的生物學(xué)原理。

對于螢火蟲發(fā)光生物學(xué)原理的數(shù)學(xué)化需要以下理想化原則：

（1）在目標(biāo)函數(shù)的尋優(yōu)過程中，螢火蟲之間的相互吸引只有亮度這個(gè)因素；

（2）吸引力只和亮度有關(guān)，與亮度成正比例關(guān)系；

（3）目標(biāo)函數(shù)決定螢火蟲的亮度；

（4）亮度和吸引力隨距離的增大而減小，與之成反比例關(guān)系。

基于上述原則，螢火蟲算法可以數(shù)學(xué)化為以下步驟：

步驟一：初始化螢火蟲群體，設(shè)置螢火蟲群體個(gè)體數(shù)為n，最大吸引力β0，光強(qiáng)吸收系數(shù)γ，步長因子α，其中α∈［0，1］。

步驟二：隨機(jī)設(shè)置螢火蟲個(gè)體的坐標(biāo)位置，計(jì)算各自的最大熒光亮度I0。其中I0的大小可由螢火蟲的目標(biāo)函數(shù)值確定。

步驟三：確定螢火蟲的相對亮度I和吸引力β，可由公式（1）、（2）得出。

其中：I0，β0取處為光源，γ為光強(qiáng)吸收系數(shù)，其設(shè)置的原因是能量會隨距離的增大或是介質(zhì)的存在而降低，所以設(shè)置此參數(shù)，符合實(shí)際客觀的要求，sij表示螢火蟲之間的距離。

步驟四：螢火蟲位置更新。螢火蟲算法實(shí)質(zhì)是逐漸靠近亮度最大個(gè)體，因此螢火蟲個(gè)體的位置會不斷更新。位置的更新可由公式（3）得出。

其中：xi、xj表示螢火蟲個(gè)體i，j的空間位置，rand為隨機(jī)因子，服從0～1的均勻分布。

步驟五：根據(jù)螢火蟲的新位置，重新計(jì)算螢火蟲個(gè)體的亮度。

步驟六：終止條件判斷。終止條件可設(shè)置為誤差精度條件或設(shè)置迭代次數(shù)上限，則輸出最優(yōu)解；否則，進(jìn)入下一次搜索。

本文采用標(biāo)準(zhǔn)Rosenbroke檢測函數(shù)對螢火蟲算法進(jìn)行測試，其函數(shù)表達(dá)式如式（4）所示。

其中：本文取值d＝1，應(yīng)用情景是二維，螢火蟲的種群個(gè)數(shù)為25只，α＝γ＝0.9。

本文利用螢火蟲算法尋找f（X）的最小值，由數(shù)學(xué)理論可知，f（X）在（1，1）時(shí)，可取的最小值0。螢火蟲算法搜索途徑如圖1、圖2所示。

圖1 螢火蟲搜索路徑1Fig.1 Fireflies search path 1

圖2 螢火蟲搜索路徑2Fig.2 Fireflies search path 2

圖1在坐標(biāo)（1.002 50，1.005 83）停止搜索，圖2是在（1.003 38，1.006 94）處。

從兩個(gè)圖可以看出，螢火蟲的最佳解搜索是從無序到有序，最后趨向最佳解的過程。螢火蟲算法將全局搜索和局部搜索自然結(jié)合在一起，在保證精度的前提下，提高了效率。

3 經(jīng)典Criminisi圖像修復(fù)算法

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

假設(shè)待修復(fù)圖像如圖3所示。其中φ表示的區(qū)域是完好區(qū)域；Ω表示的區(qū)域是破損區(qū)域；δΩ表示待修復(fù)區(qū)域的邊界。

圖3 符號說明圖Fig.3 Figure of Symbol

Criminisi算法優(yōu)先權(quán)共有C（p）和D（p）兩項(xiàng)所決定。其中C（p）為置信度，表示的是以P為中心的待修補(bǔ)塊ψP中原圖的像素所占的比重；D（p）為數(shù)據(jù)項(xiàng)，表示的是邊界ψP在P處的梯度法向量np與完好區(qū)域的邊緣梯度向量.I⊥p的乘積。

Criminisi算法提出的P點(diǎn)優(yōu)先權(quán)計(jì)算如式（5）所示，C（p）、D（p）如式（6）、（7）所示：

其中：α是歸一化算子，在灰度圖中我們?nèi)ˇ粒?55。

3.2 最佳匹配塊的搜索與填充

確定優(yōu)先權(quán)數(shù)值最大的待修補(bǔ)塊后，在完好區(qū)域搜索確定最佳匹配模板并填充。其匹配原則如式（8）所示：

為了實(shí)現(xiàn)工程進(jìn)度前緊后松的總體勻速管控，前期準(zhǔn)備階段編制進(jìn)度規(guī)劃綱要的同時(shí)，要制定進(jìn)度管理實(shí)施細(xì)則和考核辦法，從分包合同中提取1%的費(fèi)用作為工程施工過程中的獎(jiǎng)勵(lì)基金，每月末總包組織相關(guān)負(fù)責(zé)人對各合同標(biāo)段的進(jìn)度、質(zhì)量、安全、基礎(chǔ)4項(xiàng)指標(biāo)進(jìn)行嚴(yán)格考核打分，按照實(shí)施細(xì)則進(jìn)行考評，考評結(jié)束后進(jìn)行評比，評比結(jié)果通報(bào)，獎(jiǎng)罰按月兌現(xiàn)。對關(guān)鍵線路或次關(guān)鍵線上的節(jié)點(diǎn)重點(diǎn)關(guān)注跟蹤檢查，影響工期的主要節(jié)點(diǎn)制定獎(jiǎng)罰對等措施，未按期完成節(jié)點(diǎn)的項(xiàng)目部進(jìn)行重罰，使其被動控制工期，使工期總體受控。

式（8）表示待修補(bǔ)塊與完好區(qū)域中樣本塊的已知元素的顏色平方和最小時(shí)，即為最佳匹配塊。

3.3 更新置信度

通過最佳匹配塊的搜索與填充，使得待修補(bǔ)塊變成完好區(qū)域中的樣本塊，置信度也會相應(yīng)的更新，成為接下來修復(fù)工作的依據(jù)。

Criminisi算法通過不斷重復(fù)上述3個(gè)步驟，直至待修復(fù)區(qū)域被填充完畢，則修復(fù)完成。

4 FA－Criminisi快速圖像修復(fù)

本文在按照Criminisi圖像算法流程的前提下，對優(yōu)先權(quán)的確定和最佳模板的搜索方式進(jìn)行改進(jìn)。

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

隨著修補(bǔ)次數(shù)的增加，置信度C（p）中的原圖的信息會急劇減少，并且很快減為0。在這種情況下，本文從數(shù)學(xué)的角度，引入正規(guī)化函數(shù)平滑置信度函數(shù)。正規(guī)化函數(shù)所起到的作用是當(dāng)輸出正比于輸入時(shí)能夠很好地抵抗噪聲及外部的干擾。

因此得出的新置信度如式（9）所示：

新置信度的引入，保證其取值的范圍在ω～1之間，置信度的曲線被平滑了，且其曲線的形狀保留，通常選取ω＝0.7。

新優(yōu)先權(quán)能夠避免置信度為0時(shí)，隨機(jī)抽取修補(bǔ)塊進(jìn)行修復(fù)的現(xiàn)象。

4.2 最佳匹配模板的搜索方式改進(jìn)

經(jīng)典Criminsi圖像修復(fù)算法是全局搜索最佳匹配模板，耗時(shí)且準(zhǔn)確率不高，其原因是當(dāng)全局搜索出現(xiàn)最佳匹配模板不止一個(gè)時(shí)，系統(tǒng)會隨機(jī)選取最佳匹配模板進(jìn)行填充。本文將螢火蟲算法引入作為最佳匹配模板的搜索方式，能夠首先確定最佳匹配模板的重點(diǎn)區(qū)域，然后在重點(diǎn)區(qū)域進(jìn)行搜索，提高效率，魯棒性強(qiáng)。

因此本文將模板匹配原則即公式（8）作為螢火蟲算法的目標(biāo)函數(shù)，如式（11）所示。

式（11）從數(shù)學(xué)角度可以看作為SSD原則，即差方和。

最佳模板的匹配與填充過程就改進(jìn)為采用螢火蟲算法的方式尋找灰度差方和值最小的模板。

綜上即為本文的FA－Criminisi算法的核心思想。

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

本文實(shí)驗(yàn)仿真平臺是MATLAB7.0和VC＋＋6.0，且本文用峰值信噪比PSNR客觀評價(jià)圖像的修復(fù)質(zhì)量。

圖像修復(fù)主要是針對破損圖像修復(fù)或是冗余目標(biāo)的移除。因此本文選用這兩大類圖像進(jìn)行仿真實(shí)驗(yàn)。

圖4 垃圾桶移除圖像修復(fù)結(jié)果Fig.4 Image inpainting of trash removal

圖5 荷花信息缺失圖像修復(fù)結(jié)果Fig.5 Image inpainting of lotus’s missing information

圖4的修復(fù)目的是垃圾箱的移除，圖5的修復(fù)目的是進(jìn)行荷花缺失部分的修復(fù)。

主觀上，從圖4可以看出，（c）、（d）、（e）圖的修復(fù)效果存在錯(cuò)誤信息的累積。（c）圖將遠(yuǎn)方房屋和欄桿信息在目標(biāo)移除區(qū)域進(jìn)行填充；（d）圖存在少量錯(cuò)誤信息累積，但人為修復(fù)痕跡明顯；（e）圖仍存在灰度跨度大的錯(cuò)誤信息的累積，無法滿足人的視覺需要；（f）中雖然有臺階少許錯(cuò)誤信息的累積，但無跨度較大錯(cuò)誤信息修復(fù)，整體效果較好；滿足人的視覺需要；從圖5可以看出，（c）、（d）中，荷花與莖的修復(fù)效果不佳，無法很好地區(qū)分邊緣結(jié)構(gòu)的信息；（e）中雖然能夠很好地區(qū)分邊緣結(jié)構(gòu)，但是在荷葉上出現(xiàn)了黑塊，有錯(cuò)誤信息的累積；（f）中能夠很好地區(qū)分邊緣結(jié)構(gòu)且無錯(cuò)誤信息的累積，達(dá)到了較理想的修復(fù)效果。

表1 耗時(shí)與PSNR統(tǒng)計(jì)表Tab.1 Time－consuming and PSNR

客觀上，由表1可以得出，在保證圖像修復(fù)質(zhì)量的前提下，本文FA－Criminisi算法提高了修復(fù)的效率。

因此本文FA－Criminisi算法能夠降低時(shí)耗，提高效率，修復(fù)效果圖滿足人的視覺需求。

6 結(jié) 論

針對Criminisi圖像修復(fù)算法核心部分的不足，對優(yōu)先權(quán)的計(jì)算和最佳匹配模板的搜索方式進(jìn)行改進(jìn)。本文FA－Criminisi算法提高了優(yōu)先權(quán)的可信度；且引入螢火蟲算法，提高了修復(fù)效率。因此，本文算法在保證修復(fù)效果的同時(shí)降低了時(shí)耗，具有一定的實(shí)用價(jià)值，可應(yīng)用于當(dāng)代的影視特技制作、圖片的美化等方面，具有較好的應(yīng)用前景。

［1］ Bertalmio M，Sapiro G，Caselles V，et al.Image inpainting［C］.Proceedings of International Conference on Conputer Graphics and Interactive Techniques，USA：John Seely Brown，2000：417－424.

［2］ 林云莉，趙俊紅，朱學(xué)峰，等.基于圖像分解的圖像修復(fù)技術(shù)［J］.計(jì)算機(jī)工程，2010，36（10）：187－192.Lin Y L，Zhao J H，Zhu X F，et al.Image inpainting technology based on image decomposition［J］.Computer Engineering，2010，36（10）：187－192.（in Chinese）

［3］ 朱文浩，魏國剛.基于樣本的紋理合成［J］.中國圖形圖像學(xué)報(bào)，2008，13（11）：2063－2069.Zhu W H，Wei B G.The technology of sampled－based texture synthesis［J］.Journal of Image and Graphics，2008，13（11）：2063－2069.（in Chinese）

［4］ Criminisi A，Perez P，Toyama K.Region filling and object removal by exemplar based inpainting［J］.IEEE Trans Image Process，2004，13（9）：1200－1212.

［5］ 郭勇，王梅.基于改進(jìn)樣本塊的數(shù)字圖像修復(fù)算法研究［J］.軟件導(dǎo)刊，2013，12（10）：156－158.Guo Y，Wang M.Research on exemplar based digital improving image inpainting algorithms［J］.Software Guide，2013，12（10）：156－158.（in Chinese）

［6］ 常晨，尹立新，方寶龍.一種改進(jìn)的Criminisi圖像修復(fù)算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2012，29（9）：238－267.Chang C，Yin L X，F(xiàn)ang B L.An improved Criminisi algorithm for image inpainting ［J］.Computer Applications and Software，2012，29（9）：238－267.（in Chinese）

［7］ 姚建亮，彭宏京.一種改進(jìn)的基于樣圖的圖像修復(fù)法［J］.電子科技，2010，23（1）：100－103.Yao J L，Peng H J.An improved exemplar－based method for image inpainting［J］.Electronic Science and Technology，2010，23（1）：100－103.（in Chinese）

［8］ 劉洋，王昊京，田小建，等.采用區(qū)域分割的變尺寸樣本塊高效圖像修復(fù)［J］.光學(xué)精密工程，2010，18（12）：2657－2664.Liu Y，Wang H J，Tian X J，et al.Efficient image inpainting based on region segmentation and varying exemplar［J］.Optics and Precision Engineering，2010，18（12）：2657－2664.（in Chinese）

［9］ 劉長平，葉春明.一種新穎的仿生群智能優(yōu)化算法：螢火蟲算法術(shù)［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（9）：3295－3297.Liu C P，Ye C M.Novel bioinspired swarm intelligence optimization algorithm：firefly algorithm ［J］.Application Research of Computers，2011，28（9）：3295－3297.（in Chinese）