（电路与系统专业论文）智能视频监控中的行人检测与跟踪算法研究.pdf

摘要 摘要 智能视频监控是计算机视觉领域一个新兴的应用方向，是计算机视觉、图像 处理、模式谚 别、人1 ：智能等多学科的结合。在智能视频监控中，行人是主要的 关注对象。因此研究一个鲁棒的行人检测和跟踪算法具有重要意义。本文主要研 究利用基于b 0 0 s t i n g 类的算法分别解决行人检测和行人跟踪问题的方法。主要 的研究工作和创新见解如下： 1 针对训练样本稀缺的情况，提出了一种面向不均衡小样本集的b o o s t i n g 训练 算法，该算法通过在训练过程中逐步加入人工合成样本，对已选定的弱分类器进 行扰动，并自适应地平衡训练集中的f 负样本比例，与当前的其他算法相比较， 本文算法提高了分类器泛化能力。 2 实现了一个基于运动特征的行人检测器，使用a d a b o o s t 算法构建级联结构的 行人检测器，加速了检测过程。 3 完成了一个基于o n l i n eb o o s t i n g 算法的行人检测器，将监控画面划分为若干 的网格，对于每个网格使用o n l i n eb o o s t i n g 算法独立的训练分类器，并融合所有 的网格分类器的判决结果来进行行人检测。该方法仅需要少量的正样本就可以达 到较高的检测率。 4 提出了一种融合先验知识的自适应行人跟踪算法，将行人检测的先验知识融 入到跟踪模型的自学习过程。首先通过离线训练，得到具有较强区分能力的子分 类器集，这些子分类器中蕴含了对于行人的先验知识；在跟踪过程中，使用o n l i n e b o o s t i n g 算法从离线训练的子分类器集成强分类器，对被跟踪的行人动态建模。 实验结果表明，该算法有效地缓解了算法的自适应性与“漂移”之问的矛盾，能 够实现真实监控场合下较长时间、具有较复杂行为的行人跟踪。 关键词行人检测行人足艮踪o n l i n eb 0 0 s t i n g 网格分类器先验知识 a b s t r a c t i n t e l l i g e n tv i d e os u r v e i l l a n c es y s t e mi so n eo fn e wa “s i n ga p p l i c a t i o nn e l d s ， w h i c hi n 、，o l v e sm a n ys u b j e c t si n c l u d i n gc o m p u t e rv i s i o n ，i m a g ep r o c e s s l n g ，p a t t e m r e c 0 2 n i t i o n a 九i n c i a li n t e n i g e n c e ，e t c a sp e d e s t r i a ni sam a j o r c o n c e r nl sv l d e o s u r v e il l a n c e ，s oi ti se x t r e m e l yn e e d e dt oh a v ear o b u s tp e d e s t n a nd e t e c t l o na n d t r a c k i n 2a 1 2 0 r i t h m i nt h i sd i s s e r t a t i o n ，w em a k eu s eo fb o o s t i n ga l g o r i t h mt os o l v e s u c ht w oi s s u e s t h eh i g h l i g h t so ft h ed i s s e n a t i o ni n c l u d e ： 1 t 0a d d r e s st h es i t u a t i o no fs c a r c et r a i n i n gs a m p l e ，w ep r o p o s eai m p r o v e d b o o s t i l l 2a l g o r i t h mo ns m a l la n di m b a l a n c e dt r a i n i n gs e tw i t ha d a p t i v es a m p l e i n i e c t i n ga n df e a t u r ek n o c ko u t ：i nt r a i n i n gp r o c e s s ，w ea p p e n ds y n t h e t l cs a m p i et o t h eo r i g i n a 【t r a i n i n gs e tt or e b a l a n c et h et r a i n i n gs e ta n dd i s t u r bt h ec l a s s i f i e r ，t h e e x d e r i m e n tr e s u l ts h o wt h a te n h a n c et h eg e n e r a l i z a t i o np e r f o r n lo fb o o s t i n ga l g o r i t h m e m c i e n t l y 2 i m p l e m e n tap e d e s t r i a nd e t e c t i o na l g o r i t h mb a s e do nm o t i o n h a a rf e a t u r e ：u s i n g a d a b o o s ta lg o r i t h mc o n s t r u c tac a s c a d ec l a s s i n e r ，i ts p e e du pt h ed e t e c t i o np r o c e s s 3 h a v ei m p l e m e n tap e d e s t r i a nd e t e c t i o na l g o r i t h mb a s e do no n l i n eb o o s t i n g a l g o r i t h m s a m p l i n gt h es u r v e i l l a n c ei m a g e i n t os e v e r a lh i g h l yo v e r l a p p i n g 酽i d ，f 0 r e a c hg r i dt r a i n i n gi n d e p e n d e n tc l a s s i 6 e rw i t ho n l i n eb o o s t i n g ，t h e nf u s i o na l lg r i d c l a s s i n er sd e t e c tr e s p o n s et om a k ed e t e c td e c i s i o n t h i sm e t h o do n l yn e e d sa s m a l l q l l a li t yo f 仃a i n i n gs a m p l e s ，w h n e c o u l dg e th i 曲d e t e c tr a t e 4 a na d a p t i v ep e d e s t r i a nt r a c k i n ga l g o r i t l u ni sp r o p o s e d ，i nw h i c ht h ep r i o r i k n o w l e d 2 eo fp e d e s t r i a ni se m b e d i n t oas e l f 二l e a r n i n gp r o c e s st ou p d a t et h em o d e lo f t r a c k i n go b j e c t a tn r s t ，as e to f s u bc l a s s i n e r sw a st r a i n e d ，i nw h i c hc o n t a i np r i o r d i s c r i m i n a t ek n o w l e d g eo fg e n e r a lp e d e s t r i a n i nt r a c k i n gp r o c e s s ，t h ea l g o r i t u p d a t e st h eg i v e np e d e s t r i a n sd y n a m i c m o d e lb yi n t e g r a t j n gs t r o n gc l a s s i n e rf - r o mt h e s u bc l a s s i n e r ss e tt r a i n e do f f l i n e e x p e r i m e n t a lr e s u l t ss h o wt h a to u rm e t h o d c f n c i e n t l vr e li e v e st h et e n s i o nb e t w e e na d a p t a t i o na n dd r i r i n g ，a n dc o u l dh a n d l e v a r i o u su n c e r t a i nm o v e m e n tu n d e rr e a ls u r v e i 】l a n c ec o n d i c i o n ，s u c c e s s f u l l yt r a c k st h e d e d e s t r i a ni nr e a l t i m e k c y 、) v o r d s ：p e d e s t r i a nd e t e c t i o n ，p e d e s t r i a nt r a c k i n g ，o n l i n eb o o s t i n g ，g r i dc l a s s 讯e r p r i o rk n o w l e d g e 中国科学技术大学学位论文原创。l | 生声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：名难签字日期：垒挈已l 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 酿开口保密( 年) ， 作者签名：j 往警车扯 签字日期：驾：呈 导师签名： 签字日期：三! 乙! ：主 第1 章绪论 第l 章绪论 近年来，随茵信息技术的发展，网络带宽、计算机处理能力和存储容量的提 高，视频监控进入了新的发展时代，其以数字视频的压缩、传输、存储和播放为 核心，并具仃一定的智能视频分析能力，称之为第三代视频监控系统。目自订，视 频监控系统已经广泛应用于银行、交通、军事、商业等部门，发挥着重要的作用。 1 1智能视频监控发展概述 智能化作为第三代视频监控系统的发展趋势，已经得到越来越多的重视。与 传统的视频监控系统不同在于，智能视频监控系统能够辨别不同的物体，发现可 疑情况，并发出警报。2 0 0 1 年美国9 1 1 事件及2 0 0 5 年英国7 7 伦敦地铁爆炸案 等恐怖暴力事件的发生更使得世界各国都高度重视如何对国家重要安全部门和 敏感的公共场合进行全天候、自动的、实时的监控，这也极大的促进了智能视频 监控的发展。 传统的视频监控需要依赖工作人员来监控各个场景，当面对多个监控画面， 长时恻的监控任务时，人的精力是无法应付的。而智能视频监控系统可以通过嵌 入存网络摄像机或视频服务器中的智能视频模块对所监控的画面进行分析，一旦 发现与安全定义不符的情况，立即报警，并可以长时间有效的工作。智能视频监 拧系统的应用包括如下： 高级视频移动侦测( a d v a n c e dv i n u a lm o t i o nd e t e c t i o n ) ：在复杂的天气环境中 ( 例如：阿雪、大雾、大风等) 精确的侦测和识别单个物体或多个物体的运动情况， 包括运动方向、运动特征等。 运动追踪( m o t i o nt r a c k i n g ) ：侦测到移动物体之后，根据物体的运动情况自 动发送控制指令，使摄像机能够自动跟踪物体，在物体超出该摄像机监控范围之 后，自动通知物体所在区域的摄像机继续进行追踪 人脸识别( f a c i a ld e t e c t i o n ) ：自动识别人物的脸部特征，并通过与数据库档案 进行比较来识别或验证人物的身份。 车辆识别( v e h i c l ei d e n t m c a t i o n ) ：识别车辆的形状、颜色、车牌号码等特征， = ； ：反馈给监控者，此类应用可以用在被盗车辆追踪等场景中 非法滞留检测( 0 b j e c tp e r s i s t e n c e ) ：当一个物体( 例如：箱子、包裹、车辆、人 物等) 在敏感区域停留的时间过长，或超过了预定义的时间长度就产生报警。典 型应j t j 场景包括机场、火车站、地铁站等。 第l 章绪论 人数统计( p e o p l ec o u n t i n g ) ：统计穿越入口或指定区域的人或物体的数量。 例如：为、i p 主计算某天光顾其店铺的顾客数量 人群控制( f l o wc o n t r 0 1 ) ：识别人群的整体运动特征，包括速度、方向等等， j f 以进免形成 f j 塞，或者及时发现异常情况。典型的应用场景包括超级市场、火 7 | ：站等人员聚集的地方。 注意力控制( a t t e n t i o nc o n t r 0 1 ) ：统计人们在某物体6 u 面停留的时i 日j 。可以用柬 评估新产品或新促销策略的吸引力，也可以用来计算为顾客提供服务所用的时 问。 交通流量控制( t r a m cf 1 0 w ) ：用于在高速公路或环线公路上监视交通情况，例 如：统汁通过的车数、平均车速、是否有非法停靠、是否有故障车辆等等。 由于智能视频监控具有广泛的应用自仃景和巨大的潜在经济价值，国内外很多 研究机构、高校和企业已经丌展了大量相关项目的研究。例如，美国国防高级研 究项目署( d e f e n s ea d v a n c e dr e s e a r c hp r o i e c t sa g e n c y ) 设立的以卡内基梅隆大学 ( c a m e g i em e i l o nu n i v e r s i t y ) 、麻省理工学院( m a s s a c h u s e t t si n s t i t u t eo f t e c h n o l o g y ) 等高校参与的视觉监控重大项目v s a m ( v i s u a ls u r v e i l l a n c ea n d m o n i t o r i n g ) ( c o l l i n se ta i 2 0 0 0 ) ，主要研究用于战场及普通民用场景进行监控的自 动视频理解技术。美国o b j e c tv i d e o 公司推出的0 b i e c t v i d e ov e w 、0 b j e c t v i d e o f o r e n s i c s ( h t t p ：、 ，、 ，o b j e c t v i d e o c o m ) 。它们实现了在用户定义规则下对监控场 景进行蛉测、跟踪、分类、统计的软件系统，可在诸如有人闯入、盗窃或者未经 许r 叮在限制区域闲逛等违反自定义规则的情况下报警。n e c 公司推出的视频分 析软件f i e l d a n a l y s t ( h t t p = 、 r 、 r 、v n e c s o r c o n 价。f i e l d a n a l y s t 是一个根据摄像机取 得的数据来推断人的性别、年龄段，并输出结果，以用于市场分析等营销活动的 系统。该系统构成简单，不保存图像数据，能够直接分析和处理获得的图像，实 现对客户的实时服务。国内的科研机构近年来也积极展开了智能视频监控系统的 研究与商业产品开发。中国科学院自动化所模式识别国家重点实验室视觉监控小 组总结了英国雷丁大学v i e w s 的车辆交通监控原型系统的研究经验，在以往的 理论研究的基础上，自行设计并初步实现了一个拥有完全自主知识产权的交通监 控原型系统v s t a r ( v i s u a ls u r v e i l l a n c es t a r ) 。国内一些公司推出了基于生物认证技 术的智能监控系统，如上海银晨智能识别科技有限公司的人脸识别系统与视频入 侵报警器等通用产品l9 1 。深圳力方远大科技有限公司的v a 4 0 0 面相识别系统 110 1 ，目i ，j 该系统己在深圳海关争岗出入境边防检查站成功应用。另外还有南京 大学、南京长城信息系统有限公司和江苏省公安厅刑警总队联合研制的“基于单 幅训练图像的多表情人脸自动识别系统”等等。 第1 章绪论 1 2行人检测与跟踪算法研究现状 考虑到视频监控场景中行人是作为监控的主要目标，因此对行人的检测和跟 踪是个至关重耍的问题，属于智能视频监控系统的前端工作，其工作性能的好 坏将直接影l i 向后续工作以至整个系统的性能。 行人检测 在现实的场合下，由于行人的衣着，运动姿态，光照存在着很大的差异，并 且由于背景的复杂，遮挡，和其它运动物体的干扰，这些因素的存在是行人检测 变得1 一分困难。 与l 期的行人检测方法通常使用变化检测束发现运动的行人( z h a oa n dn e v a t i a 2 0 0 4 ) ，首先使用背景建模来发现运动块，然后根据摄像机的视角和摄像机标定信 息来检测和跟踪行人。这类方法在背景单一，人的密度较小的场合下可以取得好 的效果。依赖与背景建模，然而当背景复杂( 例如有剧烈的光照变化) 时，很难获 得满意的效果。 近年来，随着机器学习的发展，很多基于机器学习的行人检测算法被提出， p a p a g e o 唱i o u 首先提出使用机器学习的算法使用支持向量机( s u p p o r tv e c t o r m a c h i n e ) 和h a a r 小波特征来训练行人检测器( p a p a g e o 唱i o ua n dp o g g i o2 0 0 0 ) 。在后 续的 作中，文献( d a l a la n dt r i g g s2 0 0 5 ) 中提出的梯度方向直方图( h i s t o g r a m o r i e n t a t i o ng r a d i e n t ) 被认为是目前描述行人最有效的特征。作者在图像不同位置 和尺度的块中，计算梯度方向直方图特征，然后使用s v m 利用在这个特征空l 日j 中进行分类。由于s v m 需要利用所有维度的特征，因此这种检测算法不能实时 的运作。为了加速检测速度，z h u ( z h ue ta 1 2 0 0 6 ) 使用级联分类器和积分图柬获 得一个可以接近实时的行人检测器。h o u ( h o ue ta 1 2 0 0 7 ) 提出的一种简化的h o g 特征，称之为e h o g 特征，该特征只需要一个维度的梯度值来进行分类，达到 了较快的速度。w u ( w ua n dn e v a t i a2 0 0 5 ) 提出了一种使用e d g e l e t 特征末训练行 人检测器，该特征可以以曲线柬描述行人的局部轮廓，达到了较高的检测精度。 v i o l a ( v i o l ae ta 1 2 0 0 3 ) 使用了一种在相邻两帧问的图像差上提取h a a r - 1 i k e 特征， 将行人的形状信息和运动信息结合，这种方法在静念摄像机拍摄的视频中取得了 不错的效果。 行人跟踪 目前主要的跟踪算法大致可以分为3 类： 基卡图像区域的目标跟踪，对被跟踪的目标区域提取一些特征例如颜色直方 图，或者单纯的狄度信息，然后在后续帧中通过序列模板匹配( h a g e ra n d b e i h l i m e u1 9 9 8 ) 或均值漂移( c o m a n i c i u ，2 0 0 3 ) 等方法找到与初始模板最相似的目 第1 章绪论 标位置。这类方法对于目标的描述过于简单，容易受目标自身形状的改变，或者 棚似背景二f 扰等冈素的影响。 基于前景检测的目标跟踪，首先需要进行背景建模以分割前景，然后利用被 跟踪同标的颜色信息或者运动信息进行跟踪。例如文献( z h a oa n dn e v a t i a2 0 0 4 ) 使 用背景建馍米检测出运动区域，然后使用粒子滤波等方法，找出最大似然的行人 位置。但背景建模只能应用在摄像头固定的场合，所以该方法不具有通用性。并 且目6 ，j 的i ，j 景分割算法容易受光线变化，阴影等因素的影响，鲁棒性不强。 基于分类器的目标跟踪，核心在于构建跟踪目标的区分模型，在每帧图像数 据中，使用区分模型对图像进行分析，找到最大释然的行人位置。a v i d a n 首先 提出基于集成分类器的目标跟踪算法( a v i d a n ，2 0 0 5 ) ，作者对跟踪目标提取一些简 单的特征( 颜色，和梯度分布直方图) ，然后使用a d a b o o s t 算法在线训练弱分类器， 并在跟踪过程中丢弃旧的弱分类器来更新目标的强分类器。文献( g r a b n e ra n d b i s c h o f2 0 0 6 ) 提出了一种皋于在线学习分类器的跟踪算法：在跟踪过程中使用 k a l m a n 滤波器分别估汁正负样本的特征值分布，构建弱分类器，然后使用o n l i n e b o o s t i n g 算法从更新后的弱分类器中集成强分类器。该方法可以较好的自适应背 景变化。 在行人检测和行人跟踪中，由于背景的差异和行人自身的差异，一个通用的 特征是难以获得的，在本文的研究工作中，我们重点研究了如何在线的选取有效 地特征来描述行人，以此来得到精度较高的行人检测器和鲁棒的行人跟踪算法。 1 3本文工作和论文章节安排 本文研究的对象是摄像头固定情况下的视频场景。研究内容包括行人的检测 和跟踪两个方面。 目前主流的行人检测算法大多是基于统计学习，搜集大量的训练样本，通过 机器学习算法在训练集中学习分类器，然后再用于实际的检测。因而训练集直接 影响到最终检测器的检测率。在实际应用中，一个完备的训练集是很难获取的， 这足目前这类检测算法存在的问题。为了减轻样本集对检测带来的影响，本文研 究了面向不平衡小样本数掘集的b o o s t i n g 算法，研究了如何使用在线的b o o s t i n g 算法构建一个鲁棒的实时行人检测器。 在面向不均衡小样本集的b o o s t i n g 算法中，我们通过在算法的迭代过程中 合成人工样本，扰动训练过程，从而使最终的分类器使用更多的差异特征，使用 陔方法可以在只有少量正样本的d ，j 提下，提高分类器的泛化能力。 在行人检测算法中，我们将监控画面划分为若干重叠的网格，对每个网格使 4 第l 章绪论 用o n l i n eb o o s t i n g 算法训练独立的分类器，再融合所有网格分类器对当前图像的 判决结粜，来检测行人。实验表明，该算法只需要搜集少量的行人样本，就可以 再不同的场景下鲁棒的检测行人，具有良好的通用性。 在行人芷 踪方面，在行人运动姿念多变等复杂的监控环境下，传统的塾于模 板的跟踪算法无法应对，而目前自适应的跟踪算法由于自学习没有受剑指导和约 束，会造成跟踪漂移。本文研究了融合先验知识的行人跟踪算法，将对于行人模 型的区分信，癌、融入到o n l i n eb o o s t i n g 的自学习框架中，使得跟踪过程的在线学习 受到约束，因而得到一个鲁棒的行人跟踪算法。实验表明，该算法可以长时i 口j 鲁 棒的跟踪个具有复杂行为的行人。 本文了芒分6 章，第1 章介绍了智能视频监控算法的发展概况，以及行人检测 和足艮踪的研究进展，介绍了目前算法存在的问题。第2 章介绍本文工作中的一些 基本理论，包括a d a b o o s t 算法的摹本原理，面向不均衡小样本集的b o o s t i n g 算 法。第3 章介绍了使用a d a b o o s t 算法的级联结构行人检测器的构建。第4 章介 绍了使用o n l i n eb o o s t i n 2 算法的行人检测器的构建。第5 章介绍了融合先验知识 的行人跟踪算法，包括先验模型的训练，在线更新跟踪模型的方法，以及实验结 果分析。第6 章总结本文的工作以及对后续工作的展望。 第2 章相关基本算法研究 第2 章相关基本算法研究 本章介绍了本文使用的相关基本算法，首先介绍b o o s t i n g 算法和a d a b o o s t 算法，然后针对刁i 平衡小样本i 、口j 题，介绍了本文对b o o s t i n g 改进算法。 2 1 b o o s t i n g 算法 2 1 1 b o o s t i n g 算法概述 b o o s t i n g 算法是一种集成学习算法，即通过使用多个弱学习器来构建一个强 学习器的机器学习算法。b o o s t i n g 算法起源于v a i i a n t 等人提出的一般化的概率 近似正确( p r o b a b l ya p p r o x i m a t e l yc o r r e c t ，简称p a c ) 学习模型。k e a m s 和v a i i a n t 在p a c 学习模型中提出弱学习算法和强学习算法的等价性问题，即是否可以将 弱学习算法提升成强学习算法。文献( s c h a p i r e ，1 9 9 0 ) 证明了任何弱分类算法能够 被有效的转变或者提升为强学习分类算法，并且首次提出了个简单的b o o s t i n g 提升过程，这个过程通过不断的训练，可以提高对数据的分类能力。之后f r e u n d 改进了s c h a p i r e 的算法，提出了“b o o s t - b y m a i o r i t y ”算法( f r e u n d ，1 9 9 5 ) 。此算 法通过循环多次调用一个弱学习算法w e a l 山e a r n ，每次调用后都赋予训练集一 个不同的分前i ，最后将所有学习得到的弱分类器组合成一个强分类器。改变权重 分衍i 的一个直观的做法是提高训练集中比较难的那部分样本的权重，使得学习得 到的新的弱分类器在这部分样本上能分类得更好。这种算法的缺点是 w e a k l e a r n 的偏差y 必须寸 先知道，但是在实际情况下偏差y 是不知道的，而且 对不同的样本分御，w e a i 也e a r n 会产生很大偏差。此外， “b o o s t - b y m a j o r i t y ” 算法没有好好利用那些由w e a l 也e a r n 学习得到的错误率很小的弱分类器。 2 1 2a d a b o o s t 算法 为了解决上述问题，f r e u n d 和s c h a p i r e 中提出了一种自适应的b o o s t i n g 算 法一a d a b o o s t ( f r e u n da n ds c h a p i r e1 9 9 7 ) 。此算法不需要预先知道弱分类器的偏 差，并且最后得剑的强分类器的分类精度依赖于每个弱分类器的分类精度，这样 百j 。以深入挖掘弱分类器算法的潜力。f 因为此算法能自适应不同弱分类器的错误 率，所以f r e u n d 和s c h a p i r e 就称此算法为a d a b 0 0 s t 。具体的算法流程如下： 给定个标记过的样本( ( 五，y ，) ，( x y ) ) ，此个样本的分仃d ，弱学 第2 章相关基本算法研究 刊算法w c a k l e a r n ，迭代的次数n 初始化权重向量= d ( f ) ，汪1 ，； 令f - 1 ，2 ，丁 7 2 南； 在分斫j p 条件下调用弓巧分类器学习算法w e a k l e a r n ，得到一个假设向； 计算曩的错误率：t = 竺。p ；l 忽( 誓) 一y ，l ；计算曩的错误率：t = 乙= 1 l 红( 誓) 一y ，l ； 令屈= 乞( 1 一t ) ； 更新样本的权重：叫= w ；一h 工，一州。 输出最后的强分类器h ( x ) = s 劬 ；：。q 曩( x ) ，q = 1 0 9 ( 1 屈) 。 上述算法中有一个迭代了丁次的主循环，每一次循环根据当前的权重向量 w 对x 定义一个分布p ，然后对这个分柿下的样本使用弱学习算法w e a i 山e a m 得到一个错误为占，的弱分类器矗。对于w e a k l e a 伸算法，对所有的，有 s ，l 2 一y ，y o 为一常数。但是这个错误的上界并不需要事先知道，实际上算 法适用于 o ，l 】。参数屈是的函数，在每一次迭代时，屈将根据q 变化，局 被用米对杖重向量进行更新。更新的规则是：减小弱分类器预测分类效果较好的 数掘的概率，增大弱分类器预测分类效果较差的数据的概率。最终的强分类器是 丁个弱分类器的加权和。 在a d a b o o s t 的实验中，s c h a p i r e 等人( s c h a p i r ee ta 1 19 9 8 ) 发现了一个令人惊 奇的现象：就是尽管训练错误已经为零，但是随着训练的继续进行，测试错误还 会一直往下降。为了解释这种现象，s c h a p i r e ( s c h a p i r ea n ds j n g e r1 9 9 8 ) 提出了样本 的“边缘”的概念。对两类问题，一个样本的边缘定义为：正确分类此样本的弱分 类器的权重之和减去错误分类此样本的弱分类器的权重之和。显然，当且仅当样 本的边缘大于零时样本被萨确分类。s c h a p i r e 等人从理论上和实验中都证明了 a d a b o o s t 算法能有效的提高训练样本的边缘，当训练错误为零时，训练样本的 边缘还会随着训练的进行而持续提高。而v a p n i k ( v a p n i k ，2 0 0 0 ) 已经证明，边缘的 最火化会提升一个分类器的泛化能力。这就解释了出现上述现象的原因。另外， s c h a p i r e 等人( s c h a p i r ea n ds i n g e r l9 9 8 ) 还将a d a b o o s t 算法进行了扩展，得到了 更一- 般化的实a d a b o o s t 算法( r e a l b o o s t ) ，而原始的a d a b o o s t 称为离散型 a d a b o o s t ( d i s c r e t b 0 0 s t ) 。 f r i e d m a n ( f r i e d m a ne ta 1 2 0 0 0 ) 从加性退化模型角度也对a d a b 0 0 s t 算法作了 第2 章相关基本算法研究 解释。他们认为a d a b 0 0 s t 以迭代的方式建立了，一个加性对数退化模型： 厂( x ) = l 。g 揣= ；| ；口。，e ，( x ) ( 2 1 ) 使用的损失函数为： ( y ，厂( x ) ) = e x p ( 一卫， ( x ) )( 2 2 ) 给定当自玎的川( x ) ，( 屈 g 。( x ) ) 的解为： a r g 咖e x p 【_ 只( 无 ) + g ( 一) ) 】 ( 2 3 ) 这罩g 。( x ) 为一个树形分类器，孱，为系数。如果设吖= e x p ( 一只厶一，( j ，) ) ， 则式( 2 3 ) 可写为： ， a r g 咖吖7e x p 一以g ( ) 】 ( 2 4 ) ” j _ l 由此可推导出a d a b o o s t 算法。在此基础上，他们还提出了l o g i t b o o s t 和 g e n t l e b o o s t 两种a d a b o o s t 的变种算法。l i e n h a r t ( l i e m l 甜a n dm a y d t2 0 0 3 ) 分 别用d i s c r e t b o o s t ，r e a l b o o s t 和g e n t l e b 0 0 s t 三种算法训练了三个人脸检测器。 实验结果表明g e n t l e b o o s t 比其它两种算法的性能要好，而且平均用到的特征数 要少。 2 2 一种面向不均衡小样本集的b o o s t i n g 算法 目自玎的b 0 0 s t i n g 算法对训练样本的依赖性较大，训练训练样本集的大小和分 佰对最终分类器的性能有着很大的影响。当训练样本的特征维数远大于样本集的 大小时，b o o s t i n g 算法容易出现过拟合( o v e rf i t t i n g ) 现象，即在训练集上得到很低 的分类错误，但在测试集上的分类错误却很大。这就是经典的小样本学习问题。 在实际应用中，样本的特征维数经常会很高，如人脸识别的特征维数一般都在 数干量级，而样本的获取印总是存在这样或者那样的困难，因此小样本问题是普 遍存在的。此外，对于目标检测等问题( o n e c l a s sp r o b l e m ) ，f 样本获取的难度要 远远大于负样本，因此训练集往往是正负样本不均衡的，这也会对算法性能产生 很大影i l 向。因此，研究如何在小规模、不均衡的样本集的情况下提高学习算法的 准确率和泛化能力具有重要的意义。正则化是提高算法泛化能力的一种主要方 法，被广泛应用于小样本学习问题。例如g u i ( g u ia n dl i2 0 0 5 ) 提出了基于支持向 量机的惩罚回归模型。p e r k i n ( p e r k i ne ta 1 2 0 0 3 ) 使用基于正则化的的嵌入式特征 选择模型。w b l f ( w b l fa n dm a r t i n2 0 0 5 ) 提出了一种融合了特征选择和合成冗余 第2 章相关基本算法研究 样本水对分类器进行扰动的方法。这些方法的基本思想都是认为：一个鲁棒的分 类器4 i 应陔过度依赖某几个特定的特征，于是通过在学习过程中对权重过大的特 征实施惩罚，以削弱其在分类器中的作用。以上方法均在特定问题上取得了很好 的效果，但是，他们都没有考虑训练集中样本不均衡的情况。 针肘样本不均衡问题，也有一些优秀的工作值得参考。例如，s m o t e b o o s t ( c h a w i a le ta 1 2 0 0 3 ) 通过合成一些少数类的样本，以减少过度拟合现象发 牛的胍险：在d a t a b o o s t i m ( g u oa n dh e m a2 0 0 4 ) 方法中，来源于多数类和少数类 的难样本在b o o s t i n g 算法的执行中都被识别出来，然后困难样本用于分别产生 多数类衣l 少数类的人工样本。人工数据被加入最初的训练集，在新的训练集中， 类的分布和不_ j 类之间的总权重被重新平衡。上述方法的目的是通过新产生的合 成样本来扩充少数类的样本库，以降低样本不均衡对算法的影响：v i o l a ( v i o l aa n d j o n e s2 0 0 1 b ) 提出了非对称的a d a b o o s t 算法( a s y m m e t r i ca d a b o o s t ) ，即在训练过程 中，漏检的f 样本的权重惩罚大于误识的负样本，使分类器向着有利于正确分类 一样本的方向偏移。这种方法的缺点在于不同类的惩罚项的比例难以确定，只能 根捌经验来获得。为此本文提出基于自适应样本注入和特征替换策略的b o o s t i n g 算法，以提高b o o s t i n g 算法在极小样本和非均衡训练集上分类器的泛化能力。 2 2 1 基于样本注入的b o o s t i n g 算法 目前的b o o s t i n g 算法弱分类器通常是基于桩( s t u m p ) 的，如下式所示： 厂( 工) = s 喀门( k 一，向) ( 2 5 ) x 为特征向量，k 为剽分类器选取的特征维数，砌为这个桩的阈值。弱分类 器的闽值只在训练集中每个样本的特征上取，当样本数为n ，特征数为m 时， 可选的弱分类器共有n m 个。 当训练集很小时，b o o s t i n g 算法只需使用少量特征就可以在训练集上达到很 高“内分类准确率。假如基于特征k 的弱分类器己对所有样本进行了正确的分类， 那么在以后的迭代丌始中，所有样本的相对权重将不再改变，因此无论迭代多少 次，最终的强分类器都将依赖这一个特征k 。这样的分类器在测试集上往往会产 牛很高的分类错误。 针对这个问题，w 6 l f ( w b i fa n dm a n i n2 0 0 5 ) 中提出一种基于样本注入的 b o o s t i n g 算法。该算法在每次迭代中加入一个人工合成的样本来扰动分类器的学 习，使之日订选择的弱分类器难以再次被选中，以达到提高弱分类器多样性、进而 提高分类器泛化能力的目的。具体的操作如下： b o o s t i n g 算法在每次迭代中，假设选择特征维度为k 组成弱分类器，在初 1 0 第2 章相芙基本算法研究 始样本集中随机抽取两个不同的样本五，x 。，其中毛为拷贝源，x 。为替换源。复 制矗的特征值，类别标号，权重，得到合成样本曼，然后用工疗( 尼) 替换曼( 尼) 的值。 将合成的新样本曼加入到训练集一起训练。由于新样本的生成是通过替换原始样 本的某一维度特征来获得，因此这种方法被称为特征替换( f e a t u r ek n o c k0 u t ) ， 将这种改进的b s ti n g 算法称为k ( ) b 0 0 s t 。 这种方法合成的样本的作用在于：如果妥和拷贝源在第k 维上的值刚好在桩 的两端，这时刚刚选取的弱分类器就会对主和矗给出相反的判决( 但曼和毛类别 相同) ，因此在接下来的迭代中，会降低使用该特征作为弱分类器的概率，而去 选择别的特征。随着迭代的进行，算法将有更多的机会选择新的特征组成弱分类 器。 设初始训练集中的正样本所占比例为p ，在每次迭代中产生的合成样本对分 类器学习形成扰动的概率为2 p ( 1 p ) ( 表2 1 ) 。当原始样本集严重不均衡时，p 很 小，例如p = 0 1 时，2 p ( 1 p ) = 0 1 8 ，因此大约需要迭代5 次才可以获得一个样本 对分类器学习形成扰动，这降低了算法的效率。并且该方法合成样本时是从原始 训练集随机抽取，因此不改变训练集的正负样本比例( 表2 1 所示) 。但是在文献 ( v i o l aa n dj o n e s2 0 0 1 b ) 中，作者指出在不均衡训练集上使用b o o s t i n g 会导致分类 器向多数类偏移，降低了分类器的分类性能。 2 2 1自适应特征替换方法a d a k ob o o s t 针对k ob o o s t 的上述问题，本文改进了在每次迭代时合成人工样本的策略， 提出了在不均衡的小样本训练集上的b o o s t i n g 算法，称为a d a k ob o o s t 。 为了在合成人工样本来扰动分类器学习的同时，保证分类器不向多数类偏 移，本文提出两点改进： ( i ) 在合成人工样本时引入概率机制，拷贝源选择j 下样本的概率是当前负样 本在洲练集中的比例，选择负样本的概率是当6 i 正样本在训练集中的比例。因此， 任饵挑选出一个弱分类器后，新产生的合成样本以较大的概率拷贝自初始训练集 中少数类的样本。同时由于新样本的类别属性和拷贝源致，随着迭代的进行， 新的合成样本不断的加入，使得在扰动分类器的同时并逐渐平衡了训练样本集。 ( i i ) 替换源从与拷贝源不同类的初始样本集中随机选取，使得每次合成的样 本对刚生成的弱分类器均产生扰动，这相比文献( w b l fa j l dm a r t i n2 0 0 5 ) 的方法更 何效：莽，可以在较少的迭代中获得更大的扰动。具体步骤如下： 输入：初始化训练集( 一，乃) ( z ，朋) ，x ，尺历，” + l ，一1 ) 输出：强分类器h ( x ) 1 ) 初始化正负样本权重1 矿，= 1 2 朋，1 2 f ，聊，7 分别是f 负样本的个数 第2 章相笑基本算法研究 2 )t o rt2l t a 调用、a k l e a r n 算法得到基于特征k 的弱分类器h ( x ) b 更新强分类器h ( x ) = h ( x ) + h ( x ) c 选择拷贝源和替换源 i 父西为当日仃样本集中的所有一样本所占比列 i j r n n d 、一扫 口从初始币样本集中随机选取 从初始负样本集中随机选取 e s i e 从仞始限样本集中随机选取 口从仞始负样本集中随机选取 e n d d 合成新样本加入训练集 x + ，= x 口，x + ，( 尼) = x 口( 七) ，w ，+ ，= 么，y j v + ，= 儿 e 更新并归一化权重 w f + i ，= w ，p 一卫( 驯，f = 1 + ， 3 ) 输m 最终强分类器h ( x ) y ( d ) y ( b ) a d a k o 概率k o 概：年 c a s el ：+ 1+ l p 。 0 c