面向圖像修復(fù)的域相似算法

何文韜，葉學(xué)義，何志偉，汪云路

杭州電子科技大學(xué)模式識別與信息安全實(shí)驗室，杭州310018

1 引言

圖像修復(fù)是指利用圖像中的已知信息，對圖像中遺失的或者損壞的區(qū)域按照一定的規(guī)則自動的進(jìn)行填充，并且盡可能地使修復(fù)后的圖像接近或達(dá)到原始圖像的視覺效果，使觀察者無法察覺[1-2]。近幾年來，該技術(shù)得到了國內(nèi)外專家的廣泛關(guān)注，并且將該技術(shù)深入到越來越多的應(yīng)用領(lǐng)域中，例如，將圖像修復(fù)技術(shù)應(yīng)用于去交織[3]、高效圖像壓縮[4]以及惡劣信道中JPEG圖像傳輸時丟失塊的恢復(fù)[5]等方面。

目前的數(shù)字圖像修復(fù)算法大致可以分為兩類：基于形態(tài)特征的圖像修復(fù)和基于紋理特征的圖像修復(fù)?；谛螒B(tài)特征的圖像修復(fù)中比較常用的方法是使用偏微分方程（PDE）進(jìn)行修復(fù)。Marcelo Bertalmio等人[2]提出了一種模擬博物館藝術(shù)家修復(fù)藝術(shù)作品過程的PDE圖像修復(fù)算法；隨后一些基于PDE的改進(jìn)算法和衍生模型也被提出，例如TV模型[6-7]、CDD模型[8]等。雖然大部分基于PDE的圖像修復(fù)算法對于劃痕等小尺度破損有較好的修復(fù)效果，但是它們的修復(fù)效率不高，而且對于破損區(qū)域較大或破損區(qū)域周圍紋理比較豐富的圖像，修復(fù)后一般都會出現(xiàn)部分失真和模糊[1，9]。

基于紋理特征的圖像修復(fù)算法的基本思路是通過從圖像完好區(qū)域中尋找與圖像受損區(qū)域最匹配的塊進(jìn)行修復(fù)。其中，Criminisi等人[10]提出一種基于優(yōu)先級的紋理合成修復(fù)算法，使得當(dāng)破損區(qū)域的周圍已知像素比例大且結(jié)構(gòu)特征明顯時，該破損區(qū)域被優(yōu)先修復(fù)。然而，現(xiàn)有的算法在尋找匹配塊的時候，大多數(shù)采用的都是全局搜索的方法。這種方法不但修復(fù)的時間很長，而且容易產(chǎn)生錯誤的匹配，影響了圖像修復(fù)的效率[11-12]。

在基于偏微分方程的圖像修復(fù)和基于紋理合成的圖像修復(fù)算法的基礎(chǔ)上，針對這些修復(fù)方法在修復(fù)效率上的不足，提出了一種新的基于域相似的圖像修復(fù)算法。本文算法先計算待修復(fù)區(qū)域邊界上的所有待修復(fù)點(diǎn)優(yōu)先級，然后按照優(yōu)先級從大到小的順序來設(shè)置圖像的修復(fù)順序，算法采用像素點(diǎn)鄰域的相似來衡量兩個像素點(diǎn)的相似程度，充分考慮了待修復(fù)像素的鄰域中已知信息對該像素的影響，而每個待修復(fù)點(diǎn)的值等于該點(diǎn)鄰域中所有滿足相似度要求的已知點(diǎn)像素值的求和平均。仿真實(shí)驗結(jié)果表明，在同等的修復(fù)區(qū)域和保證修復(fù)效果的條件下，本文算法顯著地縮短了修復(fù)時間，提高了圖像修復(fù)的效率。

2 域相似算法的修復(fù)

2.1 算法的基本框架

設(shè)I為待修復(fù)圖像，Ω為待修復(fù)區(qū)域，即目標(biāo)區(qū)域；?Ω為待修復(fù)區(qū)域的邊界；Φ表示待修復(fù)區(qū)域以外的部分(Φ=I-Ω)，即已知區(qū)域；邊界上待修復(fù)點(diǎn)p的鄰域記為Ψp，即以p點(diǎn)為中心的N×N的區(qū)域，如圖1所示。

