（计算机应用技术专业论文）基于表格的影像文档特征提取算法的研究与设计.pdf

五邑大学硕士学位论文 摘要 近年来，随着计算机技术、多媒体技术的飞速发展，表格影像文档的自动分类、 存储和管理日益成为人们研究的热点。而表格影像文档的特征提取是影像文档自动 管理领域里重要的研究课题之一，对图像本身进行深入研究，通过合理的提取其特 征，来提高影像文档分类的速度以及分类的准确性己成为必然要求。 当今虽然对表格影像文档处理进行了大量的研究，而且在一些行业已经应用， 但这些系统基本上都是针对专用表格，对通用表格的分析和识别还不成熟。因此如 何对通用表格特征的提取以及通用表格的分析和分类已经成为研究的热点。基于以 上原因，本文以图像处理和模式识别理论为基础，研究了两种通用表格特征提取方 法，并通过m a t l a b 仿真，验证了算法的有效性。具体研究工作包括以下三方面： 1 在表格预处理阶段，本文提出一种简单有效的去除黑边的方法，该方法利用 数学形态学原理首先对表格图像进行开运算，得到只有黑边的和原图一样大小的图 像，再利用图像减法运算，可以很好的将黑边去除。 2 在特征提取阶段，研究了一种简单实用的通用表格特征提取方法，将表格结 构作为表格识别特征。其处理过程是：先提取表格中的线段，再按照本文算法对相 关线段进行合并或剔除，最后根据表格特性调整表格线，得到完整的表格结构。经 实验结果表明该方法是可行的。 3 在对第一种特征提取算法分析的基础上，又给出了基于傅立叶变换特征提取 算法。该算法综合考虑表格文档水平和垂直投影方向的信息，以傅立叶变换后的频 谱作为特征，并采用b p 神经网络作为分类器，实验证明这种特征可以有效地解决对 称表格分类难的问题，并具有很好的抗干扰和泛化能力。 关键词：表格分类；特征提取；表格结构；傅立叶变换；神经网络 五邑大学硕士学位论文 a b s t r a c t w i t ht h e r e p a i dd e v e l o p m e n to fc o m p u t e ra n dm u l t i m e d i at e c h n o l o g y , t h ea u t o m a t i c c l a s s i f i c a t i o n ，s t o r a g ea n dm a n a g e m e n to ff o r mi m a g i n ga 坞b e c o m i n gh o ts p o t s e x t r a c t i n g c h a r a c t e r so fi m a g ei so n eo ft h em o s ti m p o r t a n tr e s e a r c h e si nd o c u m e n ti m a g i n gm a n a g e m e n tf i e l d e x t r a c t i n gt h er e a s o n a b l ec h a r a c t e r so fi m a g ec a ni m p r o v i n gt h ev e r a c i t ya n ds p e e do fd o c u m e n t i m a g i n g s oi ti sn e c e s s a r y r e s e a r c h e r sd i dl o t so fr e s e a r c h e si nf o r mi m a g i n gp r o c e s s i n ga n dm a n ya c h i v e m e n t sh a v eb e e n a p p l i e di ns o m ei n d u s t r i e s ，b u tt h o s et e c h n o l o g i e su s u a l l yc o n c e n t r a t eo nt h es p e c i a lf o r m i t sn o t i m m a t u r ei nt h eu n i v e r s a lf o r mr e c o g n i t i o na n da n a l y s i s s oh o wt oe x t r a c tf e a t u r e sa n da n a l y z et h e u n i v e r s a lf o r mi sb e c o m i n gt h eh o ts p o t a c c o r d i n gt ot h e s er e a s o n s ，t h i sp a p e rb a s e do ni m a g e p r o c e s s i n ga n dp a t t e r nr e c o g n i t i o n i tr e s e a r c h e dt w om e t h o d st oe x t r a c tu n i v e r s a lf o r m sf e a t u r e s a n dh a sa c h i e v e dg o o dr e s u l t sb ym a t l a b t h em a i nw o r k si n c l u d e dt h r e ef a c t s 1 i np r e p r o c e s s i n gs t a g e ，t h ep a p e rp u tf o r w a r das i m p l ea n de f f e c t i v em e t h o dt or e m o v eb l a n k s i d e s t h em e t h o du s e dat h e o r yo fm o r p h o l o g i c a l i tg o ta ni m a g ew i t hb l a c ks i d e sa n dh a ds a m e s i z ea sp r i m a r yi m a g eb yp e r f o r m i n go p e no p e r a t i o n t h e nw ed e l e t e db l a c ks i d e sb ys u b t r a c t i o n o p e r a t i o n 2 i ne x t r a c t i n gf e a t u r e ss t a g e ，t h ep a p e rr e s e a r c h e daf a s ta n dp r a c t i c a lm e t h o df o ru n i v e r s a l f o r mc h a r a c t e r s f o r ms t r u c t u r e 懿t h ec h a r a c t e r s t h ep r o c e s s i n gi sc i t e da sf o l l o w s f i r s t l y , w e e x t r a c t e dt a b l el i n e s e c o n d l y , w em e r g e do rd e l e t e dr e l a t i v el i n e sb ya l g o r i t h m f i n a l l y , w ea d j u s t e d t h ef o r ml i n eb a s e do nf o r m sf e a t u r e sa n dg o tt h es t r u c t u r eo ff o r m e x p e r i m e n t a lr e s u l t ss h o w e d t h a tt h em e t h o dw a sf e a s i b l e 3 a f t e ra n a l y z i n gt h ef i r s t m e t h o d ，w ep r o v i d e dt h eo t h e ra l g o r i t h mb a s e do nf o u r i e r t r a n s f o r m a t i o n w ec o n s i d e r e dv e r t i c a la n dh o r i z o n t a ld i r e c t i o np r o j e c t i o ni n f o r m a t i o ni nf o r mf i l e a n dg o ts p e c t r u mf e a t u r e sb yu s i n gf o u r i e rt r a n s f o r m a t i o n t h e nw e a d o p t e db pn e u r a ln e t w o r ka s c l a s s i f i e r t h o s ef e a t u r e sc a ns o l v et h eh a r dc l a s s i f i c a t i o np r o b l e mi ns y m m e t r i c a lf o r m t h e e x p e r i m e n tp r o v e di th a sg o o dr e s i s td i s t u r b a n c ea n dp r a c t i c a l i t y k e yw o r d s ：f o r mc l a s s i f i c a t i o n ；f e a t u r ee x t r a c t i o n ；f o r ms t r u c t u r e ；f o u r i e rt r a n s f o r m a t i o n ；n e u r a l n e t w o r k i l 本人声明 我声明，本论文及其研究工作由本人在导师指导下独立完成，完成论文所用的 一切资料均已在参考文献中列出。 作者：解正梅 签字：鳞占樯 2 0 0 8 年4 月1 5 日 五邑大学硕士学位论文 1 1 课题来源及研究背景 第一章绪论 随着计算机技术、多媒体技术的飞速发展，影像文档图像处理进入高速发展时 期。由于纸制的票据、单证、文件和档案资料等在存放上受时间、环境的影响比较 严重，而且传统的文档分类方式是采用手工的方式，这种方式存在处理速度慢、劳 动强度大、准确率低等缺点，所以人们越来越倾向于将票据、单证、文件和档案资 料等通过扫描仪等用图像的形式存储起来，于是影像文档出现了。通过计算机对影 像文档进行自动分析、检索，能提高工作效率、减轻劳动强度和增加处理的准确性。 影像文档的识别包括纯文本识别和表格识别两大部分。目前对纯文本的识别率 相当高，但表格识别在实际应用中的识别率却还远低于期望值，速度也不很理想。 同时由于表格文本作为一种常见文本，是日常工作中处理最多的文本之一。如银行 支票、发票其实就是一种较简单的表格，而信用卡申请表、财务税务报表则是一种 较为复杂的表格。对表格的处理成为了商业和政府部门中一项主要的事务性工作， 因此基于表格的影像文档识别技术也越来越受到人们的重视。 为了能够快速而准确地识别出表格，对表格进行分类，有效地提取表格特征并 建立特征库是后续工作的关键。一旦特征库建好了，在识别表格过程中，就可以通 过提取待识别表格的特征，并与存储在特征库中的特征信息进行匹配，从而得出表 格的类型。 基于以上原因，并结合江门市科技计划项目“电子影像文档类型自动识别方法 的研究 ( 江财工 2 0 0 7 2 8 号) 课题，本论文以图像分析为基础，对表格影像文档 特征算法进行了研究，通过实验验证了有关方法的可行性，对于提高计算机识别影 像文档的准确率和处理速度，满足市场应用需求，都具有重大的研究意义和应用前 景。 1 2 表格文档研究现状 目前有许多大学和研究机构都在表格分析领域开展了大量的研究工作，并且取 得了一定的成绩。对如何全面的解决表格处理中的难点提出了各种各样的解决途径。 五邑大学硕士学位论文 下面介绍一下国内外对于表格图像特征提取的现状。 k a il u o 和s h a h r a ml a t i f i 等人【i 】将表格物理结构作为识别的特征，提取表格中的 水平垂直线段，该方法要求表格图像已经纠正了倾斜，并且按照该算法，只能找到 长度大于一个阈值的水平或者垂直线框，而且这个算法只有在图像特别理想的情况 下才能实现，比如线段不能出现局部的曲折，线框不能断裂等，对于现实的表格文 档基本上没有太大意义。在同样假设理想情况下，a n d r e wb u s c h 和w a g e e hw b o l e s 2 】 认为表格元素的组成方式不仅仅是一般的矩形单元格表示的表格，它给出了几种表 格的基本组成元素。依靠识别横竖的线段来判断表格的构成方式，来决定属于哪种 基本构成元素。在理论上可以判断更多形式的表格，但其主要缺陷还是无法解决现 实中表格无可避免的图像质量问题。 e c e s a r i n i 和m g o r i 等人【3 】提出了一种自上而下分析算法来分析表格逻辑结构， 使用层次结构来表示表格的逻辑结构，它没有考虑单元格之间的约束关系，而是根 据单元格与多个单元格构成较大整体之间的嵌套关系，来形成一棵层次树的结构 通过将整张表格沿着长度等于宽或者高的那些线条进行分割，然后对分割出的子部 分，再沿长度等于这个子块的宽或者高的线条进行分割，直到分割的最小单位为单 元格为止。 国内对表格处理研究起步较晚，表格版面分析和识别技术与国外尚有差距。清 华大学电子工程系智能图文实验室对表格识别系统的研究始于1 9 9 2 年，1 9 9 9 年该实 验室的潘世言提出一种基于所定义的图像结构基元“有向单连通链 的自底向上表 格框线检测算法【4 】，在此算法中，有向单连通链是一种黑像素游程序列，在引入一 定表格框线约束信息的条件下合并单连通链，提取表格框线。在此算法的基础上他 研制出一套通用表格识别系统，该系统经过郑冶枫的进一步改进后【5 】【6 1 ，被集成进清 华大学电子工程系研制的t h o c r 2 0 0 0 系统中。 从目前国内外研究成果来看，在识别的准确性和处理速度等方面仍有许多值得 研究的地方。 1 3 论文的研究内容 本文针对通用表格特征提取问题，提出了两种通用表格特征提取算法。研究内 容主要涉及图像处理、模式识别、机器学习等领域的知识。具体工作包括： ( 1 ) 为了便于后面更有效的提取特征，预处理阶段是不容忽视的。本文在研 2 五邑大学硕士学位论文 究了图像预处理方法的基础上，给出了一种新的去除黑边和去噪的方法， 并用m a t l a b 进行了仿真。 ( 2 ) 在研究现有的一些表格特征提取算法后，结合表格文档的结构特点，针 对表格线存在的断线、折线及因字符中的长笔画引起杂线或者由距离很 近的字符引起的杂线等情况，给出了一种简单实用的表格结构特征算法。 ( 3 ) 针对对称表格文档的特点，给出了基于傅立叶变换特征提取算法，该算 法从表格文档的全局信息考虑，将表格图像从空间域通过傅立叶变换转 换成频率域进行分析，并结合b p 神经网络进行分类，实验结果表明了该 算法的有效性。 1 4 论文的组织形式 根据所研究的内容及特点，本论文各章节内容安排如下： 第一章：绪论 介绍了国内外表格特征提取方面的研究现状、本文的研究内容，及组织形式。 第二章：特征提取理论基础及相关技术 阐述了模式识别中的特征提取与选择的理论知识，分析了常用的表格特征提取 算法，介绍了在特征提取中需要运用的傅立叶变换的基本原理。 第三章：表格文档的预处理 首先介绍了去除黑边所运用的数学形态学原理，在此基础上，提出了一种新的 去除黑边算法，并给出了相应的实验结果。最后介绍了常用的去噪方法，并给出本 文所采用的去噪算法。 第四章：表格结构特征提取算法的研究 简单的介绍了关于直线检测的相关算法，给出了本文的表格线检测算法，并对 最终得到表格结构作了详细的介绍，通过实验证明了该算法的有效性。 第五章：基于傅立叶变换特征算法的研究 重点阐述了基于傅立叶变换的特征提取和标准样本构造算法，介绍了在表格分 类中所用到的b p 神经网络，最后给出了相关的实验结果，证明了该算法在对称表 格文档分类中的优势，并与结构特征提取算法进行了比较。 3 五邑大学硕士学位论文 结束语 对整个毕业设计期间所做的研究工作进行了总结，并给出了基于表格的影像文 档识别系统未来的改进方向。 4 五邑大学硕士学位论文 第二章特征提取理论基础及相关技术 图像特征是指图像的原始特性或属性。每一副图像都具有其本身的特征，其中 有一些是视觉直接感受到的自然特征，如亮度、边缘的轮廓、纹理或色彩等；有些 是需要通过变换才能得到的人为特征，如谱、直方图等。图像特征包括形状、颜色、 纹理等。图像特征提取的结果给出了某一具体的图像与其他图像相区别的特征。 2 1 特征提取和选择 特征选择和提取是模式识别中的一个关键问题，在一个较为完善的模式识别系 统中，特征提取与选择技术环节是必不可少的。通常对于图像特征数据采集和分类 识别两个环节之间，特征提取与选择的优劣极大地影响着分类器的设计和性能，它 是模式识别三大核心问题之一，其目的都是为了在尽可能保留识别信息的前提下， 降低特征空间的维数，来达到有效的分类。 一般把特征分为三大类：( 1 ) 物理特征；( 2 ) 结构特征；( 3 ) 数学特征。物理 和结构特征易于为人的直觉所感知，但有时难于定量描述，因而不易用于机器判别。 数学特征易于用机器定量描述和判别，如基于统计的特征等。 2 1 1 特征提取 特征提取，就是使( 五，毛，) 通过某种变换，产生m 个特征( y n ，y 2 ，虼) ( m 以) 作为新的分类特征( 或称为二次特征) 。在特征提取过程中必须对识别对象的各种重 要特征充分理解，其常用的方法有： ( 1 ) 按欧氏距离度量的特征提取方法 不同类样本占有不同的特征空间，不同类样本区域间的距离愈大，其可分性就 愈大。经常用样本间的平均距离作为特征提取的判据函数，两个特征向量之间的距 离是它们相似度的一种很好度量。距离判别方法直观、简单，对变量的概率分布不 要求有什么限制。 ( 2 ) 按概率距离判断的特征提取方法 欧氏距离度量的特征提取方法没有考虑概率分布，因此当不同类样本中有部分 在特征空间中交迭分布时，简单地按距离划分无法表明与错误概率之间的联系。因 5 五邑大学硕士学位论文 此用概率密度函数间的距离来度量。 ( 3 ) 基于判别熵的最小化特征提取 它是基于后验概率分布的判据。为了衡量后验概率分布的集中程度，可以借助 信息论中熵的概念，制订定量指标。 2 1 2 特征选择 在很多实际问题中，往往不容易找到那些最重要的特征，或受客观条件的限制， 不能对它们进行有效的测量；因此在测量时，由于人们心理上的作用，只要条件许 可总希望把特征取得多一些。如果将数目很多的测量值不做分析，就直接用作分类 特征，不但耗时，而且会影响到分类的效果，产生“特征维数灾难 问题。为了设 计出效果好的分类器，通常需要对原始的测量值集合进行分析，经过选择或变换处 理，组成有效的识别特征；在保证一定分类精度的前提下，通过减少特征维数，即 进行“降维 处理，使分类器能够实现快速、准确和高效的分类。为达到上述目的， 关键是所提供的识别特征应具有很好的可分性，使分类器容易判别，为此，需对特 征进行选择。所谓特征选择，就是从聆个度量值集合 而，毛， 中，按某一准则选 取出供分类用的子集，作为降维( m 维，m n ) 的分类特征；特征选择应遵循如下 原则： ( 1 ) 去掉模棱两可、不易判别的特征； ( 2 ) 去掉相关性强且没有增加更多分类信息的特征； ( 3 ) 选择特征必须与同类对象的特征比较相近，否则所选的特征就是不良特征，将 导致识别不可靠； ( 4 ) 选择尽可能少的特征，因为模式识别系统复杂程度与特征个数成正比； 2 2 常用的表格特征提取方法 表格图像是一个二维的灰度阵列，测量空间的维数很高，不适宜分类器的设计； 更为重要的是二维灰度阵列并不能直接反映对象的本质。因此，为了进行分类器设 计，需要将表格图像从测量空间变换到低维数的空间，使被研究的表格图像在这个 特征空间中由一个特征向量表示。由于表格图像本身的特殊性，结构特征是以往表 格识别技术中最为常用的特征，也有一些采用统计特征来表示。 6 五邑大学硕士学位论文 2 2 1 结构特征提取方法 表格结构特征主要分为两种：物理结构特征和逻辑结构特征【7 1 。物理结构特征 主要是利用表格物理特性提取单元格之间的绝对位置。提取表格物理结构特征，需 要把表格扫描到计算机中，对得到位图使用单元格、或者线段的形式来对其进行矢 量化表示。逻辑结构特征通过对单元格之间的约束关系确定逻辑关系。表格中某些 单元格已经包含了确定的信息，这些信息可以指导用户填写数据，对用户需要输入 的数据区存在语义约束，因此逻辑分析的重点是找出对用户需要填写数据的单元格 具有指导作用的所有单元格，从而获取对输入信息的约束规则。 a r i a sj f 曾利用物理结构特征的方法【引，提出过线段相交直角特征的方法，将 表格线框相交形成的交叉分成多种特征情况。n e v e sl a p 【9 】对a r i a sj f 进行了改进， 增加了一种特殊情况，给出了1 4 种合法相交特征情况，并且给出了纠错机制。这种 方法可以快速地进行识别，但是对于字符跟表格线框相交的情况并不适用，而且汉 字经常会出现笔画交叉为直角的情况，导致直角特征的识别失效，给这种识别方法 带来很大的影响。 郜丽丽提出了物理结构特征与逻辑结构特征相结合的方法【1 0 】，通过提取表格的 物理结构，分析其逻辑约束关系，再结合文字识别软件，达到表格自动处理的目的。 这种方法由于表格中单元格之间的逻辑约束需要手工指定，增加了表格识别的时间。 2 2 2 统计特征提取方法 统计特征是一种数学的方法，具有很强的抽象和泛化能力，统计的方法主要有： 统计平均值、相关系数、协方差阵的本征值及本征向量等。 统计特征的优点是易于由计算机进行处理，并且采用这种方法能较好地从总体 上对识别对象的特征进行提取，由于能够综合考虑对象的全部特征，因此，与结构 特征比，具有很好的抗干扰能力；同时，使用统计特征，在很多情况下能够很好地 避免使用结构特征所带来的识别系统泛化能力的问题。 在图像的统计特征中认为图像信号是一个随机信号，可以用振幅或相位的分布 函数、概率密度函数以及一系列的相关矩、中心矩、功率谱等来描述表示图像的特 性，建立图像信息的数学模型，对图像信息进行分析和处理。表格图像统计特征的 抽取便在此基础上进行，一般通过各种变换手段对图像进行处理，如投影、离散傅 7 五邑大学硕士学位论文 立叶变换( d f t ) 、离散余弦变换等，然后，对图像的特征进行分析、提取，选择对 分类具有实质性作用的特征来设计分类器。 2 3 傅立叶变换 在图像处理中，对于某些在空间域中难于处理或处理起来比较复杂的问题，可 以利用傅立叶变换【1 1 】把用空间域表示的图像映射到频率域，采用频域滤波或频域分 析方法进行处理和分析，从而达到简化处理和分析的目的。 函数f ( x ) 的一维傅立叶变换公式如( 2 1 ) 式给出。 f ( c o ) = ff ( x ) e 嘲j d x( 2 1 ) 我们称函数f ( c a ) 为f ( x ) 的傅立叶变换，简称傅氏变换。f ( r o ) 的逆变换定义如式 ( 2 2 ) ： m ) = 专王m 螂d 国 协2 ) 上式( 功称之为函数f 佃) 的傅立叶逆变换，简称傅氏逆变换。 2 3 1 离散傅立叶变换( d f t ) 傅立叶变换实际上就是对频谱的分析，而利用计算机或数字设备对图像进行频 谱分析时，只能处理有限长数据，由于离散傅立叶变换能对有限长序列的傅立叶变 换及频率离散化，因此用计算机处理傅立叶变换时通常采用离散傅立叶变换。采用 离散傅立叶变换主要有两个原因： ( 1 ) 因为d f t 的输入输出均为离散值，非常适用于计算机的运算操作。 ( 2 ) 采用离散傅立叶变换，就可以用一种快速算法，即快速傅立叶变换( f a s t f o u r i e rt r a n s f o r m ) 。 对于长度为的序列x ( n ) ，其离散傅立叶变换形式为： x ( k ) = d f t x ( 力) 】：芝x ( 栉) e f 等h k ：o ，l ，n - 1 ( 2 3 ) 力) 】= x ( 栉) e 1 百“ = o ，l ， ( 2 3 ) 其逆变换为： x ( 刀) ：i d f t x ( k ) ：n - i x ( 后) p 警b l 胆：o ，l ，一1 ( 2 4 ) k = o 8 五邑大学硕士学位论文 有限长序列缸刀) 离散傅立叶变换的意义是： ( 1 ) x ( 七) 为序列缸刀) 在离散频率点q = 弓笋上的频谱值。 ( 2 ) x ( k ) 相当于频谱x ( e o ) 在【o ，2 万】范围内实施了等间隔采样，采样间隔为 a c t = 2 1 。 n 2 3 2 快速傅立叶变换( f f t ) 快速傅立叶变换是计算d f t 的一种快速而又有效的方法。快速傅立叶变换的原 理是： 在公式( 2 - 3 ) 中令d f t 的长度n = 2 肘，m 为正整数。将点的d f t 分解为两 个2 点的d f t 。现将x 0 ) 分解为两组，一组为偶数项，一组为奇数项，则： x ( 2 r ) m = x l ( r ) ，：0 , 1 ，2 一l ( 2 - 5 ) 【x ( 2 r + 1 ) = x 2 ( r ) 一 将d f t 运算也相应分为两组，即： x ( 忌) 2 丢五( ，) + 唬委而( ，) 嗡 ( 2 6 ) = 五( 后) + 孵置( 七)妒 其中，墨( 尼) 和五( 七) 分别是毛( ，) 和屯( ，) 的2 点离散傅立叶变换，孵：e f 箐时 是一个周期函数。 可见，一个点的离散傅立叶变换可以分解为两个2 点的离散傅立叶变换， 这两个2 点的离散傅立叶变换可再按照式( 2 6 ) 合成一个点的离散傅立叶变换。 而五( 七) 、五( 七) 有2 个点，即k = o 1 ，n 2 - 1 ，由式( 2 6 ) 得到x ( k ) 只有2 点。 依此类推，每次将2 除以2 ，就可分成越来越小的子序列执行离散傅立叶变换，直 到执行2 点的离散傅立叶变换为止，最后再合成点的离散傅立叶变换。 由于孵的对称性，由式( 2 6 ) 可得到： x ( 譬+ 七) ：五( 后) 一磷置( 尼) ，k = 0 ，1 ，了n 一1 ( 2 7 ) 式( 2 - 6 ) 表示了x ( 七) 前半部分( k = o ，1 ，2 一1 ) 的组成方式，式( 2 - 7 ) 则 9 五邑大学硕士学位论文 表示了后半部分( k = 3 1 2 9o 9 n 一1 ) 的组成方式。这两式所表示的运算过程可用一幅 称做蝶形的信号流图来表示。 如图2 1 ( a ) 所示，图中左面两支为输入，中间以一个小圆圈表示加、减运算， 右上支为相加输出，右下支为相减输出。如果在某一支路上信号需要进行乘法运算， 则在该支路上标以箭头，并将相乘的系数标在箭头边。 a + b r i ( j | ) a - b x 2 ( 七) ( a ) 加减蝶形运算符号( b ) 带有乘法的蝶形运算符号 图2 1 碟形运算流图符号 假设n = 2 3 = 8 ，用蝶形运算来分解的一个完整流程图如下所示： 图2 - 2n = 8 的按时间抽取法f f t 计算流图 由于这种方法每一步分解都是按输入时间序列是属于偶数还是奇数来抽取的， 所以称为“按时间抽取法 或“时间抽取法 。 时间抽取法f f t 的运算特点如下： ( 1 ) 蝶形运算 对于任何一个2 的整数幂= 2 肼，总是可以通过m 次分解最后完全成为2 点的 d f t 运算。这样的m 次分解，就构成x ( n ) 到x ( k ) 的m 级运算过程。 ( 2 ) 原位计算 当数据输入到存储器中以后，每一级运算的结果仍然储存在同一组存储器中， 1 0 川 五邑大学硕士学位论文 直到最后输出，中间无需其他存储器，这叫原位计算。这种原位运算结构可节省存 储单元、降低设备成本，还可节省找地址的时间。 ( 3 ) 序数重排 原位运算的输入与输出是按码位倒置来存储的，在实际运算中，直接将输入数 据“刀) 按码位倒置的顺序排好通常很不方便，因此总是先按自然顺序输入存储单元， 然后再通过变址运算将自然顺序的存储转换成码位倒置顺序的存储，之后再进行 f f t 的原位计算。 ( 4 ) 蝶形类型随迭代次数成倍增加 从图2 2 可以看出，第一级迭代只有一种类型的蝶形运算系数孵，第二级迭代 有两种运算系数暇、呒，参加运算的两个数据点间隔为2 ，第三级迭代有四类蝶形 运算系数蝶、暇、昭、暇，参加运算的两个数据点间隔为4 。所以，每次迭代的 蝶形类型比上一次迭代增加一倍，数据点间隔也增大一倍。 2 4 本章小结 本章首先介绍了模式识别中的特征提取与选择的理论知识，描述了两种常用表 格特征提取方法的特点及应用，然后介绍了傅立叶变换的原理，并重点阐述了快速 傅立叶变换。 本章内容是全文的基础，为其它内容的介绍作好了铺垫。 五邑大学硕士学位论文 第三章表格文档的预处理 为了便于将纸质的表格文档进行自动化管理和长久存放，需要将纸质的文档转 化成电子文档，但由于纸质文档存放时间可能比较长或其它方面的污染，将纸质文 档通过扫描仪扫描后的图像质量会有所降低，为了更加准确的对表格文档进行处理， 所以需要进行预处理工作以提高源图像的质量，将图像变换成便于人们观察、适于 机器识别或存储的形式。 预处理通常是由一系列图像到图像的变换组成，经预处理后的图像不会增加其 内容，但有助于我们对其内容的提取。针对不同的图像，常常需要采用不同的方法 或多种方法的组合来进行预处理，对含有噪声的图像，要除去噪声、滤去干扰，以 提高信噪比：对信号微弱的图像要进行灰度变换等增强处理；对己经退化的模糊图 像要进行各种复原。 图3 1 描述了表格预处理的步骤，表示的内容主要包括去黑边、图像的增强、去 噪、二值化等。 预处理 副图像蝴h 搬悃 3 1 数字图像的表示 图3 1 预处理流程图 图像分为物理图像和数字图像。我们处理的是数字图像，是物理图像的数字表 示形式。 数字图像的表示方式可以分为两类：位图方式和矢量方式【1 2 1 。 ( 1 ) 位图方式：也叫做点阵图、删格图像、像素图，简单的说，就是最小单位 由像素构成的图，缩放会失真。构成位图的最小单位是像素，位图就是由像素阵列 的排列来实现其显示效果的，每个像素有自己的颜色信息，在对位图图像进行编辑 操作的时候，可操作的对象是每个像素，我们可以改变图像的色相、饱和度、明度， 从而改变图像的显示效果。 1 2 五邑大学硕士学位论文 五邑大学硕士学位论文 黑色进行补充。由于黑边不是文档本身的信息，而是扫描过程中产生的附加信息， 因此，去除黑边对提高图像压缩比，改善视觉效果都非常有好处；甚至在一些识别 应用中，对于提高识别率都有很大帮助。因此，对于扫描图像而言，去黑边是必须 的。以下就去除黑边的有关原理和方法予以叙述。 3 2 1 数学形态学原理 数学形态学( m a t h e m a t i c a lm o r p h o l o g y ) 是由法国数学家g m a t h e r o n 和j s e r r a 于 1 9 6 4 年提出而逐渐发展起来的数学分支，成为图像集合特征分析与处理的有力工具， 它用具有一定形态的结构元素( s t r u c t u r ee l e m e n t ) 去度量和提取图像中的对应形状特 征，以达到对图像进行分析和识别的目的【13 1 。 数学形态学的基本运算包括膨胀( d i l a t i o n ) 、腐蚀( e r o s i o n ) 、开启( o p e n i n g ) 和 闭合( c l o s i n g ) ，由这些算法可以推导和组合各种实用算法。这种运算通常给出一个 图像集合和一个结构元素集合，利用结构元素对图像进行操作【1 4 1 。 ( 1 ) 平移 当一个结构元素s 的原点移到点( x ，y ) 处时，我们将其称为平移，记作。 ( 2 ) 对称集 图像x 对于图像原点的反射结果，称为x 的对称集，记为： z = u 一j ，) ( 3 - 1 ) ，ej ( 3 ) 腐蚀 图像x 用结构元素s 腐蚀所产生的图像e 中的点y ) 满足如下定义： e ( 石) = x o s = ( x ，y ) i 氏x ) ( 3 2 ) 上式表明：当结构元素s 的原点移动到( x ，y ) 位置时，s 完全包含在x 中。 腐蚀可以把小于结构元素的物体去除，选取不同大小的结构元素，可以去掉不 同大小且无意义的物体。如果两物体间有细小的连通，当结构元素足够大时，腐蚀 运算可以将物体分开。腐蚀有对图像内部滤波的作用，并将图像缩小。 ( 4 ) 膨胀 膨胀可看成腐蚀的对偶，图像x 用结构元素s 腐蚀所产生的图像e 中的点( x ，y ) 满足如下定义： e ( 工) = x o s = ( x ，y ) 博。n x a ) ( 3 3 ) 1 4 五邑大学硕士学位论文 上式表明：如果结构元素s 的原点位移到( x ，y ) ，它与x 的交集非空，这样的点 o ，j ，) 组成的集合就是s 对x 膨胀产生的结果。 膨胀可以填充图像中的小孔( 相对于结构元素而言比较小的孔洞) 及在图像边缘 出现的小凹陷部分，有对图像外部滤波的作用。 ( 5 ) 开运算 先腐蚀后膨胀的过程称为开运算，x 关于s 的开运算定义为； ( 柳蒯= x o s = ( 嬲s ) o s ( 3 4 ) 开运算的作用是消除细小物体，但又不明显改变其面积。 ( 6 ) 闭运算 先膨胀后腐蚀的过程称为闭运算，工关于s 的闭运算定义为： ( z ) 删= x o s = ( r o s ) s ( 3 - 5 ) 闭运算的作用是填充物体内细小空洞，连接相邻物体，在不明显改变物体面积 的情况下平滑其边界。 3 2 2 图像减法运算 图像减法运算也称差分方法，是一种常用于检测图像变化及运动物体的图像处 理方法。图像减法可以作为许多图像处理过程的准备步骤。例如，可以使用图像减 法来检测一系列相同场景图像的差异。 在m a t l a b 7 0 中，使用i m s u b t r a c t 函数可以将一幅图像从另一幅图像中减去，或 者从一幅图像中减去一个常数，其格式如下： i p = i m s u b t r a c t ( i ，b a c k g r o u n d ) ； 上式中的i 表示输入图像，b a c k g r o u n d 为另一幅输入图像并且与i 中的图像存在 部分相似，i m s u b t r a c t 函数将一幅输入图像的像素值从另一幅输入图像相应的像素值 中减去，再将相应的像素值之差作为输出图像相应的像素值。 3 2 3 去除黑边算法 去黑边有两种方法，一是将黑边从扫描图像中裁减掉：二是用白色填充黑色边 缘。在前一种方法下，图像的大小将会缩小到与原文档相同的实际大小；而在后一 种方法下，图像的尺寸将保持不变。本文将采用第二种方法。由于图像黑边一般比 图像内容灰度大，所以本文先对灰度图像使用开运算得到只有黑边的图像，再利用 1 5 血邑大学硕士学位论文 图像的减法运算将黑边去除，最终达到去除黑边的目的，具体步骤如下： ( 1 ) 将彩色的表格图像转化为灰度图像，如图3 - 3 所示； ( 2 ) 对耿度图像进行开运算，得到如图3 - 4 所示的图像： ( 3 ) 使用图像的减法运算，将图3 - 3 减去图3 - 4 ，得到图3 - 5 所示和原图一样 大小且没有黑边的图像。 用m a t l a b 工具箱提供的函数i m o p e n 和函数i m s u b t r a c t 来去除黑边的部分代码如 下所示： p s = i m r e a d ( h e ib m p l ) ； i = r g b 2 9 r a y ( p s ) ； j = i m a d j u s t ( i ，【0 15o 8 】， 01 ) ； s e l = s t r e l ( s q u a r e ，3 ) ； b w 3 = i m o p e n ( j ，s e l ) ； 对图像进行开运算 j = d o u b l e ( j ) ； b w 3 = d o u b l e ( b w 3 ) ； l p = i m s u b t r a c t ( j ，b w 3 ) ； 对图像进行减法运算 f i g u r e ，i m s h o w ( i p ， 】) ； 秕净幔z 啤自化 磊钍吃鱼 嘭布嘎晦 了i 百歹 1 l ! _ l i 盟d t 0 l ， j 、。m ， 审棱确认 谨存旅( ” 图3 - 3 灰度图像 翟到 ! 垡璺本湮一一l ； r 皓潆“ o l 五邑大学硕士学位论文 3 3 图像增强 图3 4 对幽3 3 进行开运算操作后的图像 兰苎竺! 竺竺笙! 竺。兰。兰。一蛔竺丝! ! j 秕唧嗜幢 嚣豫 ? 匿霹匾蕊 i 一i i 1 磊磊爵扩 图3 - 5 减法运算后的图像 经扫描或其他方式得到的图像通常都含有各种各样的噪声与畸变，会大大影响 图像的质量。因此，在对图像进行分析之前，必须先改善图像的质量。通常，采用 的是图像增强的方法。图像增强不会引起图像质量下降，而是将图像中感兴趣的特 征有选择地突出，并衰减不需要的特征，达到了改善图像的视觉效果，提高图像的 清晰度和工艺的适应性，以及便于人与计算机的分析和处理。 图像增强的方法分为空域法和频域法两类，空域法主要是对图像中的各个像素 1 7 五邑大学硕士学位论文 点进行操作；而频域法是在图像的某个变换域内对整个图像进行操作，并修改变换 后的系数。 3 3 1 直方图灰度变换 灰度变换增强是根据某种目标条件，按一定变换关系逐点改变原图像中每一个 像素点的灰度值的方法，即设原图像素的灰度值为d = f ( x ，y ) ，处理后图像像素的灰 度值为d = g “y ) ，则灰度增强可表示为1 5 1 ： 9 y ) = n g ( 毛少) 】( 3 - 6 ) d = r ( d ) 通过变换，达到对比度增强的效果。当灰度变换关系d = 丁( d ) 确定后，则确定 了一个具体的灰度增强方法。d = r ( d ) 通常是一个单值函数。 有多种方法可以实现灰度变换，其中最常用的就是直方图变换的方法对灰度图 像进行增强。图像的直方图是图像的重要统计特征，可以认为图像灰度分布密度函 数的近似，通常图像的灰度分布密度函数与像素所在的位置有关。设图像在点似y ) 处的灰度分布密度函数为p ( z ；x , y ) ，那么图像的灰度密度函数为： p 2 趣p 训) 蛐 ( 3 7 ) 式中，d 表示图像的定义域，s 是区域的面积。一般地讲，要精确得到图像的 灰度分布密度是比较困难的，所以实际中用图像的直方图来代替。灰度直方图是一 个离散的函数，它表示数字图像每一灰度级与该灰度级出现频率的对应关系。 假设一幅数字图像的像素总数为，有m 个灰度级，具有第七个灰度级的灰度 的像素共有个，则第七个灰度级出现的概率为： k = 鲁，七= 0 ，1 ，膨一l ( 3 - 8 ) 直方图灰度变换就是通过改变直方图的形状来达到增强图像对比度效果的。 3 3 2 图像去噪 图像系统中的噪声效应可以用一个无噪声或者很小的图像和一个随机噪声相加 表示。抑制相加性噪声的办法之一是对图像中的噪声信号进行线性滤波，其结果是 使图像和干扰系统进行平均的均方误差最小。可如图3 - 6 所示： 五邑大学硕士学位论文 图3 6 含有噪声图像模型 消除噪声一般采用低通滤波的方法。但低通滤波在消除图像噪声的同时，也会 消除图像部分有用的高频信息，因此，一种有效的图像去噪方法，就是在去噪的同 时又能保留有用的高频信息。目前关于图像去噪文献提出的方法主要有以下几类【1 6 】： ( 1 ) 维纳滤波器【1 7 1 维纳滤波器是线性平滑滤波器中的典型滤波器，常用于从加性噪声中恢复未知 信号。在均方误差最小的最优准则下，维纳滤波是一种最优滤波器。下面将详细介 绍维纳滤波过程。 假设图像和噪声互补相关，且噪声为零均值，对于恢复图像为g “y ) ，原始图 像为f ( x ，y ) ，噪声图像为n ( x ，y ) ，则有： g ( x ，) ，) = j j l ( 工一口，y - p ) ( a ，p ) d a d p + n ( x , y ) ( 3 9 ) 上式中f ( x , y ) 、g ( 毛y ) 和n ( x , y ) 分别为随机像场。式中噪声随机像场是无法准 确提前知道的，但它的统计特性是已知的。故在给定了g ( 毛y ) 时，仍不能求解f ( x ，y ) ， 但却可以求出原图像的估计值( 工，y ) ，使得均方误差万2 最小。 万2 e r i x ，y ) 一f 。o ，y ) 2 ( 3 1 0 ) 其中，f “j ，) 称为给定g ( x , y ) 时f ( x , y ) 的最小二乘方估计。 假设图像f ( x ，y ) 和噪声n ( x ，y ) 不相关，且它们同时都是零均值，则有： e f ( x , y ) n ( x ，y ) - e f ( x ，y ) e 以( 石，y ) = o 经过化简，得到 m ( u ，v ) ：旦掣一( 3 - i i ) ( “，v ) l h ( u ，