基于面属性相似的CAD模型检索方法

陶松桥，郭顺生

(1.武汉理工大学 机电工程学院，湖北 武汉 430070；2.武汉交通职业学院 机电工程学院，湖北 武汉 430065)



基于面属性相似的CAD模型检索方法

陶松桥1,2，郭顺生1

(1.武汉理工大学 机电工程学院，湖北 武汉 430070；2.武汉交通职业学院 机电工程学院，湖北 武汉 430065)

针对现有基于面属性图需要应用图匹配或子图匹配计算来实现CAD模型的形状匹配，且其模型检索方法存在检索效率低下或检索结果不够准确的问题，提出了一种基于面属性相似的CAD模型检索方法。在现有的模型面属性基础上，引入了包含较多属性的面特征属性和面几何边界特征属性来表达CAD模型的形状特征。特别是外环边循环码可以更详细地表达模型的面几何边界特征属性，只需要采用简单的模型面属性相似性度量方法就能实现CAD模型的形状检索。实验结果表明，该方法能够实现CAD 模型的形状检索，其检索效率和精准程度能够满足实际需要，显著提高了CAD模型面的形状辨识能力。

面属性图; 外环边循环码；模型检索；子图匹配

由于CAD模型中蕴含丰富的产品设计与制造知识，设计工程师可以使用CAD模型数据库检索到相似产品的CAD模型作为设计参考，激发新产品设计的灵感；制造工程师可以通过CAD模型检索，查找到相关产品的生产工艺及生产供应商。尽管CAD模型数量连续不断地增长，数以千计的CAD模型可以从公共和私人数据库中免费获取，但设计和制造工程师面临如何从这些CAD模型数据库中检索其所需要的CAD模型的问题[1]。

由于提取三维CAD 模型的边界表示(boundary representative, B-rep)信息简单方便，并且现有的图与子图匹配算法可直接应用于CAD模型的整体与局部匹配，故用面属性图描述CAD模型的形状是一个自然而实用的选择[2-6]。EI-MEHALAWI等[7]较早用面属性图描述 CAD模型的形状，考虑包括面的几何类型、边的几何类型及边分别与X轴和Y轴的相对方位角等面属性。陶松桥等[8]提出的面属性图考虑的面属性包括面的几何类型和凸性等,以及边的几何类型和凸性等。王飞等[9]提出的面属性图考虑的面属性包括面的几何类型、法矢、曲率、面积，以及共边、平行、垂直和共面等面关系。高艺等[10]用典型面来描述CAD模型的形状，典型面是同一功能类别的机械零件中出现频率较高，具有一定功能和语义的面。面属性图描述CAD模型的优点是生成过程计算简单，缺点是实现模型的形状匹配还需要复杂的图匹配或子图匹配计算。当模型形状比较复杂时，由于模型的面数量很多，导致面属性图的规模较大，其缺陷更加明显。笔者在现有的模型面属性基础上，引入了包含较多属性的面特征属性和面几何边界特征属性来表达CAD模型的形状特征。特别是引入的外环边循环码更详细地表达了模型的面几何边界特征属性，大大提高了用面属性表达CAD模型形状特征的辨识能力，只需采用简单的模型面属性相似度度量方法就能实现CAD模型的形状检索。

1 面属性编码

由于编码易于生成，进行相似性度量比较方便，笔者用面属性编码表达CAD模型的面形状特征。其中面属性包括面特征属性和面几何边界特征属性。考虑的面特征属性包括：面的几何类型(平面、圆柱面、圆锥面和球面等)、相对面积(该面面积与总表面积的比值)、环数(内环数和外环数的和)、面的凸性(凸面、平面和凹面等)[11]和外环中边数。由于实体模型的面几何边界可能由外环和内环组成，一个面的内环边界最终是另一个面的外环边界或外环边界的一部分，这里的面几何边界仅考虑模型的外环边界。引入的面几何边界特征值包括：外环边的几何类型(直线和圆弧等)、外环边的相对长度(外环边的边长与外环总长的比值)、外环边起始角和终点角(外环边在面上的夹角)，以及外环边凸性(外环边的中点处所连接的两个面在体内空间夹角的凹凸性)。

1.1 面特征属性编码计算方法

