基于ＭＲＦ模型的圖像修復(fù)算法

摘要：基于馬爾可夫隨機(jī)場(chǎng)(MRF)模型，提出一種直接采樣的圖像修復(fù)方法。通過優(yōu)先權(quán)機(jī)制來決定邊界像素的修復(fù)次序，充分顧及到圖像的邊緣結(jié)構(gòu)信息，同時(shí)能夠恢復(fù)紋理細(xì)節(jié)，避免了模糊效應(yīng)。實(shí)驗(yàn)證明該算法具有很好的修復(fù)效果。

關(guān)鍵詞：圖像修復(fù)； 紋理合成； 馬爾可夫隨機(jī)場(chǎng)

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)04-0179-03

圖像修復(fù)（Inpainting）技術(shù)是一項(xiàng)古老的藝術(shù)，它最早出現(xiàn)于歐洲文藝復(fù)興時(shí)期。為了恢復(fù)美術(shù)作品中丟失或損壞的部分，同時(shí)保持作品的整體效果，人們開始對(duì)美術(shù)作品進(jìn)行修復(fù)，主要是填補(bǔ)作品上所出現(xiàn)的裂痕或溝，稱為Retouching(潤飾)或Inpainting(修復(fù))。

現(xiàn)今，數(shù)字圖像修復(fù)技術(shù)已成為圖像工程領(lǐng)域的一個(gè)新的活躍研究方向。其目的就是研究和解決如何更好地實(shí)現(xiàn)檢測(cè)圖像上的受損部分或被遮擋區(qū)域，并根據(jù)周圍的有效信息進(jìn)行自動(dòng)恢復(fù)。通過研究，人們已經(jīng)提出了一些算法。

Nitzberg.M^[1]借助于圖像分割提出一種去遮擋算法。其基本思想是利用最小曲率和相同灰度值的曲線連接T型接頭。該方法只適合比較簡單的圖像，而不適合復(fù)雜的自然圖像。Masnou和Morel^[2]擴(kuò)展Nitzberg.M的思想，提出一種變分算法。它采用測(cè)地曲線連接斷開于待修復(fù)區(qū)域邊界的等照度線來達(dá)到圖像修補(bǔ)的目的，但存在要求修復(fù)區(qū)鄰域的拓?fù)潢P(guān)系簡單、直線連接、保角性差等缺點(diǎn)。Bertalmio等人^[3]首次采用偏微分方程（Partial Differential Equations，PDE），通過將待修補(bǔ)區(qū)域外圍的信息沿著等照度線方向進(jìn)行擴(kuò)散來填補(bǔ)，能夠處理不同結(jié)構(gòu)和背景的區(qū)域，并且自動(dòng)化程度較高。在偏微分方程的基礎(chǔ)上，Chan和Shen^[4]提出TV（Total Variational，整體變分）模型，采用歐拉—拉格朗日方程和各向異性擴(kuò)散來保持等照度線的方向。針對(duì)TV模型的不足，Chan和Shen^[5]又提出CDD(CurvatureDriven Diffusion)模型，使之能夠處理更大的區(qū)域。Oliveira^[6]提出一種非常簡單的方法，反復(fù)地通過3×3卷積運(yùn)算將已知信息不斷向修補(bǔ)區(qū)域內(nèi)部進(jìn)行擴(kuò)散，達(dá)到修復(fù)目的。

以上各種圖像修復(fù)方法取得了一些效果，但仍然存在一些缺陷，不令人滿意。基于PDE的方法，需要反復(fù)迭代，速度非常慢，并且這些方法一般只能修復(fù)較小的區(qū)域，無法處理大的區(qū)域；另外這些方法不能很好地保持修復(fù)區(qū)域的紋理細(xì)節(jié)，修復(fù)后的圖像往往具有模糊效應(yīng)。Oliveira的卷積方法簡單，對(duì)于平滑的區(qū)域具有較好的效果，但無法保持等照度線方向，也容易出現(xiàn)模糊現(xiàn)象。

圖像修復(fù)的難點(diǎn)在于：自然圖像非常復(fù)雜，既包含結(jié)構(gòu)信息，也包含紋理細(xì)節(jié)。結(jié)構(gòu)信息非常重要，然而紋理細(xì)節(jié)也是不可丟失的。前面基于PDE的方法，主要在于恢復(fù)圖像中的結(jié)構(gòu)線，但無法保持紋理細(xì)節(jié)，所以存在不可避免的模糊效應(yīng)。為了能夠保持紋理細(xì)節(jié)，本文將引入紋理合成技術(shù)。紋理合成，簡單說來就是根據(jù)一個(gè)紋理樣圖，生成新的具有相同視覺效果的紋理，可以用來恢復(fù)自然圖像中的紋理區(qū)域。

