江 平, 張 錦
(合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院,安徽 合肥 230009)
一種結(jié)合CDD模型和Criminisi算法的圖像修復(fù)算法
江 平, 張 錦
(合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院,安徽 合肥 230009)
針對(duì)既含有大塊缺失信息又含有劃痕的圖像,結(jié)合CDD模型和Criminisi算法的優(yōu)點(diǎn),提出一種新的修復(fù)算法。算法先采用可以強(qiáng)化細(xì)節(jié)的自適應(yīng)直方圖均衡化操作來(lái)擴(kuò)大圖像的動(dòng)態(tài)范圍,后利用形態(tài)學(xué)算子分離出待修復(fù)圖像中的劃痕區(qū)域與大塊區(qū)域,接著用CDD模型對(duì)劃痕進(jìn)行修復(fù),再用改進(jìn)優(yōu)先級(jí)的 Criminisi算法進(jìn)行后續(xù)修復(fù),最后把修復(fù)后的圖像對(duì)應(yīng)于缺失區(qū)域的像素填補(bǔ)到待修復(fù)圖像的區(qū)域中。實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的算法克服了現(xiàn)有算法可能存在的偏差延續(xù)問(wèn)題,使圖像修復(fù)的結(jié)果更加符合人們的視覺(jué)效果。
CDD模型;Criminisi算法;圖像修復(fù);自適應(yīng)直方圖均衡化;形態(tài)學(xué)算子
圖像修復(fù)技術(shù)是近年來(lái)計(jì)算機(jī)圖形學(xué)和計(jì)算機(jī)視覺(jué)中的一個(gè)倍受關(guān)注的研究熱點(diǎn),所謂圖像修復(fù)[1]是指針對(duì)圖像中遺失或缺損的部分,利用未丟失或未破損的圖像信息,按一定的方法自動(dòng)填補(bǔ)的過(guò)程,其目的是使觀察者無(wú)法察覺(jué)到圖像曾經(jīng)缺損或已被修復(fù)。圖像修復(fù)技術(shù)在文物的保護(hù)、多余物的剔除、影視特技的制作、圖像壓縮等方面得到廣泛的應(yīng)用。
2000年,Bertalmio等[2]首先提出了一個(gè)基于三階偏微分的 BSCB修復(fù)模型,他開(kāi)創(chuàng)了基于偏微分方程修復(fù)的先河,其基本思想是利用待修復(fù)區(qū)域的邊緣信息,將待修復(fù)區(qū)域邊界的外部信息沿輪廓擴(kuò)散到中間待修補(bǔ)區(qū)域的像素上;2002年,Chan和Shen[3]在全變分(total variation, TV)去噪模型[4]的啟發(fā)下提出了基于 TV模型的圖像修復(fù)方法,同時(shí)說(shuō)明了TV模型不滿足人類視覺(jué)中的“連續(xù)性”準(zhǔn)則的缺點(diǎn),進(jìn)一步提出了曲率驅(qū)動(dòng)擴(kuò)散(curvature driven diffusion, CDD)[5]修復(fù)模型,讓圖像中不自然的大曲率迅速擴(kuò)散,能以較低的計(jì)算復(fù)雜度實(shí)現(xiàn)有效的修復(fù)。此類修復(fù)方法對(duì)于小面積的圖像缺失(例如劃痕)有顯著的效果,但對(duì)破損區(qū)域較大的圖像修復(fù)效果不太理想。
基于樣本塊紋理合成方法能夠較好地處理大范圍缺失圖像,其中較為經(jīng)典的修復(fù)算法是Criminisi等[6]提出的Criminisi算法:將待修補(bǔ)區(qū)域分塊修復(fù),按照優(yōu)先級(jí)公式計(jì)算出修補(bǔ)順序,在圖片中尋找與待修復(fù)區(qū)域塊最相近的塊將其填補(bǔ);此后,文獻(xiàn)[7]中描述了該算法,并通過(guò)更多的實(shí)例說(shuō)明該算法的有效性。盡管如此,Criminisi算法在處理圖像時(shí),對(duì)較強(qiáng)的結(jié)構(gòu)信息持續(xù)優(yōu)先處理很容易造成偏差延續(xù),導(dǎo)致修復(fù)效果不理想。文獻(xiàn)[8]提出了改進(jìn)優(yōu)先級(jí)的方法解決偏差問(wèn)題,取得了一定的成效,具有較好的視覺(jué)效果。
目前的圖像修復(fù)算法主要都是針對(duì)大塊信息缺失(文獻(xiàn)[8-11])或小區(qū)域破損(文獻(xiàn)[12-14])的圖像,但是對(duì)既含有劃痕又含有大塊缺失信息的圖像卻很少涉及,如果分別用CDD算法和Criminisi算法修復(fù)此類圖像時(shí),都會(huì)產(chǎn)生一些不好的視覺(jué)效果:CDD算法修復(fù)大塊區(qū)域會(huì)產(chǎn)生模糊現(xiàn)象,并且會(huì)有一些修復(fù)不到的孤立點(diǎn);Criminisi算法修復(fù)會(huì)優(yōu)先處理劃痕,再修復(fù)大塊區(qū)域時(shí)會(huì)產(chǎn)生錯(cuò)誤信息的累積。本文分析了這些算法,找到造成修復(fù)效果不佳的原因,在此基礎(chǔ)上,提出一種將強(qiáng)化細(xì)節(jié)的自適應(yīng)直方圖均衡化、CDD模型、改進(jìn)的Criminisi算法及形態(tài)學(xué)濾波結(jié)合起來(lái)的修復(fù)方法。
CDD模型是建立在TV模型的基礎(chǔ)上,而TV模型[3]是在約束條件下求泛函極值的問(wèn)題:
如圖1所示,這里Ω為待修復(fù)區(qū)域,Φ為待修復(fù)區(qū)域周圍完好相鄰的區(qū)域,I=Φ∪Ω為整幅圖像,u為原始圖像,0u為破損圖像,▽表示梯度,λ表示Lagrange乘子。
圖1 圖像受損區(qū)域及其鄰域
根據(jù)變分原理,可求得與之對(duì)應(yīng)的Euler-Lagrange方程為:
其中:
為解決 TV模型中的不連續(xù)問(wèn)題,Chan和Shen[5]在TV模型的基礎(chǔ)上提出CDD模型,即將TV模型的擴(kuò)散系數(shù)修改為此處,g的定義為:
由于這種選擇可以在大曲率處擴(kuò)散變強(qiáng),小曲率處擴(kuò)散逐漸消失,因此,CDD修復(fù)模型為:
Criminisi等[6]提出的基于樣本紋理合成的圖像修補(bǔ)方法可以概括為以下3個(gè)步驟。
2.1 計(jì)算待修補(bǔ)塊的優(yōu)先權(quán)
圖2中,I表示整幅圖像,Ω表示待修復(fù)區(qū)域,?Ω代表其輪廓,Φ表示已知區(qū)域,且有 IΦ= ?Ω。
圖2 Criminisi算法示意圖
對(duì)于以?Ω上的點(diǎn)p為中心的目標(biāo)塊pΨ,定義其優(yōu)先權(quán)為:
上式中,
其中 C(p)稱為置信度項(xiàng),規(guī)定優(yōu)先填充那些含有較多已知像素部分的模塊,是Ψp的面積,一般C(p)的初始化取值為:
D(p)為數(shù)據(jù)項(xiàng),它反映邊緣前沿的等照度強(qiáng)度,具有較強(qiáng)結(jié)構(gòu)特征的部分優(yōu)先修復(fù)。 ▽Ip⊥表示p點(diǎn)的等照度線的方向和強(qiáng)度,np表示待修補(bǔ)區(qū)域輪廓的單位外法線方向,α為歸一化因子,這里取255。
本文采用的 Criminisi算法為改進(jìn)優(yōu)先權(quán)的Criminisi算法[8],取優(yōu)先權(quán)為:
這里 C(p), D(p)滿足式(5),設(shè){Ωi}(0 ≤i≤ N)是每執(zhí)行一次修復(fù)之后新的待修復(fù)序列,則令:
2.2 搜索最佳匹配塊
在?Ω上找到 ()Pp值最大的目標(biāo)塊?pΨ后,然后在已知區(qū)域內(nèi)搜索此目標(biāo)塊的最佳匹配塊?qΨ,目標(biāo)塊與最佳匹配塊有如下匹配準(zhǔn)則:
其中,d (Ψp?,Ψq)表示目標(biāo)塊Ψp?和樣本塊Ψq中對(duì)應(yīng)已知像素的顏色差的平方和,I,I′分別對(duì)應(yīng)塊Ψp?和Ψq中的已知像素點(diǎn),則 d(Ψp?,Ψq)可由下式表示:
2.3 置信度的更新
在找到最佳匹配塊?qΨ后,將塊?qΨ中的像素對(duì)應(yīng)復(fù)制到目標(biāo)塊?pΨ中的未知像素點(diǎn),該目標(biāo)塊內(nèi)未知像素點(diǎn)轉(zhuǎn)變?yōu)橐阎袼攸c(diǎn),因此這些點(diǎn)的置信度需要更新為:
重復(fù)上述的3個(gè)步驟,直至待修復(fù)區(qū)域被填完為止。
直方圖均衡化是由圖像灰度演繹得出的一種增強(qiáng)圖像整體對(duì)比度的增強(qiáng)技術(shù),但是這種變換擴(kuò)大圖像的動(dòng)態(tài)范圍卻是以犧牲圖像的細(xì)節(jié)為代價(jià)的,因此本文將采用可以強(qiáng)化細(xì)節(jié)的自適應(yīng)直方圖均衡化[16],不僅擴(kuò)大了圖像的動(dòng)態(tài)范圍,還可以抑制圖像噪聲,即先保存圖像細(xì)節(jié),再對(duì)圖像進(jìn)行直方圖均衡化處理,最后再把細(xì)節(jié)加在處理后的圖像上。
根據(jù)文獻(xiàn)[15-16],強(qiáng)化細(xì)節(jié)的自適應(yīng)直方圖均衡化的原理可以用以下公式來(lái)說(shuō)明:
上式中, xi,j為原始圖像的灰度值, xi′,j為處理后圖像的灰度值, mi,j為以點(diǎn) xi,j為中心的的圖像窗領(lǐng)域內(nèi)所有像素點(diǎn)的灰度均值, H(xi,j)表示對(duì)點(diǎn) xi,j進(jìn)行直方圖均衡化操作,而 k(xi,j? mi,j)是用于增強(qiáng)所選圖像的局部對(duì)比度即強(qiáng)化圖像的細(xì)節(jié),為了使增強(qiáng)后的圖像不超過(guò)[0,255]圖像的灰度值范圍,上式增加了判別條件。
在式(6)中,k為自適應(yīng)參量,通過(guò)自適應(yīng)改變的取值,可以在增強(qiáng)圖像細(xì)節(jié)的同時(shí)抑制掉圖像背景中的噪聲。為了實(shí)現(xiàn)這個(gè)目的,將參量的表達(dá)式定義為:
上式中,σi2,j為一個(gè)選定的大小為n×n方形窗W內(nèi)的灰度方差, σn2為整幅圖像的噪聲方差,k′為根據(jù)所選圖像的實(shí)際噪聲狀況決定的比例系數(shù),其數(shù)值不宜過(guò)大也不宜過(guò)小。
在圖像修復(fù)前用強(qiáng)化細(xì)節(jié)的直方圖均衡化處理,可以擴(kuò)大圖像的動(dòng)態(tài)范圍,范圍越大,層次感越強(qiáng),有利于CDD模型的擴(kuò)散和最佳匹配塊的選擇,但是不可避免的會(huì)降低圖像的峰值信噪比,因此本文最后把修復(fù)后的圖像,對(duì)應(yīng)于待修復(fù)區(qū)域位置上的像素填充到原待修復(fù)圖像上,以降低對(duì)原圖像的影響。
相對(duì)于本文算法,盡管Criminisi算法可以修復(fù)大塊破損的圖像也可以修復(fù)劃痕區(qū)域,但由于劃痕區(qū)域在利用塊搜索時(shí)將浪費(fèi)大量時(shí)間,同時(shí)由于破損處較多,可能導(dǎo)致無(wú)完整塊進(jìn)行填充,必將導(dǎo)致修復(fù)結(jié)果偏差,造成錯(cuò)誤信息的累積。因此本文先人工提取圖像掩膜信息,利用形態(tài)學(xué)運(yùn)算,先腐蝕再膨脹的方法分離出劃痕區(qū)域與大塊信息缺失區(qū)域的掩膜信息;然后利用CDD模型對(duì)劃痕區(qū)域修復(fù);再利用改進(jìn)的Criminisi算法進(jìn)行大塊信息缺失區(qū)域的填充,最后把修復(fù)后的圖像對(duì)應(yīng)像素填補(bǔ)到待修復(fù)圖像中。實(shí)驗(yàn)結(jié)果證明改進(jìn)算法具有良好的視覺(jué)效果。
算法流程可以分為三部分,第一部分:對(duì)圖像進(jìn)行強(qiáng)化細(xì)節(jié)的自適應(yīng)直方圖均衡化(步驟1~2);第二部分:分離出劃痕區(qū)域與大塊信息缺失區(qū)域的掩膜,并用CDD算法對(duì)劃痕區(qū)域處理(步驟3~4);第三部分:用改進(jìn)的Criminisi算法進(jìn)行后續(xù)處理(步驟5~9)。
本文算法具體如下:
步驟 1.讀入受損圖像,確定自適應(yīng)均衡化操作所需要的方形窗W的大小(本文選取W為5×5)和比例系數(shù)k′的值(本文選取 k′= 7);
步驟2.計(jì)算窗內(nèi)的噪聲方差 σi2,j,整幅圖像的噪聲方差 σn2及窗內(nèi)像素點(diǎn)的平均灰度值 mi,j,帶入式(7),即計(jì)算出 xi′,j;
步驟 3.確定圖像的掩膜信息,根據(jù)形態(tài)學(xué)運(yùn)算[17]分離出劃痕區(qū)域與大塊信息缺失區(qū)域,并分別繪制其掩膜圖;
步驟4.根據(jù)步驟3找出劃痕區(qū)域的掩膜,利用CDD算法修復(fù)(本文CDD算法中迭代次數(shù)均取n= 1000次);
步驟 5.找出分離后待修復(fù)大塊區(qū)域的邊界?Ωi( ?Ω0=?Ω),設(shè)置(初始時(shí) i= 0),如果 Ωi= φ,退出循環(huán);
步驟6.計(jì)算優(yōu)先權(quán) P(p), ?p ∈?Ωi;
步驟 7.找出具有最大優(yōu)先權(quán)值的待修復(fù)區(qū)域塊?pΨ ,即
步驟8.計(jì)算最佳匹配塊Ψq?∈Φ,并把Ψq?中對(duì)應(yīng)的圖像信息復(fù)制到中;
Ψ?p∩Ω
步驟9.i=i+1,重復(fù)步驟5~8;
步驟10.把修復(fù)后的圖像對(duì)應(yīng)于掩膜的部分取出填補(bǔ)到待修復(fù)圖像中。
本文實(shí)驗(yàn)用 Matlab 2012b作為工具,在 Intel酷睿 2處理器(2.0 GHz),2 G內(nèi)存的 PC機(jī)上實(shí)現(xiàn)的。
實(shí)驗(yàn)將本文的算法與本文去掉步驟1和步驟2的算法(以下簡(jiǎn)稱算法1)、CDD算法、Criminisi算法及文獻(xiàn)[8]的算法分別進(jìn)行了比較,如圖 3~4所示。
圖3是圖像修復(fù)常用的蹦極圖,圖3(b)出現(xiàn)偏差延續(xù),存在明顯的不連續(xù)性;圖3(c)~(e)(本文取λ1= λ2= 1, λ3= 3)屋頂及屋頂上下都存在一定的偏差,不能自然地體現(xiàn)屋頂?shù)奶卣?;圖3(d)在大塊信息缺失區(qū)域產(chǎn)生模糊現(xiàn)象,白色圈出來(lái)的位置為沒(méi)有修復(fù)到的孤立點(diǎn);圖3(f)很好地解決了以上出現(xiàn)的問(wèn)題,取得了較好的視覺(jué)效果。
圖3 蹦極修復(fù)效果比較圖
如圖4可見(jiàn),圖4(b)和4(c)出現(xiàn)偏差延續(xù)現(xiàn)象,狒狒的鼻子上均有明顯的黑色部分;圖4(d)在大塊信息缺失處出現(xiàn)模糊現(xiàn)象;圖4(e)保證了圖像在大范圍上的視覺(jué)效果,但鼻子的左右兩側(cè)均稍有瑕疵,紋理不自然;圖4(f)顯示本文算法克服了上述算法的種種瑕疵,視覺(jué)效果最好。
圖4 狒狒修復(fù)效果比較圖
本文選取了兩幅具有代表性的圖片進(jìn)行修復(fù),通過(guò)實(shí)驗(yàn)對(duì)比與其他算法的修復(fù)時(shí)間,從表1中可以看出,本文算法相對(duì)于其他3種算法有效地縮短了時(shí)間,雖然CDD算法時(shí)間最短,但是在大塊區(qū)域時(shí)有明顯的模糊現(xiàn)象。表2展現(xiàn)了本文算法與其他算法的峰值信噪比(peak signal-to-noise ratio, PSNR)比較。
表1 不同算法修復(fù)時(shí)間比較(s)
表2 不同修復(fù)算法的峰值信噪比比較(dB)
本文簡(jiǎn)單介紹了CDD模型及Criminisi算法,分別分析了這兩類算法的特點(diǎn),因此在對(duì)待既含有劃痕又含有大塊破損的區(qū)域的圖像,區(qū)分對(duì)待不同的待修復(fù)區(qū)域。實(shí)驗(yàn)結(jié)果表明,本文提出的算法不僅在處理劃痕區(qū)域與大區(qū)域破損處能夠較好的結(jié)合,而且Criminisi算法還能較好的處理CDD算法修復(fù)不到的孤立點(diǎn),縮短修復(fù)時(shí)間,修復(fù)后的視覺(jué)效果更好。由于目前對(duì)圖像修復(fù)的質(zhì)量,均是依靠人眼主觀評(píng)價(jià),未來(lái)希望對(duì)修復(fù)質(zhì)量的定量客觀評(píng)價(jià)進(jìn)行研究。
[1] 張紅英, 彭啟琮. 數(shù)字圖像修復(fù)技術(shù)綜述[J]. 中國(guó)圖象圖形學(xué)報(bào), 2007, 12(1): 1-10.
[2] Bertalmio M, Sapiro G, Caselles V, Ballester C. Image inpainting [C]//SIGGRAPH 2000, Proceedings of the 27thAnnual Conference on Computer Graphics, New Orleans, USA: ACM, 2000: 417-424.
[3] Chan T, Shen J. Mathematical models for local non-texture inpainting [J]. SIAM Journal on Applied Mathematics, 2002, 62(3): 1019-1043.
[4] Rudin L I, Osher S, Faterni E. Nonlinear total variation based noise removal algorithms [J]. Physica D, 1992, 60: 259-268.
[5] Chan T, Shen J. Non-texture inpainting by curvature-driven diffusions (CDD) [J]. Journal of Visual Communication and Image Representation, 2001, 12(4): 436-496.
[6] Criminisi A, Perez P, Toyama K. Object removal by exemplar-based inpainting [C]//Proc Conf Comp Vision Pattern Rec, Madison WI, 2003: 721-728.
[7] Criminisi A, Perez P, Toyama K. Region filling and object removal by exemplar-based image inpainting [J]. IEEE Transactions on Image Processing, 2004, 13(9): 1200-1212.
[8] 黃淑兵, 朱曉臨, 徐云云, 朱 坤. 一種改進(jìn)的基于紋理合成的圖像修復(fù)算法[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2011, 34(2): 313-320.
[9] 任 澍, 唐向宏, 康佳倫. 利用紋理和邊緣特征的Criminisi改進(jìn)算法[J]. 中國(guó)圖象圖形學(xué)報(bào), 2012, 17(9): 1085-1091.
[10] Li B R, Qi Y, Shen X K. An image inpainting method [C]//Computer Aided Design and Computer Graphics, 2005. Ninth International Conference on. IEEE, 2005: 6.
[11] Wang Min qin. A novel image inpainting method based on image decomposition [J]. Procedia Engineering, 2011, 15: 3733-3738.
[12] Bugeau A, Bertalmio M, Caselles V, Sapiro G. A comprehensive framework for image inpainting [J]. IEEE Transactions on Image Processing, 2010, 19(10): 2634-2645.
[13] 劉庚龍, 檀結(jié)慶. 一種改進(jìn)的整體變分圖像修復(fù)方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(7): 194-196.
[14] 趙顏偉, 李象霖. 基于 CDD模型的快速圖像修復(fù)算法[J]. 計(jì)算機(jī)仿真, 2008, 25(10): 223-227.
[15] 任 慧, 李新華, 朱逸婷. 自適應(yīng)直方圖均衡化改進(jìn)的全變分圖像修復(fù)[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用, 2013, 22(6): 98-101.
[16] 宋 剛, 劉瑤華. 一種能強(qiáng)化細(xì)節(jié)的自適應(yīng)直方圖均衡法[J]. 山東工業(yè)大學(xué)學(xué)報(bào), 1999, 29(1): 81-93.
[17] Rafael C G, Richard E W. 數(shù)字圖像處理[M]. 3版. 阮秋琦, 阮宇智, 譯. 北京: 電子工業(yè)出版社, 2011: 402-493.
An Image Inpainting Algorithm Combined of CDD Model and Criminisi Algorithm
Jiang Ping, Zhang Jin
(School of Mathematics, Hefei University of Technology, Hefei Anhui 230009, China)
Aiming at images with a lot of missing information and scratches, this paper puts forward a new restoration algorithm by combining the advantages of CDD model and Criminisi algorithm. Specifically, this algorithm first adopts the equalized operation of detail-oriented and self-adaptive histogram to expand the dynamic range of the images, and then utilizes morphology operators to separate the scratch regions and large areas in the images that need to be restored. Subsequently, CDD model is applied to restore the scratches and then the improved priority Criminisi algorithm is used to implement subsequent restoration. Finally, the restored images corresponding to the pixel of missing areas are filled into the regions of images need restoration. As the experimental results indicate, the improved algorithm has overcome the possible deviation continuation problems in current algorithm and can make the restored images more consistent with people’s visual effect.
CDD model; Criminisi algorithm; image inpainting; equalization of self-adaptive histogram; morphology operators
TP391
A
2095-302X(2014)05-0741-06
2014-03-03;定稿日期:2014-06-11
國(guó)家自然科學(xué)基金資助項(xiàng)目(11471093)
江 平(1972–),女,安徽安慶人,副教授,博士。主要研究方向?yàn)镃AGD、圖像修復(fù)。E-mail:jiang_hfut@126.com