基于形状上下文的复杂验证码识别算法

基于形状上下文的复杂验证码识别算法 基于形状上下文的复杂验证码识别算法 第37卷 Vo1.37 第2期 NO.2 计算机 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 ComputerEngineering 2011年1月 January2011 ? 人工智能及识别技术?文章编号:1ooo—3428(2ol1)l}2—o2ot卜加3文献标识码:A中圈分类号:TP391?41 基于形状上下文的复杂验证码识别算法 贺强,晏立 (江苏人学计算机科学L_』通信]:程学院,江苏镇江2120l3) 摘要:使用改进的形状卜F文方法对复杂验进行识别,采用整体识别方法,不对图片进行切割,使用半极坐标圆进行建模的方式, 解决2个字符连接处像素点建模互相I扰的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 .设计并实现复杂验证码识别算法,井与简单验证码进行比较.实验结果证明,复杂验证 码识别算法能对字符粘连的复杂验证码进行_i:}{别. 关健词:验证码;形状上下文;整体识别 RecognitionAlgorithmofComplicatedCAPTCHA BasedonShapeContext HEQiang,YANIA (SchoolofCompuleJ'ScienceandCommunicationEngineering,JiangsuUniversily,Zhenji ang212013,China) [AbstractIThispaperusestheimprovedshapecontexttorecognizethecomplicatedCAPTC HAThroughtheholisticrecognitionmethod,without cuttingthepictureintopieces,butadoptingsemi— polarcoordinatestomodel,itsolvestheproblemthatpixelpointsbetweentwoadhered characteristicsinterferedeachotherwhenmodeling,designsandrealizesitsarithmeticmeth od,andmakesacontrastwithothersimpleCAPTCHA's identifyingprocessExperimentalresultshowsthemethodputf1)rwardinthispapercarlreco gnizecomplicatedCAPTCHA [KeywordslCAPTCHA;shapecontext;holisticrecognition D0I:10.3969/jissn.1000—3428,2011.02.069 1概述 验证码技术已经广泛应用_F互联网,用以防止网络上的 恶意攻击.由于网络攻击不断增加,验证码技术也在快速改 进,由以前单一固定数字到现在粘连扭曲的符,使攻击者 更难实现程序自动识别. 国内外越来越多的学者对验证码的设计和识别进行了研 究.文献[1]提出一种高效的验证码识别技术,能处理比较复 杂的验证码图片,并对验证码进行了分类.文献f2】将形状上 下文方法用于验证码识别,提出_r将样本字符匹配测试字符 的方法.文献【3J运用统计学方法,提出一种加权模板匹配算 法,得到了很高的识别率. 但是,一k述文献研究的验证码鄙属于简单验证码,这种 验证码的共同点是能够对图片上的字符进行切割,得到单个 字符,然后进行匹配识别.本文研究的对象是复杂验证码, 此类验证码字符粘连且有一定扭曲,没有有效的算法能够准 确切割出单个字符,所以很难进行识别.本文提出一种形状 上下文的改进方法,采用不对图片进行切割,整体识别的方 法,使用单像素跟踪算法获取字符的轮廓,有效减少了像素 点数目,降低了形状上下文描述的复杂度,采用半圆形式的 对数极坐标建模,解决了2个字符粘连处字符建模时互相f 扰的问题,准确地描述出字符特征,实现了对字符粘连复杂 验证码的识别. 2基于改进形状上下文方法的复杂验证码识别 根据分割和识别的难易,本文将验证码分为以F3种: (】)字符没有粘连.这类验证码人和计算机程序都比较容 易识别,只要有足够多的样本数量,识别率都能按近于100%. (2)字符粘连且轻度扭曲.这类验证码人很容易识别,但 是计算机程序比较难识别,是现在网络上使用比较多的一种 验证码. (3)字符粘连且极度扭曲.这种验证码人和计算机程序都 很难识别.用户体验性比较差,国内网站很少用. 定义1形状_卜下文是以有限点集来 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示待匹配的物 体,并假设这些物体内部或者表面轮廓上的离散点足以表征 该物体的形状信息.这些点能够用边界检测器来检测边缘像 素的位置而得到,={Pl,P2,…}.这些点不需要是特殊点, 比如曲率最大,变形点等,只要求这些点尽可能均匀一致分 布在物体的边缘上. 本文以第(2)类字符粘连的验证码为例进行复杂验证码 识别. 2.1单像素轮廓的提取 首先对验证码图片进行预处理.预处理一般包括灰度化, 二值化,平滑,去噪等.灰度化处理是指把含有亮度和色彩 的彩色图像变换成灰度图像的过程.这里采用的是加权平均 值法,利用Grey=O.29xred+O.587xgreen+O.114xblue算出每个 像素的灰度值Grey.根据灰度图片的Grey值进行二值化处 理,将灰度图转化为黑白两色图.取128作为阈值,根据计 算得到的Grey值,值大于128的像素点RGB值设置为(255, 255,255),而值小于128的像素点设置为(0,0,0). 示例图片背景简单,没有噪点,二值化完成后就得到了 基金项目:国家科技型中小企业技术创新基金资助项目(09C26213 203797) 作者简介:贺强(1984一),男,硕士研究生,主研方向:模式识别, 图像处理;晏藏,教授 收稿日期:2010—07一l7E—mail:heqiangcug@163.COIII 第37卷第2期贺强,晏:基于形状上下文的复杂验证码识别算法201 预处理后的图片,如图1所示. (a)原图 (h)二值化图 (c)单像素轮廓图 图1顶处理和取单像素轮廓效果 如果直接对预处理后图片进行形状上下文的建模,算法 的时间开销非常大.根据定义1可以知道,只需要对字符轮 廓像素点进行建模,就足够描述出字符的特征.为减小算法 复杂度,这里只对字符的轮廓点进行形状上下文描述,舍去 字符上的非轮廓点. 定义2围绕该区域生成的,区域中所有像素均在其内部 的区域轮廓,称为区域外边界. 定义3围绕该区域生成的,区域中所有像素均在其外部 的区域轮廓,称为区域内边界. 根据定义2和定义3,要分别获取字符的外边界和内边 界.有的字符只有外边界,而有的字符包括外边界和内边界. 本文参考文献【51提出的轮廓跟踪算法,并针对验证码字符特 征,进行了一些改进. 示例验证码图片上4个字符都两两粘连,对于外部轮廓, 只需使用带标记信息的轮廓跟踪算法进行获取.从图片左上 角开始扫描,山上到下,由左至右找到第1个黑色像素点, 设置为外部边界的开始点,使用约定符号(O,1,2,3,4,5,6,7) 对该点的8个相邻像素点进行标号.用0和1分别表示该边 界像素点没有被搜索和已经被搜索.从外边界开始点开始搜 索,先找到标号的8个相邻像素点巾一个没有被搜索的黑色 像素点,并且该像素点的相邻一个像素点为白色,即为下一 个开始搜索的轮廓像素点,将该点的标记信息设置为l,从 该点开始接着找相邻的未搜索过的边界像素点.以此类推可 以得到一个封闭的回路,直到搜索到第一个被标记的边界像 素点.便得到了4个字符的整个外部边界. 有的字符还有内边界,需要对图片从左到右,从上到下 再扫描一遍.从图片上方到下方扫描像素点时,找到第1个 有梯度变化,并且没有被标记的黑色像素点,即为内边界的 开始点,扫描一遍后可以得到所有内边界的开始点,然后使 用带标记的轮廓跟踪算法进行处理,得到每一个内边界.如 果没有搜索到内边界的开始点,即表示验证码上的4个字符 都没有内边界.得到所有的内边界后,就可以得到单像素表 示的字符轮廓图.图1中字符6有内轮廓,而另外3个字符 没有内轮廓. 2.2基于半极坐标圆建模的样本字符制作 形状上下文采用对数极坐标圆描述圆心像素点的特征, 描述出该像素点与周围像素点的相对分布角度与距离.然而 对于字符粘连的验证码字符,2个字符粘连处的像素点在使 用对数极坐标圆建模时,会受到另一个字符像素点的干扰, 而不能准确描述出目标像素点的形状上下文特征.为了解决 两字符粘连处像素点建模互相干扰的问题,本文提出了半极 坐标圆建模的形状上下文方法. 在制作样本时,由于没有算法能够对验证码上字符进行 自动切割,只能手工切割字符进行样本的制作.先从单像素 轮廓图上手工切割出单个字符,然后进行特征伉的提取.样 本特征值提取采用了形状上卜文方法,对每个轮廓像素点进 行半极坐标圆建模. 一 般图像中像素的位置可以用笛长尔坐标表示为(Y), 也可以用极坐标表示为(r'0).设圆心的坐标为(X(J.Y0),相对 于网心标,图像中其他任意一点坐标值设为(X,),则笛卡 尔坐标系转换到极坐标系的变换过程如F: r= ?(-1而,0=arctan()— X0 取坐标原点(X0,Yo)为(0,0),其用复数Z表示为: z:X+jY=r(cos0+jsin)= 令~o=lnz=lnr+jO,则笛卡尔坐标转换为对数极坐标的映 射方程为p(r,O)=lnr,q(r,f,)=0.本文的对数极坐标0值被划 分为8份,而r值被划分为3份,0值取一90.-90.或90.-270. 的半极坐标圆进行建模.这样可以得到一个4x3的矩阵.相 对于坐标原点(o,Y0),根据标(ly)的r和0值可以判定该 点位于哪一个格内. 取字符宽度的一半作为对数极坐标圆的半径值,字符左 半边的像素点只编码右半圆的值,而右半边的像素点只编码 左半圆的值,这样处理有利于进行后面的字符整体识别. 建模的示例如图2所示,字符6一共有像素点115个, 每个像素点都可以编码成这样的一个4x3的矩阵,面得到一 个描述非常丰富的样本. l49 l00 0411 230 (a)半极坐标圆建模(b)建模得到的矩阵(c)圆心像素点编码字符串 图2半极坐标圜建模过程 2.3字符整体识别 在样本足够多以后,就可以实现程序的自动识别.识别 过程中不对测试验证码图片进行切割,以样本的每个字符作 为匹配源字符,将样本的每个字符到图片上去比对,以该样 本的宽度作为直径,对图片上的每个像素点进行左右半圆的 形状上下文建模,找出编码结果与样本中的点能够匹配的点, 本文设定相似度95%以上即判定为匹配成功,如果相似度没 有达到95%以上的,选择相似度最高的进行匹配.对整个样 本库扫描一遍之后,就可以识另0出图片上有哪几个字符,再 根据各个字符像素点在图片上的相对位置排好顺序,从而实 现程序的自动识别. 假设样本上一个点的形状上下文为:hi=fhi(1),hi(2),…, hi()),测试图片上任意一点的形状上下文为:hj={hj(1), hi(2),…,hj(k)},这里k=12.令C"为形状上下文算法的Cost 值,则: ,2毫,z Cost值在0,1之间,Cost值越小,相似度越高,两点的 匹配度越高. 本文取半圆是因为半圆就足够对像素点形状描述,而且 202计算机工程2011年1月20日 消除了2个字符连按点附近像素点建模受到旁边字符的干 扰,半圆就能够准确地描述出该点的形状上下文信息.整体 识别的效果如图3所示. (b)错误识别 图3字符整体识别效果 3算法实现 本文基于.NET平台,使用c#语言进行算法实现,参考 文献f61的部分代码.输入:网络上随机获取验证码,用Bitmap 类型变量Recbmp保存.识别步骤如下: (1)对Recbmp进行灰度化,取128作为闽值,使用SetPixel 类将图片设置为只有(255,255,255)和(0,0,0)的黑白图. (2)O-Recbmp.Heigh一1和O-Recbmp.Width一1搜索到第1个 外边界像素点(mY.),将该点标记值设置为1. 1)从(o,Yo)的8个相邻像素点中搜索下一个边界点(1, Y1),标记值设置为1; 2)重复步骤1)直到搜索到边界点(YO)为止,得到所有 字符外边界; 3)根据梯度变化,从O-Recbmp.Height一1和0,Recbmp. Width一1搜索未标记的黑色像素点为内边界像素点开始点( y??(…Y),使用步骤1)和步骤2)得到每一个内边界. (3)取一个样本字符,取样本字符宽度Height作为极坐标 直径r,根据样本字符取左(右)半极坐标圆建模,利用2.2节 的方法,对验证码图片上每一个像素点(Xo,y0)分别进行左(右) 半极坐标圆建模. (4)利用2.3节的方法,根据每个像素点编码值与测试图 片上像素点编码值,计算样本字符与测试图片上像素点组成 字符的相似度Cost值. (5)根据当前的Cost值判定测试图片上是否存在该样本 字符,然后接着取下一个样本字符,蘑复(3)和(4). (6)找出Cost值最小的4个字符后,根据像素点相对位置 对字符排序,完成字符识别. 4实验与分析 本文用2种方法对复杂验证码识别进行实验:(1)制作不 同数量的样本进行实验,将识别率与简单验证码进行比较; (2)每个样本选取不同像素点数目进行建模,观察识别率随建 模像素点数目改变情况. 示例验证码有数字和字母,每个字符构造一个样本,即 ,这种情况下随机识别100张图片,识别率为 有36个样本 60%.本文对简单验证码也进行了大量实验,同样只有一个 样本的情况F,普通方法对简单验证码的识别率也只有46%. 然而,随着样本数量的增加,简单验证码的识别率能很快接 近于100%,而复杂验证码的识别率最高只能到达80%左右, 如表1所示. 表1不同数量字符样本的识剐率 字符样本数望型兰!! 简单验证码复杂验证码 对字符形状上下文建模时选取不同数量的像素点数目. 图2中字符6包含有115个像素点,其实2个相邻的像素点 形状上下文基本相同.实验时选择全部像素点建模,相邻的 2个像素点选择1个建模以及相邻的3个像素点建模一个. 选择不同数量的像素点建模得到的识别率如下: (I)全部像素点的识别率为78%; (2)1/2像素点的识别率为70%; (3)1/3像素点的识别率为67%. 选择不同数日的像素点进行建模,随机识别100张图片 的结果.可以看出,减少建模的像素点数目,程序自动识别 的正确率变化很小,然而程序运行速度明显加快. 通过大量的验证码识别实验也 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 了反识别的思想:为 了防止程序自动识别,字符粘连是第1步;然而简单的粘连 还是能够被破解,需增加干扰线以及字符适当扭曲.第3类 验证码字符扭曲程度很大,非常难识别,但人眼识别困难, 用户体验也比较差. 5结束语 验证码是网络应用的一个重要技术,简单的验证码很容 易被破解,字符粘连的验证码是比较复杂的验证码,很难通 过常规的方式去破解.然而,这种验证码也不是绝对安全的, 本文提出的基于形状上下文的复杂验证码识别算法就能够识 别字符粘连的验证码.因此,为了防止程序破解,还应在不 影响用户体验性的前提下,增加字符的扭曲和一些干扰线, 加大识别难度,实现用户比较容易识别而计算机程序难以识 别的验证码. 参考文献 …文晓阳,高能,夏鲁宁,等.高效验证码识别技术与验证码 分类思想fJJ.计算机工程,2009,35(8):186—188. [2j苏磊,马良形状上下文在验证码识别中的应用[J1.微计 算机信息,20(/7,12(2):252—253. 王虎,冯林,孙宇哲.数字验证码算法的研究和设计[J1_ 计算机T=程与应用2007,43(32):86—88. f4]BelongieS,MalikJ.MatchingwithShapeContexts[D].Berkeley, USA:UniversityofCaliforniaatBerkeley,2000. [5]桑红石,傅勇,张天序,等基于标记信息的快速轮廓跟踪 算法….华中科技大学,2005,33(9):1-4. [6]赵春江.c数字图像处理算法典型实例【M].北京:人民邮电出 版社,2009 编辑顾姣健 ——