常用验证码的识别方法
此文已由作者杨杰授权网易云社区发布。
全自动区分计算机和人类的图灵测试（Completely Automated Public Turing test to tell Computers and Humans Apart，简称CAPTCHA），俗称验证码，是一种区分用户是计算机和人的公共全自动程序。验证码的主要目的是强制人机交互来抵御机器自动化攻击，为了确保服务器系统的稳定和用户信息的安全，越来越多的网站采用了验证码技术。图片验证码是目前最常用的一种，本文也主要讨论这种验证码的识别。
最近在一个爬虫项目中遇到了验证码，需要机器自动识别绕过。这些验证码大都分辨率都较低，本身信息量不大。通常被加入一种或多种干扰因素：各种背景干扰，噪声点像素，字体形变和累叠，字符位置随机及个数不定，反色等情况。在网上调研了资料和文献后，分别采用OCR识别和模板库匹配方法对不同类型验证码进行了识别。主要过程可以分解为三个步骤：1.图片清理，2.字符切分，3.字符识别。以下结合工作经验和调研内容讲解一些常用的验证码识别方法和过程。
1.图片清理
图片清理是为接下来的机器学习或模板匹配阶段做准备的，指通过灰度化、二值化、干扰点清理等过程，得到比较干净的图片数据，具体样例见下表。
1.1 彩色去噪
在计算机中使用最多的 RGB色彩空间，分别对应红、绿、蓝三种颜色，通过调配三个分量的比例来组成各种颜色。以最常见的32位颜色为例，一个分量是用8位来表示，最大值是255，灰度图是指组成颜色的三个分量相等。原始彩色图片包含的信息量是最大的，如果验证码图片中有一些利用颜色反差加的干扰点或者线条，最好能在该阶段做初步清理。比较简单的一种处理方法是采用3*3矩阵对图像进行平滑处理，即对每个像素取他所在3*3矩阵所有点的RGB均值，分别作为新的RGB值。稍微做点优化，取3*3矩阵中RGB三维欧式距离最接近均值的点作为新值。
1.2 灰度化
在彩色电视机系统中，通常使用一种叫 YUV 的色彩空间，其中Y表示亮度信号，对于人眼来说，亮度信号（Y）是最敏感的，如果将彩色图像转换为灰度图像，仅仅需要转换并保存亮度信号就可以。从RGB到YUV空间的Y转换有一个很著名的心理学公式：Y = 0.299R + 0.587G + 0.114B。
而实际应用时，将系数缩放1000倍来实现整数运算：Gray = (R*299 + G*587 + B*114 + 500) / 1000 。注意后面那个除法是整数除法，所以需要加上500来实现四舍五入。该公式的另一个简化变种也很流行：Gray = (R*30 + G*59 + B*11 + 50) / 100。更快的算法是采用移位代替除法，所以可以将系数缩放成 2的整数幂，再做右移操作。该整数取7从精度和速度上最合适：Gray = (R*0.299*2^7 + G*0.587*2^7 + B*0.114*2^7)>>7 = (R*38 + G*75 + B*15)>>7
1.3 二值化
为了简化接下来的计算，需要把灰度图片转化成黑白二值图。默认情况下值大于127的像素点被设置为白色，其余像素点设置为黑色。当然，这个阈值也需要根据图片的实际情况计算调整。一般采用直方图统计确定动态阈值的方法比较靠谱，白底黑字的取直方图靠左边的波谷位置作为阈值，黑底白字则取直方图右边的波谷位置作为阈值，将背景和字符作很好的区分。
以
（图A），和
（图B）为例，对应直方图分别为直方图A和直方图B，图A对应的动态阈值取127，而图B的动态阈值则取241比较合适。
1.4 底色统一
如果是黑底白字的图片，需要转换成白底黑字，如以上图B。
1.5 干扰点清理
在黑白二值图片去噪阶段，常用的去噪方法为联通性去噪，通常采用8向联通来计算连通点个数，若某个点的连通点数目小于预设的阀值，则认为这些点都是噪声点。这一简单粗暴的清理方法，通常情况下是非常有效的。
2 字符切分
该阶段对前期预处理后的图片进行切割处理，定位和分离出整幅图片中的每个孤立的字符主体部分。主要采用X轴和Y轴投影的方法，即统计对应坐标上黑色像素点的个数。对于图片
得到的X轴和Y轴投影分别如下。利用X轴投影可以切割出单独的字符，再分别利用Y轴投影，裁剪掉顶部和底部的空白部分。
3. OCR软件识别
我们使用的是开源的OCR识别引擎Tesseract，初期由HP实验室研发，后来贡献给了开源软件业，后经由Google进行优化并重新发布。调用代码以及识别效果如下：
该方法的优点是：开发量少；比较通用，适合于各种变形较少的验证码；对于扭曲不严重的字母和数字识别率高。缺点也很明显：对于扭曲的字母和数字识别率大大降低；对于字符间有粘连的验证码几乎难以正确识别；很难针对特定网站的验证码做定制开发。
4.模板库匹配
4.1 建立字符模板库
首先需要针对目标网站收集大量的验证码；然后根据上一章节的方法，进行图片清理；最后按照固定的长宽值切分出字符模板图，保存文件名带上对应字符的标记。
4.2 字符匹配
首先，把目标验证码图片按字符个数切分，这里的图片切分方法必须与模板制作时的切分方法一致，得到与模板图同样大小的字符图。接下来通常的做法是使用汉明距离或编辑距离定义相似度，并用KNN方法得到K个最相似的字符，最后从K个字符中选取出现次数最多的那个作为匹配结果。参考了文献[1]中K取值和字符识别率的变化关系（如下图）。
然后，我们把K取值为5。并且把相似度重新定义为：matchScore = dotMatch^2 / (dotCaptcha * dotTemplate)，其中dotMatch为验证码字符图与模板图对应位置都是黑色点的个数，dotCaptcha为验证码字符图中黑色点个数，而dotTemplate为模板图中黑色点个数。取这个分母是为了防止某些黑色点较多的模板图在匹配度计算中始终得到较大值。识别效果如下表：
该方法的优点是：原理简单直观；可以针对不同网站定制优化；对于扭曲的字母和数字识别率较高。缺点是：开发量大，需要定制开发；需要收集大量的字符图片库；字符变化很多的情况，匹配次数增加速度下降；对于字符有粘连的图片识别率低；
5. 支持向量机
支持向量机通俗来讲是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。实际应用上，往往遇到的是非线性可分得情况，因此通过核函数把低维向量映射到更高维空间，使得样本满足线性可分。
验证码识别问题实际上是其中单个字符识别问题，而在字符可穷举的情况下，比如只有英文字符和数字，单个字符识别问题其实是一个分类问题。一个英文字母或数字表示一类，而验证码中切分后得到的单个字符需要被机器自动分到某一类。一般情况下，把单个字符的灰度图片转成整形数组，数组的每一个元素表示图片的一个像素，即一个特征维度。我们切分得到的图片大小为10x16=160像素，即有160个特征，当特征数量多且特征之间关系不明确时，采用支持向量机分类比较合适。
LIBSVM 是台湾大学林智仁(Lin Chih-Jen)副教授等开发设计的一个简单、易于使用和快速有效的SVM模式识别与回归的软件包，他不但提供了编译好的可在Windows系统的执行文件，还提供了源代码，方便改进、修改以及在其它操作系统上应用。该软件还有一个特点，就是对SVM所涉及的参数调节相对比较少，提供了很多的默认参数，利用这些默认参数就可以解决很多问题；并且提供了交互检验(Cross Validation)的功能。主要参数使用：多类别（C-SVC=0），radial basis function（kernel_type=2），训练和预测代码如下。对于 这样轻微变形的验证码，有字母和数字共36个类别，收集训练样本共778个字符图的情况下，单字符预测准确率接近100%：
labels = []
samples = []for ch in captchaTemplate.keys(): for table in captchaTemplate[ch]:
labels.append(ord(ch))
samples.append(map(lambda e:e/255., table))
problem = svm_problem(labels, samples)
model = svm_train(problem, '-t 2 -c 500')print len(samples)
data = map(lambda e:e/255., list(Image.open(TESTFILE).getdata(TESTFILE)))
y = ord('z')
prediction = svm_predict([y,], [data,], model)print prediction该方法的优点是：无需设计快速的图像匹配算法；只要图片切分方法合适，对于扭曲倾斜的字母和数字识别率也较高；并且可以针对不同类型的验证码做定制优化。缺点是：支持向量机原理比较复杂，无法直观解释，需要了解支持向量机等机器学习方法。
6. 神经网络
以上验证码识别都依赖于字符切分，切分的好坏几乎直接决定识别的准确程度。而对于有字符粘连的图片，往往识别率就会低很多。目前验证码识别最先进的是谷歌在识别“街景”图像中门牌号码中使用的一套的算法。该算法将定位、分割和识别等几个步骤统一起来，采用一种“深度卷积神经网络”（deep convolutional neural network）方法进行识别，准确率可以达到99%以上。谷歌拿自有的reCAPTCHA验证码做了测试，结果发现，对于难度最大的reCAPTCHA验证码，新算法的准确率都达到 99.8%，这可能也好于大多数人为验证。
验证码作为一种辅助安全手段在Web安全中有着特殊的地位，了解验证码识别的方法和原理，不仅有利于绕过验证码抓取网站内容，而且有利于设计更安全合理的验证码。
参考资料：
[1] 《高效的验证码识别技术与验证码分类思想》
[2] 《验证码的识别与改进》
[3] Tesseract项目：http://code.google.com/p/tesseract-ocr
[4] 常见验证码的弱点与验证码识别：http://drops.wooyun.org/tips/141
[5] http://blog.csdn.net/v_july_v/article/details/7624837
[6] http://www.codeproject.com/Articles/106583/Handwriting-Recognition-Revisited-Kernel-Support-V