形状上下文在验证码识别中的应用 旗鱼博客

形状上下文在验证码识别中的应用 旗鱼博客 形状上下文在验证码识别中的应用 旗 鱼博客 形状上下文在验证码识别中的应用|旗鱼博客2011-03-11 13:25一、引言 验证码是近几年发展起来的技术，主要是用来防止网络机器人的一些恶意行为。它是一种CAPTCHA(Completely Automated Public Turing test to Tell Computers and Humans Apart)测试，即一种完全自动的公开的图灵测试，目的是为了区分人和电脑。很多优秀的程序员写程序来参加这个测试，并且通过了一些简单的测验。他们的工具就是人工智能，如人工神经网络等等。但验证码技术也是越来越先进，产生了像Msn和Yahoo的这些尚无非常有效的破解方法的验证码。这些验证码因为很多干扰因素的存在，这对人工智能提出了更大的挑战。 二、验证码 现在当我们注册一个邮件帐号的时候，经常会被要求输入一张图片中所展示的字母和数字，这就是验证码技术。验证码技术现在已经被广泛地应用在了网站中。它主要用来防止网络机器人的恶意行为，如申请邮件帐户、注册到BBS系统、自动投票等。本文主要讨论视觉的验证码技术，即验证码图片识别。 验证码图片识别不同于光学字符识别(OCR)，前者要比后者多很多干扰因素。图1展示了Msn和Yahoo～的验证码图像，它们对于阻止网络机器人都是非常有效的。从中我们可以发现优秀的验证码图像的几个特点: 1.字符存在变形、仿射变换、缩放。 2.图像中存在干扰线。 3.一般存在6个以上的字符需要识别。 这三个特点都给识别增加了难度。通常的验证码识别需要以下三个步骤。 1.图像进行二值化和细化处理。 2.去除干扰线，并进行图像切割，使得切割后的每幅图像只包含一个字符。 3.特征提取和单个字符识别。 、3是识别的难点。图步骤1很简单，现在已经有很多成熟的方法。步骤2 像中的干扰线使得分割难以实现，比如Msn的验证码图像中的干扰线，它有长短不一，粗细不均，与字符有交叉等特点，这使得计算机程序很难区分哪些是字符，哪些是干扰线。即使是这样，通过巧妙的，也能够使分割正确率达到很高的水平。但分割后的单个字符图像中，还是不可避免的存在着干扰线。这不是本文重点，不做详细说明。本文着重讨论的是步骤3，单个字符的识别。 由于经过分割后的字符图像不可避免的存在干扰线，而且特征1的存在，也使得一般的识别方法失效，如点阵方法、十三点方法等。这些方法提取的字符特征因为图像的干扰因素而变得没有意义，这里，我们采用了形状上下文的方法。 三、形状上下文 形状上下文(shape context)最早由Serge Belongie,和Jitendra Malik提出这里简单叙述一下。 对于一幅二值图像，黑点表示字符，白点表示空白，这样我们就可以用一组黑点集合来表示一幅图像，即一幅图像可以表示为集合P={1 p,…,n p}，图2(a)(b)展示了图像上的点的例子。我们取了这两幅图像上的三个点A、B、C，然后用图2(c)所示的对数极坐标来重新表示这三个点，就得到了图2(d)(e)(f)。它们是这样得到的，以该点为极坐标中心，对于每一个由r和θ确定的极坐标区域，如果该区域内包含的点越多，则其在由θ和? r组成的直角坐标系中对应的区域颜色越深。我们可以看到，点A、C所对应的直角坐标系图很相似。这里使用的是由12个角度和5个环组成的对数极坐标系，得到的是有60个区域的直角坐标系，每个区域的值大小不同。这样原图每个点都可以对应一个维数为60的向量。Serge Belongie,和Jitendra Mali把这个向量称为点对应的形状上下文。 对于两幅比较图像，如果分别得到了每幅图像上每一个点的形状上下文，我们就可以计算两幅图中任意两个点的距离。假设两个点ip、jq，它们的形状上下文分别为其中K为形状上下文的维数。 我们可以通过下面的公式来计算两点之间的距离j iC,:得到了两幅图像任意两个点的距离，下面就是要找到两幅图像的点的一个对应关系最小。这个问可以用Hungarian方法在()3n O的时间复杂度内解出来。这中间可能会碰到两幅图像的点数不一致的问题，这可以通过增设"虚点"的方法来解决。 形状上下文包含了中非常丰富的信息，它对图像变形、仿射变换、缩放都有非好的鲁棒性。这也可以从下面的实验看出。 四、应用图形上下文进行字符识别 首先，我们需要建立样本字符图库。以Msn的验证码为例，经过观察发现，它一共有24个字母和数字，分别为A BC DE GH JK MN RS TU WX Y2 35 68 9。用字体Times New Roman做了每个字符的图像示例，并设置每幅图像的大小为21×21，单位为象素。这是小象素图像，这很关键，下文会做解释。对每个样本字符图像进行二值化和细化处理，得到了样本字符图库。 接着进行验证码图像实别。这里假设我们已经得到了经过切割后的图像。图3展示了这样一些典型测试图像示例，为了形象，第一行是原图像，第二个是对应的经过二值化和细化后的图像。 因为涉及到大量矩阵运算，所以程序用MATLAB编写。实验中，每个字符取三幅测试图像，共72个测试实例，正确识别个数为63个，正确识别率为87.5%。下面分别从正反两方面对测试结果进行说明。 从图5中我们可以看匹配错误出现的两点主要原因。 1.样本字符包含的信息太少。这是小象素样本图像不可避免的灾难。"B"确实是包含一个"3"。类似的错误还有"K"与"X"。 2.字体特征的影响。Times New Roman这种字体的特征是笔画的尽头存在冗余笔画。正是这些多余信息，使得"E"被识别成"B"。针对这些问题，我们有 一些可以改进的选择。比如说用主曲线的方法细化字符，这种方法能够淡化字体特征的影响。 五、总结 因为字符存在变形、仿射变换、缩放且图像存在干扰线等原因，这使得验证码识别变得非常困难。形状上下文存储了非常丰富的图像信息，这使得识别非常可信，而且对字符的变换和干扰线的影响都有很强的鲁棒性。该理论不光在验证码识别领域，而且在其它图像识别领域都有其强大的作用，这值得我们更加深入地进行研究。 本文作者创新点:一是首先应用形状上下文理论进行msn验证码识别，二是跳出用测试字符匹配样本字符的常规思路，进行逆向思维，用样本字符匹配测试字符，而且取得了更好的效果。