朱園珠， 朱曉臨， 陳 嫚， 李雪艷

（合肥工業(yè)大學 數學學院，安徽 合肥 230009）

基于改進優(yōu)先級的自適應圖像修復算法

朱園珠， 朱曉臨， 陳 嫚， 李雪艷

（合肥工業(yè)大學 數學學院，安徽 合肥 230009）

文章基于Criminisi算法，提出了改進優(yōu)先級的自適應樣本塊匹配算法，在Criminisi算法的優(yōu)先級中增加了信息項，使圖像的修復順序更加合理；針對以往修復圖像時樣本塊大小固定不變，造成圖像的不合理結構累積，部分區(qū)域的局部結構丟失等不足，提出一種改進的自適應樣本塊匹配方法，其核心思想是通過局部結構特征，確定修復樣本塊大小。實驗結果表明，所提算法對許多圖像都能取得較好的修復效果。

圖像修復；優(yōu)先級；信息項；結構特征；自適應

圖像修復［1］是根據圖像修補的已知領域信息，估計被修復區(qū)域缺失信息的過程，其目的是使觀察者在無法察覺的條件下，對缺失區(qū)域進行恢復［1］。圖像修復主要用在破損圖像修補、珍貴文物的復原及文字或物體等目標對象的移除等。目前圖像修復方法主要有基于結構的圖像修復方法和基于紋理的圖像修復方法。

基于結構的圖像修復方法是一類用于修復小尺度缺損的數字圖像修補技術。文獻［2］最早將偏微分方程方法應用于圖像修復，其基本思想是沿著圖像等照度方向將已知區(qū)域信息傳輸到缺損區(qū)域，該算法對破損區(qū)域較小的結構圖像修復效果較好；文獻［3－6］對這類方法進行了一系列的改進，提高了算法效率，改善了修復效果。

基于紋理的圖像修復方法，主要用于針對破損區(qū)域比較大的圖像進行修復。這類算法主要是利用匹配準則在圖像未損壞區(qū)域尋找最相似的紋理像素塊，然后填充到圖像破損區(qū)域的修復過程。文獻［7－8］提出的基于樣本的圖像修復方法是這類方法中比較典型的算法；文獻［9］對Criminisi方法進行了改進，提出一種依據一致性局部搜索方法 （Coherence－Based Local Searching，簡 稱CBLS）的算法來完成破損圖像的修復；文獻［10］提出了一種基于非局部信息的圖像修復算法，從圖像的已知信息中選取多個樣本塊，根據每個樣本塊與待修復塊的相似性確定其權重信息，從而達到用多個塊的和與待修復塊匹配；文獻［11］在Criminisi算法中改進了優(yōu)先級計算，增加了邊界對修復順序的影響，對部分圖像的修復起到積極的作用；文獻［12］改進了最佳匹配塊的選取標準，考慮到匹配塊與待修復塊的距離，使選取的最佳匹配塊更合理；文獻［13－15］提出了自己的改進方法，取得了一定的進展；文獻［16］提出了一種自適應樣本塊大小的算法，該算法能夠根據完好區(qū)域圖像像素所處鄰域的結構信息，自適應選取樣本塊的大小，對一些具有復雜背景的圖像能得到較好的修復效果；文獻［17］對文獻［16］提出的算法進行了改進，對最佳樣本塊提出了約束條件，修復效果更好，但是在優(yōu)先級計算和區(qū)域搜索等方面沒有改進，時間復雜度依然很大。

本文在Criminisi算法基礎上，提出了一種改進優(yōu)先級的自適應樣本塊匹配的圖像修復算法。

1 Criminisi算法及存在的問題

1.1 Criminisi算法

文獻［7］提出了基于樣本的圖像修復方法，主要是用于區(qū)域較大的塊，能保持一些簡單的紋理，同時對變化比較明顯的區(qū)域也能起到較好的修復效果。

Criminisi算法示意圖，如圖1所示。

圖1 Criminisi算法示意圖

