一種改進的基于紋理合成的圖像修復算法

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

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

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

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

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

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

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

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

1 Criminisi算法及存在的問題

1.1 Crim inisi算法主要思想

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

圖1 C rim inisi算法示意圖

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

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

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

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

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

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

1.2 Criminisi算法中存在的問題

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

2 改進的算法

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結果與比較

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

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

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

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

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

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

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

圖3 本文算法與Criminisi算法修復結果的比較

圖4 本文算法與文獻[7]中的算法修復結果的比較

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

4 結束語

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

[1] 張紅英，彭啟琮.數(shù)字圖像修復技術綜述[J].中國圖象圖形學報，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] 朱 為，李國輝，李 丹.紋理合成技術在舊照片修補中的應用[J].計算機工程與應用，2007，43(28):220-222.

[7] 李景輝，張曉峰，馬 燕.紋理合成在圖像修復中的應用研究[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è)大學學報:自然科學版，2005，28(11): 1361-1364.