康凱，尹東，張榮

中國科學(xué)技術(shù)大學(xué)電子工程與信息科學(xué)系，合肥230027

1 引言

圖像修復(fù)[1]是一門傳統(tǒng)技藝，它的目的是以不易覺察的方式重建藝術(shù)作品中丟失的或損壞的區(qū)域，或者去除不愿讓其出現(xiàn)的區(qū)域，以恢復(fù)藝術(shù)作品原來的質(zhì)量，增加藝術(shù)表現(xiàn)力或隱藏信息等。數(shù)字圖像修復(fù)技術(shù)是這門傳統(tǒng)技藝的發(fā)展，它利用計算機對數(shù)字圖像進行與手工圖像修復(fù)相似的操作。

數(shù)字圖像修復(fù)算法大致分為兩類：基于變分偏微分方程的算法和基于紋理合成的算法[2]?；谧兎制⒎址匠痰乃惴ㄍㄟ^建立圖像的先驗?zāi)Ｐ秃蛿?shù)據(jù)模型，將圖像修復(fù)問題轉(zhuǎn)化為一個泛函求極值的變分問題。這類方法適用于修復(fù)圖像中小尺度的缺損區(qū)域，對大尺度的缺損區(qū)域進行修復(fù)時得到的結(jié)果比較模糊。這方面的主要文獻有[1，3-5]?；诩y理合成的圖像修復(fù)算法利用已知圖像數(shù)據(jù)模型，將紋理信息復(fù)制到破損區(qū)域，對于大面積的圖像破損，能獲得較好的主觀效果。文獻[6]中提出的Criminisi算法是這一方面的典型算法。

Criminisi算法是基于樣圖復(fù)制粘貼的，不會產(chǎn)生模糊現(xiàn)象，而且其不僅可以修復(fù)破損區(qū)域的紋理信息，還可以修復(fù)破損區(qū)域的結(jié)構(gòu)信息。Criminisi算法簡單有效，學(xué)者們在其基礎(chǔ)上，提出了不少改進算法。有的研究從填充優(yōu)先級角度進行改進，如文獻[7-10]。一些研究通過改進搜索順序或限定搜索范圍等來提高Criminisi算法的修復(fù)速度，如文獻[11-13]。

Criminisi算法在圖像平滑區(qū)域和突變區(qū)域均鼓勵優(yōu)先填充線性邊緣結(jié)構(gòu)，這樣可能會在圖像的平滑區(qū)域填充虛假的線性邊緣結(jié)構(gòu)。本文針對于此對數(shù)據(jù)項進行改進。此外本文還針對最優(yōu)匹配塊搜索過程的時間復(fù)雜度高的缺點，對SSD算法進行優(yōu)化，在進行SSD計算的同時更新最佳匹配塊。

2 Criminisi算法描述

設(shè)I為輸入圖像，Ω為其待修復(fù)區(qū)域，?Ω為Ω的邊界，Φ=I-Ω為I中的完好區(qū)域。p為?Ω上一像素點，Ψp是?Ω上以p為中心的一圖像塊，如圖1所示。

圖1 Criminisi算法中符號約定

在利用Criminisi算法[6，14]進行圖像修復(fù)之前，需要人工交互選定待修復(fù)區(qū)域Ω。然后按照下面的算法對圖像進行處理：

（1）計算?Ω上各像素點的優(yōu)先級，以確定修復(fù)次序。

優(yōu)先級的計算采用兩個指標(biāo)，置信度項C(p)和數(shù)據(jù)項D(p)，最終的優(yōu)先級定義為兩者之積。

置信度項用于保證由外向內(nèi)地填充待修復(fù)區(qū)域。首先需要根據(jù)人工交互的結(jié)果確定圖像中各點置信度的初始值：

式中d(Ψ，Ψq)表示兩圖像塊差異的度量，通常選擇兩圖像塊各對應(yīng)像素點各對應(yīng)通道的顏色值的差的平方和（SSD）。

然后按照式（1）計算邊界上各點的新置信度，式中|Ψp|表示以p為中心的窗口區(qū)域內(nèi)的像素總數(shù)。

