基于形式概念分析的3D零件结构模型关键结构确定方法

吴 强 谢丽萍 董 雁

绍兴文理学院，绍兴，312000

0 引言

目前，工程图纸检索主要是基于文本的检索，它充分利用了几何图元的属性和这些图元之间的空间关系。Berchtold等［1］开发的S3系统是一个支持局部相似性检索和基于文本的图纸检索系统。S3系统检索主要依靠图形轮廓的匹配，而忽略了空间关系，使得此检索方法不适合于复杂的图形。Müller等［2］提出了一种新的随机模型的检索方法，使用的是伪二维隐马尔可夫模型（P2DHMM），此方法仅支持简单的图形检索，不适合于大量的图形。Park等［3］提出了一种基于关键形状特征的复杂二维机械零件图检索方法，但该方法很难用于处理大量的工程图纸。

工程图纸检索的关键是如何迅速、准确地完成相似度计算，而相似度计算与图纸特征的提取密 切相 关［4－6］。 Wang 等［7］基 于 图 匹 配 的 方 法 对零件图的检索进行了研究，其方法是，首先提取图形的结构和形状的特征，然后将图形匹配问题转换为图和子图同构问题。子图同构问题被证明是一个NP完全问题，现有解决方案中的算法不仅时间复杂度相当高，且算法的性能不稳定。Wang等［7］提出了一种近似图形匹配方法，即基于任务嵌套分配的图形相似性匹配算法。该方法分为两个步 骤：首 先，使 用 EMD（earth mover’s distance）算法计算顶点之间的距离矩阵，然后根据距离矩阵使用EMD算法得到顶点间映射匹配矩阵。实验表明，该方法可以检索不同相似程度的图纸，并且搜索精度和搜索的效率满足实际应用的要求。该方法不足之处在于其计算比较粗略。

徐静等［8］和董雁等［9］提出了一种基于结构相似的零件工程图检索方法。该方法将零件工程图中的几何图形标记为功能表面，根据是否共边、共点或点在边上，判断功能表面是否拓扑相连，并进一步确定功能表面间的位置关系，生成零件2D结构模型。通过对视图结构模型公共顶点、公共边约束定义的“并”运算，构造零件3D结构模型。借鉴化学数据库中化合物的线性符号表示法生成零件工程图结构码。以零件工程图子结构布尔模型表达检索要求，通过查询子结构码与分支结构码的匹配，实现零件工程图的子结构检索；以零件工程图表达检索要求，通过视图结构码的整体匹配，实现零件工程图的示例检索；通过零件工程图3D结构码与零件三维模型结构码的匹配，实现零件工程图的模型检索。这种方法要求使用者必须熟悉结构码，编码基本上是抽象的，在处理复杂和大量的工程图纸时，逐一对比耗时且缺乏效率。

本文在文献［8］的零件工程图3D结构码的基础上，根据其构成的特点（功能面和位置关系）给出其基于概念格的表示方法，并利用信息熵确定功能面和位置关系的重要概念对。在此基础上，结合结构码，发现零件关键结构。

1 零件工程图结构模型

文献［8］给出的零件工程图结构模型是基于功能表面分类的。功能表面的基本类型为平面、圆柱面、圆锥面、球面和孔。功能表面视图中大写字母P、C、H和S分别表示平面、圆柱面、孔和槽，小写字母w、k、h和r分别表示螺纹连接、平键连接、半回转面和环结构。图1为几个常见零件和它的功能表面视图。

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

这里功能表面间的拓扑关系是通过连接边的凹凸性来表示的，凹边用“0”标记，凸边用“1”标记。若两相连功能表面均为回转面时，拓扑关系通过回转面是内表面还是外表面来定义，并用“！”标记。零件工程图中判断功能表面是否拓扑相连包括共边、共点或点在边上三个条件。

