張雨禾，耿國華，劉倫椿，周子駿

(西北大學(xué)信息科學(xué)與技術(shù)學(xué)院，陜西西安710127)

紋理技術(shù)可以表現(xiàn)幾何模型無法體現(xiàn)的細(xì)節(jié)和特征，彌補幾何繪制的不足，在計算機基于圖像的真實感繪制中占據(jù)重要的地位。常見的紋理技術(shù)主要有紋理映射、過程紋理合成和基于樣圖的紋理合成?；跇訄D的紋理合成技術(shù)，既克服了傳統(tǒng)紋理映射的缺點，同時避免了過程紋理合成中的參數(shù)選擇等繁瑣過程，因而受到越來越多的關(guān)注。目前，基于樣圖的紋理合成技術(shù)基本上都是基于馬爾可夫隨機場模型［1］的。在1999年的ICCV會議上，Eorfs和Lueng率先提出了非參數(shù)采樣的算法［2］，該方法利用紋理圖像中鄰近點相關(guān)性強的特征，根據(jù)預(yù)先在待合成圖中設(shè)置的種子，從而在給定的鄰域中查找匹配點來合成紋理，隨后的紋理合成算法都受到了該方法的影響。Ashikhmin利用相鄰像素間的相關(guān)性原理進行紋理合成［3］，對自然紋理的合成取得了很好的效果。針對紋理塊的拼接，Efros提出了一種基于塊縫合的紋理合成算法［4］，通過查找誤差最小的路徑實現(xiàn)各塊的拼接，對一些紋理取得了非常好的效果。Kwatra使用GraphCut進行紋理合成［5］，并將ImageQuilting算法中的矩形紋理塊推廣到任意形狀，獲得了較高的合成質(zhì)量。隨后在這些基本合成算法的基礎(chǔ)上，研究學(xué)者又提出了一些改進的合成方法［6-8］，合成速度和質(zhì)量都得到了很大的提高。

紋理合成的主要步驟是:1)確定當(dāng)前需要合成的點(或塊)的位置;2)根據(jù)當(dāng)前位置的鄰域的特征，從樣圖或自身圖像中尋找相似塊;3)將搜索到的相似塊和已存在的圖像合并。3)圖像拼合的好壞往往依賴于2)中尋找的相似塊，如果相似塊與輸出圖像不能較好地匹配，即使后續(xù)運用較好的拼接算法，最后也難免存在視覺上的不連貫?，F(xiàn)有的算法通常都是精確到像素點的計算，采用基于RGB色彩空間的L2距離，即對二者L鄰域中的每個像素點對，求其在顏色空間中的差值和，如果差值和小于給定的閾值，則認(rèn)為相匹配。從視覺的角度觀察圖像，每個像素對人眼和心理的刺激是不同的，像點之間的相關(guān)性也是不同的。而在L2距離公式中，卻將L鄰域中的所有像點放在同等的地位對待。目前已有很多學(xué)者認(rèn)為將L鄰域作為鄰域的相似性判斷條件，存在著不足，將其不足歸因為使用其整體匹配誤差［9-10］。該誤差直接造成合成后紋理的不連續(xù)，或者丟失樣本紋理中的某些特征信息，從而嚴(yán)重影響紋理的合成質(zhì)量。

本文就針對以上使用L鄰域的整體匹配誤差而造成的紋理合成質(zhì)量差的問題進行了討論，利用結(jié)構(gòu)性紋理中像點間的相關(guān)性信息，提出了一種新的鄰域匹配方法，改進了現(xiàn)有算法運行速度慢以及易產(chǎn)生誤匹配等缺點，有效地改善了紋理合成的視覺效果，加快了紋理合成中預(yù)處理的速度。

1 L鄰域的分割理論

結(jié)構(gòu)性紋理中存在紋元(保持紋理局部特性的最小紋理塊)，整個紋理圖像可以由一系列的紋元及其擺放規(guī)則決定，因此，結(jié)構(gòu)性紋理往往具有一定的周期重復(fù)性和方向性(在這里主要指紋理的主方向)。從視覺角度來講，紋元相同，擺放規(guī)則不同，則構(gòu)成的紋理圖像也不同，紋理圖像的周期和主方向也就不同。紋理的主方向體現(xiàn)在紋理圖像的結(jié)構(gòu)構(gòu)成上，就是像點之間的相關(guān)性，即處于(或接近)紋理主方向上的像點之間相關(guān)性較強，否則，相關(guān)性較弱。紋理的方向是一個區(qū)域上的概念，是在一個大的鄰域內(nèi)的統(tǒng)計特性。依據(jù)這一特性，要保證生成的圖像與樣圖圖像在視覺上保持相似性，在L鄰域的相似性度量中，就應(yīng)將L鄰域中與待合成像點相關(guān)性較強的像點放在更重要的位置，優(yōu)先考慮其相似性。

