（模式识别与智能系统专业论文）中文版面中标点符号的提取与识别.pdf

颈士论文中文版面中标点符号的提取和识别 摘要 版面分析技术是o c r 系统的重要组成部分，对o c r 系统中字符识别的速度和正 确率都有着很大的影响。标点符号是文档图像中重要的组成部分，它决定着文字块中 句子的结构和区域，提取和识别出标点符号有利于版面中文字块的迸一步分割和理 解。而长期以来，研究者们在对版面分析的研究中部比较重视文字的分割，而忽视对 文档中标点符号的分割和识别，所以对文档中的标点符号进行提取和识别有着很重要 的意义。 本文主要研究中文文档中标点符号的提取和识别问题。主要工作包含以下内容： ( 1 ) 研究了版面分析预处理的过程。本文首先在比较各种已有方法韵基础上，采用 h 0 l l 曲变换的方法对图像进行倾斜校正，然后用中值滤波方法对校正后的图像进行去 噪，最后采用基于矩的闽值选取方法进行二值化处理，实验结果表明可以得到较好的 预处理结果图，方便了进一步的分割。 ( 2 ) 在版面分析过程中，首先研究比较了传统的投影法和连通域方法，然后在此基 础上，采用一种基于膨胀算法的连通域搜索法对文档图像进行了分割。该方法根据数 学形态学的原理对文档图像进行膨胀处理，并在此基础上进行连通域搜索，获得更加 有效的分割效果。 ( 3 ) 在预处理和版面分析步骤获得的结果图像基础上，采用了以相似度为决策函数 的模板匹配方法以及基于支持向量机的方法的对标点符号分别进行识别。实验表明两 种方法都可以有效的识别出文字块图像中的标点符号。 关键词：版面分析，版面分割，倾斜校正，投影法，连通域法，字符 识别，模板匹配，支持向量机 硕士论文中文版面中标点符号的提取和识别 a b s t r a c t t h ed o c u m e n tl a y o u ta n a l y s i si sa l li m p o r t a n tt e c h n o l o g yo f t h eo c rs y s t e m , w h i c h h a sp l a y e dm o i m p o r t a n tr o l eo nt h ec h a r a c t e rr e c o g n i t i o na n dp r e c i s e n e s si no c r s y s t e m t h ep u n c t u a t i o ni si m p o r t a n tp a r to fd o c u m e n t , w h i c hd e c i d e st h es t r u c t u f ea n d r e g i o no fs e n t e l i c e i ti sb e n e f i tw i t hd o c u m e n ts e g m e n t a t i o ni fw ec a na b s t r a c ta n d r e c o g n i z et h ep u n c t u a t i o ni ns e n t e n c e b u t ，m o s tr e s e a r o h e r sw h op u tm o s ta t t e n t i o no nt h e w o r dh a v ei g n o r e di t s o ，i ti sv e r yi m p o r t a n tt h a tt h i sp a p e rp a yh i sa t t e n t i o n0 1 1t h e p u n c t u a t i o n t h ep r o b l e mw h i c ht h i sp a p e rf o c u s e s i sh o wt oa b s t r a c ta n dr m g i l t z et h e p 蚴t i o n i ns e n t e n c e t h ec o n t e n t sa r em a i n l yc o m p o s e do f ； ( i ) t h i sp a p e rs t u d y o i l t h e p r e t r e a m a e n t p r o c e s s o f d o c u m e n t l a y o u t a n a l y s i s b a s e do i lc o m p a r i n g t h ee x i s t e d m e t h o d s ，h o u g h t r a n s f o r m i s u s e d t or e s o l v e t h e p r o b l e m o f s k e w c o r r e c t i o n , m e a n f i l t e r i s u s e d t os m o o t h t h es p e c k l e ，a n d a m e t h o db a s e d0 1 1m o m e n tt h r e s h o l ds e l e c t i o ni su s e dt oc r e a t et h eb i n a r yi m a g e ( 2 ) i nt h e 3 r o c e s 5o f d o c u m e n tl a y o u ta n a y s i s ，t h i sp a p e r h a ss t u d i e dt h ep r o j e c t i o n m e t h o da n dc o n n e c t i v i t y - s e g m c o t a d o nm e t h o d t h e n , am e t h o db a s e do n d i l a t i o nw h i c hb e l o n g st om a t h e m a t i c a lm o r p h o l o g y , t h i sr e s u l to fd o c u r n e a t a o a l y s i sb yt h em e t h o di sb e t t e rt h a n t h eo t h e rm e t h o d s ( 3 ) b a s e do i lt h er e s u l to ft h ep r e t r e a t m e n tp r o c e s sa n dt h ep r o g o s $ o fd o c u m e n t l a y o u ta n a l y s i s ，t h i sp a p e ru s e dt w om e t h o d s , w h i c ha x eb a s e do i lt e m p l a t e m a t c h i n ga n ds v m , t or e c o g n i z et h ec h a r a c t e r k e y w o r d ：d o c u m e n ta n a l y s i s ，d o c u m e n ts e g m e m a t i o n , s k e w c o r r e c t i o n , p r o j e c t i o n - s e g m e n t a t i o n , c o n n e c t i v i t y - s e g m e n t a t i o n , c h a r a c t e rr e c o g n i t i o n , t e m p l a t e m a t c h i n g ，s u p p o r tv e c t o rm a c h i n e s - 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名：函柙缉6 月日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名 尊卑 川缉臼珀 硕士论文中文版面中标点符号的提取和识别 1 绪论 1 1 引言 在现今的信息社会里，随着计算机技术的推广应用，尤其是互联网的日益普及， 人类越来越多地依赖计算机获得各种信息，大量的信息处理工作也都转移到计算机上 进行。在日常生活和工作中，存在着大量的文字信息处理问题，因而将文字信息快速 的输入计算机的要求变得非常迫切。这使得以键盘输入为主要手段的计算机输入设备 变得相形见绌，输入速度已经成为信息进入计算机系统的主要瓶颈，影响着整个系统 的效率。因此，要求有一种能将文字信息高速、自动的输入计算机的方法。目前，文 字输入方法主要有键盘输入、手写识别、语音输入，虽然简单便捷，但其输入速度不 高，对于大量已有的文档资料，采用这些方法要花费大量的人力和时间。因此，能够 实现文字信息高速、自动输入的只能是计算机自动识别技术，即光学字符识别( 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 ) 1 1 - 3 1 技术。 o c r 系统由以下几个部分组成： 1 图像的预处理： 在进行文档资料中字符识别时，首先要将印在纸上的字符，经光电扫描产生模拟 电信号，再通过模数转换将其转换为带灰度值的数字信号并输入计算机。纸张的薄厚 度、洁白度、油墨深浅、印刷或书写质量都要造成字形畸变，产生污点、飞白、断笔、 交连等干扰。所以，在单个汉字识别之前，要对这幅带有随机干扰、噪声的文档图像 进行预处理，预处理包括对原始图像的去噪、倾斜校正，若输入图像不是二值图像， 还首先要对该图像进行二值化。 2 版面分析： 这一步骤包括版面分割和版面的识别两步。版面分割就是要对文本图像进行总体 分析，分割出文本图像的各个属性块；版面识别即是要识别出文本图像的各属性块的 属性，即文本的文字块、图像、表格区域等等。 3 字符切割： 先将文本图像中的文字块切割为行或列，再从图像行或列中分离出单个字符。这 一过程很多时候在第二步骤中就可以实现。 4 特征提取： 从单个字符图像上提取统计特征或结构特征，是整个环节中最重要的，所提取特 征的稳定性以及有效性直接决定了识别的性能。在提取特征前常常先进行归一化、细 化等处理过程。 5 单字识别： 1 硕士论文中文版面中标点符号的提取和识别 从学习得到的特征库中找到与待识字符特征相似度最高的字符，该字符即为识别 结果。 6 后处理： 对单字的识别结果，利用词义、词频、语义、上下文等先验知识进行识别结果的 确认或纠错。 主要过程如图1 i 1 所示： 进入o c r 系统l 1 l 获取识别图像i 图像预处理 jl 版面分析 识 u 别 文本的切割 n 特征提取 l 上 单字识别 l i 后处理 i il 文稿校对 jl 识别结束 图1 1 1o c r 沉程图 目前文字识别技术已经广泛的应用到了各个领域中。它作为计算机智能接口的重 要组成部分，在信息处理领域中可以大大提高计算机的使用效率，是办公自动化、新 闻出版、计算机翻译等领域中最理想的输入方式，将庞大的文本图像压缩成机器内码 可以节省大量的存储空间。 国内很多高校和研究机构在版面分析方面和字符识别上都做出了大量的研究工 作，也取得了很大的进展。现在也有许多o c r 软件中都有版面自动分析功能。如： 汉王的尚书系列，表格自动录入系统，蒙恬o c r 文字扫描辨识系统，清华的文通 t h - o c r 系列等等，从这些产品的实际使用效果来看，它们在印刷体文字识别方面， 不论是识别速度还是识别率上，都基本上达到了令人满意的效果。但在版面分析速度， 硕士论文 中文版面中标点符号的提取和识别 准确性，自动化程度上都需要进一步的提高。 1 2 版面分析介绍 1 2 1 版面分析的发展 在早期的o c r 系统的研究中，人们并没有充分的认识到版面分析的重要性，而 是把注意力主要都集中在了字符识别上。但是，随着字符识别技术的日趋成熟，人们 对o c r 系统的要求越来越高，不仅要求系统能用，更要求系统好用。这时，系统在 版面分析上的不足，成为了制约整个o c r 系统性能的一个瓶颈因素，并逐渐引起了 研究者们的重视和关注这样，从上世纪8 0 年代后期起，国外的o c r 系统的研究者 们就开始对版面分析进行深入地研究。从1 9 9 1 年开始，国际模式识别协会开始每两 年举办一次“国际文档分析与识别”会议( i n t e r n a t i o n a lc o n f e r e n c eo bd o c u m e n t a n a l y s i sa n dr e c o g n i t i o n ，i c d a r ) h ，在已经举办的历届会议上，版面分析都是重 要议题之一，版面分析也就成为了模式识别领域的一个重要分支。 目前，对版面分析的研究已经取得了很多的成果，版面分析技术已经达到了相当 深入的水平，设计出了一些效果比较好的算法，也开发出很多能够使用的产品。但大 多研究都是针对英文、日文的版面，而中文版面与之存在很大差距，中文版面有其自 身的复杂性，因此，对中文版面分析进行深入地研究，具有十分重要的意义。 版面分析主要是要解决将单个字符图像从整个文本图像中分割出来的问题，它分 为版面分割和版面识别。为此，一般需要两个步骤，首先是对整个文本文档按不同的 区域属性( 文本区，图像和图形区，表格区等) 进行鉴别和分割，称之为文本的行切 分和字切分，只有当每一单个字符的图像都能正确地从整个文本页面图像中分割出 来，才有可能进行正确的文字识别，也就是说，一旦字符的切分发生错误，必然造成 难以校正的错误，在目前低质量的印刷文本识别中，字符切分引入的错误几乎达到总 错误的一半以上，可见它在文本识别中的重要影响。 1 2 2 版面分析的基本思想 版面分析的基本思想一般来说有两种嘲：自顶向下的分析方法和自底向上的分析 方法。 自顶向下( t o p - d o w n ) m 的分析方法是根据版面设计的思路，将版面划分为若干 区域，根据每个区域的信息确定该区域的属性，即确定该区域分别为文字域、插图域、 表格域等等，并对文字域间的连接关系予以描述。这是通过对图像沿水平、垂直方向 投影的方法寻找域间距，或者根据文字块间的间隔线或花纹线来确认域界。根据域界 硕士论文中文版面中标点符号的提取和识别 的坐标将整个版面分成若干文字块，并将这些文字块的形状归纳成几种标准多边形。 在跟踪域间距的过程中形成一种多边形，记录多边形的结构信息，建立文字域集的分 析结果。 自底向上( b o s o m u p ) 聊的分析方法是基于文字的排版过程，由局部到整体，先 提取局部区域的特征信息，再汇总得到相同特征合并的区域。例如，p a v l i d i s l 9 1 提出的 分析合并( s p r i t - a n d - m e r g e ) 方法。依据局部图像的特征进行分析，以确认各种数据 块的组合，有助于版面的理解。这是自底向上分析方法的优势，尤其在解决复杂版面 的切块中，比自顶向下的分析方法要好。 自顶向下和自底向上的两种分析方法，都是将版面按照排版的有关规则分块，前 者以特征相同的大块为界，将版面分成若干块；后者以不可分的最小字符或汉字为界， 根据间距特征将各小块合并为特征一致的文本块。对于无图的单文单栏或多栏的版 面，前者比后者速度快，而对图文并存、多文多栏的版面，前者分析难度大，后者以 局部特征的优势，先切分后合并，可以解决比较复杂版面的分析。 当然现在我们进行版面分割时，所采用的方法并不能严格的归入自顶上下或者自 底向上的类别中去。由于这两种方法都有自身的优缺点，所以将“自底向上”与“自 顶向下”的方法结合起来，即采用以“自底向上”为主，融入“自顶向下”某些思想 的方法，是目前公认的版面分析技术的发展方向。 1 3 字符识别简介 1 3 1 字符识别的发展 利用机器识别文字符号，最早是从1 9 2 9 年陶舍克利1 1 1 用光学模板匹配识别开始， 当时他做的方法是，使用1 0 块模板对应十个数字，把模板的数字部分镂空，依次把 待识别的数字投影到这十个模板上，当模板透过的光达到最小的时候，数字就被识别 成这块模板上的数字，这是模板匹配的思想的最早体现。电子计算机问世后，大约在 5 0 年代末，就出现了关于利用计算机识别数字及英文符号的研究论文了。对汉字进 行识别研究最早的是日本，他们的研究开始于上世纪七十年代，1 9 8 4 年，日本正式 推出用于实用的多体印刷体汉字识别装置，识别率和识别速度都达到了相当高的水 平。 而在字符识别方面，我国的研究工作起步也比较晚，到八十年代后期才有初步实 用的印刷体识别系统问世。经过众多研究者的不懈努力，现在对印刷体字符的识别率 普遍在9 5 以上，对于扫描质量比较好的文档图像来说，字符的识别率通常可以达到 9 8 以上。这说明我国在字符识别领域已经取得了长足的进步，国产的o c r 系统已 经达到了实用的要求。 硕士论文 中文版面中标点符号的提取和识别 1 3 2 字符识别的方法 字符识别的任务是把用版面分析方法从文档图像中分割出来的字符图像识别出 来，然后以文本的形式存入计算机中目前已有的字符识别方法主要有三种，即统计 决策的方法，结构分析法，和人工神经网络方法。识别方法同时也称为识别器，识别 器是整个系统的核心，识别器的结构通常如图1 3 2 1 所示： 图1 3 2 1 识别器结构图 统计决策方法就是使用字符图像的统计特征，如区域中黑象素、笔划及方向统计 特征、图像矩特征、字符投影特征等等，作为特征向量与字典库的标准模板进行匹配， 匹配根据一些判别尺度来分类，一般我们常用的判别尺度有距离准则和类似度准则， 这两种准则的基本思想都是把与待识量最接近的标准模式作为识别结果。 结构分析法又称为句法分析识别法，这种方法的主要思想是用代表字符形状本质 特征的结构信息，用字符模式，如笔划、部件等，构成分层结构来描述一个字符，通 过句法分析得到识别结果。 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r ka n n ) i 嚏一种模拟人脑神经元细胞的 网络结构，它是由大量简单的基本元件一神经元相互连接成的白适应非线性动态系 统，具有一定的学习和组织能力，通过调整神经元间的连接系数完成分类、识别等复 杂功能。 1 4 选题的意义及本文主要工作 长期以来，人们在对版面图像的分析和识别研究工作中，几乎所有的注意力都集 中到了对文字( 汉字、英文字等) 的分割和识别上，都忽略了对文字块的另一个重要 组成部分一一标点符号的分割和识别。其实，在文本图像中，特别是文字块中，标点 硬士论文中文版面中标点符号的提取和识别 符号有很重要的意义。文字块都由段落、行、句子、文字组成，标点符号正是决定了 文字块中句子的所在。分割出文字块中的句子对下一步分割有着很大的帮助，能够简 化下一步分割的难度。而且，当一个文本块中的标点符号被提取和识别出来后，对文 字块的研究工作就只剩下了文字识别的问题。所以，本文对文档图像中的标点符号单 独进行研究，进行文字块中的标点符号提取和识别，是一项很有意义的工作。 本文的主要工作： 首先，对文本图像进行预处理，包括用h o u g h 变换对图像进行倾斜校正，用邻域 平均法和中值滤波的方法去除噪声，分别比较了基于梯度均值、熵以及矩的阈值选取 方法对图像进行了二值化。 然后，在比较了版面分析的两种基本方法投影法和连通域法的基础上，采用了一 种基于膨胀算法的连通域提取方法对文字块中的标点符号进行了提取。 最后，在比较了已有的一些字符识别方法的基础上，根据标点符号自身的一些特 点，采用了模板匹配的方法和基于支持向量机的方法对提取出的标点符号进行了识 别，取得了比较好的效果。 本文所有标点符号的提取和识别过程，均已用v c + + 实现，得出了实验结果。 1 5 本文的组织结构 本文的主要工作是对文档图像中的标点符号的提取和识别 论文第一章首先介绍了版面分析、版面识别以及字符识别的研究背景、发展状况， 和应用领域，对版面分割和字符识别的一些基本方法作了简单的介绍。并分析了进行 这项工作的意义所在。 第二章主要介绍文档分割前的预处理过程，包括图像的去噪、倾斜校正、二值化 等主要步骤，并都给出了一些本文在研究过程中所运用的方法。 第三章介绍了版面分割的两种基本方法，即投影法和连通域法。投影法中介绍了 简单的二分法，以及多分法；连通域法中先是简单介绍了最基本的连通域搜索法，然 后使用了一种基于膨胀算法的连通域法，对标点符号进行了提取。 第四章介绍了字符识别的三种基本方法，即统计决策法、结构分析法和人工神经 网络的方法。并在此基础上分析了本文所采用的识别标点符号的方法。 第五章给出了实验结果。并在论文的最后对所做工作进行了总结和对未来工作的 展望 硕士论文中文版面中标点符号的提取和识别 2 版面理解前的预处理 在通过对文本文档扫描得到版面图像之后，由于种种原因还需要对其进行一些分 析前的预处理过程。这些预处理过程包括倾斜校正、噪声过滤、二值化等。下面就简 单介绍一下预处理的一些过程和具体方法。 2 1 文档图像的倾斜度校正 我们在用扫描仪对文件进行扫描以获得文档图像的时候，很可能由于扫描时文件 摆放不正，或者光源位置不佳等种种原因，使得我们所获得的文档图像有不同程度的 倾斜。当倾斜角度不大，并不影响以后的识别过程，我们可以忽略不计，但是若倾斜 角度较大，就会直接影响到以后的识别工作，如在以后工作中会用到投影法，要对文 档图像进行横向和纵向的投影，这时倾斜的图像会对投影的结果产生很大的影响。所 以，我们在识别前一般要对倾斜的文档图像进行校正。 倾斜校正就是要根据文档图像相应的倾斜角度，反向旋转文档图像，从而把图像 的倾斜度控制在对下面的版面分析工作没有影响的范围之内。设扫描所得的倾斜图像 为p ( x 。，y 。) ，倾斜角度为0 ，纠正后的图像为p ( x ，力，则倾斜校正的过程如下： ix i - i 。攀之5 m 曼i i 而i( 2 1 1 ) l y l - s m c o s v j l y o j 由上述过程可以清晰的看出，倾斜校正的关键就在于求出图像的倾斜角度目。知 道了图像的倾斜角度，倾斜校正就只需要对扫描所得的倾斜图像进行几何旋转即可。 目前，对文本图像的倾斜校正算法有很多，也比较成熟。方法主要有：基于h o u g h 变换的方法、基于投影图的方法、基于直线连续性的方法i n l ，交叉相关性方法1 1 2 1 、 最近邻簇类方法【埘、基于f o u r i e r 变换的方浏1 等，它们各有各的优缺点。 基于投影图的方法是利用投影图的一些特征进行图像倾斜的判断，这些特征包括 均方差、第一特征矢量、以及梯度特征等统计特性，但是，这种方法需要整个图像的 统计特征值，所以计算量和复杂度都较高；基于直线连续性的方法是选取文本图像的 某个子区域中字符连通区包围框底边中心点作为特征点，利用基线上的点的连续性， 计算出对应的文本行的方向角，从而得到整个页面的倾斜角；交叉相关性算法是基于 等距离的竖直或水平平行线上的像素点的相关性的方法，如以平行线上像素点建立相 关矩阵，并对矩阵在竖直方向上作投影，投影图的全局最大值对应于倾角，这种方法 虽然准确率高，但相关矩阵的计算量较大；基于f o u r i e r 变换的方法是利用页面倾角 对应于使基于f o u r i e r 空间密度最大的方向角的特征，将文档图像的所有像素点进行 基于f o u r i e r 变换，这种方法的计算量也是非常大，所以一般很少用到这种方法；最 ， 硕士论文 中文版面中标点符号的提取和识别 近邻簇类方法是先找出所有连通区中心点的k 个最近邻，计算每对近邻点的矢量方 向并统计生成直方图，直方图的峰值对应于整个页面的倾角，计算复杂度为“：) ， 其中n 为连通区个数。由于图像的倾斜校正不是本文的研究重点，在此就不一一赘 述，仅仅简单介绍一下基于h o u g h 变换的方法。 h o u g h 变换的基本思想就是将直角坐标系中的几何元素用参数空间中的元素重新 表示即在操作中，我们可以把直角坐标系x o y 中的任意条直线l 均由参数空间 p ，0 中的一个点( n ，b ) 表示： n 2 x c o s s l + y s i n 0 , 1 1 7 l ( 2 1 2 ) 式( 2 1 2 ) 中 ，y ) 是直线上任一点的坐标，岛为原点到直线l 的距离。o l 是x 轴与直 线l 的法线间的夹角。上式就是表示了直角坐标系x o y 平面上任意直线l 与参数空 间( 岛国的一点( n ，b ) 的对应关系。x o y 平面上的一直线g 与( 岛目) 空间中的点g t 一 一对应。所以可以由p ，空间中的点集来描述x o y 平面上的直线。 图2 1 1 表示了( a 印上的h o u g h 变换，其中( a ) 表示出了参数p 和0 ，( b ) 为( p ，d 空间。 ，一一 觚 朱7 t a ( b ) 例2 1 1 在实际计算中式( 2 1 2 ) 可以转换为： i 岛一 c o s 6 l + y s m e , ) i _ v a l u 8 一t o “力 戤2 ) v ( 玩l 乙2 2 ) v ( 勿2 t 锄2 ) v ( 砚l 乃笠) ) )( 3 2 2 1 ) 上述公式成立时，应合并两个连通区域五和z ，。 然后，是合并属于同一字符的连通域。前面已经介绍过，汉字往往都是有多个连 通域组成的，如。件”、。旦”就分别是两个连通区域，这些字必须加以合并后才能为 后面的分析提供整个字符的坐标信息。 同上，还是设z l 和z ：分别为版面上任意的两个连通区域，它们的左上角和右下 角的坐标分别为：z i ( z x l 。，私。) ，。，矾：) ，z 2 ( 。，矽：，) ，( 盘趋，勿。) 。 再加上一个变量：d v l a u e ，为字符间连通域间距离阙值。若z l 和z 2 这两个连通区域 的坐标满足下面的逻辑表达式： d ( ( z x 2 l ( z h 2 + d v l a u e l ) ) v ( z x l l ( z x n + d v l a u e l ) ) ， 、 v ( 锄l ( z y l 2 + l 兔, z a u e x ) ) v ( z y l l ( 勿2 2 + o v l a u e o ) ) ) ”叫 此时，z 1 和乙为同一字符的两个连通域，应把他们合并。 再把单个字符合并成行。同样的设z 1 和z 2 分别为版面上任意的两个连通区域， 再设d 为z l 和z ：两个连通域的最近距离，日为所有连通域的平均高度， 和分 别为z 1 和z 2 的高度，h 和z 为两个连通域合并后的连通区域的高度和长度。当下式成 立时： ( d 五时，z 1 和z ，的位 置关系为横向相连。其中，名为一常数。 最后，把同属一块的行连通区域进行合并当下式成立时，就应该合并两个连通 域： 【( i 魄一j i x ) v ( i 一1 2 i 五) 】 ( d 夕叻：( 3 2 2 4 ) 硕士论文中文版面中标点符号的提取和识别 其中，名为一大于l 的常数，为小于l 的常数，d 为z l 和乙两个连通区域在其 属性垂直方向上的最近距离。 至此，我们就可以得到版面图像上各个文字块的坐标。 由此，我们已经介绍完版面分割的两种最基本的方法投影法和连通域法。当然如 果仅仅使用上述两种方法，我们在版面分割的过程中，会遇到很多困难，这两种方法 都有其局限性，在前面的介绍中我们也都分析过了所以，我们在进行版面分割时， 我们一般都把这两种方法结合起来，并做一定的改进，尽量让分割的过程简单，实用， 效率高。 一 3 3 本文提取标点符号所用方法 本文对标点符号的提取采用的是一种基于膨胀算法的连通域搜索法，其中也结合 了投影的方法上节介绍的是连通域搜索算法的一般过程，但是，我们在实际操作中， 一般并不直接对文本图像进行连通区域的提取。因为直接对文档图像进行连通域的提 取是基于像素的，这样我们提取的连通域会非常多，而且非常小，然后再根据字内部 的间距、字间距，行间距等特性对它们进行合并，以形成大的连通区域。这样的过程 会比较复杂，计算量大，速度慢。所以，在文档图像分割之前，我们首先对其进行膨 胀处理，将相邻的字词，句子，以及属于同一段落的相邻行连接起来，以形成相对独 立和大的连通单元，这样进行下一步分割工作的时候就比较方便。这其实就是把“自 顶向下”和“自底向上”的两种技术路线相结合的一种方法。 对文挡图像进行膨胀处理，属于数学形态学1 2 7 - 3 1 1 的范畴。形态运算的基本思想就 是用具有一定形态结构的结构元素去度量和提取图像中的对应形状，达到图像分析和 识别的目的。形态运算可以简化图像数据，在保持图像的基本特性的基础之上消除不 相干的结构。这里我们只讨论对二值图像的形态运算。 这里，我们运用的是数学形态学中的膨胀技术。膨胀是在结构元素的约束下，将 与物体接触的部分背景点合并到该物体之中的过程。进行这种运算后，物体的面积增 大了相应数量的点。例如，假设结构元素是半径为r 个像素的小圆，我们要进行膨胀 运算的元素是一个大圆。那么膨胀运算的结果就是，沿大圆的边界向外扩展了r 个像 素的宽度，也就是说，被操作的对象大圆的半径增加了r 个像素。那么在被膨胀的图 像中，两个相邻的物体的半径各被增大了r 个像素，如果它们之间在某一处的相隔距 离小于等于2 r ，那膨胀后的结果就是的这两个物体在这一处连通，合并为一个连通区 域。这样，在被膨胀的图像中连通区域的个数就减少了，单个连通区域的面积相应的 增大了。这就是我们进行膨胀处理的目的。 在介绍膨胀运算之前，先介绍一下平移转换m l 。设a 和b 是两个二维集合，a 和b 中的元素分别是：a = ( a t ，口2 ) ，b = ( h i ，6 ：) 。再定义x = “，x 2 ) ，对集合a 做平 硕士论文 中文版面中标点符号的提取和识别 移转换定义如下； ( 彳) ，= c i c = a + x ，f o r a 彳( 3 3 1 ) 膨胀运算的数学定义如下： 彳o b = x i 【( 口) ，n 4 】妒( 3 3 2 ) 这个公式表示a 被b 膨胀，记为j 4 0 口，o 为膨胀算子，b 一般称为结构元素。 集合台称为集合b 的映像集，定义为：蜃= 缸i 工= - b ，b b ) 。( 雪) ，表示对集合雪做 平移转换。由此可以看出，膨胀过程是对结构元素b 先做关于原点的映射，然后平 移x 。a 被b 的膨胀是雪被所有x 平移后与a 至少有一个非零公共元素。根据这个解 释，上式也可以定义为： 0 0 b = x l 【( 召) ，n a 】)( 3 3 - 3 ) 相对于基本的基于连通域方法的版面分析方法所提取出的很多的较小的连通区 域，通过进行膨胀处理后的文档图像中所包含的连通域“变大”了显然这对之后的 连通域的搜索工作是大有裨益的，“变大”的过程就是一个膨胀处理的过程，膨胀处 理后将相邻的字词，以及属于同一段落的相邻行连接起来，形成了相对独立的连通单 元。“变大”的连通域使得对它们的搜索工作相对变得简单，速度明显加快，且降低 了之后的合并的工作量，这也就是改进后的算法与原算法的最大不同所在。 下面给出算法过程的简单描述： ( 1 ) 首先，选取膨胀模块，并对图像进行膨胀运算。 膨胀模块的选取还是依赖于文档图像自身的一些特征，如字符间的间隔，文本行、 段之间的问隔，各个属性块( 如文本块、图像块、表格块等等) 之间的间隔，以及它 们之间间隔的大小顺序等特征，这些在前文都做过一定的介绍。这个算法就是把文档 图像进行膨胀后，再来提取基本连通域。 显然，这一步是本算法的最关键所在，最关键的就是膨胀模块的选择删。上文已 经介绍过了膨胀运算，这里所提的膨胀模块就是前文介绍的结构元素b 。我们运用膨 胀运算的目的就是要膨胀字符以及字符内的部件，减少连通域，从而减少运算量。 膨胀的尺寸就是膨胀模块的边界到原点的距离，也就是膨胀模块的半径。在这里 我们对文档图像的膨张也作出一个改进，即对图像分别作水平方向和垂直方向上的膨 胀，这两个方向上的膨胀尺度由文档图像本身的特征来决定，一般来讲水平膨胀和垂 直膨胀的尺度是不一样的。所以这里的膨胀模块有两个膨胀尺寸；水平膨胀尺寸和垂 直膨胀尺度。 对于文档图像，特别是文本块中，同属一个文本段的行在垂直方向上的间隔比较 小，在水平方向上同一行的字符间以及字符内部的间隔较小。相反地，属于不同段间 的间隔较大，因此一般来讲我们设定的垂直膨胀尺寸较大，水平膨胀尺寸较小 ( 2 ) 提取出较小的连通区域 硕士论文中文版面中标点符号的提取和识别 对文档图像进行膨胀运算后，属于同一区域的像素点，小连通区域大多粘连起来， 形成了较大的连通单元，这时候我们再进行连通域的提取，可以运用边缘检测1 3 4 1 的方 法来进行，每个单元都可以用一个闭合的曲线表示出来。然后，我们可以采用一个 n x 开大小的模板对经过边缘提取出的区域进行涂抹，如果该区域小于我们所设的模 板，就可以认为该区域为一个小的连通域，需要进行合并。疗x h 大小的模板可以根据 实际需要选取，比如在对中文文本图像的分析中，此模板就可以取为一个文档中汉字 的大小。 ( 3 ) 搜索大的连通域，对小的连通域进行合并 经过第二步之后，我们获得了图像中比较小的连通区域，可以用最优路径搜索法， 采用宽度优先的算法，并以“四邻域”搜索出较大的连通域，通过得到较大连通域完 成小连通域的合并。 搜索较大连通域的算法如下： 第一步，对图g 进行搜索，首先选择起始区域，设为s ，建一个扩展表o p e n ， 把s 放到0 p e n 表中 第二步，再建立一个c l o s e d 已扩展的表，初始值为空 第三步，若o p e n 表为空，则退出。 第四步，选择o p e n 表上的第一个区域，把它从o p e n 表移出并放进c l o s e d 表中，称此区域为区域n 。 第五步，搜索区域n 的邻域。若搜索不到区域n 的邻域，则转向第三步。 第六步，把区域n 的所有邻域放到o p e n 表的末端，转向第四步。 ( 4 ) 获得完整的连通区域 按上述算法搜索完一块大的连通域后，设版面中的矩形连通区域尼为四元组： 置= ( 五。，x 。，五：，k ：) ，其中，c 以。，五。) 、( 五：，墨：) 分别为矩形区域焉的左上角、右 上角坐标。比较这个区域中的所有小连通域的左上角和右下角的坐标，在比较的结果 中，取最小的坐标值作为大连通区域的左上角坐标( 墨。，墨。) ，最大的坐标值作为大连 通区域的右下角的坐标值( 五：，z ：) ，记录下这块大连通区域的坐标，然后再重复进行 以上步骤，搜索其他的大的连通区域，直到把整个图像上的大连通区域搜索完为止。 ( 5 ) 检查合并连通域 经过以上步骤后搜索到的连通区域，很可能会出现这种情况：两个区域之间间隔 很小，或者一个区域包含于另外的区域之中，这时候就有必要对搜索到的区域进行合 并。 设置= ( 五- ，k 一，五：) ，其中，( 五，e 。) 、c 墨：，墨：) 分别为矩形区域置的左上 角、右上角坐标设b = ( 砭。，j 乞，圪) ，其中，( 邑。，艺。) 、c x 趋，) 分别为矩形 区域r ，的左上角、右上角坐标。若两个区域满足下面的关系，则合并这两个区域： 2 6 硕士论文中文版面中标点符号的提取和识别 i ) 五l 砭。 ：i 乞且k l e 1 e 2 ，也就是说两个区域置和q 有重叠的部分； n ) x t l x 2 l 如 x 1 2 且五1 e l 墨2 ，也即区域置包含区域玛； l i d 拓i i 了而而s 肘； 至此，算法完毕 下面，重点介绍一下膨胀尺寸的选择方法。决定膨胀尺寸的文本图像特征有字符 间距、行间距、段间距等等，这些间距可以用投影的方法来得到。但用投影法得到的 间距数值会非常多，这时候就产生了一个阈值选择的问题。我们可以用聚类的方法来 决定膨胀尺寸的选择，一般用k 一均值聚类法。 k 一均值聚类法要求各类样本到聚类中心的距离平方和最小，这种方法是建立在 误差平方和准则的基础上的。具体步骤如下： 设样本集为： 舛 ( 1 ) 任选k 个初始聚类中心毛( 1 ) ，乃( 1 ) ，气( 1 ) 。一般选样本的开头k 个 样本作为初始聚类中心。 ( 2 ) 然后逐个将模式样本集 砖的每一样本按最小距离原则分配给k 个聚类中 心，形成k 个类群，即在第m 次迭代时，若 肛一z ，( 埘) 0 ，j ( 幻i = l ，2 ，m 且i j( 4 2 1 2 ) 与类峨和留，相联系的区域之间的边界，称为判别边界。有下式表示： z ( x ) - f a x ) = 0 ( 4 2 1 3 ) f a x ) 作为判别函数，有很多种不同形式，都是根据某种判别准则来设定的，常 用的判别标准有：距离准则，类似度准则等。下面就介绍两种比较典型的统计决策技 术：最小距离分类和最近邻分类鲫 1 最小距离分类器 最小距离分类器是线性分类器，它是以待识别字符与参考向量或特征空间中的一 些特征点之间的距离作为分类准则。 硕士论丈 中文皈面中标点符号的提取和识别 设有m 个参考向量：墨，岛，& 。最小分类器的思想就是： z 一峨，即特征向量x 所表示的输入模式在峨中。 常用的距离有下述几种： ( 1 ) 明考夫斯基距离： i ( x ，趵= 【l 五- - $ ，i q p i 耐 几种特殊情况： 当g = 1 时，为绝对值距离： f ( x ，s ) = e i 一丑i 当q = 2 时，为欧氏距离： 当陋- s 。l = m i n 枣t ， ( 4 2 1 4 ) ( 4 2 1 5 ) f ( x ，回= 1 f 一) 2 ( 4 216 ) ( 2 ) 马氏距离 当x ，s 两个m 维向量呈正态分布，且具有相同的协方差矩阵a 时，其马氏距离 为； ，( x ，s ) = ( x - s ) a 。1 ( z s ) 7 】l 心( 4 2 1 7 ) 分别计算待识别字符的特征向量x 和字典中特征向量s 之间的距离，求出其中最 小的f ( x ，s 。) ，就可以判别x 属于第i 类了 2 最近邻分类器 上文说过，常用的判别标准有距离准则和类似度准则，最小距离分类器运用的就 是距离准则。同样，我们也可以用类似度准则来构造判别函数，这就是最近邻分类器。 在最近邻分类器中，我们定义类似度函数为r ( x ，d 【3 9 1 ，具体定义如下式： 郴，。最吊一孵 固 其中，分子为向量x ，s 之间的内积，分母中l 例i ，l p 0 分别为向量x ，s 的模，口是 向量x ，s 在m 维空间之间的夹角。将m 维向量带入上式得到： ( + 丑) g ( x ，回= 1 l _ - 一 ( 4 2 1 9 ) 【x ；s 2 t = lp 由上式可见，当x ，s 两个向量完全相同时，它们之间的夹角为0 ，g ( x ，研= 1 ，它 硕士论文 中文版面中标声符号的提取和识别 们的距离，( 五s ) = 0 。 当然，这种类似度的判别也是理想情况下的，在实际的文本图像中，总存在很多 的干扰影响，用上面的类似度准则判别来解决字符识别的问题就将会出现许多错识。 因此，提出了以下的复合类似度的方法。 设岛为给定的标准文字的特征向量，现在我们构造三个相互正交的图形办，唬， 晚，如下式所示： 加赢( 4 2 1 1 0 ) 纠南+ 曲，厕( 4 2 1 1 1 ) 丸2 啬，丽( 4 2 1 1 2 ) 魁泸警确= 等m 黼 【( z ，妒) 2 】l 2 这样，复合类似度r 何，$ = 上生 i 五疆一( 4 2 1 1 3 ) 在上式中，每类文字有t - - 个标准的模板，这虽然增加了字典的容量以及判别的 时间，但是其抗干扰的能力也大大增强，使识别的准确性大大提高，所以这样做还是 很值得的。 属于统计识别的方法主要有以下几种i 蚓：模板匹配法、笔画复杂性指数方法、四 边码法、粗网格特征、特征点法、变换特征法、笔段特征法、包含配选法等等，这里 就不一一介绍。 4 2 2 结构分析的方法 结构分析的方法也叫做句法方法，就是用一定的句法描述一个字符的结构。按照 句法的方法，认为每一个字符都是由它的各个部分按照一定的顺序组合在一起的，字 符的各个部分称为子模式或者模式基元。字符的这种组合顺序与语言的组织形式之间 有一定的相似性，这也就是称之为句法方法的原因所在。模式识别常以这种句法的方 式进行，即由一组的给定的句法规则来剖析模式的结构。 句法模式识别的示意图如图4 2 2 1 所示。 图中的左半部是识别部分，右半部为分析部分。识别部分就是对字符进行预处理、 硕士论文中文版面中标点符号的提取和识别 基元包括基元和子模式之间关系的提取、以及句法分析组成。分析部分包括基元选择 和文法、结构推断。 图4 2 2 1 句法模式识别的示意图 在句法方法中，一个模式由一个句子表示。该句子属于一个文法所规定的语言， 用一组模式基元和他们的组合关系来提供结构描述语言，支配基元组合成模式的规则 由所谓模式文法来确定。模式结构信息的另一种表示方法是利用关系图，在关系图中 结点表示子模式，分支表示子模式之间的关系。 一条直线可由