基于AdaBoost的车牌字符识别模型研究

作者：李晶、陈媛媛　　单位：中北大学信息与通信工程学院、山西省光电信息与仪器工程技术研究中心　　转载：仪器仪表学报

1、引言

　　车牌字符识别是车牌识别系统中重要组成部分之一，是模式识别的一个应用领域，车牌字符样本集是字符集合的一个有限子集，包括汉字约50个，字母A– Z，数字0–9，属于特定的有限字符集识别问题。目前最常用的车牌字符识别方法主要有模板匹配法、基于字符特征的识别方法和神经网络法等。模板匹配法简 单，实用于一些特定情况，如尺寸固定、车牌位置水平不发生旋转等情况，当车牌字符图象轻微扭曲变形、笔画粗细不均甚至缺损断裂时，容易产生误识别。文献1 作者把K近领法用到车牌字符识别中，K近领法是典型的统计学习方法，在分类领域中经常用到，主要思想是先对待识别字符进行特征提取、建库，然后计算待测样 本的特征与模式库中特征的相似度，最后根据判别函数来识别待测样本属于哪一类。基于字符特征的识别方法主要有PCA法和ICA法，文献2就是采用了独立分 量法（ICA）对车牌字符进行识别。神经网络方法具有较强的并行数据处理能力、容错能力和泛化能力。但是神经网络是一种弱学习算法，分类精度也不高，文献 3针对这一弱点提出了一种改进的BP神经网络方法用于车牌字符识别中。

　　Boosting是一种框架算法，它主要通过对样本集的操作来生成一系列分类器。理论证明，只要每个弱分类器分类能力比随机猜测略好，当弱分类器个数趋向于无穷时，强分类器的错误率将趋于零^[4]。

　　基于以上分析本文提出一种基于AdaBoost的车牌字符识别方法，该方法把BP弱分类器置于AdaBoost框架中，通过AdaBoost框架对样 本的操作，Ｔ次迭代后，产生ｎ个分类器，然后AdaBoost算法将这ｎ个分类器进行加权融合，最终产生一个分类器，实验证明该分类器具有较高的识别率。

2、Boosting算法

2.1 基本概念

　　分类器（classifier）：在已有数据的基础上学会一个分类函数或构造一个分类模型。该函数或模型能够把数据库中的数据记录映射到给定类别中的某一个，从而可以应用于数据分类或预测。分类器实质是一个数学模型。

　　训练集（training set） 由一组数据库记录或元组构成，每个记录是一个由有关字段值组成的特征向量，训练集是构造分类器的基础。

　　测试集（testing set） 由已知属性的样本组成的集合，作为测试过程的输入数据。
PAC模型 Probably Approximately Correct，一种近似学习模型^[5]。

　　弱分类器（weak classifier） PAC学习模型中，对一定分布的训练样本给出弱假设判断（识别错误率小于1/2，即准确率仅强于随机猜测）。

　　强分类器（strong classifier） PAC学习模型中，若存在一个多项式级的学习算法来识别一组概念，且能够给出稳定的高识别率的分类器（识别准确率很高并能在多项式时间内完成）。

2.2 Boosting算法

　　Boosting是提高预测学习系统预测能力的有效工具，由Freund和Schapire于1990年提出，其代表算法分为AdaBoost和Boost-by-majority两个系列^[6]。 Boosting算法通过对训练集操作产生多个假设，建立分类器集合。AdaBoost在训练集上维护一套概率分布，通过成员分类器在训练集上的错误率来 调整训练集上的概率分布。权重改变的作用使得被误分的例子上放置更多的权重，在分类器正确的例子上减少其权重，最后通过每个分类器的加权投票建立最终分类 器。Boosting算法一般用于提高不稳定的分类器的性能。

　　Boosting算法速度快，简单，易于编程，除了迭代次数 外不需要调整参数。它不需要弱分类器的先验知识，因此可以灵活地和任意方法结合寻找弱假设。

3、AdaBoost算法分析

3.1 AdaBoost算法

　　AdaBoost（Adaptive Boost）算法是Freund和Schapire于1995年提出的^[7]，该算法是Boosting家族算法中具有代表性的算法，其基本思想是：