功能表面间的位置关系包括方位关系和领域关系。方位关系通过方位矢量的空间方位关系来定义，有平行（∥）、同轴（⊙）、垂直（⊥）和偏斜（∠）；领域关系指功能表面占据的空间区域间的关系，领域关系的种类与方位关系类型有关，二元领域关系见表1［8］。因为平面功能表面占据区域的长度为0，所以平面与回转面间的相遇、重叠、共点关系合并为相遇。两垂直平面之间不定义二元领域关系，并用“！”标记。符号“！＃”表示两功能表面拓扑相连，而符号“＃”则表示拓扑不相连。符号“？”表示功能表面间的位置关系不能通过单个视图确定。

将零件工程图的功能表面进行标记，再根据判断拓扑相连功能表面的几何条件、功能表面间位置关系的确定方法以及分布关系的定义，可以得到零件工程图结构模型［8］。图2即为图1的工程图结构模型。

图2 图1的3D零件结构模型

2 零件工程图结构模型到形式概念格的映射

零件工程图组成部分主要是功能表面和位置关系。依据形式概念分析的特性，我们可以以此构建零件工程图结构的形式背景，进而构建零件工程图的概念格（有关形式概念格的具体内容可参见文献［10］）。

零件工程图结构模型的功能表面与其关系可以用互相抵达来表明，设SourceSurface、Relation和TargetSurface是PG（Part Graph）中G的三个组成部分，用g.source、g.relation和g.target分别表示。I是构成形式背景的对集（Object，Attribute），有

映射是PG的关系目标可以成为另一个关系的源CG（Concept Graph）概念的传递。该传递产生隐式映射的推理：

映射算法如下：

该算法的工作原理是最初设定每个三元组的目标概念为MovingTarget和FixedTarget，然后调用FormContext通过所有的三元组迭代，形成了相应的形式概念分析的（Object，Attribute）对，每次MovingTarget匹配一个三元组的目标概念。二元转换是由递归调用FormContext形成的，对当前的源概念设置MovingTarget，而留下FixedTarget不变。

3 形式概念分析与零件关键结构

形式概念分析也称为形式概念格。设（X，Y，I）表示一个形式背景。（X，Y，I）的对象、属性对（A，B）（A⊆X，B⊆Y）成为一个形式概念的条件是当且仅当A↑＝B并且B↓＝A，其中A↑＝｛y∈Y｜x∈X∶（x，y）∈I｝，B↓＝ ｛x∈X｜y∈Y：（x，y）∈I｝，分别是A中所有对象的公共属性集（称为形式概念（A，B）的内涵）和B中所有属性的公共对象集（称为形式概念（A，B）的外延）。背景（X，Y，I）的所有形式概念集合表示为b（X，Y，I）。b（X，Y，I）的超概念 －子概念偏序小于等于构成（X，Y，I）的概念格。图2的形式背景和概念格如表2和图3所示。

表2 图2c的形式背景

图3 图2c的概念格

形式概念分析的基点是形式背景，它的主要研究对象是形式概念和概念格。概念是外延和内涵的统一体，概念格在本质上描述了对象和属性之间的联系，表明了概念之间的泛化和例化关系，而它的Hasse图则实现了对数据的可视化。在我们实现了用概念格表示零件结构后，概念格的关键部分（重要概念或称核概念）就是零件结构的重要部分。由于零件的不同形变关系直接关系到零件的功能及作用，因此，零件功能表面的位置关系的重要程度应该是有差别的，或者说这些位置关系对于形成整个零件来说所起的作用是不同的。完成了零件工程图结构模型到形式概念格的映射后，这种差别或不同就可以在属性上体现出来。

在文献［11］中，针对属性重要性的不同，给内涵引入权值ω（0≤ω≤1）以标识内涵的重要性而建立了一种新的概念格结构——加权概念格。如果一个形式背景可表示为四元组（X，Y，I，W），Y＝ ｛y1，y2，…，yn｝，W为Y中属性yi（i＝1，2，…，n）的权值集合，W＝ ｛ω1，ω2，…，ωn｝，W标识了属性yi的重要程度。若（A，B，ω）为（X，Y，I，W）上的一个任意三元组，如果（A，B）是一个形式概念，ω＝W（B）为属性集B的权值且0≤ω≤1，称（A，B，ω）为（X，Y，I，W）上的一个加权概念。A称为加权概念的外延，B称为加权概念的内涵，其超概念 －子概念与一般概念格相同。

