三维CAD模型检索方法的优化研究*

田 柳，徐赐军，黄 浩，张绍峰，陈 磊

(1.武汉科技大学 机械自动化学院,湖北 武汉 430081;2.湖北理工学院 机电工程学院,湖北 黄石 435003)

0 引 言

CAD技术已广泛地应用于工程设计的各个领域，尤其是在机械行业，CAD建模已成为机械产品设计、制造等各个环节的重要步骤。

随着企业的产品更新，企业拥有CAD模型数量也在日益增加[1]。三维CAD模型的重用技术应用满足了设计人员重新绘图和建模等需求，提高了产品的设计效率。

徐赐军等[2]结合机械结构形态相关知识，提出了基于机械结构形态的三维CAD模型检索方法；XU L等[3]针对复杂的三维模型，基于局部细节特征的相似性比较来评估CAD模型，提高了三维模型的检索效率，但是部分模型检索的准确率有所下降；TASHIRO S等[4]采用具有尺度和旋转不变性的兴趣点来提取超向量编码特征，实现了对三维模型的检索;SIDDIQU A A等[5]开发了一种自动编码器，进行了语义建模以实现三维模型的检索。

随着大数据应用的发展，出现了分布式计算、分布式服务器集群、分布式存储等技术，大大改善了大数据的处理效率，分布式技术已成为了各研究领域的热点。LI B等[6]运用分布式检索技术，基于Hadoop建造的检索系统，使用户可以从海量的信息检索数据中找到所需的答案；郭飞等[7]提出了一种基于HDFS和传统关系型数据库相结合的图像及其特征数据的存储结构设计方法,实现了海量图像信息的快速存储和读取，降低了图像检索时间;杨进展[8]部署了一个具有HDFS和MapReduce分布式三维模型管理系统；廖先富[9]基于Hadoop的HDFS文件存储功能与Django技术，构建了一个云端分布式三维数据存储系统。

随着模型库三维CAD模型数量的增多，单台计算机算力不足的问题成为检索的瓶颈。三维CAD模型检索系统检索需要的时间越来越多，分布式计算成为优化三维CAD模型检索方法的首选。

针对三维CAD模型检索效率问题，笔者采用机械结构形态知识[10]及分布式计算技术，研究协同设计环境下三维CAD模型检索方法的优化。

1 三维模型检索框架

基于机械结构形态和分布式计算的三维模型检索系统以机械结构形态为主要特征，以分布式计算技术为主要工具。

基于机械结构形态和分布式计算的三维CAD模型检索方法，其框图如图1所示。

图1 三维模型检索框架

图1中：

(1)基础模块主要功能是通过基本体转换模型实现机械结构三维模型和机械结构形态的相互转换；

(2)数据整理模块主要是对基础模块中的机械结构形态库进行处理，以获取用于后续分布式计算的数据表，主要研究机械结构形态库中的模型相似度分组方法，并将模型的分组结果存储于数据库中；

(3)优化检索模块主要是分布式计算技术在三维模型检索中的应用，即对数据处理模块产生的数据进行处理；

(4)应用模块主要根据模型检索需要选择合适的指标实现三维模型的检索。

分布式计算是基于机械结构形态的三维模型相似度比较方法，结合MapReduce分布式计算编程模型，将模型相似性比较过程分为Map阶段和Reduce阶段，并经过分布式计算输出模型ID与相似度的键值对，获取模型ID所对应的机械结构形态和三维模型。

因此，图1中的三维模型检索框架是基于机械结构形态的三维CAD模型检索方法，该方法采用数据整理模块和优化检索模块对其检索算法进行优化。

2 模型相似链

基于机械结构形态的三维CAD模型检索方法，可大幅度提升模型检索的效率，但是在三维模型检索过程中模型库中的所有模型都需要参与相似度计算，大大增加了计算量。机械结构模型库往往存在许多只有少许细节不同的机械结构，若将这一系列的机械结构模型分成一组，构成模型相似链，则当遇到类似的机械结构进行检索时，待检索模型仅与该集合中每个模型进行相似度计算，可大大减少不必要的比较过程和计算。

