（通信与信息系统专业论文）文档图像的文种识别系统.pdf

四川大学硕士学位论文文档图像的丈种识别系统 文档图像的文种识别系统 通信与信息系统专业 研究生：昊长生指导教师：罗代升 摘要 在当今时代，网络和多媒体技术迅猛发展，在促进了信息交换的 同时，也带来了对信息的巨大需求。光学字符识别o c r 作为计算机信 息录入的一个重要技术，也得到了飞速发展。文种识别作为o c r 技术 的前端和基础，同时也是自动化处理工作中的重要部分，近年来得到 了广泛的关注与研究。 本文设计和实现了一个文档图像的文种识别系统。该系统运用于 我们的实际工作中，取得了较好的效果。该系统由预处理、版面分析、 文种识别三大部分组成。本文的主要研究工作有： ( 1 ) 图像预处理。预处理是图像处理中一项很重要的工作，预处 理的质量直接影响后续工作的效果和成败。本文着重介绍我们改进的 h o u g h 变换方法，用于文档图像的倾斜校正。这种算法，通过以下措 施减小了计算量：采用合适的量化角度，减小量化步长：选择子区域 取代完整的图像，减小待处理的数据量；选取特征点集而不是处理区 域全部像素，进一步减小待处理的数据量。最后，为了提高图像质量， 不是简单地旋转而是用像素面积插值法进行倾斜的校正。 ( 2 ) 采用投影法进行简单版面的分割。改进了常用的递归算法， 使用多叉树取代二叉树算法，大大减小了冗余运算，降低了算法的复 杂度。为了避开投影法对嵌入式等复杂版面分析中的失效，充分利用 投影法简单快捷的优点，我们将投影法应用于区域提取和文字行的切 分上。 ( 3 ) 金字塔模型的版面分割。本文提出了一种新的基于形状的版 面分析方法一基于金字塔模型的版面分割，解决了复杂版面分析问 题。该方法符合人类视觉由粗到精的特点，我们改进了基于连通区的 四川大学硕士学位论文 文档霉像的文种识别系统 特征选择，并取得了较好的分割效果。 ( 4 ) 凹度特征算法。在文种识别部分，我们改进了凹度特征算法， 避免了确定文字行参数和计算方差等计算工作；改进了基于小波纹理 的文种识别算法，使用可变阈值代替距离公式，使得判决结果可按用 户意愿调节，并增加了拒识功能，使识别工作更具人性化、灵活性、 交互性；提出了一种叫穿越次数的算法，实验证明这种算法具有很高 的准确率，是我们在文种识别工作中的一个有益探索和很大进步。 关键词：文档图像处理，h o u g h 变换，倾斜校正，金字塔算法，版面 分析，穿越次数法，文种识别 璺型盔堂堡主堂竺丝壅 苎堡里竺塑塞登望型墨塾 a s t u d yo fl a n g u a g er e c o g n i t i o ns y s t e m f o rd o c u m e n ti m a g e s m a j o r ：c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m s p o s t g r a d u a t e ：w uc h a n g s h e n gs u p e r v i s o r ：l u od a i s h e n g a b s t r a c t i nt h i st h e s i s ，ad o c u m e n ti m a g ep r o c e s s i n gs y s t e mi s d e s i g n e da n d p e r f o r m e d i tc a nb ea p p l i e df o rl a n g u a g ei d e n t i f i c a t i o n t h es y s t e m c o n s i s t so f i m a g ep r e p r o c e s s i n g ，l a y o u ta n a l y s i s ，a n dl a n g u a g e i d e n t i f i c a t i o n t h em a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o ni n c l u d e ： ( 1 ) i m a g ep r e p r o e e s s i n g i no r d e rt od e t e c ta n dc o r r e c tt h es l o p ya n g l e s o fa ni m a g e ，am e t h o db a s e do nh o u g ht r a n s f o r mi sp r e s e n t e d t or e d u c e t h ec o m p u t a t i o no fh o u g ht r a n s f o r m ，i ti sm o d i f i e di nt h ef o l l o w i n gw a y s a na p p r o p r i a t eq u a n t i t a t i v e a n g l es t e pi s t a k e nt od e c r e a s en u m b e ro f a n g l e s ；as u b - r e g i o no t h e rt h a nt h ew h o l ei m a g ei su s e dt or e d u c et h e d a t at ob ep r o c e s s e d ；f e a t u r e dp i x e l s ”a r ee x t r a c t e dt or e d u c et h ed a t a f u r t h e r + t oi m p r o v et h ee f f e c to fi m a g er e c t i f i c a t i o n ，t h ea r e a st h a tt h e o r i g i n a lp i x e l so c c u p ya r eu s e dt oc a r r yo u tt h ei n t e r p o l a t i o no fa f t e r r o t a t i o n b l a n kp i x e l s ( 2 ) r e c u r s i v e d i c h o t o m y a l g o r i t h m b a s e do n p r o j e c t i o n o f h o r i z o n t a l v e r t i c a lo r i e n t a t i o ni sap r a c t i c a lb u ti n e f f i c i e n ta l g o r i t h mf o r d o c u m e n tu n d e r s t a n d i n g t oi m p r o v et h e e f f i c i e n c ya n dr e d u c et h e c o m p u t a t i o n a lc o m p l e x i t y ，t h ed i c h o t o m yi sr e p l a c e dw j t hp o l y t o m y a l g o r i t h m ，t h ep o l y t o m ya l g o r i t h mc a nb ea p p l i e dt os u b r e g i o n s e l e c t i o na n dc h a r a c t e rl i n e sd i v i s i o n ( 3 ) an e ws h a p e - b a s e dm e t h o d ，l a y o u tu n d e r s t a n d i n gb a s e do np y r a m i d m o d e l ，i sp r o p o s e dt os o l v et h ep r o b l e mo fc o m p l e xl a y o u ts e g m e n t a t i o n e x p e r i m e n t ss h o wt h a tt h em e t h o dc a ng e th i g hv e r a c i t ya n dh a sh i g h 四川大学硕士学位论文 文档图像的文种识别系统 a d a p t a b i l i t y ( 4 ) i nl a n g u a g ei d e n t i f i c a t i o n ，ad e v e l o p e du p w a r d - c o n c a v i t ya l g o r i t h m i s p r o p o s e d t oa v o i dp a r a m e t e rm e a s u r i n go fc h a r a c t e rl i n e sa n d d e v i a t i o nc a l c u l a t i o no f t h e p a r a m e t e r s ； a n i m p r o v e dw a v e l e t t e x t u r e - b a s e dl a n g u a g ei d e n t i f i c a t i o nm e t h o di sp r o p o s e ds ot h a tt h e i d e n t i f y i n gw o r kc a nb em o r ei n t e r a c t i v ea n dm o r ef l e x i b l e ；am e t h o d ， c a l l e dr u nn u m b e ra l g o r i t h m ，i sa l s op r o p o s e dt og e th i g h e rv e r a c i t y k e yw o r d s d o c u m e n t i m a g ep r o c e s s i n g ，s l o p ei m a g e c o r r e c t i o n ， h o u g ht r a n s f o r m ，l a y o u tu n d e r s t a n d i n g ，p y r a m i dm o d e l s ，l a n g u a g e i d e n t i f i c a t i o n ，r u n n u m b e ra l g o r i t h m 四川大学项士学位论文 文档图像的文种识别系统 第一章综述 1 1论文背景 文档图像( d o c u m e n ti m a g e ) 是指内容主要为文字的电子文档形 式存在的图像。文档图像通常包含噪声、图形、表格，还会出现某种 程度的倾斜，如图1 1 。在当今时代，网络和多媒体技术迅猛发展，在 促进了信息交换的同时，也带来了对信息的巨大需求。模式识别技术 作为新一代计算机智能接口的重要组成部分，可以有效地改善计算机 输入信息的能力，已成为研究热点。光学字符识别o c r ( 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 无法直接运用，因此 作为o c r 技术的前端技术和基础，版面分析与文种识别就成为关键的 问题。 。 图i - 1 文档图像 1 2 论文工作及组织结构 本文介绍了一个文档图像的文种识别系统，该系统运用于我们的 实际工作中，取得了较好的效果。该系统由预处理、版面分析、文种 识别三大部分组成，如图1 2 。 图i 2 文种识别框图 口ujn l 大学硕士学位论文 文档图像的文种识别系统 文档图像的预处理包括去噪、倾斜校正等，预处理的效果直接影 响字符识别或文种识别的精度。通常的步骤是先去噪，再倾斜校正。 去噪的目的是为了得到一个较干净的图像，倾斜校正是为了更好地进 行版面分析。这种各阶段独立的方法不能完全利用各阶段的特点进行 综合处理，要么增加了难度，要么限制了效果。比如去噪，通常采用 平滑滤波，但该方法对二值图像的效果并不好，中值滤波对噪声有很 好的效果，但对字符笔画有损伤。我们在版面分析的同时，也进行噪 声的清除，不但能清除孤立噪声，对细长赢线和细长条块也有效地去 除。我们采用多层次各阶段交互的预处理方法，实验结果表明，该方 法大大提高了预处理的效果，从而提高了字符识别或文种识别的精度。 由于扫描等原因，文档图像经常会出现一定程度的倾斜，而大多 数图像处理方法都要受到倾斜的影响：由于歪斜，将使o c r 中的字符分 割困难，3 。以上的歪斜引起字符明显的变形，大部分o c r 方法难以适 应：在表格处理中，图像的歪斜会引起表格对正、识别和表格中固有 信息的移去发生困难。图像的倾斜校正分为手工校正和自动校正。由 于靠人眼进行手工校正费时费力，因此文档图像的自动校正成为一件 非常有意义的工作，而文档图像的特殊性使得自动校正成为可能。 目前用于倾斜校正的方法很多。如b a g d a n o v l l 】等用基于投影的方 法进行倾斜检测，但是在应用中由于所需的投影方向较多，从而导致 计算量增大；y a n f 2 l 等提出了利用行与行之间的相关性进行倾斜角检测 的方法，这一方法不仅很耗时，而且如果文档中出现图片，将严重影 响到结果的准确性；s u n 3 】等利用梯度信息进行倾斜角的估计，这同样 是一个比较耗时的运算过程，而且当文档中出现较大面积的图片时， 这一方法也不能够保证准确性：r o n d e l l 等用f o u r i e r 变换和神经网 络来实现倾斜检测，尽管这一方法适合于手写文本，但其速度较慢， 这主要是由于f o u r i e r 变换和多层神经网络的收敛较慢造成的； o g o v m a n1 5 提出的最近邻方法主要通过对相近邻字符对之间的方向向 量的统计得到图像的倾角，这种方法对纯文本图像倾角检测的效果很 好，速度也很快，但易受噪声的干扰；牛轶峰1 6 】等用可变模板检测倾斜 角，采用遗传算法进行快速优化搜索，能够精确检测文本的倾斜角度， 四川大学硕士学位论文文档图像的文种识别系统 并且不受倾角大小和文字方向的影响，具有较强的抗噪声性和较快的 收敛速度，但是如果模板定义得不准确，就有可能收敛到较差的解上， 而且如果遗传算法参数选择不当也会导致错误的计算结果。h o u g h 变换 是h o u g h 在1 9 5 9 年首先提出来的，最初是为了检测图像中间的直线段 7 1 ，现在已经是图像分析中一个经典的工具，并广泛用于模式识别的 各个领域。我们使用h o u g h 算法进行倾斜角的检测，但是经典的h o u g h 算法运算量太大，为此我们作了一些改进。 版面分析是文档图像分析的重要组成部分，受到了越来越多的重 视。由于复杂的版面格式导致o c r 系统无法直接运用或效果极差，另 一方面用户可能希望同时保留原始的版面信息，因此版面分析成为一 个关键的技术。版面分析被定义为从文档图像中提取几何结构( 8 】。一 个图像根据其内容所占区域的位置、大小、形状以及属性的不同被划 分为许多块，每一块区域可能代表字符行或图形等。版面分析的任务， 就是把原始文档图像中包含的文本、表格、图像、图形等不同性质的 区域划分开，以利于后续的分析处理。 版面分析可以分为基于形状的方法和基于纹理的方法两类，其中 基于形状的方法又可以分为自顶向下、自底向上、混合法。基于形状 的方法主要利用了文档图像中各个不同区域的结构分布特征，例如文 本、图像般以矩形的方式存在，各个结构单元呈层次关系，各个区 域之间一般有明显的间隔，如较大的空白或分割花纹等。在这类方法 中，自顶向下的方法从版面的全局特征开始，一个页面首先分割成几 个大的区域，然后每个区域再递归分割成子区域，代表性的有林雁平 等【a l 、l i uj i m i n g 等1 0 、王海琴等1 、w a n gky 等【12 1 、n a g yg 等【1 3 1 提 出的版面分折算法。自底向上的方法从像素点开始，将相邻的部分根 据局部特征的相似性合并成为一个小区域，小区域再连续地合并为大 区域以0 】，其中刘定强与张j 所中提出的基于组件的中文版面分析、周 杰与马洪的基于数学形态学的版面分析、陈明等人的一种可信度指导 的版面分析是其中典型的代表算法。另外还有将两种方法结合起来的 混合法 2 1 , 2 2 ，以及主要依据背景特征进行分割的基于背景的方法等 1 2 3 , 2 4 。这类方法的主要缺点是很大程度地依赖于特殊的规则和经验性 四川大学硕士学位论文文档图像的文种识别系统 的阈值，对日益复杂的版面格式的适应性较差。 基于纹理的方法主要思路是将图像看作是一些具有不同纹理的区 域的组合。文本具有一系列相同方向的文本行，行中具有一系列大小 基本一致的字符。这种相对一致的纹理特性完全不同于图像，因此可 以用来进行版面分析。这类算法近来得到了比较大的发展【2 扣3 0 】。 本文提出一种新的基于形状的版面分析方法。首先介绍金字塔模 型，然后描述了该模型在版面分析中的应用。 在过去的二三十年里，人们对文档图像的文种识别技术的研究日 渐深入，提出了一系列的算法。这些算法中，有的是从组成文字的连 通区域中提取局部特征进行识别，有的是提取文档的攘体特征进行识 别。在基于局部特征的方法中，w o o d 等人将文字行在水平方向上投 影，根据投影图中峰值的位置识别罗马字母、俄文、阿拉伯文、中文、 韩文【3 l 】；c h e wl i mt a n 等人提出利用连通区域外接框的长宽比、分布 图等特征区分中文、泰米尔语、拉丁文、阿拉伯文l 3 21 ：s p i t z 提出利 用垂直方向的凹度分布来区分东方文种( 中日韩) 和西方文种1 3 3 1 。 基于整体特征的算法中具有代表性的算法有：边缘特性处理( e d g e a t t r i b u t ep r o a e s s i n g ) 、多通道盖伯滤波( m u l t i c h a n n e lg a b o r f i l t e r i n g ) 【3 4 】、小波分解( w a v e l e td e c o m p o s i t i o n ) 、c s a r 法( e i r c u l a r s i m u l t a n e o u sa u t o r e g r e s s i v e ) 1 35 1 。这些算法的共同点是提取文档的 整体特征，不需要进行连通区域划分。 本文介绍三种我们使用的文种识别算法，其中穿越次数法和凹度 特征算法属于局部特征算法，适用于要求识别精度较高的非实时环境 中，而小波纹理算法属于整体特征算法，适用于要求识别精度不高的 实时环境中，如果进一步研究，可能还会提高识别精度，是一种很有 前途的算法。 本文的组织结构安排如下：在第2 章中介绍我们在文档图像的倾 斜校正中所使用的方法，第3 章介绍基于投影的简单版面分析方法， 第4 章提出一种基于金字塔模型的版面分析方法，用于解决复杂版面 情况，第5 章介绍一种改进的基于凹度局部特征的文种识别算法，作 为对照，第6 章介绍我们在文种识别的探索过程中自己提出的一种叫 穿越次数的算法，说明基于局部特征的算法可以获得较高的识别准确 率，在第7 章介绍一种基于小波纹理的全局特征的文种识别算法，第 四川大学硕士学位论文文档图像的文种识别系统 8 章对全文作出总结。 四川大学硕士学位论文 文档图像的文种识别系统 第二章h o u g h 变换法倾斜校正 倾斜校正是文档图像预处理中一项较重要的工作，因为很多文档图 像都有一定程度的倾斜，而大多数图像处理方法都要受到倾斜的影响。 h o u g h 变换是目前最好的倾斜校正方法。 2 1 h o u g h 变换 h o u g h 变换是一种有效的检测直线的算法，因为直角坐标系x y 空间 上的一点对应于极坐标p - 0 空间上的一条曲线，而x y 空间上同一条直线 上的各点在p - 0 空问对应的曲线均相交于一点，故此点的o 值即该直线 在x y 空间的倾斜角度，如图2 1 所示。h o u g h 变换就是先把直角坐标系 的目标点映射到极坐标系上进行累积，即先使直角坐标系平面上任一 直线上的所有点均累积到极坐标系的同一点集中去，然后通过寻找极 坐标系中点集的峰值来发现较长的直线特征。由于这种累积的统计特 性，因而可容忍直线的不连贯性，这样文档图像中即使没有直线，也 会因为文字行间较强的方向特性而检测出倾斜角度。 ， 狐| | n c a ) p 、0 的意义 ( b ) 矗) 巾备点在p 一9 空同的轨漆 图2 - 1h o u g h 变换示意图 设直角坐标系中点( x ，y ) ，其变换后的极坐标为( p ，0 ) ，则h o u g h 变 换可表示为： p = x c o s 0 + y s i n 0( 2 - 1 ) 四川大学硕士学位论文 文档图像的文种识别系统 2 2 h o u g h 变换的算法原理 h o u g h 变换的基本思想是：把目标像素的直角坐标变换成极坐标， 并在一个累加器中给该点计数，然后对累加器中同一角度进行行列求 和，找出较大极值对应的角度即为倾斜角度。 即用h o u g h 变换检测文本图像倾斜角度的算法可设计为： 在p , 0 合适的最大值与最小值之间建立一个离散的参数空间。 例如： p = p m i n p m a x ，0 = 0 m i n 一0 m a x 其中我们取p m i 。= o ，p 。= s q r t ( w + w + h + h ) ，0 m i 。= 0 ，0 。= 18 0 ，w 为图像的宽，h 为图像的高。 建立一个累加器a ( p ，0 ) ，并将每个元素清零。 a 2 z e r o s ( p m a x - p m i n ，o m a x - o m i n ) 将图像中的每个象素点( x , y ) ，对0 空间的每个取值0 ，计算p = x c o s o + y s i n 0 ，并在相应的累加器加1 ：a ( p ，0 ) = a ( p ，0 ) + 1 。 对a ( p ，o ) 进行行列累加，得到a ( o ) ，则a ( 0 ) 中最大元素所对应 的角度0 即为文本图像倾斜角度。 m a f l a b 语言的算法程序如下： a = z e r o s ( f m a x - p m i n ，0 m a x - 0 m i n ) ； f o rx = i ：w f o r y = l ：h f o r 0 = 0 m i n ：0 m a x p = x c o s 0 + y s i n 0 a ( p ，o ) = a ( p ，o ) + 1 e n d e n d e n d a = s u r n ( a ，1 ) ； 对a ( p ，o ) 进行行列累加，得到a ( 0 ) s l o p e a n g l e = m a x ( a ) ； 四川大学硕士学位论文 文档图像的文种识别系统 2 3 改进h o u g h 变换 h o u g h 变换的优点在于它抗噪声的能力强，并且不受图像中直线走 向的限制。但如何解决精确度和运算复杂度的矛盾以及它对存储空间 的要求是应用h o u g h 变换的主要困难。参数空间量化得越精细( 或分辨 率越高) ，算法的精度越高，但算法所需的存储空间和运算量也越大。 通过实验统计表明，对1 。内的倾斜角度的文档图像，各种识别方法 都能取得较高的精度。故角度量化不用取太高的精度，取l 。的步长即 可，大大减小了运算量。另一个减小运算量的措施是，不使用完整的 文档图像，而是使用文档图像的一个子区域即可。减少采样点也是减 小运算量的有效措施，如果对每个象素点都进行h o u g h 变换，则计算量 相当大。根据人类视觉特点，人判断图像倾斜主要根据文字行的底部 基线的倾斜情况，或者是文字行之间的空白条的倾斜情况，如图2 2 所示。故将每个文字的底部基线的中点，或者行间空白矩形条的中心 点，作为采样点，必将大大减小运算量。 一翱瓣 图2 2根据文字行的底部基线或行间空白矩形条判断倾斜 2 3 1 子区域的选取 通常文档中文本行之间具有较强的方向性，且相邻文本行之闯的 距离相对固定，因此检测页面图像豹倾角不必对整个图像进行扫描计 算，只须选择台适的文本子区域，其文本行的方向危对应于整个文档 图像的倾斜角。由于文档图像边缘可能会出现大段黑区或噪音，这些 区域不仅会影响倾角的检测，而且会大大增加计算量。 因此，在选择被测子区域时，首先考虑将图像边缘区域去除，并 且应保证其一定的大小，即子区域r 满足： r = ( x ，y ) 1 w l x 墨w 2 ，h l y 3 ，如果不能满足 此条件，就选最大的那个子区域。 子区域应当选取字密度较大的区域，我们采用投影法( 见3 1 ) 进行 选择，如图1 1 是一幅较复杂的文档图像，包含有文字、噪声、表格， 还有倾斜。图2 3 是他的垂直投影曲线，其中( b ) 是( a ) 经平滑处 理后的曲线。 从( b ) 中可以看出，曲线的山峰对应的区域就是原图像文字 密度较大的区域，如果后续工作是文种识别，则只需选取坡度较宽的 一个山峰就可以了。 单单垂直投影选取的区域，可能还有无用的空白等区域。需要再 作水平投影；有的图像可能要水平投影才行。总的说来，用递归的纵 横投影法，总能选取出一块合适的区域。 ( a ) 图2 - 3 垂直投影曲线 如果所选的区域包含图片内容，子区域应重新选取。所选予区域 中是否为纯文本，须在分析其内部连通区的特征之后才可判定( 见 2 3 2 ) 。纯文本子区域的重新选取采用上述同样的方法，只是选取的 是上一山峰的次山峰即可，同时必须满足上述区域大小条件。 四川大学硕士学位论文 文档图像的文种识别系统 2 3 2 特征点集的确定 在予区域中，确定每个字符( 或粘连字符) 的连通区的闭包盒。为 方便起见，称每一个连通区为一个对象。一行文本中有三类对象： ( 1 ) 对象闭包盒底线与基线重合，包括大部分普通字符如a 、 s 、 m 等； ( 2 ) 对象闭包盒底线在基线之上( a s c e n d ) ，包括部分标点符号如 一、+ 、 木等； ( 3 ) 对象闭包盒底线在基线之下( d e s c e n d ) ，包括少数普通字符如 p ，y ， q 等，以及部分标点符号如，、 。、 ； 等。 由此可见，大部分普通字符的最底象素点与文本行基线重合，仅 存在少数字符如p 、q 等的闭包盒穿过基线的情况，并且其底 线到基线的距离：l 3 * h c ，h c 为字符闭包盒高度。标点符号以 及字符i 、j 上的小圆点虽然不在基线上，但其闭包盒底线到基线的距 离与闭包盒的高度之间不存在确定规律，且不满足上述条件。为了减 少这些点对基线方向角计算的影响，仅选取满足如下条件的对象c ： c = c i iw ( c i ) d r v h ( c i ) d h ，l i k ( 2 - 3 ) 其中c 为满足条件的候选对象集合，w ( c i ) 与h ( c i ) 分别为对象c i 闭 包盒宽和高，d w 、d h 分别为闭包盒宽和高的阈值，k 为对象的个数。 本文将对象闭包盒的最底象素行中点作为特征点。在纯文本区域 中，由于文本行相互平行，因此对应予不同的文本行的特征点可分为 几个不同的集合。而含有图片的区域，特征点的分布是发散的，无法 划分成几个不同的集合。 由于这些特征点大部分位于文本行基线上，故由这些点拟合的直 线基本代表了文档图像的倾斜情况，但由于存在少量特征点不在基线 上，因而拟合的直线与实际基线之间存在一定的误差。但是由于b o u g h 变换的累积作用，这些不在基线上的少量特征点的影响将被忽略，最 后得到的将是精确的倾斜角度。 四川大学硕士学位论文文档图像的文种识别系统 2 4像素面积插值法倾斜校正 利用上面h o u g h 变换法得到的倾斜角度，将图像旋转即可进行文档 图像的倾斜校正了。设文档图像的倾斜角度为伍，建立同一个坐标原点 的两个坐标系，分别设为( x ，y ) 和( x ，y ) ，其中x 、y 、x 和y 均大 于0 ，原点为( 0 ，0 ) ，两个坐标系的夹角为，如图2 - 4 所示。当坐标值 可取连续值时，有 x = ( c o s ( i ) x + ( s i n a ) y ( 2 - 4 ) y = 一( s i n a ) x + ( c o s a ) y ( 2 5 ) f ( x ，y ) ：f ( x ，y ) ( 2 - 6 ) f ( x ，y ) 和f ( x ，y ) 表示的是同一像素的值。 将式( 2 - 4 ) 和( 2 - 5 ) 代入式( 2 - 6 ) 得 f ( x ，y ) = f ( ( c o s n ) x + ( s i n 旺) y ，卜( s i n ) x + ( c o s u ) y ) ( 2 7 ) ( o 0 ) y | | r r ( x ，y ) - ，一一，( i ，y ) | r y ， x i 图2 - 4夹角为的同原点的两个坐标系 数字图像是离散的，而( x ，y ) 是连续的点，为此，引进3 个记号， z n 是最接近z 的整数， z s 是小于且最接近z 的整数， z l 是大于且最接 近于z 的整数，那么改进式( 2 - z ) 可以得到3 个算法。 a p ( x ，y ) = f ( x 。，y 。) ，其中x 。= x n ，y 。= y n b p ( x ，y ) = ( x l x ) ( y l - y ) f ( x 。，y 。) + ( x l x ) ( y - y 。) f ( x ，y 1 ) + ( x x 。) ( y 1 _ y ) f ( x l ，y 。) + ( x x 。) ( y - y 。) f ( x l ，y 1 ) ， ( 2 8 ) 其 中 x ，= x s，x l = x l ，y 。= y s ， y l = y 1 ， s 1 = ( x 1 一x ) ( y 1 一y ) ，s 2 = ( x x ：) ( y 1 一y ) ， s 3 = ( x x ，) ( y y ：) ， 四川大学硕士学位论文文档图像的文种识别系统 s 4 = ( x 1 - x ) ( y - y ，) ，s l 、s 2 、s 3 和s 4 分别表示以( x ，y ) 为中心的倾斜像 素在相邻的4 个像素中所占的面积，如图2 5 所示。利用这些面积，我 们可以使用像素面积插值法，即一个像素的颜色值，等于它在相邻的 区域中所占的面积与相应区域的颜色值的积之和。 名八 少 图2 5 倾斜像素在相邻像素中所占的面积 c 前两种算法已较好地实现了图像的倾斜校正。但上述算法忽略了一 个问题，即由于图像本身是倾斜的，那么它的像素应该也是倾斜的， 如图2 - 6 所示。p 1 p 9 分别表示倾斜像素的相邻像素，p 表示倾斜像 素。所以，还需要进一步改进算法。由于像素的倾斜，那么它必会在 相邻的9 5 像素中占有一定的面积，可以根据该像素的中心点( x ，y ) 和图像倾斜的角度，计算出像素的4 条边的线性方程，然后根据这4 4 方程计算出这个像素点分别在相邻的9 5 像素中所占的面积s 。再用得 到的面积和相应的像素点的颜色值f ( x ，y ) ，改进式( 2 7 ) 得到点( x ，y ) 的颜色值f ( x ，y ) ，即 9 f ( x ，y ) = 乏：f ( x i ，y i ) + i i ( 2 - 9 ) 四川大学硕士学位论文 文档图像的文种识别系统 p 1p 2 p 3 p 4p 5p 6 p 7p 8 p 9 图2 - 6 倾斜像素 理的质量窟接影响届臻工律的鸯坌杀和 y , o u g h 变换穷! 盎，用予文档图像的赖 施，峨小了计算盘。采用台适的量忧角 取代完整的圈像。减小褥处理盼数耀 域垒部像紧，避一步减小待处理的数 不建谪单地旋转筛悬用像拳蔺积插值 ( b ) 算法a 的校正结果 四川大学硕士学位论文文档图像的文种识别系统 理的质量直接影响后续工作的效果和 h o u g h 变换方牲，用于文档图豫的颊 施减小了计算墨。采用合适的量化角 取代完整的图像减小待处理的数据 域垒部像素。进步减小待处理的数 不是简单地旋转布i 是用像豢面积插值 ( c ) 算法b 的校正结果 图2 7 图像倾斜校正结果 四川大学硕士学位论文 文档图像的文种识别系统 第三章基于投影的简单版面分析 3 1投影 任何一个图像都是由像素构成的：我们约定图像文件上的背景所 对应的像素是白点( 值为o ) ，文字、图形、图像等所对应的像素是黑点 ( 值为1 ) ，那么，一个像素行( 列) 的黑点数的总和，就是这一像素行( 列) 的投影值，把所有像素行( 列) 的投影值都统计出来，就得到整个图像 文件的水平( 垂直) 投影，用公式表示为： p 所= f ( x j ，y i ) ， 如图3 1 所示是一幅六行文字的图像及其投影。 投影是这样的一种特征函数：它把二维图像的像素分布特征简化 为：x 轴和y 轴上的两个一维函数。投影算法正是从这两个一维函数出 发来进行版面分析的。 从图3 一l 可以看出，一行的文字越多，投影值就越大，而空白行的 投影值则几乎是零( 如果没有噪声的影响，空白行所对应的投影值就 是零) 。通常将投影值小于某个闽值d 并且具有一定宽度的连续区间称 为低谷( v a l l e y ) ，而将位于两个相邻低谷之间的、投影值大于阙值d 的连续区间称为脉冲( p i t c h ) 。例如，在图3 1 中：若取阈值d = d 1 则y 轴上就有五个低谷，六个脉冲。 y 理的质量直接影响后续工作的效罘和 h o u g h 变换方 击用于文档图像的倾 施硪小了计算量采用合适的量化角 取代完整的图像减小待处理的数据 域全部像素，进一步减小待处理的数 不是简单地旋转丽是用像素面积插值 图3 - l 图像的行投影和列投影 x 四川大学硕士学位论文 文档图像的文种识别系统 一般而言，低谷对应着空白行，而具有一定的周期性的脉冲则对 应着文字行，周期性不明显的脉冲则可能对应着其它的图形、图像， 也可能是由行列不对齐的版面投影形成的。脉冲和低谷的这种周期性， 正是基于投影的版面分析算法的基础。 3 2基于投影的多分法算法原理 基于投影的多分法是这样的：首先，求出整个图像版面的水平( 或 垂直) 投影，并尽可能多地找出可供分割的低谷位置，从而将各区域作 出尽可能多的分割。这样，就充分地利用了一次提取的特征，从而避 免了同一特征的多次抽取，减少了冗余运算，降低了算法的时间复杂 度。然后在另一个方向上作投影，重复上述的过程，把它们各分为更 小的区域，如此重复下去，构成一个递归过程，直到分出各个分栏为 l e 。 l 这是一个版面示意j i 这是第二这是第二分 1 分栏， 栏 3 lz 我爱你。同 i 翅量l 爱着你，重 斟l 黻i 就像老鼠 爱大米。 图3 - 2 一个版面示意图和它对应的多叉树模型 这个过程可以用一个多叉树模型来表示。原始的图像文件，即最 初的版面，是树的根结点( b o o tn o d e ) 、最终的分栏是叶结点( l e a f n o d e ) ，而中间状态的区域就是中间结点。图3 - 2 是一个版面的示意图 和它对应的多叉树，图中，圆表示初始的版面；椭圆表示中间状态的 待分区域；方框表示最终的分栏。 四川大学硬士学位论文 文档图像的文种识别系统 3 3多分算法的实现过程 为了讨论的方便，先将有关的变量做如下说明： ( 1 ) s t a r t ：脉冲的起点 ( 2 ) e n d ：脉冲的终点 ( 3 ) w i d t h ：脉冲的宽度 w i d t h = e n d s t a r t 如果脉冲正好对应于文字行，则其宽度实际上就是行高 ( 4 ) d is t ：相邻脉冲之间的距离 假设p i t c h 2 表示一个脉冲，p i t c h l 表示紧接在p i t c h 2 前面的、 并与p i t c h 2 相邻的那个脉冲，则 p i t c h 2 的d is t = p i t c h 2 的s t a r t p i t c h l 的e n d 如果脉冲正好对应于文字行，则其间距实质上就是行距。 ( 5 ) 脉冲的周期性： 一股地，文件由很多行组成，而行的高度大体相等，并且同一段 落的行间距也是相等的，因而脉冲的w i d t h 和d i s t 应该在一定范围内具 有周期性。 整个算法由四个核心过程构成：用动态规划法求阈值d ：根据n 求 出区域中的所有脉冲：求出脉冲的周期性；根据脉冲的周期性和经验 规则对区域做出切割。 用动态规划法求阈值d 阈值d 直接影响到脉冲的正确选择，从而决定了整个算法的成败， 因此这一过程是非常关键的。实验证明，仅仅根据字号的大小确定一 个静态的d 值，切割的效果往往很不理想。为此，我们可以采用动态规 划等方法，求出一个合适的闽值d ，以便取得较好的分割效果。 根据d 求区域中的所有脉冲 这个过程可以描述如下： f i n d p i t c h 0 f o r = 0t o 投影总数d o b e g jn i f b i t s i 1 耋d ，则标志一个p i t c h 的开始：s t a r t = i ； 四川大学硕士学位论文 文档图像的文种识别系统 i f b i t s i d ，则标志一个p i t c h 的结束： 记录p i t c h 的有关参数e n d ，w i d t h ，d i s t e n di f e n d 由于噪声的影响，有些p i t c h 被分割对待，造成几个不同的p i t c h ， 这样的假p i t c h 应该加以合并。所以在这个过程中还有一个p i t c h 的合 并过程，这是为了纠正噪声所引起的误差。下面是p i t c h 的合并算法： b i n d p i t c h o f o ri = ot op i t c h 总数一1d o b e g i n i f ( ( p i t c h i w i d t h d e l t a w i d t h ) & & ( ( p i t c h i + l 】w i d t h d e l t a w i d t h ) ) 则将其合并：修改p i t c h i 】的有关参数，删除p i t c h i + l 】 e n d i f e n d 求脉冲的周期性 这个过程通过排序、类比等手段对脉冲的宽度、脉冲间距等做出 检测，并求出周期性脉冲所占的百分比如果这个百分比低于3 0 ，也 就是周期性相当差，一般就认为该区域不是文本区域。 区域的切割 这个过程根据一些经验规则和所求得的脉冲及其分布规律，将一 个区域分为几个子区域。如果该区域的脉冲分布整齐，即具有相当的 文字行的特征时，就不再切割它，将它作为文本分栏保存，退出递归； 如果脉冲的分布规律性较差，那么就认为这个区域是图形或图像，这 样的区域也不做切割，而是作为图像分栏保存起来，并退出递归。介 于这两种极端情况之间的区域，一般应加以切割，算法描述如下： d i v i d e ( r e g i o n ) b e g in f i n d d i v i d o r 找出赖以切割的分割位量 i f ( d i v i d o r n u m = = 0 ) ，则保存分栏并退出 四川大学硕士学位论文文档图像的文种识别系统 a d d c o l u m n ( r e g i o n ) r e t u r n e n di f 根据d i v i d o r ，将区域分为d i v i d o r n u m + 1 个子区域s u b r e g i o n f o r i = 0t 0d i v i d o r n u m + 1d o d i v i d e ( s u b r e g i o n i ) e n d 3 4 实验结果 我们用2 0 0 幅文档图像进行了实验，取得了较好的效果。如图3 3 ， 像这样的版面，该方法仅需要一次水平投影与一次垂直投影即可正确 地进行版面分割。 色滤光片、导光板增亮 、逆变器、柔性电、路 、镀膜设备、t 鱼刻、膜 仪清洗、切刻、检测、 光修复、熟压焊接、邦 分 器 光 率 ，b 怖胍 。、胜1 ) 一、 用器件、波长分割器、j 滤波嚣、整台嚣、光棚 晶体、光通信测试仪器、 、定位嚣、光纤熔揍机、 圈3 - 3 一次水平投影与一次垂直投影的分割结果 但是我们也发现，对于像图3 4 这样的嵌入式等复杂版面，该方法 不能进行较好的分割。我们的结论是，投影法可以应用到简单版面和 特定环境中的版面分析以及特殊运用，比如区域提取( 见2 3 1 ) 和文 字行的切分等。 复、举计 t j i i 大学硬士学位论文文档图像的文种识别系统 繇够激黜 7e 胎体质芥乍 ： 谯一 咤甘扑气的螂- k 士木鲁椭气惝 簸；t 抵太l ，山靠 悱- i i 羹束太量山霸、藕米 蕞量耳悻一大謇胡， f 骛、豆一、肆瞻赫冉 生由，* “，牛由、鼻膏青、t 韵也有朴气 t 拘功烛 图3 - 4 嵌入式版面 下面对文字行的切分作一简单的介绍，因为基于局部特征的文种 识别的