李大錦

（山東師范大學傳媒學院，山東 濟南 250024）

基于樣圖的紋理合成的實質(zhì)是根據(jù)給定的一張樣本圖像，通過分析其像素顏色的統(tǒng)計規(guī)律性，重新生成一張任意大小的圖像，生成的圖像在視覺上與原樣本圖像非常相似。目前紋理合成主要是利用馬爾科夫隨機場的理論?；隈R爾科夫模型，國內(nèi)外學者已經(jīng)提出較多的紋理合成算法，這些方法基本可歸結(jié)為兩大類：基于像素點的紋理合成[1-3]和基于塊的紋理合成[4-6]。隨后在這些基本合成算法的基礎上，人們又提出了一些改進的合成方法[7-9]。 文獻[7-8]提出的可并行計算的紋理合成方法，可有效地提高合成速度。為了減少基于塊的合成方法中紋理塊間的不連續(xù)，熊昌鎮(zhèn)等[9]在基于塊的合成方法的基礎上利用不規(guī)則紋理塊來實現(xiàn)逐塊合成。Zhang等[10]基于像素的合成方法，利用基于特征的變形和融合技術，實現(xiàn)了紋理圖案方向的改變和兩種紋理間的漸變。此外，人們還提出了針對某類具體應用的紋理合成算法。Miyata等[11]提出的用于合成“鋪路”圖案的紋理合成方法以及Ashikhmin[3]的自然紋理合成算法；文獻[10，13]分別提出了兩種多尺度紋理合成算法，在合成過程中，可以將樣本的圖像任意縮放，形成不同尺度的紋理圖案。

Ashikhmin的自然紋理合成算法是所有基于像素點的紋理合成算法中較快的一種，不僅適合自然景物的合成，對于隨機性較強的紋理同樣適應。它采用L型鄰域搜索匹配點，同時將匹配點的搜索限制在L型鄰域產(chǎn)生的候選點之中，既提高了合成速度，同時使合成圖片像素間保持了良好的連續(xù)性。最近，岳曉菊等[14]也提出了一種Ashikhmin的改進算法，將Ashikhmin算法中的像素點改為像素塊，雖然可有效的提高合成速度，但是卻沒有解決塊間的不連續(xù)問題。

在Ashikhmin的算法中，由L型鄰域產(chǎn)生的候選點有時會超越樣圖邊界，候選點的越界是造成結(jié)果圖像明顯產(chǎn)生塊間不連續(xù)的主要原因。在Ashikhmin的文章里沒有給出很好的解決方法，對于越過樣圖底部的候選點，只是簡單的用一個隨機選取的有效點來代替。對于越過水平邊界的候選點Ashikhmin沒有明確指出如何解決。本文對Ashikhmin的算法進行了改進，通過在樣圖內(nèi)部尋找邊界點的最佳匹配像素將越界候選點重新定位，有效地解決了Ashikhmin算法中紋理塊間的不連續(xù)問題。

1 Ashikhmin的自然紋理合成算法

Ashikhmin算法的合成順序是從輸出圖像的第1行開始，從左至右逐行合成每個像素。采用L型鄰域來計算匹配點的顏色誤差。從已合成的像素中選取和待合成像素相鄰的若干像素形成一個L型的像素鄰域，如圖1所示。

合成過程中記錄下每個已經(jīng)合成的像素在樣本圖像中的位置。對于待合成像素的L型鄰域中每個已合成的像素，根據(jù)其和待合成像素的位置偏移，在樣本圖像中可以找到一個相同位置偏移的像素點（圖1樣本圖像中黑色點），該像素點就是待合成像素的一個候選點。L型鄰域中每個像素都產(chǎn)生一個候選點，待合成像素最終確定的采樣點是所有候選點中匹配最好的候選點。候選點的匹配計算采用顏色空間的歐氏距離作為匹配標準。顏色距離計算如式(1)。

圖1 Ashikhmin算法中候選點的確定

其中，N1和N2分別是用于計算顏色距離的樣本圖像和目標圖像L型鄰域。R、G、B分別是在p點處像素的紅、綠、藍顏色值，下標1、2分別代表樣本圖像和目標圖像。

Ashikhmin的算法描述如下：

用隨機產(chǎn)生的坐標位置采樣樣本圖像的像素填充目標圖像，同時記錄每個像素的采樣坐標；

for( 掃描線順序掃描每個點)

{

找出目標圖像中當前點L型鄰域內(nèi)的所有點；

for( L型鄰域內(nèi)的每個像素點 ){找到該像素的候選點，插入到候選點列表中；}

將候選點列表中相同的候選點刪除；

for( 每個候選點 ){計算其L型鄰域和當前待合成像素L型鄰域的顏色誤差；}

將顏色誤差最小的候選點像素拷貝到當前合成像素，并記錄其在樣本中的坐標；

}