模型相似链是指彼此之间相似度较高的机械结构的模型集合，并以模型编号表示。当待检测机械结构模型与相似链中的某个机械结构模型相似度较高时，说明待检测机械结构模型与相似链中其他机械结构模型相似度高的可能性较大；相反，当待检测机械结构模型与相似链中的某个机械结构模型相似度较低时，说明待检测机械结构模型与相似链中其他机械结构模型相似度低的可能性较大。

因此，只将待检测机械结构模型与相似度高可能性大的相似链中的模型进行比较，不与相似度低可能性大的相似链中的模型进行比较，可以大大减少比较次数。

模型相似链基于所有模型的相似性比较矩阵的相似度进行分组，模型相似性比较矩阵即是记录模型库中三维模型之间的相似度。

n个机械结构三维模型的相似性比较矩阵如图2所示。

IDa1……ai……aj……ana11……S1i……S1j……S1n…………1…………………………aiSi1……1……Sij……Sin……………………1………………ajSj1……Sji……1……Sjn………………………………1……anSn1……Sni……Snj……1

本文采用基于机械结构形态的三维模型相似度计算方法，构建三维CAD模型的相似性比较矩阵，以便于模型相似链构建过程中进行遍历和筛选数据。

若将所有模型ID组成集合A，令A中有n个元素，ID分别为a1、a2、a3…，则数据库模型相似链构建流程如图3所示。

图3 数据库模型相似链构建过程向下取整，即小于或等于的最大整数；Bi—第i条相似链，Bij—第i条相似链的第j个元素;SH—表示模型相似链元素构建的相似度阈值，一般取表示相似链规模的控制值，其目的是保证相似链构建效率，能够有效控制一条相似链的长度，如果一条相似链过长，会导致在后续对相似链所有元素进行相似度计算时计算量过大

3 分布式计算

分布式系统是多个处理机通过通信线路互联而构成的松散耦合的系统，通过网络相互连接传递消息与通信后并协调行为，且组件之间彼此交互以实现一个共同的目标；把需要进行大量计算的工程数据分割成小块，由多台计算机分别计算，然后上传运算结果，并将结果统一合并产生数据结论。

分布式计算过程如图4所示。

图4 分布式计算过程

该模型将输入工作划分为多个小块，并行计算，并将得出的结果进行汇总，最终产生计算结果。其中，map1表示待检索模型与第一条相似链中元素进行相似度计算，计算得出的map(id，score)即为模型id和相对应的相似度。

首先是待检索模型与每个相似链的相似度计算，将每组的运算过程为一个Map阶段，每个Map可并行进行计算；然后将Map的运算结果自动上传到Reduce，Reduce将所有键值对传入全局变量散列表N中，散列表N是用来记录键值映射关系的数据结构，可存储三维模型ID与相似度的映射关系；最后通过对N中的数据进行值排序得到相似度高的三维模型ID，通过ID映射到机械结构形态库和三维模型形态库，输出检索到的三维模型，完成检索。

Map函数主要逻辑运行调用相似度计算方法，经过相似度计算后，输出(id，score)，即(序号，相似度)键值对；经过MapReduce框架自动将键值对数据传入Reduce阶段。

令模型数据库共有m个模型相似链Bi，且令初始值i=1，j=1，则Map阶段运算过程如下。

步骤1：当i≤m时，将待检索模型与Bi中第j个元素进行相似度计算，即Sij；否则过程终止；

步骤2：若Sij≥SH(SH—相似度上限值，一般取0.6)，则待检索模型可以与模型相似链Bi其他模型进行相似性比较，即该链为可用链，进行下一步；若Si≤SL(为相似度下限值，一般取0.2)，则待检索模型不与模型相似链Bi中其他模型进行相似性比较，即该链为不可用链，i=i+1返回步骤1；若SL≤Sij≤SH，则当j<3时j=j+1，返回步骤1；当j>1时i=i+1，j=1，返回步骤1；

步骤3：将可用链中所有模型与待检索模型进行相似度计算，计算出的键值对(id，score)上传至Reduce处理；

步骤4：若i>m，则结束Map运算，否则返回步骤1。

4 实验验证

