引用本文

吴强, 董雁, 吴域西, 谢丽萍. 基于概念格因子分解的零件三维CAD模型检索. 自动化学报, 2019, 45(2): 407-419. doi: 10.16383/j.aas.c170205

WU Qiang, DONG Yan, WU Yu-Xi, XIE Li-Ping. Concept Lattice Factorization Based 3D Model Retrieval of Mechanical Parts. ACTA AUTOMATICA SINICA, 2019, 45(2): 407-419. doi: 10.16383/j.aas.c170205

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c170205

关键词

概念格，对象(属性)概念，布尔矩阵，因子分解，零件工程图结构模型，关键结构 

摘要

针对影响概念格应用的重要问题—即使是一个小规模数据集也会产生大量的形式概念，文中提出了可以满足关系覆盖的用对象（属性）概念分解形式背景对应的布尔矩阵的新方法.用这种方法原对象属性间的二元关系可以用数量在对象（属性）概念个数以内的概念表达出来，成为概念格因子.文中给出了概念格因子生成的基本原理及其算法.通过分析三维CAD零件模型功能表面间的关系构建零件工程图结构模型，并将其映射为形式背景，从而完成概念格因子到零件关键结构的应用.最后，实例演示了概念格因子在基于零件工程图结构模型的零件CAD模型检索中的运用.

文章导读

对于概念格来说, 即使是一个小的数据集可能产生大量的形式概念[1].这是源于其存在高组合复杂性和结构.最坏的情况可以达到 (|G|,|M|分别为对象和属性的总数).此外, 产生的形式概念的数量和概念之间关系的复杂性使得最终格的分析十分困难[2].

为简化概念格, 现有的研究主要采用了知识约简的方法.所谓知识约简, 就是针对不同的目的要求, 保持知识库分类能力不变, 删除其中不相关或不重要的属性, 使知识表示简化的同时又不丢失基本信息.

已有研究者研究了从给定的二元形式背景[3]、决策形式背景[4-5]、模糊形式背景[6-7]、实决策形式背景[8]中约简生成形式概念. Dias和Vieira[9]提出了一种分析概念格约简的方法.它是基于存在于原始与约简后的形式背景, 或概念格间的特有的蕴含集合的.通过这些蕴含集合, 设计的约简方法能够显现数据信息的保持、消失、增加及变化.他们从方法论的角度分析了三类约简技术, 强调了其在转换时的共同之处. Konecny[10]的研究表明, 虽然有各种扩展, Ganter和Wille的概念格属性约简和解释依然是优于基于可辨识矩阵约简的. Singh等[11]提出了一种在形式概念分析中用模糊属性减少形式概念数目的方法.其以香农熵计算模糊形式概念的权重.用计算的权重选择粒约简模糊形式概念.结果表明, 所提出的方法得到的结果与Levenshtein距离法以及区间值模糊形式概念的方法一致, 但计算复杂度更低.因为是基于属性的, 这些方法的结果很难直观地、易于理解地反映出对象——属性关系(即形式概念)的重要程度.

就目前的结果来说, 关注重要概念选择以至于对概念格进行分解的研究较为鲜见. Babin和Kuznetsov[12]引进了概念稳定性来测度概念的重要性. Belohlavek和Macko[1]利用权重研究了重要的概念并讨论其应用. Dias和Viera[13]提出基于连接的对象相似(JBOS)方法约简形式概念的数目. Li等[14]讨论了加权概念格及其应用. Kang等[15]提出一种在不同粒度下减少模糊概念格大小的方法. Li等[16]提出了一种采用K-medoids聚类来压缩近似概念格的方法. Martin等[17]提出一种使用Levenshtein距离测度模糊概念格的变化的方法. Singh等[18]推出了一个使用香农熵来计算给定模糊形式概念的权重的方法, 选择根据所计算出来的权重的粒度约简模糊形式概念. Aswani等[19]新近提出了在形式背景上用非负矩阵分解约简知识, 但仅提出了一个思想, 对矩阵存在与约束条件尚无探讨.

将概念格与因子分析联系起来的是Keprt和Snášel[20].他们提出了基于形式概念分析计算非层次二元因子分析的方法.尽管计算概念格本身也是十分繁杂的, 它仍然帮助加快了二元因子分析的计算. Belohlavek和Vychodil[21]提出了一个有序数据的矩阵分解和因子分析的方法.这些因子对应于输入数据的形式概念成为数量最少的因子, 并可以十分简单的解释分解.

由于图能较好地描述三维CAD模型的几何、拓扑乃至语义信息, 近年来基于图的模型表征和检索方法受到了更多关注[22-23].典型的用于CAD模型检索的工作有属性邻接图[24-27]、完全二分图[28]、扩展特征树[29]等描述子方法.这些基于图的检索方法尽管可以采用各种"图结构"较好地表征模型的几何、拓扑乃至语义信息, 但最终都要通过繁琐的图匹配来实现对应模型间的相似性比较, 十分复杂而耗时, 因此这些检索方法效率很低.虽然有文献[24, 27]对CAD模型用向量化表征在一定程度上可提高匹配和检索效率, 但其只能表达模型的整体形状, 当模型较大型且复杂时, 其局部细节特征描述能力不足, 局部特征信息不突出.检索精度和检索效率存在一定程度的矛盾.徐静等提出了一种基于装配结构相似的零件三维模型检索方法[30], 借鉴化学符号表示零件功能表面、相对位置、朝向以及面与面之间拓扑关系, 并对装配结构进行编码, 建立检索机制, 但随着零件复杂程度增加编码变得十分庞杂.近来朱文博等[31]利用机械零件形状和工艺的特点, 将复杂的机械零件拆分成若干相对简单的形体, 随后再进行匹配检索.然而有些零件形状非常复杂, 使得拆分较困难, 而且拆分后可能破坏形状的完整性, 因此要使该方法具有更广泛的适应性, 还需后续更深入地研究.皇甫中民等[32-33]提出一种基于图谱及空间词袋表征的CAD模型层次特征描述子构建和检索方法, 同时基于图索引过滤机制对三维CAD模型局部检索方法进行了研究.

