基于小波變換的紋理合成算法研究

尤鴻霞，王壽兵

（江蘇工程職業(yè)技術(shù)學(xué)院素質(zhì)教學(xué)部，江蘇南通226007）

0 引言

現(xiàn)實世界中存在著各種各樣的紋理，紋理合成是計算機圖形學(xué)的一個重要研究方向，紋理合成技術(shù)可廣泛應(yīng)用于圖像編輯、圖像修復(fù)、虛擬現(xiàn)實中大面積場景繪制等領(lǐng)域[1]。紋理合成主要有過程紋理合成和基于樣圖的紋理合成。過程紋理合成通過仿真紋理的生成過程來合成紋理，其合成效果非常逼真，但計算量大且合成速度慢，對每一種新的紋理都需要調(diào)整參數(shù)反復(fù)測試。基于樣圖的紋理合成基本思想是根據(jù)給定的小區(qū)域的紋理樣本，拼合生成任意大小的紋理圖像并且在視覺上與樣本是相似而連續(xù)的。

基于樣圖的紋理合成主要有兩大類方法：基于像素的紋理合成和基于塊的紋理合成。Efros等人1999年提出基于像素的鄰域匹配算法[2]，主要思想是對于每一個待合成的像素，都是在樣圖圖像的相似鄰域中確定像素值。對于輸出圖像中待合成的點，是通過比對該點的鄰域和輸入樣圖圖像中所有點的鄰域來查找匹配點，并將查找到的與待合成點最匹配的點作為該點的值。Efros在2001年的FIGGAPH會議上提出了一種基于塊拼接的紋理合成算法[3]，又稱圖像縫合算法，即image quilting算法。與基于像素的紋理合成相比，基于塊的紋理合成每次向輸出圖像填充一個圖像塊，有效地減少了搜索和匹配的次數(shù)，在紋理合成的速度和質(zhì)量等方面都得到了很大的提高。Image quilting算法存在的問題是有時紋理出現(xiàn)重復(fù)，有些邊界不匹配。

J.chen和B.zeng[4]提出將紋理合成引入到了小波域內(nèi)，使得紋理合成的速度得到了提高，但合成時丟失了圖像的高頻信息。LeandroTonietto等人[5]通過用小波變換后的小波系數(shù)來體現(xiàn)圖像的細(xì)節(jié)信息，在一定程度上考慮了圖像結(jié)構(gòu)信息的匹配，但是由于在搜索最佳匹配塊時需對整個樣圖進(jìn)行搜索，使得該方法的合成時間較長。

本文基于image quilting算法，考慮紋理的結(jié)構(gòu)信息，將小波變換引入到紋理塊的特征分析與匹配過程中，結(jié)合小波變換后的小波系數(shù)和小波變換后的低頻域圖像來進(jìn)行塊的匹配和分析。實驗表明，該算法能夠獲得良好的紋理合成圖。

1 Image Quilting算法描述

Image quilting紋理合成算法[3]的基本思想是：按照掃描線的順序，每次根據(jù)一定的匹配規(guī)則從紋理樣圖中選擇固定大小的紋理塊，將其拷貝至輸出紋理，直至達(dá)到輸出紋理大小。Image quilting算法的合成單位是紋理塊，合成速度較快。

Image quilting算法采用最小誤差路徑來縫合紋理，即：設(shè)B1為已合成紋理塊，B2為待合成紋理塊，B1和B2沿著垂直方向重疊，B1ov和B2ov分別為B1和B2各自的重疊區(qū)域，誤差定義為e=(B1ov-B2ov)，通過式(1)獲得重疊區(qū)域最后一行各點的累積誤差：

圖1 三種塊縫合

選取累積誤差最小的一點，通過反向跟蹤可獲得最佳縫合路徑。對水平方向有重疊的區(qū)域，采用相同的方法得到最佳縫合路徑，當(dāng)同時具有垂直和水平重疊區(qū)域，兩條路徑會在某點相交，選取總體誤差最小的路徑作為最佳縫合路徑。

2 基于小波變換的紋理合成

2.1 haar小波變換

Haar小波函數(shù)是最簡單的正交函數(shù)，其構(gòu)造簡單，計算方便，本文采用haar小波變換將圖像的低頻信息和高頻信息分離，即在對樣圖進(jìn)行紋理合成之前，先對樣圖進(jìn)行小波分解，將樣圖分解為低頻、水平高頻、垂直高頻、高頻四部分。經(jīng)過小波變換后，樣圖的大部分能量都集中在小波變換后的低頻部分，經(jīng)過一次小波變換，其低頻部分的的面積縮小為原來的1/4，在搜索最佳匹配塊的時候只在低頻部分搜索。傳統(tǒng)的紋理合成方法在搜索最佳匹配塊時，直接對樣圖進(jìn)行全局搜索，可能導(dǎo)致搜索時間過長，而搜索小波變換低頻域，能夠節(jié)約大量的搜索時間使合成速度得到提升。

圖2 織物紋理小波變換樣圖

2.2 紋理合成過程算法描述

本文紋理合成算法是在image quilting算法基礎(chǔ)上加以改進(jìn)，首先從樣本圖像中隨機選擇一塊指定大小的圖片塊作為輸出圖像的第一個塊B1，然后根據(jù)一定的規(guī)則從樣本圖像中選擇合適的圖片塊B2拼接在B1之后，并且使拼接后的輸出圖像看上去與樣圖的紋理是相似的而且是連續(xù)的，無明顯的拼貼痕跡。

