基于K-means的快速紋理合成

李程鵬

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0　引言

在計(jì)算機(jī)圖形學(xué)中，紋理常用于三維模型的紋理貼圖，豐富三維模型的表面，提升渲染的質(zhì)量。通常用于三維模型貼圖的紋理一般來至美工的繪制或則直接通過攝影器材拍攝得到，但這些方法獲取到的紋理的尺寸大小固定。如果需要獲取大尺寸的紋理，通常有兩種方式：第一種重新繪制或拍攝得到，這種重新獲取的方法比較麻煩；第二種就是通過相關(guān)圖像處理軟件進(jìn)行處理，但處理的結(jié)果或多或少地存在模糊或重復(fù)的問題。紋理合成算法就是為了解決上述紋理尺寸大小固定的問題，通過使用紋理合成算法即可很方便地合成任意尺寸的紋理，同時也不會出現(xiàn)紋理模糊或重復(fù)的問題。

1　紋理合成

紋理合成的目標(biāo)是通過紋理樣圖合成任意尺寸大小的紋理，該合成紋理的任意局部區(qū)域都和紋理樣圖相似。下文將首先介紹紋理合成的基本算法實(shí)現(xiàn)，然后再詳細(xì)介紹紋理合成過程中需要處理的一些細(xì)節(jié)問題。

1.1　算法實(shí)現(xiàn)

給定一張基本的紋理樣圖S，并由程序動態(tài)生成一張由隨機(jī)數(shù)組成的噪聲圖R。然后根據(jù)紋理樣圖S的紋素信息，將噪聲圖R從左至右和從上至下的線性順序逐步將其所有的噪聲點(diǎn)替換成和紋理樣圖S一致的紋理像素。

圖1　左為紋理樣圖，右為合成紋理

根據(jù)馬爾科夫隨機(jī)場模型，噪聲圖R中的某一點(diǎn)P的值由其周圍像素點(diǎn)共同決定，這些像素點(diǎn)被稱為點(diǎn)P的鄰域N(P)。替換噪聲圖R中的某一點(diǎn)P的值的具體計(jì)算方式如下：首先，計(jì)算得到點(diǎn)P的鄰域N(P)，然后將N(P)和樣本紋理S中所有像素的鄰域進(jìn)行對比，計(jì)算得到與其距離最近的鄰域N(Pi)，最后將樣本紋理S中像素Pi的值賦值給噪聲圖中像素P，完成P點(diǎn)的紋理合成。不斷重復(fù)上述操作直至噪聲圖中所有的噪聲點(diǎn)都被紋理樣圖正確賦值，紋理合成具體流程如圖2所示：

圖2　紋理合成流程

圖3　不同鄰域大小的紋理合成

上述計(jì)算過程中，鄰域之間的比較方式為其鄰域間的歐式距離的平方，而不是直接使用歐氏距離。通過這種方式，在計(jì)算鄰域間的歐氏距離的時候不再進(jìn)行根號運(yùn)算，一定程度上提高鄰域間的比較速度。

1.2　鄰域

根據(jù)上文中曾提到的馬爾科夫隨機(jī)場原理，噪聲圖中某點(diǎn)P的值由其鄰域的像素點(diǎn)有直接聯(lián)系，而鄰域特指P點(diǎn)之前的鄰近的像素，和點(diǎn)P再之前或之后的鄰近區(qū)域無直接聯(lián)系。點(diǎn)P的鄰域N(P)理論上可以是任意形狀，只要保證鄰域內(nèi)的所有像素都已經(jīng)被樣本紋理賦值。文中選擇L形的形狀作為鄰域N(P)的形狀，該形狀能最大限度地保證點(diǎn)P周圍的像素和點(diǎn)P鄰近且都已經(jīng)被樣本紋理賦值。

L鄰域的大小將直接影響紋理合成的質(zhì)量，理論上鄰域的尺度越大，其決定噪聲點(diǎn)P的參考像素就越多，合成的紋理就越趨近于紋理樣圖。但是，當(dāng)鄰域的尺度達(dá)到一定程度過后，合成紋理的質(zhì)量反而會逐步下降。其原因是過多的參考像素也會帶來更多的噪聲影響。

