張巧煥，唐向宏，2，任澍

1.杭州電子科技大學通信工程學院，杭州 310018

2.杭州電子科技大學信息工程學院，杭州 310018

區(qū)域自適應的圖像修復算法

張巧煥1，唐向宏1，2，任澍1

1.杭州電子科技大學通信工程學院，杭州 310018

2.杭州電子科技大學信息工程學院，杭州 310018

基于樣本的Criminisi算法是紋理合成圖像修復技術中的經(jīng)典算法[1-3]，文中稱之為Criminisi算法，它通過定義優(yōu)先級函數(shù)來確定圖像修復的順序，并使用窮盡搜索的方式在整幅圖像的已知信息中尋找最優(yōu)匹配像素塊，并能夠同時修復結構和紋理信息，取得了較好圖像修復效果。但是Criminisi算法使用全局搜索的方式尋找最優(yōu)匹配塊，導致算法耗時較多并出現(xiàn)一定的錯誤匹配；同時在修復的過程中使用固定大小的像素模板，在一定程度上導致了在結構處信息的誤匹配，造成了修復結果的失真。

針對這些不足，不少學者也從不同的角度進行了改進探索。Feng Τang等人利用紋理相似性對圖像進行區(qū)域劃分和相干置信度衡量[4]，不僅減少了修復時間，也在一定程度上提高了圖像修復的精度和抑制了誤差的傳播，但是由于對不同紋理的邊界定義模糊，所以在某些情況下也會出現(xiàn)較大的修復誤差。張紅英[5]和魏琳[6]等人使用梯度信息來決定修復模板的大小，但在紋理方向不明顯時，梯度的計算不準確，圖像的修復效果則不夠理想；同時由于使用梯度信息自適應選擇修復像素塊大小，在一定情況下梯度計算不準確，可能會導致一定的錯誤匹配，從而影響圖像的修復效果。

因此，本文通過對破損區(qū)域的形狀和尺寸進行分析，以及待修復像素點鄰域中邊界的存在和強弱情況，從最優(yōu)匹配像素塊搜索的區(qū)域和修復像素塊大小的自適應選擇來探討基于樣本的圖像修復算法Criminisi圖像修復改進算法。

1 Criminisi算法的基本原理

Criminisi算法主要由三部分組成[3]：（1）優(yōu)先級計算；（2）最優(yōu)匹配像素塊的搜索和像素信息更新；（3）置信度更新。

圖1 Criminisi算法修復示意圖

（1）優(yōu)先級計算。在優(yōu)先級的計算過程中，首先確定待修復區(qū)域的邊緣，從而計算邊緣上各像素點的優(yōu)先級。待修復區(qū)域邊緣上任意一個像素p的優(yōu)先級函數(shù)P(p)定義為：

式中，置信項C(p)和數(shù)據(jù)項D(p)的大小分別為：

其中，|ψp|是ψp的面積，α是歸一化系數(shù)（對于8位的灰度圖像，α=255）。C(p)是像素點p周圍可靠信息的數(shù)目的一種度量。初始化時，置C(p)=0 ?p∈Ω，C(p)=1，?p∈Ι-Ω。D(p)表示每次迭代時輪廓δΩ處等照度線與邊界法向量的內(nèi)積，兩者的夾角越小，優(yōu)先級越高，它反映的是圖像的結構信息。

（2）尋找最優(yōu)匹配像素塊。一旦待修復區(qū)域邊緣上各個像素點的優(yōu)先級值計算出來，具有最大優(yōu)先級的點p對應的像素塊ψp就確定下來了，然后在整個圖像的已知信息區(qū)域中尋找與ψp最相似的圖像塊，即最優(yōu)匹配像素塊，它是通過式（4）計算得到的最小值。

其中，m、n表示像素塊的長度和寬度，p表示待修復像素塊中的像素，q表示匹配像素塊中的像素。

（3）像素灰度值和置信度的更新。當找到最優(yōu)匹配塊后，用最優(yōu)匹配像素塊中對應像素的數(shù)值填充待修復像素塊中的未知像素，從而完成一次修復。由于原來的未知像素變?yōu)橐阎袼?，此時，它們的置信度也需要更新，更新的方式如下：

