黃淑兵， 朱曉臨， 許云云， 朱 坤

(合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，安徽合肥 230009)

圖像修復(fù)是對圖像上信息缺損區(qū)域進(jìn)行信息填充的過程，其目的是為了對有信息缺損的圖像進(jìn)行恢復(fù)，并使觀察者無法察覺到圖像曾經(jīng)缺損或已被修復(fù)[1]。圖像修復(fù)技術(shù)主要應(yīng)用于破損圖像的修補以及文字或物體等目標(biāo)對象的移除。

文獻(xiàn)[2]首次將偏微分方程方法應(yīng)用于圖像修復(fù)，其基本思想是將待修復(fù)區(qū)域邊界的外部信息沿圖像等照度線方向擴散到中間待修復(fù)區(qū)域，該算法對破損區(qū)域較小的結(jié)構(gòu)圖像修復(fù)效果較好。而對于破損區(qū)域較大的紋理圖像，大多采用類似文獻(xiàn)[3]的紋理合成的方法進(jìn)行修復(fù)。該類算法的思想是從圖像的已知區(qū)域中尋找與受損區(qū)域最匹配的塊進(jìn)行填充，從而實現(xiàn)圖像修復(fù)。

文獻(xiàn)[4]提出的修復(fù)方法繼承了以上2類圖像修復(fù)算法的優(yōu)點，可以用來修復(fù)破損區(qū)域較大的圖像，同時能保留圖像的結(jié)構(gòu)和紋理信息。此后，文獻(xiàn)[5]中描述了該算法，并通過更多的實例說明該算法的有效性。雖然Criminisi的算法保留了圖像中原有的結(jié)構(gòu)信息，但對較強的結(jié)構(gòu)信息持續(xù)優(yōu)先處理也會帶來不好的結(jié)果，由于這種方法是直接復(fù)制紋理進(jìn)行填充，很容易造成偏差延續(xù)，導(dǎo)致整體結(jié)構(gòu)出現(xiàn)較大偏差。

為了解決偏差延續(xù)的問題，文獻(xiàn)[6]提出一種優(yōu)先權(quán)遞減的方法，在一定程度上解決了偏差延續(xù)的問題，但并未指出遞減因子如何選擇才能達(dá)到最佳修復(fù)效果，這使得該方法的實用性成為一個問題;此外，文中提出的遞減因子并無實際的物理含義，很難在理論上進(jìn)行分析。

文獻(xiàn)[7]在Crim inisi算法的基礎(chǔ)上，使用數(shù)據(jù)結(jié)構(gòu)中隊列的先來先服務(wù)(FCFS)的原則，并結(jié)合“剝洋蔥”的方法，逐層按照優(yōu)先隊列的順序進(jìn)行修復(fù)。但是，這種方法過分考慮了邊緣區(qū)域信息，把“洋蔥皮”的層與層之間完全孤立開來了，這又會導(dǎo)致另一種問題:無明顯邊緣、變化較弱的區(qū)域可能會出現(xiàn)在本應(yīng)該有較強邊緣的位置，導(dǎo)致修復(fù)效果不夠理想。

本文對Crim inisi算法造成偏差延續(xù)的原因進(jìn)行了分析，在Crim inisi提出的信任項(confidence term)和數(shù)據(jù)項(data term)的基礎(chǔ)上，又增加了一個邊界項(boundary term)，充分考慮已知區(qū)域比例、結(jié)構(gòu)信息和是否接近原始邊界3個因素對優(yōu)先權(quán)的影響。實驗證明，改進(jìn)的算法更為合理，修復(fù)的結(jié)果更好。

1 Criminisi算法及存在的問題

1.1 Crim inisi算法主要思想

Criminisi算法示意圖如圖1所示。

圖1 C rim inisi算法示意圖

