王茜艷,陳力,李萌
(汕頭大學(xué)工學(xué)院,廣東汕頭515063)
基于插值的圖像修復(fù)算法
王茜艷,陳力,李萌
(汕頭大學(xué)工學(xué)院,廣東汕頭515063)
目前,針對(duì)小區(qū)域缺損的圖像修復(fù)算法中,大多采用基于迭代的修復(fù)算法,然而這些效果較好的圖像修復(fù)算法,其時(shí)間復(fù)雜度一般都比較大.本文通過插值的方法,利用破損區(qū)域與周邊鄰域的有效信息之間的相關(guān)性,提出改進(jìn)的基于FMM(快速行進(jìn))的圖像修復(fù)算法;調(diào)用僅適用于被檢測(cè)到的高局部活躍的像素,提出基于LMMSE(線性最小均方誤差估計(jì))插值的圖像修復(fù)算法.實(shí)驗(yàn)結(jié)果表明,提出的兩種算法分別與FMM算法和TV(整體變分法)算法相比,在整體上其修復(fù)效果和效率都具有明顯的優(yōu)勢(shì).
圖像修復(fù);快速行進(jìn)法;鄰近像素;線性最小均方誤差估計(jì);整體變分法
圖像修復(fù)是根據(jù)圖像中信息丟失部分周圍的已知信息,對(duì)該部分進(jìn)行重建,其主要目的是對(duì)破損的圖像進(jìn)行修復(fù),以構(gòu)造人眼主觀系統(tǒng)可以接受的圖像[1].數(shù)字圖像修復(fù)的研究發(fā)展至今,從方法上可以大致分為基于非紋理和基于紋理合成兩大類,按破損區(qū)域則可以大致分為小尺度缺損的圖像修復(fù)和大區(qū)域缺損圖像的修復(fù).其中基于非紋理的圖像修復(fù)方法主要針對(duì)小尺度缺損的圖像,大概分為基于變分PDE(偏微分方程)的圖像修復(fù)方法和基于插值的圖像修復(fù)方法.基于紋理修復(fù)的主要針對(duì)的是大區(qū)域缺損的圖像,大概包含兩種修復(fù)技術(shù):一種是基于圖像分解的修復(fù)技術(shù),如文獻(xiàn)[2]將圖像分解為結(jié)構(gòu)部分和紋理部分,利用已有的算法分別對(duì)其進(jìn)行修補(bǔ)和填充,最后把這兩部分修復(fù)結(jié)果疊加起來,得到修復(fù)圖像;另一種方法如文獻(xiàn)[3-4]采用樣本塊合成技術(shù)來填充缺損的信息.
目前,針對(duì)小尺度缺損的圖像修復(fù)模型和算法中,文獻(xiàn)[5-7]采用基于高階偏微分的模型進(jìn)行多次迭代修復(fù).這些圖像修復(fù)效果較好的算法,大多都是以較大的時(shí)間復(fù)雜度為代價(jià),盡管可以得到較好的修復(fù)效果,但其耗時(shí)較嚴(yán)重.而在實(shí)際應(yīng)用時(shí),通常對(duì)處理速度有一定的要求,因此,研究快速有效地修復(fù)破損圖像的算法具有重大意義[8].基
于插值的修復(fù)算法在小區(qū)域破損圖像的快速修復(fù)中,具有一定的優(yōu)勢(shì).其中Telea等人[9]提出的快速行進(jìn)法,盡管在修復(fù)效率上有很大的改進(jìn),但其對(duì)強(qiáng)弱邊緣的保持能力不足.因此,若分析其問題原因并將其改進(jìn),在快速修復(fù)圖像的過程中保持破損區(qū)域的邊緣強(qiáng)度,是非常有意義的.然而,利用文獻(xiàn)[10]提出的由約束最小二乘方法改進(jìn)的圖像恢復(fù)方法中的迭代估計(jì)思想,可在破損區(qū)域內(nèi)對(duì)其邊緣像素進(jìn)行線性最小二乘誤差迭代估計(jì),以達(dá)到圖像的快速修復(fù).在文獻(xiàn)[11]中,有人通過定向?yàn)V波和數(shù)據(jù)融合邊緣引導(dǎo)提出一種保持邊緣結(jié)構(gòu)的線性最小均方誤差估計(jì)的圖像插值技術(shù),因缺失區(qū)域的樣本在其邊緣方向上與其鄰近有較高的相關(guān)性,即把缺失樣本附近區(qū)分為兩個(gè)正交方向上的子集,通過結(jié)合兩個(gè)定向的線性最小均方誤差估計(jì),得到高分辨率圖像.因此,若將其應(yīng)用到多個(gè)小塊區(qū)域缺失的圖像修復(fù)中,對(duì)保持缺損圖像的邊緣信息和快速修復(fù)都是具有重大意義.
因此,本文將基于插值的圖像修復(fù)技術(shù),從以下兩個(gè)方面進(jìn)行研究:1)針對(duì)快速行進(jìn)(FMM)修復(fù)算法中對(duì)強(qiáng)弱邊緣的保持能力不足,分析其問題原因并將其改進(jìn),提出一種新的基于FMM的修復(fù)算法,結(jié)合等照度線的擴(kuò)散方向,定義新的權(quán)函數(shù)以保持邊緣信息.2)將結(jié)合LMMSE的方法對(duì)缺損圖像進(jìn)行修復(fù).本文將把它應(yīng)用到多個(gè)小塊區(qū)域缺失的圖像修復(fù)中,調(diào)用僅適用于被檢測(cè)到的高局部活躍的像素進(jìn)行線性最小均方誤差估計(jì),在很好的保持邊緣清晰的前提下,快速的修復(fù)破損圖像.該方法雖然在破損區(qū)域比較大的圖像中沒有優(yōu)勢(shì),但其在針對(duì)較規(guī)則或因傳輸過程中而導(dǎo)致的缺損圖像上的效果非常顯著,相對(duì)于其他方法而言,其在圖像修復(fù)的速度和對(duì)破損區(qū)域邊緣的處理上都很有優(yōu)勢(shì).
FMM算法通過快速行進(jìn)法,對(duì)缺損區(qū)域逐步修復(fù),其主要利用待修復(fù)像素與周邊鄰域有效信息的相關(guān)性來定義權(quán)函數(shù).快速行進(jìn)法的基本思想是采用時(shí)間函數(shù)T(x,y)的形式模擬曲線演化過程,將修復(fù)區(qū)域邊緣逐步往里推進(jìn),直到破損區(qū)域完全修復(fù)[12].假設(shè)I為待修復(fù)的圖像,若記Ω為待修復(fù)圖像I的缺損區(qū)域,則鄣Ω為缺損區(qū)域Ω的邊界,點(diǎn)p位于缺損區(qū)域Ω內(nèi),且設(shè)p點(diǎn)的梯度方向?yàn)镹.FMM算法為方便計(jì)算T值,將圖像的像素分為三種狀態(tài):缺損區(qū)域邊界上的像素、邊界內(nèi)的像素和邊界外的像素,每種狀態(tài)的像素都有一個(gè)對(duì)應(yīng)的到達(dá)時(shí)間T.其本質(zhì)是利用擴(kuò)散方程求出缺損區(qū)域邊界內(nèi)部所有的點(diǎn)到邊界上的距離T,其中邊界內(nèi)部的點(diǎn)T的初始值為106,而待修復(fù)邊界和邊界外點(diǎn)的T初始值為0,并將各個(gè)像素設(shè)為其對(duì)應(yīng)的狀態(tài),最后根據(jù)計(jì)算出來T值,按照離缺損區(qū)域邊界越近(即T值越?。较刃迯?fù)的順序進(jìn)行修復(fù),直到缺損區(qū)域Ω內(nèi)的點(diǎn)完全修復(fù).
圖1 修復(fù)模型
由于FMM算法設(shè)計(jì)的權(quán)函數(shù)沒有考慮其等照度方向,致使邊緣信息保持不佳,因
此其權(quán)函數(shù)的設(shè)計(jì)不夠合理;且對(duì)已知鄰域信息采取的信任是相同的,導(dǎo)致對(duì)破損區(qū)域往里逐步推進(jìn)修復(fù)時(shí),產(chǎn)生誤差的累積,使修復(fù)后的破損區(qū)域比較模糊[13].本文在設(shè)計(jì)權(quán)函數(shù)時(shí),考慮加入等照度線方向,并引入自適應(yīng)插值的置信度因子,對(duì)破損區(qū)域的像素點(diǎn)插值.即當(dāng)缺失像素進(jìn)行插值時(shí),對(duì)其鄰域的原始像素全部信任,而對(duì)經(jīng)修復(fù)得到的像素部分信任,由此避免誤差累積導(dǎo)致的修復(fù)后破損區(qū)域模糊現(xiàn)象.
2.1 權(quán)函數(shù)設(shè)計(jì)
根據(jù)圖1的修復(fù)模型,未知像素Ω的點(diǎn)p是由已知鄰域信息Bε(p)的點(diǎn)q決定,所以,p點(diǎn)的像素可由Bε(p)中所有的點(diǎn)加權(quán)得出,
由于FMM中設(shè)計(jì)的加權(quán)函數(shù)W(p,q)是采用切線方向N(p)來評(píng)價(jià)已知鄰域像素點(diǎn)與缺失像素點(diǎn)的相關(guān)性程度,即保證了距離p點(diǎn)法線方向越接近的像素點(diǎn)對(duì)p點(diǎn)的貢獻(xiàn)越大[8].
我們定義權(quán)函數(shù)為:
N(p,q)為幾何距離因子,表示已知鄰域信息內(nèi)與p距離越近的點(diǎn)其貢獻(xiàn)越大;R(p,q)為方向因子,可以明顯看出它與FMM的方向因子有區(qū)別,即利用等照度方向的信息進(jìn)行傳輸,考慮到了圖像已知區(qū)域的結(jié)構(gòu)特征,使離等照度線越近的點(diǎn)的貢獻(xiàn)越大;L(q)為水平距離因子,表示離經(jīng)過P點(diǎn)的缺失圖像邊界越近的已知像素,對(duì)P點(diǎn)的貢獻(xiàn)越大.其中為p點(diǎn)的等照度方向矢量,其實(shí)際上是由p點(diǎn)附近已知鄰域信息所有像素的等照度方向共同決定的,因此,可定義為
2.2 置信度因子
破損區(qū)域修復(fù)都是通過其周圍已知鄰域的像素點(diǎn)決定.因此,在其修復(fù)的過程中,其周圍已知像素越多,則越能得到更好的修復(fù)值,且被修復(fù)的點(diǎn)也能更好的確定其他待修復(fù)點(diǎn)的灰度值,以此達(dá)到整體上的修復(fù).本文將建立一種自適應(yīng)的可信度模型M,將破損區(qū)域附近所有像素分為已知像素1(原始)、已知像素2(修復(fù)后)和未知像素點(diǎn)三大類,初始化時(shí),將所有的已知像素1置為1,未知像素點(diǎn)置為0,且選取矩陣R進(jìn)行掩膜,求出已知像素2的值,如圖2所示.
本文以p為中心,ε為中心到邊界的距離,選取修復(fù)時(shí)以大小為(2ε+1)×(2ε+1)小方窗ψp的矩陣,模板選取ε為2的方窗,對(duì)可信度模型M進(jìn)行掩膜,以計(jì)算出已知像素2(修復(fù)后)的像素點(diǎn)的可信度,掩膜后的結(jié)果存于矩陣P.
圖2 缺損圖像掩膜過程
則矩陣P中元素表明圖像中相應(yīng)位置的像素點(diǎn)中周圍已修復(fù)像素的相對(duì)個(gè)數(shù)[15],且0≤P(i,j)≤1,P(i,j)的值越大,則表明破損圖像中(i,j)點(diǎn)所在的5×5鄰域內(nèi)的已知像素越多.如果P(i,j)=1,則表明點(diǎn)(i,j)所在的小方窗鄰域全部為已知像素,即處于破損區(qū)域的外部;如果0<P(i,j)<1,表明點(diǎn)(i,j)所在的小方窗鄰域內(nèi)既有已知像素也有未知像素,即處于破損區(qū)域的邊緣;如果P(i,j)=0,表明點(diǎn)(i,j)所在的小方窗鄰域全部為未知像素,即處于破損區(qū)域的內(nèi)部.
2.3 修復(fù)步驟
通過對(duì)權(quán)函數(shù)和自適應(yīng)插值的置信度因子分析,改進(jìn)的FMM修復(fù)算法具體過程如下.
(1)初始值設(shè)定
①根據(jù)水平距離因子L(q),初始化T(q)的值.T被標(biāo)識(shí)為三種狀態(tài),即設(shè)缺損區(qū)域邊界上的像素和邊界外的像素的T值為0,而邊界內(nèi)的像素取106(原本設(shè)為∞);
②將待修復(fù)圖像進(jìn)行標(biāo)記.待修復(fù)圖像輸入為x0,將標(biāo)記過缺損區(qū)域塊的圖像設(shè)為x1,對(duì)輸入的x1圖像取反,表示標(biāo)記缺損以外的區(qū)域,且令可信度模型
(2)像素點(diǎn)修復(fù)過程
①根據(jù)模板R對(duì)可信度模型M進(jìn)行掩膜,且保存于優(yōu)先度矩陣P中;
②找出待修復(fù)區(qū)域中P值最大的像素點(diǎn)f(m,n);
③利用式(1)修復(fù)點(diǎn)f(m,n),同時(shí)將p點(diǎn)值更新;
④更新M值,將上一步修復(fù)完成的該像素點(diǎn)的M值標(biāo)記為1,即令M(m,n)=1,x1(m,n)=0;
⑥重復(fù)②~④的步驟,直至缺損區(qū)域完全修復(fù)為止,輸出處理過的圖像x0.
3.1 LMMSE插值
基于插值的圖像修復(fù)技術(shù)主要是根據(jù)破損區(qū)域周圍鄰近的像素點(diǎn)的相關(guān)性,采用一定的修復(fù)順序進(jìn)行加權(quán)或迭代修復(fù).本文取多個(gè)小塊區(qū)域缺失的圖像,利用LMMSE對(duì)
待修復(fù)的圖像Dh(m,n)中的破損區(qū)域沿著兩個(gè)方向進(jìn)行插值:45°方向和135°方向,分別對(duì)缺損像素進(jìn)行線性最小均方誤差估計(jì).通過一些線性方法對(duì)這兩個(gè)方向插值的結(jié)果用D贊45(m,n)和D贊135(m,n)表示.考慮到以這兩個(gè)方向作為缺失像素的插值輸出時(shí),可能會(huì)產(chǎn)生的噪聲測(cè)量V45和V135.
圖3 對(duì)像素進(jìn)行45°和135°方向插值
可寫成以下式子進(jìn)行估計(jì):
將上式重寫成矩陣形式Y(jié)=1×Dh+V.
在實(shí)際應(yīng)用中,經(jīng)常用LMMSE替代MMSE,因?yàn)檫@個(gè)估計(jì)在最小均方誤差中,必須知道缺損圖像的先驗(yàn)信息.而實(shí)現(xiàn)LMMSE,只需要計(jì)算Dh和Y的一階統(tǒng)計(jì)和二階統(tǒng)計(jì),他們也可以是自適應(yīng)估計(jì)的.因此,Dh的LMMSE可計(jì)算為[16]:
其中,μh=E[Dh],協(xié)方差運(yùn)算符
方差運(yùn)算符Cov(A)=Cov(A,A).Dh通過LMMSE運(yùn)算,融合兩個(gè)定向測(cè)量提供的信息.根據(jù)文獻(xiàn)[11]可假設(shè)v是零均值,并且與Dh無關(guān),則可由(8)推出,
圖4 對(duì)Dh(m,n)附近像素的迭代插值
且Var(V45)和Var(V135)可估算為:
3.2 LMMSE修復(fù)步驟
通過以上分析,本文基于LMMSE的圖像插值修復(fù)方法的具體過程如下:
(1)輸入待修復(fù)圖像x0和將待修復(fù)圖像中缺損區(qū)域標(biāo)記的圖像x1,檢測(cè)并標(biāo)記x1圖像中缺損區(qū)域的邊緣;
(2)通過(6)和(11)分別對(duì)破損塊進(jìn)行45°和135°方向上的定向融合插值;
(3)估計(jì)出相應(yīng)的RV,根據(jù)式(10),對(duì)標(biāo)記圖像x1待修復(fù)區(qū)域中的像素點(diǎn)修復(fù)進(jìn)行插值迭代修復(fù);
(4)與上一節(jié)中的FMM改進(jìn)算法和TV算法進(jìn)行PSNR和時(shí)間上的比較.
本文的兩種算法都是用Matlab R2014a在Core(TM)2 Duo,1.96 GB內(nèi)存的PC機(jī)上實(shí)現(xiàn)的.實(shí)驗(yàn)中將本文提出的兩種算法分別在修復(fù)效果和修復(fù)時(shí)間上與FMM算法、TV算法進(jìn)行對(duì)比,快速的圖像修復(fù)算法主要用于小尺度破損的圖像,因此本文的實(shí)驗(yàn)圖片Lena和Peppers都是通過對(duì)正常圖像添加人工劃痕得出,如圖5(a)和(e),而試驗(yàn)圖片Lena_mask則是通過模擬傳輸過程中導(dǎo)致的缺損圖像而得出的多塊小區(qū)域破損圖,如圖6(a).本文采用PSNR來對(duì)圖像修復(fù)的效果進(jìn)行評(píng)價(jià),
其中,
MSE是表示原始圖像與缺損區(qū)域修復(fù)后的圖像之間的均方誤差,N為圖像的整體像素?cái)?shù),xi為原始圖像的像素值,yi為缺損區(qū)域修復(fù)后的輸出圖像x0的像素值.
本文給出了三種圖像(Lena圖像、Peppers圖像和Lena_mask圖像),利用不同修復(fù)算法得出的對(duì)比結(jié)果如圖5所示.本文利用提出的FMM改進(jìn)算法進(jìn)行實(shí)驗(yàn)時(shí),Bε(p)取為以p點(diǎn)為中心的鄰域窗口.由于改進(jìn)的FMM算法加入等照度線方向,且當(dāng)缺失像素使用經(jīng)修復(fù)過的像素進(jìn)行自適應(yīng)插值時(shí),對(duì)其鄰域的原始像素全部信任,而對(duì)經(jīng)修復(fù)過的像素部分信任,因此其在修復(fù)效果上對(duì)于缺損區(qū)域邊緣的保護(hù)比較明顯;且引入自適應(yīng)插值的置信度因子對(duì)缺損區(qū)域的像素進(jìn)行順序選擇,與FMM的擴(kuò)散方程相比,其在修復(fù)時(shí)間上也更有優(yōu)勢(shì).表1列出了相應(yīng)的PSNR和修復(fù)時(shí)間T統(tǒng)計(jì)結(jié)果,P1和P2分別表示FMM算法和TV算法進(jìn)行修復(fù)后的PSNR,P3為通過改進(jìn)的FMM算法修復(fù)后的PSNR;T1和T2分別表示FMM算法和TV算法進(jìn)行修復(fù)所花費(fèi)的時(shí)間,T3為通過改進(jìn)的FMM算法修復(fù)后所花費(fèi)的時(shí)間.
表1 FMM算法、TV算法與改進(jìn)后FMM算法的修復(fù)結(jié)果對(duì)比
圖5 圖像修復(fù)結(jié)果1
而本文提出的基于LMMSE的插值修復(fù)算法,主要是根據(jù)破損區(qū)域周圍鄰近的像素
點(diǎn)的相關(guān)性,采用一定的修復(fù)順序進(jìn)行加權(quán)或迭代修復(fù).以Lena_mask為實(shí)驗(yàn)圖,表2列出了LMMSE算法和FMM算法、TV算法修復(fù)的結(jié)果對(duì)比,P1、P2、T1、T2與表1中的表示是一樣,P4和T4分別表示通過LMMSE的插值算法進(jìn)行修復(fù)后的PSNR和花費(fèi)的時(shí)間.從表1、表2中可以看出,綜合考慮修復(fù)效果和時(shí)間,本文提出的兩種算法比FMM和TV算法更具有優(yōu)勢(shì).
表2 FMM算法、TV算法與LMMSE插值算法的修復(fù)結(jié)果對(duì)比
圖6 圖像修復(fù)結(jié)果2
本文針對(duì)FMM算法修復(fù)可能導(dǎo)致的缺損區(qū)域修復(fù)后邊緣信息模糊問題,提出了一種改進(jìn)的FMM算法,結(jié)合等照度線方向,并引入自適應(yīng)插值的置信度因子對(duì)缺損區(qū)域的像素點(diǎn)插值.而在針對(duì)多塊小區(qū)域較規(guī)則破損的圖像修復(fù)時(shí),本文采用的是基于LMMSE的插值修復(fù)算法,調(diào)用僅適用于被檢測(cè)到的高局部活躍的像素進(jìn)行線性最小均方誤差估計(jì),因此,其可以更好的保持缺損區(qū)域的邊緣信息.實(shí)驗(yàn)結(jié)果表明,從整體上來說,本文提出的兩種算法都能在保持良好的修復(fù)效果時(shí),有效的提高了修復(fù)效率,達(dá)到快速且有效的修復(fù)目標(biāo).
[1]魏琳,陳秀宏.基于紋理方向的圖像修復(fù)算法[J].計(jì)算機(jī)應(yīng)用,2008,28(9):2315-2317.
[2]張紅英,彭啟琮.數(shù)字圖像修復(fù)技術(shù)綜述[J].中國圖象圖形學(xué)報(bào),2007,12(1):1-10.
[3]李景輝,張曉峰,馬燕.紋理合成在圖像修復(fù)中的應(yīng)用研究[J].計(jì)算機(jī)工程,2009,35(7):206-208.
[4]鄧悟,吳笛,騰奇志,等.基于區(qū)域填充的圖像修復(fù)算法研究[J].計(jì)算機(jī)與數(shù)字工程,2014,42(3):495-525.
[5]Bertalmio M,Sapiro G,Caselles V,et al.Image inpainting[C].Proceedings of ACMSIGGRAPH 2000. New York:ACM Press,2000:417-424.
[6]Chan T F,Shen J H.Mathematical models for local non-texture inpainting[J].SIAM J Appl Math,2002,62(3):1019-1043.
[7]Chan T F,Shen J H.Non-texture inpainting by Curvature-Driven Diffusions(CDD)[J].J Visual Comm Image Rep,2001,12(4):436-449.
[8]李開宇,孫玉剛.引入連續(xù)性強(qiáng)度和置信度因子的快速圖像修復(fù)[J].中國圖象圖形學(xué)報(bào),2012,17(4):465-470.
[9]Telea A.An image inpainting technique based on fast marching method[J].Graph Tools,2004,9(1):23-34.
[10]沈瑛,吳建華,吳祿慎.由約束最小二乘方法改進(jìn)的圖像恢復(fù)方法[J].數(shù)據(jù)采集與處理,2002,17(3):325-327.
[11]Zhang L,Wu X L.An edge-guided image interpolation algorithm via directional filtering and data fusion[J].IEEE Trans,on Image Processing,2006,15(8):2226-2238.
[12]康佳倫,唐向宏.一種基于FMM的帶方向圖像修復(fù)算法[J].杭州電子科技大學(xué)學(xué)報(bào):自然科學(xué)版,2012,32(5):147-150.
[13]孫玉剛.數(shù)字圖像修復(fù)技術(shù)研究[D].南京:南京航空航天大學(xué),2011.
[14]肖志云,張文霞,姜玉莉.基于快速行進(jìn)法的快速圖像修復(fù)算法[J].計(jì)算機(jī)應(yīng)用,2007,27(12):60-65.
[15]侯正信,何宇清,許微.一種快速的圖像修復(fù)算法[J].中國圖象圖形學(xué)報(bào),2007,12(10):1909-1912.
[16]Karmen E W,Su J K.Introduction to optimal estimation[M].London:Springer-Verlag,1999.
Image Inpainting Algorithm s Based on Interpolation
WANG Xiyan,CHEN Li,LI Meng
(Department of Electronic Engineering,College of Engineering,Shantou University,Shantou 515063,Guangdong,China)
For image repair in a small defect area,iterative algorithms with high computational complexity are commonly used.In this paper,an improved fast marching method(FMM)is proposed by using correlation information in the neighborhood of damaged area.A new image restoration algorithm based on LMMSE interpolation is also proposed by using pixels with high local activity only.Experimental results show that the proposed algorithms have improved performance as compared with the FMM method and integral variation method(TV).
image inpainting;fast marching method;adjacent pixel;linear minimum mean square error estimation;integral variation method
TN 919.8
A
1001-4217(2015)02-0072-08
2014-09-29
王茜艷(1990-),女,江西吉安人.研究方向:數(shù)字圖像處理.E-mail:12qywang@stu.edu.cn