目標移除的Criminisi圖像修復(fù)算法

李 尊，吳 謹，劉 勁

?

目標移除的Criminisi圖像修復(fù)算法

李 尊，吳 謹，劉 勁

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

待修復(fù)區(qū)域標記、優(yōu)先權(quán)、最佳匹配模塊的搜索及填充和更新置信度是Criminisi圖像修復(fù)算法的4個重要組成部分，每一部分對Criminisi算法的圖像修復(fù)結(jié)果都有不可忽視的作用。針對大目標移除的Criminisi圖像修復(fù)，從數(shù)學的角度優(yōu)化待修復(fù)區(qū)域標記和提高優(yōu)先權(quán)可信度，并將蝙蝠算法運用到最佳匹配模板搜索中，提高修復(fù)效率。實驗表明：本文改進的算法能夠有效的減少錯誤信息的累積，具有較好的實用性。

Criminisi圖像修復(fù)算法；修復(fù)區(qū)域標記；優(yōu)先權(quán)；蝙蝠算法

0 引言

圖像修復(fù)[1-2]就是利用圖像中原有的信息來恢復(fù)缺失的信息。目前圖像修復(fù)技術(shù)廣泛應(yīng)用到文物保護，冗余目標的移除，影視特效制作等方面，是當前計算機視覺研究的一個熱點。

圖像修復(fù)主要由兩種代表性計算機自動修復(fù)算法構(gòu)成，基于結(jié)構(gòu)的圖像修復(fù)[3-4]和基于紋理的圖像修復(fù)。

Criminisi圖像修復(fù)算法[5]是基于紋理的典型算法，由Criminisi等人于2004年提出。其將紋理特征和結(jié)構(gòu)信息結(jié)合起來進行修復(fù)，取得了不錯的效果。

近年來，Criminisi圖像修復(fù)算法的改進主要是提升優(yōu)先權(quán)的可信度。但是Criminisi圖像修復(fù)算法是一個有機整體，由修復(fù)區(qū)域標記、優(yōu)先權(quán)計算、最佳匹配塊搜索與填充和更新置信度組成，每一步在Criminisi圖像修復(fù)算法中都不可或缺。

本文針對目標移除的情況進行研究，探究其修復(fù)效果的影響因素，從數(shù)學的角度改進Criminisi圖像修復(fù)算法，提高目標移除的Criminisi圖像修復(fù)質(zhì)量。

1 Criminisi圖像修復(fù)算法

圖1為Criminisi圖像修復(fù)算法示意圖，圖中，表示待修復(fù)區(qū)域；表示待修復(fù)區(qū)域的輪廓；表示完好區(qū)域。

Criminisi圖像修復(fù)算法核心思想就是通過優(yōu)先權(quán)公式確定要修補的目標塊，進而根據(jù)一定的匹配原則在已知信息區(qū)域進行搜索并填充，直至待修復(fù)區(qū)域修復(fù)完畢。

對圖1中目標塊的優(yōu)先權(quán)的計算公式如式(1)所示：

priority()＝()() (1)

其中：

式中：()為置信度，用于衡量目標塊中已知信息的比重；()為數(shù)據(jù)項，決定圖像修復(fù)是沿等照度線的方向進行；在灰度圖中通常取＝255。

圖1 Criminisi算法示意圖

通過優(yōu)先權(quán)確定最大值的待修補塊后，在樣本區(qū)域根據(jù)式(4)的匹配原則選取最佳匹配模塊進行填充：

Criminisi圖像修復(fù)算法通過上述原則不斷地進行填充，直至待修復(fù)區(qū)域修復(fù)完成。

2 Criminisi算法的分析與改進

2.1 待修復(fù)區(qū)域的標記

在進行Criminisi算法修復(fù)前，圖像的待修復(fù)區(qū)域需要一種特定的顏色進行標記，通常選用白色。

但是預(yù)先標記往往會影響待修復(fù)區(qū)域的結(jié)構(gòu)信息和紋理信息。因此本文引入數(shù)學形態(tài)學中的腐蝕與膨脹[6]對待修復(fù)圖像進行預(yù)處理。本文引入數(shù)學形態(tài)學來保證Criminisi圖像修復(fù)算法的進行是在合理的標記的基礎(chǔ)上。

形態(tài)腐蝕與膨脹對圖像處理有如下效果：

1）形態(tài)膨脹使得孔隙消失，縫變粗，擴展圖像；

2）形態(tài)腐蝕使得孔隙擴大，縫變細，收縮圖像。

本文采用形態(tài)膨脹與腐蝕的基本組合形式，對待修復(fù)圖像進行處理,即先膨脹后腐蝕：

式中：、都為結(jié)構(gòu)元素。

2.2 優(yōu)先權(quán)的計算