算法的關(guān)鍵問題有三。第一，確定搜索路徑，快速準(zhǔn)確地在樣圖中搜索到能夠合適拼貼在已合成圖片塊B1后面的圖片塊B2。經(jīng)分析，因在輸出紋理圖像中B2是拼貼在B1之后，在樣圖中B2出現(xiàn)在B1附近的概率較高，所以，確定搜索路徑時，首先在樣圖中B1的位置附近搜索，如圖3a中，極易在B1的附近找到合適的B2，這樣可快速定位B2，提高搜索速度。另外，也有一些情況，在B1位置的附近，沒有適合可以作為B2的塊，如圖3b，那么當(dāng)在B1位置附近搜索失敗，則從樣圖的起始處開始搜索。

第二，確定已合成塊B1和待合成塊B2的匹配準(zhǔn)則。對于已合成塊和待合成塊的重合區(qū)域，如果待合成區(qū)域的位置不同，則重疊區(qū)域也是不同的[3]，共有三種情況：（1）待合成塊位于第一行，只有左邊的垂直重疊區(qū)域。如圖4a所示。（2）待合成塊位于第一列，只有上邊的水平重疊區(qū)域，如圖4b所示。（3）其余情況，同時包含水平和垂直兩個重疊區(qū)域，即L形重疊區(qū)域，如圖4c所示。

圖3 搜索策略

圖4 重疊區(qū)域

將圖像進(jìn)行2級小波變換，用小波變換后的小波變換系數(shù)來進(jìn)行重疊區(qū)域匹配計算。設(shè)B1ov和B2ov為已合成塊B1和待合成塊B2各自的重疊區(qū)域，將B1ov和B2ov的二級小波變換系數(shù)做匹配計算，使其匹配誤差控制在一定范圍內(nèi)。為提高搜索速度，設(shè)定閾值，當(dāng)匹配計算誤差值小于設(shè)定閾值時，則認(rèn)為找到了合適的B2并停止本次搜索，以避免每次都進(jìn)行全局搜索。用小波變換系數(shù)來進(jìn)行匹配計算，充分考慮了紋理的結(jié)構(gòu)信息，但是從實驗結(jié)果分析，拼貼縫合時，重疊處的圖像紋理邊緣處偶見不能準(zhǔn)確對接或是出現(xiàn)明顯的紋理結(jié)構(gòu)循環(huán)現(xiàn)象，如圖5b1和圖5b2。

為解決此問題，將一級小波變換低頻域的圖像以一定的權(quán)重參與到重疊區(qū)域匹配中，步驟為：首先將樣圖做小波變換，獲得其一級小波變換的低頻域圖像BL；其次在輸出圖像中取得重疊區(qū)域，將其做小波變換，并將重疊區(qū)域一級小波變換后的低頻域圖像在BL圖像中做搜索對比，以獲合適的B2。一級小波變換后的低頻域圖像包含了原圖像的大部分信息而大小僅為原圖像的1/4，匹配次數(shù)較少，從實驗結(jié)果分析，結(jié)合小波系數(shù)和小波變換低頻域圖像進(jìn)行紋理塊匹配能夠得到較好的紋理合成效果。

第三，將搜索到的紋理塊B2縫合在B1的后面，使其縫合的邊緣無明顯拼貼痕跡，本文使用最小路徑法將待合成紋理塊縫合在已合成紋理塊之后。

本文算法步驟如下：

步驟一：指定紋理塊的大小，以及紋理塊之間重疊區(qū)域的大小。

步驟二：隨機取樣本紋理中的一個紋理塊B1放在輸出圖像中，作為輸出圖像的第一個拼貼塊。

步驟三：從輸出圖像中取出重疊區(qū)域，結(jié)合小波系數(shù)和小波變換低頻域圖像進(jìn)行重疊區(qū)域紋理匹配，從樣圖中找到合適的待合成塊B2。

步驟四：將B2其拼貼到已合成區(qū)域B1的后面，拼貼的縫合過程采用最小路徑法。

步驟五：重復(fù)以上步驟三和步驟四過程，獲得合成紋理圖。

實驗結(jié)果如圖5所示，圖中a1、a2為樣圖，b1、b2為在塊匹配步驟中只采用小波系數(shù)進(jìn)行重疊區(qū)域匹配得到的紋理圖，c1、c2為本文算法的合成紋理圖。

圖5 紋理合成結(jié)果圖

3 結(jié)論

紋理合成是計算機圖形學(xué)領(lǐng)域的研究熱點之一，本文基于原有image quilting紋理合成方法的優(yōu)勢與不足，從待匹配塊的搜索路徑、合成塊的匹配策略等方面對算法進(jìn)行了改進(jìn)。從實驗結(jié)果分析，對于多數(shù)紋理模型合成質(zhì)量較好，但是對于不同類型的紋理，合成塊的大小的選擇需要做適當(dāng)?shù)恼{(diào)整以取得最佳合成效果，所以未來工作中應(yīng)進(jìn)一步研究此問題，以獲取更好的解決方案。

[1]朱文浩，魏寶剛.基于樣本的紋理合成技術(shù)綜述[J].中國圖像圖形學(xué)報，2008(11)：2063-2069.

[2]Efros A,Leung T.Texture synthesis by non-parametric sampling[A].In:Proceedings of IEEE International Confer?ence on Computer Vision[C],Corfu,Greece,1999:1033-1038.

[3]Efros A,Freeman W T.Image quilting for texture synthesis and transfer[A].In Proceedings of SIGGRAPH 2001[C],USA,2001:341-346.

[4]J.chen,B.zeng.Patch-Based Multi-Resolution Real-Time Texture synthesis in wavelet domain[J].International Confer?ence on Communications,Circuits and Systems,2004(2):788-791.

[5]L.Tonietto,M.walter and C.R.Jung.Patch-based texture synthesis using wavelets[C].IEEE Computer Society,Proceed?ings of SIBGRAPI,Natal:IEEE Press,2005:383-389.