康凱,尹東,張榮
中國科學(xué)技術(shù)大學(xué)電子工程與信息科學(xué)系,合肥230027
圖像修復(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)P秃蛿?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計算的同時更新最佳匹配塊。
設(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ù)完畢。
在介紹改進算法之前,先引入一些背景知識。
對于灰度圖像,可以在任意像素點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ù)。
利用
一個圖像可以分為平滑區(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ù)項。
可以使用梯度方向和邊緣方向的灰度加速率來表征圖像位于平滑區(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。
為了加快搜索最佳匹配塊,在計算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
本文算法實現(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 運行時間比較
針對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.