在像點P的L鄰域中(如圖1所示)，像點的位置不同，其與待合成像點的相關(guān)性也不同。結(jié)合L鄰域的特點，取4個特殊方向，將L鄰域分割為4個區(qū)域(如圖2所示)。其中，區(qū)域1與像點P成45°;區(qū)域2與像點P成90°;區(qū)域3與像點P成135°;區(qū)域4與像點P成0°。

圖1 像點P的L鄰域Fig.1 L neighbor of pixel P

圖2 像點P的分割L鄰域Fig.2 Segmented L neighbor of pixel P

2 L鄰域分割紋理合成方法

基于L鄰域分割的合成方法，如果只用分割后的一部分鄰域來尋找匹配塊，同樣只是考慮到了局部匹配的誤差，也會出現(xiàn)匹配錯誤。所以本文方法兼顧局部和整體的誤差，設(shè)計了一種新的匹配規(guī)則:對L鄰域進行分割，采用基于優(yōu)先級的多次匹配，完成L鄰域的完整匹配。

2.1 灰度共生矩陣

灰度共生矩陣(記為W陣)［11］是統(tǒng)計空間上具有某種位置關(guān)系的一對像元灰度對出現(xiàn)的頻度。其實質(zhì)是從圖像灰度為i的像元(位置為x，y)出發(fā)，統(tǒng)計與其距離為d，灰度為j的像元(x+Dx，y+Dy)同時出現(xiàn)的頻度p(i，j，dH)，數(shù)學(xué)表達(dá)式為

式 中:(x，y)是 圖 像 的 像 元 坐 標(biāo);i、j=0，1，...，L－1是灰度級，Dx、Dy是位置偏移量，d為W陣的生成步長?；贚鄰域自身的特點，本文方法計算灰度共生矩陣時，取d=1，即灰度共生矩陣的生長步長為1;θ為W陣的生成方向，當(dāng)Dx=1，Dy=0時，像素對是水平的，即0°掃描，θ=0°;當(dāng)Dx=0，Dy=1時，像素對是豎直的，即90°掃描，θ=90°;當(dāng)Dx=1，Dy=1時，像素對是右對角線，即45°掃描，θ=45°;當(dāng)Dx=－1，Dy=1時，像素對是左對角線，即135°掃描，θ=135°。

灰度共生矩陣的相關(guān)值如式(2)所示，被用來度量灰度共生矩陣元素在行或列方向上的相似程度［12］，如果圖像的某方向上紋理性較強，則該方向的相關(guān)值W3將大于其他方向的值。因此，W3可用來判斷紋理在4個特殊方向上的相關(guān)程度。如圖3所示。由圖可見，該紋理樣圖像素對在豎直方向上具有較大的相關(guān)性，其次是水平方向，并且水平方向和豎直方向上的像點間相關(guān)性較接近，像點間相關(guān)性較小的是右對角線方向及左對角線方向。

圖3 樣本紋理及其相關(guān)值Fig.3 Sample texture and its IDM

2.2 基于灰度共生矩陣相關(guān)值的優(yōu)先級分配

根據(jù)計算出的灰度共生矩陣的相關(guān)值，按照由高到低的順序依次對已分割好的L鄰域的4個區(qū)域進行優(yōu)先級的分配:使得相關(guān)值最大的θ值對應(yīng)的區(qū)域，分配最高的優(yōu)先級，使得相關(guān)值次大的值對應(yīng)的區(qū)域，分配次高的優(yōu)先級，依次類推，完成L鄰域所有已分割區(qū)域的優(yōu)先級分配。如圖4所示，按照優(yōu)先級分配原則，優(yōu)先級由高到低的次序依次為:區(qū)域1、區(qū)域 2、區(qū)域3、區(qū)域 4。

圖4 優(yōu)先級分配示意圖Fig.4 Priority assignment

2.3 L鄰域的多次匹配

使用分割L鄰域的方法對結(jié)構(gòu)性紋理合成時，需要經(jīng)過多次匹配才能找到最符合條件的L鄰域，然后將其拼貼到合成圖中，這種分而治之的方法，雖然步驟增加了，但是計算量卻明顯下降了，具體步驟如下:

1)選取L鄰域中優(yōu)先級最高的部分進行匹配。即在原樣圖中搜索與該部分顏色差最小的塊，如果誤差大于給定的閾值K1，則丟棄此塊繼續(xù)搜索，若小于K1，轉(zhuǎn)到步驟2);

