基于模型分割的子区域局部匹配算法

李 芳，莫 蓉

（西北工业大学 机电学院，陕西 西安 710072）

0 引言

随着数字化设计技术的深入发展，产品的三维模型越来越多地应用于企业中，成为可以利用的有效资源，如何快速准确地从模型库中找到所需的零件模型成为应用的一个难点。在机械工程领域，CAD模型的相似性检索具有重要的应用价值[1-2]。人们往往将已有的模型作为设计参考或重用，而模型的细节结构成为结构细分的重要因素，因此，在模型库中进行三维模型的局部检索在工程界具有重要的应用价值。近年来，基于内容的检索技术研究成为热点，它可以直接利用三维模型的特征来建立索引和完成检索，其关键是使提取的结果能够描述模型形状特征[3]。Zhang和Chen[4]在几何结构上通过三角网格描述模型的表面轮廓，但由于数据多计算效率较低，效果不理想；Osada[5]提取模型表面采样点，计算点与点之间诸如角度距离、面积和体积作为几何度量的形状函数，其形状函数值的概率分布作为模型的特征向量，但分布函数会丢失细节信息。Cyr和Kimia[6]将图片进行聚类并最终根据图片之间的关系将它们组织成 shock图结构，采用shock图匹配算法计算物体的图片之间的相似度。

为了更好地实现局部检索时准确性与效率的双重结合，本文提出了一种基于模型分割的子区域局部匹配算法。提取CAD模型的B-rep信息，交互或预定义方式获取预检索的局部区域，将局部区域和CAD模型分别用属性邻接图表示，并对两者按照模型凸凹性区域分割算法进行区域分割，再在凹凸性基础上实现CAD模型的局部匹配。

1 基于模型子区域局部匹配算法

1.1 CAD模型的B-rep表示

模型的B-rep表示可以直接反映形体元素的几何信息与拓扑信息，其优点是可直接表示点、边、面等几何元素及其之间的关系[7]。属性邻接图（Attributed Adjacency Graph，AAG）是一种用图来表示实体的B-rep结构的方法，其表达式为G=（V，E，A）。其中，G表示CAD模型；V表示图的节点集合，代表模型的几何曲面，每个面fi都有唯一一个节点vi与之对应；E表示图的边集合，对于模型的每两个相邻面fi，fj都有唯一的弧ei与之对应；A表示面集合和边集合的相关属性，面的属性包括其所属类别以及指向，其中，类别包括平面、柱面、双曲面、球面等。面的指向则根据其曲率正负分为凸曲面、凹曲面、平面[7]。边作为两面的相交部分，其属性可以按照两曲面外夹角分为凸边、凸切边、凹边、凹切边[9]。考虑到工程应用中大部分三维模型由相对简单的几何面构成，本文的研究对象均为由简单几何面如平面、柱面构成的CAD模型。

定义一：凸子图。（1）图 g=（v，e，a）是图 G=（V，E，A）的导出子图；（2）g中的任意节点表示的面的属性为凸曲面或平面；（3）g中节点之间的连接边均为凸边。则称g为凸子图。凸子图所代表的曲面组成的区域为凸区域。

定义二：凹子图。（1）图 g=（v，e，a）是图 G=（V，E，A）的导出子图；（2）g中的任意节点表示的面的属性为凹曲面或平面；（3）g中节点之间的连接边均为凹边。则称g为凹子图。凹子图所代表的曲面组成的区域为凹区域。

定义三：凸节点。图 g=（v，e，a）中，节点 vi表示面为凸曲面或平面；并且它的连接边中无凹边，则称这类节点为凸节点。

定义四：凹节点。图 g=（v，e，a）中，节点 vi表示的面为凹面或平面；并且它的连接边中无凸边，则称这类节点为凹节点。

定义五：混合节点。图 g=（v，e，a）中，节点 vi表示凸（凹）曲面，并且连接边中存在凹（凸）边；或者vi节点表示平面，并且它的连接边中同时存在凸边和凹边。

