摘 要：为提高三维模型的检索性能，将聚类分析用于特征描述符的提取以及模型间相似性关系划分等方面，能够对三维模型进行较为合理的分类，对较大规模三维模型数据库的索引和组织进行完善，提高三维模型检索效率。针对当前主流的基于聚类的三维模型检索算法进行分析，比较几种聚类算法的优势与不足，在其基础上进行改进，并继续应用于三维模型的检索中。
关键词：三维模型检索； 聚类； 特征描述符； K-Means

随着多媒体技术和虚拟现实等技术的不断提高，三维模型在医学、机械工程、计算机辅助设计(CAD)和娱乐等众多领域都有广泛应用，并在高度关注中不断发展。
描述三维模型需要的信息量庞大，形成数据库时模型间形状和其他性质的相似性关系复杂，使得合理地组织三维模型数据库非常困难。同时，为了充分利用已有的模型资源，迅速找到需要的三维模型，对三维模型数据库的构建和三维模型的检索都有极高的要求。
1 三维模型检索
对于庞大、复杂的三维模型数据库，三维模型检索的目的是要快速准确地搜索出所需模型。在此检索过程中，模型特征的选取以及相似度的确定就显得尤为重要。一般来说，一个完整的模型检索系统包括以下几个部分：
(1)特征描述符提取。在计算机中存储和显示三维模型时，往往只记录模型的顶点坐标、拓扑连接等几何属性以及顶点颜色、纹理等外观属性，但这些在模型匹配计算中不仅数据量大，而且可能会随模型形变等因素改变，因此效率和准确性都不高。特征描述符SD(Shape Descriptor)是根据模型基本点、线、面特点计算出的特征，能够尽量表达模型信息，容易被计算机应用。因此,如何提取更好的特征描述符成为三维模型检索中首先要解决的问题。一个理想的特征描述符应具备一些特点[1]：易于表达和计算；不占用太多的存储空间；适合进行相似性匹配；具有几何不变性，即对模型的平移、旋转和缩放等具有不变性；具有拓扑不变性，即当相同模型有多个拓扑表示时，SD应是稳定的；SD对模型的绝大多数处理(如子分、模型简化、噪声增减和变形等)是鲁棒的；SD必须具有唯一性，即不同类型的模型对应的特征表示应该不相同。
(2)特征匹配。特征匹配的目的是得到模型间的相似程度，其匹配结果作为输出检索结果的依据。选取合适的算法，对提取的特征描述符进行相似性度量，也是一个重要的问题。
(3)模型分类。三维模型资源庞大，需要建立一个分类数据库以便提高模型查找效率，该分类数据库必须适合高级语义描述。近年来的资料表明，将聚类分析用于对模型的分类，能够提高检索速度、查全率和查准率。
(4)搜索方法的研究。有了已分类的模型数据库作基础，好的搜索方法则会使三维模型检索更加高效。
(5)查询接口的设计。一个成熟的三维模型检索系统应具有良好的交互性能，拥有友好的界面，方便用户进行查询。
2 基于聚类分析的三维模型检索算法
聚类分析可以在没有任何先验知识的情况下对三维模型检索过程进行处理，如对特征描述符聚类或是对模型间相似性关系聚类，最终达到将相似性高的模型聚为一簇(一组)，即对三维模型进行高效分类，提高三维模型检索速度和准确性。
2.1 基于K-Means和Mean Shift的三维模型检索算法
基于K-Means和Mean Shift算法的三维模型检索算法[2]是将聚类分析运用于模型对称特性的提取上，将得到的模型对称信息作为模型特征描述符。
K-Means算法是一种基于划分的聚类方法，该算法是一种经典聚类算法，后续的很多基于划分的方法都是在其基础上进行的改进。算法的具体过程如下：
(1)选择k值，确定分类数目，即将目标对象分为k类。
(2)在目标对象中随机选取k个初始聚类中心。初始中心的选取很重要，不仅决定了以后的迭代次数，也影响着分类的准确性。
(3)计算所有其他数据与聚类中心的距离，将其归入离它最近的聚类中心所属的类别。
(4)计算各个类中数据的平均值，以此作为此类的中心值。
(5)当每个分类的中心值收敛时，停止聚类；否则，重复步骤(3)~(5)。
Mean Shift算法又称均值漂移算法,是一种基于密度的聚类方法。该方法通过反复迭代搜索数据集中数据点最密集的区间，聚类的中点沿着数据点密度增加的方向“漂移”到局部密度极大点。Mean Shift方法不需要预先指定数据集的分类个数，它是根据数据集中数据分布的密度对数据进行分类的，通过设定阈值b来控制最终得到的分类数目，使之处在一定范围之内。
根据参考文献[2]中所提到的方法，算法的实现过程如下：
(1)数据样本准备。获取模型表面信息，包括顶点信息、面片信息、计算中心点以及三角面片面积等，并进行模型标准化处理，使之位于标准坐标系内。
(2)特征选择。对三维模型表面进行采样，利用随机采样点产生算法在模型表面均匀采样,得到N个采样点。
(3)特征提取。计算每两个采样点之间的对称平面，得到N×(N-1)/2个对称平面组成的集合P。每个平面使用4个数据表示，包括原点到平面的距离以及平面单位法向量的3个分量。
(4)聚类。在该算法中，聚类分析用在对特征描述符的进一步提取上。分别使用K-Means和Mean Shift两种聚类算法对集合P中的数据进行聚类，得到模型的堆成平面P′。用K-Means算法获得的P′是一个K行4列的矩阵。而对于Mean Shift算法，由于无法事先确定对称平面个数，因此获得的P′是一个任意行4列的矩阵。这就是最终得到的模型的特征描述符。
(5)分组。模型分类的方式很多，仍旧可以选用聚类方法。但这里所得到的特征描述符已经是一个低维数据，直接使用距离算法简单易行。采用欧几里得距离计算2个模型特征矩阵之间的距离，表示它们之间的相似程度。
参考文献[2]中的实验结果表明，基于K-Means和Mean Shift算法的三维模型检索算法的查全率和查准率比传统算法有显著提高。因此，将聚类算法用在对特征描述符的处理上，是一种切实可行的聚类检索算法。
2.2 基于人工免疫聚类的三维模型检索算法
基于人工免疫聚类的三维模型检索算法同样是将聚类分析运用于模型对称特性的提取上，将得到的模型对称信息作为模型特征描述符。但不同的是，采用人工免疫和K-Means混合算法进行聚类分析，提取特征描述符，避免了K-Means算法对初始聚类中心极其敏感的不足，增强检索稳定性。
生物免疫系统中的克隆选择原理[3]描述了免疫系统对抗原激励做出免疫响应的基本特性。在基于克隆选择原理的免疫算法中，抗原对应于问题的目标函数，抗体对应于目标函数的优化解。首先根据抗体的适应值对解进行评价和选择，然后通过记忆细胞保留局部最优解以保持解的多样性，再用类似于抗体的亲和度来逐步改善优化过程，最终得到问题的全局最优解。这种算法提高局部解空间的搜索效率，并能避免局部最优解的干扰。
将人工免疫和K-Means混合算法用于三维模型检索中，其方法与2.1节中对模型表面随机采样、提取特征平面一样，得到一个对称平面组成的集合P。2.1节中将对称平面P的处理运用了K-Means和Mean Shift两种聚类算法，而在本试验中，将采取人工免疫和K-Means混合算法得到最终的模型特征描述符。
具体聚类过程如下：
(1)选择k值，确定分类数目，即将目标对象分为k类。
(2)产生k个抗体。从P中(假设P中包含N个对称平面)随机抽取k个元素作为初始抗体，即初始第0次迭代的聚类中心。
(3)抗体分组。采用欧几里得距离作为测量指标，根据N个元素与k个聚类中心间的距离，将其划分到最近的簇。
(4)计算每一组包含的元素个数c，对该组的聚类中心克隆c个副本，对这c个克隆抗体进行变异，变异速率和亲和力相关，分别计算这c个克隆抗体中的每一个和c的抗原的亲和力之和，选出亲和力最大的抗体作为该次迭代的最佳抗体，即下次迭代的聚类中心。
(5)如果抗体（即聚类中心）满足最优条件，则终止聚类，否则，反复执行步骤(3)~(5)继续迭代。
至此就完成了对初始对称平面集合P的聚类，得到模型的对称平面集合P′(P′是一个k行4列的矩阵)，以此作为该模型的特征描述符,最后采用距离函数度量模型间的相似程度。
本算法利用人工免疫和K-Means混合算法对三维模型表面任意两个采样点的对称平面数据集进行处理，得到更加优化的对称平面矩阵作为特征描述符。参考文献[3]中的实验结果表明，该算法比单纯使用K-Means算法进行检索的效率更高。
2.3 基于FCM算法的三维模型检索算法
形状分布算法(Shape Distribution)是一种简单有效的三维物体相似性度量算法。其主要思想是测量模型表面随机采样点之间的几何距离，将其概率分布绘制成直方图，作为模型间相似度比较的基础。其主要步骤为：首先将模型信息输入，提取特征点，即进行随机采样；再计算采样点之间的距离；最后绘制成直方图，这个直方图也就是该模型的特征描述符。
模糊均值聚类(FCM)算法是K-Means算法的改进。K-Means算法能对大型数据进行高效分类，但通常会在获得一个局部最优值时终止，其性能依赖于聚类中心的初始位置。解决的办法可以是利用其他算法先求出好的初始聚类中心，也可以是每次用不同的初始聚类中心计算多次求最好的结果。而FCM算法把N个向量分成C个模糊组，并求每组的聚类中心， 这样就可使非相似性指标[4]的价值函数达到最小。K-Means算法是一种硬聚类算法，把每个样本严格地划分到某一类中，但实际的模型对象不具有严格的所属群组划分特性。而FCM算法采用模糊划分，用0~1间的隶属度来确定其所属各个类群的程度，它是一种软划分，尤其对于模型分割效果很理想。
根据参考文献[5]中所提到的方法，具体检索算法的实现过程如下：
(1)数据样本准备，对模型进行特征标准化。
(2)特征提取。利用随机采样算法对模型表面进行随机点的选取，统计采样点之间的距离信息，生成模型的形状分布直方图。该直方图就是该模型的特征描述符。
(3)特征匹配。利用FCM算法对模型的直方图进行模糊聚类划分。将模型划分为若干类，确定初始聚类中心，并开始迭代计算目标函数。当目标函数最小时，聚类结束。
(4)分组。利用聚类进行相似性度量后，即完成了模型较好的分类。当进行检索时，只需输出所有这一类模型作为检索结果即可。
参考文献[5]中的实验结果表明，单纯采用形状分布算法，即直接使用距离函数进行相似性度量的检索精度比较低。而本实验采用聚类分析方法进行相似性度量，能够克服距离函数的不足，提高查全率和查准率。
上述几种基于聚类分析的三维模型检索算法，分别将K-Means算法或其改进算法应用于三维模型的特征提取和特征匹配过程中。实验结果表明，上述算法增强了特征描述符的鲁棒性，减少了对于模型几何形变和边缘值的影响，抗干扰能力强，检索结果查全率和查准率都有显著提高。
目前的三维模型检索系统检索效率和效果都不是很理想，各种研究中不断对特征描述符的提取和特征匹配方法进行改进。聚类分析技术具有独特的优点，在图像领域也有着很好的应用。将聚类分析运用于基于内容的三维模型检索是一个新的思路，能够提高检索效率，具有广阔的应用前景。
参考文献
[1] 崔晨旸,石教英.三维模型检索中的特征提取技术综述[J].计算机辅助设计与图形学学报，2004，16(7):882-889.
[2] 徐鹏捷,叶志伟,史川.基于聚类的三维模型检索算法[J].现代计算机,2009(10):71-74.
[3] 吕洋,刘平,唐奇峰.一种基于人工免疫聚类的三维模型检索算法[J].现代计算机,2011(2):57-59.
[4] 刘金春,蒋先刚,詹学峰.均值聚类在三维重构图像预处 理中的应用[J].微计算机信息,2007,24(5-3):303-305.
[5] 景晖,黄美发,钟艳如.基于模糊C均值聚类算法的三维模型检索[C].中国仪器仪表学会第九届青年学术会议,