新搜索策略下的快速圖像修復算法

（1.燕山大學 a. 信息與計算科學系； b. 計算機科學與工程系 河北 秦皇島 066004；2. 上海交通大學 計算機科學與工程系 上海200030）

摘 要：提出了一種新搜索策略下的快速圖像修復算法。通過定義新的優先權計算函數，克服了圖像低紋理區域修復過于滯后的問題。又通過預測修復后圖像塊統計屬性，對所有待匹配的圖像塊進行篩選，加快了圖像修復速度，改善了修復效果。實驗結果顯示，該算法適用于多種類型的數字圖像修復。

關鍵詞：圖像修復; 搜索策略; 優先權; 匹配函數

中圖分類號：TP391.41文獻標志碼：A

文章編號：1001-3695(2009)05-1991-03

Quick image inpainting algorithm under new searching strategy

NIE Dong-dong1a MA Qin-yong1b MA Li-zhuang2

(1. a. Dept. of Information Computing Sciences b.Dept.of Computer Science Engineering Yanshan University Qinhuangdao Hebei 066004 China； 2. Dept. of Computer Science Engineering Shanghai Jiaotong University Shanghai 200030 China)

Abstract:This paper proposed a quick image inpainting algorithm under a new searching strategy. By a new priority computation function it overcame the problem caused by the hysteresis of the low texture regions inpainting and by forecasting the statistical property of the image patch to be inpainted selected the source image patches which accelerated the inpainting process improved the inpainting results. Experiments confirm that this algorithm is suitable to various digital images inpainting.

Key words：images inpainting; searching strategy; priority; matching function

0 引言

數字圖像修復（digital image inpainting）技術是當前計算機圖形學和計算機視覺中的一個研究熱點。數字圖像修復是一種融合圖像修復和圖像編輯的技術，它通過適當的算法估計并填充圖像指定區域內的缺損數據，盡可能地使修復后的圖像看起來自然逼真。這使得該技術在文物保護、影視特技制作、多余目標物體剔除(如視頻圖像中刪除部分人物、文字、標題等)、圖像縮放、圖像壓縮、視頻通信錯誤隱匿等方面有著廣泛的應用價值。

雖然某些當前流行的圖像處理軟件，如Photoshop等，也可以對受損圖像進行修復處理，但這種方法對用戶的專業技術要求很高，而且在操作時用戶必須仔細考慮要填充的顏色、紋理等，經過復雜而繁瑣的手工處理后才能完成，這就使自動的數字圖像修復算法的研究更為迫切。

早期的圖像修復技術多數都是基于偏微分方程（partial differential equation PDE）的^[1]，如Bertalmio圖像修復算法^[2]、Chan等人^[3，4]提出的變分模型圖像修復算法。該類算法通常速度比較慢，而且因為PDE模型傾向于光滑地重構目標區域，這樣在處理較大區域時，修復的中心區域會出現明顯的過于平滑、缺少紋理現象，所以只適用于對非紋理圖像或低紋理圖像的修復。

目前的圖像修復算法多數以基于樣本的紋理合成（texture synthesis from samples TSFS）算法^[5]為核心。該類方法通常不是以像素而是以圖像塊為單位進行修復。例如Drori等人^[6]提出的基于反向遮片的圖像修復算法，Criminisi等人^{[7 8]}提出的基于樣例的圖像修復算法，以及Sun等人^[9]提出的交互式圖像修復算法。與基于PDE的圖像修復算法通過信息擴散或能量函數最小化來完成圖像修復不同，由于基于紋理合成的圖像修復算法是直接從圖像的已知區域采樣進行修復，不會出現模糊現象，能夠很好地修復圖像目標區域的紋理細節信息。

1 算法實現

本文提出的算法也是以基于樣本的紋理合成算法為核心，它以馬爾可夫隨機場模型為基礎，認為紋理具有局部統計特征，即紋理中的任一部分都可以由其周圍鄰域完全決定。

具體而言，本文算法通過新的優先權計算函數，確定當前待修復圖像塊的位置；進而利用其中的已知像素信息，估計修復后圖像塊在各個色彩分量上的均值，并以此對已知圖像區域內的所有待匹配圖像塊進行篩選，再從中找到與當前待修復圖像塊匹配代價最小的圖像塊；最后，通過拷貝最佳匹配圖像塊中對應的信息到當前圖像塊的未知像素部分，完成對當前圖像塊的修復。依此類推，以圖像塊為單位逐步完成整個指定圖像區域的修復。

