基于特征匹配与CNN的浮动验证码识别研究

胡蝶 侯俊 何晨航

摘 要：为有效识别浮动验证码，提出一种基于特征匹配与卷积神经网络的识别方法。首先使用特征匹配的方法得到匹配特征点，结合交叉匹配算法与K近邻匹配算法滤除错误匹配;然后对特征点进行聚类及投票分析，得到待识别字符区域，将其分割得到单个字符;最后在mnist手写数字数据集的基础上加入英文字符，构建卷积神经网络模型，将数据集送入模型进行训练。对10 000张浮动验证码进行测试，结果表明，该方法对浮动验证码的识别准确率达95%，且构建的训练集具有可扩展性，可进一步应用到其它类型的字符识别中。

关键词：特征匹配;卷积神经网络;交叉匹配算法;K近邻匹配算法

DOI：10. 11907/rjdk. 191914 开放科学（资源服务）标识码（OSID）：

中图分类号：TP301文献标识码：A 文章编号：1672-7800（2020）005-0037-05

0 引言

随着信息服务产业的不断发展，网络信息安全面临日益严峻的挑战。利用机器人程序自动注册网站、发送大量垃圾邮件、恶意破解用户密码等行为降低了网络信息服务安全性和实用性，验证码技术应运而生。验证码是一种用来区分人类和计算机的全自动图灵测试，该测试随机生成一个验证码，要求用户在文本框中输入看到的内容，只有验证通过才能访问接下来的网站内容。一个好的验证码系统既要考虑计算机安全问题，也要考虑人性化问题。对验证码识别技术的研究可用于检验网站验证码技术保证网站安全的有效性，及时发现验证码漏洞，促进验证码设计系统的发展。

近年来国内外众多学者对验证码识别技术进行了研究，以完善验证码生成技术，促进网络信息安全技术发展。于志良[1]使用模板匹配法对简单类型的验证码进行识别，该方法是从待识别图像中提取若干特征向量与模板对应的特征向量进行比较，计算图像与模板特征向量之间的距离，用最小距离法判定所属类别。该方法易于实现，但是准确率不高，缺乏系统性且不易移植;殷光等[2]提出基于支持向量机的验证码识别算法，该算法利用核函数特征空间有效训练线性学习器，同时还考虑了泛化性理论，其分类性能优良，具有统计学理论支撑，取得了较好的识别效果，使用该方法的识别率达到80%以上;田怀川[3]在验证码分类和识别阶段，建立了神经网络模型，通过对分割后验证码图片进行学习和测试，大幅提高了驗证码识别效率和准确性;张涛[4]针对数字字母组合验证码识别问题，先对验证码进行去噪和分割，然后再利用卷积神经网络模型对普通验证码进行训练识别，取得比利用传统神经网络方法和支持向量机更高的识别率，达到90%;Lin等[5]提出一种基于卷积神经网络的中文验证码识别方法，使用卷积神经网络学习汉字字符笔画、部首和字符特征，该方法大幅提高了有失真、旋转和背景噪声的汉字验证码识别精度，实验结果表明，该方法对单个汉字的识别率达到95%以上;Bostik等[6]比较了几种常用的验证码识别机器学习分类算法，包括神经网络、K近邻算法、支持向量机和决策树算法。实验在MATLAB计算机环境下进行，最终实验结果表明基于以上算法识别验证码的正确率超过89%，同时指出，算法结果差异主要体现在学习时间上。因此，识别任务应针对不同的识别需求选取合适的算法。

本文针对浮动验证码进行识别，如图1所示，其待识别主体为“US5T1”，其余字符均为干扰。干扰由字母和数字组成，与待辨认的验证码主体类似，同时这两种类型的字符处于不断运动中，增加了机器识别难度。

本文方法主要分为两部分：第一部分将动态待识别字符与干扰字符分割开来。在分割阶段，首先对验证码图片进行特征检测，使用交叉匹配算法与K近邻匹配算法[7]滤除错误的匹配。为将干扰字符与待识别字符的特征点区分开来，使用投票算法及聚类算法[8]得到待识别字符特征点，再经过以投影为基础的分割算法处理得到待识别字符图片;第二部分是识别，在识别阶段使用深度学习方法构建卷积神经网络模型以获得较高的识别率。

1 特征检测算法

1.1 SIFT算法

尺度不变特征转换（Scale Invariant Feature Transform，SIFT）[9]是一种用计算机视觉技术检测与描述图像局部特征的算法。它在尺度空间中寻找极值点，对图像尺度缩放、平移、旋转、亮度变化、目标遮挡和噪声等具有良好的不变性，对视觉变化、仿射变换也可保持一定程度的稳定性。该算法由David？Lowe在1999年提出，于2004年得到完善，算法将图像数据转换为相对于局部特征尺度的不变坐标。该方法在图像整个尺度和位置范围内可产生大量特征点，这些特征点可密集地覆盖图像，因其特征点信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配。