重復步驟（1）～（3），直至所有的未知像素都修復完畢。

2 算法的改進

2.1 搜索區(qū)域尺寸的確定

由于馬爾可夫隨機場模型是紋理圖像的一種客觀認識，它體現(xiàn)了紋理的局部性和穩(wěn)定性，即一個像素點或像素塊的亮度都可以由它們的鄰域像素唯一確定，而與圖像的其他部分無關[7]。由于圖像破損程度的大小，直接影響圖像中剩余已知像素的多少，所以當用像素的鄰域信息決定其亮度時，其鄰域尺寸應與圖像的破損大小有關。

因此，可通過對圖像中破損區(qū)域的形狀和尺寸進行判斷分析，確定最優(yōu)匹配像素塊的搜索區(qū)域[8]，且此搜索區(qū)域為以待修復像素為中心的正方形像素塊（為了方便說明，文中以像素為單位測量破損區(qū)域的尺寸）。

首先，根據(jù)數(shù)學中縱橫坐標的概念，找出橫坐標方向和縱坐標方向的最大尺寸，并分別定義為破損區(qū)域的橫向尺寸和縱向尺寸；當破損區(qū)域的橫向尺寸和縱向尺寸相差較大時，規(guī)定其中較小者對應的坐標方向為破損區(qū)域的主方向；其次，文中定義破損區(qū)域主方向上的最大破損尺寸為搜索區(qū)域基值νal；最后，根據(jù)圖像破損區(qū)域的面積大小及其包含結構紋理信息不同，建立搜索區(qū)域尺寸與搜索區(qū)域基值之間不同的函數(shù)關系。

經(jīng)過大量反復的實驗證明，搜索區(qū)域基值等于30是劃分破損區(qū)域“狹長”型與“非狹長”型的閾值。而且本文規(guī)定：當破損區(qū)域存在主方向，并且搜索區(qū)域基值不大于30時，稱此破損區(qū)域為規(guī)則性破損區(qū)域；如果破損區(qū)域不存在主方向或者搜索區(qū)域基值大于30，則稱之為非規(guī)則性破損區(qū)域。

因此，破損圖像搜索區(qū)域尺寸與搜索區(qū)域基值νal的關系如下：

（1）由于規(guī)則性破損區(qū)域的搜索區(qū)域基值不大于30，所以破損區(qū)域整體上屬于“狹長”型，圖像剩余的已知信息比較豐富，則此時的搜索區(qū)域邊長S定義為：

（2）如果搜索區(qū)域基值大于30，不論破損區(qū)域是否存在主方向，則破損圖像的正方形搜索區(qū)域邊長S采用下式計算：

（3）當圖像中存在多個破損區(qū)域時，則分別計算各自的搜索區(qū)域尺寸，判斷各自是規(guī)則性破損區(qū)域或非規(guī)則性破損區(qū)域，其對應的搜索區(qū)域邊長按照式（6）和式（7）計算，并且當圖像破損區(qū)域周圍的結構或紋理信息比較復雜時，也通過式（7）計算其搜索區(qū)域的邊長。

2.2 自適應修復模板大小的確定

現(xiàn)有的圖像修復方法大多是利用圖像中的已知信息首先恢復破損區(qū)域中信息的結構，然后再恢復結構中的具體信息[1]，這也體現(xiàn)了格式塔原理中人眼對圖像信息的低層和高層感受[9]。通常情況下，圖像的結構信息理解為圖像中物體的邊界，因此，利用邊界信息來引導圖像修復，會提高圖像修復的準確度。通常認為，在紋理和結構較平滑的區(qū)域，修復時應選擇較大尺寸的像素塊，這樣既不影響圖像的修復效果，還相應地提高了修復執(zhí)行的效率；當破損區(qū)域中包含的紋理比較豐富，或者包含明顯的結構信息時，為了避免產(chǎn)生較大的修復誤差，因此應選用較小尺寸的修復像素塊。

由于邊界信息在圖像修復中的重要影響和引導作用，所以利用邊界信息確定修復模板大小則會在一定程度上提高圖像修復的精度和質量。文中根據(jù)人眼視覺系統(tǒng)對圖像信息交界處對比度的感知能力，按照對比度由強到弱的程度依次把邊界分為強邊界、較強邊界和弱邊界（平滑區(qū)域）三種類型。