　　⑴给定弱分类器和训练集 ，ｘ_i ∈X表示样本集合，该集合带有类别标号，，此时表示二值分类问题，是多类问题的扩展，+1表示正例，-1表示反例；

　　⑵初始化，训练集初始分布为１/m，每个训练例的权重为1/m；

　　⑶调用弱分类器，对训练集进行训练，得到弱假设序列：h_i；
　　
　　⑷经过Ｔ次迭代，每次迭代根据训练错误率更新训练集权重，给错误分类的训练例赋予较大权重，此后按照新的分布进行训练；从而得到新的假设序列h1,h2...ht。

　　⑸经过带权重的投票方式最终得到一个假设Ｈ。

　　带权重的投票方式可以自动调整Ｈ的精确性，给定弱分类器的前提下，随着迭代次数的增加，最终得到的假设 的错误率按照指数规律递减^[7]。

3.2 算法理论分析

　　Freund和Schapire证明了AdaBoost生成的最终分类器的训练误差最大为^[8]：

（1）

　　其中ε_t为h_t的训练误差，，公式（1）表明只要弱分类器稍好于随机猜测，训练误差将随 按照指数规律递减。AdaBoost之前的Boosting算法要求预先知道γ_t的下限，在实际问题中这一点很难做到。AdaBoost算法没有此要求。

　　Freund和Schapire还利用VC维从训练误差角度分析Boosting的泛化误差（generalization error），VC维是学习算法的复杂度以及学习能力的度量^[8]，假设训练集中样本个数为ｍ，弱分类器的VC维为ｄ，迭代次数为Ｔ，则泛化误差最多为：

（2）

　　表示对训练集的经验概率。公式（2）说明若训练迭代次数过多，Boosting将导致过适应即退化现象（over-fitting）。因此必须恰当选择迭代次数Ｔ。

4、车牌字符识别系统建模

　　车牌字符识别是车牌识别系统中的核心内容，一般车牌字符识别包括如下步骤：首先对采集到的车牌图象进行定位、预处理、字符分割以及归一化处理等，每个 字符变成大小相同的字符，然后在归一化后的二值图象中进行特征提取，属性优化，最后用优化后的属性作为经AdaBoost提升后的BP神经网络的输入，构 造神经网络字符分类器。字符识别原理如图1。

图1 字符识别原理

4.1 提取字符特征

　　字符特征的提取有多种方法，目前常用的方法有：逐像素特征提取法、骨架特征提取法、垂直方向数据统计特征提取法、13特征点提取法、粗网格特征提取法 等。本文采用粗网格特征提取法对归一化的二值图象进行特征提取。首先把字符平均分成16×16个网格，再把这16×16个网格的字符平均分成16个4×4 的象素大小的子图象，统计每一份内黑色像素点的个数，而每个网格反映的是字符的部分特征，所以需要把所有网格组合起来作为字符的统计特征，最后得到 16×16维的字符特征。然后以这16个特征作为条件属性，字符的种类作为决策属性。条件属性集为，属性值集合为，决策属性集为，即字符的真实值。决策表构造好之后用粗糙集对属性进行约简、优化，限于篇幅不再赘述。

4.2 AdaBoost算法提升BP算法

　　具体算法如下^[7]　：

　　输入 训练集，由车牌字符属性构成

；

　　类标号：，训练集分布Ｄ，迭代次数Ｔ。

　　弱分类器：BP神经网络。

　　初始化 赋予训练集初始分布；

　　For

　　Step1：调用BP弱分类器，使用分发权值向量Ｄ_t训练BP弱分类器，得到假设 ；

　　Step2：计算h_t的错误率：

（3）

　　若ε_t＞0.5，则设T=t-1并退出循环。

　　Step3：置（4）

　　Step4：计算新的权重向量：

（5）

　　输出　假设：

（6）

　　没有先验知识的情况下，初始分布为等概率分布，分发权值向量Ｄ_t总和为1，ω_t为分类器权值，准确率越高分类器权重越大。

5、字符识别实验及结果

5.1 实验设计