给定一个值θ∈V（V为阈值空间）可得到B（X，Y，I）的部分形式概念Bθ（X，Y，I）＝ ｛（A，B）∈B（X，Y，I，W）｜ω≥θ｝，Bθ（X，Y，I）可以看做是重要形式概念的集合。

信息熵可表示数据的统计特征，可以用来描述信息源提供的平均信息量，也可以描述信息源的平均不确定性。参照文献［12］，信息熵的相关定义如下。

定义1 设P在U上导出的划分为X＝｛X1，X2，…，Xl｝，则P在由U的子集组成的σ的代数的概率分布为

定义2 属性集合P的熵E（P）为

根据系统熵的计算公式，当系统可能处于几种状态的概率相等时，即P（Xj）＝1/m时，系统熵 值 最 大，即E（P（X1），P（X2），…，P（Xn）≤E（1/m，1/m，…，1/m）＝log2m。

对于给定的形式背景，各属性特征取值的概率大小客观隐含着信息量的大小，由于形式背景中各对象具有独立性，其提供的共同属性的信息量具有可加性，因此形式背景中某属性的信息量为各对象提供的属性信息之和，即某属性信息熵的多少隐含了其不确定性程度。对于yi（yi∈Y，i＝1，2，…，n）在X上划分出的等价类Xj（Xj⊆X，j＝1，2，…，m），P（｛yi｝/Xj）表示对象为Xj元素，具有属性yi的概率，E（｛yi｝）表示Xj提供给属性yi的平均信息量，其可以表示yi的重要性：

在形式背景中属性集Y＝ ｛y1，y2，…，yn｝，对于 （A，B，ω），若B＝ ｛yi｝（i＝ 1，2，…，n），则E（B）＝ωi。容易看出，在｜X｜＝m的形式背景中，最大熵E（｛yi｝）max＝log2m。使用最大熵E（｛yi｝）max对熵值进行归一化处理，有

对于概念格的多属性内涵权值的计算，既要能反映多属性内涵的总体重要程度，又要考虑构成内涵的重要性存在偏差，可进一步有效地反映和提取用户需求的知识。

定义3 对于（A，B，ω），若B＝ ｛y1，y2，…，yk｝，y1，y2，…，yk∈Y，W（yi）＝ωi（i∈1，2，…，k），则A的内涵B的重要性权值定义为

重要性标准偏差定义为

根据偏差的特点，定义D（B）＝0（n＝1）。

在确立了形式概念的权值和偏差后，对于一个由零件工程图结构模型转化而来的形式背景，我们可以求出属性的信息熵，并进行归一化处理。对于一般形式概念，属性内涵权值和重要性偏差值由数据特征值均值、标准差计算。用户可以输入α和β（α、β分别为属性内涵和重要性偏差的阈值），通过判断生成重要概念集合。由这个概念集合的概念对（功能面，位置关系），我们就可以得到零件的关键结构。

关键结构的概念格算法如下：

4 零件关键结构获取实例

为验证本文提出方法的有效性，笔者就文献［8］的11个零件工程图结构模型中的6个进行了逐一计算，图4～图9是转换后的概念格和各节点内涵权值及重要性偏差值。其中，我们将得到的任意概念格节点设为（A，B）。如果设β＝0，α取各自最大值，可以得到如表3所示的三维零件结构模型的重要概念与关键结构。

图4 微调螺杆概念格各节点内涵权值及重要性偏差值

图5 拉杆轴概念格各节点内涵权值及重要性偏差值

表中“关键结构”表示的整个代码是取自文献［8］的零件工程图结构码，加黑的部分是用本文方法计算出的关键结构。从表3中可以看出，对于大部分的零件，本文方法不仅能确定重要位置关系（重要内涵），也能确定构成这种关系的功能表面（概念对象），进而确定出零件的关键结构。当然，对于完全对称的毫无“特色”的零件，本文的方法也表现出了局限性（如拉杆轴）。究其原因是这些问题中，位置关系（概念内涵）权值完全相同，也就是说零件图本身提供的信息不足以将其区分，因此，只要设计者提供进一步的信息，这个问题就会迎刃而解。

