謝伙生，潘姣君

(福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，福建福州 350116)

0 引言

圖像修復(fù)主要是利用圖像中已知區(qū)域的信息對信息缺損區(qū)域進行填充的一個過程，其目的在于恢復(fù)圖像中信息缺損的區(qū)域，以便使觀察者察覺不出圖像曾經(jīng)缺損或已被修復(fù)［1］.目前對圖像中具有大面積信息缺損的區(qū)域進行修復(fù)的主要方法為紋理合成算法，該方法主要是根據(jù)圖像中已知區(qū)域的紋理特性，來復(fù)制已知區(qū)域中紋理較為相似的圖像塊到缺損區(qū)域.圖像修復(fù)技術(shù)在古文物的保護、影視特技的制作、舊照片的修補、圖像中文字及障礙物的去除等領(lǐng)域具有廣泛的應(yīng)用.

在基于紋理合成的數(shù)字圖像修復(fù)算法中，主要有兩個難點需要解決:一是紋理塊的填充次序問題，雖然在算法中圖像的紋理特性可以較好地被保留下來，但是僅僅依靠紋理合成而忽略紋理塊的填充次序常常會使得待修復(fù)區(qū)域的邊緣特征不夠清晰，從而影響修復(fù)后圖像的視覺效果，因此合理安排紋理塊的合成次序顯得尤為重要.二是最佳匹配塊的搜索問題，一般采用的匹配準(zhǔn)則是紋理合成中常用的SSD(sum of squared differences).目前基于塊的紋理合成修復(fù)技術(shù)中代表性的成果就是Criminisi等人提出的算法［2－3］，其中文獻［2］提出的修復(fù)算法可用來修復(fù)具有較大面積區(qū)域信息缺損的圖像，其修復(fù)后圖像的結(jié)構(gòu)信息和紋理信息都得到較好的保留.文獻［3］也同樣描述了此算法，主要是用較多的例子進一步說明此算法的可行性及有效性.Criminisi算法在修復(fù)大面積區(qū)域信息缺損的圖像時雖然可以取得較為滿意的修復(fù)效果，但時間復(fù)雜度高，同時優(yōu)先權(quán)的計算還存在一定的不足，容易造成偏差的延續(xù)，使修復(fù)結(jié)果不夠理想.

針對Criminisi算法中存在時間復(fù)雜度高的不足，文獻［4］提出一種基于圖像特征值的紋理修復(fù)算法，該方法通過在匹配過程中先利用圖像平均灰度值進行快速比較，減少了大量的匹配時間，從而大幅度提高Criminisi算法的修復(fù)效率，保證了實時性.但該算法旨在保證修復(fù)效果同Criminisi算法相當(dāng)?shù)那疤嵯绿岣咝迯?fù)效率.

為了解決Criminisi算法修復(fù)中偏差延續(xù)的問題，文獻［5］提出一種優(yōu)先權(quán)遞減法，該方法使修復(fù)順序能夠按照待修復(fù)邊界上所有的強邊緣點逐個進行，保持了圖像的邊緣結(jié)構(gòu).但是其使用的遞減因子為0～1之間的值，并未指出具體取多大的值才能使修復(fù)效果達到最佳.文獻［6］在算法運行中按照隊列的先來先服務(wù)(FCFS)原則逐層對待修復(fù)區(qū)域進行修復(fù).然而該算法沒有較好地解決待修復(fù)邊界存在非線性的問題，從而使修復(fù)效果不夠理想.文獻［7］在Criminisi算法優(yōu)先權(quán)計算的基礎(chǔ)上，除了考慮置信度項和數(shù)據(jù)項外，還增加一個邊界項，使優(yōu)先權(quán)值的計算更為合理，從而使修復(fù)結(jié)果更好.然而該方法側(cè)重于修復(fù)效果的提高，其修復(fù)所需的時間較長.

