（计算机应用技术专业论文）流形降维方法在视频内容分析中的应用研究.pdf

复旦大学硕七学位论文 摘要 随着计算机、网络和数字化技术的发展和普及，网上多媒体数据量急剧增加， 计算机自动处理、分析、挖掘、检索网上海量多媒体数据( 特别是视频数据) 已 经成为信息社会的迫切需求，视频信息处理和内容分析的研究迎来了巨大的发展 机遇，也面临着许多挑战。 过去1 0 多年来，人们在镜头边界检测、场景分析，视频摘要等许多方面取 得很大研究进展，主要成绩有：研究了各种低级视觉特征( 例如颜色、边缘、纹 理等) 的提取方法和表示能力；采用了多种数学模型( 例如隐马尔科夫模型h m m 、 高斯混合模型g m m 等) 进行视频内容分析，以发现各种模型对视频信息的建模 和表达能力；探索了各种基于机器视觉、模式识别的方法，以发现更加有效的时 空特征，以及更适合视频特征提取与识别的方法。 在这些研究中，已经有很多方法能够进入实际应用，如镜头边界检测技术等。 但是，在所取得的大量研究进展之背后，我们还应清楚地看到一些难以解决的问 题，例如涉及高层语义的场景分析问题仍然没有切实可行的解决方案，因为语义 鸿沟的存在，基于语义的视频内容分析的研究尚无重大进展。 近年来提出的一些非线性降维方法，例如流形降维方法，在视频内容分析中 可能会发挥重要作用，因为它能更好地揭示隐藏在观察数据中的某些内在规律， 这是传统线性方法( 例如主分量分析p c a ) 无法做到的。 本文采用流形降维方法处理视频内容分析中两个实际问题：镜头边界分类和 场景分析。我们用一种流形降维方法即拉普拉斯特征映射束发现镜头边界附近图 像序列的时域变化模式，用图像序列在其低维流形空间的映射来表示镜头边界的 特征，以期反映镜头边界的本质特性；同时，我们针对镜头边界分类问题的样本 不平衡特性，设计了一种样本大小相关的k n n 分类器，以学习每一种类型的镜 头边界的模式。实验表明，流形空问表示的图像帧序列模式能很好地反映镜头内 容变化的本质特性。 对于视频场景分析，至今也没有取得良好进展，其主要原因是语义鸿沟问题。 本文提出了一种介于镜头和场景之间的结构特征，它能在一定程度上刻画类似场 景的结构信息，但又不涉及高层语义信息提取的难题。我们用拉普拉斯特征映射 来提取上述结构特征，把镜头映射到流形空间上，并进行编码，从而获得一维的 变化特征曲线。通过对具体案例的观察分析，我们发现该曲线既能反映镜头特征， 又隐含了一定程度的场景结构信息。 复日大学硕十学位论文 2 总之，本文探索了流形降维方法在镜头边境分类和场景分析方面的应用，实 验表明流形降维方法对于视频内容分析是一个有用的工具。 关键字：视频内容分析、流形降维、流形学习、镜头边界分类、场景分析 中图分类号：t p 3 7 复邑大学硕士学位论文 3 a b s t r a c t w i t l lt h ep o p u l a r i z a t i o no fd i g i t a lc a m e r aa n dt h er a p i dd e v e l o p m e n to fc o m p u t e r , n e t w o r ka n dd i g i t a lt e c h n i q u e s ，t h en e e dt h a tc o m p u t e rc a l la u t o m a t i c a l l yp r o c e s s ， a n a l y z e ，m i n ea n dr e t r i e v em u l t i m e d i ad a t a , e s p e c i a l l yv i d e oi n f o r m a t i o ne m e r g e s 1 1 1 er e s e a r c ho fv i d e op r o c e s s i n ga n dc o n t e n ta n a l y s i si s f a c i n gab i gc h a n c ea n d c h a l l e n g e i nt h ep a s td e c a d e s ，g r e a ts u c c e s sh a sb e e na c h i e v e di nt h ef i e l do f s h o tb o u n d a r y d e t e c t i o n ，s c e n ea n a l y s i sa n dv i d e oa b s t r a c t i o n i nv i d e oc o n t e n ta n a l y s i s ，s o m el o w l e v e lf e a t u r e so ff r a m e sh a v eb e e na n a l y z e da n de x p e r i m e n t e d ，s u c ha sc o l o r , s h a p e a n dt e x t u r e ；d i f f e r e n tm o d e l s ，s u c ha sg m ma n dh m m ，h a v eb e e na p p l i e dt oe x p l o r e t h e i ra b i l i t yi nm o d e l i n gs p a t i o t e m p o r a lf e a t u r e so fv i d e o ；m o r em a c h i n el e a r n i n g ， p a t t e r nc l a s s i f i c a t i o n , c o m p u t e rv i s i o na n ds i g n a lp r o c e s s i n gm e t h o d sh a v ea l s ob e e n u s e di nv i d e oc o n t e n ta n a l y s i s d u et ot h o s ee f f o r t s ，s o m er e s e a r c hr e s u l t sc a nb ea p p l i e dt or e a li n d u s t r y s u c c e s s f u l l y , i n c l u d i n gs h o tb o u n d a r yd e t e c t i o n h o w e v e r , b e h i n dt h e s es u c c e s s e s ， t h e r ea r es o m ee s s e n t i a lp r o b l e m su n s o l v e d f o re x a m p l e ，b e c a u s eo ft h ee x i s t e n c eo f s e m a n t i cg a p ，s e m a n t i cr e l a t e dv i d e oc o n t e n ta n a l y s i sh a sn o tg a i n e de s s e n t i a l d e v e l o p m e n t s ，i n c l u d i n gs c e n ea n a l y s i s r e c e n t l y , i np a t t e mr e c o g n i t i o n , s o m ed i m e n s i o n a l i t yr e d u c t i o nm e t h o d s ，n a m e l y m a n i f o l dd i m e n s i o n a l i t yr e d u c t i o n , h a v ea t t r a c t e dm o r ea n dm o r ef o c u s e s ，d u et h a t t h e yc a nf i n dt h ei m p l i c i ti n f o r m a t i o ni nt h ed a t a s e tb e t t e rc o m p a r i n gw i t ht r a d i t i o n a l l i n e a rm e t h o d ss u c ha sp c a a n dt h e yh a v es o m er e l a t i o n s h i pw i t l lt h em e c h a n i s mo f h u m a np e r c e p t i o n i nt h i s a r t i c l e ，w er e g a r dv i d e of r o mt h ep e r s p e c t i v eo fm a n i f o l d , a n da p p l y m a n i f o l dd i m e n s i o n a l i t yr e d u c t i o nm e t h o dt od e a lw i t l lt w op r o b l e m so f v i d e oc o n t e n t a n a l y s i s ：s h o tb o u n d a r yc l a s s i f i c a t i o na n d s c , e n ea n a l y s i s i ns h o tb o u n d a r yc l a s s i f i c a t i o n , w eu s eo n ek i n do fm a n i f o l dd i m e n s i o n a l i t y r e d u c t i o nm e t h o d - - l a p l a c i a ne i g e u m a p - - - t od i s c o v e rt h et e m p o r a lp a t t e mi m p l i c i t i nt h ef r a m es e q u e n c ea r o u n dt h es h o tb o u n d a r y , a n dr e p r e s e n tt h es h o tb o u n d a r ya s t h em a p p i n go ft h ef r a m es e q u e n c ei n t ot h el o w - d i m e n s i o n a lm a n i f o l d s u c h r e p r e s e n t a t i o nc a nr e f l e c tt h ee s s e n c eo fs h o tb o u n d a r y i na d d i t i o n , r e g a r d i n gt h e 复日大学顽十学位论文 4 s a m p l es i z eu n b a l a n c e dc h a r a c t e r i s t i c so fs h o tb o u n d a r yc l a s s i f i c a t i o n , w ed e v e l o p o n es a m p l es i z ed e p e n d e n tk n nc l a s s i f i e rt ol e a r nt h ep a t t e r no ft y p e so fs h o t b o u n d a r i e s e x p e r i m e n t a lr e s u l t ss h o wt h a ts u c hm a n i f o l dr e p r e s e n t a t i o nc a l ld e s c r i b e t h es h o tb o u n d a r yw e l l s i n c et h es e m a n t i cg a pb e t w e e nl o wl e v e li m a g ef e a t u r ea n dh i g hl e v e lc o n c e p t s a n dt h ed e f i n i t i o no f 剐x a sac o n c e p tf u l lo f s e m a n t i ci n f o r m a t i o n , s c e e t e s e g m e n t a t i o nn e v e ra c h i e v e da9 0 0 dp e r f o r m a n c e i nt h i sa r t i c l e ，w ep r o p o s ean c v v s t r u c t u r ef e a t u r e - e i g e n v i d e o m a p - - l y i n gb e t w e e nt h es h o ta n ds c e n ei nt h ev i d e o s t r u c t u r eh i e r a r c h y , w h i c hi se s s e n t i a l l yp h y s i c a la n do fn os e m a n t i c s ，b u tc a l lr e f l e c t s o m ee h a r a c t e r i s t i c so fs c e n e s t h ee x t r a c t i o no ft h i sf e a t u r ec a nb ed i v i d e di n t ot w o m a i ng e p s f i r s t l yw ee m p l o yl a p l a e i a ne i g e n m a pt om a ps h o t si n t ot h ee m b e d d i n g m a n i f o l d ，a n dt h e ne n c o d et h el o w d i m e n s i o n a lr e p r e s e n t a t i o ni n t oo n e d i m e n s i o n a l c u r v e w ec a l lt h ec b r v ea se i g e n v i d e o m a p t h r o u g ht h es t u d i e so ft h ea b o v et w op r o b l e m s ，w ee x p l o r et h ep r o b a b i l i t y , f e a s i b i l i t ya n da p p r o a c h e so fa p p l y i n gm a n i f o l dd i m e n s i o n a l i t yr e d u c t i o nm e t h o d st o v i d e oc o n t e n ta n a l y s i s e x p e r i m e n t a lr e s u l t ss h o wt h a tm a n i f o l di sag o o dp e r s p e c t i v e o fv i d e or e p r e s e n t a t i o na n dt h em a n i f o l dd i m e n s i o n a l i t yr e d u c t i o nm e t h o d sc a l l a c h i e v eg o o dp e r f o r m a n c ei nv i d e oc o n t e n ta n a l y s i s k e y w o r d s ：v i d e oc o n t e n ta n a l y s i s ，m a n i f o l dd i m e n s i o n a l i t yr e d u c t i o n , m a n i f o l d l e a r n i n g , s h o tb o u n d a r yc l a s s i f i c a t i o n , s c e n ea n a l y s i s 复旦大学硕十学位论文 5 第一章视频内容分析概述 随着数字多媒体技术越束越普及，数字相机、数码摄像机等一系列数字图像 视频获取设备的价格越束越低廉，视频制作越束越便捷，普通人也可以方便地制 作出自己的视频。同时，由于互联网技术以及存储技术的快速发展，人们互相共 享数据越束越容易，网络已经成为人们的信息仓库。人们可以非常方便地获取大 量的多媒体数据，并且这样的信息还在不断破制造、共享的过程中。加州大学伯 克利分校的“h o w m u c h i n f o r m a t i o n ? 2 0 0 3 ”【1 】项目显示，世界上从1 8 9 0 到2 0 0 2 年总共生产出3 7 万部影片，如果连续播放的话，将会播放到2 1 0 8 年才会结束。 并且，越来越多的电视、电影节目正在被制作出来。另外，数码摄像设备越来越 受到人们的关注，2 0 0 2 年全球共售出2 7 5 0 力台数码相机。由于数字视频编辑成 本更为低廉，数字电视将会渐渐取代基于胶片的电影和电视。 在面对如此大的视频信息量的情况下，人们不可能再像以前那样依靠手工去 选择自己感兴趣的节目以及从视频节目中获取自己有用的信息。因此，迫切需要 一种自动化的方法，依靠计算机束帮助人们来实现自动的视频内容分析、检索和 挖掘。 1 1 视频的基本概念 1 1 1 视频的分类 视频的分类方法有很多种，可按其制作方式分为模拟视频、数字视频等，按 其内容可分为体育节目、新闻、故事影片等等。虽然有的视频分析算法并不限制 针对特定视频，但是一般来说，由于视频节i i i 的复杂性，大部分算法都是针对某 一类特定视频节目有效的，特别是一些语义相关的研究工作。下面，将简要描述 一下研究中主要遇到的几类视频。 ( 1 ) 新闻视频 由于全世界的电视台每天都在制作大量的新闻节目，并且新闻节目富含广泛 的时效信息，因此，一直以来都受到研究人员的广泛重视。由美国n 1 s t 组织的 t r e cv i d 2 评比，其主要的实验数据就是从电视台录制的新闻节i i i 。 新闻节i i i 具有如下特点：场景信息明确，总体结构清晰，且内容广泛。特别 针对新闻节目的研究领域还有播音员检测等等。 复旦大学硕士学位论文 6 ( 2 ) 体育运动视频 体育运动节目同样具有结构清晰的特点，并且场景相对单调、简单。体育节 目中的事件明确，且重复度高，如投篮等等，也是事件检测研究方向所大量采用 的数据。另外，因为其视频片断重复多，还有大量的重放、快放、慢放等，体育 节目也是视频检索领域的较好的实验数据。 全世界同样在以增长的速度不断制造体育运动类节目，因此，一个有效的、 快捷的分析、检索技术也是非常有意义的。 ( 3 ) 监控录像 银行以及很多公共场所希望以安装摄像头拍摄监控录像束获得对环境的监 控。监控录像具有相当多的特点，如背景基本不变，前景对象简单等。因此，可 以采用如物体分割、跟踪等方法，另外，也可以进行如突发事件检测等研究。 ( 4 ) 故事影片 故事影片的制作融入了导演的一系列意图，且制作手法专业。因此，故事影 片的分析需要一定的关于电影语法的先验知识。 ( 5 ) 家庭制作视频( h o m ev i d e o ) 近年束，由于数码相机、数码摄像机的日益普及，家庭制作视频越柬越多， 如何分析、索引自己拍摄的视频，以方便自己的检索，也就变得越来越重要了。 家庭制作视频具有如下特点：制作手法单一，没有丰富的特效，镜头也比较单一； 相对来说场景比较简单；由于手法的不熟练，可能引入一些抖动。 1 1 2 视频的表示 视频从物理上讲就是在时间上有序且等间隔采样的图像序列。因此，视频的 表示不仅要考虑每一帧图像的信息，还要融入时间上的一些信息，例如帧间的关 系等等，需要获得一个时空的视频表示。 除了最基本的帧序列表示外，为了不同应用的需要，还有一些其它形式的表 示方法。 ( 1 ) 图的表示 3 】 把视频的每一帧图像看作图中的结点，内容相似且时间相近的帧之间存在 边，且边的权重就是两帧之日j 的综合时域与空域的相似度。将视频转换为图的表 示后，就可以应用一些图的算法束进行视频的分析，如图分割等等。另外，也有 复日大学硕十学位论文 7 将视频表示为时空的图，即将每一帧分割成不同的物体，单帧内所有物体之间可 以构成图，并且该物体在不同帧之间也可以构成图。 ( 2 ) 对象序列【4 】 将每帧图像分割成物体，然后利用物体跟踪的技术，使得该视频中的所有物 体都可以在各帧之间形成一个序列，所有物体的时域上的序列就构成了该视频的 表示。但是，由于物体分割与跟踪技术并不是很成熟，因此，这样的表示方法可 能仅对特定的视频类型有效，如监控视频。 ( 3 ) 结构化表示 5 】 视频的结构化表示是视频最重要的表示方法之一，也是视频结构化分析研究 的目标。由于大多数视频在制作的时候就考虑到了结构的因素，因此，结构化表 示也许是视频在语义层面的一个本征的表示。在下一节( 视频的结构) 中，我们 将详细分析视频的结构化表示。 ( 4 ) 索引表示 6 】 视频的索引表示一般是为了检索的需要，在构建视频数掘库时所采用的表示 方法。用较少的存储空间来索引表示视频的一些信息，以获得更快的搜索速度。 1 1 3 视频的结构 一般来说，一段视频代表了制作者一定的意图，表达了一定的语义信息。像 自然语言一样，视频制作也有其一定的语法，办称f i l mg r a m m a r 。视频研究中， 为了接下来的视频分析、浏览、检索的需要，一般将视频看作层次化的、结构化 的表示，在这个表示的基础上再进行其他的分析，提取其他的表示方法。视频一 般可划分为帧、镜头、场景的表示，如图3 1 所示。 视频的最原始表示就是帧序列，镜头表示一次相机从丌启到关闭之间所摄录 下的帧序列。一个镜头具有较完整的信息。我们可以认为，帧和镜头的概念都属 于低级特征概念，没有涉及到视频的语义信息，虽然有时候镜头代表了视频制作 者的一定意义上的意图，但是总的来说还是一个物理的概念。 场景由一组语义上相关、时间上连续的镜头组成，描述了一个独立的故事单 元，是视频的基本语义单元。因此，场景的分割、分析需要视频语义分析工具的 支持。 复旦大学硕十学位论文 8 1 2 视频的内容分析 图1 1 视频的结构化表示 视频内容分析的目标是让计算机理解视频，以便能够更智能地为人们在视频 中挖掘有用的信息，快速检索到人们想要的视频段。当前，由于计算机视觉、图 像分析、机器学习等技术的限制，要想达到这一目标还很困难，因此当前视频内 容分析领域的研究主要集中在利用视频的低级特征来进行有限的分析，辅助人们 对视频信息的处理、检索。下面我们简要介绍当前视频内容分析的两个基础研究 领域的工作。 1 2 1 视频分割 视频内容分析的第一步就是恢复出视频的结构信息，分割出镜头、场景的边 界。视频分割包含这两部分。镜头边界检测是最首先、最基本的一步，也是视频 内容分析中一个基本的工作，主要任务是检测出镜头变换的边界，有人也同时判 断出缓变镜头的镜头转变区的长度。镜头边界检测主要利用视频的低级特征，如 颜色、边缘等，采用一些设计好的、专门的检测算法来检测这些特征的变化，以 判断是否有一个镜头边界的存在。近年柬也有方法采用机器学习算法来训练一个 分类器，让机器自动学习镜头边界特征变化的模式。由于镜头是一个物理上的概 念，因此现在的镜头边界检测己能够获得一个较好的性能，特别是对于切变镜头； 但是由于缓变镜头的复杂性，以及视频中运动以及其他编辑特效的干扰，尚需进 一步的研究。 复旦大学硕士学位论文 9 相对于镜头分割，场景分割更多地涉及到了视频的语义信息。场景不是一个 物理的概念，而是一个相当主观的概念。不同的人对场景的分割会得到不尽相同 的结果。因此，现有的场景分割算法大都利用一些人们预先赋予的先验知识，或 者为场景建立一个数学上的模型，或者采用聚类的方法，来检测场景的存在。这 些方法的主要问题是由于采用的低级特征不包含有语义信息，因而不能反应场景 的语义内涵。 1 2 2 视频摘要 视频摘要是为了寻求视频的更简洁表示，以方便人们的浏览，主要分为两种， 一种称为v i d e os u m m a r y ，还有一种是v i d e os k i m m i n g 。v i d e os u m m a r y 是一种静 态的视频摘要技术，选取一定数量的关键帧来代表视频的信息，其缺点是不能很 好地反映视频的时域信息。v i d e os k i m m i n g 有时也被称为动态视频摘要，是从原 始视频中生成一个更简短的视频序列来表示视频的摘要信息，v i d e os k i m m i n g 相 对更复杂，但也能更好的反映视频的信息。 7 】给出了关于视频摘要的一个说明。 复黾大学硕七学位论文 1 0 第二章流形降维方法概述 视频是由一系列的图像帧所组成的，而图像的原始数据一般都具有非常高的 维数，例如一副1 6 0 1 2 0 的狄度图像，其像素数据就有1 9 2 0 0 维。如果我们在这 1 9 2 0 0 维的数据上直接进行学习和分类，将会带来巨大的维数灾难问题。这是因 为：( 1 ) 由于数掘的维数很高，要想充分训练分类器将需要巨大的样本库，而对 于1 9 2 0 0 维的数掘，这样数量的样本库一般是不可能的，( 2 ) 由于维数的增高， 分类器的学习和训练的复杂度将会有很大的提高。因此，我们需要在原始数据上 进行降维。降维不仅能一定程度上缓解前两个问题，而且降维有的时候还能扮演 自动特征提取的角色，这是由于在更低维数的数掘空间上，有些噪声信息会被丢 弃，而保留一些真正能够表示样本数据特性的信息。 在图像和视频研究领域，主成分分析( p c a ) 【8 】由于其简单性、易用性、以 及在图像数据上较好的性能，广泛应用于人脸识另1 1 1 8 、基于图像的自主导航【9 】 等方面。但是p c a 实现的是线性降维，而对一些非线性的问题，如s w i s sr o l l ， 不能得到很好的结果。m d s ( 多维尺度变换) 【1 0 1 1 】，有时也称为“非线性映 射”，区别于p c a 的线性映射，是寻找一种与原始高维数据具有一致相似性的低 维表示，即降维以后的低维空间的数据之日j 的相似度要与其在原始空间对应点的 相似度保持一致。它保持的是样本之间的拓扑关系。另外，谱图方法近年来也引 起了人们的广泛关注，并应用于聚类【1 2 】【1 3 】，也成功应用在多种降维方法中。 发表于s c i e n c e2 0 0 0 年的流形文章【1 4 】【1 5 】【1 6 】显示了流形降维的方法在发现 高维数据的内在低维特征的能力。1 5 1 6 使用了由于旋转或其他动作所导致的 一个或者两个自由度的人脸数据集，说明了流形降维方法在恢复这个内在自由度 的能力，展现了相对于p c a 等线性降维方法的优越性。目i j ，虽然尚不清楚流 形是否人类感知视觉以及其他信息的基础，但是近柬已经有研究显示人脑中存在 有暗示连续吸引子的神经流形【1 4 】。由于流形与人类感知可能存在的潜在联系， 以及流形降维的良好性能，流形学习也越来越得到研究人员的广泛关注。1 8 对 当前存在的流形方法进行了一个较为全面的综述。 然而，流形方法尚在研究中。还不成熟，例如流形降维方法并没有一个投影 矩阵能够把新进的高维样本映射到低维流形中。有人提出利用学习的方法学习原 始数据到低维空间表示的映射【1 9 】，也有人把流形方法的一些思想融入了基于线 性投影矩阵的降维方法【2 0 】。但是这样的解决方法并没有解决流形降维方法本质 上的问题。另外，流形维数的确定也是一个难题。 复e l 大学硕士学位论文 但是，总的来说，流形方法由于引入了非线性的特性，能够有效地发现样本 内在信息，在很多方面都有了应用。近年来，已经有不少的研究在尝试着流形降 维方法在视频分析、检索方面的应用【1 9 】 2 l 】。后面我们也将进行概述。 2 1 传统降维方法 由于降维技术在机器学习、信息检索领域的重要性，近几十年的研究过程中 取得了很多的算法，在这里，我们重点介绍p c a 、m d s 。由于谱聚类技术近年 来的广泛关注，以及其与一些流形降维方法的密切关系，我们也将对其进行介绍。 2 1 1 主成分分析( p c a ) p c a 的目标是寻求原始数据在低维空| 日j 的投影表示，且最大程度地保留信 息。也就是说，投影后的数据与原始数据的距离平方和最小。即，最小化下列目 标函数： -，=n(hi+善dkffil纠吖 旺，= q ) 一吒0 ( 2 1 - i 其中，m 表示样本的均值，表示样本的原始数据，q 表示原始数据在 低维空间的表示，岛表示低维空间的基，d 是低维空间的摧数，且d 个q 组成的 矩阵就是投影矩阵。从中我们可以看出，p c a 的投影矩阵是一系列经过样本中 心的向量。 通过对上式求解，我们可以得出p 必须满足，& = 知，s 是样本的协方差矩 阵， s = ( 耳- m x x , 一y ( 2 2 ) 而使得j 最小的投影空b j 的d 个基岛，白是s 最大d 个特征值对应的特征向 量，则一_ 【q ，】则是原始空间到低维空间的投影变换矩阵。 从几何上解释，样本点在原始空间形成了一个椭球状的分布，而协方差矩阵 最大特征值对应的特征向量就是这个椭球的主轴，代表了样本信息散度最大的方 向，因此，在这个方向的投影也就保持了样本数据的平均最大信息。 在有的情况下，由于噪声的分布，导致了样本数据的散布，这时的p c a 就 不能正确地判断真正的信息主方向，而会保留噪声方向的信息。另外，p c a 不 是为分类设计的降维方法，有的情况下对分类问题得不到好的结果。 复日大学硕十学位论文 1 2 2 1 2 多维尺度变换( m d s ) m d s 是用于高维数据可视化的一项技术，它的目标是数据在低维空间的表 示尽量保持原始空问的相似度关系。假如有n 个样本而，毛，我们希望将其降维 到低维空日j ，设分别对应的低维表示为m ，因为很多情况下不可能获得低 维空间表示与原始空间的样本之间有完全对应的相似度，因此有不同的目标函数 去获得整体的最优，如，我们可以有以下目标函数定义： 厶= 鬯署 ( 2 3 ) 有了这样的目标函数，我们就可以使用梯度下降的方法进行迭代来逼近这个 目标函数，也有将这个问题转换为代数特征系统的解的问题( 经典m d s ) 。得到 的最终低维表示就会一定程度上保持了原始数据问的拓扑关系。 相比于p c a ，m d s 在一定的情况( 原始数据问的度量采用不同于欧氏距离 的非线性度量) 下具有一些非线性的特点。后面我们可以看到，i s o m a p 就基于 了m d s 的方法进行了流形降维。 2 1 3 谱聚类技术 谱聚类技术是一类利用谱图论的方法来进行聚类的技术。下面我们将给出一 个常见的谱聚类算法【1 3 】。 给定一样本集s = “，s ：， ，样本维数为”，并且其聚类数设为k ，则可按 以下步骤进行聚类： ( 1 ) 构造相似度矩阵职 形，：e x p ( 一l i 茸一。2 盯2 ) f j ( 2 4 ) 【0 i = ( 2 ) 构造对角矩阵d ，d i = ；以及矩阵三= d 4 ”w d 。1 ” ( 3 ) 解三的特征值问题，得到其最大k 个特征向量：而，屯，以，并对其分 别归一化，得到一个矩阵，形式为：y _ 高 ，蠢净，”毒手】r 。 ( 4 ) 将y 的每一行看作为k 维空问的一个点，对其进行k - m e a n s 聚类，每 一行得到一个类属标号。于是，y 每一行所对应的原样本s 则属于相应的聚类。 从上述步骤我们可以看出，谱聚类的方法主要是依赖谱图论的一些方法将原 复日大学硕i 学位论文 始数据映射到一个更低维的空间上，在低维空间上使用一些传统的聚类方法进行 聚类分析，再映射到原始的数据上。因此，谱聚类的方法也包含着一个谱降维的 过程。 2 2 流形降维方法 我们处理的真实图像、声音或者其他类型的数据不一定是分布在一个线性子 空间上，流形降维是指这样的一类降维方法：它们假设样本数据分布在一个嵌入 在欧氏空间的低维流形上，在保持样本的测地距离的条件下获得其在低维欧氏空 间的表示。这里，我们主要介绍三种流形降维方法：等度规映射( i s o m a p ) 、局 部线性嵌入( l l e ) 以及拉普拉斯特征映射( l a p l a c i a ne i g e n m a p ) 。i s o m a p 是一 个全局的方法，而l l e 和拉普拉斯特征映射都属于局部的方法。 2 2 1i s o m a p i s o m a p 是一个全局的流形学习算法。主要有三步： ( 1 ) 构造邻接图。对于训练样本x i ，毛，构造一个以这疗个样本为顶点的 图，边的设置可以有两种方法：a ) s t s o m a p ，即当且仅当两顶点薯，乃之间的距 离小于阈值g ，两顶点之间存在一条边；b ) k - i s o m a p ，当且仅当顶点葺是_ 的 k 近邻或者点_ 是薯的k 近邻时，存在一条边。这里可以采用欧氏距离计算顶点 之间的距离。 ( 2 ) 计算测地距离。如果俩顶点之间存在一条边，则边的仞始权重设为两 顶点之间的距离，否则设为。o 。然后采用f l o y d 最短路径算法，逐次计算顶点之 问的最短路径。这样得到的每对顶点之间的最短距离就是估算的测地距离。它的 基本思想是假设每一点的邻域都是线性的。 ( 3 ) 构造低维嵌入。使用m d s 基于上一步构造的加权图以及测地距离发 现原始效掘到低维空间的映射，尽可能保持样本的测地距离。也就是最小化下列 代价函数： ，= 忆d o ) 一f ( q ) 峙 ( 2 5 ) 其中，f 是距离矩阵到内积的转换函数( 参见经典m d s 算法【1 1 】) ，d g 表示 测地距离，鼠表示投影后的欧氏距离。通过解这个目标函数最小化问题，可以 得到原始数据的低维投影即是r ( 以) 的最大d 个特征值所对应的特征向量。 复日大学硕十学位论文 1 4 2 2 2l l e l l e 方法的目标是保持局部邻域信息不变。具体算法有_ - - 步： ( 1 ) 构造邻居集。对于数掘集中的每一个样本如，搜索其k 近邻，构成集 合玎御。 ( 2 ) 计算重构权矩阵。对于每个样本而，我们希望能够以其邻居集来重构 它，即五= 一，并最小化重构的均方误差： 军卜一，磊，_ 1 2 c 2 6 ， 可以通过最小二乘法束解得权矩阵w o ( 3 ) 构造低维表示。我们希望构造x 的低维表示e 使得其与x 保持一致 的邻域信息： 咖手巧j 2 眨7 ， 其中w 是上一步解出的重构权重矩阵。最小化等式2 7 ，并且加上平移不变、 旋转不变以及尺度不变的限制， e = o ( 2 8 ) 专；啊= 五 ( 2 9 ) 可以转化为一个特征值求解的问题，即求解矩阵( e 一) ，( e 一) 的最小舟j 个特征向量。 2 2 3 拉普拉斯特征映射 拉普拉斯特征映射算法的步骤详述如下： 第一步( 构造加权邻接图) 高维空间的每一个点作为邻接图中的顶点。有两 种方法可以确定两顶点之间是否存在一条边。( 1 ) 甩近邻法。给定两顶点而、琦， 当且仅当而是而的n 近邻或者而是而的，l 近邻时，这两个顶点之间有一条边。( 2 ) 占邻域法。如果两个顶点x ，、而之间的距离小于某个阈值占，则这两个顶点之间 存在一条边。 如何确定边的权重，也存在两种方法。( 1 ) 简单方法。如果而，而之间存在 复日大学硕= p 学位论文 一条边，则这条边的权重2 1 ，否则= o 。( 2 ) 热核法。如果而，吩是连通的， 隅一，胛 则它们之问的权为：= ，_ ，这里的t 是一个调节因子，可以根据实验确定。 如果而，母不连通，则2 0 。 第二步( 特征映射) 假设上面构造好的图是连通的，否则针对每个连通子图 分别进行下述处理。 ( 1 ) 构造图拉普拉斯矩阵( g r a p hl a p l a c i a n ) 。首先构造对角矩阵d ，d 的对 角线元素为d = ，则图拉普拉斯矩阵则可得到：l = d 一阡，o ( 2 ) 计算如下广义特征值问题：l y = t d y 。设计算出的特征值为：如“ 屯，厶，按从此小到大升序排列，它们对应的特征向量为：玩玩圪，l 。 可以证明，2 0 = 0 ，且所有的元素值都是1 。因此，特征向量玩圪，匕是最 终的解，表示了嵌入的流形结构， 是数据集的内在维数。 2 3 流形降维方法在视频分析、检索中的应用 流形方法由于利用了流形嵌入的特性，比传统的线性方法或基于欧氏距离的 方法更好地适用于一些高维、复杂的数据，也更能反映人类对图像、视频的感知， 已经应用于图像检索【2 0 】、视频分析 2 l 】以及网络可视化分析 2 2 1 中。接下来我们 介绍流形方法在视频图像分析检索中的两个应用案饲。 2 3 1 图像流形1 2 0 】 流形降维方法在应用到实际的图像检索中，存在两个问题：( 1 ) 流形方法要 想能较好地发现实际的嵌入流形需要非常大量的样本来训练，并且训练样本数据 能够对实际的流形形成一个紧密的分布，否则测地距离的估算就不会准确。( 2 ) 流形方法由于是非线性的，不存在一个投影矩阵，因此，如何对新的样本获得一 个在低维流形的表示? 【2 0 】提出了上两个问题的解决方法，针对样本不足的问题，使用相关反馈来 估算样本之日j 实际的测地距离。而针对新样本表示的问题，则使用了一个r b f 网络来学习原始空间到低维流形空间的映射。 具体的方法如下： ( 1 ) 从用户交互中不断改进测地距离的估算，通过不断的相关反馈信息， 最终获得尽量好的距离估计。 复日大学硕十学位论文 1 6 ( 2 ) 已经获得了距离矩阵的表示，再利用拉普拉斯特征映射去发现嵌入流 形，尽量保持了样本之间的距离信息。 ( 3 ) 训练一个r b f 神经网络柬拟合样本原始空间到低维流形空间的映射。 对于新柬的数据，使用这个训练好的r b f 网络束预测其在低维流形的表示。 2 3 2 使用i s o m a p 发现视频轨迹【2 1 1 视频是由许多连续的图像所组成的有序序列。因此，可以从两方面看待视频， 首先，一段视频表达了相关图像的空间；其次，视频也包含了存在于这个空间的 轨迹。 r o b e r tp l e s s 2 1 基于以上考虑，尝试使用i s o m a p 来进行小视频片断的分析。 主要有两步，一是发现视频图像空间的低维流形。一段视频中的所有图像都具有 一定的相关性，存在于一个低维的流形空间中。文中使用i s o m a p 来发现这个嵌 入流形。第二步则在这个低维的流形空问上得到图像序列的有序表示，即视频轨 迹。在这个低维的表示上，我们能更容易发现视频片断的一些特征。文中就描述 了几种这样的模式：循环的、螺旋状的、多节的( 没有周期性的模式) 、线性的 以及组合的模式。 r o b e r t 也举例说明了这样的轨迹掐述能够应用于视频分析的多个领域，如视 频分割以及视频的超分辨率表示。 r o b e r t 的方法在应用流形到视频分析中作了一个有效的尝试，但是直接应用 流形降维到视频分析中尚存在很多问题。例如，虽然视频在时间上的采样比率比 较高，一般有2 5 帧每秒，但是视频中存在的不连续性( 如镜头边界、高速运动 以及相机运动等) 所引起的图像空间的不紧密分布给流形降维的性能造成一定影 响。另外，r o b e r t 的工作是对小的视频片断进行的分析，2 0 0 帧的视频花费了大 约4 分钟的时间【2 l 】，如果应用于长视频序列的分析，时间复杂度也是一个需要 考虑的问题。 我们也看到，流形降维提供了视频一个更符合人类感知的表示。因此，我们 也有理由相信，流形降维方法对视频的分析和检索必定产生深刻的影响。 复日大学硕士学位论文 1 7 第三章镜头边界分类 镜头，通常是指在一次相机的开关过程中所拍摄下的视频序列。现在我们所 指的镜头也包括由于视频编缉而产生的类似于相机开关的效果下而形成的视频 序列。镜头包括切变镜头( h a r dc u t ) 和缓变镜头( g r a d u a lt r a n s i t i o n ) 。通常缓 变镜头还可以分为溶解镜头( d i s s o l v e ) 、淡入淡出镜头( f a d ei n o u t ) 、擦变镜 头( w i p e ) 等等。在视频制作中制作人员需要融合各种镜头编辑类型，以表达一 定的语义，暗示制作人员一定的意图。例如，体育视频中，擦变镜头( w i p e ) 往 往表示重放或者犯规；同样，淡入淡出( f a d ei n o u t ) 往往表示一段新节目的起 始和结束；溶解镜头( d i s s o l v e ) 一般发生于故事片( f e a t t a 屯f i l m ) 、纪录片 ( d o c u m e n t a r i e s ) 、人物传记片( b i o g r a p h i c a l v i d e o ) 以及风景片( s c e n i c v i d e o ) 中，常用于表示一段时间的流逝 2 3 】。 镜头是视频内容分析与处理的基本单元，镜头边界检测是视频内容分析的一 个重要步骤。镜头边界检测是指通过自动的方法寻找出两个镜头切换的边界。镜 头边界分类则是分类出各镜头边界是切变镜头还是缓变镜头，如果是缓变镜头的 话，再分类出是溶解镜头、淡入淡出镜头或是擦边镜头。 由于镜头边界检测的基础性和重要性，在过去的十几年中，视频分析研究人 员对此