显然凸（凹）区域中的节点一定是凸（凹）节点，如果可以继续分离子图，则分离后的子图凸凹类型不变。对于混合节点，其凸凹性比较模糊，视分割情况而定。

1.2 模型区域分割

将模型表面按照凸凹类型分成凸区域、凹区域，AAG中与之对应的即凸子图、凹子图，因此三维模型中凸凹区域的分割等价于对应的属性邻接图的分割。我们可以将模型区域分割定义如下：

图 G=（V，E，A），存在一组子图 g1，g2，…，gi，gn（i=1，2，…，n），其中 gi=（v，e，a）是凸子图或凹子图，且满足 GV=g1V∪g2V∪∪gnV；且 giV∩gjV=ø（i≠j）；则称图g1，g2，…，gi，…，gn（i=1，2，…，n）是图G的一组分割。

在分割中，我们希望实现凸区域和凹区域的合理划分，其中凸凹子图中节点和边的凸凹性质与其子图本身一致。在划分中，凸节点划分到凸子图，凹节点划分到凹子图，而混合节点中既有相连的凸边又有相连的凹边，划分起来比较麻烦，因此需要重新确定混合节点的凸凹性质。鉴于先识别凸子图或者先识别凹子图会得到不同的效果但又不会影响区域凸凹区域特征的表现，我们规定在分割时先识别并分离凸子图，后识别并分离凹子图[10]。

一种最直接最简单的分割即是将图的每个节点作为一个子图，显然，这种分割没有意义。我们希望分割后的区域数量越少越好，并且能够明显的描述模型表面凸凹特点。因此提出下列分割方法：

（1）根据节点凸凹性，通过图的遍历识别出G中所有混合节点，若无，则图G中节点的凸凹性质一致，本身G就是一凸子图或者凹子图，将图G=（V，E，A），输出到区域H中；若存在混合节点，转到步骤（2）；

（2）由步骤（1）识别出了混合节点后，删除混合节点的所有凹边，将G分割成子图集M={g1，g2，…，gm}；

（3）在剩余的子图集中肯定存在凸子图，可能存在凹子图，因为本身混合节点就连接着凸边和凹边，删除了与其连接的凹边，必然剩下凸边，否则与混合节点的定义相违背。将子图集M输出到H中；

（4）将分割后的凸子图输出到H后，在剩余的图中恢复删除的凹边，并重新确定子图gi（i=m+1，…，n）中混合节点的凸凹类型。若不存在混合节点，则将它输出到区域R中；否则，将以gi作为输入，重复步骤（2）；

（5）输出分割结果H。

1.3 子区域局部匹配算法的实现

传统的模型匹配算法大多按照CAD模型以及预匹配模型的B-rep信息，在大图中搜索与小图的拓扑与几何相同的子图。由于属性邻接图中包含了模型每个面和边的属性信息，算法实现起来信息量大，效率不是很理想，区别能力有限。因此我们在CAD模型B-rep表示的基础上，构建模型的属性邻接图，提出模型表面区域分割的思想，经过分割后，模型被分解为凸凹子图的集合 G={g1，g2，…，gu}，设预匹配子图为 Q={q1，q2，…，qs}，下文中我们称图 G为大图，预匹配子图为小图，分三种情况进行匹配，具体的匹配过程如下：

情况一：小图均为凸子图（或凹子图）

（1）小图Q由凸节点组成，即本身为一凸子图，则只需在大图G中的凸子图中进行匹配搜索，设G的一个凸子图gi，ηi∈E，i=1，2，…，t（ηi为凸子图的边，t为此凸子图的边数）vj∈e，j=1，2，…，s（vj为小图的边，s为小图的边数）若t≥s，则继续匹配，转到步骤（2）；反之，此凸子图中无法与已知子图匹配；如此过程遍历Q中的所有凸子图；

