关于验证码:验证码与人工智能的激荡二十年成为对手

在上篇中，咱们介绍了验证码在 2000 年左右时诞生，而人工智能在平行世界中曾经倒退了 40 多年。作为验证码（CAPTCHA）概念的提出者，Luis von Ahn 认为 CAPTCHA 的设计应该基于尚未解决的人工智能难题[1]，具体到字符验证码而言，过后面对的次要挑战就是 OCR（Optical Character Recognition，光学字符识别）。因而，理论开发出的验证码个别是退出了烦扰之后的字符，OCR 技术难以辨认，而人类则能够比拟轻易地在泛滥烦扰中精确地认出残缺的词汇或者字符序列，这也合乎 CAPTCHA 中「人类能够轻易通过，然而很难写出一个程序达到较高通过率」的定义。例如 2001 年 Luis von Ahn 和雅虎（Yahoo）网站合作开发出 EZ-Gimpy 字符验证码就长这样：

也就是说，早在验证码刚诞生的时候，就不得不面对人工智能这个对手，特地是曾经倒退多年的 OCR 技术。因而，本文首先简要介绍 OCR 技术，随后会重点去论述 OCR 技术原理中经典的 Shape context 算法，最初回到事实中的反抗状况，主观剖析过后 OCR 技术对字符验证码的破解辨认状况。

一、OCR 简介

OCR 是指对文本材料的图像文件进行剖析辨认解决，获取文字及版面信息的过程[2]。其历史最早能够追溯到电报时代，同时其在帮忙视力阻碍人士浏览等方面的利用也极大地推动了晚期 OCR 技术的提高。倒退到当初，OCR 更多的是模式识别，人工智能和计算机视觉的综合钻研畛域。

而在字符验证码诞生之初的 2000 年左右，那时的 OCR 的支流实现伎俩在当初看来还比较简单，比拟有代表性的有基于卷积神经网络（convolutional neural networks）的 LeNet[3]、基于反对向量机（support vector machines）的 4，以及上面将要重点介绍的经典计算机视觉算法「形态上下文」（shape context）[6]等，这也是最早用于辨认字符验证码的 OCR 算法之一。

二、Shape Context 算法

2.1 算法原理

Shape Context 是一种形容物体形态的办法，用于测量形态之间的类似度以及还原形态上点之间的对应关系，因而该算法人造地就能够用来实现 OCR 工作：计算出已知字符和待辨认形态的 shape context，通过比对 shape context 之间的间隔找到最有可能的形态和字符对应关系，从而达到辨认字符的目标。

算法的基本思路如下：

算法的思路看起来并不简单，而且每一步的具体实现都在论文中解释得很分明：

最初，下图简要形容了 shape context 的计算和匹配过程。

2.2 代码实现
这里联合一份开源的 shape context 的 Python 实现 [7] 对算法细节和匹配成果做个演示：

• 设置对数极坐标系角度（弧度）和半径的切分参数（依照论文的预设值）：

nbins_r=5
nbins_theta=12
r_inner=0.1250
r_outer=2.0

• 计算每个点间的间隔，并标准化。计算出间隔最远的两个点以备后用：

t_points = len(points)
# distance
r_array = cdist(points, points)
# getting two points with maximum distance to norm angle by them
# this is needed for rotation invariant feature
am = r_array.argmax()
max_points = [am / t_points, am % t_points]
# normalizing
r_array_n = r_array / r_array.mean()

• 把间隔切分 bin 并计算区间内点呈现的次数：