本文針對Criminisi算法存在的上述兩個問題，基于文獻［4］及文獻［7］的思想，提出一種在時間和視覺效果上進行權(quán)衡優(yōu)化的方法.實驗證明，該優(yōu)化方法合理有效.

1 Criminisi算法分析

Criminisi算法的核心思想是在填充待修復(fù)區(qū)域時先計算邊界上所有待修復(fù)塊的優(yōu)先權(quán)，尋找優(yōu)先權(quán)最高的塊作為當(dāng)前待修復(fù)塊，然后在已知區(qū)域中搜索與之最為匹配的紋理塊并將其復(fù)制到缺損區(qū)域，最后更新置信度及待修復(fù)邊界，這樣就完成一次的修復(fù)過程，如此循環(huán)，直至缺損區(qū)域已被完全修復(fù)為止.

如圖1所示，對于待修復(fù)圖像I，首先手工選定待修復(fù)區(qū)域Ω，圖像的已知區(qū)域用Φ表示(Φ=I－Ω)，δΩ為缺損區(qū)域的邊界，是以點p為中心的待修復(fù)塊.

p點優(yōu)先權(quán)的計算:

式中:

圖1 符號圖Fig.1 Symbol diagram

搜索到最佳匹配塊后，復(fù)制其對應(yīng)位置處的顏色信息到待修復(fù)塊中相應(yīng)的位置，然后根據(jù)式(7)更新置信度C(p)，并抽取新的待修復(fù)邊界.

通過對Criminisi算法的分析，其仍存在一定的不足.①算法在匹配過程中，每次搜索最佳匹配塊時都要遍歷圖像已知區(qū)域中的所有紋理塊，計算每一紋理塊與待修復(fù)塊的SSD，而SSD的計算較復(fù)雜，這樣就要消耗大量的匹配時間，增加修復(fù)的時間開銷.②對純色區(qū)域來說D(p)=0，如果仍用C(p)D(p)來計算優(yōu)先權(quán)，顯然不可靠.算法先填充具有最高優(yōu)先權(quán)的點，并用缺損圖像已知區(qū)域中與其最為匹配的塊中對應(yīng)的顏色信息來填充，執(zhí)行一次后更新待修復(fù)邊界，如此循環(huán).如果循環(huán)中優(yōu)先權(quán)最高的點出現(xiàn)在剛剛填充的塊的邊界上，并且剛填充的塊中被填充了不符合視覺效果的顏色信息，這將會導(dǎo)致不合理的顏色信息向缺損區(qū)域內(nèi)部繼續(xù)填充，從而使修復(fù)效果不理想.

2 優(yōu)化方法

首先在進行SSD準(zhǔn)確匹配之前事先計算待修復(fù)圖像已知區(qū)域中所有紋理塊的平均灰度值，然后在匹配過程中結(jié)合平均灰度值閾值Tagv對已知區(qū)域中紋理塊及當(dāng)前待修復(fù)塊的平均灰度值進行比較，篩選淘汰灰度差異較大的一些紋理塊，這樣在進行準(zhǔn)確匹配時就只需與較少的候選塊匹配，從而節(jié)省大量復(fù)雜的SSD計算，減少匹配時間，提高修復(fù)效率.其次在對待修復(fù)邊界點優(yōu)先權(quán)的計算時，定義一種新的優(yōu)先權(quán)計算公式，增加是否接近原始邊界因素對優(yōu)先權(quán)的影響，使優(yōu)先權(quán)的計算更為合理，修復(fù)的結(jié)果更理想.

在SSD準(zhǔn)確匹配之前選平均灰度值作比較:其一，可預(yù)計算，且計算簡單.通過平均灰度值的比較后，減少大量SSD的復(fù)雜計算，使單次搜索只需計算較少次的SSD，節(jié)省匹配時間，提高了修復(fù)效率.其二，閾值可控性好.只要對平均灰度值閾值進行合理的控制，就可以在不明顯降低修復(fù)效果的同時提高修復(fù)效率.實際上，若平均灰度值閾值取足夠大(灰度圖像最大為255)，此時修復(fù)效果與文獻［7］算法相當(dāng).

