基于插值的圖像修復算法

王茜艷，陳力，李萌

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

基于插值的圖像修復算法

王茜艷，陳力，李萌

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

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

圖像修復；快速行進法；鄰近像素；線性最小均方誤差估計；整體變分法

0 引言

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

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

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

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

1 FMM算法

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

圖1 修復模型

2 FMM修復方法的改進

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

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

2.1 權函數設計

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

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

我們定義權函數為：

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

2.2 置信度因子

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

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

圖2 缺損圖像掩膜過程

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

2.3 修復步驟

通過對權函數和自適應插值的置信度因子分析，改進的FMM修復算法具體過程如下.

（1）初始值設定

①根據水平距離因子L（q），初始化T（q）的值.T被標識為三種狀態，即設缺損區域邊界上的像素和邊界外的像素的T值為0，而邊界內的像素取106（原本設為∞）；

②將待修復圖像進行標記.待修復圖像輸入為x0，將標記過缺損區域塊的圖像設為x1，對輸入的x1圖像取反，表示標記缺損以外的區域，且令可信度模型

（2）像素點修復過程

①根據模板R對可信度模型M進行掩膜，且保存于優先度矩陣P中；

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

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

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

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

3 基于LMMSE的插值修復算法

3.1 LMMSE插值

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

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

圖3 對像素進行45°和135°方向插值

可寫成以下式子進行估計：

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

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

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

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

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

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

3.2 LMMSE修復步驟

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

（1）輸入待修復圖像x0和將待修復圖像中缺損區域標記的圖像x1，檢測并標記x1圖像中缺損區域的邊緣；

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

（3）估計出相應的RV，根據式（10），對標記圖像x1待修復區域中的像素點修復進行插值迭代修復；

（4）與上一節中的FMM改進算法和TV算法進行PSNR和時間上的比較.

4 實驗與分析

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

其中，

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

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

表1 FMM算法、TV算法與改進后FMM算法的修復結果對比

圖5 圖像修復結果1

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

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

表2 FMM算法、TV算法與LMMSE插值算法的修復結果對比

圖6 圖像修復結果2

5 結論

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

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

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

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

[4]鄧悟，吳笛，騰奇志，等.基于區域填充的圖像修復算法研究[J].計算機與數字工程，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]李開宇，孫玉剛.引入連續性強度和置信度因子的快速圖像修復[J].中國圖象圖形學報，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].數據采集與處理，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的帶方向圖像修復算法[J].杭州電子科技大學學報：自然科學版，2012，32（5）：147-150.

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

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

[15]侯正信，何宇清，許微.一種快速的圖像修復算法[J].中國圖象圖形學報，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-），女，江西吉安人.研究方向：數字圖像處理.E-mail：12qywang@stu.edu.cn