一種基于樣圖的圖像修復改進算法

康凱，尹東，張榮

中國科學技術大學電子工程與信息科學系，合肥230027

1 引言

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

數字圖像修復算法大致分為兩類：基于變分偏微分方程的算法和基于紋理合成的算法[2]。基于變分偏微分方程的算法通過建立圖像的先驗模型和數據模型，將圖像修復問題轉化為一個泛函求極值的變分問題。這類方法適用于修復圖像中小尺度的缺損區域，對大尺度的缺損區域進行修復時得到的結果比較模糊。這方面的主要文獻有[1，3-5]。基于紋理合成的圖像修復算法利用已知圖像數據模型，將紋理信息復制到破損區域，對于大面積的圖像破損，能獲得較好的主觀效果。文獻[6]中提出的Criminisi算法是這一方面的典型算法。

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

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

2 Criminisi算法描述

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

圖1 Criminisi算法中符號約定

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

（1）計算?Ω上各像素點的優先級，以確定修復次序。

優先級的計算采用兩個指標，置信度項C(p)和數據項D(p)，最終的優先級定義為兩者之積。

置信度項用于保證由外向內地填充待修復區域。首先需要根據人工交互的結果確定圖像中各點置信度的初始值：

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

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

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

（2）搜索最優匹配塊并填充：

搜索得最優匹配圖像塊Ψq后，將其中的像素點復制到Ψ∩Ω中對應的位置。

（3）更新置信度項，待修復區域和完好區域。

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

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

3 本文改進算法

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

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

上式中，Ix和Iy分別為p處x和y方向的偏導數；Ixx，Ixy和Iyy為相應的二階偏導數。

3.1 Criminisi算法數據項的局限性

利用

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

3.2 本文對數據項的改進

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

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

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

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

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

3.3 優化最佳匹配塊搜索

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

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

算法1 SSD算法描述

CALCULATE_SSD（待填充塊，候選塊）

current_ssd=0

for i←0 to圖像塊的高度

for j←0 to圖像塊的寬度

do current_ssd+=

對應像素點各通道顏色的差的平方和

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 實驗結果及分析

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

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

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

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

圖2 實驗結果一

圖3 實驗結果二

圖4 實驗結果三

表1 運行時間比較

5 結束語

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

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

[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]張紅英.數字圖像修復技術綜述[J].中國圖象圖形學報，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]陳龍.基于樣本塊的圖像修復方法的改進[J].計算機應用，2011，31（S1）：47-49.

[10]劉奎.基于樣例的圖像修復改進算法[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]朱霞.一種基于顏色區域分割的圖像修復算法[J].計算機工程，2008，34（14）：191-193.

[13]張晴，林家駿.紋理分布分析的快速圖像修復算法[J].中國圖象圖形學報，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]吳亞東.數字圖像修復技術[M].北京：科學出版社，2010.