　　本实验分为两步：即训练和识别。首先用AdaBoost算法对BP分类器进行训练，经过Ｔ 次迭代后得到分类规则Ｈ，然后用Ｈ对测试集分类，给出分类结果。具体方法如下：

　　训练阶段：⑴训练集即车牌字符属性集作为输入，ｍ为训练样本集样本个数；⑵初始化权重分布；⑶用BP神经网络训练得到弱假设h_t；⑷计算h_t的错误率：⑸根据错误率调整权重；⑹计算新的权重；⑺重复⑶～⑹ T次；⑻得到新规则h₁,h₂,...,h_t；⑼采用权重投票方式得出最终分类规则H。

　　识别阶段：⑴测试集也为车牌字符属性集作为输入ｎ为测试集样本个数；⑵用上述训练得到的规则Ｈ进行识别；⑶得出识别结果。

5.2 实验结果

　　实验中，车牌字符样本来自于随机拍摄，样本总数为300幅，训练样本为200幅，测试样本为100幅。训练次数为1500次，网络的权值和阈值为随机 选取。BP网络采用三层结构；输入层、隐含层、输出层，各层的激活函数依次为双曲正切S型函数tansig.m和线性函数purelin.m。对优化后字 符属性做了如下实验：⑴BP神经网络识别；⑵BP算法作为弱分类器用AdaBoost提升后进行训练识别的方法，⑶模板匹配法作为弱分类器用 AdaBoost提升后进行训练识别的方法。

　　实验目的：⑴比较用AdaBoost提升前、提升后识别准确率的变化；⑵比较不同弱分类器用AdaBoost提升后识别准确率的变化。

　　实验前每幅车牌均经过定位、预处理、分割和归一化等处理。然后分别经过上述三种不同方法构造的分类器，实验结果如表1：

表1 实验结果

　　从表1的识别结果可见，只用BP神经网络得到的识别率是最低的，而且训练迭代次数较多，说明用AdaBoost算法提升弱分类器比单一分类器分类效果 好，而后两种方法中BP神经网络作为弱分类器比模板匹配作为弱分类器效果好，这说明了运用AdaBoost框架算法最终识别效果还和弱分类器的选择有关， 另外从平均识别时间角度看，本文提出的算法识别时间是最短的。

6、结论

　　AdaBoost框架算法具有速度快、简单等优点，除了迭代次数 外不需调整参数，不需要弱分类器的先验知识，可以灵活地与任意算法结合寻找弱假设，给定足够数据以及一个中等精度的弱分类器，它可以把该弱分类器提升为强 分类器，从而提高识别效果，但是AdaBoost框架算法也有不足之处，当样本存在较大噪声或者有错误样本时，训练所得规则偏向这个假样本，进而导致分类 器对其它正常数据不能准确分类，发生退化现象，如何避免这种情况发生，是今后的工作重点之一。

参考文献

　　[1] 杨晓敏,何小海,吴炜,陈默,薛磊.一种基于相似度判据的K近邻分类器的车牌字符识别方法[J].四川大学学报(自然科学版),2006,43(5):1043-1047
　　[2] 李旻,吴炜,杨晓敏,周红,龙建忠.基于独立分量分析的车牌字符识别[J].四川大学学报(自然科学版),2006,43(6):1259-1263
　　[3] 胡乃平,王丽,周艳平.一种改进的BP算法及其在车牌识别中的应用[J].微计算机信息,2006,22(9-1):313-314
　　[4] Lebanon G., Lafferty J., Boosting and maximum likelihood for exponential models [A]. Advances in Neural Information Processing Systems[C],2001
　　[5] Valiant L G., A Theory of the Learnable. Communication of the ACM 1984,27(22):1134-1142
　　[6] Schapire R. E., The Strength of weak Learnability. Machine Learning, 1990,5(2):197-227
　　[7] Freund Y., Schapire R. E. A., Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting Journal of Computer and System Sciences,1997,55(1):119-139
　　[8] Schapire R. E., Freund Y., Bartlett P., Lee W. S., Boosting the Margin: a New Explanation for the Effectiveness of Voting Methods The Annals of Statistics,1998,26(5):1651-1686