带干扰验证码

浙江工业大学 硕士学位论文 带干扰的验证码识别研究 姓名：吕刚 申请学位级别：硕士 专业：计算机技术 指导教师：郝平;包中文 20091018 浙江工业大学硕士学位论文 带干扰的验证码识别研究 摘 要 验证码(CAPTCHA)是现在很多网站通行的方式，在每次访问页面时随机生成。对验 证码识别技术的研究，可以及时发现和改善认证码生成程序的漏洞，在加强网站安全性， 防止恶意程序的攻击方面有着重要意义。 本文运用计算机视觉，模式识别相关理论对多种不同类型的验证码进行识别研究，总 结探讨验证码识别的一般方法，提供验证码反识别的建议。通过对比各种的不同识别方法， 使研究具有一定的理论水平和实用价值。 本文的主要工作和成果如下： 1．研究图像灰度化相关的理论和方法。常用的彩色图像灰度化方法因为没有考虑到 像素的色度差，灰度化后的图像丢失色度信息会让目标区域变得很难分割。通过试验对比 各种灰度化的应用效果，本文采用了一种非线性灰度化公式，取得了很好的灰度化效 果。 2．在验证码字符识别上，本文先研究基于模板匹配的识别方法，在此基础上，研究 了Hopfield神经网络的识别效果。通过两者的对比，分析了各自的优缺点及规避方法。 3．在传统模板匹配识别的基础上引入了加权模板和透明模板的改进，大大提高了模板 匹配识别的识别率。 4．基于半监督学习对二值化阀值进行优化，得到比Otsu阀值分割更好的效果。采用 半监督学习进行模板权值学习，提高了权值模板的识别率。 其中，上面3，4点是我们的创新点。 虽然，本文的方法在验证码识别上具有一定的实用性，但离人类的识别能力还有很大 的差距。今后，我们将在特征提取和匹配上开展更多的研究，以求在验证码识别上的更大 突破。 关键词：验证码， 模式， 神经网络， 模板匹配，图像处理 浙江工业大学硕士学位论文 StudyOnRecognitionOfCAPTCHA ABSTRACT CAPTCHAhereisanimagewithrandomizedcharacters，whichisproducedwhilespecial webpageisrequested．Characterimagesfromdifferentprogramhavegreatdifference；someof themhaveobviousvulnerabilities．StudyOilrecognitionofauthenticationcodewillhelptofind theseleaksandtopreventwebsitefromattacksbyrobotprogram． Followingisourmainworks： 1．Westudiedtheoriesaboutimagegrayprocessing，takeafew-usedformulaonimage nonlineargrayprocessing．Asouraimistosegregatethetargetpixelsfrombackground，wehope keeporenlargethegrayleveldifferencebetweenthebackgroundpixelsandthetargetpixels whilegrayprocessing．Herewetakeanewgrayprocessingformulawhichisbetterthan traditionalformulaintheapplicationwestudied． 2．Westudiedtemplatematchingbasedcharacterrecognitionandneuralnetworkbased characterrecognition，discussedtheiradvantagesanddisadvantages． 3．Weightedtemplateandtransparenttemplateisadoptedherebasedontraditionaltemplate matching，whichimprovedtherecognitionrategreatly． 4．Semi—supervisedlearningisusedinthresh—holdingofgrayimageandgetabetterresult thantraditionalOtsuthreshold．Semi-supervisedlearningisusedinadjustingtemplate’Sweight， whichimprovestherecognitionrate． Theabove3，4areourinnovativepoints． Ourmethodsinthispresentpaperareusefulinalimitedrange，thereisabiggaptosimulate human’Sability．Ourtasksinthefuturewillbemainlyinfeatureextractionandfeaturematching． KeyWords：CAPTCH八Pattern，NeuralNetwork，TemplateMatching，ImageProcess 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名：∑父∥∥)，j 日期：砂矿睁卜月加日 【一／ ， 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1、保密口，在 年解密后适用本授权书。 2、不保密口。 (请在以上相应方框内打“v”) 作者签名： 导师签名： 日期：b。锋lz--B加日 日期：砂。7年I乙月乙·日 浙江1=业大学硕士学位论文 第1章引言 验证码(CompletelyAutomatedPublicTuringtesttotellComputersandHumans Apart，CAPTCHA)这个词最早是在2002年由卡内基梅隆大学的LuisvonAhn、ManuelBlum、 NicholasJ．Hopper以及IBM的JohnLangford所提出。一种常用的CAPTCHA是让用户输 入一个扭曲变形的图片上所显示的文字或数字，扭曲变形是为了避免被OCR之类的电脑程 式自动辨识出图片上的文字、数字而失去效果。由于这个测试是由计算机来考人类，而不 是图灵测试中那样由人类来考计算机，人们有时称CAPTCHA是一种反向图灵测试。因 为图灵测试中，测试者是人类，受试者是机器和人；而验证码验证过程中，测试者是计算 机，受试者是人或机器。 验证码系统在用户每次访问页面时随机生成一个图像，图像里的信息对于人类是可识 别，而对于计算机则无法识别(基于当前的发展水平)。Google，Yahoo，微软MSN都采用 了验证码来防止非法的邮箱注册、反垃圾邮件等。国内QQ，tabao等著名的网站也有类似 的系统，用来防止暴力的账号猜解以及其他的机器人程序。随着游戏外挂的泛滥，很多网 络游戏中也采用了验证码来防止外挂程序，比如QQ农场，完美世界等。比较有意思的是 著名的reCaptcha憎验证码程序，把书籍电子化和验证码结合起来，把书籍电子化过程中， 目前的OCR系统无法识别单词拿出来，用做验证码。然后通过Web发布到各个采用 reCaptcha傅验证码的系统中，由人类进行识别，通过统计识别结果得到最佳的识别结果。 充分利用了互联网资源，在防止SPAM的同时，甚至还被用来帮助识别电子图书中机器无 法识别的单词，为书籍的电子化做出了贡献。 由于验证码生成程序的不同，认证码图像各种各样，安全级别也不相同，有些生成程 序甚至还存在着不少漏洞。文献[1，2，3，4，5]中对相应验证码的识别率都达到了80％以上， 对于当前的Gmail验证码也有识别的报道，这些信息验证码的安全性是一个有待检验 的课题。对验证码识别技术的研究，可以及时发现弱验证码，改善验证码生成程序的漏洞， 在加强网站安全性，防止恶意程序的攻击方面有着重要意义。 同时，验证码作为一种比较容易获得的样本资源，具有内容丰富，干扰性强等特点。 是学习和研究图像处理，模式识别技术的良好样本资源。验证码识别涉及到图像预处理， 分割，特征提取，识别等相关技术，很多研究成果可以推广到其他的应用领域。更重要的 是验证码设计的一条基本规则是减少硬人工智能(hardAI)问题[2]，即任何能通过验证码 ．1． 浙江l。业大学硬十学何论文 测试的程序都可以用来解决个困难的未解决的人工智能问题c1]。因此个问题如果才； 能用计算机程序解决．则可以加做验证码，反之，如果这个验证码被破解，则是人工智能 领域的一大进步，这是一种双赢的情况。 1．1课愿的研究背景 目日U验证码主要有Gimpy，Bongo，PIX三人类[1]．网络上流行的以Gimpy及其变形 为={三，Gimpy是一种基于OCB的文本验证码，也是本文的研究类型。验证码图片的文本内 容一般为数字、英文字母或者数字和英文字母的组台，也有少量程序采用了中文字符。其 基本原理就是由服务器端程序随机生成一串文本，把这串文本转换为图片后发送到客户端 要求客户识别。 早先的研究表明单个的字符已经能够很好的被计算机所识别[4]。如表1．1所示r各种 典型的扭曲字符都能够很好的破程序勘{别。正如文献[4]指出，如果一个字符能够被成功 分割(定位)出来，那么以别这个验证码就变成了单纯的字符识别问题，而字符识别问题 已经有标准的机器识别算法如神经网络，没有多大的研究价值。 表Il各种扭曲情况下的单个字符识别率(表中所有数据摘自文献[4]) 典型的扭曲字符 识别率％ j ；2 C(‘ 100 k3，，1#n96+ P L乒。C毯 lOO ．I)?13 7 98 》耸獭糯噬 辫辎辫燃鹱 00 95 虽然，字符的识别已经不是一个大问题；然而宁符的分割(定位)则仍旧是手写谚{别 和机器视觉领域一个有挑战性的问鲤。一般而者，分割是一个耗时的问题也常常是一个复 ．2- 浙江下业人学硕十学位论文 杂的组合问题[3]。 当前验证码设计的一个主要思路就是增加验证码被分割的难度。 为了增加机器识别的难度，在人眼可以识别的前提下，目前的验证码生成程序往往会 添加一些随机的干扰手段，如粘连、噪声、形变、旋转等。本文的研究重点，就是研究对 添加了各种干扰的验证码如何进行有效的识别。对于能分割的验证码，研究了通过 nopfield神经网络进行分割识别的可行性和识别率；针对粘连字符分割无法有效分割的现 状，结合验证码自身的特点，提出了无分割的权值模板匹配识别法，能够对分割法识别率 不高的csdn验证码进行有效的识别。 1．2国内外研究现状 验证码识别和其他字符识别方法有很大的相似性，可以参考现有的图像识别、字符识 别方法。在这一方面，国内外已经发展了较为成熟的识别技术，在OCR系统、车牌识别、 指纹识别、人脸识别都有成功的商业应用。 在字符识别上，有大量的学者投入了很多精力在各个应用领域丌展了很多研究。CR识 别可以追溯到1900年俄国科学家Tyuing试图发明一种视觉障碍的辅助工具，20世纪．40 年代中期借助计算的第一台字符识别装置问世。早期的字符识别研究重点是的印刷字 的识别。第一个商用的CR系统出现在1950s，然而直到1980才有第一个比较成熟的联机 手写识别系统。20世纪90年代早期图像处理、模式识别技术和人工智能有效结合后，研 究者开发出了复杂的CR系统。神经网络、隐马尔科夫模型、模糊集推理、自然语言处理 等技术被大量研究和采用。这一时期的脱机印刷体识别和小字符集脱机手写识别已经能够 符合严格环境下的商业应用[21]。目前字符识别的难点在于脱机手写识别，极端条件下的 印刷体字符识别。 国内近些年也有很多字符识别的研究，以小字符集条件下的识别比较多见，如车牌号 码识别。2003年王韬[30]用连续性Hopfield网络对噪声字符进行了分类识别，结果表明 连续性Hopfield不仅在失真率较大和吸引半径变化较大的情况下，都能正确识别，而且 与NTE方法比较，求解质量稳定，速度快，且对吸引半径不敏感，有较强的鲁棒性；2004 年谭旭等人[31]用语义和Hopfield网络对车牌上的模糊汉字进行识别研究，在一定程度 上可以解决印刷字体中较为模糊不清汉字的识别问题。2005年韩笑[20]等人对机动车号牌 图像进行大小、灰度方差、灰度均值的标准化处理。然后根据机动车号牌字符的特点，抽 ．3． 浙江工业大学硕士学位论文 取字符3种不同的特征，构造3个BP神经网络对机动车号牌字符进行识别达到了92％以 上的识别率。2005年徐海兰，刘彦婷，杨磊等人用模板匹配法、完全基于字符结构特点和 笔画类型的识别法以及基于BP神经网络的字符识别法对字符识别进行了研究，但没有给 出具体的识别数据和结果。 验证码图片有其自身的特点，如干扰性强、干扰信号的变化相对单调，字符图片很小， 一般不需要考虑时间代价。因此目前对少量离散噪声干扰，无粘连字符，无旋转，扭曲的 验证码识别上，已经取得了较好的识别效果。对于彩色干扰线干扰、粘连、选择、扭曲以 及缩放干扰的验证码识别效果还很不理想，对于这类验证码的识别，属于极端环境下的字 符识别。 2004年DONTNOD公司的Hocevar．S[29】在网络上发布了他的验证码识别程序 PWNtcha(PretendWe’reNotaTuringComputerbutaHumanAntagonist的英文缩写)，以告 知人们验证码不是一种安全的交互验证手段，现在这个项目已经开源。Hocevar同时还在 网站上发布了多个验证码的识别结果，识别率从49％到100％，其中有著名的电子支付公 司Paypal的验证码。PWNtcha针对的验证码主要是背景容易分离和非粘连的验证码，网站 也给出了一些难以识别的验证码样本，但没有给出识别结果。2003年Mori．G和Malik．J13】 利用形状上下文对Gimpy和EZ—Gimpy验证码进行了识别，识别率分别达到33％和92％【2】； 2008年英国纽卡斯尔大学的Yah．J，AHMADASE等人对Microsoft的验证码进行了威功 分割，并通过多分类器进行识别，识别率达到60％；2005斯坦福大学的年Chellapilla．K等 人f4】的研究表明单个的验证码字符可以很好的被计算机识别。国内学者对基于分割法的验 证码识别也有一些研究，2007年张淑雅等人【5】对SMTH．BBS验证码进行分割识别，分割 结果采用分别采用K近邻分类器、BP网络、SVM进行识别，识别率均在95％以上；2007 年潘大夫、汪渤[7]提出了一种基于外部轮廓的数字验证码识别方法，选取验证码字符的 外部轮廓结构上下左右四个方向的一阶微分作为识别特征，通过待识别数字某一侧外 部轮廓特征以及多侧外部轮廓的组合特征就能以非常高的J下确率识别出数字验证码； 以上的研究采用的方法都是先分割后识别的思路，对于字符粘连比较严重，无法分割 的验证码如QQ，Google等网站的验证码，尚无明确的被破解的报道。另外，目fj{『对验证 码识别的研究多是针对一种验证码，通过一种或多种方法进行识别。这类方法对先验知识 的依赖很大，识别方法对其他验证码不一定有效，或者需要大量调整来适应新的验证码。 浙江T业大学硕士学位论文 1．3课题研究的主要内容 本文按照验证码字符是否能分割把验证码分成两类。 一类是已经有较多研究的可分割的验证码。这类验证码的研究重点是粘连字符分割的 问题和算法的适应性问题。为了研究可分割验证码识别算法的适应性问题，通过选取多个 具有代表性的网站的验证码图像，基于分割法和Hopfield神经网络进行分析和试验，取得 了较好的试验结果。试验结果表明利用字符图像灰度信息和Hopfield网络可以有效的对可 分割的验证码进行分类识别，算法有一定的适应性，并且仅需字符图像的灰度信息既可适 应新的验证码，对先验知识的依赖少。 另一类是基于目前的研究水平不能分割或者说分割比较困难的验证码。基于验证码自 身的特点，本文通过最佳模板匹配识别法对其进行识别，取得了良好的识别效果。 验证码识别系统是一个基于图像处理，模式识别等技术的智能化系统。系统主要有图 像获取，图像预处理，字符分割和字符识别四部分构成。 1．3．1图像获取 验证码图片的获取方式主要有两种。网站验证码主要通过HTTP协议发送，可以通过 URL地址获取到验证码图片；网络游戏等应用程序的封包经过加密处理，可以从本机内存 ． 中读到验证码图片或者从封包数据中直接产生验证码图片。本文假设验证码图像已经获 得，不讨论图像获耿的技术。 1．3．2图像预处理 图像预处理属于初级图像处理的范围，处理的输入数据和输出数据都是图像。验证码 图像预处理是对验证码图像进行有目的的图像增强，以便进行图像分析。本文中主要讨论 图像灰度化、二值化、抑噪(滤波)等技术。在常用的2个灰度化公式外，给出了一个不常 用的灰度化公式，应用在验证码图像灰度化上，取得了突出的效果。并基于半监督学习改 进了验证码图像二值化的自动化程度和二值化效果。 1．3．3字符分割 字符分割包括从验证码图像中分割出字符区域和把字符区域划分成单个字符两个部 分。如果采用统计特征匹配以及神经网络法识别，必须要先分割出单个的字符。简单的分 割方法包括等距分割，积分投影分割，交叉点分割，求连通区等。其中，粘连字符的分割 是一个难点，复杂的粘连情况下分割比较困难，是一个硬人工智能问题。本文主要研究了 积分投影分割和求连通区。 浙江工业人学硕十学位论文 1．3．4字符识别 字符识别就是把处理后的图片还原回字符文本的过程。可以分成基于字符分割的识别 (包括采用神经网络、SVM、各种统计距的识别法)和模板匹配法识别。本文运用Hopfield 网络对可分割的验证码进行识别，识别率达到85％以上；对于不可分割的验证码，本文改 进了传统的模板匹配法，提出了最佳模板匹配识别法，引入了透明模板，加权模板。通过 基于字符宽度估计的匹配点过滤等方法提高了模板匹配法的识别率。 浙江T业人学硕十学位论文 第2章数字图像处理基础 数字图像处理是将图像信号转换为数字格式并用计算机进行处理的过程。数字图像处 理最早的应用是在报纸页，早在20世纪20年代曾引入Bartlane电缆图片传输系统，把 横跨大西洋传输-N图片的时间由1个多信息减小为3个小时。1964年，美国加利福尼亚 的喷气推进实验室，利用计算机对“旅行者7号"发回的月球图像进行畸变校J下，取得明 显的效果。进行空间应用的同时，数字图像处理技术在20世纪60年代末和20世纪70年 代初开始用于医学图像、地球遥感监测和天文学等领域，如今已经在各个技术领域取得显 著的成果。我国在20世纪70年代后期开始大规模的数字图像处理研究，取得了巨大的进 步。 2．1图像的数字化与表述 一副图像可以定义为一个二维函数f(x，Y)，这里石，Y是空间坐标，而在任何一对空间 坐标(石，y)上的幅值f称为该点图像的强度或灰度。当x+，Y和幅值厂为有限的、离散的数 值时，称该图像为数字图像。自然界呈现在人眼中的图像是连续的模拟信号，在计算机处 理前，必须用图像传感器把光信号转换为表示亮度的电信号，再通过取样和量化得到一副 数字图像。取样是对图像坐标上的离散化过程，每～个取样点称为像素。量化是对图像灰 度上的离散化过程。取样后将得到MxN个像素，每个像素量化得到一个灰度值￡，以L表 示灰度值的允许取值范围，则数字图像存储需要的比特数b可以表示为 b；M×N×L (2．1) 图像的厌度值取值范围也常被称为图像的动态范围。把占有灰度级全部有效段的图像 称为高动态范围图像，高动态范围图像有较高的对比度。相反，低动态范围的图像看上去 是冲淡了的灰暗格调。 2．2数字图像处理概念 数字图像处理就是利用计算机对数字图像进行各种目的的处理。早期的数字图像处理， 浙江工业人学硕+学位论文 主要是改善图像的视觉质量。视觉是人类最高级的感知器官，然而人类感知只限于电磁波 谱的可视波段。成像机器则可涵盖几乎全部的电磁波段，从伽马射线到无线电波。它们可 以对非人类习惯的那些图像源进行加工。这些图像包括超声波、电子显微镜和计算机产生 的图像。因此数字图像处理涉及各种各样的应用领域。 图像处理所涉及的范畴或其他领域(例如，图像分析和计算机视觉)的界定在初创人 之间并没有一致的界定[4]。一般把图像处理分为低级，中级，高级三个层次。低级图像 处理涉及初级操作，如降低噪声的图像预处理，对比度增强和图像尖锐化。低级处理是以 输入、输出都是图像为特点的处理。中级图像处理是以输入为图像，但输出是从这些图像 中提取的特征(如边缘、轮廓)为特点的。高级图像处理涉及在图像分析中被识别物体的 总体理解，以及执行与视觉相关的识别函数等。其中中级图像处理常称为图像理解，高级 图形处理常称为计算机视觉。 图像理解和计算机视觉与模式识别，专家系统，计算机图形学等众多科学有着密切的 联系。目前虽然取得了不小的进展，但它本身是一个较难的研究领域。因人对自身的视觉 系统还不甚了解，因此计算机视觉是一个有待人们进一步探解的新领域。 23图像处理常用方法简介 数字图像处理的基本方法主要有空间域法、频域法、小波变换。1987年Mallat在《多 分辨率基础》一文中采用了以小波为基础的分析方法，此后小波变换作为数字图像处理的 重要方法，在图像压缩、传输和分析等很多领域得到了广泛的应用。 图像处理的通用方法是不存在的，例如一种适合X射线的图像增强方法，不一定是增 强由空间探测器发回的火星图像的最好方法。需要根据特定的应用选择特定的处理方法。 2．3．1空间域图像处理 空间域一词是指图像平面自身，这类方法是以对图像的像素直接进行处理为基础的。 空I、日J域处理可由下式定义： g(x，．)，)=r[f(x，)，)】 (2．2) 其中f(x，Y)是输入图像，g(x，Y)是输出图像，r是对，的一种操作，其定义在@，Y)的 邻域。 丁操作最简单的形式是1×1的邻域(即单个像素)，这样的操作又叫做点操作，如对 比度增强的灰度级变换函数。更大的邻域会有更多的灵活性。一般的方法是，利用点O，Y) 一只一 浙江工业大学硕士学位论文 事先定义的邻域里的一个，值的函数来决定g在点(X，)，)的值。这个事先定义的厂值的函 数，从根本上说说就是一个二维阵列，常称为模板、滤波器、掩模等。 如邻域平均法、选择平均法、中值滤波等都是常用的空间域处理法。空问域处理法的 重点是选择合适的滤波器(包括滤波器窗口大小)。在实际的使用中，窗口的尺寸一般选3 再选5，逐渐增大，直到滤波效果满意为止。对于有缓慢变化的较长轮廓线物体的图像， 采用方形或圆形窗口为宜，对于包含尖顶角的图像，适宜用十字形窗口[6]。 2．3．2频域图像处理 频域图像处理是以修改图像的傅罩叶变换为基础的。法国数学家傅里叶指出任何周期 函数都可以表示为不同频率的正弦或余弦函数的和的形式(现在称这个和为傅罩叶级数)。 甚至非周期的函数(有限域)也可以用正弦或余弦乘以加权函数的积分来表示。在这种情 况下的公式就是傅里叶变换。傅里叶级数和傅罩叶变换是解决实际问题的工具，给信号处 理领域带来了巨大的变革[6]。 a)傅罩叶变换 单变量连续函数f(x)的傅里叶变换F(u)定义为等式： ，@)；广。厂@)P一，加出 (2．3) 其中．『一√一1。相反，给定F@)，通过傅里叶反变换可以得到f(x)： ，@)：广。F@弦72”du (2．4) 这两个等式组成了傅里叶变换对，它们指出了一个重要的事实，既一个函数可以从它 的反变换中重新获得。这种等式很容易扩展到两个变量U和v： F(H，y)一L'i(x，y)e。72玎‘“+咿’蛐 类似地，反变换为： ／(x，y)=L-Pl，就可以 把4个字符分割开。从图上来看，就是寻找明显的波谷区，做字符分割。 c)粘连分割 粘连分割是图像分割的一个难点[12]，[13]。积分投影分割可以处理简单目标区域分 割，对于目标区域粘连的情况，则显的无能为力。下图是CSDN网站验证码的一些粘连字 符截图，第一栏是原图，第二栏是预处理结果，第三栏是积分投影。 ：：．。。j- SQ so -- ．勰 ∞， 山 i∥． 。f一 _．． 原图 预处理结果 积分投影图 图3．4积分投影 图3．4中，字符的垂直投影图没有明显的波谷区，所以用积分投影法很难识别。可以 采用等距分割，交叉点检测分割等方法进行分割，能取得一定效果。 CSDN网站验证码的字符大小是固定的，而且没有变形、旋转、缩放等形变干扰。可以 采用模板匹配法，跳过分割的难题。用于验证码识别的模板库都比较小，匹配法可以获得 很好的速度。参看4．1基于模板匹配的识别法。 如果复杂粘连再结合各种形变干扰，则识别的难度就很大。 浙江l：业人学硕士学位沧文 苓刮蛤 幽3．5是Qq验证码图像，复杂的粘连结合旋转和缩放。目前还无法有效的进行识别。 D)计算连通区 如果两个字符的外边框叠加，但字符的目标像素没有粘连如图3．6。则可以采用求连 通区的方法获得字符区域。求连通区Ij勺方法也可以用在’，符粗分类上，参看3．2．2特{if!提 取。 &她藏 圆鏖曩圈 暑皇踊IllLl-‘ 宇符： 字符2 图3．6游戏完美世界的验证码 无意义字符 泼图是网络游戏完美世界的验证码的部分截图，可以通过求连通区得到4个字符区 再通过汁算连通区的面积等方法去掉两个无意义的字符区。 种搜索封闭环的算法[26]蜘l下： 1)读入二值宁符图像。 2)找到个像素值为”0”的背景像素点B。 3)搜索B的连通域，井将该连通域内的像素仝部标记为背景l。 4)遍历剀像中像素值为”0”的像素。 5)若所有”0”像索都已标记为背景1，则馥图像内_||寸闭环个数为0，跳转到(11)。 6)若存存没有标记为背景1的”0”像素点Bl，则有封闭环。 7)搜索Bl的连通域，并将改琏通域内的像素全部标记为背景2。 8)遍历罔像中像素值为⋯0的像素。 9)若所有”0”像素都已标记为背景1或背景2谈图像内土寸脚环个数为I，跳转到(1l 10)*存在没有标也为背景1或背景2的”0”像累，则该图像内封闭环个数为2。 11)结束搜索，返回封闭环个数。 浙江：』：业人学硕十学位论文 3．2．2特征提取 特征提取是分割法字符识别的关键问题。要选取合适的特征以便把不同的字符区分开， 还要考虑特征对字体的不同、字符大小的不同以及噪声等因素的不敏感性。 a)归一化 在对文字图像做特征提取之前通常需要对文字图像做归一化处理。归一化主要有位置 归一化、大小归一化和笔画粗细归一化。 有两种简单的位置归一化方法。一种是基于质心的位置归一化；另一种是基于文字外 框的位置归一化。基于质心的位置归一化方法需要首先计算文字的质心，然后再把质心移 动到指定的位置上来。基于文字外边框的位置归一化需要首先计算文字的外边框，并找出 中心，然后把文字中心移动到指定的位置上来。基于质心的位置归一化方法抗干扰能力更 强。 对不同大小的文字做变换，使之成为同一尺寸大小的文字，这个过程被称做大小归一 化。常用的大小归一化方法也有两种。一种是将文字的外边框按比例线性缩放到规定尺寸 的文字。另一种是根据水平和垂直两个方向文字目标像素的分布进行大小归一化。基于外 边框的方法对噪声很敏感。 笔画粗细的归一化在手写识别中用的比较多。在验证码识别中较少使用。一种笔画粗 细的归一化方法是骨骼化，在交叉点检测，环检测中用的比较多。 b)封闭环检测 验证码一般都是以英文字母和数字构成，通过检测图像中封闭环的数量可以很好的把 字符分成几个大类，提高的后续识别的准确度。如在模板匹配识别法中字符5和6是比较 接近的，容易混淆。通过环检测就能很好的区分字符5和6。 搜索封闭环实际上就是在字符图像中搜索连通域。在字符的二值图像中，假定字符像 素值"1"，背景像素值为"0”，则无封闭环的字符图像中只有两个连通域，即字符连通 域和背景连通域； 只有一个封闭环的字符图像中有三个连通域，即一个字符连通域和两 个背景连通域；有两个封闭坏的字符图像中有四个连通域，即一个字符连通域和三个背景 连通域。 c)不变矩 不变矩是图像的统计特性，满足平移、绅缩、旋转均不变的不变性，在图像识别领域 得到了广泛的应用[6]。Hu首先提出了用于区域形状识别的不变矩，但对封闭和不封闭结 构，由于不能直接计算矩的特征，因而还需要先构造区域，而且由于这种矩的计算涉及区 一20— 浙江j二业人学硕十学位论文 域内部和边界的所有像素，因而耗费的时间较多。另外，Chen也提出了基于边界的计算区 域不变矩的快速算法。目前矩特征广泛应用于目标识别、景物匹配、形状分析，以及字符 识别等许多方面。 不变矩的方法是一种比较经典的特征提取方法。单纯的中心矩或是原点矩尽管可以表 征平面物体的几何形状但都不具有不变性，然而可以从这些矩构造不变量。这种方法最初 由Hu提出。他利用中心矩构造出了7个不变量，这些不变量已经被成功地应用于很多领 域。关于对平移、缩放、镜像和旋转都不敏感的7个二维7变矩可以参看HUMK[18]。 浙江下业大学硕士学位论文 第4章验证码字符识别 目前市场上已经有成熟的商业化OCR识别系统，这类系统对印刷体字符的识别效果良 好，但对添加了复杂形变干扰的验证码字符的识别上效果不佳；脱机手写字符的识别对验 证码识别也有很好的借鉴意义，但是手写字符识别比验证码更加复杂和庞大，验证码识别 的针对性比脱机手写识别强。还是需要针对不同的验证码编写有针对性的识别系统。验证 码的识别主要包括分类器设计和粘连字符的分割问题，是～个涉及多个硬人工智能问题的 研究领域。 4．1基于模板匹配的识别法 验证码图像一般具有如下特点： 1)图像分辨率很小，一般在200．100像素以内。 2)一般只包含数字和英文字符，模板数相对有限。 3)包含的字符个数一般是4-6个，很少超过10个。 基于以上特点，加上验证码识别的实时性要求不高，本文认为模板匹配法可以作为验 证码识别的有效方法。字符模板匹配中一般以字符的点阵图为模板，通过狄度相关匹配在 验证码图像中寻找最佳匹配点。 模板匹配法识别中图像预处理的主要工作包括图像灰度化，图像二值化。这部分的技 术在第3章中已经做过介绍，这里不在重复。对于能够直接分割的验证码，可以通过计算 连通区得到字符模板，对于无法分割的验证码可以借助图像处理软件制作模板，因为模板 本身数量很少，这个工作并不费时。因此模板匹配法可以绕过字符分割的难题。 模板可以是基于字符特征的N维向量。字符模板匹配中一般以字符的点阵图为模板， 通过序贯相似性检测法(SSDA)在验证码图像中寻找最佳匹配点，这是一种狄度相关匹配 [6]。SSDA算法是一种快速图像匹配算法，它使用式4．1作为相似性度量，以随机不重复 的顺序选取像素对0，Y)，求和时不需要计算所有像素，只要其和超过设定的阀值(又称 为拒绝因子)，则说明当前位段为非匹配位置，停止本次计算，否则进行下一位置的测试， 直至找到匹配点为止。实际操作中，常做从图像左上角到右下角的遍历，选择最佳匹配点。 设模板图像x州的大小为m×，l，输入图像k大小为MxN，其中M>m，N>以。 Y(a，6)胛表示输入图像以(口，6)为中心，与模板图像大小相等，对应(工，y)位置的像素灰度。 一22— 浙江工业大学硕士学位论文 则相似度可以表示为： 卿，炉去∑二，∑；．。№垆x叫 模板匹配法在实际使用中很容易受相似性字符的干扰。如图4．1、4．2所示。 ．汐izr 输入图像K 部分最佳匹配点如图4．2， 图 8(0 B(0 D(0 E(0 Z(0 I(0 L(0 I(0 I(0 7(0 T(0 ， 字符i的模板 ～ f 字符二的模板 4．1模板的例子 117．0184 ／16，0184， 118．0184 117．0184 150．0184 137．3184 116．0184 13914184 117．2184 15e，0184， 151，0184， b 468 404 363 354 348 163 144 135 135 128 儿4 图4．2模板匹配识别的部分数据 C ．468 ．348 246 ．213 ．1