謝伙生，潘姣君

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

0 引言

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

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

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

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

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

1 Criminisi算法分析

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

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

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

式中:

圖1 符號(hào)圖Fig.1 Symbol diagram

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

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

2 優(yōu)化方法

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

3.1 時(shí)間對(duì)比

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

表1 運(yùn)行時(shí)間比較Tab.1 Comparison of the runtime

圖2 實(shí)驗(yàn)結(jié)果1Fig.2 Experiment result 1

3.2 效果比較

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

圖3 實(shí)驗(yàn)結(jié)果2Fig.3 Experiment result 2

圖4 實(shí)驗(yàn)結(jié)果3Fig.4 Experiment result 3

圖5 實(shí)驗(yàn)結(jié)果4Fig.5 Experiment result 4

圖6 實(shí)驗(yàn)結(jié)果5Fig.6 Experiment result 5

4 結(jié)語(yǔ)

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

［1］張紅英，彭啟琮.數(shù)字圖像修復(fù)技術(shù)綜述［J］.中國(guó)圖象圖形學(xué)報(bào)，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］.中國(guó)圖象圖形學(xué)報(bào)，2010，15(1):50－55.

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

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

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