基于改進優先權的對稱相似圖像修復算法

鄭成松，李 琦

(福州大學 物理與信息技術學院，福建 福州 350108)

0 引言

許多藝術珍品在漫長的時間長河中會被慢慢侵蝕，圖像修復是人們為了修復損壞的圖像而興起的一項技術。隨著時代的變遷，數字圖像修復的技術應聲而出，它根據待修補區域圖像的鄰域信息來推算待修補區域中已損失的圖像信息，進而達到修補圖像的目的。數字圖像修復是在2000年的一個學術會議上提出的術語。從那時起技術蓬勃發展，例如Gram-Schmidt融合算法[1]。這些圖像修復的方法與手工修復相比更加快速、穩定，消耗的人力與物力大大減少。

BERTALIMIO M等人最早將高階偏微分方程(PDE)引入圖像處理中來估計等照線的方向，典型的PDE算法是BSCD模型[2]，利用三階高階微分方程模擬平滑傳遞的過程，保證了邊緣的連續性。SHEN J等人提出變分(TV)模型，在修復小規模的破損方面表現良好，但是在修補區域的邊界上有時不能修補得很自然[3]。CHAN T F等改進了TV模型[4]，在方程中加入了曲率，利用曲率更好地預測信息傳遞方向，這就是利用曲率驅動的修復模型(Curvature Driven Diffusion,CCD)。

基于紋理算法的代表之作是由CRIMINISI A[5]等人提出的。他們提出的算法是在整個圖像內遍歷搜索最合適匹配塊，這個過程的時間消耗巨大。曾接賢等人[6]改進了基于樣本塊算法中置信因子的賦值方法，提高了該算法的修復效果，并較大程度地縮短了時間。Criminisi算法在處理結構相似性較大的圖像時效果并不理想。因此本文針對Criminisi算法的缺點提出一種改進優先權的算法并針對對稱結構的圖像有更好的處理結果。

1 算法基礎

Criminisi算法只包括三個步驟：計算優先級搜索最合適匹配塊并填充以及更新置信度。該算法結合偏微分方程，利用圖像塊之間的相似，尋找最合適的匹配塊并填充到相應位置，是一個比較經典的圖像修復算法。算法過程如圖1所示，循環該過程直至將待修復區域填充完整為止。

1.1 計算優先級

圖1 Criminisi算法過程

圖2 Criminisi算法符號示意圖

計算優先級P(p)的公式為：

P(p)=C(p)·D(p)

(1)

其中C(p)、D(p)的計算過程如公式(2)所示：

(2)

式中|Ψp|表示樣本塊的數量，初始時，Φ中的C(p)值是1，Ω中的C(p)值是0，α是一個歸一化的值，當圖像為灰度圖像的時候α的值為255。

1.2 搜索最佳樣本塊并填充

假設Ψp為經過計算后優先級最高的破損塊，Ψq為找到的樣本塊，最優匹配應該滿足公式(3)：

Ψq=argmin(D(Ψp,Ψq))

(3)

其中D函數為相似性度量，灰度圖像可表示為:

(4)

彩色圖像的計算公式與上式相差無二，計算差值時只計算RGB分量的差值即可。

1.3 更新置信度

循環一次后，原先未知的樣本塊已經變成確定的樣本塊，置信度也產生相應的變化。置信度的更新公式如下：

(5)

重復以上的步驟，直至待修復的區域面積為零，結束修復。

2 算法改進

2.1 改進優先權

Criminisi算法中的破損區域的修復順序由優先權P(p)項決定，優先權的計算公式如式(1)所示，置信項C(p)和數據項D(p)乘積構成的。C(p)的值介于0和1之間，代表已知像素的比例，C(p)值越高，優先權越大。D(p)是等照線方向與邊界方向的點積，保證了圖像的修復方向是沿著等照度線的方向進行的。置信項C(p)與D(p)兩項在修復過程中是一種相互制約又相互補充的關系。

C(p)在計算多次后出現了迅速下滑的情況，這導致了D(p)在優先權計算過程中發揮不了作用，效果如圖3所示，因此計算出的優先權也變得不準確，將導致修補順序的錯亂。圖4是采用Criminisi算法修復時，C(p)與D(p)的變化情況。可以從圖4(a)中看出C(p)在200次迭代和400次迭代的時候出現了明顯的下滑，接下來的數值即趨于0。再從圖4(b)觀察D(p)的走勢，D(p)的整體比較穩定，在迭代700次左右時出現了下滑，P(p)受D(p)的影響因素較小。根本原因在于優先權的計算方式不合理，乘法運算在一項趨于0時，將直接忽視另一項的作用。文獻[7]修改乘法運算為加法運算，并為D(p)與C(p)分別分配兩個權重值α與β，使得P=αC(p)+βD(p)，這樣D(p)項在優先權的計算中能夠占到正常的權重，但是在圖像結構復雜的破損區域會有斷裂的情況。

圖3 修復順序錯亂圖

圖4 置信項迅速下滑圖

觀察兩個相同大小的待修復塊，可以發現已知信息區域呈現包圍情況比已知信息區域呈現半包圍情況的修復效果更佳。為了更有利地獲取呈包圍情況的樣本塊，在已知像素相等的情況下，將已修復的像素q與中心位置的距離參考加入作為置信項C(p)，如此置信項的值越大說明已知像素對中心點的包圍程度越大，越利于修復。重新定義得到的置信項為:

(6)

式中，n為樣本塊中的已知像素(除去中心點)，Distance(p，q)是已知像素點q到中心點p的棋盤距離，樣本塊中所有像素點的距離如圖5所示。其中Distance()取得的為已知像素q點的x，y坐標與中心點的x，y坐標差值的最大值，定義為：

Dis(p,q)=max(|qi-pi|,|qj-pj|)

(7)

圖5 樣本塊中所有像素點的距離

2.2 相似度

基于樣本塊的圖像修復算法大都利用圖像塊之間的相似性。相似性分為兩種，一種是正相似，另外一種是對稱相似。Criminisi算法則利用圖像樣本塊之間的正相似進行修復。正相似情況十分常見，但是對稱相似的結構在圖像中同樣十分普遍，Criminisi等修復方法中并未有利用到圖像之間的對稱相似的方法。因此，本文將圍繞圖像的對稱相似的特性，提出另外一種修復思路。

針對對稱相似圖像的特征，將對稱相似的具體情況分析清楚，針對不同的對稱相似圖像需采用不同的處理方式。如水平方向的對稱情況，圖像的對稱軸是垂直的，處理時則需將匹配圖像塊旋轉后再與需匹配的樣本塊進行比較計算。這樣水平方向的對稱情況對于對稱相似來說是一種特殊的情況，為了針對普遍的對稱相似圖像，需要計算出準確的圖像對稱相似角度之后將旋轉后的圖像塊再與匹配塊進行計算。計算準確的圖像對稱相似角度，循環多次，遍歷整個圖像區域，尋找出最合適的匹配塊，會造成大量的時間消耗。本文采用的是八個方向的模板來尋找最佳的對稱相似匹配塊，再根據最佳匹配塊的對應對稱規則將紋理信息填充到待修復區域的圖像塊之中，按照這個規則循環直至待修復的圖像區域為空為止。

為了方便快捷本文采用了八方向的對稱算法。圖6顯示了待修復的區域塊和匹配塊之間的對應關系，是以3×3的圖像模板為例，中間的圖像塊為破損的圖像塊，其他的八塊從上到下、從左到右的關系分別表示左上方、上方、右上方、左方、右方、左下方、下方、右下方的匹配塊，其中字母相同的代表像素所在的對應位置。之后根據公式(8)計算每個圖像的相似度平均值，計算過程使用灰度圖計算，若圖像為真彩色，那便根據計算公式分別計算RGB三個顏色上的相似度值，最后再求去三個值的平均值。

(8)

其中，Ψp為破損的樣本塊，Ψq為匹配到的樣本塊，xi,j為破損塊的像素值，yi0, j0為對應的匹配塊處理后的像素值，處理過程類似圖6的對應過程，將破損塊對應的a塊像素的坐標對應到匹配塊的對應坐標。

圖6 樣本塊對應規則

3 本文算法

綜合上述修改，最終算法的流程如下。

(1)傳入待修復的圖像和確定好待修復區域范圍。

(2)根據修改的置信項計算公式，更新圖像置信項。

(3)利用優先級公式計算優先級，找到最高優先級的點，記為p點。

(4)以p為中心，確立破損塊Ψp，根據修改的樣本塊匹配規則搜索最佳樣本塊，將樣本塊填入修復圖像中。

(5)判斷受損區域面積是否為零，是則結束算法，否則重復步驟(2)。

4 實驗

本文為了驗證算法的實踐效果，在內存4 GB、處理器為i5-3210M、CPU主頻為2.5 GHz的計算機上進行實驗，通過實驗得出的效果如圖7～圖9所示。

圖7 對稱相似圖像圖像修復效果

圖8 去除騎手的修復效果

圖9 移除人物圖片

圖7中，圖(a)是將屋檐的一角移除作為待修復區域進行實驗，圖(b)為Criminisi的算法結果，因為只能搜索正相似的樣本塊，所以無法對這種對稱結構的圖片進行較好的修復。其中屋檐的結構是對稱的，該算法在搜索到正相似中最為合適的樣本塊后填充，無法找到對稱的另外一個屋檐樣本塊進行處理后填充，導致錯誤的樣本塊持續迭代而出現圖(b)的效果。本文算法使用對稱相似進行匹配樣本塊，最終效果比較理想。

圖8的圖像結構比較復雜，去除圖中的騎手作為破損區域為實驗，圖(b)中的修復結果在草地上出現了些許欄桿處的樣本塊。本文在修改圖像修復的優先權后，對圖像沿著等照線的方向傳遞信息的準確度有所提高，達到了實驗的預期效果。

圖9是比較常規的圖像，可以看出Criminisi算法的處理結果已達到一定效果，但是在中間房屋邊緣的連續問題的處理上不夠理想，本文算法雖不完美，但較前者也有一定提升。

表1是Criminisi算法與本文算法對各圖的算法運行時間對比。從表格中可以看出本文在計算效率上略有遜色，原因在于本文在樣本塊匹配過程中消耗了較多的時間，但相應地在修復的效果上有較好的提升。

表1 算法運行時間比較 (s)

5 結論

本文的算法基礎是Criminisi的基于樣本塊的修復方法，針對該算法存在的沿等照線傳遞信息方向錯亂、只匹配正相似的問題提出了修改方法，并進行了實驗驗證。實驗結果表明，本文的修復方法可以做出更好的視覺效果。但在針對圖像上的適應性和運行效率上還有待提高。