針對匹配塊不存在的Criminisi算法改進研究

任 澍，唐向宏，康佳倫

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

0 引言

圖像修復技術主要是用來修復圖像中的破損區(qū)域或者用來去除圖像中的物體。屬于紋理合成技術的Criminisi圖像修復算法［1］，通過將最相似的目標塊填充到待修復區(qū)域來達到修復的目的，取得了較好的修復效果。但是在圖像修復的過程中，當已知區(qū)域中不存在合適匹配塊的情況下，該算法根據(jù)相似性所選擇的匹配塊往往并不能滿足修復需求，容易造成修復效果的失真。針對這一情況，文獻2通過對優(yōu)先權和搜索方式進行改進，并采用新的相似性準則來尋找匹配塊，雖然獲得了一定的效果，但是對于某些區(qū)域的修復仍然不是十分理想。Bertalmio利用圖像分解模型將圖像分解為結構部分和紋理部分，然后分別對其進行修復，對小尺度破損區(qū)域有較好的修復效果，但是對大尺度破損區(qū)域的修復容易產(chǎn)生模糊［3］。本文利用匹配塊相似度量，即誤差平方和(Sum of Squared Differences，SSD)對Criminisi算法進行了改進。通過對不良修復區(qū)域的定位，分別對結構部分和紋理部分的不良修復區(qū)域進行修復，以克服Criminisi算法中因不存在合適匹配塊造成的修復失真。

1 Criminisi修復算法特征分析

Criminisi算法是一種基于樣本的圖像修補算法，實質是直接結合結構傳輸和紋理合成的方法。這種紋理合成主要由3步組成:優(yōu)先權計算、搜索和復制［4－6］。在實際研究中發(fā)現(xiàn)，Criminisi算法在進行搜索的時候，若在已知區(qū)域中不存在合適的匹配塊，算法會使用不恰當?shù)钠ヅ鋲K去對破損區(qū)域進行填充，從而影響最終的修復效果。算法的修復效果如圖1所示，圖1(c)給出了Criminisi算法對圖像破損區(qū)域的修復效果。從圖1(c)中可以看到，Criminisi算法在修復肩膀處的曲線時沒有保持其線性結構的平滑性，使得修復邊緣出現(xiàn)了一定的凹凸。出現(xiàn)這種修復效果的主要原因是在已知區(qū)域中不存在合適的匹配塊，算法所找到的匹配塊并不能滿足曲線的修復要求。

2 Criminisi算法的改進

基于對Criminisi修復算法的分析，本算法的改進思路為先利用匹配塊的相似性度量，完成對修復失真區(qū)域的定位，然后利用基于圖像分解的圖像修復算法對失真區(qū)域重新修復。

圖1 Criminisi算法對lena的修復效果圖

2.1 修復失真區(qū)域的定位

在尋找最佳匹配塊的過程中，Criminisi算法是通過對已知象素點的SSD進行計算，并將其值最小的匹配塊選擇為最佳匹配塊［6，7］。

若將SSD值除以待修復塊中已知象素個數(shù)所得的均值設為均值象素差平方和(Average Sum of Squared Differences，ASSD)。在實驗中發(fā)現(xiàn)，當圖像的已知區(qū)域不存在最佳匹配塊時，雖然此時所尋找到的塊具有最小SSD，但是其ASSD相比于其他待修復塊仍會較大。如表1所示，表1列出了圖1(b)破損區(qū)域的部分ASSD變化情況。從表1中可以看出，當修復順序號為18時，修復塊的ASSD為350，將它與先前已修復的9 個修復塊的 ASSD(8、63、17、12、123、56、45、5、27)進行比較后可以發(fā)現(xiàn)，雖然算法在搜索時所尋找到的SSD已是最小，但它的ASSD相比于先前已修復塊仍然較大，大于它們均值的3倍(350＞212)。此時若采用匹配塊替換，就不能保證待修復塊能得到滿意的修復效果，易造成較大的偏差，從而造成如圖1(c)所示的不良修復效果。為尋找這些由于不存在最佳匹配塊而造成修復失真的區(qū)域(定義為un-matching)，本文采用以下方法來對其進行定位:

(1)對已修復塊，按修復先后順序以10個為一組，計算該修復組的ASSD均值(記為mean_ASSD)，并將該組中每個修復塊的ASSD分別與3×mean_ASSD進行比較。若修復塊的ASSD大于3×mean_ASSD，則判定該修復塊為un－matching。然后，右移一位，將該組剩余修復塊與后續(xù)已修復塊重新組成新的一組，進行類似的判斷處理，直到圖像修復完畢;

