王茜艷，陳力，李萌

(汕頭大學(xué)工學(xué)院，廣東汕頭515063)

基于插值的圖像修復(fù)算法

王茜艷，陳力，李萌

(汕頭大學(xué)工學(xué)院，廣東汕頭515063)

目前，針對小區(qū)域缺損的圖像修復(fù)算法中，大多采用基于迭代的修復(fù)算法，然而這些效果較好的圖像修復(fù)算法，其時間復(fù)雜度一般都比較大.本文通過插值的方法，利用破損區(qū)域與周邊鄰域的有效信息之間的相關(guān)性，提出改進(jìn)的基于FMM（快速行進(jìn)）的圖像修復(fù)算法；調(diào)用僅適用于被檢測到的高局部活躍的像素，提出基于LMMSE（線性最小均方誤差估計）插值的圖像修復(fù)算法.實驗結(jié)果表明，提出的兩種算法分別與FMM算法和TV（整體變分法）算法相比，在整體上其修復(fù)效果和效率都具有明顯的優(yōu)勢.

圖像修復(fù)；快速行進(jìn)法；鄰近像素；線性最小均方誤差估計；整體變分法

0 引言

圖像修復(fù)是根據(jù)圖像中信息丟失部分周圍的已知信息，對該部分進(jìn)行重建，其主要目的是對破損的圖像進(jìn)行修復(fù)，以構(gòu)造人眼主觀系統(tǒng)可以接受的圖像[1].數(shù)字圖像修復(fù)的研究發(fā)展至今，從方法上可以大致分為基于非紋理和基于紋理合成兩大類，按破損區(qū)域則可以大致分為小尺度缺損的圖像修復(fù)和大區(qū)域缺損圖像的修復(fù).其中基于非紋理的圖像修復(fù)方法主要針對小尺度缺損的圖像，大概分為基于變分PDE（偏微分方程）的圖像修復(fù)方法和基于插值的圖像修復(fù)方法.基于紋理修復(fù)的主要針對的是大區(qū)域缺損的圖像，大概包含兩種修復(fù)技術(shù)：一種是基于圖像分解的修復(fù)技術(shù)，如文獻(xiàn)[2]將圖像分解為結(jié)構(gòu)部分和紋理部分，利用已有的算法分別對其進(jìn)行修補和填充，最后把這兩部分修復(fù)結(jié)果疊加起來，得到修復(fù)圖像；另一種方法如文獻(xiàn)[3-4]采用樣本塊合成技術(shù)來填充缺損的信息.

目前，針對小尺度缺損的圖像修復(fù)模型和算法中，文獻(xiàn)[5-7]采用基于高階偏微分的模型進(jìn)行多次迭代修復(fù).這些圖像修復(fù)效果較好的算法，大多都是以較大的時間復(fù)雜度為代價，盡管可以得到較好的修復(fù)效果，但其耗時較嚴(yán)重.而在實際應(yīng)用時，通常對處理速度有一定的要求，因此，研究快速有效地修復(fù)破損圖像的算法具有重大意義[8].基

于插值的修復(fù)算法在小區(qū)域破損圖像的快速修復(fù)中，具有一定的優(yōu)勢.其中Telea等人[9]提出的快速行進(jìn)法，盡管在修復(fù)效率上有很大的改進(jìn)，但其對強弱邊緣的保持能力不足.因此，若分析其問題原因并將其改進(jìn)，在快速修復(fù)圖像的過程中保持破損區(qū)域的邊緣強度，是非常有意義的.然而，利用文獻(xiàn)[10]提出的由約束最小二乘方法改進(jìn)的圖像恢復(fù)方法中的迭代估計思想，可在破損區(qū)域內(nèi)對其邊緣像素進(jìn)行線性最小二乘誤差迭代估計，以達(dá)到圖像的快速修復(fù).在文獻(xiàn)[11]中，有人通過定向濾波和數(shù)據(jù)融合邊緣引導(dǎo)提出一種保持邊緣結(jié)構(gòu)的線性最小均方誤差估計的圖像插值技術(shù)，因缺失區(qū)域的樣本在其邊緣方向上與其鄰近有較高的相關(guān)性，即把缺失樣本附近區(qū)分為兩個正交方向上的子集，通過結(jié)合兩個定向的線性最小均方誤差估計，得到高分辨率圖像.因此，若將其應(yīng)用到多個小塊區(qū)域缺失的圖像修復(fù)中，對保持缺損圖像的邊緣信息和快速修復(fù)都是具有重大意義.