（2）分别在凸子图gi中寻找与边vj属性相同的所有边，如果存在则存入集合，Si，j，i=1，2，…，z，j=1，2，…，s（z为凸子图个数，s为集合元素的个数，与小图中边的个数相同）；若凸子图gi中无与边vj属性相同的边，则该凸子图中不含有预匹配的局部结构。

（3）在 Si，j中任取一条边，并按照边的顺序提取出各边相邻的面，去除重复的面，形成面的集合Vy。若Vy中面的个数与小图的面的个数相同，则转到步骤4，否则进行下一个组合。

（4）将Vy组成的局部结构从CAD模型中分离出来并表示出其邻接矩阵，如果新结构的邻接矩阵与小图的邻接矩阵相等，则该凸子图中含有预匹配的局部结构；反之，返回步骤（3），继续下一组合。

（5）若小图Q由凹节点组成，即本身为一凹子图，匹配过程类似凸子图，过程如步骤（1）到（4）。

情况二：小图为混合子图

若小图Q由凸节点和凹节点组成，设分割后的小图表示为 Q={q1…ql，ql+1…qh}，其中{q1…ql}表示小图的凸子图集合，{ql+1…qh}表示小图的凹子图的集合；分割后的大图表示为 G={g1…gm，gm+1…gs}；其中{g1…gm}表示大图的凸子图集合，{gm+1…gs}表示大图的凹子图集合。

（1）通过图的深度优先算法或宽度优先算法遍历大图G的各节点，判断大图是否也由凸凹节点组成，如果是，转向步骤（2），反之，大图中无匹配区域；

（2）从小图的一个凸子图中任取一个边wj，并在大图的各凸子图中搜索与该边属性相同的边，设为vi；

（3）将搜索到的大图中边所在的凸子图存入集合 M={g1…gt}；

（4）任取M中的一个凸子图，从vi开始遍历与其相连的各边，看是否与wj所连的相应的边的属性相同，若相同，则此凸子图匹配成功，继而重复步骤（2），进行下一小图中的凸子图的匹配；若在遍历过程中，有属性不一致的边，则停止此次搜索，由于大图中可能存在不止一个凸子图中有与边wj相同属性的边，因此，还需继续重复步骤（2），直到与wj属性相同的边所在的凸子图都遍历完成，还无可匹配子图，则结束匹配；

（5）小图中凹子图的搜索及匹配与凸子图类似，步骤如上，这里就不再赘述。

（6）由于小图是由凸凹子图组成，只有其凸凹子图同时在大图中找到相匹配的部分才能说明大图中存在与小图匹配的子结构。

2 实验与分析

本节给出了采用本文方法得到的部分实验结果：一个是根据凸凹性质的模型表面区域划分；另外一个是基于凸凹子区域的局部匹配得到的检索结果。

2.1 模型的凸凹区域分割

利用本文的方法，选取典型零件对其区域分割。图1a所示为一个CAD模型经过表面区域分割后的结果，我们将同一区域的部分标记为同种颜色。该模型经过分割后共有五个区域，其中四个凹区域，一个凸区域；为了更好的显示，图1b中给出了该模型的拓扑连接图，其中“+”表示面与面的连接边为凸边，“-”则为凹边。工程中的正特征和负特征对于模型的特征表述以及制造加工具有重要的意义，而我们的凸区域和凹区域也和这两种特征有一定的联系。实验可以看出，利用该方法能较好的实现CAD模型的区域分割，并且对于得到的分割区域具有一定的工程意义，为模型分析及下文的子区域匹配奠定了良好的基础。

图1 模型凸凹区域分割

2.2 基于凸凹子区域的局部匹配

图2 典型结构

图3 典型结构搜索结果