在Criminisi算法基礎(chǔ)上對優(yōu)先權(quán)的計算進行改進，不僅考慮了置信度項和數(shù)據(jù)項，而且增加了是否接近原始邊界因素對優(yōu)先權(quán)的影響.這是由于新的待修復(fù)邊界點中離原始邊界越近的，相對越可靠，也就越應(yīng)當(dāng)優(yōu)先修復(fù)這些點所在的塊.這里，是否接近原始邊界的因素用二值項來表示，記為B(p)(p∈δΩ).

為了權(quán)衡置信度項、數(shù)據(jù)項和二值項對優(yōu)先權(quán)的影響，定義新的優(yōu)先權(quán)計算公式［7］:

式中:參數(shù)a、b、c為非負常數(shù)，分別為是否接近原始邊界、待修復(fù)塊中已知區(qū)域比例和結(jié)構(gòu)信息對優(yōu)先權(quán)的影響權(quán)重.若參數(shù)a的取值遠大于b、c，則接近原始邊界的區(qū)域?qū)⒈粌?yōu)先修復(fù);若參數(shù)b的取值遠大于a、c，則待修復(fù)塊中已知區(qū)域比例較大的區(qū)域?qū)⒈粌?yōu)先修復(fù);若參數(shù)c的取值遠大于a、b，則待修復(fù)塊中具有明顯邊緣的區(qū)域?qū)⒈粌?yōu)先修復(fù).a、b、c的取值情況決定著修復(fù)次序，并最終影響修復(fù)結(jié)果.因此，在值的選擇上，對不同特征的圖像，需通過調(diào)試a、b、c值來使修復(fù)的效果達到最好.一般情況下，a、b、c的值均取為1，使3個影響因素具有一樣的權(quán)重.如果取a為0，b、c均為1，此時得到的結(jié)果類似于Criminisi算法.因為這時優(yōu)先權(quán)值的計算也只考慮了置信度項和數(shù)據(jù)項，且兩者對優(yōu)先權(quán)的影響權(quán)重相同.

對于是否接近原始邊界的因素B(p)的取值情況，考慮到C(p)、D(p)的取值范圍均為0～1，這里B(p)(?p∈δΩi)的取值按照式(9)、式(10)進行設(shè)置，以使B(p)也具有同樣的數(shù)量級.

其中:δΩi表示對缺損圖像修復(fù)i(i≥0)次后待修復(fù)區(qū)域的邊界.

綜上所述，該方法的具體實現(xiàn)過程為(初始時i=0):

首先用綠色標(biāo)出圖像中待修復(fù)區(qū)域，設(shè)置平均灰度值閾值Tagv及參數(shù)a、b、c的值.

1)抽取用戶選定的待修復(fù)區(qū)域Ω(等于Ω0)的邊界δΩ(等于δΩ0)，設(shè)置B(p)值;預(yù)先計算圖像已知區(qū)域中所有紋理塊的平均灰度值.

2)如果Ωi=φ，退出，算法終止.

5)將當(dāng)前待修復(fù)塊及已知區(qū)域中紋理塊的平均灰度值進行比較，篩選淘汰灰度差異較大的一些紋理塊;再根據(jù)式(5)、式(6)在候選塊中搜索最佳匹配塊.

7)更新置信度;置i=i+1，抽取新的待修復(fù)邊界，并根據(jù)式(9)、式(10)更新B(p)值，轉(zhuǎn)步驟2).

3 實驗結(jié)果分析