Ashikhmin算法的合成過程實質(zhì)上是像素塊的生長過程，像素塊呈不規(guī)則狀。紋理塊從某個位置開始沿著垂直方向逐步向下生長，當紋理塊生長到樣本圖像的底部時會產(chǎn)生無效的候選點。Ashikhmin給出的解決方案是：將樣圖中的像素與樣圖底部的距離坐標規(guī)格化為[0，1]之間，規(guī)定一個標準距離d∈[0，1]，然后隨機產(chǎn)生一個距離rand∈[0，1]，滿足rand4﹥d；在樣圖中取該點對應的候選點代替越界的無效候選點，由隨機產(chǎn)生的有效候選點開始繼續(xù)紋理塊的生長。Ashikhmin沒有給出如何解決水平越界候選點的問題。一般的方法是通過將候選點的水平坐標x對樣圖寬度取模運算，循環(huán)采樣樣本圖像；或者同樣采用Ashikhmin解決垂直方向越界的方法，隨機產(chǎn)生有效候選點。

Ashikhmin算法合成的結(jié)果圖像塊在豎直方向上是不規(guī)則的，但在圖像塊生長到樣本圖像的底部時會產(chǎn)生明顯的水平分解線。由于樣本圖像底部和隨機產(chǎn)生的候選點像素沒有任何相關性，在視覺上也不能形成平滑的過度，導致了明顯的塊間躍變。同時由于候選點的隨機性還導致了上下兩個紋理塊之間的像素比較紊亂。

2 改進的自然紋理合成算法

針對上述Ashikhmin算法的不足，本文對原Ashikhmin算法進行了改進。將樣本圖像的底部和右側(cè)邊界區(qū)域用樣圖內(nèi)部其他的像素塊代替，使合成中的圖像塊在生長到接近邊緣處時轉(zhuǎn)向樣圖內(nèi)部某個區(qū)域重新開始生長。

受文獻[5]“圖像縫合”思想的啟發(fā)，將邊緣處一定寬度的像素塊用樣圖內(nèi)的最佳匹配像素塊來代替。取靠近樣圖邊緣的1/4樣圖高度的區(qū)域（圖2中2區(qū)域），在樣圖中尋找與之匹配的區(qū)域（圖2中的1區(qū)域），匹配誤差的計算采用式(1)的方法。匹配區(qū)域確定后，再確定兩塊區(qū)域的“縫合線”。這條縫合線將兩塊區(qū)域各劃分出兩部分（圖2中的白色線），將區(qū)域2中處于縫合線以下的部分用區(qū)域1的縫合線以下的區(qū)域像素來代替。在合成過程中當紋理塊生長到縫合線處時，會轉(zhuǎn)向替代區(qū)域的位置，重新進行紋理塊的生長。為了避免再生長的紋理塊很快又到達底部，在尋找匹配區(qū)域的時候，將匹配區(qū)域限制在樣本圖像上部的1/2之內(nèi)。因為處于縫合線兩側(cè)的兩個像素塊的相鄰像素顏色距離差別最小，所以縫合后的圖像在視覺上不會看到明顯的分界線。

圖2 邊緣像素區(qū)域的替代

縫合線的計算確定采用最短路徑法，首先要建立一個有向無環(huán)圖（見圖3所示）。以求水平縫合線為例，有向無環(huán)圖的建立方法是：將兩塊圖像重疊合，圖3中圓圈是兩個圖像塊重疊的像素。先在重疊圖像的左右兩側(cè)建立兩個節(jié)點，作為有向無環(huán)圖的開始和結(jié)束節(jié)點；在圖像中每四個相鄰像素的中間也分別建立節(jié)點（圖3中黑色方塊）；然后從左到右用弧連接這些節(jié)點，上下每相鄰的兩個節(jié)點也都用一條弧相連。取弧的左右兩邊重疊像素的顏色誤差eij作為每條弧的權值。從開始點到結(jié)束點的一條最短路徑即是最佳匹配的縫合線。權值eij的計算如下：

圖3 用于計算縫合線的有向無環(huán)圖

式中，eij是像素（i,j）到像素（i,j+1）之間的顏色誤差；Eij是兩個匹配區(qū)域?qū)c（i,j）處顏色的誤差；C1、C2分別是兩個匹配區(qū)域某點像素的顏色值，下標i,j指對應像素的坐標，上標r、g、b分別指3個顏色通道。

另外需要一個用于索引樣本坐標的索引二維數(shù)組，存放樣本中每個像素對應的實際坐標，用匹配的區(qū)域替代邊緣區(qū)域以后，被替代邊緣區(qū)域的像素坐標索引應指向替代區(qū)域的坐標。在合成過程中，從索引數(shù)組中查找像素的位置。在初始化輸出圖像時，我們不用單個像素，而是采用隨機產(chǎn)生的像素塊來初始化索引數(shù)組。像素塊的大小根據(jù)紋理特征的不同來確定。實驗證明：對于結(jié)構性較強的紋理，像素塊取基本紋理元素的1～3倍。對于一般的自然紋理，可取樣圖大小的1/8～1/4。