其中，I為待修復圖像；Φ為待修復圖像的已知區(qū)域；Ω為待修復區(qū)域，其邊界為?Ω；Ψp為以p∈?Ω為中心點的待修復塊。

文獻［7］認為，圖像的修復順序要有先后之分，如果順序選擇不好，很容易出現(xiàn)連鎖反應，修復效果不理想，因此，提出了由優(yōu)先級決定修復的先后順序想法。優(yōu)先級含有2個因素，即置信項C（p）和數據項D（p）。C（p）表示待修復塊中已知區(qū)域中像素點個數占整個待修復塊像素點個數的比值，D（p）表示每次通過邊界?Ω的等照線的強度函數，其表達式為：

其中，｜Ψp｜為待修復塊Ψp中已知像素點的個數；np是待修復區(qū)域Ω的邊界?Ω在點p處的法向量；▽為已知區(qū)域Φ的邊界的梯度向量的垂直向量；α為標準化因子，α＝255。

對?p∈Ω，（p）＝0；對?p∈I－Ω（p）＝1。取P（p）作為決定修復順序的優(yōu)先級，即

通過優(yōu)先級尋找出每一次要優(yōu)先修復的像素點，從而確定待修復的目標塊。假設待修復塊Ψ＾p具有最高優(yōu)先級，Ψ＾q是待修復區(qū)域中與Ψ＾p最匹配的塊，一般情況下，Ψ＾q整塊都應完全包含在已知區(qū)域Φ中，則

其中，d（Ψ＾p，Ψq）為2個塊中已知像素的平方誤差之和。找到Ψ＾q之后，將Ψ＾q中相應的顏色信息拷貝至Ψ＾p∩Ω的位置。

目標塊完成一次修復后，原來目標塊中的邊界像素點都變成了已知像素點，原待修復區(qū)域內的部分像素點變?yōu)橐阎袼攸c或者邊界點，這時需重新計算C（p）及邊界像素點的優(yōu)先級。更新公式如下：

重復上述步驟，直至修復所有的破損區(qū)域。

1.2 Criminisi算法中存在的問題

（1）實驗表明，隨著修復的進行，C（p）值下降很快，并趨向0，即使D（p）值很大或者上升，但是由于計算優(yōu)先級是采用乘法形式，即P（p）＝C（p）D（p），優(yōu)先級P（p）值還是隨著C（p）趨向0而趨向0，以至于后面的填充順序變得不確定［18］。因此，將計算優(yōu)先級由C（p）和D（p）相乘改為相加是合理的。

（2）在計算優(yōu)先級時，Criminisi算法只考慮了D（p）和C（p）2個影響因素，包含的信息不夠全面。這樣會使確定的修復順序不夠合理，容易造成修復過程中誤差積累，最終導致修復效果不是很理想。

（3）Criminisi算法在圖像修復過程中，樣本塊的大小是固定不變的。然而一幅圖像中通常具有各種不同的紋理結構，對所有位置都采用相同大小的樣本塊進行修復是不夠合理的，也會導致修復效果不理想。

2 本文算法

2.1 優(yōu)先級改進

針對Criminisi算法，本文提出了一種新的計算優(yōu)先級方法。在計算優(yōu)先級時考慮到待修復塊中邊界線的長度，本文定義為信息項，記作E（p），p∈?Ω。E（p）表示以p點為中心的修復塊中邊界長度與待修復塊周長的比值，分子可以理解為待修復塊中已知信息與未知信息之間的接觸的多少。信息項定義類似置信項的定義，置信項可以理解為待修復塊中已知信息的面積占整個待修復塊面積的比值，信息項是待修復塊的邊界長度與待修復塊周長的比值，信息項中分子可以表示邊界的凹凸變化程度。

如圖2所示，圖2a與圖2b對比，發(fā)現(xiàn)2個圖的置信項相同，而圖2b的E（p）比圖2a的E（p）大，說明圖2b未知區(qū)域與已知區(qū)域的接觸面更大一些，與已知信息接觸更多。這時如果數據項相同，應該優(yōu)先修復圖2b的情況。

