昨天听Vani说他们pku程设的作业是要求识别 这个网站 的验证码，我感觉非常好玩，于是花了一天时间尝试了一下，感觉非常有意思，记录一下过程。
下面是这个网站的验证码示例
看起来好像很坑爹 >_<
众所周知验证码识别至今都没有什么优秀的通用算法。。 因此我们需要充分观察这个网站验证码的特殊性。
首先用wget拖一大批验证码下来看吧。
wget -q "http://www.airchina.com.cn/www/servlet/com.ace.um.common.verify.VerifyCodeServlet" -U "Mozilla/5.0 (X11; Linux i686) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.63 Safari/537.31" -O "$i.jpg"
经过简单的观察，可以发现，这个验证码是一张网格上“凸起”了若干字符。网格的大小是2像素x2像素。 各个字符和整个网格都有一定旋转，这也导致有一些地方有错位，但字符的大小和字体都是一致的，而且没有故意增加的噪音。这是一个很有用的性质。
因为我没有专门学习过任何这方面的课程，所以土法上马吧 >_<
首先那张网格肯定很碍眼，我们应该想办法把它去掉。 观察若干验证码的图案后，可以发现，所有网眼的大小都是4或者3（因为错位）。 因此。如果一个白色联通块的大小既不是3也不是4,那么说明这个“网眼”很可能是验证码文字的一部分。 还可以发现，大小小于3的黑色四联通块也很可能是文字的一部分。 而大小2×2的黑色方块很可能是文字的“阴影”造成的（看上面的图片），我们把这些方块标记为红色。
我们只保留图片中这些可能属于文字的部分，可以发现，效果已经非常好了。 但因为上面的方法显然不是很精细，图片中还存在一些很明显不属于文字的噪音。
我们发现，密集的噪音主要有以下几种格式： 长度为2的短横线、短竖线；一个像素以及相邻4个像素组成的十字形图案。 我们把这些噪声排除。 此时图片已经基本可看了，但因为网格的旋转，四个角落还有大块的黑色，并且图案中还有少量噪声。
我们先把与边界联通的黑色像素都去除。 然后把过于稀疏的黑色像素也去除，我采用的方法是，如果一个7*7的矩形中黑色像素不超过4个，那么就全删掉；11×11的矩形中黑色像素不超过10个，那么也全删掉。
经过以上处理，图片已经非常可看了。 下面是几个示例。
是不是效果很不错呢？ 几乎没有噪音，文字比较清晰。
接下来，我们的任务就是识别出这些文字。
显然，针对每个文字刻画它们的特征并进行判定是很不切实际的。 我们应该充分发挥机器的优势。
因为这个验证码中文字的字体都是相同的，我们很容易想到，在上述生成的图片中，找100个字母，人工进行识别。 然后识别新的图片时，在这100个字母中寻找与其最接近的那个，作为我们的答案。
但因为字母有旋转，位置也不一定相同，我们需要找一种比较优的匹配方案。
我们观察到，字符大小都是相同的。 因此，我们容易想到，找到每个字符的重心，在匹配两个字符时，最优的匹配应该让重心重合。 然后，我们可以枚举一个旋转角度。 这样，我们就只剩下确定两个字符的相异程度这个问题了。
很容易想到的估价是，对于两个字符中所有有色像素点，找到另外一个字符中与其最接近的像素点，以其距离作为估价。 得到了一组距离后，用它们的和/平均数/标准差等得到最终估价。
经过尝试，可以发现用“它们的和”作为估价是一个比较好的选择。
但这时候，5689这四个数字依然很接近，难以分辨。 经过观察，可以发现，5和6区别在于，5的凸起在“钩”那个地方结束了，因此产生了一块黑色，对应我们提取后图中的一块红色，而6没有这个性质。 因此，我们很容易想到，应该在寻找最近点时，更优先找同色点。 也就是，异色的点虽然也可以作为答案，但要承受一个额外的代价，我设定的是距离会额外乘2.5。 并且，显然，如果有点根本不能在近距离匹配上，那么这个字母不太可能是答案。 为了突出这一点，我设定以所有距离的2.5次方后的和为估价。 这样及时很小的不匹配也能造成比较大的答案差距。
但这个程序实在太慢了。 每个字母大约有1000个非白色像素，匹配时还要枚举旋转角度。 即使只枚举10个角度，暴力求估价的复杂度也将达到1000^2*10（枚举的旋转角度）*100（样本数），每个字母都要跑近1分钟，根本难以接受。
但我们发现，“给定一组点，求一个点的最近点”这个问题有很大的优化余地。 用V图可以优化到O(n)-O(1)，当然太复杂了。 也可以考虑套用平面最近点对分治算法，但对于这个问题是会退化到O(n^2)的，不过对于随机数据应该表现还不错。 也可以用k-d树，期望log级别，而且是在线的，代码简单。
加上k-d树优化后，速度提高了很多，每个字母只要大约10秒钟就出解了，基本可以接受，经过实际测试，每个字母出错概率仅为百分之一左右。
update: 今天又加了一些小优化，速度提高到每个字母2秒钟了。。
下面是我的代码（主程序+样本包）
http://pan.baidu.com/share/link?shareid=4162412259&uk=2249476017