基于條塊拼接的快速紋理合成

鄒 昆，沃 焱，張見威

（1.電子科技大學 中山學院計算機學院，廣東 中山528402；2.華南理工大學 計算機科學與工程學院，廣東 廣州510006）

0 引 言

紋理映射是計算機圖形學中增加計算機生成模型的真實感的一種重要方法。基于樣圖的紋理合成［1－3］可以根據給定的樣圖生成任意大小的相似紋理，解決了紋理映射中因紋理尺寸不足所引起的接縫和走樣問題。與過程紋理合成相比，其生成模型的適用范圍更廣，且無需復雜的參數調試，因此成為近年來的一個研究熱點。

基于樣圖的合成算法可分為逐點合成［4－7］和逐塊合成［8－14］兩類，逐塊合成算法在速度和結構特征保持方面更有優勢。對于這兩類算法，匹配點/塊的搜索通常是其瓶頸，一種加速方法是優化匹配搜索過程［11－12］，另一種加速方法是通過預處理來縮小合成時的搜索范圍甚至免除匹配搜索。如文獻 ［9］通過在預處理階段計算得到一組優選位移，來大幅縮小合成時匹配塊的搜索范圍。而Zelinka［4］在預處理階段計算得到一個Jump Map，可通過其查找樣圖中與任一像素具有相似鄰域的像素，合成時通過連續拷貝像素以及在相似鄰域像素間的跳轉來完成合成。

在已有的大量基于樣圖的紋理合成算法中，大多數是離線的［4－6，9－14］，即 提 前 合 成 好 所 需 要 的 紋 理 ， 將 輸 出 保 存起來供渲染時使用。離線紋理合成算法的一個問題是當合成紋理較大時，要占用較多存儲空間，特別是當待渲染場景需要很多不同的紋理圖時。在2010年的SIGGRAPH上，Lefebvre等［8］提出了一種基于圖的紋理合成算法，根據可生成紋理空間建圖，并將紋理合成轉化為該圖中的最短路徑搜索問題，合成完成后，僅需要保存得到的路徑，合成的紋理可在渲染時實時重建，這樣就節省了大量內存空間。然而該方法僅適用于建筑紋理，在合成更具一般性的紋理時不能較好地保持紋元特征。

本文基于 Lefebvre算法［8］，并結合 Zelinka［4］提出的基于Jump Map的合成算法中跳轉的思想，以及文獻 ［9］中預先計算優選位移的思想，提出一種新的紋理合成算法。與文獻 ［8］類似，通過相繼沿垂直和水平方向通過對樣圖中的條塊重組進行合成，區別在于沒有建圖并進行最短路徑搜索，而是在預處理中計算原圖在垂直和水平兩個方向上的平移誤差，得到與誤差較小的平移間距對應的平行切割集，在合成時按照與誤差相關的概率值選擇增長或在平行切割間跳轉來完成合成。該算法對于在兩個主方向上具有平移相似性的紋理具有很好的合成效果，合成過程因無需匹配，速度很快，合成完成后僅需保存與垂直和水平拼接方案所對應的兩組切割集，占用空間小。

1 Lefebvre紋理合成算法

假定樣圖I為W×H像素，待合成圖像為WT×HT像素。Lefebvre算法的合成過程由兩個方向的合成組成，先沿垂直方向合成出W×HT的中間圖，再以此中間圖為樣圖，沿水平方向合成出WT×HT的目標紋理。由于兩個方向合成類似，在此以水平方向為例介紹其單方向的預處理和合成過程，然后簡介雙方向合成。

1.1 預處理

預處理階段的主要任務是，對于每個整數σ∈ ［1，W－1］，在樣圖中查找相距σ像素的平行切割并添加到集合C。圖1給出了σ＝100時的一對平行割。平行切割的誤差為c和c‖右邊像素的誤差之和

式中：p——預定義的常數。該誤差為c的左部和c‖的右部的拼接誤差，也是c‖的左部和c的右部的拼接誤差。在合成過程中可能發生從c到c‖的跳轉或從c‖到c的跳轉，前者將c的左部和c‖的右部拼接，后者將c‖的左部和c的右部拼接。

在查找平行割時，需要δ（c，c‖）盡可能小。其步驟如下：

（1）計算得到一個 ［W－σ］×H的誤差圖Eσ，Eσ（x，y）＝‖I（x，y）－I（x＋σ，y）‖p；