圖2 信息項作用說明圖

在Criminisi算法中計算優(yōu)先級時，會出現(xiàn)多個像素點的優(yōu)先級P（p）相等的情況，本文算法增加了信息項，一方面使優(yōu)先級更加合理，另一方面更好地區(qū)分優(yōu)先級，減少了出現(xiàn)優(yōu)先級P（p）相等的情況。

改進后的優(yōu)先級計算公式如下：

其中，β1、β2、β3為非負常數。

信息項E（p）為：

其中，?Ω為待修復區(qū)域Ω的邊界；Ψp為以p∈?Ω為中心點的待修復塊；為待修復塊Ψp的周長；~E（q）＝1，q∈?Ω為局部邊界的長度，當q點是邊界時，在信息項中所表示的邊界長度為1（假定相鄰像素之間距離為1）；~E（q）＝0，q??Ω表示當q點不是邊界時，在信息項中所表示的邊界長度為0。

2.2 自適應樣本塊

2.2.1 自適應樣本塊提出的背景

很多基于樣本塊的圖像修復方法中，樣本塊大小都是固定不變的。由于大部分圖像含有復雜的紋理信息和結構信息，對不同位置的待修復區(qū)域，采用不同的樣本塊進行替換更為合理。本文在改進優(yōu)先級的基礎上，對樣本塊大小進行動態(tài)選擇，使得樣本塊的選取更合理、更省時。

如圖3所示，Ω為待修復區(qū)域；I為整幅圖像；?Ω為Ω的邊界；pi（i＝1，2）為待修復樣本塊的中心。圖3b中以（i＝1，2；j＝1，2）為中心的樣本塊分別是圖3a中以pi（i＝1，2）為中心的待修塊的備選對象。

圖3 樣本塊大小自適應原理說明圖

若從p1點開始修復，因為待修復塊本身結構變化不是很明顯，并且周圍的結構變化也不大，所以在修復時應該選擇半徑大一點的待修復塊，這樣可以保持圖像的整體性，同時可以節(jié)約修復的時間。如圖3a中以p1點為中心的待修復塊，可以選擇圖3b中以點或點為中心的較大樣本塊進行修復。

如圖3a所示，若從待修復點p2開始修復，因為p2點周圍結構變化較為明顯，而且周圍區(qū)域的結構變化也較大，所以為了盡量減少修復誤差，待修復塊的半徑應該選小一點，并且替換樣本塊的中心點應該選在p2點左上方線段上。如果待修復塊半徑較大，選擇的替換樣本塊半徑也應該大一些。由圖3b可以看出，如果替換塊半徑較大，修復會產生較大的誤差，所以應該選擇以q2點為中心點的內層替換塊。

通過以上分析，選取一種自適應的樣本塊修復算法是非常必要的。

2.2.2 自適應樣本塊計算方法

通常情況下，一幅圖像的梯度場可以反應圖像在局部區(qū)域的結構信息，因此，可以通過局部梯度場的變化衡量局部結構特征的變化，最后通過局部結構特征的變化確定樣本塊的大小。

設SQ（p，k）是以p為中心點、邊長為2k＋1的樣本塊，假定（2k＋1）×（2k＋1）的樣本塊半徑為k，其中p點是邊界上的待修復點。樣本塊SQ（p，k）與SQ（p，k＋1）的局部結構特征差異可以用其局部梯度場的變化體現(xiàn)，可以表示為：

其中，M（p，k，θ）為樣本塊SQ（p，k）中已知區(qū)域的像素點在θ方向的梯度向量模值的和；nk＋1、nk分別為SQ（p，k＋1），SQ（p，k）樣本塊中已知像素點個數；Mv（p，k）為SQ（p，k＋1）與SQ（p，k）局部結構特征的差異。

自適應算法說明如圖4所示。

圖4 自適應算法說明