此处以美国普渡大学开发的ESB模型库为基础数据进行实验验证。ESB中包含866个STL格式的工程模型，笔者以其中任意1个模型作为输入，以检索出模型库中相似的模型。

实验采用的PC机参数为：Intel®Core (TM) i7-7700HQ@2.80 GHz CP，分布式Slave1 内存2 GB；Slave2 内存2 GB；Master内存2 GB。

以ESB模型库[11]ganter_din6304号模型机械结构形态为例，其相似度计算结果如表1所示。

表1 机械结构形态相似度

表1中，元素值越大说明三维模型之间的相似度越高。

同理，在三维模型数据库构建过程中，基于机械结构形态的三维模型相似度比较算法，获得的模型库中三维模型的相似性表矩阵，如图5所示。

ID12345678110.890.430.360.30.470.490.420.8910.720.360.390.330.020.2630.430.7210.50.760.430.720.7840.360.360.510.430.660.520.6350.30.390.760.4310.390.390.7760.470.330.430.660.3910.630.2670.490.020.720.520.390.6310.2280.40.260.780.630.770.260.221

图5中，模型1表示ganter_din6304-m20-110-f1，模型2表示ganter_din6304-m8-50-f1。

模型库相似链存储表如图6所示。

12345679101129182627364223123578133334973461224338996410112539469811811954474129145164175176

由图6第1行数据可以看出，1号模型与2号模型在同1条相似链中。

图6中行表头表示相似链ID，列表头表示相似链中的元素索引，表中数据表示模型id。

图5模型相似性比较矩阵生成图6相似链的过程如下：第1行中，1为第1条相似链的第1个元素，继续遍历得到与1号模型相似度大于0.6的模型ID，分别为2号、9号等模型，故集合[1,2,9,18…]为1条相似链；第2行中，1、2均被剔除，故第2条相似链从3开始，集合[3,5,7,8…]为1条相似链，继续生成多条相似链。

在进行和模型检索时，只需根据流程先和1号、2号模型进行相似度计算，即可确定该相似链是否可用。若为可用相似链，则与后续9号、18号等模型继续进行相似度计算；若为不可用链，则直接跳过该链，继续判断下一条相似链是否可用。

例如：待检索模型为1号模型，1号模型与1号相似链相似度为1，相似度大于0.6，则1号相似链为可用链，可与该相似链后续元素继续比较。1号模型与2号、3号、4号相似链相似度均小于0.6，则这3条相似链为不可用链，简化检索流程，以提高检索效率。

本文算法与文献[2]算法查准率与查全率曲线图如图7所示。

图7 查准率-查全率曲线图

图7显示，本文算法的查准率查全率与文献[2]算法基本一致，说明基于机械结构形态三维模型检索的准确率较高。

笔者随机选取3个模型ganter_din6305-M20、Nozag_bfi_60，以及winkel_ap，分别使用文献[2]检索算法和本文算法进行比较，其结果如表2所示。

表2 检索算法的结果比较

由表2可知：本文算法与文献[2]算法所获检索结果大致相同，但是本算法的检索时间明显较短，检索效率较高。

由此可见，通过模型相似性比较矩阵和相似链等技术的应用，三维模型的检索效率可以获得提升。

5 结束语

三维模型的重用是提升机械产品开发效率的重要途径，三维模型检索是实现三维模型重用的重要方法；但是随着三维CAD模型库模型数量的增加，导致检索效率大幅度降低。

为了保证检索效率，本文针对三维模型检索的需求，分析了基于机械结构形态的三维CAD模型检索的特点，提出了模型相似性比较矩阵、相似链两个概念，以简化模型检索过程；并给出了模型相似性比较矩阵、相似链的计算以及使用方法；结合分布式系统架构提出的分布式计算方法，实现了基于机械结构形态的三维CAD模型检索分布式计算系统的搭建；通过简化模型检索过程和使用集群代替单机以解决单机算力瓶颈问题的方法，完成了对三维CAD模型检索方法的优化。

实例验证的结果表明：该方法能够在保证检索精度的条件下，显著减少三维模型的检索时间，检索效率获得了提升。