圖1 待修復(fù)區(qū)域及像素的鄰域

修復(fù)從待修復(fù)邊界?Ω開始，由外向內(nèi)，逐層推進(jìn)，按照修復(fù)順序修復(fù)每一層上的待修復(fù)點(diǎn)。本文修復(fù)順序設(shè)定為優(yōu)先級從大到小的順序，因此先對待修復(fù)區(qū)域邊界點(diǎn)p計算優(yōu)先級（優(yōu)先級定義見2.2節(jié)），按照修復(fù)順序逐個的修復(fù)待修復(fù)區(qū)域邊界中的像素點(diǎn)。在對待修復(fù)點(diǎn)p修復(fù)時，因為每個像素點(diǎn)受其鄰近像素點(diǎn)的影響比較大，所以先計算待修復(fù)點(diǎn)p與其Ψp鄰域中已知點(diǎn)的相似度值（相似度的定義見2.3節(jié)），如果Ψp鄰域中已知點(diǎn)的相似度值小于預(yù)先設(shè)定好的相似度閾值，那么將這些已知點(diǎn)求和并平均，并將該值作為待修復(fù)點(diǎn)p的像素值。

為了降低在修復(fù)過程中的誤差，采用從待修復(fù)區(qū)域邊界向內(nèi)逐步推進(jìn)的修復(fù)方法[9]。因此，算法的修復(fù)流程是先獲取待修復(fù)區(qū)域邊界上的所有點(diǎn)，計算這些點(diǎn)的優(yōu)先級，然后把優(yōu)先級按照從大到小的順序設(shè)置為修復(fù)順序依次修復(fù)每一個待修復(fù)點(diǎn)。在每一個待修復(fù)點(diǎn)修復(fù)完成之后更新圖像，這樣可以提高接下來其他待修復(fù)點(diǎn)修復(fù)的準(zhǔn)確性，在待修復(fù)區(qū)域所有的邊界點(diǎn)修復(fù)完成后，再更新圖像，重新提取邊界，直到整個圖像修復(fù)完成。而在修復(fù)每一個待修復(fù)點(diǎn)時，先計算出待修復(fù)點(diǎn)鄰域中所有已知點(diǎn)與該點(diǎn)的相似度值，然后根據(jù)預(yù)先設(shè)定好的相似度閾值判斷這些已知點(diǎn)與待修復(fù)點(diǎn)的相似關(guān)系，最后將鄰域中符合相似度要求的所有已知點(diǎn)的像素值求和平均，并作為待修復(fù)點(diǎn)的值。

具體的修復(fù)流程如圖2所示。

圖2 圖像修復(fù)流程圖

2.2 優(yōu)先級函數(shù)

任選待修復(fù)區(qū)域邊界上一點(diǎn)p，Ψp表示以p點(diǎn)為中心的N×N正方形區(qū)域。由于修復(fù)是從邊界向內(nèi)部逐步推進(jìn)，邊界點(diǎn)的修復(fù)會影響待修復(fù)區(qū)域內(nèi)部的修復(fù)，因此應(yīng)該最大可能的降低邊界點(diǎn)的修復(fù)錯誤。對于待修復(fù)的邊界點(diǎn)p，如果Ψp中含有的已知像素點(diǎn)越多，表示點(diǎn)p周圍的有用信息越多，那么點(diǎn)p應(yīng)該優(yōu)先被修復(fù)，這樣就可以提高邊界點(diǎn)修復(fù)的準(zhǔn)確率。而如果Ψp中的結(jié)構(gòu)特征明顯，那么點(diǎn)p也應(yīng)該優(yōu)先被修復(fù)，這樣就可以防止結(jié)構(gòu)信息的丟失，保證圖像邊緣結(jié)構(gòu)的連通。因此，定義p點(diǎn)的優(yōu)先級函數(shù)P(p)如式（1）所示：