面特征属性中的面几何类型和凸性编码都为一位十进制整数，其编码方法如下：用fT表示面的几何类型编码，如平面fT=0，圆柱面fT=1，圆锥面fT=2，球面fT=3，其他面fT=4。用fC表示面的凸性编码，如平面fC=0，凸面fC=1，凹面fC=2，其他面fC=3。

1.2 面几何边界特征属性编码计算方法

面几何边界特征属性中的外环边几何类型和凸性编码都为一位十进制整数，它们的编码方法如下：用eT表示外环边的几何类型编码，如直线边eT=0，圆弧边eT=1，其他边eT=2。用eC表示外环边的凸性编码，如直线边eC=0，凸边eC=1，凹边eC=2。用rL表示外环边的相对长度编码，为两位十进制整数，其计算公式为：rL=(int)(100×relLength)，relLength为外环边的相对长度。

1.3 外环边循环码计算方法

采用单一的面特征属性和面几何边界特征属性对模型面进行形状辨识时，同样存在着辨识能力不足的问题。另外，考虑到模型面的外环边界由外环边首尾连接形成了一个封闭区域，从任意一条外环边的端点出发，沿逆时针方向遍历边界上的所有外环边后，最终仍将回到起点。因此，笔者引入外环边循环码来更详细地表达模型的面几何边界特征属性，以提高模型面属性的形状辨识能力。外环边循环码计算方法如下：

(1)计算每一条外环边的属性编码e。e的计算公式为：

e=eW-rL

(1)

式中:rL为外环边的相对长度编码;符号“-”为编码连接符;eW为两位十进制整数，其具体计算方法如下：

eW= 33×eT+ 32×eC+ 31×seC+ 30×eeC

(2)

式中：eT和eC分别为外环边的几何类型和凸性编码；seC和eeC分别为外环边起始角(startAngle)和外环边终点角(endAngle)对应的编码。当startAngle=180°时，seC=0；当startAngle﹤180°时，seC=1；当startAngle﹥180°时，seC=2。类似地，当endAngle=180°时，eeC= 0；当endAngle﹤180°时，eeC= 1；当endAngle﹥180°时，eeC= 2。

(2)从任意一条外环边出发，沿逆时针方向连接边界上的所有外环边编码，形成外环边编码串。选择不同的外环边作为循环起点时，得到的外环边编码串不同。为了保证模型面的外环边循环码的唯一性，引入最大编码串的概念。设编码数组为e[0],e[1],…,e[n-1],n为外环边数。第k条边的编码串eS[k]为：

eS[k]=e[k]-e[k+1]-…-

e[n-1]-e[0]-…-e[k-1]=

eW[k]-rL[k]-eW[k+1]-

rL[k+1]-…-eW[n-1]-rL[n-1]-

eW[0]-rL[0]-…-eW[k-1]-rL[k-1]

外环边循环码Cycle定义为最大编码串:

Cycle= max {eS[k] |k=0,1,2,…,n-1}，即Cycle=e(e0)-e(e1)-…-e(en-1),e0为最大编码串的起始边。

以图1中CAD模型的面f为例说明外环边循环码Cycle的计算过程。面f有4条外环边e0,e1,e2和e3，其面几何边界特征属性如表1所示。

图1 面f及其4条外环边示意图

表1 模型面f的外环边特征属性

由表1和式(1)可知：

e[0]=04-01，e[1]=04-42，e[2]=04-17，e[3]=04-39。

编码串为：

eS[0]=04-01-04-42-04-17-04-39;

eS[1]=04-42-04-17-04-39-04-01;

eS[2]=04-17-04-39-04-01-04-42;

eS[3]=04-39-04-01-04-42-04-17。

最大编码串为eS[1]，因此面f的外环边循环码Cycle为04-42-04-17-04-39-04-01。

2 相似性度量

2.1 面特征属性相似性度量

假设相比较面a和b的特征值向量分别为：

Va=(va1,va2,va3,va4,va5)

Vb=(vb1,vb2,vb3,vb4,vb5)

其中，vai和vbi(i=1,2,3,4,5)分别为相比较模型的面几何类型编码fT、凸性编码fC、相对面积、环数和外环中边数，则面a和b的特征值向量相似度SfV(a,b)为：