(2)在修復過程中，若待修復塊的中心點屬于un-matching(已修復)中的坐標點(即該待修復塊不完全屬于un-matching)，則在其修復完之后也歸為un-matching;

(3)在修復線性結構時，往往會因最后一個待修復塊的不匹配而造成線性修復的不連續(xù)，因此，在修復線性結構時將最后一個待修復塊歸為un-matching。最后一個待修復塊的判定原則為:在圖像用Criminisi算法進行修復之后，按修復先后順序對已修復塊進行檢索，并利用方差判斷其是否為線性結構塊。若是線性結構塊，則檢索該塊周圍的并且修復順序號在其之后的修復塊中是否有線性結構塊，若沒有，則判斷該塊為線性結構修復時的最后一個待修復塊。

表1 圖1中破損區(qū)域的部分ASSD變化情況

2.2 對修復失真區(qū)域的重新修復

當Criminisi算法對圖1(b)進行修復之后，利用Vese-Osher［8］模型將修復結果分解為結構部分u和紋理部分v。對結構部分u的修復，本文首先利用un-matching將結構部分中沒找到最佳匹配塊的區(qū)域重置為待修復區(qū)域，如圖1(d)所示。重置之后的待修復區(qū)域較小，可以使用TV模型來進行修復，但由于其修復結果容易產(chǎn)生模糊，因此需要使用拉普拉斯濾波器來對已修復部分進行濾波，修復并濾波的結果如圖1(e)所示。從圖1(e)中可以看到，結構部分修復之后，其肩膀處的曲線得到了較好的保持，取得了比較理想的修復效果。

對紋理部分v的修復本文采用文獻9中的紋理合成技術來進行修復。文獻9算法不能對所有紋理都有較好的修復效果，但是其中的優(yōu)先權保證了在修復紋理的過程中能使線性結構部分得到較好的保持。

3 實驗結果和分析

為了驗證改進算法的有效性，本文在計算機上進行了仿真實驗。圖1(f)給出了圖1(a)的修復效果，與原算法相比，改進算法對曲線等線性結構和紋理都有較好的保持，克服了原算法所固有的不足，峰值信噪比(PSNR)提高了9.108 4dB，取得了較好的修復效果。為了驗證本算法的一般適用性，本文選取不同破損區(qū)域以及不同圖像來進行實驗，如圖2、3所示。

圖2 不同區(qū)域的修復效果對比圖

圖3 圓球去除后的效果

從圖2、3的修復結果中可以看到，在修復不同的區(qū)域時，改進算法相比原算法和類似算法無論是紋理區(qū)域還是邊緣區(qū)域，都有較好的修復效果，特別是在修復曲線等較強線性結構時，有效保持了邊緣的線性特性，具有更好的視覺效果。

4 結束語

本文針對Criminisi算法在已知區(qū)域不存在合適匹配塊的情況下易產(chǎn)生修復效果失真的問題，對Criminisi算法進行了改進。改進算法首先利用平均誤差平方和完成對修復失真區(qū)域的定位，然后分別對分解為結構部分和紋理部分的這些區(qū)域進行修復。對于結構部分，采用TV模型及拉普拉斯濾波器進行修復濾波，對于紋理部分采用基于塊的紋理合成技術進行修復，之后對圖像進行重構并得到最終的修復效果。實驗證明，改進算法相比Criminisi算法有更好的修復效果。

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

［2］ 代仕梅，張紅英，曾超.一種基于樣例的快速圖像修復算法［J］.圖形、圖像與多媒體，2010，29(22):34－39.

［3］ Bertalmio M，Vese L，Sapiro G，et al.Simultaneous textureand structure image inpainting［J］.IEEE Transactions on Image Processing，2003，12(8):882 －889.

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

［5］ 吳亞東，張紅英，吳斌.數(shù)字圖像修復技術［M］.北京:科學出版社，2010:11.

［6］ 張巧煥，唐向宏，任澍.一種基于區(qū)域搜索的快速圖像修復算法［J］.杭州電子科技大學學報，2011，31(5):139－142.

［7］ 林云莉，趙俊紅，朱學峰，等.改進的紋理合成圖像修復算法［J］.計算機應用與軟件，2010，27(10):11－12.

［8］ Vese L，Osher S.Modeling textures with total variation minimization and oscillating patterns in image processing［J］.Journal of Scientific Computing，2003，19(1/3):553 －572.

［9］ Wu J Y，Ruan Q Q.A Novel Hybrid Image Inpainting Model［C］.Shanghai:International Conference on Audio Language and Image Processing，2008:138 －142.