1算法描述

1.1MRF模型

Efros^[7]首次在紋理合成中采用馬爾可夫隨機(jī)場(chǎng)模型。其概率模型基于紋理的空間局域性：對(duì)于一個(gè)給定的像素p，它的灰度值分布概率只與其空間鄰域N(p)有關(guān)而與圖像的其他部分無關(guān)。所謂空間鄰域N(p)，就是以像素p為中心，直徑為d的一個(gè)方形窗口。窗口的大小d是一個(gè)自由參數(shù)，它取決于紋理的隨機(jī)程度或結(jié)構(gòu)基元的大小。如圖1（a）為給定的紋理樣圖，（b）為待合成紋理圖。現(xiàn)在要合成一個(gè)未知像素p(圖1（a）中方框的中心像素，記p的鄰域窗口為N(p))。首先在樣圖中找到與鄰域窗口N(p)相匹配的一些候選鄰域窗口，然后從這些候選鄰域窗口中任取一個(gè)，將其窗口中心像素賦給p。這就是一個(gè)從采樣區(qū)搜索最佳匹配像素的過程。

在紋理合成過程中，首要的步驟就是在樣圖中搜尋與p的鄰域N(p)相似的鄰域窗口。這里的相似性準(zhǔn)則采用鄰域窗口像素的誤差平方和來衡量。由于鄰域中心像素具有更重要的作用，可以對(duì)鄰域中的像素賦予二維高斯權(quán)重。在計(jì)算中，對(duì)于鄰域中還未合成的未知像素，不予考慮。設(shè)N1為待合成像素的鄰域，N2為樣本鄰域，則N1、N2的相似性測(cè)度為

其中，p為像素索引，分別表示鄰域N1、N2中對(duì)應(yīng)的像素；b1是鄰域N1的二進(jìn)制模板，若N1中的像素p為已知像素，則b1(p)=1，否則b1(p)=0；G為方形鄰域窗口的高斯權(quán)重。

1.2基于MRF模型的圖像修復(fù)

前面介紹了基于MRF模型的紋理合成，它適合純紋理圖像合成，對(duì)大多數(shù)紋理具有較好的合成效果。由于這種基于樣圖的紋理合成直接從樣本圖中尋找最佳匹配像素，能較好地保持紋理細(xì)節(jié)。在圖像修復(fù)中，可以認(rèn)為在局部區(qū)域，圖像滿足MRF模型，從待修復(fù)區(qū)域的外圍鄰域直接采樣并復(fù)制，逐漸完成圖像缺損信息的填補(bǔ)。其基本思想與傳統(tǒng)基于PDE的圖像修復(fù)思想一樣：將外圍已知圖像信息逐漸擴(kuò)散到待修補(bǔ)區(qū)域內(nèi)部。但不同于單純的紋理合成，自然圖像不僅包含紋理信息，還具有復(fù)雜的結(jié)構(gòu)信息（主要是邊緣），所以需要充分顧及圖像的邊緣特征。

1.2.1邊界像素修復(fù)順序問題

在紋理合成中，一般采用掃描行順序進(jìn)行處理，但對(duì)于圖像修復(fù)，采用這樣的順序是不合適的。由于自然圖像不是單純的紋理，缺損區(qū)域可能覆蓋多種紋理區(qū)，并且各紋理區(qū)域之間具有明顯的邊緣。采用簡單的行處理順序無法顧及邊緣結(jié)構(gòu)特征，可能導(dǎo)致明顯的錯(cuò)誤填補(bǔ)。

另外一個(gè)想法就是從待修復(fù)區(qū)域外圍邊界開始，采取蠶食的方式，逐漸縮小包圍圈。該方式優(yōu)于逐行順序處理方式，能夠保證先填補(bǔ)離已知信息近的區(qū)域，可靠性更強(qiáng)一些。如圖2所示，虛線為待修復(fù)區(qū)域的初始邊界；實(shí)線表示待修補(bǔ)區(qū)域的當(dāng)前邊界，該邊界逐漸向內(nèi)收縮。

在修復(fù)過程中，將像素分成四個(gè)類別，分別標(biāo)志為

（1）KNOWN——已知像素：圖2中白色區(qū)域。

（2）FILLED——已修復(fù)像素：圖2中灰色區(qū)域。