在进行特征匹配和识别时，首先选取一张参考图片和一张待匹配、识别的图片。从参考图片中提取SIFT特征并将其存储于数据库中，再将待识别图像中的每个特征与数据库中的特征进行比较。根据特征向量的欧氏距离得到候选匹配特征以匹配待识别图像。具体可以分为3个步骤：①生成高斯差分金字塔[10]，构建尺度空间;②SIFT特征检测;③特征点匹配，计算两组特征点128维的关键点欧式距离，欧式距离越小，则相似度越高，当欧式距离小于设定的阈值时，可判定为匹配成功。

其中SIFT特征检测过程主要包含4个步骤：①尺度空间极值点检测。在尺度空间中先初步搜索所有尺度上的图像位置，通过高斯微分函数[11]识别具有尺度和旋转不变性的潜在兴趣点;②特征点定位。在每个候选位置上，通过一个精确的模型确定其位置和尺度，特征点选取主要依据是候选兴趣点的稳定程度，即滤除低对比度与不稳定的边缘响应点，得到最终稳定的特征点;③方向分配。根据局部图像梯度方向，为每个关键点分配一个或多个方向。后续对图像进行方向、尺度、旋转变换，从而提供针对这些变换具有健壮性的特征点;④特征点描述。在每个特征点周围邻域内，在选定的尺度上测量图像梯度。这些梯度被转换成一种在局部形状失真和光照变化的代表。

1.2 SURF算法

加速稳健特征（Speeded Up Robust Features，SURF）算法[12]是一种稳健的局部特征点检测和描述算法。SURF算法是对SIFT算法的改进，提升了算法执行效率。SURF算法基本步骤与SIFT算法相同，其特点是特征稳定，具体指对各种旋转、尺度、噪声、亮度的变换保持稳定性。SURF算法在继承这些优点的基础上使用黑塞（Hessian）矩阵[13]和降维的特征描述子，完成了特征点提取和特征点描述，在执行效率上有大幅提升。

SURF算法具体实现流程为：

（1）构建黑塞（Hessian）矩阵，生成所有兴趣点用于特征提取。构建黑塞矩阵生成图像稳定的边缘点，为后续特征提取打好基础。这个过程对应于SIFT算法的高斯卷积过程。黑塞矩阵是由一个多元函数二阶偏导数构成的方阵，描述函数局部曲率，在图像I中取一个点x = （x， y），其在尺度空间[σ]下的黑塞矩阵定义为：

（3）兴趣点定位。为了对图像中的兴趣点进行定位，在3*3*3邻域内采用非最大抑制，使用由Neubeck & Van Gool[14]提出的快速变体方法;然后用Brown等[15]提出的方法在尺度和图像空间内插入黑塞矩阵行列式的最大值，将经过黑塞矩阵处理的每个像素点与二维图像空间和尺度空间邻域内的26个点进行比较，初步定位出关键点;再滤除能量比较弱的关键点及定位錯误的关键点，最终筛选出稳定的特征点。

（4）定向分配。在SURF算法，采用的是统计特征点圆形邻域内的harr小波特征[16]。即在特征点圆形邻域内，统计60°扇形内所有点的水平、垂直harr小波特征总和，然后对扇形以0.2弧度大小的间隔进行旋转并再次统计该区域内harr小波特征值，最后将值最大的扇形方向作为该特征点主方向。

（5）生成特征描述子。SIFT算法取特征点周围4*4个区域块，统计每小块内8个梯度方向，用4*4*8=128维向量作为SIFT特征描述子。SURF算法也是在特征点周围取一个4*4的矩形区域块，但是所取得矩形区域方向是沿着特征点的主方向。每个子区域统计25个像素水平方向和垂直方向的haar小波特征，水平和垂直方向均相对主方向而言。该haar小波特征为水平方向值之和、垂直方向值之和、水平方向绝对值之和及垂直方向绝对值之和4个方向。把这4个值作为每个子块区域的特征向量，所以一共有4*4*4=64维向量作为SURF特征描述子，比SIFT特征描述子减少了一半。

2 特征匹配

特征匹配[17]是针对特征描述子进行的，特征描述子通常是一个向量，两个特征描述子之间的距离可反映其相似程度，距离越小，相似度越高。根据描述子不同，选择不同的距离度量。对于浮点类型的描述子，使用欧式距离;对于二进制的描述子，使用汉明距离。特征匹配即在特征点集合中寻找与目标特征点最相似的特征点，主要有4种方法。

2.1 暴力匹配方法

暴力匹配法首先需得到一个特征点描述子，然后计算与其它所有特征点描述子的距离，将得到的距离进行排序，距离最近的特征点记为匹配点。该方法简单、易实施，且得到的匹配点也显而易见。但是这种暴力匹配方法会产生很多错误匹配，因此后续出现了很多改进机制以过滤一些错误匹配。