在構(gòu)建鄰域空間時，鄰域空間中的鄰接像素可能在圖像的邊緣區(qū)域而不存在，因此需要對圖像邊界區(qū)域的鄰接像素進(jìn)行特別的處理。對于鄰接像素，選擇其圖像空間中所對應(yīng)的像素進(jìn)行替代，替換方式如圖4所示：

圖4　邊緣處理

2　K-means加速

K-means算法是一種經(jīng)典的聚類算法，采用歐式距離作為衡量類別的標(biāo)準(zhǔn)。算法的大致思想是通過簡單的迭代不斷的修正聚類中心直至超過最大迭代次數(shù)或則誤差小于某個閾值結(jié)束。

在紋理合成過程中，噪聲點(diǎn)的鄰域和樣本紋理所有像素鄰域的比較得到最近的鄰域的過程十分耗時。因此，提高鄰域與紋理樣圖中所有鄰域的比較速度是加速紋理合成的關(guān)鍵點(diǎn)。將鄰域中所有的像素依次轉(zhuǎn)換為一個高維向量，這樣鄰域之間的對比隨機(jī)即可轉(zhuǎn)換為高維向量之間的對比。直接通過K-means算法對紋理樣圖的所有鄰域進(jìn)行聚類，從而構(gòu)建有效的加速結(jié)構(gòu)提高紋理合成速度。將鄰域轉(zhuǎn)換為向量的過程如圖5所示。

圖5　鄰域轉(zhuǎn)向量

使用K-means聚類算法創(chuàng)建紋理合成加速結(jié)構(gòu)流程如下：首先，計(jì)算得到紋理樣圖中所有像素的鄰域，并將其轉(zhuǎn)化為由像素組成的向量。然后再把這些向量通過K-means算法聚類成K類，每一類的子向量集都對應(yīng)一個聚類中心。

K-means加速結(jié)構(gòu)創(chuàng)建完成后，即可通過加速結(jié)構(gòu)進(jìn)行紋理合成。在合成噪聲圖中某一點(diǎn)P的紋理時，計(jì)算得到P點(diǎn)的鄰域N(P)，并將其轉(zhuǎn)換為向量V(P)。再將V(P)和加速結(jié)構(gòu)中的所有聚類中心進(jìn)行對比得到距離V(P)最近的聚類中心Ki。最后，再在類Ki中找到距離V(P)最近的向量，并將其所對應(yīng)的像素賦值給噪聲點(diǎn)P。從左至右和從上至下的順序重復(fù)上述流程直至噪聲圖中所有的噪聲點(diǎn)都被正確賦值，紋理合成完成。

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

表1中所有的實(shí)驗(yàn)數(shù)據(jù)使用Intel Core i3-4160處理器及大小為15的鄰域測試得到，從表中可以得到通過使用K-means算法極大的提高了紋理合成的效率。

4　結(jié)語

基于紋理樣圖和馬爾科夫隨機(jī)場模型的紋理合成算法可以合成質(zhì)量較高的紋理，但該方法的合成效率卻十分低下，針對該問題提出了使用K-means聚類算法來加速噪聲點(diǎn)和紋理樣圖的比較過程，極大的提高了紋理合成的效率。但是，基于K-means的快速紋理合成還有以下幾個問題有待解決：首先，合成的紋理還存在較多的噪聲點(diǎn)，影響合成的質(zhì)量；其次，K-means算法雖然能有效的提高紋理合成的效率，但是由于該算法本生的缺陷，在計(jì)算之前必須指定聚類的數(shù)量K。未來將在這些方面進(jìn)一步進(jìn)行深入的研究。

圖6　使用K-means加速結(jié)構(gòu)合成紋理

3　.2紋理合成速度對比

表1　

參考文獻(xiàn)：

[1]Hartigan J A,Wong M A.A K-means Clustering Algorithm[J].Applied Statistics,1979,28(1):100-108.

[2]Krishna K,Murty M N.Genetic K-means Algorithm[J].IEEE Transactions on Systems Man&Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man&Cybernetics Society,1999,29(3):433.

[3]Bradley P S,Fayyad U M.Refining Initial Points for K-Means Clustering[C].Fifteenth International Conference on Machine Learning.Morgan Kaufmann Publishers Inc.1998:91-99.

[4]Chi H L.Texture synthesis[J].Cwi Quarterly,2007,volume 90(4):506-506(1).

[5]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.