（机械设计及理论专业论文）线画图标记中的异常节点处理研究.pdf

雨北t 业人学倾士学位论文 摘要 线画图标记中异常节点的处理研究 摘要 本文系陕西省自然科学基金( 2 0 0 2 e ：2 4 ) ，江西省自然科学基金( 0 3 1 1 0 1 8 ) ， 南昌航空工业学院测试技术与控制工程研究中心基金( 2 0 0 3 - - 0 1 3 ) 资助项目的 一部分。 计算机视觉研究的目的就是使计算机具有像人类一样的视觉能力，使机器能 够像人一样观察视力范围内的景物，理解它所看到的景物状态，依掘程序做出相 应的反应。 三维物体重建是计算机视觉研究领域中的一项重要内容，而线画图的机器解 释是三维重建的一种重要方法。当三维场景投影成二维图像时，许多三维信息就 会被丢失，三维重建的目的就是要恢复这些丢失的信息。 线画图标记作为一种行之有效的手段，在由线画图重建场景三维结构的研究 中起着重要作用。它能够排除三维场景不可能的情况，利用图中的节点和线的信 息，进行简单的预测，为线画图的定量分桥减少工作量。 不少学者对线画图的标记理论和方法都进行了深入研究，提出了各种标记方 法，但是在实际情况中，从图像得到的物体的线画图，因提取方法等的原因，线 条不能正确连接，常常存在缺线或多线等现象，这样就使得线画图的标记无法进 彳亍下去，从而就不能正确解释和识别图像所表示的物体。 本文主要研究对不完整线画图中的多余线和缺线进行处理的问题。利用现有 的平面立体线画图标记理论和方法，基于合理的节点标记形式，详细分析了在存 在多余线和缺线的情况下线画图中节点的变化情况，把不完整线画图中存在的多 线和缺线情况与节点形式紧密联系起来，把判断个线画图中的缺线或多线转化 为判断线画图中的节点是否为合法节点的问题，推出了在存在缺线的情况下合法 节点的退化形式，提出了种补全线的有效方法，并提出了一种判断线画图中存 在多余线的方法。为了有利于计算机对线画图的有效分析和处理，给出了计算机 处理不完整线画图的操作流程，研制了相应的几个操作模块。 芙键词：不完整线画图，标记，平面立体，节点，补线，删除线，多余线 两j l 工业_ 大学硕i 。学位论文 摘要 m a k i n gi m p e r f e c tl i n ed ra w i n gi n t 0p e r f e c t t h r o u g ha d d i n ga n dd e l e t i n gl i n e s u s i n gl a b e l s a b s t r a c t t h i sm a s t e rt h e s i si st h ep r o j e c ts u p p o r t e db yn a t u r a ls c i e n c ef o u n d a t i o n o fs h a a n x i p r o v i n c e ( 2 0 0 2 e 2 2 4 ) ，j i a n g x ip r o v i n c e ( n o 0 3 1 1 0 1 8 ) ，a n do p e n f o u n d a t i o no fr e s e a r c hc e n t e ro f m e a s u r i n gt e c h n o l o g i e s a n dc o n t r o l e n g i n e e r i n go fj i a n g x ip r o v i n c e ( n o 2 0 0 3 - 0 1 3 ) o n eg o a lo fc o m p u t e rv i s i o nr e s e a r c hi st o g i v ec o m p u t e r sh u m a n l i k ev i s u a l c a p a b i l i t i e s s ot h a tm a c h i n e sc a ns e n s et h ee n v i r o n m e n ti nt h e i rf i e l do fv i e w ， u n d e r s t a n dw h a ti sb e i n gs e n s e d ，a n dt a k ea p p r o p r i a t ea c t i o n sa sp r o g r a m m e d r e c o v e r i n g t h et h r e e d i m e n s i o n a ls c e n e sf r o map r o j e c t e d i m a g e o ral i n e d r a w i n gi s a ni m p o r t a n tp r o b l e mi nc o m p u t a t i o n a lv i s i o n w h e nat h r e e - d i m e n s i o n a l s c e n ei sp r o j e c t e dt oat w o d i m e n s i o n a li m a g e ，al o to f t h r e e d i m e n s i o n a li n f o r m a t i o n w a sl o s t ，a n dt h eg o a lo ft h et h r e e d i m e n s i o n a ls c e n e sr e s t o r a t i o ni st or e c o v e rt h el o s t i n f o n n a t i o n t h el a b e l so fal i n ed r a w i n ga sa l le f f i c i e n tm e 也o di st a k ep a r ti nr e c o v e r i n gt h e t h r e e d i m e n s i o n a ls c e n ef r o mt h el i n ed r a w i n g m a n yi m p o s s i b l ec o n f i g u r a t i o n sc a n b ee x c l u d e db yc o n s i s t e n tl a b e l i n g ，u s i n gt h ei n f o r m a t i o no fl i n e sa n d j u n c t i o n si nt h e l i n ed r a w i n gt of o r e c a s ts i m p l y , s oi tc a nr e d u c ew o r k l o a di nq u a n t i t a t i v ea n a l y s i s m a n ys c h o l a r sh a v ed o n eal o to fw o r k si ns t u d yt h et h e o r i e sa n dm e t h o d si n l a b e l i n gal i n ed r a w i n g ，a n dp r o p o s e dm a n ye f f e c t u a lm e t h o d s b u ti nf a c t ，t h el i n e s a r en o tl i n k e di nt h el i n e d r a w i n gw ee x t r a c t e df r o mt h ep r o j e c t e di m a g ei nm a n y c a s e s ，t h u st h el a b e l i n gc o u l dn o tb ep r o g r e s s e df a r t h e r ，a n db en o ti n t e r p r e t e da n d r e c o g n i z e do b j e c t st h ep r o j e c t e di m a g ed e n o t e d i nt h i st h e s i s ，w em a i n l ys t u d yt h em e t h o df o r d e l e t i n gt h ef a l s el i n e sa n da d d i n g t h em i s s i n gl i n e si na ni m p e r f e c tl i n ed r a w i n g ，a n dm a k et h ei m p e r f e c tl i n ed r a w i n g i n t oap e r f e c t u s i n gt h ee x i s t e dt h e o r i e sa n dm e t h o d so f l a b e l i n go n ap l a n a ro b j e c t ， a l lp o s s i b l ec o n f i g u r a t i o n so f i m p e r f e c tl i n ed r a w i n gh a v eb e e ne x h a u s t i v e l ys t u d i e d ， a n di ti sf o u n dt h a ti m p e r f e c tl i n ed r a w i n g sa r ec l o s e l yr e l a t e dt o j u n c t i o nf o r m i na p e r f e c tl i n ed r a w i n g ，t h e r ea r eh a sj u s tt h r e el i n e sb e l o n g e dt oe v e r y j u n c t i o n b u ti n a ni m p e r f e c tl i n ed r a w i n g ，t h e r em u s tb e j u n c t i o n sw h i c hc o n n e c tl i n en u m b e r sb en o t e q u a lt ot h r e e ，t h a ti sm o r eo rl e s s a ne f f i c i e n tm e t h o df o rc o m p l e t i n gt h ei m p e r f e c t i i 西j e 工业大学硕士学位论文 摘要 l i n ed r a w i n g t h r o u g ha d d i n g t h em i s s i n gl i n e sa n d d e l e t i n gt h ef a l s eo n e s i sp r o p o s e d a n df o rt h es a k eo f s i m p l eo p e r a t i o ni nc o m p u t e r , s e v e r a lo p e r a t i o nm o d u l e sa n dt h e f l o wa r ep r o p o s e d ac o m p u t e ri m p l e m e n t so p e r a t i o n sf o ra d d i n ga n dd e l e t i n gl i n e s i na ni m p e r f e c tl i n ed r a w i n g a u t o m a t i c a l l y k e y u 7 0 r d s ：i m p e r f e c tl i n ed r a w i n g ；l a b e l i n g ；p l a n a ro b j e c t ；j u n c t i o n ；a d d i n gl i n e ；d e l e t i n g l i n e ：f a l s el i n e i l l 两 t = 业大学坝上学位论文 第一章绪论 第一章绪论 1 1 计算机视觉的研究内容 计算机视觉是研究用机器代替人的眼睛和大脑，对客观世界进行视觉感知和 解释，实现对客观的三维世界的识别的学科。八十年代以来，计算机视觉的研究 已经历了从实验室走向实际应用的发展阶段。从简单的二值图像处理到高分辨率 多灰度的图像处理，从一般的二维信息处理到三维视觉机理以及模型和算法的研 究都取得了很大的进展。而计算机水平的飞速提高以及人工智能、并行处理和神 经元网络等学科的发展，更促进了计算机视觉系统的实用化和涉足许多复杂视觉 过程的研究。目前，计算机视觉系统正在广泛地应用于视觉检测、机器人的视觉 引导、物体识别、目标跟踪和自动化装配领域中。 机器视觉系统是指用计算机来实现人的视觉功能，也就是用计算机来实现对 客观的三维世界的识别。按现在的理解，人类视觉系统的感受部分是视网膜，它 是一个二维采样系统。三维的物体的可见部分投影到视网膜上，人们按照投影到 视网膜上的二维的像来对该物体进行三维的理解。所谓三维的理解是指对物体的 形状、尺寸、离开观察点的距离、质地和运动特征的理解。计算机视觉希望解决 的是完全相同的问题。计算机视觉系统的输入装置可以是摄像机、转鼓等，它们 都把三维的影像作为输入源，即输入计算机的就是三维客观世界的二维投影。如 果把三维客观世界到二维投影像看作是一种正变换的话，那么计算机视觉系统所 要做的是从这种二维投影像到三维客观世界的逆变换，也就是根据这种二维投影 像去重建三维的客观世雾。从三维客观世界至0 二维投影像，有一维信息从显露成 为隐含，计算机视觉系统的工作就是要把这种隐含的三维信息提取出来，进行理 解加工。 计算机视觉与模式识别是计算机科学与人工智能研究领域的重要分支，计算 机视觉的研究目的：一是提供人类视觉的计算模型：二是利用计算机来设计与发 展某种真实的、适度的视觉系统，并提供具有良好性能价格比的专用系统。前者 是关于计算神经学的基础性研究，而后者往往涉及很强的应用性和工程性问题。 两j l t 业入学硕- f 学位论文 篱一章绪论 模式识别研究的基本目的是赋予机器类似物的莱种信息处理能力。因而在计算机 视觉应用系统的研究中，往往要利用模式识别的一些基本技术和方法。 1 2 线画图研究的内容及发展现状 三维物体的重建是计算机视觉研究领域的重要问题之一。当三维场景投影成 二维图像时，许多三维信息就会被丢失，三维重建的目的就是要恢复这些被丢失 的信息。线画图的机器解释是三维重建的一个重要方法。在很多情况下，人们用 线画图来描述物体的三维形状，如三视图、轴测投影图、透视图。虽然线画图是 由一些平面上的线段组成，但它表达了三维景物中物体结构的许多信息，人们可 以很容易地理解线画图所表达的物体。 线画图是物理成像的结果，它忽略了表面材质等细节，可见线段用实线表示， 不可见线段用虚线表示，这些都是人为的规定，这是线画图的符号性。线画图广 泛用于工程实际中，如机器零件的工程图、一般物体的说明图等。 长期以来，人们一直在画法几何中研究三维物体的线画图，即如何在二维平 面上描述物体的三维结构，并己形成了成熟的理论和方法。而对其逆问题如 何由线画图重构三维物体结构的研究，是在计算机能处理图像数据以后才引起人 们注意，一方面，对人而言，可凭借常识和人类感知器，确定线画图所代表的三 维物体结构，另一方面，对计算机面言，线画图是一个二维平面上线段的集合， 由于线画图含有二义性，会产生多种空问结构的理解，此外，线图的略微误差， 可能会导致线画图对应的物体不存在，如图1 1 ，我们一般把它理解为棱台，但 圈l ，1 在严格数学意义上，它是不正确的，因为棱台的三条棱边应交于同一点而从图 中可以看到它们并不交于点，故在数学意义上该线画图不是棱台的投影，但人 两北工业入学碗士学位论文第一章绪论 们仍把它看作棱台，因此我们在研究线画图的过程中不能将其看作纯数学意义上 帕结果。 从线画图识别它所表示的三维物体的研究开始于上世纪6 0 年代，r o b e r t 最 早提出了建立目标模型和匹配理解的方法，并应用于物体识别。各个多面体的模 型由其顶点及其多边形形成的特征集组成，输入图像经分析处理可以形成线画 图，将其和能从不同观察点作透视变换的模型进行匹配，选择最佳的匹配作为识 别结果。这种方法由于知道了目标属于哪种模型，也可以提供任何观察角度下这 科，模型的成像，r o b e r t 所识别的多面体如图1 2 所示。该系统要求较强的假设， 即成像物体完全分离，能完全提取线画图，而且存放的目标有限，该系统不适宜 于识别多类目标，当存在隐藏边时要增加计算量，但这种方法为基于模型的线画 图解释提供了基础，使物体可从一定数量与定义好的原型中获得。 囝 幽1 - 2 r o b e r t 方法识别的部分多面体 随后，g u z m a n 圳提出t s e e 程序，采用的是区域分割的方法。这个程序 不用预先存贮模型，可从线画图识别多面体。这个程序第一次引入了启发性知识， 同时首次用符号处理代替数字匹配过程，适合大多数复杂线画图，该程序的不足 之处在于难于分析、预报物体性能，不能识别有洞目标。 f a l k “1 平1 g r a p e 进一步发展了基于模型的线画图解释，从而能处理不完整的 线画图和部分被遮挡的物体。 从二维投影提取物体的三维信息的研究导致发展了许多技术，诸如由灰度恢 复结构、由纹理恢复结构、由轮廓恢复结构。在所有单目视觉中，二维轮廓是最 重要的一种，早期由轮廓恢复结构的工作主要集中在多面体世界，利用二维线画 图的线标记、灭点、对称性等约束重构三维结构，每种约束都能有效地限制可能 的三维物体解释的数量，但不能唯一确定三维物体形状，为了综合各种二维约束， 提出了许多基于规则的系统。 标记法作为一种行之有效的辅助手段被引入解释三维景物的研究中，对平 西j e 工业人学硕十学位论文 第一章绪论 面物体和曲面物体引入线和节点的标记是有效的，标记类型覆盖了各类平面物 体和曲面物体的所有有效投影。为了解释三维景物，人们提出了一系列的标记 算法。 1 9 7 1 年，h u f f m a n “1 $ 口c l o w e s 1 分别独立地针对三面顶点组成的平面体提 出了标记理论和方法，对线画图中节点处线的结构进行了分析，根据凸棱、凹棱 及遮挡棱给线条赋以四种标记：“+ ”、“一”、“一”、“一”，得到了合理的 节点形式，称为h u f f r n a n c l o w e s 标记法，该标记方法的有效性已在许多种类线图 解释中得到证明。但h u f f m a n c l o w e s 标记法主要考虑的是物体与线图几何结构和 拓扑结构的一致性，只能标记没有画出隐藏线的线图。 w a l t z 6 1 1 对h u f f m a n ，c l o w c s 标记法进行了推广，使线段的标记分类由凹棱、 凸棱及遮挡棱延拓至阴影棱、裂缝棱等，因而能处理l t h u f f m a n 更为一般的情况， 但其最终的顶点库有好几千个基元。 s u g i h a r a 蛸。1 提出的解释立体线图机理也采用了对线条进行标记的方法，标 记方法与h u f f m a n c l o w e s 标记法类似，s u g i h a r a 的标记方法可以标记画出隐藏线 的线图，但线图中隐藏线的画法有些不符合人们的画图习惯。s u g i h a r a 把线图结 构分为：几何结构、拓扑结构、代数结构和组合结构4 个方面，研究了正确线图 与不正确线图之间的区别，用代数的方法给出了一个线图表示一个三维平面物体 的充要条件。其主要依据的是平面立体上顶点与平面间的从属关系，但这种约束 是建立在方程组可解性的基础上，是判别性而非构造性。 署 1 s u g i h a r a - - 样，s h i m s h o n i 。n 1 也利用一组线性等式和不等式对平面立体 线画图建立了约束条件，但是明确考虑了节点位置的不确定性，对于一个给定的 误差范围，把判断一幅线画图是否为个平面立体投影的问题降低为线性求解问 题，使三维形状恢复在线性约束下得到优化。 魏湘曙1 1 3 1 引入对偶原理找到了线画图的四个基本约束，并证明这四个基本 约束是二维形态制约三维形态的充分必要条件，它们是构造性的，利用这四个基 本约束可建立相应的求解算子，可以对二维线画图进行递推求解。从理论上讲， 月魏湘曙所提出的四个约束来完成线画图求解是可行的，但在实际求锯过程中， 对大量有误差的线画图将会得到不存在的结论，而我们的视觉系统却接受这些线 画图。针对这种情况，封举富4 1 等在此基础上引入了一个与存在性约束相容的 西北工业人学硕士学位论文 第一章绪沦 误差校正策略，从而对节点位置有偏差的线画图也能恢复平面立体的三维形态。 t u r n e r 5 ，讨论了光滑曲面立体的标记情况，但导出的合理的节点形式达好 几万种，不利于计算机进行检索和匹配；k a n a d e 6 。7 1 则考虑纸折体的情况，证 明了线画图具有某些对称性时可从其推断出物体的三维形状，在他的对象集中， 还包括了平面立体的室内景物。c h a k r a v a r t y “粕提出了一种基于区域的曲面立体 标记技术，可处理多种类型的曲面立体，且顶点分类只有七种，远l l t u m e r 的要 简单。l e e 和h a r a l i c k 9 1 提出了一种适合于平面立体和曲面立体线画图标记方法， 用标记信息组合属于同一个物体的表面区域并估计隐藏节点类型。他们对 c h a k r a v a r t y 的标记作了一些修改，不仅用节点标记而且用线的标记，并总结了 标记的一般过程：获得图像或线画图，并进行数字化处理：通过边缘检测和 标记的方法获得线、区域、顶点的链码数据文件；搜索外围轮廓线并标以箭头 符号；搜索每个区域边缘进行标记、组合以获得更有效的搜索。 潘峰等人“邮详细考察了曲面立体与多面立体的异同点，提出了一种曲面立 体标记的新方法。它继续沿用h u f f m a n 对各种棱的定义，通过引入线段的一些新 的标记类型，解决了在曲面体标记过程中可能出现的不一致性。 p o n e “”把物体简化为轴线为直线的广义圆柱体，提出了关于这种物体的几 何和高斯曲率的严格数学研究，证明了s h g c 的一些新特性，并转化为由图像轮 廓恢复三维描述的算法。u l u p i n a r 2 2 1 建立了透视投影下线画图解释的一些约束 关系，研究了高斯曲率为零的可展曲面、轴线为直线的广义圆柱体以及轴线为任 意曲线但截面为不变图形的广义圆柱体的线画图解释问题。s h a f e r 将梯度空间方 法扩展到透视投影线画图中，从而得到图形的梯度信息和深度信息来进行三维重 建。 m a l i k 年 i m a y d a n 呓3 2 4 1 在过去线画图解释的基础上，利用标记约束和灰度约 束，对不透明规则物体及分段光滑由面物体提出了一种新的算法，可从二维图像 恢复物体的三维形态，即表面方向及相对深度。c o o p e r 呓5 3 0 分析了由分段c 3 连 续的曲面物体组成的场景的线画图解释问题，关于节点类型的讨论说明了线图标 记实现的充要条件，当所有灭点可知时，标记问题在线性时间内是可解的并给出 了相应的算法。当不是所有灭点可知时，标记问题是一个n p 问题。 p a r o d iq 。”1 等人对线画图标记的复杂性进行了深入研究分析后发现，在线 堕! ! 三些生兰堡主兰堡堡兰 兰二童! ! 鱼 画图标记中，只要选取合适的算法，线画图标记的复杂程度一般是和线画图的节 点的数目成线性增长的。 d i n g # d t z a v 1 对不完整线画图解释作了分析，特别是线画图中的l 型节点 的特性。建立了由不完整线画图数据的输入到三维物体形态的完全输出的系统， 把完整线画图看作系统的特例。 鲁字明m 1 针对画隐线画图，修改了关于平面立体的标记形式，分析了曲面 立体的一些特殊情况，提出了一种出现在曲面立体画隐线画图中的v 型节点，从 而进一步完善了画隐线画图的标记形式。 1 3 本论文的工作 本文主要研究对不完整线画图中的多余线和缺线进行处理的问题。利用现有 的平面立体线画图标记理论和方法，基于合理的节点标记形式，详细分析了在存 在多余线和缺线的情况下线画图中节点的变化情况，把不完整线画图中存在的多 线和缺线情况与节点形式紧密联系起来，把判断一个线画图中的缺线或多线转化 为判断线画图中的节点是否为合法节点的问题，推出了在存在缺线的情况下合法 节点退化成的3 6 种“v ”型节点形式和8 种“一”字型节点形式，提出了一种 补全缺线的有效方法，并提出了一种判断线画图中存在多余线的方法。为了有利 于计算机对线画图的有效分析和处理，给出了计算机处理不完整线画图的揉作流 程，研制了相应的几个操作模块。 本文共分为如下几章： 第一章介绍了计算机视觉研究的内容，简单介绍了线画图计算机解释在其研 究领域中的作用及线画图标记研究的发展现状。 第二章阐述了线画图解释中已有的理论和方法。 第三章利用画隐线画图的标记理论和方法，详细分析了2 4 种合法节点形式在 缺线情况下的退化型式，提出了线画图在缺线情况下的3 6 种“v ”型节点形式和8 种“一”字型节点形式，以及线画图中存在多余线时节点可能出现的形式，提出 了一种补全丢失线和删除多余线条的有效算法。此外，对于节点丢失的悬挂线， 6 西北t 业，：学硕= l 学位论文 进行了简单的探讨。 第四章以实例 最后一章即第 本文的创新点 第一章绪论 研制了线画图计算机处理的几个操作模块。 方法，从计算机实现角度验证了所提出的算法的有效性 章是对本文工作的一个总结以及对后续工作研究的展望 ( 1 ) 把线画图中存在的多线和缺线问题与线画图中的节点形式联系了起来 利用线画图中节点的连线数来判断线画图中是否存在多线和缺线。 ( 2 ) 提出了判断线画图中存在多线的一种有效方法，并给出了相应的识别删 除方法。 ( 3 ) 提出了线画图在缺线情况下的3 6 种“v ”型节点形式和8 种“一”字型节 点形式，并给出了相应的补线方法。 的五 ： 西北工业大学碗士学位论文 第二章线画图的标记理论和方甚 第二章线画图的标记理论和方法 线画图一直是人们之间以及人与计算机之间交换三维物体( 或场景) 信息的 一种重要媒介。人们理解一幅三维物体或场景的投影线画图毫不费力，但对计算 机来说，理解一幅投影线画图就存在很大的困难。计算机自动解释投影线画图是 计算机视觉系统或计算机辅助设计( c a d ) 系统研制中的一个重要问题。如计 算机视觉系统理解一幅三维场景的图像时，第一步是利用边缘检测、区域分析技 术从图像得到线画图；第二步是理解线画图，以得到三维场景的描述。在c a d 系统中，图形信息输入问题是人们普遍关注的问题之一，是一个非常重要又非常 困难懂得问题。目前，把三维物体模型信息输入到计算机内大致有三种方法：一 是用一套专用指令去填充预先定义好的数据结构；二是定义若干体素，用集合运 算的方法构造模型；三是通过输入、解释二维投影图以获取三维信息。最后一种 方法，由于符合设计者的思维形式，且应用方便，因此越来越受到人们的重视。 在输入二维投影图中，可以输入物体的三视图( 或零件图) ，也可以输入物体的轴 测投影图或透视投影图。在计算机解释物体的三视图或零件图研究中，存在的主 要问题之一是如何扩展形体的覆盖域，这是这种输入模型信息方法尚未在c a d 系 统中广泛应用的一个重要原因。而计算机解释轴测投影图或透视投影图时，尽管 仍存在扩展形体的覆盖域的问题，但相对来说比较容易解决。 2 1 ，1 基本概念 2 ，1 线画图的基本概念和假设 考虑的平面立体是由确定数量的平面围成的三维实体。两个平面的交线称为 棱边，简称为棱。棱边的交点称为端点，也可称为顶点。物体不是简单的平面 立体，可能有空洞，这里所讨论的线画图仅限于表示平面立体的投影图。一个线 画图是由一定数量的直线段组成n _ - 维图形，“线段”简称为线，“线的端点” 简称为节点，“通过节点”指的是两条线或多条线交于一点，“直线”指的是 被节点分成的最短直线段，直线间没有其它节点。 两北工业大学硕士学位论文第二章线画图的标记理论和方法 2 1 2 基本假设 景物中的边线在图像上的投影组成景物的线画图，为适合实际应用领域，本 文所述线画图为手画或通过数字图像处理所得。有些线画图常常具有多义性，如 图1 1 所示的线画图也可把它看作一个空间中四个漂浮物体经过调整的结果， 如图2 1 所示，这是可能的，但人们几乎没有产生过这种解释，这说明在解释 幽2 1 不合理但可能的线l 里i 图 这些线画图时经常需要利用日常生活知识来排除异常解释，对计算机来说可能需 要训练。为排除线画图的多义性，使依据线画图解释的立体为真实的平面立体、 线图为真正的透视投影图或轴测投影图( 可以有小的误差) ，同时也避免病态情 况出现，需要做一些基本假设： 假设1 对于每一平面，它的一边被有形物质占据而另一边是空的。因此不 必考虑平面片物体的情况，如一张纸。 假设2 在投影图中仅画出平面立体上棱线和顶点的投影。可见棱线用粗实 线表示，不可见的棱线用虚线表示。因此，物体表面有纹理或覆盖物 都不必考虑。 假设3 物体上的每条棱线仅属于物体上的两个面。因此不必考虑如图2 2 所 示的非自然物体，这里棱e 属于4 个面，两个可见面，两个不可见面。 事实上图2 2 所示的物体是一种“病态”的物体，从工程上来说，是 不合理的物体。 假设4 观察者不与物体任何平面共面。如果观察者与物体上某一平面共面， 此面就投影为直线，假设排除了这种退化情况，在图像平面中每个 西北工业夫学硕士学位论文 第m - - 章线画图的标记理论和方法 平面对应线画图中的非空区域。亦即平面立体上的表面，在透视投 影时不能通过投影中心，在轴测投影时不能平行于投影方向。 图2 2 ：棱线e 属于4 个平面的病态物体 假设5 观察者不与物体任何棱线共线。如果观察者与物体上某一棱线共线 此棱线就投影为点，假设排除了这种退化情况。亦即平面立体上的 棱线，在透视投影时不能通过投影中心，在轴测投影时不能平行于 投影方向。 假设6 物体上两条棱线的投影不能重合。即一条棱线的投影不能落在另一 条棱线的投影上。 21 3 线画图的分类 线画图作为一种表示物体的手段，有两种不同类型的作用。一种是用于计算 机输入，不需要人类常识，通过计算机判断。这要求从计算机的角度设计算法， 另一种是依靠人类常识便能表达物体几何形体，没有严格的数学性。 根据是否画出物体上的不可见棱线( 对曲面立体还有轮廓线) ，将线画图分 为两种：一种是仅画出物体上可见棱线和轮廓线投影的线画图，这种方式产生的 线画图称为自然线画图，也称消隐线画图；另一种是画出物体上所有棱线和轮廓 线投影的线画图，其中可见棱线用实线表示，不可见棱线用虚线表示，这种线画 图2 3 自然线画图图2 4 画隐线画图 西北工业大学硕士学位论文第二章线画图的标记理论和方磕 图称为画出隐藏线的线画图，简称画隐线画图。 图2 3 为自然线画图，图2 4 为画隐线画图。 应注意到，一些线画图既可看作为自然线画图，也可看作为画隐线画图。如 图2 5 ( a ) 所示线画图，当它被看作自然线画图时，它表示有5 个可见面的物体， 图中没有给出物体不可见部分面的任何信息，因此不能确定物体背后是一个平面 还是存在复杂的结构，如图2 5 ( b ) 所示。当该线画图被看作画隐线画图时，则 该线画图不但给出了物体可见部分的信息，而且还给出了物体背面的信息。除非 有特别的说明，这种有二义性的线画图将被看作为自然线画图。 ( a ) 有二义性的线图( b ) 物体背后有复杂结构 图2 5 不同线图所反映的情况 22 1 棱线的分类和标记 2 2 线画图的标记 首先分析画隐线画图，自然线画图是画隐线画图的一种特殊情况。 由于平面立体的许多重要信息，可被包含在边和点组成的线框结构中，而曲 面物体的线框不能表达足够的信息，因此，在计算机视觉研究初始阶段将物体限 制在平面立体。h u f h n a i l 对平面立体棱线进行了分类，现介绍如下。 两个相交平面将空间分为四个区域，如图2 6 所示，称之为象限，依次记为 圆 图2 6 四个象限 西北工业人学硕士学位论文 第二章线画图的标记理论和方法 i 、i i 、i i i 、。用有形物质填满某些象限时，两个平面的交线就形成了物体上 的一条棱线。若在两个连续的象限中填满有形物质，则两个平面的交线就不存在； 若在两个相对的象限中填满有形物质，则交线属于4 个平面，依据假设3 不分析 这类情况。当且仅当用有形物质充满一个或三个象限时，两个平面的交线才能形 成物体上的一条棱线。 不失一般性，考虑画隐线画图的棱线分类，假设观察者位于i 象限，则可根 据属于该棱线的两个面以及观察者之间的相对位置情况，将线画图中的棱线分为 8 种，如图2 7 所示，图2 7 ( a ) 为仅用有形物质填满第三象限时，形成的棱线的两 个面均为可见，此棱称为凸棱，用“+ ”表示。图2 - 7 ( b ) 、( c ) 分别为用有形物 质填满第二象限和第四象限时的情况，棱线是可见的，棱线的两个面中一个面可 见，而另一个面不可见，这种棱称为遮挡棱，用箭头表示。箭头的方向按如下方 式规定：当沿着箭头的方向行走时，可见面总位于该棱线的右边。图2 7 ( d ) 为用 有形物质填满第二象限、第三象限和第四象限时的情况，属于棱线的两个面均为 可见，此棱称为凹棱，用“一”表示。通过交换充满有形物质的象限和空的象限， 可从图( a ) ( b ) ( c ) ( d ) 次得到( e ) ( f ) ( g ) ( h ) ，此时棱为不可见，用虚线表示。把 虚线和实线与四种标记结合起来，就形成了图2 7 所示的8 种标记。 回函时向 ( a )( b )( c )( d ) 固囝回田 ( e )( f ) ( g ) ( h ) 图2 7 八种棱线 西北_ t 业大学硕士学位论文第二章线画图的标记理论和方法 若一幅线画图为自然线画图，则仅用前4 种标记( a ) ( d ) 就可以表示棱线的 类型。 这样每个物体的线画图都有相应的标记，对每个线画图都可对其进行标记分 配，从而得到不同的空间结构的集合，再来判断结构是否正确。对一幅线画图中 所有线作出标记，意味着选择线画图所表示的物体集合中的种物体，若不考虑 物体的物理意义，则一幅含有i 条线的线画图在理论上将有8 。种不同的标记方案， 随着线画图中线的数量增加标记方案种类将成指数倍增加，这对计算机的时问开 销来说是不可能的，况且在8 。种标记对应的8 。种物体中，绝大多数是无意义的。 h u f f m a n 发现，在8 。种标记中，对应客观真实存在的物体的标记只是一个很小的 子集。 2 2 2 节点的分类和标记 虽然景物世界的种类很多，但是占绝大多数的还是h u f f m a n 给出的那些三面 顶点，以上事实可在h u f f m a n 和w a l t z 达成一卜折中，即只对h u f f m a n 的顶点集 进行标记分析，而对那些不包含在h u f f m a l l 顶点集内的顶点( 包括t 型节点) 保 持其含糊性，这样处理比较符合人类视觉特性。 在引入节点分类和一致性标记前，为避免一些无意义的标记，需建立一些规 则： 规则1线画图中的每一条线，必须具有图2 7 中8 种标记之一。 规则2 线画图中的实线的标记应为图2 - 7 中前4 种，即( a ) 、( b ) 、( c ) 、( d ) 。 规则3 线画图的外围轮廓线应为实线，且它的标记为顺时针的箭头。 规则4 在线画图的x 型节点处，共线的线应有相同的标 己。 利用上述规则可以对实际物体进行唯一标记，但上述规则的单独使用并不能 完全排除无意义的标记方案，为此需要对线画图的节点( 对应于物体的顶点) 进 行分类和标记。物体上的顶点是r h - - 个或三个以上的平面相交而形成的，三个平 面相交而形成的顶点称为三面顶点，我们这里只讨论三面顶点。交于个顶点的 三个平面将空间分为八个区域，如图2 8 所示。 运用线标记分类的方法对节点的可能结构进行分类，得到2 4 种节点标记， 如图2 9 所示。 西北工业人学硕士学位论文 第二章线画目的标记理论和力法 图2 8 八个象限 、 ， 、乩z - - - , i 埘、协彬妙 i _ 彬彤串渺 图2 9 2 4 种节点形式 4 丫l - 一 i 百北t 业入学硕士学位论文 第二章线画图的标记理论和方法 这里并不关心节点处各线间的精确角度，只要知道线之间的夹角是大于n 还 是小于n 。三条线的相互夹角都小于n 的节点称为y 型节点，有一个角大于 的节点称为w 型节点。从图2 9 中可以看出，y 型节点有8 种标记形式，w 型 节点有1 6 种标记形式。如果忽略物体的物理意义，w 型节点允许5 1 2 种标记 形式，y 型节点有1 7 6 种标记形式，而在实际上w 型节点只有1 6 种，y 型节 点只有8 种是合法的。这样，节点处的可能结构大为减少，由此得到线画图标 记的又一规则。 规n 5 在一幅线画图上，若属于某一节点的线有且仅有3 条，则属于该 节点的3 条线的标记为图2 - 9 中2 4 种形式之一。 对画隐线画图进行分析可发现，画隐线画图中存在x 、y 、w 三种节点形式， 其中y 、w 型节点是物体的顶点，x 型节点的形成是由于线画图中图线相交所 致，他们并不是物体的顶点。 2 3 约束传播问题 上面已经看到，虽然一个画隐线画图中有l 条线，允许8 。不同标记形式，但 标记方案能使正确的解释结构容纳在一个很小的子集中。要考虑的是花多少时间 选择解，如果只是简单地标记线画图，然后检查是否遵守规则，除非图线的数量 很小，否则要在合理的时间内完成这项工作是不可能的。例如，如果一幅图有 1 5 条线组成，线画图中的线标记的标记形式就达8 ”，即使每种形式需要1 毫秒 的时间进行检查，要检查完所有情况，需要花一年多的时间。 然而，前面介绍的每条规则都能被局部地检查，因此不必分别检查每种被标 记的线画图。例如，如果一个节点的线的标记局部分配是错误的，则意味着所有 包含这种节点的线画图都是错误的，这样，只要通过一个局部检查就能排除许多 标记结构形式，这种思想产生了下面的系统方法，有时称作约束传播。 对线画图中每个节点，用一集合j ( s ) 来表示允许的节点结构，开始j ( s ) 包含所有可能结构，一条棱线只可能有一种标记形式，如果集合中有些结构与邻 近节点的结构出现不一致，则把这些结构从集j ( s ) 中排除。 令s 、t 是一条线的两个节点，如果t 点的结构集j ( t ) 和s 点的结构集j ( s ) 中，对同一条线标记是相同的，就称j ( t ) 与j ( s ) 满足局部一致性标记。如图， 西北工业大学硕士学位论文 第二章线画图的标记理论和方法 s j ( s 扣曛b 荤 扛咩 节点s ，t ，假设s 、t 的结构集为j ( s ) 、j ( t ) ，分别如图2 1 0 所示。j ( s ) 包含a 、b 、c 三种结构，j ( t ) 包含d 、e 两种结构，连接s 、t 的这条线的标记 在j ( s ) 集中有“+ ”和“一”，而在j ( t ) 集中有“+ ”和“一”，根据标记 的一致性要求，它们共有的标记是“+ ”因此j ( s ) 集中只有a 、b ，j ( t ) 只有 一种结构d 符合一致性标记，结构c 、e 被排除，a h o 等给出了这种方法的算法， 下面是此算法例子，见图2 1 1 。 假设线画图是三面顶点物体的一部分，2 1 1 ( a ) 表示初始状态，线画图图 中有节点1 ，2 ，3 ，4 ，每个顶点包含的可能结构为j ( 1 ) 、j ( 2 ) 、j ( 3 ) 、 j ( 4 ) ，e ( 1 - 2 ，2 3 ，3 - 4 ，1 _ 4 ，2 - 4 ) 是线画图的线的集合。 第一步，从集合e 中选取线1 2 ，根据标记局部致性，j ( 1 ) 中只有两个 元素和j ( 2 ) 中关于1 2 的标记符号是一致的，于是得至0 2 1 1 ( b ) 中的j ( 1 ) ， 从集合e 中删除线1 2 ： 第二步，从集合e 中选取线2 3 ，根据标记局部一致性，得到2 11 ( b ) 中 的j ( 3 ) ，从集合e 中删除线2 3 ； 第三步，从集合e 中选取线3 - 4 ，根据标记局部一致性，得至f j 2 11 ( b ) 中 的j ( 4 ) ，从集合e 中删除线3 4 ：由于j ( 3 ) 的结构集发生变化，增添线2 3 到集合e 中，接着依次选取1 4 ，2 - 4 检验标记的局部一致性，得到2 1 1 ( c ) 中的j ( 1 ) 、j ( 2 ) ，并从集合e 中删除1 4 、2 - 4 ，同时将线1 2 添加到e 中， 现在所有节点都有唯一标记，从集合e 中删除线2 3 、1 2 ，e 变成空集，结束 操作。 从上例可看到，最后得到的线画图有唯一标记，一般说来，通过标记一致性 的约束传播，结构子集中最后只剩下几种形式，这是一个很小的集合。 西北工业大学硕士学位论文 第二章线画图的标记理论和方法 ) i 州，斟爿蝴 ( n )e - - ( 1 2 。2 3 。3 4 ，1 4 2 - 4 ( i 。) = ( 3 4 1 4 ，2 - 4 ) j ( 3 ) 州，相伽 州，斟爿浏 ( ) = ( 2 3 ，1 - 2 ) j 相 j ( 4 ) 图2 一ll 约束传播 对平面立体的线图标记基本上已达成共识，理论也趋于完善，但这种方法直 接用于曲面立体，则会出现不一致的标记问题。 2 4 曲面立体消隐线画图的标记 线画图标记能将物体特征点的物理内涵赋以线画图的节点，这在计算机景物 分析中起着极其重要的作用。但曲面立体的线画图标记是一项非常困难的工作。 在此介绍一些可取的关于曲面立体线画图标记分析方法，前面已经对平面立