基于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.