通過對多幅不同圖像不同信息交界處對比度的分析和總結，得到邊界處信息對比度的不同，實質上是邊界處像素差值的不同，即相鄰像素數(shù)值相差越大，它們之間的邊界越明顯；反之，當它們之差低于某一定值時，則它們之間的邊界表現(xiàn)不強烈。同時，文中規(guī)定強邊界存在時相鄰像素的最小差值為35；較強邊界存在時相鄰像素的最小差值為15，最大差值為35；而當相鄰像素的差值小于15時，則認為像素處于平滑區(qū)域。

同時，為了找出像素點鄰域中邊界的存在和強弱情況，確定一個以待修復像素點為中心的7×7鄰域像素塊，并通過對該像素塊的相鄰列差值矩陣K2{7×6}和相鄰行差值矩陣K3{6×7}的矩陣元素進行分析找出其存在的邊界情況（如果元素相減的過程中有未知像素存在則此處差值置0）。

若令numel計算矩陣中滿足一定條件的元素個數(shù)，則本文規(guī)定：

（1）當矩陣K2滿足：

或矩陣K3滿足：

則認為待修復像素點鄰域中存在強邊界，修復該未知像素時采用大小為3×3的像素塊。

（2）當矩陣K2和矩陣K3滿足：

則認為待修復像素點鄰域中存在較強邊界，修復該未知像素時采用大小為5×5的像素塊。

（3）當矩陣K2和矩陣K3滿足：則認為待修復像素點處于弱邊界或平滑區(qū)域中，修復該未知像素時采用大小為7×7的像素塊。

2.3 置信度的更新和圖像修復順序

由于圖像修復的結果只是在一定相似程度上對原始完整圖像的呈現(xiàn)，因此并不等同于原始完整圖像。如果修復后的圖像在人眼視覺系統(tǒng)觀察下沒有明顯的誤差，則稱修復結果與原始完整圖像近似，如果填充的像素與原始像素的數(shù)值相同，稱之為像素的重現(xiàn)；如果填充的像素與原始像素的數(shù)值之差在一定小的范圍內(nèi)，稱之為像素的近似，填充的像素稱為原始像素的相似像素點。較理想的圖像修復結果即是用破損像素的相似像素填充的結果。通過大量的實驗及驗證，文中定義：如果兩個像素點的數(shù)值之差不大于4，即它們之間沒有可識別的邊界，則稱這兩個像素點相似。

Criminisi算法直接用中心像素點的置信度更新此次修復的所有未知像素，沒有考慮本次修復效果對此后圖像修復順序的確定以及誤差累積的影響。為了減少誤差的傳播，本文在像素相似的基礎上，調(diào)整了置信度更新方法[8]和圖像修復順序：

（1）如果最優(yōu)匹配塊與待修復像素塊在已有信息位置的像素相似，此時，按照Criminisi算法中的更新方式進行更新[3]，如式（8）所示：

如果最優(yōu)匹配像素塊與待修復像素塊之間的誤差在已有信息位置的像素不相似，這時，認為最優(yōu)匹配像素塊與待修復像素塊差別較大，采用以下更新方式：

（2）根據(jù)像素的相似性，調(diào)整后的圖像修復順序為：第一步，提取破損區(qū)域的初始邊緣，并按照優(yōu)先級單調(diào)遞增的順序對邊緣上的像素點進行排序。

第二步，修復當前像素序列中的最后一個像素。在區(qū)域搜索的基礎上，搜索由序列中最后一個像素對應待修復像素塊的最優(yōu)匹配像素塊；結合相似像素點的判斷方法，對當前最優(yōu)匹配塊的對應已知像素進行相似判斷：如果最優(yōu)匹配像素塊與待修復像素塊對應位置已知像素滿足像素點相似條件，則用此最優(yōu)匹配像素塊中的信息進行修復，并把該像素點從序列中刪除；如果不滿足像素點相似條件，則把此未知像素點移至像素序列的3/4位置處，并等待下次修復，直到初始邊緣上所有的像素點都不滿足修復條件。

第三步，重復第一步和第二步驟，直到新的破損區(qū)域邊緣上所有的像素點都不滿足附加匹配條件。此時按照文獻[8]進行修復，并直至所有剩余的未知像素修復完畢。

