本人因为工作的关系，在去年下半年接连做了3个验证码识别的项目，分别是Airchina, ChinaSSS和Qunar。
做完之后，觉得其实验证码识别并不是什么很困难的项目，只要能针对要识别的图片进行内容结构上的分析，将内容分成几个部分，针对不同部分用好的对策进行处理，把图片有意义的内容(例如数字或者字符)分离出来。最后使用一些类似K近邻或者相似度的办法，和手工做好的模板进行匹配，对于国内网站的验证码，大都可以识别出来。
当然，我写这些文章的目的，并不是想教别人用爬虫去爬别人的暗网数据，也不是想教别人写抢票的工具，我只是针对这一类问题，记录一下自己工作中用到的方法和经验。这些方法，对于文本图像复原和损毁书籍的保护同样适用，虽然我现在还没有机会接触到这方面的工作，但我觉得用在这些方面才是有益的。
这第一篇就是对于Airchina验证码图像的识别。
1. 识别对象的特征分析
图1. 验证码样图
上面就是一张程序将要进行识别的验证码图像，经过观察后可以看到里面的文字有两部分组成。
第一部分是大小不规则的多边形。图像的背景是大小相同的正方形格子，而文字里面的大部分都是经过扭曲的不规则多边形。
第二部分是大小为m×n的实心黑色矩形。上图中，大小为1×1的矩形是背景线的交点，而m×n(m>=2或n>=2)的实心黑色矩形则是文字的边缘。
本程序识别的第一步就是拿到这两部分的位置信息，把这两部分组合起来形成文字的轮廓，以和背景区分开来。第一步运行之后的结果为，文字轮廓区域皆为白色，背景区域为黑色。
第二步是将取到的轮廓信息和已有的模板进行一一匹配，找到最相似的模板，将模板代表的字符返回，识别结束。
2. 算法步骤
2.1找出图片中所有的m×n(m>=2或n>=2)的实心黑色矩形，分别记录左上点坐标left_top和右下点right_bottom的坐标，保存下来。因为这一步找到的矩形可能存在包含关系，也就是一个矩形可能和另一个矩形有交集，所以要进行矩形区域的合并，合并成两两不相交的矩形区域。
在取到第二部分的区域后，把这些矩形区域都涂成白色，并入第二部分。
2.2观察图片，边缘的白色会影响最终的结果，所以需要将图片边缘的白色都涂成黑色。
具体做法是，从上、下、左、右四个方向，逐行逐列的从边缘向中心涂上黑色，直至该行该列的下个像素为黑色停止。这一步将边缘也并入图片的背景中。
2.3对图像进行分析，找出大小不规则的多边形。
具体做法是，对于下面3×3的图像区域，考察位置5上的像素。
图2. 8邻域图
如果和其相邻的8个位置上大多数像素为白色，则5若为黑色，直接改为白色。
如果和其相邻的8个位置上大多数像素为黑色，则5若为白色，则分两种情况进行处理：
2.3.1 将该位置改为黑色，
2.3.2不将该位置的白色改为黑色。
该考虑的原因是，白色区域有很大可能属于最后的文字区域，不应该轻易改变。
由此得到两种结果，白色改为黑色，白色不改为黑色。而后对这两种结果进行合并。
合并这两种结果的具体做法如下。
仍然考虑位置5上像素内容，不过现在参考的范围为2个3×3的区域。
1. 如果这两个图像块在位置5上的像素内容一致，则不进行改变。
2. 如果这两个图像块在位置5上的像素内容不一致，则考察这2×3×3=18个像素点的内容，计算像素点值为黑色cblack和白色cwhite的像素点数目。
a)如果cblack>cwhite，确定位置5为黑色；
b)如果cblack<cwhite，确定位置5为白色；
c)如果cblack==cwhite，则找离它最近的同像素值的点，(因为此时两个区域上位置5的像素内容肯定一个为黑色，另一个为白色)计算两者距离dis_black和dis_white返回，
i)如果dis_black<dis_white，确定位置5为黑色；
ii)如果dis_black>dis_white，确定位置5为白色；
iii)如果dis_black==dis_white，确定位置5为默认色(白色)。
2.4 涂白2.1找到的实心黑色矩形
2.5 去掉孤立色素点
具体做法是，对于下面3×3的图像区域，考察图2位置5上的像素。
如果5上为白色，与其相邻8个位置上都是黑色，则5改为黑色；
如果5上为黑色，与其相邻8个位置上都是白色，则5改为白色。
2.6 图片生长，补全图像边缘
仍然考虑3×3的图像区域，对于(1,5,9),(3,5,7),(2,5,8),(4,5,6)的位置区域。如果5位置上的像素值和其他两个位置上的像素值不同，则改为和另两个位置相同的像素值。即
如果另外两个位置像素值为白色，则修改位置5为白色；
如果另外两个位置像素值为黑色，则修改位置5为黑色。
至此，已经得到文字区域的两个部分。下图为处理的样例图片。
图3. 处理后的样例图片
3. 字符识别
3.1 切分由2得到的图片
具体做法如下。
3.1.1 先找出所有全黑色的垂直线位置{p1, p2, p3, …, pn}
因为字符有一定的宽度，所以设定一个阈值CWIDTH，如果pi-p(i+1)>=CWIDTH，就认为pi和p(i+1)之间有一个字符。最后得到几组(start, end)，程序中设计可以找出若干组(start, end)，并不是只能找到4组，以支持以后的程序扩展和图片变化。
3.1.2 对每一个子图像区域，因为此时已经找到每个字图像区域的水平起始位置，接下来对于每一个区域找垂直的起始位置。此处，从上至下，从下至上扫描两次，分别找到垂直起点行，和终点行。
3.1.3 返回每个字符区域的左上点坐标和右下点坐标
3.2 计算子图像块的特征值
这一步骤要找具体的理论和算法，根据效果可替换。
3.3与模板图像的特征进行比较，找到最接近的模板图像，返回其值。
具体代码，可以参考：https://github.com/jiabailie/Digital-Image-Processing/tree/master/Airchina