（信号与信息处理专业论文）手写体数字识别中的特征提取和特征选择研究.pdf

手写体数字识别中的特征提取和特征选择研究 摘要 手写数字识别是文字识别中的一个重要的研究课题，数字的类别 只有十种，笔划又简单，其识别问题似乎不是很困难。但事实上，一 些测试结果表明，数字的正确识别率并不如印刷体汉字识别正确率 高，甚至也不如联机手写体汉字识别率高，而只仅仅优于脱机手写体 汉字识别。手写数字识别的难度在于其变体极多，而且对数字识别单 字识别正确率的要求要比文字要苛刻得多。目前对各类字体的数字识 别特别是脱机手写数字识别仍然处在发展阶段，识别效果仍然不够理 想。因此，研究简单高效的手写数字识别依然是一个重要的研究方向。 本文主要对手写体数字识别的关键问题特征提取和特征选 择进行了探讨和实验。本文的工作主要有以下几个方面： 1 在研究了多种手写数字特征的基础上，本文提取了轮廓特征、 笔划密度特征、粗网格特征、重心及重心矩特征、首个黑点位置特征、 投影特征及傅立叶变换特征等七种手写数字的结构和统计特征。 2 从多种特征选择方法中，采用了类内类间比、k w 检验及熵函 数这三种特征选择方法对特征进行了选择。 3 通过大量实验，对手写体数字的特征降维问题进行了分析研 究。 4 建立了一个基于b p 神经网络的手写体数字识别系统，将原始特 征和选择后的特征经过该b p 神经网络检验，取得了较好的系统性能， 从而证明上面提出的方法是可行的。 关键词：手写数字识别b p 算法神经网络特征提取特征选择 a b s t r a c t h a n d 而t i n gd i g i t sr e c o g n i t i o ni sa ni m p o r t a mr c s r c hs u b j e c ti n c h a r a c t e rr e c o g n i t i o n t h ed i 衔c u l t i 镐o fh 粕d w r i t i n gd i 西t sr e c o g n i t i o n a r ed u et oi t sv a d o u sa i l 锄。叩h o s i s a tp r e s e n t ，t h ed i g i t sr e c o g n i t i o n so f d i 毹r 印tl e t t 晌m s ，e s p e c i a l l yt h eo m i n eh 龃d w r i t i n gd i g i t sr e c o g n i t i o n ， a r cs t i l lu n d c rd e v e l 叩m e n t ，龃dt 1 1 e r e c o g i l i t i o ne m 娥i sn o ti d e a l t h e r e f o r e ，i ti ss t i l lav e r yi i n p o n a n tr e s e a r c hd i r e c t i o nt os t u d ys i m p l e a n dh i g h e 衔c i e n th 锄d 、r i t i n gd i g i t sn 瑚g n i t i o n t h et h e s i s p r o b e s i n t ot h e k e yi s s u e o fh a i l d 、州t i n g d i 百t s r e c o g n i t i o n f e a t i l r ee x m l c t i o n 锄df e a t u r es e l e c t i o n t h em a i nw o r ko f t h e 也e s i si n c l u d e st h ef o l l o w i n g a s p e c t s ： 1 b a s e do nt h er e s e a r c h 嚣o nt h ef e a t u r e so fs e 、r e m lh 锄d 、州t i n g d i g i t s ，t h em e s i se x 仃a c t s t 1 1 es t r u c t l l r e s 卸ds t a t i s t i cf 细r c so fs e v c n k i n d so fh a n d 、槲t i n gd i 百t s ，i e 叫t l i n ef e a t u r e ，s 仃o k ed e n s i t ) rf c a t u r e ， w i d e 鲥df e a t u r c ，b 叫c e n t c ra n db a r y c e m e rd i s t a n c ef e a t u r c ，t h ef i r s t b l a c kp o i n tp o s j t i o nf e a t u r e ，p r o j e c tf 孤r e ，a n df o 嘶e rs w i t c hf e a t u r e 2 f m md i f f b r c n tf 妇t i l r es e l e c t i o nm c t h o d s ，t i l i st h e s i sa d o p t st h r e e m c t h o d s i n n c r加do u t e r a i l a l o g y ， k - wc h e c l 【i n ga n d e 劬r o p y m n c t i o n t 0s e l e c tt l l ef - c a t u r e s 3 1 1 l i sm e s i s 锄a l y z e st h ef 龃t u r ed i m e n s i o nd e c r e a s ei s s u eo ft h e h a n d w t i i 培d i g i t st h r o u g hal o to fe x p 耐m e n t s 4 t h i sm e s i se s t a b l i s h e sah a n d 、) i r t i n gd i 百tr e c o 印i t i o ns y s t e m b a s e do nb pn e u r a ln e t w o r k t h eo r i g i n a lf c a t u l c sa n ds e l e c t e df c a t u r c s b o t hh a v eg o o ds y s t e m a t i cp e r f o 曲锄c ea f i c rc h c c k e dm r o u 曲b pn e i l m l n e t v y o f i ( ，w h i c hp m v e st h ea b o v cm e n t i o n e dm e t h o df e a s i b l e k e yw o i s ：h a n d w r i t i n gd i g i t sr e c o g i l i t i o n b pa l g o r i t h m sn e u r a ln e t 、，帕r k f e a t u r ce x t r a c t i o nf e a t u r cs e l e c t i o n 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示了谢意。 萎爻薹篓? 三錾窆 处，本人承担一切相关责任。 日期：兰竺2 ：! ：! ! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位 本人签名 导师签名 适用本授权书。 r 期： 日期： 2 矿p 7 弓弓口 印7 ； 口 1 1 模式识别 第一章引言 本文研究的脱机手写数字识别是模式识别的一个分支，因此先对模式识别作 一个简单的讨论。什么是模式和模式识别呢? 从广义地说，存在于时间和空间中 可观察的事物，具有时间或空间分布的信息，如果可以区别它们是否相同或相似， 都可以称之为模式；狭义地说，模式是通过对具体的个别事物进行观测所得到的 具有时间和空间分布的信息；把模式所属的类别或同一类中模式的总体称为模式 类( 或简称为类) 。而“模式识别”则是用计算机实现人对各种事物或现象的分析， 描述，判断，识别，在某些一定量度或观测基础上把待识模式划分到各自的模式 类中去。回顾模式识别的发展历史，模式识别诞生于二十世纪二十年代，随着四 十年代计算机的出现，五十年代人工智能的兴起，六十年代初迅速发展成为一门 学科。它所研究的理论和方法在很多科学和技术领域中得到了广泛的重视，推动 了人工智能系统的发展，扩大了计算机应用的可能性，其中也包括了文字识别系 统的迅速发展。 模式识别的研究主要集中在两方面，即研究生物体( 包括人) 是如何感知对象 的，以及在给定的任务下，如何用计算机实现模式识别的理论和方法。前者是生 理学家、心理学家、生物学家、神经生理学家的研究内容，属于认知科学的范畴： 后者通过数学家、信息学专家和计算机科学工作者近几十年来的努力，已经取得 了系统的研究成果。 1 2 手写数字识别的综述 1 2 1 手写数字识别的研究背景和研究意义 字符识别处理的信息可分为两大类：一类是文字信息，处理的主要是用各国 家、各民族的文字( 如：汉字，英文等) 书写或印刷的文本信息，目前在印刷体 和联机手写方面技术已趋向成熟，并推出了很多应用系统；另一类是数据信息， 主要是由阿拉伯数字及少量特殊符号组成的各种编号和统计数据，如：邮政编码、 统计报表、财务报表、银行票据等等，处理这类信息的核心技术是手写数字识别。 j e 基鲤皇盍堂亟主堂僮监塞壬星佳煎主迟别虫曲挂延量取塑挂延造捶硒蕴 这几年来我国开始大力推广的“三金”工程在很大程度上要依赖数据信息的输入， 如果能通过手写数字识别技术实现信息的自动录入，无疑会促进这一事业的进 展。因此，手写数字的识别研究有着重大的现实意义，一旦研究成功并投入应用， 将产生巨大的社会和经济效益。 手写数字识别作为模式识别领域的一个重要问题，也有着重要的理论价值： 1 阿拉伯数字是唯一的被世界各国通用的符号，对手写数字识别的研究基 本上与文化背景无关，这样就为各国，各地区的研究工作者提供了一个施展才智 的大舞台。在这一领域大家可以探讨，比较各种研究方法。 2 由于数字识别的类别数较小，有助于做深入分析及验证一些新的理论。 这方面最明显的例子就是人工神经网络( a m o 一相当一部分的a n n 模型和算 法都以手写数字识别作为具体的实验平台，验证理论的有效性，评价各种方法的 优缺点。 3 尽管人们对手写数字的识别已从事了很长时间的研究，并已取得了很多 成果，但到目前为止机器的识别本领还无法与人的认知能力相比，这仍是一个有 难度的问题。 4 手写数字的识别方法很容易推广到其它一些相关问题，一个直接的应用 是对英文这样的拼音文字的识别。事实上，很多学者就是把数字和英文字母的识 别放在一块儿研究的。 1 2 2 手写数字识别的难点 数字的类别只有十种，笔划又简单，其识别问题似乎不是很困难。但事实上， 一些测试结果表明，数字的正确识别率并不如印刷体汉字识别正确率高，甚至也 不如联机手写体汉字识别率高，而只仅仅优于脱机手写体汉字识别。这其中主要 原因是：第一，数字笔划简单而平滑，字形相差不大，使得准确区分某些数字相 当困难；第二，数字虽然只有十种，而且笔划简单，但同一数字写法千差万别， 全世界各个国家各个地区的人都用，其书写上带有明显的区域特性，很难完全做 到兼顾世界各种写法的极高识别率的通用性数字识别系统。另外，在实际应用中， 对数字识别单字识别正确率的要求要比文字要苛刻得多。这是因为，数字没有上 下文关系，每个单字的识别都事关重要，而且数字识别经常涉及的财会、金融领 域，其严格性更是不言而喻的。因此，用户的要求不是单纯的高正确率，更重要 的是极低的、千分之一甚至万分之一以下的误识率。此外，大批量数据处理对系 统速度又有相当的要求，许多理论上很完美但速度过低的方法是行不通的。因此， 研究高性能的手写数字识别算法是一个有相当的挑战性的任务。 拙基邮电太堂亟堂僮i 金塞 壬曼佳熬主迟型生趋挂延埕塑塑挂延蠡捶班究 1 2 3 学习和测试样本库的选择 正如前一部分提到的，手写数字的写法带有明显的地区性和民族性，因而选 择一个可供系统训练和测试使用的样本库是手写数字识别研究的重要基础之一， 对识别系统的性能也有重要的影响。研究者对所需的样本库有两种选择：一是自 己根据需要建立专门的样本库，二是选用其它机构做好的现成的样本库。前者的 优点是帖近自己的应用，缺点也是明显的：要费相当的精力且代表性很难保证， 与其它人的结果不好比较。另一种选择是使用有权威性的通用样本库。目前，比 较有代表性的、样本数量较大的手写数字样本库有：( 1 ) n i s t 数据库，由美国国 家标准与技术局收集；( 2 ) c e d a r 数据库，是由纽约州立大学b u 咖。分校计算机 科学系文本分析与识别中完成的邮政编码的样本库；( 3 ) e t l 数据库，由日本电工 技术研究所收集；( 4 ) 哪数据库，由日本邮电通信政策研究所收集。本文中使 用的是美国邮政服务数据库u s p s 中的手写体阿拉伯数字数据库作为训练样本 集。 1 2 4 识别系统性能的评价 作为一个识别系统，我们最终要用某些参数来评价其性能的高低，手写数字 识别也不例外。评价的指标除了借用一般文字识别里的通常做法外，还要根据数 字识别的特点进行修改和补充。 对一个手写数字识别系统，可以用三方面的指标表征系统的性能： 正确识别率a = 正确识别样本数全部样本数xl o o 替代率( 误识率) s = 误识样本数全部样本数1 0 0 拒识率r = 拒识样本数全部样本数l o o 三者的关系是：a + s + r = 1 0 0 数字识别的应用中，人们往往很关心的一个指标是“识别精度”，即：在所有 识别的字符中，除去拒识字符，正确识别的比例有多大，我们定义如下： 识别精度p = 三：1 0 0 t 以+ 6 j 一个理想的系统应是r 、s 尽量小，而p 、a 尽可能大。而在一个实际系统中，s 、 r 是相互制约的，拒识率r 的提高总伴随着误识率s 的下降，与此同时识别率a 和 识别精度p 的提高。因此，在评价手写数字识别系统系统时，我们必须综合考虑 这几个指标。另外，由于手写数字的书写风格、工整程度可以有相当大的差别， 因此必须弄清一个指标在怎样的样本集合下获得的。 j e 立蛭皇盍堂亟堂焦论塞壬兰佳熬主迟型生的挂堑埕塑塑撞延选显硒宜 以上多种因素使得不同系统的性能很难做绝对比较，有学者提出划，手写 数字识别研究的较高水平是：对自由书写的数字，在不拒识时达到9 6 以上的识 别率；在拒识少于1 5 的样本时，误识率能降到0 1 以下。 1 2 5 手写数字的识别方法 手写数字识别在学科上属于模式识别和人工智能的范畴。在过去的四十年 中，人们想出了很多办法获取手写字符的关键特征。这些手段分两大类：全局分 析和结构分析。对前者，我们可以使用模板匹配、象素密度、矩、特征点、数学 变换等技术。这类的特征常常和统计分类方法一起使用。对后者，多半需要从字 符的轮廓或骨架上提取字符形状的基本特征，包括：圈、端点、节点、弧、突起、 凹陷、笔画等等。与这些结构特征配合使用的往往是句法的分类方法。 多年的研究实践表明，对于完全没有限制的手写数字，几乎可以肯定：没有 一种简单的方案能达到很高的识别率和识别精度。因此，最近这方面的努力向着 更为成熟、复杂、综合的方向发展。一方面，研究工作者努力把新的知识运用到 预处理，特征提取，分类当中，如：神经网络、数学形态学等。作者认为，在手 写数字识别的研究中，神经网络技术和多种方法的综合是值得重视的方向。 1 2 6 基于手写数字识别的典型应用 手写数字识别有着极为广泛的应用前景，这也正是它受到世界各国的研究工 作者重视的一个主要原因。下面我们将介绍以手写数字识别技术为基础的典型应 用。 1 、手写数字识别在大规模数据统计中的应用： 在大规模的数据统计( 如：行业年检、人口普查等) 中，需要输入大量的数据， 以前完全要手工输入，则需要耗费大量的人力和物力。近年来在这类工作中采用 o c r 技术已成为一种趋势。 因为在这种应用中，数据的录入是集中组织的，所以往往可以通过专门设计 表格和对书写施加限制以便于机器的自动识别。目前国内的大多数实用系统都要 求用户按指定规范在方格内填写。另外，这些系统往往采用合适的用户界面对识 别结果做全面的检查，最终保证结果正确无误。可以看出，这是一类相对容易的 应用，对识别核心算法的要求比较低，是目前国内很多单位应用开发的热点。 2 、手写数字识别在财务、税务、金融领域中的应用： 财务、税务、金融是手写数字识别大有可为的又一领域。随着我国经济的迅 速发展，每天等待处理的财务、税务报表、支票、付款单等越来越多。如果能把 j e 塞整皇盔堂亟堂僮j 金塞壬量住熬芏迟型主笪拄延埕取塑赞延选捏班究 它们用计算机自动处理，无疑可以节约大量的时间、金钱和劳力。与上面提到的 统计报表处理相比，在这个领域的应用难度更大，原因有：1 1 对识别的精度要求 更高；2 ) 处理的表格往往不止一种，一个系统应能智能地同时处理若干种表格； 3 ) 由于处理贯穿于整个日常工作之中，书写应尽量按一般习惯( 如：不对书写者 的写法做限定，书写时允许写连续的字串，而不是在固定的方格内书写) ，这样 对识别及预处理的核心算法要求也提高了。 3 、手写数字识别在邮件分拣中的应用： 随着人们生活水平的提高，经济活动的发展，通信联系的需求使信函的互换 量大幅度增加，我国函件业务量也在不断增长，预计到2 0 0 0 年，一些大城市的中 心邮局每天处理量将高达几百万件，业务量的急剧上升使得邮件的分拣自动化成 为大势所趋。在邮件的自动分拣中，手写数字识别往往与光学条码识别，人工辅 助识别等手段相结合，完成邮政编码的阅读。目前使用量最大的o v c s 分拣机的 性能指标：o c r 拒分率3 0 ，o c r 分拣差错率i 1 。 1 2 7 手写数字识别技术展望 随着国家信息化进程的加速，手写数字识别的应用需求将越来越广泛，因此 应当加强这方面的研究工作。作者认为，应用系统的性能的关键与瓶颈仍然在于 手写数字识别核心算法性能上，最终目标是研究零误识率和低拒识率的高速识别 算法。此外，尽早建立反映中国人书写习惯的、具有国家标准性质的手写数字样 本库也是当务之急。 1 3 本文的讨论内容和重点 脱机手写数字的识别在很多场合都有着实际的应用，目前仍然是一个值得重 点研究的方向。本文通过分析手写数字的特点，重点研究了脱机手写数字基于骨 架和基于外轮廓的不变特征，提取了数字的粗网格特征，笔划密度特征，外轮廓 特征，投影特征，重心及重心矩特征，首个黑点位置特征及傅立叶特征等几个特 征，并利用类内类间比，k w 检验，基于熵这三种方法验证了所提取特征的有效 性，选择了可靠性高的特征，并采用单级b p 神经网络，验证了所提取特征的分 类能力。 2 1 特征提取概述 第二章特征提取 在整个光学字符识别技术( 0 p 石c a lc i l 心蛾c r r e c o 鲥t i o n ，简称o c r ) 中， 最为困难的就是脱机手写字符的识别。到目前为止，尽管人们在脱机手写英文、 汉字识别的研究中已取得很多可喜的成就，但距真正意义上的实用还有一定的距 离。手写数字识别在o c r 的研究和发展中扮演了一个非常重要的角色，手写数 字识别有很多潜在的应用，比如说银行，邮局，税务和其他多种的手写形式。近 年来，许多方法论也被发表了。经过多年的研究，研究工作者已经开始把它向各 种实际应用推广。尽管如此，因为手写字符具有多样性的字体，所以，为了增加 识别的精度，对研究者来说，在这个方面还有机会以发展出新的方法。现在有许 多种方法可以改进识别的性能。一种方法是改进分类器的性能。另一种方法是寻 找新的特征提取的方法。本论文主要的工作集中在了特征提取和特征选择上。 模式特征对于分类是十分重要的，数字识别的关键在于能否找出有效的特 征，使得选取的特征具有可分辨性、可靠性、独立性和特征数量少。具体来说， 特征的可分辨性是指对属于不同类别的样本，特征应取相对差别比较大的值，这 样不同类别的样本才能区分的开；特征的可靠性是指对属于同一类别的样本，特 征应具有稳定性。这样同一类别的样本才可以判别为同一类别而不至于误判；特 征的独立性是指选择出来的不同特征之间应该互不相关，这样才能减少信息的冗 余性；特征的数量要少是指特征越少越容易满足前面的三个原则，处理速度也会 相应提高。模式识别系统的复杂度会随着特征量的增加而迅速增大。更重要的是， 训练分类器和判别一个分类器好坏所需要的数据量也会随着所用特征量的数目 呈指数增长。因此，在选择特征时要遵循以上四个原则，选择出最合适识别系统 的特征集。在适宜的情况下，都可以作为基本特征用于实际的识别系统。 下面给出一些相关定义： ( 1 ) 原始特征：在模式采集过程中形成的样本诸测量值称为原始特征。原 始特征的数目，对于给定的问题，就是其模式空间的维数r 。在一般情况下，模 式空间是高维的，这意味着r 一般很大，但是r 还是有限值。在大多数情况下， 不能直接对原始特征进行分类器设计。一方面因为模式空间的维数很高，不适宜 进行分类器设计。另一个重要的原因是原始特征描述常常不能直接反映对象的本 质。 j b 塞整皇太堂亟堂焦论塞壬兰住熬主迟型生殴挂堑埕取塑挂延选攫砑冠 ( 2 ) 特征提取：通过映射或变换的方法，把模式空间的高维特征变成特征 空间的低维特征，即用由较多的原始特征映射得到的较少的新特征来描述样本， 这个过程称为特征提取。特征空间的维数用d 表示，一般情况有d “d 。特征提 取实现了维数压缩，但是应该保持样本属性的不变，并且更具有代表性，更能反 映本质。为此，特征提取的过程要具有某些约束条件。在广义上，特征提取就是 给定约束条件下的某种变换t ，实现模式空间e r 到特征空间e d 的映射，即 t ：e rje d 又称t 为特征提取器 在模式识别过程中，常常要求模式的相似性变换、旋转变换和平移变换，因 此，提取对于这些变换具有不变性质的量作为特征是很重要的。为了达到这个目 的，对上式中的变换t 要增加更严格的限制。由于各类正交变换有与此相适应 的某些良好性质，因此被有效的应用于特征提取中。 ( 3 ) 特征选择：从一个特征集中挑选出最有利于分类的特征子集的过程称 为特征选择。经过特征选择以后，特征空间的维数也被压缩了。为了选择出最有 影响的特征，最简单的方法是利用专家的知识和经验，最严格的方法是在给定约 束条件下通过数学方法进行筛选。特征提取和特征选择，作为两个过程，它们的 先后次序并不是固定不变的。在处理实际问题时，可以根据具体情况决定先进行 哪一个过程。 。 这篇论文的重点就是进行特征提取和选择。之所以要进行特征选择和提取， 一个显然的理由是，在很多情况下，测量空间的维数很高( 比如，一个5 1 2 x 5 1 2 灰度阵列图像就相当于5 1 2 ) ( 5 1 2 维测量空间中的一个点) ，这样是不能直接在测量 空间中进行分类器设计的，更重要的是这样一种描述并不能直接反映对象的本 质，因此需要把图像从测量空间变换到维数大大减少的特征空间，被研究的图像 或现象在这个特征空间中就由一个特征向量来表示。以本文研究的脱机手写数字 识别来说，如果直接把预处理后的数据作为神经网络的输入，则数据量过大；同 时由于手写字体的多样化以及图像本身和预处理过程中附带了某些干扰的影响， 因而不仅网络训练时间长，而且由于图像数据随机分布，训练出的网络也不够强 壮。而特征提取的目的就是从分析数字的拓扑结构入手，把它们的某些结构特征 提取出来，使数字的位移、大小变化、字形畸变等干扰相对减小，而把那些反映 数字特征的关键信息提供给神经网络，这样就等于间接地增加了网络的容错能 力，降低误识率和拒识率；而且通过特征提取，数据量也大大减少，相应地，网 络规模也减小了，有利于减少运算时间。可见，为了有效地进行数字识别，特征 提取是必要的。 由此可见，特征提取与选择的基本任务是研究如何从众多特征中求出那些对 韭塞塑皇太堂亟堂焦逾塞壬星佳熬呈迟型虫鲍挂堑握题型挂堑丝竖硒塞 分类识别最有效的特征，进而实现特征空间维数的压缩。在一个较完善的模式识 别系统中，特征提取与选择技术通常介于对象特征数据采集和分类识别两个环节 中间，所抽取与选择特征的优劣，强烈的影响着分类器的设计和性能。在样本数 目不是很多的情况下，用很多特征进行分类器设计，无论从计算复杂程度还是分 类器性能来看都是不合适的，因此，研究如何把高维特征空间压缩到低维特征空 间，以便有效的设计分类器就成为一个重要的问题，这也是模式识别中的一个关 键问题。 特征提取方法的选择是影响识别率的一个至关重要的因素。必须指出的是， 对于不同的识别问题和不同的样本数据，使用不同的特征提取方法的适应性差别 很大，也就是说，一种特征提取方法对一个问题和数据很奏效对另一个问题或数 据可能失效。一个解决的办法是寻找不同的数据的共同特征，或称不变量。另一 方面，对于一个有限的训练数据集，如果使用的是统计分类器，特征集必须保持 在一个合理小的数量内。就数字识别来说，在实际过程中，如何选择若干种特征 提取的方法取决于识别的用途。我们必须考虑到待识别的数字是否有固定的方向 和大小，是印刷体还是手写体，是否存在不同的书写风格，是否有缺损，程度如 何。这些将有利于缩小特征提取选择的难度和提高识别率。此外，虽然特征提取 是一个好的字符识别系统的重要组成部分，但是，对于一个识别系统，为了达到 较佳的结果，其他的步骤，如二值化，归一化等也需要优化处理，并且这些处理 不是前后相互独立的。特征提取的选择取决于这些预处理的结果。 显然，在一定意义上特征提取和特征选择都是要达到特征降维的目的，只是 所实现的途径不同，特征提取是通过某种变换的方法组合原始高维特征，获得一 组低维的新特征，而特征选择是根据专家的经验知识或根据某种评价准则来挑选 出那些对分类最有影响力的特征，并未生成新的特征。有时这两者并不是截然分 开的，例如可以先将原始特征空间映射到维数较低的空间，在这个空间中再进行 选择以进一步降低维数。当然也可以先经过选择，去掉那些明显没有分类信息的 特征，再进行映射，以降低维数。 在这一章中主要讨论了特征提取，对本课题提取的特征进行了详细的说明， 特征选择的内容会在下一章详细讨论。 2 2 手写体字符特征提取方法概述 特征提取是整个字符识别系统的关键，识别算法是根据选取特征的种类来进 行选择的。所选取的特征是否稳定，是否代表一类字符的特点，是系统识别率的 高低的关键。 j e 瘟整虫太堂亟堂焦论奎壬兰佳熬主蛆剔史曲挂延埕取塑挂延选捏班窥 手写体字符特征提取的方法可分为结构特征和统计特征两种。下面分别简述 这两种特征提取方法的特点与一般方法。 2 2 1 结构特征提取方法 采用结构特征提取对字符进行结构分析从而达到识别的目的，是一种非常直 观的方法，其思想与人认字的原理有点相象，但又有所不同。其基本思想是：字 符可以逐级分解成部件、笔划乃至笔段，识别时可以自底向上，由象素得到笔段， 由笔段结合成笔划，由笔划构成部件，由部件组成字符，逐级分析字符图象的结 构，根据各元素的属性、数量及其相互关系，便可以判定待识字符。目前研究较 成熟，效果比较好的是基于笔划和基于笔段分析的手写体字符识别。 对不同的字符手写样本，尽管人书写风格千变万化，然而，笔划与笔划之问 的位置关系、以笔划为基元的字符的整体拓扑结构是不变的，人认字就是抓住了 这些本质不变的特征，因此能适应不同的书写风格的文字。所以，基于笔划来自 动识别字符一直是手写体字符识别研究的一类主要研究方法。 虽然字符的笔划特征受字体、字形大小等影响较小，是识别字符的良好特征， 但可惜笔划特征对实际的书写文本来说较难稳定的提取。通常，用基于笔划段作 为特征能较好的解决这一困难。采用结构特征提取方法的难点在于笔划或笔段等 基元的准确提取。虽然提取笔划或笔段的方法己有多种研究，但它们都是基于图 象处理的方法，截然不同于人根据知识和经验而作出的视觉处理。单纯建立在图 象处理方法上的笔段机器分析只能十分机械地按图象就事论事，结果提取到的笔 段难免与人的判别不完全一致。这种情况在存在连笔、断笔、模糊等的场合尤为 不可避免。所以，书写畸变对结构特征分析法有十分重要的影响。因此，寻求稳 定可靠的笔段提取方法仍然是当前有待进一步研究的课题。 2 2 2 统计特征提取方法 从统计模式识别的观点来看，字符识别实际上是一个模式分类问题，人对自 然物体的识别，是建立在对该物体进行学习、特征分析的基础上的，计算机模式 识别的过程与人的识别过程有着相识的地方。实际上就是一种通过学习或者其它 方法，形成一个记忆知识库，进行模式识别时，清晰地表达出一种从物体到记忆 知识库的映像，从而得到识别结果。人在进行物体识别时，是利用大脑中通过学 习形成的记忆库，对识别的物体进行一种黑箱式的映像，从记忆库中找出相匹配 的类别。计算机要把人类识别物体时的这种黑箱式的映像表达出来，一般是由两 个步骤来完成的：第一步，以适当的特征来描述物体，即由x i 一取i ) 的映像；第 韭壶鲤鱼太堂亟堂建迨塞壬蔓佳熬主迟型生的缱延握取狸挂堑堡登型宜 二步。计算机执行某种运算完成由f ( x 卜啾户x 的映像。此过程实际上就是传统 的统计模式识别进行物体识别时所采用的一般方法，具体来说就是特征提取和分 类函数的设计的问题。而特征提取是问题难点和的关键所在。因为如果特征己知， 就可以利用现有的数学理论来指导设计映像函数r ( x i ) 。然而，对于特征的选择和 提取，却没有可遵循的理论来指导，我们很难比较一个物体中哪些特征是实质性， 那些特征是有代表性的，那些特征可能是不重要的或与识别无关的，这需要大量 的实验和理论指导。经过人们在这方面的大量研究工作，发展了一些统计特征提 取方法，在本章后面部分，我们将讨论几种常用的特征提取方法，并提出了本文 中使用的特征向量。 2 3 手写数字识别的特征提取中所使用的模板说明 1 九点窗：对每一个二值化后的0 、1 点阵，值为1 的点称为黑点，值为0 的点称为白点，每个黑点和它周围相邻的八个点构成一个九点窗。这个黑点定义 为p o ，从它左上角的点开始，沿逆时针方向，分别定义为p 1 p 8 ，具体形式如图 2 1 所示。 p 1p 2 p 3 p 8 p 0p 4 p 7p 6p 5 图2 1 九点窗示意图 2 八个特征提取方向：定义沿逆时针的八个方向，分别是o 度和1 8 0 度、+ 4 5 度和一1 3 5 度、+ 9 0 度和一9 0 度、+ 1 3 5 度和一4 5 度分别在四条直线上，称 为四个特征提取的方向，若再加上从外至内的搜索方向，则称为了八个特征提取 的方向。如下图2 - 2 所示。 韭立鲣电太堂亟堂焦j 金塞壬要住堑主迟剔虫的挂延埕取塑挂延选捶班宜 9 0 度 1 8 0 度 1 3 5 度4 5 度 1 3 5 度一4 5 度 0 度 9 0 度 图2 2 八个特征提取方向示意图 3 四个象限：将每个点阵分割成4 个点阵，按顺时针方向分别称为第一象限、 第二象限、第三象限和第四象限，具体如下图所示 第一象限第二象限 第四象限第三象限 图2 3 四个象限示意围 这里所说的象限实际是对字符点阵的矩形区域的覆盖，所以每个区域的大小 尺寸应取得合适，如果取得太小，则有些特征表现不出来，反之取得太大，则特 征会变得太复杂。对矩形的大小来说，必须能覆盖整个点阵的图像，否则会丢失 一些信息，但也不能取得太大，否则将会产生较多的重复信息，这样也不利于分 类。我将一个1 6 1 6 的点阵平均分成4 个8 8 大小的矩形区域，在后面描述特 征时，将分别称为第一象限、第二象限、第三象限和第四象限。 2 4 手写数字识别中的特征提取 在抽取过程中，针对手写数字的特点，抽取了包括傅立叶系数特征、笔划密 度特征、轮廓特征、投影特征、重心及重心矩特征、粗网格特征和首个黑点位置 特征共1 0 4 维特征。 2 4 1 笔划密度特征 笔划密度特征的提取方法是：以不同方向扫描数字，计算扫描线和笔划相交 的次数，形成笔划密度特征向量。在本文中，我对1 6 1 6 的样本在水平方向上每 隔4 行扫描一次，提取了4 个特征值，并在垂直方向上也每隔4 行扫描一次，提取4 个特征值，最后共形成8 个值的特征向量。从密度特征的提取方法容易看到，笔 划密度特征对字形畸变的抗干扰能力较强，但抗噪声能力较弱。 2 4 2 傅立叶变换特征 关于在频域里提取形状特征的问题，一般来说，区域的别界是一条封闭的曲 线。如果在此轮廓线上取一动点，并且沿曲线逆时针方向移动，则从点的坐标的 变换是一个周期函数。通过规范化以后，这个周期函数可以展开成傅立叶级数。 显然，傅立叶级数中的一系列系数于边界曲线的形状有关，可以用作形状的描述。 当增加级数的项数使系数取到足够多的阶次时，几乎可以把形状信息完全提取出 来，并且可以通过这些系数重建原来的几何形状。 傅立叶变换是在图像处理中应用广泛的一种二维正交变换，傅立叶变换后平 均值即直流项正比于图像灰度值的平均值，低频分量则表明了图像中目标边缘的 强度和方向。手写体字符一般能用很多线段构成的封闭轮廓来表示，通过映射所 得到的一些离散量能够充分的反映这些封闭轮廓的变化。傅立叶系数能够很好的 描述图像边界轮廓，其值与相似字形的平移、旋转、位移和尺寸大小无关。在字 形表征和识别时，这些特征形成明显的数据压缩。 图像经数字化处理后，可以用二维的离散信号贝m 一) 来表示。对于二维离散 信号扳研，竹) ( 肼= o ，1 ，m l 万= o ，1 ，n 一1 ) ) ，其离散傅立叶变换定义为： 脚，咖南美笺他，咖叫矧协。 在式中，删，1 ，m 1 ，脚，l ，n l ，称为空间频率。，为虚数单位，= 一1 j 立邮虫太堂亟堂僮i 盆塞 壬量佳熬主迟剔生的挂延握取扭挂延选叠班究 逆变换定义为 m = 赤笔笺脚m ( 篱 c z 划 在式中，l = 司，1 ，m - 1 ，：o ，l ，n l 。 在图像处理时，一般选取图像块为n n 的方阵，即取m = n ，这时二维离散 傅立叶变换和逆交换式为 即，v ) ：告兰1 艺1 m 川p 叫半 。：吲f ( ) = 吉，( m ，以) p ”“n j ( 2 _ 3 ) ( m ，靠) ：告窆f ( “，v 弦吖2 1 半) 。2 4 ，( m ，1 ) = 吉f ( “，弦”“l j ( 2 4 ) 在( 2 3 ) 和( 2 4 ) 两式中，珥m 棚，n = o ，l n l ， 从物理效果看，傅立叶变换是将图像从空间域变换到频率域，其逆变换是将 图像从频率域转换到空问域。换句话说，傅立叶变换的物理意义是将图像的灰度 分布函数变换为频率分布函数，傅立叶逆变换是将图像的频率分布函数变换为灰 度分布函数。傅立叶变换可以得出信号在各个频率点上的强度。 傅立叶变换之所以在图像处理中被广泛使用，成为图像处理的有力工具，就 是因为它具有良好的性质。傅立叶变换具有可分离性，式( 2 1 ) 的指数可以被 分解，从而变换可以写成如下形式： 脚，= 击薹t 嘉篓舳川p 叫2 嘈p 2 曙 c 2 根据此式，二维离散傅立叶变换分解为水平和垂直两部分运算。式( 2 5 ) 中方 括号中的项表示在图像的行上计算的离散傅立叶变换，方括号外面的求和则实现 结果数组在列上的离散傅立叶变换。这种分解使得可以用一维的快速傅立叶变换 来实现二维傅立叶变换。具体来说，一般采取连续2 次运用一维离散快速傅立叶 变换的方法来实现，即先 召l 厦m ，n ) 的每一个m 对n 求变换，再乘以n 得到尺坍，v ) ，完 成第一次变换。然后再将得到只m ，v ) 沿厦m ，帕的每一个v 对m 求变换，即可得至帆坍，力 的最终变换尺“，力。对字符点阵( 1 6 1 6 ) 做二维离散傅立叶变换，可以得到2 5 6 个傅立叶系数。 将，( ”，v ) 用矩阵表示如下： ff ( o ，o ) f ( o ，一1 ) 、l ，= i ； l ii i ，( ，o ) f ( 一1 ，一1 ) j 以“，v ) 的大幅值系数集中在低频区域内，即矩阵的左上、右上、左下、右下 四角的周围。 我对字符点阵做二维( 1 6 x 1 6 点) 的离散傅立叶变换，并从上文中所提到的 四个低频区域中选取了3 2 个离散傅立叶变换系数作为特征。这3 2 个特征系数是： f ( o ，o ) ，f ( 0 ，1 ) ，f ( o ，2 ) ，f ( 0 ，3 ) ，f ( 0 ，4 ) ，f ( 1 ，0 ) ，f ( 2 ，o ) ，f ( 3 ，o ) ，f ( 4 ，o ) ，f ( 1 ，1 ) ，f ( 1 ，3 ) ， f ( 2 ，1 ) ，f ( 2 ，2 ) ，f ( 2 ，3 ) ，f ( 3 ，1 ) ，f ( 3 ，2 ) ，f ( 1 ，1 5 ) ，f ( 1 ，1 4 ) ，f ( 2 ，1 5 ) ，f ( 2 ，1 4 ) ，f ( 3 ，1 5 ) ， f ( 1 5 ，1 ) ，f ( 1 4 ，1 ) ，f ( 1 4 ，2 ) ，f ( 1 3 ，1 ) ，f ( 1 5 ，1 5 ) ，f ( 1 5 ，1 4 ) ，f ( 1 5 ，1 3 ) ，f ( 1 4 ，1 5 ) ，f ( 1 4 ，1 4 ) ， f ( 1 3 ，1 5 ) ，f ( 1 3 ，1 4 ) ，然后再将这些特征归一化到 0 ，l 】区间之内。 2 4 3 轮廓特征 字符的轮廓特征能够很好的反映字符的整体结构和特性，提取轮廓特征时先 由根据边界信息算法的阈值操作组成，从而提供了字符的轮廓外形。从规整化的 轮廓中直接可以导出字符的边缘轮廓。规整化的字符以n n 的点阵表示，在这里 n 为1 6 。 记b ( 1 ( ) 、( k ) 为点阵第k 行的左、右轮廓。 k = j 拈【o ，n 1 】，j o 满足妣j o ) = 1 且当j j o ，f 【k j ) = 0 ( 1 ) 字符宽度定义为： w = 砩- k ) ( 2 6 ) k 【o j 1 表示指定的行。宽度在描述某些字符如“o ”，“6 8 ”9 ”时非常有 用。 ( 2 ) 比率定义为 比率= n ，w 。 w 。是字符有效宽度，w 一= m 戤州) ，k 【0 ，n l 】 利用比率特征可以有效识别字符“l 竹，对于字符“l ”来说， 2 5 ，而对于其他字符来说，比率特征并非总是大于2 5 。 ( 3 ) 字符有效高度h 一定义为： h 。= m 缸( h ( k ” k 【0 ，n l 】，h ( k ) 为第k 列的字符高度 ( 2 7 ) 比率特征总是大于 ( 2 8 ) 北立邮电太堂亟堂焦 盆奎壬呈佳熬主迟剔虫殴挂延埕取狸挂延选挂班究 ( 4 ) 宽高比定义为w 一h 一 左右边缘线的一阶有限差分别为： b 肚) = k ) 一l p ( k 1 ) ( 2 9 ) r d ( k ) = 砩( k ) 一砩1 ) ( 2 1 0 ) 由此，定义了如下特征 字符轮廓线最大值和最小值所在的位置 l r 。= kik = m a x ( k ( 1 ( ) ) ) r 一= ( k k = m 强( r ( 1 【) ) ) k 血= f kik = n l i n ( l p o 【) ) ) l t 血= k i k = m 域砩( k ) ) ) 字符左右边缘线的正负峰 ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) ( 2 一1 4 ) l 伸k + = m a 】【 l 僦f ( 1 【) ) ( 2 1 5 ) k + = m 强 r d i f o c ) ， ( 2 一1 6 ) b 出= m i i l k t ( 1 【) ) ( 2 1 7 ) k = m i n r d i 肚) ) ( 2 一1 8 ) k 吐= ib 。hl + lb 出i ( 2 1 9 ) 砩曲k = ir 灿l + lr p 凼i ( 2 2 0 ) 这样共有1 4 个特征，分别是字符有效宽度、字符比率、字符有效高度、字符 高宽比、字符轮廓线左侧最大值、字符轮廓线左侧最小值、字符轮廓线右侧最大 值、字符轮廓线右侧最小值、字符边缘线左侧正峰值、字符边缘线左侧负峰值、 字符边缘线右侧正峰值、字符边缘线右侧负峰值、字符边缘线左侧正负峰值绝对 值之和、字符边缘线右侧正负峰值绝对值之和。 f 2 4 4 投影特征 如图2 2 所示，将一个字符点阵划分成四个象限区域，共有十二个边线。将 一个字符点阵中的每一个黑点向最近的四条边线沿水平和垂直方向投影，用十二 条边线上的投影长度作为投影特征，一共有十二个特征。 厂l) l = _ l夕 l 1 图2 2 投影特征示意图 投影算法的基本描述如下： 对于字符点阵中的每一个点，投影到离它最近的四条边线上，具体投影方法 如图2 3 所示， 图2 3 水平、竖直方向上的投影 当一点被