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