（计算机软件与理论专业论文）多区域图像的分割和倾斜检测方法研究.pdf

山j 甑师范大学坝l j 学位论义 摘要 在现代信息社会里，计算机已经进入了社会的各个领域，互联网也臼益普及，人 翻越来越多遮依赖计算枫获褥吾秣信息，大量煎处理工俸也都转移到计算褫上进行。 研究如何将传统的纸张文本转换成电子文本就成为了人们关注的课题。在日常生活和 工作中，存在着大量的文件资料的处理闻题，这些文件不仅包括那些只有文字信息的 文件还包括那些图文混排的文件和图像文件，因而如何将文件快速准确的输入计算机 的要求变得非常迫切。 本文主要研究的是多区域嚣像的分割和馈斜检测方法。钟对常用的文本图像分割 算法进行了综述，并对各个分割算法的优缺点进行了介绍。一般的文本图像的处理算 法大体可以分藏两类：耍何分褥法和纹理分析法。其中凡 莓分孝厅法又可获分为垒顼彝 下、自底向上、混合法。本文详细介绍了两种自顶向下的分割算法，分别是游程平滑 算法霸投影轮廓算法，以及两种自底囊上的处理方法：近邻线密度法靼连逶分量分折 法。除此之外，还列举了几种常觅的图像分割算法。 本文总结以上的基本分割方法，针对多区域图像提出了改进的投影轮廓算法。该 算法解决了使用般的投影轮廓算法不携遥震于复杂酶其有倾斜角度的多区域图像 的分割，本文首先对图像进行二值化，使用数学形态学的腐蚀一膨胀操作降低图像上 鲶噪声。对于得到豹霾像使用改进的投影轮薅算法，该算法鼗傻在x 、y 轴方彝上没 有谷点，也可以根据图像像素的分布状况找出切分点，将图像切成小块，再对小块图 像进行投影分析，循环此过程，直到将图像的各个区域分割出来为止。 文档倾斜角的检测大体可以麴为五大类，基于嚣。醢醢变换静方法、基于交叉相 关性的方法、基于投影的方法、基于f o 谢e r 变换的方法和敝最近邻簇法，其中基于 面嚣变换酶方法计算量非常大，故瑟很少使用。 通常文档图像在扫描入计算机时难免余有损失，文档图像的边缘也很不规则。如 果用普通豹边缘提取方法寻找图像轮廓，不仅增加了计算量而且增加了许多不必要的 计算。本文针对般倾斜检测算法计算量大的问题，提出了种简革的寻找边缘的方 法，这里并不需要精确地找出文档图像的边缘轮廓，只是找出含有图像的区域就可以 了，这个区域就是夕 、接矩形，帮b 棚n 莲珏gb o x 。本文萼l 入g a 方法检测鋈像的倾斜囊， 该方法使用b o u | ：1 d i n gb o x 的面积作为适应度函数值，只需要找出图像的上下左右四个 坐标值便可以了，这样大大减少了计算量。实验结果表弱该算法对倾斜角的检测具有 较高的糟确度。 关键词：多区域图像；图像分割；投影轮廓切分算法；图像倾斜检测；遗传算法；夕卜 接矩形 分类号：t p 7 5 1 、 a b s t r a c t h 1m em o d e mm f o m a t i o ns o c i e 坝c o m p u t e rt e c h n 0 1 0 9 yh a sb e e i li n v 0 1 v e di nv a r i o l l s 蠡e l 蠡o fo 醒l i v e s 翻王e 至嗽e 豫e th 鑫s 蔹s 。b e c 激ep o p 毽l 瑟i e c r e 猫诬誉xa 薹通w ed 印e 越陇 c o m p u t e r st og e ti n f o m l 撕o nm o r et h 舭e v e rb e f o r e ，al o to fw o r k i ss l l i r e do nt 0c o m p u t c l s 抛蛳n g 幻w 稔c o v 鳅激e 投越i 蠢。越p a p 嚣i 哟e l e c 撤畦e 渤囊a sb e e 懈ea 卸i cq f c o n c e m md a i l yl i f e ，m e r ea r eal 科g en 帆b c ro fd o c u i n e n t st ob eh a i l d l e d a l lo ft h e s e 拍e 啪饿t si 1 1 c l u d e 黝to n l yt e x t 基l e sb 越采s oi 粼喀e s 褫d 商x 甜m e s ，s o 抽w 幻p 砒t h 毛髓 i n t oc o h l p u t e re 蕊c i e n t l ya l l da c c l l f a t e l yh a sb e c o m eu 瑁tr e q u i r e m e n t s t h em a 洫p u 坤o s eo ft l l i st j l e s i si st os t u d ya l g o r i t h m sf o rp a g es e 班酬撕o na n d s k e w d e 专e c 专主强o fm u l t i 。f e 酉强d o e 啦嘲i m a g 髂， 髓em e s i ss 髓魏雒z e s 羹l ec 溅强。纛 a l g o r i m 触so fp a g es e g m c n t a t i o n ，a 1 1 d 百v e st h e i ra d v a n t a g e s 搬dd i s a d v a n t a g e so fe a c h 舔g o 蠲巍。g 镪e 蹦l x 毽鼬。d so f p a g es e g m 啾蕊。建c 觚ee l a s s i 爨e d 礁。懈。姊e s ，强e l s 鼬m c t i l r a la i l a l v s i s ，a n dt t l eo m e ri st e x t i l r e 姐a l y s i s - t h es t n l c t u r a la n a l y s i si n c l u d e s 勺如w 致，_ b o 鼢戳蹿锺da 辙蕊珏go f 稿建t w r o t k 也e s i sp f e s 铋t s 溉ot 蹲。棚也o d s ， 一l e r i g ms m o o m i l l g 弧dp r o j e c t i o np r o m ec u t ， a n d铆ob o t t o m 。u pm e 畦l o d s ， i g h b o r h o o dl i n cd e n s 埘撇dc 0 锄e c t e dc 叫攀o n 铋t 躐a l y s i s 融删t i o n ，i t 垂v e ss e v e r a l a l g o 棚强sw 量l 主c hu s u a l l yb eu s e di 醢i m a g es e 辨e n t 如o n a c c o r d i n gt on l e s ea l g o r i t h 【1 1 8 ，t h i sp a p e rp r e s 蹦t s 越i m p r o v e dm e m o do fm e p 蛹e e 重主。稳即蠡l ee 滋蠢g o 娃髓鞋弧i s 磷p 纛髓建s o l v e s 垃搀p 灿l e m 墩敷瞧撑p 蛹e c 毫i o 瑟 p r o f i l e c u ta l g o m h mc o u l d n td e a lw i t h m p l i c a t e dd o c u m e n t sc o n t a i l l i n g s k e w e d 皴珏l | i r e 承滋s f 娃i s l ，龇 赫a g ei sb i n 撕z e d ，垃娥如n o i s e db ye 鳓s i o n 强d 越l a 专i o no p 茛a 专i 潍 o fm a t h 啪a t i c a lm o 印h o l o g y a p p l ) ，i n gt h ei m p r o v e dp r o j e c t i o np r o f i l | ec u ta l g o d m mt o d o c u m e n ti m a g e s ，w ec a n 是n dn l cc u t - o 磊p o i n t so ft h ei m a g e 嘶嫩c hd o n th a v e 孤y p e a 王【v a l l e yp o i n to nt h ex 。a ) 【i sa n d 孓a x i s w i t 重lt h e s ec u t o gp o i n t sw ec o u l dc m 墩e i m a g ei n 上os m a np i e c e s ，撇dt h c nw ec o n d u c tt h es 糊e0 p e r a t i o nu n t l lm u l t l - r e 辨o n s a r e s e p a r 越o d 。 s k 刚ve s t i m a t 洫gm e t h o d sc a nb ec l a s s i f i e di n t o f i v eg e n e r a lc a t e g o r i e s ：h o u 曲 锹糙s 受溉，e 羚s s 。e o 嚣e l 越。藏，p 避；e e 磊np 筠蠡l e ，f o 砥封墩避s 凡f 黻托d 鬏e 教e s t 一珏e i 啦b o r ，o f w 1 1 i c hf o 试e rt r 嬲s f o mi sr a r e l yu s e db e c a u s eo fi t sh i 曲c o n l p l e x i t y - d u 赢g 豳e u 撒锄s c a 融i n g ，也ei m a g em a yl o s es o m e t h i n gi n 丽t a b l y ，a l l d 饿ee d g e s v 山东师范大学颁士学位论义 a f en o t 锄o 。t h i n g 董fw eu s e 伽en o 锄啦i m a g ee d g ed 敷e c t i o n 协f 过d 也e 弘。蠢l e ，i t i n c r e a s e sn o to n l ym ea m o u n to fc o m p u t a t i o nb u ta 1 8 0m a n yu i m e c e s s a r yc a l c u l a t i o n s 矾i e 也e s 主sp r o p o s e da 磁e f 搬e b d 协蠡鞋d 证ep 曩l eo f 也e 趣a g e ，至w 越e h 氇e 瓣主sn o 辩e d t of l n d | 【1 1 ee d g e sa c c u r a t e l y ，j u s tt o 丘n dt h ea r e aw h i c hc o n t a i n st h ei m a g e t h ea r e ab e i n g f o u l l di sc 蠢l e db o u n ( 1 进gb o x 。弧l et h e s i s 璐e dg _ a 艇g o r i 也m 稔d e t e 吱s 妇w 勰g l e so f 搬e i m a 葛e s t 1 1 i sm e t h o du s e st h ea r e ao f 蛳b o u n d i n gb o xa si t sf i t n e s s 如n c t i o n ，i n 喊c h o n l vm ec o o r d i n a t ev a l u e so ft l 瓣4c o m e r sn e e dt ob ef o u n d t b i sc a 聪r e d l l c et r e m e n d o u s c o 螂u t 证ge o 驳攀l c x i t y - e x p e r i m e n t a l s u l t 8 s 抽wt h a t 魂ep r 。p o s e da _ l g o r i 缅nc 觚 c e n a j n l yg u a r a n t e em ea c c u i a c yf o rd o c m n e n ti m a g ed e s k e w i n g 圣畸w o r 蠡：躺l l i r e 誊镰西c 嘲强妇鑫g e s ；幽e 啪e n ts e g 瞅馘撕潍；p 蛹e c t 主。觳p 瓣鑫l ee 憾； s k e wd e t e c t i o n ；g a ；b o u n d i n gb o x ； c l a s s i l l c a t i o n ：t p 7 5 】 v 1 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得( 注：如没有其他需要 特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：考孑 新签字： 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 邋可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权 书) 学位论文作者签名材 导师签字： 签字日期：2 0 0 p 年厂月夕日签字日期2 0 0 妊彤d 日 山东师范人学颂： ：学位论义 1 1 本章概述 第一章绪论 本章首先在1 2 节中介绍了纸张文档处理已经成为目前我们迫切要解决的问题， 丽o c r 系统是现在最常使用的文字识别和处理系统，在l 。3 介绍了一下o c r 系统的 发展和该系统的工作原理。由于o c r 的识别过程对图像的簧求比较高，相应的这就 对图像的预处理也就是本论文所研究的内容提出了较篙的要求，从丽引入了对多区域 图像的分割和倾斜检测处理的问题，1 4 节便详细介绍了这两方面的发展，并介绍了 其分类。1 5 节给| 出了本文的组织结构。 1 2 问题的提出 在现代的信息社会里，计算机已经进入了社会的各个领域，互联网也日益普及， 入们越来越多地依赖计算机获得各种信息，大量的处理工作也都转移到计算枧上进 行。研究如何将传统的纸张文本转换成电予文本就成为了人们关注的课题。在日常生 活和工作中，存在着大量的文件资料的处理闯题，这些文件不仅包括那些只有文字信 息的文件还包括那些图文混排的文件和图像文件，因而如何将文件快速准确的输入计 算机的要求变得非常迫切。 1 。3o c r 系统 o c r 是“光学字符识别 ( o p t i c a lc h a r a c t e r c o 鲥t i o n ) 的英文缩写。光学字符 识别作为模式识别学科中个相对古老的研究领域，在模式识别的历史中有重要的地 位n 吒1 。中文o c r 系统是针对汉字信息高速输入计算机的问题，致力于解决困扰汉字 使用者低速信息输入与高速信息处理的矛盾，从而提高整个计算机系统的效率。用户 只要用扫描仪将整个页面图像输入计算机，o c r 系统就会露动产生汉字文本文件， 比手工输入要快几十倍。o c r 系统主要的应用领域有：办公自动化中印刷体汉字、 英文、嚣文等文件资料的逸动输入：建立汉字文献档案库：语言处理中文书刊资料 的自动输入：汉字文档图像的压缩存储和传输：书刊自动阅读器，盲人阅读器： 书刊资料的再版输入，吉籍整理：智能全文信息管理系统，汉英翻译系统；名片识 别管理系统：表格、票据、发票识别系统：网络出版，无纸化办公等。 目前针对如健将信息快速有效地输入计算机这问题的解决主要是通过文字识 山东师范人学颂_ 卜学位论文 别技术来实现，即通过扫描仪将待处理的文字材料以图像的形式输入到计算机中，然 后在图像中分割出文字块，再从文字块中分割出单个字符的图像表示，最后启动识别 模块，将字符从图像表示转化为编码表示，从而完成文字自动输入的工作。这样的文 字处理技术称为光学字符识别技术，相应的系统称为o c r 系统。o c r 的步骤一般包 括以下几步： 1 用光学技术把纸上资料扫描进计算机，以图像格式保存 2 对图像进行版面分析，将文本区域单独提取出来 3 对得到的文本区域进行行字分割，得到每个单字或字符图像 4 对单字或字符图像进行识别 5 对识别结果进行编辑、排版，还原成原始的版面。 1 3 1o c r 的发展历史 o c r 研究是模式识别领域中开展较早的一支，其思想可以追溯到上世纪二十年 代。1 9 2 9 年t a u s h e c k 在德国获得了一项o c r 专利。他用一个光电探测器检测透过模 具的光，当遇到匹配的模板时，探测器便检测不到光，这种模板匹配的思想直到今天 仍然是o c r 技术的主导思想之一。经过几十年的发展和完善，并伴随着计算机技术 的飞速发展，现在o c r 技术已经广泛应用到各个领域，使大量的文档资料能快速、 方便、及时地自动输入到计算机中。到目前为止，o c r 系统的研究及其相应的技术 已臻于完善，特别是对印刷文字的o c r 技术已经相当成熟。 中文的o c r 技术最早可以追溯到6 0 年代。1 9 6 6 年m m 公司的c a s e y 和n a g y 发表了第一篇关于中文o c r 技术的论文，在这篇论文中他们利用简单的模板匹配法 识别了1 0 0 0 个印刷体汉字。2 0 世纪7 0 年代以来，日本学者作了许多工作，其中有 代表性的系统有1 9 7 7 年东芝综合研究所研制的科研识别2 0 0 0 汉字的单体印刷汉字系 统；8 0 年代初期，日本武藏野电器研究所研制的科研识别2 3 0 0 个多体汉字的印刷体 汉字识别系统，代表了当时汉字识别的最高水平。 我国对中文o c r 技术的研究始于7 0 年代末、8 0 年代初，大致可以分为三个阶 段： 第一阶段从7 0 年代末期到8 0 年代末期，主要是算法和方案的探索。 第二阶段9 0 年代初期，中文o c r 由实验室走向市场，初步实用。 第三阶段目前，主要是印刷汉字识别技术和系统性能的提高，包括汉英双语混 排识别率的提高和稳健性的增强。 同国外相比，我国的中文o c r 研究起步比较晚。但由于我国政府对汉字自动输 入的研究从8 0 年代开始给予了充分的重视和支持，经过科研人员2 0 多年的辛勤努力， 2 山东师范人学硕j ：学位论文 中文o c r 技术，尤其是在印剃体汉字识别方面，涌现出了汉王o c r 、清华文通等许 多优秀的o c r 产晶，标志着汉字o c r 技术已经发展到了实用化阶段。在用户需求 的驱动下，国内o c r 技术酶研究正囱两个方向拓展：一是脱机手写汉字技术的研究 及实用o c r 系统的集成，二是实用背景的专用o c r 系统的研制与开发。所谓专用 o c 袋系统是指系统所要处理的扫描文本是特定的，如税票、信封、车牌、名片等等。 专用o c r 系统的研究开发，将在很大程度上拓展o c r 技术的应用领域，提高相应 领域的自动化程度。同时，由于系统所要处理的对象是特定的，在系统的实现过程中 所遇到的一些新问题和所采用的新方法，对于o c r 技术的研究具有一定的理论价值。 王。3 。2o c r 系统工作流程 在了解了o c r 系统的发展历史之后，我们详细了解一下c r 的工作流程。o c r 系统是一种汉字文稿的自动输入方式。其工作原理是：通过扫描仪等光学输入设备获 取纸张上的文字图片信息，将文稿的图像输入给计算机，计算机取出每个字的图像并 利用各种模式识别算法分析文字形态特征，判断出文字的标准编码，将其转换成为汉 字的编码，最后按格式存储为计算机的文本文件格式。 下面以中文o c r 为例，介绍一下o c r 系统的工作流程。 如图1 1 ，为一个中文o c r 系统的简单流程图。 。r 纛戆蜜辩、 文三一 扫描输入图像 审 图像的预处瑷 r 舨瑟分橱理麟 文本行字切分 l 文字特援舞敬 审 | 文字识别处理 识剐结果编改 迫多 r 识别维莱、 。 图l 一1o c r 流程图 扫描输入图像：原始图像是透过光学仪器，如影像扫播仪、传真机或任何摄影器 材，将影像转入计算机而得到的。科技的进步，扫描仪等的输入装置已制作的越来越 山东师范大学硕1 j 学位论文 精致，轻薄短小、品质也高，对o c r 有相当大的帮助，扫描仪的分辨率使影像更清 晰、扫描速度更增进了o c r 处理的效率。 图像的预处理：这部分包括对原始图像的去噪、倾斜检测和各种滤波处理。 版面的分析理解：版面分析完成对于文本图像的总体分析，区分出文本段落及排 版顺序，图像、表格的区域；对于文本区域将进行识别处理，对于表格区域进行专用 的表格分析及识别处理，对于图像区域进行压缩或简单存储。 文字行切分：行字切分是将大幅的图像先切割为行，再从图像行中分离出单个字 符的过程。 文字特征提取：特征提取是整个环节中最重要的一环，它是从单个字符图像上提 取统计特征或结构特征的过程，包括为此而做的细化、归一化等步骤。提取的特征的 稳定性及有效性，直接决定了识别的性能。目前，特征提取的方法可以大致分为两类： 一类为统计的特征，如：文字区域的黑白点数比。当文字区域分成好几个区域时， 这一个个区域的黑白点数比之联合，就成了一个数值向量，在比对时，基本的数学 理论就足以应付了。另一类为结构特征，如：文字影像细线化后，取得字的笔划端点、 交叉点之数量及位置，或以笔划段为特征，配合特殊的比对方法进行比对。 文字识别处理：文字识别即将待识别字符与通过学习得到的特征库进行对比，找 到相似度最高的字符类作为结果的过程。根据特征提取的方法不同，比对的方法主要 有欧式空间的比对方法、松弛比对方法、动态规划比对法，以及类神经网络的数据库 建立及比对、洲( h i d d e l lm 破o vm o d e l ) 等著名的方法。为了使识别的结果更稳 定，也有专家系统被提出，利用各种特征比对方法的相异互补性，使识别出的结果可 信度特别的高。 识别结果编改：即后处理。是利用词义、词频、语法规则或语料库等语言先验知 识对识别结果进行校正的过程。 1 4 针对多区域图像的预处理 通过上一节，我们知道：图像的预处理在整个o c r 系统有着很重要的地位，它 对识别结果产生直接的影响。 然而对于多区域的图像，基本的o c r 预处理并不十分有效，这是由多区域图像 具有的特点所决定的。如信封，它的图像各个部分倾斜的方向可能是不同的，而且由 字符的字体繁多，因人而异，因此高性能的信封识别系统的实现有一定难度。如果跳 过预处理这一步，那么文档图像的版面分析理解和文字行的切分都会有很大的影响。 另外，由于倾斜产生的字符变形，也会对字符的特征提取产生影响，并最终影响系统 的识别率。由实验表明：当倾斜角度大于3 度时，字符将产生明显变形，绝大多数 4 山东师范人学颂匕学位论文 o c r 系统都无法适应。因此，本文主要给如了对于多区域图像的预处理方法，包括 对图像的分割和倾斜检测，并对其中的一些问题作了具体的应用基础研究。 多区域图像的研究从2 0 世纪8 0 年代就开始了。l a b e kf w 越褫dw s e h 蕊】， j t o y o d a ，y n o g u c ma i l dy n i s h i i l l u r a 吧i y w b n g ，r g c a s e ya n df m w 地1 【5 j 等人做了 最初的探索。由于多区域页面图像鲶复杂性，以前论文中提出的方法很多不同的处理 方法。和其他领域的处理技术不同，多区域图像的分割和倾斜检测算法之间没有一定 的继承关系，各种算法的着眼点不同，处理手段也就各不相同。 1 4 1 页面分割算法的发展情况及其分类 页面分割与区域分类是文本图像处理领域中的重要研究课题，该课题介于文本资 料预处理和高级页面识别之闻刀。文本匿像页蘧分割和分类技术的研究最早可追溯 到2 0 世纪8 0 年代0 1 。基于页面的复杂性，以前的文献【1 1 1 3 】中提出了许多不同的处 理方法。与其它领域的处理技术不阍，各种文本图像员面分割和分类算法之间没有一 定的继承性。由于各种算法的着眼点不同，处理手段的差别也很大：有的算法将分割 与分类过程分步完成；有的算法将分割与分类结合起来同时完成；还有的算法根据文 本图像中不同区域的几何特征进行分类；另外还有根据图像中个区域纹理特征的不同 进行分类。所有这些分割与分类方法各有优缺点，到目前为止，还没有种可以处理 各种页蔼版式豹通用算法。 文本图像的处理算法大体可以分成两类：几何分析法和纹理分析法。其中几何分 析法又可以分为留顶向下、自底氲上、混合法。 几何分析法主要利用了文档图像中各个不同区域的结构分布特征，例如文本、图 像一般以矩形的方式存在，各个结构单元呈层次关系，各个区域之间一般有明显的间 隔，如较大的空白或分割花纹等。在这类方法中，自顶向下的方法从版面的全局特征 开始，一个页面首先分割成几个大的区域，然后每个区域再递归分割成子区域。自底 向上的方法从像素点开始，将相邻的部分根据局部特征的相似性合并成戈一个小区 域，小区域再连续地合并为大区域。另外还有将两种方法结合起来的混合法，以及主 要依据背景特征进行分割的基于背景的方法等。这类方法的主要缺点是很大程度地依 赖于特殊的规则和经验性的阈值，对日益复杂的文本页面的适应性较差。 纹理分析法主要思路是将图像看作是一些具有不同纹理的区域的组合。文本具有 一系列相同方向的文本行，行中具有一系列大小基本一致的字符。这种相对一致的纹 理特性完全不同于图像，因此可以用来进行图像分割。这类算法近来得到了比较大的 发展。 这两种方法对应的常用算法，我们将在第二章作详细介绍。 山东师范大学硕十学位论文 1 4 2 页面倾斜检测算法的发展情况及其分类 图像的倾斜检测，特别是页面图像的倾斜检测的方法也是多种多样的。这些方法 有的是对原有方法的改进，有的则开辟了一些新的思路和方法，例如，基于g a b o r 小波变换的图像倾斜矫正算法、基于直线拟合的文本倾斜检测算法、基于主元分析的 车牌图像倾斜校正新方法、基于空白条方向拟合的复杂文本图像倾斜检测等。这些方 法可以归为五大类： 基于h o u 曲变换的方法 基于交叉相关性的方法 基于投影的方法 基于f o l l r i e r 变换的方法 k 最近邻簇法。 h o u 曲变换是最常用的检测倾斜角方法，由于基本h o u 咖算法计算量非常大， 因此一些专门用于倾斜角检测的h o u 曲变换改进算法被提出来【悼15 1 。虽然这些算法 的核心思想是减少h o u 曲变换的数据量，但由于h o u 曲变换本身计算量较大，因此 改进算法的速度仍然较慢。 交叉相关性算法是基于等距离的竖直( 水平) 平行线上像素点的相关性的方法。 文献 1 4 1 5 以平行线上的像素点建立相关矩阵，并对矩阵在竖直方向上作投影，投影 图的全局最大值对应于倾角。该方法虽然准确率高，但相关矩阵的计算量较大。基于 投影的方法利用投影的某些特征进行判断，如均方差、第一特征矢量以及梯度等统计 特性。但是，由于需要对整个图像统计特征值，因此计算量和复杂度都较高。 f o 谢e r 变换方法【1 6 】是利用页面倾角对应于使f o 谢e r 空间密度最大的方向角的 特性，将文档图像的所有像素点进行f o u r i e r 变换，计算量非常大，目前很少采用。 最近邻簇( k n n ) 方法【1 7 】先找出所有连通区中心点的k 个最近邻，计算每对近 邻点的矢量方向并统计生成直方图，直方图的峰值对应于整个页面的倾角，计算复 杂度为o 小球，其中n 为连通区个数。 1 5 本文的组织结构 本文要找到一种快速有效的算法，实现对经过扫描并二值化的多区域图像分割， 并对其进行倾斜检测及校正，便于以后文字识别和分类处理。 在第二章中，详细介绍了图像倾斜检测的常用算法，将各个算法的优缺点进行了 比较。 在第三章中，给出了一种单幅图像的倾斜校正方法基于g a 的倾斜检测算 山东师范人学顾 ? 学位论义 法，该算法使用g a 对具有单区域的图像文档进行检测就有较高的精确度，并可以节 省部分的计算量。 在第露章孛，介绍了曩前常用的文档图像分割算法，给文了各个算法在文献中的 应用，并将这些算法进行比较。 在第五章中，提出了本文所采用的投影轮廓切分算法，详细会绍了算法的具体步 骤及实验结果。 在论文的最后对所做工作进行了总结和对未来工作的展望。 7 山东师范人学硕 ? 学位论文 2 1 本章概述 第二章图像的倾斜检测和校正 关于文档的倾斜检测，我们在第一章已经介绍过：文档的倾斜检测大多可以归为 五大类，基于h o u 曲变换的方法、基于交叉相关性的方法、基于投影的方法、基于 f o 嘶e r 变换的方法和k 最近邻簇法。本章将详细介绍这五种方法的基本原理，并对 这些算法的优缺点进行比较。 2 2 基于h o u g h 变换的方法 h o u 曲u 8 】变换是h o u 曲在1 9 6 2 年首先提出的，最初发表是用来检测图像中的直 线，现在己经成为图像分析中的一个经典工具，并广泛用于模式识别的各个领域。其 不仅可以用来检测直线段，而且可以检测圆周以及各种事先定义好了的曲线。h o u g h 变换的基本思想是利用点一线的对偶性( d u a l i t y ) 。即图像空间共线的点对应在参数空 间里相交的线：反过来，在参数空间中相交于同一个点的所有直线( 曲线) 在图像空间 里都有共线的点与之对应。下面我们先以直线的检测来说明h o u 曲变换的基本原理。 在图像空间x y 里，所有过点( x ，y ) 的直线都满足方程： y = 彤+ g ( 2 1 ) 其中p 为斜率，q 为截距。式( 2 1 ) 也可以写成： g = 一肜+ ) ， ( 2 2 ) 式( 2 2 ) 可认为代表参数空间p q 中过点0 ，q ) 的一条直线。 图2 一l 给出了一个示例，图2 一l ( a ) 为图像空间，图2 1 ( b ) 为参数空间。 在图像空间x y 中过点( t ，m ) 的通用直线方程按式( 2 1 ) 可写为 = 既+ g ，也 可照式( 2 2 ) 写成g = 一肚，+ y ，后者表示在参数空间p q 里的一条直线。同样，过 点( z ，y ，) 有) ，= 肛+ g ，也可写成g = 一雕+ y ，它表示在参数空间p q 里的另一条 直线。设这两条直线在参数空间p q 里的点( p ，g i ) 相交，这里对应图像空间x y 中一条 过( t ，m ) 和( x f ，y f ) 的直线，因为它满足m = p 鼍+ g 和y f = p x + g 。由此可知，图 像空间x y 中过点( 五，乃) 和( x ，y ，) 的直线上的每个点都对应在参数空间p q 里的一条直 线，且这些直线相交于点( p ，g i ) 。 山东师范人学颀l j 学位论嶷 y q 图2 1 图像空间对比图 由此可知在图像空闻中共线的点对应在参数空间里相交的线，反过来，在参数空 间中相交与同一个点的所有直线在图像空间里都有拱线的点与之对应，这就是点线 的对猖性。根据点。线的对偶性，当给定图像空间的一些边缘点，就可以通过h o u 豳 变换确定连接这些点的直线方程。h o u 醢变换把图像空间中的直线检测问题转换到参 数空间里对点的检测问题，通过在参数空间里进行简单的累加统计完成检测任务。 h o u 醢变换其实就是将笛卡尔坐标系中的( x ，y ) 映射到h o u 曲空闻的点( p ，e ) ， 即： 尹= x c 。s 移y s 澈毋 。， ( 2 。3 ) 一系列笛卡尔坐标系中的点可以映射为h o u g h 空间的若干曲线。每当一条h o u 曲 空阗的曲线与另一条曲线在( p ，8 ) 相交时，对应于( p ，8 ) 的直线在原来笛卡尔空间存 在的可能性就会增加。因此可设计一个二维的计数器h ( p ，e ) ，用于记录这种可能性 的增加，其维数对应于参数p 和e 。将原始图像中的所有点映射到h o u g h 空间并将结 果记录与计数器中，检查计数器的局部极大值，每个极大值都对应了原始图像中存在 的直线。在实际处理过程中，为了减少计算量，通常选择一定范围内的p 和。进行计 数，鳏原始图像中每个黑像素点对应的x 和y 值只需应用与一定范围的8 值，再计算 出相应的p 值，并将结果存储于计算器。 o u 曲变换一般包括三个基本步骤： 1 几何空间的每个待处理像素转换成参数空间的参数直线。 2 在参数空间设置一个累加阵列并初始化，每个待处理像素对阵列中处于 其参数直线上的单元加王。 3 从阵列中选出最大值的单元，其对应的参数所决定的直线就是我们在几 何空闻上要寻找的直线。 由于h o u g h 变换是对图像中的每个像素进行考查。因此其数量非常大，在实际应 用过程，通常采用修正的方法来降低计算的复杂度。 9 山东师范人学硕 学位论义 f a r r o w 叫等人以每2 0 个像素点为单位进行采样，再将重新采样的点利用h o u g h 变换的方法，对应于每个e 值，累加计算其p 值，并选择对应于结果平方的最大值的 e 作为倾斜角。l e 瞳伽等人首先抽取页面中某一文本区域中的连通区：由于字符连通区 的闭包盒底边通常与文本行的基线对齐，且基线方向平行于倾斜方向，因而可将字符 的底线作为样本点进行h o u g h 变换，求出倾斜角。文献 2 1 将文档的分辨率由3 0 0 d p i 降至7 5 d p i ，以行程编码方式表示图像；将原始图像中每个连续黑段的端点都由改行 程的像素点个数取代；在此基础上，应用h o u g h 变换，计算一1 5 到+ 1 5 度之间，位0 5 分辨率e 值对应的p 值；最后选取计算器的最大值对应的。的倾斜角。层次式h o u g h 变换方法以连通区的中心点作为h o u g h 变换的样本点，首先选择较大的分辨率嘏， 在较大范围口内应用h o u g h 变换，找出可能的估计值日；再在小范围( 9 一阳，臼+ 粥) 内选择较小的分辨率碱，再次利用h o u g h 变换确定准确的o 。文献 2 2 将文档图像 在竖直方向上分为若干个区域；在每个区域中，将最左边的黑像素点定义为检测点， 并将相邻检测点的方向定义位局部倾斜角；该方法也采用样层次式方式，首先选择数 量最多的局部倾斜角只作为倾斜方向的初始估计值，在以以为中心，在一定范围内 应用h o u g h 算法计算出精确的倾斜角【。7 0 j 。 虽然上述改进算法的核心思想都是减少h o u 曲变换的数据量，但由于h o u g h 变 换本身计算量较大，因此这些算法的速度仍较熳【6 5 1 。 2 3 基于投影的方法 基于投影图的方法是目前最常用的倾斜检测方法之一。投影图是指沿着某一特定 方向，累计出图像中黑像素点个数的统计图，令，( x ，y ) 表示图像的二维点值，图像大 小为日形，且 地= 譬是箍是熹 眨4 ， 投影可能沿着任意方向，但通常是沿着水平或者垂直方向，即行或者列方向，所 得的投影分别称为水平和竖直投影。图像，( x ，) ，) 在x 、y 轴上的投影分别为： 竖直投影i ( 力= ( x ，y ) y = 0 h 一1 水平投影i ( y ) = ，( x ，y ) ( 0 x 日) ( 2 5 ) ( 0 y ，其中n 为连通区个数2 粕】。 1 3 山东师范犬举硕七学位论文 3 。1 本章概述 第三章一种单幅图像的倾斜校正方法 本章使焉遗传算法将一个单独的文档页面进行倾斜检测，寻找恕该文档对应的倾 斜角，然后对该文档进行图像的倾斜校正。3 2 节中介绍了遗传算法的基本原理。3 3 节给出了使用遗传算法进行倾斜检测的具体参数的设置。3 。4 节介绍使用遗传算法进 行倾斜检测的具体算法流程。3 5 节使鲻检测出来的倾斜角对图像进行倾斜校正。在 本章的最后给出了实验的结果及其讨论。 3 。2 遗传算法的基本原理 遗传算法【3 2 】是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经 过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色 体作为遗传物质的主要载体，即多个基因的集合，其内部表现( 即基因型) 是某种基 因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特 征的菜种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码 工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初代种 群产生之磊，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。 在每一代，根据问题域中个体的适应度大小挑选个体，并借助自然遗传学的遗传算子 进行组合交叉和变异，产生出代表新的解集的种群。这个过程导致种群像自然进化一 样的詹代种群比前代更加适应予环境，末代种群中的最优个体经过解码，可以作为问 题近似最优解。 遗传算法采纳了自然进化模型，如选择、交叉、变异、迁移、局域与邻域等。计 算开始时，一定数目n 个个体( 父个体1 、父个体2 、父个体3 、父个体4 ) 即 种群随机地初始化，并计算每个个体的适应度函数，第一代也霹初始代就产生了。如 果不满足优化准则，开始产生新一代的计算。为了产生下一代，按照适应度选择个体， 父代要求基因重组( 交叉) 丽产生子代。所有的子代按一定概率变暴。然后子代的适 应度又被重新计算，子代被插入到种群中将父代取而代之，构成新的一代( 子个体l 、 子个体2 、子个体3 、子个体4 ) 。这一过程循环执行，直到满足优化准则为止。 遗传算法是以生物进化过程为背景，模拟生物进化的步骤，将繁殖、杂交、变异、 竞争和选择等概念引入到算法中，通过维持一组可行解，并通过对可行解的重新组合， 1 4 山东师范大学硕 ：学位论义 改进可行解的多维空间内的移动轨迹或趋向，最终走向最优解。它克服了传统优化方 法容易陷入局部极值的缺点，是一种全局的优化方法。遗传算法的运行过程是一个典 型的迭代过程，其必须完成的工缛内容和基本步骤如下： ( 1 ) 选择编码策略，把参数集合x 和域转换为位串结构空间s ； ( 2 ) 定义适瘦度僮函数f ( x ) ； ( 3 ) 确定遗传算法策略，包括选择群体大小n ，选择、交叉、变异方法，以及 确定交叉概率p c 、变异概率p m 等遗传参数； ( 4 ) 随机初始优生成群体p ； ( 5 ) 计算群体中个体位串解码后的适应值f ( x ) ； ( 6 ) 按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体； ( 7 ) 判断群体性能是否满足某一指标，或者已完成预定的迭代次数，不满足则 返回步骤( 6 ) ，或者修改遗抟策略再返回步骤( 6 ) 。 3 3 基于g a 的图像倾斜检测的参数设置 基于遗传算法的倾斜检测蕊基本原理是用遗传算法对文档图像辨接矩形进行计 算，利用g a 的寻优能力来获取最佳值。遗传算法在整个进化过程中的遗传操作是随 机性的，但它呈现出的特性并不是完全的隧机搜索，它能有效地利用历史信息来推测 下一代期望性能有所提高的寻优点集。这样一代代地不断进化，最后收敛到一个适应 环境的个体上，求得问题的最优解。遗传算法所涉及的五大要素：参数编码、初始种 群的设定、适应度函数的设计、遗传操作的设计和控制参数的设定，在下面将会一一 给出。一 3 3 1 参数编码 由于遗传算法计算过程的鲁棒性，它对编码的要求并不苛刻。实际上，大多数问 题都可以采用基因呈一维排列的定长染色体表现形式，尤其是基于 0 ，l 符号集的二 进制编码形式。然而，编码的策略或方法对于遗传算子，尤其是对交叉和交异算子的 功能和设计有很大影响。 由于编码形式决定了交叉算子的操作方式，编码润题往往称作编码交叉问题。 因此，作为遗传算法流程中第一步的编码是遗传算法中需要认真研究的问题，很多专 家提出了各中编码方法。 对于给定的优化问题，由g a 个体的表现型集合所组成的空间称为问题空间，由 g a 基因个体所组成的空阀称为g a 编码空闻。遗传算子在g a 编码空间中对位串个 1 5 山东师范人学硕士学位论文 体进行操作。 由问题的可行解从解空间转换到遗传算法编码空间的过程就称为编码，编码是应 用遗传算法是要解决的首要问题，也是设计遗传算法的一个关键步骤。按照遗传算法 的工作流程，当用遗传算法求解问题时，必须在目标问题实际表示与遗传算法染色体 位串结构建立联系，即确定编码和解码运算。一般来说，参数集及适应函数是与实际 问题密切相关的，往往由用户斟酌确定。 传统的遗传算法使用的编码方式是二进制编码，即遗传空间的个体或染色体通常 由二进制串来表示。 在倾斜文档图像的倾斜检测中，使用二进制编码存在以下缺点： 1 ) 倾斜的角度是来知的，范垂一般在，1 5 度主5 度之闻。恧用二进制编码，划编 码到度数的转换十分复杂，而采用实数编码则很容易办到。 2 ) 二进制位交叉和变异后有可妻毫会产生无对应可行解的个体，这些个体经解码 后所表示的可能是无效解。 由于倾斜检测是对倾斜角的检测，丽焦度和实数可以进行一一对应的转换，对于 倾斜文档圈像需要检测的就是倾斜的角度。一般所求得的精确角度都是实数，因此本 文采用实数编码。实数编码具有精度高，便于大空间搜索的优点。 3 3 2 初始种群的设定 遗传算法与传统随机类搜索算法的最大区别之一，在于它的整个算法是在群体上 进行的。正是这一特点使g a 具有了搜索过程的并行性、全局性和鲁棒性，可见群体 的设定对整个g a 的运行性能具有决定性的作用。 初始群体中的个体一般是随机产生的。在不具有关于问题解空间的先验知识的情 况下，很难判断最优解的数量及其可行解空闻中的分布状况。因此我们往往希望在阙 题解空间均匀采样，随机生成一定数目的个体( 为群体规模的2 倍，即2 n ) ，然后从 孛挑擞较好的个体构成初始群体。在本文中静初始种群采用随机产生的方法，因为对 于计算机来说，倾斜图像的倾斜方向和倾斜角都是未知的，使用随机方法有可能更快 速的找到图像所对应的倾斜焦。 3 3 3 适应度函数 遗