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

鄒 昆，沃 焱，張見威

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

0 引 言

紋理映射是計(jì)算機(jī)圖形學(xué)中增加計(jì)算機(jī)生成模型的真實(shí)感的一種重要方法?；跇訄D的紋理合成［1－3］可以根據(jù)給定的樣圖生成任意大小的相似紋理，解決了紋理映射中因紋理尺寸不足所引起的接縫和走樣問題。與過程紋理合成相比，其生成模型的適用范圍更廣，且無需復(fù)雜的參數(shù)調(diào)試，因此成為近年來的一個(gè)研究熱點(diǎn)。

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

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

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

1 Lefebvre紋理合成算法

假定樣圖I為W×H像素，待合成圖像為WT×HT像素。Lefebvre算法的合成過程由兩個(gè)方向的合成組成，先沿垂直方向合成出W×HT的中間圖，再以此中間圖為樣圖，沿水平方向合成出WT×HT的目標(biāo)紋理。由于兩個(gè)方向合成類似，在此以水平方向?yàn)槔榻B其單方向的預(yù)處理和合成過程，然后簡介雙方向合成。

1.1 預(yù)處理

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

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

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

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

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

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

1.2 單方向合成

圖1 相距100像素的平行割

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

圖2 通過添加切割進(jìn)行合成［8］

1.3 雙方向合成

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

2 本文合成算法

2.1 算法基本思想

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

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

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

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

2.2 預(yù)處理

預(yù)處理階段的主要任務(wù)是計(jì)算得到水平和垂直方向一組誤差較小的切割路徑，在此以水平方向?yàn)槔?（針對水平方向合成，切割為垂直方向）。

2.2.1 最小誤差平移距離集計(jì)算

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

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

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

2.2.2 切割集計(jì)算

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

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

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

2.3 合 成

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

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

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

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

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

（4）產(chǎn)生一 ［0，1］內(nèi)的隨機(jī)數(shù)r，若r＜P（c→c‖），則將c添加至LH，并跳轉(zhuǎn) （即設(shè)c＝c‖），轉(zhuǎn) （2）；否則直接轉(zhuǎn) （2）。

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

圖7 合成結(jié)果對比

表1 圖7中紋理的合成時(shí)間數(shù)據(jù)

4 結(jié)束語

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

［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）. ［朱文浩，魏寶剛.基于樣本的紋理合成技術(shù)綜述 ［J］.中國圖象圖形學(xué)報(bào)，2008，13 （11）：2063－2069.］

［3］XUE Feng.Research on texture synthesis from sample ［M］.Hefei：Hefei Univerity of Technology Press，2007 （in Chinese）.［薛峰.基于樣圖的紋理合成技術(shù)研究 ［M］.合肥：合肥工業(yè)大學(xué)出版社，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）.［李大錦.可控的連續(xù)多尺度紋理合成 ［J］.計(jì)算機(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）.［鄒昆，韓國強(qiáng)，李聞，等.基于Graph Cut的快速紋理合成算法 ［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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）.［陳昕，王文成.基于復(fù)用計(jì)算的大紋理實(shí)時(shí)合成 ［J］.計(jì)算機(jī)學(xué)報(bào)，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］.計(jì)算機(jī)工程與設(shè)計(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］.計(jì)算機(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ìn)方法 ［J］.計(jì)算機(jī)工程與設(shè)計(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］.計(jì)算機(jī)工程與設(shè)計(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.