基于二叉树和Adaboost算法的纸币号码识别.pdf

第 3 1 卷 第 2期 2 0 1 1年 2月 计算机应 用 J o u r n a l o f C o mp u t e r Ap p l i c a t i o n s V0 1 31 No 2 Fe b 201 1 文章 编号 1 0 0 1 9 0 8 1 2 0 1 1 0 2 0 3 9 6 0 3 d o i 1 0 3 7 2 4 S P J 1 0 8 7 2 0 1 1 0 0 3 9 6 基于二叉树和 A d a b o o s t 算法的纸币号码识别 潘虎 陈斌 李全文 中国科学 院 成都计算 机应用研究所 成都 6 1 0 0 4 1 t t t i m m y h o t m a i l c o n 摘要 运用一种快速弱分类器训练算法和高速缓存策略来加速 A d a b o o s t 算法的训练 集成学习算法 A d a b o o s t 能够精确构建二分类器 运用二叉树型结构快速灵活地将纸币号码识别转化为一 系列的 A d a b o o s t 二分类问题 实验 结果证明 快速 A d a b o o s t 训练算法能加快训练速度 基于二叉树和 A d a b o o s t 的纸币号码识别系统具有较好的识别率 和处理速度 已经应用在点钞机 清分机和 A T M 中 关键词 A d a b o o s t 算法 快速 A d a b o o s t 算法 z X树 号码识别 中图分类号 T P 3 9 1 4 1 文献标志码 A Pa pe r c u r r e n c y n u m b e r r e c o g n i t i o n b a s e d o n b i n a r y t r e e a n d Ad a b o o s t a l g o r i t hm P A N H u C HE N B i n L I Q u a n w e n C h e n g d u b s t i t u t e o f C o m p u t e r A p p l i c a t i o n C h i n e s e A c a d e m y o f S c ie n c e s C h e n g d u S i c h u a n 6 1 0 0 4 1 C h i n a Ab s t r a c t A f a s t w e a k c l a s s i f i e r t r a i n i n g a l g o r i t h m a n d a f a s t c a c h i n g s t r a t e g y we r e u s e d t o a c c e l e r a t e Ad a b o o s t t r a i n i n g I nt e g r a t e d l e a r ni n g a l g o rit hm Ad a b o o s t c a n a c c u r a t e l y c o n s t r u c t t wo c l a s s i fie r s S O p a p e r c u r r e nc y n umb e r r e c o g n i t i o n wa s f o r mu l a t e d a s a s e r i e s o f Ad a b o o s t t wo c l a s s c l a s s i fic a t i o n p r o b l e ms q u i c k l y a n d fle x i b l y b y u s i ng bi n a r y t r e e s t r uc t u r e Th e e x p e r i me n t a l r e s u l t s d e mo n s t r a t e t h a t t h e f a s t Ad a b oo s t t r a i n i n g a l g o r i t h m c a n s p e e d u p t h e t r a i n i n g a n d t h e p a p e r c u r r e n c y nu mbe r r e c o g n i t i o n s y s t e m b a s e d o n bi na ry t r e e a n d Ada bo o s t a l g o r i t h m h a s g o o d r e c o g ni t i o n r a t e a n d pr o c e s s i n g s p e e d a n d i t ha s wi d e l y be e n u s e d i n c u rre n c y c o u nt e r c a s h s o e r a n d ATM Ke y wo r d s Ad a b o o s t a l g o r i t h m f a s t Ad a b o o s t a l g o r i t h m b i n a r y t r e e n u mb e r r e c o g n i t i o n 纸币是市场上一般等价物的主要形式 它在人们的社会 生活 中起着不可替代的作用 纸币上的号码是 纸币的非常重 要的标识之一 可以用来识别纸币的身份 如果能开发一种 智能纸币号码识别系统 自动记录下通过点钞机的纸币的号 码 并存储备案 就可以实现对纸币号码的便捷管理 这就要 求所采用的识别算法既有很高的识别率 又具备足够快的识 别速度 A d a b o o s t 算法是一种构造准确分类器的学习算法 预 先把负样本和正样本加入待学习样本 通过机器学 习 将一系列 比随机预测略好的弱分类器线性组合为识别能力很强 识别范围 更广的强分类器 A d a b o o s t 广泛地应用在人脸检 测 汽 车牌 照号码快速定 位 等领域 文献 3 将A d a b o o s t 成功用于手写体数字的识别 A d a b o o s t 的训练随着样本的增加会非常耗时 常见的处理方法是 对训练样本进行数据降维处理 文献 4 用到的随机投影和主 成分分析 P r i n c i p a l C o m p o n e n t A n a l y s i s P C A 会 降低分类器性 能 快速 阈值选择和高速缓存策略能够有效缩减 A d a b oos t 的训 练时间 xX树型分类树结构简单 能够充分发挥 A d a b o o s t 解决 二分类问题的优势 对于 类分类问题只需构造 k 一 1 个A d a b o o s t 分类器 将两者结合起来应用到纸币号码的识别 能有效提高计 算机自动号码识别的速度和准确率 l A d a b o o s t 算法简介 1 1 弱可学 习定理 1 9 8 4年 V a l i a n t 提 出机 器学 习 的另 类理 念 即学 习模 型无需绝对精确 只需概率近似正确 P r o b a b l y A p p r o x i ma t e l y C o r r e c t P A C 即可 1 9 9 0年 S c h a p i r e 通过构造性方法证明 了弱学习算法和强学习算法的等价性 即可以将若干个略好 于随机猜测的弱学习算法提升为强学习算法 而不必直接去 找通常情况下很难获得的强学习算法 这就是著名的弱可学 习定理 1 2 A d a b o o s t 算法 弱可学 习定 理是 B o o s t i n g算法 的理论 基础 1 9 9 0年 S c h a p i r e 提出了B o o s t i n g 算法 该算法的基本思想是找出若干 个精度比随机预测略高的弱学习规则 再将这些弱学习规则组合 成一个高精度的强学习规则 在众多的 B oos t i n g 算法中 F r e u n d 和S c h a p i r e l 在1 9 9 5年提出的A d a b o o s t 算法最具有实用价值 也 是目前研究的热点 A d a b o o s t 算法的美妙之处在于它使用加权 后选取的训练数据代替随机选取的训练样本 将弱分类器联合起 来 使用加权的投票机制代替平均投票机制 A d a b o o s t 算法被 V i o l a 和 J o n e s 成功运用于人脸检测 其算法步骤如下 1 给 定 训 练 样 本 Y Y Y Y E 一1 1 其中Y 一1 代表负样本 Y 1 代表正样本 2 初始化权值 对于负样本 其权重 l 2 m m为负 样本个数 对于正样本 其权重W 1 2 r b m n m为正 样本个数 3 F o r t 1 2 归一化权值 W 一 W 确 保W 服 从 一 个 概 率 J 1 分布 对每一个特征 训练一个弱分类器 其误差由样本 收稿 日期 2 0 1 0 0 8 1 6 修回 日期 2 0 1 0 1 0 1 1 作者简介 潘虎 1 9 8 6 一 男 湖南岳阳人 硕士研究生 主要研究方向 图像处理 模式识别 陈斌 1 9 7 0一 男 四川广汉人 研究员 博 士 主要研究方向 图像处理 模式识别 工业视觉 李全文 1 9 8 4一 男 广西桂林人 硕士研究生 主要研究方向 图像处理 模式识别 第2期 潘虎等 基于二叉树和 A d a b o o s t 算法的纸币号码识别 3 9 7 分 布 的 权值W 来 衡量 q I h j x 一 Y I 挑选具有最小误差 的分类器 h a r g rai n 8 更新样本的权值 W r 6 1一 当样本 被正确分类时 0 否则 s 1 4 最终 的强 分类 器为 1 r 一 s i g n I 一 f 1 其中O l l o g p 2 纸 币号码识别 2 1预 处 理 本系统做的预处理是将在清分机 C I S灯光下获取的纸 币 灰度图像进行搜边定位 倾斜校正 号码区域定位 分割得到号 码图像 如图 1 所示 然后进行单个字符的分割得到单个号码 的灰度图像 最后对单个字符归一化 其中阿拉伯数字图像全 部归一化到 1 9 2 9 英文字母 图像全部归一化到 2 3 3 5 A d a b o o s t 是一种基于集成学习方法训练出来的分类器 具有很 强的学习泛化能力 可以直接应用于灰度图像 字符不需要二 值化 和传统的模板匹配 字符穿刺等方法相比 不仅节省了时 间 也避免了对字符轮廓可能造成的偏差 降低了误识率 图 1 纸币号码图像 2 2 弱分类特征的选取 特征的选择和提取是纸币号码识别的重要步骤 纸币号 码由2个英文字母和 8个阿拉伯数字组成 V i o l a将很简单 的 H a a r L i k e 矩形特征成 功应 用于 人脸检 测 纸 币号码 字 符结构简单 特征提取用到几种常用的 H a a r L i k e矩形特征 如 图 2所示 分别为 2 一 矩形特征 3 一 矩形 特征和 4 一 矩形特征 l 口 a b c d 图 2 H a a r L i k e 矩形特征 对于每个样本 其矩形特征对应有一个特征值 2 一 矩形 特征和4 一 矩形特征的特征值为所有白色矩形区域 的灰度值 的和减去所有黑色矩形区域的灰度值的和所得到的差 3 一 矩 形特征的特征值为所有白色矩形区域的灰度值的和减去所有 黑色矩形区域的灰度值的和的2倍所得到的差 特征值的计算是通过积分图像快速实现的 对于一幅灰 度图像 它的积分图的定义为 y ii x y i x Y 1 其中 i Y 为像素值 将 图像所有像素的位置的积分图 用一个二维数组存储 则图2中矩形 D内的灰度值的和可以 由积分图上的四点的坐标快速计算 出 不妨设图 3中 1 2 3 4共 4个点 的坐标分别 为 y Y 和 Y 4 则矩形 D 内的灰度值的和为 i i Y 一i i x y 一 i i 弘 Y 3 i i Y 2 3 弱分类器 的构 造 给定一个特征集和带标记的正负样本集 存在许多将它 们分类的算法 采用最简单的单阈值加偏置值的函数来构建 的弱分类器 具有很好的对称性 对于第 个特征 和样本 其对应的弱分类器 h 定义为 s i g n 一p 其中 为特征值 为阈值 偏置值P 1 输入样本 为一幅数字图像 一个特征 对应一个弱分类器 该 弱分类器结构具有对称性 即当 0 j 确定 且偏置值 P 1和 P 一1时 分类器 的误差之和为 1 2 4弱分类器 的快 速训练 A d a b o o s t 是一种统计学习算法 需要大量的样本进行训 练 一个弱分类器的训练就是寻找最优阈值 的过程 一轮 分类器的训练过程就是寻找最优弱分类器 的过程 训 练所用的阿拉伯数字图像全部归一化到 1 9 2 9 将 图2中的 每种 H a a r L i k e矩形 特 征用 五元 组 y W h s t y l e 表 示 记 录矩形特征左上角坐标 宽度高度和类型 根据组合原理 穷 举计数所有的五元组 得到 1 9 X 2 9的数字图像 中 H a a r L i k e 特征的总数 目高达 1 0 3 0 8 0 英文字母图像全部归一化到 2 3 3 5 特征数 目更加巨大 如果按照传统的 A d a b o o s t 弱分类 器的训练算法 阈值的计算和选择将导致训练极其地耗费时 问 利用弱分类器结构的对称性 J 通过对特征值预排序并 缓存可以实现弱分类器的快速训练 具体算法流程如下 1 输入 个 训练集 Y Y Y Y 一1 1 权值为 W 矩形特征 2 将特征 在所有样本的特征值 将它们从 小到大排序 得到一个次序表 f l 2 3 初 始 化p 1 W 即 阈 值 Yi I 为 时弱分类器 的误差 4 f o r 1 2 n 一1 d o i f Y 1 t h e n L 1 占 f 一 k e l s e g I V i k e n d i f e n d f o r 5 f a r g m a x 7 i k 0 0一 j 一 6 i f 1一s 一t h e n 输出 弱分类器 s i g n 0 一 e s e 输出 弱分类器 s i g n 一0 一 预先对特征值的排序可以在弱分类器训练过程中充分利 用弱分类器结构的对称性 计算误差时可以利用上一次的结 果 在每轮 A d a b o o s t 训练中 样本 Y 本身并没有 改变 更新 的只是 样本 的权 重 W 对 于每 一个 特 征 样 本特征值和排序结果在训练过程中也不会发生变化 因此在 第一次计算特征值和对特征值排序时 对每个特征的特征值 的排序结果 新建一个 M N的序列表 G M为所有特征数目 N为样本总数 此后的迭代训练都直 接从缓存 中读取特征值序列 进行阈值选择计算 除了第一 次迭代需要消耗较长时间 之后每次迭代只需花费较少时间 以空间换时间的高速缓存策略是提升特征选择速度的关键 在算法 时间复杂度上 原米 法 训练的时 问复杂度为 0 l o g N 使 用 高 速 缓 存 策 略 训 练 的 时 问 复 杂 度 为 3 9 8 计算机应 用 第 3 1卷 0 N M l o g N 为迭代次数 2 5 二叉树型多分类结构 模式识别问题归根结底就是分类问题 由于纸币号码是 字母的数字的组合 类 别较 多 A d a b o o s t 用 于多类 问题 时 思 想还是转化为两类问题 以A d a b o o s t 分类器为节点的二叉树 分类结构具有如下优势 A d a b o o s t 解决二分类问题已经非常 成熟 在人脸检测等领域 的应用都取得 了极 大的成功 因此在 此基础上实现的二又树形多重分类器也较容易得到很高的识 别率 同时二叉树型结构直观 便于理解 树形结构也在一定 程度上减少 了比较的次数 节 约了时间 对于阿拉伯数字 0 9的识别 建立二叉树分类结构 每 个节点处设置一个 A d a b o o s t 分类器 共需要设计 9个分类器 如图4所示 号码识别的过程就是从树根到任意叶子节点的 分类过程 该二叉树型结 构的设计 也并不 是唯一 的 主要是 依据一些先验知识 实验结果表明 这种结构模型很好地利 用了先验知识来提高分类器性能 图 4 阿拉伯数 字二叉树分类结构 对于英文字母的识别 同样依据一些先验知识以及字符 的结构 特征差异 如字符 4个 方向 圆弧 的饱 满程度 对纸 币号 码 里 的 2 5个 英 文 字 母 人 民 币 编 码 冠 字 不 包 括 V 用 A d a b o o s t 分类器分成 2个子树 左子树节点为 B c D E G O Q S Z 其对应的二叉 树分类 结构 如 图 5所示 右子树 节 点为 A F H I J K L M N P R T U W X Y 其对应的二 叉 树分类结 构如图 6所示 图 5 英文字 母左子树 二叉树分类结构 图6英文字母 右子树二叉树分类结构 3 实验结果 训练样本集 是 由高 速纸 币清 分 机 C I S白光扫 描通 过 的 1 0 0元人民币获取的 包括 2 1 1 6个阿拉伯数字 5 8 5 8个字母 运用快速 A d a b o o s t 弱分类器训练算法和缓存策略来训练每 一 层的A d a b o o s t 强分类器 每一层训练 3 5个弱分类器 在 I n t e l P e n t i u m E 5 3 0 0 2 6 G H z 机器 和 V C 2 0 0 8编译环 境下 分 别对 O p e n C V训练算法 O p e n C V采用的是原始 A d a b o o s t 训练 算法 与改进后的训练算法在每一层训练所需要的时间进行 了测试对比 结果如表 1 改进后的训练策略使 A d a b o o s t 的训 练时间大大缩减 表 1 O p e n C V和快速 A d a b o o s t 的训练 时间对 比 正样本数负样本 数 O p e n C V方法 时间 mi n 快速算法时间 rai n 测试用的纸币号码单个字符是由清分机 C I S白光实时对随 机高速通过的 1 3 8 4张人民币扫描 并经过一系列预处理获取的 测试中阿拉伯数字的识别率非常高 仅有3个识别错误 全部是 把 5 错识别为6 英文字母的识别率因其二叉树分类结构更加复 杂而略有降低 纸币号码的识别率和识别速度如表 2 所示 表 2纸币号码 识别率和 平均识别时 间 实验所采用的基于 A d a b o o s t 的二叉树型多分类器对纸 币号码的识别率很高 单个字符的平均识别时间在 3 4 m s 能 够满足工业上实时应用的要求 4 结语 本文提出的基于二叉树和 A d a b o o s t的纸币号码识别系 统对纸币号码的实时识别取得了非常理想的识别效果 实践 证明 快速阈值选择和缓存策略能够加速 A d a b o o s t 训练 A d a b o o s t 方法可以充分发掘样本间的差异 产生高精度的二 分类器 二叉树分类结构能够充分发掘A d a b o o s t 的泛化能力 灵活地将多分类问题转换为一系列简单的二分类问题 沿着 此应用思路 还可以把 A d a b o o s t 学习算法应用到更多的识别 检测等领域 参考文献 1 V I O L A P J O N E S M R o b u s t r e a l t i m e f a c e d e t e c t i o n J I n t e r n a t i o n a l J o u r n a l o f C o m p u t e r V i s i o n 2 0 0 4 5 7 2 1 3 7 1 5 4 2 潘石柱 殳伟群 王令群 基于 A d a b o o s t 的汽车牌照快速定位 J 计算机工程 2 0 0 6 3 2 1 2 1 8 7 1 8 8 3 赵万鹏 古乐野 基 于 Ad a b o o s t 的手 写体数字识 别f J 计算机 应用 2 0 0 5 2 5 1 0 2 4 1 3 2 4 1 7 4 P AU L B A T H I T H A N G MUR T Y M N S p e e d i n g u p A d a B o o s t c l a s s i fi e r w i t h r a n d o m p r o j e c t i o n C 7 t h I n t e r n a t i o n a l C o n f e r e n c e o n Ad v a n c e s i n P a t t e r n Re c o g n i t i o n W a s h i n g t o n DC I EEE Co m p u t e