订单表格与内容识别算法研究.doc

订单表格与内容识别 算法研究 科研训练报告 2010/12/30 目录 1. 引言.42. 二值化.8 2.1概述.8 2.2线性对比度增强.9 2.3非线性对比度增强.10 2.4 LoG算子.14 2.5最大类间方差法. .16 2.6小结.173.自动校正倾斜法.18 3.1图像自动倾斜矫正算法的提出.,18 3.2文档图像倾斜角度自动检测算法的研究.18 3.2.1 档图像倾斜角度自动检测算法的研究.18 3.2.2 传统的Hough变换方法.19 3.2.3 带参数约束条件的Hough变换HTPC方法的提出.21 3.2.3.1 Hough变换算法的提出.21 3.2.3.2 参数约束条件的讨论.22 3.2.3.3 用HTPC方法检测图像倾斜角度.24 3.3 图像旋转算法的研究.25 3.3.1 传统的图像旋转方法.25 3.3.2 改进的快速图像旋转方法.26 3.3.3 旋转图像.284.表格字符定位与提取.29 4.1 概述.29 4.2 表格线搜索.29 4.2.1 采用投影法提取直线.29 4.2.2 消除表格中的文字.30 4.2.3 搜索表格线的位置.32 4.2.4 待分割区域位置描述.32 4.3 表格线的去除.34 4.3.1 表格线的描述.34 4.3.2 字线分离后对字符笔画的修整.37 4.4 字符分割.385.手写数字字符识别.39 5.1 特征提取.39 5.1.1 基于形状上下文的手写数字识别.39 5.2 分类器设计 . 416. 心得体会.427. 参考文献.44 摘要随着信息时代的来临,数字信息已经成为人类最重要的资源。而表单是最常见的一种信息载体,如何将表单文档中的信息电子化、数字化,已经成为研究的热点之一。本文对订单表格与内容识别算法进行了一系列的研究，为实现面向企业大规模报表的处理，提供半自动的识别与交互系统软件。首先从表单图像的特点出发,介绍了几种图像去噪方法和二值化方法,然后再对表格单元格定位和字符的提取。其次,针对扫描图像可能产生倾斜,论文对图像的倾斜角度进行了检测，并加以校正。模式识别在系统控制、人工智能、生物医学工程、遥感数据分析、军事目标识别等领域发挥了重要的作用,在国民经济、国防建设、社会发展和社会治安等方面得到广泛的应用。关键词ocr模式识别 表格识别 二值化 倾斜校正1引言订单表格与内容识别算法研究，主要内容为面向企业大规模报表的处理，提供半自动的识别与交互系统软件。脱机手写体字符识别技术是当前的热点和难点问题,是解决目前大量已有的文档资料录入工作的关键。在系统控制、人工智能、生物医学工程、遥感数据分析、军事目标识别等领域发挥了重要的作用,在国民经济、国防建设、社会发展和社会治安等方面得到广泛的应用。随着我国服务业的发展，国际外包业务也在不断延伸。其中订单表格的半自动处理，已成为发展国际外包业务中的重要需求软件。本项目正是瞄准这一市场需求目标，联合软件外包企业，开展这一研究工作。 手写数字识别是光学字符识别技术(简称OCR)的一个分支, 它研究的对象是如何利用计算机自动辨认人手写在纸张上的阿拉伯数字。在整个OCR 领域中, 最为困难的就是脱机手写字符的识别。到目前为止, 尽管人们在脱机手写英文、汉字识别的研究中已取得很多可喜成就, 但距实用还有一定距离。而在手写数字识别这个方向上, 经过多年研究, 研究工作者已经开始把它向各种实际应用推广, 为手写数据的高速自动输入提供了一种解决方案。由阿拉伯数字及少量特殊符号组成的各种编号和统计数据, 如 邮政编码、统计报表、财务报表、银行票据等等, 处理这类信息的核心技术是手写数字识别。因此, 手写数字的识别研究有着重大的现实意义, 一旦研究成功并投入应用, 将产生巨大的社会和经济效益。目前脱机字符识别的研究虽然取得很大的进展，但其技术还不太成熟，相对于使用的要求仍处于滞后状态。这主要是由于手写文档有一下两个特点：1.丢失了字符笔划书写顺序、速度等重要信息，且同一字符的写法千差万别，字符形态的随意性很大，识别过程存在大量的不确定性，从而导致字符特征信息较难选取，分类器的设计也较难实现。2.因书写习惯、用笔颜色深浅、力度变化以及扫描效果的不同而产生的手写体连笔、笔画断裂、噪声污染等原因使得字符图像不利于直接进行分类和识别，对于含有表格等较复杂格式的手写文档而言，字符信息的准确定位和完整提取也存在一定的难度。从目前流行的研究方法来看，针对脱机手写字符的第一个特点，人们主要从特征提取、分类器设计等方面着手研究；而对于第二个特点，人们则主要从文档图像预处理和文档字符提取两方面进行研究，即考虑文档图像去噪、二值化、字符信息提取与修复等问题。对于这两方面的问题，目前人们对前者进行了大量深入的研究，而对于后者则探讨较少。现在的一些关于文档图像处理、二值化及字符提取的方法在理论上也不太完善，缺乏系统的阐述和算法推导，效果也不太理想。 本项目的工作即就上述的第二个方面，进行深入研究并进行系列算法改进。主要工作内容包括：交互式表单处理软件系统的实现、印刷表格的识别、印刷数字与手写数字的分割和识别等方面的内容。另外本课题的工作涉及知识主要包括：图像处理、软件系统编程等方面的内容。表格识别的一般步骤如下图（1.1）所示：表格识别是字符识别技术最重要的应用领域之一。人们在日常工作、学习和生活中经常需要填写各种各样的表格:财务报表、商业数据统计表、税务统计表、学生成绩表等等，而这些表格中的大量信息常常需要输入到计算机进行整理、归类、排序和分析等更高一级的应用。因此，人们迫切需要一种表格自动识别系统来替代繁重的人工输入操作。一套高准确率、高效率和健壮的表格识别系统能够大大加快信息输入的速度、提高工作效率，从而产生巨大的经济效益。目前人们对带有一定格式文档的自动识别系统的研究较多的是邮政编码自动识别、金融票据识别、车牌识别等应用领域，而关于较复杂的表格识别的研究也有一些，但成型的实用系统较少，理论也不够完善。一个典型的表格识别系统由三部分组成:预处理模块、字符提取模块，以及OCR识别模块。表格识别的一般流程如图所示:表格文档首先经扫描仪扫描成图像;然后，预处理模块对表格图像进行自动倾斜校正和二值化处理;字符提取模块进一步对表格的单元格内字符进行定位和提取;最后，OCR模块对字符进行分割、特征提取和模式分类。这三个部分都是表格识别系统中不可缺少的组成部分。从图中我们也可以看出OCR识别模块的性能依赖于前两个模块的结果，良好的预处理和字符提取过程能为后续的特征提取及特征分类提供尽可能完整、可靠、无噪声干扰的字符信息，是提高整体识别率的关键之一。在表格文档扫描成图像的过程中，表格在图像中或多或少会出现一定角度的倾斜。这个问题会直接给表格单元格定位、字符分割等造成困难，甚至会影响系统最终的识别率，因为大部分OCR方法对字符的倾斜变形较敏感。关于文档图像倾斜角自动检测的问题，现有方法主要可归结为5类:Hough变换方法、侧面水平投影方法、傅立叶变换方法、k一近邻聚类方法，以及直线拟合方法。其中，前4种方法都比较耗时，而且除Hough变换方法外，其他方法都无法保证对含手写数字的表格文档图像取得较好的精度。倾斜校正之后，为了进一步提取出表格图像前景中的表格线和字符，我们还必须对图像进行二值化处理，这个过程实际上也能帮助简化后续的特征提取，因为一般而言，二值化图像中字符特征的维数比在灰度图像中直接提取的情况要少的多。现有的图像二值化方法分为6类:基于直方图形状分析的方法、基于聚类的方法、基于嫡的方法、基于前景对象属性的方法、基于空间信息的方法，以及局部自适应闻值选取方法。但这些方法都比较单一，在实际应用中往往无法较好的适应各种不同条件下的情况(如扫描结果亮度不均匀、笔划灰度较浅、图像直方图灰度值分布较均匀等)。表格字符准确定位与提取是表格识别最困难也是最关键的环节之一。表格字符定位的方法主要有两种:一种是利用先验知识，而另一种则是通过表格线检测来定位。前者一般先检测表格矩形边框的四个顶点在图像中的坐标，然后再利用单元格宽度和高度的先验知识求出每个单元格在图像中具体的位置，或者直接把表格图像和标准的空白表格进行模板匹配。这种方法需要借助先验知识，因而无法自动适应各种不同格式的表格。后者依表格线检测方法不同又可分为侧向投影法、轮廓提取法、表格线交叉点分析法、Hough变换法等几种。侧向投影法简单、速度快，但较容易受到表格倾斜和字符粘连表格线的影响;轮廓提取法也很容易因表格线断裂或字符粘连表格线而产生错误;表格线交叉点分析法则通过对相邻交叉点进行分类和匹配来迭代地构建出表格中的所有单元格，但该方法比较耗时，且容易受断裂表格线的影响;Hough变换是一种效果较好的方法，能有效检测出断裂表格线、虚线等不同类型的表格线。定位好字符所在的单元格以后，我们还需要把单元格里面的字符提取出来。对于字符与单元格边框线不重叠的情况，只需简单的把边框线去除就能达到目的。而字符与边框线重叠的情况就要复杂的多，重叠在边框线上的字符在边框线去除后都出现了不同程度的笔划断裂或缺失，这样将大大影响OCR模块对这些字符的识别效果。人们在完整提取表格字符这方面也做了相当多的研究。其中的一些研究把重点放在了如何改进识别算法上面。而更多的则是研究如何去除边框线，这方面又再细分出两类不同的方法:一类是只去除属于边框线的象素，而保留与边框线重叠的属于字符笔划部分的象素。由于一般的表格文档经扫描成灰度图像后，字符笔划与表格边框线的灰度值比较接近，通常很难直接区分边框线上的象素是否属于某个重叠在该边框线上的字符。一些方法则通过检测字符与边框线的交点，然后把属于一个字符的相邻两交点中间的象素保留下来，但这样从边框线中恢复出来的字符笔划往往恢复的不够充分，表现为字符笔划出现残留的边角，轮廓不够平滑。另一类方法则考虑先去除所有的边框线，然后根据重叠区域的局部性质(如笔划方向、连接点等)来恢复断裂、丢失的笔划。但该类方法对含有圈型结构的字符重叠边框线的情况则无法有效恢复。本文的引言部分描述了OCR及脱机表格识别的相关概念及背景，并对本文主要关注的相关问题的主流研究方法进行了全面的概述。第二部分通过对现有的单一图像二值化方法的研究，在现有方法的基础上给出了一种基于非线性对比度增强及 LoG算子的混合二值化方法，有效克服了使用单一方法进行二值化的缺点。第三部分主要分析了现有的倾斜角检测方法，并在传统Hough变换方法的基础上构造出一种带参数约束条件的Hough变换方法，另外还给出了一种实现图像旋转的快速方法。第四部分着重介绍了表格字符定位与提取方法。第五部分介绍了脱机数字识别的字符分割、特征提取、分类器设计等问题。2 二值化 2.1 概述在各种文档分析及自动识别系统中，人们在对扫描后的文档图像进行进一步的分析和识别之前通常会对其进行二值化处理，即把图像中的每个象素点按照某种规则标记为前景点(通常为黑色)或背景点(通常为白色)，以使得前景字符与背景分割开来。二值化过程将直接影响提取出来的前景字符图像质量的好坏，从而影响整个自动识别系统后续环节的性能。但现实中一些不利的因素常常会导致图像二值化的效果变差，例如手写输入工具不好、文档背景图案干扰以及扫描亮度不均匀等等。因此，如何从各种文档图像的背景中用二值化方法提取出人们感兴趣的待识别字符就成了一个非常有挑战的问题。经过了无数的数学家和计算机科学家的努力和研究，图像二值化的方法有很多很多。通过实验尝试和分析项目需求，在综合考虑了时间复杂度、空间复杂度和二值化效果等各种因素后，我采用“最大类间方差法”来实现项目的图像二值化。针对现有的单一化方法存在的缺点，我们提出了一种基于非线性对比度增强及LoG算子的混合二值化方法。该方法的主要思想是：通过非线性对比度拉伸改善图像前景、背景象素在直方图中的分布，尽量使直方图出现双峰或近似双峰的特性，从而突出前景字符;然后用高斯型拉普拉斯算子模板对图像中的字符边缘进行定位，并利用LoG算子可以判定给定象素点是在边缘较亮的一边还是较暗的一边的特性，找出字符的内部象素。最后，我们通过最大类间方差法阈值选取对图像进行二值化处理。下面几节将详细介绍每一个步骤，我们首先从线性对比度增强谈起。2.2 线性对比度增强我们约定前景象素比背景象素的灰度值更小（更暗），并记AVE为图像的平均灰度值，Tfmax 、 Tfmin分别为图像前景象素的最大、最小灰度值，Tbmax , Tbmin分别为图像背景象素的最大、最小灰度值。在理想情况下，我们有以下关系式:Tfmin Tfmax AVE Tbmin Tbmax (2.1)在该情况下，我们只需把AVE作为阐值对图像进行二值化，便能完全区分前景和背景象素。但现实中的情况往往比(2.1)式复杂。文档图像往往由于亮度不均匀，而且图像中背景象素往往比前景象素多的多，因此实际中下式往往成立:Tfmin Tfmax Tbmin AVE Tbmax （2.2）例如，一幅图像的前景象素的最小和最大灰度值分别为0和40，背景象素的最小和最大灰度值分别为200和254，前景象素和背景象素的总数分别为500和10000，则图像的平均灰度值可近似的计算出来:显然，该结果满足(2.2)式:040200217.141时，灰度值映射的权重偏向较高（较亮）的灰度值；当R1，故原来落在(MIN,TbMin的部分象素又被映射到了TbMin,AVE上。这样的结果显然不是我们希望看到的。所以，线性灰度值拉伸并不能充分满足我们的要求。根据以上分析的结果，我们最终希望找到一种映射函数，使得其拉伸率在(MIN,TbMin内满足R1以抑制背景象素，从而真正达到增强图像前景和背景象素对比度的目的。经过研究，我们发现非线性映射函数能较好的满足这样的要求。图2.1显示了非线性与线性映射函数的区别。从图中可以看出，当x(MIN,TbMin时，非线性映射曲线位于恒等映射曲线y=x的下方，此时显然有R1。而线性映射曲线则恒位于y=x的上方，拉伸率恒保持R1不变。图2.1 灰度值非线性拉伸与线性拉伸的区别图2.2 p取不同值时对应的非线性灰度值映射曲线非线性灰度值拉伸可按下面的非线性灰度值映射函数进行：（2.4）(2.4)式中I(i,j),I(i,j)分别为原图像和对比度拉伸后的图像，MIN.AVE分别为原图像的最小灰度值和平均灰度值，P为指数。显然，当p=1时，(2.4)式就是(2.3)式。即我们可以认为，线性灰度值映射是非线性灰度值映射的一个特例。图2.7显示了P在不同取值下对应的非线性映射曲线。从图中可以看出当p=1时，映射曲线恒位于y=x的上方，拉伸率恒保持Rl，显然我们不应采用这类曲线，因此P的取值可进一步限制为。0pl。但P具体取何值才能满足我们的需要呢?根据前面的分析，指数P应满足:非线性映射曲线与恒等映射曲线y=x相交时x=TbMin。但TbMin的值是无法知道的，因为TbMin依赖于最终阈值选取的结果，然而阈值选取的过程(非线性映射)又依赖于TbMin的值。因此，P值无法直接通过解析的方法求出，只能在不同的应用中依靠经验来确定。在我们的表格文档图像识别应用中，P应该根据图像的不同情况来确定。与线性对比度增强相比，非线性对比度增强使文档图像的前景象素灰度更暗，同时使背景象素灰度更亮，从而更能有效增大图像对比度，为后续的边缘提取以及阈值选取步骤作了更好的准备。图2.3 对比度拉伸图2.4 拉伸对比度图2.4 拉伸2.4 LoG算子一阶导数可以用于检测图像中的一个点是否是边缘上的点，但却无法直接检测出一个点的灰度是亮还是暗。因此一般的一阶微分算子只能提取出文档图像中的字符边缘，而无法提取出字符笔划内部。我们希望找到一种能够直接判断一个点是外部点还是内部点的边缘提取算子，而基于二阶微分的边缘算子恰好能满足这个要求，因为二阶微分可以用于判断一个象素是在边缘亮的一边还是暗的一边。拉普拉斯算子是图像增强处理应用中的一种常用的二阶微分算子。一个二元函数f(x,y)的拉普拉斯变换定义为： （2.5）为了使（2.5）式适用于数字图像，我们必须引入(2.6)式的离散形式，在x方向和y方向上我们分别对二阶偏微分采用下列定义：（2.6） (2.7)因此，2.5式可变为：(2.8)(2.8)式可用图2.3(a)所示的滤波器模板来实现。对角线方向也可以加入到离散拉普拉斯变换的定义中，即两个对角线方向各加一个类似(2.6)式或(2.7)式的新添项。类似地，这一新的定义可用图2.3(b)所示的滤波器模板来实现。图2.3(c)、(d)所示的滤波器模板也比较常用，它们分别为滤波器模板(a)、(b)符号取反的情形，因此它们产生等效的结果。图2.3 四种离散拉普拉斯变换所用的滤波器模板由于拉普拉斯算子作为一个二阶导数对噪声具有敏感性，为了解决这一问题，我们可以考虑在应用拉普拉斯算子之前先用高斯函数对图像进行平滑处理以减少噪声的影响。考虑二维高斯函数： （2.9）其中，是标准差。用(2.9)式与图像做卷积就可以模糊图像，图像模糊的程度是由值决定的。因为二阶导数是线性运算，所以先用（2.9）式的高斯型平滑函数卷积图像然后应用拉普拉斯算子，与先对（2.9）式应用拉普拉斯算子（即求h(x,y)的二阶导数）再把结果与图像做卷积是一样的。H的二阶导数是： （2.10）（2.10）式一般称为高斯型拉普拉斯算子，其图像的形状像一个墨西哥草帽。类似拉普拉斯算子，我们也相应地引入（2.10）式的一种离散形式，如图2.4中的5*5模板所示。这种模板并不是唯一的，其目的是近似h本质的开关，即，一个正的中心项，周围被一个相邻的负值区域围绕，并被一个零值的外部区域所包围。模板的系数总和也是必须为零，以便在灰度级不变的区域中模板的响应为零。 图2.4 LoG算子的近似5*5模板 图2.5 复合拉普拉斯算子模板LoG算子在拉普拉斯算子的基础之上引入了高斯滤波，这种图像的平滑处理降低了噪声的影响，并且更为严重的是抵消了由拉普拉斯算子中的二阶导数引起的逐渐增加的噪声影响。在应用的时候为了能使结果符合我们的习惯，即背景灰度值较亮而前景灰度值较暗，我们将LoG算子的运算分开进行：先进行高斯滤波，然后用图2.5所示的复合拉普拉斯算子模板进行滤波。图2.5所示的复合拉普拉斯算子模板实际上是在图2.3(d)中模板的基础上再与原图进行相加而来的，即,即相当于模板中心系数比原来加了1。实际上这也是一个图像增强的过程，图像整体显得更加锐利，背景与前景象素的对比度也进一步拉大。图2.6 边缘检测加强2.5 最大类间方差法根据运算范围的不同,文档图像的二值化方法分为全局方法和局部方法,全局方法根据文档图像的直方图和灰度空间分布确定一个阈值,以此实现灰度文档图像到二值化图像的转化,典型的全局算法包括平均灰度法,Otsu方法,迭代最优算法等,局部阈值通过考查每个像素点的邻域来确定阈值,比全局阈值具有更广泛的应用,常用的局部阈值方法有Niblack方法,Bernsen方法,平均梯度法等。另外还有很多其他方法例如基于熵和基于模糊集合的方法等。Otsu方法:又称为最大类间方差的方法,于1979年提出,是一种自适应的阈值确定方法。它根据图像的灰度特性,将图像分成背景和目标两部分,背景和目标的方差越大,说明两部分的差别越大,因此类间最大方差的分割意味着错分概率最小。最大类间方差法它的基本思想是利用一幅图像的灰度直方图，依据类间距离极大准则来确定区域分割门限。该方法的基本原理如下：设图像有L个灰度级，灰度值是i的像素数为ni，则总的像素数是N=ni（i=0 to L-1），各灰度值出现的概率为pi=ni/N，显然pi0且pi=1。设以灰度t为门限将图像分割成2个区域：灰度级为1t的像素区域A（背景类）和灰度级为t+1L1的像素区域B（目标类）。则A、B出现的概率分别为pA=pi , (i=0 to t)pB= 1 pA=pi , (i=t+1 to L-1)则A和B两类的灰度均值分别为A、B图像总的灰度均值为：0 = p A * A + pB * B = i * pi ,(i=0 to L-1)由此可以得到A、B两区域的类间方差：2= pA * ( A 0 ) 2 + pB * ( B 0 ) 2。显然，pA、pB、A、B、0、2都是关于灰度级t的函数。为了得到最优分割阈值，Otsu把两类的类间方差作为判别准则，认为使得 2 值最大的t*即为所求的最佳阈值：t* = Arg Max pA * (A 0 ) 2 + pB * ( B 0 ) 2(0t L 1)因为方差是灰度分布均匀性的一种度量，方差越大，说明构成图像的两部分差别越大，当部分目标错分为背景或是部分背景错分为目标都会导致两部分差别变小。因此，使类间方差最大意味着错分概率最小，这就是Otsu准则。2.6 小结本章介绍了对文档表格的二值化方法，我们先通过非线性灰度值拉伸增强了图像的对比度，然后通过LoG算子定位出字符边缘及字符内部象素，最后采用Ostu最大类间方差法阈值选取方法求出阈值并进行二值化。取得较好效果。3. 自动校正倾斜法3.1 图像自动倾斜矫正算法的提出待识别文档被扫描成图像的过程中，或多或少地会出现某种程度的倾斜。这常常会引发以下儿个问题:1. 倾斜图像会给字符分割造成困难;2. 大部分OCR方法对倾斜变形的字符都比较敏感，这会直接影响这些方法的识别精度;3. 在表格处理中，图像的倾斜会引起单元格的定位不准确，从而影响表格字符的提取。因此我们有必要设计出一个算法，来自动测量图像的倾斜角度，并进行快速倾斜矫正。OCR识别输入的图像中一般包含两种成分:文字段落和表格(包含印刷体或手写体字符)，我们把所有包含任一种成分或两者兼而有之的图像统称为文档图像(DocumentIm age)，不同的倾斜校正方法适用于不同类型的文档图像。文档图像的倾斜校正一般分为两个步骤:文档图像倾斜角度检测和图像旋转。3.2 文档图像倾斜角度自动检测算法的研究3.2.1 现有倾斜角度检测算法的介绍人们对图像倾斜角检测问题做了许多深入的研究，归结起来，主要的检测方法可分为5类:Hough变换方法、侧面水平投影方法、傅立叶变换方法、k一近邻聚类方法，以及直线拟合方法。Hough变换是用来在图像中检测直线的一种方法，该方法因其对有噪声千扰的图像表现出相当好的稳定性和鲁棒性而被广泛应用于各种类型文档图像的倾斜角度检测。但传统的Hough变换计算复杂度较高，人们又提出了一些改进方法，如分层Hough变换等，来提高计算速度。侧面水平投影法是利用侧面投影直方图的变差来计算文档图像的倾斜角度，即倾斜角度对应着图像侧面投影直方图的平均平方变差为最大的方向。此方法要求逐步旋转侧面投影方向并多次计算平均平方变差，因此实现起来比较费时，且较难达到满意的精度。在傅立叶方法中，文档图像的倾斜角度对应着傅立叶空间中密度最大的方向，但此方法必须对图像的每个象素点都进行耗时的傅立叶变换，因此它的计算复杂度非常高。而k一近邻聚类方法提出，可利用一系列相邻连通区域对应的k一近邻中心来计算任意一对中心之间的向量的方向，随后就可以利用向量方向直方图的峰值来求得文档图像的倾斜角度。此方法通常能获得较高的精度，但计算时间代价却相对比较高，特别是连通区域较多的情况下。直线拟合方法是一种新提出的比较快速有效的倾斜角检测算法。该方法通过寻找同处一行的每个字符(看成一个单独的连通区域)的特征点，并对这些特征点进行聚类和直线拟合来计算出文档图像的倾斜角度，并通过子区域选取来减少数据量，从而获得较快的计算速度。该方法对印刷体字符文档图像有不错的效果，但对手写字符文档图像却常常无法保证很好的精度，这是因为手写体的字符即使同处一行也很难保证其笔划底端都在一条直线上。3.2.2 传统的Hough变换方法Hough变换是用来在图像中检测直线的一种方法，该方法因其对有噪声千扰的图像表现出相当好的稳定性和鲁棒性而被广泛应用于各种类型文档图像的倾斜角度检测。设在一个二值图像上画了一条直线，要求出这条直线所在的位置。我们知道：直线的方程可以用y=k*x+b来表示，其中k和b是参数，分别是斜率和截距。过某一点(x0,y0)的所有直线的参数都会满足方程y0=kx0+b。即点(x0,y0)确定了一族直线。变换方程y0=kx0+b为b= -kx0+y0,即将x,y参数平面转换为k,b参数平面。且方程b= -kx0+y0在参数k，b平面上代表一条直线，(即定点（x0,y0）相当于b= -kx0+y0 方程的斜率和截距，这样，x0，y0 就在k,b参数平面上确定了一条直线)。这样，图像x，y平面上的一个前景像素点就对应到参数平面上的一条直线。图3.1 (a) xy平面 (b)参数平面我们举个例子说明解决前面那个问题的原理。设图像上的直线是y=x, 我们先取上面的三个点：A(0,0), B(1,1), C(2,2)。可以求出，过A点的直线的参数要满足方程b=0, 过B点的直线的参数要满足方程1=k+b, 过C点的直线的参数要满足方程2=2k+b, 这三个方程就对应着k,b参数平面上的三条直线，而这三条直线会相交于一点(k=1,b=0)。同理，原图像上直线y=x上的其它点。对应k,b参数平面上的直线也会通过点(k=1,b=0)。这个性质就为我们解决问题提供了方法，就是把图像平面上的点对应到参数平面上的线，然后通过对这条线进行投票，最后通过对参数平面的投票数进行统计来解决问题。假如图像平面上有两条直线，那么最终在参数平面上就会看到两个峰值点，依此类推。简而言之，Hough变换思想为：在原始图像坐标系下的一个点对应了参数坐标系中的一条直线，同样参数坐标系的一条直线对应了原始坐标系下的一个点，然后，原始坐标系下呈现直线的所有点，它们的斜率和截距是相同的，所以它们在参数坐标系下对应于同一个点。这样在将原始坐标系下的各个点投影到参数坐标系下之后，看参数坐标系下有没有聚集点，这样的聚集点就对应了原始坐标系下的直线。图3.2 用于Hough变换的参数平面进一步分割但是在实际应用中，y=k*x+b形式的直线方程没有办法表示x=c形式的直线(这时候，直线的斜率为无穷大)。所以实际应用中，是采用参数方程p=x*cos()+y*sin()。这样，图像平面上的一个点就对应到参数p，平面上的一条曲线上，其它的还是一样。图3.3(a)直线的参数方程表达式 (b)将平面细分为不同单元两种方程的实例如下：3.2.3 带参数约束条件的Hough变换HTPC方法的提出在3.2.2介绍的Hough变换基本算法思想的基础上，为了有效降低算法的计算复杂度，我们针对手写字符表格图像的特点，构造出了一种带参数约束条件的Hough变换方法，简称为HTPC (Hough Transform with Parameter Constraints)方法。首先，我们根据Hough变换的基本思想写出Hough变换算法流程：3.2.3.1 Hough变换算法的提出算法3.1 Hough变换算法(1)初始化:令x=0,y=0(2)取图像A中的点A(i,j)，如果A(i,j)是前景点，则跳到(3)，否则跳到(4)(3)令;(3.1)如果,则往下执行(3.2)，否则跳到(4);(3.2)计算p值：p=xcos+ysin;(3.3)令n=p-pmin;(3.4)累加器加1:Accum(m,n)=Accum(m,n)+1;(3.5)令，m=m+1;跳回(3.1)继续执行。(4) 令y=y+1，若j=height，则跳回(2)继续执行，否则令x=x+1, y=0,若x=width，则跳回(2)继续执行，否则终止算法。说明:上述算法中，、分别代表可取的最小和最大值；pmin、pmax分别代表p可取的最小和最大值；表示将离散化的步长值:Accum是一个2维数组，第1维对应不同的值，第2维对应不同的p值。当和p分别取定、时，数组对应参数为、的直线段的累计点数。3.2.3.2 参数约束条件的讨论容易发现，Hough变换算法中总共有等5个参数，若不对这5个参数进行取值约束，那么Hough变换的计算量将变得非常大。接下来我们将讨论这些参数的约束条件。为了方便表达，我们在此约定一种表达方式:X=Cond?E1:E2 。其中X是变量;Cond是一个逻辑判断语句(含=等逻辑运算符号)，其结果取值是True或False;E1、E2是两个不同的运算表达式，其结果取值皆为实数。该表达式的意思为若逻辑判断语句Cond结果取值为True，则X=E1,的值;否则，若Cond取值为False，则X=E2的值。设文档图像倾斜角满足:,其中，为文档图像的最大倾斜角度。从图3.4(a)中可以看出，当时,这是因为：此时，。否则，当时,如3.4(b)所示，图3.4 图像倾斜角限制在时满足不同条件的情形概括起来就是当时, (3.1) (3.2)可见，的取值范围是依赖于的取值范围的，取值越小，的取值范围也越小。在实际开发过程中，我们发现，所有表格的倾斜角都不超过40，事实上最大的倾斜角只有3.20，这是由于一般家用、商用扫描仪扫描面板大小所限，对于A4大小的文档，如果倾斜角度过大会导致文档一部分内容落在扫描面板以外而无法被扫描。因此，在实际应用中我们限制取较小的值是合理和可行的。我们取定。另外,我们通过对大量真实表单的研究发现Hough变换没必要对整幅表单图像进行，而可以只对其某个区域来进行，我们称这个区域为AOI（Area OfInterest)。同时，通过研究我们发现表单有以下特点:1.表格线分布比较规则和均匀;2.只含两个方向的表格线，彼此互相垂直;3.同方向的表格线之间几乎等距间隔。因此，我们用图像的长宽的一半来识别。3.2.3.3 用HTPC方法检测图像倾斜角度根据以上3.2.3.2小节的分析，Hough变换的参数约束条件可以归纳为:条件3.1 Hough变换的参数约束条件我们把满足条件3.1的Hough变换称为HTPC方法，把传统Hough变换称为THT(Traditional Hough Transform)。HTPC方法比THT优胜之处在于，它能够非常有效的缩小Hough变换算法中和的取值范围及图像中进行Hough变换的区域大小，从而提高运算速度同时节省存储空间。假设正/余弦三角运算时间耗费为T，乘法运算时间耗费为M，加法运算时间耗费忽略不计，以一幅尺寸为1024*1365的图像为例，下面我们分别讨论THT和HTPC方法的时间、空间复杂度，并加以对比。在THT中，根据(3.2)式和(3.3)式可知，即，取，则THT的时间耗费为，即，空间耗费为个单位。而在HTPC方法中，根据式Hough2和式Hough3可知，即，取，AOI面积为，则HTPC方法的时间耗费为,即，空间耗费为个单位。从理论上的分析可以看出，HTPC比THT在运算速度上快了约100倍，在存储空间上节省了约97%。因此，HTPC方法大大改善了Hough变换的性能，是一种非常高效的算法。3.3 图像旋转算法的研究3.3.1 传统的图像旋转方法：设图像绕任意点C(x0,y0)旋转角度，如图所示：我们可通过以下几个步骤来实现该旋转变换:(1)将指定的任意旋转中心C(x0,y0)平移到坐标原点O，变换矩阵为Ts1。(2)使图像绕坐标原点逆时针旋转角，变换矩阵为Tr.(3)使旋转中心从坐标原点平移回原来的位置C(x0,y0)。变换矩阵为Ts2.所以图像绕任意点C(x0,y0)的旋转过程为将每一象素点的齐次坐标的行向量右乘变换矩阵:x,y,1=x,y,1Ts1TrTs2=x,y,1T其中:所以：即：根据上式，我们可以计算出传统图像旋转方法的时间复杂度。假设正/余弦三角运算时间耗费为T，乘法的运算耗费为M，加法的时间耗费我们可忽略不计，图像的宽和高分别为W,H。则进行一次旋转的时间耗费为，我们以一幅尺寸为1024*1365的图像为例，旋转一次需要耗费时间为。显然，这样的执行效率是非常慢的，我们需要对算法进行改进。3.3.2 改进的快速图像旋转方法由于图像是线性存储的，一幅图像就是一个象素点阵列，象素点之间的相对位置关系是确定的。如下图所示，图像定义在矩形域PA、PB、PC、PD中。任意象素点P(x,y)和与其同列的第一行象素点PR(xR,yR)，和与其同行的第一列象素点PL(xL,yL)，以及位于第一行第一列的象素点PA(xA,yA)在几何上是矩形的四顶点关系。在旋转之前，矩形的一个顶点坐标可以由其它三个顶点坐标来确定:由于旋转变换是线性变换，矩形的形状并不因旋转而发生变化。如上图右所示。因此，旋转后上式（我们标记它为式二）仍然成立！所以利用图像第一行和第一列的象素的旋转结果就可以计算出其它所有象素的旋转后的位置。因此旋转一幅图像，只需对第一行和第一列的象素按（式一）进行旋转变换，对除第一行和第一列以外的象素用(式二)进行简单的加减运算即可，这样就避免了对整幅图像的所有象素都作复杂且耗时的矩阵相乘运算。据说，这样做效率提高了500多倍！3.3.3 旋转图像下面介绍如何正确的旋转我们的图像。经Hough变化检测直线算出直线的极坐标角度0。后，可确定图像需要旋转的角度。当0/2时分为三种情况：a.当0/4时：（如下图）可知图像需要顺时针旋转/2-0c.45度角时正反转都行。当0/2 时情况与此类似。这里就不再赘述了。翻转实例：4. 表格字符定位与提取4.1 概述表格是一种常见的文档形式。它作为一种高度精练集中的信息表达手段，以其简明规范便于填写和处理等特点，被广泛地应用在国民经济和日常生活的各个方面。表格的自动输入存储管理已经成为文档智能处理领域的一个重要组成部分。表格由一