（计算机软件与理论专业论文）视频对象分割算法研究.pdf

摘要 基于内容的视频对象分割是数字视频技术乃至计算机视觉领域的一个研究 热点。从视频序列中分割出视频对象对于第二代编码标准而言是一个非常重要的 步骤，是基于内容的视频应用的基础，这些应用包括基于内容的视频检索、面向 对象的视频压缩和编辑、智能人机交换等方面。尽管人们对基于对象的视频编码 做了大量的研究工作，但到目前为止，还没有一种通用的方法能够有效地将物体 模型从景物中分割出来。 本文通过对现有的视频序列中运动对象分割算法的研究，针对现有的一些方 法抗噪声差，分割结果精度低，阴影问题，提出了两种视频对象分割方法。 ( 1 ) 提出一种新的基于s v m 的视频对象分割。 首先，它从本质上把视频分割中的图像分为背景和目标两类，从而转化为分 类问题。把视频对象分割跟踪闷题看作二值分类问题，以目标的特征属性为分类 的依据，对每一个像素使用分类的方法确定是目标或背景。采用多帧序列图像灰 度差异的4 次高阶统计量假设检验提取训练样本的掩模，接着利用空域分割算法 进行分割，时空联合，得到运动对象，艮p i ) t l 练样本。从而提取特征，进行训练， 得到s v m 分类器，进而把s v m 用于前背景的分割，得到视频帧的前背景景分 割掩模。 然后，空域分割中使用分水岭算法，得到帧图像的空域分割结果。 最后，将前背景分割掩模与空域分割结果结合，可以消除运动区域中多余的 部分。得到准确的运动对象掩模图像，进行填充即可得到分割出的运动对象。 实验表明其有一定的抗噪性，且提高分割结果的精度。 ( 2 ) 提出一种新的基于背景重构的视频对象分割。 首先，在时域分割中获取单帧图像的运动区域，摒弃了直接用帧差或者二次 帧差图做变化模板的做法。利用二次帧差求交集得到单帧的运动信息，阈值化得 到帧差掩模图像； 然后通过一定的算法初始化背景帧，此算法利用计数器累积判决像素点是否 属于背景，使得构造的背景帧更加可靠；最后用当前帧和重构的背景图像相减提 取目标对象，并提出一种消除阴影方法，得到较为准确的视频对象。实验证明其 有效的解决阴影问题。 关键字：s v m ，视频对象分割，背景重建 a b s t r a c t c o n t e n t - b a s e dv i d e oo b j e c ts e g m e n t a t i o nh a sb c c 沁m eah o tt o p i ci nt h ed i g i t a l t e c h n o l o g y , a l s ot h ec o m p u t e rv i s i o n t h es e g m e n t a t i o no fm o v i n go b j e c t si nv i d e o s e q u e n c e si sv e r yi m p o r t a n tf o rs e c o n dg e n e r a t i o nc o d i n ga n di sab a s i cp r e r e q u i s i t e f o rc o n t e n t - b a s e dv i d e oa p p l i c a t i o n s ，w h i c hc o n t a i nv i d e os e a r c h e s , c o m p r e s s i o na n d o b j e c t - o r i e n t e de d i t i o n , a p t i t u d eh u m a n m a c h i n ee x c h a n g e ，e t c t h er e s u l t so fo b j e c t s s e g m e n t a t i o nw i l la f f e c ts u b s e q u e n ta p p l i c a t i o n sd i r e c t l y a tt h ep r e s e n tt i m e , t h e mi s n oc u r r e n tm e t h o d ，w h i c hc a ns e g m e n to b j e c tm o d e l sf l o r at h eb a c k g r o u n de f f i c i e n t l y , t h o u g hag r e a td e a lo f r e s e a r c hw o r kh a sb e e nd o n ef o rv i d e oc o d i n g b a s e d0 1 1r e s e a r c ho i lm e t h o d sf o rt h es e g m e n t a t i o no fm o v i n go b j e c t si nv i d e o s e q u e n c e s ，t w on e wm e t h o d sa r ep r o p o s e dt oa c h i e v ea u t o m a t i cs e g m e n t a t i o nf r o m v i d e os e q u e n c e sf o rt h ep r o b l e mo fl o wa n t i n o i s e ，p o o ra c c u r a c ya n ds h a d o w e l i m i n a t i o n ( 1 ) v i d e oo b j e c ts e g m e n t a t i o nb a s e do ns v m f i r s t , t h ev i d e oi sd i v i d e di n t ob a c k g r o u n dp a r ta n dt a r g e tp a r ti ne s s e n c e , a n dt h e s e g m e n t a t i o np r o b l e m i sr e g a r d e da sc l a s s i f i c a t i o n e a c hp i x e li sd e t e r m i n e df o rt a r g e t o rb a c k g r o u n d ，s oi th a sn oi n f l u e n c eb yt e n s i l e , t r a n s l a t i o na n dt h er o t a r yo ft h el e n s t h em a s ko ft h et r a i n i n gs a m p l eo ft h es v mi se x t r a c t e db yf o u r t h - o r d e rs t a t i s t i c s d e t e c t i o nm e t h o db a s e do nt h e 莎a yd i f f e r e n c e sb e t w e e nm u l t i p l yf r a m e s t h e n s e g m e n tt h e f r a m eu s i n gt h ea i r s p a c es e g m e n t a t i o na l g o r i t h m ，a n dt i m e - s p a c e c o m b i n a t i o nt og e tt h et r a i n i n gs a m p l e ，a n dt h e ne x t r a c t i n gt h ef e a t u r e , t r a i n i n g , g e t t h es v m ，u s i n gt h es v mt os e g m e n t a t i o no ft h ef o r ea n db a c k g r o u n d ，g e t t i n gt h e m a s ko ft h eo b j e c t t h e nt h es p a c es e g m e n t a t i o ni sg o tb yw a t e r s h e da l g o r i t h m a tl a s t , c o m b i n e dt h es v mm a s ka n dt h es p a c er e s u l t ，a n dt h eo b j e c ti sg o t e x p e r i m e n ts h o wt h i sm e t h o dh a sa n t i - n o i s et os o m ee x t e n t , a n di m p r o v e st h e a c c u r a c y ( 2 ) v i d e oo b j e c ts e g m e n t a t i o nb a s e do nb a c k g r o u n dc o n s t r u c t i o n f i r s t , m o v i n gr e g i o n sa r ea c h i e v e dt h r o u g ht e m p o r a ls e g m e n t a t i o n , g e t t i n gr i do f m a k i n gf r a m ed i f f e r e n c eo rt w i c ef r a m ed i f f e r e n c ei m a g ea sm o d e l s f r a m em a s k i m a g ec a nb ea c h i e v e dw i t hat h r e s h o l df r o mm o v i n gi n f o r m a t i o ng o tb yi n t e r s e c t i o n s o ft w i c ef r a m ed i f f e r e n c ei m a g e s t h e nb a c k g r o u n df r a m ei si n i t i a l i z e db yac e r t a i na l g o r i t h m ，i nw h i c h ，ac o u n t e ri s u s e df o ra c c u m u l a t i o n ，a n dm a k e st h ec o n s t r u c t e db a c k g r o u n dm o r er e l i a b l e a tl a s t ， t h em o v i n go b j e c ti s s e g m e n t e db yc u r r e n tf r a m ed i f f e r e n c ef r o mp r 。d i c t e d b a c k g r o u n d a n dan e wm e t h o di sp r o p o s e dt os o l v et h es h a d o we l i m i n a t i o n e x p e r i m e n ts h o wi tc a ns o l v et h es h a d o we l i m i n a t i o ne f f e c t i v e l y k e yw o r d s ：s v m ，v i d e o0 b j e c ts e g m e n t a t i o n ，b a c k g r o u n dc o n s t r u c t i o n 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。 本人在论文写作中参考的其他个人或集体的研究成果，均在文中以明 确方式标明。本人依法享有和承担由此论文产生的权利和责任。 声明人( 签名) ：懈 2 伪g 年岁月三8 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电 子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学 校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索， 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适 用本规定。 本学位论文属于 1 保密( ) ，在年解密后适用本授权书。 2 不保密( ) ( 请在以上相应括号内打“) 作者签名：o 辛跟日期：歹以年占月) 莎日 导师签名：水尹够日期枷矿年岁月谚日 第一章绪论 1 1 研究背景与目的 第一章绪论 在当今信息社会，以多媒体为代表的信息技术和信息产业的发展和应用对人 类社会产生的影响和作用越来越显著。在此背景下，多媒体信息已成为人类获取 信息的最主要载体，同时也成为电子信息领域技术开发和研究的热点。多媒体信 息经数字化处理后具有易于加密、抗干扰能力强、可再生中继等优点，但同时也 伴随海量数据的产生，这对信息存储设备及通信网络均提出了很高要求，从而成 为阻碍人们有效获取和使用信息的重大瓶颈。 为了解决多媒体信息在存储和传输过程的瓶颈一庞大的信息量和计算机系 统的处理能力之间的矛盾，单纯用扩大存储器容量、增加传输率是不现实的，因 此研究高效的多媒体数据压缩编码方法，以压缩形式存储和传输数字化的多媒体 信息具有重要意义。作为多媒体技术的核心及关键，多媒体数据压缩编码近年来 在技术及应用方面都取得了长足进展，它的进步和完善正深刻影响着现代社会的 方方面面。 数字视频的压缩技术受到了前所未有的关注。所以，数字视频的编码压缩技 术成为了多媒体领域的一项重要的技术，它为人们观赏、存储、交换和操纵视频 信息，提供了有利的支持。新一代支持甚低码率传输的压缩标准m p e g - 4 ，提出 了基于内容编码的重要思想。正是多媒体领域产生的这种基于内容的可视信息表 达方法的强烈需求，使视频对象分割技术成为一个研究热点。 视频对象分割，是指按照一定的标准将视频序列分割为具有一定意义的语义 实体的组合。我们把该语义实体叫做视频对象( v i d e oo b j e c t ，v o ) 。 尽管m p e g - 4 描述了v o p 的概念和用途，但是并没有对v o p 的具体生成算 法做出标准化的规定，而只是提供了v o 的表示模型。这并不是意味着它不重要， 相反，对于m p e g - - 4 来说，视频对象分割是一个非常重要的步骤。可以说，视频 对象获取是支持基于内容功能中不可缺少的一部分。 我们在研究的“8 6 3 ”项目“引入觉知机制的视觉动态计算模型及其应用实 现一，此项目主要研究内容包括觉知计算模块的构建与实现、有意识视觉感知计 l 视频对象分割算法研究 算模型的建立和动态场景中人物自动监视应用。它依据人类视觉认知机理研究的 新成果，参考意识模型的有关成果，引入觉知机制，采用可资利用的各种神经计 算模型，来形成一种有意识的视觉感知动态计算模型，并具体应用于动态场景中 人物的自动监视。其中视频对象分割，能为人物自动监视做一些准备。 1 2 视频对象的定义 在m p e g 4 标准中，视频对象被定义为“在景物中的一个单元，允许用户存 取( 搜索，浏览) 和操作( 剪切，粘贴) 一，即视频对象是区域的聚集，且至少有一个 共同的特征一致地出现在视频对象中。这个概念较为抽象，在实际的视频场景中， 视频对象是指某些具有语义意义的区域。由于视频所反映的客观世界十分复杂， 对象本身也是多种多样的，缺乏一种十分贴切的定义描述。现实世界中的任何一 个有语义意义的实体，如行驶的汽车，人等，都可以被视为语义视频对象。而且， 对同一视频场景，不同的应用所感兴趣的视频对象是不同的。人眼可以很容易地 识别出语义视频对象，但对计算机来说，适合于通用视频序列的全自动视频分割 和提取目前还是一个难题，视频对象的语义很难用图像分割中常用的低级特征如 灰度、颜色、运动来进行明确的定义和描述，而是依赖于具体的应用。语义对象 提取过程，本质上是一个分割问题，而分割本身就是计算机视觉和图像处理领域 的一个经典问题。视频对象分割算法的研究是随着m p e g 4 和m p e g 7 标准的制 定而出现的新的研究热点。 1 3 视频对象分割的研究现状与分类 早在上世纪八十年代末九十年代初，视频分割就引起了许多学者的兴趣。近 年来，视频对象分割算法已经成为多媒体领域的热点研究课题。最初在m p e g - 4 标准的制订过程中，m p e g 专家组也提出并测试了一些算法，这些算法大多利用 多帧差分模板的累积来作为当前帧的差分模板，测试结果不够理想，仅适用于在 有限的范围内反复运动的缓动目标，对于快速以及大范围运动的对象难以获得理 想的结果。此外，国内外一些研究机构和高等院校积极探索鲁棒的、快速的视频 分割算法，这些方法从不同的角度或不同的目的对视频对象分割问题进行了研 究，可以按照如下几种方式把它们分为不同的类别： 2 第一章绪论 按照用途的不同，视频对象分割算法可以分为两类：一类是用于视频压缩编 码，将分割出来的视频对象单独进行压缩编码，并通过按视频对象对人眼视觉的 重要性对不同的视频对象分配不同的码率，达到有效提高视频压缩比改善视觉效 果的目的。这种应用一般要求实时、自动地实现对视频对象的提取，并对于分割 出的视频对象轮廓要求并不十分严格。另一类是用于基于内容的交互式多媒体应 用，这类应用一般不要求实时、自动实现视频分割，但要求得到准确的视频对象 轮廓。这种应用可用于基于m p e g 4 的虚拟场景，即将视频对象分割出来后，可 以在场景中使用，并按对象进行操纵。 按是否需要人工参与分割过程，视频对象分割算法也可以分为两类方式：即 自动方式【l 】和半自动方式【2 埘。自动视频分割算法在分割过程中无需人工的参与， 可以自动地从视频序列中分割出运动目标并进行跟踪。然而，在自动视频分割中， 由于语义一致性往往采取一些低级特征的组合，作为先验知识隐含在算法中，当 自动视频分割算法应用于不同的图像序列时，如果序列中视频对象的语义一致性 与先验知识不符，就不可能得到满意的结果。因此，大多数自动视频分割算法只 适合于特定的应用场合，而且绝大多数的自动分割算法采用运动信息作为主要的 特征。一般来说，基于运动的分割往往计算量大，对噪声很敏感。自动分割算法 的主要特点是面向特定应用，预先调整好参数，可完成实时处理任务，如车辆检 测系统、大厅监测系统、可视电话和电视会议等。半自动的分割算法需要借助人 工的参与来定义语义，如协助定义视频对象的轮廓、位置，所选择的跟踪对象是 刚性还是柔性等，然后跟踪后续帧中的初始区域，区域的边界按预先定义的语义 特征被修正，以克服由于跟踪带来的误差。因此，半自动分割往往可以获得更好 的分割质量。半自动分割方式则适用于复杂场景下对象的分割，虽然分割质量较 好，但不具有实时性。它的主要特点是依赖于人工的交互确定语义级对象并干预 分割和跟踪结果，可用于任意对象的分割、操作和高效压缩。 从模型化角度，视频对象分割可以分为模型化的分割方法和非模型化的方 法。模型化的分割方法是指算法中建立了与图像空域信息或者时域信息相对应的 数学模型，这种方法在国外的相关文献中运用较多。比如，文献 9 1 建立了贝叶斯 基的时域跟踪模型，文献【1 0 】中的3 d 分水岭模型，文献m 1 2 1 中的支持向量机模 型，文献 1 3 - 1 4 】中的g i b b s 随机场模型，文献【1 5 】中针对人体分割提出的模糊神经网 3 视频对象分割算法研究 络模型，文献f 1 6 】中使用马尔可夫随机场模型，文献【1 7 】中的高斯混合模型等等。 这些数学模型的建立，为视频分割算法的理论化提供了良好的参考基础和启示， 对视频分割算法的标准化和通用化具有一定的理论价值和实际意义。例如，马尔 可夫随机场模型就己经被许多学者广泛应用于图像、语音及多媒体领域，因此， 在视频分割中引入有效的相关数学模型是十分有益和值得探索的。 按照分割算法利用空间和时间信息的不同，视频对象分割算法可以分为空域 分割算法、时域分割算法以及联合时空的分割算法。 其中空域分割算法包括形态学分水岭变换【1 8 j9 】、最短扫描树形算法、聚类 【2 1 1 以及区域增长算法【2 2 】等，这些空域的分割往往将每帧图像分割成不同的纹理 一致区域，一般用来定位待分割视频对象的初始位置和轮廓，使得前景对象与背 景之间具有明显的准确的边界。但是，这样单纯的空域分割在很多情况下，很难 引入人们感兴趣的对象定义信息，从而无法确认人们需要的对象区域。 而时域分割方法一般是通过对帧问变化检测或者是对背景的变化检测来获 得视频对象的位置和区域，比如帧差【2 3 - 州、高阶统计1 3 1 - 3 3 】、背景差【弘3 引、以及 结合帧差和背景差的方法等。但是，单纯利用时域分割，由于遮挡问题和孔径问 题以及图像中噪声的干扰，分割的结果可能不够完整、不够准确，尤其是对待分 割对象的边界定位不精确。 为克服两种方法各自的不足，大多数的相关学者都采用了时空联合的分割方 法【3 9 5 ，即同时利用当前帧的纹理一致区域分割结果和相邻帧之间的变化检测结 果。其中，最为典型的方法就是首先根据时域分割方法粗略地确定前景对象的大 概区域，然后在对应的空域分割结果中精确地定位对象的边缘。时空联合分割方 法包括三个基本部分：时间域分割( 时域分割) 、空间域分割( 空域分割) 以及 时空联合分割。 人眼的视觉特性对分割的对象质量要求非常高，符合视觉特性的视频对象的 定义和表达没有一个固定的、通用的标准，计算机无法自动地、正确地理解和判 断视频对象。在实际的图像和视频序列中，物体没有一个固定的形状、灰度和运 动等信息，而且这些信息也只能看作基本的特征，还不能直接作为视频对象的高 层语义定义，对这些信息的有效融合以及进一步抽象表达是有待于进一步提高 的。 4 第一章绪论 1 4 主要的研究工作与创新点 1 4 1 主要研究工作 本文以视频对象分割技术为研究课题，深入地进行国内外视频对象分割算法 的研究，对相关分割技术进行了分类。根据不同的应用背景，对视频分割从不同 的角度进行了研究，主要做了以下工作： ( 1 ) 对当前视频对象分割算法进行了较为系统的归纳。 ( 2 ) 分析现有一般视频对象分割算法的优劣性，提出了一种新的基于s v m 与 分水岭的视频对象分割。把视频对象分割跟踪问题看作二值分类问题，以目标的 特征属性为分类的依据，对每一个像素使用分类的方法确定是目标或背景。 ( 3 ) 分析现有视频对象分割算法中遮挡与阴影问题，提出了一种新的基于背 景重构的视频对象分割。 1 4 2 本文的创新点 本文的创新点归纳如下： ( 1 煨出了一种新的基于s v m 与分水岭的视频对象分割。从本质上把视频分 割中的图像分为背景和目标两类，从而转化为分类问题。训练的样本采用多帧序 列图像灰度差异的4 次高阶统计量假设检验，从而提高了算法的抗噪性。利用分 水岭算法分割结果进行联合，去除毛糙表面。 ( 2 ) 提出了一种新的基于背景重构的视频对象分割。在时域分割中获取单帧 图像的运动区域，摒弃了直接用帧差或者二次帧差图做变化模板的做法。利用二 次帧差求交集得到单帧的运动信息，阈值化得到帧差掩模图像，从而提高了背景 重构的精度。其中阈值化过程所需要的阈值可以通过l h s ( 最小1 2 抽样法，l e a s t h a l fs a m p l e s ) 方法得到，该方法可以及时地产生自适应阈值。最后提出了一个消 除阴影的方法，从而较好的解决阴影问题。 5 视频对象分割算法研究 第二章研究的关键技术 2 1 支持向量机基本原理 2 1 1 机器学习 机器学习问题就是通过某种训练手段，根据给定的训练样本集将系统的输入 和输出之间的依赖关系估计出来，并且希望这一估计可以对任意给定的输入进行 尽量精确的输出预测【5 2 l 。该问题可以形式化描述如下： ( 1 ) 从固定但未知的概率分布函数砖) 中独立抽取随机向量工r 4 ( 2 ) 根据固定但未知的条件分布函数p ( yl x ) ，对随机向量给出一个输出值 j ，r 。 ( 3 ) 重复步骤l 、步骤2 共1 次，可以得到一组样本“，y 。 k ，y ： ，k ，儿) ， 对应的概率分布函数为p b 。，j ，jp g ：，y ： ，p “，y ，) ，这组样本被称为从某一 未知概率空间抽取的训练样本集合。因为这些样本都是随机抽取的，它们之间无 任何关系，并且这些样本的发生所对应的概率分布函数均为p ( x ，y ) ，所以这些 样本是相互独立的、一致分布的。 ( 4 ) 选择一个函数集s = 扩b ) 。 ( 5 ) 机器学习问题就是：确定一个函数f ( x ) e s ，作为y 的预测值，使得在 某一准则下f ( x ) 是y 最佳的预测值。 综上所述，机器学习用数学的语言可描述为： 机器学习根据给定的1 个独立同分布观测样本 g ，y 。l g ：，y ：l ，“，y ，) ( 2 1 ) 其中x l r ，y l e 凡i l ，2 ，l 选择适当的函数集s ；并选定损失函数c ，在 s 中寻找一个函数坟x ) 使 尺杪) = 佟g ，y ，g 舳屯以 ( 2 2 ) 达到最小。其中，p ( x ，y ) 是未知具体形式的概率分布函数；f ( x ) 称为决策函数， 6 第二章研究的关键技术 或假设：“x ，弘f 【x ) ) 为用f ( x ) s 对y 进行预测而造成的损失函数。r ( f ) 称为期 望风险。在求得一个决策函数f ( x ) 后，对一个新的输入x ，根据f ( x ) 推出x 相应 的输出y ，这称为推广。 2 1 2 统计学习理论 ( 1 ) 经验风险最小化原则 机器学习的目标在于使( 2 2 ) 式的期望风险r ( f ) 最小化。但由于我们可以利 用的信息只有训练样本数据，并不知道概率分布函数p ( x ，y ) 的具体形式，只是 知道存在着这样一个概率分布，使得训练样本是按照这个分和独立产生，因此要 构造一个仅仅根据训练样本就能找到使期望风险最小的假设f 的学习算法显然是 不可能的。但因为知道训练集，所以可以计算出f 在这些样本上的偏差，这导致 出下面的经验风险的概念。传统的机器学习方法都是根据训练集上的经验风险来 选择f 经验风险设给定的训练集r = 眠，咒l f = 1 , 2 ， ，其中而r ”， y ， + 1 ，一1 ) 江l ，2 ，并且给定损失函数c ，假设f 对应它们的经验风险是 尺唧u ) = 去善如，y ，厂“) ) ( 2 - 3 ) 经验风险最小化原则设任意给定训练集t ，并适当选取假设集 s = 扩：x e r 4 - - y + 1 ，一1 ) ，经验风险最小化原则就是在假设集中，寻找使经 验风险尺伽驴) 最小化的假设厂。 基于经验风险最小化原则的学习过程的缺点也是明显的：( 1 ) 它是一个经验 的方法，即，运用经验风险杪) 代替期望风险尺扩) 来选择厂并没有经过严格 的证明与充分的论证，只是一种想当然认为合理的方法；( 2 ) 基于经验风险最小 化原则下的学习方法容易发生“过学习 问题。这是盲目追求小误差而导致推广 能力下降的必然结果。例如，在神经网络学习中，神经网络对于有限样本可以显 现强大的学习能力，因为它记住了每个样本提供的信息，往往使得训练误差为0 ， 即经验风险为0 。但是，这并不能保证对未来的样本的预测产生好的结果。再例 如，对于给定的训练集r ，令假设 视频对象分割算法研究 r y g ) = ，a 【 i ， 工2 一，f = l ，2 ，( 2 - 4 ) z 毛 显然，这个假设也在s = 扩 x e r _ ye + l ，一l 中，并且满足 杪) = 0 ( 2 5 ) 但是把这个假设f 作为决策函数显然是不妥的。由此可以看出，如果使用经 验风险最小化归纳原则来选择f 应适当缩小假设集s ，至少它不应该包含类似 ( 2 4 ) 式的假设。总之要对假设集s 加以限制。 ( 2 ) v c ( v a p n i k c h e r o n e n k i s ) 维 从上一节可知，要寻找f ，需要选择适当的假设集s 。实际上，选取假设集 s 的关键因素是s 的大小，或丰富程度，或表达能力。v c 维是对这种表达能力 的一种描述。 v c 维的直观定义是：对一个假设集s ，如果存在h 个样本能够被s 中的假 设按所有可能的2 h 种形式分开，则称假设集s 能把h 个样本打散，或称h 个样 本被打散。则假设集s 的v c 维就是它能打散的最大样本数h 。例如，取r 2 ( 2 维实平面) 上的3 个点，3 个点分别由( r ) 、( b ) 、i i ( p ) 这3 个图形符 号来表示( 也可以用图形符号旁边的英文符号表示它们) 且这3 点不共线。设函数 集合s 为r 2 上的线性指示函数的集合，即s 为 s = 扩k w ) = s g n ( w o + w l b l + w 2 b 】2 ) ( 2 6 ) 易知，若对这3 个点分别标上“+ 标号和“标号，共有2 3 ( = 8 ) 种标号方 式：( r p ，b ) 、( r b ，p ) 、f p b ，r ) 、( r p b ，) 、( b ，r p ) 、( p ，r b ) 、( r ，p b ) 、( ， r p b ) ；其中，二元组的第1 项指示的是标“+ 标号( “+ l 类) ，二元组的第2 项指示的是标“一标号( “1 ”类) 。对每一种标号方式，都存在一个假设f s ， 使得“+ 1 类和“1 类能被f = o 分开。如图2 1 所示，图中“一 所在的部分 为“+ 1 类。另外，这样的函数集合无法划分2 维平面中任意4 个点。所以，式 ( 9 ) 所示的函数集合s 的v c 维就等于3 。 8 第二章研究的关键技术 穴士 寸7 x 图2 1v c 维的例子 若对任意数目的样本都有假设能将它们打散，则假设集s 的v c 维就是无穷 大。例如，函数集合 s = 扩k 曲= s i l l ( 谳w r ) ， ( 2 7 ) 的v c 维就是无穷大。 ( 3 ) 结构风险最小化原则 根据v c 维理论，得到以下结论： 设h 为假设集s 的v c 维，l 是训练集所含的样本个数，当 ， h ， ( 2 8 ) ( - n i 2 1 + ) + - n 吾1 弘9 ， 成立时，则对任意的概率分布p ( x ，y ) 和任意的6e ( o ，1 】，假设集s 中的任 意假设f 都可使得下列不等式至少以1 6 的概率成立 r 驴) 驴) + 特别地，当时驴) = o ，有 r 驴) ( 2 - 1 0 ) ( 2 一1 1 ) 式( 3 - 1 3 ) 给出了期望风险r 驴) 的一个定量估计，它的右端的第二项 9 视频对象分割算法研究 称为置信区间，而右端的两项之和称为结构风险，它是期 望风险尺杪) 的一个上界。从式( 2 1 0 ) 可以看出，这个上界是经验风险和置信区间 之和，而经验风险依赖于的选择，置信区间是v c 维 的增函数。粗略地说， 当集合s 比较大时，可以选到适当的厂，使得杪) 比较小，而此时由于s 的 v c 维h 比较大，导致置信区间也比较大。反之，当缩小集合s 时，s 的v c 维 降低，置信区间变小，而此时的驴) 可能比较大。所以经验风险和置信区间 之间有相互矛盾的倾向。为了选出兼顾二者的假设，引进结构风险最小化原则。 结构风险最小化原则结构风险最小化原则是在s 中寻找假设厂，使得式( 2 1 0 ) 右端所示的结构风险最小。 结构风险最小化归纳原理的基本思想是：不仅要使经验风险最小，还要使 v c 维尽量小，对未来样本才会有较好的推广能力。即，如果要求风险最小，就 需要不等式( 2 1 0 ) 右边中的两项相互平衡，共同趋于极小；另外，在获得的学习 模型经验风险最小的同时，希望学习模型的推广能力尽可能大，这样就需要h 值尽可能小，即置信风险尽可能小。根据式( 2 - 1 0 ) ，如果固定训练样本数目的大 小，则控制结构风险的参数有两个：扩) 和j i i 。其中， ( a ) 经验风险驴) 依赖于学习机器所选定的函数厂，这样一来，我们可以 通过控制，来控制经验风险。 ( b ) v c 维h 依赖于学习机器所工作的函数集合s 。为了获得对h 的控制，可 以将函数集合s 结构化，建立j i i 与各函数子结构之间的关系，通过控制对函数结 构的选择来达到控制v c 维的目的。例如，选择一系列假设集 墨c 是c c cs 。c ，( 2 1 2 ) 在每个中找出使经验风险最小的假设z ，f = 1 , 2 ，刀。考查与相应的结构 风险随i 的变化情况，可以发现： ( a ) 经验风险随i 的增加而减小 8 呷“) 8 。驴) 8 翻矽) ( 2 1 3 ) 1 0 第二章研究的关键技术 ( b ) 置信区间随f 的增加而增大因为 j i i i 屯5 h i ， ( 2 1 4 ) 其中j j l ，为乃的v c 维，f = l ，2 ，一， 因为s i 是嵌套的，结构风险最小化原则就是对于给定的一组样本 g 。，y a g ：，y ：l ，k ，y ，) ，在函数子集中选择一个函数来最小化经验风险，同时， 确保置信风险是最小的。 2 1 3 标准支持向量分类机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 是统计学习理论中最新的 内容，也是最实用的部分。正因为支持向量机的提出，才促进了统计学习理论的 发展。支持向量机是一种通用的学习机器，传统的学习方法主要是最小化经验风 险来归纳学习的，而支持向量机依据统计学习理论中的结构j x l 险最小化原理构造 而成的一个通用的学习机器。它在学习方面表现出了良好的性能。 支持向量机最初研究是针对模式识别中的线性可分的两类分类问题。分类问 题就是根据给定的训练样本集7 = 融，y ，l f = l ，2 ，) ，r 。，y ，e “1 ，一l ， 寻找决策函数 g ) = s 印( g g ) )( 2 1 5 ) 推断对任一样本x 的y = 厂b ) 的值。在机器学习中，把求解分类问题( 即寻找 决策函数) 的方法称为分类学习机。当g ( x ) 为线性函数时，由式( 2 - 1 5 ) 确定分类准 则时，被称为线性分类学习机；当为非线性函数时，被称g ( x ) 为非线性分类学习 机。分类问题有三类问题：线性可分问题、近似线性可分问题、线性不可分问题。 下面就介绍解决这三类分类问题的支持向量分类学习机。 ( 1 ) 线性可分问题 如图2 2 所示的问题，很容易找到一条直线把训练集正确地分开( a p 两类点分 别在直线的两侧，没有错分的点) ，这类问题为线性可分问题。如图2 2 中的分割 线1 和分割线2 都能正确地将两类样本分开，即都能保证使经验风险最小化( 为 视频对象分割算法研究 零) ，但支持向量分类机要求分割线不仅能将两类样本正确分开，还要使分类间 隔( m a r g i n ) 最大( 如图2 2 中的分割线1 ) ，这样的分割线被称为最优分类线( 高维即 为最优分类面) 。使分类间隔最大实际上就是使结构风险最小化，这也就是支持 向量分类机具有较强的推广能力的原因。 oo 图2 2 最优分类线 f 面导出线性司分的支持向量分类机的优化问题。 设线性可分的训练样本集r = 融，y ，l f = l ，2 ”，x 毛r 4 ，乃 + l ，一i ) ， 则必然存在一个分离超平面为： ( w j ) + 6 = 0( 2 1 6 ) 将其中的两类样本点分开。其中( w 工) 是w 与x 的内积。等比例调节w 和b 将分类超平面方程归一化，使两类所有样本都满足 y l “w _ ) + 6 ) 1 , i = 1 , 2 ， ( 2 1 7 ) 这样分类f a j 隔( m 删n ，等于丽2 ，使间隔最大等价于使警最机训练样本正 确可分，且使掣最小的分类面就是最优分类面。使分类间隔最大实际上就是对 推广能力的控制，这是支持向量机的核心思想之一。根据统计学习理论，一个规 范超平面构成的指示函数集 f ( x ) - s g n ( w 工) + 6 】 ( 2 1 8 ) 的v c 维h 满足： 第二章研究的关键技术 h 0 ，来综合这两个基本目标，就得到 i f f i i 下面的优化问题： m 咄i n f 扣2 + c 善i 缶， s j y i 【( w x , ) + b l - - i 一点，i = 1 ，2 ， 磊o , i = 1 , 2 ，z ， ( 2 3 1 ) ( 2 3 2 ) ( 2 3 3 ) 其中c 为可调参数，c 越大表示对错误分类的惩罚越大。这是一个二次规划 问题，其最优解为下面拉格朗日函数的鞍点： 三( w ，6 ，口) ：妻l 卅2 + c 圭当一圭a i 【y ，w x i + 6 ) + 当- 1 一圭屈磊( 2 - 3 4 ) i f f i li f f i li = 1 其中，q 0 ，层0 为拉格朗日乘子，由于在鞍点处的w 、6 和f 的梯度为 零，因此可得 詈= w 一善i 口，乃毛= 。jw = 喜y ， c 2 - 3 5 ， 篆= 静胪。磐胪。， 詈= c - g , - , o , = o ， ( 2 3 6 ) ( 2 3 7 ) 将式( 2 - 3 5 卜( 2 3 7 ) 代入式( 2 3 4 ) ，并对它关于口求最大，徽t j ( 2 3 1 ) ( 2 3 3 ) 的 对偶最优化问题： 呼参一丢妻喜a i t z j y l y i k _ ) 亿3 8 ， ， 豇y 。= 0 ( 2 3 9 ) k l 1 5 视频对象分割算法研究 0 鲰j c , i = 1 , 2 ，* o - 9 1 ( 2 4 0 ) 求解问题( 2 3 8 ) 一( 2 删得到的中，嘶可能是：嘶= o ；0 qsc ； = c ；后两者所对应的而为支持向量。在支持向量中，= c 所对应的毛位 于边界上，称为边界支持向量( b o 岫d a 拶s u p p o r tv e c t o r ，b s v ) ；0 c 所对 应的而位于间隔内，称为标准支持向量( n o r m a ls u p p o r tv e c t o r ，n s v ) 。根据k k t 条件知，在最优点，拉格朗同乘子与约束条件的积为0 ，即 口，陟，“w ) + 6 ) 一l + 茧】= o ，f = 1 , 2 ，( 2 - 4 1 ) 届鼻= o ，i = 1 , 2 ，z ( 2 - 4 2 ) 对于标准支持向量( o 口，c ) ，由式( 2 3 7 ) 可知屈 0 ，则由式( 2 - - 4 2 ) 得到 毛= 0 ，因此，对于任一标准支持向量，满足 y ，【( w 五) + 6 】= 1 ( 2 4 3 ) 所以b 为： b = y 广( w 毛) = y ，一口，y ，“j ，h 剧， ( 2 4 4 ) 其中为标准支持向量的集合，j 为支持向量的集合。为了计算可靠，可 以对所有标准支持向量分别求b 的值，然后求平均。 式( 2 - 3 2 ) - ( 2 3 3 ) 的约束条件约束了w , b 使得经验风险误差为0 ，同时最小化 8 叫| 使v c 维最小，因此，i h - j , 题( 2 3 1 ) - ( 2 - 3 3 ) 的最优化体现了结构风险最小化原则， 具有较好的推广能力。 ( 3 ) 线性不可分问题 对于图2 4 所示的问题，无论用任何一条直线去划分都会错分很多训练样本， 这类问题被称为线性不可分问题，这时就得使用非线性分类学习机来求解。 1 6 第二章研究的关键技术 i ji ：厂 、 。 、 | 1 j ，i 。l + 图2 4 线性不可分问题 对于线性不可分问题，支持向量机的思想是：通过引进一个非线性映射矽， 将低维的输入空间中的线性不可分问题，转化为高维的特征空间中的线性可分闯 题，在高维的特征空间中，就可以利用线性分类学习机。如图2 。4 所示的问题， 对于这类问题，显然不能用超平面去划分，而需要用“超曲面”来代替。寻找超 曲面的问题比较复杂，可以通过一个映射，将寻找超曲面的问题转化为寻找超平 面的问题。如图2 4 所示的问题，可以看出，比较合理的划分是，s ) 平面的一个 圆 ，2 + s 2 = 6 ， 、 ( 2 _ 4 5 ) 其中6 为常数，希望通过线性划分的方法来求出这个圆。考虑将( ，j ) 平面上 的点x = 取】l ，b 】2 y 映射到“，v ：) 平面上的点h = l ，k 】i ) r 的一个映射 “= 以) = o 】l ，b 】：) r ： 仿k l = b 1 2 k l = b 】2 它把，s ) 平面上的非线性划分转化到。，：) 面上的线性划分，如图2 5 所示 1 7 视频对象分割算法研究 图2 5 高维特征空间映射 通过上面的例子可以看出，对于线性不可分问题，引入一个非线性映射函数 缈将输入空间映射到一个高维特征空间， 缈：xcr ”专以) c 日( 2 - 4 7 ) 其中h 为特征空间。在特征空间构造线性划分，此时分类超平面为： w 伊g ) ) + 6 = 0 ， 其中w h ，b e r 为下面最优化问题的解 m 岫i n f 扣2 + 嘻当 s j y i 【( w 伊b ) + 6 ) 】l 一，i = 1 ，2 ，l 缶0