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