因此，本文將基于插值的圖像修復(fù)技術(shù)，從以下兩個方面進(jìn)行研究：1）針對快速行進(jìn)（FMM）修復(fù)算法中對強弱邊緣的保持能力不足，分析其問題原因并將其改進(jìn)，提出一種新的基于FMM的修復(fù)算法，結(jié)合等照度線的擴散方向，定義新的權(quán)函數(shù)以保持邊緣信息.2）將結(jié)合LMMSE的方法對缺損圖像進(jìn)行修復(fù).本文將把它應(yīng)用到多個小塊區(qū)域缺失的圖像修復(fù)中，調(diào)用僅適用于被檢測到的高局部活躍的像素進(jìn)行線性最小均方誤差估計，在很好的保持邊緣清晰的前提下，快速的修復(fù)破損圖像.該方法雖然在破損區(qū)域比較大的圖像中沒有優(yōu)勢，但其在針對較規(guī)則或因傳輸過程中而導(dǎo)致的缺損圖像上的效果非常顯著，相對于其他方法而言，其在圖像修復(fù)的速度和對破損區(qū)域邊緣的處理上都很有優(yōu)勢.

1 FMM算法

FMM算法通過快速行進(jìn)法，對缺損區(qū)域逐步修復(fù)，其主要利用待修復(fù)像素與周邊鄰域有效信息的相關(guān)性來定義權(quán)函數(shù).快速行進(jìn)法的基本思想是采用時間函數(shù)T（x，y）的形式模擬曲線演化過程，將修復(fù)區(qū)域邊緣逐步往里推進(jìn)，直到破損區(qū)域完全修復(fù)[12].假設(shè)I為待修復(fù)的圖像，若記Ω為待修復(fù)圖像I的缺損區(qū)域，則鄣Ω為缺損區(qū)域Ω的邊界，點p位于缺損區(qū)域Ω內(nèi)，且設(shè)p點的梯度方向為N.FMM算法為方便計算T值，將圖像的像素分為三種狀態(tài)：缺損區(qū)域邊界上的像素、邊界內(nèi)的像素和邊界外的像素，每種狀態(tài)的像素都有一個對應(yīng)的到達(dá)時間T.其本質(zhì)是利用擴散方程求出缺損區(qū)域邊界內(nèi)部所有的點到邊界上的距離T，其中邊界內(nèi)部的點T的初始值為106，而待修復(fù)邊界和邊界外點的T初始值為0，并將各個像素設(shè)為其對應(yīng)的狀態(tài)，最后根據(jù)計算出來T值，按照離缺損區(qū)域邊界越近（即T值越小），越先修復(fù)的順序進(jìn)行修復(fù)，直到缺損區(qū)域Ω內(nèi)的點完全修復(fù).

圖1 修復(fù)模型

2 FMM修復(fù)方法的改進(jìn)

由于FMM算法設(shè)計的權(quán)函數(shù)沒有考慮其等照度方向，致使邊緣信息保持不佳，因

此其權(quán)函數(shù)的設(shè)計不夠合理；且對已知鄰域信息采取的信任是相同的，導(dǎo)致對破損區(qū)域往里逐步推進(jìn)修復(fù)時，產(chǎn)生誤差的累積，使修復(fù)后的破損區(qū)域比較模糊[13].本文在設(shè)計權(quán)函數(shù)時，考慮加入等照度線方向，并引入自適應(yīng)插值的置信度因子，對破損區(qū)域的像素點插值.即當(dāng)缺失像素進(jìn)行插值時，對其鄰域的原始像素全部信任，而對經(jīng)修復(fù)得到的像素部分信任，由此避免誤差累積導(dǎo)致的修復(fù)后破損區(qū)域模糊現(xiàn)象.

2.1 權(quán)函數(shù)設(shè)計

根據(jù)圖1的修復(fù)模型，未知像素Ω的點p是由已知鄰域信息Bε（p）的點q決定，所以，p點的像素可由Bε（p）中所有的點加權(quán)得出，

由于FMM中設(shè)計的加權(quán)函數(shù)W（p，q）是采用切線方向N（p）來評價已知鄰域像素點與缺失像素點的相關(guān)性程度，即保證了距離p點法線方向越接近的像素點對p點的貢獻(xiàn)越大[8].

我們定義權(quán)函數(shù)為：

N（p，q）為幾何距離因子，表示已知鄰域信息內(nèi)與p距離越近的點其貢獻(xiàn)越大；R（p，q）為方向因子，可以明顯看出它與FMM的方向因子有區(qū)別，即利用等照度方向的信息進(jìn)行傳輸，考慮到了圖像已知區(qū)域的結(jié)構(gòu)特征，使離等照度線越近的點的貢獻(xiàn)越大；L（q）為水平距離因子，表示離經(jīng)過P點的缺失圖像邊界越近的已知像素，對P點的貢獻(xiàn)越大.其中為p點的等照度方向矢量，其實際上是由p點附近已知鄰域信息所有像素的等照度方向共同決定的，因此，可定義為