1.1 確定當前待修復圖像塊

在圖像修復中確定當前待修復圖像塊也就是要確定一個合理的修復處理順序，這對提高圖像的修復效果是一個至關重要的因素。相對于多數修復算法都采用的從外向內剝洋蔥似的層層推進的處理方式 Criminisi等人在其圖像修復算法中率先提出了邊界像素修復優先權的概念，以確定圖像修復順序。然而，其邊界像素優先權的計算過于簡單，對較為平坦的低紋理區域的修復順序明顯滯后，容易造成修復后圖像高紋理區域向低紋理區域過度擴張的問題。本文采用式(1)計算優先權，它通過對當前像素點的信心因子和數據因子規則化，避免了由于兩者數量級上的差異，使兩者對優先權計算有相對均衡的影響力。同時，又引入了全局梯度強度閾值Tg，只有在梯度值大于全局梯度閾值時，才考慮邊緣結構對優先權計算的影響。這就避免了圖像細節部分的弱小梯度差異對修復順序的影響，突出圖像中真正的區域邊緣結構對修復順序的影響。

對圖像中待修復區域邊界上的任一像素p∈Ω，計算其相應的優先權值P(p)，以優先權值最大的像素點為中心，構成的鄰域窗口ψp就是當前要修復的邊界圖像塊。

信心因子C(p)衡量像素點p的鄰域窗口ψp內已知像素信息的可信程度。在優先權計算中，使用信心因子C(p)體現了優先考慮已知像素較多的邊界圖像塊的修復原則。

C(p)=∑i∈ψp∩ΩC(i)/｜ψp｜(3)

其中：｜ψp｜表示鄰域窗口ψp的面積；像素點i為當前像素點p的鄰域窗口內任意一個已知的像素點。

C(p)初始化定義如下：

C(p)=0 p∈Ω1 p∈Ω(4)

在圖像修復過程中，待修復區域外層像素的信心因子普遍相對較高，從而使它們被優先填充。待修復區域的中間由于被估計像素點的信心因子普遍較低，使得它們只能較晚被填充。另外在圖像待修復區域突出的部分，在其邊界像素點的鄰域窗口內有較多的已知像素信息，其信心因子較大，也就有可能被優先填充。在圖像待修復區域凹進的部分，在其邊界像素點的鄰域窗口內只有少量的已知像素信息，其信心因子比較小，也就只能被較晚填充。在圖像待修復區域邊界曲率等大致相等的情況下，信心因子就退化成了簡單的層層推進式的填充順序數據因子D(p)表示圖像邊緣結構信息對當前像素點的優先權值的影響。它不僅要考慮該點的邊緣結構強弱，還要考慮邊緣走向與該點待修復區域邊界法向之間的一致程度。

D(p)=｜I⊥p×np｜/αd(5)

其中： αd是歸一化系數，若圖像各分量值為255級，則取αd=255;np是待修復區域邊界Ω在p點的單位法矢量；I⊥p表示與p點圖像梯度矢量大小相同、方向垂直的矢量。

對離散的數字圖像，p點的單位法矢量并不容易求解。本文取邊界像素點p的鄰域窗口ψp內所有未知像素點到p點的方向的單位矢量，然后把這些矢量的平均值單位化后，作為p點的邊界法矢量。另外對彩色圖像，本文取圖像亮度分量上的梯度值作為邊界像素點的圖像梯度。

一般利用差分表示離散圖像梯度。常用的差分計算方法有前向差分、后向差分和中值差分三種。對邊界像素點p，其前向或后向鄰接點可能恰好是待修復的未知像素點。所以實際計算時并不能固定于某種單一的差分計算，只能根據實際情況分別計算。以p點x方向的梯度計為1；否則為0）。

邊界像素點p在y方向的梯度計算與此類似，不再贅述。

1.2 修復當前圖像塊中的未知像素

在確定了當前待修復區域邊界上具有最高優先權的像素點P后，就確定了以P點為中心的鄰域窗口ψp作為當前待修復的圖像塊。在ψp中，有部分像素點信息是已知的，而另一部分像素點信息是未知的。這些未知的像素點就是當前有待算法修復的部分。一般利用ψp中的已知像素信息，與已知圖像區域Ω中所有待匹配的圖像塊ψq相匹配，計算相應的匹配函數值，并以此確定與ψp最佳匹配的圖像塊。利用圖像的局部相關性可知，如果ψp中的已知像素信息與ψq中的相應像素非常相似，在一般情況下ψp中的未知像素信息與ψq中的相應像素也會非常相似，也就可以利用ψq中對應像素點修復ψp中未知像素信息。

