（计算机软件与理论专业论文）无约束手写数字串切分与识别算法研究.pdf

四j l li j 币范大学学位论文独创性及使用授权声明 本人声明：所呈交学位论文，是本人在导师王验指导下，独立 进行研究工作所耿得的成果。除文中已经注明引用的内容外，本论文不含任何 其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符而 引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学拥 有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提交印 刷版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数据库进 行检索：2 ) 为教学和科研目的，学校可以将公开的学位论文或解密后的学位 论文作为资料在图书馆、资料室等场所或在校园网上供校内师生阅读、浏览。 论文作者签名：髓 呻7 年亭月哆日 硕士学位论文 无约束手写数字串切分和识别算法研究 计算机软件与理论专业 研究生罗佳指导老师王玲教授 手写数字识别是光学识别技术o c r 的一个分支，属于模式识别的一个重要 问题，研究如何利用电子计算机自动辨认人手写在纸张等介质上的阿拉伯数字。 这在邮政分拣、银行票据识别、报表统计等众多领域中有着广泛应用前景。同时， 数字串切分是识别的关键步骤，其准确与否直接影响到后面识别率的高低，因此 同样具有重要研究价值。本文主要讨论手写体数字串在脱机、无约束( 即没有任 何类4 陛框格限制) 的情况下对其进行切分和识别的算法。 多年来，人们在这个研究领域提出了很多有效的方法，但因书写人的随意 性，风格的迥异性使得该领域远不能达到完善的程度。尤其是在无约束造成大量 重叠、粘连、断笔存在的情况下，其切分和识别率都达不到满意的效果，仍有许 多工作要做。本文在前人研究成果的基础上，致力于无约束脱机手写数字串的切 分和识别算法的研究，目的是为了能在该领域做些有益的探索。主要工作包括以 下几个方面： ( 一) 数字串切分：在歹0 举了多种现有经典切分算法的基础上，提出一种新 的基于数字串字符图像凹凸特性的切分方法。该方法从根本上克服了已有算法需 要细化、路径搜索等复杂处理的弊端，从而大大提高切分率，缩短切分时间。 ( 二) 单数字识别：本文未采用目前广为流行的神经网络方法，而是提出一 种利用字符图像的凹凸特性，构造其笔顺编码及正则表达式匹配的新方法。因利 用字符的整体特征，故识别过程简单快速。在获得了较高识别率的同时，识别速 度也较其它方法提高了近一倍。 坝k 学位论文 ( 三) 数字识别扩展：除了数字，本文提出的基于凹凸特性的识别方法还可 扩展n d , 类别字符集。为此，特别做了有关2 6 个大写英文字母识别的实验，并 详细描述了利用字母图像凹凸特性识别的完整方法。与其它方法相比，识别率和 速度都得到了提高。 ( 四) 系统实验：使用m a t l a b7 0 开发工具，以国际上通用的手写体数字 图像数据库和自主采集的手写体数字图像库为实验对象，独立完成了一个基于凹 凸特性的无约束手写数字串切分和识别的演示系统。同时还与部分其它相关算法 作了比较。可以看出，本文方法取得了较好效果。 关键词：手写数字识别数字串分割赋值背景凹凸特胜笔顺编码 坝i 。学位论立 r e s e a r c ho naig o rit h mf o ru n c o n s t r ain e dh a n d w rit t e n n u m e r a is t ri n gs e g m e n t a t i o na n dr e c o g n i t i o n h a n d w r i t t e nn u m e r a lc h a r a c t e rr e c o g n i t i o ni sab r a n c ho fo c ra n dj t a l s oi st h ei m p o r t a n tp r o b i e mo fp a t t e r nr e c o g n i t i o n i ti sc o n c e r n e dh o w t oa u t o r e c o g n i z et h eh a n d w r i t t e na r a b i cn u m e r a l so nt h ep a p e r su s i n g e l e c t r o n i cc o m p u t e r ，w h i c hh a st h ea b r o a da p p l i c a t i o np r o s p e c t si nt h e a r e a ss u c ha sp o s tt a p ，s t a t i s t i cr e p o r tf o r m sa n ds oo n ：a tt h es a t a et i m e ， t h en u m e r a ls t r i n g ss e g m e n t a t i o ni st h ek e ys t e pf o rr e c o g n i t i o n ，s oi t a l s oh a st h ei m p o r t a n tr e s e a r c hv a u e i nt h i sp a p e rw em a i n l yd i s c u s s g e n e r a lm e t h o d sf o ru n c o n s t r a i n e do f f l i n eh a n d w r i t t e nn u m e r a ls t r jr i g s s e d n e n t a t i o na n dr e c o g nj t i o n h a n d w r i t t e nc h a r a c t e rr e c o g n i t i o nh a sb e e ne x t e n s i v e l ys t u d i e df o r m a n yy e a r sa n dan u m b e ro ft e c h njq u e sh a v eb e e np r o p o s e d h o w e v e r ，i ti s s t i l lad i f f i c u l tt a s ka n dt h er e s u ti ss t i l l f a rf r o mp r a c t i c e e s p e c a 】l yw h e nt h e r ea r em a n yc o n n e c t e dn u m e r a lsi nt h ei m a g e ，b e c a u s e o ft h ed i f f e r e n tw r i t e ra n dd i f f e r e n tw r jt i n ss t y l e t h i sp a p e ri sf o c u s e d o nu n c o n s t r a i n e dh a n d w r i t t e nn u m e r a ls t r i n gs e g m e n t a t i o na n dr e c o g n i t i o n p r o b l e m t h em a i nc o n t e n t so f t h et h e s i s8 r ea sf o l l o w s ， ( a ) i nn u m e r a ls t r i n gs e g m e n t a t i o ns t a g e ，b a s e do n1i s t in gt h ep r e s e n t c l a s s icm e t h o d s ，t h ea u t h o rp r o p o s e dan o v e lm e t h o db a s e do nc o n v e xa n d c o n c a v ef e a t u r e t h em e t h o db a s i c a l l yo v e r c o m e st h ed e f e c t so ft h i n n i n g a n dp a t h s e a r c h i n g ，s oi tg e t st h eh i g h e rs e g m e n t a t i o nr a t ea n ds h o r t e r t i m e ( b ) w ed on o ta d o p tn e u r a ln e t w o r k ，w h i c hi st h ep o p u l a rm e t h o df o r n u m e r a lc h a r a c t e rr e c o g njt i o na tp r e s e n t ，b u tp r o p o s ean e wm e t h o dt h a t i tc o m p o s e s s e q u e n c ec o d ea n dr e g u l a re x p r e s s i o nu s ir l gt h ec h a r a c t e r s c o n v e xa n dc o n c a v ef e a t u r e s i n c eg l o b a lf e a t u r e so fc h a r a c t e r s ，t h em e t h o d 坝i 。学位论文 h a sh i g h e rr e c o g n i t i o nr a t ea n d t h er e c o g n i t io nt i m ei sr a i s e do n el i m e a sw e l l ( c ) o t h e rt h a nn u m e r a l s ，w ee x p a n dt h em e t h o d i n t o t h es m a l l s e t c h a r a c t e r s t h e r e f o r e ，w es p e c i a l l yh a v eat e s ta b o u tt h ec a p i t a le n g l i s h l e t t e r sr e c o g n i t i o n a n dw ed e s c r i b et h ef u l lm e t h o d ，w h i c hi sh o wt o r e c o g n i z et h el e t t e r sb a s e do nt h ec o n v e xa n dc o n c a v ef e a t u r e c o m p a r e d w i t ho t h e rm e t h o d s ，i t sr e c o g n i t i o nr a t ea n ds p e e da r ei m p r o v e d ( d ) a tl a s t ，w eh a v ef i njs h e da nu n c o n s t r a i n e do f f ljn eh a n d w r i t t e n n u m e r a ls t r i n g ss e g m e n t a t i o na n dr e c o g n i t i o nd e m os y s t e m ，w h o s eo b j e c t a r en i s ts d l 9a n ds h n i d b e s i d e s ，t h em e t h o dp r o p o s e di nt h et h e s i sw a s i nc o n t r a s tt oo t h e rm e t h o d s ，a n da c q u i r e db e t t e rr e s u l t k e y w o r d s ：h a n d w r i t t e nn u m e r a lr e c o g n it i o n ：n u m e r a ls t r i n gs e g m e n t a t i o n ： v a l u e a s s o c i a t e db a c k g r o u n d ：c o n v e x a n d c o n c a v ef e a t u r e ：s e q u e n c ec o d i n g 4 - 硕士学位论文 第一章绪论 1 ，1 引言 光学字符识别( o p t i c a lc h a r a c t e rr e c o g n i t i o n ，简称o c r ) 是2 0 世纪2 0 年代逐步发展起来的- - f 3 自动化技术，是图像处理与模式识别领域的一个重要分 支【”。其目的就是通过扫描、摄像等光学输入方式将汉字报刊、书籍、文稿及其 它印刷品的文字转化为图像信息，使图像内的图形、表格继续保存，再利用文字 识别技术将图像内的文字或表格中的资料律变成计算机能识别的文字，从而达 到减少存储容量、通讯交流的信息、循环利用已识别出的文字以及节省因键盘输 入而浪费的人力、物力、财力和时间的目的。 手写数字识别( h a n d w r i t t e nn u m e r a lr e c o g n i t i o n ，简称哪r ) 是o c r 的 个分支，它的任务是把手写阿拉伯数字( 如0 ，l ，2 ，9 ) 通过非键盘方 式输入到计算机中，以便作进一步的处理和应用，给计算机建立视觉系统，自动 辨识人用笔写在纸( 介质) 上的数字。它属于模式识别、人工智能的一个重要分 支，涉及到模式识别和图像处理、人工智能、统计决策理论、模糊数学、组合数 学、信息论、计算机等学科；同时也涉及心理学等，是介于基础研究与应用研究 之间的一门综合性的技术目，在办公室、机器翻译等方面具有重大实用意义。一 旦研究成功并投入应用，将产生巨大的社会和经济效益。再加上近年来我国开始 大力推广的“三金”工程在很大程度上要依赖数据信息的输入，如果能过手写数 字识别技术实现信息的自动录入，无疑将会促i 茳i 塞卜事业的进展。 r 主要包括两大类：一类是联机手写数字识别；二是脱机手写数字识别。 在联机r 中，计算机能够通过与计算机相连的手写输入设备获得输入字符笔划 的顺序、笔划的方向以及字符的形状，所以相对h n r 来说它更容易识别些。但 联机r 有个重要的不足就是要求输入者! 必须在指定的设备上书写，然而生活 中大部分的书写情况是不能满足这一要求的，如人们填写的各种表格资料，开具 顾十学位论文 的各种票据等等，如果需要计算机去认识这些已经成为文字的东西，就需要脱机 恨技术。比起联机州r 来，脱机 恨不要求书写者在特定的输入设备上书写， 它可以与平常样书写，所以脱机r 的应用更为广泛。 在现实生活中我们会遇到各种各样的数字信息。如邮政编码、统计报表、 财务报表、银行票据、学生成绩、车牌号码等。可以发现这些数字往往不是单独 出现，而是连在起，形成一串数字字符，甚至有时还没有任何框格之类东西的 限制，如银行票掘中的“帐号”一栏，只有一根横线，要求用户在这根横线上随 意地填写连串数字。这就往往造成数字之间粘连、断笔、重叠现象严重，比起 那些单独的数字识别或有类似框格限制的数字串识别来，这种没有任何约束的数 字串识别难度更大，给研究造成了巨大挑战。 1 2 国内外研究历史和现状 o c r 系统的历史可以追溯到1 8 9 0 年项帮助盲人阅读装置的发明专利。 1 9 2 9 年，由德国人t a u s h e c k 首先正式提出o c r 概念，并取得了o c r 专利权，四 年后，美国人h a n d e l 也取得了同样的专利权。但是真正o e r 是在本世纪5 0 年代 随着计算机的出现而到来的。 第代o c r 软件是在1 9 5 7 年开发的e r a ( e l e c t r i cr e a d i n ga u t o m a t i o n ) ， 它是基于窥视孔方法实现的，识另速度是每秒1 2 0 个英文字母。在此以后，世界 范围内广泛地进行着o c r 技术的研究和丌发工作。现代典型的商品化0 c r 系统可 分为三代： 1 9 6 0 年到1 9 6 5 年出现的商品化o c r 产品属于第一代，n c r 公司、f m r i n g t o n 公司、i 蹦公司分别研制出了自己的o c r 软件。其中最早的o c r 产品应该是i 蹦 公司的i b m l 4 1 8 。它的识别对象是印刷体的数字、英文字母及部分符号。6 0 年代 末，日立公司和富士通公司也分另岣瑞9 出各自的o c r 产品。这代产品的特点是 被识别的字符字体很少，是经过特殊设计或指定的，甚至于某些字符看上去都不 太自然。 二十世纪6 0 年代中期到7 0 年代初期的o c r 产品属于第二代。典型系统是 i 雕公司于1 9 6 5 年在“纽约世界博览会”上展出的0 氓产品一一i 删1 2 7 8 。这些 硕士学位论文 系统能识别规则的印刷体字符，也能识别部分手写字符，但这些手写字符只限于 数字和少数字母和符号。这些成果迅速得到了应用。第一个实现手写邮政编码识 别的信函自动分拣系统是由日本东芝公司研制的，两年后n e c 公司也推出了同样 的系统。在这个时期，另一些有重要意义的事件是建立了一些供字符识别研究的 标准化字符数据库，使研究人员可以很容易地评估自己的进展。 第三代0 僳产品起始于二十世纪7 0 年代中期。从这时开始，主要解决的技 术问题就是对于质量较差的文档及大字符集的识别，例如汉字的识别，高精度的 手写数字的识别等。最先投入汉字识别研究的日本东芝公司，于1 9 8 3 年发布了 其识别印刷体日本汉字的o c r 系统一一0 c r v 5 9 5 ，其识别速度为每秒7 0 1 0 0 个汉字，最高识别率达到9 9 5 9 i 。 我国在o c r 技术方面的研究工作起步较晚，在7 0 年代才开始对数字、英文 字母及符号的识别进行研究；7 0 年代末开始进行汉字识别的研究；到1 9 8 6i f - i t 字识别的研究进入个实质性阶段，取得了较大的成果，不少研究单位相继推出 了中文o c r 产品。时至今日，对印刷体汉字的i p j j , j 率最高可达到9 9 以上，可识 别宋体、黑体、楷体、仿宋体、繁体等多种字体，并且可以对多种字体、不同字 号混合排版进 氕蝴0 ；对手写体汉字的识别率最高达到7 0 以上。国家的“8 6 3 计划”对o c r 技术的研究给予了很大的资助，促使o c r 的研究取得重大进展。重 庆大学精密仪器系研制的高精度a v l 0 0 表格自动阅读系统在1 9 9 4 年第四次全国 人口普查和1 9 9 7 年第一次全国农业普查中得到大规模的成功应用，这项成果引 起了联合国和国际社会的普遍关注，受到广泛的好评。从此以后，中国的各种全 国性普查工作都将把o c r 设备作为标准的计算机数据录入设备，使我国的大规模 数据录入技术走在了世界的前列，也使我国的社会统计数据更加快速和准确。不 久清华大学自动化系建立了基于神经网络的银行支票容错系统，其识别率为 8 2 8 9 i ，误识率为0 9 i ，拒识率为1 4 8 ，识别处理速度平均为2 3 秒，这项指标 均超过国外现有支票识别系统的指标( 国外现有系统的识别率约为4 5 9 6 7 0 9 6 ，误 识率为5 9 6 1 0 ) 闷。 当前o c r 系统的目标是使计算机能处理更复杂的一般情况，能够识别没有 限制的手写体字符，但遗憾的是目前仅处于刚刚开始阶段。近年来出现的手写体 阿拉伯数字识别系统都属于第三代的o c r 系统。其中银行支票自动处理系统成为 硕e 学位论空 手写体阿拉伯数字识别系统中的热点。它的无约束手写体阿拉伯数字识别( 即没 有其它框格之类的限制，类似银行票据中的“帐号”部分，如图卜l ( b ) 所示) 是数字识别中最为困难的一部分，也是最具挑战性的课题之一。 1 3h n r 典型应用 无约束的手写数字串 图i - i 有无约束手写数宇串样图 ( 1 ) 删r 在大规模数据统计中的应用 在大规模的数据统计( 如：人口普查、成绩单录入、行业年检、财务报表录 入) 中，需要输入大量的数据，以前完全靠手工输入，耗费大量的人力和物力。 近年来使用o c r 技术大大提高了工作效率。 ( 2 ) 呱在财务、税务、会融领域应用 随着我国经济的快速发展，每天会有大量的财务、税务、支票等需要处理。 如果使用计算机进行自动化处理，无疑会节省大量的时日j 和会钱。当然，该领域 对识别的精度要求很高，因此对预处理和识别的算法要求椭艮高。 ( 3 ) r 在自胖盼拣中的应用 传统的邮件分拣主要是由人工来实现的。随着经济的发展，各种私人和商务 信件会越来越多，一些大城市每天处理的邮件高达几百万件。因此邮件的自动分 拣成为大势所趋。目前国内县市级以上邮政部门都已使用邮件分拣机，其中使用 量最大的o v c s 分拣机的o c r 拒分率为3 0 ，o c r 分拣差错率为1 1 蚪 - s 。 随着国家信息化进程的加速，手写数字识别的应用需求将越来越广泛，近几 硕士学位论文 年我国开始大力推广的“三会”工程就是 帜的典型应用。尽早建立适应中国 入书写习惯的、具有国家标准性质的手写数字样本库，研究高识另u 率、零误识 率和低拒识率的高速识别算法，将是近期内备受关注的重点课题。 1 4 研究难点 数字的类别只有十种，属于小字符集的范围，而且笔划简单，其切分和识别 问题 以乎不是很困难。但事实上，一些顶酊式结果表明，数字串的切分和数字字符 的币确识别率并不如印刷体汉字识别t e 确率高，甚至不如联杌手写体汉字识别率 高，而仅仅优于脱叽手写体汉字识别。这其中主要原因就在于： 第一，因为是无约束的，容易造成粘连、重叠、断笔的情况，这使得数字串 的切分没有了任何的辅助，切分起来就非常困难。如图l - 2 所示。 第二，数字串由连串的阿拉伯数字连续组成，只要有个数字切分销吴， 整个数字串的识别就宣告失败，所以要求要有高精度的切分算法。 第三，某些单个数字的捌以性很大，字形相差也不太大，使得准确区分某些 数字显得相当困难。 第四，单个数字虽然只有十种，而且笔划简单，但因为书写人的随意性，每 个人的书写习惯、风格都非常迥异，同一个数字因书写人不同而千差万别，甚至 同一个人因不同的写法同一数字也会大相径庭。所以说 艮难完全做到兼顾各种写 法的极高识别率的通用性数字识别系统。 第五，在实际应用中，对数字识别单字识别正确率的要求比文字苛亥0 得多。 这是因为，数字没有上下文关系，每个单字的识另0 都至关重要，而且数字识另n 常 涉及的财会、金融领域如银行票据等都是要求有非常高的识别精度的，这就为数 字的识别增加了更大困难。 固1 - 2 数字串难点 1 1 硕j 二学位论文 1 5 系统描述 在本文中，手写数字串识别系统是由s i d 采集、预处理、数字串切分、 单个字符凹凸特性的提取、分类识别五个主要步骤组成。系统描述如图1 3 下面 介绍一下各部实现的主要功能。 数字串字符图像 结果输出 图卜3 数字串识别流程图 ( 1 ) s f 州i d 采集：为了验证算法的可靠性，我们除了采用了美国国家标准 和技术研究所提供的一个国际t 通用手写体数字字符库n i s ts d l 9 唧( 样本集见 图l - 4 ) 之外，还自行采集了4 0 个人，每人2 8 个数字串的字符图像作为另一数 据库( s e l f - c o l l e c t i o nh a n d w r i t t e nn u m e r a ld a t a b a s e ，简称s i d ) 。首先 让4 0 个不同年龄、不同职业、不同学历的人用普通签字笔在我们事先准备好的 a 4 打印纸上自由书写数字串，每个人书写一页约2 8 个，采集模板见图卜5 ；然 硕士学位论文 后再将这写好的4 0 页纸i 融立扫描仪扫描成计算机能识别的图像。一般来说，扫 描仪的扫描精度与能获得的图像信息成正比，扫描精度越高，包含的信息量就越 大，但需要的存贮空间和处理时间也会相应的增加。常用的扫描精度有2 0 0 6 0 0 d p i 几种，综合各方面因素，本文选用3 0 0 d p i 的扫描精度。扫描仪选用的是 清华紫光a 6 0 0 扫描仪的真彩模式，扫描图像以j p g 格式存储。为了集中扫描， 采集时要求书写者将数字串书写在模板的方框内。扫描完成后使用图像处理软件 p h o t o s h o p 将数字串字符从扫描页面中提取出来，提取出的每个数字串图像大小 均为8 8 7 x 1 4 2 。 g 秒镪觞跫豌鲫 印细鲜形刃仰刖 r 必国叙耐彻 固1 - 5s 嘲 d ( 2 ) 预处理：在将物理数字串图像转换成计算机能识别的数字图像过程中 不可避免地存在噪声的干扰，在得到数字图像的同时也捕获了一定的噪声。由于 这些噪声的影响，对转换设备得到的数字图像进行直接处理通常不能得到满意的 结果，因此在将物理图像转换成数字图像后，应该对图像进行去噪处理。同时， 一方面是后面提取凹凸特性的需要，另一方面为了大量压缩数据减少存储量，大 大简化其后分析和处理步骤，因此在此阶段还需要对数字图像进行二值化处理。 本文算法不需要复杂的归一化、细化等处理，故预处理环节的主要任务就是去噪 和二值化，保留干净完整的二值化数字串图像。具体方法详见第二章。 ( 3 ) 凹凸特性提取：原始的数字图像由于数据量大，冗余信息量大，不能 直接进行匹配，再加每个的书写风格迥异，数字形状变化特别大，不可能有足 够的检验数据库空间来存储，从而进行直接完全匹配。因此需要将图像从维数很 硕七学位论文 高的数字图像模式空间变换到维数大大降低的特征空间，并且理论上应该选用易 于提取，最具代表性的( 即同类之间相似，异类之间区别性特别大) ，以及稳定 性好( 也就是不会因书写变化而变化) 特征。特征的选取是数字识别的关键环节， 也是研究者们一直寻找研究的重点。目前提出了很多有关数字字符有价值的特 征，诸如轮廓、投影、宽高比、点( 端点、连点、三叉点、四叉点、垂直交点、 水平交点) 、弧、连通区域、笔顺( 横、撇、竖、捺) 、笔画密度等，然而这些都 是基于字符图像的局部特征，变化性很大。故笔者经过反复观察，寻找到字符的 一种新的凹凸特征。这种特征是基于字符图像的整体特征，同一数字不同人、不 同书写其整体特征( 凹凸) 是基本一致的。 ( 4 ) 数字串的切分：连续手写数字串的不切分直接识别技术目前还仅限于 理论研究角度，其实现性以及切分的正确率都还不可取。因此本文还是采取先切 分后识另的模式。数字串的切分准确率直接影响到后面革字的识别率。故切分技 术的研究也是度成为o c r 领域的热点问题，同时也是0 c r 系统的一个瓶颈。研 究者们针对连续手写数字串中连笔、重叠、断笔等情况纷纷提出各种各样的方法， 或是对现有的方法进行不断的改进，以期达到更高的切分准确率。如基于骨架特 征的、动态规划d p 的，滴水算法( d r o p - f a l l i n g ) 、还有根据识别结果反复切分 的等等，都取得一定程度的切分准确率。我们经过对收集到的数字串特征大量研 究探讨，提出了另一种基于数字串图像凹凸特征的切分方法。该方法的优点是较 先自口的方法更加简单快速，同时还自g 提高准确率。具体算法描述详见第三章。 ( 5 ) 分类识别：当特征提取之后，就送入分类器中做最后的字符分类识别。 该环节瑚在普遍采用的是基于神经网络和模板匹配两种模式。考虑到本文提取的 特征是从字符图像的背景域出发，比较简单，而且该特征是基于字符图像的整体 特征，比那些局部特征更具代表性，因此，我们认为只需要将提取的特征值与我 们先前建立好的特征摩 进：行模板匹配即可，这样简单、速度快，不需要神经网络 的复杂口i i 练，也不会发生神经网络模式的未经过训练的测试集往往识别率很低的 情况。 硕士学位论文 1 6 本文内容及结构安排 我们的主要目标是对有噪声、无约束书写条件下的脱机手写体数字串的切 分和识别算法进行些有益的探讨性研究，以期提高其准确性和可靠性。为此忽 略了票据识别其它方面如倾斜矫正、版面分析、印章提取，数字串的提取等，而 是直接对已经提取出来的数字串进行研究。 本文在内容上的总体安排为六章。 第一章主要是对o c r 和手写数字识别作简单回顾；o c r 及手写数字识别的历 史与现状；m r 的典型应用和研究难度；数字串识别系统的整体描述以及本文 的研究目标和研究重点。 第二章主要是预处理方法研究分析以及凹凸特性的提取。因本文创新性地 采取了基于手写数字串的凹凸特性的切分和识别方法，这是基于数字串字符的 整体特性，因此在这个环节无需细化、连通域标记等复杂的处理方法，只需要 简单地去噪、二值化即可。同时这章也详细介绍了本文字符凹凸特性提取的具 体过程。 第三章：首先总结了目前数字串切分的三类方法以及代表性算法，并详细 分析了各个方法的优劣性。接着提出本文基于数字串字符图像凹凸特性的切分 方法。 第四章：在介绍了目自口广为流行的神经网络数字识别方法之后，提出本文 的基于单个数字图像不同凹凸特性的模板匹配识别方法。同时，还将该方法扩 展到2 6 个大写英文字母的识别。 第五章：通过对n i s ts d l 9 和s i 州i d 图像数据库进行了实验，给出了相关 实验数据，并和其它具有代表性的相关算法进行了比较，分析出可靠的实验结 论。另外本章还介绍了演示系统的实验方法和基本界面。 第六章：对研究过程中遇到的问题进行了总结，并提出了后期研究工作中 应该改进的地方以及对以后的展望。 硕士学位论文 第二章预处理及特征提取 2 1 预处理 预处理对于个良好的图像处理系统是至关重要的，甚至可以说是必不可 少的环节。对于个完整的银行票据处理系统而言，其预处理包括很多个部分， 如去噪、二值化、平滑、归一化、细化、去边框、去各类印章、去票据底纹、 倾斜矫正、版面分析、识别要素的提取( 包括帐号、大写金额、小写金额、日 期等) 等。但由于我们着重是对票据识别中的类似手写帐号这种无约束的手写 体数字串进行研究，其研究目的也只是期望能对目前手写体数字串的切分和识 别算法研究作一点有益的探索，并不是为了开发一个完整的商业化票据识别系 统，因此我们在采集数据时有意地让书写入直接书写个个数字串，这样就简 化了部分细节操作( 如倾斜矫正、去印章、去边框、去底纹等) ，有利于我们 直接提取出有效的数字串进行实验。又因为我付 的算法是提取的字符图像的整 体特征，所以我们的预处理不需要复杂的细化、曲线拟合等处理，只需要简单 的去噪、二值化即可。 2 1 1 去嗓 噪声可以理解为妨碍人的视觉器官或系统传感器对所接收图像源信息进 行理解或分析的各种因烈姗。噪声对于图像的预处理非常重要，它会影响图像 处理的输入、采集、处理的各个环节和输出结果的全过程。特别是图像的输入、 采集的噪声是十分关键的问题。若输入不良伴有较大的噪声，必然严重影响处 理的全过程以至输出结果。噪声的去除已经成为图像处理中极为重要的步骤， 在我们的手写数字串识别和切分系统中，其实验对象之一n i s ts d l 9 数据库中 的图像已做了去噪处理，而另一个我们自行采集的数据库s 刖i d 就不可避免地 会产生些噪声。一是由于纸张材质引起的色彩的部分失真，主要表现为扫描 后的图像原本是白色的背景色发生的变化，如图争l 所示：二是由于在扫描时 纸张没有铺平、纸张匕存在杂质或信号干扰等造成扫描后的图像中存在斑点、 硕士学位论文 断点等噪声，如图2 - 2 所示。因此经过转换设备得到的图像是不能直接进行处 理分析的，应该首先对扫描后的图像进行去噪处理。 图2 - 1 色彩失真 删 图2 - 2 斑点和断点噪声 去噪的方法很多，最常用的是平滑滤波去噪法，其主要思想为在图像空间 中借助模板对图像进行领域操作，用平均运算法去除突然变化的点从而滤掉一 定的噪声。输出图像的每一个像素的取值都是根据模板对输入像素相应领域内 的像素值进行计算得到的 h i 。例如，较为经典的中值滤波算法就是将一个n x n 大小的模板依次移动到图像的各个像素上，用模板中所有像素灰度值的中间值 取代当前像素的灰度值。图2 3 是3x3 大小的中值滤波模板。图中e 点像素 的灰度值等于周围3 x 3 领域范围内a i 各像素灰度值的中值( 对于奇数个元 素，中值是指按大小排序后，中间的数值；对于偶数个元素，中值是指排亭后 中间两个元素灰度值的平均值) 。 abc d ef g hi 硕七学位论文 t l a b7 0 提供了多种平滑滤波函数旧，如线性滤波函数i 珊f i l t e r ( ) 、 均值滤波函数f i l t e r 2 ( ) 、中值滤波函数m e d f i l t 20 等。图2 4 是图像做中 值滤波后的结果，其模板大小分别为3 3 和5 5 。比较图2 - 4 ( a ) 和2 - 4 ( b ) 可知，模板越大，噪声去得更干净，但其滤波后图像效果越模糊，而且还会丢 失掉更多的笔划边缘，因此不同的噪声应选用不同的模板。 3 x 3 中值滤波后的图像 2 1 2 二值化 5 x 5 中值黼的图像 图纠中值滤波 所谓二值化( i m a g eb i n a r y ) ，就是把其它类型的图像( 如r g b 图像、灰 度图像、索引图像等) 处理成二值图像( 指其像素的取值只有两种：“1 ”或0 ) 的过程【l o l 。它对于图像分析之所以重要，就在于二值图像中，图像的各种目标 及其特征比其他类型更为明显突出，更易于分析；再加上本文凹凸特性提取的 对象必须是二值图像，而n i s t $ d 1 9 、s 刑i d 数据库中的图像大多数是r g b 图 像或次度图像，所以二值化在预处理中是必不可少的。 二值化的原理其实很简单，如公式争l 所示，其中值为1 表示二值化后图 像的i ； 景部分，值为0 表示背景部分，t 叫做二值化阈值( t h r e s h o l d ) 。由公 式可以看出，二值化的好坏关键就在于阈值的选择是否合适，为此产生了很多 经典的阈值选择方法，如整体阈值法( 包括直方图法、o t s u 法叩1 、熵澍“噜) 、 局部阈值法( 包括k a m e l - - z h a o o 算澍1 5 】等) 、动态阈值法( 包括b e r n s e n 算澍i q 等) 。 慌f ( i 嚣0 j 燃之r t c 船， 【，_ ，) ，( f ，_ ，) ( a ) h 水平v 瓤( c ) c 圈( c o l 左凹( e ) r 右凹 图编码的5 种码宇类型 提取出凹凸特性( 类似图2 - 7 ( c ) ) 之后，依据人们从上到下，从左至右的书 掺一 ， 符石踢：l| 够：一 占脚变 形6 槲 细 f d 图 硕七学位论文 写习惯，对每个标记区域按该区域类型( 圈c 型、左凹l 型、右凹r 型) 分别 采用对应的方法与其邻域进行合并，获得其智顷序列号( 1 、2 、3 ) 和笔划 类型编码( 按图4 8 的五种码字类型) ，最后将所有笔划的编码按序列号依次排 列即完成訇i 暖的编码过程。其中为了保证圈的完整性，当标记区域为圈或邻域为 圈时，应将圈区域所在的全部前景边一同提取为一个笔划；同对为了不重复提取 相同前景边，应只提取没有被其它区域提取过的前景边。具体步骤如下。 s t e p1 ：初始化：( m ) 一所有区域标记字符；a 一空字符。 s t e p 2 ：若f m l 全为空，转步骤8 ：否则，a 一( m ) 第一个不为空的成员。 s t e p3 ：判断a 是否含有c ，若是，将a 区域所有前景边全部提取作为一 个笔划，转步骤6 ；否则( e ) _ a 区域所有前景边。 s t e p 4 ：判断 e ) 中每个成员所在区域标记中是否为空或含字符，若是， 删除所有这样的成员。 s 1 曰5 ：判断( e ) 是否为空集，若是，转步骤7 ；否，将( e ) 中所有成员 提取出来作为个笔划，同时 e ) 一空集。 s t e p6 ；标记序列号和笔划编码。 汛p 7 ：该( m ) 成员一空字符；转步骤2 。 s t e p8 ：判断a 是否为空，若是，直接输出字杼z ；否，将所有笔划编码 按序列号排列成字符串输出。 下面我们将以数字字符“9 ”为例( 如图4 - 9 ( a ) 所示) ，分别以图片( 如图 4 - 9 ( e ) 所示) 和流程图( 4 q 0 ( a ) 4 1 0 ( c ) ) 形式详细叙述了其鞫皈编码的 全音瞄立程，它的最终编码为c v 。 7 穸尹尹”贸三 ( c )仰( e ) 图4 - - 9 数字9 的鞫膨寅码 硕七学位论文 初始化：集合l t f f c l ，l 1 ：a - ” 趸集合m 是否为空彳 a - c 1 入a 翩眙有c 彳 将边e l 提取出来并标 上序列号及编码为l c 清除c 1 ，口f l 1 入集合m 是否为空7 彳j 瓮输出展终编码 li 4 0 硕士学位论文 4 2 3 分类识别处理 字符图像的特征提取之后，其识别重点就是分类器的设计。它是模式识别 中最为关键的问题。分类器的合理性和分类效果的好坏直接关系到字符识别的速 度与准确率，高性能的分类器有助于提高识别系统的整体性能。目前分类器的类 型有很多，根据不同的模式特征、不同的判别决策，可将常用的分类器分为六大 多少7 j ：模板匹配法、统计决策法、句法结构法、模糊判决法、逻辑推理法和神经 网络法，并依次构造出相应的分类裂5 8 1 。它们各自都有优缺点【5 9 1 ，如模板匹配法 的优点就在于原理简单，易于实现，但其缺点就是需要构造大量的匹配模板造成 识别率低下；句法结构法虽然能够反映出模式的结构特征，对模式结构的畸变也 不敏感，非常适合印刷体字符的识别，但其基元的抽取较为困难，而且抗噪干扰 能力较弱，因此限制了其使用范围：模糊判决法往往能反映出字符的主要特征， 从而允许有相当程度的干扰与畸变，但建立准确合理的隶属度函数是非常困难 的，故l h ，也限制了它的应用；神经网络法因其具有自动学习和记忆的功能而备受 现在研究者们的青绦，广泛应用于图像处理与模式识别之中，在本章第一节中我 们已简单地介绍了它的原理和方法。本文根据提取的凹凸特性设计出一种新的模 板匹配法：字符串匹配法。其原理类似于模板匹配法，也是通过逐个比较未知样 本与模板( 即匹配) ，不同的是模板匹配中的模板一般是用二维的数字点阵来描 述，而我们用的是字符串，为此我们还引入了正则表达式。 4 2 3 1 正则表达式 手写数字识别难度特别大就在于其变体很多( 也就说由于书写人不同的书 写风格而造成同一个数字有两种及两种以上的书写形式) 。如图4 - 1 0 虽然数寄掣9 ” 有两种写法，但从其图像正下方的笔j i 目鳊码可以看出是一致的，这就初步证明， 本文的编码方法对数字的变体具有一定程度的抗变作用。但对于图4 - 1 1 同一数 字“3 ”的四种写法却对应了4 种不同的编码，这就意味着如果直接按照数字的 编码进行匹配识别的话，部分数字的变体就有可能被误识或拒识，这样识别率必 然将会很低。所以本文引入了正则表达式来统一每个数字包括其变体的编码模 式。 硕：b 学位论文 q 9 j ，只 鸯鬟墨荔 l h l札也( c ) l c 也油i h 删 图 1 1 数字“3 ”自9 ；自码 正则表达式r e ( p ( e g u l a re x p r e s s i o n ) ，起源于1 9 5 6 年，位叫s t e p h e nk l e e n e 的数学家在m c c u l l o c h 和p i t s 早期工作的基础上发表了一篇标题为“神经网事 件的表示法”的论文，后来u n i x 的主要发明人k e nt h o m p s o n 又将其作为一个 实用程序第一次贼j 到u n i x 中的g e d 编辑器。r e 描述了一种字符串匹配模式， 可以用来检查一个字符串是否含有某种子串或将匹配的子串做替换或从某个串 中取出符合某个条件的子串等。它是种由普通字符( 如字符a 到z ) 以及特殊 字符( 也称元字符m e t a c h a m a e 培) 组成的文字模式，它只需作为个匹配模板， 将某个字符模式与所搜索的字符串进行匹配即硎删。 表4 1 列出了我们经过大量实验总结的数字o 9 笔顺编码的正则表达式。 o 叫r i h v c 5 r r j l lz6￥c f 鼯 2l h i l c l 嘲iu l 7l 3 r l e hj c h l l c i c h 8 l c c 4rl h i c l v l l h v l0 i v9 h c v h 1 c l 其中】下则表达式表中符号“口”为字符集合，匹配所包含的任意个字符。 硕士学位论文 例如 a b e l 可以匹配“p l a i n ”中的a ；符号叩为“或”操作，例如z l f o o d 能匹配“z ”或“f o o d ”。 4 2 3 2 分类识别 有了各数字字符的正则表达式表，其识别就变得非常简单。只需将待识别的 数字字符的訇颐编码字符串与表4 - 1 的十个正则表达式分别进行匹配，匹配成功 的表达式所对应的数字就是该字符的识别结果。由于j f 则表达式涵盖了数字的多 种变体情况，因而识别率很高。 例如图4 - 1 1 四种“3 ”的常g - t - 写体写法，先分别提取它们的鞫噘编码字符 串分别为