2.2 置信度因子

破損區(qū)域修復(fù)都是通過其周圍已知鄰域的像素點決定.因此，在其修復(fù)的過程中，其周圍已知像素越多，則越能得到更好的修復(fù)值，且被修復(fù)的點也能更好的確定其他待修復(fù)點的灰度值，以此達(dá)到整體上的修復(fù).本文將建立一種自適應(yīng)的可信度模型M，將破損區(qū)域附近所有像素分為已知像素1（原始）、已知像素2（修復(fù)后）和未知像素點三大類，初始化時，將所有的已知像素1置為1，未知像素點置為0，且選取矩陣R進(jìn)行掩膜，求出已知像素2的值，如圖2所示.

本文以p為中心，ε為中心到邊界的距離，選取修復(fù)時以大小為（2ε+1）×（2ε+1）小方窗ψp的矩陣，模板選取ε為2的方窗，對可信度模型M進(jìn)行掩膜，以計算出已知像素2（修復(fù)后）的像素點的可信度，掩膜后的結(jié)果存于矩陣P.

圖2 缺損圖像掩膜過程

則矩陣P中元素表明圖像中相應(yīng)位置的像素點中周圍已修復(fù)像素的相對個數(shù)[15]，且0≤P（i，j）≤1，P（i，j）的值越大，則表明破損圖像中（i，j）點所在的5×5鄰域內(nèi)的已知像素越多.如果P（i，j）＝1，則表明點（i，j）所在的小方窗鄰域全部為已知像素，即處于破損區(qū)域的外部；如果0＜P（i，j）＜1，表明點（i，j）所在的小方窗鄰域內(nèi)既有已知像素也有未知像素，即處于破損區(qū)域的邊緣；如果P（i，j）＝0，表明點（i，j）所在的小方窗鄰域全部為未知像素，即處于破損區(qū)域的內(nèi)部.

2.3 修復(fù)步驟

通過對權(quán)函數(shù)和自適應(yīng)插值的置信度因子分析，改進(jìn)的FMM修復(fù)算法具體過程如下.

（1）初始值設(shè)定

①根據(jù)水平距離因子L（q），初始化T（q）的值.T被標(biāo)識為三種狀態(tài)，即設(shè)缺損區(qū)域邊界上的像素和邊界外的像素的T值為0，而邊界內(nèi)的像素取106（原本設(shè)為∞）；

②將待修復(fù)圖像進(jìn)行標(biāo)記.待修復(fù)圖像輸入為x0，將標(biāo)記過缺損區(qū)域塊的圖像設(shè)為x1，對輸入的x1圖像取反，表示標(biāo)記缺損以外的區(qū)域，且令可信度模型

（2）像素點修復(fù)過程

①根據(jù)模板R對可信度模型M進(jìn)行掩膜，且保存于優(yōu)先度矩陣P中；

②找出待修復(fù)區(qū)域中P值最大的像素點f（m，n）；

③利用式（1）修復(fù)點f（m，n），同時將p點值更新；

④更新M值，將上一步修復(fù)完成的該像素點的M值標(biāo)記為1，即令M（m，n）=1，x1（m，n）=0；

⑥重復(fù)②～④的步驟，直至缺損區(qū)域完全修復(fù)為止，輸出處理過的圖像x0.

3 基于LMMSE的插值修復(fù)算法

3.1 LMMSE插值

基于插值的圖像修復(fù)技術(shù)主要是根據(jù)破損區(qū)域周圍鄰近的像素點的相關(guān)性，采用一定的修復(fù)順序進(jìn)行加權(quán)或迭代修復(fù).本文取多個小塊區(qū)域缺失的圖像，利用LMMSE對

待修復(fù)的圖像Dh（m，n）中的破損區(qū)域沿著兩個方向進(jìn)行插值：45°方向和135°方向，分別對缺損像素進(jìn)行線性最小均方誤差估計.通過一些線性方法對這兩個方向插值的結(jié)果用D贊45（m，n）和D贊135（m，n）表示.考慮到以這兩個方向作為缺失像素的插值輸出時，可能會產(chǎn)生的噪聲測量V45和V135.

圖3 對像素進(jìn)行45°和135°方向插值

可寫成以下式子進(jìn)行估計：

將上式重寫成矩陣形式Y(jié)=1×Dh+V.

