在写爬虫的时候难免会遇到验证码识别的问题，常见的验证码识别的流程为：
- 图像灰度化
- 图像去噪(如图像二值化)
- 切割图片
- 提取特征
- 训练
但这种方法要切割图片，而且破解验证码的重点和难点就在于 能否成功分割字符。
本文要介绍的算法 不需要进行图片切割，也不需要进行机器训练 ，这种方法就是模板匹配：将待识别的文字切割成一个个模板，在待识别的图像中去匹配模板。
这篇文章将分为两个部分：
第一部分介绍模板匹配的基本概念以及模板匹配的一种实现算法：快速归一化互相关匹配算法;
第二部分是一个具体实例。
1、 模板匹配
模板匹配是在图像中寻找目标的方法之一，目的就是在一幅图像中寻找和模板图像最相似的区域。
模板匹配的大致过程是这样的：通过在输入图像上滑动图像块对实际的图像块和输入图像进行匹配。
假设我们有一张100x100的输入图像，有一张10x10的模板图像，查找的过程是这样的：
从输入图像的左上角(0,0)开始，切割一块(0,0)至(10,10)的临时图像;
用某种方法得出临时图像与模板的相似度c,存放到相似度矩阵中(矩阵大小为91 x91);
切割输入图像从(0,1)至(10,11)的临时图像，对比，并记录到相似度矩阵;
重复上述步骤，直到输入图像的右下角。
最终得到一个相似度矩阵，找到矩阵中的最大或最小值，最大值(最小值)对应的临时图像即为与模板最相似的图像。
在步骤b中，求模板与图像的相似度有多种方法，如平均绝对差算法(MAD)、绝对误差和算法(SAD)、误差平方和算法(SSD)、归一化互相关算法(NCC)，本文使用的是归一化互相关算法。
2、 归一化互相关算法
什么是归一化互相关?
从几何图形上来看，空间中的两个向量，同方向平行时，归一化互相关系数为1，表示两个向量最相似，反方向平行时归一化互相关系数为-1，垂直时为0，表示最不相似(用互相垂直的三个向量来代表整个空间也是这个道理，垂直的向量之间不包含对方的信息，相关系数为0)，存在一定夹角时处于(-1，1)，是不是跟余弦函数很像，cos(0)=1,cos(pi/2)=0,cos(pi)=-1。就是这个样子的，相关系数可以看作是两个向量之间夹角的cosine函数。
在数学中是这么计算cosine函数的，假设两个n维向量X,Y，对应的坐标分别为(x1，x2，…xn), (y1，y2，…yn) 则：
(如果想要了解更多，请参考文献【2】)
但这是一维的，在模板匹配中要再加一个维度 (具体算法请参考文献【3】) ，简要说一下文献【3】的内容：如果直接计算二维相似度的话计算复杂度会非常高，文献【3】利用快速傅里叶变换与积分图像快速算法来降低计算复杂度。
接下来让我们看一个具体的应用。
3、 具体实例
模板匹配识别验证码的具体步骤为：
1. 找出图片中所有可能出现的字符，制作成模板集合
2. 图像灰度化
3. 图片去噪(二值化)
4. 模板匹配
5. 匹配结果优化
要识别的图片如下，以识别图片中的加字为例：
(image)
(template)
要从image中找到与模板最匹配的部分，Template图像是事先从image图像中截取的一部分。所用的为python模块skimage中的match_template方法，match_template方法使用的是快速归一化互相关算法 【2】 。