（2）使用動態規劃在Eσ中尋找一條最小誤差路徑π（從上至下，y值單調遞增）；

（3）如果π的誤差為∞，則結束。否則將π對應的一對平行切割添加到C中，并將Eσ中與π相距σ以內的像素值設為∞，然后返回步驟 （2）。

1.2 單方向合成

圖1 相距100像素的平行割

合成結果由樣圖中的條塊拼接而成，每一種拼接方案對應于一系列切割c＊，c0，c0‖，…，cn，cn‖，c＋，其中c＊和c＋是由用戶指定的起始和終止切割，默認對應于原圖的第一和最后一列，而ci和ci‖分別是前一條塊的終止切割和下一條塊的起始切割。合成過程可以看成是從c＊開始，逐步添加切割到合成圖中，如圖2所示。在某一時刻，當前終止割為ca時，接下來有兩種選擇：要么增長當前條塊至ca的后繼切割 （綠色表示），要么通過跳轉到與ca平行的切割ca‖（紅色表示）而拼接一個新的條塊。前者代價為0而后者代價為δ（ca，ca‖）。這樣可以創建一個圖G＝ （C×Z，E＜∪E‖）來表示所有可能的合成方案，其中每個結點（c，z）∈C×Z代表切割c在合成圖中放置在橫坐標z處，而E＜和E‖分別表示增長邊和跳轉邊集合，與之前的兩種選擇相對應。圖G每條從結點 （c＊，）到結點（c＋，WT）的路徑都對應一種拼接方案，其誤差為路徑上所有跳轉邊的代價和，這樣合成問題就轉化為最短路徑搜索問題。

圖2 通過添加切割進行合成［8］

1.3 雙方向合成

合成的最終目標是合成WT×HT的圖像，這通過先沿垂直方向進行單方向合成，再沿水平方向合成來實現，其中第二步使用前一步的結果作為樣圖。為了快速計算出中間結果的切割集，在預處理階段，對于每一σ，保存與Eσ對應的路徑圖 （與Eσ相同大小，記錄了在每個像素位置處的最小誤差路徑走向），以及每條最小誤差路徑的起始位置，完成垂直方向合成后，將其拼接方案應用于每一路徑圖，根據路徑起始位置快速算出新的路徑 （誤差不一定最小），并重新計算每條路徑的誤差。

2 本文合成算法

2.1 算法基本思想

Lefebvre算法僅適用于建筑紋理合成，對于更具一般性的紋理合成效果較差，分析其主要原因如下：

（1）在添加平行切割路徑時僅考慮了局部匹配誤差，不能較好地保持大尺度特征，如當平行切割間距σ與紋理的周期性相違背時，相對應的跳轉會帶來明顯的瑕疵；

（2）合成過程限定了起始和終止位置，這種控制很容易違背紋理的周期性，為了滿足這種限定條件容易在最短路徑中包含誤差較大的邊。

為了提高一般紋理的合成質量，在預處理中查找平行切割時對σ做了限制，僅對整體匹配誤差較小的σ值查找平行切割；另外摒棄了基于圖的合成過程，仍然通過添加切割的方式進行合成，但合成至某一切割時，是增長當前塊至其后繼切割還是跳轉到其平行切割是通過誤差大小相關的概率值來判定。

2.2 預處理

預處理階段的主要任務是計算得到水平和垂直方向一組誤差較小的切割路徑，在此以水平方向為例 （針對水平方向合成，切割為垂直方向）。

2.2.1 最小誤差平移距離集計算

將樣本I沿水平方向平移σ像素后得到Iσ（如圖3所示），其與平移前I的重疊區域的逐像素誤差其實正好等于Lefebvre算法中的誤差圖Eσ中的像素值，在此針對每一σ計算其整體誤差 （為了便于加速將p值取2）

然后取前N個誤差最小的σ值構成集合TH。為保持大尺度特征，避免特征拖曳，限制σ值于區間 ［0.1W，0.9W］內。由于

等式右邊前兩項為矩形區域的像素值平方和，可用平方和查找表 （SST）［15］加速，最后一項I（x＋σ，y）可改寫為I－（W－σ－1－x，y）（其中I－為將樣本I左右翻轉后得到的圖像），即H個一維卷積之和，可用FFT進行加速。