现有的三维模型检索方法大多关注网格模型.然而, 在制造业中三维实体模型更有可能重用.构造立体几何(Constructive solid geometry, CSG)和边界表示法(Boundary representation, B-rep)是两个流行的三维实体模型描述手段. CSG允许建模者创建一个复杂的表面或用布尔操作合成对象. B-rep是通过一定的限制表示形状的实体建模方法.一个实体集连接表面元素、实体和非实体之间的边界为一体.由于产品模型数据交换标准(STEP)在一个产品的生命周期提供了一种机制来呈现和交换数据, 不同的B-rep模型用STEP很容易交换.鉴于一个三维实体模型的CSG描述是不唯一的, 通常用B-rep表示和分析实体模型[34-35].此外, 面邻接图(Face adjacency graphs, FAGs)可以很容易地从B-rep模型建立, 现有的图或子图匹配可以用于三维模型的形状比较. FAGs是一个有序对是一组用其属性描述模型表面的顶点集, Ef是一组用其属性描述模型边的边的集合.因此, 一些基于FAGs的三维实体模型检索方法被提了出来[24, 36-39].

然而, 在一个实际的复杂模型中观察到的数以百计的面, 以及其有限的面粒度(如多边形平面和圆柱面), 产生的FAGs具有很大的规模和很高的复杂性.最近提出的解决这个问题的方法是分割三维实体模型为一组大粒度的面区域以取代CAD模型的面[40-41].在三维模型被分解为一组面区域后, 三维形状检索的另一个任务是面区域之间的形状匹配.研究者将区域属性代码引入表示CAD模型的面区域. CAD模型主要是由常规的几何面(如平面、圆柱、圆锥和球体)构成, 机械零件的拓扑结构取决于邻接面的类型, 对CAD模型面和区域描述是可行的.此外, 区域属性代码很容易创建, 并且区域代码的比较比子图匹配的模型形状比较要快.于是, 区域属性代码相似性就是两个比较模型之间的相似性.在面区域方法中, 三维分割对三维形状检索是必不可少的, 因为它能用增加模型元素的粒度来明显降低CAD模型的复杂性, 并且提取的面区域通常包含一些有效模型比较的语义信息[30].尽管如此, 三维分割本身的巨大工作量却也无法回避.本文提出的功能表面划分零件与面区域方法相类似, 重要形式概念确定的关键结构关注关键"分割", 可以有效地减少分割带来的工作量, 提高检索效率.

零件功能表面具有功能和结构的双重属性, 从功能上讲, 功能表面直接体现零件的基本功能; 从几何上讲, 功能表面是实现零件基本功能的最小造型单元, 这些功能表面及其空间布局决定了零件功能的物理结构.因此, 在相似零件检索过程中, 可只用功能表面及其相互关系作为评价零件相似性的特征.

本文拟在功能表面及其相互关系构成的零件工程图结构模型映射的形式背景上研究概念格因子, 进而找出反应零件本质特征的关键结构, 以此提高零件模型检索的效率.

图 1  几个常用零件功能表面的视图表达

图 2  零件工程图结构模型

图 3  零件工程结构模型图 1(a)的概念格

概念格理论是一种有效的数据分析和知识处理的工具, 在人工智能的许多研究领域已经被成功地运用.但在实际中, 一个中等大小的输入数据集通常可以产生相当大的一组形式概念, 这直接影响着它的应用.本文引入了形式背景布尔矩阵分解的概念, 讨论基于对象概念、属性概念的概念格因子分解的特性, 并提出了概念格因子发现的方法和近似测度的公式, 给出了相应的概念格因子生成算法.通过实例把本文提出的因子分解理论应用于零件模型检索, 优点是可以用较少的结构较高的效率确定被查找的对象.本文进一步扩充了概念格的约简理论(是对概念格无前置条件的约简), 对概念格的研究和应用都有重要意义.

作者简介

吴强

绍兴文理学院计算机科学与工程系副教授.2008年获得上海大学计算机学院控制理论与控制工程专业博士学位.主要研究方向为智能数据处理, 知识表示与知识发现.E-mail:cswq@usx.edu.cn

董雁  

绍兴文理学院机电工程系教授.2005年获浙江大学机械工程专业博士学位.主要研究方向为三维模型检索.E-mail:zsdongyan@tom.com

谢丽萍  

绍兴文理学院机电学院讲师.2008年获得东北师大管理系学士学位.主要研究方向为数据挖掘.E-mail:Lpxie@usx.edu.cn

吴域西  

上海民族乐器一厂技术员, 2017年获得上海大学数码学院硕士学位.本文通信作者.E-mail:Kiriwu@hotmail.com