數(shù)據(jù)項用于鼓勵線性結(jié)構(gòu)優(yōu)先填充，以避免其可能受到的破壞。式中np為點p處的單位法向量；為點p處的等照度線向量，它正交于該點處的梯度向量?Ip。?Ip=[Ix，Iy]，，式中Ix和Iy分別表示點p處x和y方向的偏導(dǎo)數(shù)。α是歸一化因子，對于灰度圖像通常有α=255。

（2）搜索最優(yōu)匹配塊并填充：

搜索得最優(yōu)匹配圖像塊Ψq后，將其中的像素點復(fù)制到Ψ∩Ω中對應(yīng)的位置。

（3）更新置信度項，待修復(fù)區(qū)域和完好區(qū)域。

Ω=Ω-Ψ∩Ω和Φ=Φ+Ψ∩Ω

（4）重復(fù)步驟（1）～步驟（3），直到Ω=?，即待修復(fù)區(qū)域修復(fù)完畢。

3 本文改進算法

在介紹改進算法之前，先引入一些背景知識。

對于灰度圖像，可以在任意像素點p處建立(η，ξ)局部坐標(biāo)系，其中η軸平行于該點處的灰度梯度方向，ξ軸正交于該點處的灰度梯度方向，即平行于該點處的等照度線或邊緣方向。設(shè)η和ξ分別為η軸和ξ軸方向的單位向量，已知?Ip和?I⊥p分別表示點p處的梯度向量和等照度線向量，所以可以得到：和。設(shè)Iη和Iξ分別為p處梯度方向和邊緣方向灰度變化率，可得：ξ=0。設(shè)Iξξ為p處邊緣方向灰度的變化率的變化率，或稱為灰度加速率，Iηη為p處梯度方向灰度的加速率，根據(jù)數(shù)學(xué)知識可得[15]：

上式中，Ix和Iy分別為p處x和y方向的偏導(dǎo)數(shù)；Ixx，Ixy和Iyy為相應(yīng)的二階偏導(dǎo)數(shù)。

3.1 Criminisi算法數(shù)據(jù)項的局限性

利用

一個圖像可以分為平滑區(qū)域和突變區(qū)域，在平滑區(qū)域幾乎沒有邊緣結(jié)構(gòu)，而在突變區(qū)域存在豐富的邊緣結(jié)構(gòu)。因此對數(shù)據(jù)項的合理約束是在圖像的平滑區(qū)域，各方向的填充沒有優(yōu)先差別，而在圖像的突變區(qū)域，鼓勵優(yōu)先填充邊緣方向。而原Criminisi算法的數(shù)據(jù)項在圖像平滑區(qū)域和突變區(qū)域均鼓勵優(yōu)先填充與np夾角小的線性邊緣結(jié)構(gòu)，這樣可能會在圖像的平滑區(qū)域填充虛假的線性邊緣結(jié)構(gòu)。于是考慮定義新的數(shù)據(jù)項。

3.2 本文對數(shù)據(jù)項的改進

可以使用梯度方向和邊緣方向的灰度加速率來表征圖像位于平滑區(qū)域還是突變區(qū)域。一般地，在平滑區(qū)域，像素點的梯度方向和邊緣方向的灰度加速率較小，而在突變區(qū)域，像素點的梯度方向和邊緣方向的灰度加速率較大。

再結(jié)合上面對數(shù)據(jù)項的約束條件，認(rèn)為對于?Ω上的像素點p，在置信度項給定的條件下，該點的填充優(yōu)先級由該點處的梯度方向和邊緣方向的灰度加速率共同決定。詳細(xì)地，如果點p在圖像的平滑區(qū)域，其梯度方向和邊緣方向的灰度加速率無差別地決定填充優(yōu)先級；而如果點p在圖像的突變區(qū)域，為了鼓勵圖像的邊緣結(jié)構(gòu)優(yōu)先填充，其邊緣方向的灰度加速率對填充優(yōu)先級的貢獻率要不小于梯度方向的灰度加速率。綜合起來考慮，定義如下的數(shù)據(jù)項：

式中k是調(diào)節(jié)因子且k∈[0，1]，其他符號的意義可以參見前文。新的數(shù)據(jù)項除了滿足上面對數(shù)據(jù)項的要求之外，還有如下特點：鼓勵優(yōu)先填充與np夾角小的邊緣結(jié)構(gòu)，并且鼓勵優(yōu)先填充圖像的突變區(qū)域。

