鄭成松，李 琦

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

0 引言

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

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

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

1 算法基礎(chǔ)

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

1.1 計算優(yōu)先級

圖1 Criminisi算法過程

圖2 Criminisi算法符號示意圖

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

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

(1)

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

(2)

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

1.2 搜索最佳樣本塊并填充

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

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

(3)

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

(4)

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

1.3 更新置信度

循環(huán)一次后，原先未知的樣本塊已經(jīng)變成確定的樣本塊，置信度也產(chǎn)生相應(yīng)的變化。置信度的更新公式如下：

(5)

重復以上的步驟，直至待修復的區(qū)域面積為零，結(jié)束修復。

2 算法改進

2.1 改進優(yōu)先權(quán)

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

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

圖3 修復順序錯亂圖

圖4 置信項迅速下滑圖

觀察兩個相同大小的待修復塊，可以發(fā)現(xiàn)已知信息區(qū)域呈現(xiàn)包圍情況比已知信息區(qū)域呈現(xiàn)半包圍情況的修復效果更佳。為了更有利地獲取呈包圍情況的樣本塊，在已知像素相等的情況下，將已修復的像素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算法則利用圖像樣本塊之間的正相似進行修復。正相似情況十分常見，但是對稱相似的結(jié)構(gòu)在圖像中同樣十分普遍，Criminisi等修復方法中并未有利用到圖像之間的對稱相似的方法。因此，本文將圍繞圖像的對稱相似的特性，提出另外一種修復思路。

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

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

(8)

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

圖6 樣本塊對應(yīng)規(guī)則

3 本文算法

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

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

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

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

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

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

4 實驗

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

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

圖8 去除騎手的修復效果

圖9 移除人物圖片

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

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

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

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

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

5 結(jié)論

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