权重自适应的多特征组合三维工程模型检索算法

刘 研，张吉庆，张旭堂

（1.哈尔滨工业大学 理学院，黑龙江 哈尔滨150001；2.中国国际工程咨询公司，北京100048；3.哈尔滨工业大学 机电学院，黑龙江 哈尔滨150001）

0 引 言

合理地重用三维模型有助于企业提高新产品开发速度，提升竞争力［1］，因此设计人员迫切需要一种有效的三维模型检索方法，快速、准确地从模型库中找到与检索模型相似的三维模型。基于文本关键字的检索方法被最先用来查找相似模型。这种方法通过在模型标注信息和用户输入的关键字之间进行匹配来实现检索，这种方法存在以下几方面缺陷：①有限的人力无法做到对所有模型进行标注；②不同的人对同一模型的标注可能是不同的，模型的标注信息随着时间的推移可能发生变化；③关键字不准确时无法检索到相似模型。随着研究的深入，基于文本关键字的检索方法被基于模型内容特征的检索方法淘汰。基于内容的检索方法核心思想是通过三维模型的内容特征来表征三维模型，将三维模型转化为特征空间中的特征向量，通过计算特征向量之间的距离来判断对应模型之间的相似度。基于内容的检索利用模型自身携带的信息，检索性能优于文本关键字方式，逐渐成为模型检索问题的研究重点［2－7］。Osada等［8］提出了一种适合任意三维模型的形状描述计算方法。该方法通过采样确定某种形状函数在模型上的分布情况，通过形状分布对模型进行描述。Osada提出了5种形状函数，如图1所示，实验显示在5种形状函数中，D2的检索效果最好。

图1 Osada提出的5种形状函数［9］

蒋立军等［9］提出一种基于网格模型面积分布的检索算法。该算法通过对网格模型各顶点进行分析建立模型的面积分布序列。为了实现相似度计算对面积分布序列的归一化操作和傅立叶变换，两个模型之间的相似度等于两个分布序列的L2距离。

侯鑫等［10］提出了一种与计算机辅助设计系统无关的基于网格特征临界点的三维工程模型检索算法。该算法根据Morse理论，采用网格顶点处的离散平均曲率作为光滑实值函数，计算网格特征临界点，采用两临界点之间的测地线距离和顶点法矢夹角余弦值作为联合形状函数，按照极大值点和鞍点，分别计算同类临界点间的联合形状函数得到形状分布，从而将模型的比较映射为形状分布矩阵的比较。通过在ESB库上的验证，算法明显提高了基于图形分布检索算法的有效性。

基于内容的检索算法在检索性能上有较大提升，但是也存在一些问题：①单一特征对模型的描述能力有限。文献 ［11］的实验结果表明，不同的特征具有各自的优缺点，不存在适用于所有模型的特征。所以，使用单一特征很难在所有模型类别中取得满意的检索效果；② “语义鸿沟”问题［12］。人对模型相似性的判断除了模型内容，还结合了模型视觉特征和语义信息，并以语义信息为重。基于特征的检索算法完全依赖模型底层特征来计算模型的相似性，并未考虑到模型的语义信息，而模型的底层特征和语义之间不存在直接关系，所以模型内容的相似不代表语义的相似。为了解决“语义鸿沟”问题，有些研究人员将相关反馈技术应用到了三维模型检索问题上［13］。在用户的反馈信息的帮助下，检索算法可以更加准确地捕捉到用户的检索意图。

本文提出三维工程模型检索算法针对上述两方面缺陷做出了如下改进：①通过多个内容特征的组合增强算法的检索能力；②根据用户的反馈信息获取用户的检索需求，通过粒子群算法优化动态选择每个特征算子在相似性计算过程中的权重，使得检索结果更加靠近用户的检索需求，在一定程度上缩小高层语义与模型底层特征信息之间的差距。

1 算法说明

1.1 相似度计算

用Q 表示检索模型，用Oi表示模型库中的任意一个模型。用F 来表示选用的特征算子集合，单个特征算子fi用表示，S（Ofii）表示在使用fi的情况下，Oi和Q 之间的相似度。其中wi表示特征算子fi对应的权重。用S（Oi）表示Oi和Q 之间的综合相似距离，S（Oi）是由S（Ofii）线性组合得到的，S（Oi）的计算公式见式 （1）S（Oi）越小说明Oi和Q 越 相 似

1.2 特征算子权重动态更新

1.2.1 粒子群算优化法

