??? 摘 要：將KL變換與小波" title="小波">小波變換相結(jié)合提出了一種新的紋理合成方法,，利用KL變換克服了合成彩色圖時(shí)存在的顏色失真；對樣圖進(jìn)行二維小波分解使得最佳匹配塊的搜索僅在原樣圖的低頻部分進(jìn)行，從而提高了合成速度。在搜索最佳匹配塊時(shí),使用多尺度小波變換" title="小波變換">小波變換后的小波系數(shù)的差異作為誤差度量,，并在比較匹配誤差時(shí)增加高頻系數(shù)的權(quán)重，突出了紋理結(jié)構(gòu)的匹配,。實(shí)驗(yàn)結(jié)果表明,，該方法不僅得到了較好的合成質(zhì)量，而且在很大程度上減少了合成時(shí)間,。
??? 關(guān)鍵詞：紋理合成? 小波變換? KL變換
?
??? 紋理合成是當(dāng)前計(jì)算機(jī)視覺,、計(jì)算機(jī)圖形學(xué),、計(jì)算機(jī)圖像處理等多個(gè)領(lǐng)域的研究熱點(diǎn)之一,。該技術(shù)可以由樣本紋理得到與其相似的大塊紋理，而且可以進(jìn)行紋理填充,、紋理傳輸?shù)?。紋理合成在圖像修復(fù)、圖像的真實(shí)感圖形繪制,、圖像視頻壓縮等方面有著廣泛的應(yīng)用,。
??? 基于樣圖的紋理合成是近幾年才發(fā)展起來的一門技術(shù)，由于該技術(shù)克服了早期的紋理映射和過程紋理合成的許多缺點(diǎn),，所以發(fā)展速度很快,，并且逐漸成為了紋理合成的主流技術(shù)。根據(jù)合成方式的不同,，基于樣圖的紋理合成可以分為兩大類：基于點(diǎn)的紋理合成和基于塊的紋理合成,。早期的基于樣圖的紋理合成方法采用的都是基于點(diǎn)的合成方式?；邳c(diǎn)的合成方式對于隨機(jī)性紋理能夠得到很好的合成效果,，但是對結(jié)構(gòu)性信息較強(qiáng)的紋理合成效果比較差，而且時(shí)間花費(fèi)也較長,。Efros[1],，Liang[2]等人采用基于塊的合成方式合成紋理,，一定程度上保證了結(jié)構(gòu)的連貫性，而且合成速度也得到了很大提高,。這些基于塊的方法在匹配時(shí)直接用L2距離比較兩個(gè)塊的誤差,，由于沒有突出圖像結(jié)構(gòu)信息的匹配，所以對于結(jié)構(gòu)不太規(guī)則的紋理合成效果較差,。近幾年隨著小波技術(shù)的發(fā)展與完善,，有的學(xué)者將小波應(yīng)用到紋理合成中，希望借助這個(gè)數(shù)學(xué)工具來達(dá)到較好的合成效果,。使用小波的紋理合成方法,，雖然在一定程度上改善了合成效果，但合成時(shí)間較長,。有鑒于此,，筆者將KL變換與小波變換相結(jié)合，提出一種新的紋理合成方法,。
1 紋理合成時(shí)引入小波的方法
??? 圖像信號經(jīng)過小波變換后可以用小波系數(shù)來描述,，小波系數(shù)體現(xiàn)了原圖像性質(zhì)，圖像信息的局部特征可以通過處理小波系數(shù)而改變,。多尺度小波變換能夠?qū)D像的低頻信息和高頻信息分離,，并通過對低頻部分的逐層分解，將包含圖像細(xì)節(jié)信息的高頻部分提取出來,，為分析圖像的特征細(xì)節(jié)提供了很大的方便,。
?? ?J.Chen和B.Zeng于2004年提出一種實(shí)時(shí)的基于塊的多尺度的紋理合成方法[3]，將紋理合成引入到了小波域內(nèi),，合成過程中僅對圖像小波分解后的低頻部分進(jìn)行合成,，使得合成得到了實(shí)時(shí)，但合成時(shí)卻丟失了圖像的高頻信息,，而這些部分恰恰是合成具有結(jié)構(gòu)信息的紋理所不可或缺的,。
?? ?Leandro Tonietto等人于2005年提出一種基于塊的紋理合成[4]，對紋理合成時(shí)誤差的度量做了修改,，采用下式計(jì)算兩個(gè)塊的匹配誤差：
??? 
式中,，cBik和cBjk分別代表兩個(gè)塊重疊部分經(jīng)過多尺度小波變換后的第k個(gè)小波系數(shù)，A是重疊部分像素的個(gè)數(shù),。在搜索最佳匹配塊時(shí),，選擇匹配誤差最小的塊作為當(dāng)前塊的最佳匹配塊。該方法通過對重疊部分進(jìn)行多尺度變換,，用變換后的小波系數(shù)來體現(xiàn)圖像的細(xì)節(jié)信息,，在一定程度上考慮了圖像結(jié)構(gòu)內(nèi)容的匹配，得到了較好的合成效果,。但是在合成時(shí)沒有做任何的預(yù)處理,，導(dǎo)致了合成時(shí)間較長,。
??? 受上面方法的啟發(fā)，這里提出一種基于小波的紋理合成方法,，先對圖像進(jìn)行二維小波分解,，然后只在分解后的低頻部分進(jìn)行最佳匹配塊的搜索，這樣可以在很大程度上減少搜索時(shí)間,。在搜索最佳匹配塊時(shí),，對計(jì)算匹配誤差的公式(1)做了修改，比較匹配誤差時(shí)增加了高頻系數(shù)的權(quán)重,，突出了結(jié)構(gòu)信息的匹配,。合成彩色圖時(shí)，借鑒參考文獻(xiàn)[5]的方法,，用KL變換消除顏色失真,，得到了較好的合成效果。
2 基于小波的紋理合成方法
??? 傳統(tǒng)的方法在搜索最佳匹配塊時(shí),，直接對樣圖進(jìn)行全局搜索,，若樣圖較大將導(dǎo)致合成時(shí)間過長。在紋理合成之前先對樣圖進(jìn)行二維小波分解,，將樣圖分解為低頻,、水平高頻、垂直高頻,、斜線高頻四個(gè)部分,。由于低頻部分包含了樣圖大部分的能量，所以合成時(shí)只在低頻部分搜索最佳匹配塊,，這樣在很大程度上減少了搜索時(shí)間,。對于其他部分則不再進(jìn)行最佳匹配塊的搜索，而是將其內(nèi)部與在低頻部分搜索到的最佳匹配塊相對應(yīng)的塊作為最佳匹配塊,。如圖1 所示，Bi塊的左上角在圖1(a)中的位置為(m,，n),，Bj塊的左上角在圖1(b)中的位置也是(m，n),，則認(rèn)為Bj塊是Bi塊在圖1(b)中的對應(yīng)塊,。這樣就使全局搜索時(shí)的樣圖縮小為原樣圖的1/4，從而很大程度上縮短了搜索時(shí)間,，提高了合成速度,。四部分合成完以后，再通過小波重構(gòu)" title="重構(gòu)">重構(gòu)得到輸出圖,。
??????????????????? 
??? 在低頻部分搜索最佳匹配塊時(shí),，與直接通過比較圖像塊的L2距離刻畫其相似程度不同[3],，這里先對兩個(gè)塊的重疊部分進(jìn)行一維多尺度小波變換，然后通過變換后的小波系數(shù)差異度量兩個(gè)塊的匹配程度,。由于對圖像進(jìn)行多層小波分解,，可以把圖像中的高頻信息逐層提取出來，而高頻信息又往往表現(xiàn)為圖像中的結(jié)構(gòu)特征,，所以可以通過比較兩個(gè)塊高頻信息的匹配誤差來度量紋理中結(jié)構(gòu)特征的匹配程度,。為了突出結(jié)構(gòu)信息的匹配，在比較匹配誤差時(shí),，對每一層的高頻系數(shù)都賦予比低頻系數(shù)高的權(quán)重,。匹配誤差的計(jì)算公式如下：
??? 
式中，Ah+Al=A(重疊部分像素的個(gè)數(shù)),，Ah,、Al分別代表高頻系數(shù)和低頻系數(shù)的個(gè)數(shù)，α,、β分別代表高頻系數(shù)和低頻系數(shù)所占的比重,，搜索時(shí)選擇d(Bi，Bj)最小的塊作為當(dāng)前塊Bi的最佳匹配塊,。圖2是使用不同匹配誤差公式計(jì)算的合成效果圖的比較,。由圖可以看出，對紋理塊的重疊部分進(jìn)行三層小波分解時(shí),，使用參考文獻(xiàn)[4]方法計(jì)算匹配誤差的合成效果圖圖2(b)中存在紋理錯(cuò)位,、結(jié)構(gòu)雜亂現(xiàn)象，與樣圖的紋理結(jié)構(gòu)有較大出入,，而使用本文方法的合成圖較好地保持了原樣圖的結(jié)構(gòu),，如圖2(c)所示(其中α=2,β=1)。
??????????????????? 
??? 上面的方法因?yàn)樾枰M(jìn)行小波分解與重構(gòu),，所以僅對灰度圖適用,。對于彩色紋理，由于每一個(gè)像素點(diǎn)都由R,、G,、B三基色表示，可以對三基色分別進(jìn)行合成,，但是這樣會引起顏色失真,，如圖3所示。借鑒參考文獻(xiàn)[5]的方法,，使用KL變換解除R,、G、B三基色的相關(guān)性,，將彩色紋理變換成相互獨(dú)立的三分量I1,、I2,、I3，然后對每個(gè)獨(dú)立分量用上面提出的方法進(jìn)行合成,，生成相應(yīng)的紋理圖像,，最后將三幅紋理圖像變換回R、G,、B彩色空間,，生成最后的彩色紋理。
???????????????
??? 綜上所述,，將本文的算法總結(jié)如下：
??? (1)對彩色樣圖進(jìn)行KL變換,，將彩色圖R、G,、B分量變換成相互獨(dú)立的I1,、I2、I3分量,。
??? (2)對每個(gè)獨(dú)立分量Ii(i=1,，2，3)進(jìn)行二維小波分解,，將圖像分解為低頻,、水平高頻、垂直高頻,、斜線高頻四個(gè)部分,。
??? (3)同時(shí)對低頻、水平高頻,、垂直高頻,、斜線高頻四個(gè)部分進(jìn)行合成，但僅在低頻部分進(jìn)行最佳匹配塊的搜索,。
??? (4)對合成后的四個(gè)部分進(jìn)行小波重構(gòu),，得到該獨(dú)立分量Ii的合成圖像。
??? (5)重復(fù)(2)～(4),，得到I1,、I2、I3三分量的合成圖像,。
??? (6)將I1、I2,、I3三分量的合成圖像變換回R,、G、B彩色空間,，輸出最終的彩色合成" title="彩色合成">彩色合成圖,。
3 實(shí)驗(yàn)參數(shù)及結(jié)果分析
??? 所有實(shí)驗(yàn)都是在CPU主頻2.66GHz,、內(nèi)存512MB" title="512MB">512MB的Pentium IV PC機(jī)上使用Matlab實(shí)現(xiàn)。
??? 實(shí)驗(yàn)中紋理塊的大小對合成結(jié)果有較大影響,，如果紋理塊太小,，則塊內(nèi)包含的信息較少，將導(dǎo)致合成的結(jié)果呈現(xiàn)較大的隨機(jī)性,，不能很好地匹配當(dāng)前塊,；紋理塊太大的話，每次小波變換的時(shí)間會較長,。所選紋理塊的尺寸一般應(yīng)該能夠涵蓋一個(gè)紋理基本元素,，重疊部分取紋理塊的1/4～1/2。表1給出了實(shí)驗(yàn)時(shí)對于不同樣圖所選的參數(shù),。
??????????????????? 
??? 二維小波分解和多尺度小波變換時(shí)都采用haar小波,，多尺度小波分解到三層或者分解到低頻系數(shù)的個(gè)數(shù)少于4。
??? 圖4給出了本文方法與參考文獻(xiàn)[1]方法的比較,，可以看出本文方法克服了參考文獻(xiàn)[1]方法引起的紋理錯(cuò)位的問題,。圖5給出了本文方法與參考文獻(xiàn)[2]方法、參考文獻(xiàn)[4]方法的比較,?？梢钥闯觯疚姆椒ê蛥⒖嘉墨I(xiàn)[4]方法在效果上都優(yōu)于參考文獻(xiàn)[2]方法,，較好地克服了參考文獻(xiàn)[2]方法引起的紋理錯(cuò)位,，結(jié)構(gòu)雜亂的問題。而且,，由表2可以看出本文方法的合成時(shí)間明顯少于參考文獻(xiàn)[4]方法的合成時(shí)間,。為了比較其效果，實(shí)驗(yàn)時(shí)對不同方法選擇了相同的初始點(diǎn),。實(shí)驗(yàn)所用時(shí)間為多次實(shí)驗(yàn)的平均,。
??????????????? 
?
?????????????? 
????????????????? 
??? 本文提出了一種基于小波的紋理合成方法，將KL變換及小波變換應(yīng)用于彩色紋理的合成中,，不僅得到了較好的合成效果,，合成速度也得到了很大提高。該算法雖然使得合成速度得到了很大提高,，但是要想實(shí)時(shí)地合成紋理,，還有很多工作要做。
參考文獻(xiàn)
[1] EFROS A A,，F(xiàn)REEMAN W T.Image quilting for texture?synthesis and transfer[J].Proc SIGGRAPH,，2001，(8)：341-346.
[2] LIANG L，LIU C,，XU Y et al.Real-time texture synthesis?by patch-based sampling[R].Technical Report MSR- TR-2001-40,，Microsoft Research，2001.
[3] CHEN J,，ZENG B.Patch-Based Multi-Resolution Real-Time Texture Synthesis in Wavelet Domain[J].Chengdu(CN)：International Conference on Communications,，Circuits and?Systems，2004,，2：788-791.
[4] TONIETTO L,，WALTER M，JUNG C R.Patch-based texture synthesis using wavelets[C].Proceedings of SIBGRAPI(Natal,，Brazil,，October 2005)，IEEE Computer Society,，2005：383-389.
[5] 李厚強(qiáng),，董朋朋，葉中付.基于無參數(shù)Markov隨機(jī)場模型的彩色紋理綜合方法[J].計(jì)算機(jī)工程,，2003,，29(18)：34-36.