摘  要： 在研究Criminisi等人的基于樣例的修復算法基礎上,提出了一種快速修復算法。該算法采用梯度數據項連同置信度確定填充順序，使得優先權的計算更加準確；并采用局部窗口搜索的策略，加快了修復速度；最后利用顏色和梯度共同決定相似性，使得修復后的圖像具有更好的視覺效果。大量實驗結果表明，該算法不僅能夠快速有效地修復受損圖像，而且能夠很好地保持受損區域的紋理和結構。
關鍵詞： 圖像修復； 目標去除； 紋理； 結構

    圖像修復是圖像復原研究中的一個重要內容，它的主要思想是:對圖像中遺失或者損壞的區域，利用未損壞的圖像信息，按照一定的規則進行填充，并且盡可能地使修復后的圖像接近或達到原來的視覺效果。隨著近幾年數字技術的發展以及數碼產品的普及，這一技術除了應用于破損照片的修復，還被用于文本提取、目標移除、超分辨率、圖像壓縮/傳輸以及視頻錯誤隱藏等方面。
    目前，圖像修復中占主流的修復模型有：偏微分方程的修復模型[1-2]、紋理合成[3]的修復模型。前者計算量大、耗時長、對紋理的還原能力有限，處理大區域圖像會有明顯的模糊現象，因此只適合于劃痕、污跡和文字等細窄的區域修復。相比之下，后者將待修復區域周圍的圖像作為樣本,從中提取特征并選取匹配的紋理，將其合成到待修復區域內，適用于較大區域的修復。
    現實中的圖像不是由簡單結構和單一紋理拼接而成的，而是同時包含復雜的結構和多種紋理特征。參考文獻[4]將圖像分割為結構和紋理兩部分，然后分別用偏微分方法和紋理合成技術進行處理，最后將兩種處理結果進行融合。但對實際圖像而言，該方法修復區域較小，速度較慢，對較大區域修復仍然有一定的模糊。Criminisi等人在2003年提出了一種不用分割圖像，同步處理紋理和結構的基于樣例的圖像修復算法[5]。他們的算法取得了滿意的效果，但是耗費的時間過長，另外優先權和相似度的計算還存在一定不足。本文改進了參考文獻[5]的圖像修補算法。為了使優先權計算更加準確，本文采用梯度數據項和置信度共同決定填充順序；為加快修復速度，本文采用局部窗口搜索的策略；最后利用顏色和梯度共同決定相似性，使得修復后的圖像具有更好的視覺效果。大量實驗結果表明，該算法提高了修復效率，同時產生了更滿意的視覺效果。

2 算法的實現細節
2.1模板大小的自適應選擇
    在反復的實驗過程中發現，用固定大小的模板窗口?追，修復誤差比較大。對于包含豐富的細節及邊緣的區域，應該采用小的模板窗口，以獲取較多的細節信息，減少畸變；對于平滑的紋理區域，由于樣本塊和目標塊的相似距離非零，修復采用直接復制樣本，應該采用較大的窗口，減少修復后的圖像產生明顯的假象。因此模板窗口的大小應當根據圖像的局部特征自適應地變化。本文采用梯度函數自適應地改變模板窗口大小。模板尺寸size(p)的定義為：

2.2 塊的優先權
    基于樣例的圖像修復算法，為了兼顧結構和紋理部分的修復效果，填充順序是這類方法的關鍵。填充順序的優先權函數大小要考慮兩方面的因素:一方面是模板窗口中已知信息量的多少,另一方面要考慮待修復區域周圍的結構特征。因為已知信息多的待填充塊的周圍可以利用的信息大，結構特征明顯的區域包含了豐富的結構信息。Criminisi定義的優先權函數為：P(p)=C(p)×D(p)。當等照度線與單位法向量垂直時，D(p)=0，這時即使C(p)很大，甚至整個塊中只有幾個未知像素，塊也得不到及時填充。這樣優先權的計算就變得不可靠，導致錯誤的填充順序，進而影響修復的效果。為了解決這個問題，本文直接引入梯度信息來計算塊的優先權。P為修復邊界dΩ上的點，ψp是以點P為中心的塊，點P的優先權函數P(p)定義為:

2.3 匹配塊的搜索空間
    Criminisi等人采用在整幅未破損的圖像中全局搜索，這樣能夠找到與目標區域塊最相似的匹配塊。但是許多圖像的匹配塊就在目標區域的附近，因此全局搜索提供了巨大的搜索空間，降低了算法的效率。為了減少搜索過程的時間消耗，一些學者提出了紋理主方向的搜索方法[6]（水平、垂直等）。這種紋理主方向的搜索方法對于方向性很強的圖像能達到很滿意的效果，但是對于其他的圖像修復效果達不到滿意效果。為了既要減少搜索空間，又要達到滿意的修復效果，采用局部窗口空間搜索匹配塊。在Criminisi的算法中，設置的填充塊大小為 PatchSize，然后在整幅圖像的未破損區域搜索匹配塊。局部窗口尺寸設置如下:

式中，M是目標塊上的已知像素點的數目，CL(p)為顏色差的平方的和，W(p)為梯度的差的平方的和，分別定義為:

式中，k是一個可調參數，d是前面提到的相似度函數。顯然，由這個方程可知相似度函數值越大，像素點誤差越大，置信度值越低。
3 實驗結果
    將本文所提的算法應用于許多的自然圖像,采用對比圖像的視覺效果來判斷修復質量的好壞，用程序的運行時間來衡量算法的效率。所有的實驗是在配置為2.1 GHz處理器、2 GB內存的計算機上運行的，仿真環境為Matlab 7.0。本文用文本移除、單一目標物移除和多目標物移除，來說明本文算法的優越性。
3.1 文本移除
    圖2為文本移除實驗。其中，(a)為原始圖像，(b)為Criminisi算法，(c)為本文算法。從原始圖像中可以看出，圖中的文字“JAPANESE ANIMATION”只在圖片的下端，其文字移走后的空白區域，修補只需要搜索不到圖片一半的空間就可以找到最佳匹配塊；而Criminisi采取全局搜索，大量的時間浪費在不必要的搜索中。對比發現，Criminisi所用的修復時間遠遠大于本文算法，而其修復效果略好于本文算法。

3.2  單一目標物的移除
    圖3為單一目標物的移除。其中，(a)為原始圖像，(b)為Criminisi算法，(c)為本文算法。從Criminisi算法可以看出，臺階恢復出現了明顯的不相容的“垃圾塊”，而且臺階下面的綠地延伸到黑色區域中；而本文算法很好地恢復了臺階的線性結構，黑色區域內也沒有綠地的延伸塊，幾乎看不出人工痕跡。
3.3 多目標物的移除
    圖4為多目標物的移除實驗。其中，圖4(a)為原始圖像，圖4(b)為Criminisi算法，圖4(c)為本文算法。從圖4中可以看出，移走多棵樹以后，本文算法修復的海平面非常自然，而Criminisi算法修復的海平面有輕微的人工痕跡。

    表1給出了這三組實驗的運行時間。從表1可以看出，運行時間與圖像本身大小、破損區域大小以及破損區域周圍的結構復雜度都有一定關系。本文方法與參考文獻[5]所用方法相比，根據圖像自身特征局部搜索運行時間更短，然而得出的效果差不多或者更好，說明了本方法的高效優質性。

    圖像修復在圖像處理和計算機圖形學領域中有許多重要應用。本文提出了一種能夠滿足破損圖片修復、文本移除、目標物體去除等多類修復要求的快速算法。本算法改進了基于樣例的修復算法，為了正確地傳播信息，有效地利用梯度值來計算目標塊的填充順序和匹配塊的相似度。因此該算法更有能力對細小結構和復雜的紋理優先傳播。
    文中提出的方法不需要人為干預分割紋理和結構信息，算法根據圖像的局部特征計算出優先權，接著根據優先權的大小先后填充。在匹配塊的搜索空間，采用局部窗口搜索，大大縮短了修復時間。然而，該算法仍然存在著一定局限性：首先，局部窗口不能完全找到最匹配的塊，如果沒有局部特性的圖像或者有明顯跳變結構的圖像修復都會失??；其次， 圖像的破損區域周圍必須有大量的樣本塊，以滿足待修復區域內的結構和紋理傳播。所以，在今后的工作中，應該對該算法的局限性進行逐步改進，擴大它的應用范圍，使其能夠應用到視頻和網格的修復工作當中。
參考文獻
[1] BERTALMIO M, SAPIRO G, CASELLES V,et al. Image inpainting[A]. In:Proceedings of International Conference  on Computer Graphics and Interactive Techniques[C]. New Orleans,Louisiana, USA,2000:417-424.
[2] CHAN T, SHEN J. Mathematical models for local nontexture inpainting [J]. SlAM Journal of Applied Mathematics,2001,62(3):1019-1043.
[3] EFROS A A, FREEMAN W T. Image quilting for texture synthesis and transfer[A]. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH[C]. Los Angeles,2001:341-347.
[4] BCAALMIO M, VESE L, SAPIRO G, et a1.Simultaneous texture and structure image inpainting[J]．IEEE Transactions on Image Processing,2003,12(8):882-889.
[5] CRIMINISI A,PEREZ P, TOYAMA K. Object removal by exemplar-based inpainting[A]. in:Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition[C]. Monona Terrace Convention Center Madison,Wisconsin,USA,2003,2:18-20.
[6] 魏琳,陳秀宏.基于紋理方向的圖像修復算法[J]. 計算機應用,2008,9(28):2315-2317.