2)選取L鄰域中優(yōu)先級次高的部分進行匹配。即在原樣圖中搜索與該部分顏色差最小的塊，如果誤差大于給定的閾值K2，則丟棄此塊，轉(zhuǎn)向步驟1)，重新搜索;若小于K2，轉(zhuǎn)到步驟3);

3)選取L鄰域中優(yōu)先級次低的部分進行匹配。即在原樣圖中搜索與該部分顏色差最小的塊，如果誤差大于給定的閾值K3，則丟棄此塊，轉(zhuǎn)向步驟1)，重新搜索;若小于K3，轉(zhuǎn)到步驟4);

4)選取L鄰域中優(yōu)先級最低的部分進行匹配。即在原樣圖中搜索與該部分顏色差最小的塊，如果誤差大于給定的閾值K4，則丟棄此塊，轉(zhuǎn)向步驟1)，重新搜索;若小于K4，L鄰域匹配完成。

在多次匹配的過程中，如果一步不能找到最優(yōu)值，即沒有塊的顏色差值小于給定的閾值，則在全局中選擇最接近閾值的塊，進行下一步的搜索匹配。

新的匹配規(guī)則，加快了預(yù)處理過程，并減少了傳統(tǒng)的L鄰域在整體鄰域匹配搜索過程中存在的計算復(fù)雜性和匹配誤差。

2.4 分割法的算法流程

使用分割法進行紋理合成，其步驟可以簡單的描述為:

1)計算紋理樣圖的灰度共生矩陣的相關(guān)值;

2)找到待合成的像點(或塊);

3)對待合成像點(或塊)的L鄰域進行分割和優(yōu)先級的分配;

4)進行L鄰域的多次匹配;在L鄰域的多次匹配過程中，利用式(3)，計算匹配誤差，最終找到最佳匹配塊;

5)對待合成像點(或塊)進行合成，若已完成圖像的合成，則轉(zhuǎn)向6)，否則轉(zhuǎn)向2);

6)算法結(jié)束。

3 實驗結(jié)果分析

3.1 實驗結(jié)果

本文方法通過Matlab7進行了實現(xiàn)，對于給定輸入基本圖，為減少計算量，對原始圖像灰度級進行壓縮，量化成16級。實驗分別采用文獻(xiàn)［13］、文獻(xiàn)［14］及本文方法(在實現(xiàn)本文方法時，采用與文獻(xiàn)［14］相同的匹配塊搜索策略，在匹配塊的相似性度量中采用本文方法)，在計算機上進行了大量的實驗。

實驗結(jié)果對比圖如圖5～7所示。

圖5 實驗結(jié)果圖:紋理中像點在一個方向上相關(guān)性較強Fig.5 Comparison of experimental results:Strong correlation in 1-direction

圖6 實驗結(jié)果圖:紋理中像點在2個方向上相關(guān)性較強Fig.6 Comparison of experimental results:Strong correlation in 2-direction

圖7 實驗結(jié)果圖:紋理中像點在3個方向上相關(guān)性較強Fig.7 Comparison of experimental results:strong correlation in 3-direction

圖5中的紋理樣圖的像點在一個方向(角度)上相關(guān)性較強而在其他3個方向上相關(guān)性較弱;圖6中的紋理樣圖的像點在2個方向上相關(guān)性較強且在其余2個方向上相關(guān)性較弱;圖7中的紋理樣圖的像點則在3個方向上相關(guān)性較強而在另一個方向上相關(guān)性較弱。結(jié)果表明，本文的方法在處理結(jié)構(gòu)性紋理時，效果好壞不依賴于其自身方向的復(fù)雜性，能夠較好的保留結(jié)構(gòu)性紋理樣圖中的結(jié)構(gòu)性信息、周期性、顏色、基本紋元信息及其擺放規(guī)則等特征分布規(guī)律，獲得令人滿意的效果。

3組實驗執(zhí)行時間如表1所示，不難看出，采用分割法進行紋理合成，加快了紋理合成中預(yù)處理的速度，進而提高了紋理合成的速度。

表1 3種方法執(zhí)行時間比較Table 1 Execution time comparison of 3 methedss

3.2 性能評價

1)紋理合成時間

本文方法與傳統(tǒng)方法在進行L鄰域匹配中，分別利用L鄰域的分割區(qū)域與L鄰域整體進行計算以度量L鄰域的相似度。下面分別通過鄰域不匹配和鄰域匹配2種情況對其時間性能進行分析。