大家知道，在圖像平滑區(qū)域，||?2I較小；而在圖像邊緣處?2I=0，邊緣點附近?2I則存在較大的波動，故可以認(rèn)為在突變區(qū)域，||?2I具有較大的值。于是可以定義：

式中β為歸一化因子，這里設(shè)置β=2×255。

3.3 優(yōu)化最佳匹配塊搜索

為了加快搜索最佳匹配塊，在計算SSD時，維護幾個變量：當(dāng)前最佳匹配塊及其與待填充塊之間的SSD（記為m in_ssd）和距離（記為best_dist）。一開始將當(dāng)前最佳匹配塊與待填充塊之間的SSD和距離初始化為很大的數(shù)，接著按照算法1，更新最佳匹配塊及其與待填充塊之間的SSD和距離。在對圖像中所有的候選塊進行如下算法操作之后，便可以得到最終的最佳匹配塊。

由算法描述可見，當(dāng)待填充塊和當(dāng)前候選塊的部分對應(yīng)像素點的SSD大于當(dāng)前維護的最小的SSD時，可以斷定當(dāng)前候選塊肯定不是最佳匹配塊，不再進行兩塊剩下對應(yīng)像素點SSD的計算，也不更新維護的變量，直接進入到下一輪待填充塊與新的候選塊SSD的計算。這一算法可以避免計算待填充塊和候選塊之間的完整的SSD，從而減少了計算量。

算法1 SSD算法描述

CALCULATE_SSD（待填充塊，候選塊）

current_ssd=0

for i←0 to圖像塊的高度

for j←0 to圖像塊的寬度

do current_ssd+=

對應(yīng)像素點各通道顏色的差的平方和

do if current_ssd>m in_ssd

then return

current_dist=兩圖像塊之間的距離

if current_ssd==m in_ssd

if current_dist<best_dist

then最佳匹配塊=候選塊

best_dist=current_dist

else

m in_ssd=current_ssd

最佳匹配塊=候選塊

best_dist=current_dist

4 實驗結(jié)果及分析

本文算法實現(xiàn)使用了OpenCV 1.0開源庫，實驗環(huán)境為PC機，硬件配置：CPU為AMD A thlon II X 2 240 Processor（2 800MHz），內(nèi)存容量為2.00GB。

實驗選取了一些典型的圖像，填充圖像塊的大小均為7×7。圖像修復(fù)的結(jié)果圖一般沒有參考圖像，一些客觀評價指標(biāo)如PSNR等已不適用，如果將原圖像作為參考圖像，由于圖像修復(fù)的結(jié)果以盡可能貌似合理為目的，而不是與原圖像的一致性，計算得到的指標(biāo)也不能正確反映實際的修復(fù)效果。因此本文采用主觀的評價方法。除了Criminisi算法，實驗還選取了文獻[7]中的算法結(jié)果圖像作為對照，在那里數(shù)據(jù)項被定義為D(p)=，其余的算法流程與Criminisi算法一致。

圖2是算法在修復(fù)破損照片中的刮痕中的應(yīng)用，由于刮痕結(jié)構(gòu)簡單，Criminisi算法，文獻[7]中的算法和本文改進算法的修復(fù)效果均比較理想。圖3是算法在大目標(biāo)對象去除中的應(yīng)用，Criminisi算法由于在平滑區(qū)域和突變區(qū)域無差別地鼓勵優(yōu)先填充與np夾角小的線性邊緣結(jié)構(gòu)，使河岸交界處出現(xiàn)了多余塊，以及岸上區(qū)域出現(xiàn)了白色雜塊，而改進算法修復(fù)的結(jié)果圖沒有。圖4是算法修復(fù)結(jié)構(gòu)圖像的示例，Criminisi算法由于相同的原因以及誤差傳播而使內(nèi)部產(chǎn)生孔洞，而改進算法會使修復(fù)后的邊緣因為較為平滑，而且沒有產(chǎn)生孔洞。對于文獻[7]中提出的算法，線性結(jié)構(gòu)對應(yīng)于較低的數(shù)據(jù)項值，所以不會鼓勵線性結(jié)構(gòu)的優(yōu)先填充，如圖3（d）中的屋頂和圖4（d）的黑色條帶的線性結(jié)構(gòu)就被修復(fù)斷裂。