圖4說明，p點為邊界點上優(yōu)先級最大點；Φ為圖像中的已知區(qū)域；?Ω為Ω的界；Ω為待修復區(qū)域；k1，…，ki，…，kn（n∈N＋）為以p點為中心點的待修復塊的半徑。

在確定待修復樣本塊大小之前，先提前設定樣本塊半徑的一個范圍。樣本塊半徑變化范圍設定為k1，k2，…，kn（n∈N＋），其中k1＜k2＜…＜kn，n∈N＋。修復的自適應半徑w滿足：

其中，T為常量；ki中i∈1，2，…n；ks在滿足maxMv（p，ki）≥T的條件下，定義為（11）式，即

其中，kj滿足Mv（p，kj）＝maxMv（p，ki）。

（10）式定義的半徑分如下3種情況：

（1）在給定范圍的半徑中，滿足maxMv（p，ki）＜T，即不同半徑之間局部結構特征的變化量不大，最大值小于T（T一般取20）。這說明在局部結構變化不是太明顯，修改半徑可以取大些，這時取給定范圍內的最大半徑為待修復塊的半徑kn。

（2）在給定范圍的半徑中，滿足maxMv（p，ki）≥T，即不同半徑之間局部結構特征的差異量比較大。但是如果不同半徑之間的局部結構特征整體變化不大，滿足 maxMv（p，ki）－minMv（p，ki）＜T，這時設定kn－1為待修復塊的半徑。

（3）在給定范圍的半徑中，滿足maxMv（p，ki）≥T，同時滿足 maxMv（p，ki）－minMv（p，ki）≥T，這說明局部結構特征變化比較劇烈，不同半徑之間的局部差異都很大。為了保證修復效果的同時盡量選擇較大半徑，取變化最強烈的內層半徑作為待修復樣本塊的半徑，盡量減少修復誤差。

優(yōu)先級計算出待修復中心點后，確定修復半徑步驟如下：

（1）k分別取k1，k2，…，kn－1，kn（n∈N＋），通過（7）～（9）式，計算出以p點為中心的待修復塊SQ（p，ki＋1）與SQ（p，ki）之間的局部信息差異程度，其中，1＜i＜n－1。

（2）得到n－1個Mv（p，k）數值。

（3）代入（10）式計算確定自適應待修復塊的半徑。

2.3 算法步驟

（1）確定待修復區(qū)域的邊界，通過（5）式計算邊界點上各待修復點的優(yōu)先級，選取出最大優(yōu)先級的待修復點。

（2）通過（7）～（10）式，自適應選取修復點的樣本塊大小，在圖像的已知區(qū)域搜索最優(yōu)匹配塊，替換待修復樣本塊。

（3）更新邊界。

（4）重復步驟（1）～步驟（3），直到邊界為0而停止。

3 實驗結果

本文以Matlab7.10為工具，在Intel酷睿I3雙核處理器（2.0GHz）、2G內存的PC機上運行。例1為屋頂修復，例2為石臺修復，例3為草坪修復。本文算法與Criminisi算法、文獻［11］算法、文獻［12］算法和文獻［17］算法的修復結果比較，如圖5～圖7所示。

圖5c是傳統(tǒng)的Criminisi算法修復結果，觀察發(fā)現(xiàn)圖像中修復的屋脊已經嚴重變形，湖面上出現(xiàn)了許多樹木，屋檐下面應該出現(xiàn)的水泥柱也很模糊。圖5d的修復效果相對圖5c有所改善，但是屋檐的右下角仍然出現(xiàn)了樹木，屋檐下面的水泥柱間距不相等，并且屋檐上方的一片樹木與周圍很不協(xié)調。圖5e的水與岸接觸的地方出現(xiàn)了多余石階，屋檐與周圍的實物過渡不自然，屋檐下方出現(xiàn)凌亂的樹木，導致偏差延續(xù)。圖5f是文獻［17］的自適應樣本塊算法修復結果，由于此算法除了在替換待修復塊時采用了自適應半徑，其他的流程仍然采用傳統(tǒng)的Criminisi算法思想，對優(yōu)先級的計算仍然采用數據項與置信項相乘，所以效果不是很理想。觀察圖像會發(fā)現(xiàn)，一部分湖水修到岸上，屋頂上出現(xiàn)不應有的白痕，房屋上方的樹木與周圍不協(xié)調。