（3）BOUND——邊界像素：待修復(fù)區(qū)域邊界上的像素，即圖2中實(shí)線所表示的像素；邊界像素屬于未知像素，是當(dāng)前需要修復(fù)的像素點(diǎn)。

（4）INSIDE——內(nèi)部像素：待修復(fù)區(qū)域內(nèi)部的像素，圖2中斜線區(qū)域。

后面的論述中將采用這四個(gè)標(biāo)志來表示不同的像素類型。

1.2.2邊界像素優(yōu)先權(quán)的計(jì)算

若對(duì)當(dāng)前邊界采用同步收縮，則是一種各向同性填補(bǔ)順序，相當(dāng)于邊界上的像素具有相同的優(yōu)先權(quán)，沒有考慮邊緣結(jié)構(gòu)的影響，效果不太理想。為了顧及圖像的結(jié)構(gòu)特征，可以采用優(yōu)先權(quán)機(jī)制，讓邊界像素具有不同的修復(fù)優(yōu)先權(quán)P(p)。每次從邊界像素中挑選具有最高優(yōu)先權(quán)的一個(gè)像素進(jìn)行處理，從而達(dá)到各向異性擴(kuò)散的目的。優(yōu)先填補(bǔ)圖像邊緣附近的像素，然后填補(bǔ)其他像素，有利于邊緣結(jié)構(gòu)的保持。如圖3所示，由于p點(diǎn)位于邊緣附近，具有最高優(yōu)先權(quán)，該像素及其附近的像素應(yīng)該最先得到修復(fù)。 

對(duì)于邊界像素p，本文采用如下的優(yōu)先權(quán)計(jì)算方法：

其中，np表示p點(diǎn)處的邊界線法線矢量；Ep表示p點(diǎn)處的邊緣強(qiáng)度矢量，體現(xiàn)p點(diǎn)處的圖像邊緣方向和強(qiáng)度(圖3)。