3 實驗結果及分析

為了驗證本文所討論的修復算法的可行性和有效性，在計算機上進行了大量仿真實驗，并與相關修復算法進行了實驗比較。實驗所用的計算機配置為Inter Pentium 4 CPU，主頻2.40 GHz，768 MB內(nèi)存，仿真軟件為Matlab 7.0。

圖2（a）和圖3（a）的破損區(qū)域中都包含了一些邊界信息，同時圖2（a）中也包含部分豐富的紋理信息。從Criminisi算法的修復結果可以看出，圖2（b）中強邊界處產(chǎn)生大量的信息模糊和延伸，圖3（b）中的桌子邊緣處產(chǎn)生了信息混亂和延伸，導致桌子的邊緣發(fā)生了變形；而本文改進算法的修復結果中，圖2（c）在較強邊界處的信息延伸已經(jīng)明顯減少，圖3（c）中的桌子邊緣處和桌布邊緣處的信息延伸也得到較好的恢復和抑制，但由于人物胳膊與地面的亮度近似，因此修復過程中在人物胳膊處仍產(chǎn)生了一定的延伸?？偟膩碚f，改進算法的整體修復效果比Criminisi算法更加接近滿足人眼視覺需要。

圖2 Baboon圖像修復實驗

圖3 Barbara圖像修復實驗

圖4中給出了去除圖像大面積人物和文字的修復實驗。從圖4（a）中可以看出，人物身后的圖像信息主要是平滑區(qū)域的海平面、存在較強邊界的波浪以及遠處的平滑背景。從Criminisi算法的修復結果來看，出現(xiàn)了視覺系統(tǒng)感知下的明顯的波浪信息延伸，即把圖像中的白色波浪信息延伸到如圖4（c）所示；從圖4（d）所示的本文改進算法修復結果來看，人物身后的波浪在一定程度上得到了恢復，并且與其周圍的波浪連接比較平滑，達到了較好的圖像恢復效果。

圖4 人物及文字去除實驗

由于改進算法中采用區(qū)域搜索的方法尋找最優(yōu)匹配塊，所以修復速度較之原有的Criminisi算法有很大的提高。表1給出了圖2～圖4在Criminisi算法和本文改進算法下的修復時間。

表1 Criminisi算法和本文改進算法下的修復時間s

從表1中兩種算法所用時間可以看出，Criminisi算法甚至需要幾個小時的時間完成圖像修復，本文提出的區(qū)域搜索方法則大大減少了修復時間，修復時間甚至可以達到Criminisi算法的幾十分之一。

為了驗證本文提出的改進算法的有效性，仿真實驗中也與類似的修改算法進行了性能比較。例如，與魏琳等人[6]提出的根據(jù)梯度信息自適應選擇修復像素塊大小的自適應算法進行性能比較，圖5給出了文獻[3]、文獻[6]和本文改進算法對破損圖像修復的結果。

圖5 本文改進算法與文獻[6]對Lena圖像的修復效果

從圖5（b）中Criminisi算法的修復結果可以看出，在人物帽子的強邊界處產(chǎn)生了較嚴重的信息延伸；文獻[6]采用自適應修復像素塊的方法，使圖像修復的精度有所提高，但是在人物帽子的邊界處仍出現(xiàn)一定的延伸，如圖5（c）所示；本文改進算法的修復結果雖然在人物左邊的灰色線條處也出現(xiàn)較小的誤差，但在人物帽子強邊界處以及整體視覺效果比較符合人眼視覺要求，在一定程度上修復效果好于文獻[6]的修復效果，如圖5（d）所示。

綜合以上實驗可以得出，本文提出的區(qū)域自適應Criminisi算法在大大縮短修復時間的同時，也能較好地保持破損處信息的結構和紋理特性，達到了較好的修復效果，并且能夠滿足大部分破損圖像的修復。

4 結束語

