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

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

1 引言

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

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

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

在基于偏微分方程的圖像修復(fù)和基于紋理合成的圖像修復(fù)算法的基礎(chǔ)上，針對(duì)這些修復(fù)方法在修復(fù)效率上的不足，提出了一種新的基于域相似的圖像修復(fù)算法。本文算法先計(jì)算待修復(fù)區(qū)域邊界上的所有待修復(fù)點(diǎn)優(yōu)先級(jí)，然后按照優(yōu)先級(jí)從大到小的順序來(lái)設(shè)置圖像的修復(fù)順序，算法采用像素點(diǎn)鄰域的相似來(lái)衡量?jī)蓚€(gè)像素點(diǎn)的相似程度，充分考慮了待修復(fù)像素的鄰域中已知信息對(duì)該像素的影響，而每個(gè)待修復(fù)點(diǎn)的值等于該點(diǎn)鄰域中所有滿足相似度要求的已知點(diǎn)像素值的求和平均。仿真實(shí)驗(yàn)結(jié)果表明，在同等的修復(fù)區(qū)域和保證修復(fù)效果的條件下，本文算法顯著地縮短了修復(fù)時(shí)間，提高了圖像修復(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)先級(jí)從大到小的順序，因此先對(duì)待修復(fù)區(qū)域邊界點(diǎn)p計(jì)算優(yōu)先級(jí)（優(yōu)先級(jí)定義見(jiàn)2.2節(jié)），按照修復(fù)順序逐個(gè)的修復(fù)待修復(fù)區(qū)域邊界中的像素點(diǎn)。在對(duì)待修復(fù)點(diǎn)p修復(fù)時(shí)，因?yàn)槊總€(gè)像素點(diǎn)受其鄰近像素點(diǎn)的影響比較大，所以先計(jì)算待修復(fù)點(diǎn)p與其Ψp鄰域中已知點(diǎn)的相似度值（相似度的定義見(jiàn)2.3節(jié)），如果Ψp鄰域中已知點(diǎn)的相似度值小于預(yù)先設(shè)定好的相似度閾值，那么將這些已知點(diǎn)求和并平均，并將該值作為待修復(fù)點(diǎn)p的像素值。

為了降低在修復(fù)過(guò)程中的誤差，采用從待修復(fù)區(qū)域邊界向內(nèi)逐步推進(jìn)的修復(fù)方法[9]。因此，算法的修復(fù)流程是先獲取待修復(fù)區(qū)域邊界上的所有點(diǎn)，計(jì)算這些點(diǎn)的優(yōu)先級(jí)，然后把優(yōu)先級(jí)按照從大到小的順序設(shè)置為修復(fù)順序依次修復(fù)每一個(gè)待修復(fù)點(diǎn)。在每一個(gè)待修復(fù)點(diǎn)修復(fù)完成之后更新圖像，這樣可以提高接下來(lái)其他待修復(fù)點(diǎn)修復(fù)的準(zhǔn)確性，在待修復(fù)區(qū)域所有的邊界點(diǎn)修復(fù)完成后，再更新圖像，重新提取邊界，直到整個(gè)圖像修復(fù)完成。而在修復(fù)每一個(gè)待修復(fù)點(diǎn)時(shí)，先計(jì)算出待修復(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)先級(jí)函數(shù)

任選待修復(fù)區(qū)域邊界上一點(diǎn)p，Ψp表示以p點(diǎn)為中心的N×N正方形區(qū)域。由于修復(fù)是從邊界向內(nèi)部逐步推進(jìn)，邊界點(diǎn)的修復(fù)會(huì)影響待修復(fù)區(qū)域內(nèi)部的修復(fù)，因此應(yīng)該最大可能的降低邊界點(diǎn)的修復(fù)錯(cuò)誤。對(duì)于待修復(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)先級(jí)函數(shù)P(p)如式（1）所示：

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

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

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

置信度項(xiàng)的初始化如下：

等照度線的計(jì)算公式如（4）：

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

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

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

2.3 相似度函數(shù)

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

圖4 域相似原理圖

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

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

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

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

對(duì)待修復(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í)（即為相似度函數(shù)，定義見(jiàn)公式（6）），g(p，q)=1，反之，g(p，q)=0。

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

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

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

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

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

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

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

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

圖6 灰度圖像文字的移除

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

圖8 彩色圖像文字的去除

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

4 結(jié)論

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

[1]張紅英，彭啟琮.數(shù)字圖像修復(fù)技術(shù)綜述[J].中國(guó)圖象圖形學(xué)報(bào)，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é)義，王靖，趙知?jiǎng)?，?魯棒的梯度驅(qū)動(dòng)圖像修復(fù)算法[J].中國(guó)圖象圖形學(xué)報(bào)，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.