優(yōu)先權(quán)處于Criminisi圖像修復(fù)算法第一步，處于核心地位，決定了修補的先后次序。

優(yōu)先權(quán)的計算存在兩點不足：

1）隨著修補次數(shù)的增加，置信度()中的原圖的信息會減少甚至出現(xiàn)數(shù)量級的差別，造成優(yōu)先權(quán)完全是由紋理信息所決定的；

2）數(shù)據(jù)項()是人為設(shè)定的修補方向按照等照度方向進行的，極易出現(xiàn)線性修補方向現(xiàn)象，人為修復(fù)的痕跡增強。

為了提高填充次序的可信度，近幾年改進的Criminisi圖像修復(fù)算法側(cè)重點在優(yōu)先權(quán)。其中文獻[7]將優(yōu)先權(quán)中數(shù)據(jù)項和置信度轉(zhuǎn)換成加權(quán)和的形式，一定程度上提升了優(yōu)先權(quán)的可信度，且修復(fù)質(zhì)量有所提升；文獻[8]通過引入曲率決定目標塊的優(yōu)先權(quán)，增強了修復(fù)圖像的結(jié)構(gòu)連續(xù)性。

本文對優(yōu)先權(quán)的改進是基于數(shù)學的角度，當輸出正比于輸入時能夠很好的抵抗噪聲及外部的干擾。所以為了增強修復(fù)邊緣結(jié)構(gòu)過程的魯棒性，本文引用正規(guī)化函數(shù)平滑數(shù)據(jù)項()曲線。因此得出的新數(shù)據(jù)項如式(6)所示：

()＝＋(1－)() (6)

新數(shù)據(jù)項的引入，保證其取值的范圍在～1之間，數(shù)據(jù)項的曲線被平滑了，且其曲線的形狀保留，通常選取＝0.7。

新優(yōu)先權(quán)為新數(shù)據(jù)項與置信度的加權(quán)形式，如式(7)所示：

Newpriority()＝×()＋×() (7)

式中：＋＝1，本文取＝＝0.5。

2.3 匹配模塊搜索與填充

Criminisi圖像修復(fù)算法的最佳匹配模塊就是完好區(qū)域的樣本塊中已知元素與待修補塊的的顏色平方和最小值的模塊，其從數(shù)學原理上來說就是差方和法，即SSD。

但在實際的修復(fù)過程中，全局搜索時最佳模塊可能不止一個，系統(tǒng)會隨機地選擇一個進行填充，且全局搜索增加計算機的工作量同時影響最佳模塊的選擇。

文獻[9]引入待匹配塊的再篩選策略，降低了匹配模塊選擇的隨機性，增強了圖像的修復(fù)效果；文獻[10]將像素點間的空間距離引入，且采用全局搜索，能夠很好地避免“貪婪性”的缺點。

本文采用蝙蝠算法[11]進行最佳模板的搜索，且匹配原則仍為SSD。蝙蝠算法能將全局搜索和局部搜索高效的融合，且具有很好的適應(yīng)性和魯棒性，能夠降低錯誤信息的累積。

蝙蝠算法公式化基于以下3個原則：

1）蝙蝠采用特定的方式判別目標物與障礙物，且利用回聲定位方式感知距離；

2）在任意位置X處，蝙蝠以速度V任意飛行，以確定大小的頻率min和大小可變的波長、響度0找尋目標物，且根據(jù)目標物與自身的距離遠近自動調(diào)節(jié)波長或者頻率，并在靠近目標物時候調(diào)整發(fā)射脈沖的頻度?[0,1]。

3）默認響度的變化是從最大值0到最小值min，0必須為正值。

基于上述原則，蝙蝠算法的步驟如下所示：

步驟一：參數(shù)初始化：目標函數(shù)()，其中維度集合＝(1,2,3,…,x)，為維度，1,2,3,…,x為變量數(shù)，蝙蝠群體的個體采用標識，初始化蝙蝠群體的個體在X處的速度V并定義X處的脈沖頻率f，初始化脈沖速率r和響度A，本文目標函數(shù)()采用SSD匹配原則。

步驟二：通過調(diào)整頻率產(chǎn)生新的解并更新速度和位置。

步驟三：根據(jù)rand1＞r進行判斷，從最佳解的集合中選出一個解，在最佳解周圍形成一個局部解，其中rand1表示產(chǎn)生一個隨機數(shù)。

步驟四：通過不確定飛行確定一個新的解。

步驟五：根據(jù)判斷條件rand2＜A&(x)＜(*)進行判斷，若條件滿足，增大r減小A，然后進入步驟六，其中rand2表示產(chǎn)生一個隨機數(shù)。若不滿足則直接進入步驟六。

步驟六：排列蝙蝠找到最佳解*。

