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

李程鵬

（四川大學計算機學院，成都 610065）

0　引言

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

1　紋理合成

紋理合成的目標是通過紋理樣圖合成任意尺寸大小的紋理，該合成紋理的任意局部區域都和紋理樣圖相似。下文將首先介紹紋理合成的基本算法實現，然后再詳細介紹紋理合成過程中需要處理的一些細節問題。

1.1　算法實現

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

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

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

圖2　紋理合成流程

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

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

1.2　鄰域

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

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

在構建鄰域空間時，鄰域空間中的鄰接像素可能在圖像的邊緣區域而不存在，因此需要對圖像邊界區域的鄰接像素進行特別的處理。對于鄰接像素，選擇其圖像空間中所對應的像素進行替代，替換方式如圖4所示：

圖4　邊緣處理

2　K-means加速

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

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

圖5　鄰域轉向量

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

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

3　實驗結果

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

4　結語

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

圖6　使用K-means加速結構合成紋理

3　.2紋理合成速度對比

表1　

參考文獻：

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