2.2.2 切割集計算

圖3 I與Iσ的重疊區域及一條切割路徑p

針對每一σ∈TH，使用和1.1節中相同方法計算平行切割 （每對平行切割對應于重疊區域的一條最小誤差路徑，如圖3中p所示），將它們添加到切割集CH，同時保存平行切割的誤差δ（c，c‖）。為了保證平行切割的誤差不至于過大，在計算同一重疊區域的多條切割路徑時，要求它們的誤差不得超過第一條路徑的20%，超過則結束與當前σ值對應的平行切割查找過程。

針對垂直方向用類似的方法計算TV和CV。

2.3 合 成

在此首先以水平方向為例，介紹從樣圖I合成WT×H目標圖的單方向合成算法。定義切割c的后繼切割為與c不交叉且在I中位于c右方的切割。將I的第一列也看成切割。定義從切割c0跳轉到其平行切割c0‖的概率為

這樣誤差最小的切割跳轉概率最大。算法描述如下：

（1）設已合成長度L＝0，設合成切割表LH為空；設當前切割c為I的第一列，并將c添加至LH。

（2）若當前切割c沒有后繼切割 （如圖4中c1‖和c3‖），則轉 （3），否則隨機選取一個最前后繼切割c’（圖4中c1和c2均為第一列的最前后繼切割），將c到c’間的條塊拼貼至合成圖，設L＋＝c’min－cmin，c＝c’，若L≥WT－1，則算法結束，否則轉 （4）。

（3）若L＋W－1－cmin≥WT－1，則將c右方的條塊拼貼到合成圖中，算法結束；否則將c添加至LH，并執行跳轉，即設c＝c‖，轉 （2）。

（4）產生一 ［0，1］內的隨機數r，若r＜P（c→c‖），則將c添加至LH，并跳轉 （即設c＝c‖），轉 （2）；否則直接轉 （2）。

為進一步增加合成的多樣性，在第 （1）步中可隨機選擇一切割為當前切割c，并設L＝cmin－cmax。上述算法最終得到一切割序列，其形式如LH＝ ｛c＊，c1，c2…cn｝，其中c＊為起始切割，后面均為執行跳轉的切割，合成圖的構成為：從到c1的條塊，從c1‖到c2的條塊，…，cn‖右方的塊。

在由單方向合成向雙方向合成的擴展方面和Lefebvre算法相同，先沿垂直方向合成，然后沿水平方向合成，并采用了類似的加速算法計算中間結果的切割集，只不多僅需對N個σ值保存對應的路徑圖。

圖4 I中所有c∈CH的示意圖（為簡單起見假設僅3對）

合成完畢后，僅需保存兩個方向的切割序列LH和LV。在渲染時對于給定的紋理坐標 （x，y），根據LH和x可確定其對應于中間圖的像素坐標 （x0，y），然后再根據LV和y可確定其對應于樣圖的像素坐標 （x0，y0），如圖5所示（僅顯示了2對切割）。

3 實驗結果

用PC機 （Intel Core 2Duo CPU T5750 2.00G/2G）對一些紋理進行了合成，圖6中為樣圖，其中包括隨機紋理、半規則紋理和規則紋理。圖7給出了使用Lefebvre算法和本文算法的合成結果，合成圖大小均為256×256像素。在使用Lefebvre算法合成時，起始切割和終止切割分別設為第一行/列和最后一行/列，在使用本文算法合成時，繩網和面包的N值取5，飲料罐N值取4，飛獅N值取3。表1中是相應的時間數據。

可以看到，Lefebvre算法的合成結果中存在特征拖曳、重復或丟失的情況，這是由于在計算切割時沒有考慮大尺度特征保持所造成的，本文算法的合成效果明顯更優。在時間方面，本文算法的預處理速度有十幾倍的提升，這歸功于FFT加速以及切割計算次數的減少，合成速度更是有幾十倍的提升，因為無需進行任何匹配操作，如圖7所示。

圖7 合成結果對比

表1 圖7中紋理的合成時間數據

4 結束語

本文在Lefebvre算法基礎上提出一種新的基于條塊拼接的快速紋理合成算法，通過在計算切割路徑時考慮整體匹配誤差，使得對一般紋理的合成質量大幅提高，在合成時改路徑搜索為隨機跳轉，增加了合成結果的隨機性，合成速度也有幾十倍的提升。該算法對于具有水平和垂直平移相似性的紋理具有較好的合成效果，且合成結果可以緊湊的方式保存，在渲染時實時重建。

