（计算机应用技术专业论文）选票图像的版面理解和快速识别方法研究.pdf

浙江工业大学硕士学位论文 选票图像的版面理解和快速识别方法研究 摘要 民主选举是人类有史以来所发明的最为强大而有力的民主工具，是人民行使民主权力 的必要过程。选票作为民主选举的依赖工具，是选民表达选举意愿发扬民主权利的媒介。 但是面对着民主选举中产生的种类繁多且数量庞大的选票，如何快速且高效地实现它们的 统计却是一个迫切需要解决的问题。 在选票统计方法研究中，基于o c r 选票图像识别技术的选票统计方法是目前相对较 为可行的方法。而对于当前该方法在自动化程度、识别速度、识别正确率以及适用的选票 类型范围等方面的不足，依然还有很多工作要做。基于此，本文的研究重点为针对该方法 在以上这些方面的不足所做的一系列改进性研究，主要贡献如下： 1 、研究了选票图像的几何结构识别问题，提出了一种基于表格线游程的选票图像几 何结构识别方法。选票图像几何结构识别问题可以归结于选票表格几何结构识别问题，因 此通过检测并分析选票图像中的表格线就可以实现选票图像几何结构识别。表格线游程具 有易于检测、存储和处理等优点，且通过表格线游程来检测表格线具有抗一定程度表格线 倾斜和表格线断裂的能力，因此可以降低表格线错识漏识的发生概率，同时，也可以加快 选票图像几何结构识别的速度。 2 、研究了选票图像的版面理解问题，提出了一种基于二叉树模型的选票图像版面理 解方法。选票图像版面理解主要是指选票表格的几何结构识别和逻辑结构识别，本文以选 票表格中的表格域为单位，定义了候选人信息域、选举符号信息域、投票单元、投票行( 列) 等逻辑结构，并构建起了选票表格的逻辑结构模型，最后通过一种二叉树模型实现选票表 格的逻辑结构识别。方法能够有效地实现规则选票的版面机器自学习，提高选票图像识别 的自动化程度。 3 、研究了基于o c r 的选票图像识别方案，提出了一整套较为合理的选票图像识别方 案。方案提高了选票图像的识别正确率，同时，也加快了选票图像的识别速度。且方案适 用的选票类型的范围也较广。 i 浙江工业大学硕士学位论文 4 、以“智能选票图像识别统计系统 为背景进行了系统开发实践，证明了本文研究 方法的合理性和有效性。 关键词：选票图像，投票单元，表格线游程，候选人信息域，选举符号信息域 浙江工业大学硕士学位论文 r es e a r c ho nl a y o u tu n d e r s t a n d i n ga n d f a s tr e c o g n i t i o no fb a l l o ti m g e a b s t r a c t d e m o c r a t i ce l e c t i o ni st h em o s tp o w e r f u ld e m o c r a t i ci n s t r u m e n t si nt h eh i s t o r yo fm a n k i n d ； i ti sa l li m p o r t a n tp r o c e s sf o rp e o p l et oe x e r c i s et h e i rr i g h t s b a l l o t sw h i c ha r et h ei n s t r u m e n t so n w h i c ht h ed e m o c r a t i ce l e c t i o nd e p e n d sf o re x i s t e n c ea r et h ei n t e r m e d i u mf o rp e o p l et oe x p r e s s t h e i rh o p e sa n de x e r c i s et h e i rr i g h t s b u ti t sa l lu r g e n tp r o b l e mt or e a l i z et h eb a l l o tc o u n to f v a r i o u sk i n d so fb a l l o t sw i t hh u g ea m o u n te f f i c i e n t l y b a s e do na n a l y z i n gt h er e s e a r c hs t a t u so ft h em o s tr e a s o n a b l em e t h o di nh o m ea n d a b r o a d - b 缸l o tc o u n tb a s e do no c r , w ec a nf m dt h a tt h i sm e t h o dh a sm a n yd e f e c t si nl o w a u t o m a t i o n ，l o wr e c o g n i t i o ns p e e d ，l o wr e c o g n i t i o na c c u r a c y a n dt h en a l t o ws c o p eo f a p p l i c a t i o no fb a l l o t st y p e s a i m e da tt h e s es h o r t c o m i n g sm e n t i o n e da b o v e ，t h em a i nt a s k sw e h a v e d o n ea l ea sf o l l o w s ： 1 am e t h o db a s e do nr u n l e n g t ho ft a b l el i n et or e a l i z et h eg e o m e t r ys t r u c t u r er e c o g n i t i o n o fb a l l o ti m a g ei sp r e s e n t t h eg e o m e t r ys t r u c t u r er e c o g n i t i o no fb a l l o ti m a g ec a nc o m ed o w nt o t h eg e o m e t r ys t r u c t u r er e c o g n i t i o no fb a l l o tt a b l e s ow ec a nr e a l i z et h eg e o m e t r ys t r u c t u r e r e c o g n i t i o no fb a l l o ti m a g eb yd e t e c t i n ga n da n a l y z i n gt a b l el i n e si nt h eb a l l o ti m a g e t h e r u n 1 e n g t ho ft a b l el i n eh a st h ea d v a n t a g e so fe a s i l yd e t e c t i n g ，r e s t o r i n ga n dp r o c e s s i n g ，a n di t p e r f o r mr o b u s t l yt o d e t e c tt a b l el i n e sb yr u n l e n g t ho ft a b l el i n e t h es i t u a t i o n so fw r o n g r e c o g n i t i o na n dm i s s e dr e c o g n i t i o no ft a b l el i n e sa r er e d u c e d ，a n dt h er e c o g n i t i o ns p e e di sa l s o i m p r o v e d 2 am e t h o db a s e do nab i n o m i a lt r e em o d e lt or e a l i z et h el a y o u tu n d e r s t a n d i n go fb a l l o t i m a g ei sp r e s e n t t h el a y o u tu n d e r s t a n d i n go fb a l l o ti m a g ec a nc o m ed o w nt ot h eg e o m e t r y s t r u c t u r er e c o g n i t i o no fb a l l o tt a b l ea n dt h el o g i c a ls t r u c t u r er e c o g n i t i o no fb a l l o tt a b l e w eh a v e d e f i n e dm a n yl o g i c a ls t r u c t u r e so fb a l l o tt a b l e ，s u c ha st h ec a n d i d a t ei n f o r m a t i o nf i e l d ，t h ev o t i n g s y m b o lf i e l d ，t h ev o t i n gu n i t , a n dt h ev o t i n gr o w ( c o l u m n ) w i t ht h e s el o g i cs t r u c t u r e so f b a l l o t t a b l e ，w ec o n s t r u c tt h el o g i c a lm o d e lo fb a l l o tt a b l e a n df i n a l l yw eu s ea b i n o m i a lt r e em o d e lt o r e a l i z et h el o g i c a ls t r u c t u r er e c o g n i t i o no fb a l l o tt a b l e t h em e t h o dr e a l i z e st h em a c h i n e s e l f - l e a r n i n go fl a y o u to fr e g u l a rb a l l o ti m a g ee f f i c i e n t l y 3 ar e a s o n a b l er e c o g n i t i o ns c h e m eo fb a l l o ti m a g ei sp r e s e n t a n dt h i sr e c o g n i t i o ns c h e m e 镒 浙江工业大学硕士学位论文 n o to n l yi m p r o v e st h er e c o g n i t i o na c c u r a c ya n dt h er e o o 班t i o ns p c n e do fb a l l o ti m a g e ，b u ta l s oi s s u i t a b l ef o rm a n yk i n d so fb a l l o t st y p e s 4 t h e i n t e l l i g e n tb a l l o t c o u n ts y s t e mb a s e do no c r d e v e l o p m e n tp r a c t i c ew a s i l l u s t r a t e d ，w h i c hc o n f i r m st h ee f f e c t i v e n e s so f t h em e t h o d sm e n t i o n e da b o v e k e yw o r d s ：b a l l o ti m a g e ，t h ev o t i n gu n i t ，t h er u n - l e n g t ho ft a b l el i n e ，t h ec a n d i d a t e i n f o r m a t i o nf i e l d ，t h ev o t i n gs y m b o lf i e l d 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名：；t 么牢张日期：2 9 u 侮 月2 r 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密日。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 洮牢强 日期：僻箩月2 日 日期：年月日 浙江工业大学硕士学位论文 1 1 选举与选票 第1 章绪论 “选举”一词，在古代的中国就有，那时选举的涵义包括两个方面：“选”与“举。 “选”就是指甄选官员，即根据候选者的才能，量才授官。“举指推荐选用，即通过推 荐或选拔的方式向君主提供可供任职的候选人。其程序是先“举 后“选”，即由少数人 通过一定的程序从少数人中挑选出一些可以担任官职的候选者，再通过甄选来确定是否授 予官职或授予何种官职【1 1 。我国古代的选举是从上而下、层层选拔举荐各级官吏，或者说 是以“贤 选“贤 ( “贤 不含褒贬义) ，即是通过少数来选择少数。它是一种自上而下 的选择。 而当代中国和现代西方社会的民主选举涵义与古代中国是不同的，甚至是完全相反 的。民主选举中的“选举”一词，源于拉丁语动词“e l i g e r e ，意为挑选，它是一种具有 公认规则的程序形式，人们据此而从所有人或一些人中选择几个人或一个人担任一定职务 【2 j 。民主选举是以“众”选“贤”、以“多选“少 的过程，即通过多数来选择实施统 治的少数。它是一种自下而上的选择。 民主选举是人类有史以来所发明的最为强大而有力的民主工具，这不仅因为真正的民 主选举能够消除各种非正义和歧视，使社会每个成员都获得平等的政治权利和各种机会； 而且因为真正的选举能将社会各种各样的意志集中起来并予以适当的反映，使社会生活能 力在一定程度上按大多数人的意愿进行。民主政治就是依靠这种强大而有力的工具而形成 和发展的1 3 1 。 在现代国家中，民主选举是人民行使权力的必要过程。通过民主选举，选民可以按照 自己的意愿选举候选人，行使自己所具有的民主权利；通过统计选举中所有选民的意愿， 产生出公认的被选人，体现出民主选举公平、公开的原则。随着社会的不断发展以及民主 制度的不断健全，民主选举越来越受到人们的关注，各种类型的民主选举活动也开始日益 增多，大到国家领导人，小到社区干部、村委干部甚至学校班委的选举，都是民主权利得 以体现的地方。 选票是民主选举赖以存在的工具，是选民根据自己的意愿对候选人表达同意、反对和 弃权的信息载体。选民只有通过选票才能表达他们的意愿，发扬他们的民主权利。选票往 l 浙江工业大学硕士学位论文 往是由各选举单位自行设计制作的，并没有统一的格式，这使得选票的种类变得十分繁多； 且一次选举中所产生的选票数量也十分庞大。面对着种类繁多且数量庞大的选票，如何才 能快速且准确地得到次选举的最终结果，这是一个迫切需要解决的问题。 1 2 选票统计方法 l21 基千人工唱票的选票统计 在传统的民主选举过程中，纸张选票的统计工作一般采用人工唱票的方式进行记录和 统计。其工作流程如下图1 1 所示，选举单位首先将选票发放给选民：选民通过填写选票 表达自己的意愿；选民将填写完成后的选票投入票箱；最后选举单位对收集到的选票进行 人工唱票，得出选举结果。但是由于一次选举所产生的选票数量是十分巨大的，基于人工 唱票的选票统计方法往往显得费时费力，效率低下，不能及时反映选举结果，而且在统计 过程中极易出错，又由于监督不便，很难保证评选工作的公正性，影响了选举工作的进度 及质量。 选票发放选票填写 幽黟 霹蛋麓 人工唱票选票收集 图l 一1 传统的民主选举 12 2 基于电子选举的选票统计 为了解决选票统计过程中的时效性以及准确率等问题，电子选举方式应运而生。电子 选举从狭义上来说，是指采用电子化手段来进行投票。从广义上来说，它可以看成是注册、 2 浙扛工业大学硕士学位论文 投票、计票三个阶段的电子化选举过程1 4 1 。电子选举不仅仅是密码学的一个研究领域，同 时也与实际应用有着密切的联系。它以各种密码学技术为理论基础，通过计算机和网络来 完成投票的整个过程。电子选举可以节省大量时间和人力资源，具有很高的效率和灵活性。 由于密码技术和电子投票自身的特点，在设计中如何既保证系统的安全性同时又具有实用 性，目前，正受到广泛研究”j 。 c h a u m d 于1 9 8 i 年提出了第一个基于m i x n e t 的电子选举方案1 6 1 ( 如下图1 - 2 所示) ， 之后，人们对电子选举进行了广泛的研究。在f u j i o k a 、o k a m o t o 和o h t a 等人于1 9 9 2 年 提出了一个实用的适应大规模选举的f o o 方案9 惦，电子选举实用方案取得了实质上的 突破，并在多个国家得n t 广泛的应用，著名的有m i t 的e v o x 系统和w a s h i n g t o n 大学 的s e n s u s 系统。2 0 0 2 年1 0 月巴西在总统选举中全面采用了电子选举。2 0 0 4 年5 月， 超过67 亿的印度人在电子投票机上选出了议会下院的席位归属。2 0 0 4 年超过2 3 的美 国人在总统大选中采用了电子投票的方式。s a f e v o t e 、v o t e h e r e 等提供电子选举解决方案 的公司的出现，也标志着电子选举正从研究走向商业领域。 投票 加密或解密加密或解密计票 一曝 ，：呱，：匦 i- 选& o 卧一：臣虱一一：臣三一 t s + 一连yt 三影：i 刮 尽管电子选举具有统计速度快，准确性高等特点，但其安全性和可靠性仍然是饱受争 议的话题。t a d a y o s h ik o h n o 等人也于2 0 0 4 年陈述了电子选举存在的诸多问题同，主要表 现在缺乏票根无法验票而产生对选举结果的质疑，选票形式的单一等等。很多研究人员提 出了不少的改进方案，国内也开展了针对性的研究，但将基于“不信任”原则的选举活动 委托给电子系统这种做法的安全性仍受到质疑，电子选举方式仍受到很大的挑战嗍。 l2 3 基于机器视觉的选票统计 机器视觉是利用机器代替人眼来做测量和判断的技术。随着o m r ( o p t i c a lm a r k r e c o g n i t i o n ，光学标记识别) 识别技术9 和o c r ( o p t i c a lc h a r a c t e rr e c o g n i t i o n ，光学字符 3 浙江工业大学硕士学位论文 识别) 识别技术【1 0 l i 的兴起与发展，人们开始使用一种全新的方法来进行选票统计。 o m r ( o p t i c a lm a r kr e c o g n i t i o n ，光学标记识别) 识别技术的工作原理如下：o m r 识 别“涂点刀上有无标记两种状态。“涂点就是信息卡上可以涂写标记的地址。“涂点一 所代表的含义可以事先定义，可以代表一个阿拉伯数字，也可以表示一个英文字母或符号。 o m r 识别一般采用光电对管阅读技术。识别用的器件是半导体发光管及光敏管。发光管 是光源器件，由它发出的光照射到“涂点上。光敏管是接收器件，接收来自“涂点位 置的反射光。因为涂有标记的地方反光弱，未涂标记的地方反光强，所以光敏管接收到的 光信号强度不同。不同强度的光信号可以代表有无标记两种状态。将“涂点 位置处的发 光管和光敏管组成一只电眼，可识别一个涂点。若干个电眼排列起来组成光电头可完成对 一排涂点的识别。o m r 识别技术快速简单，识别率高且成本低，广泛应用于标准化考试 自动阅卷、各类调查问卷的统计、选举结果的统计等，是自动识别领域中应用较多的一种 方法。 2 0 0 2 年，安徽大学的王庆生等人就利用o m r 选票识别技术成功研发了计算机选举 系统【1 2 】，实现了选票的自动统计。但是基于o m r 的选票识别方法在现实应用中存在着一 系列的限制：信息卡上的“涂点 要与电眼完全对齐，即选票在录入时不能倾斜；选票不 能折皱；选票纸张质量、印刷技术要求高；选票填写标记要规范，否则就要影响识别结果。 而在实际应用中，选票在录入时由于走纸机械误差而略有倾斜，因此，基于o m r 的选票 识别方法很容易出现识别出错的情况。 随着o c r 识别技术的出现，通过将o c r 识别技术和o m r 识别技术进行结合，产生 出了一种全新的识别技术，即基于图像的o m r 识别技术f 1 3 】1 1 4 】【15 1 。该技术的出现在一定 程度上削弱了o m r 识别技术本身的一系列限制。所谓基于图像的o m r 识别技术，就是 将信息卡进行光电变换，形成二值图像；再经倾斜校正、图像分割，并对分割出的小块图 像( 含“涂点”) 中的黑像素点数进行计数。若该小块的黑像素点数大于某个阈值，就认 为有标记，否则就没有标记，从而完成了标记识别。 张香让等人于2 0 0 4 年利用基于图像的o m r 识别技术成功开发了高速后台选举系统 【坫】( 如下图1 3 所示) ，实现了纸张选票图像的快速识别及统计。该系统中的图像处理模 块如下图1 - 4 所示。基于图像的o m r 识别技术虽然在一定程度上削弱了o m r 识别技术 本身的一系列限制；且相对于o c r 识别技术而言，又省去了最耗时的字符特征抽取步骤； 但是该技术所针对的选票形式仍然是填涂卡形式的选票，这在选票的适用范围上受到了很 大的限制。而o c r 识别技术相对于o m r 识别技术来说具有更广的适用范围，且现今对 4 浙江工业大学硕士学位论文 于小字符集的o c r 识别技术已经发展得十分成熟1 刀，能够很好地识别传统纸张选票中的 勾( 4 ) 、叉( ) 、圈( o ) 等选举符号，因此基于o c r 识别技术的选票统计方法能够 取到更好的效果。 图l - 3 高速后台选票系统的流程图 图像识别模块 图1 4 高速后台选票系统中的图像处理模块 o c r ( o p t i c a lc h a r a c t e rr e c o g n i t i o n ，光学字符识别) 识别技术的工作原理如下：首先 将要识别的文字和图像扫描进计算机，然后进行图像的预处理，再抽取字符特征进行识别， 转变为计算机能够识别的字符信息。图像预处理包括去除噪声、倾斜校正、图像分割、平 滑及规范化等。其中图像分割是一个重要的步骤，它的作用是将要识别的单个字符的图像 找到并分割出来。o c r 识别技术主要应用于文字图像识别及处理，例如用于印刷体和限 制手写体字符的识别。o c r 识别技术己成为大规模数据录入的首选方案，它将随着计算 s 浙江工业大学硕士学位论文 机技术的发展而更加成熟。 刘建胜、汪同庆等人于2 0 0 2 年对传统的表格文档提出了一种基于o c r 识别技术的 表格文档识别方案( 如图1 5 所示) 0 8 1 。而纸张选票作为一个特殊的表格文档，也能很好 地适用于该方案。 图1 5 表格文档处理流程图 浙江工业大学的刘海萍等人也于2 0 0 8 年提出了一种基于版面理解的选票快速识别统 计方案【1 9 1 1 2 0 ! 。该方案在一定程度上能够适应选票类型的多样性，且在一定的人工辅助下能 够实现选票的初步识别和统计。 图l - 6 基于版面理解的选票快速识别统计方案流程图 综上所述，以上几种选票统计方法各有优缺点。由表1 1 中对这些选票统计方法的对 比可以看出，基于o c r 识别技术的选票统计方法在选票统计方面具有极大的优势。而随 着o c r 识别技术的不断发展和完善，基于o c r 识别技术的选票统计方法必将有着更为 广阔的发展及应用前景。本文所讨论的选票统计方法也为基于o c r 识别技术的选票统计 方法。 6 浙江工业大学硕士学位论文 表1 1 各种选票统计方法的比较 基于电子选举的 基于机器视觉的选票统计 人工唱票 基于图像的 选票统计 o m r 方式o c r 方式 o m r 方式 选票统计准确率一般 高 一般高高 安全可靠性一般 低高高高 否 是否可重复验证是是是是 不存在选票票根 选票统计速度慢极快快快快 限制限制 选票格式限制任意任意 填涂卡格式填涂卡格式的 任意 的选票选票 低 经济性高 需要借助于一定 一般高高 的机械设备 限制 选举场所限制任意 需要在特定的场 任意任意任意 所里进行 低 选民接受程度高 选民需要接受一 一般一般 高 定形式的培训 1 3 论文研究内容 基于o c r 识别技术的选票统计方法在选票统计方面具有极大的优势。但是通过对于 该方法研究现状的分析可以发现，现有的基于o c r 识别技术的选票图像识别方法还不是 很成熟，在自动化程度、识别速度、识别正确率以及适用的选票类型等方面仍存在着一定 的不足，具有很大的优化和改进的空间。 1 、在选票版面理解方面，自动化程度并不高。很多学者采用通过将选票的大部分甚 至所有的版面信息人工告知计算机的方式，来达到选票版面理解的目的。这样的版面理解 方式显得自动化程度不高，且效率很低。 2 、选票图像几何结构识别正确率不高。很多学者采用的选票图像几何结构识别方法 一般都会发生表格线错识、漏识等情况。而选票图像的几何结构识别是其余一系列选票图 像识别的基础，可想而知，一旦选票图像几何结构识别出错，就意味着该选票图像是无法 再继续进行其它识别操作的。 7 浙江工业大学硕士学位论文 3 、选票图像识别速度慢，识别正确率不高。选票图像的识别速度和识别正确率是一 对矛盾的关系，很多学者采用的方法都无法实现两者关系很好地融合，以至于最后得出的 结果在识别速度和正确率上都无法令人满意。 4 、现有的基于o c r 识别技术的选票图像识别方法针对的选票格式类型比较单一， 对于类型多样、页数多张的选票类型适应性比较差。而在现实社会中，由于选票是由各选 举单位自行设计的，并没有统一的格式。 针对基于o c r 识别技术的选票图像识别方法在上述方面存在的这些问题，本文也提 出了一系列相应的解决办法，本文的主要研究内容如下： l 、针对选票图像的版面特征进行了具体的分析，提出了一种基于二叉树模型的选票 版面理解方法，实现了选票版面的机器自学习。 2 、针对选票图像中选票表格部分的特征进行了具体的分析，提出了一种基于表格线 游程的选票图像几何结构识别方法，不仅大大降低了表格线错识、漏识的发生概率，同时， 也大大加快了选票图像几何结构识别的速度。 3 、提出了一整套比较合理的选票图像快速识别方案，在一定程度上解决了选票图像 识别速度和识别正确率这一对矛盾关系的融合问题。不仅在一定程度上提高了选票图像的 识别正确率，同时也在一定程度上加快了选票图像的识别速度。且该方案能够适用的选票 类型范围比较广。 4 、以基于c s 模式的智能选票识别统计系统为背景进行了系统开发实践，对系统各 个功能模块和具体流程进行了系统的规划，实现了系统的开发，验证了本文算法的合理性 和有效性。 1 4 论文体系结构 本文的主要结构按如下七个部分进行安排和阐述： 第一章分析了国内外现有的各种选票统计方法，通过对这些选票统计方法的比较可 知，基于o c r 识别技术的选票统计方法是一种较为合理的选票统计方法。通过对该方法 研究现状的分析，提出了本文的研究内容。 第二章阐述了基于o c r 识别技术的选票图像识别基本原理，并对其中的一些相关 关键技术进行了研究与分析。 第三章分析了选票的版面特征，并根据选票图像中选票表格的特征，提出了一种基 8 浙江工业大学硕士学位论文 于表格线游程的选票图像几何结构识别方法，实现了选票图像的几何结构识别。最后通过 实验验证了该方法的有效性。 第四章构建了选票中选举符号及其相关候选人之间的逻辑依赖关系，并结合选票表 格部分的特征，提出了一种基于二叉树模型的选票图像逻辑结构识别方法，实现了选票图 像的版面理解。最后通过实验验证了该方法的有效性。 第五章提出了一整套比较合理的基于o c r 识别技术的选票图像识别方案，最后通 过实验验证了该方法的有效性。 第六章对智能选票识别统计系统进行了开发实践。 第七章对本文所做工作的回顾和展望，总结了工作中取得的成绩和不足，并对下一 步工作出新的目标。 1 5 本章小结 本章首先回顾了民主选举的历史，引出了选票统计这个难题。通过对现有的各种选票 统计方法的分析比较可知，基于o c r 识别技术的选票统计方法是现行选票统计方法中较 为合理的选票统计方法。最后，通过对基于o c r 识别技术的选票统计方法研究现状的分 析，提出了本文的研究内容。 9 浙江工业大学硕士学位论文 第2 章基于o c r 的选票图像识别基本原理 基于o c r 的选票图像识别过程主要分为三个步骤，即选票图像预处理、选票图像版 面理解和o c r 字符识别( 如图2 1 所示) 。其中，选票图像预处理是选票图像识别的基础， 采集到的任何一幅原始选票图像，都存在一定程度的噪声干扰，必须对选票图像进行图像 预处理操作，从选票图像中分割出计算机需要处理的选票信息。选票图像的版面理解是 o c r 字符识别的基础，选票图像的版面理解主要告诉计算机选票图像各个位置上信息的 属性，在此基础上，计算机才能在需要提取特定信息的时候到选票图像的特定位置去提取。 最后通过对于提取到信息的o c r 字符识别，实现选票图像的识别。 ：i 字符信息识别卜卜一字符信息处理 2 1 选票图像预处理 图2 - 1 选票图像的识别过程 采集到的任何一幅原始选票图像，都存在着一定程度的噪声干扰。为了对选票图像做 进一步的处理，必须对选票图像进行二值化、平滑去噪等预处理操作，从选票图像中分割 出计算机需要处理的选票信息。选票图像的预处理过程一般包括二值化、平滑去噪和倾斜 校正等操作。 2 1 1 图像二值化 图像的二值化是图像分割的一种方法，它特别适用于目标和背景占据不同灰度级范围 1 0 浙江工业大学硕士学位论文 的图像。图像的二值化通过设定相应的灰度值阈值来实现，在二值化图像的时候把大于某 个灰度值阈值的像素设为灰度极大值，把小于这个值的像素设为灰度极小值，从而实现图 像的分割。图像的二值化可以用以下的数学模型来表示。 假设( x ，y ) 是二维数字图像的平面坐标，整幅图像灰度等级的取值范围为 0 ，2 5 5 】( o 表示最暗的灰度级，2 5 5 表示最亮的灰度级) 。i ( x ，y ) 表示分割前坐标( x ，y ) 处像素的灰度 值，g ( x ，力表示分割后坐标( z ，y ) 处像素的灰度值。假设分割阂值为t ( t 【0 ，2 5 5 】) ，则图 像在阈值r 上就可以将图像分割成两个部分，分割后的图像为 i o ， ，o ，y ) - p , l o g p r ，整个图像的熵为： 一l h o - - - z p t l o g p _ f ( 2 6 ) ( 2 - 7 ) ( 2 8 ) 1 2 浙江工业大学硕士学位论文 当忽略边缘和噪声的熵时，就可以得到下式： h b = h o 一勉，p b = l n 那么 ( 2 9 ) 日( b ) = l o g o 一弘) + ( h o - l - 玉) ( 1 一弘) ( 2 - 1 0 ) 则熵的判别函数定义为： g ( t ) = ( 彳) + ( b ) = l o g p a ( 1 一用) 】+ ( 胁一h _ ) ( 1 - - w ) + n 4 p a ( 2 - 1 1 ) 从l 到一l 改变t ，并计算o ) ，使得h ( t ) 值最大的f + 即为所求的最佳阈值。 该方法由于涉及对数运算，运算速度较慢，但对不管图像直方图是否有明显双峰都 能产生较好的分割效果。 3 、最大类间方差法( o s t u ) 1 9 7 9 年，o s t u 提出了一种常用的自适应阈值分割方法，它是建立在一幅图像的灰度 直方图基础上的，依据类间距离极大准则来确定区域分割门限。该方法概述如下： 设图像有三个灰度级，灰度值为，的像素数为胁，则图像中总的像素数为= 协， 各灰度值出现的概率为p ：i n i ，显然p o ， n 一l 且y p t ：1 。 一一 i = 0 设以灰度值t 作为门限将图像分割成两个区域，灰度级为1 r 的像素区域a ( 背景 级) ，灰度级为t + l 三一l 的像素区域b ( 目标类) 。a 、b 出现的概率分别为： ，l - i n = p ，p b = p j = l n i = 0，= ，+ l ( 2 1 2 ) 彳和b 两类的灰度均值分别为： t l l， 国彳= 驴，n ，国口= 枷丸 ( 2 - 1 3 ) i = 0 t=t+li 图像总的灰度均值为： 细；n 们+ n 伽：y 泐 一1 由此可以得到彳、b 两区域的类间方差为： 仃2 = p a ( o ) a 一彩o ) 2 + p b ( c o b c o o ) 2 ( 2 1 4 ) ( 2 1 5 ) 显然。n 、p b 、蜘、缈口、锄、o r 2 都是关于灰度级，的函数。为了得到最优分割阈值， 1 3 浙江工业大学硕士学位论文 o s t u 把两类的类间方差作为判别准则，从1 到三一1 改变f ，并计算类间方差口2 ，认为使得 c r 2 值最大的f 即为所求的最佳阈值。 忙a r g o m 口州a x p a ( o ) j | 一缈。) 2 + e 口( c o b 一国o ) 2 】 ( 2 1 6 ) 方差是灰度分布均匀性的一种度量，方差越大，说明构成图像的两部分差别越大，当 部分目标错分为背景或是部分背景错分为目标都会导致两部分差别变小。因此，使类间方 差最大意味着错分概率最小，这就是o s t u 准则。这种方法不管图像的直方图有无明显的 双峰，都能得到较满意的结果。 2 1 2 图像平滑滤波 图像平滑滤波的目的是消除或尽量减少噪声的影响，改善图像质量。图像平滑滤波实 际上是低通滤波，让主要是信号的低频部分通过，阻截属于高频部分的噪声信号汹1 。由于 图像中的噪声往往和信号交织在一起，平滑滤波往往会使图像本身的细节如边界轮廓、线 条等变得模糊不清。因此本文所采用的选票识别方案并不采用平滑滤波方式来降低图像噪 声，本章对图像平滑滤波也不进行详细概述。 2 1 3 图像倾斜校正 选票图像是经扫描得到的，在扫描过程中，不可避免会发生图像倾斜现象。而选票图 像版面理解和o c r 字符识别对于图像倾斜十分敏感，因此选票图像的倾斜校正是选票图 像预处理阶段的重要环节。选票从本质上来说是一种特殊的表格文档。表格的特殊性( 由 表格线组成) ，使得选票图像的倾斜校正成为可能。选票图像中包含了数条表格线( 表格 横线和表格竖线) ，其中，每一条表格线的倾斜程度都可以在整体上代表整幅图像的倾斜 程度。因此通过表格线的倾斜角度检测就可以实现选票图像的倾斜角度检测。常用的直线 倾斜检测方法有以下三类：h o u g h 变换及其加速方法m 1 3 3 1 、投影方法、近邻法汹1 。 l 、h o u g h 变换 h o u g h 变换( h o u g ht r a n s f o r m ，h t ) 是最常用的检测倾斜角的方法之- - 1 3 6 1 ，下面简单介 绍h o u g h 变换，用极坐标可将直线j ，= m x + b 表示为： p = x c o s o + y s i n o ( 2 1 7 ) 也可表示为： 1 4 浙江工业大学硕士学位论文 p = 扩可s i n ( e + 咖，其中留( 力= 形( 2 - 1 8 ) 其中，( p ，0 ) 定义了一个从原点到该直线最近点的向量，显然，这个向量与该指向垂 直，如图2 - 3 所示。 图2 - 3 直线的极坐标表示 以参数p 和秒构成的二维空间，x ，】，平面的任一直线对应了p ，0 平面上的一个点。 即x ，】厂平面的任一直线的h o u g h 变换是p ，0 平面上的一个点( 如图2 4 所示) 。 图2 4 直线的h o u g h 变换 对于x ，】，平面的一个特定的点( x o ，y o ) ，每一条过该点的直线，都对应了p ，秒空间 中的个点。这些点必须是满足以o o ，p ) 作为常量时的等式。因此在参数空间中与x ，】， 空间中所有这些直线对应的点的轨迹是一条正弦型曲线，即彳，y 平面上的任一点对应 1 5 浙江工业大学硕士学位论文 了p ，秒平面上的一条正弦曲线。 如果有一组位于由参数印和仇决定的直线上的边缘点，则每个边缘点对应于p ，护空 间的一条正弦型曲线。所有这些曲线必交于点( 印，秒o ) ，因为这是它们共享的一条直线的 参数。 为了找出这些点所构成的直线段，可以将p ，口空间量化成许多小格。根据每一个 ( x o ，y 0 ) 点代入秒的量化值，算出各个p ，所得值( 经量化) 落在某个小格内，便使该小格 的计数累加器加1 ，当全部( x ，y ) 点变换后，对小格进行检验，有大的计数值的小格对应 于共线点，其( p ，目) 可用作直线拟合参数。有小的计数值的各个小格一般反映非共线点， 应丢弃不用。可以看出，计算量与搜索角度步长良和搜索角度范围良密切相关。 由于基本h o u g h 算法( b h t ) 计算量非常大，因此一些专门用于倾角检测的h o u g h 变换改进算法被提了出来，采用了多级h o u g h 变换，用由粗到细的角度搜索步长进行倾 斜检测。虽然这些算法的核心思想是减少h o u g h 转换的数据量，但由于h o u g h 转换本身 计算量较大，因此改进算法的速度仍然较慢。h o u g h 变换最大的缺陷就是不适合处理版面 中图像占多数的文档。 h o u g h 变换具有较高的倾斜估计精度，但是它的计算量较大，不适用于版面大部分为 图像的文档。 2 、投影法 投影法也是最常用的倾斜校正方法之一p 6 i ，它是基于对投影图形状进行分析的方法。 其基本方法是计算每个倾斜角度的投影形状，并定义一个目标函数，实际的倾斜角度就是 使目标函数最优。由于这种方法需要计算每个倾斜角度的投影形状，要使得倾斜估计精度 较高，这种方法的计算量非常大。 最简单的方法是将文档图像向不同的方向投影。当投影方向和水平文字行方向一致 时，文字行对应的投影图上的峰值最大，行间空白对应投影的峰谷。b a i r d 3 7 j 提出了一种 改进投影算法提高了倾斜校正计算的速度和精度，它是基于连通元素的方法，假设一行中 的字符是对齐并且十分靠近的。它采用一种自底向上的方法进行分析，将该行字符作为一 个连通区域，以不同的角度进行投影，投影图上出现最大峰值和最宽峰谷时，该投影角度 就是倾斜角度。a k i y a n m a 3 8 】将一页文档分成几列，然后向水平方向投影，计算每一列的 投影值。每一个峰值对应于该列的文字行。将投影图上每一列的峰值连接成条曲线，曲 1 6 浙江工业大学硕士学位论文 线的切线就是文档的水平方向，切线的倾斜角度就是文档的倾斜角度。 投影法是一种基于文字行的倾斜校正方法，不适用于版面复杂的文档，计算量比较大， 而且精度不高。 3 、近邻法 文献 3 9 提出了一种新的倾斜角检测的算法。该算法选取文本图像的某个子区域中字 符连通区的中心点作为特征点，利用基线上的点的连续性，计算出对应的文本行的方向角， 从而得到整个页面的倾斜角。该方法通过检测连通区域，然后找到最近的连通区域，通过 连通区域间隔的中心线计算出倾斜角度。不同的近邻连通区域可计算出多个倾斜角度，根 据大多数倾斜角度的方向确定实际的倾斜方向。近邻法也具有较高的估计精度，对于具有 较多相互邻近的组成部分时，也很费时。k 最近邻簇( k n n ) 方法m 1 是一种改进的近邻 法。该方法先找出所有连通区中心点的k 个最近邻，计算每对近邻点的矢量方向并统计 生成直方图，直方图的峰值对应于整个页面的倾角，计算复杂度为o ( s 2 ) ，其中n 为连通 区个数。 2 2 选票图像版面理解 选票图像的版面理解主要告诉计算机选票图像各个位置上信息的属性。在此基础上， 计算机才能在需要提取特定信息的时候到选票图像的特定位置去提取。选票图像的版面理 解可以分为两个步骤，选票图像几何结构识别和选票图像逻辑结构识别h 。其中，选票图 像几何结构识别是选票图像逻辑结构识别的基础。 2 2 1 选票图像几何结构识别 选票的绝大部分信息存在于选票表格中，因此，选票表格部分的识别是选票图像识别 的关键。表格域是表格最基本的几何结构单元，选票表格部分就是由一系列表格域构成的， 选票图像的几何结构主要就是指这些表格域之间的相对位置关系。而每个表格域是由相邻 的两条表格横线和相邻的两条表格竖线相交而成的矩形块，因此，要研究选票表格中各个 表格域之间的相对位置关系首先就需要从选票图像中提取出选票表格的表格线。直线检测 是图像分析领域中最基本、也是不断研究探讨的问题之一，常用的直线