基于VM特征值融合的模型检索算法研究

尚福华，于志东，周亚东，解红涛

(东北石油大学计算机与信息技术学院，黑龙江大庆163318)

随着计算机科学的不断进步，3D技术逐步发展起来.三维模型作为继一维的文本信息、二维的图像信息之后的又一虚拟媒体信息，增加了信息量和信息的复杂度，同时也加大了人们对于信息检索工具的依赖，而这些检索工具的复杂性和规模性也日益增强.伴随着三维建模软件和三维扫描技术的不断成熟，三维模型的生成越来越容易.同时电子娱乐、工业设计、虚拟现实等领域也积累了越来越多的三维模型，这些三维模型通过互联网广泛传播，形成了许多三维模型库.在这些模型库中一部分是针对特定领域的，比如说美国国家癌症研究所的NCIDIS3D模型库，该三维模型库包含了40万个三维模型;美国MDL的化学品三维模型库ACD－3DMDL有30万个模型;美国普林斯顿大学和通用模型库有6万个模型[1－2]，是规模比较大的模型库.

随着模型数量的不断激增，现有搜索引擎已经难以有效地进行三维模型的检索.十分需要一种三维模型检索方法，基于内容(content－based 3D model retrieval)的三维模型检索方式应运而生.该技术不仅可用在三维数据库中浏览和检索三维场景或三维模型[3]，也可用于三维物体形状分析和三维物体的自动识别与分类[4].近几年来无数的学者对于三维模型的检索方式进行了许多的创新和改进，但是大多都是针对普林斯顿大学的模型库为实验数据，缺乏实际中应用到的小型、专业模型库作为实验的模型库.针对大庆油田钻井模型库模型数量相对较少、相似性高等特点，本文提出了通过特征融合技术将法向面和视图特征融合为一体，增强对模型的描述能力，从而实现快速而又准确的进行三维模型检索.实验表明该方法在小型专业模型库上能够提高模型检索的速度和准确度.小.

1 VM特征融合

特征融合(Feature Combination)由德国CCCC小组提出.研究表明基于多特征融合的模型检索方式，比使用单个模型特征的检索效果要好很多[5].因此，很多研究人员一方面在寻找高效的特征提取方式进行高效的模型检索，一方面在考虑融合现有的特征提取方法[6].这两方面互为补充，在没有找到更好的特征提取方式之前，将两者结合进行三维模型检索的方式仍然是一个很好的选择.

特征融合的过程主要分为3步:首先模型标准化，然后对模型分别抽取各个指定的特征向量，最后融合特征值.

VM即View(视图)和Mesh(面)大写首字母.当提取面特征向量时，提取的是面的朝向和面在模型各个朝向上面的分布密集程度两个特征.对于面的特征提取方式，由于模型本身数据存储方式没有将面的上述两个特征作为一个属性存放，而是通过法线进行表现，其实这两个属性中面的朝向就是法线的特征表现，不同朝向上面的密集程度是面的属性.为了方便计算表达，本文将这两个特征属性作为一个特征M(mesh，面)来表示.

1.1 模型标准化

基于内容的模型特征提取大多数是需要预处理将模型标准化的，如图1中两个相似的杯子模型，却有着不同的坐标轴;可能还有的情况是有相似外形的模型即便有着相一致的坐标轴但是大小却相差很多;或者在世界坐标系中所处位置也不相同，如图2所示.这些情况下需要进行标准化处理，使相同的或者相近的模型具有相同的大小和朝向，使得特征提取受模型大小、朝向等影响因素降到最

1.2 抽取特征向量

模型在标准化之后，就可以进行特征提取了.为了能够全面的表达模型的特征、性质，提取的特征之间需要互补，最大化的表达模型的属性.

在对三维模型进行特征抽取前，需要对模型进行规范化，以保证模型在平移、旋转、缩放的情况下，保持本身特征的不变性.首先计算模型的主轴，将模型的质心放在坐标系原点处，采用PCA(Principal Component Analysis)或CPCA(Continuous PCA)的方法确定主轴，再将三维模型表面的各个点到坐标系原点距离的平均值调整为“1”，使三维模型具有相同的大小.最后，对该模型分别提取基于视图、法向量、面的特征向量.