本文針對Criminisi算法使用固定大小修復模板和全局搜索的方式修復圖像，容易導致圖像在邊界處產(chǎn)生信息延伸和局部的錯誤匹配，以及整個修復過程耗時較多的問題，從圖像破損區(qū)域的尺寸和未知像素鄰域中邊界的強弱情況出發(fā)，探討了最優(yōu)匹配塊的區(qū)域搜索和自適應模板的圖像修復算法，并同時根據(jù)像素的相似性影響置信度更新和圖像修復順序。大量仿真實驗表明，本文提出的區(qū)域自適應Criminisi圖像修復算法不僅能夠有效地抑制邊界處信息的延伸，同時在一定程度上提高了修復的精度，并且大大縮短了圖像修復的時間，相對于Criminisi算法和相近算法取得了較好的修復效果。

[1]Bertalmio M，Sapiro G.Image inpainting[C]//Proceedings of SlGGRAPH，2000：417-424．

[2]張紅英，彭啟琮.數(shù)字圖像修復綜述[J].中國圖象圖形學報，2007，12（1）：1-10.

[3]Criminisi A，Perez P，Τoyama K.Region filling and object removal by exemplar-based inpainting[J].IEEE Computer Τransactions on Image Processing，2004，13（9）：1200-1212.

[4]Τang F，Ying Y，Wang J，et al.A novel texture synthesis based algorithm for object removal in photographs[C]//Τhe Ninth Asian Computing Science Conference，2004：248-258.

[5]張紅英.數(shù)字圖像修復技術的研究與應用[D].成都：電子科技大學，2006.

[6]魏琳，陳秀宏.基于紋理方向的圖像修復算法[J].計算機應用，2008，28（9）：2315-2317.

[7]Efros A，Leung Τ.Τexture synthesis by non-parametric sampling[C]//IEEE International Conefrence on Computer Vision，1999：1033-1038.

[8]張巧煥，唐向宏，任澍.基于樣本的快速圖像修復算法[J].杭州電子科技大學學報，2011，31（5）：139-142.

[9]Koffka K.Principle of Gestalt psychology[M].London：Lund Humphries，1935.

ZHANG Qiaohuan1,ΤANG Xianghong1，2,REN Shu1

1.School of Communication Engineering,Hangzhou Dianzi University,Hangzhou 310018,China
2.School of Information Engineering,Hangzhou Dianzi University,Hangzhou 310018,China

Τhe exemplar-based image inpainting algorithm proposed by Criminisi and his partner,which uses exhaustive searching to get the best-matching patch and adopts fixed-size patch to fill the image,will cause error matching and information extension. For this problem,based on the decisive role of a pixel’s neighboring block in the pixel’s value and the importance of structure information,this paper presents an image inpainting algorithm based on regional searching and adaptive template to enhance the local information harmony and boundary recovery ability,so it can improve the whole inpainting effect.A number of experiment results demonstrate that the improved method not only reduces the inpainting time and keeps the structure better,but also has a better visual effect.

Criminisi;exemplar-based;image inpainting;boundary;regional searching;adaptive template

針對Criminisi等人提出的基于樣本的圖像修復算法使用窮盡搜索的方式尋找最優(yōu)匹配像素塊，以及采用固定大小的修復像素塊進行修復時產(chǎn)生的錯誤匹配和信息延伸對圖像修復質量的影響，根據(jù)像素點周圍鄰域信息對該像素點的決定作用和結構信息的重要性，提出一種區(qū)域搜索和自適應模板圖像修復方法，以增強信息的局部協(xié)調(diào)性和邊界信息的恢復能力，提高圖像整體的修復效果。大量實驗表明，改進算法在減少修復時間的同時，能較好地保持圖像的結構，從而使修復結果達到更好的視覺效果。

Criminisi算法；基于樣本；圖像修復；邊界；區(qū)域搜索；自適應模板

A

ΤP391

10.3778/j.issn.1002-8331.1201-0216

ZHANG Qiaohuan,TANG Xianghong,REN Shu.Regional and adaptive image inpainting algorithm.Computer Engineering and Applications,2013,49（21）：160-163.

張巧煥（1984—），女，碩士，研究方向：多媒體信息與技術；唐向宏（1962—），男，博士，教授，研究方向：小波理論以及多媒體通信；任澍（1987—），男，碩士，研究方向：多媒體信息與技術。E-mail：qiaohuan1984@163.com

2012-01-12

2012-11-19

1002-8331（2013）21-0160-04