何文韜，葉學義，何志偉，汪云路

杭州電子科技大學模式識別與信息安全實驗室，杭州310018

1 引言

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

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

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

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

2 域相似算法的修復

2.1 算法的基本框架

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

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

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

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

具體的修復流程如圖2所示。

圖2 圖像修復流程圖

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

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

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

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

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

置信度項的初始化如下：

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

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

圖3 坐標系示意圖

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

2.3 相似度函數(shù)

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

圖4 域相似原理圖

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

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

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

2.4 修復的具體實現(xiàn)

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

待修復點的修復公式如式（11）所示：

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

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

3 仿真實驗及分析

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

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

圖5 灰度圖像劃痕的修復

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

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

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

圖6 灰度圖像文字的移除

圖7 彩色圖像劃痕的修復

圖8 彩色圖像文字的去除

表1 幾種不同修復方法運行時間對比

4 結論

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

[1]張紅英，彭啟琮.數(shù)字圖像修復技術綜述[J].中國圖象圖形學報，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]葉學義，王靖，趙知勁，等.魯棒的梯度驅(qū)動圖像修復算法[J].中國圖象圖形學報，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.