（计算数学专业论文）印刷体数学公式识别系统的设计与实现——分割、识别与重组.pdf

摘要 随着计算机的普及，人们越来越多的使用计算机处理日常工作和存储信息。目前广 泛应用的o c r 系统对手写、印刷体文本都有很高的识别率，已经广泛应用于办公自动化、 快速录入等领域，克服了人工输入费时费力的缺点。但是，对于一篇科技文献，其中有大 量的数学公式，它们是由特殊的符号、希腊字母、英文字符和数字组成的复杂的结构体。 当前的o c r 系统只能识别单个字符，还不能分析公式结构，这样识别出来的公式只是一 组毫无关系的字符串，失去了它所表达的数学含义。为此，我们提出了一种新的关于表达 式识别的设计思想，并给出了完整的算法，将印刷体的数学公式( 图像格式) 转换成可编 辑的电子格式( 如m ，w o r d 公式编辑器) 。 按照表达式识别系统的流程，本文相应的分为以下四部分： 粘连字符的分割。由于纸质文档的印刷质量、纸张的光洁度、扫描仪的分辨率、二值 化等因素的影响，扫描得到的图像中的字符可能是粘连的。这为字符识别带来了困难。本 文提出用自组织映射作字符分割的方法，对经典的自组织学习规则做了一些改进，使其 能以较少的神经元结点、较快的速度逼近粘连字符的白像素点的分布。文中对最短路径 分割方法和自组织映射法分割做了对比，后者能分割一些前者不能处理的粘连字符。 特征提取与选择。一个字符图像只是模式空间中的特征，还不能用来分类必须在 它上面提取抗旋转、缩放、平移的几何不变性特征。文中介绍三种常用的矩方法：规则 矩、z e r n i k e 矩和样条小波矩。通过计算这三种矩可分性度量，发现z e r n i k e 矩更适于做字符 的特征。文中还介绍了基于神经网络的主分量分析方法，在3 8 维矩特征中选取1 8 维的主 特征，保留信息量的同时，大大降低了特征矢量的维数消除了样本间的相关性，突出了 差异性。 字符识别。分类器是整个识别系统的核心。神经网络已经被广泛用于模式识别，克 服了当前常用的模式识别方法的缺点，有效提高了识别率。文中用自组织特征映射做字 符的粗分类，将特征相近的字符分在一组。然后b p 神经网络对各组字符做细分类，识别 出同一组的不同字符，有效地提高了分类精度， 公式重构。如何从一组字符中判断它们复杂的结构至今也没有很好的解决。文中将 介绍一种新的公式重构的方法。主要包括上下标定位的方法、符合l l ( 1 ) 文法的数学表达 式构成规则和语法分析器。无序的字符串通过语法分析器生成语法树，最终被转换成可 编辑的d t f t x 公式格式。 文章最后，以一定数量的英文数学资料作实验，结果表明该系统具有一定的实际应 用价值，但是还有待进1 步改进。 关键词：模式识别，粘连字符分割，矩特征，主分量分析，自组织映射，b p 神经网 络，公式重构 a b s t r a e t t h ec o m p u t e r i z e dd o c u m e n t h a n d l i n gs y s t e m s h a v eb e e nw i d e l yu s e d ，b u tf e ws y s t e m sh a v ep r o v i d e df u n c t i o n sf o rr e c o g n i z i n ga n du n d e r s t a n d i n gm a t h e m a t i c se x p r e s s i o n s p r i n t e di nd o c u m e n t t h es y s t e mp r o p o s e di n t h i sa r t i c l eh a st h ea b i l i t yt or e c o g n i z e m a t h e m a t i c se x p r e s s i o n si nf i l e ss c a n n e dd i r e c t t yf r o mp a p e ra n dt or e c o n s t r u c tt h er e c - o g n i z e de x p r e s s i o n si n t op a r t i c u l a rp u b l i c a t i o nf o r m a ts u c ha si 掣t e xo rw o r d t h e s y s t e mw o r k sa sf o l l o w s ： m e r g e d ，s y m b o ls e g m e n t a t i o n d u et o t h eq u a l i t yo fp r i n t e r ，c l e a n l i n e s so fp a p e r t r e s o l u t i o no fs c a n n e r ，b i n a r i z a t i o ne t c ，s y m b o l si ns c a n n e dd o c u m e n tm a yb em e r g e d ， t h e r e f o r e ，c a nn o tb ee a s i l yr e c o g n i z e d i nt h i sa r t i c l e ，w ep r o p o s e dan e wm e t h o d ，s e l f - o r g a n i z i n gf e a t u r em a p lt os e g m e n tm e r g e d s y m b 0 1 b ym o d i f y i n gt h ec l a s s i cu p d a t i n g r u l eo fs e l f - o r g a n i z i n gm a p ，w eo b t a i n e dan e t w o r kt h a tc a na p p r o x i m a t et h ed i s t r i b u t i o n o fw h i t e p i x e l sb e t w e e nt w os y m b o l si nl e s st r a i n i n gt i m ea n dw i t hl e s su n i t s f e a t u r ee x t r a c t i o na n ds e l e c t i o n as y m b o l i ni m a g ef i l ec a nn o tb ec l a s s i f i e dd i r e c t l y , c a u s ei ti sn o ti n v a r i a n tw i t hr e s p e c tt oi m a g et r a n s l a t i o n ，o r i e n t a t i o na n ds i z ec h a n g e s i nt h i s a r t i c l e ，w ei n v e s t i g a t e dt h r e ek i n d so fm o m e n tf e a t u r e st h a tu s e da 8as h a p e d e s c t i p t o r ：r e g u l a rm o m e n t s ，z e r n i k em o m e n t sa n db s p l i n ew a v e l e tm o m e n t s w ea l s o u s e dp c an e a r a ln e t w o r kt os e l e c tp r i n c i p a lf e a t u r e s w h i d lr e d u c e dd i m e n s i o n so ff o a t u r e s p a c ew h i l er e t a i n i n gu s e f u li n f o r m a t i o n c h a r a c t e rr e c o g n i t i o n r e c o g n i z e ri sk e yp a r ti no u rs y s t e m n e u r a ln e t w o r k s ，w h i c h o v e r c o m et h ed i s a d v a n t a g e so ft r a d i t i o n a lp a t t e r nr e c o g n i t i o nm e t h o d s 7 h a v eb e e nu s e d e x t e n s i v e l yo no c r a n dh a v ea c h i e v e dh i g h e rr e c o g n i t i o nr a t e i nt h i sa r t i c l e w eu s e d s o f mn e t w o r ka sr o u g h c l a s s i f i e r ，w h i c hc l a s s i f ys i m i l a rs y m b o l si n t os a m eg r o u p a f t e r t h a t ，w eu s e db pn e t w o r ka sf i n e - c l a s s i f i e r ，w h i c hi d e n t i f i e ds y m b o l sw i t h i no n eg r o u p e x p r e s s i o nf o r m a t i o n s of a r ，t h ep r o b l e m o f u n d e r s t a n d j n g a c o m p l i c a t e dm a t h e m a t i e se x p r e s s i o n si na p r i n t e dd o c u m e n th a sn o tb e e nc o m p l e t e l ys o l v e dy e t w ei n t r o d u c e d af o r m a t i o na l g o r i t h mf o rl o c a t i n gt h es u p e r s c r i p ta n d s u b s c r i p t ，a n df o ra n a l y z i n gt h e t w o d i m e n s i o n a ll a y o u ts t r u c t u r eo ft h es y m b o l sw i t h i na e x p r e s s i o n t h e nt h es t r u c t u r e o fa r e c o g n i z e de x p r e s s i o nw a sr e p r e s e n t e db yat r e es t r u c t u r ea n dt h eo r i g i n a le x p r e s s i o n c o u l db er e p r o d u c e db yu s i n gas u i t a b l ef o r m a t t e rl i k e 琊 t h ee x p e r i m e n t a lr e s u l t sa tt h ee n do fa r t i c l eh a v ed e n l o n s t r a t e dt h ef e a s i b i l i t yo f t h es y s t e m b u tt h em o d e lw ep r o p o s e ds t i l ln e e d sf u r t h e ri m p r o v e m e n tf o rc o m m e r c i a l a p p l i c a t i o n k e yw o r d s ：p a t t e r nr e c o g n i t i o n ，c h a r a c t e rs e g m e n t a t i o n ，m o m e n ti n v a r i a n t s ，p r i n c i p a lc o m p o n e n ta n a l y s i s ，s e l f - o r g a n i z i n gf e a t u r em a p ，b pn e u r a ln e t w o r k ，e x p r e s s i o nf o r n a t i o n i i 第一章综述 1 _ 1 神经网络 人工神经网络( a r t i f i c a ln e u r a ln e t w o r k ：a n n ) 是近二十年发展起来的一个十分活 跃的交叉学科，它涉及生物、数学、物理、电子及计算机技术，因此，在科学界存在许多 不同的神经网络的定义。目前使用得最广泛的是t k o h o n e n 的定义，即“神经网络是由 具有自适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统 对真实世界物体所作出的交互反应。” 根据一个简化的统计，人脑由百亿条神经组成，每条神经平均连结到其它几千条神 经。通过这种连结方式，神经可以收发不同数量的能量。神经的一个非常重要的功能是 它们对能量的接受并不是立即作出响应，而是将它们累加起来，当这个累加的总和达到 某个临界阈值时，它们将它们自己的那部分能量发送给其它的神经( 见图1 1 ) 。大脑通过 调节这些连结的数目和强度进行学习。尽管这是个生物行为的简化描述，但同样可以充 分有力地被看作是神经网络的模型。 s u m ：i = z x i w i i n p u t ：z nw e i g h t ：n 图1 1 ：神经元模型 f i g 1 1 ：m o d e lo fn e u r o n 神经网络也许是计算机计算的将来，如果我们将人脑神经信息活动的特点与现行 冯诺依曼计算机的工作方式进行比较，就可以看出人脑具有以下鲜明特征： 1 巨量并行性。在冯诺依曼机中，信息处理的方式是集中、串行的，即所有的程序指令都 是一1 条一条地执行。而人在识别一幅图像或作出项决策时，存在于脑中的多方面的 知识和经验会同时并发作用以迅速作出解答。据研究，人脑中约有多达1 0 1 0 1 0 t t 数 量级的神经元，每一个神经元具有1 0 3 数量级的连接，这就提供了巨大的存储容量，在 需要时能以很高的反应速度作出判断。 2 信息处理和存储单元结合在一起。在冯诺依曼机中，存储内容和存储地址是分开的， 知鲫如；靠 印刷体数学公式识别系统的设计与实现 必须先找出存储器的地址，然后才能查出所存储的内容。一旦存储器发生了硬件故 障，存储器中存储的所有信息就都将受到毁坏。而人脑神经元既有信息处理能力又有 存储功能，所以它在进行回忆时可以由一部分内容恢复全部内容。当发生“硬件”故 障( 例如头部受伤) 时，并不是所有存储的信息都失效，而是仅有被损坏得最严重的 那部分信息、丢失。 3 自组织自学习功能。冯诺依曼机没有主动学习能力和自适应能力，它只能按照人们 已经编制好的程序步骤来进行相应的数值计算或逻辑计算。而人脑能够通过内部自 组织、自学习的能力，不断地适应外界环境，从而可以有效地处理各种模拟的、模糊 的或随机的问题。 前面提到过神经网络是多学科交叉的产物，不同的理论背景可以建立不同的神经网 络理论模型。感知器理论中，需要用到线性空间、凸分析、超曲面等代数、几何方面的有 关理论。在离散h o p f i e l d 神经网络系统理论中，用到网论、纠错码。在连续h o p a e l d 神经 网络系统理论中，用到非线性微分方程及稳定性理论。对波尔曼机用至1 m a r k o v 链及其遍 历性问题、信息论与相对熵等工具，还要用到近世微分几何，黎曼几何，信息统计等工 具。h a k e n 根据协同形成结构，竞争促进发展的规律，将协同的非线性动力理论与神经网 络有机结合，提出了协同联想记忆网络。a m a r i 提出用微分流形和统计推理来研究神经网 络。在a m a r i 理论的基础上史忠植等提出了一种神经场模型，由场组织模型和场效应模型 构成。 1 1 1 神经网络的设计 神经网络的设计是复杂的，设计者往往要经过一系列反复试验才能得到满意的设计。 神经网络的设计包括以下几方面： 神经元之间的排列方式； 不同层神经元之间的连接方式，以及同层神经元之间的连接方式： 神经元接受输入和产生输出的方式； 连接权值的学习规则： 分层结构 一般来说，所有的神经网络都有相似的拓扑结构。神经网络中的处理单元可以分戍 称为层的不相交子集，在同一层中的神经元具有相同的传递函数。最常见的有三种形式： 一是输入层，输入神经元只接受从外部环境到达的输入。 二是输出层，神经元把信号从系统输出，这些输出即可直接影响运动系统，也可只影 响外在于系统的其它系统。 三是隐藏层。是那些输入与输出都在系统中的单元，对于外界来说，它是看不见的。 输入层接受从外部环境到达的输入，产生输出。继而，这个输出被用于隐层的输入。 这个过程一直持续到满足某个特定条件或直到从输出层输出到外界。 几种常用的连接方式 神经元通过权值相互连接，将一个神经元的输出传给另一个神经元的输入。这些连 接可能是单向的，也可能是双向的。一个神经元可能有一个或多个输入，个或多个输 2 印刷体数学公式识别系统的设计与实现 出。同层之间的神经元可能有连接，也可能没有连接。下面是几种不同层之间神经元的 连接，称为层间互联( i n t e r 1 a y e rc o n n e c t i o n s ) ： 全连接( f u l l yc o n n e c t e d ) ：第一层的神经元与第二层所有的神经元都有连接： 部分连接( p a r t i a l l yc o n n e c t e d ) ：第一层的神经元不一定与第二层所有的神经元都有 连接： 前传( f e e df o r w a r d ) 连接。第一层神经元的输出传给第二层的神经元，但是它们不 接受第二层的神经元的输出； 双向( b i d i r e c t i o n a l ) 连接：第一层神经元的输出传给第二层的神经元，同时它们也 接受第二层的神经元的输出； 层级( h i e r a r c h i c a l ) 连接：只有上下两层之间的通信，没有跨层通信； 共振( r e s o n a n c e ) 连接：全连接，并且层问反复传送消息直到满足某条件； 更复杂的结构是同层内神经元也有连接，称为层内互联( i n t r a - l a y e rc o n n e c t i o n s ) ： 递归( r e c u r r e n t ) 连接：同层的神经元全连接或部分连接，神经元之间相互通信，直 到满足条件，才输出到另层； o n 。c e n t e r o f fs u r r o u n d ：神经元对它的邻居有兴奋性连接，对其它神经元则是抑止性 连接； 几种常用的训练方法 无导师学习( u n s u p e r v i s e dl e a r n i n g ) 。不存在来自环境的反馈来指示网络的输出应 该是什么或是否正确，神经元和连接呈现某种程度的自组织性； 强化学习( r e i n f o r c e m e n tl e a r n i n g ) 。也叫有导师学习。通过来自环境的指导信息( 包 括输入和期望输出的训练样本) 来告诉连接怎么修改权值。通常，为了保证训练的成 功，需要很多训练样本和很长的训练时间： 误差反传( b a c kp r o p a g a t i o n ) 。误分类或错误信号被反向传播以修改权值，是有导师 学习的一种； 几种常用的学习规则 这些学习规则是用数学公式表示的网络连接权值更新算法，虽然简单，但是稍加变 化，就可以导出各种新的规则。 肌b b lsr u l e ： 蚴；= 叩q x i 心理学家d o n a l do l d i n gh e b b ( 1 9 0 4 1 9 8 5 ) 写了一本题为t h eo r g a n i z a t i o no fb e h a v i o r 【1 】的书，在这本书中他提出了神经元之间连接强度变化的规则，即后来的h e b b 学习法 则。h e b b 写道：“当神经细胞a 的轴突足够靠近细胞b 并能使之兴奋时，如果a 重复或持 续地激发b ，那么这两个细胞或其中个细胞上必然有某种生长或代谢过程上的变化， 这种变化使a 激活b 的效率有所增加。”简单地说。就是如果两个神经元都处于兴奋状态 ( 给它们有相同的符号) ，那么它们之间的突触连接强度将会得到增强。 3 印刷体数学公式识别系统的设计与实现 h 0 西e l dl a w 掣：瑚) + m 蛳哪) 地 ( 1 2 ) t 9 8 2 年美国加州理工学院的生物物理学家j jh o p f i e l d 提出t h o p f i e l d 槲络 2 】。他 利用非线性动力学系统理论中的能量函数方法研究反馈人工神经网络的稳定性，并利 用此方法建立全互连型神经网络和计算能量函数，成功求解y n p c o m p l e t e 的t s p 问题 ( t r a v e l l i n gs a l e s m a np r o b l e m ) 。基本的h o p f i e l d 神经网络是一个由非线性元件构成的全 连接型单层反馈系统，能量函数e ( w 1 在网络迭代运行过程中不断地降低能量，最后趋于 平衡状态。 t h ed e l t ar u l e ： a w j i = q ( 吗一仍) 盈( 1 3 ) d e l t a 规则是h e b b 规则的进一步扩展。基本思想是：连续地更改网络权值，使网络对输入 模式的输出响应尽可能地接近各自的期望输出。调节权值的方法是最小化实际输出与期 望输出的均方误差，并反传误差直至第一层。也被称为w i n d r o w h o f f 学习规则或最小均 方学习规则f l e a s tm e a f ls q u a r el e a r n i n gr u l e ) 。 k o h o n e n sl e a r n i n gl a w ： p ( + 1 ) = ( d m 。，k ) ( m ) 一w i n ( k ) )( 1 4 ) t e u v ok o h o n e n 提出的模仿大脑皮层活动的拓扑网络结构，其中的神经元之间相互竞争， 胜者获得学习机会( w i n n e rt a k e sa 1 1 ) 。获胜的神经元在更新自己权值的同时，抑止其 它神经元的活动。k o h o n e n 规则不需要期望输出，属于无导师学习， 学习理论 学习是基本的认知活动，是经验与知识的积累过程，也是对外部事物前后关联地把握 和理解的过程，以便改善系统行为的性能。学习的目的是通过有限个例子( i l l 练样本) 的 学习找到隐含在例子背后的规律( 如函数形式) 。通过学习解决问题是神经网络的一个主 要特点。包括以下三方砸问题 e l ： 1 学习的统计性能，通过的例子能否学到其中规律? 或者说随着所学例子的增加学习结 果是否越来越趋于真正的规律( 错误率一o ) ? 这是从信息论观点，原则上能否学习 的问题是统计学习理论的主要研究内容； 2 学习的计算复杂性，为学到真正规律所需样本量( 样本复杂度) 与计算量( 计算复杂 度) 。这里从算法及其现实性看实际上能否学习的问题，它是计算学习理论重点研究 的内容： 3 学习过程是反馈的，因而是一个动态过程，作为动态过程，一些学习算法的收敛性问 题。 通过选择不同的层结构、连接方式、训练方法、学习规则，可以得到不同的神经网络 模型( 见附录b ) 。 4 印刷体数学公式识别系统的设计与实现 s 1 1 2 神经网络的应用 神经网络的研究已有近4 0 年( 有关神经网络的发展史，可见徐秉铮 3 】) ，神经计算成 为了一个非常热门的研究领域，已成为人工智能两大主流( 连接主义和符号主义) 之一。 但这领域仍处于发展的初期阶段，可以说是- - r 具有活力的学科。 神经网络具有其它方法所不具有的性能，能成功地解决其它一些方法解决不了的问 题，已经被用来解决各种复杂的、模糊的、不完备模式问题。最常见的是用于预测，如各 种专家系统、股市预测。也可以用来解决各种分类问题，如模式识别、翻译、银行信用风 险评估、签字识别。还被广泛用于其它学科，如信号处理、故障检测、自动化控制、语音 识别、可化视、优化问题、排序问题等等。 目前已经成熟的应用n n s 的产品有很多。n n s 的商业用途目前已经引起人们越来越 多的关注一些大型金融机构已在使用神经网络来增进某些特殊功能，如评定顾客的信 用、评判抵押品的价值、目标行销以及贷款风险评估等，虽然这些系统实际运行时只比传 统演算法的精确度高出几个百分点，但因为这些评估涉及了巨大的资金交易，因此它具有 突出的实用价值。现在还有些机构使用神经网络来分析信用卡的交易情况，以判断是否 被盗刷。一家叫n e s t o r 的公司用n n s 做抵押贷款的金融风险预擐4 ，将贷款的风险分为优质 和不良两个等级。h n c 公司( h e c h t n i e l s e nc o ) 为b a n k t e c 开发的手写体识别系统，用 于支票和信用卡的签字识别。n n s 也可用来侦测犯罪行为，美国大多数机场都用n n s 来侦 测旅客的行李箱里是否夹藏炸弹或其他爆裂物品，如安装在美国机场的s n o o p e 炸弹探 测器。而芝加哥警察局的风纪处则用n n s 来“过滤”受贿警官。还有常用的人脸识别技术 用于在大型体育场等公共场所搜索罪犯。计算机智能方面，语音自动生成系统n e t t m k ， 它可以“读”出文本上的文字。而在p d a 上，常见的手写软件也免不了使用n n s 。还有应 用n n s 的网络信息自动挖掘，图像矢量量化的神经网络编码器。还可以用n n s 设计人机交 互游戏，如西洋双陆棋( b a c k g a m m o n ) 、桥牌、跳棋等等，让计算机与人对弈。工业上， 许多自动化工厂也用n n s 来监控操作流程、调节温度设置、判别出错环节，如高炉的温度 控制、轧制机床生产计划的制定、电力调度计划的制定、大规模集成电路的设计等。这种 类型的n n s 取代了人工操作，大大提高了整体生产力， 综上所述，神经网络的应用分为下面几类： 预测：通过输入值来预测输出，如股市预测、天气预报、癌症诊断，信用卡发行机构 也用n n s 做破产预测和预防欺诈； 分类：判断输入的模式属于哪一类，如字符识别、语音识别，通过对病况、模式、图 像、化学成分或顾客的经济状况的分析，产生一份诊断计划或投资计划； 数据联想：类似于分类问题，但是具有联想功能，能从受损模式中恢复出原始数据， 如图像恢复； 数据过滤：平滑输入信号，如图像或语音信号的去噪； 数据概念化：通过分析输入模式，推理数据之间的关系，如数据挖掘： 智能控制：当控制对象或控制过程具有复杂的时变性、非线性或不确定性时，对它们 不能精确建模- 此时经典控制理论很难实现有效控制。而神经网络具有非线性映射能 5 印刷体数学公式识别系统的设计与实现 力，可以对不确定系统自适应和自学习； 优化计算与决策：由目标函数和约束条件建立网络的能量函数，用网络状态的动态方 程驱动恻络运行，当系统稳定时，在稳定点上的能量达到极小值，此时神经元状态对 应最优值； 1 2 模式识别 模式识别是6 0 年代迅速发展起来的一门新学科，属于信息、控制和系统科学的范畴。 随着计算机的普及，无论在理论上，还是在应用上，模式识别技术都有显著的发展，大大 推动了以计算机为基础的具有智能性质的自动化系统的实际应用，促进了人工智能、专 家系统、动态景物分析和三维图像识别等许多新的学术方向和毅技术的产生与发展。 模式识别是一门研究对象描述和分类方法的学科人们的日常生活中差不多每个时 刻都在进行模式识别。一般来说，模式识别问题指的是对一系列过程或事件的分类与描 述。要加以分类的一系列过程或事件可以是一系列物理的对象，或者是一些比较抽象的 如心理状态等。具有某些相似的性质的过程或时间就分为一类。 关于模式识剐的研究成果，在一维和二维的应用方面，有文字识别、语言识别与理 解、指纹鉴别等；同时，在医疗诊断、生物医学信号分析、工件识别与自动检测以及考古 学、侦探学等领域里，也有许多应用成果。8 0 年代后，三维目标的检测与识别越来越为人 们所关注，成为地质勘探、气象观测、遥感图像分析、成像精密制导、空间站交会对接等 高新技术领域急需研究的课题。 1 2 1 模式识别的主要问题 在物理上可以觉察到的世界里，适当地选择某些事物和事件，我们把它们称为样本 对它们分别进行观测。每个样本的观测数据的综合都构成模式，所有的样本观测数据则 构成模式空间。显然，模式空间的维数与所选择的样本和测量方法有关，也与特定的应j ；j 有关，一散来说是很大的，但是有限值。在模式空间里，每个模式样本都是一个点，点的 位置由该样本在各维上的测量数据来确定。由物理上可以觉察到的世界到模式空间所经 历的过程称为模式采集。 模式空间的维数虽然是有限的，还是非常多的。例如一个文字图像可以有几千个数 据，一个心电图波形也可能有几千个数据，一个卫星遥感图像的数据量就更大，其中有些 并不能有效地揭示样本的实质。正像人们对事物进行判断之前要进行综合分析一样，机 器在做出判断之前也要对模式空间里的各坐标元素进行综合分析，获取最能揭示样本属 性的观测量作为主要特征，这些主要特征就构成特征空间。显然，特征空间的维数大大地 压缩了。特征空间里的每个坐标都是样本的主要特征，两且，这些主要特征对于通常所遇 到的变化和畸变是不变的或不敏感的。每个样本在特征空间里也是个点，点的位置由 该样本在各维上的测量数据来确定。由模式空间到特征空间所需要的综合分析，往往包 含适当的变换和选择，称为特征提取或特征选择。特征提取是模式识别中的广泛研究的 课题。特征提取可以避免维数灾难，改进分类器的泛化能力，减少运算次数。 6 印刷体数学公式识别系统的设汁与实现 维数 无限 很大 r 有限 d 图12 模式识别过程，其中c d r 无限 f i g 1 ，2 ：p r o c e s so fp a t t e r nr e c o g n i t i o n 、w h e r ec d r 0 ，说明两个神经元之间相互作用。各神经元的平衡态由于m m 的存在而 相互影响，接受域r i 也通过m m 相互影响。 训练结束后，所有的权值达到一个相对稳定的状态。此时，我们选择第二列的结点 ( 口点) 作候选分割结点，连接它们( 共有七种组合q + 喏+ 嘏= 7 ，最上面的和最下 面的结点分别向上、向下作垂线) 作分割路径。分别计算路径长度( 如遇到黑象素，长度 办n i o ；遇到白像素，长度加1 ) ，选择一条最短路径作分割路径f 见图2 5 1 。 图2 5 ：神经元的分布( 口a n d ) ：口表示候选分割结点，折线表示分割路径 f i g2 5 ：d i s t r i b u t i o no fn e u r o n s ( 口a n d ) 口r e p r e s e n tc a n d i d a t es e g m e n t a t i o nn o d c s ，a n d t h ez i g z a gl i n er e p r e s e n t ss e g m e n t a t i o np a t h 1 4 印w 0 体数学公式识别系统的设计与实现 图26 ：，口a n d 表示a 中不同列的神经元( a ) 新的学习规则的神经元分布：a 中不同列的神经元的 分布跫清晰的：( b ) 传统学习j j ! j l 则的神经元分布：a 中不同列的神经元的分布混杂的 f i g 2 6 ：x ，口a n d r e p r e s e n td i f f e r e n tc o l u m n so fa ( a ) r e s u l t so fd e wu p d a t i n gr u l e ： c o l u m n so faa r ea p p r o x i m a t e l yp a r a l l e l ；( b ) r e s u l t so ft r a d i t i o n a lu p d a t i n gr u l e ：n o d e so fa 7 a l - e i na t a n g l e 2 4 实验参数及结果 本节介绍用最短路径法和s o f m 法作对比试验的具体的参数设置和试验结果。 s o f m 分割法的参数 在s o f m 分割中用白像素坐标p ) = ( x 1 ，x 2 ) 作输入向量。由于像素之间的距离非常 近，我们采用离线训练方法，样本随机输入。定义3 3 神经元结点矩阵a ，4 一邻域，其中 每个神经元结点( i ，i 2 ) 用a i l , i 2 表示。初始时刻a 的结点均匀分布在n m 的二维图像平面 上。取步长函数为 q ( ) = 1 t( 2 , 3 ) 影响因予为 m 。k = 1 1 a l l i 一圳2 ( 2 4 ) 邻域函数为 h ( d o j , k ) ：e x p ( 一锚瓣) ，向( 2 5 ) 【0 ，j c 训练结束后( 1 0 0 步迭代) ，神经元结点矩阵a 的分布( 见图2 6 ( a ) 和2 7 ( a ) ) 。为了比较，我 们刷时用传统的学习规则( 式( 4 6 ) ) 做训练得到分布a 7 ( 见图2 6 ( b ) 和2 7 ( b ) ) 。图2 6 中 口j _ 以看出，a k p , a 7 更稳定，而a 7 比a 更均匀。 两神分割方法的比较 为了弓最短路径( s p m ) 方法比较，我们用一篇从科技期刊上扫描的文章，以及 以哪的四种字体( i t s h a p e ，m d s e r i e s ，s l s h a p e 和t t f a m i l y ) 打印的文章为样 本，从中选取常见的粘连字符，分别用最短路径法和s o f m 分割法作分割试验。表2 1 是 分割结果的统计( 未成功分割次数) ，图2 8 和图2 9 是s o f m 能分割而最短路径不能分割 的部分实例。图2 1 0 和图2 1 1 是s o f m 不能分割而最短路径能分割的部分实例。综合来 印刷体数学公式识别系统的设计与实现 罔27 ：( a ) 新的学习规则的神经元分布：a 中神经元的分布是均匀豹，即使是比较小的白色区域也有 神绎兀，如t w ：( b ) 传统学习规则的神经无分布：a 中神经尢的分布混杂的，神经兀聚集在较大的 f 1 色区域 f i g 27 ：( a ) r e s u l t so fn e wu p d a t i n gr u l e ：t h ed i s t r i b u t i o no fai su n i f o r m ，a n dt h er e f e r e n c e n o d e sa l s oa p p e a ri ns m a l lw h i t er e g i o n ss u c ha si nt h el e f tm a r g i no f t w ；( b ) r e s u l t so f t r a d i t i o n a lu p d a t i n gr u l e ：n o d e so fa 7c o n c e n t r a t eo nb i gw h i t er e g i o n s 看，s o f m 分割对倾斜的字体( 如i t s h a p e ，s l s h a p e ) 分割效果比较好，而且不受字符 笔划粗细的影响。缺点是速度较慢，运算时间是最短路径法的几倍。 i t s h a p e m d s e r i e s s l s h a p ez t f a m i l y s c a n n e dp a p e r 样本总数7 1 1 1 0 8 08 38 8 不能被s o f m 分割的1 41 09l1 1 不能被s p m 分割的 2 191 5l 1 2 表2 1 ：分割结果 t h b ，2 hs e g m e n t a t i o nr e s u l t 1 6 印刷体数学公式汉别系统的设计与实现 图28 ：s o f m 能分开的 f i g 2 8 ：m e r g e dl e t t e r ss u c c e s s f u l l y s e g m e n t e db ys o f m 图2 1 0 ：s o f m 不能分开的 f i g2 1 0 ：m e r g e dl e t t e r sn o ts e g m e n t e d b ys o f m 图2 9 ：s p m 分不开的 f i g 2 9 ：m e r g e dl e t t e r sn o ts e g m e n t e db y s p m 图2 i i ：s p m 能分开的 f i g 2 1 hm e r g e dl e t t e r ss u c c e s s f u l l y s e g m e n t e db ys p m 第三章特征的提取和选择 人们针对客观世界里的具体物体或时f a 进行模式采集时，总是尽可能的多采集测量 数据，致使样本在模式空间里的维数很大。带来的问题是处理的困难，处理时问的消耗和 费用都会很大，有时直接_ j 于分类甚至是不可能的，即所谓“维数灾难”。其次。在过多 的数据坐标中，有的可能对刻划事物的本质贡献不大。这就是特征提取的必要，就是要压 缩模式的维数，使之便于处理，减小消耗。 如何提取独立于位置、尺寸、方向变化的特征是当前模式识别的热点问题。为了使分 类系统具有我们期望的特性( 抗平移、旋转、尺度、扭曲和噪声) ，通常有以下几种特征： ( 1 ) 可视特征，如边缘、纹理和外形： ( 2 ) 变换系数特征，如f o u r i e r 系数、h a d a m a r d 系数； ( 3 ) 代数特征，如基于图像的矩阵分解； ( 4 ) 统计特征，如矩特征。 另一方面，如何消除特征矢量的冗余( 即减小矢量维数) 。选择出最有影响的特征。 以提高识别器的分类效率，也是模式识别中被广泛研究的课题。 综上所述，特征提取与选择可以被看作是从维模式空间到m 维特征空间的映射： ：r “一r 埘，m n( 3 1 ) 使某一标准c 达到最优化。m 可以是线性映射，也可以使非线性映射。这个公式类似于函 数逼近的公式，不同的是，逼近问题需要期望输出；而在某些情况下，特征提取问题的期 望输出是不可知或不需要的。 在字符识别过程中，如果将字符图像的像素直接输入送到识别器中一般来说，会存 在如下些问题： 它们的特征空间是非正交的： 它们不可能表示出被识别模式的显著特征： 它们是冗长的。多余的大输入矢量会导致需要容量更大的识别器，使其性能下降： 对于平移、旋转、尺度的变换，它们不会是恒定的。 在以下各节我们将介绍解决以上问题的方法。在3 1 介绍什么是不变性特征及特征的可 分性度量准则。在3 2 中介绍基于矩特征的特征提取，其中包括几何矩，z e r n i k e 矩和样条 小波矩。在3 3 中介绍了基于p c a 神经网络的主成分分析。在3 4 给出对三种矩提取特征 的能力做了比较，认为对于数学符号z e r n i k e 矩提取的特征更适于分类。还给出了p c a 神 经网络的参数设置和特征选择的效果。 3 。1模式类别可分性度量 什么样的特征能使不同类的样本有效地分离? 选择什么样的准则作为类别可分性依 据? 从直观上讲，如果同类模式的分布比较密集，不同类模式相距较远，分类识别就比较 容易正确。因此，在实际中我们要求提取的特征对不同类的对象差别很大，而同类的对象 差别较小，这样给识别带来很大方便。 1 8 印刷体数学公式识别系统的设计与实现 假设有c 个类型，令。l 表示类内总平均平方距离，则 l = ( p j j 9 ( 3 - 2 ) j = l 式中，p j 为类型屿的先验概率，可用屿的样本数目唧和总样本数目礼估计，而易是类型屿的 类内平均平方距离所以 以= 去善( 刊w 刊 式中，叻为类型u ，的样本均值向量。 同样，可令以为类问总平均平方距离，则 以= p j ( m j m ) t ( 啊一m ) j ；1 ( 3 3 ) ( 34 ) 式中，m 为所有样本的均值向量。 若令以为所有样本之间的总平均平方距离，则 n = f ( ( q m ) 7 ( ( “) 一m ) ( 35 ) “函 在 3 6 j 中已经证明 = l + 五。也就是说，在给定礼个样本后， 是不变的量，类内总平均 平方距离乩的减小必然导致类间总平均平方距离以的增大。为了反映类内距离减小和类 间距离大的要求。可以构造准则函数 3 z = 二竺t ( 3 , 6 ) u u 当然，根据不同需要，也可以有其它准则函数【3 1 。 3 2基于矩的特征提取 矩和矩的函数在二维图像的不变量模式识别中有广泛的应用。美籍华人学者胡名桂 教授f 2 2 】首次提出矩不变量，并用规则矩( 规则矩这里指几何矩) 的非线性组合，得到了 图像在平移、旋转、尺度变换下都具有不变性的不变矩描述符。其后c h e