粒子群优化算法 （particle swarm optimization，PSO）源于对鸟群捕食行为的研究，是近年来发展起来的一种进化算法［14］。PSO 求解优化问题时首先随机生成若干个粒子（particle），每个粒子对应搜索空间中的一个解。每个粒子具备位置和速度两个属性，由适应度函数决定粒子对待优化问题的优劣程度。粒子的初始状态随机确定后，算法进入迭代求解过程。在迭代过程中，粒子利用两个极值来更新自己，一个称为pbest（当前粒子在进化过程中出现的最优位置），一个称为gbest （整个种群在进化过程中出现的最优位置）。式 （2）、式 （3）为粒子的速度与位置更新公式。迭代终止条件为预先确定的最大迭代次数或者为对优化结果的精度要求。假设粒子在D 维空间搜索问题最优解，第i个粒子的位置信息可表示为：Xi＝（xi1，xi2，…，xiD），速度信息 可 表 示 为：Vi＝（Vi1，Vi2，…，ViD）。式 （2）和 式（3）为PSO 在第t＋1次迭代时的粒子速度和位置更新公式，式 （2）中的pbesti表示第i个粒子在第t 次迭代时的个体极值点，gbest表示粒子种群当前的全局极值点，w 为惯性权重，c1和c2为学习因子，r1和r2为0到1之间的随机数。式 （4）为PSO 的适应度函数，适应度函数以粒子的位置信息为输入，fitnessi表示第i 个粒子对待优化问题的优劣程度。每个粒子完成一次迭代后根据适应度大小更新自己的局部极值点 （pbest），粒子种群完成一次迭代后根据适应度大小更新全局极值点 （gbest）

1.2.2 权重优化过程

初次检索结束后，将每个特征算子前K 个检索结果返回给用户供其标记，所以供用户标记的模型总数为×K 个。用户可将返回的模型标记为 “相关”、 “不相关”和“一般”3类。用R （relevant）来表示被用户标记为 “相关”的模型集合，用R（Ofii）来表示特征算子fi的前K 个相似模型中属于被标记为“相似”的模型；用IR （irrelevant）来表示被标记为“不相关”的模型集合，用IR（Ofii）表示不相关模型中被fi检索到的模型；用M （middle）来表示被标记为“一般”的模型集合，用M（Ofii）表示 “一般”模型中被fi检索到的模型。以上信息确认完毕后，使用粒子群算法优化fi的权重，权重优化过程中循序以下几条规则：

R（Qfii）中的模型个数越多fi的权重越大；

IR（Qfii）中的模型个数越多fi的权重越小；

如果特征算子的相关模型个数一样多，则考察其相关模型的排名之和，和越小fi的权重越大。

根据上述几条原则构建粒子适应度计算公式，见式（5）。其中Fitness（pi）表示粒子第i个粒子的适应度，其值越大表明粒子状态越优化

1.3 算法流程

权重更新完毕后，使用式 （1）重新计算模型Oi和Q之间的综合相似度。算法将按照综合相似度对模型库中的模型进行排序，并返回前F ×K 个模型供用户标注，用户标记完毕后开始下一轮权重优化，照此循环直至用户主动结束检索过程。算法流程如下文所述，流程如图2所示。

（1）初始化所有特征算子的权重；

（2）分别使用各个特征算子计算相似度R（Ofii）；

（4）用户对模型进行相关性标注；

（5）PSO 更新所有特征描算子的权重；

（6）按照式 （1）计算综合相似度S（Oi）；

（7）根据S（Oi）对数据库中的所有模型排序，返回前×K 个模型供用户标注；

（8）如果用户对结果满意，结束；否则返回第（4）步，开始下一轮反馈。

图2 基于相关反馈的多特征融合算法流程

2 实验讨论

以Visual C＋＋6.0 为集成开发环境，结合Matlab R2011b实现了本文提出的算法。在实验环节实现的算法联合了上文中介绍的3种特征算子，分别是：D2［8］，临界特征点［10］和测地线连接图［15］。PSO 的参数选择如下：粒子 规模50，惯性权重w＝1，学习因子c1＝c2＝1，迭代50次。使用普渡大学建立的工程标准模型库ESB （engineering shape benchmark）对本文算法进行了验证。ESB 库中包含866个模型，被分为3个大类，45个小类［16］。表1为部分检索实验的前10个检索结果，3个检索模型分别来自ESB库的3个大类，表格中图片下方文字为模型名称。

表1 部分检索实验结果

图3为参与组合的3种检索算法以及本文算法在ESB库上的平均查全率－查准率曲线。由图3可知，本文算法的PR 曲线优于参与的组合的3种检索算法。

图3 查全率－查准率曲线

3 结束语