2.2 最小距离法

在使用暴力匹配法得到一些匹配点之后，设置一个距离，当已经匹配的点间距离不大于该距离时，则认为是一个正确的匹配，否则视为错误的匹配。该方法非常简单，对比暴力匹配方法，利用该方法进行过滤后的匹配效果大幅改善。

2.3 交叉匹配法

针对暴力匹配法，可以使用交叉匹配的方法过滤错误匹配。交叉过滤的思想是在暴力匹配的基础上再进行一次匹配，即利用被匹配到的点进行匹配，如果匹配到的仍然是第一次匹配点，则认为这是一个正确的匹配。例如，M图中的特征点记为a、b、c，N图中的特征点记为A、B、C，在N图中使用暴力匹配算法找出特征点a的匹配点为A，然后在M图中寻找A点的匹配点，若该匹配点为a，则记为正确匹配，否则视为错误匹配被过滤掉。使用交叉匹配算法可大幅提高特征点匹配正确率，过滤掉错误匹配，减小后续工作计算量。

2.4 K近邻匹配法

K近邻匹配法是在匹配时选择K个与特征点距离最近的点，如果这K个点之间的距离足够大（相似度低），则选择与特征点距离最小的点作为匹配点，通常情况下，K取值为2。即对每个匹配返回两个最近的匹配，如果这两个最近的匹配特征描述子比率足够大（比率阈值通常设置在2左右），则认为是正确匹配。

3 卷积神经网络模型

3.1 卷积神级网络模型

卷积神经网络是将图像进行分类的模型构架[18]，它由多个卷积层加池化层构成，每个卷积层后接池化层，最后一个卷积层后接密集层，密集层可能有多个，其作用是执行分类任务，该层输出节点个数应与类别数对应。之后应用Softmax激活函数[19]将输出节点的值转化为0～1之间的值，该值即可作为输入图像可能属于某个类别的概率。

本文使用交叉熵[20]函数刻画实际输出概率和期望输出概率分布之间的距离，交叉熵值越小，两个概率分布越接近，识别准确率越高。假设概率分布[p]为期望输出概率分布，[q]为实际输出概率分布，[H（p，q）]为交叉熵，则交叉熵函数为：

3.2 数据集扩展

本文构建的数据集包括0-9的数字及英文字母A-Z共计36个字符类别。其类别较多，工作量庞大，因此本文选用一种效率较高的方法构建数据集。现有mnist数据集包含0-9数字字符，本文将nist数据库中的英文字符图片格式修改成与mnist数据集图片格式一致，并添加到mnist数字数据集中，构建一个完整的验证码识别数据集。

训练数据集合由两个文件组成，一个是训练图像文件，里面存放所有训练图片，另一个是图像标签文件，记录每个训练图片最终标记类型。训练图像文件的前16个字节分为4个整型数据，每个4字节，分别代表：数据信息、图像数目，图像行数、图像列数，第5到第8字节保存的是整个训练数据集的图片数目，从第9个字节开始存放训练图像，每个图像占用784个字节，每个字节代表一个灰度值。

向訓练图片集中添加图片的步骤包括：①将图片处理成28像素×28像素的灰度图;②新建一个一维数组暂存该图各点像素值，将该数组以uint8的数据类型格式写进一个空白矩阵中，最后将这个28×28的矩阵转换成1×784的矩阵;③以二进制格式打开mnist训练图片集，将一维矩阵添加到训练集末尾;④修改训练图片集图片数目。

训练标签文件第4～8个字节记录的是标签数目信息，第8个字节后记录的是标签信息，修改标签数目信息并添加标签信息。至此，可构建一个完整的数据集。

4 实验分析与结果

从一张浮动验证码中截取9张图，如图3所示;使用SIFT、SURF特征检测算法，找到图3（a）、（b）中的特征点;对得到的特征点使用暴力匹配法，如图6所示，可得到大量匹配结果，其中包含一些错误的匹配点;结合交叉匹配法与最近邻匹配法，滤除错误匹配点，筛选后的匹配结果如图7所示。

如图3所示，随着干扰字符的不断运动，干扰字符可能消失在验证码图片中，而待识别字符一直在验证码图片中。根据该特点，对图3（a）与图3（c）、（d）、（e）、（f）、（g）、（i）分别重复上述步骤，进行特征匹配，得到匹配的特征点。使用投票算法，将特征点按重复出现的次数排序，保留出现次数前20位的特征点，滤除出现次数较少的特征点。经过对干扰字符特征点的滤除操作，可以将干扰字符的特征点与待识别字符的特征点有效区分开来。

给所有保留类的特征点作最小矩形框，将验证码图片尽可能地缩小识别范围，如图9所示。利用Huang等[21]提出的分割算法处理图9，得到的分割字符如图10所示。

