（计算数学专业论文）用神经网络方法分割粘连字符的一种改进方案.pdf

大连理工大学硕士学位论文 摘要 随着计算机的普及，人们越来越多地使用计算机处理日常工作和存储信息。o c r 系统已经广泛应用于办公自动化、侠速录入等领域。科技文献中有大量的数学公式，它 们是由特殊符号组成的复杂的结构体。如何将o c r 系统应用于数学公式识别的问题引 起了人们注意。为此，我们的研究集体提出了一种新的关于数学表达式识别的设计思想， 并写出了程序。最终实现的系统可以将印刷体的数学公式( 图像格式) 转换成可编辑的电 子格式( 如l 姐e ( ，w o r d 公式编辑器) 。在前人工作的基础上，本文对粘连字符分割的 神经网络方法提出了一种改进方案，期望进一步改进印刷体数学公式识别系统的表现。 论文在简述系统构成的基础上，主要讨论了粘连字符的分割和字符识别两个部分。 粘连字符的分割：由于纸质文档的印刷质量、纸张的光洁度、扫描仪的分辨率、二 值化等因素的影响，扫描得到的图像中的字符可能是粘连的。这为字符识别带来了困难。 本文提出了综合运用“查找最短路径方法”和“修正自组织特征映射神经网络方法”的 一种粘连字符分割方案。该方法对印刷质量较差的粘连字符效果更好，可以作为常用的 最短路径法的一个很好的补充算法，以提高分割成功率。 字符识别：分类器是整个识别系统的核心。由于神经网络方法在模式识别领域的良 。好表现，已经提出用自组织特征映射做字符的粗分类，b p 神经网络对各组字符做细分 类。针对这方面的工作，本文对b p 神经网络的输出层设计问题给出统计学习理论方面 的一种解释，期望在b p 网络分类器中输出层设计作出改进，进一步优化网络。 关键词：模式识别；字符分割；最短路径；自组织映射网络；b p 神经网络； 奎堡墨三查堂堡主堂垡笙壅 a n i m p r 0 v e dn e l l r a ln e 觚o r km e t h o df o rs e g m e n t a t i o no f m e r g e dc h a r a 酏e r s a b s t r a c t c 0 m p u t e r a i d c dd o c i l m e n t _ h a n d l i gs y s t e m sh a v eb e e nw i d e l yu s e d ，a i l do c rs y s t e m s h a v ef 0 i l n di t sp l a c ei no 气q u i c ki n p 峨a i l de t c n e r c 盯cm 翘ym & m e m a t i c a le x p r e s s i o 璐i n s c i e c ea n dt e c h n o l o g yl i t e m t u r ea dt h e s ee x p r e s s i o n sc o n s i s to fs p e c i a lc h a 删e r sw i m c o m p l i c a t e ds t m c t u r e t h eq u e s t i o nh o wt ou s eo c rf o rr e c 0 乒i z i i l ga n di n l d e r s t a n d i n g m a t 蛔n a t i c a le x p r e s s j o i l si np r i n t e dd o c u m e n ti sb e i n gs t u d i c d t ot l l i se n d ，0 u rr e s e a r c h 乎0 u ph a sd e s i g e d8r e c o g i t i o ns y s t e mf o rm a t h e m a t i c a le x p r e s s i o 丑si np r i n l e dd o c u m e n t t h es y s t 唧h a st h ea b n j t yt 0 舢弘i z em a t h c m a t i c a le x p r s i o n si ns c 脚e df i l e s 觚dt o r e c 0 璐t n l c tt h er e c 0 铲i z e de x p r e s s i 咖si n t oap a r t i c i l l 盯f o m a ts u c ha sia t e xo rw o r d b 觞e do nt h ep r c v i o u sw o r k si n t h i sr e s p c c t ，w ei nt l l i st h e s i si l n p o s e 壮i m p r o v e dn e u f a l n e t w o r km e t h o df o rs e g m e n t a t i o no fm e r g e dc h a n c t e r ss 0a st 0i i n p m v et h ep e r f 0 衄a n c eo f t h er e c o g n i t i o ns y s t e m a n e rab r i e fi i 岫d u c t i o no ft h e n s t n l 舐o no ft h es y s t 锄，t h i s 也e s i sm a i n l ys t u d i e sm o p r o b l e m s ：m e r g e d c h a r a c t c rs e g m e n t a t i o na n dc h a r a c t c fr e c o g l l i t i o n m e i g e da l a r a c t c rs e g m e m a t i o n ：d u et ot l l eq u a l i t yo fp r 主n t e r ，d e a n l i n e s so fp 印e r ， r c s o l u 矗o no fs c 砌e r ，b i n a r i z a t i o n 如de t c ，s y m b o l si l ls c 籼e dd o c u m e mm a yb em e r g e d 粕d c a l i o tb ee a s i l yf e c 0 印i z e d bt h i s m 鹪i s ，a l la l g o r i t h mf o rs e g m e n t a t i o no fm e r g e d c h a r a c t e r sb a s e do n “s h o n e s tp a t h ”a i l d “m o d i f i e ds o f m i sp r e s t e d t h i sp m p o s e d s e g m e n t a t i o nm e t h o db c h a v e sp a n i c u l a r l y9 0 0 df o rp o o r l yp r i n t e dc h a r 毛i c t e r s ，a i l di tc a nm a ：k e a 斟，o ds l l p p l e m 吼to ft h em o s to f t e nu s c ds h o n e s tp a t hm e t h o d c h a 伯d e rr e c 0 弘i t i o n ：r e c 0 鲥z e ri sak e yp a ni l l 血es y s t e m d u et oi t s g o o d p e 1 0 肋a n c ei np a t t c mr e c o g n j t i o nf i c l d ，a n i f i c i a ln e u f a ln e 撕o f kh 鲢a l r e a d yb e e nu s e di t h i sp a n f i r s t ，as o f mn e 咐o r kw o r k sa sr o u g l l d a 豁i f i e r w h i c hd a s s i f ys i m i l 缸s y m b o l s i n t ot h es a i n e 蓼o u p 。t h e n ，b pn e 嘲o r ka r eu s e da sf i n e d 蠲s 饱e i s ，w h i c hi d e 删f ys y m b o l s w i t h i nag r o u p i nt h i st h c s i s ，s o m ee x p l 锄a t i o n sj nt 咖so fs t a t i s t i c a ll e a r n i n ga r eg i v 吼f o r t h eo u t p u tr 印r c s e n t a t i o no fb pn e 砒a ln 咖o r k s ，h o p i n gl h a ti tw m i i n p r o v et h ep e 哟珊a n c e 0 fb pn c u r a in e m d r k sw h e nt l l e yd e a lw i mc l a s s i f i c a t i o np m b l 锄s k e yw o r d s ：p a “e mr e c o 驴l t i 帆； c h a 强c t e rs e g m e n t a t i o n ；s h o n e s tp a t h ； s e l f - o i 罂n i z i n g 纳t u nm a p ；b p n e u r a ln e t w o f i k 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：魄粤日期：堕生! 旦矽闫 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名： 诱丘i 聊躲墨。熟导师签名：；茎二。幽垒 超年么月丝日 大连理工大学硕士学位论文 1 绪论 1 1 人工神经网络 1 ，1 1 人工神经网络概述 人工神经网络( a n n ) 是以计算机网络系统模拟生物神经网络的智能计算系统。一个 人工神经网络是一个由简单处理单元构成的规模宏大的并行分布式处理器。人工神经网 络在两方面与人脑相似： 1 人工神经网络获取的知识是从外界环境中学习得来的。 2 互连神经元的连接强度，即突触权值，用于存储获取的知识。 根据一个简化的统计，人脑由百亿条神经组成，每条神经平均连结到其它几千条神 经。通过这种连结方式，神经可以收发不同数量的能量。神经的一个非常重要的功能是 它们对能量的接受并不是立即作出响应，而是将它们累加起来，当这个累加的总和达到 某个临界闽值时，它们将它们自己的那部分能量发送给其它的神经( 见图1 1 1 。大脑通过 调节这些连结的数目和强度进行学习。尽管这是个生物行为的简化描述，但同样可以充 分有力地被看作是神经网络的模型。 输入 = 一l ( ) ，d a 上在如下意义下一致收敛于实际风险 只 ) 熙p 孵脚) 咄扣) ) s ) - o ，v s 。 ( 1 1 9 ) 换句话况，e r m 原则的一致性等价于式( 1 1 9 ) 的一致单边收敛。 对应于一致单边收敛，还有一致双边收敛 大连理1 大学硕士学位论文 牌p 溜) 一r 一( a ) | ，十o ，v s ，o ( 1 2 0 ) 显然，一致双边收敛是一致单边收敛的充分条件。 上述讨论说明一致单边收敛与e r m 方法的有效性是等价的。对于任意一个学习机 器( u ) 来说一致单边收敛又是和被称为函数集q ( z ，口) ，a a 容量的概念密切相关。在 统计学习中，函数集容量( 、，c 维) 是一个重要概念，它描述了函数集q 0 ，a ) ，a a 的分 类能力，是学习过程致收敛与否及其推广能力的重要因素。 】3 3 一致收敛的界 v c 维【9 】 定义一个指标函数集q ( z ，a ) ，a a 的v c 维，是能被集合中的函数以所有可能 的2 “方式分成两类的向量z ，z 。的最大数目 ( 也就是能够被这个函数集打散的向量的 最大数目) 。如果对任意的n ，总存在一个n 个向量的集合可以被函数集q ( z ，a ) ，口a 打散，那么函数集的v c 维是无穷大。 神经网络的v c 维 关于神经网络的v c 维有以下结论： 1 令n 表示由神经元构成的任意前馈网络，激活函数为 础) = 怯= ( 1 z ，) 则n 的v c 维为d ( l o g 缈) ，其中是网络中自由参数的总数f l l 1 2 1 。 2 令n 表示一个多层前馈网络，其神经元使用个s i g m o i d 激活函数 妒p ) 2 南 1 2 2 ) l + e x 口( w i 则n 的v c 维为d 缈2 ) ，其中是网络中自由参数的总数 1 3 】。 e r m 原则一致收敛的速度1 1 4 1 5 ，1 q v c 维在学习的一致收敛的速度上提供了一个界。对于v c 维为 的指示函数集， 下面的不等式成立 p 鬻) 叫口) l 小( 等几x p ( 一) ( 1 2 3 ) 口e ” 用神经网络方法分割粘连字符的一种改进方案 其中p ) 是学习机器在所有样本上分类错误的期望，v ) 是在训练样本上的分类错误 率。当v c 维 是有限的时候，式( 1 2 3 ) 右端随增大趋于0 。 令，7 表示事件s u p 旧 ) 一v ) lz 发生的概率。那么，以概率1 一卵，我们可以说对所 有权值向量口a ，下面不等式成立 p ) c v ) + g ( 1 2 4 ) 令叩：( 三掣) 一e x p ( 一。：) 解得 “蛳莉；挣。g 晕) + 1 】一扣叩 ( 1 2 5 ) 式( 1 2 4 ) 以f = 。( ， ，叩) 描述的界在p ( 口) = 时有最坏情况。对于小的p ) ，有 哩等掣嘲c c 唧c 一争 m z s ， 从( 1 2 6 ) 式推出，以概率1 一叩，对于所有的a a ，有 p ( 口) v ( 口) + 1 ( ， ，叩，v )( 1 2 7 ) 其中 删力川- 2 酿啪川) ( 1 + j 1 + 哥丢) ( 1 2 8 ) 当1 吖a ) = o 时 ，( ， ，7 ，o ) - 4 s j ( ， ，叩)( 1 2 9 ) 总结一下关于一致收敛速度的界： 1 一般情况下，我们有如下一致收敛速度的界 p ( a ) v ( a ) + 占1 ( ，a ，叩，v )( 1 3 0 ) 2 对于v ) 较小，有 尸( 口) v ( a ) + 4 ；( ， ，叩) ( 1 3 1 ) 3 对于接近于1 的大训练误差v ( a ) ，有 大连理li 大学硕士学位论文 p ( a ) v ( a ) + o ( ，i l ，叩)( 1 3 2 ) 一般的学习方法( 如神经网络) 是基于使v 位) 最小。在理论上可以通过增加算法( 如神 经网络) 的规模使得v ) 不断降低以至为0 。但是，这样使得算法( 神经网络) 的复杂度增 加，即v c 维 增加，会导致出现学习机器推广能力差的现象出现。在第四章中将会对 此进行举例说明。 1 4o c r 系统中数学公式的分割、识别与重组 1 4 1o c r 的发展现状 o c r 是光学字符识别( o p t i c a lc 抽a r a c t c rr e c o g n i t i o n ) 的英文缩写，是利用专门的识别 软件对使用光学方法得到的文字或字符图像进行分析、识别，最后转换成计算机内码的 技术。它是一门融合图像处理、识别、文本理解与还原、表格膘据处理等技术于一体的 综合性技术产业，涉及到模式识别、人工智能、模糊数学、组合论、信息论、计算机等 多个学科，也涉及到语言文字学、心理学等学科。根据应用情况可具体分为印刷体识别 和手写体识别，手写识别又分为在线和离线手写识别。印刷体识别7 】和离线手写识别 通常通过扫描仪把已经印刷或写在纸上的文字输入到计算机中，作为一幅图像存储在计 算机的存储器中，然后根据需要对这些图像做图像处理，从中提取出用于识别的特征。 在线手写识别【1 8 】则需要一种专门的输入设备，使得能在使用人写字的同时，将所写的笔 划轨迹、写字人用力等信息直接输入到计算机中。这样的数据不是图像形式，因而避免 了图像处理这一步。 当前的o c r 系统对手写、印刷体文本都有很高的识别率，已经广泛应用于办公自 动化、快速录入等领域，克服了人工输入费时费力的缺点。这方面国内有代表性的研究 单位有清华文通、中自汉王、北京信息工程学院、国家智能计算机研究中心以及重庆大 学光机所。现在对于汉字这样的超大字符集，识别率也达到了9 5 以上。汉王、清华文 通在办公自动化方面作了很多工作，已经有成熟的o c r 产品进入市场。清华文通研制 开发出多体汉字识别、汉英混排文体识别、多文种印刷手写全能文本自动识别、联 机手写汉字识别、脱机手写汉字数字识别、票据识别、表格识别、名片识别、身份证识 别、车辆号牌识别和网络o c r 等系列产品。汉王公司的汉王笔完全不受笔划顺序限制， 允许常见的倒插笔及习惯性连笔。对连笔识别率大幅度提高，可混合识别繁体、简体、 香港字及常见异体字。正楷识别率达9 9 ，连笔字识别率达9 0 。国外优秀酌o c r 软 件有c a e r e 公司的0 m n i p a 鼬p r o ，它具有自学习的功能，当用户把它认错的字纠正过来 以后，在读其它文档时就不会重犯错误，准确率可达到9 9 7 以上。w o r d s c a n 和 用神经网络方法分割粘连字符的一种改进方案 w o r d s c a n p l u s ，识别针打文档时性能特别好，适于处理较早期的计算机打印文件。 t e x t p e n 支持若干种罕见的外文，还能把表格输入到电子表格中。m i c r o s o f t 推出的办公 套件m i c r o s o f t o 舾c e x p 中，不仅加强了原有对手写输入支持，还增加了o c r 的工 具组件。i b m 、m o t o r o l a 、h p 等公司都陆续展开了这方面的研究。 1 4 2o c r 系统中的数学公式识别 数学公式识别系统与普通文档字符识别系统的区别在于数学表达式具有复杂的结 构，识别系统识别出单个字符后，重组系统必须将这些字符置于各自正确的位景，否则 结果将失去数学公式的意义。因此，数学表达式的识别研究分两个方面：符号识别和结 构分析。符号识别，主要集中在数学符号的识别，本质上与大多数字符识别问题一样， 二维模式结构分析的研究已有很长的历史，可以借鉴它们的方法；结构分析则主要在前 面工作的基础上，通过句法分析和语法分析辨识各个字符之间的关系。 符号识别由三个部分组成，文档图像预处理和符号提取、字符特征提取、识别器。 识别系统处理的对象是从扫描仪扫描到计算机中的数字图像。扫描后的图像必须经 过二值化、倾斜矫正、去噪等步骤。去噪是一个重要过程，系统处理的是从实际环境中 取得的字符图像，一方面扫描对象可能包含不可预测的噪音，一方面扫描过程中扫描仪 可能产生噪音。因此扫描后得到的数字图像可能有随机污点。目前的去噪算法与问题相 关，还没有通用的去噪算法。倾斜矫正将倾斜的文本旋转矫正，倾斜矫正也为后期结构 分析做准备。通过把倾斜文本矫正，使数学符号的重心在同一水平线上，然后才能分析 各个符号的位置关系。另外，由于纸质文档的印刷质量、纸张的光洁程度、扫描仪的分 辨率、二值化等因素的影响，扫描得到的图像中的字符可能是粘连的。因此，粘连字符 的分割是预处理过程中重要的一步。在第二章，将介绍常用的图像预处理算法，以及本 人提出的一种新的基于m s o 刚1 1 j 平口最短路径法1 2 】的粘连字符分割。 不同的特征提取方法提取一个字符的特征是不同的。需要提取抗平移、抗缩放、抗 旋转以及抗干扰的字符特征。在第三章中，介绍基于矩方法的特征提取方法和基于人工 神经网络特征选择方法。 识别器是整个识别系统的核心，也就是识别分离后的字符。好的识别器不但在训练 样本上错误率较小，而且在测试样本上也要有高识别率。成功的识别方法之是联合 s o f m 网络和b p 网络。s o f m 网络用来粗分类，按字符图像的矩特征把它1 门先分成若 干子类，把”大”问题化为”小”问题。然后用b p 网络细分类，用属于各类的训练样 本的矩特征矢量对子b p 网络进行训练。b p 网络是一个使用较多的网络，但是它不好控 大连理工大学硕七学位论文 制，训练中有较多人为因素。就周凤麒提【3 】出的b p 网络的输出层设计问题，本文将在 第四章给出统计学习理论方面的解释。 字符识别为结构分析作了前期准备。侯利昌【1 】提出公式重组的算法，将二维平面上 的公式结构转换成用u 1 ) 文法表示的语法树结构。在第5 章，将简要介绍这一方法。 本文作者创新性的工作主要集中在提出了基于“查找最短路径方法”和“修正自组 织特征映射神经网络方法”的一种粘连字符分割方案。 圈 图1 5 系统结构 f i g 1 5s y s l e ms i f u c t u r e 注1 1 大连理： 大学应用数学系智能计算 教研室提出的表达式识别系统的结构图 齑固 用神经网络方法分割粘连字符的一种改进方案 2 图像预处理与字符分割 o c r 系统通过“分割一识别”过程把数字化图片转化为可编辑文档。在英文文献 的识别过程中，只要能识别1 0 0 多个字符就可以了。可是，由于纸质文档的印刷质量、 纸张的光洁程度、扫描仪的分辨率、二值化等因素的影响，扫描得到的图像中的字符可 能是倾斜、粘连或断裂的。如此巨大的待识别样本是任何一个o c r 系统都难以处理的。 因此，识别前的图像处理是十分必要的。 & 2 1 讨论图像的预处理。& 2 2 介绍如何从一幅图像中分离出字符，接着2 3 给出 三种粘连字符分割方法。它们的核心思想是最短路径和自像素聚类。 2 1 图像的预处理 倾斜矫正：倾斜文本的矫正，使同一行的字符重心处于同一水平线上。 在扫描的过程中，可能会因为印刷品摆放位置不正而引起图像的倾斜。倾斜的图像 会给结构分析工作带来很大的困难。所以我们需要提前把它旋转过来。依据公式如下【”】 8 ：委删缸且。等( 。；2 ) z m 2 0 一川0 2 z ( 2 1 ) 其中一是包含目标区域的椭圆的长轴与y 轴的夹角，m 。= 罗z 9 y 9 ， ，_ ) ，) ， ，y ) 是 ( r 了白 点血，y ) 的像素值。旋转后，文本行处于水平位置，可以方便的进行字符分割和公式重 组。 二值化：选择合适的域值以减少字符的粘连和断裂。 为了使数字图像中的对象与背景相分离，我们采用整体闽值选择法进行二值化，既 考虑到处理速度又保证了二值化的效果。闽值的选取按以下原则： 1 计算原来的整个灰度图像像素值的均方差v 和灰度均值p ； 2 取图像像索灰度均值与均方差的差作为闽值：日；e v ； 3 若该像素的灰度值小于扫，则该像素为黑点( 像素值为0 ) ，否则为自点( 像素值为 2 5 5 、。 平滑处理：去掉孤立噪声，平滑边沿。 二种最简单的行之有效的平滑方法就是中值滤波方法【2 0 】。所谓中值滤波，就是对二 值图像上的一点o ，y ) ，按下式计算0 ，y ) 及其8 邻域的代数和f ( f ，) 聊棚= 。荟。鬣( 卜们* 1 0 1 m - 一1 ，0 1 1 8 ( 2 2 ) 大连理工大学硕士学位论文 像素0 ，_ ) ) 的值厂( f ，) 由决定 邝一辟磊，裂篡2 5 5 仁s ， 2 2 文字符号自动分离 普通符号的分离方法 字符与字符之间没有包含、上下标等关系，只是普通的前后关系时，而且行与行之 间，前后字符之间没有黑像素或者很少的黑像素，可以使用水平垂直分割法来分割这样 的普通符号图像。其思想是利用两行字符之间的行空白以及两个字符之间的列空白来切 分字符，把字符从图像中分离出来。大多数文档中的文本部分都可以使用这个方法来分 离，这也是为什么预处理中要求图像中的字符的排列必须是水平的。具体算法如下： 1 由上向下、由左向右扫描图像，找到的第一个有黑像素的行作为起始行，并以这 个黑像素点作起点； 2 继续对图像按照由上向下、由左向右扫描，如果检测到一个空白行( 一行中没有 一个黑像素点) ，那么从起始行到这个空自行之间的图像，作为第一行字符，实现了第 一行字符的分割； 3 对分割来出来的第一行，把起点所在的列作为起始列，由左向右、由上向下扫描， 如果检测到一个空白列( 一列中没有一个黑像素) ，则由起始列到空白列的这一部分被看 作一个字符，实现个字符的分离； 4 同样的方法，寻找下一个起始列和空白列，依次分割同一个字符行中剩下的字符； 5 寻找新的起点，依次分割剩下的字符行。 重叠符号的分离方法 r， 一些数学符号，如、等，与其它符号是包含关系，如果用上述的水 平垂直分割法来分割这些字符是不可能的。可采用轮廓跟踪算法来处理这些情况。 定义( 轮廓) 至少有一个4 - b 域不在r 内的所有r 中像素的集合，其中r 是连通的 像素集合。如图2 1 ，其中c ， ) 不是轮廓上的像素点，而是内部点。 用神经网络方法分割粘连字符的一种改进方案 b a 、 眯) 基j )、瞰珩 _ 二- 。 ， l c d 图2 1 轮廓的定义，a 、b 、d 是轮廓上的点 f 远2 1d e f i n i t i o no fc o n t o l i f ，a 、b 、d 盯ep o i n t so fc o n t o u r 一个字符，总可以认为它存在一个封闭的轮廓。因此，一个轮廓上的像素总可以有 一条通路来跟踪它。由自上而下、自左向右扫描，当遇到黑像素时，设为起始点a 。用 “连接成分的轮廓跟踪”方法【”j ，沿轮廓“走”，直到当前像素遇到起始点a 时，跟 踪结束，确定此字符的区域。然后用区域填充方法完成整个字符的提取。一个字符完成 后，再寻找新的字符，照此办理，从最左面逐层地剥离原来纠缠在一起的符号，实现符 号的分离。 对于待识别的数学表达式，使用这个方法将表达式中的每一个字符分割出来，将每 一个字符的信息如字符边界，字符矩阵等存放在一个节点中，得到一个线性链表。 综合上述，待识别数学表达式字符图像进入预处理系统后将经过以下几个步骤：图 像旋转，图像二值化，轮廓跟踪算法提取数学表达式每个字符信息，字符图像平移和缩 放，字符图像平滑。 2 3 粘连符号的分割方法 许多研究者试图用各种方法分割粘连字符【2 ，扭2 “。最短路径方法( s p m ) 应用的比较广 泛。侯利昌队朱并队【2 2 】提出了一种新的s o m 神经网络权值更新算法和基于这种新的 s o m 神经网络权值更新算法的一种印刷体粘连字符的新分割方法。可以称为m s o m ( 修 改的自组织特征映射方法1 。其思想就是先利用修改的s o m 找到粘连字符之间白像素区 域的中心，然后有选择地连接这些中心，达到分割的目的。本文作者用m s o m 确定一 个适当的分割区域，然后在这个区域中用最短路径方法查找最短路径。该方法对印刷质 量较差、粘连较严重的样本效果较好，分割成功率比最短路径法和m s o m 都要高。 大连理工大学硕士学德论文 2 3 1 最短路径分割 文献【2 j 提出了一种基于“查找最短路径”的分割方法。算法的思想是假设一对粘连 字符粘连程度最轻的路径就是切割路径。它预先定义了切割点移动的代价，通过迭代计 算、比较最小值来寻找切割路径。具体地，一对粘连字符，假设其大小为m 行n 列，算 法选出代价最小的连接第一行和最后一行的“路径”来完成分割。定义路径的代价如下： 1 朝着一个自像素向下做一次移动视为无损耗，丽朝着一个黑像素同样向下做一次 移动的代价为1 0 。 2 朝着一个白像素向对角线方向做一次移动的代价为1 ，而朝着一个黑像素同样向 对角线方向做一次移动的代价为1 0 2 。 从上述路径的方向及其代价的定义可见切割点只有三种移动方向：一种是垂直向下 移动，另外两种分别是向东南和向西南移动。移动方向上的限制避免了路径的环状检查， 也使算法变得简单。利用一个n 维向量y ，它存储从首行到当前行上每个像素的最小代 价，以及m 行”列矩阵丁，此矩阵( f ，f ) 元素记录了从首行到达( f ，) 位置的最短路径经过 f _ 1 行时的横坐标。计算最短路径按行从上到下依次进行，直到最后一行。在最后一行 中的最小值就是最短路径的代价，记它经过矩阵元素，七) ；查找最短路径就从 ，k ) 开 始，按行从下到上根据r 中元素值回朔到第一行就找到了最短路径。 ( a ) 图2 2 “查找最短路径”算法的切割路径 f i g 。2 2t h ec u tp a t l lo f s h o r t e s tp a t h ” 注1 1 图片来自论文【2 】 蕊二嚼嚣豢嚣墓 ；o。；。：黜m：。；o：-： 震一 l l i黎i f l 嚣纛蠡 墨l | i ；产 用神经网络方法分割粘连字符的一种改进方案 最短路径方法能够在一定程度上对切割路径起到调节作用，但由于计算切割代价的 方式具有局部性，如果遇到粘连情况严重或者粘连字符中有的字符发生断裂，很难保证 找到的“最短路径”就是正确的分割路径。 2 3 2 基于s o f m 网络的字符分割 自组织特征映射，也称为自组织映射，它的主要目的是将任意维数的输入信号模式 转变为一维或二维的离散映射，并且以拓扑有序的方式自适应实现这个变换。s o f m 网 络基于竞争学习，网络的输出神经元之间通过侧向连接相互竞争以求被激活。在每个时 刻，只有一个输出神经元被激活，称为获胜神经元。获胜神经元及其一定拓扑领域内神 经元的调整保持临近关系这种拓扑性质不变，即相距相近的输出向量对应距离相近的输 入向量。s o f m 采用非监督竞争学习。 图2 f 3s o f m 网络结构 f 远2 3s o h 幢n n l ss t r u c t u r e 网络结构 s o f m 网络分为输入层和输出层，输入层的任意一个单元石。( n = 1 ，) 通过权值 阡_ 。与输出层的每一个单元y 。( m = 1 ，m ) 连接。输出层各单元常常排成一维、二维或 多维阵列。如图2 _ 3 所示，输出单元排成一个二维阵列。注意，图中每条连线表示一个 维输入向量。 学习过程 设训l 练样本为仁，f ；。c r “，可以通过下述过程来确定网络权值矩阵。 1 初始化将训练样本仁。r ，排成序列工“。随机选取初始权矩阵。令七= o 。 犬连理j 二大学硕十学位论文 2 竞争对每一个输入，网络中的神经元计算它们各自的输出值，具有最大值的特 定神经元成为竞争的胜利者。 具体地，设网络输入工”一0 ：，x ：，j ；) ，输出为 y ：= 吒x ：， 坍t 1 ，m ( 2 4 ) 全体输出单元竞争后，选出唯一的获胜单元y ： y ：2 要糯y ： ( 2 5 ) 这表示输入向量x 被分到y ：所代表的这一类中。可以证明，在权值向量既长度 固定 i 瞧卜c ( 2 6 ) 的条件下，下式与式( 2 6 ) 等价 肛一比| 1 = 品魏忙一眠0 ( 2 7 ) 3 合作获胜神经元决定兴奋神经元的拓扑邻域的空间位置。 可以用各种方式对输出层的获胜神经元y 。定义其z 阶f lo ，l 2 ，邻域：，如图2 4 所示。设另一个输出单元y 。? ，但y 。唾r ，定义_ y 。和) ，。的距离为 d 。暑口 ( 2 8 ) ( 日) ( 6 ) 图2 4 输出单元的邻域 f i g 2 4n e i g h b o r h o o do fo u i p u lu n i t s 用神经网络方法分割粘连字符的一种改进方案 出。 4 权值修改兴奋神经元通过对它们权值的适当调节以增加它们关于该输入的输 利用适当选定的距离函数矗彬。k ) ，按下式修改权值 5 权值归一化 成立。 6 收敛性检测 由式( 2 9 ) ，得 仰譬“- 矸曹+ ( d 。，t ) o 一印：) ( 2 9 ) 权值修改后，将各神经元的权值分别乘以适当的常数，使式( 2 6 ) 若按某种准则权值迭代收敛，则停止；否则七增加1 ，转到2 。 h 曹一工件) 一( 1 一矗( d m 。，七) ) ( 阡葛一工) ( 2 1 0 ) 因此， 当1 _ l l ( d 。七) lc 1 时，算法是收敛的： 慨“”噼一x 6 ( 2 1 1 ) 距离函数 在上面的学习过程中，选出获胜单元y 。后，我们应该调整y 。及其适当邻域内的各 神经元的相应权值矢量，使其对于z 做出更大的响应或更接近于z 。调整的幅度j 立 随着各单元与y 。距离的增加而减弱，即距离函数厅q 。，七) 应随着d ，。的增大丽减小。常 用的几种距离函数在图2 5 中给出，分别为阶梯函数( a ) 、三角形函数( b ) 、高斯函数( c ) 和墨西哥草帽函数( d ) 。其中墨西哥草帽函数是两个高斯函数的差： 蜊) 嘞e x 卧参) 嘞e x p ( 一刍) ( 2 - 1 2 ) z 口z 盯， 大连理1 ：大学硕十学位论文 1 7 ； j ； l、 一、 、一一 图2 5 常用距离函数取固定) f i g 2 5d i s t a n c e f u n c t i o n ( k i s f i x e d ) 它具有对邻域边缘消除刺激的效应，从而会增强输出平面上分类边界的“对比度”。 修正的s o f m 聚类白像素点咿2 】 利用s o f m 将白像素点聚类，让聚类点停在白像素点密集的地方( 见图2 8 ) ，然后 连接聚类点，这样就确定了符号间的一条分割线，就可以把粘连的字符分割开。 把经过图像处理的二值图片看作信源空间s ，白像素点的坐标亭似看作输入信号， 神经元w 呈二维网格状网格分布a 。通过训练，得到映射庐。：s a ，使a 中结点分 布在图像中自像素聚集的区域。 通过实验，侯等【1 ，篮】发现传统s o f m 学习规则容易使神经元聚集在一起，不适合作 分割。根据f i s h e m a n sr u i e 【2 8 】，让最佳匹配单元( b e s tm a 瞄l i n gu n i t ：b m u ) 的邻近神经 元被b m u 和输入向量双重影响，而不只是b m u 周围的神经元权向量向输入向量方向 移动。于是改进了s o f m 的学习规则，使神经元相互之间存在排斥作用，从而尽量扩大 自己的接受域 j a 彬( 七+ 1 ) 2 叩( 。) “ c ，2 ) ( 亭“一k ( 2 ) f 2 1 3 ) i ，( k + 1 ) ；m f 啦 + 1 ) ， ，c 、 7 并j 神经网络方法分割粘连字符的一种改进方案 其中，肼。是获胜神经元f 和神经元女之间的影响因子。( 如图2 7 ，图中：神经元一， 的更新权值通过系数m 。对神经元4 的影响，l ：输入样本对神经元4 。的影响， 工，= l 。+ ：) 。若卅。，0 ，说明两个神经元之间相互作用。各神经元的平衡态由于m 。的 存在而相互影响，接受域r 也通过埘。相互影响。 过三 图2 6 传统的学习规则：输入样本 f i g ，2 6t r a d i t i o n a lu p d a t i n gr u k f o rs o f m ：i l l p u t。：n e u r o n s 图2 7 新的学习规则：厶= 工l + l 2 f i g 2 7n e wu p d a t i n gn l l e f o r s o f m 上3l 工1 + 2 训练结束后，所有的权值达到一个相对稳定的状态。此时，侯等选择第二列的结点 ( 口点) 作候选分割结点，连接它们( 共有七种组合c ；+ c ；+ c ；一7 ，最上面的和最下面的 结点分别向上、向下作垂线1 作分割路径。分别计算路径长度，选择一条最短路径作分 割路径( 见图2 8 ) 。 孤辨 图2 8 神经元的分布( 口a i l d ) 口表示候选分割结点；红线表示分割路径 f i g 2 8d i s t r i b u t i o no fn e u r o n s ( 口a n d ) 口：叩r e s e n ic 柚d i d a l es e g m e n t a i i o nn o d e s a n dt h er e dl i n er e p r e s e n t ss e g m e n t a t i p a t h 大连理工大学硕士学位论文 2 3 3 基于最短路径方法和s o f m 的字符分割方法 相比于最短路径分割，修改的s o f m 分割更具有全局性。本人结合局部性的“查找 最短路径”和全局性的“修正s o f m ”方法，提出一种综合实现方案，用于粘连字符的 分割。对印刷质量较差、粘连较严重的样本，效果较好，成功率有所提高。可以作为常 用的最短路径法的一个补充算法，以提高分割成功率。 方法的基本步骤是：首先用“修正s o f m ”方法进行白像素点的9 点聚类，然后依 掘9 个聚类点的收敛位置，划分出一个最可能包括实际粘连边界的有适当宽度的矩形区 域5 印r e 占f d n ，最后在s 印r e 占f d n 里查找最短路径。详情如下： 1 “修正s o f m ”对白像素的聚类 s o f m 聚类时，聚类点初始值对聚类点的最终位置有较大影响。本文提出以下选取 初始值方法，作为对文献l l 】中自像素聚类算法的修正。首先解释一下左中右3 列的概念。 左中右3 列，每列包含3 个聚类点，共9 个，是s o f m 中的9 个神经元的值。s o f m 聚 类前，9 个神经元的初始值是以3 列的形式放置在粘连字符上的。文献【1 j 提出的自像素 聚类算法，保证了聚类后神经元不会聚集在一起，并保持9 个神经元相对位置大致不变。 因此，本文按位嚣称9 个神经元为左中右3 列。记由每列神经元在z 轴方向的边界和粘 连字符上下边界所围成的矩形区域分别为m 、尺2 、r 3 ；粘连字符宽度为h w 耐折。 以下算法都基于我们的以下努力：让左中右3 列神经元的位置分别大致对应左字符、 粘连区域和右字符。当聚类前3 列神经元的x 位置大致重合于左字符、粘连区域和右字 符，则用“修正s o f m ”方法得到了s o f m 收敛后3 列神经元所在3 个区域，即r 1 、尺2 和r 3 这3 个区域后，由于“修正s o f m ”完成白像素的聚类的功能，故r 1 的位置仍大 致相当于左字符，r 2 的位置仍大致相当于粘连位置，只3 的位置仍大致相当于右字符。 如果3 列神经元的初始位置与左字符、粘连区域和右字符的位置之间有较大偏移，那么 聚类后r 1 、r 2 和r 3 不一定能大致重合于左字符、粘连区域和右字符，但是聚类前后3 列神经元位置的移动仍是受到白像素聚类的影响，适当修改3 列神经元初始值再次聚类 后，可能就能让3 列神经元的位置分别大致对应左字符、粘连区域和右字符。 算法如下： s t e p l 借助文献【3 0 】提出的公式，利用直方图确定粘连边界的初始预测值咖。 s t e p 2 将咖2 、驷和咖+ ( h w f d 柝一驴) 2 分别定为左列、中列和右列在工方向上的初 始值( 此时，m 、尺2 和r 3 宽度均为0 ) 。每列在y 方向上均匀放置。然后利用文献1 1 】提 出的白像素聚类算法进行s o f m 聚类。 用神经网络方法分害0 粘连字符的一种改进方案 s t e p 3 s o f m 聚类结束后，比较驴和j r 2 的位置关系( 此时，一般情况下，尺1 、r 2 和 r 3 宽度均大于或等于1 ) 。当与r 2 较近，就认为粘连边界的预测值咖较准确，可以作 为s o f m 的初始值使用，算法结束。否则转s t e p 4 。 s t e p 4 向月2 方向移动妒。转s t e p 2 。 2 5 印r e g i 的调整 以r 2 为基础，遇到r 2 与咖较近，或尺1 与r 3 一个过宽，另个过窄时调整 5 印r e g f d n 。( 例如，r 1 较窄而r 3 较宽，说明r 3 比较充分的覆盖了右边字符，而r 2 也 许因此过于偏向左边字符，所以分割区域可适当向右增宽的多一些) 经过以上调整之后 5 印r e g f d h 的宽度仍过窄，适当增宽s 叩r e 占f d n 。如果调整方式依据粘连字符高宽比有 所区别。具体过程如下： 图2 9 分割区域的调貉 f i g 2 9t 1 1 l ea d j u s i m e n t 。f g m e n t a t i o nr e g i o n 以上5 印r e g 曲n 的确定和调整过程的细节，见附录a 。 3 在5 印r e 占f d n 中查找最短路径 按文献【2 1 定义的切割