（计算机软件与理论专业论文）支持向量机在视频交通信息检测系统中的应用研究.pdf

支持向量机在视频交通信息检测系统中的应用研究 摘要 统计学习理论是一种专门研究小样本情况下机器学习规律的理论，支 持向量机方法是在该理论基础上发展起来的通用学习方法，它具有全局优 化、适应性强、理论完备、泛化性能好等优点，统计学习理论和支持向量 机是i f l 前机器学习领域的研究热点。 随着城市交通管理的不断发展，交通信息检测在交通管理和控制中的 应用越来越普遍，作用越来越突出。在众多自动化检测技术中，视频检测 是当前最具发展前景的交通信息检测技术之一。视频交通信息检测系统是 一种利用图像处理技术对交通目标检测和识别的计算机处理系统。通过对 道路交通状况的实时检测，实现路段上行驶机动车数量的自动统计，行驶 车辆速度和车辆类别等交通参数的自动计算和识别等功能。 本文将支持向量机引入视频交通信息检测系统，主要进行的工作如 下： ( 1 ) 整理总结了国内外关于统计学习理论方面的研究成果，介绍统计 学习理论的基本概念和支持向量机的基本原理； ( 2 ) 介绍了视频交通信息检测系统在交通信息检测技术中的优势与前 景，阐述了交通信息检测系统的工作原理和常用交通参数的检测方法； ( 3 ) 设计并实现了一个视频交通信息检测系统，通过实际测试运行， 分析了目前所用的检测方法的性能及弊端： ( 4 ) 将支持向量机应用于视频交通信息检测系统中，通过对交通流在 检测区域中状态特征进行分类，从而动态监测、跟踪车辆通过检测区域的 过程，实现了交通流量、车速、车型信息的检测，并与当前的视频交通检 测技术进行了对比。 关键词：统计学习理论支持向量机视频交通信息检测 s t u d yo fs u p p o r tv e c t o rm a c h i n ea n d i t sa p p l i c a t i o n si n v i d e ot r a f f i ci n f o r m a t i o nd e t e c t i o ns y s t e m a b s t r a c t s t a t i s t i c a ll e a r n i n gt h e o r y ( s l t ) i sal e a r n i n gt h e o r yw h i c hs p e c i a l i z e si n m a c h i n el e a r n i n gw i t hf i n i t es a m p l e s a sal e a r n i n gm e t h o db a s e do ns l t , s u p p o r tv e c t o rm a c h i n e ( s v m ) h a st h ea d v a n t a g e so fg l o b a ls o l u t i o n s ，w e l l a d a p t i v e l y h i g hg e n e r a l i z a t i o na b i l i t ya n dm a t u r i t yi nt h e o r y s l ta n ds v m a r et h eh o t s p o ti nt h ef i e l do fm a c h i n el e a r n i n gn o w a d a y s w i t ht h ed e v e l o p m e n to fu r b a nt r a f f i cm a n a g e m e n t ，t h ed e t e c t i o no ft r a f i l e i n f o r m a t i o ni sp a i dm o r ea n dm o r ea t t e n t i o n v i d e od e t e c t i o ni ss u p e r i o rt o o t h e rm e t h o d s v i d e ot r a f f i ci n f o r m a t i o nd e t e c t i o ns y s t e mi sac o m p u t e r p r o c e s s i n gs y s t e mu s i n gi m a g ep r o c e s s i n gt e c h n o l o g i e sa n da i m st og a t h e r t r a f f i ci n f o r m a t i o ns u c ha sp a s s e dv e h i c l ec o u n t ，v e h i c l es p e e da n dv e h i c l e t y p e s i nt h i st h e s i s 。w ei n t r o d u c es v mt ot h es y s t e mo fv i d e ot r a f f i c i n f o r m a t i o nd e t e c t i o n ；t h em a i nw o r ki sd e s c r i b e da sf 0 1 l o w s ： f 1 、w es u m m a r i z et h el a t e s tr e s e a r c ha c h i e v e m e n t sa n dd e v e l o p m e n to f s l l ：p r e s e n tt h ec o n c e p t i o n so fs u a n dt h ep r i n c i p l e so fs v m ； r 2 、i n t r o d u c et h e s u p e r i o r i t yo fv i d e o t r a f f i ci n f o r m a t i o nd e t e c t i o n t e c h n o l o g i e s p r e s e n tt h et h e o r i e sa n d m e t h o d st h a ta r eu s e di nav i d e ot r a f f i c i n f o r m a t i o nd e t e c t i o ns y s t e m ； f 3 1 a c c o m p l i s has y s t e mo fv i d e ot r a f f i ci n f o r m a t i o n d e t e c t i o nu s i n g c u r r e n tm e t h o da n da n a l y z ei t sf u n c t i o na n ds h o r t n e s s r 4 1a p p l yt h et h e o r yo fs v mt ov i d e ot r a f f i ci n f o r m a t i o nd e t e e t i o n s y s t e m t h r o u g hc l a s s i f y i n gt h et r a f f i cf l o wi m a g e si nd e t e c t i o na r e aa n d t r a c e sv e h i c l e st og e tt h ei n f o r m a t i o no fp a s s e dv e h i c l ec o u n t ，v e h i c l es p e e d a n dv e h i c l et y p e s l a s t l y ，w et a k eac o m p a r i s o nb e t w e e ns v mm e t h o da n d c u r r e n tm e t h o d k e yw o r d s ：s t a t i s t i c a ll e a r n i n gt h e o r y ，s u p p o r tv e c t o rm a c h i n e ，v i d e ot r a f f i c i n f o r m a t i o nd e t e c t i o ns y s t e m 插图清单 图2 1 机器学习的基本模型 图2 2 v c 维示意图 图2 2 结构风险最小化示意图 图3 1 最优超平面示意图 图3 2 支持向量机示意图 图3 3 支持向量机用于二维样本分类的例子 图3 4 多类识别决策树 图4 1 系统基本上作流程 图4 2 道路交通视频图像 图4 3 图像预处理 图4 4 车辆经过检测区域的过程 图4 5 多值分类决策树 图4 6 划分检测区域 母b 体加n m卯勰孙凹弛” 表4 1 分类器设计表 表4 2 五种分类的实验结果 表4 3 实验结果比较 表格清单 3 1 3 3 3 4 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 垒卫王些盔堂一或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 意。 学位论文作者签名：谚元乳 一一| 签字日期：讪，年97 日 7 学位论文版权使用授权书 本学位论文作者完全了解盒妲些太堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权世 至些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 才元砂 签字日期：矽。6 年厂月9 日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名：7 彪 ，卜，o 签字日期：衫年于月夕日 电话 邮编 致谢 两年半的研究生生活转瞬即逝，一路走来，所收获的点滴成绩不仅凝 聚着自己的血汗，而且有赖于大家给予我的热心帮助。 首先感谢我的导师王浩教授，感谢他对我的悉心栽培，感谢他为我付 出的每一分心血。王老师严谨求实的科研态度，渊博的专业知识，宽以待 人严于律己的学者风范，使我终身受益。 感谢师兄姚洪亮，感谢我的同学琚旭、高建清，与各位的交流与讨论 丰富了我的知识，给了我有益的启示。感谢我们研究室所有同学，每一次 的研讨会，都令我受益匪浅。 感谢谷峻老师，他给予我的信任与激励，使我有勇气去面对一个个难 题和挑战，令我更加自信而执着。 向计算机与信息学院的王新生、徐静、曹航等老师付出的辛勤工作表 示感谢。 衷心的感谢我的父亲、母亲、姐姐，一直以来，我的每一步足迹都有 他们的见证，他们对我默默的支持与一贯的鼓励，无微不至的关怀与体贴 备至的爱护，永远是我赖以进步的基石，是我不断前进的动力。 最后，感谢我的男友宿彦民，他积极向上的生活热情，面对困难时的 坚韧与执着，时时感染激励着我。感谢他对我的关心、爱护、理解和支持。 作者：李元元 2 0 0 6 年4 月 第一章绪论 基于数据的机器学习是现代智能技术十分重要的一个方面，主要研究 如何从一些观测数据( 样本) 出发得出目前尚不能通过原理分析得到的规 律，利用这些规律去分析客观对象，对未来数据或无法观测的数据进行预 测。现实世界中存在大量我们尚无法准确认识但却可以进行观测的数据事 物，因此这种机器学习方法在现代科学技术及社会经济各领域中都有着十 分重要的应用。 统计是我们面对数据而又缺乏理论模型时最基本的( 往往也是唯一的) 分析手段，传统统计学所研究的是渐进理论，即当样本数目趋向于无穷大 时的极限特性，但实际应用中，这种前提条件往往得不到满足，因此一些 理论上很优秀的学习方法在实际中的表现常常不尽人意。为此，试图从本 质上研究机器学习问题的理论一一统计学习理论( s t a t i s t i c a ll e a r n i n g t h e o r y ，简称s l t ) 逐步受到重视，它的不断发展使得以上问题的解决变 成可能。 1 1 统计学习理论 与传统统计学相比，统计学习理论是一种专门研究小样本情况下机器 学习规律的理论，而支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 是 在统计学习理论基础上发展出的一种机器学习的方法，在解决小样本、非 线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函 数拟合等其他机器学习问题中。 v v a p n i k 等人早在2 0 世纪6 0 年代就开始研究有限样本情况下的机器 学习问题，由于当时这些研究尚不十分完善，在解决模式识别问题中往往 趋于保守，且数学上比较艰涩，因而直到9 0 年代以前并没有提出能够将 其理论付诸实现的较好的方法。虽然，早期的统计学习理论提出了v c 维 ( v a p n i k c h e r v o n e n k i s ) 理论，为衡量预测模型的复杂度提出了有效的理 论框架，但它仍然是建立在经验风险最小化原则基础之上，即：以训练平 均误差为最小的模型作为期望的最终模型。所以，早期的统计学习理论一 直停留在抽象的理论和概念的探索之中。加之当时正处在其他学习方法飞 速发展的时期，因此这些研究一直没有得到充分的重视。直到9 0 年代中 期，v a p n i k 和他所在的a t & b e l l 实验室小组提出了支持向量机算法，进一 步丰富和发展了统计学习理论，使它不仅是种理论分析方法，还是一种 能构造具有多维预测功能的预测学习算法的工具，使抽象的学习理论能够 转化为通用的实际预测算法，这标志着其理论的发展成熟。同时，也由于 神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越 来越广泛的重视。 统计学习理论的一个核心概念就是v c 维概念，它是描述函数集或学习 机器的复杂性或者说是学习能力的一个重要指标，在此概念基础上发展出 了一系列关于统计学习的一致性、收敛速度、推广性能等重要结论。 统计学习理论是具有坚实的理论基础的，为解决有限样本学习问题提 供了一个统一的框架，它能将许多现有方法纳入其中，有望帮助解决许多 原来难以解决的问题；同时，在这一理论基础上发展出了一种通用的学习 方法一支持向量机，它已初步表现出很多优于已有方法的性能。 1 2 支持向量机 支持向量机方法的重要理论基础是统计学习理论的v c 维理论和结构 风险最小化原理。支持向量机根据有限的样本信息在模型的复杂性和学习 能力之间寻求最佳折中，以期获得最好的推广能力。支持向量机可以自动 寻找对分类有较好区分能力的支持向量，由此构成的分类器可以最大化类 与类之间的间隔【j j 。 支持向量机方法的几个主要优点有： ( 1 ) 它是专门针对有限情况的，其目标是得到现有信息下的最优解 而不仅仅是样本数趋于无穷大时的最优值； ( 2 ) 算法最终将转化为一个二次寻优问题，从理论上来说，得到的 将是全局最优点，解决了在神经网络方法中无法避免的局部极值问题； ( 3 ) 算法将实际问题通过非线性变换到高维的特征框架，在高维空 间中构造线性判别函数以替换原空间中的非线性判别函数，这样能保证学 习机器有较好的推广能力，同时它巧妙的解决了维数问题，其算法复杂度 与样本维数无关。 在支持向量机方法中，只要定义不同的核函数，就可以实现多项式拟 合、径向基函数方法、多层感知器网络等许多现有学习算法。支持向量机 克服了神经网络分类和传统分类法的许多缺点，具备较高的泛化能力，可 以替代多层感知机、r b f 神经网络和多项式神经网络等学习算法4 1 。 支持向量机在实际中的一些应用也说明了其实用价值。在国外，继b e l l 实验室以后，微软研究所、i b m 公司等世界著名的研究所、公司和高校开 展了对支持向量机的研究，支持向量机的理论研究与应用日益丰富。蓬勃 发展的互联网为广大研究者提供了丰富的支持向量机相关资源，知名的网 站硐h t t p ：w w w s u p p o r t - v e c t o r n e t ；h t t p ：h w w w r e s e a r c h m i c r o s o f t t o m ： h t t p ：w w w a i m i t e d u ；h t t p ：l w w w k e r n e l - m a c h i n e s o r g 一等。 目前，对支持向量机的研究大体可以分为以下几个方面【5 ： f 1 ) 标准s v m 理论深化、完善及s v m 的改进与方法拓展研究 这方面的研究包括对理论的继续研究以及创新，如n c r i s t i a n i n i 详细描 述了支持向量机的贝叶斯解释，这种统计学的解释对于为支持向量机寻找 一个合适的核具有一定的指导意义。在对支持向量机算法的具体改进方 面，j a k s u y k e n s 等人在1 9 9 9 年提出了最小方差支持向量机，简称 l s s v m ，它是以二次误差函数为基础发展来的，通过求解一组线性方程 以适应在线应用的需要。2 0 0 1 年，o l m a n g a s a r i a n 等人提出了拉格朗日 支持向量机，简称为l s v m ，具有较高的分类速度。a v v a z q u e z 等人提出 了一种基于权重最小方差优化的迭代“块”方法柬训练支持向量机，这是 对l s s v m 的一个有益补充。 ( 2 ) 核及核方法的拓展与应用 核函数及核方法的研究是支持向量机理论与方法研究很活跃的一个分 支。核函数可隐含的将输入空间的数据映射到高维特征空间，通过非线性 变换转化为某个高维空间的线性问题，在变换空间求最优分类面，这种思 想已经成功应用到其他算法中，如主分量分析、聚类和贝叶斯分类。基于 核的学习方法仍是一个热点的研究方向。虽然关于核函数和核方法的研究 很多，但是至今没有一个优秀的理论能够有效的指导支持向量机选择最优 的核，目前大多是在特定的应用领域内，通过实验分析来解决。核函数的 选择仍然是一个具有挑战性的问题。 ( 3 ) 支持向量机实现算法研究 尽管支持向量机算法的性能在许多实际问题的应用中得到了验证，但 是该算法在计算上存在一些问题，包括训练速度慢、算法复杂且难以实现 等【6 】。近年来研究人员提出了许多算法来解决这些问题，分别从解析和几 何两个角度来寻求解决的途径 7 1 。在解析法中，根据子问题的划分和迭代 策略的不同，又可以大致分为“块算法”和“固定工作样本集”方法两类 f 8 【9 1 。几何方法有最近点算法和投影算法。e d g a ro s u n a 1 1 1 等人则提出了一 个分解算法能够保证得到全局晟优而且能够在很大的数据库上被用来训 练支持向量机。该方法的主要思想是用子问题的迭代解和最优性评估条件 来产生改进的迭代值，同时也确立算法的停止准则。 ( 4 ) 多类问题研究 由于支持向量机是二值分类器，怎样有效的把它拓展到多分类问题仍 是一个正在研究的问题。比较出名的有“一对”方法和“一对多”方法， 还有一种解决多类问题的方法是j c p l m t 在2 0 0 0 年提出的“决策定向非 循环图s v m ”。多类问题是目前研究的难点，目前尚无在理论上和实用效 果上都特别好的方法，因而限制了支持向量机的广泛应用。 ( 5 ) 应用研究 目前，支持向量机方法已被应用于模式识别、回归估计和密度估计等 方面，在大多数情况下，支持向量机的泛化能力要显著优于其他方法。 k y u n g h e el e e 等人f 1 2 】提出了一个人脸确认的有效算法，它对于用遗传算法 提取出的特征集合使用了支持向量机方法。通过使用g a 来选择有差别的 特征集合，能够做到仅用很少的内存就得到一个高识别率。j e f f r e yh u a n g 等人f 13 提出用支持向量机来解决人脸角度识别问题，支持向量机在未知的 测试集上针对三种可能的人脸角度之间进行识别的准确率是1 0 0 。 t e r r e n c es f u r e y 等人【1 4 将支持向量机用于分析d n a 微排列实验产生的有 关基因表达差异的信息数据。在许多应用中，每一个输入点可能不是完全 的属于两类中的某个类别。为此，c h u n f ul i n 和s h e n g d ew a n g1 1 5 】提出 了一个称之为模糊s v m s 的方法：为每个输入点赋予一个模糊集的隶属度， 然后再用支持向量机的方法来表示。o l i v e rc h a p e l l e 等人 16 1 发现支持向量 枫在高维空间中能够有较好的泛化能力，因此将它用在基于直方图的图像 分类中并取得了较好的结果。作为该领域最新的一些研究，m a n a b u s a s s a n o mj 研究了如何使用支持向量机的主动学习来很好的解决自然语言 处理中的非平凡问题，在实验中，选择把日文字符的分割作为一个测试的 例子。h u m al o d h i 等人1 1 埘提出了一个新的核函数以及它用在文本分析中 的近似，着重阐述了使用支持向量机来进行文本分类。 我国早在8 0 年代末就有学者注意统计学习理论的基础成果，但之后较 少研究。1 9 9 5 年以后，尤其是近几年来，许多学者已经认识到这个重要的 研究方向，正在这个领域积极的开展研究工作，一些大学或者研究所也相 继投入到这个领域的研究中来。北邮模式识别与人工智能网站 ( h t t p ：2 0 2 1 1 2 1 0 8 15 8 ) 提供了一些研究资料和国外相关研究站点的链 接，清华大学的水木清华b b s ( 2 0 2 1 1 2 5 8 2 0 0 ) 、南京大学的南大小百合 b b s ( 2 0 2 1 1 9 3 2 1 0 2 ) 也为研究者提供了一个交流的网上场所。 进一步发展和完善支持向量机的基本理论和方法以及推动支持向量机 在实际中的应用是当前亟待解决的一个问题，已经有许多学者为此做了大 量的工作，但还有很多路要走。 1 3 视频交通信息检测系统 随着我国经济建设的蓬勃发展，城市的人口和机动车拥有量也在急剧 增长，交通流量日益加大，交通拥挤堵塞现象日趋严重，交通事故时有发 生。交通问题已经成为城市管理工作中的重大社会问题，阻碍和制约着城 市经济建设的发展。因此，深入研究解决城市交通问题有着极为重要的现 实意义。要解决城市交通问题，就必须准确掌握交通参数信息，为交通控 制决策和交通流的疏导提供依据。 目前国内常见的交通信息检测方法有人工检测、地埋感应线圈、超声 波探测器、红外线检测以及视频检测等方法 1 9 1 。随着电子技术、计算机技 术、通信技术和控制技术的发展，交通检测技术也得到了长足的发展。在 各种交通检测技术中，视频检测技术已充分显示了其强大的生命力，正逐 步成为交通检测中最有前途的一种技术。国外从7 0 年代就开始了运用视 频检测技术检测交通参数的研究，并在理论和实践方面取得了令人满意的 研究结果。事实表明：这种检测技术比其它检测技术能够收集更多和更全 面的数据，同时也有能力执行更复杂的任务i 2 们。 交通流的视频检测是通过记录( 拍摄) 车流的运动过程( 图像) ，来达 到获取各种交通参数的目的。因为摄像机所记录( 拍摄) 的图像中包含了 能反映交通流状况的各种参数，通过处理这些图像，我们就可以得到所需 的各种交通参数，如车辆的存在、车流的时间平均速度、空间平均速度、 车头时距、车辆占有率等2 。对于视频检测系统来说，它可以检测摄像机 拍摄范围之内的许多指定地点交通参数，这些指定地点的几何关系图形必 须事先存入计算机中。下面介绍常见的交通参数的检测方法： 车辆存在的检测 用参数p a t 表示在检测点a ，时刻t 是否有车辆存在( 通过) ，即： p 一1 表示有车存在 1 一 0 表示无车存在 交通流量的检测 交通流量q a 是时间t 内通过检测点a 的车辆总数，即： q a = p a t 车流率的检测 车流率q a ( t ) 是单位时间内通过检测点a 的车辆数即： q a ( t ) = 警 时间平均速度v ，的检测 对于在时间t 内通过检测点a 的车辆的时间平均速度是各车在通过检 测点时的速度之平均，即： 玑 v t - 昔 其中：以。是第n 辆车通过检测点a 时的速度 空间平均速度的检测 空闻平均速度是指道路上距离较长的两点之间的车辆的平均行驶速 度，设任意两检测点a 、b 之间的距离为x ，第1 3 辆车通过a 、b 两检测 点的时间分别是，。、，则a 、b 两地之间的平均速度，即空间平均速度 是： v = 订鱼 一t 。 n - 1 车头时距、间距的检测 车头时距是前后两辆车车头之间的时间间隔，第n 辆车与第n 1 辆车 的车头时距可以用两辆车通过检测点时的时间差表示： h a h = t a n t an l 在时间t 内的平均车头时距可以用下式获得 0 4 h 。 h t a t2 苛 在时间t 内的平均车头间距是车头时距乘以平均速度，即： h s a t = m a t v t 占有率的检测 检测点a 的车辆占有率是在时间段t 内平均有车辆通过( 占有) 检测 点a 的比率： r 巴 吼r = ! = 停车次数的检测 停车次数的检测可以通过检测车辆通过检测点的速度获得，当车速低 于设定的一个速度阂值，则认为车辆停车一次。在时间段t 内的总停车次 数是检测到的所有停车次数之和，即 s r = z s t ，= l 其中：s 。= 1 表示在时刻t 有车辆停车， 车队长度的检测 视频检测系统可以检测的车队长度分为： 车辆的长度。 否则s 。= 0 无车辆停车。 运动车流的长度和停车排队 运动车流的长度是描述车辆在行进过程中，保持较小车头时距的一个 密集车队的车辆数的多少，用车辆数表示长度。这一长度可以通过判断车 6 头时距来得到，在一个连续的车流里，车头时距保持在一个阈值之内的车 辆数即为时刻t 的一个车流长度，车流长度对于车流的预报是非常重要的 参数，也是交通控制中常采用的检测参数之一。 q d = h i + 1 ( 辆) 其中：h j = 1 0 ，l , h h i 。i i h h o 。，h m 为前后两辆车的车头时距，h 。为预先设 定的车头时距阈值。 在道路交通系统中，车流的排队长度通常是指在任意时刻t ，路段上 两断面之间的排队车辆数。可以间接地用停车的车辆数来表述，即 q 。= s i ( 辆) 车辆延误的检测 在道路交通系统中，车辆延误实质是指车辆通过两地点之间所需的时 间比在正常情况下通过两地点的时间大。因此只要检测出车辆的实际行程 时间就可以得到车辆的延误，设在时间t 内，通过a 、b 两地点的车辆为q ， 任意一辆车的实际行程时间是t a b 秒，则在时间t 内通过a 、b 两地的车 辆的总延误时间是： d = 艺ta b i i q a ( 秒) 其中：i 是无延误情况下，车辆通过a 、b 两地的行程时间，单位为 秒。 通过视频检测方法，能够获得大量的交通参数。但是，通过上面的分 析，我们可以发现，很多交通参数是根据基本的交通参数：交通流量、车 辆类型和车辆行驶速度这三个参数计算而来的，还有些参数是根据多个检 测点的检测数据计算而来的。因此，对于单个检测点而言。实现交通流量、 车辆类型和车辆行驶速度的检测是视频交通信息检测系统需要解决的最 重要的问题。 通过视频检测来检测交通信息具有一定的优越性，但目前在国内城市 的应用还不是很广泛，主要是由于其检测的精度还有待于提高，所以仍然 有很多企业、学校和一些研究机构在从事视频交通信息检测的研究工作。 本文提出一种基于支持向量机的视频交通信息检测的设计方案，可以有效 地获取交通流量、车速、车型等信息。 1 4 本文的内容安排 本文在研究分析支持向量机工作机理的基础之上，提出了一种基于支 持向量机的视频交通信息检测的设计方案，通过对视频交通流的检测、处 理和分析，获取所需样本数据，采用有导师训练方法训练支持向量机识别 器。最后利用获得的识别器判断检测区域内交通流图像的类别，从而动态 跟踪车辆，实现交通流量、车速、车型信息的检测，取得了令人满意的结 果。同时由于传统的支持向量机仅适用于二值分类的情况，而实际应用中 面临的一般都是多值分类问题，因此本文在理论上和具体应用中对多分类 支持向量机的分类策略进行了探讨。 文章的具体安排如下 第二章以机器学习的基本问题开始，从理论上系统地研究了经验风险 最小化原则成立的条件、有限样本下经验风险与期望风险的关系以及如何 利用这些理论找到新的学习原则和方法等问题，进而引入函数集的v c 维 以及结构风险最小化原则这两个概念，它们是统计学习理论的基石。统计 学习理论作为一个比较完备的小样本学习理论，能够将很多现有方法纳入 其中，有望帮助解决许多原来难以解决的问题。 第三章首先分析了支持向量机的工作机理，但是由于经典的支持向量 机仅适用于解决二值分类问题，而在实际应用中一般面临的都是多值分类 问题，所以接着我们介绍了一些常用的多值分类支持向量机方法，包括一 对多以及一对一模式的二类组合分类方法，全局优化分类方法，决策树分 类方法。接下来的一章我们将多值分类支持向量机算法应用于具体问题。 第四章简要介绍了交通信息检测领域的现状，由于视频检测方法越来 越得到重视，而其在国内的研究发展还未成熟。为此，本文在介绍了视频 交通信息检测系统的工作原理后，在交通视频检测技术方面做了一些探 索，将支持向量机理论应用到视频流状态特征的检测识别，克服现有的视 频交通检测方法的弊端，并通过实验验证了该方法的有效性。 第五章对本文所做工作进行了总结，并对后续工作提出展望。 第二章统计学习理论概述 统计学习理论是一种专门研究小样本情况下机器学习规律的理论。该 理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计 推理规则不仅考虑了对渐进性能的要求，而且追求在现有有限信息的条件 下得到最优结果。统计学习理论的一个核心概念就是v c 维概念，它是描 述函数集或学习机器的复杂性或者况是学习能力的一个重要指标，在此概 念基础上发展出了一系列关于统计学习的一致性、收敛速度、推广性能等 的重要结论。 2 1 机器学习的基本问题 2 1 1 机器学习问题的表示 机器学习的基本模型如图2 1 所示2 1 。其中，系统s 是我们研究的对象， 它在一给定输入x 下得到一定的输出y ，l m 是我们所求的学习机器，输出 为多。 图2 1 机器学习的基本模型 学习的目的是根据给定的训练样本求系统输入输出之间的依赖关系。 学习问题可以一般的表示为变量y 与x 之间存在未知依赖关系，即遵循某 一未知的联合概率f ( x ，y ) 。机器学习问题就是根据n 个独立同分布观测样 本： ( x i , y 1 ) ， 2 y 2 ) ， y ) ( 2 1 ) 在一组函数 f ( x ，c o ) ) 中，求一个最优的函数f ( x ，c o o ) ，对依赖关系进行 估计，使期望风险 r ( ) = jl ( y ，f ( x ，m ) ) d f ( x ，y ) ) ( 2 2 ) 最小。其中， ，( x ，c o ) ) 称作预测函数集，国q 为函数的广义参数。 f ( x ，国) 可以表示任何函数集。l ( y ，f ( x ，c o ) ) 表示由于用f ( x ，c o ) 对y 进行预测而造成 9 的损失，称为损失函数。 有三类基本的机器学习问题；模式识别、函数拟合和概率密度估计。 不同类型的学习问题有不同形式的损失函数。 对于模式识别问题，讨论二类情况中系统输出y 只取两种值y = o ，1 ， 并令f ( x ，) ，国q 为指示函数集合( 指示函数即只有0 或1 两种取值的 函数) 。损失函数可以定义为： l ( y f ( ) ) = oi i f y fy = f i f ( x x , c o ) ( 2 3 ) 我们称指示函数给出的答案与系统输出不同的情况为分类错误。对于这个 损失函数，学习问题就成为在联合概率f ( x ，y ) 未知但数据( 2 1 ) 式已知的 情况下，寻找使分类错误最小的函数。 类似地，在函数拟合问题中，y 是连续变量，它是x 的函数，这时损失 函数可以定义为： l ( y ，f ( x ，珊) ) = ( y f ( x ，脚) ) 2 ( 2 4 ) 这样，函数拟合的问题就是在联合概率v ( x ，y ) 未知但数据( 2 1 ) 式己知的 情况下，对采用( 2 4 ) 式损失函数的期望风险( 2 2 ) 式最小化。 对于概率密度估计问题，学习的目的是根据训练样本确定x 的概率分 布，记估计的密度函数为p ( x ，) ，则损失函数可以定义为： l ( p ( 工，c o ) ) = 一l o g p ( x ，c o ) ( 2 5 ) 待求的密度函数要在损失函数( 2 5 ) 下使期望风险( 2 2 ) 式最小化。 2 1 2 经验风险最小化 由上节可知，学习的目的就是使( 2 2 ) 式所示的期望风险最小化。为 了实现这一目的，必须依赖关于联合概率f ( x ，y ) 的信息，在模式识别问题 中就是必须已知类先验概率和类条件概率密度。但是，在实际的机器学习 问题中，我们只能利用已知样本( 2 1 ) 的信息，因此期望风险无法直接计 算和进行最小化。 为此，根据概率论中大数定理的思想，采用算术平均来代替式中的数 学期望，于是定义 1n r 。( c o ) = 二z l ( y ，f ( x 。，) ) ( 2 6 ) n i = l 来逼近期望风险，称之为经验风险。所谓经验风险最小化原则( e m p i r i c a l r i s km i n i m i z a t i o n ，简称e r m ) ，就是指用对参数国求经验风险r 。 ) 的 最小值代替求期望风险r ( 珊) 的晟小值。 经验风险最小化原则是非常一般性的。解决一些特殊的学习问题的很 多传统方法，比如在回归估计问题中的最小二乘方法、概率密度估计中的 最大似然方法( m l 法) 等，都是该原则的具体实现。 仔细研究经验风险最小化原则和机器学习问题中的期望风险最小化 要求，可以发现，从期望风险最小化到经验风险最小化并没有可靠的理论 依据，只是直观上合理的想当然做法。首先，概率论中的大数定理只说明 了( 在一定条件下) 当样本趋于无穷多时r 。洄) 将在概率意义上趋近于 r ( r o ) ，并没有保证使r 。) 最小的珊4 与使r ( c o ) 最小的c o o 是同一个点， 更不能保证r ) 能够趋近于r ( o o ) 。其次，即使我们有办法使这些条 件在样本数无穷大时得到保证，我们也无法认定在这些前提下得到的经验 风险最小化方法在样本数有限时仍能得到好的结果。 2 1 3 复杂性与推广能力 经验风险最小化原理不成功的一个例子是神经网络的过学习问题。开 始，很多注意力都集中在如何使r ) 更小，但很快发现，训练误差小并 不能导致好的预测结果，某些情况下，训练误差过小反而导致推广能力的 下降，即真实误差增加。 之所以会出现这种过学习现象，一是因为学习样本不从充分，二是学 习机器设计不合理，这两个问题是相互关联的。设想一个很简单的例子， 假设有一组训练样本( x ，y ) ，x 分布在实数范围内，而y 取值在 o ，1 之间， 那么不论这些样本是依据什么函数模型产生的，只要用函数f ( x ，口) = s i n ( a x ) 去拟合这些样本点( 其中a 是待定的参数) ，总能够找到一个d 使训练误差 为0 ，但显然得到的这个“最优”函数并不能正确代表原来的函数模型。 出现这种现象的原因，就是试图用一个复杂的模型去拟合有限的样本，结 果导致丧失了推广能力。在神经网络中，如果对于有限的训练样本来说网 络的过学习能力超强，足以记住每一个训练样本，此时经验风险很快就可 以收敛到很小甚至零，但却根本无法保证它对未来新的样本能够得到好的 预测。这就是有限样本下学习机器的复杂性与推广能力之问的矛盾。 在很多情况下，即使已知问题中的样本来自某个比较复杂的模型，但 由于训练样本有限，用复杂的预测函数对样本进行学习的效果通常也不如 用简单的预测函数，当有噪声存在时就更是如此。在文献1 2 2 1 中给出了一个 实验例子，在有噪声条件下用二次模型y = x 2 产生l o 个样本，分别用一个 一次函数和一个二次函数根据经验风险最小化的原则去拟合，结果显示， 虽然真实模型是二次多项式，但由于样本数目有限且受到噪声的影响，用 一次多项式预测的结果更接近真实模型。同样的试验进行了1 0 0 次，7 l 的试验结果使一次拟合优于二次拟合。 由此可以看出，在有限样本情况下， ( 1 ) 经验风险最小并不一定意味着期望风险最小： ( 2 ) 学习机器的复杂性不但与所研究的系统有关，而且要和有限的 学习样本相适应。 2 2 统计学习理论 统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理 论。它从理论上系统地研究了经验风险最小化原则成立的条件、有限样本 下经验风险与期望风险的关系以及如何利用这些理论找到新的学习原则 和方法等问题。统计学习理论主要包括以下四方面的内容： ( 1 ) 经验风险最小化原则下统计学习一致性的条件： ( 2 ) 在这些条件下关于统计学习方法推广性界的结论； ( 3 ) 在这些界的基础上建立的小样本归纳推理准则： ( 4 ) 实现这些新原则的实际方法( 算法) 。 其中，最有指导性的理论结果是推广性界的结论，与此相关的一个核心概 念是v c 维。 2 , 2 1 函数集的v c 维 为了研究函数集在经验风险最小化原则下的学习一致性问题和一致性 收敛的速度，统计学习理论定义了一系列有关函数集学习性能的指标，其 中最重要的是v c 维( v a p n i kc h e r v o n e n k i sd i m e n s i o n ，简称v c 维1 ，它是 统计学习理论中的一个核心概念，而且是目前为止对函数集学习性能的最 好描述指标。 模式识别方法中对v c 维的直观定义是：一个指示函数集 q ( z ，c o ) ，国e q 的v c 维，是能够被集合中的函数以所有可能的2 “种方式分 为两类的向量z l ，z2 ，z h 的最大数目h ，即能够被这个函数集打散的向量 的最大数目。如果对任意的n ，总存在一个n 个向量的集合可以被函数集 q ( z ，c o ) ，国q 打散，那么函数集的v c 维就是无穷大。有界实函数的v c 维可以通过用一定的阈值将它转化成指示函数来定义。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量 越大) 。遗憾的是，目前尚没有通用的关于任意函数集v c 维计算的理论， 只对一些特殊的函数集知道其v c 维，比如在n 维实数空间中线性分类器 和线性实函数的v c 维是n + l ，而f ( x ，口) = s i n ( 僦) 的v c 维则是无穷大。对 于一些比较复杂的学习机器，其v c 维除了与函数集有关以外，还受学习 算法的影响，其确定更加困难。 对于2 维空间的3 个点，如果它们属于不同的两种类别，则一定可以找 到一条直线，把这两类点打散，如图2 2 ( a ) 所示；对于2 维空间的4 个点，如 图2 2 ( b ) 所示，其中点2 l 和z 3 标为类别1 ，点2 2 和z 4 标为类别1 ，那么此 时用一条直线不能把这两类点打散。因此可以看出平面中直线集的v c 维 等于3 。 2 2 2 推广能力的界 伴。 争吲 r ( b p 图2 2 v c 维示意图 统计学习理论系统地研究了各种类型函数集的经验风险和实际风险之 间的关系，即推广性的界，关于两类分类问题有如下结论：对指示函数集 中的所有函数( 包括使经验风险最小的函数) ，经验风险和实际风险之间 至少以概率l - 玎满足如下关系： r ( o ) r e i n p ) 4 - j h ( 1 n ( 2 n h + _ 1 ) - l n ( r 4 ) ( 2 7 ) -j 其中h 是函数集的v c 维，n 是样本数。 由此可见，学习机器的实际风险由两部分组成：一是经验风险( 训练 误差) r 。( 国) ，另一部分称为置信范围( c o n f i d e n c ei n t e r v a l ) 。置信范围 和学习机器的v c 维h 以及训练样本数n 有关，因此，式( 2 7 ) 可以简单 地表示为： ) - r e m p ( 咖痧( ( 2 8 ) 式( 2 7 ) 和( 2 8 ) 给出了关于经验风险和实际风险之间差距的上界，反 映了根据经验风险最小化原则得到的学习机器的推广能力，因此称作推广 能力的界。 从( 2 8 ) 式可以看出，当h n 较大( 即样本数n 较少) 时，置信范围一 较大，用经验风险近似实际风险就会有较大的误差，用经验风险最小化取 ， 一 0 ，若y = 1 ( 3 1 ) w x - i - 6 0 为某个指定的常数，它控制 对错分样本的惩罚程度。 线性可分模式的最优化问题是作为一种特殊的情形包含在刚才所述的 线性不可分模式的最优化问题中。特别的，在式( 3 1 4 ) 和式( 3 15 ) 中对所 有i 令 。= 0 即可得到相应的线性可分情况时的形式。 不可分模式和可分情况的差别就在于可分模式的约束条件2 0 在不 可分模式中换为了更严格的条件0 s 1 2 ，c 。除了这一修正，不可分情况的 约束最优化问题以及权值向量脚和偏差b 的最优值的计算都和线性可分情 况中的过程是相同的。 3 1 2 非线性支持向量机 在