圖5g是為了說明優(yōu)先級中信息項的作用而作的對比圖，圖的算法除了優(yōu)先級計算改為：P（p）＝αC（p）＋βD（p），其他步驟與本文算法一樣。從圖5g發(fā)現(xiàn)前面屋檐上出現(xiàn)了許多樹葉，水泥柱修復不夠對稱，而且最右邊水泥柱不夠完整，這是因為修復順序不夠合理造成的。

圖5h是本文算法的修復結果，由圖5h可以看出，屋檐下方的水泥柱與已有的水泥柱間距很勻稱，水與岸過渡自然，并且房屋上方修復出來的樹木和周圍的環(huán)境非常相稱。

上面幾種算法修復結果對比，尤其是圖5g和圖5h的修復結果對比表明，（5）式確定的修復順序更加合理，使修復順序更好地沿著特征明顯的方向修復。

由圖6可知，圖6c～圖6g修復都不是很理想。圖6f雖然采用了自適應樣本塊的選取方法，但是由于待修復圍墻結果變化復雜，對修復的先后順序有較高要求，所以效果也不是很明顯。

圖6g的修復算法加入了分割思想。由于優(yōu)先級定義不夠合理，使得修復順序也不合理，圖像中間修出了一條石臺，圖像的下半部分的磚臺修復不夠平整。

圖6h算法采取分割修復的思想，上半部分采用自適應樣本塊的修復算法，修復的樣本塊半徑可以取很大，修復半徑范圍為4～8，可以節(jié)省大量時間；下半部分采用自適應修復半徑在3～5范圍的修復方法，可以保持局部特征變化。

圖6h與圖6g對比可知，加入信息項優(yōu)先級使修復順序更加合理，修復結果更好地保持了圖像的顯著特質。

圖6 例2本文算法與其他算法修復結果對比

由圖7可知，圖7c～圖7f的修復效果都不是 十分理想。

圖7 例3本文算法與其他算法修復結果對比

圖7g的右下角草坪與水泥路面接觸的地方過渡得不合理，圖的中間草坪部分修成了明顯錯誤的水泥路面，這些都與修復的先后順序有關，這進一步說明本文改進優(yōu)先級的合理性。

圖7h是本文算法的修復結果，自適應半徑的設定范圍為4～8，在修復過程中發(fā)現(xiàn)這幅圖的大部分修復點取得半徑比較大，而且參數的適用范圍也比較廣，說明本文的算法魯棒性強。從修復效果上與圖7g對比，進一步體現(xiàn)了信息項對確定優(yōu)先級、建立合理的修復順序的作用。

從修復時間和效果上看，也體現(xiàn)了自適應半徑可以減少修復時間，同時更好地保持局部特征。幾種算法修復時間比較，見表1所列。

表1 修復時間比較 s

4 結束語

本文提出了一種改進優(yōu)先級的自適應樣本塊匹配算法，通過增加信息項，計算出更合理的優(yōu)先級來決定修復的順序，同時能夠針對不同的結構區(qū)域，利用圖像的局部結構信息，實現(xiàn)樣本塊大小的自動選取。實驗結果表明，本文算法的修復效果好，耗時少。

［1］張紅英，彭啟琮.數字圖像修復技術綜述［J］.中國圖象圖形學報，2007，12（1）：1－10.

［2］Bertalmio M，Sapiro G，Caselles V，et al.Image inpainting［C］／／Proceedings of International Conference on Computer Graphics and Interactive Techniques，New Orleans，Louisiana，USA，2000：417－424.

［3］Chan T F，Shen J.Mathematical models for local nontexture inpaintings［J］.SIAM Journal on Applied Math，2001，62（3）：1019－1043.