2.2 外环边循环码相似性度量

假设相比较面a和b的外环边循环码分别为Cyclea=(a1-r1-a2-r2-…-am-rm)和Cycleb=(b1-s1-b2-s2-…-bm-sm),这里a和b的值对应于式(1)中的eW编码,r和s对应于式(1)中的rL编码。将Cyclea和Cycleb分解为A=(a1,a2,…,am)，R=(r1,r2,…,rm)，B=(b1,b2,…,bn),S=(s1,s2,…,sn)，则面a和b的外环边循环码相似度Sfe(a,b)为：

2.3 面相似性度量

假设相比较面a和b的面特征属性相似度和外环边循环码相似度分别为SfV(a,b)和Sfe(a,b)，则面a与b的相似度Sf(a,b)为：

Sf(a,b)=w1×SfV(a,b)+w2×Sfe(a,b)

(3)

式中,w1、w2为权值，w1≥0,w2≥0,w1+w2=1。

2.4 CAD模型相似性度量

假设相比较模型q和d的面数量分别为m和n，检索模型q的第j个面与数据库模型d的第k个面的相似度为Sf(fqj,fdk),则模型q和d的相似度S(q,d)为：

(4)

3 CAD模型检索实验与分析

3.1 CAD模型检索实验

为了验证所提出的基于面属性相似的CAD模型检索方法的有效性，笔者基于Visual C++,ACIS和HOOPS系统开发了一个CAD 模型检索原型系统。实验所用微机配置为Intel 3.0 GHz的CPU和1.0 GB内存，实验所用模型数据库中绝大部分模型从美国普渡大学的ESB模型数据库下载，包含420个ACIS格式的CAD模型。

在模型数据库中，选择了3个面数量分别为59、33和11的CAD模型进行检索效果和检索效率测试，进行局部检索实验时选择的模型面数量分别为9、11和11，相关实验结果如表2所示。选择这两个模型是因为与它们具有相似局部特征的CAD模型在模型数据库中较多，能够充分地反映所提方法的特点。在表2中，模型本身的颜色是浅色，待检索模型中用于局部检索的形状特征用浅灰色标记，检索结果返回的相关数据库模型中被成功匹配的面用深灰色标记。检索结果模型下面的数字由式(4)计算得到，相似度数值越小，说明两个相比较模型越相似，相似度为0，表示两个模型完全匹配。表2中所列出的时间没有包含面属性编码和外环边循环码的生成时间，仅为待检索模型与数据库所有模型的面相似度计算时间。面属性编码、外环边循环码及其他面属性在模型检索前的离线阶段批量生成，以记事本的形式保存在模型描述子数据库中，检索时直接从描述子数据库中读取。另外，为了进一步说明该方法的有效性，在表2中同时列出了文献[9]的实验结果，以便进行对照比较。

3.2 实验结果分析与计算方法处理

假设待检索模型q用于检索的局部特征包含的面数量、边数量及外环边数量分别为m、a和k，数据库模型d的面数量、边数量及外环边数量分别为n、b和l。笔者方法中模型检索时的面相似度计算复杂度是max(m×n×k×l，m×n×5×5)，而现有的面属性图匹配方法大多与文献[9]方法类似，一般要求相比较模型的面和边分别匹配，模型检索时面匹配的计算复杂度一般不低于m×n×a×b。明显地，max(m×n×k×l，m×n×5×5)一般远小于m×n×a×b。因此，笔者方法与文献[9]相比，模型检索效率具有较大的优势，表2中的实验结果也验证了该结论。

表2 CAD模型检索实验结果

为了提高模型检索的效率，在模型面相似度计算时设置了过滤措施和阈值，如相比较面的面几何类型不同或凸性不同，就直接认为它们不匹配，将相似度设为1；如相比较面的面特征属性或外环边循环码相似度计算结果大于阈值，就直接认为这两个面不匹配；如待检索模型中有一个面在相比较的数据模型中找不到相匹配的面，就直接认为这两个相比较模型不匹配。

