（模式识别与智能系统专业论文）关于手写数字串切分的研究.pdf

关子手写封今 全 碧勿分时研乡 之 一诵亨 雳 摘要 票据自 动处理系统是一个基于切分的识别系统。 本文重点讨论了手写数字串 的切分过程， 这里用到的切分方法是基于字符本身特征的， 而不依赖于识别技术。 切分系统包括预处理、 初步切分和连写数字串切分三部分。 预处理包括二值化和 去边框， 提出了一种保留字符信息而去除边框的算法。 初步切分包括连通域提取 和连通域属性判别， 给出了一种适应不同书写风格的属性判别方法。 针对连写数 字串切分的问题， 提出了基于字符边缘的字符个数估计方法， 同时找出切分参考 点; 在此信息的指导下， 分别提出了改进滴水算法和全局最优的多模具算法。 构 建了 一个集成所有方法的切分平台( m m s s t o o l b o x ) ， 基于它可以 方便地研究现有 和潜在的切分技术。 该切分系统作为票据自 动处理系统的关键组成部分， 己 经集 成到识别系统中。 关键字 票据o c r ;手写数字串切分;连写数字:改进滴水算法;多模具算法 关子手写翻笋 碧切分劣兑 护ab s t r a c t ab s t r a c t a u t o m a t i c c h e c k p r o g r a m i s a s e g m e n t a t i o n - b a s e d r e c o g n i t i o n s y s t e m . t h i s t h e s i s w i l l f o c u s o n t h e s e g m e n t a t i o n o f h a n d w r i t t e n d i g i t s t r i n g . i n p a r t i c u l a r , i t i s t h e c l a s s i c a l a p p r o a c h o f s e g m e n t a t io n b a s e d o n c h a r a c t e r f e a t u r e s a lo n e ( i .e . n o t a i d e d b y r e c o g n i t i o n ) . t h e s e g m e n t a t i o n s y s t e m i n c l u d e s p r e p r o c e s s i n g , e l e m e n t a r y s e g m e n t a t i o n a n d t h e s e g m e n t a t i o n o f c o n n e c t e d d i g i t s . t h e p r e p r o c e s s i n g i s m a d e u p o f b i n a r i z a t i o n a n d f o r m re m o v a l , a n e w t e c h n i q u e f o r i n t e l l i g e n t f o r m r e m o v a l i s d e v e l o p e d f o r c h a r a c t e r s t r o k e p r e s e rv a t i o n . t h e e l e m e n t a r y s e g m e n t a t i o n i s m a d e u p o f c o n n e c t e d c o m p o n e n t s e x t r a c t i o n a n d t h e d e t e r m i n a t i o n o f c o n n e c t e d c o m p o n e n t s , a n e w d e t e r m i n a t i o n a l g o r i t h m a d a p t i n g t h e w r i t e r s s t y l e i s d e v e l o p e d . i n o r d e r t o s o l v e t h e p r o b l e m o f s e g m e n t i n g c o n n e c t e d d i g it s , e s t i m a t i n g t h e n u m b e r o f c o n n e c t e d d i g i t s a n d f i n d i n g t h e r e f e re n c e p o i n t a r e p r o c e s s e d ; t h e n , t h e im p r o v e d d r o p f a l l a l g o r i t h m a n d m u l t i - m o u l d a l g o r i t h m a r e d e v e l o p e d . a m u lt i - m e t h o d s s t r i n g s e g m e n t a ti o n t o o l b o x ( m ms s t o o l b o x ) i s d e v e l o p e d f o r t h e p u r p o s e o f s t u d y i n g c u r r e n t a n d p o t e n t i a l t e c h n i q u e s f o r n u m e r ic a l d i g i t s e g m e n t a t i o n . a s a k e y t e c h n o l o g y , t h e s y s t e m i s s y s t e m. i n c o r p o r a t e d i n t o a c o m p l e t e o p t i c a lre c o g n i t i o n k e y w o r d s c h e c k o c r ; t h e s e g m e n t a t i o n o f h a n d w r i t t e n d i g i t s t r i n g ; c o n n e c t e d d i g i t s ; i m p r o v e d d r o p f a l l a l g o r i t h m ; mu l t i - m o u l d a l g o r i t h m 尖买手写 裁 演笋勿分内钾 21 - 落1 肴 摆 e 第1 章 概述 模式识别诞生于2 0 世纪2 0 年代， 随着4 0 年代计算机的出 现， 5 0 年代人工智能的兴 起， 模型识别在6 0 年代初迅速发展成一门学科。 儿十年来， 模式识别研究取得了大量的成果， 在很多方面得到了成功的应用。 作为模式识别的一个重要组成部分， 文字识别技术的应用正在把人类从许多枯燥无味的 文字录入和校验中解脱出来. 虽然文字识别机器的性能还远不如人， 但是文字识别技术已 经 产生了巨大的 应用价值。 1 . 1金融票据 o c r系统 文字识别是一个很大的领域， 按照识别对象可分为两个子领域: 印刷文字识别和手写文 字识别。 由于印刷文字比 较工整和清晰， 识别系统能够分析并识别通用的印 刷文本， 如报纸、 杂志等。与印刷 o c r技术相比 较，由于书写 人习 惯不同， 实现自由 手写识别相当艰难，因 此手写的识别仅限定在小字符集识别。 文字识别系统还可以 分为联机识别系统和脱机识别系统。 联机识别系统是在书写的同时 实现识别，实际应用如p d a ,掌上电脑等。 脱机识别系统一般应用于文档识别、邮件分拣和 表格数据自 动录入系统。 由于缺少可能的笔划和同步信息， 脱机识别相对联机识别是一个更 难解决的问题。 o c r ( o p t i c a l c h a r a c t e r r e c o g n i t i o n ) 作 为 一 种 脱 机 文 字 识 别 技 术， 它 通 过 扫 描、 摄 像等光学输入方式将汉字报刊、 书籍、 文稿及其它印 刷品的文字转化为图 像信息， 再利用文 字识别技术将图 像信息转化为可以 使用的 计算机输入， 广泛应用于大量文字资料、 材料、 票 据、 档案卷宗， 文案的录入和处理领域。 适合于有大量录入、 保存、 查阅电 子文档需求的个 人或单位。 手写o c r 系统是 通过对书写字符定义字符集或词集、 书写字体等提出 足够的限制而获得 的。 有调查表明:以1 0 0 个美国城市名称作为词集， 其识别率可达9 5 % ， 若以1 0 0 0 个名称 作为词集， 则识别率降到9 0 % 。由于手写o c r 技术的限制， 专业型o c r 系统的产品多面向 特 定的行业， 即适用于大量表格信息录入的 部门， 如邮政、 税务、 海关等。 这种面向 特定行业 的专业型 o c r系统信息 格式较为固定，识别的字符集相对较小、 经常与专用的输入设备结 合使用，因此具有速度快、效率高等特点。 上个世纪九十年代， 在美国仅支票一项， 每年就有六千六百多万张。 随着现金业务的减 少， 金融系统的银行单据将成倍增加。 这些数千万甚至上亿的单据， 在数据录入工作中一般 采用人工录入，由 于录入速度慢、 错误率较高，已 无法满足信息量日 益增加的需要， 成为金 融行业计算机信息化进程的瓶颈。 我国的情况更是如此， 随着我国 金融行业的电 子化进程的 加速， 越来越多的金融票据需要采用电子化的存储形式， 同时以 信息化带动工业化总体社会 发展目 标要求更多的 企业 流程中的 业务单 据要由 计算机来处 理。 应用手写o c r系统可以 将 人们从繁忙的录入工作中解放出 来， 极大地提高工作效率。 而o c r 识别技术以 其高速、 准确、 低成本的特点，成为金融行业建立影像索引并替代人工工作的重要手段。 现在己 经有一些面向 银行的o c r 系统 1 , 幻， 它们在识别支票金额部分有 5 0 % - 7 0 % 的识 别率。 也就是说， 这些系统在提供合理可信度的条件下有5 0 % - 7 0 % 的识别率， 但同时有0 . 1 % 的误识率。 由于系统只识别了 支票的金额部分并且误识率高于手工处理的差错率， 不能满足 实用需求。 1 9 9 9年，北京邮电 大学 模式识别实验室和山东中创公司 达成协议，共同 研究开发一套 金融票据o c r 系统，并于2 0 0 1 年成功申请了国家8 6 3 重点项目( 2 0 0 1 a a 1 1 4 0 8 0 ) d金融票据 尖买笋与 一黔# d s d h i i 撰超 o c r 系统主要完成银行票据( 支票、 存款单、 取款单等) 的 稽核工作， 即 通过o c r 技术识别票 据上书写信息， 检查票面的合法性( 如大小写是否一致， 日 期是否过期等) ，目 的在于减少甚 至完全替代重复性的人工操作。 构成一个可以处理支票、 存款单、 取款单、 转账汇票等 3 0 余种票据的金融ocr 系统，系统要达到如下技术指标: 整票误识率 笔划特征点一 底部特征点， . 或者底部特征点一 笔划特征点一 顶部特征点，如图2 - 8 ; 在处理多点连写的数字时，连接的特征点顺序为: .顶部特征点一 笔划特征点一 空洞特征点一 ) 底部特征点， .或者底部特征点一 笔划特征点一 空洞特征点一 顶部特征点，如图2 - 9 a 1? 0 图2 - 8 : ( a ) 连写数字( b ) 前景背景细化( c ) 顶部( d ) 底部 ( e ) 笔划部分( f ) 空洞部分( b ) 前景背景上特征点( h ) 连接特征点得到切分线 图2 - 9多点连写数字 特征点连接顺序 该系统的细化过程， 尤其是背景细化，由于算法本身的特性， 使得运算量很大， 导致系 统速度很慢， 所以 不适合用在对实时性要求比 较高的金融o c r 系统中。 2 . 3逐步搜索的连写数字串切分算法 2 . 3 . 1滴水算法 滴水算法是通过模仿水滴在两个字符间的下落或者滚动的轨迹来构筑切分路径， c o n g e d o 1 1 于1 9 9 5 年首先提出。 根据起始点和滴水方向的不同， 可以 将滴水算法分为四 类: 从顶部左侧向 右下、 从顶部右侧向 左下、 从底部左侧向 右上、 从底部右侧向 左上。 s . a . k h a n 4 1 于1 9 9 8 年证明，采取其中的两类组合:从顶部左侧向右下和从底部右侧向左上，相当于四 类的工作。 算法涉及到三个关键步骤: ( 1 ) 起始点的确定; ( 2 ) 下一步寻址算法: ( 3 ) 从顶部左侧 关尹手写尝f功勿5 .-落2 煮 娜着手节勿 i友7 e 2 . 3 . 2动态规划算法 数字串 切分的过程实际就是寻找最佳路径的过程。 动态规划d p ( d y n a m i c p r o g r a m m i n g ) 是一种很有效的寻找最佳路径的方法， 它通过把一个n 步过程转化为n 个单步过程的方法使 算法的复杂性按对数级降低。 g . l i u 在 1 2 1 提出基于l d p ( l i m i t e d )算法的连写数字串切 分方法，对d p 算法的搜索空间、搜索方法加以限制，可以避免传统滴水算法中陷入局部最 优的问 题，同时进一步降 低了运算复杂度。以 下将详细介绍l d p 算法。 搜索空间的限制 对搜索空间加以限制主要是限制搜索空间的左右边界。 对搜索空间的限制主要是为了防 1上 不正确的切分路径的出 现， 一般都是对于书写不规整的 情况， 如开口的 0 等，同时也 缩小了 搜索范围，降低了搜索运算量。考虑字符倾斜的情况，可以计算出字符的倾斜程度， 根据倾斜度确定搜索空间的左右边界。 例如， 对于字符向 右倾斜这种一般情况， 就要左边界 放宽一些，右边界缩小一些。 代价函数 代价函数是动态规划算法中比 较重要的一个要素， 它的选取将影响到最终最小代价路径 的搜索结果。这里选择的代价函数为:穿 越笔划数( c s n : c r o s s s t r o k e n u m b e r ) 、穿越黑像 素数( c p n : c r o s s p o i n t n u m b e r ) 及路径曲 率( p c : p a t h c u r v a t u r e ) ， 它们的 优先级依次降 低，即 c s n c p n p c ，实现时只有在高 优先级的代价函 数相差不大的情况下， 才考虑次优先 级的 代价函数。 总的说来， c s n 保存切分路径上像素点的分布信息， c p n 保存切分路径上穿 越的 像素点数， 二者结合确定候选路径，而p c 则从全局角度出 发， 从候选路径中 选择最佳 路径。 搜索算法 根据 d p的原理， 可将全局最优转化成局部最优之和， 其决策过程必须是一个马尔可夫 过程， 即它的下一步行为必须完全由当前状态控制并与过去状态无关。 根据这一原理， 在计 算每一点的代价时，按照图2 - 1 3 所示方法，即每一点只能从上一行的相邻三个点中的一个 到达。 这样做的好处在于限制横向一次移动多个点的路径出现， 保持向下搜索的趋势， 减少 运算量。 当由 上一行的相邻三个点到达的代价相同时， 取中间点， 即与当 前像素点同一垂直 方向的点，以 保持路径的曲 率最小。 ( i - 1 , 一 1 ) ( i , j - 1 ) ( i + 1 , j - 1 ) ( i , j ) 图2 - 1 3 搜索方法 对于提出的三个代价函数，将最小笔划穿越数和最小黑像素点穿越数为主代价函数 ( c p n i = c s n * 1 0 + c p n ) ，决定搜索中每一步的 路径选择， 最小路径曲率为辅代价函数，只在搜 索到达底端， 在判断最小代价路径的终点， 当主代价函数相差不多的情况下， 作为判断的依 据。 2 . 4基于识别技术的连写数字串切分算法 2 . 4 . 1反复识别与切分 c o n g e d o , g . 于1 9 9 5 在 1 3 1 中 提 到的 连写 数字的切 分方法， 用到了 识别 技术。 由 于 切分 的盲目 性， 使用识别结果作为评价当前切分结果正确与否的依据， 如果无法识别， 则认为当 尖于手写者今 全 碧崖 夕 分 时班夕 之 一 一第2 薰 娜着 一尝 今 句 矽翻分 友术 前切分结果错误， 尝试另外一种切分方法， 直至找到可以识别的切分结果。 这样就在识别与 切分之间反复进行，用到的切分方法很多， 包括各种滴水算法和前/ 背景分析算法等。假设 一共有 n 种切分方法，图2 - 1 4 给出该系统的流程图。 图2 - 1 4反复识别与切分流程图 该方法使用识别器来选择切分线， 虽然基于统计的方法， 但是由于识别过程运算量非常 大， 无法满足实时性要求;同时识别器本身并非是理想的， 可能识别错误， 这样会带来错误 的叠加: 更重要的是， 该方法只能 对字块做进一步切分， 而无法判别切分出 来的是否是数字 碎片，进而做相应处理。 2 . 4 . 2滑动窗口的方法 在 1 4 中， m a r t i n , g . 描述了一种将切分过程和识别过程融合在一起的方法。 该方法使 用了一个滑动窗口， 从数字串的左侧向右侧滑动。 使用神经网络的方法识别位于滑动窗口中 间 位置的字符。 理想状态下， 数字串中的每一个字符都有可能位于滑动窗口的中间， 这样就 可以直接识别了， 而不需要严格意义上的复杂切分过程了。 为了克服滑动窗口中可能带有的 其他字符的笔画，在训练神经网 络识别器的时候， 加入噪声训练。图2 - 1 5 给出 滑动窗口的 一个示意图。 2 w、骨动窗 图2 - 1 5滑动窗口 方法示意图 这种方法表面看起来只有滑动窗口 的大体切分， 避免了 复杂的 切分过程。 但是事实上， 这是一种运算量非常大的 算法， 每一次移动窗口， 都需要用到运算量很大的神经网络的方法 来识别。 而且， 很多窗口的位置是无法识别的 ( 如在两个字符之间)， 或者对于同一个字符 可能多次识别。 如果增快窗口的移动速度， 可以减少运算量并消除一些冗余识别的情况， 但 是这样也有可能由于移动太快而造成遗漏应该识别的字符。 关子笋写尝y节勿分时适 f g 袭2 箕 珊a 计算量小的滴水等算法， 又很容易陷入局部最优。 正是由于这些原因， 有必要对 改进现有算法。 本文提出了一种对传统滴水算法的改进改进滴水算法和一种全新的多模 具算法，这两个算法将在第4 章中详细介绍。 芜子手写舒 节切分9 夕 felt 兑 二 一 ， 瑞j 肇 f ff k h lff与 勿多切分 . l ， 是 水 平的 或 有 正 斜 率 ， l ， 是 垂 直 的 或 有 负 的 斜 率 ; . l ， 和l r 不同 时 完 全 垂 直 和 完全 水 平; . 空白 部分长度必须小于门 限1 = m a x ( 1 0 , 5 .0 x m ) ， 这避免了 填补两个不同 字符之间的 过大得空白: . l ， 和l ; 交又 于中 间的 空白 部 分 区 域内 的 一点 。 图3 - 8 是一个用该方法去 边框的实例， 虽然穿越部分包含有多余的 直角， 不够平滑， 但 是并不影响后面的切分和识别。 ( a ) 原图像( b ) 去边框后 图3 一 8去边框算法实例子 3 . 2连通域提取 3 . 2 . 1垂直投影方法初步分离 所谓连通域， 是指从该区 域内 任何一个点到另外一个点的路径只通过黑 像素点， 而不经 过白 像素点， 并且该区域包含所有满足条件的 黑像素点。 在整幅图像中 确定这样的连通域， 需要一个全部图像的搜索算法。 为了缩小搜索范围， 减少运算量， 可以先用垂直投影的方法 分离整幅图像中有垂直空隙的部分。目 标像素 ( 黑像素) 垂直投影为零处， 直接用直线分离 各部分。如图3 - 9 所示。 ( a ) 原图像初步分离 图3 - 9 垂直投影初步分离 3 . 2 . 2连通域提取算法 垂直投影的方法将原图像分为几个部分， 连通域的提取将对每一个部分单独处理， 这样 就缩小了搜索范围，提高了 运算速度。 按照从左往右， 从上到下的 顺序搜索， 找到第一个黑像素点， 以 这个黑像索点为 起点开 劣夕 二尹尊 甜笋月笋 姜 夕 分 丈 冲 筋 卿 卜一袭 ，了章 演迎今扔 i p 4j l i t 始搜索与之相连的所有黑像素点， 如图3 - 1 0 ( a ) 所示。 对已 经归属某个逐通域的x - i t 素点做 标记， 以 避免再次作为 起点开始搜索。 以此类推， 找到 f 一个起点， 搜索所有相连的黑像素 点。 直至找到所有连通域， 保证图像上每一个黑像素点都有所归 属。 所有连通域的左右顺序 必须严格排列， 这样才能保证识别结果的正确顺序。 但是如果仅仅按照寻找到的起点的先后 顺序来排列左右顺序的话。 不免会出 现错误， 如图3 - 1 0 ( b ) 所示。 为了解决这样的问 题， 还 需要提取连通域几 何中心的 特征。 综合考虑起点的位置和连通域几何中心的位置， 来确定左 右排列顺序。 ( a ) 从左到右找起点 伪 ) 按 起点的先后排连通域a序可能出错 瞬 3 - 1 0找连通域起点 连通域的提取还有一个关键问 题， 如何定义相连的概念。 这:i 定义该点的正 上方、 正下方、 正左方以及正 右 方相连点， 一个像素点周围有8 个像素点， 的点， 如图3 一 h( a ) 所示。 这样的定义方法可以 完成由于毛刺， 如图3 - 1 1 ( b ) 所示。 而 其余4 个点被认为 是不相连 稍有接触的两个数字的分离， 田.圈 当 前很紊点相邻点 非相邻点 ( a ) 相邻的定义( b ) 对角线认为非相邻 图3 一 u 连通域搜素算法 33连通域属性判别 3 . 3s连通域特征提取 对于提取出来的连通域， 需要进一步判别其属性， 可能是噪声、数字的一部分、单个数 字或者多个连写数字的组合。 这里定义一个结构体来描述连通域的特征， 用这些特征来判定 属性， 结构体定义如下;( 一般连 通域为不规则图形， 为了 存储方便和便于分析， 将连通域 扩展到一个长方形区域里。) s t r u c t c o n n e c t e d - c o m p o n e n t 史 u n s i g n e d c h a r d a t a , / 1 连 通 域 中 每 个 像 素 点 信 息 i n t x l , y l : / / 连 通 域 粗 对 整 幅 图 像 的 起 始 点 i n t w , h : / / 连 通域宽 度和高 度 i n t x 2 , y 2 , / /连通域右下 角点 i n t a r e a ; 刀 连 通 域 面 积 i n t b l a c 气n u m : / / 连通域包含的黑 像素点 个数 ， ) ; 芜子手写找字节切分功解乡 之 一彰3 章 预妙理与匆步勿分 不同人使用不同的书写工具， 使得每一幅图 像的书写风格都不同。 所以对于每一幅具体 的图像， 我们都需要对其书写风格进行判断， 这里采用两个指标来描述书写风格: 估计笔画 宽度e s w ( e s t i m a t e d s t r o k e w i d t h ) 和估计字符高度 e c h ( e s t i m a t e d c h a r a c t e r h e i g h t ) 。 这里采用了一种相对简单的方法来估算这两个值。 e s w定义为该图像中所有笔画宽度的中值，e c h 定义为该图像中所有连通域高度的最大 值。 还有可能用到的一个量， 标准笔画面积s s a ( s t a n d a r d s t r o k e a r e a ) 定义为: s s a=e s w x e c h ( 3 - 1 ) 3 . 3 . 2判别数字部件 由于扫描得到的图像质量不好， 可能形成断笔， 同时书写习惯也可能造成一个数字被分 离开来， 如数字 5 。 在提取连通域的过程中， 就不可避免的 将本来属于同一个数字的部 分， 分到不同的连通域中， 这时需要重新组合被分离的 数字部件。 m i c h a e l d . g a r r i s 在 1 6 中做了 对连通域属性的判别做了 详细介绍，参考其方法， 实际 采用的流程如图3 - 1 2 所示。 图3 - 1 2连通域属性判别流程图 以下分别详细说明决策框中的判别准则: 1 . 是否噪声? 将提取一幅图像得到的所有连通域按照由小到大的顺序排列， 面积比 较小的部分是噪声 的可能性比较大。 如果( c .a r e a ( 0 .5 x s s a ) ) 11 ( ( c .w ( 2 x e s w ) ) s s a 是标准笔画面积，e s w 是估计笔画宽度。 这样的噪声可能是真正的噪声， 应该去除: 也有可能是数字内部的一部分， 应该合并到 数字里。所以后面还需要进一步判别该噪声是否位于一个数字的内 部。 2 . 是5的顶部? 比噪声大，并且满足一定条件的连通域，可以被认为是数字 5 的顶部，应该合并到 数字内。 如果满足( 顶部高度比较小腿不能太靠右被测试的部分为t ， 左边相邻部分为n ， 那么条件可以 具体为: 顶部高度比较小:t . h n .h 尖关笋写 蒸? 节tj j s m 貂3 章 朋迈理与p j ,p 切分 不能太靠右 ( t x 2 一 ” .x 2 ) m i n ( ( t .w x 0 . 5 ) , ( n .w x 0 .5 ) ) 不能太靠左 : ( n .x l 一 t .x l ) m i n ( ( t .w x 0 . 5 ) , ( n .w x 0 . 5 ) ) 不能太靠下 ( t .y 2 一 n .y l ) ( n .h x 0 . 5 ) 象破折号:( t .b l a c k _ n u m / e s w ) ( t .l + e s w ) 其中l 是连通域对角线长 度， e s w 是估计笔画宽度: h , w , x l , x 2 , y 1 , y 2 分别为结 构体中定义的成员。 3 . 是合并候选项? 这里只讨论水平重叠情况下，合并候选项的 判别。设两个待判别部分分别为c l 和c 2 : 如果( c l .x l _ c 2 .x l ) 如果由这两个特征构成的点落在直线的上方， 那么认为该连通域包含有多个数字。 很多切分 系统都是基于这种计算简单并且具有适应不同书写风格的判别方法。 标准笔画数ssc 0 0 . 5 1 1 . 5 2 2 . 5 3 3 . 5 高宽比 ( a r ) ( a ) 单字图像 。 . 飞 。:p .一 . 礼。 标准笔画数留忍 ， . 喻， 之2 日 高宽比 ( a r ) ( b ) 多字图 像 图3 - 1 4单字和多字在二维空间分布图 x -f t写 w-7 1 v ty 分/1 y o f ,一 一 - -m 4 i ff .i t 写数y沪 t v r 第4 章 连写数字串切分 金融票据o c r 系统中， 手写数字串一般是用来书写账号和日期的。 由于账号一般比较长， 书写容易形成连笔， 所以直线切分和连通域提取的方法很难将所有数字分离开来。 同时，由 于阿拉伯数字笔画很少， 对切分的准确性要求就比较高， 否则会严重影响识别结果的正确性。 所以连写数字的切分的研究，不仅成为数字串切分研究的一个重点也是一个难点。 本章详细讲述了连写区域内数字个数的估计方法， 同时给出了相邻两个数字之间的切分 参考点， 用来指导下一步的切分; 针对逐步搜索的方法， 给出了改进滴水算法， 该算法是传 统滴水的改进算法:同时讲述了基于结构特征的一种全新的切分算法多模具算法。 4 . 1连写区域内数字个数估计 连写数字所需要的切分次数由 连写区域内包含的数字个数决定，为了指导切分的进行， 应该首先估计连写区域内 所包含的数字个数。z . k . l u在 5 中提到使用基于结构特征的 神 经网络的方法来估计数字个数， 该方法虽然是基于统计的方法， 稳定性比较高， 但是方法本 身比较复杂，而且只能估计数字的个数，不能给出切分参考点。 这里首先定义上、 下边界波峰、 波谷的概念， 如图4 - 1 所示， 上边缘曲 线突起的部分为 波峰，凹陷的部分为波谷:下边缘曲线凹陷的部分为波峰，突起的部分为波谷。 功 波峰、 下边烤曲线 图4 - 1上下边界 波峰波谷定义 根据连写数字本身的 特点， 统计上边界或者下边界波峰的个数 ( 即波的个数) ， 就可以 得出连写区 域内 所包含的字符的 个数。由于开口 的 4 和开口的 0 往往会造成“ 假” 的 上边界波峰， 如图4 - 2 ( a ) 所示，并且有些连笔往往会淹没上边界波峰，如图4 - 2 ( b ) 所示。 由此可见， 字串上边界波峰往往不稳定， 所以这里使用比较稳定的下边界波峰来估计字符个 数。 民产 漏 留 ( a ) 开口 0 和 4 上边界的假波峰( b ) 连笔淹没上边界波峰 图4 - 2上边界波峰情况 求得字串的 下边界 波形后， 采用三点平滑的 方法平滑下边界波形，设 d o t i 是下边界 波形上i 点的值， 方法描述为: d o t i = ( d o t i 一 1 + d o t i + d o t i + 1 ) / 3 ( 4 - 1 ) 得到光滑的 波形之后， 如何识别波形的 波峰呢? 使用句法分析的方法来分析波形是一种 简单有效的方法， 如在 1 7 1 用句法识别的方法来对波形进行分类。 这里采用句法识别的方法 识别波形中的波峰。 波形 的 句 法: 设w = w i w 2 . . .w为 波 形的 链表 达， 其中w ; e ( p , n ,0 ) ，p代表 上 升 段， 完t手写 辫乡 之 节切分村翻 一光 二 一 ， 奈4 罩 逆写 数笋 清名 夕 分 n 代表下降段，0 代表非升非降段。 为了识别波峰，需要一个确定的有限状态自 动机，它是一个五元式 a = e . q , s , : ， f(4 - 2 ) 其 中 e = 伽 ， p ,0 ; q 一 : ， p i p 2 : : 为 初 始 状 态 ; f 一 q 是 终 il 状 态 集 合 集 : s 是从qx l 到q的映 射: s ( z , n ) = p 2 8 ( z ,0 ) = z s ( z , p ) = p i : ,5 ( p , n ) = p 2 *i ,0 ) = p i s ( p a = p i ; s 伽 2 , n ) = p 2 8 伽 2 ,0 ) 一 p 2 6 伽 2 1 p ) = p , : 利用确定的有限状态自 动机a ， 可以 很容易将波峰、波的 起始点和波的终点识别出来: 当自 动 机由p i - -) , p : 时， 是 波 峰 位 置: 当由p 2 - -) p . 时， 是 此 波 的 终点， 下 一 个 波的 起始 点。 在实际的账号书写中， 不规范的书写会产生不合理的波峰分布情况， 为了解决这种问题， 还需进一步判别波峰的合理性。 这里定义一个结构体来描述完整波形( 包括上升段和下降段) 的特征， 用这些特征来判定其合理性，结构体定义如下: s t r u c t w a v e i n t * w a v e _ d o t ; / / 波 形 上 每 一 个点 的 值 i n t x s , y s ; 刀 波形起点坐标 i n t t o p x , t o p y ; / /波峰点坐标 i n t x e , y e ; / /波形终点坐标 i n t w , h ; / /波形的宽度和波峰的高度 : 判别依据主要是基于经验值的， 为了 保证依据能够应用于 不同书写风格的数字。 这里 采 用两个指标来描述书写风格:估计笔画宽 度e s w ( e s t i m a t e d s t r o k e w i d t h ) 和估计字符高 度 e c h ( e s t i m a t e d c h a r a c t e r h e i g h t ) , e s w 定义为连写区 域中所有笔画宽度的中值。 e c h 定义 为连写区域中上下边界差的最大值。 基于经验的判别依据具体描述如下: 如果( 波峰的高 度太小 波形的 宽 度太小 两相邻波 峰的高 度值相差太大) ， 那么认为 这个波峰是不合理波峰: 波峰高 度太小:h 0 . 1 x e c h 波 形 宽 度 太 小 : w 0 .7 5 x m a x ( h l ,