1.3 融合特征值

对模型抽取基于视图(View)、法向量(Normal vector)和面(Mesh)的特征向量后，融合抽取出来的特征值.其中法向和面的特征紧密相连，可以将两者归结为面的特征.特征值的构成过程中，并不是将选择的几个特征值简单的连接在一起就形成特征值的，而是通过对各个特征值识别能力的分析来分配在特征值中三种特征值分别占多少维.

2 VM特征值计算

计算三维模型基于视图的特征值方法为:通过模型的外包围正方体，获取在X、Y、Z三个轴向上的投影，获取轮廓图像，对于每个面进行采样的深度线序列.

计算三维模型基于法向面的特征值方法为:提取模型基于法向和面的特征向量，通过从模型表面中每个三角面得出的法向量与外包围十二面体相交的点，判定在每个外包围二十面体索引面的交点所在的法线和交点数，进而判断不同朝向上模型面的分布密集程度.即m=(m1……mN)，其中 m1+……+mN=M.

对三维模型进行规范化之后，提取出基于视图和法向面的特征，再通过这两种特征向量融合成模型的VM特征值c=(v|n).特征值维数为C=V+M.VM特征值的形成不是简单的把视图和法向面两种特征值累计在一起，而是根据不同特征值对于模型的识别能力，决定最后哪一种特征值在VM特征值中占有多少比例(或者说是多少维).由于基于视图的特征值要比基于法线的有效，因此基于法线的特征值的维数就要比基于视图的特征值要少，也就是M＜V.在特征值的选取过程中，每一种特征值都是使用固定维数的，本文基于视图的特征提取采用了180维，也就是每个视图上对比60条深度序列线，每条深度线有60个采样点.基于法向面的特征提取使用了80维(采用了外包围球面数为80的正多面体)，所以最后的VM融合特征值为180+80=260维特征值.对于这种提取维数的合理性通过对比实验加以证明.

3 VM对比实验及分析

实验中使用的三维模型来自大庆油田钻井三公司钻井仿真三维模型库，该库为小型、专业模型库，总计四个类别共1 023个模型，每个模型包含着大量的点和面，模型的数据格式为off.采用该模型库中所有模型为试验样本.对该模型库使用不同的三维模型特征提取方法，对比基于视图的和基于法向面检索方式的检索效果.最后使用基于特征融合检索方法进行实验对比，使用Recall/Precision(查全/查准率)表现检索对比效果.经过多次输入实例模型(牙轮转头、大绞车、固井胶塞、大钩、转盘等)进行检索.

3.1 确定特征值之间比例

对于确定两个特征维数值总量和两者之间比例，先通过实验确定维数总和显然是不合适的，因为无论在何种比例下维数总和越大检索效果越好，不同比例下最佳维数值也不一样.两种特征提取方式融合后在不同的特征维数比例下其检索性能曲线是不一样的.但是在两者维数总和一定的情形下，检索效果并不随着两者比例值的增加而提高，而是有个最大值，这个最大值就是我们要寻找的.

通过实验对比基于视图的模型检索方式和基于法向面的检索方式，可知基于视图的模型检索方式检索效果优于基于法向面的检索方式的检索效果，因此基于视图的特征提取方式在特征融合中所占的比例就应该大一些.所以实验数据中只有一个比例是小于1的，在实验中两种特征值VM(视图，法向面)比例从0.5增加到3，如图3所示.结果表明在两者比例为9∶4的时候检索效果最好.

图3 不同视图和法线比例的检索效果对比

对于VM各自维数最佳组合是需要经过不断试验进行验证的，也会随着模型库的变动而发生变化，所以只能通过不断试验和不断增进对模型库本身模型信息的了解，才能够根据经验及实验得到一个比较合适的比例，也可以在检索界面设置两者维数的比例，根据检索结果不断地进行修改，使其趋近一个合理的比率.