①L鄰域不匹配

原樣圖中當(dāng)前搜索到的L鄰域與待合成塊的L鄰域不匹配時，傳統(tǒng)方法利用L鄰域整體做相似性度量，在誤差計算過程中，需要參與計算的像點數(shù)F為

式中:n為鄰域的規(guī)模。

而本文方法在對L鄰域的相似性度量中，將L鄰域分割成4個區(qū)域分別進行計算，每個區(qū)域的像點數(shù)約為整個L鄰域像點數(shù)的1/4。因此，需要參與計算的像點數(shù)F'為

式中:θ≤1，為匹配階段計數(shù)值。即:當(dāng)優(yōu)先級最高的分割區(qū)域不匹配時，θ=1/4;當(dāng)優(yōu)先級次高區(qū)域不匹配時，θ=2/4;當(dāng)優(yōu)先級次低的區(qū)域不匹配時，θ=3/4;當(dāng)優(yōu)先級最低的區(qū)域不匹配時，θ=1。

②L鄰域匹配

當(dāng)原樣圖中當(dāng)前塊L鄰域匹配時，本文方法中L鄰域的4個區(qū)域都已參與計算，與傳統(tǒng)方法相同，因此，參與計算的像點數(shù)相同，如式(4)所示。

綜上所述，在保證匹配精度相同的情況下，當(dāng)L鄰域匹配時，本文方法計算的像點數(shù)與傳統(tǒng)方法相同;但在不匹配時，本文方法需要計算的像點數(shù)明顯少于傳統(tǒng)方法。因此，本文方法能夠有效地減少L鄰域匹配過程中的計算時間，降低紋理合成的預(yù)處理速度，進而提高紋理合成的速度。并且，在大規(guī)模繪制中，隨著鄰域規(guī)模的增大，本文方法的性能越好，如圖8所示。

圖8 時間對比圖Fig.8 Comparison of time

2)紋理適用性

結(jié)構(gòu)性紋理中含有紋元，每個紋元基本相同且其排列具有一定的結(jié)構(gòu)性及周期性，本文在處理結(jié)構(gòu)性紋理時，能夠有效的保持結(jié)構(gòu)性紋理中的周期性等結(jié)構(gòu)特征，獲得了令人滿意的效果，如圖5所示。

本文在上述實驗基礎(chǔ)上，還對自然紋理、隨機型紋理(即紋元大小、顏色等不全相同，但是又呈現(xiàn)出一定的規(guī)律性)、紋元結(jié)構(gòu)較簡單型紋理及紋元結(jié)構(gòu)較復(fù)雜型紋理分別進行了仿真實驗，結(jié)果如圖9～12所示。實驗結(jié)果表明，本文方法在處理不同類型紋理時，都獲得了較好的視覺效果，表現(xiàn)出了較強的適用性。

圖9 自然紋理Fig.9 Natural texture

圖10 隨機型結(jié)構(gòu)Fig.10 Random structural texture

圖11 簡單紋元結(jié)構(gòu)Fig.11 Simple texel

圖12 復(fù)雜紋元結(jié)構(gòu)Fig.12 Complex texel

3)L鄰域匹配塊優(yōu)化性

傳統(tǒng)方法在進行L鄰域的匹配時，采用了L鄰域整體誤差作為相似性度量標(biāo)準(zhǔn)，因為其只反映了鄰域中像點顏色的統(tǒng)計分布差異，并未考慮到鄰域中像點顏色的空間分布特征。如圖8所示，空間分布差別很大的2個塊，統(tǒng)計分布差異卻很小。因此，采用傳統(tǒng)方法進行鄰域匹配時，會造成一定的匹配誤差，甚至是匹配錯誤，從而導(dǎo)致在紋理合成全局誤差的累積，嚴(yán)重影響合成效果。

圖13 空間分布差別說明圖Fig.13 Different spatial distribution

本文方法在進行L鄰域的匹配時，將L鄰域進行分割，采用基于L鄰域分割的優(yōu)先級多次匹配方法，對各個已分割區(qū)域分別進行相似性度量，既能反映出2個L鄰域中像點顏色的統(tǒng)計分布差異，又能考慮到其空間分布差異。有效地減少了L鄰域匹配過程中的誤差，從一定程度上解決了誤匹配問題，對提高紋理合成的質(zhì)量具有明顯的效果。

4 結(jié)束語

本文在充分考慮了結(jié)構(gòu)性紋理的方向性、周期性等特點的基礎(chǔ)上，提出了一種基于L鄰域分割的優(yōu)先級多次匹配方法，通過計算紋理樣圖的灰度共生矩陣相關(guān)值，完成L鄰域所有已分割區(qū)域的優(yōu)先級分配，有效地改善了紋理合成的視覺效果，對減少匹配誤差、提高運算速度具有明顯效果。

