（应用数学专业论文）基于识别反馈机制的多粘连字符分割与识别.pdf

中山大学硕士学位论文：基于识别反馈机制的多粘连字符分割与识别 基于识别反馈机制的多粘连字符分割与识别 专业：应用数学 姓名：李甲长 指导老师：赖剑煌教授 摘要 手写文字识别技术已广泛应用于各类智能系统。粘接文字的分割是手写文字识别的 第一步，因其分割难度之大，往往成为进一步识别甚至是整个智能系统的瓶颈，分割的 好坏直接决定了识别率的高低。通常，随着字符串个数的增加，粘连程度的增大，分割 难度也在进一步加大。目前，多粘连字符串的分割与识别现在已成为手写文字识别系统 研究的热点之一。 针对含有字符和数字的强粘连字符串的分割与识别问题，本文做了如下工作： 1 本文对初始灰度图片进行分割之前，采用了一种新的预处理方法，以求粘连字 符串分成尽可能多的几个连通区域，然后采用本文提出的字符串上下轮廓提取 方法，对预处理后的图片提取上下轮廓。得到上下轮廓后，利用k n n 分类器找到 候选的特征点，进而根据候选特征点构造出分割路径集合。 2 利用分治算法依次处理字符串图片的每个连通区域，然后对粘连字符部分使用 基于识别反馈机制的字符分割算法，筛选出最优分割路径来完成分割和识别， 再组合所有连通区域的识别结果得到最终的结果。此方法与以往算法相比，时 间复杂度在一定程度上有所降低。 3 本文采用k n n 和b p 神经网络这两种分类器做单字符识别，最终选择识别率更高的 b p 神经网络用于识别反馈。 本文的创新点是：首先我们采用一种新的预处理方法来处理灰度图片，然后利用k n n 分类器来提取轮廓特征点，随后采用了一种打分机制匹配上下轮廓特征点来构造分割路 径集合。最后，我们将遗传算法和识别反馈结合起来完成字符分割与识别。 实验结果表明，本文提出的方法在解决强粘连多字符串的分割与识别方面取得了不 错的效果，同时反馈机制的引入，也提高了识别的可靠度。 中山大学硕士学位论文：基于识别反馈机制的多粘连字符分割与识别 t h i r d ，w eu s ek n na n db pn e u r a ln e t w o r kc l a s s i f i e rt od e a lw i t hi s o l a t e dc h a r a c t e r s r e s p e c t i v e l y b pn e u r a ln e t w o r ki sf i n a l l yu s e di nt h er e c o g n i t i o na n df e e d b a c kb e c a u s eo fi t s h i g h e rr e c o g n i t i o nr a t e s o m ei n n o v a t i o n sa r ep r e s e n t e di nt h ea r t i c l e f i r s to fa l l ，w eu s ean e wm e t h o dt o p r e p r o c e s st h eg r a yi m a g e ，a n dt h e ne x t r a c tt h ef e a t u r ep o i n t sb yk n nc l a s s i f i e r a n dw ea d o p t as c o r em e c h a n i s mt om a t c ht h ef e a t u r ep o i n t si no r d e rt oc o n s t r u c tt h ec u t t i n g p a t hs e t f i n a l l y , w ec o m b i n et h e g e n e t i ca l g o r i t h mw i t h n e u r a ln e t w o r kr e c o g n i z e rt o c o m p l e t et h e s e g m e n t a t i o na n dr e c o g n i t i o n e x p e r i m e n tr e s u l t si n d i c a t et h a tt h ea l g o r i t h mp r o p o s e di nt h i sp a p e rw a se f f e c t i v ei n s o l v 崦t h em u l t i p l y - t o u c h i n gc h a r a c t e r sw i t hs t r o n ga d h e s i o n f u r t h e r - m o r e ，t h ei n t r o d u c t i o n o ff e e d b a c km e c h a n i s ma l s oe n h a n c e st h er e l i a b i l i t yo fr e c o g n i t i o n k e y w o r d s ：c h a r a c t e rs e g m e n t a t i o n , d i o d ea n dc o n q u e r , t o u c h i n gc h a r a c t e r s ，f e e d b a c k m e c h a n i s m i v i 囊i砷蓟莉剃薹睡冀妻囊蓁孽；萋主蓁霎鐾爹囊薹薹主 霎薹，茎塞茎要雾蚕萋姜鐾至萋：鬟霎喜霎霎明叁冀薹| 蓁耋薹霎； 蚕窭篓蓁i 篓妻嘉薹篓委姜萋薹耋差主雾薹霎薹霎墓薹塞霆要委 羹蓁羹羹篓鬟霎薹；雾囊冀囊冀蠢琴冀冀j 霪墓翼霪薹喜扣蠡薹 鎏薹囊薄矍i 萋篆蓁羹；誊侧霎薹篓姜攀霎萎塞霎霎霎薹藿篓；摹 萋委塞錾薹薹囊薹鬟蠹萋菱i 妻 薹鎏薹霎耋妻囊；j 墓鋈薹嘉耋妻霎篓 零蔫i 薹 学有关保留、使用学位论文的规定，即：学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有 室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩 印或其他方法保存学位论文。学位论文作者签名：巷甲欤耋雾i 砷年多月岁日 导师签名：，划 a 日 期1年多月士日日 x 第1 章引言 1 1 选题背景与意义 第1 章引言 光学字符识别技术( 0 l p t 妇lc h 觚a c t e rr e c o g i l i t i o l l ，简称o c r ) 的研究目的是使计算 机能够自动识别人手写在纸张上的字符 1 2 3 儿4 5 。文字识别技术广泛应用于各类 智能系统，如手写连体中英文字符串识别邮政编码识别，印刷字体读取转换，银行自 动读取支票，车牌识别等等。粘接文字的分割是文字识别的第一步，因其分割难度较大， 往往成为进一步识别甚至是整个智能系统的瓶颈，分割的好坏直接决定了识别率的高低。 到目前为止，尽管人们在脱机手写英文、汉字识别上投入了很多的研究而且取得了 很多可喜的成就。但还不能达到实用。在手写体数字识别这方面，经过多年研究，研究 者们已经开始把各种理论方法实用化，为手写数据的高速自动录入提供了一种解决方案。 对于非粘接手写字符串的识别，识别算法相对较简单，对于这种字符串的识别。现在很 多好的识别系统的识别率都已经接近1 0 0 。对于粘接字符串，对其进行正确的分割是文 字识别的关键步骤，文字分割的正确与否和分割效率的高低将直接影响到文字识别的正 确率和识别效率。因为如果粘接文字分割出错，则所得的识别结果也必然误差增大，一 个好的分割方法，也会使分割的效率大大提高 1 。但手写字符的识别研究有着重大的现 实意义，一旦研究成功并投入应用，将产生巨大的社会和经济效益，比如银行系统、网 络安全等。故粘接字符串的文字分割已成为文字识别研究的热点之一。 现在我们研究的o c r 所识别的对象范围很广。通常按其识别的对象字符集可以分为 汉字识别，英文识别，拉丁字母识别，阿拉伯数字识别等，以及把各种字符集组合在一 起形成新的字符串。字符集的自由度越大，字符集的类别越多，识别的过程就越复杂， 难度就越大。本文主要研究英文和阿拉伯数字混合在一起的手写粘连字符串的识别情况。 比起以前的两个字符粘连的字符串，现在字符串的粘连程度特别严重，很多相邻的字符 笔画都已经重叠在一起，有些字符串肉眼都已经无法准确识别，另外字符串字符个数的 增多以及个数的不确定性，都使分割的难度进一步加大。现在多数手写数字识别器不能 直接识别有粘连的字符，必须首先将粘连的字符分割开。因此高效可靠的分割与识别方 法是本文研究的重点之一 1 3 儿6 。 第1 章引言 该方法在连接特征点作为分割线之前，分析所有特征点的属性，舍弃无法构成正确分割 线的特征点，这样可以避免连接一些不合理的分割线。最后提取分割路径的特征，通过 混合高斯概率函数挑选出最优切分路径。 在该类方法中，需要对前景和背景进行细化操作。细化之后，提取端点和分支点等 特征点。这类方法的优点是思想比较简单，但是算法本身过于依赖字符本身的质量，往 往由于不规则的字符形态、干扰线的扰动使得算法不稳定。而且这类方法往往比较耗时， 有时会产生新的突起，从而与真正的端点和分支点产生混淆，适应性差。 1 2 3 基于滴水算法的手写字符串分割 2 0 0 3 年，p a l u 等【1 l 】中提出的滴水算法通过模仿水滴在字符粘连处滚落来构造分割 路径。它从当前位置出发，根据一系列滴水滚动规则，在相邻位置搜索路径的下一个点。 滴水算法中的关键问题是如何确定水滴滚落的起始位置和选择滴水路径，合理的滴水规 则应使得算法能处理扭曲字符分割问题。通过从上到下，从左到右扫描图像，选择同时 满足以下条件的点作为起始点；( 1 ) 、左邻接点。( 2 ) 、右边存在黑像素点。但是这种传 统滴水算法中容易陷入局部最优的问题。 刘刚等在 1 2 l 提出基于l d p ( 1 i m i t e dd y n a m i cp r o g r a m m i n g ) 算法的连写数字串分割方 法，对d p 算法的搜索空间、搜索方法加以限制，可以避免传统滴水算法中陷入局部最优 的闯题，因而是一种高效搜索算法。寻找分割路径的方法很多，其中动态规划就是一种 很有效的方法。d p 是一个多步决策的过程，可以使算法的复杂性按对数降低，此外通过 对d p 算法的搜索空间，搜索方法加以限制，会进一步降低运算复杂度。 1 2 4 基于识别技术的连写数字字符串分割 为了避免分割的盲目性，人们提出了基于识别技术的连写字符串的分害- i j 1 3 1 4 】【1 5 】。 c o n g e d o g 等- ：1 9 9 5 年在【1 5 】中提到的连写数字的分割方法，用到了识别技术。由于分割 的盲目性，使用识别结果作为评价当前分割结果正确与否的依据。如果无法识别，则认 为当前分割结果错误，尝试另外一种分割方法，直至找到可以识别的分割结果。这样就 在识别与分割之问反复进行，这时各种分割方法都可以使用，包括各种滴水算法和前背 景分析算法等。 基于识别的方法使用识别器来确定分割线，虽然是基于统计的方法，但是由于识别 3 中山大学硕士学位论文：基于识别反馈机制的多粘连字符分割与识别 过程运算量非常大，无法满足实时性要求。同时识别器本身并非是理想的，可能识别错 误，这样会带来错误的叠加。更重要的是，该方法只能对字块做进一步分割，而无法判 别分割出来的是否是数字碎片，可靠性不能得到保障。 基于识别的方法使用识别器来确定分割线，此类基于识别器去分割粘接字符的方法 称为识别器分析法，这类方法的关键在于构建识别器。识别器分析法过分地依赖于识别 器的鲁棒性，而且比较耗时，无法满足实时性要求，并且在重叠的多文字粘接字符中效 果很不好。基于识别器的技术主要有人工神经网络模型，混合高斯概率密度识别器等。 1 2 5 切分路径评价方法 粘连字符串很难一次性的得到最佳切分路径。因此构造多条候选路径，然后从中选 择出最佳路径，成为多数算法的选择。对于所有候选路径的评价主要采用混合高斯概率 密度函数和决策树【1 6 】两种方法。 y k c h e n 等在【1 0 】中使用高斯概率密度函数，使用的特征如下： ( 1 ) 、分割后的两部分的宽度比； ( 2 ) 、分割后的两部分的高度比； ( 3 ) 、分割后的左部分的宽高比； ( 4 ) 、分割后的右部分的宽高比； ( 5 ) 、分割后的两部分的黑像素比值； ( 6 ) 、分割后的两部分水平重叠部分与两部分较小宽度的比值； ( 7 ) 、路径上的黑色像素与图像宽度的比值； ( 8 ) 、路径中心与图像中心水平坐标的差的绝对值与图像的宽度的比值。 于是得到一个8 维的特征向量，人工选择最佳路径作为训练集，在训练集上用 m o d i f i e dk l l r t e a l q s 算法对特征向量进行聚类，分成2 0 类( 其中5 类为多粘连字符串，1 5 类为单粘连字符串) ，然后根据以下公式计算特征向量k 的混合高斯概率值。 其中： 盹，= 薹去唧c 一姜掣， n ， 4 第2 章常用的图像分割技术 比如边界、骨架以及凸壳等【1 7 】。经过二值化的操作之后，往往会造成笔画断裂的情况， 这就需要利用形态学闭运算来进行修补。下面介绍几个最常用的形态学操作。 1 ) 膨胀运算 膨胀是把二值图像“变胖”的操作。数学上，膨胀定义为集合运算。假设a 和b 是中的集合，则a 被b 腐蚀( 记为么ob ) 定义为： 么。雪= z l ( 君) ：厂、么g 其中b 为结构元素。这个公式是以a 到b 的相对于它自身原点的映像并且由z 对 映像进行位移为基础的。a 被b 膨胀是所有位移z 的集合，这样曰和a 至少有一 个元素是重叠的。从而可以将以上定义写为： 么。艿= z i 【( 召) ：r 、彳】a 2 ) 腐蚀运算 腐蚀是把二值图像“变瘦 的操作，它可以看作膨胀的对偶操作。像在膨胀中一样， 收缩的方式和程度由一个结构元素控制。对z 中的集合a 和b ，使用b 对a 进行腐 蚀，用么 b 表示，并定义为： 么 四= 仁l ( 召) ：a ) 即使用b 对a 进行腐蚀是所有b 中包含于a 中点z 的集合用z 平移。 膨胀和腐蚀对于集合求补运算和反射运算是彼此对偶的，即： ( 彳 b ) = 么。o 召。 3 ) 形态学开操作 开操作一般使对象的轮廓变得光滑，断开狭窄的间断和消除细的突出物。 使用结构元素b 对集合a 进行开操作，表示为么o b ，定义如下： 彳。曰= ( 么o _ 功。曰 即先用b 对a 进行腐蚀，而后用b 对结果进行膨胀。 4 ) 形态学闭操作 闭操作同样能使对象的轮廓变得光滑，而且消除狭窄的间断和细长的鸿沟，消除 小的孔洞，并填补轮廓线中的断裂。 使用结构元素b 对集合a 进行必操作，表示为彳曰，定义如下： 9 羹雾鍪霾薹雾蓁蓁薹攀蓁蓁蓁雾 蒿羹羹i 薹妻鎏一羹驰蓁釜! 崩们薹羹羹薹塞蒌霎鬟；拿拿三蓁| 羹 l 雾妻i蠢篓藿囊霪耄霎霎露冀一蠹攀羹篓囊薹孽墓萋囊垂；霎薹”妻甫i 囊鋈j 妻羹。薹萎。翼囊冀霎釜一囊薹雾 | 譬茎羹霎割蠡。蒌囊5 萋搴薹囊。= 霪萎薹雾奏奏雾蔓薹璧蓑萋霎善冀塞；萎萋薹奏雾囊蓦= 羹毒霎螽；鋈薹雾薹：餮嘉 茎蚕；壅篓蚕一墼薹鋈耋r 霪薹蠢j 莹塞蓁一萋薹霪。萋妻萋茎囊耋，鬓鍪薹；誓鋈蓥蠢重蚕霎冀雾：蠢妻霎耄奏 篓喜霎毒蓁蚕；主蠹謦j 藿薹霾誊i 季雾奏薹薹薹季孽妻二蒌季祷娶，蓁雨么薹| 。型5 霎5 薹蓥；霎耄鋈囊。羹 萋薹 薹孽耋爹蓁= 孛嘉萋薹垂j 童酲。萎妻茎羹霪；篓蚕萋萋囊； ：薹萋篓i霎耋萋翼薹羹霎囊薹耄篓 薹薹薹；薹茎蓁萋薹；耋墓霉蓁一薹i 鍪鬟薹鬟蠹；誊咔釜譬奏 ；耋萋薹囊囊霎羹蓁氐= 蓁薹垂姻霎墓蓁塞錾 水算法，以及用 动态规划法改进的滴水算法；三是基于识别的字符分割算法。下面分别详细介绍其中具 有代表性的分割方法。( 一)基于前 景信息的分割方法基于前景信息 的方法是分析二值图像前景信息(黑像素点)，以找到正确的分割线。该类方法主要有两种：一是n w s t r a t h y 等【萋l 于1 9 9 3 年提出的轮廓分析的方法，二是z s h i 等【8 】于1 997年提出的笔划分析的方法。nwstr a t h y 等【7 】的算法是：( 1 ) 轮廓分析得到s c p s ( s i g n i f i c a n tc o n t o u r points)；(2)scp s 成对进行排序；( 3 ) 连接入口s c p 和出口s c p ，完成分割。轮廓分析分别 确定出轮廓线上的敞开部分、山峰部分、山谷部分以及空洞部分(图21)，满 足如下任何一个条件的点为s c p ：每一个山峰 的最大点每一个山谷 的最小点沿山峰或者 x 中主= 企翼琴叫攀蜀8 萎堕蚕园鼋州艟i 冀澎嚷圃馨隙曼震静雾 萋弥囊挺矍= 辐抬雾篓薹薹薹薹薹霎；萎写囊娄蓁蓥| 鋈藿嘉霪誊墓蓄 少l l l 耋萎翼。冀薹薹坚川l 蠹l 薹鬟薹琴囊萎羹慕矍，冀冀二萋雨量 菰篙贸珏韧实铆蘑青图羹葫翥；踞萌篓霎隧薹雨营酎薹翼堑； 霎夏妻霎萎蓁r 霆；霎薹| 囊篓蓁首墅囊薹篓夔塞奏茎雾雾霎萋一 薹霎荔篓： 囊薹警鍪蠢霎蠢萎 奏h 蒌耋薹霞囊薹囊；| 蓁霎萎萎委囊薹鍪= 羹薹霎篓姜蓬羹 薹：冀疆羹萋鎏萋雪霎薹羹薹羹羹；薹耋薹翼蠢蓄鍪妻；摹羹薹曩 耄妻薹雾。嚣篓孬奏霎耄霎霪薹蓁塞霹霎薹霎羹薹蓁冀望。2 雾 羹霎摹霎萋篱霎霎蓬謇薹萋霎窭霎；翼蓁霎。霎荔2 篓妻= 薹蠢羹 饕囊霎霪璧冀薹妻雾蓁翼薹薹，墓霉霪曩霎薹喜霪霎j 羹蓁耄奏 霎霎堕雾薹襄蠢霎2 荔蓁4 ；耋雾雾霎委一霎霪薹薹篓羹，蓁孽p 蓉 羹。霪蓁雾霎5 ：圣窭薹鋈襄篓羹霎妄薹雾，雾蚕一冀薹；一妻薹萎 中山大学硕士学位论文：基于识别反馈机耕的多帖连字符分瓤与识别 o l i _ 一 ( 1 ) ( 2 ) ( 3 ) 一1 ， 一渤 ( 4 )( 5 )( 6 ) 囱27 倚统滴水算法移动规划示孽田【1 1 】 数字串分割的过程实际就是寻找展佳路径的过程。动态规划d p ( d y n a m i c p r o g r a m m i n g ) 是一种很有效的寻找琅佳路径的方法，它通过把一个n 步过程转化为n 个单 步过程的方法使算法的复杂性按对数级降低。刘刚在| 1 2 1 对传统的滴水算法进行了改进， 提出基于l d p ( l i m i t e d ) 算法的连写数字串分割方法，对d p 算法的搜索空问、搜索方法加 以限制，可雌避免传统滴水算法巾陷入局部最优的问题同时进一步降低了运算复杂度。 ( 五) 基于识别的分割方法 c o n g e d og 等于1 9 9 5 在文献i l5 】巾提到的连写数，的分割方法，用到了i ! 别技术。 由于分割的盲日性，使用识别结粜作为评价当前分割结果j f 确与否的依据，如果无法t 别，则认为当前分割结果错误，尝试另外一种分割方法，直至找到可以识别的分割结果。 这样就在识别与分割之间反复进行用到的分割方法很多，包括各种滴水算法和前背最 分析算法等。该方法仕用识别器来选择分割线虽然基于统训的方法，但是由于识别过 程运算量非常大，无法满足实时性要求；同时识别器木身并非足理想的，可能识别错误， 这样会带来错误的叠加：型蕈要的是醵方法只能对字块做进一步分割，而无法判别分 割出米的是否是数字碎片，进而做相应处理。 在文章1 2 0 1 中，m a r l i n ，g 描述了种将分割过程和识别过程融合在一起的方法。该方 法使用了个滑动窗口，从数字串的矗侧向右侧滑动。使用神经网络的方法识别位于滑 动窗e 1 中间位置的字符。理想状态下，数字串中的每一个字符都有可能位于滑动窗口的 中间，这辑就可以直接识别了，而不需要严格意义上的复杂分；4 过程了。为了克服滑动 窗口中可能带有的其他字符的笔画，在训练神经网络识别器的时候，加入噪声训练。这 种方法表面看起来只有滑动窗口的大体分割，避免了复杂的分割过程。但是事实上，这 是一种运算量非常大的算法，每一次移动窗口部需要用到运算量很大的神经网络的方 第2 章常用的图像分割技术 法来识别。 鉴于过切分在手写英文字符串中的有效应用，雷云等在【1 3 】中引入了一种新的基于识 别的粘连手写数字串切分方法。此系统结合轮廓分析和投影分析寻找候选切分线，克服 了一般的轮廓分析方法无法找到平滑过渡区域的切分点的问题。然后，为所有候选切分 结果和其对应的书写风格建立一个概率模型，同时嵌入了单个数字分类器。利用最大后 验概率准则，选取最优的切分结果。在搜索最优切分结果时，还使用了剪枝算法，降低 了系统的时间和空间复杂度，从而实现了系统的实时性。文【1 3 】提出的基于反馈识别的分 割算法就是找出最优的识别结果对应的分割方案作为最优的分割路径。根据最大后验概 率准则，定义最优切分方法为： k = a r g m l a x m z a x l o g p ( z ，li ，) 】) = a r g m a x m a x l o g p ( zll ，) 尸( 三ij ) 】 = a r gm a x m a x l o g p ( zi1 ：，) 尸( ；z 1 ，j 2 ，川l 纠) ) = a r gm a x m a x l o g p ( zll ，i ) o 尸( i ，) p ，2 ，j 一ln ，) ) ) 我们假设字符串z 可表示成n 个彼此独立的字符z l ，z 2 ，- 磊，则可推导 nnn p ( z i l ，) = 兀p ( 乙i 三，) = 兀p ( 互i ) = 1 - i u ( ，互) i = lf = ls = i 在上式中，p ( n id 表示给定图像i 时，z 中包含n 个字符的概率。在给定n 和 i 后，p ( j r l ，2 ，- 1i ，) 是切分线j 1 ，2 ，肛1 的联合概率，它在本质上，反映了手写 字符串属于某种书写风格的概率，这里的书写风格指的是数字字符串中所有字符模 式在l 中的位置和大小属性。可利用模糊隶属度函数对烈lj ) 和p ( 1 i , z 2 ，j 肌1l ，d 进行估计。 1 7 中山大学硕士学位论文：基于识别反馈机制的多粘连字符分割与识别 ( 1 ) 、丢失灰度图中的许多有用信息。( 2 ) 、简单粗糙，分割难度大。 针对以上提到的情况，我们分析了字符串图像的特点，采用了一种新的预处理方法， 即先将灰度图像处理，尽量将粘连的字符分割开，然后使用动态阈值将处理后的灰度图 像二值化，得到在分割阶段我们将要使用的二值图像。该算法的具体流程如下： ( 1 ) 使用如下的一个5 拳5 的掩膜对灰度图像进行处理 一1一ll l一1一l 2 4一ll l一1一l lll 记处理后的图片为g ，得到g 的灰度最小值1 0 w 和最大值h i g h ，使用公式g _ ( g l o w ) l l i 曲将灰度图像归一化到区间【o ，1 】，然后转化成2 5 6 的灰度图g ，找 出图片g 中背景灰度，即g 的灰度比例最高的那个灰度值，记为垤。 ( 2 ) 分别以b g 一1 和b g 一1 0 为阈值( 其他值亦可) ，把g 转为二值图，并去小洞，得到 的图片，在下文中分别记为图a 和图b 。 ( 3 )比较a 图与b 图可以发现：a 图分割得不明显，有较多干扰信息；而b 图则 该割之处基本都能割裂，但孔洞较多。因此我们可以利用a 图来优化b 图， 把b 图相对a 图新增孔洞填充掉。 ( 4 ) 修复不合理断肢。对于小于一定像素数且与其他连通分支只有“一墙之隔 的连通分支，判断为不合理的断肢。修复时将其与其他连通分支间的细缝补 上( 该细缝在灰度图中颜色较“深 ，方可填充) 。 ( 5 ) 把原图中接近全黑的点，赋为1 。去毛刺、内部小孔及内部裂纹。去内部小孔 时，首先对小于一定大小的孔洞进行填充。但字母中的一些狭长裂缝，则参 考连通区域的平均宽度进行填充 ( 6 ) 通过动态阈值方法将上面得到的灰度图像直接二值化，转化为二值图。 下面用图3 1 来说明新的预处理方法的步骤。 第3 章多粘连字符串的分割与识别 3 2 连通域分割法 本文中我们采用的像素连通是四连通。经典的求连通方法是连通域生长法【1 7 】， 使用的是如下的递归算法 ( 1 ) 扫描图像，找到没有标记的像素点，对其进行标记； ( 2 ) 递归标记该点的邻点； ( 3 ) 如果不存在未标记的点则停止； ( 4 ) 返回第( 1 ) 步执行； 递归方法在形式上是很简单的，但是效率很差。下面还有一种算法，可以在较小 的时间复杂度内完成连通域生长法的计算，具体算法如下： ( 1 ) 自左至右，自下而上扫描整幅图像，找到第一个未标记的像素点； ( 2 ) 初始化像素队列为空； ( 3 ) 把该像素点做标记，加入队列； ( 4 ) 搜索队列头像素点周围邻域的像素并标记，加入队列； ( 5 ) 删除队头元素； ( 6 ) 重复( 3 ) 、( 4 ) 两步，直到队列空为止； ( 7 ) 返回第( 1 ) 步。 连通域分割法的特点是不会受到图像倾斜的影响，定位精确。经过预处理的图像被 分成几个连通区域，通过连通分量提取，就可以将一个长的字符串图像分割成几个子图 像，从而利用分治法依次分割每个子图像，组合得到最终的识别结果。 3 3 基于反馈的粘连字符分割方法 本文提出了基于识别反馈的多粘连字符分割算法。该算法首先通过本文的方法提 取字符串的上下轮廓，在轮廓上提取特征点，然后构造可能的分割路径，最后利用遗 传算法和识别器置信度反馈来决策出最佳分割路径。本文分割算法的大致流程图见图 3 3 。 中山大学焉士学位论文：基于识剐反馈机科的多帖建宇符分割与识别 f pb o o t t o t n f p 【n 】；存储下轮廓特征点 ( c ) 图34 轮廓特征点提取( a ) 二值化图片( b ) 上下轮晦点集合，其中红色为上轮廓，绿色为下轮廓k ) 轮廓特征点其中红色为上轮廓特征点蓝色为下轮廓特征点 3 3 2 分割路径集合的构造 经过卜西】的步骤已经得到上下轮廓的特征点序列，f 一步就是要按照一定的规则连 接上下轮廓的特征点来构造分割路径集台。这里采用的分割是个过分割策略。如果这 些分割路径巾包含能够正确分割字符串图像的路径。那么就认为对这个字符串的过分割 是合理的。 f 面介绍分割路径的构造流程。 ( 1 ) 遍历上轮廓的所有特征点，对于上轮廓的每个特征点【。州，j 寻找与其匹配 的下轮廓的特征点“y ) ，其中( x ，y ) 满足式( 3 1 ) 。如果同时存在多个符合条件 中山大学硕士学位论文：基于识别反馈机制的多粘连字符分割与识别 3 3 3 利用识别反馈筛选最优分割路径 利用上面的方法，已经构造出了分割路径集合，从而完成了对一个字符串图像的过 分割，下面要讨论的就是从所有可能的分割路径中筛选出最佳分割路径，这也是非常关 键的一个步骤，这将直接决定分割结果的正确性。 这一节主要是利用遗传算法，同时结合神经网络模型的识别反馈对整个分割路径集 合进行筛选，筛选出最优路径，从而完成对粘连字符串的分割。 假设有刀条路径，那么就可以构造出2 ”个分割假设，即2 ”个分割路径组合。当刀比 较大时，如果采用穷举搜索法来寻找最优分割路径，将会有非常大的时间开销，这是不 可行的。许多研究者使用d p 来寻找最优分割路径。如文 2 2 1 使用单字符分类器产生的积 累相异性度量来评估不同的路径。因为字符串的长度预先是未知的，实验结果表明这种 算法仅局限于短的或者分割路径少的字符串。文【2 2 】中试图用平均路径得分来对应路径的 长度。但是因为平均路径得分是非单调的，所以没法保证通过平均路径得分搜索到最优 路径。 为了弥补上面提到的问题，我们采用遗传算法( g a ) 作为搜索算法，从候选分割空间 中筛选出最优的分割路径。随着问题规模的增大，组合优化问题的搜索空间也急剧增大， 有时在目前的计算机上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到 应把主要精力放在寻求满意解上，而g a 是一种寻求这种满意解的最佳工具。g a 是一种 受生物进化启发的学习方法，它不是从一般到特殊或从简单到复杂地搜索假设，而是通 过变异和重组当前已知的最好假设来生成后续的假设。每一步更新被称为当前群体的一 组假设，方法是使用当前适应度最高的假设的后代替代群体的某个部分。这个过程形成 了假设的生成测试的柱状搜索，其中若干个最佳当前假设的变体最有可能在下一步被考 虑。实践证明，遗传算法对于组合优化中的n p 问题非常有效。g a 不但计算简单，同时 功能强大，在解决像不连续空间的最优化或者多峰值目标函数的问题时，它是一种鲁棒 性的搜索技术。它有许多功能强大的操作，像选择、繁殖、交叉、变异。g a 首先根据问 题域中个体的适应度大小选择个体，并借助于遗传算子进行组合交叉和变异，产生出适 应性更好的新种群。这个过程将导致后代种群比前代更加适应于环境，末代种群中的最 优个体可以作为问题近似最优解。 我们知道对于一个含有i 条候选分割路径的集合总共可以产生? 个分割路径组合。 第3 章多粘连字符串的分割与识别 这里把每个分割路径组合用一个含有疗个基因的二值染色体来表示。当第m 基因为0 时， 说明舍弃了第m 条分割路径，也就是第m 条分割路径没有在这个分割假设中考虑。相反 的，当第m 基因为1 时，说明第m 条分割路径在这个分割假设中，即用来分割字符图像。 分割假设都可以表示成二值染色体，这样就可以很方便的使用选择、交叉、变异等遗传 操作来筛选最优分割路径。选择是指确定在某一代中哪些染色体可以作为父本为下一代 提供遗传信息。到这里为止，我们都假定染色体已经打分，并且按照适应度高低排序和 选择，直到生成下一代为止。这有利于种群向着得分高的方向进化。因此选择的本质是 筛选，它的功能就是定向进化。经过选择算子多次的定向积累，种群中的个体就会迅速 向使目标函数值高的区域靠拢，形成高质量的种群。交叉是把两条染色体混合或配对的 过程，得到两条新的染色体。在染色体上随机确定一个位置并截断，将彳染色体的第一 部分与b 染色体的第二部分连接，另一半也如此。变异是允许每个位以一个很小的概率 改变自身，比如从0 变成l ，或者相反。这里应用最简单的一些遗传算子，比如轮盘赌 方法选择、随机单点交叉、随机单点变异。本文使用的适应性函数是按照如下几个公式 来确定的： c h a r l = “1 勘c h a 刀r l 嚣裂职别成功 l+ l 。识别错误 r e c w r o n g r a t e = ( c h a r n u m - c h a r s r i g h t ) c h a r n u m o b j v a l u e ( g i n d e x ) = ( c h a r l c h a r n u m ) 宰r ec w r o n g r a t e f i r ev a l u e ( g i n d e x ) = 2 - o b j v a l u e ( g i n d e x ) 其中幽a m u m 是分割路径分割出的子图片的个数，c i n d e x = l ，2 ，i c h a r n u m ； r ec w r o n g r a t e 是误识率； o b j v a l u e ( g i n d e x ) 是第g i n d e x 个种群个体的目标值，g j n d e x = 1 ，2 ，初始种群数目； f i t n v a l u e ( g i n d e x ) 是第g i n d e x 个种群个体的适应度。 分割模块主要由两个部分构成：连通区域分析及粘连切分。在连通区域分析阶段， 一个字符串被视为连通区域的组合。观察表明，有三种不同类型的连通区域：被过分割 的字符碎片，孤立的字符，以及粘连字符。我们需要对第三种情况进行切分。观察表明， 粘连字符的宽度一般大于其他两种类型的连通区域。如果一个连通区域的宽高比( 即该 连通块的宽度连通块的高度) 低于一定阈值( 根据实际图像库确定一个阈值) ，则认为 中山大学硕士学位论文：基于识别反馈机制的多粘连字符分割与识别 是一个独立的字符( 或者是分割造成的字符碎片) ，否则认为是粘连的字符。在粘连字符 切分模块，所有的连通区域都基于这一准则进行分类，只有当满足粘连字符的情况时才 对其进行进一步分割。上面所述的分析模块避免了对许多孤立字符的过分割，从而节省 了很多计算时间，同时也避免了很多由于对独立字符过分割而造成的错误。 图3 6 每个连通区域的分割识别流程图 经过上一章的预处理后，每个字符串图像都可以分成几个连通区域。对于一个字符 串的连通区域，下面介绍分割的具体流程：( 1 ) 首先用神经网络识别器来识别这个连通 区域，如果识别为合理的字符，说明成功，则继续处理剩下的连通区域。如果神经网络 第3 章多粘连字符串的分割与识别 不能识别这个连通区域，则进入分割过程。( 2 ) 如果这个连通区域没有任何分割路径， 则说明连通区域识别错误。( 3 ) 如果这个连通区域有且只有一条分割路径，则用这条路 径把此区域分成b wl c i t 和b wr i g h t 两部分，如果b wl e i t 和b wr i g h t 都识别正确，则此 连通区域识别正确，否则直接刷掉该图片。( 4 ) 如果这个连通区域有两条或两条以上的 分割路径，就利用基于识别反馈的遗传算法，来筛选最优分割路径，达到对这个连通区 域的分割。对于每个连通区域的分割过程可用图3 6 的流程图来表示。 因为本文所研究的字符都是变形比较大的，扭曲程度比较严重，而且笔画的粗细大 小也不一致，所以使用一般的模板匹配法是很难正确识别的。针对这种情况，本文在字 符识别部分采用了现在经常使用的两种字符识别方法，一种是神经网络，一种是k - 近邻 分类法，然后根据各自的实现过程和识别率对这两种方法进行比较，通过实验结果我们 得到在处理本文的字符时神经网络的识别率比较高，所以选用神经网络识别器用来做识 别反馈。 3 4 神经网络识别法 近年来，人工神经网络( m 州) 以其抗干扰、容错、自适应、自学习能力强、识别 速度快等特点受到人们的广泛关注。神经网络进行字符识别的基本原理就是利用神经网 络的学习和记忆功能，先让神经网络学习各个模式类别中的大量学习样本，以记住各模 式类别中的样本特征，然后在识别待识别样本时，神经网络会回忆起之前记住的各模式 类别的特征并将他们逐个与样本特征相比较，从而确定样本所属的模式类别。 人工神经网络是由人工建立的以有向图为拓扑结构的动态系统，它通过对连续或断 续的输入作状态相应而进行信息处理。神经网络的推导过程严谨，物理概念清晰，通用 性强，具有很好的分类性。现有的研究情况表明，用神经网络的方法进行字符识别是可 行的，识别的正确率很高。但是网络的训练比较麻烦，样本的选择很重要，需要大量的 样本才能保证最终识别结果的正确。神经网络模型主要有：h o p f i e l d 模型， b o l t z m a n n 机，a d a l i n e 模型，b p 网络。文字识别技术中所用到的神经网络模型可以有b p ( b a c k p r o p a g a t i o n ) 算法，考虑到模拟实现的方便性和b p ( b a c kp r o p a g a t i o n ) 的模式识别特性，本 文的识别反馈采用基于b p ( b a c kp r o p a g a t i o n ) 的算法来进行的。 3 l 中山大学硕士学位论文：基于识别反馈机制的多粘连字符分割与识别 3 4 1b p 神经网络的设计 本文采用了三层的b p 神经网络作为分类器，其实现用到了m a t l a b r 2 0 0 7 a 的n e u r a l n e t w o r k st o o l b o x ( m a t l a b 神经网络工具箱) ，可以方便地构建b p 网络。b p 学习算法的基 本思想是学习过程由信号的正向传播与误差的反向传播两个过程组成。正向传播时，输 入样本从输入层输入，经各隐层逐层处理后，传向输出层。若输出层的实际输出与期望 输出的( 教师信号) 不符，则转入误差的方向传播阶段。误差的反传是将输出误差以某 种形式通过隐含层向输入层逐层反传，并将误差分摊给各层的所有单元，从而获得各层 单元的误差信号，此误差信号即作为修正各单元权值的依据。这种信号正向传播和误差 反向传播的各层权值调整过程，是周而复始地进行的。权值不断调整，也就是网络的不 断学习，这个过程一直进行到输出误差减小到可接受为止，或进行到预先设定的学习次 数为止。图3 7 是本文使用的三层感知器模型。 目标向量f 2 输出向量 输入模式 图3 7 三层感知器 输出层 隐含层 输入层 本文直接用已有的b p 神经网络程序，对新库的单字符重新进行训练测试，得到一个 满足新的图片库要求的字符识别系统，然后将此系统用于识别反馈【2 3 】【2 4 】 2 5 2 6 2 7 1 。 下面我们简要介绍这个文字识别系统。首先对单字符图片分别进行特征提取【2 9 】【3 0 】，其 中包括基于k i r s c h 算子的小波特征、基于m a t 变换的方向特征、p r e w i t t 梯度特征、图像 距离特征、中值滤波梯度特征、外轮廓链码特征、和字符结构特征。因为上述几类特征 值的动态范围是不同的，因此直接拿混合特征来做分类并不能反映它们所具有的重要程 第3 章多粘连字符串的分割与识别 的就是选定样本进行训练。首先从我们研究的字符图片中分割出单个字符，把分割出的 字符分类，分别存放在对应的目录中。本文人工“制造 出一些能传达更多信息的训练 数据，比如我们将图像旋转以“制作出新的训练点，这样可构成一个更大的训练集。 网络训练完毕后，把网络的参数和计算出的权值存在a n n t r a i n p a r a a l l m a t 文件里，供字 符识别时调用。 3 5k 一近邻分类法 近邻算法是分类算法中比较常用的一种方法【2 5 】。k - 近邻法( 简称k n n ) 是最近邻 法的一个推广，是基于统计的分类方法。k n n 的思想是根据测试样本在测试空间中k 个 最近邻样本中的多数样本的类别进行分类。它非常直观，无需先验统计知识等特点，从 而成为非参数分类的一种重要方法。 假定k - 近邻分类法的所有例子都在n 维空间中，一般每个例子x 被表示为特征向量 ，这里q ( 功表示例子x 的第i 4 分量。两个实例薯，x j 之间的相似度 量我们采用的欧式距离。 本文引入k 近邻分类器，主要是来和a n n 作对比，选择识别率比较高的分类器用于 本文的识别反馈，k n n 的算法如下： ( 1 ) 本文所使用的训练样本都已经明确了它们所属的类别。 ( 2 )以训练集的分类为标准，对每个测试样本寻找k 个近邻，采用欧式距离作为 样本问的相似程度的度量标准。一般近邻可以选择1 个或者多个。 ( 3 ) 测试样本的最终输出为近邻类中个数最多的那一类。 对每个待分字符，本文提取了和b p 神经网络一样的特征向量，作为样本数据。这里 取k = 3 ，在实验部分本文对比了a n n 分类器和k n n 分类器的分类结果。由于总体上a n n 的分类效果要优于k n n ，故本文采用的a n n 分类器来做识别反馈。 3 5 第4 章实验结果与分析 第4 章实验结果与分析 为了测试和评价本文提出的算法的好坏，本章着重讲述用本文的算法对含有2 8 类字 符的1 0 0 0 幅多粘连字符串图像进行分割和识别，并统计出分割结果，同时对于算法中的 关键步骤我们都用实验进行了分析，给出了实验数据。 4 1 实验数据说明 本文主要研究含有多字符的多粘连字符串的分割识别，其中每个字符串图片一般含 有6 8 个字符( 包括字母、数字) ，如图4 1 所示是部分样本。 图4 1 多粘连字符串图片 为了测试本文提出的算法的性能，搜集了1 0 0 0 幅含有多字符的粘连字符串图片。本 文的实验部分都是基于这些字符串图片来进行的。 4 2 实验设计 对于两字符粘连的情况，y i - k a i 在文 1 0 1 中做了详细的介绍，并且取得了不错的效果。 但本文主要研究的是粘连多字符串，这种情况是相当复杂的，因为这些字符间既存在单 粘连情况，也存在多粘连情况，并且字符问粘连程度非常高，甚至有些字符笔画直接冲 叠在一起，人眼都很难正确分辨出。 首先，将一般的预处理方法和上述算法所得到的效果做个对比。通过图4 2 ，我们可 以看到本文使用的预处理方法有明显的优势，经过这种方法处理后的字符串更加容易辨 认，而且原本粘连的字符串图像现在变成了几个连通区域。图4 2 ( a ) 经一般的预处理后， 得到图4 2 ( c ) ，通过连通区域提取法可以从4 2 ( c ) 中提取出三个连通区域。而用新方法得 到的图4 2 ( e ) 含有四个连通区域，这样就更利于后期的处理。图4 2 ( b ) 得到的图4 2 ( d ) 含有 两个连通区域，而用本文方法得到图4 2 ( 0 含有四个连通区域。通过实验，我们可以看出， 新提出的预处理方法比一般的预处理方法更能有效地用于后期的分割，因为这种预处理 中山j = 学硕士学位论文：基于识别反馈机制的多粘连字符分割与识别 方法一般是将原始图像分成几个连通区域，然后再依次分割每个连通区域内的粘连部分 大大减少了分割的难度。 胂蛾 ( a ) 原始图( b ) 原始图 ( c ) 一般二值化图片 ( d ) 般二值化图片 ( e ) 新的顶处理图片 ( f ) 新的预处理图片 固42 两种顶处理方法的对比图 当然这种新的预处理方法还有些不足，有些图像经过预处理后会把原本一个完整 的单字符分割成两个部分，像h ，w 等。图43 是一个分割错误的例子，在囤43 中w 被分到了两个连通区域，直接导致了最终的识别错误。 圈43 原围( 左) 以及预i 臼里错误的图片( 右 本文我们还提出了一种新颖的特征点提取方法，利用k n n 分类器来自动区分上下轮 廓上的特征点与非