基于改進(jìn)優(yōu)先權(quán)的對(duì)稱(chēng)相似圖像修復(fù)算法

鄭成松，李 琦

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

0 引言

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

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

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

1 算法基礎(chǔ)

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

1.1 計(jì)算優(yōu)先級(jí)

圖1 Criminisi算法過(guò)程

圖2 Criminisi算法符號(hào)示意圖

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

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

(1)

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

(2)

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

1.2 搜索最佳樣本塊并填充

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

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

(3)

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

(4)

彩色圖像的計(jì)算公式與上式相差無(wú)二，計(jì)算差值時(shí)只計(jì)算RGB分量的差值即可。

1.3 更新置信度

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

(5)

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

2 算法改進(jìn)

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

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

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

圖3 修復(fù)順序錯(cuò)亂圖

圖4 置信項(xiàng)迅速下滑圖

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

(6)

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

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

(7)

圖5 樣本塊中所有像素點(diǎn)的距離

2.2 相似度

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

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

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

(8)

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

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

3 本文算法

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

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

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

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

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

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

4 實(shí)驗(yàn)

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

圖7 對(duì)稱(chēng)相似圖像圖像修復(fù)效果

圖8 去除騎手的修復(fù)效果

圖9 移除人物圖片

圖7中，圖(a)是將屋檐的一角移除作為待修復(fù)區(qū)域進(jìn)行實(shí)驗(yàn)，圖(b)為Criminisi的算法結(jié)果，因?yàn)橹荒芩阉髡嗨频臉颖緣K，所以無(wú)法對(duì)這種對(duì)稱(chēng)結(jié)構(gòu)的圖片進(jìn)行較好的修復(fù)。其中屋檐的結(jié)構(gòu)是對(duì)稱(chēng)的，該算法在搜索到正相似中最為合適的樣本塊后填充，無(wú)法找到對(duì)稱(chēng)的另外一個(gè)屋檐樣本塊進(jìn)行處理后填充，導(dǎo)致錯(cuò)誤的樣本塊持續(xù)迭代而出現(xiàn)圖(b)的效果。本文算法使用對(duì)稱(chēng)相似進(jìn)行匹配樣本塊，最終效果比較理想。

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

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

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

表1 算法運(yùn)行時(shí)間比較 (s)

5 結(jié)論

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