（模式识别与智能系统专业论文）三维草图交点识别的概率方法.pdf

中文摘要 三维草图语义描述是三维草图理解研究的基本问题之一，其中线型标注是 三维草图语义描述的基本方法，三维草图交点识别又是三维草图线型标注中必 不可少的工作，由于草图随意性和歧义性对草图识别造成的挑战，现有三维草图 交点识别工作都不能为三维草图线型标注提供很好的支持。 本论文工作以积木世界为背景，提出一种识别三维草图交点的概率方法，该 方法运用贝叶斯网表达和处理三维草图的随意性和歧义性，从草图中选取1 7 个 特征作为贝叶斯网的基元，不用分割笔划或对草图进行规整，最大限度地保留用 户绘制的原始信息，避免错误的识别，为三维草图线型标注提供强有力的支持。 关键词：概率方法，贝叶斯网，三维草图，交点识别 a b s t r a c t s e m a n t i c sr e p r e s e n t a t i o no f3 d s k e t c hi sf u n d a m e n t a lt o3 d - s k e t c hu n d e r s t a n d - i n g 3 d s k e t c hj u n c t i o nr e c o g n i t i o n i sa nr e q u i r e dp a r to fl i n el a b e l i n g ，w h i c hi s8 ne s - s e n t i a la p p r o a c ht os e m a n t i c sr e p r e s e n t a t i o no f3 d s k e t c h w h e r e a s ，t h ef r e e d o m sa n d a m b i g u i t i e si n h e r e n ti nh a n d - d r a w ns k e t c h e sp r e s e n tm a i nc h a l l e n g e t os k e t c hr e c o g n i t i o nr e s e a r c h e x i s t i n gr e s e a r c hi n3 d s k e t c hj u n c t i o nr e c o g n i t i o nd o n ts u p p o r t l i n e l a b e l i n gw e l l i nt h i sp a p e rw ep r o p o s ean e wp r o b a b i l i s t i cm e t h o dt o3 d 。s k e t c hj u n c t i o nr e c o g 。 n i t i o ni 1 1t 1 1 eb l o c kw o r l d ，w h i c he x p r e s sa n d h a n d l et h ef r e e d o m sa n da m b i g u i t i e sw i t h b a v e s i a nn e t w o r k 17f e a t u r e sh a v eb e e ns e l e c t e df r o m3 d 。s k e t c ha n d a st h eb 傩o m n o d e so ft h eb a y e s i a nn e t w o r k i tc o u l dr e s e r v er a wi n f o r m a t i o n i nt h ep i c t u r e sd r a w n b vu s e r sa sm u c ha sp o s s i b l e ，w i t h o u td i v i d i n gs 仃o k eo rs t a n d a r d i z i n g t h es k e t c h a v o i d 。 i i l ge r r o rr e c o g n i t i o na n do f f e r i n gs t r o n gs u p p o r t f o rl i n el a b e l i n gi n3 d - s k e t c h k e yw o r d s ：p r o b a b i l i s t i cm e t c h o d b a y e s i a nn e t w o r k ，3 d s k e t c h ，j u n “o n r e c o g n i f i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特另t i ：d n 以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得天津大学或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示了谢意。 学位论文作者签名：二塑! 主一签字日期：兰攀 关于学位论文使用授权的说明 本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。特授 权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并 采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家 有关部门或机构送交论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 学位论文 签字日期 导师签名： 签字日期： 第一章绪论 第一章绪论 本章概述研究背景、研究现状和论文主要工作。 1 1 研究背景 三维草图语义描述是三维草图理解研究的基本问题之一，即要解释绘制在 二维平面上草图的三维空间语义。其中线型标注就是三维草图语义描述的一种 基本方法，它的基本思路是运用线标符对线条进行标注，来表示图形的三维空间 信息。自然约束严格限定了各种物理上可实现的汇于图形交点的线标符的组合 数目，即线标符是通过图形交点传播的因此三维草图交点识别是三维草图线型 标注中必不可少的部分。 1 2 研究现状 1 9 7 1 年h u f f m a n 和c l o w e s 提出线型标注的方法，用于解释二维线条图的 空间结构，并同时建立了h u f f m a n - c l o w e s 标号集用于标注积木世界中三面顶点 实体的精确投影图【l 】，其他研究者就在h u f f m a n - c l o w e s 标号集的基础上对三维 草图线型标注进行研究【撕】。1 9 9 6 年g r i m s t e a d 和m a r t i n 首先尝试用线型标注 的方法解释几何实体组成的三维草图的空间结构【2 】，其三维草图交点识别工作 是将三维草图规整成精确的三维图，在规整后的精确图上用图匹配的方法识别 h u f f m a n - - c l o w e s 标号集中的交点类型。2 0 0 0 年s c h w e i k a r d t 和g r o s s 用线型标注 的方法为建筑领域的草图提供空间信息【3 】，其工作在识别交点前先调用规整过 程，用精准的直线代替用户手绘的线条，并将这些直线按顺序首尾严格相连。在 将原始三维草图规整成封闭的精确图后再利用图匹配的方法识别其中的交点属 于h u f f m a n - c l o w e s 标号集中的那种交点类型。2 0 0 7 年l o v e r 正式将线型标注 方法用于三维草图语义描述 4 5 】，并在此基础上，于2 0 0 8 年提出了与绘制方向 第一章绪论 无关的三维草图空间结构的描述方法【7 】。l o v e r 的工作利用了a l v a r a d o 于2 0 0 5 年提出的多领域草图识别的动态贝叶斯网模型【8 】来识别三维草图的交点。 贝叶斯网能够表达和处理草图的不确定信息，因而不用对三维草图进行规 整，不会损失用户输入的原始信息，因此在草图识别领域的研究中，不少研究 者都运用贝叶斯网识别草图语义符号。m i t 的a l v a r a d o ，她的s k e t c r e a d 系 统【9 】9 采用动态构建的贝叶斯网络来进行语义符号的识别，系统中的每个语义符 号都用一个贝叶斯网络片段来描述，其底层节点对应的是基元形状及其空间关 系，高层对应的是语义符号的类别。该系统拥有一个草图美化过程，它将笔划分 割，分割后的笔划通过最小二乘拟合匹配到预先规定的基元形状和基元间的空 间关系。该草图理解系统允许用户自由的勾画图形，不用限制用户一笔绘制一 个语义符号【lo 】，或者绘制完一个语义符号后点击按钮告诉系统【1 1 】，或者限制用 户绘制完一个语义符号后才能绘制另一个【1 2 。但是这个特点会造成分割模块在 分割基元时产生错误，而贝叶斯网络可以把这种分割歧义性表示在网络节点的 条件概率表中，同时贝叶斯网络的统计推理机制使得系统对每个输入笔划的理 解都要受到其周围的笔划的影响，使得系统可以从底层模块的错误识别中恢复 过来。天津大学的廖士中结合u m l 设计草图的识别与理解，提出了一个草图理 解的贝叶斯模型【1 3 】，该模型利用贝叶斯网络统一地表示笔划、手势、空间关系 和领域知识，并且可以在人机交互过程中增量学习，在草图的随意性和歧义性处 理上取得了较好的效果。南京大学的孙正兴也提出了一种在线手绘草图识别的 贝叶斯网络结构【1 4 1 5 】，它在a l v a r a d o 的基础【8 ，9 ，1 6 1 7 上引入了同层节点间的依 赖关系，并且它的每个基元都是7 维的组合特征向量，取得了较好的识别效果。 由于草图固有的随意性给三维草图交点识别带来很大困难，在现有的为数 不多的三维草图交点识别工作中，普遍存在的问题有以下两点： 1 多数研究者都采用了图匹配的方法识别交点，这种方法利用草图前处理过 程将手绘草图规整成精确的三维图，规整的过程消除了草图固有的随意 性，但同时损失了大量的用户输入信息，极有可能导致错误的识别结果。 2 另外也有研究者采用了贝叶斯网来表达和处理草图的不确定信息，获得了 较好的效果，但在利用贝叶斯网进行三维草图交点草图识别的工作中，基 元的取值都依赖于对笔划进行分割，这与草图自然绘制的特点相违背，不 能完全反映用户的绘制意图。 2 第一章绪论 目前的三维草图交点识别工作都不能为三维草图线型标注提供很好的支持。 1 3 本文工作 本论文工作以积木世界为背景，对有遮挡的三维草图线型标注问题进行研 究，提出一种识别三维草图交点的概率方法。该方法运用贝叶斯网表达和处理三 维草图的不确定信息，使用贝叶斯网概率推理识别出交点类型。其中贝叶斯网 的底层节点对应的是从三维草图中提取的特征，这些特征能够反映笔划内部的 局部信息和笔划间的整体信息。该方法不用分割笔划或者对草图进行规整，最 大限度地保留用户绘制的原始信息，避免错误的识别，为三维草图线型标注提供 强有力的支持。 3 第二章线型标注与贝叶斯网 础。 第二章线型标注与贝叶斯网 本章主要介绍本论文工作所涉及的三维草图标注和贝叶斯网络的理论基 2 1线型标注 线型标注方法由h u f f m a n 和c l o w e s 于1 9 7 1 年提出，并同时建立了h u f f m a n - c l o w e s 标号集用于标注积木世界三面顶点实体的精确投影图。本节在此工作基 础上介绍线型标注方法。 2 1 1 符号标记 符号标记是对基本素描表达的各组成部件用符号来进行标记。 2 1 1 1 语义标号 所有的线分为边界线和内线。当物体的一个面遮住另一面时，就产生边界 线。图形中由一条边界限分离的两个面不会沿界线相邻接。内线是凹边缘或凸 边缘。图形中由一条内线分离的两个面必然沿该线相邻接。观察边界线的哪一 旁对应于物体形成边界线的某一个面，可确定边界语义标号的指向。假设你沿 线而行，含边界线的物体居右，你行走的方向，便是边界语义标号的方向。为便 于识别，在图形中采用3 种语义标号类型，如下表所示： 表2 1 语义标号定义 线 凸边缘 凹边缘 边界线 语义标号类型 + - 4 第二章线型标注与贝叶斯网 2 1 1 2 交点标符 一个积木世界是交叉线所组成的角度的组合，因此对积木世界的理解，首先 就是对由交叉线所组成的角度的符号标记【1 8 】。 根据形成交点线的条数和各线间的角度，可将所有物理上可实现的交点加 以分类。再根据下面一些简单的假设，排除研究范围之外的交点，保留下如图 2 - l 所示的l 形、箭形、叉形和t 形四种交点类型，其物理意义如表2 2 所示。 假设2 1 ：线：不允许有阴影和缝隙。 假设2 2 ：三面顶点：有物体的3 个面相汇而成的顶点。 假设2 3 ：一般位置：选择视点要求该视点稍有变化不会影响对所有交点的分 类。 ( b )箭( w ) 形( c )叉( y ) 形( d ) t 形 图2 1 四种交点类型 表2 2 各交点类型的物理意义 1 l 是两条边线的l 形相交，从这一方向看过去，只能看到被l 包围着的一 个平面。 2 m 是三边线的箭形相交，是三个面相交的侧视投影，可见的只是两个面。 3 t 是两个块体的两个面的两条边缘投影相交形成的t 形交叉，只有在有遮 挡的情况下会形成。 4 y 是三条边线的叉形相交，是三个面的交汇。 5 形 l 一 第二章线型标注与贝叶斯网 汇于交点的语义标号的组合称为交点标符。自然约束严格限定了各种物理 上可实现的交点标符的数目e 1 】。表2 3 给出了三面交点标符的1 8 种类型。 表2 3 三面交点标符的1 8 种类型 2 1 2 约束传播 有了如图2 2 所示的交点标符集合，下一步就可以分析线图找出正确的交 点标符类型了。以对单一的立方体进行标注为例，想象立方体是悬空的，则可先 标上边界线的语义标号，即沿顺时针方向，在边界线上标以一。下一步，为羽支 是边界的箭形点的箭杆标上语义标符，就完全对所有的线加以一致的标注了。 可是对复杂的线图，就不是这么容易能完全标注了，标号约束传播为计算机 分析线图提供了一种好的方式。华尔兹过程就是一种通过交点传播标符约束的 方法。其过程可简单描述为：设想为每个交点设定一对可能的标符类型。首次访 问一交点时，便为该交点设定一对可能的标符类型，而每当其邻交点的一堆可能 6 第二章线型标注与贝叶斯网 标符类型有所变化时，便加以重新审视并作为相应的修改。例如一旦建立了一 个可能的标符类型堆，且已被一些邻堆所缩小，这时可检查那些邻堆包含的标符 类型是否有与新建堆中的每个标符类型不相容的情况。进程一旦启动，只要被 访问的交点的堆不断在缩小，约束传播就会继续进行下去，直到每个交点的堆都 不在缩小结束传播。 2 2 贝叶斯网 贝叶斯网络( b a y e s i a nn e t w o r k s ) 是人工智能中不确定知识表示和 推理的重要方法，是概率论和图论相结合的产物，最初是由r h o w a r d 和 l m a t h e s o n 于1 9 8 1 年提出来的。贝叶斯网络是一个有向无环图( d i r e c t e da c y c l i c g r a p h ，d a g ) ，其中节点代表随即变量，节点间的边代表变量之间的直接依赖关 系。每个节点都附有一个概率分布，根节点x 所附的是它的边缘分布p r ) ，而 非根节点x 所附的是条件概率分布p r ( x l7 r ( x ) ) ，其中7 r ) 表示x 的父节点【1 9 】。 2 2 1 概述 在实际应用中，人们往往利用因果关系来确定贝叶斯网的结构，这样建立起 来的贝叶斯网中，变量间的边表示的是因果关系，而非简单的概率依赖关系。这 样的贝叶斯网成为贝氏因果网( b a y e s i a nc a u s a l n e t w o r k s ) ，简称因果网【2 0 】。采 用图形的方法描述数据间的相互关系，不但语义清晰，而且可理解性强，有助于 利用数据间的因果关系进行预测分析。这里的概率指的是贝叶斯概率。某一事 件的贝叶斯概率是观测者对该事件发生的相信程度，是利用先验知识对未知事 件出现频率所作的预测，不同于普通意义上的事件的客观概率，客观概率是在反 复多次实验中事件发生的频率的近似值。 一组变量u = ( v l ，圪， 组成的贝叶斯网络有定性和定量两个方面的内 容，可表示成一个二元组s = ( 风，b p ) ： 1 ) 岛表示以u 中变量为网络节点建成的贝叶斯网的网路结构，变量之 间的因果关系通过网络节点间的有向弧表达。贝叶斯网络的一个重 要特征就是具有条件独立性【2 1 】。考虑3 个随机变量x ，y 和z ，设 7 第二章线型标注与贝叶斯网 p r ( z = z ) 0 ，讫化。我们说x 和y 在给定z 时相互条件独立，记为 x 上v l z ，即下式成立： p r ，r l z ) = p r i z ) p r ( y i z ) u 中每一节点在给定其父节点后条件独立于它的前辈节点，即有如下公 式： ， p r ( v i ，圪，) = n p r ( v i z r ( v ) ) f = l 其中7 r ( 巧) k 一1 ，约) 是节点巧的父节点集合。 前面介绍过贝叶斯网是概率论和图论相结合的产物，因此我们也可以从 图论的角度谈论节点之间的连通与分隔。贝叶斯网络条件独立性的一个 很重要的判据是著名的分隔定理( d s e p a r a t i o n ) 。其内容是如果x 和y 之 间的所有通路都被z 阻塞，那么我们就说z 有向分隔( d i r e c t e ds e p a r a t e ) x 和y ，简称d 分隔( d s e p a r a t i o n ) x 和y 。要理解d 分隔的概念，我 们先来了解一下两变量x 和y 通过第3 个变量z 间接相连的三种情况。 ( 1 ) 顺连( s e r i a lc o n n e c t i o n ) 结构如图2 1 ( a ) 所示。其中z 若未 知，则对x 的了解会影响关于z 的信度，进而影响关于y 的信 度；反之亦然。此时x 和y 相互关联。另一方面，若z 的取值己 知，则对x 的了解就不会影响z 的信度，从而不会影响关于y 的信度。此时x 和y 之间的信息通道被z 阻塞，x 和y 相互条 件独立。 ( 2 ) 分连( d i v e r g i n gc o n n e c t i o n ) 结构如图2 1 ( b ) 所示。它与顺连 的情况相似：当未知z 时，x 和y 相互关联；当z 已知时，x 和y 相互条件独立。 ( 3 ) 汇连( c o n v e r g i n gc o n n e c t i o n ) 结构如图2 1 ( c ) 所示。在结构 上，它与分连恰恰相反。分连代表一因多果，而汇连代表多因一 果。在信息通道性质方面，它也与分连相反，即：在未知z 时， x 和y 相互独立；而在已知z 时，x 和y 却相互关联。 8 第二章线型标注与贝叶斯网 o ( a )顺连 ( b ) 分连 ( c )汇连 图2 2 两个变量x 和y 通过第3 个变量z 间接相连的三种情况 这时我们再来理解d 分隔定义中的通路被阻塞：设z 为一个节点集 合，x 和y 是不在z 中的两个节点，考虑x 和y 之间的一条通路。如果 满足下面条件之一，则称a 被z 所阻塞： ( 1 ) a 上有一个在z 中的顺链接点； ( 2 ) 仅上有一个在z 中的分连节点； ( 3 ) a 上有一个汇连节点w ，它和它的后代结点均不在z 中。 这因为贝叶斯网络具备这个特征，所以能有效的表示指数级大小的 联合概率分布，假设有n 个二值随机变量，要表示其全概率分布原本需 要( 2 打) 存储空间，而采用贝叶斯网络以后，存储空间下降为( n 2 七) ， 其中k 为网络中节点的最大扇入系数。以图2 2 中的贝叶斯网为例，运 用链式规则，可以把联合概率分布p r 口，b ，c ，d ) 表示为： p r ( a ，b ，c ，d ) = p r ) p r ( b m ) p r ( c a ，b ) p r ( d i a ，b ，c ) 但根据贝叶斯网的条件独立性，上式的联合概率分布可化简为： p r ( a ，b ，c ，d ) = p r ( a ) p r ( b i a ) p r ( c i b ) p r ( d i c ) 根据以上性质再考虑计算p r ( d ) ，有 p r ( d ) = p r ( a ，b ，c ，d ) a b c = p r ( a ) p r ( b i 彳) p r ( c i 曰) p r ( d i c ) ( 2 1 ) 一 、，、 、 ，、 a ，b ，c 假设所有变量均为二值，而且乘法按顺序进行。式( 2 1 ) 的运算复杂度 如下：p r 0 ) 与p r ( b i a ) 相乘需要做4 次数字乘法，其结果与p r ( c i b ) 相乘 9 第二章线型标注与贝叶斯网 需要做8 次数字乘法，它的结果再与p r ( d i c ) 相乘需要做1 6 次数字乘 法。所以，总共做2 8 次数字乘法，另外需要做1 4 次数字加法。接下来我 们要对联合分布进行分解，使得运算局部化来降低复杂度。我们可以注 意到在式( 2 - 1 ) 右边的4 个因子中只有p r ( a ) 和p r ( b i a ) 与变量a 相关， 变量b 、c 类似，因此，有 p r ( d ) = p r ( d i c ) p r ( c i b ) p r ( a ) p r ( b a ) c曰a 这样就只需做1 2 次数字乘法和6 次数字加法，这比式( 2 - 1 ) 的复杂度 要低。 图2 3 一个链状贝叶斯网 2 ) 风网络的参数b 口，指明变量u 的局部概率分布集合，即给定其父 母节点状态，该节点取不同值的概率，值的大小反映变量之间关联的强 度和致信度，通常称为条件概率表( c o n d i t i o n a lp r o b a b i l i t yt a b l e ，c p t ) ， 对于根节点来说，其对应的概率称为先验概率，先验概率一般分为两类， 一是客观先验概率，指利用过去的历史资料计算得到的概率；二是主观 先验概率，是指在无历史资料或历史资料不全的时候，只能凭借人们的 主观经验来判断其概率。 贝叶斯网具有强大的知识表示能力，其显著的优点体现在以下几方面： ( 1 ) 能够方便地处理不完全数据对于一般的机器学习方法，必须知道所有 可能的数据输入，如果缺少其中的某一输入就会使建立的模型产生偏 差，贝叶斯方法则可解决这个问题。因为贝叶斯网络反映的是整个数据 域中数据间的概率关系，因此贝叶斯网络可以处理不完整和带有噪声的 数据集。 ( 2 ) 能够学习变量间的因果关系。因果关系的挖掘是在数据分析中经常遇到 的问题，因果关系有利于对领域知识的理解，而且当存在较多干扰时， 便于做出精确的预测。例如市场销售人员想知道增加广告投入是否能提 1 0 第二章线型标注与贝叶斯网 高产品的销量，换言之，在某种程度上，广告投入是否是提高销量的原 因，贝叶斯网络能够容易的回答这个问题而其它模型比较难以处理。 ( 3 ) 贝叶斯网络与贝叶斯统计相结合能够充分利用领域知识和样本数据的 信息。贝叶斯网络用弧来表示变量间的依赖关系，用概率分布表来表示 依赖关系的强弱，将先验知识与样本信息有机结合起来。先验信息或领 域知识在数据建模方面具有重要的作用，尤其在样本数据稀疏或数据较 难获得的时候。由于贝叶斯网络可以综合这两方面的信息，既可避免只 使用先验知识可能带来的主观偏见以及缺乏样本信息时的盲目搜索与 计算，也可比避免只使用样本数据信息带来的噪声的影响。 贝叶斯网最初是作为一种处理专家系统中不确定性的工具而被提出的。该 方法以其独特的不确定性知识表达形式、丰富的概率表达能力、综合先验知识 的增量学习特性等日益引起研究者的重视，近年来，它越来越多被用于数据分 析，以揭示和刻画数据中所蕴含的规律和进行概率推理【2 0 】。 2 2 2 概率推理 推理( i n f e r e n c e ) 是通过计算回答查询( q u e r y ) 的过程。贝叶斯网中的推 理问题有三大类：后验概率问题、最大后验假设问题以及最大可能解释问题。 2 2 2 1 后验概率问题 后验概率问题指的是已知贝叶斯网中某些变量的取值，计算另外一些变量 的后验概率分布的问题。在此类问题中，已知变量通常称为证据变量( e v i d e n c e v a r i a b l e s ) ，记为e ，它们的取值记为e ；需要计算其后验概率分布的变量成为查 询变量( q u e r yv a r i a b l e s ) ，记为q ；需要计算的后验分布为p r ( q i e = p ) 。 以经典的a l a r m 问题为例。a l a r m 问题的背景是，p e a r l 教授家住在洛杉矶， 那里地震和盗窃时有发生。教授的家里装有警铃，地震和盗窃都可能触发警铃。 昕到警铃后，两个邻居m a r y 和j o h n 可能会打电话给他。一天，p e a r l 教授接到 m a r y 的电话，说听到他家警铃响，p e a r l 教授想知道他家遭盗窃的概率是多大? 该问题的贝叶斯网络结构如图2 3 所示，5 个算计变量，节点b 表盗窃，节点e 表地震，节点a 表警铃响，节点m 表接到m a r y 的电话，节点j 表接到j o h n 的 电话，所有变量的取值均是“y 或“1 1 。 第二章线型标注与贝叶斯网 图2 - 4a l a r m 贝叶斯网络结构 人们常说的概率推理指的就是后验概率问题。根据证据变量和查询变量所 扮演的因果角色的不同，概率推理有以下4 种不同类型。 1 从结果到原因的诊断推理( d i a g n o s t i ci n f e r e n c e ) 。例如，已知m a r y 打电话， 计算发生盗窃的概率p r ( b = y l m = y ) 。 2 从原因到结果的预测推理( p r e d i c t i v e i n f e r e n c e ) 。例如，已知发生了入室盗 窃，计算m a r y 打电话的概率p r ( m = y l b = y ) 。 3 在同一结果的不同原因之间的原因关联推理( i n t e r c a u s a li n f e r e n c e ) 。例如， 已知警铃响后，对发生盗窃的信度为p r ( b = y l a = y ) 。如果接着又获知发 生了地震，则对盗窃的信度将变为p r ( b = y l a = y , e = y ) 。由于警铃响了已 有了一个可能的解释，即地震，所以此长彼消，对发生盗窃的信度将会减 小，即p r ( b = y l a = 儿e = y ) e c i 0 笔划s 1 在点p 1 速率未变化 0ss p e e d ( p _ 1 ) se s 一1 恳 1 笔划s 1 在点p l 速率变化s p e e d ( p j1 e s 一1 0 点p 1 的类型为起点或终点p 1 t y p e = s t a r t 或p 1 t y p e = e n d 尼 1 点p l 的类拐点p 1 t y p e = c u r v e 0 点p l ，p 2 重合0 d i s t a n c e ( p l ，p 2 ) 1 3 * d 1 2 尻 l 点p l ，p 2 不重合 d i s t a n c e ( p l ，p 2 ) 1 3 d 1 2 0 笔划s 1 在点p 2 曲率未变化0 墨n o r m _ k 2 ) e c 一1 b 1 笔划s 1 在点p 2 曲率变化n o r m _ k ( p 21 e c 一1 o 笔划s 1 在点p 2 速率未变化0 s p e e d ( p 2 ) e s 一1 民 1 笔划& 在点p 2 速率变化s p e e d ( p 21 e s 一1 0 点p 2 的类型为起点或终点p 2 t y p e = s t a r t 或p 2 t y p e = e n d r l 点p 2 的类拐点p 2 t y p e = c u i w e o 点p 1 ，p 3 重合0 d i s t a n c e ( p l ，p 3 ) 1 3 * d 1 2 最 1 点p l ，p 3 不重合d i s t a n c e ( p l ，p 3 ) 1 3 * d 1 2 o s _ n u m = 1 ，2 局 基元中涉及的笔画数 1 s _ n u m = 3 o 笔划蜀在点p 3 曲率未变化0 n o r m _ k ( p 3 ) e c 一1 e 1 0 1 笔划& 在点p 3 曲率变化n o r m _ k ( p 3 ) e c 一1 0 笔划s l 在点p 3 速率未变化0 s p e e d ( p 3 ) e s 一1 局1 l 笔划s l 在点p 3 速率变化s p e e d ( p 31 e s 一1 0 点p 3 的类型为起点或终点p 3 t y p e = s t a r t 或p 3 t y p e = e n d 局2 1 点p 3 的类拐点p 3 t y p e = c u r v e 0 点p 2 ，p 3 重合0 冬d i s t a a c e ( p 2 ，p 3 ) 1 3 * d 1 2 蜀3 1 点p 2 ，p 3 不重合 d i s t a n c e ( p 2 ，p 3 ) 1 3 * d 1 2 0 射线f g 与线段。见相交m t e r s e c t ( 1 g ，易l 见) = t r u e e 4 1 射线，g 与线段，见不相交m t e r s e c t ( 1 g ，t p l 见) = f a l s e 0 射线i g 与线段易。刃相交 m t e r s e c t ( 1 g ，易l p 3 ) = t r u e 月5 l 射线i g 与线段。p ，不相交m t e r s e c t ( 1 g ，仍) = f a l s e 0 射线，g 与线段k 以相交m t e r s e c t ( 1 g ，t p 2 仍) = t r u e 局6 l 射线i g 与线段k 用不相交m t e r s e c t ( 1 g ，k p 3 ) = f a l s e 第三章三维草图交点识别 续表3 2贝叶斯网络基元特征具体描述 基元 基元描述 名称取值取值条件 0 点p l 在笔划& 上 1 i n t e r s e c t i o n _ h u m ( & ，p 1 ) 2 局7 l 点p l 不在笔划& 上i n t e r s e c t i o n m u m ( & ，p 1 ) 2 表3 3 表3 - 2 符号注解 标记 注解 s _ n u m基元中涉及的笔画数 s i第i 号笔划 e c 笔划f 各点过点曲率的均值 e s j 笔划f 各点过点速率的均值 d u l e n ( s ( p i ) ) l e n ( s ( p ，) ) 中的较小值 l p 以点p 为端点，水平向左延伸的射线 l p i p i 以点p i 和点p j 为端点的线段 t i j i c以点p i ，p j ，p k 为顶点的三角形 s o f )点p i 所在的笔划 点p i 和点所之间的距离，( d i s t a n c e ( p i ，p y ) = 一 d i s t a n c e p f ，乃) 当p 不存在时，d i s t a n c e ( p i ，力) = o o ) 肌是s j ( j i ) 上的一个点，以p k 为圆心， i n t e r s e c t i o n m u m ( s i ，p 女)1 3 * l e n ( s j ) 为半径作圆，圆与墨的交点数 ( 当s 不存在时，i n t e r s e c t i o n m u m ( s ，p k ) = o ) n o r m _ k ( p i )p f 点的正则曲率 s p e e d ( p )p f 点的过点速率 l e n ( s i ) 笔划s 外接矩形长、宽中长度较小者的长度值 点p i ，乃，肌的重心p 。 g c ( p i ，p j ，p k ) p c 工= 1 3 卑b i ) c + p j 工+ p k 书 p c y = 1 3 聿b i y + p j y + p k 们 易f 乃的中点p c ，p c j = 1 2 丰0 f j + 乃z ) g c p f ，乃) p c = 1 2 聿i p i y + p j n 射线拓与线段竹是否相交，是返回t r u e ， i n t e r s e c t ( , ，l p i p 0 否返回f a l s e ，( 当f 力不存在时，返回f a l s e ) 2 1 第三章三维草图交点识别 这些特征有些反映笔划内部信息的局部特征，如1 3 ；有些是反映可能相 交的笔划间的整体特征，如4 7 。局部特征在笔划采集时即可计算得到，整体特 征在检测到可能相交的笔划后计算得到。 3 3 2 贝叶斯网概率推理 理。 贝叶斯网概率推理部分包括为四种交点类型搭建贝叶斯网络和进行概率推 3 3 2 1 网络结构 四种交点类型的贝叶斯网络结构如图3 3 图3 - 6 所示，四个根节点是四个 交点类型，叶节点是1 7 个特征中的若干特征，第二、三层节点是叶节点向根节点 传递依赖关系所必须的中间节点。从乃一珏分别描述如下： 1 乃反映的是对关键点的正则化曲率、过点速率和点的类型信息进行概率推 理后得到的新的点的类型； 乃= 0 表示该关键点是始末点；乃= 1 表示该关键点是没有形成交点的可 能拐点；乃= 2 0 表示该关键点是形成交点的拐点。乃、乃与乃类似。 2 瓦反映的是一对关键点引出的线条相对于这些关键点的重心的分布情况， 它由局4 、f 1 5 、五6 的取值推理得来。 7 4 = 0 表示这些关键点所引出的线条相对于重心分布较均匀，类似于叉形 交点的分布；7 4 = 1 表示这些关键点所引出的线条相对于重心分布于一侧， 类似于箭形交点的分布。 3 乃反映的是一个笔划是否和与之可能相交的笔划呈t 相交，它由对特征 局7 的取值信息进行推理得来。 t 5 = 0 表示该是呈t 形相交；兀= l 表示该不是呈t 形相交。 4 t 6 ( 乃、t 8 ) 反映的是两个笔画在某关键点处呈哪种相交，它由对 乃、恐、乃、局、风、局、局3 的取值信息推理得来。 r 6 ( 7 7 、r 8 ) = 0 表示两笔划在某关键点处呈l 形相交；r 6 ( 乃、t s ) = l 表示 两笔划在某关键点处呈由一个笔划与单笔划拐弯l 相交；7 6 ( 乃、t 8 ) = 2 表示两笔划在某关键点处不相交。 蔓三至三丝茔里至盛望型 圈3 - 3 l 形交点的贝叶斯阿络结构 图3 - 4 箭形交点的贝叶斯网络结构 墨三要三堕蔓圈童盛堡型 圈3 - 5 叉形交点的贝叶斯网络结构 圈3 巧t 形交点的贝叶斯网络结构 3 322 霸络参数 圈3 - 3 一圈3 - 6 所示的贝叶斯网络结构相应的阿络参数，即网络中各节点的 先验概率我们通过观察、实验，以节点间的相互条件依赖关系为基础手工给 出( 见附录a ) 。 第三章三维草图交点识别 3 3 2 3 概率推理 贝叶斯网络推理实际上就是概率计算，本论文的识别问题可以转化为后验 概率问题，即已知网络中某些变量的取值，计算另一些变量的后验概率分布。 以图3 2 所示的l 形交点的贝叶斯网络为例，假设变量为虼，它的证据e 为 乃、死，也就是要计算已知死和死的取值时圪的后验分布，即p r ( 圪i 乃，死，局) 。 而乃的后验分布为p r ( t i i e l ，f 2 ，f 3 ) ，死的后验分布为p r ( 死1 乃，局，死) ，恐的后 验分布为p r ( t 2 1 f 5 ，f 6 ，f 7 ) ，其中局而在特征提取过程得到其取值，那么从底层 基元逐层向上推理就能得到圪的后验分布了，计算公式如下： p r ( 虼l 羁，局，f 9 ) = a p r ( 圪，局，局) = a 乃死死p r ( 圪) p r ( t 6 i 圪) p r ( t l i 圪，死) p r ( t z l t 6 ) p r ( f i i t i ) p r ( f a i 乃) p r ( f 3j r l ) p r ( f 4 i 死) p r ( f s i t 2 ) p r ( f 6 l 乃) p r ( f 7 i 乃) p r ( f 9 l 死)( 3 - 3 ) 这时我们再分析图3 2 一图3 5 所示贝叶斯网络结构会发现一个与直觉不 一致的问题：表示变量间依赖关系的边的箭头不是从证据节点指向假设变量节 点，而相反，是从上层的假设变量节点指向下一层的假设变量节点或证据节点。 这貌似与因果关系推理相反，但是， 1 上层假设变量是否为真直接影响下层假设变量是否为真。比如，已知l 形 交点的最高层假设虼如果为真，那么也就可以推断下层两个的假设变量 正和死全为真。 2 这种网络结构表达了在给定上层假设变量取值的条件下下层假设变量或证 据变量之间的条件独立关系，这样就能减少构建相应网络结构所需的网络 参数，即减小了节点条件概率表的大小。 草图的随意性使得一个笔划或一组可能相交的笔划会产生1 个或多个交点。 但因为交点只会出现在关键点出现的地方，因此笔划上关键点的数目与笔划产 生交点的个数相关。定义4 指出一个交点可能包含l 一3 个关键点，所以一个笔 划或一组可能相交的笔划里，任何一个包含l 一3 个关键点的组合都有可能形成 交点，所以由每个关键点的组合获得一组基元取值，从而决定进行概率推理的次 数。表3 - 4 所示的推理过程说明了本论文工作提出的概率方法在识别三维草图 2 5 第三章三维草图交点识别 交点时如何从一组可能相交的笔划找出推理所需的基元取值，而不会遗漏掉任 何可能的交点。 表3 _ 4 推理过程 推理过程 输出：列表m _ r e s u l t _ l i s t 列表的一个成员为 p r ( d = 圪i e ) ，p r v = v w i e ) ，p r ( j = h i e ) ，p r ( j = 玢i ) ) l ：l i s t m u m = 0 ： 2 ：i f ( 刀= = 2 ) 3 ：f = 0 ： 4 ：m = o ： 5 ： j = f + l ； 6 ：，= m + l ： 7 ： w h i l e ( s 1 印f t y p e 哳a n ds j 幼f t y p e 巧a n ds 1 锄t y p e 呖a n d s 、k p i t y p e v y 8 ： m _ r e s u l t d i s t 1 i s t _ n u m + + 1 = b a y e s i a n _ i n f e r e n c e ( p i c k u p _ f e a t u r e ( s 1 印f ，s 1 k p j ) ) 9 ： s e t _ n e w t y p e ( s i k p i s 1 k p ，) 1 0 ： w h i l e ( & 幼。a n d & k p 。t y p e 晰a n d & 印。t y p e 蹄) 1 1 ： m _ r e s u l t l i s t 1 i s t _ h u m + + = b a y e s i a n _ i n f e r e n c e ( p i c k u p _ f e a t u r e ( s 1 k p i ，& 印一) ； 1 2 ： s e t _ n e w r y p e ( s i k p i s 2 印m ) ； 1 3 ： m _ r e s u l t l i s t 1 i s t _ h u m + + i = b a y e s i a n _ i n f e r e n c e ( p i c k u p _ f e a t u r e ( $ 1 k p i ，s i 印，& 印朋) ) ； 1 4 ： s e t n e w t y p e ( s 1 k p i & k p ，& 印m ) ； 1 5 ： w h i l e 【& 印，a n d & 印- ，a t ) ，p e 哳a n d & 却，t y p e 巧) 1 6 ： m _ r e s u l t d i s t 1 i s t _ n u m + + 】= b a y e s i a n a n f e r e n c e ( p i c k u p _ f e a t u r e ( s 1 k p j ，& k p 肼，k p r ) ) ； 1 7 s e t m e w t y p e ( s 1 印，& k p 。，& 印，) ； 1 8 ：，+ + ： 1 9 ： e n d w h i l e 2 0 ：m + + ； 2 l ：e n d w h i l e 2 2 ：f + + ： 2 3 ：e n d w h i l e 2 4 ： e l s e ； 2 5 ：f = o ： 2 6 ： j = 0 ： 2 7 ：m = o ： 2 8 ： w h i l e ( 蜀印fa n d 蜀印f t y p e 哳a n d 两印f t y p e 巧) 2 9 ： w h i l e ( s 2 k p ia n ds 2 k p f t y p e y ma n ds 2 k p j t y p e h 1 3 0 ： w h i l e ( & 印。a n d & 印。t y p e 哳a n d & 印搠t y p e 巧) 31 ： m _ r e s u l t l i