步驟七：處理結(jié)果：若結(jié)束條件滿足，則結(jié)束迭代輸出最優(yōu)解；不滿足則返回第二步進行迭代。

第次迭代執(zhí)行到步驟二時，其中速度、位置的更新如式(8)～式(10)所示：

f＝min＋(max－min)(8)

V＝V－1＋(X－*)×f(9)

X＝X－1＋V(10)

當＝1時，X－1、V－1采用初始化所得結(jié)果。

可根據(jù)問題的領(lǐng)域大小確定脈沖頻率f的值，比如取min＝0，max＝100，開始時每只蝙蝠隨機分配頻率，頻率可從[min,max]平均得出的。min為最小脈沖頻率，max為最大脈沖頻率，可自行預(yù)先設(shè)定取值。?[0,1]為隨機向量，*為當前全局的最佳解。在固定(f)的同時改變f()，且在局部搜索的過程中，每只蝙蝠的新的位置就近得出，其中表示對應(yīng)脈沖頻率的波長，如式(11)所示：

new＝old＋A(11)

式中：?[－1,1]為隨機數(shù)；old表示蝙蝠所處的舊位置；new表示蝙蝠所處的的新位置；A為所有蝙蝠在本次迭代中的平均值。

隨著蝙蝠的速度與位置的更新，脈沖發(fā)射的響度A和速率r也會更新。通常目標物一旦發(fā)現(xiàn)，其脈沖的發(fā)射響度A會降低，脈沖的發(fā)射速度r會升高，其表達式如下所示：

A＋1＝A(12)

r＋1＝r0(1－e－) (13)

式中：、為恒量，且滿足0＜＜1，＞0。在、的取值范圍定義下，隨著迭代次數(shù)的增加，脈沖發(fā)射的響度A會逐漸趨于0，脈沖發(fā)射的速率r會逐漸趨于初始化脈沖的發(fā)射速率r0，其數(shù)值通常選用在0附近，滿足蝙蝠算法公式化的原則。

本文采用標準的Rosenbroke檢測函數(shù)對蝙蝠算法進行測試，其函數(shù)表達式如下所示：

其中，本文取值＝2，應(yīng)用情景是二維，蝙蝠的種群中個體的個數(shù)為25只，即1≤≤25且?*，＝＝0.9。*為正整數(shù)。

本文利用蝙蝠算法尋找()的最小值，由數(shù)學理論可知，()在(1,1)時，可取得最小值0，其蝙蝠搜索路徑如圖2所示。

圖2 蝙蝠算法搜索路徑圖

從圖2中，可以看出標準的Rosenbroke檢測函數(shù)通過25只蝙蝠將搜索區(qū)域確定，然后在確定的小范圍的搜索區(qū)域進行最優(yōu)解的搜索。最后最優(yōu)解的點坐標為(1.0006,1.0011)與理論值相差不大。

因此在最佳匹配模板的搜索的過程中，SSD原則作為蝙蝠算法的目標函數(shù)，搜索方式即為蝙蝠算法，如式(15)所示：

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

蝙蝠算法能很好地將全局搜索和局部搜索高效的融合。且此算法具有很好的適應(yīng)性和魯棒性，提升圖像修復(fù)效果。

綜上，本文對待修復(fù)區(qū)域標記、優(yōu)先權(quán)的計算、最佳匹配模板的搜索方式3方面進行改進，旨在降低錯誤信息的累積進行修復(fù)，提高修復(fù)質(zhì)量，滿足人的視覺需要。

3 仿真實驗結(jié)果分析

本文實驗仿真平臺是MATLAB7.0和VC＋＋6.0，峰值信噪比PSNR是目前最普遍用來評鑒圖像質(zhì)量的客觀量，因此本文實驗結(jié)果修復(fù)結(jié)果質(zhì)量用此客觀地評價。

圖3的修復(fù)目的是對于前景人群而言，背景人群是冗余目標，需要移除。其中，(a)是原圖，(b)為預(yù)先標記圖像，(c)為經(jīng)過數(shù)學形態(tài)學處理后的標記圖。

圖4的修復(fù)目的是對于風景而言，垃圾桶是冗余目標，需要移除。其中，(a)是原圖，(b)為預(yù)先標記圖像。(c)為經(jīng)過數(shù)學形態(tài)學處理后的標記圖。

本文數(shù)學形態(tài)學處理的結(jié)構(gòu)元素為圓形，目的是能夠很好地強化邊緣結(jié)構(gòu)信息。本文的圖像修復(fù)是在經(jīng)過數(shù)學形態(tài)學處理后的標記圖的基礎(chǔ)上進行的。