P(p)=(αC(p)+ω)(βD(p)+λ)，0＜α，ω，β，λ＜1（1）其中C(p)為置信度項，表示Ψp中已知像素所占的比例，它要求優(yōu)先修復(fù)那些鄰域中包含已知像素更多的點(diǎn)；D(p)為數(shù)據(jù)項，表示Ψp中的結(jié)構(gòu)信息量，它反映了鄰域塊中結(jié)構(gòu)信息的強(qiáng)弱，從而保證結(jié)構(gòu)特征明顯的部分被優(yōu)先修復(fù)。由C(p)和D(p)根據(jù)式（1）計算點(diǎn)p優(yōu)先權(quán)的大小。

置信度項和數(shù)據(jù)項的計算公式引用于文獻(xiàn)[9]中，分別如式（2）所示：

其中，|Ψp|為p鄰域中所有像素點(diǎn)個數(shù)，q為p鄰域Ψp中除點(diǎn)p外的像素點(diǎn)，γ為歸一化因子，一般圖像的灰度值取值范圍為0～255，本文取255（對于彩色圖像，本文分為R、G、B三個通道分別進(jìn)行修復(fù)）。?的方向是圖像的等照度線方向，即梯度的垂直方向，np是待修復(fù)區(qū)域邊界?Ω上p點(diǎn)的單位法向量。這里的數(shù)據(jù)項D(p)是用p點(diǎn)的等照度線方向和邊界上p點(diǎn)內(nèi)法線方向的內(nèi)積表示，如果p點(diǎn)等照度線方向和內(nèi)法線方向的夾角越小，由數(shù)據(jù)項定義可知，就說明p點(diǎn)數(shù)據(jù)項越大，即優(yōu)先級越大[9]。

置信度項的初始化如下：

等照度線的計算公式如（4）：

其中Ix、Iy分別表示圖像在x方向、y方向上的差分，坐標(biāo)系示意圖如圖3所示，計算公式如式（5）所示。

圖3 坐標(biāo)系示意圖

與Criminisi等人[9]提出的優(yōu)先級函數(shù)(P(p)=C(p)D(p))相比較，式（1）中的ω能夠有效地防止在計算過程中C(p)快速下降到0，導(dǎo)致P(p)計算失去真實(shí)性的情況。而λ可以防止在結(jié)構(gòu)特征不明顯的區(qū)域D(p)為0，導(dǎo)致P(p)計算失去真實(shí)性的情況。在本文實(shí)驗中將這兩個參數(shù)設(shè)置為ω=0.001，λ=0.001。而α、β是權(quán)重因子，且α+β=1，修復(fù)者可以根據(jù)不同的圖像要求選擇不同的α、β來控制優(yōu)先級的計算中置信度項和數(shù)據(jù)項的側(cè)重程度。經(jīng)過多次實(shí)驗之后，如果破損區(qū)域為平滑區(qū)域，設(shè)置α=0.7，β=0.3，如果破損區(qū)域為結(jié)構(gòu)特征明顯區(qū)域，設(shè)置α=0.3，β=0.7，這樣能夠達(dá)到比較好的修復(fù)效果。

2.3 相似度函數(shù)

考慮到圖像的局部信息能夠比單個像素更好地描述圖像的特征，因此判斷相似性的基本思想是利用圖像待修復(fù)區(qū)域中某一點(diǎn)（這里為點(diǎn)p）的鄰域與已知點(diǎn)鄰域的相似性來判斷已知點(diǎn)和該待修復(fù)點(diǎn)的相似程度，而不是直接利用傳統(tǒng)的單個像素點(diǎn)來比較相似。鄰域塊的選擇具體如圖4所示（灰色區(qū)域為破損區(qū)域）。

圖4 域相似原理圖

