一種基于樣圖的圖像修復(fù)改進(jìn)算法

康凱，尹東，張榮

中國(guó)科學(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ā)展，它利用計(jì)算機(jī)對(duì)數(shù)字圖像進(jìn)行與手工圖像修復(fù)相似的操作。

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

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

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

2 Criminisi算法描述

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

圖1 Criminisi算法中符號(hào)約定

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

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

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

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

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

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

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

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

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

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

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

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

3 本文改進(jìn)算法

在介紹改進(jìn)算法之前，先引入一些背景知識(shí)。

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

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

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

利用

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

3.2 本文對(duì)數(shù)據(jù)項(xiàng)的改進(jìn)

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

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

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

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

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

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

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

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

算法1 SSD算法描述

CALCULATE_SSD（待填充塊，候選塊）

current_ssd=0

for i←0 to圖像塊的高度

for j←0 to圖像塊的寬度

do current_ssd+=

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

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 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

圖2 實(shí)驗(yàn)結(jié)果一

圖3 實(shí)驗(yàn)結(jié)果二

圖4 實(shí)驗(yàn)結(jié)果三

表1 運(yùn)行時(shí)間比較

5 結(jié)束語(yǔ)

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

本文還在以下方面進(jìn)行了嘗試：（1）將本文的SSD算法與螺旋線搜索或菱形搜索結(jié)合，以期加快最佳匹配塊的搜索速度。（2）填充優(yōu)先級(jí)鼓勵(lì)邊緣結(jié)構(gòu)優(yōu)先填充，但不能保證邊緣結(jié)構(gòu)正確填充。于是筆者在SSD計(jì)算之前根據(jù)某種結(jié)構(gòu)度量淘汰結(jié)構(gòu)差異大的圖像塊，以避免結(jié)構(gòu)差異大而SSD小的候選塊被填充到待填充塊?？墒沁@些嘗試的效果不是太理想，這是今后的工作方向之一。本文還可以在如下方面進(jìn)行改進(jìn)：填充圖像塊的大小設(shè)置對(duì)實(shí)驗(yàn)效果的影響較大，為了避免這種影響，可以將本文算法與填充圖像塊大小自適應(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].中國(guó)圖象圖形學(xué)報(bào)，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ìn)[J].計(jì)算機(jī)應(yīng)用，2011，31（S1）：47-49.

[10]劉奎.基于樣例的圖像修復(fù)改進(jìn)算法[J].計(jì)算機(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].計(jì)算機(jī)工程，2008，34（14）：191-193.

[13]張晴，林家駿.紋理分布分析的快速圖像修復(fù)算法[J].中國(guó)圖象圖形學(xué)報(bào)，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.