np的計(jì)算方法是：取p點(diǎn)的鄰域N（p），計(jì)算鄰域中所有INSIDE像素點(diǎn)qi(i=0~m-1，m為點(diǎn)數(shù)）到p點(diǎn)的方向單位矢量vi=norm(xqi-xp，yqi-yp)(其中x、y表示像素坐標(biāo)，norm(#8226;)表示單位化運(yùn)算)；然后計(jì)算這些矢量的平均值，作為p點(diǎn)的法線矢量np=(nx，ny)。

Ep矢量需要通過梯度(Gradient)來計(jì)算。先計(jì)算p點(diǎn)鄰域N(p)中所有KNOWN像素點(diǎn)和FILLED像素點(diǎn)的梯度Gi(i=0~k-1，k為點(diǎn)數(shù))；然后計(jì)算這些梯度的平均值Gp=(Gx，Gy)。由于梯度方向和邊緣方向相互垂直，將Gp旋轉(zhuǎn)90°，得到邊緣強(qiáng)度矢量Ep=(-Gy，Gx)。最后將np和Gp代入式（1）得到點(diǎn)p的優(yōu)先權(quán)。

1.2.3邊界更新

每次從邊界像素中挑選具有最高優(yōu)先權(quán)的像素p進(jìn)行修復(fù)后，將發(fā)生兩個(gè)變化：①點(diǎn)p由邊界像素(BOUND)變成已修復(fù)像素(FILLED)，且p的四鄰域中的INSIDE像素將成為新的BOUND像素；②p的鄰域N(p)中其他BOUND像素的優(yōu)先權(quán)將發(fā)生變化。所以，在每完成一個(gè)邊界像素p的修復(fù)后，需要重新確定p的鄰域N(p)內(nèi)的邊界像素，并重新計(jì)算這些邊界像素的優(yōu)先權(quán)。

1.2.4自適應(yīng)采樣區(qū)的確定

自然圖像與紋理圖像的區(qū)別在于不具有穩(wěn)定性。更確切地說，自然圖像應(yīng)該用非穩(wěn)定性MRF模型來描述。進(jìn)行采樣修復(fù)時(shí)，不同的邊界像素應(yīng)該采用不同的采樣區(qū)域，而不是從相同的樣本區(qū)中尋找最佳匹配像素。一般來說，待修復(fù)像素附近的區(qū)域最有可能成為其搜索區(qū)域。因此，對(duì)于每個(gè)待修復(fù)的邊界像素p，本文采用自適應(yīng)的采樣區(qū)確定方法：以p為中心，以初始半徑為r的方框覆蓋原圖像，若落入方框內(nèi)的KNOWN像素和FILLED像素的總數(shù)目M大于某個(gè)閾值時(shí)，將該方框區(qū)域作為p的采樣區(qū)；否則，逐漸增大r，直到M滿足條件。

2實(shí)驗(yàn)結(jié)果

本文算法以Visual C++為平臺(tái)，在PⅢ 800MHz的CPU，256MB內(nèi)存的微機(jī)上實(shí)現(xiàn)。用戶只需將損壞的或需要移除的圖像部分用某種固定顏色標(biāo)定，余下的工作由程序自動(dòng)完成，并動(dòng)態(tài)顯示處理過程。本文對(duì)多種圖像進(jìn)行了修復(fù)實(shí)驗(yàn)，并與Bertalmio^[3]算法的修復(fù)結(jié)果進(jìn)行比較（實(shí)驗(yàn)圖中，MRF表示采用本文算法的修復(fù)結(jié)果）。

圖4(a)是存在缺損信息的圖像(圖中白色區(qū)域是待修復(fù)區(qū)域，以下同)；(b)~(e)顯示了采用本文算法分別處理完成20%、36%、71%、100%的中間結(jié)果。由其過程可見，整個(gè)待修復(fù)區(qū)域逐漸被分成零碎的小區(qū)域，圖像邊緣附近的像素首先得到修復(fù)；并且還可以看出，圖像中最重要的邊緣結(jié)構(gòu)首先得到恢復(fù)，然后是細(xì)小結(jié)構(gòu)，最后才是平滑區(qū)域。這正是算法中采用梯度計(jì)算像素優(yōu)先權(quán)的結(jié)果。因?yàn)橹匾吘壧幭袼氐奶荻戎当厝淮螅磧?yōu)先權(quán)高，因而最先得到恢復(fù)，這與人工修復(fù)圖像的過程一致，所以能夠較好地保持圖像的邊緣結(jié)構(gòu)。另外，本文的算法也能很好地保持局部紋理細(xì)節(jié)，避免傳統(tǒng)修復(fù)方法所帶來的模糊效應(yīng)。圖4(f)是采用Bertalmio算法的修復(fù)結(jié)果，其紋理細(xì)節(jié)不能得到恢復(fù)。

圖5是對(duì)人物圖像中劃痕的修復(fù)實(shí)驗(yàn)，劃痕寬度在8~12個(gè)像素之間。Bertalmio算法的修復(fù)結(jié)果存在紋理細(xì)節(jié)丟失和邊緣模糊現(xiàn)象；本文的算法具有非常好的視覺效果，人物褲子上的條紋完全得到恢復(fù)，手臂處的邊緣也保持較好，幾乎看不出修復(fù)痕跡。圖6是對(duì)照片中大目標(biāo)的移除填補(bǔ)實(shí)驗(yàn)。由于Bertalmio算法一般只適合于細(xì)小劃痕的修復(fù)，無法處理大面積缺損信息的修補(bǔ)，其效果非常差。然而，采用本文的算法能夠很好地填補(bǔ)缺損區(qū)域的圖像信息，效果比較理想。

3結(jié)束語

本文基于圖像的局部馬爾可夫隨機(jī)場(chǎng)模型，采用直接采樣

的方法，逐漸修復(fù)圖像缺損區(qū)域。在修復(fù)過程中，采用優(yōu)先權(quán)

機(jī)制來決定邊界像素的修復(fù)先后次序，充分顧及到圖像的邊緣結(jié)構(gòu)特征。該算法既能夠重建缺損區(qū)域的結(jié)構(gòu)信息，又能夠很好地恢復(fù)紋理細(xì)節(jié)，避免傳統(tǒng)修補(bǔ)方法帶來的模糊效應(yīng)。對(duì)于細(xì)小劃痕的修復(fù)和大面積區(qū)域的圖像填補(bǔ)均具有很好的效果。

本文算法也具有一些不足之處：①當(dāng)?shù)貌坏胶线m的局部采樣區(qū)域時(shí)，可能出現(xiàn)錯(cuò)誤的填充信息；②當(dāng)目標(biāo)存在前后遮擋關(guān)系時(shí)，算法無法自動(dòng)識(shí)別和確定多個(gè)邊緣的修復(fù)順序，導(dǎo)致錯(cuò)誤的修復(fù)結(jié)果。這些問題需要進(jìn)一步研究，以增強(qiáng)算法的穩(wěn)定性和智能化。

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。