CAD模型自动语义标注.pdf

第 22 卷第 12 期 2010年 12 月 计算机辅助设计与图形学学报 Journal of Computer Aided Design 修回日期 2010 08 19 基金项目 国家自然科学基金 50805122 国家 八六三 高技术研 究发展计划 2007AA04Z184 张 欣 1985 男 博士研究生 主要研究方向为模式识别 三维模型搜索 莫 蓉 1957 女 博士 教授 博士生导师 主要研究方向为协同设计 宫中伟 1985 男 博士研究生 主要研究方向为复杂零件的三维建模 连 鑫 1984 男 硕士研究生 主要研 究方向为计算机集成制造 CAD模型自动语义标注 张 欣 莫 蓉 宫中伟 连 鑫 西北工业大学现代设计与集成制造技术教育部重点实验室 西安 710072 zhangx0325 hotmail com 摘要 为了解决基于关键字检索方式难以获得符合设计意图的 CAD 模型的问题 通过对 CAD 模型自动添加语义 标签来改进传统关键字方式检索 CAD 模型的准确性 首先提出一种利用属性图比较 CAD 模型形状相似性的算法 根据图的邻接矩阵及顶点属性构造图顶点集的序列 通过动态编程方法求出图的最大公共子图 得到 CAD 模型之 间的形状相似度 然后根据求出的未知模型与已知模型之间的形状相似度 利用概率方法实现对未知模型的自动语 义标注 实验结果表明 采用文中方法可以使基于关键字的检索方法具有搜索形状相似模型的功能 在很大程度上 改进了传统关键字方式检索 CAD 模型的准确性 关键词 语义标签 自动标注 CAD 模型检索 设计意图 中图法分类号 T P391 Automatic Semantic Tagging of CAD Models for Retrieval Zhang Xin Mo Rong Gong Zhongwei and Lian Xin K ey L aboratory of Contemp orary Design and Integrated Manuf acturing Technology Ministry of Education N orthwestern Polytechnical University Xi an 710072 Abstract T he traditional text based search method for CAD models often obtain searched results that may not satisfy with user s design intent To solve this problem a new method is proposed to improve the precision of the text based search by automatically assigning semantic tags to CAD models First a method based on attributed graph for determining the shape similarity of the CAD models is introduced A sequence of graph nodes is created based on the adjacent matrix of graph and attributes of nodes The maximum common graph representing the shape similarity of models is calculated by dynamic programming with the sequence of the graph nodes Then probability method is used to tag the CAD models automatically according to the similarity between the models T he experiments show that the text based search for CAD models with semantic tags could enable the users to more accurately locate the models with similar shapes and the user s design intents can be satisfied Key words semantic tag automatic tagging CAD model retrieval design intent 随着企业中 CAD CAM 系统的普及 三维 CAD 模型在工程界得到了越来越广泛的应用 据保守估 计 80 以上的新产品都不是从零开始设计的 而是 在原有产品模型的基础上修改得到的 CAD 模型蕴 含了丰富的设计知识 如何快速 准确地找到符合用 户设计意图的三维 CAD 模型 帮助用户重用已有 CAD 模型的设计知识 以提高产品设计质量 缩短 新产品的设计周期 已成为当前国内外的热点研究 课题 迄今为止 企业中 CAD 模型的检索仍然大都 停留在基于关键字 编码的传统检索方式上 这种检 索方式由于受到命名规则等一些主观因素以及有些 复杂 CAD 模型很难用文字来充分描述的影响 使 得这种检索方法虽然简单 易于实现 但是检索可靠 性不高 因此一些学者提出了基于形状的 CAD 模 型检索方法 基于形状的 CAD 模型检索方法可以 分为两大类 模型整体形状检索和模型局部形状检 索 模型整体形状检索要求检索模型与查询模型整 体几何形状相似 模型局部形状检索要求检索模型 与查询模型具有某一个或某几个相似局部结构 无 论是模型的整体检索或者局部检索 首要问题是比 较模型的 相似性 而模型的相似性比较算法主要 分为形状描述符的提取以及形状描述符的比较两 部分 对于模型整体检索而言 目前三维模型形状描 述符的提取方法有三维模型投影方法 1 基于球射 线方法 2 形状分布方法 3 和 Reeb 图方法 4 等 形 状描述符的比较方法主要是利用数学变换将形状描 述符转换为可比较的向量 如球面调和 2 球面小 波 5 等 然而上述算法处理的对象是三角网格模型 并没有充分利用 CAD 模型的拓扑结构知识 针对 CAD 模型相似性比较的算法有拓扑不变量算法 6 特征向量距离算法 7 模型依赖图近似匹配算法 8 以及基于图的序列化算法 9 等 基于图的序列化算 法检索的结果要优于其他类算法 但是该算法在比 较图的相似性时没有考虑模型面之间的位置关系 例如平行 垂直 共轴等 因此该算法还有待进一 步改进 而对于模型局部的检索 文献 10 提出了一 种尺度空间分解方法来提取模型的局部特征 文献 11 利用带有属性的 Reeb 图来实现模型的局 部比较 文献 12 利用子图同构来实现 CAD 模型 的局部匹配 文献 10 11 针对的都是三角网格模 型 它们都需要基于一个尺度函数对模型进行分解 这样会导致分解的模型子部分并不是 CAD 模型的 典型结构特征 文献 12 是一种精确的 CAD 模型 局部匹配算法 它可以检索到具有相同结构特征的 CAD 模型 但是在实际应用中 模型的局部结构特 征不可能完全相同 会受到一些辅助特征 如倒角 倒边等 的影响 因此该算法应用范围非常有限 尽管基于形状的 CAD 模型检索方法可以很好 地解决文字难以准确表达 CAD 模型的问题 但是 很多 CAD模型虽然形状相似 其功能 用途或者加 工方法 也就是 CAD 模型包含的语义知识却相差 甚远 例如 对于 CAD 模型上的孔结构来说 尽管 孔的尺寸相同 但是由于孔的加工精度不同 那么孔 的加工方法则会差别很大 利用关键字可以很好地 区分这类包含不同语义知识的 CAD 模型 因此本 文希望依据模型形状相似的特性对 CAD 模型自动 添加语义标签 使传统基于关键字的检索方式也具 有基于模型形状检索的功能 以提高关键字方式检 索 CAD 模型的准确性 本文利用属性图来表示 CAD 模型的几何和拓扑信息 并采用图的序列化方 法比较图的相似性 以得到 CAD 模型之间的形状 相似度 其次 依据 CAD 模型之间的相似度 利用 概率方法自动标注 CAD 模型 1 CAD模型相似性比较算法 属性图可以完全表示 CAD 模型的拓扑和几何 信息 那么模型的形状相似性比较就可以转化为图 的相似性比较 然而由于图的子图同构问题是一个 NP 完全问题 只有对顶点非常少的图才可求解 所 以文献 9 提出了利用图的序列化算法来比较属性 图的相似性 但是其没有考虑图顶点对应模型面之 间的位置关系 例如平行 垂直 共轴等 本文提出 了一种 CAD 模型形状相似性比较的新方法 其主 要步骤如图 1 所示 图 1 CAD 模型相似性比较算法流程 2163 第 12期张 欣 等 CAD 模型自动语义标注 1 1 CAD 模型的图表示 CAD 模型包含了丰富的拓扑和几何信息 如何 用可比较的描述符来表示这类信息 已成为 CAD 模型相似度比较的首要问题 本文利用属性邻接图 attributed adjacency graph AAG 来表示 三维 CAD 模型 其定义为 G V E 其中 1 V 为图 G 的顶点集 CAD 模型中的每一个 面 fi在图G 中都有一个唯一的顶点 Vi与之对应 2 E 为图 G 的边集 对于模型中的任意 2 个相 邻面 fi fj 图 G 都会有唯一的一条边 Ei j与之对应 3 为图 G 的顶点属性集 它表示 CAD 模型 面的属性 例如面的几何类型 平面 球面 圆柱面 等 面的面积 面的边数以及面的边长等 4 为图 G 的边属性集 它表示 CAD 模型相 邻面的位置关系 例如平行 垂直 同轴或者平行等 如图 2 所示 CAD 模型可以用图 2 右边的邻 接图 G 来表示 图 2 CAD 模型及其对应 AAG 1 2 图的序列化 当 CAD 模型用 AAG 表示后 CAD 模型的相 似性比较问题就转化为图的子图匹配问题 图的子 图同构问题是一个典型的 NP 完全问题 这主要是 因为图的顶点是无序的 而顶点在匹配的过程中需 要多次反复遍历 如果能够对 AAG 的顶点集建立 一个唯一的序列 那么图的子图同构问题就简单了 很多 本文试图根据 AAG 的顶点 边的属性以及顶 点之间的拓扑关系 对 AAG 的顶点集进行排序 文献 13 提出利用 AAG 的邻接矩阵 A来确定 图顶点集的序列 它可以最大程度地保证序列中的 相邻顶点在图中具有相邻的边 其定义向量 x 为顶 点集的序列 并且该向量 x 满足 gmax x V 1 i 1 V k 1 A i k A i 1 k x 2 k 其中 xk为x 的第k 项 表示顶点集 V 的第k 个顶点 的序列值 文献 13 指出 当 x 为邻接矩阵 A 的最 大特征值对应的特征向量时 g x 可以取得最大 值 通过该方法求出图 G 的序列x 可以最大程度上 使序列中的相邻点 Vi Vi 1对应的 CAD 模型的面 相邻 这样可以使序列中的顶点集包含更多的信息 有助于图顶点的匹配 然而文献 13 只利用了图的 邻接矩阵计算图的序列 并没有考虑图顶点属性的 影响 例如 对于表示 CAD 模型的 AAG 来说 如果 两个图的顶点代表着不同的类型 一个为平面 一个 为圆柱面 那么这两个顶点肯定不匹配 本文根据 这一特性对 x 做出一些修改 使尽可能相同类型的 顶点在序列 x 中聚集 如在实验中 由于 CAD 模型 包含的平面比较多 因此本文认为对应平面的顶点 的序列值要大于对应圆柱面的顶点序列值 其具体 排序过程步骤如下 Step1 定义一个链表 L 用来记录 AAG 中顶点的访问 序列 其中 Lk为 L 中的第 k 个顶点 初始化 L0 Vi 其中 Vi max x Step2 查找顶点 L0在 AAG 中的邻集 NL0 i L0 Vi E 那么链表 L 中的第二个点 L1 Vi max x V NL0 Step3 经 过 k 步 迭 代后 链表 长 度为 k 1 如 果 k 1 n 其中 n 为属性图的顶点数 则排序结束 否则 求顶 点集的补集 C i Vi L Vi V 令 AAG 新的顶点集 V C 并重复上述计算过程 直到 AAG 中的所有顶点都被 访问到 图 3 所示为图 2中的 AAG 按照上述方法的排 序结果 图 3 AAG 的排序结果 1 3 图的相似性比较 本文计算图之间的距离公式为 d G1 G2 1 2 mcs G1 G2 G1 G2 1 其值越小 表示图越相似 其中 函数 为图的顶点 个数 mcs G1 G2 为图 G1和 G2的最大公共子图 它是式 1 的关键 本文通过动态编程 DP 方法求出 排序后的图之间的编辑距离 EditDis G1 G2 并将 式 1 转化为 2164 计算机辅助设计与图形学学报 第 22 卷 d G1 G2 1 G1 G2 EditDis G1 G2 G1 G2 动态编程 DP 方法比较成熟 本文不再赘述 本 文在实验中计算 AAG 的编辑距离 EditDis G1 G2 的伪代码如下 初始化替换 删除和插入的代价 Rep lCost 1 DelCost 1 InsCost 1 G1 G2 为图 G1 G2的顶点数 for i 1 G1 for j 1 G2 s1 i s2 j 分别表示排序后的图 G1第 i 个和 G2 第 j 个顶点 if s1 i s2 j if IsCompatible s1 s2 i j IsCompatible为兼容函数 Repl 0 else Repl ReplCost Repl 为替换代价 end else Repl ReplCost end D i 1 j 1 min D i j Repl D i 1 j DelCost D i j 1 I nsCost end end 那么图的编辑距离 EditDis G1 G2 D i 1 j 1 其中函数 IsCompatible 为兼容函数 判断 该顶点是否与已有的 mcs G1 G2 中的顶点保持兼 容 例如 假设图 G1 G2的最大公共子图 mcs G1 G2 V 1 i V 1 i 1 或者 mcs G1 G2 V 2 i V 2 i 1 其 中f V 1 i V 2 i f V 1 i 1 V 2 i 1 当遇到一对新的顶 点 V 1 i 2 V 2 i 2时 函数 IsCompatible 判断顶点 V 1 i 2 与顶点集 V 1 i V 1 i 1 中的位置关系是否与 V 2 i 2与顶 点集 V 2 i V 2 i 1 的位置关系相同 如果相同 则加入 这对顶点到图的最大公共子图中 即mcs G1 G2 V 1 i V 1 i 1 V 1 i 2 或者 mcs G1 G2 V 2 i V 2 i 1 V 2 i 2 2 CAD 模型自动标注方法 当 CAD 模型之间的距离确定后 模型的自动 标记问题就可以简化为聚类问题 已知一些已经标 记过的 CAD 模型 根据定义的模型 距离 将未标 记模型归为其中某一类 本文采用概率的方法自动 标记 CAD模型 本文采用已知一些典型模型或者模型的一些 典型结构来对大量的 未知的 CAD 模型进行整体 和局部的自动语义标注 假设已知 CAD 模型的标 签集为 1 2 其中 D M M j 为模型 M 和M j 的距 离函数 即 D M Mj d GM GMj 既然模型 M 和 M j 的相似度为p M M j 那么本文有理由认为模 型 M 标记为 i 的概率为 p i M p M Mj p i Mj 这是根据单个模型 M j 得出模型 M 标记为 i 的概 率 其结果可能会具有一定的随机性 如果考虑整个 模型集 对M 的影响 那么可以很大程度上提高标 记的可靠性 因此本文定义 p i M n j 1 p M M j p i Mj 同理 可以计算模型 M 标记为其 他标签的概率 3 实验及结果分析 我们以 Design Repository 模型库 中的 CAD 模型为研究对象 来验证本文提出的模型比较算法 以及 CAD模型自动标注结果 3 1 CAD 模型形状相似度比较 根据第 1节提出的CAD 模型相似性比较算法 图 4 列出了 5 类模型的比较结果 可以看出实验结 果基本上可以反映出 CAD 模型的相似程度 由于 本文在第 1 3 节求图的最大公共子图 mcs G1 G2 时 兼容函数 IsCompatible 只考虑了 CAD 模型面 的类型以及面之间的位置关系 因此该算法目前不 能区分具有相同拓扑结构而几何外形有差异的 CAD 模型 如图 4中距离为 0 的模型 2165 第 12期张 欣 等 CAD 模型自动语义标注 www designrepository com 图 4 CAD 模型相似性比较 3 2 模型自动语义标注结果 本文从 Design Repository 模型库中的一些典 型类别中提取一个模型作为已知的标记模型 如 图 5a 所示 并对模型库中剩余的 CAD 模型进行自 动语义标记 图 5b 所示为一些 CAD 模型自动标注 的标签以及该标签属于模型的概率 可以看出 实验 结果基本上符合人的主观判断 图 5 CAD 模型自动语义标注 3 3 算法的准确性比较 本文用查全率 查准率 Recall Precision 曲线 来验证算法的准确性 图 6 所示为本文算法与其他 4 类算法的比较 其中 MDG 表示模型依赖图近似 2166 计算机辅助设计与图形学学报 第 22 卷 匹配算法 ITV 表示特征不变量算法 Eigen Brep 表示基于特征向量距离算法 MDG ITV 和 Eigen Brep 算法的查全率 查准率曲线来自文献 14 ED 表示文献 9 提出的算法 从图 6 中可以看到 本文 提出的基于语义标签的 CAD 模型关键字检索方法 在准确性方面优于其他 4 类算法 图 6 5 种算法的查准率 查全率曲线比较 4 结 语 本文通过对 CAD 模型自动添加语义标签 解 决了关键字方式难以准确表述 CAD 模型问题 使 基于关键字的检索方法同样也可以检索到具有整体 或局部相似的 CAD 模型 在很大程度上改进了传 统关键字方式检索 CAD 模型的准确性 然而 本文 算法仍存在一些不足的地方 在比较 CAD 模型时 本文主要是通过比较模型的拓扑结构 而对模型的 几何信息考虑的比较少 这样会造成模型相似性比 较的程度相对粗糙 算法的准确性容易受到 CAD 模型辅助特征的影响 因此 我们下一步工作的重点 就是在 CAD 模型比较时 更多地考虑模型几何信 息对模型比较的影响 进一步完善本文算法 参考文献 References 1 Chen D Y Tian X P Shen Y T et al On visual similarity based 3D model retrieval J Computer Graphics Forum 2003 22 3 223 232 2 V ranic D V An improvement of rotation invariant 3D shape based on functions on concentric spheres C Proceedings of the IEEEInternational Conferenceon Image Processing Washington D C IEEE Computer Society Press 2003 2 757 760 3 OsadaR FunkhouserT ChazelleB etal Shape distributions J ACM Transactions on Graphics 2002 21 4 807 832 4 Hilaga M Shinagawa Y Kohmura T et al T opology matching for fully automatic similarity estimation of 3D shapes C Computer Graphics Proceedings Annual Conference Series ACM SIGGRAPH New York ACM Press 2001 203 212 5 Schr der P Sweldens W Spherical wavelets efficiently representing functions on the sphere C Proceedings of the 22ndAnnualConferenceonComputerGraphicsand Interactive T echniques New York ACM Press 1995 161 172 6 Mcwherter D Peabody M Regli W C et al Solid model databases techniques and empirical results J Journal of Computing and Information Science in Engineering 2001 1 4 300 310 7 Peabody M Finding groups of graphs in databases D Philadelphia Drexel University 2002 8 Cicirello V A Regli W C An approach to a feature based comparison of solid models of machined parts J Artificial IntelligenceforEngineeringDesign Analysisand Manufacturing 2002 16 5 385 399 9 Zhang Xin Mo Rong Shi Yuan et al String based CAD models similarity assessment al