3.2 确定特征值维数总量

在确定VM比例为9∶4的情况下进行试验求得维数最佳数量总和.实验是通过不断增加维数来确定最合适数量的.从图4中可以看出当VM维数各自增加到180、80后，再增加的时候检索效果已经相差无几，所以为保证检索的快速性，这里采用了V=180，M=80的260的维数总和.

图4 不同特征数量检索效果对比

通过不断进行实例模型的检索可以绘制出如图5所示的检索性能曲线.根据该曲线可以估计两者比例和两者各自维数值.由图5看出，随着每一条检索曲线维数不断的增加，其检索性能显示急剧增加后是趋于平稳，无论怎样增加也达不到100%.因此可以在斜度为30°左右的地方进行维数的确定.而基于特征融合的检索方式实质上就是将两种检索方式附加到一起，但是基于特征融合的检索方式的最佳检索状态，并不是简单的将上述两者最佳状态时的组合简单附加到一起.如果单一地把两者维数组合融合在一起，基于特征融合的检索方式肯定是比任何一种检索方式效果都要好.但是只是简单的将两者附加到一起会出现叠加上的浪费，如果对其中一种检索方式的维数大幅度减少，会发现检索性能只会有微弱的降低，这样换来的检索时间的缩短却是十分有意义的.

图5 检索性能曲线

3.3 检索效果对比

将基于特征融合的检索方式和基于三视图的、基于法向面的检索方式进行对比(PR曲线和检索时间进行对比).

1)PR曲线对比

基于特征融合的检索方式与基于三视图的、基于法向面的检索方式的检索效果对比，结果如图6所示.其中基于特征融合的检索方式PR曲线整体偏于右上方，其次为基于视图的检索方式，最后是基于法向面的检索方式.融合了基于视图的和法向面的特征提取方式的特征融合检索方式，明显要好于前两种检索方式.

图6 检索效果对比

2)检索时间对比

检索时间为生成对比序列时间和匹配时间，由于实验使用多次检索进行对比，所以采用的是平均时间.在检索时间上基于特征融合的检索方式由于使用了两种对比序列生成方式，也就耗费了相对多的序列对比时间，如表1所示.根据表中所示的检索时间对比，可以看出基于特征融合的检索时间处于基于三视图检索方式和基于法向面检索方式之间.

表1 检索时间对比

4 结语

通过以上实验可以看出，对于一些专业性较强的小型三维模型库，基于特征融合的模型检索效果要好于基于三视图的和基于法向面的模型检索方式，虽然基于特征融合的检索方式相对来说耗费了一些时间，但是相对于其优秀的检索效果，这些时间的耗费是可以忽略的.因此，该模型检索方式对于一些专业性较强的小型三维模型库，在模型检索的准确度和效率上具有很大的优势.

[1] MOUSTAKAS K.Masterpiece:physical interaction and 3D content－ based search in VR applications[J].IEEE MultiMedia，2006，13(3):92 －100.

[2] 郭 竞，冯 筠，叶豪盛.相对角度直方图聚类在3维模型检索中的应用[J].中国图象图形学报，2010(11):67－68.

[3] 高 岩，陈敏刚，王长波.二维动画关键帧的层次约束插值算法[C]//第十五届全国图象图形学学术会议论文集，2010:678－680.

[4] 申 伟，苗振江，万丽莉.三维模型检索和逼真显示功能在可视媒体平台的实现[C]//第18届全国多媒体学术会议(NCMT2009)，2009:345－346.

[5] 汤 进，陈展展，罗 斌.基于复杂网络和最优子序列双射的形状描述与匹配[J].电子学报，2011(8):56－57.

[6] ATMOSUKARTO I.Feature Feature Combination and Relevance Feedback for 3D Model Retrieval[C]//Proceedings of the 11th International Multimedia Modeling Conference，[S.l.]: [s.n.]，2005:334－339.