圖1中，I為待修復(fù)圖像;Ω為待修復(fù)區(qū)域;其邊界為?Ω;Φ為待修復(fù)圖像的已知區(qū)域。Criminisi算法的思想是在邊界?Ω上根據(jù)優(yōu)先權(quán)選取一點p，選定以p點為中心的小方塊 Ψp為當(dāng)前需要修復(fù)的塊，然后在已知區(qū)域 Φ中尋找最匹配的塊Ψq，最后將 Ψq中對應(yīng)點的顏色信息復(fù)制到Ψp∩Ω，并更新邊界?Ω，重復(fù)上述過程直至 Ω為空。該算法最核心的思想就是考慮了目標(biāo)區(qū)域修復(fù)的順序，提出了按優(yōu)先權(quán)的順序進(jìn)行修復(fù)。

Crim inisi的算法考慮已知區(qū)域比例和結(jié)構(gòu)信息對優(yōu)先權(quán)的影響，并分別用信任項C(p)和數(shù)據(jù)項D(p)來表示這2個因素(p∈?Ω)。它們分別被定義為:

其中，n p是待修復(fù)區(qū)域Ω的邊界?Ω在點p處的法向量;▽I⊥p是已知區(qū)域Φ的邊界的梯度向量的垂直向量;α是標(biāo)準(zhǔn)化因子(灰度圖像取α=255);對?p∈Ω，C(p)=0;對?p∈I-Ω，C(p)=1。最后，取

(2)式作為決定修復(fù)順序的優(yōu)先權(quán)。

確定了待修復(fù)的目標(biāo)塊之后，利用類似文獻(xiàn)[3]的方法在已知區(qū)域中直接采樣，并復(fù)制顏色信息到待修復(fù)區(qū)域中。假設(shè)待修復(fù)塊 Ψ?p具有最高優(yōu)先級，Ψ?q是待修復(fù)區(qū)域中與 Ψ?p最匹配的塊(一般情況下，Ψ?q整塊都應(yīng)完全包含在已知區(qū)域 Φ中)，則

其中，d(Ψ?p，Ψq)是2個塊中已知像素的平方誤差和。找到 Ψ?q后，將 Ψ?q中相應(yīng)的顏色信息拷貝至Ψ?p∩Ω的位置。重復(fù)上述過程直至修復(fù)完畢。

1.2 Criminisi算法中存在的問題

對于純色區(qū)域，D(p)為0，若用C(p)D(p)來決定優(yōu)先權(quán)，顯然是不合理的。Criminisi算法首先處理優(yōu)先權(quán)最大的點，填充的顏色信息是圖像已知區(qū)域中與之所在的塊最匹配的，循環(huán)執(zhí)行一次后更新邊界，這極有可能導(dǎo)致新邊界上優(yōu)先權(quán)最大的點就處于剛填充的塊中，然后繼續(xù)向內(nèi)部延伸。如果循環(huán)中某個塊被填充了不符合視覺效果的顏色信息，而下一次循環(huán)又以這次的邊界為基礎(chǔ)，就會導(dǎo)致不合理的顏色信息繼續(xù)延伸下去，最終導(dǎo)致修復(fù)的視覺效果不佳。

2 改進(jìn)的算法

Crim inisi算法在計算優(yōu)先權(quán)時，修復(fù)之后的邊界點中越靠近原始邊界的，可靠性相對越高，也越應(yīng)當(dāng)被優(yōu)先處理。接近原始邊界的因素為邊界項(boundary term)，記為B(p)(p∈?Ω)。同時，為了避免過分考慮邊界項[7]，本文提出了優(yōu)先權(quán)公式，即

其中，λ1、λ2、λ3是非負(fù)常數(shù)，它們決定著優(yōu)先權(quán)中接近原始邊界、已知區(qū)域比例和結(jié)構(gòu)信息3個因素的權(quán)重。C(p)、D(p)的表達(dá)式與(1)式相同。設(shè){Ωi}是每執(zhí)行一次修復(fù)之后新的待修復(fù)區(qū)域的序列，其中0≤i≤N，Ω=Ω0?Ω1?…?ΩN=?，則

