数字验证码识别算法的研究和设计王虎, 冯林, 孙宇哲Wang Hu, Feng Lin, Sun Yuzhe大连理工大学大学生创新院，大连116023Institute of University Students’ Innovation, Dalian University of Technology, Dalian 116023, ChinaE-mail: wlys111@Research and Design of Digital character-based CAPTCHA RecognitionAbstract:CAPTCHA Recognition can be used in multi-send technology. Digital character-based CAPTCHA Recognition, which is foundation of pattern recognition research, is a kind of OCR. In this paper, we proposed a CAPTCHA Recognition System based on simple distortion and its architecture is template matching. Hilditch thinning algorithm, circle structure searching algorithm and dynamic template analyzing algorithm is chose and the weigh of template is also used to improve the recognition accuracy. The advantage of the system is that the recognition precision is perfect.Key words:Template matching, Weighted Template, dynamic template, grid feature, crossing points feature摘要:验证码识别技术可以用于网站的群发软件，数字验证码识别是光学字符识别(OCR)的一种，是进行模式识别研究的基础。
论文提出了以简单变形的数字字符为理论研究素材，将模板匹配作为基本框架的验证码识别系统。
系统采用图像的Hilditch细化算法、环结构的搜索算法、活动模板分析算法，加入模板分量的权值。
其优点在于能够对特定数字验证码精确识别，实验中识别准确率基本达到100%。
关键字:模板匹配，加权模板，活动模板，网格特征，交叉点特征文章编号：文献标识码：A 中图分类号：TP391.43引言目前，网络上出现了很多以图片形式出现的基于文本的验证码。
所谓验证码，就是将一串随机产生的字符，生成一幅图片，图片里随机的加入一些像素干扰、颜色干扰和形变干扰等等，以达到防止恶意注册等目的。
有的验证码是无像素干扰的、大小固定的、质心位置居中，含有形变干扰的数字字符，我们称之为简单变形体。
反之，我们称加入了更多干扰的字符为复杂变形体。
验证码千变万化，而当前的识别系统都具有很强针对性，只能够识别一种类型的验证码，而且验证码的技术不断发展，出现了更加复杂的基于图像的验证码系统[5]，并且目前人工智能（机器智能）还远未赶上人类智能，但是对于给定的验证码系统，在获知其特点之后，基本能够以一定的准确率进行识别[6、7]。
基金项目: 国家自然科学基金( the National Foundation of China under Grant No.10471051 )。
作者简介: 王虎(1984-),学士,研究方向:计算机图形处理,模式识别与智能控制; 冯林(1969-),博士,教授,研究方向:图像压缩、配准及融合和演化算法; 孙宇哲(-),硕士,研究方向:.目前，在公开的验证码识别算法中，只有一些简单的、识别率低的识别方法，且缺乏系统性，这不利于对日新月异的验证码的识别，因此我们需要一个系统、高准确率的算法。
本文讨论了图像的模板匹配算法，细化算法，网格特征、交叉点特征[1]，并由此构架识别算法的基本框架。
为了提高识别准确率，使用改进的活动模板部分结构分析算法[2]，减弱了字符形变对识别系统的干扰；提出一种能较大地增强模板区分能力的加权模板。
1. 数字验证码识别算法的识别对象是网络上较为常用的简单变形体数字验证码，验证码样本取自于动网论坛。
这种验证码没有像素和颜色干扰，也没有字符粘连和重叠，因此仅需要进行形变字符的识别。
图1展示了十个数字字符两种不同程度形变的样本：图 1 数字验证码样本将四个字符为一组的验证码二值化后存入处理数组中，该数组就保存了待识别数字的外部形状特征，所以算法的关键就是通过处理数组中的形状特征，计算获取最接近的数字字符。
系统的识别过程如图2所示：图 2 识别系统及字符特征统计2. 模版匹配和加权模板定义数字字符图像模板为：数字图像已知的形状特征量化值的数学期望。
例如，对某特定数字图像进行网格特征分析，某一格的黑点数目大致服从正态分布，其均值即为一个模板量。
字符图像有多种形状特征，因而模板是由一个N维向量构成。
每个形状特征都有一定的可信度，例如，统计数字“1”的横向扫描时只有一个交叉点的行数，该值比较固定，样本方差小，具有较高的可信度；数字“2”的下部变形较大，而且位置不定，网格特征分析时，黑点数目的样本方差大，因而此模板分量不可信。
特征权值就是某形状特征的可信度的量化，可信度高则权值高，可信度低则权值低。
模板向量的每个分量均对应一个权值，从而每个字符对应一个N 维的权值向量，由这两个向量共同决定该数字的特征模板，这两个向量便组成了加权模板。
加权模版可以提高某特殊外形特征的权重，降低不可信外形特征的权重，从而更加准确的获得识别结果。
此外，为了达到字符的总体均衡，也需要进行权值调整。
模板匹配时，由待识别的字符x 特征向量α和某个字符i N 的模板向量β与权值向量γ即可计算两者之间的差异度。
计算公式如下：()()∑=⨯-⨯-=nk k k k k k i Diff 1γβαβα， n 为模版向量的长度。
10个模版对应10个i Diff 值，其中最小值对应的数字即可作为x 的识别结果。
模板分量的权值j γ是基于统计学方式计算得出的。
在随机的N 个验证码样本(4*N 个字符样本)中，模板长度为M 的字符图像有如下几个参数：各个字符的个数)9,,1,0( =i N i ，各个字符某模板分量的样本均值),,1,0(M j Y j =、样本方差),,1,0(S 2j M j =，不同字符的同一分量样本均值的方差),,1,0(S 2j M j ='。
其中，j Y 是该模板分量的期望值，作为某个字符模板分量j 的数值j β；2j S 展示了对应模板分量度对于该字符的可信度，是确定j γ的主要依据，2j S 越小，可信度越高；2j S '展示的是该模板对各个字符的区分能力，2j S '越大，模板的区分能力越强，该数值用于调整模板分量权值。
下面三个表格展示了模板分量权值的计算方式（0-4五个数字字符的六个分量）：根据表格 3，表格 1到表格 2的影射：模板法是本项目算法的基本框架，将各个数字字符的外形特征都统一到模板内部，然后进行一致的运算，降低了程序的复杂度，提高了开发效率。
那么，如何来构造一个好的模板呢？3. 细化图像细化就是把图像中的笔画细化成单像素的线条。
它作为一种图像预处理技术出现，目的是提取源图像的骨架，即将原图像中线条宽度大于1个像素的线条细化成只有一个像素宽，形成“骨架”，形成骨架后便于分析图像特征，例如，进行网格特征统计、活动模板分析等。
我们采用的是比较成熟的Hilditch细化算法。
4. 网格特征模板网格特征模板是第一个外形模版，也是最简单、最基本的模板。
先将20*20的图形分成4*4块，每块5*5个像素，然后统计各个网格中黑点个数。
图像的网格分块如图 3所示：图 3 细化字符以及原始字符图像分块由于字符的基本形状一定，并且质心不动，字符的笔划经过每个网格的笔划数大致保持稳定。
细化后的笔划是由单像素构成，各个网格的黑色像素不会受字符笔划的粗细而变化。
对于模板期望值的计算，采用了统计的方法：选取1000个样本，计算各个字符在每个网格的平均黑点数，此数值即所求期望值。
5. 活动模板对于部分数字，活动空间较大。
经过形变后其某部分结构不定于某网格，即网格特征模板的可信度较低。
例如数字"1"，常常以正斜或者反斜的形态出现，倾斜角度也很不一定，因此容易出错。
本算法所使用的活动模板，是用一个小方块包围字符图形的某一部分，例如上、中、下部。
虽然某些字符整体形变大，但是部分的形变却很小，从而具有较大的参考价值。
例如，"7"的下部是很简单的一条斜线，可以用于区分数字"1"和数字"2"，如图4所示：图 4 部分结构示例部分结构A的参数有，黑点个数，不均衡度等。
不均衡度可分为水平不均衡度和垂直不均衡度，水平不均衡度就是A中各黑点到水平中心的坐标差值求和。
A的水平不均衡度计算方法如下：a) 计算A 的水平中心位置；b) 对A 中各个黑点与水平中心的距离算术求和（规定中心左边的黑点距离为负）。
计算公式：∑-=)(x ix z c Balance ，其中ix c 为A 中第i 个黑点的横坐标，x z 为中心的横坐标。
垂直不均衡度类似于水平不均衡度，即A 中各黑点到垂直中心的坐标差值求和。
6. 交叉点特征模板实验中，我们发现分块黑点计数模板对于"2"、"3"、"5"、"7"，"1"、"2"、"7"和"3"、"5"、"6"、"9"这三组数据区分不到位。
分析这些数字字符图像的特点，我们发现，使用直线切割字符图像的同一坐标位置所得的交叉点数目是不同的。
沿第一组数据的纵向某两坐标进行切割，所得的交点数目不同，如图 5所示：图 5 纵向两列交叉点数7. 环结构由于字符"6"、"8"、"9"图形相近，且字符"6"、"9"的部分变形体非常接近于字符"8"，以至于上述方法容易出错。