基于蚁群算法的三维CAD模型检索.pdf

第2 3 卷第4 期计算机辅助设计与图形学学报 V 0 1 2 3N o 4 2 0 11 年4 月J o u r n a lo fC o m p u t e r A i d e dD e s i g n C o m p u t e rG r a p h i c s A p r 2 0 11 基于蚁群算法的三维C A D 模型检索 张开兴 张树生 李亮 西j t r 业大学现代设计与集成制造技术教育部重点实验室西安7 1 0 0 7 2 k a i x i n g z h a n g g m a i l c o r n 摘要 为了更好地实现C A D 模型的重用 提出一种利用蚁群算法的三维C A D 模型检索算法 通过提取C A D 模型 的B r e p 信息 将模型用属性邻接图来表示 根据如果2 个C A D 模型存在相似的特征或局部结构 那么C A D 模型对 应的属性邻接图就应存在公共子图这一原理 利用蚁群算法来检测属性邻接图中的公共子图 从而得到2 个C A D 模型相似的局部细节特征 然后通过比较相似局部细节特征对C A D 模型进行相似性评价 实验结果表明 该算法能 较好地实现三维C A D 模型检索 检索性能高于通用领域的检索算法 可以实现C A D 模型设计和制造知识的重用 关键词 重用 蚁群算法 属性邻接图 公共子图 中围法分类号 T P 3 9 1 AM e t h o do f3 DC A DM o d e lR e t r i e v a lB a s e dO i lA n tC o l o n yA l g o r i t h m Z h a n gK a i x i n g Z h a n gS h u s h e n g a n dL iL i a n g K e yL a b o r a t o r yo fC o n t e m p o r a r yD e s i g na n dI n t e g r a t e dM a n u f a c t u r i n gT e c h n o l o g y N o r t h z v e s t e r nP o l y t e c h n i c a lU n i v e r s i t y M i n i s t r yo f E d u c a t i o n X i a n7 1 0 0 7 2 A b s t r a c t T or e u s e3 DC A Dm o d e l sm o r ee f f i c i e n t l y f ln e w3 DC A Dm o d e Ir e t r i e v a lm e t h o db a s e do n t h ea n tc o l o n ya l g o r i t h mi sp r o p o s e di nt h i sp a p e r A tf i r s t aC A Dm o d e li sr e p r e s e n t e db yt h e a t t r i b u t ea d j a c e n tg r a p h A A G w i t ht h eB r e pi n f o r m a t i o ne x t r a c t e df r o mt h em o d e l T h e n t h ea n t c o l o n ya l g o r i t h mi se m p l o y e dt od e t e c tt h ec o m m o ns u b g r a p hi nt h ec o r r e s p o n d i n gA A G so fd i f f e r e n t m o d e l s T h es i m i l a rs u b p a r t sa r eo b t a i n e da c c o r d i n gt ot h ep r i n c i p l et h a tt h ec o r r e s p o n d i n gA A G so f t w om o d e l sh a v ec o m m o ns u b g r a p h si ft h em o d e l sh a v es i m i l a rs u b p a r t s A tl a s t t h es i m i l a r i t yo ft h e m o d e l si sc a l c u l a t e db yc o m p a r i n gt h es i m i l a rs u b p a r t s O u re x p e r i m e n t a lr e s u l t ss h o wt h ep r o p o s e d m e t h o do u t p e r f o r m st h ee x i s t i n gr e t r i e v a lm e t h o d sa n dc a na c h i e v et h ereuseo fd e s i g na n d m a n u f a c t u r i n g K e yw o r d s r e u s e a n tc o l o n ya l g o r i t h m a t t r i b u t ea d j a c e n tg r a p h c o m m o ns u b g r a p h 目前 基于三维模型的产品设计与制造已成为 我国制造业的主流模式 由于产品三维模型具有可 视化 数字化和虚拟化等特点 使其成为产品开发各 环节 C A D C A E C A P P C A M 等 不可或缺的基础 载体 研究和统计分析表明 在新产品开发中 约 4 0 是重用过去的部件设计 约4 0 是对已有设计 部件的微小修改 而只有约2 0 是完全新的设 计 1 因此 如何方便 准确 快速地获取已有产品三 维模型的相似性设计成果 并加以有效重用 是提高 设计效率 缩短产品开发周期的关键之一 在产品的 概念设计 详细设计 工艺 工装设计等各设计阶段 中 通过基于内容的检索技术可以实现企业产品三维 收稿日期 2 0 1 0 0 7 0 7 l 修回日期 2 0 1 0 0 9 1 3 基金项目 国家自然科学基金 5 1 0 7 5 3 3 6 国家 八六三 高技术研究发展计划 2 0 0 7 A A 0 4 2 1 3 7 张开兴 1 9 8 4 男 博士研究生 主要研究方向为C A G D 几何造型与处理 模型检索 张树生 1 9 5 6 一 男 博士 教授 博 士生导师 主要研究方向为C I M S 先进制造技术 计算机图形学 C A G D 李亮 1 9 8 3 男 博士研究生 主要研究方向为计算机图形学 C A G D 万方数据 计算机辅助世汁 图形学学撤 C A D 模型资源的多粒度 精确化 个性化快速聚炎 为复杂产品的数据管理提供基于内容的 维C A D 模型可视化检索新技术 为产品设计过程中各类殴 计成果的重用提供一种全新的支持手段 在C A D 领域 C A D 模型有其自身的特点 如 C A D 模型由曲线和曲面组成 包含很多特征 对称 性比较强 有明显的边界轮麻线等 但由于通J H 领域 的检索算法 2 无法充分地考虑这衅特点 用此将通 用领域的检索算法应川于C A D 模型检索效率不 高而在C A D 模型检索方丽的研究尚处于起步阶 段 文献 4 通过构造C A D 模型特征向量 并将其 作为自组织特征映射神经网络的输入 借助神经 网络进行C A D 模型的A 动聚娄 文献 5 提出通过 计算模型 的面形位码束对模型之I h 不同精度的相 似度i 平价 文献 6 3 提m 利用I 雩I 论巾二分图最优匹配 算法来评价模到之间的相似度 文献 7 则利用扩展 R e e b 刳并附带几何属性来实现C A D 模型整体相似 性比较和模型子部分的对应 义献 8 通过提取 C A D 模型的骨架 将C A D 模型的相似性度揖转化 为对鹰骨架图的相似性比较 现有的检索方法更侧 重C A D 模 I l l 整体外形的棚似性 对模型的局部细 节特征描述不足 但在设计和制造过程中 企业往往 更咒注模型的局部细节特征 只有达到局部特征级 别的牛龟索才能更好地实现参考并重用已有的模型 基于此 本文将通过C A I 模型所包含的局部细节 特征埘萁进行相似性评价 利川一种启发式算 法蚁群算法米检测2 个C A D 模型包含的相似 的局部细节特征 井根据这些相似的局部细节特征 第2 3 茌 接关系作为图的条边 边的类型和n 凹性作为边 的属性 避过属性邻接罔表 下方法 口f 将C A D 模型相 似性比较的问题转换成检测属性邻接罔的公共子斟 的问题来解决下面给出公共子田和最大公共子图 的定义 定义1 公共于图给定图G 吐和G 若图G 与罔G 子图同构 同时 图G 也与网 子图同构 则称图G 是用G 和图G 的公共子圈 记作c s G 岛 定义2 最大公共子罔给定图G 和G 若图 G 是图G 和图G 的公共子圈 且不存在图G 蹦 G 7 也是图G 和圈G 的公共子图 图G7 的节点个数 大子图G 的节点个数 则称 骞 G 是图G 和图G 的 最大公共子图 记作m c s G G 给定2 个C A D 模型 它们对应的特征或者局部 结构可以通过查找2 个属性邻接嘲的公共子罔来获 得 如图1 所示的2 个C A D 模型及其属性邻接图 虽然这2 个模型整体形状不相似 但它们具有一个 如图1a 所示 彳I 同的局部结构 图1b 所示椭圆内节 点形成的图即为2 个属性邻接图的公共子图 同时 也是最大公共子围 鋈溪蓑蒸 通过它的边界 即面的子集 来表示 每一个面义通 过边 边通过点来定义 通过精确描述每个顶点 每 条边和每个曲面 就能精确地描述整个三维C A D 模型 通过提取三维C A D 模型中的Br e p 信息 可将 模型J j 届性邻接图来表示在属性邻接图中 图的每 一个顶点对应C A D 模型的一个面 面的属性 如面 的类型 方向等 作为顶点的屈性 2 个面之问的邻 刚1C A D 模型及其属性邻接强 2 基于蚁群算法的检索 检测2 个图的最大公共子罔的问题是一个N P 完全问题 算法复杂度非常高本文利用一种多项式 时间内的算法 蚁群算法来实现公共子图的检测 万方数据 第4 期张开兴 等 基于蚁群算法的三维C A D 模型检索 6 3 5 蚁群算法是从自然界蚂蚁觅食行为中得到启发而产 生的 是一种基于种群的模拟进化算法 它最初是用 来解决旅行商问题的 本文算法首先通过给定的2 个C A D 模型属性邻接图建立一种关联图 然后利 用蚁群算法实现C A D 模型公共子图的检测 该算 法可以检测出2 个C A D 模型包含的相似的局部细 节特征 2 1关联图 给定2 个图G 和G z 顶点集V 和V 设二者 的关联图为H y 则构建关联图的具体步骤如下 S t e p l 对图G 中的任意一个顶点q V 1 1 i 遍历图G 2 中每一个顶点U V z 1 J m 组成顶点对 t U 若饥与U 具有相同的属性值 则将 7 3 U j 加入关 联图H v 的顶点集y H 作为其一个顶点 S t e p 2 任取关联图H v 中的2 个顶点U H 乱1 U2 和 口H 口1 2 若 1 口l 2 口2 且图G 1 中的边e 1 一 扎l 与图G z 中的边e 2 一 z 口2 具有相同的属性值 或网G 中的顶点 和口 图G z 中的顶点Uz 和口z 各不相邻 则构 造一条边e 一一 并加入到关联图H v 的边集E 中 a 图G l 作为其一条边 关联图的构造示意图如图2 所示 其中圆 正方 形和三角形节点分别表示属性不同的顶点 根据 S t e p l 关联图H v 由节点a A b C c B 和c D 组成 根 据S t e p 2 节点a A 和b C 通过一条边连接 关联图中 其他边用相同的方法构造 其中节点a A 和f D 之间 由于在图G 中顶点a 和c 图G 中顶点A 和D 各不 相邻 因此在关联图中它们也通过一条边连接 关联 图H v 如图2C 所示 三角形内的顶点集合称为关联 图H y 的最大团 则检测2 个C A D 模型属性邻接 图的公共子图问题就转换成为检测关联图最大团 问题 在此 先给出最大团的定义 定义3 最大团 对于给定图G V E 其 中 V 一 1 疗 是图G 的顶点集 E V V 是图 G 的边集 G 的团就是一个两两之间有边的顶点集 合 如果一个团不被其他任一团所包含 即它不是其 他任一团的真子集 则称该团为G 的极大团 顶点 最多的极大团称之为G 的最大团 b 图G 2c 关联图日y 图2 关联图构造示意图 2 2 最大团检测 F e n e t 等 9 1 于2 0 0 3 年首次提出将蚁群算法用 于解决最大团问题 该算法采用顶点对应的信息素 模型 使用了全局信息素更新规则和局部搜索策略 但其存在2 个主要问题 1 容易使搜索过程陷入局 部最优 无法搜索出全局最优解 2 对于给定的2 个 三维C A D 模型 其相似的局部结构可能有多个 在 关联图中对应多个极大团 而该算法只能检测到最 大团 而不能检测所有的极大团 本文在深入分析现 有算法优缺点的基础上 结合由C A D 模型转换得 到的属性邻接图及其局部结构对应的子图的特征 设计了一种改进的蚁群优化算法 由最大团的定义可知 最大团问题的可行解是 一个满足一定约束条件的顶点集合 为了与解的表 示相一致 本文采用基于顶点的信息素模型 这种信 息素模型与最大团问题的解的表示相一致 效率也 比较高 令信息素模型为垂 r r z 岛 其中n I y l r l 表示顶点i 上积累的信息素的数量 其值越 大意味着在构造极大团过程中该顶点被选择的概率 越大 算法的步骤如下 输入 关联图G 一 y E 输出 关联图中所有极大团集合S i b e g i n d o 初始化最大团黾 蚂蚁数目m 最大迭代次数 m a x i t e r 初始化信息素模型中 w h i l e 未达到最大迭代次数m a x i t e r 未找到S 6 f o r 蚁群中的每一个蚂蚁k 构造一个团 信息素模型圣局部更新 e n df o r 计算本次迭代最优解S 衙 根据S 沁 判断S 是否需要更新 信息素模型垂全局更新 万方数据 6 3 6计算机辅助设计与图形学学报第2 3 卷 i fS h 的顶点数目 2 将最大团S 存人集合S 将S 中的顶点从关联图G 中删除 并重新构造G e n di f w h i l eS b 的顶点数目 2 e n d 本文算法将信息素模型西各顶点信息素数量 限制在一个区间 r m i m a x 中 在初始化信息素模型 时 所有顶点上的信息素的初始值为r r m 对于每一 个蚂蚁构造极大团的过程如下 蚂蚁忌从只包含一 个随机选择顶点的部分解S 开始 在每一步构造 中 当前团S 都是通过增加一个来自顶点集合 v s 中的顶点不断地扩展 直到成为一个极大团 集合v s 中的顶点要满足与当前团S 中的顶点 具有连接关系 在从集合V S 中选择加入当前团 S 中的顶点是概率选择的 选择概率最大的加入到 当前团 每个顶点被选择的概率为 5 专每 E v s k 其中参数口决定了信息素对概率的影响权重 当任意一个蚂蚁k 构造完一个极大团S 后进 行局部信息素更新 极大团S 所包含的顶点上的信 息素的数蟹按 小 m 卜 斜 口t 2 r 锄i o t h e r w i s e 进行更新 采用局部信息素更新可以增加算法在一 次迭代过程中解的多样性 从而间接地指导后继蚂 蚁选择那些尚未选择的顶点 搜索尚未探索的解空 间区域 在一次迭代过程中 当所有蚂蚁都构造完一个 极大团以后 根据S 计算本次迭代最优解S 并 根据S 嘶判断S 6 是否需要更新 然后按 r 可f P r 口 A r 口i 3 进行全局信息素更新 其中 A r v i v i 丽耶S 击b S i 口t s h r J 1 I I l I 一 0 o t h e r w i s e P 称为信息素持续率 且p 1 全局信息素的更新过程可以分为信息素蒸发阶 段和信息素加强阶段 信息素蒸发阶段是模拟现实 世界中信息素的蒸发 现实世界中蚂蚁在往返于巢 穴和食物源之间的路径上会释放信息素 同时释放 的这些信息素会随着时间的流逝不断地蒸发 这就 避免了信息素的无限制积累 信息素增强阶段的目 的是增加那些属于本次迭代最优解的顶点上的信息 素的数量 使得在下一次迭代过程中蚂蚁们能够朝 向本次迭代产生的最优解的邻近区域进行搜索 在 局部信息素更新和全局信息素更新过程中 信息素 的值是在区间 r m I l r m 中的 因此当顶点上的信息 素的数量改变后 要判断改变之后的值是否越界 如 果某个顶点上信息素的值小于信息素下界 则给其 赋值r m I 若某个顶点上信息素的值大于信息素上 界 则给其赋值Z r a n 全局信息素更新完成后继续迭代 直到找到最 优解或算法达到最大迭代次数 由于C A D 模型的 特征或局部结构一般是由多个面组成 因此本文设 置最大团的顶点个数至少为3 当最大团的顶点个 数满足条件时 将当前最大团S 缸存入一个集合 然 后将当前最大团中的顶点从关联图中删除并重新构 造关联图 继续查找重新构造的关联图的最大团 直 到将所有的极大团查找出来 算法结束 2 3 相似度计算 查找出的团对应于2 个C A D 模型上相似的特 征或局部结构 采用所有团的顶点个数除以2 个 C A D 模型面的个数之和的一半所得值来描述2 个 模型相似性大小 即 s 一志 4 其中 S 表示2 个模型之间的相似度 N 表示所有 团顶点的个数 和N 表示2 个C A D 模型中面的 个数 S 越大 表示2 个C A D 模型之间的相似性越 大 它们所包含的相似的特征或局部结构就越多 3 算法验证与讨论 为了验证本文算法的有效性 本文以M i c r o s o f t V i s u a l S t u d i o2 0 0 8 为集成开发环境 O p e n C A S C A D E L l 0 3 为几何平台构建了一个三维C A D 模 型测试库 该库中包含2 0 0 个常见的C A D 模型 在 实验中 蚁群算法的参数设置如下 0 t 1 p 0 9 9 最大迭代次数m a x i t e r 3 0 0 0 r m i 一0 0 1 r 6 0 蚁群中蚂蚁数目m 一1 0 表1 所示为6 种C A D 模型之间的相似性比较结果 从比较结果可以看出 2 个模型之间包含的相似特征或局部结构数目越 多 相似值越高 万方数据 第4 期张开必 等 基于蚁群算法的一维C A D 模型检索 表16 种C A D 模型之间的比较结果 表2 所示为本文算法与文献 9 葬法对6 个C A D 模型检索值的比较与排序 从比较值大小分析 由于 本文算法能检索出C A D 模型所包含的所有相似的 特征或局部结构 而文献 9 算法只能检索出C A D 模型中面数最多的一个特征或局部结构 用此本文 算法得到的模型之间的相似值更太 检索结果更符 合人的相似性感知同时 由于本文算法对信息索模 型进行了全局更新和局部更新 检索结果更加准确 例如 文献 9 算法中排在第6 位的模型与检索模型 的相似度值应该排在第4 位和第5 位模型之前 但 由于文献 9 算法没有进行信息素模型局部更新 搜 索过程陷人局部最优 投有搜索小全局最优解 表22 种算法对6 个C A D 模型检索值的比较与排序 万方数据 计算机辅助设计与图形学学报弟2 3 卷 丧3 4 所示为本文算法与通用领域的典制算 法 形状分布算弦 一和球面谐波算法 埘2 个 C A D 模制的检索实验结果表3 所水为以一个外八 角螺钉为检索模型 测试库中存4 个这种类型的模 型3 种算法检索结果排列在前6 位的模型巾 形状 分布苒法检索H 个 其他3 个分别排列在第9 2 0 和3 8 位 球面谐波算法检索m1 个 其他3 个分别 排列在第1 1 1 8 和2 4 位 本文算法检索出4 个 分 别排在第1 2 4 和5 位表4 所示为以一个叉形结 构的C A D 模型作为椅索模划 测试库巾含有这种 叉形结构的C A D 模型共有3 个3 种算法检索结果 排列在前6 位的模型中 形状分布算法检索出1 个 其他2 个分别排列在第5 9 和8 4 位 球面谐波算法 检索m2 个 排在第1 和4 位 第3 个模型排列在13 位 本文算法检索出3 个 分别排在前3 位从检索 结果可以看m 形状分布算法平 球面谐波算法更 侧重整体外形的相似性 无法比较模型更为精确 的细节特征 而本文算法可以将包含检索模型细 节特征的所有模型检索出来 可更好地指导企业 参考并重用已有模型为r 充分对比3 种算法的 性能 本文对模型库中的C A D 模型进行统计测试 获得了一个平均查全率 查准率曲线 如图3 所示 可以看m 本文算法的检索性能明显地高于其他2 种算法 裹3 检索实倒 万方数据 第4 期张开兴 等 基于蚁群算法的三维C A D 模型检索6 3 9 1 O 0 8 糯0 6 磐 蛔O 4 0 2 O 00 20 40 60 81 0 查全率 图33 种算法的查全一查准率曲线 本文算法的时间复杂度主要集中在利用蚁群算 法查找最大团 其时间复杂度是O n 2 其中n 是关 联图顶点的个数 本文实验采用为I n t e r P e n t i u m D u a l1 8 0G H zC P U 2 o oG B 内存的P C 机 表5 统计了3 种算法对单个模型的平均处理速度 包括 特征提取速度和特征比较速度 可以看出 本文算法 的时间效率明显高于其他2 种算法 表53 种算法执行时问对比s 算法时间 本文算法 形状分布算法 球面谐波算法 0 2 3 8 1 6 4 9 0 7 8 4 4 结语 本文提出一种面向重用的三维C A D 模型的检 索算法 首先将C A D 模型用属性邻接图来表示 然 后利用蚁群优化算法来检测C A D 模型中所包含的 相似的特征或局部结构 最后根据相似特征或局部 结构实现C A D 模型的相似性评价 该算法的最大 特点在于充分考虑企业在设计和制造过程中更注重 模型局部细节特征相似性 只有达到局部细节特征 的检索才能更好地实现C A D 模型的重用 实验结 果表明 本文算法的综合性能要明显地高于形状分 布算法和球面谐波算法 参考文献 R e f e r e n c e s 1 l y e rN J a y a n t iS L o uKY e ta 1 T h r e e d i m e n s i o n a ls h a p e s e a r c h i n g s t a t e o f t h e a r tr e v i e wa n df u t u r e t r e n d sE J C o m p u t e r A i d e dD e s i g n 2 0 0 5 3 7 5 5 0 9 5 3 0 2 O s a d aR F u n k h o u s e rT C h a z e l l eB e ta 1 S h a p e d i s t r i b u t i o n s J A C MT r a n s a c t i o n so nG r a p h i c s 2 0 0 2 2 1 4 8 0 7 8 3 2 3 K a z h d a nM F u n k o u s e rT R u s i n k i e w i e z S R o t a t i o n i n v a r i a n ts p h e r i c a lh a r m o n i cr e p r e s e n t a t i o no f3 Ds h a p e d e s c r i p t o r s c P r o c e e d i n g so fE u r o g r a p h i c sS y m p o s i u mo n G e o m e t r yP r o c e s s i n g A i r e l a V i N e E u r o g r a p h i c sA s s o c i a t i o n P r e s s 2 0 0 3 1 5 6 1 6 4 4 W a n gY u M aH a o j u n H eW e i e ta 1 C l u s t e r i n g r e t r i e v a l o fm e c h a n i c a l3 DC A Dm o d e l s J C o m p u t e rI n t e g r a t e d M a n u f a c t u r i n gS y s t e m s 2 0 0 6 1 2 6 9 2 4 9 2 8 i nC h i n e s e 王玉 马浩军 何玮 等 机械3 维C A D 模型的聚类和 检索 J 计算机集成制造系统 2 0 0 6 1 2 6 9 2 4 9 2 8 5 M aL u j i e H u a n gZ h e n g d o n g w uQ i n g s o n g R e t r i e v a lo f C A Dm o d e l sb a s e do ns h a p e l o c a t i o nc o d e so ff a c e s 口 J o u r n a lo fC o m p u t e r A i d e dD e s i g n C o m p u t e rG r a p h i c s 2 0 0 8 2 0 1 1 9 2 5 i nC h i n e s e 马露杰 黄正东 吴青松 基于面形位编码的C A D 模型检 索E J 计算机辅助设计与图形学学报 2 0 0 8 2 0 1 1 9 2 5 6 W a n gH o n g s h e n Z h a n gS h u s h e n g B a i X i a o l