（通信与信息系统专业论文）复杂背景下的头肩像检测与定位.pdf

摘要 头肩图像检测是人体分析研究中受关注的研究方向，是人脸检测的第一 步，也是行人检测的基础。头肩图像检测在智能监视系统和基于内容的图像 索引等方面都有广泛的应用，因而研究快速而且准确的头肩图像检测技术具 有十分重要的意义。 本文研究的是在复杂背景下对灰度图像中头肩像的检测问题，从基于样本 学习的方法出发，提出了一种基于支持向量机( s v m ) 和离散小波变换( d w t ) 的头肩像检测算法。该算法由训练和检测两部分组成。i ) i l 练过程是收集大量 头肩样本和“非头肩”样本，然后将训练样本图像进行h a a r 小波变换，选择 变换后图像的低频子带的小波系数作为特征，训练一个由线性s v m 分类器和 非线性s v m 分类器组成的复合分类器。检测阶段应用训练好的复合分类器对 图像进行检测，以确定图像中头肩像的位置。 论文给出了使用该算法检测头肩图像的实验结果。实验结果表明，由8 5 张包含1 5 3 个头屑图像组成的测试图集中，其正确翠达到8 7 5 8 。 将陔算法应用到动态头肩像检测，采用基于运动检测的背景分离技术获得 图像中可能存在的头肩像区域，然后采用基于s v m 的方法在可能存在的头肩 像区域进行检测。因为检测的区域较小，所以这种方法既保证了检测的准确 性同时也为人体实时检测奠定基础。 关键词：头肩图像检测；支持向量机：离散小波变换 a b s t r a c t h e a da n ds h o u l d e rd e t e c t i o ni s o n eo ft h e i m p o r t a n tp r o b l e m s o n h u m a nb o d ya n a l y s i s i ti st h ef i r s ts t e po ff a c ed e t e e t i o na n dt h e b a s eo fp e d e s t r i a nd e t e c t i o n ，i tc a nb ea p p i e dt oc o n t e n t b a s e di m a g e i n d e x i n ga n ds m a r ts u r v e i l l a n c es y s t e m s i t ise s s e n t i a lt od e v e l o p r o b u s ta n de f f i c i e n ta l g o r i t h m st od e t e c th e a da n ds h o u l d e r s i nt h i st h e s i s ，w ep r e s e n t a na l g o r i t h mb a s e do ns u p p o r tv e c t o r m a c h i b e ( s v m ) a n dd i s c r e t ew a v e l e tt r a n s f o r m ( d w t ) t od e t e c tu p p e rb o d y o fh u m a ni ng r a yi m a g e su n d e rc o m p e xb a c k g r o u n d t h i sa 1g o r i t h mi s m a d eo ft r a i n in gs e c t i o n a n d d e t e c t i n g s e c t jo n fl o to f h e a d a n d s h o u l d e rs a m p l e sa n d “n o th e a d a n ds h o u l d e r ”s a m p l e sa r e c o l l e c t e da st r a i n i n ge x a m p l e s f e a t u r e sa r ee x t r a c t e df r o mw a v e l e t c o e f f i c i e n t so ft h e s et r a i n i n gi m a g e s ，a n du s e dt ot r a i nac o m b i n e d c l a s s i f i e rw h i c hc o n s i s t so fal i n e a rs v mc l a s s i f i e ra n dan o n l l n e a r s v mc l a s s i f i e r t h ed e t e c t i o ns y s t e mw o r k sb yt e s t i n gw h e t h e rt h e r e i sah e a da n ds h o u d e rj ne a c hw i n d o wo ft h e i m a g e t h et h e s i sg i v e st h ee x p e r i m e n tr e s u l to fo u ra l g o r jt h m t h er e s u l t s h o w st h a tt h ea l g o r i t h mi sa b l et oo b t a i na c c u r a c yo f8 7 5 8 o v e ra t e s ts e to f8 5 i m a g e sc o n t a i n i n g1 5 3t a r g e t s w eu s et h i sa l g o r i t h mt od e t e c tt h em o t i o n i m a g e sa n da d o p tt h e b a c k g r o u n ds e p a r a t et e c h n i q u et og e tt h ea r e aw h i c hh a st h eu p p e rb o d y o fh u m a n ，a n dt h e na d o p ts w m e t h o d ，w h i c hh a sv e r yh i g hd e t e c t i o nr a t e ， t od e t e c ti nt h i sa r e a b e c a u s ei to n l yd e t e c t st h i ss m a l la r e a t h is m e t h o dc a nb ec o n s i d e r e da st h ef o u n d a t i o no fr e a lt j m eh u m a nm o t i o n d e t e c t i o na sw e la s g u a r a n t e e st h ea c c u r a c yo fd e t e c t i o n k e y w o r d s ：h e a d a n d s h o u id erd e t e c ti o n ；s u p p o r tv e c t o rm a c hib e ； djs c r e t ew a v ele tt r a n s f o r m 1 绪论 1 1 课题研究的意义 头肩图像是手持无限终端或可视电话中最常见的一种图像模式，它广泛存 在于可视电话、视频消息、手持无线终端、电视新n , w 电视会议等视频业务 中。复杂背景下的头肩像检测和定位就是在对输入图像的背景不加任何控制 条件下，检测是否有头肩像存在，若存在，则标定其位置。 研究头肩像检测定位具有十分重要的作用。首先可作为人脸检测定位识别 的第一步。人脸是一类具有相当复杂的细节变化的自然结构目标，因此人脸 的不同姿态、不同的成像条件、不确定的饰物以及复杂的背景条件等都给人 脸的检测与识别提出t j ! j t 战【1 1 。利用头肩像进行检测定位不仅减少了复杂背景 及成像条件等因素的影响，同时也为人脸的正确识别创造了有利的先期条件。 头肩像检测的另一个重要应用是在智能交通中的行人检测 2 1 ，这也是近几年目 标检测中的一个热点问题。由于人是复杂的变形体，人体四肢关节自由度多， 运动范围很大，因此不能用单一的模板来表征人体。同时行人的衣着颜色、 步态等的不同和周围环境的不断变化使得行人检测这一热点问题也成为目标 检测中的难点问题之一。利用头肩像检测不易受其他因素( 例如，人体的步 态、衣着颜色、环境等) 的干扰这一有利的条件，为行人的准确检测与定位 提供了先决条件。 目前国内外学者对头肩像检测问题的研究主要是以人脸检测、行人检测和 人体运动分析为目的的。每年在i e e e 的f g ( i e e ei n t e r n a t i o n a lc o n f e r e n c eo n a u t o m a t i cf a c ea n dg e s t u r e r e c o g n i t i o n ) 、i c i p f i n t e m a t i o n a l c o n f e r e n c eo n i m a g ep r o c e s s i n 曲、c v p r ( c o n f e r e n c e o n c o m p u t e r v i s i o na n dp a t t e r n r e c o g n i t i o n ) 等重要国际会议上都有大量的相关论文发表。并且对头肩像的检 测定位在视频检索( v i d e oi n d e x ) 、视频通信( v i d e oc o m m u n i c a t i o n ) 、智能监视 系统( s m a r ts u r v e i l l a n c es y s t e m s ) 、虚拟现实( v i s u a lr e a l i t y ) 、视频会议( v i d e o c o n f e r e n c i n g ) 和智能人机交互( i n t e l l i g e n t h u m a n c o m p u t e r i n t e r f a c e s ) 等方面都 有广泛的应用。 1 2 国内外的研究状况 目前在对于头肩像检测的方法中较典型的方法是模板匹配法，即利用头肩 像的几何信息，通过某种方法建立能够较全面的表示出头肩像特征的模板， 应用该模板确定头肩像的位置。模板匹配方法的基本思想是：计算测试样本 与参考模板之间的相似度，以其是否大于某一预先设定的阈值来判断测试样 本是否为需要检测定位的目标。模板分为固定模板和弹性模板1 3 】两种。 a b r o g g i l q 和d b e y m e r 和k k o n o l i g e l 5 1 应用一个q 模型表示头肩像，建 立不同尺寸的多个模型，利用这些从租到细的头肩像模型，根掘模板与目标 之l 、自j 的距离大小进行检测以达到检测行人的目的。 头肩像检测定位对于人脸特征提取和基于模板的图像编码有重要的意义。 里墨塑墨! 塑兰旦堡监型生童丝一一 在文献 6 】中陈启泉等人采用基于几何特征的人脸识别的方法，设计一个初步 的自动人脸特征提取系统。在该方法中，作者应用s o b e l 算子对输入图像进行 边缘检测，在边缘图中从上至下，从左到右逐行扫描，将相连的象素点构成 连续的曲线段，并对这些曲线段进行连接合并，找到头像的位置a 然后在此 基础上进行人脸特征的提取并最终完成对人脸的识别。该系统对人脸虽然有 很好的检测率但系统所处理的是针对证件类型照片的识别，照明条件一般比 较好。 此外，v g o v i n d a r a j u 等人【7 q 0 提出的基于人脸几何轮廓特征，利用图像中 部分线条推测拟合检测人脸的方法也可用于对于头肩像的检测。但这种方法 需要一些先验知识，且误判时常发生。对于复杂背景的图像，轮廓提取和线 条拟合的计算量极大。 文献 1 l 】提出的利用椭圆模板实现单人脸正面图像的检测方法也可用于背 景简单的头肩像检测。首先对图像进行二值化处理，然后利用椭圆模板进行 检测。泼方法可用于背景变化不大的视频会议或监控系统中的目标跟踪。 除了应用模板匹配的方法外，基于统计学习的方法也可用于头肩像的检 测。统计学习的方法可看作是在给定样本中识别目标样本的模式识别问题。 该方法将目标区域看作一类模式，使用大量的正反样本训练、构造分类器， 通过判别图像中所有可能区域属于哪类模式的方法实现目标的检测。目前普 遍采用的是人工神经网络和支持向量机的方法。基于统计学习的方法不依赖 于人脸的先验知识和参数模型，而是采用了实例学习的方法获取模型的参数， 在统计意义上更可靠，并且可以通过增加学习的实例可以扩充检测模式的范 围、提高检测系统的鲁棒性；但是该方法在前期需要对样本进行大量的训练 才能达到一定的可靠性，同时利用该方法进行检测时需要对所有可能的检测 窗口进行搜索，计算复杂度很高，因此减少训练用的样本数量和提高检测的 速度是该方法目前的难点问题。 文献 1 2 1 中应用支持向量机对头肩像及人体进行分析检测，取得了较高的 检测率，同时将此方法应用在智能交通中，利用汽车中的视频摄像机进行行 人检测和跟踪。目前有很多方法是将支持向量机同其他的检测方法相结合， 形成一个级联的检测系统以得到更高的检测率和更快的检测速度。 p a p a g e o r g i o n 等人1 13 1 提出基于事例的应用组件的方法对人体进行检测。该方法 中，p a p a g e o r g i o n 等人将人体分成头肩、左右手臂和左右腿五部分。分别对每 部分应用小波变换进行处理，提取特征，并输入到支持向量机中进行分类判 断，最后将结果进行组合检测行人。该算法提出了级联检测的思想，提高了 检测的准确率，并对背景的要求不高，可以不受光照等条件的限制。该算法 不仅可以对人进行检测同时也可用于对人体各部分的检测。 o r e n 等人【1 4 。16 】利用小波变换，建立了一个用以表征人体的小波模板，并 利用此模板进行特征的提取，应用支持向量机进行分类检测行人。该方法不 仅能检测出行人的正面，同时也能检测出背对着镜头的行人。 此外，在对人体的分析【7 i 中，m u m w a il e e 等人用编码的形式表征头肩像 并将其应用于人体头部的检测定位，为人体的分析提供条件。 复杂背景下的头肩像检测与定位 近几年国内外对头肩像检测问题的研究主要是以人脸检测、行人检测及 人体运动分析为目的的。面向头肩像的人脸检测大多针对正面端讵的人脸， 对多姿念的人脸的检测( 特别是侧面人脸的检测) 还存在很大的困难，有效 的方法不多。另外，在人体运动分析的研究中，应用检测到的头肩像信息进 行人体定位、分析也将是一个研究方向，同时将头肩像检测应用到智能交通 中进行行人检测【4 j 也是头肩像检测识别走向实际应用的重要一步。 1 3 应用领域 近些年来，头肩像检测定位在计算机视觉领域受到研究者的关注。这是 因为设计一个能够自动检测定位头肩像的算法，并应用头肩像检测定位人脸 以及对人体进行分析与跟踪的系统有着许多应用场合。具体说明如下： ( 1 ) 智能监控 这里所指的“智能”包含两个方面的含义。一方面是指系统能够在一定 的场景中检测是否有人的出现，防止由于非人运动所造成的错误报警，例如 因为动物活动或者刮风摇动树枝等等而造成的误报。另外一方面是指系统能 自动将检测到的人脸与数据库存储的罪犯的人脸相匹配，确定是否是罪犯并 采取相应的报警措施。在对安全要求敏感的军事区域、国界、机场、停车场、 银行、住宅小区等地方都需要智能监控设施。而基于计算机视觉的头肩像检 测技术则可以实现全天实时监控，并能够自动对摄像机捕获的数据进行分析， 若发现可疑人物则及时发出警报，同时也减少了雇佣大批监控人员的费用； 而用于交通管理、公共场所、超市等则可以自动监控以实现流量控制等。 ( 2 ) 虚拟现实技术 应用头肩像检测定位，可以实现跟踪现实世界人的姿态，从而创建一个虚 拟的仿真场景，实现人与这个虚拟世界的交互。该领域的具体应用涉及视频 游戏，虚拟摄影棚，计算机动画等方面。 ( 3 ) 高级人机接口 在此领域中，对头肩像进行检测定位，进而实现对人体运动信息的捕获可 以帮助我们实现智能的人机交互。例如在高噪音场合( 如机场、车间等) 可 以进行比语音方便精确的交流或信息输入，也可以用于机器人绕过障碍物等。 ( 4 ) 运动分析 分割图像中的人体部分并在图像序列中跟踪分析感兴趣的关节运动，对于 建立人体的几何模型、解释人体的运动行为机制从而提高它的运动性能有着 积极的推动作用，这可以应用于体育运动、舞蹈等训练中；传统的步态分析 是肌电图学、关节动力学的研究范畴，通过分析病人的行为和步态，判断其 疾病或受伤情况，以便做出有效的治疗；另外与生物特征识别技术相结合的 视觉监控，特别是非接触式远距离的身份识别可以实现远距离情况下人的检 测、分类和识别，从而增强国防、民用等场合的保护能力。 1 4 研究目标及研究内容 针对头肩像的检测方法进行理论和实际的研究，找到一个基本可实用的复 3 复杂背景下的头肩像榆测与定位 杂背景下头肩像检测定位的方法，实现对静态及动态头肩像的检测，为今后 人体运动分析跟踪的研究奠定基础。 本文研究的是在背景条件不受限制的情况下，对灰度图像中头肩像进行检 测问题。研究从基于样本学习的方法出发，提出了一种使用双层支持向量机 ( s v m ) 和离散小波变换( d w t ) 的头肩像检测算法。该算法由训练利检测 两部分组成。训练过程是收集大量头肩样本和“非头肩”样本，然后将训练 样本图像进行h a a r 小波变换，选择变换后图像的低频子带的小波系数作为特 征，训练一个由线性s v m 分类器和非线性s v m 分类器组成的复合分类器。 检测阶段应用训练好的复合分类器对图像进行检测，以确定图像中头肩像的 位置。 1 5 章节安排 第一章简单介绍了头肩像检测及国内外的研究情况，然后详细介绍了一些 目前国内外比较成功的头肩像方法，提出了研究的方向和内容。 第二章简要介绍了统计学习理论的基本内容，讨论了如何建立以统计学习 理论为基础的支持向量机的头肩像检测方法。 第三章介绍了在一定的限制条件下，采用改进的差分法获得复杂背景中的 运动目标存在的区域，然后应用支持向量机方法确定头肩像的具体位置，同 时给出了一些试验结果。 第四章给出了基于支持向量机的头肩像检测方法的实验结果。 第五章对全文算法进行总结及以后工作的展望。 4 复杂背景下的头肩像检测与定位 2 基于支持向量机的头肩像检测方法 2 1 引言 头肩像检测属于计算机视觉和模式识别领域。头肩像检测就是给定一幅任 意的图像，确定这幅图像中是否含有头肩像，如果头肩像存在则标定其位置。 头肩像检测定位可以作为人脸检测的第一步，也是行人检测中的关键一步， 更是人体运动分析跟踪的基础。通过第一章中对当前头肩像检测算法的总结 分析，发现基于统计学习理论的检测方法得到国内外的重视，成为目前模式 识别、计算机视觉等领域的研究热点。 传统的统计学所研究的是渐进理论，也就是当样本数目趋向于无穷大时的 极限特性，但是在实际应用中该前提一般无法满足，因此一些理论上很成熟 的学习方法在实际中的表现却可能不尽如人意，比如说如何确定网络结构的 问题、过学习( o v e r - f i t t i n g ) 问题、局部极小点问题等，这从本质上来说就是 因为理论上需要无穷样本与实际中样本有限的矛盾造成的。 与传统统计学的方向不同，v a p n i k 1 8 】等人提出了一个较完善的基于有限样 本的理论体系统计学习理论。统计学习理论( 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 ) 是一种专门研究小样本情况下机器学习规律的理论，它试图从更本 质上研究机器学习问题，以解决神经网络中的固有缺陷。该理论针对小样本 统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑 了对渐进性能的要求，而且追求在现有有限信息的条件下得到最优结果。 v a p n i k 等人从六、七十年代开始致力于此方面的研究，到九十年代中期，随 着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质 性进展，统计学习理论开始受到越来越广泛的重视。由于统计学习理论是建 立在一套较坚实的理论基础之上的，为解决有限样本学习问题提供了一个统 一的框架。它能将很多现有方法纳入其中，有望帮助解决许多原来难以解决 的问题( 比如神经网络结构选择问题、局部极小点问题等) ；同时，在这一一理 论基础上发展了一种新的通用学习方法一一支持向量机 1 9 1 ( s u p p o r tv e c t o r m a c h i n e ，简称s v m ) ，它已初步表现了很多优于已有方法的性能。 目前，支持向量机算法由于其出色的学习能力进面成为机器学习领域的研 究热点，并在很多领域内得到成功的应用，如人脸检测【2 0 j 、人脸识别、手 写体数字识别1 2 2 等。 对于头肩像来说，可以看作是两类模式的问题，而建立在统汁学习理论基 础上的支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 的优势就在于对两类 模式能够很好的分类，因此s v m 方法对于头肩像检测的两类模式识别问题是 非常适用的。本文提出的头肩像检测方法就是基于支持向量机的算法。 本章首先对统计学习理论做一个简单的介绍，给出s v m 的理论基础：然 后介绍了s v m 的具体学习算法及目前常用的训练算法，提出用于头肩像检测 的方法。 复杂背景下的头肩像检测与定位 2 2 统计学习理论 学习的定义是如果一个系统能够通过执行某种过程而改进它的性能，这就 是学习。过程、系统和改变性能是学习的三个要点。机器学习的目的是根据 给定的训练样本求出对系统输入输出之间依赖关系的估计，使它能够对未知 样本的输出做出尽可能准确的预测，为此，可以通过下面定义的风险函数( r i s k f u n c t i o n ，也可称为期望风险) 对学习效果进行评估。 对n 个相互独立并服从同一分布的观测样本，假定系统在给定输入为x 的 情况下输出为y ，且变量y 与x 之间存在未知依赖关系，即遵循未知的联合概 率f ( x ，y ) ，那么学习机器的期望风险定义为r ( w ) = i l ( y ，f ( x ，w ) ) d f ( x ，y ) 。其 中 f ( x ，w ) ) 称作预测函数集，w 为函数的广义参数，l ( y ，f ( x ，w ) ) 称为损失函 数，表示由于用f ( x ，w ) 对y 进行预测而造成的损失。期望风险是机器学习在 整个样本空间中出错率的数学期望。 学习的目的就是为了使期望风险最小，为达此目的，必须依赖联合概率 f ( x ，y ) 。但是，在实际的机器学习问题中，这条件是未知，只能利用已知 训练样本的信息，因此期望风险无法直接计算和进行最小化。为此，在实际 应用中，一般根据大数定理即采用算术平均来代替，利用求经验风险 1h r 。，( w ) = 二三( m ，f ( x 。，w ) ) 的最小值来代替求期望风险的最小值即为经验风 百 险最小化原则( 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 ) ，公式中五的下标表示经验 风险。 经验风险最小化原则是目前绝大多数模式识别方法的基础。但事实上，用 e r m 准则代替期望风险最小化并没有充分的理论依据，只是直观上合理的想 当然做法，但这种思想却在多年的机器学习方法研究中占据了主要地位。人 们一直将大部分注意力集中在如何更好地求取最小经验风险上。 统计学习理论是一种专门研究小样本统计估计和预测的理论。它从理论上 较系统地研究了经验风险最小化原则成立的条件、有限样本下经验风险与期 望风险的关系及如何利用这些理论找到新的学习原则和方法等问题。它的一 个核心概念就是v c 维( v cd i m e n s i o n ) 概念，它是描述函数集或学习机器的 复杂性或者说是学习能力( c a p a c i t yo f t h em a c h i n e ) 的一个重要指标，在此概 念基础上发展出了一系列关于统计学习的一致性( c o n s i s t e n c y ) 、收敛速度、 推广性能( g e n e r a l i z a t i o np e r f o r m a n c e ) 等的重要结论。其内容主要包括四个 方面”1 ： ( 1 ) 经验风险最小化准则下统计学习一致性的条件： ( 2 ) 在这些条件下关于统计学习方法推广性的界的结论； ( 3 ) 在这些界的基础上建立的小样本归纳推理准则； ( 4 ) 实现新准则的算法。 2 2 1v c 维 统计学习理论的一个核心概念就是v c 维( v cd i m e n s i o n ) 概念，它是描 6 复杂背景下的头肩像榆铡与定位 述函数集或学习机器的复杂性或者说是学习能力( c a p a c i t y o f t h e m a c h i n e ) 的 一个重要指标。模式识别方法中v c 维的直观定义为，对于一个指示函数 ( i n d i c a t i o nf u n c t i o n ) 集( 指示函数即只有0 或1 两种取值的函数) ，如果存 在h 个样本能够被函数集中的函数按所有可能的2 6 种形式分开，则称函数集 能够把h 个样本打散( s h a t t e r i n g ) ：函数集的v c 维就是它能打散的最大样本 数目h 。若对任意数目的样本都有函数能将它们打散，则函数集的v c 维是无 穷大。 例如，在平面上3 个点的任意组合可以用直线分割开，但4 个点的任意组 合则不能用直线分割开，因此平面上直线函数的集合的v c 维数是3 。在这种 情况下，恰好等于自由参数的数目，但在一般情况下并非如此，例如s i n ( a x ) 具 有无限维的v c 维数。 ， ? ， i x ”二一、 1 17 -、 r 。芦：二弋 卜、。一! ， i 7 、“。一一- “ i 7 i ： ， i 二 ， 幽217 c 维事例图 f i g u r e2 1e x a m p l eo f v cd i m e n s i o n v c 维是学习机器能够正确划分的任意二值标识的最大点集样本数，它表 征了学习机器的最大学习能力，是衡量学习机器复杂程度的一个指标，v c 维 越大则学习机器越复杂( 容量越大) 。但是到目前为止，我们只是对一些特殊 的函数集知道其v c 维，比如在n 维实数空间中线性分类器和线性实函数的 v c 维是n + l 。对于一些较复杂的学习机器( 如神经网络) ，其v c 维除了与 函数集有关外，还受学习算法等的影响，其确定更加困难。对于给定的学习 函数集，如何用理论或实验的方法计算其v c 维是当前统计学习理论中有待研 究的一个问题l “l 。 2 2 2 推广性的界 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险 之间的关系，即推广性的界。统计学习理论中关于经验风险和实际风险之间 关系的重要结论是分析学习机器性能和发展新的学习算法的重要基础【18 1 。 v a p n i k 【1 8 】证明期望风险r ( 叻满足这样的关系，即任取刁满足o 町 一 问 题。根据约束最优化问题的k a r u s h k u h n t u c h e r 条件( 简称k k t 条件，见附 录1 ) ，这个优化问题的解须满足 q m ( w t + 6 ) 一1 】= 0 ，i = 1 ，( 2 1 2 ) 对多数样本a i 将为零，取值不为零的a i 对应于使式( 2 3 ) 中等号成立的 样本，即支持向量( s u p p o r tv e c t o r s ) ，它们通常只是全体样本中的很少一 部分。对于学习过程而言，支持向量是训练样本集中的关键元素，它们距离 决策边界最近：如果去掉所有其他训练点( 或移动位置但不穿越日或何，) ， 再重新进行训练，得到的分类面是相同的。 解上述问题后，得到的最优分类函数就是： f ( x ) = s g n f y , a i ( 薯x ) + 6 0 1 l 支持向量 j ( 2 1 3 ) 其中z 。为支持向量，口。是对应的l a g r a n g e 系数，6 。是常数，它可由任意一个 支持向量求得，或通过两类中任意一对支持向量取中值求得。在通过训练得 到最优超平面后，对于给定的未知样本x ，只需计算厂( x ) 就可判定未知样本z 所属的分类。 复杂背景下的头肩像榆测与定位 最优分类面是在线性可分的前提下讨论的，在线性不可分的情况下，由于 某些样本不满足式( 2 3 ) 的约束，因此引入一个非负的松弛变量，i = 1 ，l 来放宽条件式( 2 3 ) 。这样( 2 3 ) 式就变成： y ； ( w t ) + 6 2 1 一董，f = 1 ，一，7 ( 2 1 4 ) 专0 ，i = 1 ，f 显然当分类出现错误时，专 o ，于是专就是训练集中错分样本数的总和。 这样就需要在目标函数式( 2 5 ) 中为分类误差分配一个额外的代价函数，即 引入错误惩罚分量c l 喜f 。所以，现在的目标函数就变为求： 卟妒圭晰+ c ( 妻戋) 泣 的最小值，即 m 嘶i n l 2 2 + c ( 喜茧 s l f “( w 置) + 6 1 一参，i = 1 ，f ( 2 1 6 ) 专0 ，i = 1 ， 其中c 0 是错误惩罚因子，一个指定的常数，它的作用就是控制对错分 样本进行惩罚的程度，常数c 越大对错误的惩罚越重。 现在的问题就是求解( 2 1 6 ) 式，即折中考虑最大分类间隔和最小错分样 本，就得到了线性不可分情况下的最优超平面，即 m a xr v ( a ) = 一妻q 口，m 乃( x j ) s 。0 a ，c ，i = 1 ，l ( 2 i 7 ) 呸m = 0 具体推导过程如下： 由( 2 1 6 ) 式，得到相应的l a g r a n g e 函数 l ( w ，6 ，口，掌) = 昙| 1 w l j 2 一圭 只w , x i + b ) 一1 + 当 一圭h 专 由k k t 条件可知，最优解满足 兰= c 一口一= 0 c q y ，( w z + 6 ) 一l + 毒 = o v 2 8 。，“， 。0 v i ( 2 1 8 ) ( 2 1 9 a ) ( 2 1 9 b ) ( 2 1 9 c ) 复杂背景下的头肩像检测与定位 ，= 0v i ( 2 1 9 d ) 由式( 2 t g a ) 一一式( 2 t g d ) 可知，若口 c ，则毒= 0 。于是只需要选择f 满足0 口 h 将输入空间的样本映射到高维特征空间 h 中，当在特征空间中构造最优超平面时，训练算法仅使用特征空间中的点 积， 即中( ) 巾( x ，) 。所以，若能找到一个函数f ) ，使得 世( 置，毛) = 中瓴) 审) 成立。这样，在高维空间中实际上只需进行内积运算， 甚至不必知道变换m 的形式。 只要一种函数k ( 葺，x ，) 满足m e r c e r 条件( 附录2 ) ，它就对应某一变换空 问中的内积。因此，在最优分类面中采用满足m e r c e r 条件的内积函数世伍，x ) 就可以实现某一非线性变换后的线性分类，而且计算复杂度也没有增加，此 时的二次规划问题的目标函数变为 缈( 口) = ：q 一言a ：e y y j k ( x ，一) ( 2 2 0 ) l = l o j ，2 l 决策函数就成为 厂o ) ：。g n m 哆足( 蕾石) 十 ( 2 2 i ) l 立持向盈 j 并且算法的其他条件均不变。由于最终的决策函数中实际只包含样本与支持 向量的内积以及求和，因此识别时的计算复杂度取决于支持向量的个数。 墨茎笪星! 塑兰旦堡丝婴兰蔓塑l 一 由图2 4 可以看出，支持向量机求得的决策函数形式上类似于一个神经网 络，其输出是若干中间层节点的线性组合，而每一个中问层节点对应于输入 样本与一个支持向量机的内积。 。 在图2 4 中输入向量x = ( z l ，b ) ，基于j 个支持向量x 1 c ，x ，的非线性变 换( 内积) ，输出( 决策函数) 为y = s g n ( a 。y ，k ( x ，x ) + 6 ) ，权值w ，2 c q y ，。 圈2 4 支持向量机示意图 f i g u r e2 ，4s u p p o r t v e c t o rm a c h i n e ( s v m ) d i a g r a m 常用的核函数有以下几种： 1 ) d 阶多项式( p o l y n o m i a l c l a s s i f i e r so f d e g r e ed ) ： k ( x ，t ) ( x e 葺) + 1 “ ( 2 2 2 ) 得到的支持向量机是一个d 阶多项式分类器。 2 ) 高斯径向基函数( g a u s s r a d i a lb a s i sf u n c t i o nc l a s s i f i e r s ) ： k ( x ) = e x p ( - l x - - x i l2 居2 ) ( 2 2 3 ) 得到的支持向量机是一种径向基函数分类器。它与传统的径向基函 数方法的基本区别是，这里每一个基函数的中心对应于一个支持向 量，它们以及输出权值都是由算法自动确定的。 3 ) s i g m o i d 函数： k ( x ，x 1 ) = t a n h ( u ( x x 。) + c ) ( 2 2 4 ) 支持向量机实现的是一个两层的多层感知器神经网络，只是在这 里不但网络的权值、而且网络的隐层节点数目也是由算法自动确定 的。 此外，小波函数也可以用来构造核函数，文献 2 5 1 给出了一种在神经网络 学习中常用的小波函数。用 ( x ) 表示该小波函数，即 b ( x ) = c o s ( 1 7 5 x ) e x p ( 一x 2 2 ) ( 2 2 5 ) 由此得到的尺度为s 的小波核函数为 1 5 星型堕墨! 塑墨旦堡里竺兰兰坐一 m ，x + ，= 晰c o s 弼剖唧 _ 学 z e ， 因此得到的分类函数为 似一扣办小粤h 一学州汜z ， 也可以采用墨西哥草帽小波来构造小波核函数，用h a ( x ) 来表示墨西哥草帽小 波，其形式为 h a ( x ) = ( 1 一x 2 ) e x p ( - x 2 2 ) ( 2 2 8 ) 掷，x ，铷一h 一譬 z 。， m 闰s n p 讣h 一唧 + 6 汜s 。， 当然，也可以构造其他的小波核函数和相应的支持向量机，这旱就不一一 介绍了。 支持向量机同神经网络相比，其相同点在于两者都是从经验数据集中学 习，是数据驱动( b a t ad r i v e r ) 的学习机。两者在结构上都可以表示为网络 结构，且数学表达也相似。在功能上，两者都可以作为通用逼近器以任意精 度逼近任何函数。但是神经网络学习的目标函数是经验风险最小化，得到 个小的训练误差，而支持向量机学习的目标函数是结构风险最小化，得到一 个小的泛化误差。此外，支持向量机和传统的神经网络相比有很大的优越性， 主要有： ( 1 ) 支持向量机是由统计学习理论的指导下导出的，体现了结构风险最 小化原则的设计思想，因此学习结果具有很好的推广性能，克服了神 经网络学习中的过学习现象。 ( 2 ) 支持向量机的设计较神经网络更灵活。首先，可以通过选择不同核 函数，不同的优化目标函数，不同的参数等得到不同等价的分类器： 再者，支持向量机的结构是通过优化目标函数得到的，因此克服了 神经网络设计中结构选择的困难。 ( 3 ) 支持向量机的训练是优化二次函数( 或者线性函数) ，有唯一的全局 最优解，因此克服了神经网络易陷入局部极小的缺点。 墨垄堕墨! 塑苎旦堡垒型篁塞竺一一 2 4支持向量机的学习算法2 6 1 埘于分类问题，用支持向量机方法进行求勰的学习算法过程为： 第步：给出一组输入样本一，i = 1 ，及其对应的期望输出y ， 十l ，- 1 ) # 第二步：在约束条件y 。口，= o 和口，0 ，i = 1 ，f 下求解 i ；1 w ( o o = q 一去q 0 。只乃( 葺x j ) 的最大值，得到口0 f _ l j j = i 第三步：计算w = “j y ，一，b = _ 1 一w _ ，其中x ，为一个特定的支持 j 一1，o 向量： 第四步：对于待分类向量x ，选择某一特定类型的核函数k ( x ，x ) ，计算 ， ，( x ) = s g n z y 。口? k ( t ，x ) + 6 。 为+ l 或1 ，决定x 属于哪一类。 = l 尽管支持向量机算法的性能在许多实际问题的应用中得到了验证，但是该 算法在计算上存在着一些问题，包括训练算法速度慢、算法复杂丽难以实现 以及检测阶段运算量大等等。 2 。5 支持向量机的训练算法 由于s v m 方法较好的理论基础和它在一些领域的应用中表现出来的优秀 的推广性能，近年来，许多关于s v m 方法的研究，包括算法本身的改进和算 法的实际应用，都陆续提了出来。尽管s v m 算法的性能在许多实际问题的应 用中得到了验证，但是该算法在计算上存在着一些问题，包括训练算法速度 慢、算法复杂而难以实现以及检测阶段运算量大等等。 传统的利用标准二次型优化技术解决对偶问题的方法可能是训练算法慢 的主要原因：首先，s v m 方法需要计算和存储核函数矩阵，当样本点数目较 大时，需要很大的内存，例如，当样本点数目超过4 0 0 0 时，存储核函数矩阵 需要多达1 2 8 兆内存；其次，s v m 在二次型寻优过程中要进行大量的矩阵运 算，多数情况下，寻优算法是占用算法时间的主要部分。 s v m 方法的训练运算速度是限制它的应用的主要方面，近年来人们针对 方法本身的特点提出了许多算法来解决对偶寻优问题。大多数算法的个共 同的思想就是循环迭代：将原问题分解成为若干子问题，按照某种迭代策略， 通过反复求解子问题，最终使结果收敛到原问题的最优解。根据子问题的划 分和迭代策略的不同，又可以大致分为以下几类： 第一类是所谓的“块算法”( c h u n k i n ga l g o r i t h m ) 。“块算法”基于的是这 样一个事实，即去掉l a g r a n g e 乘子等于零的训练样本不会影响原问题的解。 对于给定的训练样本集，如果其中的支持向量是已知的，寻优算法就可以排 除非支持向量，只需对支持向量计算权值( 即l a g r a n g e 乘子) 即可。实际上 复杂背景下的头肩像检测0 定位 支持向量是未知的，因此“块算法”的目标就是通过某种迭代方式逐步排除 非支持向量。具体的作法是，选择一部分样本构成工作样本集进行训练，剔 除其中的非支持向量，并用训练结果对剩余样本进行检验，将不符合训练结 果( 一般是指违反k k t 条件) 的样本( 或其中的一部分) 与本次结果的支持 向量合并成为一个新的工作样本集，然后重新训练。如此重复下去直到获得 最优结果。该算法的主要步骤如下： 第一步：取训练样本集合的任意一个子集作为工作集嚣； 第二步：用二次规划方法对嚣求解最优化问题，得到支持向量并构成一个 分类器； 第三步：用该分类器测试集合中的样本，将其中不满足最优化条件( k k t 条件) 者按其偏离最优的程度顺序排列为候补工作集c ；若c 中 所有样本都满足最优化条件或c 为空集，则结束程序，否则继续； 第四步：除掉四中的非支持向量样本，添加c 中排列在前面的若干个样本 构成新的工作集曰，返回第二步。 这种方法的特点是当支持向量的数目远远小于训练样本数目时，“块算法” 能够大大提高运算速度。然而，如果支持向量的数目本身就比较多，随着算 法迭代次数的增多，工作样本集也会越来越大，算法依旧会变得十分复杂。 第二类方法是子问题规模固定的分解算法，即把问题分解成为固定样本数 的子问题：工作样本集的大小固定在算法速度可以容忍的限度内，迭代过程 中只是将剩余样本中部分“情况最糟的样本”与工作样本集中的样本进行等 量交换，即使支持向量的个数超过工作样本集的大小，也不改变工作样本集 的规模，而只对支持向量中的一部分进行优化。 该方法最早是由o s u n ac ta 1 ”“提出，其关键就在于确定一种最优的工作样 本集选择方法。算法的主要思想是将训练样本分为工作集四和非工作集，嚣 中的样本个数为q 个，q 远小于总样本个数。每次针对工作集b 中的口个样本 训练，而固定中的训练