［4］Chan T F，Shen J.Non－texture inpainting by curvature－driven diffusions（CDD）［J］.Journal of Visual Communication and Image Representation，2001，12（4）：436－449.

［5］邵肖偉，劉政凱，宋 璧.一種基于TV模型的自適應圖像修復方法［J］.電路與系統(tǒng)學報，2004，9（2）：113－117.

［6］Chan R H，Wen Y W，Yip A M.A fast optimization transfer algorithm for image inpainting in wavelet domains［J］.IEEE Transactions on Image Processing， 2009， 18（7）：1467－1476.

［7］Criminisi A，Perez P，Toyama K.Object removal by exemplar－based inpainting［C］／／Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2003：721－728.

［8］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）：1200－1212.

［9］Tang F，Ying Y T，Wang J，et al.A novel texture synthesis based algorithm for object removal in photographs［C］／／Advances in Computer Science：ASIAN，2004.Berlin：Springer，2005：248－258.

［10］Wong A，Orchard J.A nonlocal－means approach to exemplarbased inpainting［C］／／Image Proceeding，2008，ICIP 2008，15th IEEE International Conference on，2008：2600－2603.

［11］黃淑兵，朱曉臨，許云云，等.一種改進的基于紋理合成的圖像修復算法［J］.合肥工業(yè)大學學報：自然科學版，2011，34（2）：313－316，320.

［12］劉麗萍.基于加權匹配塊的圖像修復方法［D］.上海：華東師范大學，2009.

［13］Nishihara A.Iterative gradient driven patch－based inpainting［C］／／Advances in Image and Video Technology.Berlin：Springer，2012：71－81.

［14］Wu X，Zeng W，Li Z.Exemplar－based image inpainting with collaborative filtering ［C］／／Image and Graphics（ICIG ），2011Sixth International Conference on，2011：8－11.

［15］Tae－o－sot S，Nishihara A.Exemplar－based image inpainting with patch shifting scheme［C］／／17th International Conference on Digital Signal Processing，2011：1－5.

［16］Zhou H L，Zheng J M.Adatptive patch size determination for patch－based image completion ［C］／／Proceedings of 2010IEEE 17th International Conference on Image Processing，Hong Kong，China，2010：421－424.

［17］孟春芝，何 凱，焦春蘭.自適應樣本塊大小的圖象修復方法［J］.中國圖象圖形學報，2012，17（3）：337－341.

［18］Cheng W H，Hsieh C W，Lin S K，et al.Robust algorithm for exemplar－based image inpainting［C］／／Proceedings of the International Conference on Computer Graphics，Imaging and Visualization（CGIV’05），2005：64－69.

Adaptive image inpainting algorithm with modified priority

ZHU Yuan－zhu， ZHU Xiao－lin， CHEN Man， LI Xue－yan
（School of Mathematics，Hefei University of Technology，Hefei 230009，China）

In this paper，an adaptive sample patch matching algorithm with a modified priority is given based on the Criminisi algorithm.An information term is added to the priority in Criminisi algorithm to make the image inpainting order more reasonable.In addition，for avoiding the problem that the sample patch size of previous restoration is fixed，which will cause the accumulation of irrational structure of the image and the loss of the local structure of some region，an improved adaptive sample patch matching method is given to determine the sample patch size by local structure features.Experimental results show that the algorithm given in the paper has good inpainting results.

image inpainting；priority；information term；structure feature；self－adaptation

TP391.41

A

1003－5060（2014）06－0683－07

10.3969／j.issn.1003－5060.2014.06.010

2013－07－02

國家自然科學基金資助項目（61272024）；第38批留學回國人員科研啟動基金資助項目（2010JYLH0322）和安徽省自然科學基金資助項目（11040606M06）

朱園珠（1989－），男，安徽宿州人，合肥工業(yè)大學碩士生；

朱曉臨（1964－），男，安徽池洲人，博士，合肥工業(yè)大學教授，碩士生導師.

（責任編輯 呂 杰）