李大錦
(山東師范大學(xué)傳媒學(xué)院,山東 濟(jì)南 250024)
基于樣圖的紋理合成的實(shí)質(zhì)是根據(jù)給定的一張樣本圖像,通過分析其像素顏色的統(tǒng)計(jì)規(guī)律性,重新生成一張任意大小的圖像,生成的圖像在視覺上與原樣本圖像非常相似。目前紋理合成主要是利用馬爾科夫隨機(jī)場的理論?;隈R爾科夫模型,國內(nèi)外學(xué)者已經(jīng)提出較多的紋理合成算法,這些方法基本可歸結(jié)為兩大類:基于像素點(diǎn)的紋理合成[1-3]和基于塊的紋理合成[4-6]。隨后在這些基本合成算法的基礎(chǔ)上,人們又提出了一些改進(jìn)的合成方法[7-9]。 文獻(xiàn)[7-8]提出的可并行計(jì)算的紋理合成方法,可有效地提高合成速度。為了減少基于塊的合成方法中紋理塊間的不連續(xù),熊昌鎮(zhèn)等[9]在基于塊的合成方法的基礎(chǔ)上利用不規(guī)則紋理塊來實(shí)現(xiàn)逐塊合成。Zhang等[10]基于像素的合成方法,利用基于特征的變形和融合技術(shù),實(shí)現(xiàn)了紋理圖案方向的改變和兩種紋理間的漸變。此外,人們還提出了針對某類具體應(yīng)用的紋理合成算法。Miyata等[11]提出的用于合成“鋪路”圖案的紋理合成方法以及Ashikhmin[3]的自然紋理合成算法;文獻(xiàn)[10,13]分別提出了兩種多尺度紋理合成算法,在合成過程中,可以將樣本的圖像任意縮放,形成不同尺度的紋理圖案。
Ashikhmin的自然紋理合成算法是所有基于像素點(diǎn)的紋理合成算法中較快的一種,不僅適合自然景物的合成,對于隨機(jī)性較強(qiáng)的紋理同樣適應(yīng)。它采用L型鄰域搜索匹配點(diǎn),同時將匹配點(diǎn)的搜索限制在L型鄰域產(chǎn)生的候選點(diǎn)之中,既提高了合成速度,同時使合成圖片像素間保持了良好的連續(xù)性。最近,岳曉菊等[14]也提出了一種Ashikhmin的改進(jìn)算法,將Ashikhmin算法中的像素點(diǎn)改為像素塊,雖然可有效的提高合成速度,但是卻沒有解決塊間的不連續(xù)問題。
在Ashikhmin的算法中,由L型鄰域產(chǎn)生的候選點(diǎn)有時會超越樣圖邊界,候選點(diǎn)的越界是造成結(jié)果圖像明顯產(chǎn)生塊間不連續(xù)的主要原因。在Ashikhmin的文章里沒有給出很好的解決方法,對于越過樣圖底部的候選點(diǎn),只是簡單的用一個隨機(jī)選取的有效點(diǎn)來代替。對于越過水平邊界的候選點(diǎn)Ashikhmin沒有明確指出如何解決。本文對Ashikhmin的算法進(jìn)行了改進(jìn),通過在樣圖內(nèi)部尋找邊界點(diǎn)的最佳匹配像素將越界候選點(diǎn)重新定位,有效地解決了Ashikhmin算法中紋理塊間的不連續(xù)問題。
Ashikhmin算法的合成順序是從輸出圖像的第1行開始,從左至右逐行合成每個像素。采用L型鄰域來計(jì)算匹配點(diǎn)的顏色誤差。從已合成的像素中選取和待合成像素相鄰的若干像素形成一個L型的像素鄰域,如圖1所示。
合成過程中記錄下每個已經(jīng)合成的像素在樣本圖像中的位置。對于待合成像素的L型鄰域中每個已合成的像素,根據(jù)其和待合成像素的位置偏移,在樣本圖像中可以找到一個相同位置偏移的像素點(diǎn)(圖1樣本圖像中黑色點(diǎn)),該像素點(diǎn)就是待合成像素的一個候選點(diǎn)。L型鄰域中每個像素都產(chǎn)生一個候選點(diǎn),待合成像素最終確定的采樣點(diǎn)是所有候選點(diǎn)中匹配最好的候選點(diǎn)。候選點(diǎn)的匹配計(jì)算采用顏色空間的歐氏距離作為匹配標(biāo)準(zhǔn)。顏色距離計(jì)算如式(1)。
圖1 Ashikhmin算法中候選點(diǎn)的確定
其中,N1和N2分別是用于計(jì)算顏色距離的樣本圖像和目標(biāo)圖像L型鄰域。R、G、B分別是在p點(diǎn)處像素的紅、綠、藍(lán)顏色值,下標(biāo)1、2分別代表樣本圖像和目標(biāo)圖像。
Ashikhmin的算法描述如下:
用隨機(jī)產(chǎn)生的坐標(biāo)位置采樣樣本圖像的像素填充目標(biāo)圖像,同時記錄每個像素的采樣坐標(biāo);
for( 掃描線順序掃描每個點(diǎn))
{
找出目標(biāo)圖像中當(dāng)前點(diǎn)L型鄰域內(nèi)的所有點(diǎn);
for( L型鄰域內(nèi)的每個像素點(diǎn) ){找到該像素的候選點(diǎn),插入到候選點(diǎn)列表中;}
將候選點(diǎn)列表中相同的候選點(diǎn)刪除;
for( 每個候選點(diǎn) ){計(jì)算其L型鄰域和當(dāng)前待合成像素L型鄰域的顏色誤差;}
將顏色誤差最小的候選點(diǎn)像素拷貝到當(dāng)前合成像素,并記錄其在樣本中的坐標(biāo);
}
Ashikhmin算法的合成過程實(shí)質(zhì)上是像素塊的生長過程,像素塊呈不規(guī)則狀。紋理塊從某個位置開始沿著垂直方向逐步向下生長,當(dāng)紋理塊生長到樣本圖像的底部時會產(chǎn)生無效的候選點(diǎn)。Ashikhmin給出的解決方案是:將樣圖中的像素與樣圖底部的距離坐標(biāo)規(guī)格化為[0,1]之間,規(guī)定一個標(biāo)準(zhǔn)距離d∈[0,1],然后隨機(jī)產(chǎn)生一個距離rand∈[0,1],滿足rand4﹥d;在樣圖中取該點(diǎn)對應(yīng)的候選點(diǎn)代替越界的無效候選點(diǎn),由隨機(jī)產(chǎn)生的有效候選點(diǎn)開始繼續(xù)紋理塊的生長。Ashikhmin沒有給出如何解決水平越界候選點(diǎn)的問題。一般的方法是通過將候選點(diǎn)的水平坐標(biāo)x對樣圖寬度取模運(yùn)算,循環(huán)采樣樣本圖像;或者同樣采用Ashikhmin解決垂直方向越界的方法,隨機(jī)產(chǎn)生有效候選點(diǎn)。
Ashikhmin算法合成的結(jié)果圖像塊在豎直方向上是不規(guī)則的,但在圖像塊生長到樣本圖像的底部時會產(chǎn)生明顯的水平分解線。由于樣本圖像底部和隨機(jī)產(chǎn)生的候選點(diǎn)像素沒有任何相關(guān)性,在視覺上也不能形成平滑的過度,導(dǎo)致了明顯的塊間躍變。同時由于候選點(diǎn)的隨機(jī)性還導(dǎo)致了上下兩個紋理塊之間的像素比較紊亂。
針對上述Ashikhmin算法的不足,本文對原Ashikhmin算法進(jìn)行了改進(jìn)。將樣本圖像的底部和右側(cè)邊界區(qū)域用樣圖內(nèi)部其他的像素塊代替,使合成中的圖像塊在生長到接近邊緣處時轉(zhuǎn)向樣圖內(nèi)部某個區(qū)域重新開始生長。
受文獻(xiàn)[5]“圖像縫合”思想的啟發(fā),將邊緣處一定寬度的像素塊用樣圖內(nèi)的最佳匹配像素塊來代替。取靠近樣圖邊緣的1/4樣圖高度的區(qū)域(圖2中2區(qū)域),在樣圖中尋找與之匹配的區(qū)域(圖2中的1區(qū)域),匹配誤差的計(jì)算采用式(1)的方法。匹配區(qū)域確定后,再確定兩塊區(qū)域的“縫合線”。這條縫合線將兩塊區(qū)域各劃分出兩部分(圖2中的白色線),將區(qū)域2中處于縫合線以下的部分用區(qū)域1的縫合線以下的區(qū)域像素來代替。在合成過程中當(dāng)紋理塊生長到縫合線處時,會轉(zhuǎn)向替代區(qū)域的位置,重新進(jìn)行紋理塊的生長。為了避免再生長的紋理塊很快又到達(dá)底部,在尋找匹配區(qū)域的時候,將匹配區(qū)域限制在樣本圖像上部的1/2之內(nèi)。因?yàn)樘幱诳p合線兩側(cè)的兩個像素塊的相鄰像素顏色距離差別最小,所以縫合后的圖像在視覺上不會看到明顯的分界線。
圖2 邊緣像素區(qū)域的替代
縫合線的計(jì)算確定采用最短路徑法,首先要建立一個有向無環(huán)圖(見圖3所示)。以求水平縫合線為例,有向無環(huán)圖的建立方法是:將兩塊圖像重疊合,圖3中圓圈是兩個圖像塊重疊的像素。先在重疊圖像的左右兩側(cè)建立兩個節(jié)點(diǎn),作為有向無環(huán)圖的開始和結(jié)束節(jié)點(diǎn);在圖像中每四個相鄰像素的中間也分別建立節(jié)點(diǎn)(圖3中黑色方塊);然后從左到右用弧連接這些節(jié)點(diǎn),上下每相鄰的兩個節(jié)點(diǎn)也都用一條弧相連。取弧的左右兩邊重疊像素的顏色誤差eij作為每條弧的權(quán)值。從開始點(diǎn)到結(jié)束點(diǎn)的一條最短路徑即是最佳匹配的縫合線。權(quán)值eij的計(jì)算如下:
圖3 用于計(jì)算縫合線的有向無環(huán)圖
式中,eij是像素(i,j)到像素(i,j+1)之間的顏色誤差;Eij是兩個匹配區(qū)域?qū)?yīng)點(diǎn)(i,j)處顏色的誤差;C1、C2分別是兩個匹配區(qū)域某點(diǎn)像素的顏色值,下標(biāo)i,j指對應(yīng)像素的坐標(biāo),上標(biāo)r、g、b分別指3個顏色通道。
另外需要一個用于索引樣本坐標(biāo)的索引二維數(shù)組,存放樣本中每個像素對應(yīng)的實(shí)際坐標(biāo),用匹配的區(qū)域替代邊緣區(qū)域以后,被替代邊緣區(qū)域的像素坐標(biāo)索引應(yīng)指向替代區(qū)域的坐標(biāo)。在合成過程中,從索引數(shù)組中查找像素的位置。在初始化輸出圖像時,我們不用單個像素,而是采用隨機(jī)產(chǎn)生的像素塊來初始化索引數(shù)組。像素塊的大小根據(jù)紋理特征的不同來確定。實(shí)驗(yàn)證明:對于結(jié)構(gòu)性較強(qiáng)的紋理,像素塊取基本紋理元素的1~3倍。對于一般的自然紋理,可取樣圖大小的1/8~1/4。
改進(jìn)后的算法描述如下:
用隨機(jī)產(chǎn)生的像素塊初始化坐標(biāo)索引數(shù)組。
搜索匹配區(qū)域,建立有向圖并計(jì)算最小路徑,將替代區(qū)域的坐標(biāo)填入索引數(shù)組中樣本邊緣被替代的區(qū)域。
用隨機(jī)產(chǎn)生的坐標(biāo)位置采樣樣本圖像的像素填充目標(biāo)圖像,記錄對應(yīng)索引數(shù)組中的像素坐標(biāo)
For(掃描線順序掃描每個點(diǎn))
{
找出目標(biāo)圖像中當(dāng)前點(diǎn)L型鄰域內(nèi)的所有點(diǎn);
For(L型鄰域內(nèi)的每個像素點(diǎn)){在索引數(shù)組中找到候選點(diǎn)并插入到候選點(diǎn)列表。}
將候選點(diǎn)列表中相同的候選點(diǎn)刪除;
For(每個候選點(diǎn)){計(jì)算當(dāng)前候選點(diǎn)L型鄰域和當(dāng)前待合成像素L型鄰域的顏色誤差;}將顏色誤差最小的候選點(diǎn)像素拷貝到當(dāng)前合成像素,并記錄其在樣本中的坐標(biāo);
}
圖4中的白色線是合成后的圖像中紋理塊的邊界,圖4(a)是Ashikhmin方法合成結(jié)果,圖4(b)是本文方法合成的結(jié)果??梢钥闯霰疚牡乃惴ㄔ谪Q直和水平兩個方向上都形成了不規(guī)則的像素塊邊界,避免了紊亂像素的產(chǎn)生,同時,從圖4(b)可以看到本文的方法生成的像素塊相對較大,能在更大范圍內(nèi)保持了像素的相關(guān)性。
圖5給出了本文算法和原Ashikhmin算法的合成結(jié)果的比較??梢钥闯觯疚乃惴ǖ慕Y(jié)果要明顯優(yōu)于Ashikhmin算法,尤其對于結(jié)構(gòu)性較強(qiáng)的紋理,能很好的保持紋理的結(jié)構(gòu)特征。
在算法時間效率上,本文算法比原來算法增加了尋找替代像素區(qū)域和“縫合線”的計(jì)算,但是在實(shí)際應(yīng)用中這些計(jì)算可以作為預(yù)處理階段事先處理,在合成過程中本文算法不再增加任何額外時間。
圖4 合成后的紋理塊邊界
圖5 原方法和本文方法的結(jié)果比較
本文基于自然紋理合成算法,提出了一種改進(jìn)的自然紋理合成方法,解決了原算法中候選點(diǎn)的越界問題,有效地降低了紋理塊間的明顯變化。實(shí)驗(yàn)結(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]陳 昕, 王文成. 大尺寸紋理的實(shí)時合成[J]. 軟件學(xué)報(bào), 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]. 計(jì)算機(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]. 計(jì)算機(jī)工程, 2009, 35(24): 211-212.
[14]岳曉菊, 康寶生, 閆麗君. 利用相關(guān)性原理紋理合成的改進(jìn)算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2011, 47(10):190-192.