图6 摆轴概念格各节点内涵权值及重要性偏差值

图7 波导开关转子概念格各节点内涵权值及重要性偏差值

5 结束语

本文在零件工程图结构模型系统框架下利用信息熵和形式概念分析技术从模型提供的位置关系的不同重要性信息入手，针对文献［7］给出的几个不同类型零件对关键结构进行分析，总结出一般零件结构图关键结构的确定方法，方便设计者快速准确地掌握设计要点，为今后最大限度地降低搜索零件制图过程中的重复性劳动奠定了理论基础。

图8 双键套概念格各节点内涵权值及重要性偏差值

图9 拔叉概念格各节点内涵权值及重要性偏差值

在下一步的工作中，我们将用本文的方法来处理CAD 3D零件图的检索，开发相应的系统。为了进一步提高所提出方法的实用性，可以引入多属性群决策中基于数据稳定性与主观偏好的综合熵权方法，以期对无“特色”零件处理有较好的效果。

［1］ Berchtold S，Kriegel H.S3：Similarity in CAD Database Systems［C］∥ACM SIGMOD Int.Conf.on Management of Data.Tucson：ACM Press，1997：564－567.

［2］ Müller S，Rigoll G.Searching an Engineering Drawing Database for User－specied Shapes［C］//Proceedings of the Fifth International Conference on Document Analysis and Recognition，ICDAR ’99.Bangalore：IEEE，1999：697－700.

［3］ Park J，Um B.A New Appaoach to Similarity Retrieval of 2DGraphic Objects Based on Dominant Shapes［J］.Pattern Recognition Letters，1999，20：591－616.

［4］ Zhou L，Xie Q，Ding Q.Engineering Drawing Retrieval Based on Graph Matching［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，2008，40（3）：354－359.

［5］ 柳玉，贲可荣.基于属性重要度的案例特征权重确定方法［J］.计算机集成制造系统，2012，18（6）：1230－1235.Liu Yu，Ben Kerong.Weight Coefficient Determination for Case Feature Based on Attribute Importance［J］.Computer Integrated Manufacturing Systems，2012，18（6）：1230－1235.

［6］ 张胜文，丁玉玲，王贵成，等.基于特征相似性的船用柴油机关键件CAD/CAPP/CAM 集成技术［J］.计算机集成制造系统，2012，18（2）：291－297.Zhang Shengwen，Ding Yuling，Wang Guicheng，et al.CAD /CAPP/CAM Integrated Components Based Technology for Marine Diesel Key on Feature Similarity［J］.Computer Integrated Manufacturing Systems，2012，18（2）：291－297.

［7］ Wang P，Jiang S.An Engineering Drawing Retrieval Method Based on Nested Assignment Algorithm［J］.Journal of Computational Information Systems，2013，9（2）：713－720.

［8］ 徐静，董雁.零件工程图结构检索方法［J］.机械工程学报，2011，47（20）：191－198.Xu Jing，Dong Yan.Structure Retrieval Method for Part Engineering Drawing［J］.Journal of Mechanical Engineering，2011，47（20）：191－198.

［9］ 董雁，谭建荣，张树有.基于符号的零件造型方法研究［J］.中国机械工程，2003，14（9）：773－776.Dong Yan，Tan Jianrong，Zhang Shuyou.Research on Part Modeling Methods Based on Symbols［J］.China Mechanical Engineering，2003，14（9）：773－776.

［10］ Bernhard G，Rudolf W.Formal Concept Analysis.Mathematical Foundations［M］.Berlin：Springer，1999.

［11］ Zhang S，Guo P，Zhang J，et al.A Completeness A－nalysis of Frequent Weighted Concept Lattices and Their Algebraic Properties［J］.Data ＆ Knowledge Engineering，2012，81/82：104－117.

［12］ 傅祖芸.信息论——基础理论与应用（第2版）［M］.北京：电子工业出版社，2007.