（机械设计及理论专业论文）基于面识别的三维重建技术研究.pdf

摘要 浙江大学硕士学位论文 a b s t r a c t s t a r t i n g 疗o mi n t e r m e d i a t es u r f a c e t h i sp a p e rf o c u s e so n3 dr e c o n s t r u c t i o nt h a t i sb a s e do ns u r f a c er e c o g n i t i o n ka t t a i nt h i st h r o u g ht h ef o l l o w i n gs t e p s0 u rf i r s t r e s e a r c hc o v e r sg r a p hr e c o g n i t i o na n di t sp r e p r o c e s s i n g ，a n db yd o i n gt h ef o r m e rw e c a l ld i s t i n g u i s ht h o s ev a r i o u sr e p r e s e n t a t i o nm e t h o d su s e dc o m m o n l yi nv i e wa n d c o m p l e m e n t t 1 1 ed e f a u l ti n f o r m a t i o nt h e no nt h eo n eh a n d b e g i n n i n gw i t ht h ec i r c l e s a n da r c si no u rv i e w , a n db ya n a l y z i n gt h ec y l i n d e rp r o j e c t i o nr u l e ，w ec a no b t a i n c y l i n d e rp r o j e c t i o nr e s t r i c t i o nr e l a t i o na n dw i t ht h i sr e s t r i c t i o nr e l a t i o n s h i pb e i n gt h e c r i t e r i o n , w ec a nf i n a l l yr e c o g n i z et h ec y l i n d e rt h r o u g hs e a r c h i n ga m o n gt h ev i e w d a t as e tt h o s ee l e m e n t st h a ta r ei nl i n ew i t ht h ep r o j e c t i o nr e s t r i c t i o nr u l e o nt h eo t h e r h a n d ，s t a r t i n gf r o ml i n e s ，a n db ya n a l y z i n gt h ep r o j e c t i o nr u l eo f s u r f a c et ov i e w , w e c a no b t a i nt h o s ep r o j e c t i o nr e s t r i c t i o nr e l a t i o n s h i po fv a r i o u sa n g l es u r f a c e st ov i e w , a n dw i t ht h i s r e l a t i o n s h i pb e i n gt h ec r i t e r i o n ，w e c a r l f i n a l l yr e c o g n i z ev a r i o u s s u r f a c e sl o c a t i n gi nd i f i e r e n ta n g l e sa f t e r w a r d s t h es u r f a c em o d e l i se s t a b l i s h e db y r e c o g n i z i n gt h ec y l i n d e r sa n dt i l es u r f a c e se l e m e n t sf i n a l l yc o m b i n i n gt h ec y l i n d e r s a n dt h es u r f a c e s t h ee n t i t ym o d e lo f t h e w o r k p i e c ei sr e c o n s t r u c t e d t h i st h e s i sc a nb ed i v i d e di n t o6c h a p t e r s ，w h i c ha r ea sf o l l o w s c h a p t e r1 d i s c u s s e st h ei m p o r t a n c eo f3 dr e c o n s t r u c t i o nt e c h n o l o g ya n dt h ei t s c u r r e n ts i t u a t i o n a n da f t e r w a r d sa n a l y z e st h es h o r t c o m i n g si nt h em e t h o d sa v a i l a b l e s of a r f i n a l l yt h i sc h a p t e rd e l i v e r 8t h eb a s i ci d e ao f t h i st h e s i s c h a p t e r 2d e a l sw i t ht h ev i e w r e c o g n i t i o na n dg r a p hp r e p r o c e s s i n gt e c h n o l o g y w ec a n d i s t i n g u i s h d i f f e r e n t r e p r e s e n t a t i o n m e t h o d s b y v i e w r e c o g n i t i o n a n d p r e p r o c e s st h o s ed i f f e r e n tr e p r e s e n t a t i o nm e t h o d st h r o u g hp r e p r o c e s s i n g c h a p t e r 3i sd e d i c a t e dt o c y l i n d e rr e c o g n i t i o n a f t e r a n a l y z i n gc y l i n d e r p r o j e c t i o n r u l et h i s c h a p t e rs u m m a r i z e st h ep r o j e c t i o n r e s t r i c t i o n r e l a t i o n s h i p o f c y l i n d e r s a n dt h r o u g hj o i n i n ga n dm e r g i n gc l o s e dr i n g sw ec a nr e c o g n i z ev a r i o u s c y l i n d e r s c h a p t e r 4c o v e r st h er e c o g n i t i o no fs u r f a c e si nv a r i o u sa n g l e s b ya n a l y z i n gt h e p r o j e c t i o nr u l eo fv a r i o u ss u r f a c e s w eo b t a i nt 1 1 ep r o j e c t i o nr e s t r i c t i o nr e l a t i o n s h i p a n dt h r o u g h s e a r c h i n g e l e m e n t st i l a ta r ei nl i n ew i t ht h i s p r o j e c t i o n r e s t r i c t i o n r e l a t i o n s h i p w er e c o g n i z ea l lt h es u r f a a e s1 0 c a t i n gi nd i f f e r e n ta n g l e s c h a p t e r5e l a b o r a t e st h ef o r m a t i o no f t h ee n t i t ym o d e lo f t h ew o r k p i e c et h r o u g h t h er e c o g n i t i o no fc y l i n d e r sa n ds u r f a c e sb e s i d e s ，s o m ew o r k i n ge x a m p l e so ft h e o r i g i ns y s t e ma r es h o w n h e r e c h a p t e r 6s u m m a r i z e sm ew h o l e p a p e ra n dp o i n t so u tf u t u r er e s e a r c ha r e a 第一章绪论 浙江大学硕士学位论文 1 1 引言 第一章绪论 计算机辅助设计和计算机辅助制造技术( c a d c a m ) 自六十年代问世以 来迅猛发展，已经使传统设计和制造方式发生了根本性的变革，它是加快制造 业自身改造、实现产品设计和制造自动化的有力手段，它提高了产品的性能和 质量，缩短了产品的开发周期，降低了生产成本，加强了产品的市场竞争力。 它的发展和应用水平已经成为衡量一个国家科技现代化和工业现代化水平的重 要标志之一，被誉为自电力发明以来最具有生产潜力的工具。 计算机图形学( c g ) 这一功能强大、应用广泛的新兴科学，是c a d c 舢订 的主要基础之一。c g 运用计算机的先进技术，对图形进行数学处理，进而研 究图形学领域中的各种理论和实践问题，并把计算机处理的结果在绘图仪上绘 图输出。因此计算机图形学把形和数很好的结合起来，做到了从图学理论到绘 图实践的完美统一。它虽然在某些方面还不完善，但其威力已初露锋芒，前景 是不可估量的。 随着计算机软硬件的飞速发展和c g c a d c a m 在制造业方面应用的不断推 广，现在c a d c a m 正朝着集成化和智能化方向发展，出现了一引起制造系统 的新模式。如计算机集成制造系统( c n s ) ，柔性制造系统( f m s ) ，智能制造 系统( i m s ) 和生物型制造系统( b i o l o g i c a lm a n u f a c t u r i n gs y s t e m ) 等等。在这 些新模式中，有的还在作理论探索，有的己经正在实施，并创造了显著的经济 效益。在上述各种系统中，产品数据模型起到了关键作用，产品数据模型由机 械工件的几何模型加上有关工件的技术信息和装配构成，有了产品模型，既可 以通过各种造型加上有关工件的技术实现对产品的直观了解，也可以对产品的 装配过程和方式进行规划和模拟，又能对未来产品进行诸如有限元分析、容差 分析等，直到生产过程的具体控制。 在传统的制造系统中，工程图是产品设计、生产组织的技术数据传递媒介， 也是各企业、系统之间重要的信息交流方式。但在目前的集成制造系统中，三 维数据模型是产品数据模型的几何核心。作为一种更先进的产品模型，三维数 据模型在实际应用中发展非常迅速，在其基础上，可以直接进行有限元分析等 自动化的c a d 技术，缩短了产品设计周期，然面，工程图也并没有马上被淘 汰。虽然工程图使用二维的信息来描述三维产品，但这种描述是准确有效的，有 时候，二维的工程图能更简洁明快地表达出所要描述的产品零件。在可以预见 的将来，工程图和三维产品数据模型将会在先进制造系统中共存，这就需要构 建两种数据形式之间的沟通桥梁，本文所讨论的三维重建技术正是这两种模型 的沟通桥梁之一。 第一章绪论浙江大学硕士学位论文 1 2 三维重建的重要意义 三维重建具有巨大的应用前景，主要体现在如下几个方面 1 三维造型系统的输入手段 近年来三维造型技术得到了迅速发展和应用，推出了一大批造型系统，著名 的有p r o e n g i n e e r 、c o m p u t e r v i s i o n 、i n t e r g r a p h 、c a t i a 、s d r c i - d e a s 、c a l m a 、 u n i g r a p h i c s 、e u c l i d 、c d c i c e m 、c a d a m 、a u t o c a d 等，但在这些强大的软 件功能背后，数学模型的原始数据输入问题却始终使研究开发者们感到棘手， 而输入问题与用户使用直接相关，输入方法简单与否理所当然地成为用户评价 一个系统好坏的重要指标。目前，把三维物体模型输入到计算机内大致有三种 方法： ( 1 ) 定义若干基本特征体素，对它们直接进行并、差集合运算生成模型或将 它们添加到已有模型构成新的形体，这是一种从三维到三维的实时输入方 法； ( 2 ) 先构造出形体的基线，然后用平移扫描或者旋转扫描生成形体，是一种 从二维到三维的实时输入方法； ( 3 ) 在二维视图基础上，通过图形理解获取物体三维模型，是一种从二维到 三维的非实时输入方法。 前两种方法已经成功地应用于前面提到的软件中，然而第三种方法虽然输 入简单、方便，符合工程设计和制造的习惯，但还没有应用在某个软件上，因 为由二维视图转化为三维形体一直是一个c a d c g 领域难以解决的课题。 2 延伸新产品信息建模的源头 在三企业中，特别是在一些历史悠久的大型制造业公司中，累积了数目非 常惊人的产品设计文档，其中绝大部分是工程图纸。这些产品设计是一批批工 程技术人员的智慧结晶，其中的经验积淀指导着将来的产品设计，而且有许多 新产品都是根据原有产品经过变形设计和适应性设计得到的。但是，纸质文档 不易于保存，而且管理非常不便，所以产生了将图纸扫描( 进一步手工或半自 动矢量化) 后的数字化管理手段。但是，先进制造技术的信息系统的核心是三 维的数据模型，要更充分有效地利用早期的设计成果，就必须将二维的工程图 转化为三维模型。另夕 ，在早期的二维c a d 系统应用阶段和现阶段，也产生 了大量的用二维工程图表达的产品图形文件，将这些产品用手工实时输入方法 正好可以利用这些图形文件重建三维模型，延伸了产品信息建模的源头。 3 一种有效的特征识别方法 自动特征识别是从零件的c a d 模型中抽取出具有特定工程语义的特征信 息由于工业界的迫切需要，c a d c a m 一体化己成为近年来c a d 、c a m 研究 人员追求的主要目标之一，然而系统集成面临许多困难，自动特征识别正是因 此而产生的c a d 与c a p p 之间的智能接口，对实现c a d c a p p c a m 集成具有 重要意义，因此一直是c a d c a m 领域的研究热点，研究成果十分丰硕。另一 方面，由于特征识别具有相当难度，该领域至今仍存在许问题有待解决。现有 第一章绪论 浙江大学硕士学位论文 的特征识别方法种类已经有很多，整体上可以分为基于边界匹配和基于立体分 解两种方法，这两类方法者从实体模型或设计特征表示的产品模型中进行识别 的，遇到的困难很多。直接从二维工程图样的表过中识别特征的优越性在于工 程图样的数据是二维的，避免了三维模型所带来的算法的复杂陛和较高的误判 率。从二维的工程图样出发的自动特征识别可能是一条有效的途径，特别是通 过特征识别可以很方便地连接到c a p p 。 4 机器人视觉的研究 在机器视觉领域，人们希望通过三维重建的研究使计算机视觉系统具有空 间想象力，以致能看懂工程图样所表达的的复杂结构体，一个潜在应用是装配 的机器人装配作业过程中的目标理解，使机器人能够从提供的图形中提取所需 的信息，明确作业目标，这样我们可以用工程图样规定机器人的任务，为机器 人行为规划提供目标。 综上所述，从二维视图转化三维褓己成为c a d c a m 和计算机视觉两个 不同领域共同关心的一个研究课题，它有着非常广泛的应用前景，但同时它又 是一个难度很大的课题，因为从三维形体生成二维视图是一个由高维向低维视 图转化三维实体时难免产生多义、多解和病态解等情况，这样一个由低维向高 维恢复信息的过程其难度是显而易见的。 1 3 国内外发展概述 对于从物体的投影图中进行三维重建的研究，最早是由i d e s a w a 【”在七十年 代早期提出来的。他根据投影和反投影描述了一般的重建问题，产生了先构造 线框型后形成成立体的算法。这一方法首先在不同的视图中标识相应的顶点。 在构造面时，要根据一系列的条件进行边的搜索：一个平面的所有边组成一个 封闭的环，要对选择到的边作进一步的处理，任何一条对该面无作用的边都被 认为是假边，需擦除i d e s a w a 算法的主要步骤是相当直观和合理的： ( a )由二维顶点生成三维顶点： ( b )由三维顶点生成三维边； ( c )擦除假图素； ( d )由三维边生成三维面； ( e )将正确的面组装成三维物体。 假图，又称幻图，是操作该系统时可能出现的。为此，他运用了一些判别 规则来消除它们。该算法只选用于多面体，尽管他断言有曲面的潜在，但对此 他不能处理。并且，因为三视图中不可见的线没有与其它的线区别开来，幻图 不能从真图中区分出来，所以后者有可能被错误地去掉。 i d e s a w a 算法被认为是有创造性的。从那以后，有关该领域的问题激起了许 多人的兴趣。他的思想方法被其他人所采纳，算法得到了不断的完善和提高， 其适用范围也不再只限于多面体。 第一章绪论 浙江大学硕士学位论文 的特征识别方法种类已经有很多，整体上可以分为基于边界匹配和基于立体分 解两种方法，这两类方法者从实体模型或设计特征表示的产品模型中进行识别 的，遇到的困难很多。直接从二维工程图样的表过中识别特征的优越性在于工 程图样的数据是二维的，避免了三维模型所带来的算法的复杂陛和较高的误判 率。从二维的工程图样出发的自动特征识别可能是一条有效的途径，特别是通 过特征识别可以很方便地连接到c a p p 。 4 机器人视觉的研究 在机器视觉领域，人们希望通过三维重建的研究使计算机视觉系统具有空 间想象力，以致能看懂工程图样所表达的的复杂结构体，一个潜在应用是装配 的机器人装配作业过程中的目标理解，使机器人能够从提供的图形中提取所需 的信息，明确作业目标，这样我们可以用工程图样规定机器人的任务，为机器 人行为规划提供目标。 综上所述，从二维视图转化三维褓己成为c a d c a m 和计算机视觉两个 不同领域共同关心的一个研究课题，它有着非常广泛的应用前景，但同时它又 是一个难度很大的课题，因为从三维形体生成二维视图是一个由高维向低维视 图转化三维实体时难免产生多义、多解和病态解等情况，这样一个由低维向高 维恢复信息的过程其难度是显而易见的。 1 3 国内外发展概述 对于从物体的投影图中进行三维重建的研究，最早是由i d e s a w a 【”在七十年 代早期提出来的。他根据投影和反投影描述了一般的重建问题，产生了先构造 线框型后形成成立体的算法。这一方法首先在不同的视图中标识相应的顶点。 在构造面时，要根据一系列的条件进行边的搜索：一个平面的所有边组成一个 封闭的环，要对选择到的边作进一步的处理，任何一条对该面无作用的边都被 认为是假边，需擦除i d e s a w a 算法的主要步骤是相当直观和合理的： ( a )由二维顶点生成三维顶点： ( b )由三维顶点生成三维边； ( c )擦除假图素； ( d )由三维边生成三维面； ( e )将正确的面组装成三维物体。 假图，又称幻图，是操作该系统时可能出现的。为此，他运用了一些判别 规则来消除它们。该算法只选用于多面体，尽管他断言有曲面的潜在，但对此 他不能处理。并且，因为三视图中不可见的线没有与其它的线区别开来，幻图 不能从真图中区分出来，所以后者有可能被错误地去掉。 i d e s a w a 算法被认为是有创造性的。从那以后，有关该领域的问题激起了许 多人的兴趣。他的思想方法被其他人所采纳，算法得到了不断的完善和提高， 其适用范围也不再只限于多面体。 第一章绪论浙江大学硕士学位论文 三维重建提出至今已有二十多年了。在这期间，人们提出了各种各样的算 法，但离开解决这个问题的目标还相当遥远。根据三维造型技术的不同发展阶 段，现有的三维重建算法也可以随之划分为两类：基于线框模型、表面模型和 b - r e p 模型的自底向上方法；基于c s g 模型和特征的模型引导方法。 1 自底向上方法 i d e s a w a 最早提出的算法就属于自底向上方法。w e s l e y 和m a r k o w s k y 为研 究由线框表示的多面体的所有可能解，阐述了一个完整的算法l ，随后又将这 一算法扩展到二维正投影三视图的情况1 1 “。作为由二维数据生成立体模型的技 术，该算法比前人有了很大的改进。算法使用了b - r e p 模型作为重建的基础模 型，基于代数拓扑和严格的几何实体定义，有能力列举所有可能的解并消除所 的假图素，是第一个能较好地识别出比较复杂例子的算法，并且可以处理非流 型物体。w e s l e y 和m a r k o w s k y 的算法合乎逻辑并且有效率。先由二维点生成三 维点，进而得到三维线框，每两条不在同一直线上的边生成一个平面，每一条 边按相反的方向使用两次，找到最小的封闭区域，而后将它们置于树构中。这 时，产生的平面称为虚面，它有一个外边界，也可能是内边界( 对有孔的面) 。 对每一条边而言，会产生一系列的虚面，它们成辐射状地分布在边的周围。相 类似地，每一虚面按相反的方向使用两次可找到最小的封闭体积，而后将它们 置于树结构中形成虚块。最终对每一虚块需决定它是实体还是孔，将实体块胶 贴在一起，找出所有可能解。w - m 算法的不足主要有两个方面：适用范围窄和 去算量大。算法只适用于多面体，并且没有考虑投影中出现虚线的情况。在重 建的每一步操作中，都需要有大量的运算来判断和去除实际并不存在的点、线、 面、体。 s a k u r a i 和g o s s a r d t ”1 在w m 算法的基础上扩展了适用范围，可以包括圆 柱、圆锥和球，这些二次曲面的轴必须平行于一个从标轴。g ue ta l 以及l e q u e t t e 也做了类似的探索，将识别范围扩展到了皓面。 我国辜凯宁等人 3 ”提出的算法对w e s l e y m a r k o w s k y 的算法加以改进和补 充。算法首先从二维点直接生成三维边，然后生成三种类型的面方程，为消除 病态解引入切割点与切割边，然后生成三种类型的面方程，为消除病态解引入 切割点与切割边。在生成面环和子体时，提出了面域基( 基环) 、体域基概念， 仅存储有界环，以期提高交率，节省存储量，算法着重于平面体和圆柱体的某 些组合，并允许视图中出现直线、圆弧、正椭圆弧及非圆柱体相贯。算法可以 排除病态解，并能在多解情况下求出全部解。 y a h 等【”1 基于图形投影的规律，在算法中使用了实线和虚线所提供的深度 信息来减少可能的面环和体环的数目。由于虚线前必定有其他面遮挡，虚线所 构成的面不会处于投影方向上的第一个面，这样，虚面的产生就减少了，后续 的单元体的生成和决策效经也相应提高。对于虚线的处理增加了可处理的平面 体的复杂度。 前述各算法在得到面环，生成单元体后，一般对单元体的和种组合方案进 第一章绪论 浙江大学硕士学位论文 行搜索，将各种可能的组合体投影加二维平面，与原先的三视图进行比较，投 影一致的组合就是所求的解。这种算法是n p 完全搜索，在单元数目较多的时 候运算量相当大，效率较低。鉴于这种情况，h i r o s h i m a s u d a 和m a s a y u k i n u m a o f 2 6 j 认为可以根据单元体和投影图之间的约束来推导出正确的单元组合方式。他们 给出了一组布尔方程，用来描述单元体和投影图线的约束，然后使用a t m s ( a s s u m p t i o n b a s e dt r u t hm a i n t e n a n c es y s t e m ) ，对基于单元体组合的投影约束 进行推理，从而得出一个符合原三视图的解。这种算法对输入数据的要求进一 步放宽，有一定的容错性，可以检查出在输入图形中存在的一些错误。 自底向上的识别方法提出最早，研究时间最长，算法最多，能够识别的实 体种类也较多，特别是对于复杂的多面体，这类算法是解决多解和病态解相对 较好的方法。但这类算法的识别方法并不是有经验的工程师的看图方法。此外， 这类算法总要进行复杂的判定以消除大量存在的虚假三维图形基元，这一要求 是相当苛刻和不实用的，因而仍有搜索量过大，无法处理大部分零件图中存在 的省略和剖切等问题。 2 模型引导方法 自底向上算法从最基本的点、线开始解决问题，而模型引导方法则是参照 c s g 造型的思想，认为一个零件可以被看成是由有限的几种体素( p r i m i t i v e ) 通过并交差运算得到，直接从视图中按模式匹配的思想进行识别，提取出各基 体，生成c s g 树或其它的表达形式，最后得到零件的实体模型。 a l d e f e l d 4 1 首先提出了这种方法，构造了均匀厚度类子体的识别模型，实现 了此类子体的识别，算法要求的视图图形是直线、圆和圆弧，而且要求每一个 均匀厚度子体的投影完全表示在三个视图上，且其基面平行某两个坐标轴构成 的平面。算法的要点是：选取一个环，假定该环是一个或多个均匀厚度子体底 面的投影，在其它视图内寻找假定子体的侧投影。如果侧投影存在，就能直接 建立起其三维子体结构，进到所有的环都被处理过。在选取环时运用了最佳优 先启发式搜索策略。 这种方法采用了结构模式识别技术。因此是从假定的子体出发，寻找相应 的三视图投影加以验证，从而避免了自底向上方法中对三维图形基元的庞大搜 索和消除操作，在某些场合速度极快，算法也比较简单。但是工程中的三视图 情况并不总是象算法要求的那样理想。当某些子体的投影因与其它子体合并而 不能全部表现在视图上时，模式无从匹配，导致算法失败。a l d e f e l d r i c h a c e r 后来提出了一个半自动的识别算法，加入人工交互，添加辅助线，以实现算法。 虽然交互识能识别很复杂的视图，但实际上主要是靠人来识别，因此识别的成 功与否主要依赖于使用者的知识和技巧。 虽然a l d e f e l d 的算法能识另j 的几何形体类型少，但其效率高，所产生的模 型更为实用，所以许多人将注意力转到模型引导方法上，针对a l d e f e l d 算法的 不足做了改进。h o 将体素分为实体和虚体，根据一些关键点( k e yp o i n t ) 的 位置来抽取体素。他没有处理好实体和虚体的顺序问题，但根据关键点的位置 第一章绪论浙江大学硕士学位论文 来抽取体素的方法还是比较简便可靠的。k a r g a s e ta t 认为一组固定的投影线可 以作为体素的“标记”( s i g n a t u r e ) 。象对一块原村料进行切削加工一样，k a r g a s 先从原始数据中分析得到一个大致的模型，再将其投影轮廓与视图进行比较， 不匹配处产生环，从环中根据“标记”识别出体素，对已有模型进行改进，然 后再进行比较、修改。投影轮廓与视图的比较由用户掌握，并作出相应处理。 台湾的c h i a h w al i u 等【 0 1 ，从二维图纸中识别出七类形状特征：立方体、 锲形体、扇形体、内圆弧体、圆柱、四面体、半圆拱形体。识别出的特征可以 是实体也可是虚体，识别后剩下的部分用拉伸和相交的方法生成一个基体，基 体加上各实特征和虚特征后即可得到零件模型。这种形状特征的划分办法在一 定程度上绕过了相交特征的识别问题，有一定的应用价值，但对于输入的图纸 仍作了过多的约定，限制了这种方法的实际应用。 y o s h i u r ae ta l t ”1 采用一个和a l d e f e l d 不同的自顶向下的重构方法。他发明了 一种基于知识的自然语言系统，并有它自身的技术词汇。先由扫描仪读出蓝图 和图纸上的所有的信息，包括图纸的文字注释，然后产生一个二进制图象文件。 基于这一图象文件，罗形部分通过字符识别技术从标注字符中分离出来。字符 被取出来组成句子，句子用自然语言系统解释得到三维信息。输出表示选择c s g 模型。 另一种不同的模型引导方法的指导思想是对零件是对零件的切削体进行单 元分解。z e nc h e n 与d e r - b a a up e r g n l 2 6 】算法就是基于这种思想，首先采用“各 个击破”的策略，将视图图形分成孤环类( 不与其它环相交的环) ，弧类和其他。 对孤环类采用基于模型引导的识别方法。对弧类，增加一条辅助线连接弧的两 个端点形成基环，再运用基于模型引导的方法。去掉这两类图形后，原图有很 大的简化。对剩下的图形以某一视图内图形的外轮廓为底面构造一个柱体，运 用这些差异边构造边界平面。运用深度优先搜索用边界平面构造子体。从柱体 上去掉假子体，将得到的新实体再投影与原视图比较。这样做下去直到新实体 投影与原视图完全一样。算法要求视图图形是直线、圆和圆弧。能识别均匀厚 度实体和非均匀厚度的平面体。算法不能处理多解和病态解。 基于体切削的识别算法的特点在于它总是在三维空间的体、面、边上进行 操作。只对生成的可能虚假子体进行判断和切削，而不要象自底向上方法那样 为确定三维点、边和面的真假而煞费苦心，因此效率较高。但也带来了大量而 复杂的三维空间操作和计算。 模型引导的特征抽取技术还被用于加工特征的识别。实际上，目前特征识 别技术在三维模型的背景下发展得并不顺利，二维的工程图纸所提供的特征信 息基于一定知识，便于模式识别，更容易被利用。基于这种认识，sm e e r a n 和 mjp r a t t f l 8 1 尝试了从图纸中直接识别出加工特征，用作n c 加工的输入数据。他 们使用了p r o l o g 作为工具，将d x f 文件读入处理后作为p r o l o g 中的原子，用 专家推理识别出特征。除了槽、孔的孤立特征外，简单特征的相交情况也能被 识别出来。 第一章绪论浙江大学硕士学位论文 3 基于专家系统的重建方法 基于专家系统的重建方法从人工智能、专家系统的角度出发，按照人工智 能、专家系统研究问题的方法建立有关识别的知识库、揄机制和搜索策略来进 行识别。v a x i v i e r ea n dt o m b r e 算法运用基于规则的专家系统开发语言o p s 5 来 建立大量的识别规则。推理策略是数据去驱动的，可以很容易地被o p s 5 的匹 配一工作控制策略执行。产生试图匹配实体目标的三维边和相应的视图上的二 维边。算法仅能识别一些很简单的平面体，而且仅生成三维边，没有形成三维 面和体。其他学者也提出一些基于专家系统的重建方法，但都不能处理多解和 病态解情况，而且不能识别复杂的实体目标。 基于专家系统方法的识别能够有效地表示知识和知识推理，从而提高了建 立识别算法的效率，因此大有可为。但目前建立的仍是一些试验性系统。而且 当体素变得比较复杂时，很难用人工的方式建立起体素的识别模式。另外，当 专家系统变得庞大以后，识别复杂实体的速度和知识库的使用效率也会受到影 响。 1 4 现有重建算法存在的问题 尽管经过了二十多年的努力，人们仍未能提供个完整、实际的三维重建 方案。三维重建要的数据对象是二维的工程图信息，显而易见的事实是：由三 维形体可以简单地得到低维的图形信息，而要从已经在降维过程中遗失了一部 分拓扑信息的二维图形中去恢复原有的三维物体则复杂多了。 宾夕法尼亚州立大学的研究主要在多视图处理上有了一定的突破，并提出 的一个较完整的解决方案。但他们所处理的多视图及辅助视图和我国国标的表 达手段不够一致，剖视、剖面等表达方式没有被处理，而剖视图可以有效的表 达零件的外部轮廓，同时又可以清晰的表示出零件的内部结构，是实际工程图 样中的常用表达方法，所以其所述的算法不能得到实际的应用。 模型引导方法通过子体的并交差运算，直接从视图中按模式匹配的思想进 行识别，提取出各基体，生成c s g 树或其它的表达形式，最后得到零件的实体 模型。它从假定的子体出发，寻找相应的三视图投影加以验证，从而避免了自 底向上方法中对三维图形基元的庞大搜索和消除操作，速度极快，效率高，算 法也比较简单，有一定的实用价值，可以对规则的形体进行有效的识别与重建， 但是工程中的三视图情况并不总是象算法要求的那样理想，例如在圆柱体的识 别中，模型引导方法可以有效的识别出工程图样中的完整圆柱体，但由于机械 零件中体与体之间的相交，面的切削导致不完整圆柱体的出现，使得视图中圆 柱体模型无从匹配，或者错误解的出现。而在复杂的多面体识别过程中，由于 多面体的不规则性，很难找到合适的子体模型，因此在对复杂的多面体识别时 则显得束手无策。 自底向上的识别方法是从二维图形的点和线等基本图元出发的，能够有效 的识别复杂的多面体，但这类算法的识别方法并不是有经验的工程师的看图方 第一章绪论浙江大学硕士学位论文 3 基于专家系统的重建方法 基于专家系统的重建方法从人工智能、专家系统的角度出发，按照人工智 能、专家系统研究问题的方法建立有关识别的知识库、揄机制和搜索策略来进 行识别。v a x i v i e r ea n dt o m b r e 算法运用基于规则的专家系统开发语言o p s 5 来 建立大量的识别规则。推理策略是数据去驱动的，可以很容易地被o p s 5 的匹 配一工作控制策略执行。产生试图匹配实体目标的三维边和相应的视图上的二 维边。算法仅能识别一些很简单的平面体，而且仅生成三维边，没有形成三维 面和体。其他学者也提出一些基于专家系统的重建方法，但都不能处理多解和 病态解情况，而且不能识别复杂的实体目标。 基于专家系统方法的识别能够有效地表示知识和知识推理，从而提高了建 立识别算法的效率，因此大有可为。但目前建立的仍是一些试验性系统。而且 当体素变得比较复杂时，很难用人工的方式建立起体素的识别模式。另外，当 专家系统变得庞大以后，识别复杂实体的速度和知识库的使用效率也会受到影 响。 1 4 现有重建算法存在的问题 尽管经过了二十多年的努力，人们仍未能提供个完整、实际的三维重建 方案。三维重建要的数据对象是二维的工程图信息，显而易见的事实是：由三 维形体可以简单地得到低维的图形信息，而要从已经在降维过程中遗失了一部 分拓扑信息的二维图形中去恢复原有的三维物体则复杂多了。 宾夕法尼亚州立大学的研究主要在多视图处理上有了一定的突破，并提出 的一个较完整的解决方案。但他们所处理的多视图及辅助视图和我国国标的表 达手段不够一致，剖视、剖面等表达方式没有被处理，而剖视图可以有效的表 达零件的外部轮廓，同时又可以清晰的表示出零件的内部结构，是实际工程图 样中的常用表达方法，所以其所述的算法不能得到实际的应用。 模型引导方法通过子体的并交差运算，直接从视图中按模式匹配的思想进 行识别，提取出各基体，生成c s g 树或其它的表达形式，最后得到零件的实体 模型。它从假定的子体出发，寻找相应的三视图投影加以验证，从而避免了自 底向上方法中对三维图形基元的庞大搜索和消除操作，速度极快，效率高，算 法也比较简单，有一定的实用价值，可以对规则的形体进行有效的识别与重建， 但是工程中的三视图情况并不总是象算法要求的那样理想，例如在圆柱体的识 别中，模型引导方法可以有效的识别出工程图样中的完整圆柱体，但由于机械 零件中体与体之间的相交，面的切削导致不完整圆柱体的出现，使得视图中圆 柱体模型无从匹配，或者错误解的出现。而在复杂的多面体识别过程中，由于 多面体的不规则性，很难找到合适的子体模型，因此在对复杂的多面体识别时 则显得束手无策。 自底向上的识别方法是从二维图形的点和线等基本图元出发的，能够有效 的识别复杂的多面体，但这类算法的识别方法并不是有经验的工程师的看图方 第一章绪论 浙江大学硕士学位论文 法，并且由于这类算法要进行复杂的判定以消除大量存在的虚假三维图形基元， 因而搜索量过大，效率太低，不能得到广泛的应用。从更高层次的图形语义出 发，使自底向上的识别算法更加符合工程师的看图方法，是提高自底向上识别 算法效率的最有效手段。 1 5 本文工作及特点 本课题从二维视图重建三维形体的基本思路是，通过各种层次的预处理， 将读入的图形信息进行处理，使其成为信息完备并且适于计算机处理的数据信 息，然后从中间层次的面出发，总结圆柱面的投影约束规则，据此识别出视图 中的完整圆柱面和不完整圆柱面；与圆柱面的识别相结合，总结各种位置平面 在视图中的投影约束关系，据此识别视图中出现的各种位置平面，完成从二维 信息重建三维形体的整个过程。 ( 1 ) 视图识别以及面向工程图样的预处理 介绍了直接面向工程图样的预处理，与工程语义的层次划分相对应，本文 所述的预处理也分为两个层面，在表达方式预处理中，本文着重讨论了全剖视 图和半剖视图的自动识别和预处理，并给出了具体的算法；在投影关系预处理 中，本文简单介绍了图元整理、打断、连通域搜索等思想。通过面向实际工程 图样的预处理，解决了传统的三维重建方法不能处理剖视图的问题，同时为圆 柱面的特征识别和平面的识别及重建打下了坚实的基础。 ( 2 ) 各种圆柱面的识别 圆柱体通常是由一个圆柱面和两端的平面包围而成，本文讨论分析了圆柱 体的投影特征，并着重分析了不完整圆柱面的投影规律。不同与传统的重建算 法，本文引入将圆柱面进行分割与组合的思想，首先将圆柱面沿其主特征投影 积聚圆上的分割点将其主特征投影分割，接下来在相应的视图中与分割点相对 应的位置加线，根据分割加线后的视图，先分别重建成出不完整圆柱面的各个 部分，然后组合出整个圆柱面，完成各种不完整圆柱面的重建。在不完整圆柱 面的重建算法中有一个极为重要的问题，那就是封闭环的组合与合并，本文在 介绍不完整圆柱面重建算法的同时，还讨论了封闭环的组合与合并的算法，这 对平面的识别与重建也是至关重要的。 ( 3 ) 各种位置平面的识别 本文讨论的平面的识别与重建思想不同于传统的自底向上的重建方法，传 统的自底向上的重建方法是从二维顶点出发，生成三维顶点，由三维顶点生成 三维边，由三维边构造三维面，由三维面合成三维目标形体；本文所讨论的方 法直接从面的角度出发，介于传统的自底向上的算法和模型引导方法之间，比 较贴近人类看一些表达不规则体的图纸时的思维习惯。通过分析直线和平面的 正投影规则，得出平面的投影规律，总结线段和封闭环的投影约束关系，然后 第一章绪论 浙江大学硕士学位论文 法，并且由于这类算法要进行复杂的判定以消除大量存在的虚假三维图形基元， 因而搜索量过大，效率太低，不能得到广泛的应用。从更高层次的图形语义出 发，使自底向上的识别算法更加符合工程师的看图方法，是提高自底向上识别 算法效率的最有效手段。 1 5 本文工作及特点 本课题从二维视图重建三维形体的基本思路是，通过各种层次的预处理， 将读入的图形信息进行处理，使其成为信息完备并且适于计算机处理的数据信 息，然后从中间层次的面出发，总结圆柱面的投影约束规则，据此识别出视图 中的完整圆柱面和不完整圆柱面；与圆柱面的识别相结合，总结各种位置平面 在视图中的投影约束关系，据此识别视图中出现的各种位置平面，完成从二维 信息重建三维形体的整个过程。 ( 1 ) 视图识别以及面向工程图样的预处理 介绍了直接面向工程图样的预处理，与工程语义的层次划分相对应，本文 所述的预处理也分为两个层面，在表达方式预处理中，本文着重讨论了全剖视 图和半剖视图的自动识别和预处理，并给出了具体的算法；在投影关系预处理 中，本文简单介绍了图元整理、打断、连通域搜索等思想。通过面向实际工程 图样的预处理，解决了传统的三维重建方法不能处理剖视图的问题，同时为圆 柱面的特征识别和平面的识别及重建打下了坚实的基础。 ( 2 ) 各种圆柱面的识别 圆柱体通常是由一个圆柱面和两端的平面包围而成，本文讨论分析了圆柱 体的投影特征，并着重分析了不完整圆柱面的投影规律。不同与传统的重建算 法，本文引入将圆柱面进行分割与组合的思想，首先将圆柱面沿其主特征投影 积聚圆上的分割点将其主特征投影分割，接下来在相应的视图中与分割点相对 应的位置加线，根据分割加线后的视图，先分别重建成出不完整圆柱面的各个 部分，然后组合出整个圆柱面，完成各种不完整圆柱面的重建。在不完整圆柱 面的重建算法中有一个极为重要的问题，那就是封闭环的组合与合并，本文在 介绍不完整圆柱面重建算法的同时，还讨论了封闭环的组合与合并的算法，这 对平面的识别与重建也是至关重要的。 ( 3 ) 各种位置平面的识别 本文讨论的平面的识别与重建思想不同于传统的自底向上的重建方法，传 统的自底向上的重建方法是从二维顶点出发，生成三维顶点，由三维顶点生成 三维边，由三维边构造三维面，由三维面合成三维目标形体；本文所讨论的方 法直接从面的角度出发，介于传统的自底向上的算法和模型引导方法之间，比 较贴近人类看一些表达不规则体的图纸时的思维习惯。通过分析直线和平面的 正投影规则，得出平面的投影规律，总结线段和封闭环的投影约束关系，然后 羔二望- 堕笙一 塑坚查堂璺主兰垒笙茎 在所有图元空间中进行组合匹配，搜索出需要莛建的面的特征。这种算法可以 和曲面立体的特征识别很好的融合在起，解决比较复杂的工程图样。 图l1 是本算法思想实现的原型系统的总流程图： 圈1 1 总流程图 本文工作其有以下特点： q ) 怂中闯层次切入。不同于传统的自底向上的重建算法和自顶向下的模型引 妻箩娑，本文从中间层次的面出发来理解工程图