一種基于區域搜索的快速圖像修復算法

張巧煥，唐向宏，任 澍

(杭州電子科技大學通信工程學院，浙江杭州310018)

0 引言

圖像修復是圖像處理的一個分支，屬于圖像復原的研究領域。圖像修復是指根據圖像破損區域的已知鄰域信息來對破損區域進行修復的技術［1－4］。目前，圖像修復主要分為基于結構圖像的修復和基于紋理圖像的修復兩種方法。前者由文獻1最早提出，它使用一種偏微分方程來實現圖像的修復，適用于修復小尺度的缺損。后者最早由文獻2提出一種基于象素的紋理合成，主要適用于修復大面積的破損。之后，文獻3提出一種基于樣本的圖像修復算法，本文稱之為Criminisi算法，它將結構信息和紋理特征結合起來，取得了不錯的合成效果，目前已經成為紋理合成技術中的典型算法。國內的一些學者針對圖像修復中存在的問題，也提出了一些改進算法［5－7］。本文針對文獻3中采用全局搜索進行匹配耗時嚴重的問題，探討在保證圖像修復質量的前提下，圖像最優匹配塊的搜索區域的確定準則。

1 Criminisi算法的基本原理

Criminisi算法的修復圖像過程主要分為3個步驟:(1)優先級的計算;(2)搜索最優匹配塊并填充待修補區域;(3)更新置信度和提取新的修復邊緣。

優先級的定義，即是待修復邊緣上任意象素點p的優先級函數P(p)定義為［3］:

式中，置信度項C(p)和數據項D(p)分別為:

式中，|Ψp|表示Ψp的面積，α是歸一化系數(例如，對于8位的灰度圖像，α=255)。C(p)用來度量象素點p周圍可靠信息的數目。初始化時，置C(p)=0?p∈Ω;C(p)=1?p∈I－Ω。D(p)表示每次迭代時輪廓?Ω處等照度線與邊界法向量的內積，兩者的夾角越小，優先級越高，它反映的是圖像的結構信息。

Criminisi算法采用中顏色平方差的和(Sum of Squared Differences，SSD)為匹配準則，SSD的大小定義為:

式中，p表示待修復象素塊中的象素點，q表示匹配塊中的象素點，m和n分別表示圖像的長度和寬度。當搜索整幅圖像的已知信息區域后，找到SSD最小的象素塊即為最優匹配塊Ψ。

算法中未知象素的置信度更新公式如下:

2 算法的改進

對于置信度的更新。在Criminisi算法修復的過程中，是用最優匹配塊中的相應象素信息填充源圖像塊中對應的未知象素，并用先前計算出來的源圖像塊的置信度來更新填充的未知象素的置信度［2］。在此過程中，沒有考慮到本次修復的效果。顯然，如果最優匹配塊對應的SSD值越大，C(p)也應越小，Criminisi算法容易導致修復效果越來越差，從而形成它的貪婪性。

為了突出填充的象素點的置信度與本次修復效果的關系，本文規定了置信度的更新原則［5、6］:如果最優匹配塊對應的SSD值小于閾值th，則填充象素點的置信度值，用源圖像塊的置信度值直接更新;如果SSD的值大于th，則采用下式進行更新:

對搜索區域的重新定義。在Criminisi算法中，為了找到與源圖像塊最匹配的象素塊，搜索在整個圖像區域的已知信息中進行，因此耗費時間較多。事實上，源圖像中與待修復素塊中信息相關的信息只存在于一定的區域中，根據馬爾可夫隨機場模型對紋理局域性和穩定性的認識［7］，本文將搜索區域限定在以待修補象素點為中心的S×S正方形鄰域內。

搜索鄰域S×S的大小可根據破損區域的形狀來確定。首先確定破損區域的大致走向，即偏橫向破損或偏縱向破損。假設破損區域為偏橫向破損，破損區域縱向方向的最大寬度值為max。如果破損區域為‘狹長形’，即max較小，則直接用max作為正方形邊長減1的一半;如果max足夠大，破損區域中則包含足夠多的信息，此時應當給正方形鄰域增加一定的尺度，以此得到更合理的修復結果。對大量的圖像進行反復實驗和驗證，本文取max的臨界值為30，即當max＜=30，則取S=2×max+1;max＞30，S=2×max+n±1，在n為偶數時取‘+’，n為奇數時取‘－’。其中表示相鄰的較大整數。反之，若破損區域為偏縱向，則max為破損區域橫向方向的最大寬度值。

3 實驗仿真

本文選取了多幅具有代表性的圖像進行修復，并比較了改進算法與原算法進行性能。圖像修復塊大小為5×5，閾值th=11，圖像的修復效果采用峰值信噪比值(Peak Signal to Noise Ratio，PSNR)作為客觀評價指標。

首先，本文選取原算法中的圖像驗證本文算法的正確性，同時改進原有算法對圖像進行修復，如圖1所示。

圖1 原文獻圖像Triangle圖

為了驗證改進算法的有效性，本文選取不同的圖像進行試驗，如圖2、3所示。

圖2 Barbara圖

圖3 Balls去除實驗

從以上兩組圖像修復實例中可以發現，本文提出的改進算法在修復圖2中較強結構處以及圖3中較大修復區域時，修復效果比原有算法的修復效果更加貼近原始圖像，也更加符合人眼視覺。

4 結束語

本文在Criminisi算法的基礎上，充分結合圖像結構和紋理特征，從最優匹配塊的搜索區域和置信度更新角度，探討Criminisi算法的改進方法。實驗結果表明，改進算法的修復效果比原算法的有一定的提高，同時大大減少了修復時間，實現了修復的實時性。但是由于破損區域的不定形性和包含信息的不同，以及算法固有的貪婪性，在一定情況下，修復結構性很強的區域時仍會出現一定的修復誤差，這也是今后的工作需要解決的問題。

［1］ Bertalmio M，Sapiro G.Image Inpainting［C］.New York:Proceedings of SlGGRAPH，2000:417－424.

［2］ Efros A，Leung T.Texture synthesis by non-parametric sampling［C］.Kerkra:Proceeding of the Intemational Conference on Computer Vision，1999:1 033 － 1 038.

［3］ Criminisi A，Perez P，Toyama K.Region filling and Object removal by exemplar-based image inpainting［J］.IEEE Transactions on Image Processing，2004，13(9):1 200 －1 212.

［4］ 張紅英，彭啟琮.數字圖像修復綜述［J］.中國圖象圖形學報，2007，12(1):1－10.

［5］ 代仕梅，張紅英，曾超.一種基于樣例的快速圖像修復算法［J］.微型機與應用，2010，29(22):34－36.

［6］ 楊秀紅，王慧琴，李蘇莉.基于自適應模板和置信度更新的圖像修復算法［J］.電子科技，2009，22(12):69－72.

［7］ 付紹春，樓順天.基于區域紋理合成的圖像修補算法［J］.電子與信息學報，2009，31(6):1 319－1 322.