基于kNN的验证码识别

0x00 kNN算法介绍

在网上找到了很多验证码识别的例子，但是唯独没有kNN的相关源码，对基于kNN的验证码识别的介绍也比较少。自己研究了两天，算是写出了一份差不多的识别源码（图像分割是手动分割的）。

kNN算法叫做K Nearest Neighbor算法，是一个相对来说比较简单的机器学习的模型，可以用于验证码识别，手写识别等领域。有一个和这个名字很像的叫做K-Means算法，这个算法是做聚类的，而kNN是做归类的。简单的理解，给定一个待分类的数据x，通过距离x最近的几个数据来投票决定这个x应该归属于哪一类，当然也可以选择最近的1个。

wiki上有一张很棒的图很简答的说明了这个问题，绿色的点是待分类的点。

如果选择k=3（即选择3个人进行投票），那么绿色的点将归类到红色中，因为红色有两个。
如果选择k=5，那么绿色的点将归类到蓝色中，因为此时蓝色的点的数量较多。

0x01 验证码图片处理

如果做验证码识别的话，遇到的第一个问题就是图片处理，我拿到的训练样本十分坑爹，与验证码完全不！一！样！

训练样本1
训练样本2

还有两张图片就不传了，下面是待识别的验证码。

先拿第一张训练样本来说，我们首先要将其二值化，简单的讲就是将其化为黑白两种颜色，方便后面的处理。在matlab中可以用im2bw函数来实现，同时需要使用medfilt2函数将其降噪，是否降噪视情况而定，如果二值化之后看到很多的噪点，那么便需要对其降噪，比如第一张图片二值化后是这样的：

图1二值化

基本不需要降噪，但是强迫症的我还是给降噪了。第二张图片二值化后如下：

这时就需要降噪了，降噪后效果如下：

相比之下效果好了很多。

0x02 分割

第二步就是分常蛋疼的分割验证码了，其实这里可以用另一个算法直接自动分割的，但是重点是识别，采取了手动分割的方法。图片二值化之后就是一个矩阵，分割图片其实就是分割矩阵，没啥难度。分割完的效果如下：

将每一个数字都单独的分割出来，你也可以不保存下来，因为现在得到的每一个数字还需要继续加工。因为每一个数字图片大小都是不一样的，为了后面的相似度比较，需要将其resize到同等的大小，这里选择了26*26，其实我也不知道为什么选这个数字，只是在某一篇论文上看到了这个，那篇论文说26*26的大小的正确率比较高。

resize的时候建议采用双线性插值算法，这个也是那篇论文中讲到的内容。在matlab中代码如下：

img = imresize(img, [26,26], 'bilinear');

0x03 提取特征值

此时我们得到的所有训练样本的数字都是26x26大小，我们需要将其转换成二进制串，如下图。

图中右边的二进制串111111110...就是我们需要的，长度为26x26=676，这个串也是我们一会比较相似度的主要特征。

0x04 识别验证码

现在已经处理好训练样本了，并且已经将待识别的验证码也经过上述处理变成了二进制串，下面要做的就是该识别了。前面讲过，如果想要使用kNN算法，需要一个距离来度量两个东西，那么对于二进制串来说应该选择哪个距离呢？

最容易想到的应该就是汉明码距了，但是对于较小的训练样本来说，汉明码距并不是很理想。参考这篇文章：http://www.cnblogs.com/heaad/archive/2011/03/08/1977733.html

我选择几个距离进行了测试，得到的结果如下：

Database create done. size of database row=31 col=676
target: x=18 y=59
target: x=18 y=59
Using kNN with Hamming distance: 
charset: 6
charset: 1
charset: 0
charset: 4
Using kNN with cosine distance: 
charset: 2
charset: 0
charset: 2
charset: 9
Using kNN with jaccard distance: 
charset: 5
charset: 1
charset: 0
charset: 4
Using kNN with correlation distance: 
charset: 6
charset: 1
charset: 0
charset: 4

可以看到，最接近的一次也是5104，将最后一位的8识别成了4，这个距离是杰卡德相似系数(Jaccard similarity coefficient)。

总结一下正确率不高的原因，第一个就是训练样本不够（但是老师只给了这么点样本啊喂！），而且训练样本和待识别的图片的相关性不高。第二就是将二进制串作为特征可能不能很好的反应一个数字的特征。对于第二点暂时没有很好的解决方法，想不到可以用其他的什么特征来代替二进制串。

我将所有的代码以及资料全部打包上传好了，需要的同学可以到这里下载：

链接：http://pan.baidu.com/s/1kT3RPwN 密码：psc0
备份：http://url.cn/S8VwYT
备份：http://yunpan.cn/cjhiB5JjtEy6E 访问密码 0028

参考资料：

[1] - http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm

[2] - 《高效的验证码识别技术与验证码分类思想》，《计算机工程》，第35卷第8期，2009年4月，文晓阳，高能，夏鲁宁，荆继武

[3] - http://www.cnblogs.com/heaad/archive/2011/03/08/1977733.html

lightless blog