r_bin_edges = np.logspace(np.log10(r_inner), np.log10(r_outer), nbins_r)
r_array_q = np.zeros((t_points, t_points), dtype=int)
# summing occurences in different log space intervals
# logspace = [0.1250, 0.2500, 0.5000, 1.0000, 2.0000]
# 0    1.3 | ->  1 0 | -> 2 0 | -> 3 0 | -> 4 0 | -> 5 1
# 0.43  0  |     0 1 |    0 2 |    1 3 |    2 4 |    3 5
for m in xrange(self.nbins_r):
    r_array_q += (r_array_n < r_bin_edges[m]

• 计算每个点之间的角度，标准化，而后都变换到 0 – 2π 的区间：

theta_array = cdist(points, points, lambda u, v: math.atan2((v[1] - u[1]), (v[0] - u[0])))
norm_angle = theta_array[max_points[0], max_points[1]]
# making angles matrix rotation invariant
theta_array = (theta_array - norm_angle * (np.ones((t_points, t_points)) - np.identity(t_points)))
# removing all very small values because of float operation
theta_array[np.abs(theta_array) < 1e-7] = 0
# 2Pi shifted because we need angels in [0, 2Pi]
theta_array_2 = theta_array + 2 * math.pi * (theta_array < 0)

• 把角度切分 bin 并计算区间内点呈现的次数：

theta_array_q = (1 + np.floor(theta_array_2 / (2 * math.pi / self.nbins_theta))).astype(int)

• 对每个半径和角度区间的点进行计数，失去 shape context 描述符：

fz = r_array_q > 0
nbins = self.nbins_theta * self.nbins_r
descriptor = np.zeros((t_points, nbins))
for i in xrange(t_points):
    sn = np.zeros((self.nbins_r, self.nbins_theta))
    for j in xrange(t_points):
        if (fz[i, j]):
            sn[r_array_q[i, j] - 1, theta_array_q[i, j] - 1] += 1
    descriptor[i] = sn.reshape(nbins)

其余局部联合论文都很好了解，这里只解释两个有可能被疏忽然而十分重要的点：
1）r_array_n = r_array / r_array.mean() 这一句的作用是把所有的间隔都标准化，标准化的形式是转换为这个间隔绝对于均匀间隔的比值。也就是 r_array 是轮廓上每个点之间的欧氏间隔，是绝对值；r_array_n 是转换之后的比值矩阵，是相对值：

这样做的目标是使 shape context 具备缩放不变性，也就是同一个物体的不同尺寸的图像，计算出的 shape context 是雷同的。

2）theta_array = (theta_array – norm_angle * (np.ones((t_points, t_points)) – np.identity(t_points))) 这里的作用和下面相似，使 shape context 具备旋转不变性（因为所有的角度都是绝对于间隔最远的两个点之间的连线示意的，这也是为什么第二步要找出所有点里间隔最远的一对）。

基于以上实现的 shape context 算法，上面的代码演示了一个最简略的利用该算法进行 OCR 辨认的过程。能够看到，在辨认毫无烦扰的数字图片时的成果是很精确的。

然而对于应用 iPad 手写的数字的辨认，辨认准确率还是很低的，如下所示：

最初，对于 shape context 论文作者而言，他过后利用 MNIST 数据集进行测试，能够达到 0.63% 的错误率，是过后的最好问题[6]，不过那是建设在大量训练集的根底上。

三、OCR 技术的辨认成果

有利益的中央就有反抗，字符验证码诞生不久，就呈现了很多对其安全性进行评估的钻研。这里以 2003 年 Greg Mori 等人的尝试 [8] 为例，阐明一下过后获得的停顿。

Greg 等人钻研的指标是在存在对抗性烦扰的背景中进行物体辨认，辨认字符验证码的正确答案就是这类工作一个很好的例子。他们选取的指标就是下面介绍过的 Gimpy 和 EZ-Gimpy，采纳的辨认算法的外围也是下面重点介绍的 shape context 算法的变体，在 EZ-Gimpy 数据集和 Gimpy 数据集上别离达到 93% 和 33% 的通过率。他们应用了之前在 [9] 中提出的两阶段的物体识别方法：

1. 疾速修剪（Fast pruning）：在大量可能的候选形态（candidate shapes）中取出一个较小的子集
2. 具体匹配（Detailed matching）：在较小的子集上进行耗时然而准确的具体匹配
   其中在形态匹配的时候作者应用的是 shape context 算法的一个变体：

$$
\hat{h}_i(k) = \sum_{q_i \in Q} t_i, where Q = \{q \neq p_i, (q – p_i) \in bin(k)\}
$$

这个转换的起因也比拟好了解，当初 bin 里的值不是一个标量而是一个向量。
论文中的这种形态描述符称为「泛化的形态上下文」（generalized shape contexts）。
看一下利用这种形态匹配算法使准确率达到 93% 的 EZ-Gimpy 的辨认过程：

看待辨认的验证码图片，先利用 Fast Pruning 进行一系列的疾速检测找到图片中字母可能呈现的地位以及可能的字符（按相信率从高到低排序），而后在所有可能的字符串组合（用有向无环图示意）中，找到分数最高的那个候选单词，即是对这张验证码图片的辨认后果。
说到这里，对于 EZ-Gimpy 的两个重要特点必须要阐明：

• EZ-Gimpy 的验证码字符串都是字典中的常见英文单词
• 一共只有 561 个单词
  所以不难看出，EZ-Gimpy 试验如此高的准确率，相当一部分要归功于作者利用了该验证码的生成逻辑。然而依据 Luis von Ahn 的定义，验证码的要求之一是 Public（Greg 也在论文里提到该验证码的生成源码是公开的），而且过后 EZ-Gimpy 确实被 Yahoo 理论利用在注册账号、聊天室发言等多个场景中，所以这个试验的后果还是十分震撼的。

同样的 Gimpy 验证码也是应用的词典中的英文单词（850 个），然而 Gimpy 一张图片中有 5 组重叠在一起的扭曲单词对（但只有 7 个不同的单词），须要正确辨认出至多 3 个单词并输出，才可能通过。试验仍然利用“辨认 + 字典的形式，能够达到 33% 的准确率，看上去如同比第一个试验的成果差很多，然而从理论利用的角度来看，无非就是启动一个脚本变成三个脚本程序并行的区别而已，仍然能够在老本较低的状况下达到靠近 100% 的通过率。

结语

综上所述，能够看到简直是从诞生之初，字符验证码就遇到了诸多强劲的对手。然而，随着各类加强版字符验证码产品的问世，再加上黑灰产在新技术利用上的绝对滞后等因素，在过后，字符验证码的安全性还是能够失去肯定的保障，并作为性价比极高的产品而被宽泛应用。不过，道高一尺魔高一丈，AI 和验证码的正面交锋正在人们看不到的中央轻轻酝酿着。用不了多久，随着深度学习时代的到来，以 CNN 为代表的 AI 技术将迅速成为字符验证码的掘墓人。

欢送关注下篇：「验证码与人工智能的激荡二十年：全面瓦解」

[1] Ahn L V , Blum M , Hopper N J , et al. CAPTCHA: Using Hard AI Problems for Security[J]. Springer, Berlin, Heidelberg, 2003.
[2] Wikipedia – Optical character recognition
[3] Lecun Y , Bottou L . Gradient-based learning applied to document recognition[J]. Proceedings of the IEEE, 1998, 86(11):2278-2324.
[4] Burges C J C , Schlkopf B . Improving the Accuracy and Speed of Support Vector Machines[C]// Advances in Neural Information Processing Systems 9, NIPS, Denver, CO, USA, December 2-5, 1996. MIT Press, 1996.
[5] Oren M , Papageorgiou C , Sinha P , et al. Pedestrian Detection Using Wavelet Templates. 2000.
[6] Belongie, Serge, Malik, et al. Shape Matching and Object Recognition Using Shape Contexts.[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2002.
[7] Medium – Shape Context descriptor and fast characters recognition
[8] Mori G , Malik J . Recognizing objects in adversarial clutter: breaking a visual CAPTCHA[C]// IEEE Computer Society Conference on Computer Vision & Pattern Recognition. IEEE, 2003.
[9] Mori G , Belongie S , Malik J . Shape Contexts Enable Efficient Retrieval of Similar Shapes[C]// Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001. IEEE, 2003.