目標移除的Criminisi圖像修復算法

李 尊，吳 謹，劉 勁

?

目標移除的Criminisi圖像修復算法

李 尊，吳 謹，劉 勁

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

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

Criminisi圖像修復算法；修復區域標記；優先權；蝙蝠算法

0 引言

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

圖像修復主要由兩種代表性計算機自動修復算法構成，基于結構的圖像修復[3-4]和基于紋理的圖像修復。

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

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

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

1 Criminisi圖像修復算法

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

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

對圖1中目標塊的優先權的計算公式如式(1)所示：

priority()＝()() (1)

其中：

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

圖1 Criminisi算法示意圖

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

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

2 Criminisi算法的分析與改進

2.1 待修復區域的標記

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

但是預先標記往往會影響待修復區域的結構信息和紋理信息。因此本文引入數學形態學中的腐蝕與膨脹[6]對待修復圖像進行預處理。本文引入數學形態學來保證Criminisi圖像修復算法的進行是在合理的標記的基礎上。

形態腐蝕與膨脹對圖像處理有如下效果：

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

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

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

式中：、都為結構元素。

2.2 優先權的計算

優先權處于Criminisi圖像修復算法第一步，處于核心地位，決定了修補的先后次序。

優先權的計算存在兩點不足：

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

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

為了提高填充次序的可信度，近幾年改進的Criminisi圖像修復算法側重點在優先權。其中文獻[7]將優先權中數據項和置信度轉換成加權和的形式，一定程度上提升了優先權的可信度，且修復質量有所提升；文獻[8]通過引入曲率決定目標塊的優先權，增強了修復圖像的結構連續性。

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

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

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

新優先權為新數據項與置信度的加權形式，如式(7)所示：

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

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

2.3 匹配模塊搜索與填充

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

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

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

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

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

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

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

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

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

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

步驟二：通過調整頻率產生新的解并更新速度和位置。

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

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

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

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

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

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

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

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

X＝X－1＋V(10)

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

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

new＝old＋A(11)

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

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

A＋1＝A(12)

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

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

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

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

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

圖2 蝙蝠算法搜索路徑圖

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

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

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

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

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

3 仿真實驗結果分析

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

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

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

本文數學形態學處理的結構元素為圓形，目的是能夠很好地強化邊緣結構信息。本文的圖像修復是在經過數學形態學處理后的標記圖的基礎上進行的。

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

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

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

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

4 結束語

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

圖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] 陳錢. 紅外圖像處理技術現狀及發展趨勢[J]. 紅外技術, 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] 任獲榮. 數學形態學及其應用[D]. 西安: 西安電子科技大學, 2004．

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

[7] 郭勇, 王梅. 基于改進樣本塊的數字圖像修復算法研究[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圖像修復算法[J]. 計算機應用與軟件, 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] 胡文瑾, 王維蘭, 劉仲民. 一種基于樣本塊的快速圖像修復算法[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] 潘姣君, 謝伙生. 結合灰度共生矩陣和熵的圖像修復算法[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-），女，河南省新鄉，碩士研究生，從事圖像修復研究工作。E-mail：895310276@qq.com。

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