通過實驗驗證，本文方法在處理結(jié)構(gòu)性紋理、隨機型紋理以及自然紋理時，均能獲得令人滿意的效果。同時，本文方法的效果好壞不依賴于紋元結(jié)構(gòu)的復(fù)雜性，即在處理簡單紋元結(jié)構(gòu)和復(fù)雜紋元結(jié)構(gòu)的紋理圖像時，均能獲得較好的視覺效果。

如何提高紋理中像點間相關(guān)性度量的精確度，以及如何在紋理合成的過程中考慮到紋理的結(jié)構(gòu)性信息將作為下一步的研究方向。

［1］王興梅，印桂生，門志國，等.基于MRF的動態(tài)場景中運動目標(biāo)提取方法研究［J］.哈爾濱工程大學(xué)學(xué)報，2011，32(8):1029-1034.WANG Xingmei1，YIN Guisheng，MEN Zhiguo，et al.Research on the extraction algorithm for a moving target in a dynamic scene based on Markov random fields(MRF)［J］.Journal of Harbin Engineering University，2011，32(8):1029-1034.

［2］EFROS A A，LEUNG T K.Texture synthesis by non-parametric sampling［C］//The Proceedings of the Seventh IEEE International Conference on Computer Vision.［S.l.］，1999:1033-1038.

［3］ASHIKHMIN M.Synthesizing natural textures［C］//Proceedings of the 2001 symposium on Interactive 3D graphics.NC USA:AMC Press，2001:217-226.

［4］EFROS A A，F(xiàn)REEMAN W T.Image quilting for texture synthesis and transfer［C］//Proceedings of the 28th annual conference on Computer graphics and interactive techniques.Los Angeles:AMC Press，2001:341-346.

［5］KWATRA V，SCH?DL A，ESSA I，et al.Graphcut textures:image and video synthesis using graph cuts［C］//ACM Transactions on Graphics(TOG).San Diego:AMC Press，2003，22(3):277-286.

［6］李大錦.一種改進的自然紋理合成方法［J］.圖學(xué)學(xué)報，2012，4(33):88-92.LI Dajin.An improved method of natural texture synthesis［J］.Journal of Graphics，2012，4(33):88-92.

［7］杜常青，錢文華.二維紋理合成算法優(yōu)化研究［J］.計算機科學(xué)，2013，4(40):314-316.DU Changqing，QIAN Wenhua.Optimization technique of 2D texture synthesis［J］.Computer Science，2013，4(40):314-316.

［8］王繼東，龐明勇，趙瑞斌.旋轉(zhuǎn)的Wang Tiles紋理合成算法［J］.中國圖象圖形學(xué)報，2013，1(18):49-54.WANG Jidong，PANG Mingyong，ZHAO Ruibin.Texture synthesis using rotational wang tiles［J］.Journal of Image and Graphics，2013，1(18):49-54.

［9］ZHU S C，LIU X W，WU Y N.Exploring texture ensembles by efficient markov chain monte carlo-toward a“trichromacy”theory of texture［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22(6):554-569.

［10］ZUCKER S W，TERZOPOULOS D.Finding structure in co-occurrence matrices for texture analysis［J］.Computer graphics and image processing，1980，12(3):286-308.

［11］HARALICK R M.Statistical and structural approaches to texture［J］.Proceedings of the IEEE，1979，67(5):786-804.

［12］劉舒，姜琦剛，邵永，等.應(yīng)用灰度共生矩陣的紋理特征描述的研究［J］.科學(xué)技術(shù)與工程，2012，33(12):8909-8914.LIU Shu，JIANG Qigang，SHAO Yongshe，et al.Investigation of the textual description based on gray level co-occurrence matrix measurements［J］.Science Technology and Engineering，2012，33(12):8909-8914.

［13］WEI L Y，LEVOY M.Fast texture synthesis using treestructured vector quantization［C］//Proceedings of the 27th annual conference on Computer graphics and interactive techniques.New Orleans:ACM Press/Addison-Wesley Publishing Co，2000:479-488.

［14］岳曉菊，康寶生，閆麗君.利用相關(guān)性原理紋理合成的改進算法［J］.計算機工程與應(yīng)用，2011，10:190-192.YUE Xiaoju，KANG Baosheng，YAN Lijun.Improved algorithm for texture synthesis based on principle of relevance［J］.Computer Engineering and Applications，2011，47(10):190-192.