其中，?Ωi表示第i次修復(fù)后待修復(fù)區(qū)域的邊界。

由于C(p)、D(p)的取值均在0～1之間，為了使B(p)與C(p)、D(p)具有相同的數(shù)量級，取?B(p)上的點的邊界項值為0.5。

參數(shù)λ1決定著修復(fù)過程中B(p)的權(quán)重，如果λ1取值比較大(相對λ2、λ3)，則修復(fù)時會優(yōu)先修復(fù)靠近邊界的部分;參數(shù)λ2決定修復(fù)過程中C(p)的權(quán)重，如果λ2取值比較大(相對λ1、λ3)，則修復(fù)時會優(yōu)先修復(fù)小方塊中已知區(qū)域比例較大的區(qū)域;參數(shù)λ3決定著修復(fù)過程中D(p)的權(quán)重，如果λ3取值比較大(相對λ1、λ2)，則修復(fù)時會優(yōu)先修復(fù)顏色變化最劇烈的區(qū)域。即λ1、λ2、λ3的取值決定修復(fù)的順序，修復(fù)的順序不同，結(jié)果也就可能不同。

本文的算法可以通過選取不同的參數(shù)值來修復(fù)不同特征的破損圖像，這大大增加了該算法的應(yīng)用范圍。通常情況下，取λ1=λ2=λ3=1，3個因素取相同的權(quán)重。若取λ1=0，λ2=λ3=1，則計算優(yōu)先權(quán)時不考慮邊界項，只考慮信任項和數(shù)據(jù)項，并且兩者具有相同的權(quán)重，此時該算法的結(jié)果恰好與Criminisi算法相當(dāng)。若取λ1?λ2，λ3＞0，則計算優(yōu)先權(quán)時主要考慮邊界項，類似于“洋蔥皮”算法，由于邊界上點的邊界項值相同，比較每層信任項和數(shù)據(jù)項的大小，此時該算法的結(jié)果恰好與文獻(xiàn)[7]的算法相當(dāng)。由此可以看出，本文的算法模型較為靈活和全面，具有更好的實用性。

改進(jìn)的算法過程為:初始時，手工選擇待修復(fù)區(qū)域或待移除的目標(biāo)，抽取待修復(fù)區(qū)域的邊界?Ω0(=?Ω)，置?B(p)=?Ω0，?p∈?Ω0。執(zhí)行步驟(初始i=0)如下:

(1)找出待修復(fù)區(qū)域的邊界?Ωi，如果 Ωi= ?，退出循環(huán)，修復(fù)結(jié)束。如果?B(p)∩Ωi=?，置?B(p)=?Ωi，?p∈?Ωi。

(2)根據(jù)(1)式、(4)式、(5)式計算優(yōu)先權(quán)P(p)，?p∈?Ωi。

(4)根據(jù)(3)式找出最匹配的塊 Ψ?q∈Φ。

(5)將 Ψ?q中相應(yīng)的顏色信息拷貝至 Ψ?p，?p∈Ψ?p∩Ω。

(6)置i=i+1，重復(fù)步驟(1)～(5)。

3 實驗結(jié)果與比較

本文實驗用Matlab7.0作為工具，在Intel酷睿2雙核處理器(2.0GH z)、2G內(nèi)存的PC機上實現(xiàn)。

本文算法中參數(shù)λ1、λ2、λ3取不同的值時修復(fù)順序的比較如圖2所示。3幅圖中第1個均為待修復(fù)圖像，最后1個為修復(fù)后的圖像。

圖2 參數(shù)取值對修復(fù)順序的影響

從圖2a中可以看出，優(yōu)先修復(fù)靠近邊界的部分，該取法與“洋蔥皮”算法的修復(fù)效果相當(dāng)，出現(xiàn)了不理想的修復(fù)結(jié)果。從圖2b可以看出，此時優(yōu)先修復(fù)的是小方塊中已知區(qū)域比例較大的部分。從圖2c可以看出，此時優(yōu)先修復(fù)的是顏色變化最劇烈的部分。因此參數(shù)值的選取決定著修復(fù)的順序，可以根據(jù)待修復(fù)圖像的特征來選取合適的參數(shù)值。