而對于相似度函數(shù)的選取，由于一方面，灰度信息是一種重要的視覺信息屬性；另一方面上，灰度信息又丟失了圖像的空間關(guān)系和結(jié)構(gòu)特征，也就是說圖像的信息沒有完全的利用起來，而且在圖像修復(fù)中，顯著結(jié)構(gòu)特征的相似更為重要。在此基礎(chǔ)上，本文通過多次實(shí)驗發(fā)現(xiàn)，灰度信息和梯度信息共同計算兩個像素點(diǎn)之間的相似度可以使得修復(fù)后的圖像更加能夠滿足人們的視覺效果。因此，定義待修復(fù)點(diǎn)鄰域與待修復(fù)點(diǎn)鄰域中已知點(diǎn)的鄰域之間像素差異的和加上在x、y方向上的梯度差異的和為相似度函數(shù)，其中第一部分表示了灰度像素信息的直接差異，第二部分代表了圖像局部區(qū)域之間的空間信息關(guān)系和結(jié)構(gòu)特征的相似度，使得像素點(diǎn)間的相對位置關(guān)系得到了考慮，從空間關(guān)系上彌補(bǔ)了傳統(tǒng)方法對于點(diǎn)的相似只考慮灰度信息差異的不足。如果這兩個像素點(diǎn)的鄰域之間的像素差異和梯度差異越小，那么這兩像素點(diǎn)之間的相似度函數(shù)值就越大，即這兩個像素點(diǎn)就越相似，反之，這兩個像素點(diǎn)就越不相似。如果這兩個差異值其中一個大，另一個小，但是只要這兩個差異的和大于相似度閾值，就認(rèn)為這兩個像素點(diǎn)相似。

其中，N為鄰域中已知點(diǎn)的個數(shù)，主要作用是將相似度函數(shù)進(jìn)行歸一化處理。為像素差異和，代表在x y方向上的梯度差異和，分別定義為式（7）、（8）、（9）：

從式（6）可以看出，其不僅包含了圖像的灰度像素值差異，而且也考慮了待修復(fù)像素信息的空間位置關(guān)系和待修復(fù)像素鄰域塊中的結(jié)構(gòu)特征相似度，因此該算法能夠保持圖像更多的細(xì)節(jié)信息，使修復(fù)后的圖像達(dá)到一個很好的視覺效果。

2.4 修復(fù)的具體實(shí)現(xiàn)

對待修復(fù)點(diǎn)p的修復(fù)，利用該點(diǎn)鄰域Ψp中所有滿足相似度要求的已知點(diǎn)，將這些已知點(diǎn)的像素值求和，再取平均賦給待修復(fù)點(diǎn)。

待修復(fù)點(diǎn)的修復(fù)公式如式（11）所示：

其中，g(p，q)為約束函數(shù)，當(dāng)已知點(diǎn)的相似度函數(shù)滿足相似度要求時（即為相似度函數(shù)，定義見公式（6）），g(p，q)=1，反之，g(p，q)=0。

如果鄰域中沒有找到滿足相似度要求的已知點(diǎn)，則選擇相似度最小的已知點(diǎn)作為待修復(fù)點(diǎn)的值。N(p)表示所有用于修復(fù)p的像素的個數(shù)，具體為式（12）：

3 仿真實(shí)驗及分析

為了能夠體現(xiàn)新的域相似算法在效率上的提高，選擇BSCB、Criminisi算法（這兩種算法的仿真實(shí)驗和新的鄰域平均算法的仿真實(shí)驗是在相同的實(shí)驗平臺下實(shí)現(xiàn)）與新的域相似算法對比，用程序的運(yùn)行時間來衡量算法的效率，用細(xì)小劃痕圖像的修復(fù)、文本的移除作為實(shí)驗內(nèi)容。對于彩色圖像的修復(fù)，先將彩色圖像分為R、G、B三個通道，按照實(shí)驗流程分別對這三個通道進(jìn)行修復(fù)。

圖5是灰度修復(fù)的結(jié)果對比圖，圖5（a）是劃痕破損圖像；圖5（b）是BSCB方法的修復(fù)結(jié)果，由于修復(fù)過程的平滑作用使得圖像略顯模糊，而且圖像上仍有修復(fù)痕跡；圖5（c）是Criminisi算法的修復(fù)結(jié)果，該算法修復(fù)的效果不錯，但是在匹配過程中需要重復(fù)的全局搜索，導(dǎo)致時間較長；圖5（d）為新的算法修復(fù)的結(jié)果，所花費(fèi)的時間是最少的，修復(fù)效果不錯。

圖5 灰度圖像劃痕的修復(fù)

圖6為灰度圖像中文字的移除，從上面幾幅圖像可以看出，圖6（b）的圖像比較模糊，圖6（c）、（d）兩幅圖像中則很難發(fā)現(xiàn)已修復(fù)過的區(qū)域。

