统计与结构结合的工程图纸符号识别方法.pdf

第12卷第5期 2000年5月 计算机辅助设计与图形学学报 JOURNAL OF COM PU TER A I DED DESIGN AND COM PU TER GRA PH ICS Vol 12 No 5 M ay 2000 统计与结构结合的工程图纸符号识别方法 董海卫 江 早 王永军 东北大学软件中心 沈阳 110006 摘要 提出一种统计识别与结构识别相结合的符号识别方法 以识别工程图纸中的各种符号 并达到了很好的 识别效果 关键词 工程图纸 符号识别 符号基元 符号文法 句子匹配 中图法分类号 TP391 Statistic and Structure Integrated Approach of Symbol Recogn ition for Engineering Drawings DON G Hai2W ei J I AN G Zao WAN G Yong2Jun S of tw are Center N ortheastern U niversity S henyang 110006 Abstract A statistic and structure integrated approach for recognizing all kinds of symbols on engineering draw ing is presented It achieves a good recognition result Key words symbol recognition symbol pri m itive symbol syntax sentence matching 原稿收到日期 1999201211 修改稿收到日期 1999204207 董海卫 男 1974年生 硕士 主要研究方向为图像处理 符号提取 符号识别 江 早 男 1965年生 博士后 副教授 主要研究方向为图像处理 文档图像分析及CAD CAM 王永军 男 1946年生 教授 主要研究方向为 图像处理技术 图像图形学 图像传输技术 1 引 言 工程图纸中存在着大量印刷体或手写体符号 这些符号往往呈现空间旋转等多种复杂的空间特 征 如何正确识别这些呈现各种空间特征的符号是 工程图纸识别的重要步骤 本文介绍了一种统计识 别和结构识别相结合的符号识别方法 以解决识别 的正确率问题 统计识别方法和结构识别方法分别 应用到符号识别的不同层次上 其中统计识别用于 基元提取 结构识别用于整体的符号识别 具体步骤 如下 1 符号处理利用归一化和细化算法对符号 进行处理 2 基元提取利用竞争学习神经元网络识别 符号节点 利用Freeman编码来识别节点之间的连 线 分别生成节点基元集合和连线基元集合 由它们 组成了符号基元集合 3 符号文法利用得到的符号基元集合建立 符号的有向图的表示法 然后利用图的遍历算法来 遍历所有节点 生成符号句子 再按不同的模糊度生 成三级模糊度符号句子 4 句子匹配对符号的三级模糊度句子进行 匹配 得到识别结果 2 符号处理 符号处理的主要目的是得到符号的统一36 36 点阵的骨架表示 这样可以减少识别算法的计算量 和噪声的影响 符号处理的主要方法的是将符号归 一化成为一个36 36的子图 然后对子图进行细 化 最后对细化结果进行修正 归一化是用实数倍缩放算法SZCNV 1 实现的 归一化完成后 利用ROSE八邻域细化算法 2 细化 1995 2005 Tsinghua Tongfang Optical Disc Co Ltd All rights reserved 36 36子图 得到单线宽符号子图 由于细化算法的 局限性 我们必须对细化结果进行修正 修正包括短 线去除 断线修补等 图1中的粗糙度符号的处理过 程如图2 图4所示 其中图1是原始图像数据 图2是归一化后结果 图3是细化后结果 图4是修 正后结果 3 基元提取 基元提取分为节点基元提取和连线基元提取 首先提取并识别节点 然后识别节点之间的连线 节 点是端点 拐点 三叉点和四叉点的统称 节点的识 别方法是扫描符号处理后得到的36 36子图上的 每一个点 每扫描到一个黑象素点 就取该点周围 5 5区域内的25个点送入神经元网络来判断该点 的类型 识别出节点以后再识别节点周围的连线 3 1 节点基元提取 节点识别采用25输入50输出两层竞争学习网 络实现 3 其中25输入分别对应黑象素点及周围 5 5区域内的象素的值 黑象素输入值为1 白象素 输入值为0 节点类型划分为8种端点 24种拐点 16种三叉点 1种四叉点 再加上1种内点 共50种 类型 分别对应网络的50个输出单元 3 1 1 网络实现的基本原理 每一个输出单元与输入层各单元都有一个连接 权值 权值取值在0与1之间 且每一输出单元的权 值总和为1 对于每一个输入值只有一个输出单元 的输出为1 其它输出单元的输出为0 输出单元的 输出值由竞争原则决定 即输出单元中有最高输入 总和的单元被确定为输出值为1 其它输出单元的 输出值为0 让每一个输出单元的权值总和为1 即 25 i 1W ji 1 每一个输出单元的输入总和为Sj 25 i 1W jiXi 输出单元的输入值最高时 它的输出值为1 其 它各单元的输出值为0 即 yj 1 若Sj MAX Sk k j k 1 2 3 25 0 其它条件下 3 1 2 网络的学习策略 输出值为1的输出单元权值正向修正 输出值 为0的输出单元权值反向修正 对输出值为1的输 出单元来说 当它的某个输入值为1时 相应的权值 增加 当它的某个输入值为0时 相应权值减少 对 输出值为0的输出单元来说 当它的某个输入值为 1时 相应的权值减少 当它的某个输入值为0时 相应权值增加 输出值为1的输出单元的权值修正方法为 Wji t 1 Wji t Wji 输出值为0的输出单元的权值修正方法为 Wji t 1 Wji t Wji 权值的改变量 Wji更新规则为 Wji d t xi m Wji d Sj MAX Sk k 1 2 3 25 t 0 1 t T m 25 i 0 xi t 权值学习因子是逐渐变小的 0为初始值 取值范围0 01 0 03之间 T为预期的学习次数 t 为当前已训练的次数 3 1 3 节点识别结果 神经元网络的识别结果用两位A SC II码表示 下面列出输入图像原始数据与得到的结果的对应关 系 其中灰象素点表示5 5区域的中点 端点对应关系见图5 673 计算机辅助设计与图形学学报2000年 1995 2005 Tsinghua Tongfang Optical Disc Co Ltd All rights reserved 锐角拐点对应关系 小于90 见图6 直角节点对应关系 90 左右 见图7 钝角节点对应关系 大于90 小于等于135 见图8 三叉节点对应关系见图9 所有四叉节点都用 7A 表示 3 2 连线基元提取 连线基元的识别采用8方向的Freeman编码 来实现 我们可以根据细化后两个节点之间的连线 的Freeman编码得到连线的方向变化 根据连线的 方向变化和连线两端节点的位置关系确定对应的连 线基元 8方向Freeman编码如图10所示 设连线共由k个象素点组成 d1和dk表示开始 节点和终止节点的Freeman编码 di表示连线上第 i个象素的Freeman编码 则连线的方向变化C为 C k 1 i 1 di 1 di dk d1 根据连线的起始点 终止点位置关系和连线的 方向改变 连线基元也可以用两位A SC II表示 得 到对应关系如表1所示 其中横坐标表示方向 纵坐 标表示方向改变 表1 连线起始点和终止点位置关系 改变 C 方向 0 45 90 135 180 225 270 315 2 A B C D E F G H 1 A B C D E F G H 0 A B C D E F G H 1 A B C D E F G H 2 A B C D E F G 表示锐角 0 90 表示钝角 90 135 33H22223 33H3 其中3 表示任意长度字符串 表示任意一个单个字 符 表示删除一个字符 4 3 三级模糊度子句 经过滤波算子滤波后即得到第1级模糊度的长 句子L ong sentence 上例中的句子经滤波后得到的 长句子L ong sentence没有发生变化 即 L ong sentence 3H A6G B1G F3C 因为第1级模糊度的长句子的精度过高 所以需 要精度低的第2级模糊度短句子S hort sentence 具 体方法为去除节点基元的方向编码 去除连线基元的 方向改变编码 即 3IJ3 3I2 3 3I3 3KJ3 3 2J3 3J3 其中I 1 2 3 4 5 6 7 8 J A B C D E F G H K 3 表示任意长度字符串 表示删除一个字符 上例中的长句子L ong sentence经处理后得到 的短句子S hort sentence为 S hort sentence 3A6B1F3 进一步可以得到第3级模糊度句子 即每个节 点的子句S ub sentence 其中每个节点的子句由该 节点基元和与该节点相连的出边基元生成 出边按 角度由小到大排序 再将节点子句按节点纵横坐标 和由小到大进行排序 这样就得到节点子句集合 上 例中的节点子句集合为 S ub sentence1 3H A H S ub sentence2 1G F S ub sentence3 6G B E F S ub sentence4 3C B D 5 句子匹配 在句子匹配之前 必须建立符号知识库 存储对 大量已知符号分析的结果与符号的对应关系 然后 将实时分析符号所得的符号句子在知识库进行匹配 和查找 所得结果即为识别结果 本文用到的知识库 结构为 R esult id L ong sentence S hort sentence S ub sentence1 S ub sentence2 S ub sentence3 R esult id为存储识别结果 L ong sentence为 第1级模糊长句 S hort sentence为第2级模糊度短 句 S ub sentence1 S ub sentence2 为第3级模糊 度节点子句集合 句子匹配过程如下 1 首先利用第1级模糊长句L ong sentence在 知识库中与L ong sentence字段进行匹配 如果成 功找到一个匹配项 识别结果为该项对应的R esult id 否则进行第2步匹配 2 利用第2级模糊度短句S hort sentence在知 识库中与S hort sentence字段进行匹配 如果成功 找到一个匹配项 识别结果为该项对应的R esult id 否则进行第3步匹配 3 利用每个节点子句分别与知识库中对应字 段进行匹配 根据子句匹配结果将得到一个结果集 合 设节点总数为n 节点子句S ub sentence1 S ub sentence2 的匹配结果分别为A B C 任取匹 配结果中的n 1项 求他们的交集 共得到n个交 集结果 然后求n个交集结果的和集 所得和集结果 即为识别结果 如果结果为空集 则降低匹配精度 即任取匹配结果中的n 2项求交集 然后求其和 集 如果得到非空集合 则该集合中即为识别结果 否则依此类推 直到n 2为止 如果这时和集结果仍 为空 则为拒识 以上例为例 设子句匹配结果为A B C D 则 识别结果为 R esultn 1 A B C A BD A CD B CD 如果R esultn 1为空集 则识别结果为 R esultn 2 A B A C A D B C BD CD 如果R esultn 2仍为空集 则为拒识 为解决空间不变性问题 可以为每一符号建立 多条知识储备 每一条知识针对同一符号的不同旋 转角度 第1级模糊匹配相当于完全匹配 第2级模糊 873 计算机辅助设计与图形学学报2000年 1995 2005 Tsinghua Tongfang Optical Disc Co Ltd All rights reserved 度匹配相当于关键信息匹配 第3级模糊度匹配相 当于节点信息匹配 这三级模糊匹配分别对应三级 模糊度句子 因为三级模糊度句子对符号的描述精 度依次降低 所以匹配结果的可信度也依次降低 所 以我们首先采用第1级模糊匹配结果 如果第1级 模糊匹配失败 则采用第2级模糊匹配结果 如果第 2级模糊匹配失败 则采用第3级模糊匹配结果 6 实验结果 因为系统是针对符号设计 所以对孤立的字符 和数字同样有效 采用孤立数字 字符和机械图符号 进行测试 结果如表2所示 表2 测试结果 孤立数字孤立字符机械图符号 98 5 97 3 96 8 经大量统计发现 本文采用的统计识别和结构 识别相结合的符号识别方法可以有效地解决符号识 别的空间旋转不变性问题 并达到很高的识别效率 和正确率 参考文献 1M a Jian2Bo The ProgrammerAnthology of I mageM anipulation w ith C Beijing Sea Press 1992 155 159 in Chinese 马建波 C语言图像处理程序集 北京 海洋出版社 1992 155 159 2M a Jian2Bo The ProgrammerAnthology