本文算法與Criminisi算法修復(fù)結(jié)果的比較如圖3所示。圖3c因為優(yōu)先權(quán)的選取不合理，出現(xiàn)偏差延續(xù)的情況。從圖3d可以看出，本文的算法(取λ1=λ2=λ3=1)很好地解決了這個問題。其中，修復(fù)塊的大小均取7×7。

本文算法與文獻(xiàn)[7]中的算法修復(fù)結(jié)果的比較如圖4所示。圖4c因為文獻(xiàn)[7]中的算法過分強調(diào)了邊界區(qū)域的重要性，導(dǎo)致邊界附近河流的顏色信息蔓延至本應(yīng)是陸地的區(qū)域。從圖4d可以看出本文算法(取λ1=0.1，λ2=λ3=10)模型的靈活性，通過調(diào)節(jié)3個因素的權(quán)重，修復(fù)結(jié)果非常好。其中，修復(fù)塊的大小均取5×5。

本文算法與經(jīng)典的TV模型[8]修復(fù)結(jié)果的比較如圖5所示。圖5c左側(cè)豎條修復(fù)的結(jié)果出現(xiàn)了模糊。從圖5d可以看出，本文算法(取λ1= λ2=λ3=1)也可以適用于結(jié)構(gòu)圖像，而且修復(fù)效果比經(jīng)典的TV模型還要好。其中，修復(fù)塊的大小均取5×5。

圖3 本文算法與Criminisi算法修復(fù)結(jié)果的比較

圖4 本文算法與文獻(xiàn)[7]中的算法修復(fù)結(jié)果的比較

圖5 本文算法與經(jīng)典的TV模型算法修復(fù)結(jié)果的比較

4 結(jié)束語

本文通過分析Criminisi算法修復(fù)某些圖像效果不好的原因，提出了一種改進(jìn)的算法。結(jié)果表明，本文改進(jìn)的算法可以有效修復(fù)破損區(qū)域較小和較大的圖像，同時提出的優(yōu)先權(quán)計算模型比較靈活，適用范圍更廣。如果已知區(qū)域中不存在與待修復(fù)區(qū)域中相近似的塊，修復(fù)的效果不是很理想。本文只注重了修復(fù)的效果，并沒有考慮減少修復(fù)所需的時間[9]。

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

[2] Bertalm io M，Sapiro G，Caselles V，et al.Image inpain ting [C]//Proceedings of SIGGRAPH'2000.ACM Press，2000:411-424.

[3] Efros A，Leung T.Texture synthesis by non-parametric sam pling[C]//Proc In t Con f Com puter Vision，Kerkyra Greece，Sep tember，1999:1033-1038.

[4] Crim inisi A，Perez P，Toyam a K.Ob ject removal by exemplar-based inpainting[C]//Proc Conf Comp V ision Pattern Rec，Madison W I，2003:721-728.

[5] C rim inisi A，Perez P，Toyama K.Region filling and object removal by exemplar-based image inpain ting[J].IEEE Transactions on Image Processing，2004，13(9): 1200-1212.

[6] 朱 為，李國輝，李 丹.紋理合成技術(shù)在舊照片修補中的應(yīng)用[J].計算機工程與應(yīng)用，2007，43(28):220-222.

[7] 李景輝，張曉峰，馬 燕.紋理合成在圖像修復(fù)中的應(yīng)用研究[J].計算機工程，2009，35(7):206-208.

[8] Chan T F，Shen J.M athematicalmodels for localnon texture inpain tings[J].SIAM Jou rnal on Applied Mathem atics，2001，62(3):1019-1043.

[9] 薛 峰，張佑生，江巨浪，等.一種快速、有效的紋理合成方法[J].合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版，2005，28(11): 1361-1364.