圖5、圖6中，(a)表示傳統(tǒng)Criminisi圖像修復(fù)算法的修復(fù)效果；(b)表示文獻[7]圖像修復(fù)算法的修復(fù)效果；(c)表示文獻[8]圖像修復(fù)算法的修復(fù)效果；(d)表示本文改進的Criminisi圖像修復(fù)算法的修復(fù)效果。

主觀上：在圖5、圖6的(a)、(b)、(c)和(d)中，(a)、(b)、(c)的修復(fù)效果圖中均有錯誤信息的累積，無法滿足人的視覺效果；(d)的修復(fù)效果最好，能夠很好地區(qū)分邊緣結(jié)構(gòu)信息，較少的錯誤信息的累積，滿足人的視覺需要。

客觀上：在表1、表2中，數(shù)據(jù)顯示(d)的PSNR數(shù)值最大，則其修復(fù)的效果最好。

因此針對目標移除這一類圖像修復(fù)，本文改進的算法具有很好的實用性，錯誤信息累積減少，視覺需求得以滿足。

4 結(jié)束語

本文針對Criminisi算法的不足，對待修復(fù)區(qū)域的標記、優(yōu)先權(quán)的計算、最佳匹配模板的搜索方法進行改進。針對目標移除這一類圖像修復(fù)，本文改進的算法提高了優(yōu)先權(quán)和匹配原則的可信度，能夠有效地避免錯誤信息的累積，增強圖像修復(fù)效果，具有很高的實用價值。

圖3 人群移除的圖像

圖4 垃圾桶移除的圖像

圖5 改進的Criminisi算法在人群的對比實驗

圖6 改進的Criminisi算法在垃圾桶的對比實驗

表1 改進的Criminisi算法在人群的PSNR值

表2 改進的Criminisi算法在垃圾桶的PSNR值

[1] Bertalmio M, Sapiro G, Caselles V, et al. Image inpainting[C]//, John Seely Brown, USA, 2000: 417-424．

[2] 陳錢. 紅外圖像處理技術(shù)現(xiàn)狀及發(fā)展趨勢[J]. 紅外技術(shù), 2013, 35(6): 311-318.

CHEN Qian. The status and development trend of infrared image processing technology[J]., 2013, 35(06): 311-318.

[3] Ballester C, Bertalmio M, Caselles V, et al. Filling-in by joint interpolation of vector field and gray levels[J]., 2001, 10(8): 1200-1211．

[4] Chan T, Shen F. Mathematical models for local non-texture inpaintings[J]., 2002, 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] 任獲榮. 數(shù)學形態(tài)學及其應(yīng)用[D]. 西安: 西安電子科技大學, 2004．

REN Huorong. Mathematical morphology and its application[D]. Xi’an: Xidian University, 2004.

[7] 郭勇, 王梅. 基于改進樣本塊的數(shù)字圖像修復(fù)算法研究[J]. 軟件導刊, 2013, 12(10): 156-158.

GUO Yong, WANG Mei. Research on exemplar-based digital improving image inpainting algorithms[J]., 2013, 12(10): 156-158.

[8] 常晨, 尹立新, 方寶龍. 一種改進的Criminisi圖像修復(fù)算法[J]. 計算機應(yīng)用與軟件, 2012, 29(9): 238-267.

CHANG Chen, YIN Lixin, FANG Baolong. An improved Criminisi algorithm for image inpainting[J]., 2012, 29(9): 238-267.

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

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

[10] 潘姣君, 謝伙生. 結(jié)合灰度共生矩陣和熵的圖像修復(fù)算法[J]. 圖形、圖像與多媒體, 2012, 31(21): 44-49.

PAN Jiaojun, XIE Huosheng. Image inpainting algorithm combining gray-level co-occurrence matrix and entropy[J]., 2012, 31(21): 44-49.

[11] Yang X S．A new metaheuristic bat-inspired algorithm[C]//2010,284, 2010: 65-74.

Criminisi Image Restoration Algorithm for Object Removal

LI Zun，WU Jin，LIU Jin

(,,438001,)

Criminisi algorithm consists of four steps which are marking area, the priority, the best sample patch and updating the degree of confidence and each step has the important effect. For removing a big target, this paper uses the reasonable marked and improved priority, and then the bat algorithm is applied to search the best match template in Criminisi image restoration. Experiment results show that this method can reduce the inaccurate matching and has relatively high practical value.

Criminisi algorithm，the marked area，the priority，bat algorithm

TP391.41

A

1001-8891(2016)01-0028-05

2014-05-26；

2014-08-19.

李尊（1988-），女，河南省新鄉(xiāng)，碩士研究生，從事圖像修復(fù)研究工作。E-mail：895310276@qq.com。

湖北省自然科學基金（2013CFB333）；高等學校博士學科點專項科研基金（20124219120002）；湖北省教育廳科研計劃（Q20131110）。