［1］WEI L Y，Lefebvre S，Kwatra A，et al.State of the art in example－based texture synthesis ［R］.Eurographics State of The Art Report Eurographics Association，2009.

［2］ZHU Wenhao，WEI Baogang.The technology of sampledbased texture synthesis ［J］.Journal of Image and Graphics，2008，13 （11）：2063－2069 （in Chinese）. ［朱文浩，魏寶剛.基于樣本的紋理合成技術綜述 ［J］.中國圖象圖形學報，2008，13 （11）：2063－2069.］

［3］XUE Feng.Research on texture synthesis from sample ［M］.Hefei：Hefei Univerity of Technology Press，2007 （in Chinese）.［薛峰.基于樣圖的紋理合成技術研究 ［M］.合肥：合肥工業大學出版社，2007.］

［4］Zelinka S，Garland M.Jump map－based interactive texture synthesis［J］.ACM Transactions on Graphics，2004，23 （4）：930－962.

［5］ZOU Kun，HAN Guoqiang，LI Wen，et al.Multiresolution texture synthesis using real－time pattern matching ［C］.Proceedings of the IEEE International Conference on Robotics and Biomimetics.Sanya，China：IEEE Press，2007：1327－1332.

［6］LI Dajin.Controllable consecutive multi－scale texture synthesis［J］.Computer Engineering，2009，35 （24）：211－212 （in Chinese）.［李大錦.可控的連續多尺度紋理合成 ［J］.計算機工程，2009，35 （24）：211－212.］

［7］Lefebvre S，Hoppe H.Appearance－space texture synthesis ［C］.New York，NY，USA：ACM SIGGRAPH，2006：541－548.

［8］Lefebvre S，Hornus S，Lasram A.By－example synthesis of architectural textures［C］.Los Angeles：ACM SIGGRAPH，2010.

［9］ZOU Kun，HAN Guoqiang，LI Wen，et al.An efficient method of texture synthesis based on Graph Cuts ［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2008，20（5）：652－658 （in Chinese）.［鄒昆，韓國強，李聞，等.基于Graph Cut的快速紋理合成算法 ［J］.計算機輔助設計與圖形學學報，2008，20 （5）：652－658.］

［10］CHEN Xin，WANG Wencheng.Reusing partially synthesized textures for real－time synthesis of large textures ［J］.Chinese Journal of Computers，2010，33 （4）：768－775 （in Chinese）.［陳昕，王文成.基于復用計算的大紋理實時合成 ［J］.計算機學報，2010，33 （4）：768－775.］

［11］CAI Zhilin，XU Wenbo，SUN Jun.Quick texture synthesis based on searching matching patch along spiral path ［J］.Computer Engineering and Design，2010，31 （23）：5052－5055（in Chinese）.［蔡志林，須文波，孫俊.螺旋線狀搜索的快速塊匹配紋理合成 ［J］.計算機工程與設計，2010，31（23）：5052－5055.］

［12］LI Yan，WANG Yongdong，WU Wenzhi，et al.Patch－based texture synthesis by searching matching patch along spiral path［J］.Computer Engineering，2006，32 （16）：210－212 （in Chinese）.［李燕，王永東，吳文治，等.螺旋狀匹配搜索的塊拼貼紋理合成 ［J］.計算機工程，2006，32 （16）：210－212.］

［13］YU Yongsheng，GU Yaolin.Improved method based on Ashikhmin and Kong texture synthesis algorithms ［J］.Computer Engineering and Design，2007，28 （2）：395－396 （in Chinese）. ［余永勝，顧耀林.基于Ashikhmin和Kong紋理合成算法的改進方法 ［J］.計算機工程與設計，2007，28 （2）：395－396.］

［14］SUN Yan，CHEN Yong.Texture synthesis based on gradient［J］.Computer Engineering and Design，2007，28 （1）：118－120（in Chinese）.［孫巖，陳勇.基于梯度的紋理合成 ［J］.計算機工程與設計，2007，28 （1）：118－120.

［15］Kilthau S L，Drew M，Moller T.Full search content independent block matching based on the fast Fourier transform ［C］.New York：International Conference on Image Processing，2002：669－672.