（计算数学专业论文）图像处理：基于概率的字符识别系统的若干问题研究.pdf

捅要 字符识别是模式识别的一个重要方面，在信息处理，办公自动化，邮政系统， 银行系统等方嚣有着重要的使用价值和理论意义。 本文主要对字符识别系统中基于概率的提取方法进行了研究，其中包括对文 本行的提取、块的提取和词的提取，并对字符识别预处理中的两个问题：图象二 值化和倾斜字体校正的几个方法的优劣进行了讨论和试验模拟，并最终为我们的 字符识别系统确定了相应的方法。相关内容如下； 对于我们的字符识别系统的识别流程作了简要介绍，并对以往的提取方法作 了简单回顾和评论，进而提出提取算法应该建立在数学模型而不是经验的基础上。 建立了提取算法的概率模型且给出了相关的算法，并详细讨论了算法的每一 个步骤。简要介绍了图象处理中常用的投影算法用于行的提取。对我们所给出的 提取行的算法进行了实验模拟，并将实验结果与投影算法的结果进行比较和分析 后选取了基于概率的提取方法。介绍了块提取算法和相应的步骤。介绍和讨论了 “细胞计数方法”用于对文中所涉及的概率的计算。 基于所建立的概率模型给出了字符识别系统中词的提取算法并对其进行了实 验模拟并对模拟结果进行了分析和讨论。 对字符识别系统中预处理中的二值化方法进行了讨论，进而提出了背景闽值 方法并且介绍了算法的步骤，对本方法和o s t u 方法进行了实验模拟和对比分析， 通过比较我们选择了背景阈值方法。介绍了基于链码统计的倾斜字体校正方法， 并将此方法与梯度法的实验结桑进行了比较，结果前者效果更好。 关键词：字符识别基于概率细胞计数二值化倾斜校正 a b s t r a c t a sa m a j o rp a r to fp a t t e r nr e c o g n i t i o n ，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 ) p l a y s i m p o r t a n tr o l ei na r e a ss u c h a si n f o r m a t i o n p r o c e s s i n g 、o f f i c ea u t o m a t i o n 、p o s t o f f i c e s y s t e ma n db a n ks y s t e m 。 t h i sp a p e rf o c u s0 1 1t h e s t u d yo ft h ep r o b a b i l i t yb a s e de x t r a c t i o nm e t h o dw h i c h i n c l u d i n gw o r d ，t e x t l i n ea n d t e x tb l o c ke x t r a c t i o ni no u 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 ns y s t e m i np r e p r o c e s s o f o c r ，s e v e r a l m e t h o d so ft h et w o p r o b l e m s ：i m a g eb i n a r i s a t i o na r e a l s od i s c u s s e d ，t h u s c o r r e s p o n d i n gm e t h o d s a r ef i n a l l y s e l e c t e da n dd e t e r m i n e d w h a tf o l l o w si st h eo u t l i n eo f t h et h e s i s ： f i r s t ，t h e a u t h o ri n t r o d u c e st h ep r o c e s so fo u ro c r s y s t e m a n dm a k e sab r i e f d e s c r i p t i o no f t h ee x t r a c t i o nm e t h o dt h e nh ep o i n t so u tt h a te x t r a c t i o nm e t h o ds h o u l d r a t h e rb eb a s e do nm a t h e m a t i c a lm o d e lt h a ne m p i r i c a lm o d e s e c o n d ，p r o b a b i l i t ym o d e la n di t sa l g o r i t h ma r ep r e s e n t e d ，w i t he m p h a s i so nt h e d e t a i l e ds t e p so f t h ea l g o r i t h ma n dt h ep r o j e c t i o nm e t h o di sb r i e f l yi n t r o d u c e di no r d e r t oc o m p a r ei t se x p e r i m e n tr e s u l tw i t ht h a to fo u r st h ec o m p a r i s o no ft h et w om e t h o d s f o l l o w st h a tp r o b a b i l i t yb a s e de x t r a c t i o nm e t h o di sb e t t e rt h a np r o j e c t i o nm e t h o dt h e a p p l i c a t i o n o fo u ra l g o r i t h mi nb l o c ke x t r a c t i o n i sa l s oi n t r o d u c e d c e l l c o u n t ”m e t h o di si n t r o d u e dt oc o m p u t et h ep r o b a b i t ya p p e a r e di nt h ep a p e r t h i r d ，b a s e do nt h em o d e lw e h a v ep r e s e n t e d ，w o r de x t r a c t i o nm e t h o di sd i s c u s s e d a n dt h ea n a l y s i so f i t se x p e r i m e n tr e s u l ti sm a d e f i n a l l n w ed i s c u s s e ds e v e r a lm e t h o d so fi m a g eb i n a r i s a t i o n w e d e s c r i b ea b i n a r i z a t i o nm e t h o dd e s i c n e ds p e c i a l l yf o ro c ro fl o wq u a l i t yi m a g e s ：b a c k g r o u n d s u r f a c et h r e s h o l d i n g t h i sm e t h o di sr o b u s ta n dp r o d u c e si m a g e sw i t hv e r yl i t t l en o i s e a n dc o n s i s t e n ts t r o k ew i d t ht h es t a t i s t i co fc h a i n - c o d eo fs t r o k ec o u n t o u r sm e t h o di s d e s c r i b e dt od e s l a n tt h ew o r d k e y w o r d ：o p t i c a l c h a r a c t e rr e c o g n i t i o n ( o c r ) p r o b a b i l i t yb a s e d c e l lc o u n t b i n a r i s a t i o nd e s l a n t 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意e 申请学位论文与资料若有不实之处， 本入签名：丝“ 本人承担一切相关责任。 r 期兰! 堕：堕! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定r 即：研究生 在校攻凄学似期问论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印什，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制于段保存论文。( 保密的论文在 解密后遵守此规定) 本人签名 导师签名 苏酶 通弛 川| ：f 1 - 。0 3 鹏0 h 期呈! 堕! 丛：! ： 第一章绪论 第一章绪论 1 1 计算机视觉与字符识别 人类是通过眼睛和大脑来获取，处理和理解视觉信息的，周围环境中的物体 在可见光的照射下，在人眼的视网膜上形成图像，由感光细胞形成神经脉冲信号， 经神经纤维传入大脑皮层进行处理与理解。视觉，不仅是指对光信号的感受，还 包括对视觉信息的提取，传输，处理，存储与理解的全过程。信号处理理论与计 算机出现后，人们试图用摄像机或其他一些信号转换与存储设备将获取的图像信 息转换成数字信号，用计算机实现对视觉信息处理的全过程。这样就形成了一门 新的科学计算机视觉。 计算机视觉的研究目标是使计算机通过一幅或多幅图像认知周围环境信息的 能力。这种能力将不仅使机器能感知环境中物体的几何信息，包括它的形状，位 置，姿态，运动等，而且能对它进行描述，存储，识别和理解。计算机视觉发展 得益于神经生理学，心理学与认知科学对生物视觉系统的研究，但多年来的研究 实践表明人类对自身具有的认知能力的认识还远远不够。从事相关科学的研究人 员越来越认识到，需要联合起来对人脑的认识过程进行从宏观到微观的深入研究。 虽然由于人脑的高度复杂性，这种跨学科的研究还不够深入，但从事计算机视觉 的研究已经建立了比较完整的计算理论和算法，从而能对计算机视觉信息进行分 析和处理。计算机视觉作为一门独立的学科正在多个领域发挥着作用，它已经应 用于文字识别，遥感图像分析，医学图像处理，多媒体技术，图像数据库，工业 检测和军事方面。随着跨学科基础研究的深入，随着视觉模型与算法的进一步研 究，随着计算机性能与速度的提高，计算机视觉将广泛的应用于更复杂的场合。 文字是人类思想的载体，是交流的重要工具。进入信息时代后，原来依靠图 形记载在纸上的文字有了电子化的以序号为代表的记载方式，这就产生了图形文 字与编码序号之间的转换问题。由编码序号到图形的转换是计算机输出的问题， 可以由计算机本身的存储记录完成，而由图形到编码序号的就是文字识别问题。 文字识别是模式识别的一个重要方面，在信息处理，办公自动化，邮政系统，银 行系统等方面有着重要的使用价值和理论意义1 6 。 字符识别的发展过程主要有： 五十年代人们开始研究印刷体字符识别闯题； 八十年代中期，随着算法的不断完善，印刷体识别系统走出实验室，进入办 公自动化的应用阶段； 八十年代中后期，计算机的硬件资源发生了重大变化，为手写体的识别提供 了相对充分的研究环境； 九十年代，手写体字符的在线和离线识别都得到了进步的提高。 三一 里堡竺堡! 苎量塑兰塑圭笪堡型墨堕竺董王塑墨堕壅 现在，对于印刷体字符的识别在比较好的条件下识别率可以达到9 8 以i - ， 己经进入实用阶段。而对于英文的字符识别精度一般可以达到9 9 以b 。但是在 一些具体的应用领域仍然有一些问题，我们需要作具体的研究，以进一步提高识 别的精度。 1 2 字符识别系统 图11 通常的字符识别流程 字符识别系统般分为预处理，特征提取f 2 】1 3 11 4 j ，分类器f 3 2 jf 3 5 】，多个分类器2 2 】 的集成和后处理模块，结构如图11 所示。其中预处理包括二值化p l 3 q p t l p r ) b 4 4 9 1 ， 去噪声f 7 3 】和归一化【6 3 】1 6 4 1 等步骤。预处理对特征的提取很关键，它关系到能不能 提取出稳定的，鲁棒的特征。在众多应用环境中，一般特征提取5 “1 7 0 l 7 1 1 ，分类器 和多个分类器集成是识别系统的核心。后处理包括字典分析 6 l 】1 6 2 1 ，上下文语义判 断等，对识别精度的提高有很大帮助。 一般的英文字符识别系统也大致如此。这里我们所开发的系统是以单词为基 础的，其中的识别器是多个分类器的杂糅，最后的判决是多数投票法( 见图1 3 ) 。 我们的系统首先从页面中分割出单词，得到单词图像后，进行字符切割，然 后是归一化，特征提取和识别( 见图12 ) 。得到识别结果后我们要进行后处理，从 字典中查处与”s c i e x e ”相似的单词，按照相似度排序，最后根据上下文语义综合 考虑选择一个合适的单词。如上图的例子中，我们通过字典可查出一下相似的单 词，并按照相似度排列如下： s c l e n c e s c h o o l s t i _ j d e s 第一章绪论 单词图象 字符切割 归一化 特征提取 识别结果 sciexe 图1 2 系统识别过程示意 图1 ，3 多数投票法 最后我们选择一个合适的单词，作为最终的结果。这只是后处理的一个示意。 三一一 塑堡丝墨：苎塑圭塑兰笪望型委竺箜董王塑望婴塞 1 3 本文的工作及意义 ( 1 ) 在字符识别中，要识别字符首先要提取单词，然后再将所提取的单词分割 为字母，因而单词提取的好坏直接关系到后续的识别，而单词的提取又依 赖于行和块的提取，因而提取字符的流程应该是如图1 4 所示： 图1 4 字符识别流程 现今的文档分析系统一般来说包含两个部分：输入图象的分割和实体类型的 分类过程。而对于分割和分类又主要有两方面的研究： 第一方面是用全局的空间关系将文本图象分割成一组包含结构化或者非结构 化内容的区域，用统计特征和结构特征将每个区域标记来作为预定义的范畴 2 。 这种从上到下的分解模式却对于有特定的拓扑结构层次的文档不起作用，尤其是 当图象中有很强的噪声或者文档过度倾斜时，而本文中所给出的方法却可以对不 同进行分割提取，而且对于噪声并不敏感。 第二二方面，将低层次部分( 连通分量 2 3 】或者行分量雎1 1 ) 提取出来并将它们分 类为文本或者非文本的，将文本部分合并为文本块。其中文档的物理和逻辑结构 提取算法能够在文献【l 】中找到。 h a e t a l i ” 中给出了一个递归切割连通域分量投影的算法，从而将图象分割为 一组区域，将区域分类为文本和非文本的，然后将文本区域分解为文本块文本行 和词。n a g y e ta l 在文献f 弼僻，讨论了技术期刊图象文本分析的一个模型。他们将文 本分析和商业o c r 系统联系起来产生了文本浏览系统。h u 和i g o l d 在文献【l 副中给 出了一个近似属性文法并且包含了合成规则和表示规则的文本描述语言。这个系 统主要由两个部分组成：一个是编译器，一个是分析器。编译器将文档类描述编 译到一个文档表和几个分段表中，分析器将图象按照文档表和分段表转换到它们 的结构表示中。d e n g e l 在文献 q 中建立了将商业信件的光栅图象划分到几个逻辑标 第一章绪论 记区中的系统。 以上以及以前的大部分工作是关于特定文本的，其中关于文档类型的信息是 事先确定好的。关于信息取得的一个方法是：通过研究一组具有代表性的文档， 人工产生一套试探规则或者文法。这样的工作不但繁重而且需要很高的专业技术。 手工制造的规则和模型非常脆弱并且只是针对特定的文档类型。如果有新的文档 类型或者有文档的部分差异，它们的系统就无能为力了，而本文所给出的算法对 于各种不同的文本图象都有着很好的提取效果。 c h e ne ta l 在文献p 3 l 中提供了一神词、彳亍、和文本块提取的算法。他们在二值 图象上应用了形态闭合转换算法，对于提取出来的片断按照大小分类为词或者非 文本片断。算法将提取出来的词按照同一行中词的共线性和相同的词间距性质的 统计模型分组到文本行的集合里面，并将得到的文本行按照同一块内的行具有相 似的高度、宽度、行间距等性质合并到块集合里。 由于对于文档的测量可能有误差并且对于文档类型也可能比较模糊，所以算 法必须具有很好的容错性和鲁棒性。为了建立一个近似完美的系统，我们需要系 统的分类而不是直观的推断，而我们算法的基础也应该是数学优化方法而不是主 观的推测。而只有c h e n e ta l 在文献【5 3 1 中提出的算法采用了系统的分类。他的算法 计算了文本行和文本块的贝叶斯估计。然而他的算法忽略了有些参数依赖于字体 尺寸的性质。因而他的算法对于字体尺寸浮动范围比较大的文档效果十分不理想。 行的提取一般分为投影法和基于概率的方法，本文二、三章详细介绍了一种 基于概率统计的提取方法，建立了提取算法的概率模型且给出了相关的算法，并 详细讨论了算法的每一个步骤，包括文本行、文本块和词的提取，简要介绍了图 象处理中常用的投影算法用于行的提取并且比较了两种方法在行提取中的优劣， 最后通过比较我们选取了基于概率统计的提取方法并且达到了很好的效果。对我 们所给出的提取行的算法进行了实验模拟，并将实验结果与投影算法进行比较和 分析后选取了基于概率的提取方法。介绍了块提取算法和相应的步骤。介绍和讨 论了“细胞计数方法”用于对文中所涉及的概率的计算。 基于所建立的概率模型给出了字符识别系统中词的提取算法并对其进行了实 验模拟并对模拟结果进行了分析和讨论。 对字符识别系统中预处理中的二值化方法进行了讨论，进而提出了背景闽值 方法并且介绍了算法的步骤，对本方法和0 s t u 方法进行了实验模拟和对比分析了， 而后者在文献6 4 1 被认为是最佳的二值化方法，通过比较我们选择了背景阈值方法 作为我们字符识别系统的二值化方法。介绍了基于链码统计的倾斜字体校正方法， 并将此方法与梯度法的实验结果进行了比较，结果为前者效果更好。 附录里我们给出了本文的部分程序。 皇一 里堡塾里! 茎王塑奎塑主笪望型墨堕塑董王塑堡婴塞 第二章基于概率的行提取的实现 2 1 前言 在这一章，我们把图象的结构问题当作一个划分问题，问题的目的在于找到一 个将图象上的字边框划分成一个分层树结构的最佳方案。这一章介绍了一个基于 概率的文档结构提取算法，这里的概率是由训练好的组数据来估算的。 我们先做离线的训练来得到概率估计，然后以此来决定在线的分割时候边框之 间的关系。作一个循环的松弛的方法去将边框之间的联系概率最大化并以此来找 到一个最佳的划分。 2 2 概率统计学模型 2 21 基本概念与定义 假设a 是源层次上的一组实体，假设n 是a 的一个在目标层次上的戈分。定 义：兀是a 的一个划分如果： 1 n 是一组互不相交的集合，比如c ai i ，d en 并且c a d ，那么 c n d = 中 2 的合集是整个集合a ，ur l = a 假设l 是一组能和n 的元素一一对应起来的标签的集合，这些标签可以是字 符，字符类型等等。比如在图象分割问题中可以把字符所在层次的类型特征作为 这个标记。 函数厂：nj l 将n 的每一个元素和标签集联系起来；v ：p ( a ) _ a 定义了 个在a 的子集上的度量，这里所说的的a 是一个度量空间。这样我们这里所提 到的分割问题便可以阐述为：给一个初始的集合a ，去找一个a 的划分n 和函数，： 兀_ l 使得概率： p 彤( f ) ：f ，f ，兀j 么) = 尸( f ) ：f 1 4 ，1 1 ，) p l ，彳妒( j 爿) ( 2 。1 ) 最大。这里假设他们是条件独立的，即当f ( r ) 是已知的，那么其它标签的信息就 不能改变v ( r ) 的概率，这样就可以将( 2 - 1 ) 式分解成 p ( z ( r ) ：f ，i 爿) = 兀尸( 矿0 ) f ，( r ) ) j p ( ，f 1 7 ，爿) p ( f 彳) ( 2 2 ) 毳兀 我4 e j i 拘方法将遍历所有可能的划分和标签，最后选择一个能够使概率最大化 的结构。“n 集合”在k 个区间内的划分数叫做第二类斯特灵( s t i r l i n g ) 数： s ( n ，k ) = k s ( n 一1 ，k ) + s ( n 一1 ，k 一1 ) ( 2 3 ) 这里s ( 1 ，1 ) = 1 ，“n 一集合”的划分数叫做贝尔( b e l l ) 数： 第二章基于概率的行提取的实现 a 。= 薹蝴 ， 这里6 0 = b ，= 1 表格21 表明了不同大小集合的可能划分的数目。 7 文档中多边形区域一般是按照一定的阅读顺序来安排的：比如英文文档是按 照从上到下从做到有的顺序排的。因此把a 的元素按照阅读顺序排列起来然后再 检查是否将相邻的元素合并， g r o u p ( 舭十1 ) ：舷 ( 2 - 5 ) “n 一集合”所有排序好的划分的数目是2 ”1 表格2l ：不同大小集合的贝尔( b e l l ) 数 集合的大小 12571 01 4 | 划分的数目125 28 7 71 1 5 9 7 51 9 0 8 9 9 3 2 2 j 假设a = ( a ，a ：，山) 是多边形( 本文我们只是特指长方形) 边框的一组线性 子集，设g = 口，) 是一个分组标志的集合。而设4 是成对的相邻多边形区域的一 个集合( 关于“相邻”的的概念及判定随后的章节将给出) ，这样a c a a 并且 a = ( ( 4 ，a ，) j 一，a ，a 并且= i + 1 ) 。分组方程g ：a 斗g 将a 的每一对相邻的 元素和一个分组标志联系起来，这里g o ) = g ( a ，a 。) 。这样分割概率尸( 兀j a ) 能 够如下计算： p ( n 1 4 ) = p ( g | 4 ) = p ( g ( 1 ) 1 4 ，爿：) p ( 占( 一1 ) i 山+ 山) 1 = 丌p ( g o ) l 爿，爿。) ( 2 - 6 ) 这样公式( 2 一1 ) 可以写成： 尸彤p ) ：r 1 7 ，f ，1 i f 爿) n - 1 = 兀p ( 矿0 ) i ( ) ) p ( ，li - i ，4 ) i - i p ( g ( f ) l4 ，a 。) ( 2 7 ) f 兀i = 1 有了以上概念和数学模型我们就可以作一个循环的松弛的方法去找一个最佳 的划分和标签来使联系概率( 2 7 ) 最大。首先，由每一对相邻的实体之间( 字母， 行或者段落之间) 的空间关系来算出最初的联合概率p ( g ( i ) 1 4 a ，) ，并基于此得 到最初的划分；然后这样我们通过求使概率兀。p ( v ( r ) l ，( f ) ) 尸1 1 7 ，4 ) 的最大 图像处理：基于概率的字符识别系统的若干问题研究 化来调整划分和标签。在每一次循环，我们选择使联系概率( 2 7 ) 最大的划分；当 不能再使联系概率提升的时候，循环停止。图21 给出了简化的算法示意。 图2 1 算法流程示惫 22 2 循环寻找算法 图21 给出了循环寻找算法的流程图，算法2 1 是这个算法的详细步骤。把一 个初始多边形集合a 按照阅读顺序排序。假设4 = 0 。a 。，4 。) 是多边形集合的 子集。 算法21 ： 1 最初的划分： f = 0 ，n = “如”备 ( a ) 计算p 。( 】，) = p ( 占( f ) = y 1 一，彳。) 并且只。( ) = p ( g ( 力= n 1 彳，a w ) 这里l j m 一1 ( b ) 设尺a a 并且r = ( 彳，4 ) 1 只o ( y ) 置o ( ) ) 提升划分= fj f = ( 爿一，a ，) ，这里( 4 ，a “) r ，j 】 2 f ，j 1 ) 2 寻找最优划分： 重复以下步骤： f o ri - 1 t o m 一1 d o i fa ，u ，a 】+ 1 w ，并且u t h e n 第二章基于概率的行提取的实现 ( a ) t = u u w ，并且兀= t u ( n 一u w ) ( b ) 寻找标记，使，。= l - i 尸( f ) i ，( r ) ) p ( ，1 4 ，n ) f e 盒 ( c ) 提升概率： 只( i ，) o c 只o ( y ) 只。，并且只( ) = 只1 ( ) i f 4 并且4 l + 1 w ，这里一 4 ，a ，a1 一，彳，) t h e n ( a ) 设s = ( a ，a ，) ，t = 彳。，a ，) ， 并且兀= ( i i 一形、u s t j t ( b ) 寻找标签函数，使得以下概率最大： 瓦。= n 尸( 矿( ) i ，0 ) ) 尸ul4 ，n ) ( c ) 提升概率；“只( ) 。cp ( ) ，如 并且耳= 只1 叮) e n d 选择k 使得 k = a r g m a x ( m a x ( f ( y ) ，f ( ) ) ) i f 只( j ，) f ( ) ，t h e n t = u u 晰塞里以u ，a w n “1 = ( n 。一u 一 矿) u t e l s e w = 4 ，a i 并r t = a 。，a ，) = ( r i 一w 1 u s u t i f 尸( 矿，“1i a ) p ( v ，f ，1 4 ) e n d 并且返回兀， e l s e ，t - = t + l 并且c o n t i n u e 在随后的章节里我们把以上算法应用于行和块的提取。 2 3 行的提取 231 引言 在介绍行的提取算法之前有必要先看一下输入图的层次关系( 图2 2 ) 1 0 图像处理：基于概率的字符识别系统的若干问题研究 图2 2 图象的层次关系 # - - a ? 型边a ( 它的提取要用到一个求连通域的算法) ，行提取的目的在于 将这些边框划分成行的集合( 即把他们分到一个行的集合里面) ，而每一行应该具 有相同的特性；同样，在每一个区域的行的特性也应该是相同的。这里所说到的 行的特性包括字母的边框离开底线的距离，底线的方向，行的高度和宽度等等。 232 算法细节： 图23 给出了算法的流程图，以下介绍具体步骤： 算法2 2 ： n 1 提取过滤字符边框 我们应用标准的连通域算法( 见附录1 ) 来得到边框，而那些边框大于 t h r e s h o l dm a x 的或者边框小于t h r e s h o l d _ r n i n 的就被滤去。 第二章基于概率的行提取的实现 ( 2 ) 确定边框对： 也就是一个边框找“相邻”的另一个边框：对每一个边框我们找它的右 边紧邻的边框，图2 4 给出了边框之间的空间关系： 参看图2 4 ，我们把边框用( x ，yw ，h ，) 来表示，x ，y ，) 是边框左上角的 坐标，而w 】h 分别是边框的宽和长。 f x ，一x ，一w ，直旺果z j x ，+ w i 其中水平距离d ( i j ) = 薯一x j w j如果- x j + w ， 1 0 其他 垂直距离乱化j ，：y j - y i - 翥霎y ， y ，+ ? ，垂直距离虬o d 2 j 0吩篓毳j 0 z + j县他 。 。 f x ；+ w ，一x ， 立口果x ， - 并且x ， x j 并且x ， y 。并且y j y j 并且y i ，且p ，后) o ) c k e c 同样边框c ，2 ( x ，y jw ，h ，) 是垂直相邻于c 。= ( ，只，w i ，而1 ) 当且仅当 c ，= a r g m i n ( d h ( i ，元) l 七i , y t 一，r o p ，素) o ) q e c ( 3 ) 合并边框： 有了以上定义和确定的边框对那么对于每一对c ：，c ，我们去求它们的 h ，h ，w ，w ，d ( i j ) ，0 ( i j ) 我们就可以算它们同线的概率： p ( s a m e l i n e ( i , j ) fc ，c ，) = p ( s a m e l i n e ( i , j ) lh ，h ，w ，w ，d ( i j ) ，o ( i j ) ) 而对于每一对c 。，c ，我们计算他们之间的联系概率p ( t m k ( i ，) ) ，丽如果 p ( 1 i n k ( i ，j ) = y ) p ( 1 i n k ( * ，j ) = n ) 那么边框c 。，c 就合并在同行内，否则就不合 并他们。而对于最初的划分p ( 1 i n k ( i ，力) = p s a m e l i n e ( i ，) h ，c ，) ，这样我们就得到一 组最初的的行的集合气。= ( t l , f ：，f k j 。 ( 4 ) 行性质的确定( 包括计算基线和x 一高度) 第二章基于概率的行提取的实现 假设f = ( c 。c 。，c 。)是提取好的一组边框，每一个边框c ，由长方形 ( _ ，y 驴x ：，y ：，) 来表示，这里( x l ，y 。，) 和( x ：，y ：，) 是长方形的左上角和右下角的坐 标，图25 给出了一个行以及行的基线和x _ 高度 图2 5 左边两个箭头之间的高度为x 高度，右上角的箭头指向的是x 一高度线，左下角的箭头 则指向基线 ( 41 ) 文本行基线坐标的估计： 我们想通过一组点 ( x ：，y ：捞( 边框右下角的点) 插值出一条直线 y ( x ；a ，b ) = 口+ b x 为此我们要使得方程 女 fj ，：，一e l - - b x 2 ji ( 2 - 8 ) j = f 最小化。我们知道一组数d ，的中值就是使得偏差方程 d j - 如俐、的解奠鉴m 于! 台e c l t a n 嘉y 挈竺端得方钗2 。8 冲柏剐、繁芳 口= ，一0 霄，f l z y j 而求参数b 的方程是： s g n ( y 2 ，一口一b x 2 j ) 3 0 ( 2 _ l o ) j = f 这个方程可以由二分法和划界法解得”1 。 ( 4 2 ) 图象角度的估计： 给一组基线的角度值捣，幺，0 ，) ，那么我们就把图象整体角度估计 为： o p 。= m e d i a n 0 1 ，吼，巳) 如果图象的角度口，。大于一个给定的阈值，图象就反方向旋转日，。来 达到纠正倾斜的目的。我们用文献5 9 1 中介绍的方法来旋转图象。 ( 4 3 ) x 一高度的计算和概率的提升 文本行静高度的计算是由每一个边框左上角( x l ，y ，) 到相应基线的距 离取中值得到的： 1 4 图像处理：基于概率的字符识别系统的若干问题研究 垃p ) = m e d i a n d ( x l j , y l ，口，b ) ii j 尼) 对于给定的一组文本行f = ( 。f ，- ，c 。) 和基线估计( 口，b ) ，计算出边框右 下角( h ，y ：，) 到估计的基线的距离： d e v ( t ，a ，6 ) = l y 2 j 一口一b x 2 jl j = i 这样对于给定的文本行f 有了以上的准备我们就可以计算t 是否具有 行的性质的概率： p ( 以o ) ，d e v ( t ，口，b ) lt e x t l i n e ( t ) ) 这样边框c ，和c 。之间的联系概率就可以按照下面的式子得到提升： p ( 1 i n k ( j ，+ 1 ) = r ) o c p ( s a m e l i n e ( j ，j + 1 ) 2 y i 。，。，“) 。( 2 - 1 1 ) p ( 以( f ) ，& f i t ，口，b ) it e x t l i n e ( t ) ) ， 和 p ( 1 i n k ( j ，j + 1 ) = n ) p ( s a m e l i n e ( j ，+ 1 ) = n ic i , c i + 1 ) 尸( 风“) ，d e v ( t , ，口，b ) l t e x t l i n e ( t 1 ) ) e ( h a t 2 ) ，d e v ( t 2 ，口，6 ) t e x t l i n e ( t 2 ) ) ( 2 一1 2 ) 这里f ，= ( 。一，c ，) 并且f ：= ( c ，。，c 。) ，显然公式( 2 1 1 ) + ( 2 1 2 ) 2 1 即 p ( 1 i n k ( j ，+ 1 ) = y ) + p ( 1 i n k ( j ，+ 1 ) = n ) 2 1 ( 5 ) 确定文本区域 、对于给定的一组行的边框，= f 。，t ：，t 。) ，要把他们合并在一组区域里面 r ：( r 1 ，r ：，r 。) ，在每个区域r ，= ，y ，w ，h ，) 里的行都被边x ，和x ，+ w ，包围 着从而形成了独立的一列。 给一个边框( x ，y ，w ，矗) ，他的水平投影就定义为： h o r z p r o j = h o r z p r o j + 1 ，x j x + w 垂直投影： v e r t _ p r o j - 一v e r tp r o j + 1 ，y ， y + h 假设( x 。，。，w 。，h m ) 表示一个文本行f 。t 的边框，那么行的左边为 e l m ：x 。，右边为p 。= x 。+ w m 行的中线为8 。= x 。+ w 。2 。那么行f 。r 在这三边 上的垂直投影累加就定义为： c ， j l = c j + l ，- ，= e l m 对于1 聊” c 。【j 】= c 。【j + 1 ，= p 。，对于1 m 胛 c ，l 订= c ， j 】+ 1 ，j = e 。，对于1 m 拧 墨三兰苎三塑垩塑堑塑坚堕壅墨 竺 算法23 ：区域边的确定： ( 1 ) ，计算所有文本行边框的水平投影 ( 2 ) 将水平投影之间的间隔大于一定阈值的行分割开，从而将整个图象分割 成一组区域。其中闽值是由所有文本行高度的均值决定。 ( 3 ) ，对于每个区域，设巨= ( e 儿，e 。) 是左边的集合，e = ( e 。p 。，e 。) 是 中线的集合，e ，= ( e 。，e 。) 是右边的集合。 重复以下步骤： ( a ) 计算文本行边框的左边c ；，右边c ，中线c 。的垂直投影累加。 ( b ) 找到累加最大的地方，它的宽度为： a r g m ，a ，x ( c d i j m c ) ，一寺w k + w ) ， ( 2 1 3 ) 这里w 由这个区域的主要文本行的高度决定。 ( c ) 岛= ( e 。i b 。e ，一了1 w e 。 p ( 1 i n k ( i ，j ) = n ) ，就将它们分到同一块内，否则就将它们分 到不同的块内。( p ( 1 i n k ( i ，) ) 的初始值为p q i n k ( i ，) ) = p ( s a m e b l o c k ( i ，) ) ) 。这一步 我们得到了初始的块集合：b i 。，= ( b 1 ，b ：，吃) ( 3 ) 标记文本块： 计算所提取的文本块吼具有文本块的性质的概率： p ( v 。) i ，( 8 。) ) 这里标记函数( 巩) 包括了相似的行间距等性质。 ( 4 ) 提升概率并且调整划分： 给定了标记概率，我们可以提升相邻的行之间的联系概率，在每次循 环里我们选择使得联系概率最大的调整。然后返回第二步并根据提升后 的联系概率调整划分。如果联系概率不再有改进，循环停止并返回所得 到的块。 2 4 2 行的合并： 对于垂直相邻的行和f 。，我们用边框( x ，y 。，w ，h x ) 来表示行( 这里 z 是边框左上角的坐标，y b 是基线坐标，w 是行的宽度，坟是行的x 一高度) 我们要 得到以下的量： ( 1 ) 行的x - 高度：向和囊。 ( 2 ) 行间距：d ( i ，i + n ( 3 ) 水平重叠：o ( i ，i + 1 ) ( 4 ) 左边之间的距离：b ，( i ，i + 1 ) = 鼍一x m ( 5 ) 中线之间的距离：b 。( f ，f + 1 ) = x ，一x + ( w ，+ w ) 2 ( 6 ) 右边之间的距离：p ，( f ，i + 1 ) = x ，一x + w ，一w f + l 行间距矗( j ) 由两行x 高度的均值规范化： 谚：善! 生卫 圭( 噍+ 红轧) 行f ，和f 。的水平重叠由它们两行的高度规范化 q = 掣，= 掣 第二章基于概率的行提取的实现 t i 和f 。的左边的相对位置由下式得到： r l = o 如果p i ( f ，f + 1 ) 三( + 绣+ 。) 1 立口果p ，( f ，f + 1 ) 三( 红+ 囊+ 。) 一1 如果8 ，q , i + i ) ( h i + 囊+ 。) 同理，f ，和f 。两行的中线和右边的相对位置可以以同样的方式得到。 有了以上的观察量，我们就可以计算f ，t n t 。同块的概率 p ( s a m e b l o c k ( i ，i + 1 ) i ，0 ，矾，r l , ，r c ，珥) 这样我们就可以得到最初的块的集合。 2 , 4 3 上下文的一致性检查： l 临近块的上下文约束概率p ub , t ) 服从马尔可夫链( m a r k o vc h a i n ) 模型， p ( f ) 1 ，( 茸一。) ，f ) ) = p ( f 。) 1 f ( b ，。) ) 这里b ，b ，这样上下文一致性概率： 兀p ( 矿( b ) if ( b 。) ) p ( ，ib ，丁) b t 口 实际上就是隐含马尔可夫模型。 给定一个划分，使得联系概率最大的标记系列可以由v l t r b i 算法6 3 1 来 得到。对于给定的观察序列0 = ( 0 1 0 ：0 ，) 为了找到最佳状态序列 q = q l q ：如) 我们定义以下量： 4 ( i ) = m a xp ( q q 2 吼= f ，o 。0 2 0 ，i 丑)( 2 2 0 ) l q 2 ，q f l 这里坑( ，) 是在时刻t 的最大概率。由归纳法得到： 瓦。( j ) = m a x 6 。( i ) a f 】6 ，( 0 。) ( 2 - 2 1 ) 我们用数组( j ) 记录使得( 2 2 1 ) 最大的路径，以下就是v i t e r b i 算法： 算法25 ： 1 初始化 茜( j ) = 石。b ，( d 1 ) ，1 f n ( f ) = 0 2 递归： 4 ( j ) 2 m 。a 。x e ( j ) 口f 6 ，( q ) ，2 f 丁，1 图像处理：基于概率的字符识别系统的若干问题研究 3 终止 4 回溯 ( ) - a r g m a ：x ( f ) 口f 】，2 f t , 1 - ，n p m a x s t ( i ) 口汪a r g m 。a ；。x 6 r ( i ) q ；= ( 口二1 ) ，t = t - 1 ，r 一2 ，1 图2 ，1 3 给出了本算法提取文本块的一个实例。 图2 1 3 文本块 2 5 概率的计算 251 基础理论 在算法中的联系和条件概率我们用离散列联表表示。表里面的每个变量有有 限个互斥的状态。如果变量爿有状态q ，口：，a 。那么p ( 爿) 就是这些状态的概率分 布 尸( 爿) = ( x l ，) ，t o ，t = 1 ， i = 1 这里x ，是彳具有状态口，的概率；如果b 有状态6 l i 一，b 。，那么尸口l 功就是一 个大小为即m 的包含数尸( 口。限) 的表( 参见表2 2 ) ，同样变量4 和b 的联系概率 p ( a ，b ) 也是一个大小为聍x 肼的表，他包含的元素为( d ，b ，) ( 参见表2 3 ) 。 第二章基于概率的行提取的实现 表2 2 p ( ab ) 的一个例子：( 每一列的和为1 ) 6 1 b 2b 3 q 03 306 70 7 5 口06 703 3o 2 5 _ b 1b 2 如 d 1 0 1o20 3 口0 2o1 ol - 我们有一下的基本定理： p ( 爿i 占) 尸( 曰) = p ( a ，丑) 将定理应用到离散列联表就得到： p ( 啊| b 1 炉( 6 ，) = p ( a ，b ，) 从离散列联表p ( 4 ，口) 我们可以得到概率分布p ( a ) 。假设日，是4 的一个状态， 那么a 在状态d ，就有删个互斥事件( 口。鱼) ) ，( 4