在實際應(yīng)用中，經(jīng)常用LMMSE替代MMSE，因為這個估計在最小均方誤差中，必須知道缺損圖像的先驗信息.而實現(xiàn)LMMSE，只需要計算Dh和Y的一階統(tǒng)計和二階統(tǒng)計，他們也可以是自適應(yīng)估計的.因此，Dh的LMMSE可計算為[16]：

其中，μh＝E[Dh]，協(xié)方差運算符

方差運算符Cov（A）=Cov（A，A）.Dh通過LMMSE運算，融合兩個定向測量提供的信息.根據(jù)文獻(xiàn)[11]可假設(shè)v是零均值，并且與Dh無關(guān)，則可由（8）推出，

圖4 對Dh（m，n）附近像素的迭代插值

且Var（V45）和Var（V135）可估算為：

3.2 LMMSE修復(fù)步驟

通過以上分析，本文基于LMMSE的圖像插值修復(fù)方法的具體過程如下：

（1）輸入待修復(fù)圖像x0和將待修復(fù)圖像中缺損區(qū)域標(biāo)記的圖像x1，檢測并標(biāo)記x1圖像中缺損區(qū)域的邊緣；

（2）通過（6）和（11）分別對破損塊進(jìn)行45°和135°方向上的定向融合插值；

（3）估計出相應(yīng)的RV，根據(jù)式（10），對標(biāo)記圖像x1待修復(fù)區(qū)域中的像素點修復(fù)進(jìn)行插值迭代修復(fù)；

（4）與上一節(jié)中的FMM改進(jìn)算法和TV算法進(jìn)行PSNR和時間上的比較.

4 實驗與分析

本文的兩種算法都是用Matlab R2014a在Core（TM）2 Duo，1.96 GB內(nèi)存的PC機上實現(xiàn)的.實驗中將本文提出的兩種算法分別在修復(fù)效果和修復(fù)時間上與FMM算法、TV算法進(jìn)行對比，快速的圖像修復(fù)算法主要用于小尺度破損的圖像，因此本文的實驗圖片Lena和Peppers都是通過對正常圖像添加人工劃痕得出，如圖5（a）和（e），而試驗圖片Lena_mask則是通過模擬傳輸過程中導(dǎo)致的缺損圖像而得出的多塊小區(qū)域破損圖，如圖6（a）.本文采用PSNR來對圖像修復(fù)的效果進(jìn)行評價，

其中，

MSE是表示原始圖像與缺損區(qū)域修復(fù)后的圖像之間的均方誤差，N為圖像的整體像素數(shù)，xi為原始圖像的像素值，yi為缺損區(qū)域修復(fù)后的輸出圖像x0的像素值.

本文給出了三種圖像（Lena圖像、Peppers圖像和Lena_mask圖像），利用不同修復(fù)算法得出的對比結(jié)果如圖5所示.本文利用提出的FMM改進(jìn)算法進(jìn)行實驗時，Bε（p）取為以p點為中心的鄰域窗口.由于改進(jìn)的FMM算法加入等照度線方向，且當(dāng)缺失像素使用經(jīng)修復(fù)過的像素進(jìn)行自適應(yīng)插值時，對其鄰域的原始像素全部信任，而對經(jīng)修復(fù)過的像素部分信任，因此其在修復(fù)效果上對于缺損區(qū)域邊緣的保護(hù)比較明顯；且引入自適應(yīng)插值的置信度因子對缺損區(qū)域的像素進(jìn)行順序選擇，與FMM的擴散方程相比，其在修復(fù)時間上也更有優(yōu)勢.表1列出了相應(yīng)的PSNR和修復(fù)時間T統(tǒng)計結(jié)果，P1和P2分別表示FMM算法和TV算法進(jìn)行修復(fù)后的PSNR，P3為通過改進(jìn)的FMM算法修復(fù)后的PSNR；T1和T2分別表示FMM算法和TV算法進(jìn)行修復(fù)所花費的時間，T3為通過改進(jìn)的FMM算法修復(fù)后所花費的時間.

表1 FMM算法、TV算法與改進(jìn)后FMM算法的修復(fù)結(jié)果對比

圖5 圖像修復(fù)結(jié)果1

而本文提出的基于LMMSE的插值修復(fù)算法，主要是根據(jù)破損區(qū)域周圍鄰近的像素

點的相關(guān)性，采用一定的修復(fù)順序進(jìn)行加權(quán)或迭代修復(fù).以Lena_mask為實驗圖，表2列出了LMMSE算法和FMM算法、TV算法修復(fù)的結(jié)果對比，P1、P2、T1、T2與表1中的表示是一樣，P4和T4分別表示通過LMMSE的插值算法進(jìn)行修復(fù)后的PSNR和花費的時間.從表1、表2中可以看出，綜合考慮修復(fù)效果和時間，本文提出的兩種算法比FMM和TV算法更具有優(yōu)勢.