针对三维模型检索领域存在的 “语义鸿沟”和单特征检索能力有限的问题，提出一种基于相关反馈和多特征组合的三维工程网格模型检索算法。该算法以网格模型为对象，通过多特征联合增强算法的检索能力；在用户相关反馈信息的指导下使用PSO 算法动态更新各特征算子在相似度计算过程中的权重，提高了检索结果的语义相关性。实验结果表明，本文提出的算法可有效提高检索效率。

在未来的研究中可从以下几方面对算法进行改进：①选取更优的特征算子参与组合以便提高组合算法的检索能力；②改善粒子群算法适应度函数，更加合理的适应度函数有助于找到更能体现用户检索意图的权重分配方案。

［1］ZHANG Kaixing，ZHANG Shusheng，WANG Hongshen，et al.Content－based 3Dmodel retrieval and its application to CAD／CAM［J］.Mechanical Science and Technology for Aerospace Engineering，2009，28 （7）：847－850（in Chinese）.［张开兴，张树生，王洪申，等.基于内容的3D 模型检索及其在CAD／CAM 中的应用［J］.机械科学与技术，2009，28 （7）：847－850.］

［2］Takahiko F，Ryutarou O.Dense sampling and fast encoding for 3dmodel retrieval using bag－of－visual features［C］／／Proceeding of the ACM International Conference on Image and Video Retrieval，2009：192－199.

［3］Apostolos A，Georgios L，Petros D.3D model retrieval using accurate pose estimation and view－based similarity ［C］／／Proceeding of The 1st ACM International Conference Multimedia Retrieval，2011：17－20.

［4］Yi Y，Nie F P，Xu D，et al.A multimedia retrieval framework based on semi－supervised ranking and relevance feedback［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34 （4）：723－742.

［5］Li J B，Sun W H，Tang L L.3Dmodel classification based on nonparametric discriminate analysis with kernels ［J］.Neural Computing and Applications，2013，22 （3－4）：771－781.

［6］Tangelder J W H，Veltkamp R C.A survey of content based 3Dshape retrieval methods［J］.Multimed Tools Appl，2008，39 （3）：441－471.

［7］Jayanti S，Kalyanaraman Y，Ramani K.Shape－based clustering for 3DCAD objects：A comparative study of effectiveness［J］.Computer－Aided Design，2009，41 （12）：999－1007.

［8］WANG Hongshen，ZHANG Shusheng，BAI Xiaoliang，et al.3DCAD surface model retrieval algorithm based on distance and curvature distributions［J］.Journal of Computer－Aided Design＆Computer Graphics，2010，22 （5）：762－770 （in Chinese）.［王洪申，张树生，白晓亮，等.三维CAD 曲面模型距离－曲率形状分布检索算法 ［J］.计算机辅助设计与图形学学报，2012，22 （5）：762－770.］

［9］JIANG Lijun，ZHANG Xutang，ZHANG Guangyu.3Dmodel retrieval method based on area distributions［J］.Computer Engineering and Applications，2012，48 （12）：6－13（in Chinese）.［蒋立军，张旭堂，张广玉.基于面积分布算子的三维模型检索算法［J］.计算机工程与应用，2012，48 （12）：6－13.］

［10］HOU Xin，ZHANG Xutang，JIN Tianguo，et al.3Dengineering models retrieval algorithm based on mesh salient critical［J］.Computer Integrated Manufacturing System，2009，15 （1）：72－81 （in Chinese）.［侯鑫，张旭堂，金天国，等.基于网格临界点的三维工程模型检索算法 ［J］.计算机集成制造系统，2009，15 （1）：72－81.］

［11］Leng B.A powerful relevance feedback mechanism for content－based 3D model retrieval ［J］.Multimed Tools Appl，2008，40 （1）：135－150.

［12］Havemann S，Fellner D.Seven research challenges of generalized 3Ddocuments［J］.IEEE Computer Graphics and Applications，2007，27 （3）：70－76.

［13］Yang Yi，Nie Feiping，Xu dong，et al.A multimedia retrieval framework based on semi－supervised ranking and relevance feedback ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34 （4）：723－742.

［14］Hu B K，Liu Y S，Gao S M.Parallel relevance feedback for 3D model retrieval based on fast weighted－center particle swarm optimization ［J］.Pattern Recognition，2010，43（8）：2950－2961.

［15］Zhang X T，Chen X F，Yang P Y，et al.Geodesic connected Graph representation of 3Dprismatic CAD models［C］／／Proceeding of International Conference on Digital Manufacturing and Automation，2010：776－779.

［16］Li B，Johan H.3D model retrieval using hybrid features and class information ［J］.Multimedia Tools and Applications，2013，62 （3）：1－26.