改進后的算法描述如下：

用隨機產(chǎn)生的像素塊初始化坐標索引數(shù)組。

搜索匹配區(qū)域，建立有向圖并計算最小路徑，將替代區(qū)域的坐標填入索引數(shù)組中樣本邊緣被替代的區(qū)域。

用隨機產(chǎn)生的坐標位置采樣樣本圖像的像素填充目標圖像，記錄對應索引數(shù)組中的像素坐標

For（掃描線順序掃描每個點）

{

找出目標圖像中當前點L型鄰域內(nèi)的所有點；

For（L型鄰域內(nèi)的每個像素點）{在索引數(shù)組中找到候選點并插入到候選點列表。}

將候選點列表中相同的候選點刪除；

For（每個候選點）{計算當前候選點L型鄰域和當前待合成像素L型鄰域的顏色誤差；}將顏色誤差最小的候選點像素拷貝到當前合成像素，并記錄其在樣本中的坐標；

}

3 結(jié) 果

圖4中的白色線是合成后的圖像中紋理塊的邊界，圖4(a)是Ashikhmin方法合成結(jié)果，圖4(b)是本文方法合成的結(jié)果。可以看出本文的算法在豎直和水平兩個方向上都形成了不規(guī)則的像素塊邊界，避免了紊亂像素的產(chǎn)生，同時，從圖4(b)可以看到本文的方法生成的像素塊相對較大，能在更大范圍內(nèi)保持了像素的相關性。

圖5給出了本文算法和原Ashikhmin算法的合成結(jié)果的比較?？梢钥闯?，本文算法的結(jié)果要明顯優(yōu)于Ashikhmin算法，尤其對于結(jié)構性較強的紋理，能很好的保持紋理的結(jié)構特征。

在算法時間效率上，本文算法比原來算法增加了尋找替代像素區(qū)域和“縫合線”的計算，但是在實際應用中這些計算可以作為預處理階段事先處理，在合成過程中本文算法不再增加任何額外時間。

圖4 合成后的紋理塊邊界

圖5 原方法和本文方法的結(jié)果比較

4 總 結(jié)

本文基于自然紋理合成算法，提出了一種改進的自然紋理合成方法，解決了原算法中候選點的越界問題，有效地降低了紋理塊間的明顯變化。實驗結(jié)果表明：使用本文的合成方法，合成效果得到了很大的改善。

[1]Efros A A, Leung T K. Texture synthesis by nonparametric sampling [C]//Proc of the International Conference on Computer Vision. Washington D C,USA: IEEE Computer Society, 1999: 1033-1038.

[2]Wei Liyi, Levoy M. Fast texture synthesis using tree-structured vector quantization [C]//Proc of the International Conference on Computer Graphics and Interactive Techniques. New York, USA: ACM Press,2000: 479-488.

[3]Ashikhmin M. Synthesizing natural textures [C]//Proc of ACM Symposium on Interactive 3D Graphics.New York, USA: ACM Press, 2001: 217-226.

[4]Liang L, Liu C, Xu Y Q, et al. Real-time texture synthesis by patch-based sampling [J]. ACM Transactions on Graphics, 2001, 20(3): 127- 150.

[5]Efros A A, Freeman W T. Image quilting for texture synthesis and transfer [C]//Proceedings of SIGGRAPH2001, New York: ACM Press, 2001:341-346.

[6]Kwatra V, Arno Sch¨odl ECT. Graphcut textures:image and video synthesis using graph cuts [C]//Proceeding of SIGGRAPH03. New York: ACM Press,2003: 277-286.

[7]陳 昕, 王文成. 大尺寸紋理的實時合成[J]. 軟件學報, 2009, 20: 193-201.

[8]Lefebvre S, Hoppe H. Parallel controllable texture synthesis [J]. ACM Trans on Graphics, 2005, 24(3):777-786.

[9]熊昌鎮(zhèn), 黃 靜, 齊 東. 基于不規(guī)則塊的紋理合成方法[J]. 計算機研究與發(fā)展, 2007, (4): 701- 706.

[10]Zhang Jingdan, Zhou Kun, Velho L, et al. Synthesis of progressively-variant textures on arbitrary surfaces [J].ACM Transactions on Graphics, 2003, 22(3):295-302.

[11]Miyata K, Itoh T, Shimada K. A method of generating pavement textures using the square packing technique [J].The Visual Computer, 2001, 17(8): 475-490.

[12]Han C, Risser E, Ramamoorthi R, et al. MultIscale texture synthesis [J]. ACM Trans. on Graphics, 2008,27(3): 1-8.

[13]李大錦. 可控的連續(xù)多尺度紋理合成[J]. 計算機工程, 2009, 35(24): 211-212.

[14]岳曉菊, 康寶生, 閆麗君. 利用相關性原理紋理合成的改進算法[J]. 計算機工程與應用, 2011, 47(10):190-192.