表2 FMM算法、TV算法與LMMSE插值算法的修復(fù)結(jié)果對比

圖6 圖像修復(fù)結(jié)果2

5 結(jié)論

本文針對FMM算法修復(fù)可能導(dǎo)致的缺損區(qū)域修復(fù)后邊緣信息模糊問題，提出了一種改進(jìn)的FMM算法，結(jié)合等照度線方向，并引入自適應(yīng)插值的置信度因子對缺損區(qū)域的像素點插值.而在針對多塊小區(qū)域較規(guī)則破損的圖像修復(fù)時，本文采用的是基于LMMSE的插值修復(fù)算法，調(diào)用僅適用于被檢測到的高局部活躍的像素進(jìn)行線性最小均方誤差估計，因此，其可以更好的保持缺損區(qū)域的邊緣信息.實驗結(jié)果表明，從整體上來說，本文提出的兩種算法都能在保持良好的修復(fù)效果時，有效的提高了修復(fù)效率，達(dá)到快速且有效的修復(fù)目標(biāo).

[1]魏琳，陳秀宏.基于紋理方向的圖像修復(fù)算法[J].計算機應(yīng)用，2008，28（9）：2315-2317.

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

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

[4]鄧悟，吳笛，騰奇志，等.基于區(qū)域填充的圖像修復(fù)算法研究[J].計算機與數(shù)字工程，2014，42（3）：495-525.

[5]Bertalmio M，Sapiro G，Caselles V，et al.Image inpainting[C].Proceedings of ACMSIGGRAPH 2000. New York：ACM Press，2000：417-424.

[6]Chan T F，Shen J H.Mathematical models for local non-texture inpainting[J].SIAM J Appl Math，2002，62（3）：1019-1043.

[7]Chan T F，Shen J H.Non-texture inpainting by Curvature-Driven Diffusions（CDD）[J].J Visual Comm Image Rep，2001，12（4）：436-449.

[8]李開宇，孫玉剛.引入連續(xù)性強度和置信度因子的快速圖像修復(fù)[J].中國圖象圖形學(xué)報，2012，17（4）：465-470.

[9]Telea A.An image inpainting technique based on fast marching method[J].Graph Tools，2004，9（1）：23-34.

[10]沈瑛，吳建華，吳祿慎.由約束最小二乘方法改進(jìn)的圖像恢復(fù)方法[J].數(shù)據(jù)采集與處理，2002，17（3）：325-327.

[11]Zhang L，Wu X L.An edge-guided image interpolation algorithm via directional filtering and data fusion[J].IEEE Trans，on Image Processing，2006，15（8）：2226-2238.

[12]康佳倫，唐向宏.一種基于FMM的帶方向圖像修復(fù)算法[J].杭州電子科技大學(xué)學(xué)報：自然科學(xué)版，2012，32（5）：147-150.

[13]孫玉剛.數(shù)字圖像修復(fù)技術(shù)研究[D].南京：南京航空航天大學(xué)，2011.

[14]肖志云，張文霞，姜玉莉.基于快速行進(jìn)法的快速圖像修復(fù)算法[J].計算機應(yīng)用，2007，27（12）：60-65.

[15]侯正信，何宇清，許微.一種快速的圖像修復(fù)算法[J].中國圖象圖形學(xué)報，2007，12（10）：1909-1912.

[16]Karmen E W，Su J K.Introduction to optimal estimation[M].London：Springer-Verlag，1999.

Image Inpainting Algorithm s Based on Interpolation

WANG Xiyan，CHEN Li，LI Meng
（Department of Electronic Engineering，College of Engineering，Shantou University，Shantou 515063，Guangdong，China）

For image repair in a small defect area，iterative algorithms with high computational complexity are commonly used.In this paper，an improved fast marching method（FMM）is proposed by using correlation information in the neighborhood of damaged area.A new image restoration algorithm based on LMMSE interpolation is also proposed by using pixels with high local activity only.Experimental results show that the proposed algorithms have improved performance as compared with the FMM method and integral variation method（TV）.

image inpainting；fast marching method；adjacent pixel；linear minimum mean square error estimation；integral variation method

TN 919.8

A

1001-4217（2015）02-0072-08

2014-09-29

王茜艷（1990-），女，江西吉安人.研究方向：數(shù)字圖像處理.E-mail：12qywang@stu.edu.cn