利用上述方法创建一个包含数字和字母的训练集。训练集图片共计138 000张，包含0-9字符，每类分别有  6 000张训练图片，英文字母（A-Z）每类有3 000张训练图片，训练集由单一字符构成（见图11）。同时采集10 000张浮动验证码图片作为测试集，如图12所示。由此构建了一个完整的浮动验证码数据集。

构建卷积神经网络模型，将数据集输入训练模型，根据交叉熵的计算结果得到正确率，并据此结果不断调整训练模型参数以获得较高的识别准确率。在数据集训练阶段，训练步数趋于20 000步时，训练准确率逐渐稳定，训练完成后保存模型，在识别验证码字符时直接调用。

调用保存的模型，输入字符进行识别。如图11所示，虽然分割后的待识别字符存在部分干扰，但卷积神经网络分类器仍能将其正确识别出来。经验证，本文方法最终在测试集10 000张动图上的测试准确率达95%。

5 结语

随着验证码技术的不断成熟，验证码识别研究备受关注，但是浮动验证码相关研究较少。本文针对浮动验证码，构建了一个识别模型。通过对浮动字符进行特征匹配，得到字符特征点，使用聚类算法初步提取出待识别字符，再进行分割得到单个待识别字符，最终在mnist数据集的基础上扩充英文字符，使用深度学习方法构建模型，提高了识别率。下一步工作将在分割阶段根据两种类型字符倾斜与完整程度进行分割，以进一步提高识别率。

参考文献：

[1] 于志良. 简单验证码的模板匹配实现[J]. 电脑知识与技术，2011，7（26）：6375-6376.

[2] 殷光，陶亮. 一种SVM验证码识别算法[J]. 计算机工程与应用，2011，47（18）：188-190，194.

[3] 田怀川. 基于神经网络的图形验证码识别及防识别的研究与应用[D]. 哈尔滨：哈尔滨工业大学，2010.

[4] 张涛，张乐乐. 基于卷积神经网络的图片验证码识别[J]. 电子测量技术，2018，41（14）：83-87.

[5] LIN D，LIN F，LV Y P，et al. Chinese character CAPTCHA recognition and performance estimation via deep neural network[J]. Neurocomputing，2018，288：11-19.

[6] ONDREJ B，JAN K. Recognition of CAPTCHA characters by supervised machine learning algorithms[J]. IFAC Papers Online，2018，51（6）：1-6.

[7] 肖春宝，冯大政. 基于K近邻一致性的特征匹配内点选择算法[J]. 计算机科学，2016，43（1）：290-293.

[8] 王千，王成，冯振，等. K-means聚类算法研究综述[J]. 电子设计工程，2012，20（7）：21-24.

[9] LOWE D G. Distinctive image features from scale-invariant keypoints[J].  International Journal of Computer Vision，2004，60（2）：91-110.

[10] 姜靓，詹永照. 基于高斯金字塔与差分法的多目标检测和跟踪算法[J]. 微电子学与计算机，2011，28（11）：129-132，136.

[11] 索春宝，杨东清，刘云鹏.多种角度比较SIFT、SURF、BRISK、ORB、FREAK算法[J]. 北京测绘，2014（4）：23-26，22.

[12] BAY H，ESS A，TUYTELAARS T，et al.Speeded-up robust features （SURF）[J]. Computer Vision and Image Understanding，2007，110（3）：346-359.

[13] ERLEBEN K，ANDREWS S. Solving inverse kinematics using exact Hessian matrices[J]. Computers &Graphics，2019，78：1-11.

[14] NEUBECK A，GOOL V. Efficient non-maximum suppression[C].  Hongkong：The 18th International Conference on Pattern Recognition， 2006.

[15] BROWN M，LOWE D. Invariant features from interest point groups[C]. Cardiff：The British Machine Vision Conference， 2002.

[16] 刘悦. 基于Harr特征的运动车辆跟踪[J]. 广东公安科技，2019，27（1）：45-47，61.

[17] 贾迪，朱宁丹，杨宁华，等. 图像匹配方法研究综述[J]. 中国图象图形学报，2019，24（5）：677-699.

[18] RYU S H，NOH J，KIM H. Deep neural network based demand side short term load forecasting[J]. Energies，2016，10（1）：1-20.

[19] 陈翠平. 基于深度信念网络的文本分类算法[J]. 计算机系统应用，2015（2）：121-126.

[20] 赵宏，郭万鹏. 深度神经网络代价函数选择与性能评测研究[J]. 软件，2018，39（1）：14-20.

[21] HUANG S Y，LEE Y K，BELL G，e al. An efficient segmentation algorithm for captchas with line cluttering and character warping[J].  Multimedia Tools and Applications，2010，48（2）：267-289.

（責任编辑：江 艳）