（控制理论与控制工程专业论文）文本处理及手写汉字切分技术的研究.pdf

文本处理及手写汉字切分技术的研究 摘要 本文从中文处理中的汉字识别和文本处理着手，分析了汉字识别和文本处理 各自的研究内容、特点以及它们在中文处理中的地位和相互关系。然后主要集中 在文本处理方面，从印刷体和手写体、西文文本和中文文本等角度，详细地分析 了各自处理的基本内容、基本特点和基本的处理方法，并且充分阐述了对这些课 题当前的研究进展。文章还分析了文本处理的基本理论，基于这些理论，介绍了 一个脱机手写汉字字符切分算法和相应的实验结果。最后文章介绍了联机手写汉 字字符切分的特点和难点，给出了个基于规则的联机汉字切分算法a 文章的具 体内容如下： 1 文本处理的研究内容及进展 文本处理包括版面理解和行字分割两方面，阐述了版面理解的描述语言和处 理方法、分析了文本特别是汉字文本行字分割的难点；根据文本的内容及格式， 文章将文本分为印刷体西文文本、手写西文文本、印刷体中文文本、手写体西文 文本，然后对各类文本，介绍了各自处理的基本特点，介绍了基本的处理方法， 以及对当前的研究进展都有相当充分的阐述。 2 基于h m m 模型的脱机汉字手写字符切分算法 在这部分中，首先从图像处理、隐马尔可夫模型和动态规划三个方面介绍了 算法的理论綦础，然后，详细地介绍了该算法的详细的设计和实现，通过模型建 立、获得切分路径、消除冗余路径、利用动态规划获得最优切分方案，实现了该 算法。通过采集到的1 5 人左右不同字体风格的手写汉字样本测试了该算法的性 能，给出了测试结果，并分析了此算法的成功和不足之处。 3 基于规则的联机汉字手写字符切分算法 联机输入是应计算机手写字符输入的要求而出现的一种特殊的输入形式，现 有的字符切分技术还很少有针对联机手写文本的，但这一课题同样有着一定的实 用意义。本文分析了联机手写文本字符切分的特点和难点，针对嵌入式手写汉字 识别系统，提出了种基于规则的联机手写汉字字符切分算法，根据实际使用效 果分析了其性能。_ 关键词：文本处理，字符切分，图像分割，i - i i v i m ，动态规划，汉字识别系统 r e s e a r c ho nd o c u m e n tp r o c e s s i n ga n dh a n d w r i t t e n c h i n e s ec h a r a c t e rs e g m e n t a t i o nt e c h n o l o g i e s a b s t r a c t t h i s p a d e ra n a l y z e s t h er e s e a r c ha r e a sa n df e a t u r e so fc h i n e s ec h a r a c t e r r e c o g n i t i o na n dd o c u m e n tp r o c e s s i n gr e s p e c t i v e l y , a n dd i s c u s s e s t h e i rr o l e sa n d r e l a t i o n s h i p si nc h i n e s ep r o c e s s i n g t h e nf o c u s i n g o nd o c u m e n t p r o c e s s i n g ，f r o mt h e a s p e c t so fp r i n t e d h a n d w r i t t e nt e x ta n da l p h a n u m e r i c c h i n e s et e x t ，w et h o r o u g h l y d i s c u s st h er e s e a r c ht a s k s ，b a s i cf e a t u r e s ，p r o c e s s i n gt e c h n i q u e s ，a n dr e s e a r c hs t a t u so f t h e s ea r e a s t h e n t h ef u n d a m e n t a lt h e o r i e so fd o c u m e n tp r o c e s s i n ga r ei n t r o d u c e d a n da no f f - l i n eh a n d w r i t t e nc h i n e s ec h a r a c t e rs e g m e n t a t i o na l g o r i t h mi sp r o p o s e d f i n a l l y , t h i sp a d e rd i s c u s s e s t h ef e a t u r e sa n dc h a l l e n g e so fo n l i n eh a n d w r i t t e n c h a r a c t e r s e g m e n t a t i o n a n di n t r o d u c e sar u l e b a s e do n 1 i n ec h i n e s ec h a r a c t e r s e g m e n t a t i o na l g o r i t h m n l i sp a p e ri so r g a n i z e da sf o l l o w i n g ： 1 t h er e s e a r c ha r e a sa n ds t a t u so f d o c u m e n t p r o c e s s i n g d o c u m e n p r o c e s s i n g j n c l u d e sf r a m eu n d e r s t a n d i n ga n dc h a r a c t e rs e g m e n t a t i o n t h e d e s c r i p t i o nl a n g u a g e sa n dp r o c e s s i n gm e t h o d sa r ei n t r o d u c e di nt h ef i r s tc h a p t e r a c c o r d i n g t ot h ec o n t e n ta n ds t y l e ，d o c u m e n ti sc l a s s i f i e di n t of o u rc a t e g o r i e s ：p r i n t e d a l p h a n u m e r i ct e x t ，h a n d w r i t t e na l p h a n u m e r i ct e x t ，p r i n t e d c h i n e s et e x ta n d h a n d w r i t t e nc h i n e s et e x t ，w h i c ha r ed i s c u s s e do nt h e i rp r o c e s s i n gc h a r a c t e r i s t i c s p r o c e s s i n gt e c h n i q u e sa n d r e s e a r c hs t a t u sr e s p e c t i v e l y 2 a no f f - l i n eh a n d w r i t t e nc h i n e s ec h a r a c t e rs e g m e n t a t i o na l g o r i t h mb a s e do n h m m i nt h i sp a r t ，t h ea l g o r i t h m st h e o r yb a s ei si n t r o d u c e df r o mt h ea s p e c t so f i m a g e p r o c e s s i n g ，h i d d e nm a r k o v m o d ea n dd y n a m i c p r o g r a m m i n g t h e nw ed e s c r i b et h e a l g o r i t h m sd e s i g na n di m p l e m e n t a t i o n ：m o d e lc o n s t r u c t i o n ，p r o d u c i n gs e g m e n t a t i o n p a t h s ，r e m o v i n gr e d u n d a n tp a t h s ，f i n d i n go p t i m a ls e g m e n t a t i o n s c h e m et h r o u g h d y n a m i cp r o g r a m m i n g t h et e s ts a m p l e sa r ew r i t t e nb y15p e o p l ei nd i f f e r e n tf o n t s a n ds t y l e sa n du s e dt ot e s tt h ep e r f o r m a n c eo f 也ea l g o r i t h m t h et e s tr e s u l ti sl i s t e d a n dt h ea d v a n t a g e sa n d d i s a d v a n t a g e sa r eb o t ha n a l y z e di nt h es e c t i o n 3 ar u l e - b a s e do n l i n eh a n d w r i t t e nc h i n e s ec h a r a c t e rs e g m e n t a t i o na l g o r i t h m 0 n l i n eh a n d w r i t i n gi sas p e c i a li n p u tm e t h o da c c o r d i n gt ot h er e q u i r e m e n to f t h e c o m p u t e rc h a r a c t e ri n p u t l i t t l e r e s e a r c hw o r kf o c u s e so no n l i n ec h a r a c t e r s e g m e n t a t i o n b u tt h i st o p i ci si m p o r t a n tt o s o m ea p p l i c a t i o n s w ea n a l y z e dt h e f e a t u r e sa n dd i 佑c u l t i e so fo n l i n ec h a r a c t e rs e g m e n t a t i o n a n df o c u s i n go ne m b e d d e d o n l i n eh a n d w r i t i n gr e c o g n i t i o ns y s t e m 。ar u l e b a s e do n l i n eh a n d w r i t t e nc h j n e s e c h a r a c t e r s e g m e n t a t i o n m e t h o di s p r o p o s e d a n di t s p e r f o f i n a n c e i sd i s c u s s e d a c c o r d i n g t ot h e p e r f o r m a n c e o fa p r a c t i c a la p p l i c a t i o n k e y w o r d s ：d o c u m e n t p r o c e s s i n g ，c h a r a c t e rs e g m e n t a t i o n ，i m a g es e g m e n t a t i o n ， h m m ，d y n a m i cp r o g r a m m i n g ，c h i n e s ec h a r a c t e rr e c o g n i t i o ns y s t e m 一奎奎丝垄曼主要这主切佥技苤的班塞 绪论 自从2 0 世纪4 0 年代数字计算机问世以来，以微电子、计算机、通信为主要 支柱的信息技术得到了突飞猛进的发展，从而将人类从工业化社会向信息化社会 推进。最初的计算机是用来进行科学计算的，但随着信息技术的发展，计算机渗 入到了各个领域，在各行各业都大显神通，发挥着极其重要的作用。由于在使用 计算机的时候，总需要把数据或资料送入计算机，或者需要把有待解决的问题以 计算机能够接受的方式送入计算机，因而如何把人与计算机两者联接起来，也就 是如何建立人与计算机两者之间的“接口”，就成了必须加以解决的问题。 计算机问世的初期，数据和程序是通过键盘被送入计算机的，后来人们很自 然地考虑到能否采用人类所习惯的交流方式与计算机打交道。为此，首先考虑的 是计算机能不能对语音、文字和图像有认识能力，只有在能够认识的前提下，才 可能以此为基础进行进一步的处理。 对于使用汉字与汉语的中国人来说，用汉语与汉字同计算机进行交互是项 具有现实意义的工作。因为我们所处理的文件资料，大部分是用印刷的或手写的 汉字完成的。我们不可能仅靠人力来处理信息，而必须依靠信息技术来进行信息 处理。汉字处理及识别问题主要包括以下两个方面。 一方面，是如何能有效地与计算机进行交互的这一计算机识别模式的问题。 近1 5 年来，p c 机的出现和推广应用，为这方面的研究工作提供了方便而有效的 工具。但是目前，我国内地、香港、台湾等地区的学者研究用计算机对联机及脱 机手写汉字进行识别时，大都着眼的是解决工程技术问题。结果表明，计算机能 识别汉字，说明计算机表现出具有一定的“智能行为”，有点像人一样“聪明”。 但实际的情况是：计算机识别手写汉字与人脑识别手写汉字的机理完全是两回 事。尽管不同人书写的汉字变化多端、龙飞风舞，但人脑能正确地加以识别。而 目前计算机进行汉字识别所用的方法往往是以设计者的“技巧”为主。它虽然能 达到较高的识别率而且速度很快，但毕竟相当“死板”。 另一方面，是从智能系统的角度。当人们看到计算机借助编制的程序，能够 认识图形，能够听懂声音，并按照语音命令作出相应的反应时，会感到惊奇。在 家喻户晓的天方夜谭中有个故事：面对着一个紧闭的石洞，只要喊一声“芝 麻开门”，两扇石门就会自动打开；如果喊的不是“芝麻”而是其他植物的名字， 石洞的门便不会打开。而当前，用模式识别技术来实现把门打开的这种声控系统 并不是天方夜谭，是不难办到的。而且，这种系统一旦开发出来，将给人们的生 活带来极大的方便。设想一个盲人，他若拥有一副特殊的眼镜，这副眼镜能看懂 报纸书籍甚至信件，那么盲人将能像正常人一样学习交流，生活工作。 上 一 塞奎处理皇壬量逯主翅筮蕴苤曲珏究 汉字识别处理的最终目的便是使得计算机也能像人一样能够读、写、听、说 中文。本文要探讨的文本处理及字符切分技术是字符识别系统的一个重要组成部 分。文章将从脱机和联机文本，中文和西文文本，印刷体和手写体等诸多方面， 详细阐述这一课题的研究内容、基本理论、处理方面及当前的研究进展。在本文 的后两章中，根据笔者的实际研究开发工作，对于脱机手写文本和联机手写文本， 分别介绍了一种处理算法，并给出了相应的实验结果。 2 塞奎熊堡皇至星逯芏切垃撞苤的班煎 第一章汉字识别与文本处理 1 汉字识别的研究内容与进展 1 1 汉字识别的研究内容 汉字识另l j ( c h i n e s ec h a r a c t e r r e c o g n i t i o n ) 是用计算机抽取汉字特征，跟机器内 预先存放的特征集匹配判别，将汉字自动转换成某种代码( 例如国标区位码) 的一 种技术。在计算机已经普遍应用的今天，利用计算机这一极为有效的信息处理工 具，对人类通讯过程中所用的各种文件进行处理是十分自然的。但在我国，各种 文件资料几乎都是用汉字书写的，为方便地处理文件资料，首先要考虑的是如何 把汉字文本送入计算机，然后才可能由计算机进行处理。 世界上所使用的文字大致有2 大类：一类是拼音类文字，另一类是象形类或 图形类文字，汉字属于后面一类。在人与计算机打交道的过程中，拼音文字具有 极大的优越性，只要借助键盘即可将文字输入计算机。对于像汉字这样的图形类 文字，由于日常使用的数量太多，字的结构又复杂，因而一直没有适当的输入设 备。随着计算机在我国的普及，越来越多的人将使用计算机，这样，利用西文键 盘输入汉字便成了计算机应用的瓶颈问题。 汉字是图形类文字，因此将汉字输入计算机的最佳方案是采用输入图形的方 式，这有两种途径：一种是让计算机识字，发展汉字识别技术，把书写在纸上或 其他媒质上的汉字( 包括图形和图形文字) ，通过扫描等技术以及自动认字的方 法，方便、自动、快捷地输入计算机。这种方法称为脱机汉字识别( 包括印刷体 和手写体) 。另一种方法称为联机手写识别，即使用者在一块特定的书写板上写 字，在写字的过程中就把所写的汉字输入计算机。汉字识别的类型大致可以概括 如下： 和其他模式识别一样，汉字识别的基本原理也是匹配判别。抽取代表未知汉 3 塞查处理当壬兰这主切筮挂盔鲍班赶 字模式本质的表达形式( 例如各种特征) 和预先存储在机器中的标准汉字模式表 达形式的集合( 常称识别字典) 逐一匹配，用一定的准则进行判别，从机器存储 的标准汉字模式表达形式的集合中，找到最接近所输入文字的模式表达形式，该 表达形式对应的字就是识别结果。下图是汉字识别的原理框图： 一圜寸b 圜匠囤撼鳃 型謦生一一一 学习部分 专家。 其中，图文扫描仪是汉字识别的输入设备，使汉字文本上的汉字图像变换成 一个带灰度值的数字化的图像信号，再经过二值化处理存入计算机。前处理( 又 称预处理) 环节的内容和要求取决于识别方法，通常包含汉字文本图像处理、分 析、行切分、字切分、规范化( 文字尺寸、位置、笔画粗细等规范) 等。对手写汉 字，还有整形变换、抽取轮廓等预处理。前处理后，一页汉字文本图像成为一个 个单独的并已规范化的二值点阵汉字，对它们抽取特征后，跟存储在字典中己知 的标准汉字特征集匹配判别，就可以识别出输入的未知汉字。后处理是从汉字单 字辨识出代码到输出正确的文本文件之间的处理过程。主要是利用语言知识对识 别结果进一步加工，自动纠错和侦错，充实字典，不断提高识别率。 1 2 汉字识别的特点 在我国，最初人们想研究汉字识别主要是从文化方面来考虑的，我们本国使 用的汉字理所当然地应由自己来用计算机进行识别汉字文本的研究。后来，则主 要是被它巨大的市场和经济价值所吸引。在经过一段时间的研究开发、人们对汉 字识别的难度有了清醒的认识之后，仍有大批研究者坚持进行这方面的研究工 作，其中最重要的原因是汉字识别属于典型的模式识别的问题。汉字识别有如下 特点： ( 1 1 汉字种类繁多。汉字识别问题是一个大类别数的模式识别问题。国标g b 2 3 1 2 8 0 共收集了6 7 6 3 个，分为二级。第一级共有3 7 5 5 个汉字，使用频率达到 9 9 7 ，第二级3 0 0 8 个汉字，两级汉字的总使用频率达9 9 9 9 。识别系统一 般应能正确识别这些常用字，以满足实际应用的需要。 f 2 ) 汉字结构复杂。汉字是一种结构性很强的表意文字，每个汉字都由若干笔划 组成，笔划间的拓扑关系也很复杂。汉字也可看成由部件组成的，部件是笔 4 童查处理复壬蔓这主切岔擅壅曲鳃峦 划有意义的组合，一般称之为偏旁、部首或字根。笔划和部首的各种排列组 合，构成了具有不同含义的结构异常复杂的汉字字符。 ( 3 ) 汉字相近字多。部分汉字之间只存在很细微的差别，如“候”与“侯”之间 只相差一个竖笔划，“大”与“太”之间只相差一点。具有相同笔划数目的 汉字字符之间的差异有时仅表现为某一个笔划位置或形态的细微变化。比如 “于”和“千”仅在字符的下部有一细微的差别。即使是人来辨认这些字， 若没有上下文的帮助，也很容易出错。识别算法和系统必须能正确判定这些 细微的差别，否则，就会发生错误。 ( 4 ) 汉字书写形变大。虽然同一个汉字的拓扑结构在不同的手写中基本保持不变， 但其图像大小、形状各异。汉字印刷体的字体就有宋、黑、楷体等多种，手 写汉字的书写更是多种多样，再加上书写环境的不同，书写就很不规则了。 ( 5 ) 汉字书写环境的复杂程度基本适中。我们知道，从复杂的背景中分割出所要 识别的对象并抽取特征，本身就是一件相当困难的事情。这也是我们对一些 对象无法进行识别的重要原因。汉字书写的背景尽管也有很复杂的，但大部 分情况下都书写在纸上，虽然大小不一，甚至还有一些其他物体图像的干扰， 但从中分离出汉字还是可能的。 ( 6 ) 汉字样本普遍存在。尽管汉字样本的收集需要花费一定的精力，都是由于汉 字使用的人多且书写频繁，因此样本的收集只是时间和财力的问题。目前， 已有一些较完备的汉字样本集。 1 3 汉字识别研究的历史和现状 上世纪6 0 年代，汉字识别研究在英文、数字识别技术的基础上开始发展。 1 9 6 6 年毋m 公司的c a s e y 和n a g y 2 发表了第一篇关于汉字识别的文章。人们 最初的研究动机，是设计一种能自动扫描中文、输出英文的中文阅读机，以便把 大量的中文材料翻译成英文，使西方人了解中国的文化和技术。现在汉字识别的 目的发生了根本性的改变，从自动汉字翻译的辅助工具变为中文信息处理和办公 自动化的重要手段。从而使得汉字识别的研究中心逐渐转移到日本和我国。七十 年代，日本的研究主要集中在印刷体汉字和联机手写汉字的识别。饭岛、中野、 山本等在1 9 7 3 年前后发表了一批有关汉字识别的论文，在1 9 7 7 年完成了日本通 产省制定的“图像信息处理系统”中的印刷汉字识别装置，并于1 9 8 0 年1 0 月进 行了公开表演。该装置是一个庞大的硬件专用设备，可识别2 0 0 0 个汉字，识别 速度达到1 0 0 字，秒。从7 0 年代中期起，日本开始研究手写规整汉字识别。进 入8 0 年代，日本汉字识别研究日趋活跃。8 0 年代中期，东芝、n t t 、三洋、理 光、三菱、富士通、松下、冲电气等公司的以软件为主并使用通用高档微机的产 品已经走向市场。 5 塞奎处理生壬曼邋主切盆燕查的班宜 我国于7 0 年代末起步，研究汉字识别技术至今已有2 0 多年了。大致可以分 成三个阶段： 一，1 9 7 9 】9 8 5 年识别方法探索阶段。 7 0 年代初，我国开始进行数字、英文、符号的识别研究。7 0 年代末，有少 数大学和研究所对汉字识别方法进行了探索，发表了一些论文，研制出少量模拟 识别软件和系统。这个阶段路途漫长，但孕育了下一阶段的丰硕果实。 二1 9 8 6 1 9 8 8 年汉字识别系统研制阶段。 这三年是汉字识别技术研究的高潮期，也是印刷体汉字识别技术研究的丰收 期。有1 1 个单位进行了1 4 次印刷体汉字识别的成果鉴定。这些系统对样张识别 能达到高指标：可识别宋、仿宋、黑、楷体，识别字数最多可达6 7 6 3 个，字号 从3 号到5 号，识别率高达9 9 以上，识别速度在用2 8 6 微机的条件下达到1 0 1 4 字秒，但对用户的实际文本识别率则大大下降，这是由于以上系统对印刷文 字形状变化的适应性和抗干扰( 如文字模糊、笔画粘连、断笔、黑白不均、纸张 质量差、油墨反透等) 性能差。三年的研制为印刷体汉字识别系统实用化打下了 基础，是识别系统从研制到实用化必经的阶段。联机手写汉字识别在这三年中也 有了初级产品。 三1 9 8 9 目前印刷体汉字识别和联机手写汉字识别走向实用化阶段，手写 规整汉字识别的研究进入高潮。 在国家重点科研计划的支持和市场驱动下，汉字识别系统一直朝不断改进系 统功能和实用化的方向发展。今天，印刷体汉字识别已有四五个系统( 例如北京 信息工程学院研制的b i o c r ，清华大学研制的t h o c r , 国家智能计算机研究开 发中心研制的n c o c r ，台湾研制的丹青o c r 等) 近万套在国内外使用。它们能 识别常用的4 0 0 0 多个不同字体、字号的汉字，识别率达到9 5 9 9 ，使用高档 微机时识别速度达到2 0 4 0 字秒。大陆和台湾研制的联机手写汉字识别实用系 统已有1 0 多种( 例如中国科学院自动化研究所研制的汉王笔，台湾研制的蒙恬笔 等) ，市场销售量已超过5 万套。这些系统能实时识别1 0 0 0 0 个以上的规整书写的 简繁体汉字，笔顺无限制或少限制，少数常用字可以连笔，熟练使用后识别率可 达9 0 以上。鉴于脱机自由手写汉字识别难度太大，当前只是对手写规整汉字识 别进行研究。目前的水平还不高，多人书写时，最高也只能达到9 0 左右的识别 率，离实用还有较大距离。 总之，我国印刷体汉字识别和联机手写汉字识别已进入实用阶段，其技术水 平和当前世界最高水平并驾齐驱。可以断言，巨大的市场需求和广阔的应用背景 必将推动汉字识别的进一步发展。 6 塞奎熊堡皇圭蔓逯呈切盐拉盔的硒蕉 文本处理与识别的研究内容 2 1 文本处理与识别的研究内容 在脱机文字识别中，各种文本，如各种书籍、报刊、杂志等印刷文本常常具 有复杂多变的排版格式。例如，一篇文章的版面中除了正文行之外，还有标题行、 小标题行、作者行等等。这些逻辑属性不同的行和由它们构成的块往往字号不等、 大小不一，并且常常具有不同的横竖版排列形式，正文中除了含有多个段落之外， 还可能分为多个分栏。在标题与正文之间、正文的各个段落之间、分栏与分栏之 间，存在着一定的逻辑顺序( 即语义顺序) 。除了文本区域外，版面中还常常含 有表格、图片、图形等区域。此外，一个较大的版面还可能包括多篇文章，而这 些文章之间的排列又可能是交错嵌入的( 如报纸) 。特别是各种手写文本，如支 票、邮件地址等文本，格式就更随意多样了。正确分析和理解版面的这些格式， 对字符识别研究具有重要的意义。这种版面格式的多元化和复杂性，使得文本的 版面处理问题成为脱机手写汉字识别系统必须加以解决的重要问题。 版面理解实际上可以分为版面分析和版面理解两部分。版面分析的主要任务 是，把原始图像文件中所包含的文本、表格、图片和图形等不同性质的区域划分 开来，给出版面基元的几何位置( 即物理结构) ，以便于下一步的版面理解和行 字分割。而版面理解则是对各个版面基元的性质和顺序( 即逻辑结构) 作出判断 和识别，以保证识别后的文件具有正确的语义关系。这两者之间的关系是十分密 切的，前者是对文件物理结构的分析，而后者是对文件逻辑结构的理解。实际上， 这两个过程常常交织在一起进行，而一般意义下的版面理解就是这两者的总称。 行字分割特指从具有一定逻辑属性的版面单元到单个字符点阵的分割过程。版面 理解和行字分割是属于识别系统中的预处理部分。 版面理解和行字分割实际上是一个特定的图像理解问题，其研究内容涉及到 图像分析、计算机视觉、模式识别、认知心理学、人工智能等很多领域，因此它 也是一个横跨多个学科、需要交叉运用多种方法才能解决的综合性问题。在o c r 研究的前期阶段，人们的注意力主要集中在字符识别上，没有充分意识到这些问 题的重要性。随着字符识别技术的日臻成熟，版面理解和行字分割方面的不足日 趋明显，成为制约整个o c r 系统性能的一个重要因素。从8 0 年代起，国外的 o c r 研究者开始了这一方面的探索，先后提出了多种版面理解的算法，从而把 原来的o c r 系统扩展成为d a r ( d o c u m e n t a n a l y s i s a n d r e c o g n i t i o n ) 系统。当 前，关于版面理解的研究已经成为模式识别领域中一个十分活跃的方面。 7 塞查丝理量王量遗主切盆鼓盔曲监宜 2 2 文本处理与识别的主要方法 2 2 1 版面理解 文献 3 从几何结构角度出发，将常见的文本版面分为以下三类版面：无嵌入 式矩形版面、嵌入式矩形版面、和非矩形版面。如前所述，版面的结构包括物理 结构和逻辑结构，好的文本版面描述语言应该能够对版面的这两种结构都作出描 述。版面的描述语言有面向对象的版面描述语言、形式定义语言、文件结构语言。 面向对象的版面描述语言 由于文件、版面基元、行、字符等对象之间存在从上到下的层次关系，下层 对象是上层对象的组成部分，有着比上层对象更丰富的信息，因此，版面描述语 言应该是善于描述层次结构的描述语言。面向对象的语言不仅可以很方便地表达 这样的层次关系，而且直接对应程序的实现过程。 形式定义语言f d l 描述版面结构的形式定义语言f d l ( f o r l t ld e f i n i t i o nl a n g u a g e ) 是一种基于框 架的知识表达方法。它把文件的版面结构描述为矩形区域，因此适合于矩形版面 的结构表达。除了定义版面的大小和结构外，f d l 还定义了一些谓词来描述版 面分析的过程。f d l 只能描述矩形结构的版面，对于直角多边形版面和非矩形 版面，这种语言无法描述其结构。此外，f d l 也不能描述版面的逻辑属性。 文件结构语言d a l 文件结构语言d a l ( d o c u m e n t a r c h i t e c t u r el a n g u a g e ) 是对形式描述语言f d l 的一个改进，它不仅可以描述矩形版面的结构，也可描述非矩形版面的结构，因 而具有更强的表达能力【4 。但这种语言虽然考虑到了文件版面的逻辑结构属性， 却没有给出逻辑属性的具体描述方法。 版面理解的算法多种多样，但都是建立在特征抽取的基础上的。具体地说， 算法的第一步总是先提取版面的图像特征，然后根据这些特征对图像文件作分 析，得到图像文件的版面结构，完成版面的理解过程。版面的特征提取是版面理 解算法的基础，不同的特征可以导致不同的算法。常用的特征函数有投影 ( 口r o j e c t i o n ) 、游长( r u nl e n g t h ) 、穿线( c r o s sc o u n t ) 等几种。 通过采用特定的特征函数，一般有下面几种常用的版面理解算法。 1 递归纵横切割法 递归纵横切割法常常采用投影和穿线等图像特征，常见的是基于投影的二分 法。基于投影的二分法是这样进行的：首先，求出整个图像版面的水平( 或垂直) 投影，然后，在一定的阈值下找出其中最宽的低谷，并以此为界将整个版面分为 上下( 或左右) 两个区域，对分出来的每个区域，再在另一个方向上作投影，重 复上述过程，把它们各分出两个更小的区域，如此往复，构成一个递归过程，直 到分出各个版面基元块为止。 8 塞查处理皇壬互遗主切盐拉盔曲班宜 不难看出，二分法中常常重复提取同一特征，存在很多冗余运算，因而实际 上通常采用的是基于多叉树模型的多分法。多分法的递归分割过程与二分法类 似，但是，在每次投影之后，多分法都尽可能多地找出可供分割的低谷位置，从 而对各区域作出尽可能多的分割，减少了递归层次，避免了同一特征的多次抽取， 降低了算法的时间复杂度。基于投影的递归纵横切割法简单易行，可以很好地分 析无嵌入式矩形版面。对于嵌入式矩形版面，可以采用基于穿线的递归纵横切割 法作分析理解。 2 游长平滑算法 这种方法是在二值图像上进行的。这种算法的主要思想是：通过闽值过滤和 黑白转变的办法去短游程长，获长游程长，从而使图像的信息块得到加强，以利 于图像的分析理解【5 ，其过程如下： ( 1 ) 计算水平和竖直方向的所有游长。 ( 2 ) 沿水平方向逐行扫描图像，凡是游长小于阅值鼠的白游程，都将它们替 换为黑游程，得到图像h 。 ( 3 ) 沿竖直方向逐行扫描图像，凡是游长小于闽值文的白游程，都将它们替 换为黑游程，得到图像v 。 ( 4 ) 将图像h 和图像v 相与，得到新的图像，即为平滑结果。 游长平滑的结果，使得图像中连通块大大减小，信息块得到加强，从而降低 了进一步分析的难度。 3 h o u g h 变换法 h o u g h 变换是图像分析中的一个经典方法，最初是用来检测图像中的直线段 的，现在已被用于模式识别的很多领域。h o u g h 变换可以看成是几何空间上的点 对参数空间上的点进行“投票”的过程，这个过程包括3 个步骤： ( 1 ) 设定一个二维记数器阵列c ( k ，b ) ，将其初始值置为0 。 ( 2 ) 对几何空间上的一点p ( x ，y ) 在参数空间上所对应的直线b = 一x k + y ， 将直线上的各点所对应的计数器单元加l 。 ( 3 ) 对所有几何空间上要考察的点作( 2 ) 的处理。计数器阵列上的峰值所对 应的参数，就是几何空间上直线方程的参数，也就是说，通过h o u g h 变 换，我们找到了几何空间上的直线段。 图像文件通常包含一些直线段，例如表格、图形等等，分栏之间的分隔单元 也往往是成直线的黑边或白边。此外，文本的纹理也常常是直线行。因此，可以 通过h o u g h 变换对图像文件提取分隔子，确定版面的倾斜度，或用作表格的分析 处理。此外，h o u g h 变换具有较强的抗倾斜和抗噪声的能力，这是它的一个突出 优点。 9 塞奎熊理皇壬呈这主切公遮苤鳆班究 4 连通块合并算法 连通块合并算法一般是基于分割子的合并算法。这种算法要求先找出白边、 黑边等分割子，然后，或者对分割子本身进行合并，或者根据行距几乎相等的排 版规则，直接将检测到的字符串等块元素进行合并，最后将分割出来的各个块再 作合并，从而得到所需的文本块等版面基元 4 。 基于分割子的合并算法主要由以下2 个步骤组成： ( 1 ) 提取分割子。一般有黑边分割子和白边分割子，利用游长平滑的方法选 出这两类分割子。 ( 2 ) 沿分割子方向将黑连通块进行合并。这一步将连通部件沿分割子方向合 并成文本行、图形、图片等，因为有分割子作指导，所以合并的判断条 件可以简化，合并的可靠性得以提高。 连通块的合并算法同时采用了自底向顶和自顶向底的策略，是一种效率较高 的混合分割算法。 5 分割算子跟踪算法 分割子跟踪算法是在找出分割子的基础上作跟踪的混合算法 4 。这种算法主 要有2 个步骤： ( 1 ) 提取分割子，主要是水平和垂直方向的白边。 ( 2 ) 建立相交表i t ( i n t e r s e c t i o nt a b l e ) 和方向表d t ( d i r e c t i o nt a b l e ) 。 _ 。是一个二维表，其中行数m 和列数n 分别是水平分割子和竖直分割子 的数目。i t 是根据提取的水平分割子和竖直分割子的相交情况来建立的。对表 中的每一个元素i t ( i ，j ) ，有 嘲，= ：，篙篇竖直艚蛹相交 从上式可以看出，在i t 中值为l 的点所对应的2 个分割子就是分栏的边界。 这样的分栏可以是矩形，也可以是直角多边形。 d r , 。也是一个二维阵列，它的元素是三元向量( 嗔，占，d ) ，其中，4 和占，分 别表示跟踪时在行方向和列方向的步长，d 采用4 一连通链编码，表示上、下、 左、右4 个跟踪方向。 在i t 和d t 上进行的跟踪实质上是轮廓跟踪，跟踪的结果就是版面基元的物 理结构。 6 分形算法 这种算法 6 的思想来自分形几何。它利用一种“毯子技术”( b l a n k e t t e c h n i q u e ) 的方法对图像进行变换和处理，在求图像子块的占一平行体的基础 上，求出隔图像子块的近似盒维数，在根据子块的分形维数来确定各子块是文本 1 0 塞奎处理皇至至速主切金技苤曲班宣 块还是背景块，从而对图像文件作出分析。 前述的几种版面理解算法是在二值图像的上进行的，而分形算法不同于那些 算法，它是在文本的多灰度级图像上进行的。它不必递归，可以一次性获得版面 区域的图文属性，而且对几何机构复杂的版面也能作出分析理解。但是，这种算 法只适于多灰度级图像，而无法对二值图像分析，因而具有一定的局限性。 7 基于模型的版面理解 在模型库的基础上对版面作分析理解，实际上就是根据各个模型类的描述， 对所要分析的图像文件作一个分类，根据版面所属类的描述，便可以得到有关版 面的物理结构和逻辑结构的描述，即得到了分析理解的结果。 基于模型的版面理解算法( m o d e j - b a s e dd o c u m e n tu n d e r s t a n d i n g ) 实际上采 用了模式识别的思想和技术，其关键是分类器的构造，即模型的建立。目前已出 现了有关表格、支票等模型的版面理解系统。0 t a k i n d e l e 提出了用树状文法 来构造同样模型的方法 4 。 8 基于知识的版面理解 由于版面形式复杂多样，使得大多数版面分析的算法都出现了一定的局限 性。不同的杂志、报纸等的排版常常采用不同的行距、字距等，因此，为了对各 种版面都能作出可以接受的分析结果，版面分析系统不得不经常调整各种阈值。 如果给系统引入一些排版知识，使它具有一定的知识水平，那么，分割版面基元 和标注基元的逻辑属性就有了一定的依据，从而使得分析理解的准确率得到提 高。 版面知识实际上是一些规则，这些规则是具有实用性的普遍规则。从规则所 起的作用来看，有些规则表达了版面基元的性质或基元之间的关系，而有些规则 则表达了版面分析应该怎样进行。前一种规则被称为知识性规则，后一种规则被 称为控制性规则。知识性规则构成了知识库，控制性规则构成了推理机。两者协 调作用，共同指导版面的分析理解过程。 基于知识的版面理解算法的关键是知识库的构造和求精，特别是版面知识的 自动获取。f l o r i a n ae s p o s i t o 等人提出了归纳推理的改进算法上下文相关 的学习算法。该算法建立在用谓词逻辑来表达规则的基础之上，采用的学习机是 f o c l ，表现为对h o r n 子句的学习 7 。 2 2 2 行字分割( 字符切分) 现有的字符识别技术是建立在字符分割的基础上的，特别是汉字识别，主要 是以单个字为识别单位，因而行字分割是o c r 系统必不可少的一个组成部分。 行字分割包括行分割和字分割两个方面。行分割一般来说比较简单，因为经过版 面分析和版面理解处理后，图像的文本块以及被分割并标注出来。根据文本的横 塞奎处堡皇至互这芏塑佥撞盔的硒窭 竖属性，利用投影法可获得文本的行高、行距，从而作出行分割。行字分割的主 要困难在于字符分割。其一，在中英文混排的图像文件中，由于英文字符或数字 的宽度常常是汉字宽度的一半，而汉字又有左右结构和上下结构，特别是左右结 构的的汉字，难以和2 个数字或英文字符区分开，从而导致分割的错误；其二， 行字的排版要求行头不能是标点，因此遇到行头出现标点的情况时，排版系统必 须调整行内的字间距，这种变化增加了切分的难度；其三，因印刷质量造成的字 符粘连或笔划缺失，同样也会造成切分错误。 在传统的光字识b i ( o c r ，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 ) d ? ，字符切分是其三 个步骤中的第一步： 假设从一个输入的文本图像开始： 1 ) 找到下一个字符( 字符切分) 2 ) 抽取字符图像的特征 3 ) 在给定字符集中找到与输入特征最匹配的成员，输出相应的结果 这三个步骤循环执行，直到所有的字符图像都已处理好。在第一步中，只是 要求回答一个简单的问题“何者构成个字符? ”许多研究开发人员已经进行了 大量的工作，试图来解决这一问题。一个字符是一个与系统将要识别的符号之 相似的一个模式。但要决定这个相似度，就必须将该模式从文本图像中分离出来。 而且，切分决策并不是一个局部的决策过程，并不与前一步和后续的决策完全独 立。产生一个和库中符合很好的匹配是必要的，但这对产生可靠的识别结果还不 够。就是说，后续的一个很差的匹配结果会导致需要重新考虑当前切分一识别结 果的正确性。甚至由于系统输出结果的上下文含义差强人意，一系列相当满意的 匹配结果也必须看作是不正确的切分一识别。 上文本图像 竖至坌塑l h _ 。_ 。_ 。一 上字符串图像 兰笙望坌i 。_ 。_ 。- 。一 0 字符图像 竺笙堡坚l 。- 。_ 。_ - 一 0 字符特征 坌鲞竖型l 厂面结果 1 2 塞查处理皇至要迅星切佥技苤的硒蕴 基于印刷体文本的多语种、多字体混排以及手写体文本的随意性给字符切分 带来的困难，许多学者对是否存在某种特征能够对这样的文本进行有效的切分持 否定态度，认为应该将切分和识别结果结合起来。因此，根据在整个过程中切分 和识别分类相互作用的不同方式，将字符切分算法分为两类：一类是传统的切分 方法( 或称直接切分) ，字符的切分是根据“类字符”特性而进行的；另一类是 基于识别结果的切分，系统在文本图像中搜索与字符表中各类别相匹配的图像 块。 在前一类方法中，判定一个切分是好的切分结果的标准是那些从极有可能是 有效字符的切分块中统计出来的通用特性，如字符高度、宽度、相邻部件间的间 隙等等；在后一类方法中，切分评价标准是识别结果的置信度，甚至还包括全部 结果的语法和语义的正确性。下一章将较详细的介绍中西文字符切分技术。 小结 在计算机技术飞速发展的今天，它的影响已经遍及人们生活的各个方面。中 文识别及中文文本处理便是这样的例子。在本章中，首先介绍了中文识别的研究 内容和汉字识别的特点，对于汉字识别的研究现状，国内目前研究得比较成熟的 是印刷体中文识别以及联机中文识别，脱机手写汉字的识别仍然期待进一步的研 究。其次，本章介绍了与字符识别联系极其紧密的文本处理这一课题，对于一个 汉字识别系统，文本处理及理解也是其中的一个重要组成部分。文本处理包括版 面理解和行字分割两方面，对版面理解，本章