圖7、8為彩色圖像修復(fù)效果對比圖，具體也分為劃痕圖像的修復(fù)和文字的去除。從圖7、8中也可以看出，在用BSCB算法修復(fù)之后，修復(fù)之后的圖像比較模糊，而Criminisi算法和新的修復(fù)算法修復(fù)之后的圖像比較自然清晰。具體各個算法所花費(fèi)的時間對比情況，見表1。

從表1給出的數(shù)據(jù)來看，運(yùn)行時間與圖像的破損區(qū)域大小以及圖片尺寸都有一定的關(guān)系。而且從表中可以看出，新的修復(fù)算法的修復(fù)時間明顯比其他兩種方法的修復(fù)時間少了幾倍。

圖6 灰度圖像文字的移除

圖7 彩色圖像劃痕的修復(fù)

圖8 彩色圖像文字的去除

表1 幾種不同修復(fù)方法運(yùn)行時間對比

4 結(jié)論

針對偏微分方程修復(fù)算法和紋理合成修復(fù)算法修復(fù)效率低的問題，新的修復(fù)算法修復(fù)時無須進(jìn)行大量的迭代和搜尋匹配模塊，縮短了計算的時間，提高了修復(fù)的效率；在修復(fù)過程中，充分利用了待修復(fù)點(diǎn)鄰域中的圖像信息，以像素點(diǎn)鄰域的相似作為兩個像素相似的指標(biāo)，在對待修復(fù)點(diǎn)修復(fù)時，僅僅利用到了局部鄰域中滿足相似度要求的已知像素點(diǎn)，提高了待修復(fù)點(diǎn)修復(fù)的準(zhǔn)確性，有效地降低了邊界上修復(fù)完成的像素點(diǎn)對待修復(fù)內(nèi)部的修復(fù)提供的信息的錯誤率，因此也能得到比較滿意的修復(fù)效果。仿真實(shí)驗結(jié)果表明，在同等修復(fù)區(qū)域和修復(fù)效果的條件下，本文算法顯著地縮短了修復(fù)時間，提高了圖像修復(fù)的效率。

[1]張紅英，彭啟琮.數(shù)字圖像修復(fù)技術(shù)綜述[J].中國圖象圖形學(xué)報，2007（1）：1-10.

[2]Bertalmío M，Sapiro G.Image inpainting[C]//Proceedings of the ACM Siggraph Processing，2000：417-424.

[3]Ballester C，Bertalm IO M，Caselles V，et al.An inpaintingbased deinterlacing method[J].IEEE Transactions on Image Processing，2007，16（10）：2476-2491.

[4]Liu D，Sun X，Wu F，et al.Image compression with edgebased inpainting[J].IEEE Transactions on Circuits and Systems for Video Technology，2007，17（10）：1273-1287.

[5]Rane S D，Sapiro G，Bertalmio M.Structure and texture filling-in of missing image blocks in wireless transmission and compression applications[J].IEEE Transactions on Image Processing，2003，12（3）：296-303.

[6]Chan T F，Kang S H.Mathematical medels for local nontexture inpainting[J].SIAM Journal of Applied Mathematics，2001，62（3）：1019-1043.

[7]Rudin L I，Osher S，F(xiàn)atem i E.Nonlinear total variation based noise removal algorithms[J].Nonlinear Phenomena：Physica D，1992，60（1/4）：259.

[8]Chan T F，Shen J.Nontexture inpainting by curvature-driven diffusions[J].Journal of Visual Communication and Image Representation，2001，12（4）：436-449.

[9]葉學(xué)義，王靖，趙知勁，等.魯棒的梯度驅(qū)動圖像修復(fù)算法[J].中國圖象圖形學(xué)報，2012，17（6）：630-635.

[10]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.

[11]Cheng W H.Robust algorithm for exemplar-based image inpainting[C]//Proceedings of the International Conference on Computer Graphics，Imaging，Vision，2005：64-69.

[12]Goyal A P，Diwakar S.Fast and enhanced algorithm for exemplar based image inpainting[C]//Proceedings of the 4th Pacific-Rim Symposium on Image and Video Technology（PSIVT），2010.