为了验证基于子区域局部匹配算法的有效性，我们选择了上述区域分割的盘类结构作为典型结构（图2），并在50个包含了轴类、齿轮类、盘类的典型结构作为三维CAD模型库中进行匹配。其中三维CAD模型库中有11个模型被准确检索到，这里选取6个具有代表性的模型进行显示如图3。本文算法较之以往的按照相似性模糊匹配方法具有明显的优势，由于在匹配之前对模型进行凸凹区域分割处理，相匹配的结构必然与预匹配模型具有相同拓扑结构的凸区域和凹区域，因此能更好的保证匹配精度。而且按照凸凹区域来匹配不需要逐边逐面的按照属性来搜索，可以大大降低搜索空间，通过与文献[3]对比，可以发现本文的算法在效率上能大约提高15%到25%。

3 小结

局部结构的检索在工程上具有一定的意义，也是模型检索中一个难点问题[11]。几何模型的数据结构只能表达产品的几何拓扑关系，不能表达产品的非几何信息，因而缺乏产品开发过程中所要求的工程语义信息[12]。本文在属性邻接图的基础上，提出一种基于凸凹子区域的局部匹配算法。首先按照模型的面和边的属性，经过一系列的处理将CAD模型分割成凸凹区域，也就相当于将其属性邻接图分割成若干个凸凹子图。在匹配过程中，将大图与小图中凸子图与凸子图，凹子图与凹子图分别匹配。通过判断子区域是否相应匹配看大图中是否含有预匹配的结构。本文算法不需逐边逐面的采用子图匹配算法来进行检索。由于考虑模型的边和面的几何信息，更有利于模型结构的检索[13]。但是属性邻接图的构造是从模型的B-rep信息入手，这种采用单一特征描述方法丧失了空间分布信息，因此存在不完整性。如何将几何和拓扑信息更好的来进行特征描述，并用于三维模型检索，仍是今后需要研究的内容。

[1]Cardone A，Gupta S K，Karnik M·A survey of shape similarity assessmentalgorithmsforproductdesign and manufacturing applications[J].Journal of Computing and Information Science in Engineering，2003，3（6）：109-118.

[2]王 玉，马浩军，何 玮，等.机械三维CAD模型的聚类和检索[J].计算机集成制造系统，2006，12（6）：924-928.

[3]胡琪波，何卫平，董 蓉，等.可重用MES模板检索技术研究[J].锻压装备与制造技术，2010，45（3）.

[4]Zhang和chen C.Zhang and T.Chen.Indexing and Retrieval of 3D Models Aided by Active Learning.In ACM Multimedia，2001：615-616.

[5]Osada R.Osada，T.Funkhouser，B.Chazelle，and D.Dobkin.shape Dis tributions.Acm Transactions On Graphics，2002.21（4）：807-832.

[6]Cyr和Kimia C.M.Cyr and B.Kimia.3D Object Recognition Using Shape Similiarity-Based Aspect Graph.In ICCV01，2001：254-261.

[7]王 飞，张树生，白晓亮，等.基于子图同构的三维CAD模型局部匹配 [J].计算机辅助设计与图形学学报，2008，（8）：1078-1084.

[8]Sonthi R，Kunjur G，Gadh R.Shape feature determination using the curvature region representation[C]//Proceedings of the 4thSymposium on Solid Modeling and Applications，Atlanta，1997：285-296.

[9]Fu M W，Ong S K，Lu W F，etal.An approach to identify design and manufacturing features from a data exchanged part model[J].Computer-Aided Desegn，2003，35（11）：979-993.

[10]马露杰，黄正东，梁 良，等.CAD模型表面区域分割方法[J].计算机辅助设计与图形学学报,2009.

[11]白 静.面向设计重用的三维CAD模型检索[D].浙江：浙江大学，2009.

[12]杜继涛，齐从谦，甘 屹.基于集成技术的汽车覆盖件产品模型.锻压装备与制造技术，2005，40（2）.

[13]徐 胜.三维物体识别研究[D].成都：电子科技大学，2009.