如果相比较的检索模型和数据库模型中面的外环边数量越多或外环边的类型越丰富，通过外环边循环码相似度计算筛选掉的面越多，导致模型面的形状辨识能力越强。因此，笔者方法可以通过灵活地设置式(3)中权值w1和w2，得到不同精度的检索结果，以满足不同用户的不同检索需求。对于处于产品设计初始阶段，不具备模型详细信息的用户，可以通过设定较小的权值w1，查找到数量较多的、与检索模型具有不同相似程度的模型作为设计参考；对于拥有精确模型结构的用户，则可以通过设定较大的权值w1，快速地定位某个模型。

4 结论

笔者提出的基于面属性相似的CAD模型检索方法，通过引入外环边循环码显著改善了模型面的形状辨识能力，避免了使用图匹配或子图匹配来实现模型的形状检索。尽管该方法中CAD模型描述符的生成及编码的计算需要一定的时间，但是它们是在检索前的离线阶段批量生成，类似于大规模模型库检索时建立的索引体系。实验结果表明，该方法能够实现CAD 模型的形状检索，检索效率和精准程度能够满足实际需要。

[1] GUNN T G. The mechanization of design and manufacturing[J]. Scientific American, 1982,247(3):86-108.

[2] TAO S Q, HUANG Z D, ZUO B Q, et al. Partial retrieval of CAD models based on the gradient flows in Lie group[J]. Pattern Recognition, 2012,45(4):1721-1738.

[3] TAO S Q, HUANG Z D, MA L J, et al. Partial retrieval of CAD models based on local surface region decomposition[J]. Computer-Aided Design, 2013,45(11):1239-1252.

[4] TAO S Q. General and partial retrieval of CAD models based on surface region partition [J]. Computer-Aided Design and Applications, 2014,46(1):32-42.

[5] 陶松桥,郭顺生.基于面上下文码匹配的CAD模型检索方法[J].计算机工程与应用,2014,50(3):1-5.

[6] 陶松桥,黄正东,马露杰.基于区域特征分割的CAD模型局部搜索方法[J].中国机械工程, 2013,24(12):1611-1615.

[7] EL-MEHALAWI M, ALLEN M R. A database system of mechanical components based on geometric and topological similarity, part I: representation[J]. Computer-Aided Design, 2003,35(1):95-105.

[8] 陶松桥,黄正东,郑坛光.基于属性邻接图匹配的三维CAD模型搜索方法[J].计算机集成制造系统,2011,17(4):680 -687.

[9] 王飞,张树生,白晓亮,等.基于子图同构的三维CAD模型局部匹配[J].计算机辅设计与图形学学报,2008,20(8):1078-1084.

[10] 高艺,王斌,胡楷模,等.基于典型面匹配的机械零件检索方法[J].计算机辅助设计与图形学学报,2011(4):640-648.

[11] 陶松桥,王书亭,郑坛光,等.基于非精确图匹配的CAD模型搜索方法[J].计算机辅助设计与图形学学报,2010(3):545-552.

TAO Songqiao:Post Doctor; School of Mechanical and Electronic Engineering, WUT, Wuhan 430070, China.

[编辑：王志全]

CAD Models Retrieval Based on the Similarity of Face Attributes

TAOSongqiao,GUOShunsheng

A CAD model retrieval method based on the similarity of face attributes was presented in order to resolve the problem that graph matching or sub-graph matching realizing the CAD model retrieval based on face attribute graph may not be effective and efficient enough. Based on the existing representations for face attributes, the face attributes and geometry boundary attributes were introduced to represent the shape of CAD models. In particular, cycle code of the outer edges was adopted to describe the shape of CAD models in detail, which greatly increased the resolution of the face shape. Thus, the similar evaluations between the compared models were used for realizing the CAD model retrieval instead of graph matching or sub-graph matching. Experimental results show that this method is able to support CAD model retrieval and its efficiency and effect meets the requirement of practical applications.

face attribute graph; cycle code of the outer edges; model retrieval; sub-graph matching

2015-03-21.

陶松桥(1973-)，男，湖北孝感人，武汉理工大学机电工程学院博士后.

国家自然科学基金资助项目(51475186);湖北省教育厅科研基金资助项目(B2013229).

2095-3852(2015)05-0537-05

A

TP391

10.3963/j.issn.2095-3852.2015.05.003