（计算数学专业论文）表格识别预处理技术与表格字符提取算法的研究.pdf

中文摘要 表格识别预处理技术与表格字符 提取算法的研究 专业 ： 计算数学 学位申请人 ： 谢亮 导师及职称 ：关履泰教授 李小福副教授 摘要： o c r 是模式识别中最热门的研究领域之一，而表格识别是o c r 的一个重要 的研究和应用方向。本文主要讨沦表格识别中的两个问题，即表格识别预处理技 术与表格字符提取算法。 二值化是图像处理和字符识别中相当重要的一个环节。本文在现有的图像二 值化算法的基础上，针对手写表格文档提出了一种基于非线性对比度增强及l o g 算子的混合二值化方法，基本上克服了现有方法所存在的对噪声敏感、速度较慢、 易导致笔划断裂等缺点。实验证明该方法比传统方法有显著改进。 待识别文档被扫描成图像的过程中不可避免地会出现定的倾斜。本文针对 表格文档图像，在h o u 曲变换的基础上提出了一种带参数约束条件的h o u g h 变 换h r p c ，有效降低了传统h o u g l l 变换的计算复杂度，并结合一种快速图像 旋转方法，实现了对表格文档图像的快速倾斜角检测及校正。 本文研究的重点之一是如何解决表格文档中手写字符经常重叠表格边框线 的问题。为此，我们提出了一种新方法来准确定位和完整地提取重叠边框线的字 符，即先通过叫r 过程准确地定位并提取出表格的所有单元格，再通过e c c e a 方法完整地提取出表格中的字符，然后利用基于连通区域检测的去噪算法对图像 进行去噪，最后对字符图像进行平滑化处理。实验表明了我们的方法的有效性。 最后，我们利用本文提出的表格文档预处理及字符提取算法，并结合我们对 字符分割、特征提取以及分类器设计等问题的最新研究，研制开发了w i n d o w s 平台上适用的成绩单自动识别系统，其总体识别率达8 5 以上。 关键字：o c r ，表格识别二值化，倾斜校正，重叠边框线，字符提取 薹苎塑至一 r e s e a r c ho np r e - p r o c e s s i n ga n dc h a r a c t e r e x t r a c t i o no ff 0 r md 0 c u m e n tr e c o g n j t i o n m a j o n a m e s u d e r v j s o r c 0 m d u t a t j o n a im a t h e m a “c s x l e 。l i a n 9 p r o f e s s o rg u a n l u t a i a s s o c i a t ep r o f e s s o rl i ，x i a o f u a b s t 怕c t ： o c rh a sr e c e i v e dc o n s i d e r a b i ea t t e n t i o nj nr e c e n td e c a d e s a n df o 咖d o c u m e n t r e c o g n i t j o nh a sb e e n a ni m p o n a n t 丘e l do fo c rr e s e a r c ha n da p p l i c a t j o n t h j s d i s s e n a t i o nm a i n l yf o c u s e s o nt w oi s s u e so ff o 册 d o c u m e n t r e c o g n j t j o n ： p r e p m c e s s i n ga n d c h a 阳c t e re x t r a c t j o n b i n a r i z a t i o na p p e a r st ob ea i li m p o n a ms t e pi ni m a g ep t o c e s s i n ga n dc h a r a c t e t r e c o 甜l i t i o n 。1 1 0o v e r c o m et h ed r a w 南a c k so fc u e n tm e t h o d si nt h e1 i t e r a t u r e n o i s e s e n s i t i v e ，1 0 ws p e e d ，a n da r o u s i n gb r o k e ns t m k e se t c ，ah y b r i dm e t h o db a s e d o nn o n 1 i n e a rc o n t r a s te l l l l a n c i n ga i l dh g0 p e r a t o ri sp r c s e n t e dt ob i n a r i z ef o m d o c u m e n tj m a g e s e x p e r i m e n t ss h o wt h a to u ra p p r o a c hh a ss i 印i f j c a l l ta d v a n t a g e s s k e w sa r ei n e v i t a b l yi n t r o d u c e dd u r i n gt h eo a u i s eo fs c 砌i n g an e wa p p r o a c h b a s e do nh o u 9 1 】t 柚s f o n n h o u 曲t 埘1 s f o 珊w j t hp a r a m c t e rc o n s t r a i n t s ，j s i m p l e m e n l e di nt h es p eo ff o 彻d o c i l m e n li m a g e s i nc o | 1 】b i n a t i o nw i t haf a s ta 彤n e t 硎n s f q 瑚，t h i s 印p t o a c ha p p e a r sl od r a m a t i c a l l ys p e e du ps k e wc o r f e c t i o n - o n eo fo u rc r i t i c a lt a s k si st od e a lw i t ht h es i t u a t i o ni nw h i c hh a n d 、】l 硝i t t e n c h a r a c t e r sa r eo v e l a p p i n gb o r d e r s an o v e la p p r o a c hi sp r e s e n t e dt os o l v e t h i s p r o b l e m ：f o 册c e l l sa r ea c c u r a l e l yl o c a t e dn o u g l i ac r fp r o c e s s 知dc h a r a c t e r s o v e f l a p p i n gb o i t s 缸ep e r f e c t l ye x 虹a c t 讨b y u t m z i i l g a ne c c e am e t h o d d e _ n o i s i n ga n ds m o o t h i n ga r ec a i r i c do u ta s al a s ts t a g e e x p e r i m e n t sp r o v et h e e f ! f - e c t i v e n e s so fo u ra p p r o a c h 。 f i n a l ly w i t hl h eh e l po ft h em e t h o d sa i l da l g o r i i h m sp 0 p o s e dj nt h i sd i s s e r t a t j o n ， a n dw j i ht h ee x 口l o i t a t i o no fo i l rl a t c s tr e s e a r c hi na r e a sl i k ec h a r a c t e rs e g m e n t a t i o n ， f c a t u f ce x t r a c f j o na n dd a s s i f i c a t i o n ，a na u t o m a i i ct r a i l s c r j p tr e c o 印i t i o ns y s t e mi s d e v e l o p e d ，w i t har e c o 鳃i t i o nr a t eo f8 5 k 鼬，1 i i o r d s ：o c r ，f 0 1 皿d o c u m e n ti e c o g n “i o n ，b i a i i z a t i o n ，s k e wc o h e c t i o n ， o v e r l a p p i n gb o r d e r s ，c h a r a c t e re x t r a c t i o n 1 i l 第一章绪论 第一章绪论 1 ，1 引言 手写文档在相当长的时期内一直被用来记载信息或用于人与人之间的沟通 交流。但到了计算机及其相关的信息技术迅速发展的今天，人们却不禁思考纸质 文档最终会否消失 1 】。但不管怎样，纸质文档作为信息保存和沟通的介质仍然有 着许多优点：安全、保密性好、非常便携，以及最为方便和符合人类的习惯。因 此，可以说纸必定将会继续充当人类用于保存和传输信息的最常用的介质，纸质 文档在人们的日常生活中还会继续扮演重要的角色。 而只要纸质文档在继续使用，人类就一定会有使用机器去识别纸介质文档这 一应用的需要。这是因为，全世界的计算机每天都要处理数以亿万计的商业、金 融及办公文档，而其中相当大一部分还是依靠人工读取和敲击键盘输入计算机进 行处理的，这种简单、重复而又繁琐乏味的工作消耗了大量的人力和宝贵的时间， 严重拖慢了人类社会信息化的步伐。解决这个问题的一种方法是用字符识别系统 来代替信息录入员的人工操作。这种系统能自动分析和识别文档材料，从而使人 们从繁重的数据录入工作中解脱出来。 字符识别是模式识别的一个重要分支，其最主要的应用就是o c r ( o p t i c a l c h a m c t e rr e c o g n i t i o n ) 。o c r 实际上是把含有印刷体字符或手写体字符( 数字、字 母、汉字等) 的文档图像识别并转换为计算机可以理解的代码( 如a s c i i 码) 的过 程。o c r 涉及模式识别、图像处理、数字信号处理、人工智能、模糊数学、信 息论等学科，是一门综合性的研究课题。人们对o c r 的研究从2 0 世纪5 0 年代 就丌始了，它是模式识别领域中最早开始被人们研究的领域之一【2 】【3 】，但早期这 方面的研究受到了当时计算机计算及存储能力的限制。从2 0 世纪8 0 年代初开始， 随着信息技术的迅猛发展，人们也逐渐显示出对0 c r 越来越浓厚的研究兴趣， 这不仅是因为该领域充满了无数令人兴奋的挑战，也是因为实用o c r 系统研究 的成果能给社会带来巨大的经济效益。经过多年的研究和发展，字符识别技术有 了长足的进步，不断涌现出大量的成果。 如果按文字的书写方式不同，字符识别技术可分为印刷体字符识别和手写体 第一章绪论 字符识别两大类，而后者又可根据字符数据产生的方式不同分为联机( o n 1 i n e ) 和脱机( o 仟1 i n e ) 两种。印刷体字符由于其书写规范、规格统一的特点，其识别 技术已经趋于成熟和完善，市场上推出的识别产品也f i 臻成熟，识别效果已经较 好，即使对印刷质量较差的文档图像也能达到较高的识别率。特别足我国的汉字 o c r 系统的研究，克服了起步晚、汉字字符集异常庞大等困难，取得了较显著 的成绩，市场上较为著名的有清华文通的t h o c r 系统和汉王的尚书o c r 系统。 对于联机手写字符识别，数据是通过书写者使用一支特殊的笔在一块电子平板 ：- 书写获得的，即字符的识别与人的书写必须同时进行。联机字符识别的研究也比 较成熟，国内外已经有多家公司从事联机手写字符识剐的产品丌发，市场上常见 的“手写板”就是这样的产品。联机字符识别主要应用于信息产品( 个人电脑、 手机、p d a 等) 的电子笔输入，以及数字签名验证、笔迹鉴定等信息安全领域。 对于脱机字符识别，数据则是通过对写好或打印出来的文档扫描成图像获得的。 脱机情况下的字符识别比联机的情况要复杂的多，市场上的一些产品识别效果都 不太理想，对书写的规范性要求较高。脱机识别主要应用于银行票据处理、邮政 信件自动分拣、商业表格识别等领域。 目前脱机字符识别的研究虽然取得很大的进展，但其技术还不太成熟，相对 于实用的要求仍处于滞后状态。这主要是由于手写文档有以下两个特点：1 丢 失了字符笔划书写顺序、速度等重要信息，且同一字符的写法千差万别，字符形 态的随意性很大，识别过程存在大量的不确定性，从而导致字符特征信息较难选 取，分类器的设计也较难实现。2 因书写习惯、用笔颜色深浅、力度变化以及 扫描效果的不同而产生的手写体连笔、笔画断裂、噪声污染等原因使得字符图像 不利于直接进行分类和识别，对于含有表格等较复杂格式的手写文档而言，字符 信息的准确定位和完整提取也存在一定的难度。从目前流行的研究方法来看，针 对脱机手写字符的第一个特点，人们主要从特征提取、分类器设计等方面着手研 究；而对于第二个特点，人们则主要从文档图像预处理和文档字符提取两方面进 行研究，即考虑文档图像去噪、二值化、字符信息提取与修复等问题。对于这两 方面的问题，目前人们对前者进行了大量深入的研究，而对于后者则探讨较少。 现有的一些关于文档图像预处理及字符提取的方法在理论上也不太完善，缺乏系 统的阐述和算法推导，效果也不太理想。 第一章绪论 本文准备就第二方面的问题展开深入研究，并把研究对象定为含手写数字的 表格文档，即本文主要研究表格识别预处理及表格字符提取的问题。另外，本文 在已有研究成果的基础上，结合字符分割、特征提取、神经元网络等技术研制了 一套用于高校学生考试成绩管理的成绩单自动识别系统。该系统也可以推广应用 于任何类似的商业、财务、办公表格的自动识别，文中的一些方法也可以应用到 更广o c r 领域中去。 1 2 表格识别的研究现状及存在问题 表格识别是字符识别技术最重要的应用领域之一。人们在日常工作、学习和 生活中经常需要填写各种各样的表格：财务报表、商业数据统计表、税务统计表、 学生成绩表等等，而这些表格中的大量信息常常需要输入到计算机进行整理、归 类、排序和分析等更高一级的应用。因此，人们迫切需要一种表格自动识别系统 来替代繁重的人工输入操作。一套高准确率、高效率和健壮的表格识别系统能够 大大加快信息输入的速度、提高工作效率，从而产生巨大的经济效益。目前人们 对带有一定格式文档的自动识别系统的研究较多的是邮政编码自动识别【9 j 【1 0 】、金 融票据识别【5 1 、车牌识别吲【7 ) 嘲等应用领域，而关于较复杂的表格识别的研究 也有一些”1 【1 3 】【1 4 】，但成型的实用系统较少，理论也不够完善。 一个典型的表格识别系统由三部分组成：预处理模块、字符提取模块，以及 o c r 识别模块。表格识别的一般流程如图1 1 所示：表格文档首先经扫描仪扫描 成图像；然后，预处理模块对表格图像进行自动倾斜校正和二值化处理；字符提 取模块进一步对表格的单元格内字符进行定位和提取；最后，o c r 模块对字符 进行分割、特征提取和模式分类。这三个部分都是表格识别系统中不可缺少的组 成部分。从图1 1 中我们也可以看出o c r 识别模块的性能依赖于前两个模块的 结果，良好的预处理和字符提取过程能为后续的特征提取及特征分类提供尽可能 完整、可靠、无噪声干扰的字符信息，是提高整体识别率的关键之一。 表格文档爿：二五三二二i 叫：二圣三三二譬 三三三三二l 刁 图1 1 表格识别的一般步骤 第一章绪论 在表格文档扫描成图像的过程中，表格在图像中或多或少会出现一定角度的 倾斜。这个问题会直接给表格单元格定位、字符分割等造成困难，甚至会影响系 统最终的谚 别率，因为大部分o c r 方法对字符的倾斜变形较敏感。关于文档图 像倾斜角自动检测的问题，现有方法主要可归结为5 类：h o u 曲变换方法、侧面 水平投影方法、傅立叶变换方法、k 一近邻聚类方法，以及直线拟合方法。其巾， 前4 种方法都比较耗时，而且除h o u 曲变换方法外，其他方法都无法保证对含 手写数字的表格文档图像取得较好的精度。 倾斜校正之后，为了进一步提取出表格图像前景中的表格线和字符，我们还 必须对图像进行二值化处理，这个过程实际上也能帮助简化后续的特征提取，因 为一般而言，二值化图像中字符特征的维数比在灰度图像中直接提取的情况要少 的多。现有的图像二值化方法分为6 类：基于直方图形状分析的方法、基于聚类 的方法、基于熵的方法、基于前景对象属性的方法、基于空间信息的方法，以及 局部自适应闽值选取方法。但这些方法都比较单一，在实际应用中往往无法较好 的适应各种不同条件下的情况( 如扫描结果亮度不均匀、笔划灰度较浅、图像直 方图灰度值分布较均匀等) 。 表格字符准确定位与提取是表格识别最困难也是最关键的环节之一。表格字 符定位的方法主要有两种：一种是利用先验知识，而另一种则是通过表格线检测 来定位。前者一般先检测表格矩形边框的四个顶点在图像中的坐标，然后再利用 单元格宽度和高度的先验知识求出每个单元格在图像中具体的位置 1 2 】，或者直 接把表格图像和标准的空白表格进行模板匹配。这种方法需要借助先验知识，因 而无法自动适应各种不同格式的表格。后者依表格线检测方法不同又可分为侧向 投影法1 6 【”】、轮廓提取法【1 b 】、表格线交叉点分析法【1 9 | 、h o u g h 变换法【驯等几种。 侧向投影法简单、速度快，但较容易受到表格倾斜和字符粘连表格线的影响；轮 廓提取法也很容易因表格线断裂或字符粘连表格线而产生错误；表格线交叉点分 析法则通过对相邻交叉点进行分类和匹配来迭代地构建出表格中的所有单元格， 但该方法比较耗时，且容易受断裂表格线的影响；h o u g h 变换是一种效果较好的 方法，能有效检测出断裂表格线、虚线等不同类型的表格线。 定位好字符所在的单元格以后，我们还需要把单元格里面的字符提取出来。 对于字符与单元格边框线不重叠的情况，只需简单的把边框线去除就能达到目 4 第一章绪论 的。而字符与边框线重叠的情况就要复杂的多，如图1 2 所示，重叠在边框线上 的字符在边框线去除后都出现了不同程度的笔划断裂或缺失，这样将大大影响 o c r 模块对这些字符的识别效果。人们在完整提取表格字符这方面也做了相当 多的研究。其中的一些研究把重点放在了如何改进识别算法上面【2 j 】。而更多的 则是研究如何去除边框线，这方面又再细分出两类不同的方法：一类是只去除属 于边框线的象素，而保留与边框线重叠的属于字符笔划部分的象素。由于一般的 表格文档经扫描成灰度图像后，字符笔划与表格边框线的灰度值比较接近，通常 很难直接区分边框线上的象素是否属于某个重叠在该边框线上的字符。一些方法 则通过检测字符与边框线的交点，然后把属于一个字符的相邻两交点中问的象素 保留下来【1 5 】，但这样从边框线中恢复出来的字符笔划往往恢复的不够充分，表 现为字符笔划出现残留的边角，轮廓不够平滑。另一类方法则考虑先去除所有的 边框线，然后根据重叠区域的局部性质( 如笔划方向、连接点等) 来恢复断裂、丢 失的笔划瞄】。但该类方法对含有圈型结构的字符重叠边框线的情况( 如图1 2 中 间的“o ”1 则无法有效恢复。 固圜固 图1 2 字符重叠单元格边框线的情形 1 3 本文的研究内容及组织结构 本文的第一章描述了o c r 及脱机表格识别的相关概念及背景，并对本文主 要关注的相关问题的主流研究方法进行了全面的概述。 第二章通过对现有的单一图像二值化方法的研究，在现有方法的基础上给出 了一种基于非线性对比度增强及l o g 算予的混合二值化方法，有效克服了使用单 一方法进行二值化的缺点。 第三章主要分析了现有的倾斜角检测方法，并在传统h o u 曲变换方法的基 础上构造出一种带参数约束条件的h o u g l l 变换方法，另外还给出了一种实现图 第一章绪论 像旋转的快速方法。 第四章着重介绍了我们提出的一种全新的基于c o i ( c e l lo fi n t e r e s t l 提取及 断裂笔划局部分类恢复的表格字符定位与提取方法。 第五章结合我们研制的成绩单自动识别系统介绍了脱机数字识别的字符 分割、特征提取、分类器设计等问题，并介绍了成绩单自动识别系统的系统 流程、相关实验及结果。 第= 章表格图像= 值化 第二章表格图像二值化 2 1 概述 在各种文档分析及自动识别系统中，人们在对扫描后的文档图像进行进一步 的分析和识别之前通常会对其进行二值化处理，即把图像中的每个象素点按照某 种规则标记为前景点( 通常为黑色) 或背景点( 通常为白色) ，以使得前景字符与背 景分割开来。二值化过程将直接影响提取出来的前景字符图像质量的好坏，从而 影响整个自动识别系统后续环节的性能。但现实中一些不利的因素常常会导致图 像二值化的效果变差，例如手写输入工具不好、文档背景图案干扰以及扫描亮度 不均匀等等。因此，如何从各种文档图像的背景中用二值化方法提取出人们感兴 趣的待识别字符就成了一个非常有挑战的问题。本章将要探讨的正是表格文档图 像的二值化问题。 人们对图像二值化分割问题做了非常广泛而深入的研究，提出了许多不同的 方法【2 4 ”。同时，人们也对这些方法在不同条件和应用背景下进行了有意义的 比较和总结【”】 4 1 】，尤其值得关注的是，最近m s e z 西n 和b s a n k u r 对近期比 较经典、流行以及最新的4 0 种二值化图像分割算法进行了广泛而细致的综述和 对比f 4 2 j 。在他们的文章中，图像二值化方法被分为6 类：1 _ 基于直方图形状分 析的方法，主要通过对直方图的波峰、波谷以及平滑后的直方图的曲率进行分析； 2 基于聚类的方法，不同灰度值的图像象素按照聚类的方法被分为前景和背景两 类；3 基于熵的方法；4 基于前景对象属性的方法，主要通过模糊形状相似性和 边缘重合度等手段来衡量灰度图像和二值化图像的相似度；5 基于空间信息的方 法，主要通过图像灰度概率分布和象素间的互相关性( c o r r e l a t i o n ) 来进行研究； 6 局部自适应阈值选取方法，该类方法主要根据图像的局部性质来决定每个象素 的阈值。m s e z g i n 和b s 柚k u r 的文章还对这6 类共4 j 0 种方法针对文档图像进 行了比较实验，实验结果表明二值化效果最好的前8 种方法几乎全部属于聚类方 法【2 4 j 【”j 【”卿j 【3 2 1 和局部自适应闽值选取方法1 3 3 】一【3 8 1 ，这与t r i e r 和j a i n 的文章中的 结果【4 1 1 是一致的。因此，我们将对这两类方法给予更多的关注。 7 第一章表格图像二值化 n u m b e ro fd i x e l s w i t hi n l e n s 仆yx 0 f o r e g r o u n d b a c k g m u n d f o r e g r o u n d b a c k g r o u n d p i x e i j m e n s i t y 图2 1 理想情况f 的灰度直方图 ( a ) 经扫描后的灰度图像 ( b ) 图像( a ) 的直方图 图22 扫辅后的文档图像髓百方图 事实上，我们通过研究发现聚类方法和局部自适应闽值选取方法弗不是在所 有情况下都能对文档图像取得好的二值化结果。我们知道，聚类方法能在最大化 类间变差【2 7 1 f 2 8 1 或最小化类内变差【”1 【州的意义下获得最优的阈值。但这类方法实 第一二章表格图像二值化 际上是对图像所有象素都采用同一个闽值，因此只适合亮度处处均匀并且图像直 方图具有较明显双峰的理想情况，如图2 1 所示。但现实中的文档图像由于亮度 不均匀或者噪声干扰，其直方图一般分布较均匀或不存在明显双峰，如图2 2 所 示，在这种情况下该类方法往往会失效。而局部阈值选取方法能够较有效的解决 图像亮度不均匀的情况，但却存在窗口大小设定的问题 4 5 】，即过小的窗口容易 导致字符笔划断裂，过大的窗口又容易使字符失去应有的笔划细节。因此，一种 比较合理的设想是把这两类方法结合起来。我们通过研究发现图像直方图的双峰 特性可以通过对比度拉伸的手段来增强，并且可以通过利用图像局部灰度变化求 出字符笔划边缘的手段来代替受窗口大小问题限制的局部阈值选取法。在以上分 析的基础上，我们提出了一种基于非线性对比度增强及l o g 算予的混合二值化方 法( n o n - i i n e a rc o n t r a s te n h a n c j n ga n dl o g0 p e r a t o rb a s e dh y b r i db i n a r i z a t i o n ， 以 下简称为h y b r i d 方法) ，即先对图像进行非线性对比度增强，然后用l o g ( 高斯型 拉普拉斯) 算子定位出字符边缘及字符内部象素，最后用r i d l e r 和c a l v a r d 的迭 代阈值选取方法( 以下简称为r c 方法) 求出阈值，从而最后得到二值化的图像。 h y b r i d 方法结合了图像的局部字符边缘信息和灰度直方图整体分布信息，有效克 服了使用单一方法进行二值化的缺点，获得了较好的效果。 本章的讨论将按如下安排进行：2 2 节将分别介绍三种有代表性的二值化方 法：r j d i e r 和c a l v a r d 的聚类方法f ”、s a u v o l a 和p i e t a k s j n c n 的局部自适应阈值 选取方法【3 8 1 以及h w a n g 和f u 的基于多尺度c a n n y 边缘的二值化方法【4 3 l ；2 3 节将介绍我们提出的h y b r j d 方法；2 4 节中我们将给出实验结果并与2 2 节中的 几种方法进行比较，从而说明h y b r i d 方法的有效性；2 5 节为本章小结。 2 2 三种二值化方法的介绍 2 2 。jr i dj e r 和c aj v a r d 的聚类方法( r c 方法) r c 方法实际上是个迭代闽值选取过程：在第n 次迭代中，新阈值l 通过 计算前景和背景两类象素各自的灰度值均值来求出，当阢一l + ，i 充分小的时候算 法结束。在具体实现的时候，r c 方法的过程可用如下算法来描述； 第二章表格图像二值化 算法2 1r c 迭代阈值选取算法 ( 1 ) 初始化，令n = o ，瓦，虽堕。其中，g 一和g 。；。分别为图像所有象素 点中的最大和最小灰度值。 ( 2 ) 令l 圹型掣， ( 2 1 ) 其中，m ，( l ) 和川。( l ) 分别为第n 次迭代后前景和背景象素的灰度值均值。 ，仃、驴页引。饔v ( 占) 脚，旺) = 号一， 哦) = 型等一， 薹烈引。密憎) l 为第n 次迭代后得到的阈值。 g 为象素点的灰度值( 取值范围为从0 到g ) ， p ( g ) 为图像直方图中灰度值g 对应的象素点数。 ( 3 ) 重复( 2 ) ，直到l + ，= l 。 由于( 2 1 ) 式右边可能为非整数，每次迭代后我们把右边的结果四舍五入为 整数处理( 事实上灰度图像的阈值只能为整数) ，当迭代结果满足瓦+ 。；l 时，我 们认为算法达到收敛。 2 2 2s a u v o i a 和p e t 8 k s i n e n 的局部自适应阈值选取方法 s a u v o l a 的方法是局部自适应阈值选取算法中最著名、被引用最多的算法之 一。s a u v o l a 的方法实际上是在n i b l a c k 方法【3 7 j 的基础上改进而来的。 n j b l a c k 方法为图像中的每个象素设定一个b x b 的窗口，窗口中心的象素点 的闽值取为r = 肌+ b ，其中，m 和s 分别为窗口中所有象素的灰度值均值和变 差，k 是一个常数。k 值主要是用来决定字符边界应取多少来作为字符的一部分 的。在t r i e r 【4 1 1 的文章中，参数取b = 1 5 ，k = 一o 2 的情况下获得了较满意的实验 结果。但是，该方法无法有效的抑制背景中的噪声，尤其当前景字符排列较稀疏 第一章表格图像二值化 时，背景中的许多噪声点都留在了二值化后的图像中。 s a u v 0 1 a 针对此问题对n i b l a c k 的方法进行了改进，采用了标准差的概念， 并增加了一个关于前景字符和背景象素的灰度值的假设，即前景字符象素的灰度 值分布在o 附近，而背景象素的灰度值分布在2 5 5 附近。在s a u v o l a 的方法叶1 ， 每个窗口中心象素的闽值为丁2 m + 1 + 七【贵一1 ，其中，r 为标准差的动态范 围，固定取为1 2 8 ，k = o 5 。相对于n j b l a c k 的方法，该方法针对文档图像能取得 更好的二值化效果，尤其在文档图像含有污渍或者亮度不均匀的情况下。 2 2 3h w a n g 和f u 的基于多尺度c a n n y 边缘的二值化方法 h w a n g 方法的主要思想是：采用不同尺度的二进小波对图像进行小波变换， 然后通过简单的阈值选取方法沿梯度方向找出小波变换局部模极大的象素点，并 定义该点为该尺度下的c a n n y 【“1 边缘点，从而获得不同二进尺度下图像的边缘 图像。然后，h w a n g 利用一个称为多尺度投票的机制找出字符的内部点，从而 对边缘所围着的字符内部进行了填充。投票填充完成后，字符之间因边缘断裂导 致互相误投票而产生了错误的细线，字符笔划也因小波变换过程对图像进行了平 滑而变粗，因此，h w a i l g 最后提出了一个基于b a y e s 测试的算法来进行补救。 22 3 1 多尺度c a n n y 边缘提取 先简单介绍二进小波变换。称任何双重积分非零的二维函数为二维光滑函 数，则小波函数分别为二维光滑函数一( x ，y ) 沿x 方向和y 方向的偏导数： 妒t ，) ，) ：掣掣，以及妒z o ，y ) ；翌业 o x o y 又记妒j “y ) = ( 扣1 亏，寺) 及1 ；f ； ，y ) = ( 扣2 ( 砉，寺) 。 则对于任意，r 僻2 ) ，在2 尺度下的二进小波变换对应地有两个分量： 形1 ，( 2 ，z ，y ) ；，十妒：，o ，y ) 和2 ，( 2 7 ，x ，y ) = ， 妒弓 ，y ) 其中+ 为卷积符号。于是，我们有 第= 章表格躅像= 僵化 f 1 ，( 2 7 ，”) 1 一， i 渺2 ，( 2 ，训) 厂 善( ，。b ，) ，_ ) ，) 批 。 三( ，* 见，) o ，y ) d v = 2 v ( ，* 乱，) ，y ) 从而，在2 尺度下的二进小波变换与被口，0 ，y ) 磨光的，( 石，_ ) ，) 的梯度向量 成正比。记该向量的模为 矿( 2 ，z ，y ) ，偏角为( 2 7 ，x ，) ，) ，则 蟛( 2 y ) = 陟1 ，( 2 y ) 1 2 + 陟2 ，( 2 ，w ) 1 2 ， 邪 加t a n 。( 黜 o 根据c a i l n y 的定义，在2 尺度f ，边缘点0 ，y ) 定义为沿偏角( 2 ，x ，y ) 的 梯度方向进行搜索，梯度向量模j 】l 妒( 2 ，z ，y ) 在局部取为极大的点。根据该定义， 可以求出图像中前景字符的边缘，而且在小尺度下求出的边缘比在大尺度下的更 加精细，因为小波在小尺度下的紧支集比在大尺度的更小。 求得的小波模极大图像中通常包含了许多噪声点的极大模，至今为i e 还不存 在一种解析的方法能对这两种模进行区分。但从m a l l a t 和h w a n g 4 7 】对奇异性的 分析中可知，字符笔划的边缘和噪声的边缘一般而言有着不同的奇异性，因此还 是可以根据极大模的大小来进行区分。一种可行的方法是在不同的尺度下根据经 验选取不同的阈值进行区分。 22 3 2 多尺度投票填充 假设前景字符象素具有较暗的灰度值，反之，背景象素具有较亮的灰度值。 该假设将被用来判断某点是否属于字符内部。如图2 3 ( a ) 所示，在8 一邻域意义 f 的每个点都有四条直线经过，分别对应0 。、4 5 。、9 0 。和1 3 5 。四个方向及其反 向延长方向。从字符内部每个点出发沿这四个方向及其相反方向进行扫描，则扫 描线与字符边缘在理想情况下( 字符边缘封闭且没有断裂) 将至少相交两次，并且 每条扫描线与字符边缘第一次相交时扫描线的走向一定是从较暗的部分到较亮 的部分，如图2 3 ( b ) 所示。 1 2 第二章表格图像二值化 【j ) 一 一 4。 。7 c 匕! dlb a a b 霉 d f ， ，j ，jl 。、 c ( a ) 每个点有四个方向的直线经过( b ) 每对扫描线与字符边缘至少相交2 次，图中 ( a - a ) ，( b _ b ) ，( c c ) ，( d - d ) 分别为4 对扫描线与边 剀2 3 判断字符内部点 缘的交点，扫描线走向从较暗部分到较亮部分 在上述假设的基础上，投票机制可以建立起来：经过一个点的每一对扫描线 一旦确认该点在字符内部，则为该点投一票。理想情况下每个字符内部点将有4 票，但现实中由于边缘常发生断裂或者受到噪声的干扰，每个内部点的票数常常 小于4 票。于是，票数较高的点通常被认为是字符内部点。该机制是合理的，因 为字符内部点获得高票数的几率较大，反之，字符外部点获得高票数的几率较小。 进一步，多尺度投票机制被建立起来：对每个点在所有尺度下获得的票数累 加起来，累计票数超过某一预设阈值的点则认为是字符内部点，并用黑色填充该 象素。于是，字符内部就可以恢复出来了。 2 2 33 基于b a y e s 测试的字符位置估计 求出边缘和投票填充以后，字符之间因边缘断裂导致互相误投票而产生了错 误的细线，字符笔划也因小波变换过程对图像进行了平滑而变粗，如图2 4 所示。 ( a ) 原图 图2 4 字符求边缘和填充后的情况 ( b ) 求边缘和投票填充后字符变 粗，并且字符之间产生错误细线 第二章表格图像二：值化 b a y e s 测试被用来解决以上问题。图像中的一个点可以有两种决策：假设日。 表示该点为背景点，h ，表示该点为前景点。则对于每个点可能有4 种结果：1 日。 为真，h 。决策被选择；2 圩。为真，h ，决策被选择；3 h 。为真，h 。决策被选 择；4 h 。为真，h 。决策被选择。第l 、4 种情况对应正确的决策，中间两种情 况对应错误的决策。设h 。、圩。发生的先验概率分别为昂、最。4 种结果的损失 函数分别为c 。、c 0 1 、c 。、c n ，其中第一个下标表示哪一个假设为真，第二个 下标表示哪一个决策被选择。于是决策的整体期望风险r 为： r 皇r c 0 0 p ( h o c d s 跚ih o 打h e ) + 只c 0 1 p ( h 1 c 删lh o 驴“。) + e c l o p ( 口。幽删1 日1 护h e ) + 最c 1 1 p ( 日1 如d s 已州h l 打“e ) 根据最小风险b a y e s 决策法则，一个象素属于前景点还是背景点最终可以通 过先验概率只、损失函数c 口以及条件概率密度函数p 哪i 曲i h ，f r “8 ) 计算获 得( 其中，f ， o ，1 ) 。但实际应用中通常无法直接知道先验概率和损失函数的值， 因此一般用似然比闽值r 来表示这些值【5 0 1 ，似然比阈值r 为r = 詈疾器，其 中p 僻i h 。) 和p 僻l h 。) 分别为特征量观察r 的概率密度函数。由于自然对数函 数单调，因此常用对数形式来表示似然比阈值：l n r = l p 僻l h ，) 一1 n p 僻i 。) 。 l n p 僻i h ，) 和l n p 俾l h 。) 的值可通过合理的近似获得：记甙p ) 为象素p 的灰 度值，给定p 的一个邻域，记m c 为p 点邻域中字符内部点的灰度中值，记m b 为p 点邻域中字符外部点的灰度中值。则9 0 ) 与m c 之间的差值可作为l n p 僻i h ，) 的近似，同理，9 0 ) 与m b 之间的差值可作为l n p 职1 日。) 的近似。于是，对数似 然比阈值可按下式近似计算获得( 其中k 为正的常数) ： l n r = l n p ( 尺i h 。) 一l n p ( 尺i h 。) 一t ( 旧( p ) 一m c i i g ( p ) 一胁6 i ) 最后，可根据l n r 的值对某象素是否属于字符内部作出判断：若对数似然比 闽值l n r 大于0 ，则认为对于该象素日，假设为真，否则认为h 。假设为真。 1 4 第= 章表格图像= 值化 2 3 基于非线性对比度增强及l o g 算子的混合二值化方法 针对现有的单一化方法存在的缺点，我们提出了一 种基于非线性对比度增强及l o g 算子的混合二值化方 法，以下简称为h y b r i d 方法。h y b r j d 方法的主要思想是： 通过非线性对比度拉伸改善图像前景、背景象素在直方 图中的分布，尽量使直方图出现双峰或近似双峰的特性， 从而突出前景字符；然后用高斯型拉普拉斯算子模板对 图像中的字符边缘进行定位，并利用i j o g 算子可以判定 给定象素点是在边缘较亮的一边还是较暗的一边的特 性，找出字符的内部象素。最后，我们通过r c 迭代闽 值选取对图像进行二值化处理。h y b r i d 二值化方法的流 程图如图2 5 所示。下面几节将详细介绍每个步骤， 我们首先从线性对比度增强谈起。 灰度图像 非线性对比度增强j _ 嚣篡鬣霎j 边缘及其内部象素_ 厂一 。r c 迭代闽值选取i 二值化图像 图2 5h y b r i d 二值化方法 2 3 1 线性对比度增强 我们约定前景象素比背景象素的灰度值更小便暗) ，并记a v e 为图像的平均 灰度值，。、乃。分别为图像前景象素的最大、最小灰度值，瓦。、瓦。分 别为图像背景象素的最大、虽小灰度值。在理想情况下，我们有以下关系式： kc kc 爿陋t kc k 。 ( 2 2 ) 在该情况下，我们只需把a v e 作为闽值对图像进行二值化，便能完全区分 前景和背景象素。但现实中的情况往往比( 2 2 ) 式复杂。文档图像往往由于亮度 不均匀，而且图像中背景象素往往比前景象素多的多，因此实际中下式往往成立： 丁删抽 陆 瓦柏 爿陋 丁矗协a( 2 3 ) 例如，一幅图像的前景象素的最小和最大灰度值分别为o 和5 0 ，背景象素 的最小和最大灰度值分别为1 9 0 和2 5 4 ，前景象素和背景象素的总数分别为5 0 0 和l o o o o ，则图像的平均灰度值可近似的计算出来： 爿陋；! ! 竺! 坐型避! 型! 趔! ! 塑虬2 2 。 5 ( ) o + 1 0 ( ) o o 显然，该结果满足( 2 3 ) 式：0 5 0 1 9 0 2 1 2 6 2 1 时，灰度值映射的权重偏向较高 ( 较亮) 的灰度值；当r 1 不变。 图2 6 灰度值非线性拉伸与线性拉伸的区别 图2 7p 取不同值时对应的非线性灰度值映射曲线 非线性灰度值拉伸可按下面的非线性灰度值映射函数进行： 1 7 第：章表格图像二值化 ，a ，) = 2 5 5 ； f ，( ，o ，) 爿陋) 2 5 5 一f 鲤盟兰盟| ；矿s ，小爿陋) r 其中一型黑型，p o 。 ( 2 5 ) ( 2 5 ) 式中( f ，) 、，( f ，) 分别为原图像和对比度拉伸后的图像，m i n 、a v e 分别为原图像的最小灰度值和平均灰度值，p 为指数。 显然，当p = 1 时，( 2 5 ) 式就是( 2 4 ) 式。即我们可以认为，线性灰度值映射 是非线性灰度值映射的一个特例。图2 7 显示了p 在不同取值下对应的非线性映 射曲线。从图中可以看出当p = 1 时，映射曲线恒位于y = x 的上方，拉伸率恒保 持r ) 1 ，显然我们不应采用这类曲线，因此p 的取值可进一步限制为o cpc 1 。 但p 具体取何值才能满足我们的需要呢? 根据前面的分析，指数p 应满足：非线 性映射曲线与恒等映射曲线y = x 相交时工= 瓦。但瓦。的值是无法知道的，因 为瓦。依赖于最终阈值选取的结果，然而闽值选取的过程( 非线性映射) 又依赖于 瓦。的值。因此，p 值