基于L鄰域分割的結構性紋理合成方法

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

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

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

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

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

1 L鄰域的分割理論

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

在像點P的L鄰域中(如圖1所示)，像點的位置不同，其與待合成像點的相關性也不同。結合L鄰域的特點，取4個特殊方向，將L鄰域分割為4個區域(如圖2所示)。其中，區域1與像點P成45°;區域2與像點P成90°;區域3與像點P成135°;區域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鄰域分割的合成方法，如果只用分割后的一部分鄰域來尋找匹配塊，同樣只是考慮到了局部匹配的誤差，也會出現匹配錯誤。所以本文方法兼顧局部和整體的誤差，設計了一種新的匹配規則:對L鄰域進行分割，采用基于優先級的多次匹配，完成L鄰域的完整匹配。

2.1 灰度共生矩陣

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

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

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

圖3 樣本紋理及其相關值Fig.3 Sample texture and its IDM

2.2 基于灰度共生矩陣相關值的優先級分配

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

圖4 優先級分配示意圖Fig.4 Priority assignment

2.3 L鄰域的多次匹配

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

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

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

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

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

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

新的匹配規則，加快了預處理過程，并減少了傳統的L鄰域在整體鄰域匹配搜索過程中存在的計算復雜性和匹配誤差。

2.4 分割法的算法流程

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

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

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

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

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

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

6)算法結束。

3 實驗結果分析

3.1 實驗結果

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

實驗結果對比圖如圖5～7所示。

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

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

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

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

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

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

3.2 性能評價

1)紋理合成時間

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

①L鄰域不匹配

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

式中:n為鄰域的規模。

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

式中:θ≤1，為匹配階段計數值。即:當優先級最高的分割區域不匹配時，θ=1/4;當優先級次高區域不匹配時，θ=2/4;當優先級次低的區域不匹配時，θ=3/4;當優先級最低的區域不匹配時，θ=1。

②L鄰域匹配

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

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

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

2)紋理適用性

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

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

圖9 自然紋理Fig.9 Natural texture

圖10 隨機型結構Fig.10 Random structural texture

圖11 簡單紋元結構Fig.11 Simple texel

圖12 復雜紋元結構Fig.12 Complex texel

3)L鄰域匹配塊優化性

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

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

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

4 結束語

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

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

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

［1］王興梅，印桂生，門志國，等.基于MRF的動態場景中運動目標提取方法研究［J］.哈爾濱工程大學學報，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，FREEMAN 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］.圖學學報，2012，4(33):88-92.LI Dajin.An improved method of natural texture synthesis［J］.Journal of Graphics，2012，4(33):88-92.

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

［8］王繼東，龐明勇，趙瑞斌.旋轉的Wang Tiles紋理合成算法［J］.中國圖象圖形學報，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］劉舒，姜琦剛，邵永，等.應用灰度共生矩陣的紋理特征描述的研究［J］.科學技術與工程，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］岳曉菊，康寶生，閆麗君.利用相關性原理紋理合成的改進算法［J］.計算機工程與應用，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.