目前，多數圖像修復算法均采用全搜索的策略，尋找已知圖像區域Ω中與當前待修復圖像塊ψp最匹配的圖像塊。這個過程非常慢，是整個圖像修復過于耗時的主要原因。如果能夠縮短搜索最匹配圖像塊所需要的時間，就能夠加快整個圖像修復過程。

實際上根據圖像的局部相關性，當前待修復圖像塊中的已知像素信息作為整個圖像塊中所有像素信息的一個采樣，可以利用其統計屬性預測修復后圖像塊中所有像素信息的整體統計屬性。再利用預測的修復后圖像塊的統計屬性對已知圖像區域Ω中的所有待匹配的圖像塊預先進行篩選，然后只計算那些與預測統計屬性相近的圖像塊的匹配函數值。這樣，就能夠有效縮短搜索最匹配圖像塊所需要的時間。

這里選用的圖像塊統計屬性是其中所有像素在紅、綠、藍三個色彩分量上各自的平均值。搜索最匹配圖像塊并對當前圖像塊中的未知像素進行修復的具體過程如下：

a)對已知圖像區域Ω中的所有待匹配的圖像塊ψq，計算該圖像塊在紅、綠、藍

2 實驗及分析

實驗采用用戶手工標記或某種圖像分割算法的結果作為圖像待修復區域。

圖1給出了本文算法與Criminisi等人提出的算法在圖像修復時間上的比較。算法采用MATLAB 6.5編寫，運行時間是在臺式PC（AMD Athlon XP1600+ 1.40 GHz CPU，256 MB內存）上多次實現后的統計結果。實驗數據顯示，采用本文提出的搜索策略可以有效加快圖像修復處理速度。

圖2顯示了采用本文優先權算法與傳統算法修復效果間的比較。其中，(a)是原始圖像；(b)是指定待修復區域（灰色區域）后的圖像；(c)是采用Criminisi等人提出的優先權計算方法得到的修復結果；(d)是采用本文提出的優先權計算方法得到的修復結果。圖2(d)中修復效果明顯要比(c)中好得多。這主要也是因為按照Criminisi等人提出的優先權計算方法，在圖像低紋理區域的優先權過于滯后，這樣不合理的修復順序就造成了山林和巖石部分向河面內的過度延伸。尤其是巖石部分，由于是近景細節要比遠處的山林部分更突出，這使得巖石部分甚至一直突入到本該屬于山林的區域內，嚴重影響了圖像的修復效果。

圖3是采用新的搜索策略后與傳統算法修復效果間的比較。其中：(a)為原始圖像；(b)為指定待修復區域（綠色區域）后的圖像；(c)為采用原來的全搜索策略修復后的圖像；(d)為采用新的搜索策略進行修復后的圖像。從中可以看出，當待修復區域尺度較大時，采用本文搜索策略后修復圖像的質量明顯比采用原來全搜索策略的修復圖像質量好。而且本文算法的處理時間只要128 s，原來算法的處理時間要1 118 s。

圖4是本文算法與幾種傳統典型算法的比較。其中：(a)是原始圖像；(b)是指定待修復區域后的圖像；(c)是Bertalmio等人提出的算法修復結果；(d)是Criminisi等人提出的算法修復結果；(e)是本文算法的修復結果。從中可以看出，Bertalmio等人提出的基于偏微分方程的圖像修復算法無法處理大面積的圖像修復工作，其修復區域過于模糊，缺少相應的圖像細節；而Criminisi等人提出的基于樣例圖像的修復結果(e)要好得多，但還存在一些問題。一方面，由于不合理的優先權計算，使河面等低紋理區域受邊緣梯度強度的制約，優先權過低，造成了岸邊草地區域向河面內的過度延伸，影響了最后圖像的修復效果；另一方面，在圖像底邊附近也有一些修復圖像塊色彩跳變的問題。在本文算法的修復結果圖4(e)中，這些問題都有了明顯改善。

從圖2~4中也可看出，本文算法在去除圖像中特定對象方面效果較好。實驗顯示本文算法在修復圖像劃痕和去除圖像中的文字方面也達到了令人滿意的效果，部分實驗結果如圖5所示。其中：第1列為待修復的圖像；第2列為采用本文算法進行修復后的圖像。

3 結束語

本文提出了一種快速圖像修復算法。