表1是各算法的運行時間比較，其中的Criminisi算法沒有采用3.3節(jié)中提出的優(yōu)化算法，而表中的Criminisi 2算法、文獻[7]算法和本文算法均使用了3.3節(jié)中提出的優(yōu)化算法。

圖2 實驗結(jié)果一

圖3 實驗結(jié)果二

圖4 實驗結(jié)果三

表1 運行時間比較

5 結(jié)束語

針對Criminisi算法提出了改進和優(yōu)化。實驗表明，本文改進算法的修復(fù)效果要優(yōu)于原來的算法，而且修復(fù)時間也有比較可觀的減少。

本文還在以下方面進行了嘗試：（1）將本文的SSD算法與螺旋線搜索或菱形搜索結(jié)合，以期加快最佳匹配塊的搜索速度。（2）填充優(yōu)先級鼓勵邊緣結(jié)構(gòu)優(yōu)先填充，但不能保證邊緣結(jié)構(gòu)正確填充。于是筆者在SSD計算之前根據(jù)某種結(jié)構(gòu)度量淘汰結(jié)構(gòu)差異大的圖像塊，以避免結(jié)構(gòu)差異大而SSD小的候選塊被填充到待填充塊?？墒沁@些嘗試的效果不是太理想，這是今后的工作方向之一。本文還可以在如下方面進行改進：填充圖像塊的大小設(shè)置對實驗效果的影響較大，為了避免這種影響，可以將本文算法與填充圖像塊大小自適應(yīng)算法相結(jié)合。

[1]Bertalm io M，Sapiro G，Caselles V，et al.Image Inpainting[C]//Proceedings of Computer Graphics，Annual Conference Series，New Orleans，Louisiana，USA，2000：417-424.

[2]張紅英.數(shù)字圖像修復(fù)技術(shù)綜述[J].中國圖象圖形學(xué)報，2007，12（1）：1-10.

[3]Bertalm io M，Bertozzi A L，Sapiro G.Navier-stokes，fluid dynamics，and image and video inpainting[C]//Proc of Conf on Comp Vision Pattern Rec，2001：355-362.

[4]Chan T F，Shen J.Mathematical models for local non-texture inpainting[J].SIAM Journal of Applied Mathematics，2001，62（3）：1019-1043.

[5]Chan T F，Shen J.Non-texture inpainting by Curvature-Driven Diffusions（CDD）[J].Journal of Visual Communication and Image Representation，2001，12（4）：436-449.

[6]Criminisi A，Pérez P，Toyama K.Object Removal by Exemplar-Based Inpainting[C]//Proc of Conf on Computer Vision and Pattern Recognition，Madison，W I，June 2003.

[7]Wu Jiying，Ruan Qiuqi.Object removal by cross isophotes exemplar-based inpainting[C]//Proceedings of the 18th International Conference on Pattern Recognition，2006.

[8]Wu Jiying，Ruan Qiuqi.A novel exemplar-based image completion model[J].Journal of Information Science and Engineering，2009，25（2）：481-497.

[9]陳龍.基于樣本塊的圖像修復(fù)方法的改進[J].計算機應(yīng)用，2011，31（S1）：47-49.

[10]劉奎.基于樣例的圖像修復(fù)改進算法[J].計算機工程，2012，38（7）：193-195.

[11]Tang Feng，Ying Yiting，Wang Jin，et al.A novel texture synthesis based algorithm for object removal in photographs[C]//Proceedings of the 9th Asian Computing Science Conference，Thailand，2004：248-258.

[12]朱霞.一種基于顏色區(qū)域分割的圖像修復(fù)算法[J].計算機工程，2008，34（14）：191-193.

[13]張晴，林家駿.紋理分布分析的快速圖像修復(fù)算法[J].中國圖象圖形學(xué)報，2012，17（1）：123-129.

[14]Criminisi A，Perez P，Toyama K.Region filling and object removal by exemplar-based image inpainting[J].IEEE Trans on Image Processing，2004，13（9）：1200-1212.

[15]吳亞東.數(shù)字圖像修復(fù)技術(shù)[M].北京：科學(xué)出版社，2010.