仿真實驗在環(huán)境為Microsoft Visual C++6.0，配置為Windows XP－2002版本、CPU 1.73GHz、內(nèi)存1GB的計算機上完成.實驗選取了幾幅具有典型性的缺損圖像進行修復(fù)，紋理塊大小均為9×9，已知區(qū)域均設(shè)定為缺損圖像中完好的部分.算法是在保證圖像修復(fù)效果不比Criminisi算法差的同時盡量提高修復(fù)效率的基礎(chǔ)上，對參數(shù)(Tagv、a、b、c)進行設(shè)置.

3.1 時間對比

表1給出本文算法與Criminisi算法修復(fù)缺損圖像的運行時間比較.從表1可以看出:本文算法在較大程度上減少了運行時間，提高修復(fù)圖像的效率.從表1中最后兩行的實驗數(shù)據(jù)看，在平均灰度值閾值設(shè)置比較大時，本算法仍然可以取得較大程度上的效率提高.

表1 運行時間比較Tab.1 Comparison of the runtime

圖2 實驗結(jié)果1Fig.2 Experiment result 1

3.2 效果比較

效果比較見圖2～圖6.由圖2～圖6的比較結(jié)果知，本文算法得到的修復(fù)效果不比Criminisi算法差.這主要是由于本文算法定義了一種新的優(yōu)先權(quán)計算公式，增加了是否接近原始邊界因素對優(yōu)先權(quán)的影響，即新的待修復(fù)邊界點中離原始邊界越近的相對越可靠，也越應(yīng)當(dāng)優(yōu)先修復(fù)這些點所在的塊.該優(yōu)先權(quán)的計算更為合理，修復(fù)的結(jié)果更理想.特別地，從圖4～圖6中可以明顯看出本文算法的修復(fù)效果更好，更符合人的視覺感知.其中，在圖4中對屋檐及樹木與水面相接的部分修復(fù)得更合理;圖5中對三角形內(nèi)部修復(fù)得很好，沒有出現(xiàn)白色區(qū)域;圖6中對線結(jié)構(gòu)修復(fù)得更好，沒有出現(xiàn)斷裂的現(xiàn)象.實驗結(jié)果證明了本文算法的可行性及有效性，它較好地解決了偏差延續(xù)的問題.

圖3 實驗結(jié)果2Fig.3 Experiment result 2

圖4 實驗結(jié)果3Fig.4 Experiment result 3

圖5 實驗結(jié)果4Fig.5 Experiment result 4

圖6 實驗結(jié)果5Fig.6 Experiment result 5

4 結(jié)語

分析了Criminisi算法修復(fù)圖像時存在的幾個問題，提出一種在時間及視覺效果上都有所優(yōu)化的方法.該方法思路簡單，容易編程實現(xiàn).實驗結(jié)果表明，該方法不僅提高了修復(fù)效率，而且在一定程度上優(yōu)化了修復(fù)效果.雖然本算法可通過人為設(shè)置一些參數(shù)，使修復(fù)的圖像范圍更大，具有更好的實用性，但文中參數(shù)的設(shè)置沒有一個特定的標(biāo)準(zhǔn)，不能根據(jù)不同特征的圖像進行自動設(shè)置，而且如果參數(shù)選取不當(dāng)將會導(dǎo)致修復(fù)結(jié)果不理想.這是本算法存在的缺陷，還需要進一步的改進.

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

［2］Criminisi A，Perez P，Toyama K.Object removal by exemplar－based inpainting［C］//IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Wisconsin:Monona Terrace Convention Center Madison，2003，2:18－20.

［3］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):1 200－1 212.

［4］彭坤楊，董蘭芳.一種基于圖像平均灰度值的快速圖像修復(fù)算法［J］.中國圖象圖形學(xué)報，2010，15(1):50－55.

［5］朱為，李圍輝，李丹.紋理合成技術(shù)在舊照片修補中的應(yīng)用［J］.計算機工程與應(yīng)用，2007，43(28):220－222.

［6］李景輝，張曉峰，馬燕.紋理合成在圖像修復(fù)中的應(yīng)用研究［J］.計算機工程，2009，35(7):206－208.

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