（信号与信息处理专业论文）基于数据挖掘的视频镜头分类技术研究.pdf

摘要 摘要 随着多媒体和网络技术的飞速发展，产生了海量的视频数据。为了使用户能 够快速准确地检索到感兴趣的视频信息，需要对这些数据进行有效地组织、管理 和分析。其中，通过视频分类技术对视频数据进行语义类别的整理分类，能够缩 小检索范围，提高检索速度。 视频分类可以分为基于关键字的视频分类和基于内容的视频分类。通过人工 标注的关键字对视频进行分类，不仅受入主观因素的影响，标注的关键字主观性 强，而且随着日益增长的视频数据量，人工标注费时费力。基于内容的视频分类 根据视频的视觉、音频等内容对视频进行自动分类，由于视觉、音频特征客观地 描述了视频的真实内容，因此克服了基于关键字分类产生的问题。 目前视频内容分析技术主要是利用视频低层特征描述其内容，与人们对视频 语义内容的理解存在很大差异，因此基于内容的视频分类存在的问题是视频低层 特征和高级语义概念之间的语义鸿沟。本文在分析现有基于内容的视频分类算法 的基础上，采用数据挖掘技术，对基于内容的视频分类若干关键技术进行了研究， 力图挖掘视频的类别语义信息，以克服现有的语义鸿沟问题。本文主要工作包括： 视频镜头边缘检测和关键帧提取、视频特征提取和视频镜头分类等。具体内容包 括以下几个方面： ( 1 ) 视频镜头分割部分，提出了一种基于因果的自适应双阈值镜头边界检测 算法，并对突变检测和渐变检测方法进行了改进，取得了较好的检测效 果，最后在镜头分割的基础上进行了关键帧提取； ( 2 ) 通过分析卡通、新闻、电影、篮球和足球五类视频在视觉特征上的差异， 完成了基于关键帧和镜头的颜色和运动视觉特征的提取，并对特征数据 进行整理，实现了一套视频镜头描述方案，取得了较好的视频镜头内容 表达效果； ( 3 ) 在视觉特征提取和视频镜头描述基础上，采用m i c r o s o r 决策树分类算 法构建视频镜头分类模型，对视频镜头进行高级语义的视频类型分类， 取得了较好的分类性能。 本文所提的视频分类方法可以进一步推广到视频检索、视频内容过滤、智 能化电视等各种应用中，并会推动新的视频应用的发展。 关键词：视频镜头分类；镜头边界检测；视频特征提取；m p e g 7 标准；数 据挖掘；m i c r o s o f t 决策树 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fm u l t i m e d i aa n dn e t w o r kt e c h n o l o g y , al a r g e a m o u n to fv i d e od a t aa p p e a r s i no r d e rt oe n a b l eu s e r sq u i c k l ya n da c c u r a t e l yr e t r i e v e t h ev i d e oi n f o r m a t i o no fi n t e r e s t ，t h ev a s ta m o u n t so fv i d e on e e dt ob em a n a g e da n d a n a l y z e de f f e c t i v e l y o n e o ft h e m ，v i d e oc l a s s i f i c a t i o nt e c h n i q u ef o rc a t e g o r i z i n g v i d e os e m a n t i cc o n t e n tc a nb eu s e dt on a r r o wt h er e t r i e v a lr a n g ea n di m p r o v et h e r e t r i e v a ls p e e d v i d e oc l a s s i f i c a t i o nc a nb ed i v i d e di n t ok e y w o r d b a s e dv i d e oc l a s s i f i c a t i o na n d c o n t e n t b a s e dv i d e oc l a s s i f i c a t i o n c l a s s i f y i n gv i d e ot h r o u g hm a n u a l l yl a b e l e d k e y w o r d si si n f l u e n c e db ys u b j e c t i v ef a c t o r , b e c a u s et h ek e y w o r d sl a b e l e da r es t r o n g s u b j e c t i v i t y w h i l ew i t ht h eg r o w i n ga m o u n to fv i d e o ，i tw i l lb eat i m e - c o n s u m i n ga n d l a b o r i o u sw o r k c o n t e n t - b a s e dv i d e oc l a s s i f i c a t i o na c c o r d i n gt ot h ev i s u a la n da u d i o c o n t e n tc a nb eu s e dt oc l a s s i f yv i d e oa u t o m a t i c a l l y t h ev i s u a la n da u d i of e a t u r e sc a n d e s c r i b et h er e a lc o n t e n to fv i d e o ；t h i sm e t h o dc a nb ea d o p t e dt oo v e r c o m et h e p r o b l e m so fk e y w o r d b a s e dv i d e oc l a s s i f i c a t i o n t h ec u r r e n tc o n t e n ta n a l y s i st e c h n i q u e su s e dt od e s c r i b et h ec o n t e n to fv i d e oa r e m a i n l yl o wl e v e lf e a t u r eb a s e d ，w h i c ha r eq u i t ed i f f e r e n tf r o mt h es e m a n t i cc o n c e p t s i nh u m a n sv i e w r n l ep r o b l e mo fc o n t e n t b a s e dv i d e oc l a s s i f i c a t i o ni st h es e m a n t i c g a pb e t w e e nl o wl e v e lf e a t u r e sa n dh i g hs e m a n t i cc o n c e p t s i nt h i sp a p e r , b a s e do n t h ea n a l y s i so fe x i s t i n gc o n t e n t b a s e dv i d e oc l a s s i f i c a t i o na l g o r i t h m s ，d a t am i n i n g t e c h n i q u ei sa d o p t e d ，a n ds e v e r a lk e yt e c h n o l o g i e sa r er e s e a r c h e df o rd i g g i n gt h e s e m a n t i ci n f o r m a t i o no fv i d e og e n r e t h em a i nw o r k si n c l u d e ：v i d e os h o tb o u n d a r y d e t e c t i o na n dk e yf r a m ee x t r a c t i o n ，v i d e of e a t u r e se x t r a c t i o n ，v i d e os h o tc l a s s i f i c a t i o n a n ds oo n ，a sf o l l o w i n ga s p e c t s ： ( 1 ) i nt h ev i d e os h o ts e g m e n t a t i o np a r t ，a na d a p t i v et w i n c o m p a r i s o ns h o t b o u n d a r yd e t e c t i o na l g o r i t h mb a s e do nt h ec a u s ea n de f f e c tm e t h o di s p r o p o s e d r e s p e c t i v e l y , t h em e t h o d sf o rd e t e c t i o no fc u tc h a n g ea n dg r a d u a l t r a n s i t i o na r ei m p r o v e dt oo b t a i nab e t t e rd e t e c t i o nr e s u l t a n do nt h eb a s i s o fv i d e os h o ts e g m e n t a t i o n ，k e yf r a m e sa r ee x t r a c t e d ； ( 2 ) b ya n a l y z i n gt h ed i f f e r e n c e si nt h ev i s u a lc h a r a c t e r i s t i c so ff i v ev i d e og e n r e s w h i c hi n c l u d ec a r t o o n s ，n e w sm o v i e s ，b a s k e t b a l la n df o o t b a l l ，t h ec o l o ra n d m o t i o nv i s u a l f e a t u r e sa r ee x t r a c t e dr e s p e c t i v e l yb a s e do nk e yf r a m e sa n d s h o t s t h ef e a t u r ed a t ai sf u r t h e rd e a l tw i t ht oa c h i e v ead e s c r i p t i o no fv i d e o i i i 北京t 业大学工学硕二l 学位论文 s h o t ，w h i c hc a l lr e p r e s e n tt h ev i d e os h o tc o n t e n te f f e c t i v e l y ； ( 3 ) i nt h eb a s i so ft h ev i s u a lf e a t u r e se x t r a c t i o na n dv i d e os h o td e s c r i p t i o n ， m i c r o s o f td e c i s i o nt r e ec l a s s i f i c a t i o na l g o r i t h ma r eu s e dt ob u i l dav i d e o s h o tc l a s s i f i c a t i o nm o d e l t h i sm o d e lc a nb ea p p l i e df o rv i d e og e n r e c l a s s i f i c a t i o na n do b t a i nag o o dc l a s s i f i c a t i o np e r f o r m a n c e t h em e t h o do fv i d e oc l a s s i f i c a t i o np r o p o s e di nt h i sp a p e rc a nb ef u r t h e ra p p l i e d t ov i d e or e t r i e v a l ，v i d e oc o n t e n tf i l t e r i n g ，a n ds m a r tt vt e c h n i q u e sa n ds oo nt o p r o m o t ea n e w d e v e l o p m e n to f v i d e o a p p l i c a t i o n s k e y w o r d s ： v i d e os h o tc l a s s i f i c a t i o n ；s h o tb o u n d a r yd e t e c t i o n ；v i d e of e a t u r e s e x t r a c t i o n ；m p e g - 7 ；d a t am i n i n g ；m i c r o s o f td e c i s i o nt r e e i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：墨叁坐! 翌日期：2 1 i 每乏曼 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 虢雌聊妣 l 眺掣 第1 章绪论 1 1 课题背景与意义 第1 章绪论 随着多媒体技术和网络技术的飞速发展，由于存储设备成本的减少、网络传 输速率的提高以及压缩技术的不断改进，各种多媒体信息不断涌现。例如：数字 图书馆、远程教育、视频点播、数字视频广播、交互式电视、多媒体信息系统等 的广泛应用产生了大量的多媒体数据。多媒体数据包括音频数据、图像数据、视 频数据、序列数据和超媒体数据。视频作为一种常见的媒体形式，包含了最丰富 的信息，与人们的日常生活密切相关。面对这些海量视频数据，如何快速有效地 对其进行分析、索引、浏览、检索和语义分类等是目前一项重要研究内科。 数据挖掘就是从大型数据库的数据中提取人们感兴趣的知识。随着视频数据 库技术的日趋成熟、数据挖掘技术应用的成功，视频数据挖掘逐渐成为数据挖掘 中的一个研究热点。视频数据挖掘就是将数据挖掘技术和视频信息处理技术有机 地结合起来，形成的在视频数据库中进行知识发现的信息处理方法。视频分类是 视频数据挖掘的一个重要分支，其目标是从视频数据中发现有关视频分类的知 识。 视频分类是许多视频应用的基础，为日益增加的视频数据管理提供了基础， 并且在v o d ( v i d e o o n d e m a n d ) 和智能h d t v ( h i g h d e f i n i t i o nt v ) 的发展中发挥 着重要的作用【2 1 。驱动它发展的主要应用包括基于样本的检索、视频摘要总结、 视频索引和标记等【3 】。如果视频被划分到不同的类型分类之中，就可以对不同分 类运用领域特定的分析算法对它们进行迸一步的处理。 数字视频虽然在制作阶段就可以被进行分类标记，但仍然需要视频自动分类 技术【4 1 。首先，目前大量存在的视频数据还没有被标注分类。对视频数据进行人 工标注或分析是一个费时费力的工作，难以适应视频数据的飞速增长。其次，基 于内容的视频分类根据视频的视觉、音频等内容对视频进行客观地自动分类，对 于视频媒体流广播而言是基本的过滤器。例如目前家居电视的发展方向之一是向 着智能个性化发展，人们希望电视具有自动识别播放内容，视频过滤等功能。另 外，视频分类技术还可以用于数字商品非法扩散检测中，与标签或水印技术容易 受到人为的错误和欺诈的影响不同，基于内容的视频分类仅依赖于真实的视频内 容。 如果能有效的对视频分类，获取视频分类的信息，就能在一定程度上弥补视 频低层特征和高层语义特征之间的鸿沟。计算机对视频的处理分析主要基于视频 的视觉特征，如帧图像的颜色、纹理，还有摄像机的运动等低层特征；而人们对 于视频的理解和认识，是建立在视频描述的内容或事件的语义理解基础之上的。 北京工业大学t 学硕士学位论文 这种人类思维中的语义概念是计算机无法从视频的视觉特征中直接获取的，这也 就是通常所说的“语义鸿沟 ( s e m a n t i cg a p ) ，如图1 1 所示。语义鸿沟是指格 式化信息和语义信息之间缺乏一致性【3 1 。视频分类技术可以通过对视频低层视觉 特征进行分析，从中发现有关视频类型分类语义，为视频语义分析的研究打下基 础。 图i 1 语义鸿沟 f i g u r el - ls e m a n t i cg a p 综上所述，视频分类技术的发展在各个领域都有其重要意义。由于一段长视 频可能包含成百上千的镜头，数据量巨大，视频又是一种非结构化的数据，不利 于后续的分析。在视频分类方法中，可以针对整段视频进行分类，也可以对分割 后的视频段进行分类，这时视频可以被分割成镜头或者场景再进行分析理解【5 j 。 场景分割需要对视频内容有一定的语义理解，实现起来比较困难。镜头是一种很 自然的视频分割方法，并且包含了一定的语义概念，镜头边界检测只需用到一些 低层物理特征，较场景分割容易实现。 数据挖掘技术能够解决许多知识发现问题，包含丰富的挖掘方法，能够促进 视频分类的研究，从而获取视频的语义信息。本文从数据挖掘的角度出发，基于 视频的视觉内容，以视频镜头为单位进行了视频分类技术的研究。 1 2 研究进展及现状 1 2 1 视频分类问题分析 视频分类是一个宽泛的主题，在许多应用中也称为视频解释或视频理解【3 1 。 根据分类依据，视频分类可以分为基于注释( 关键字) 的分类和基于内容的分类。 第1 章绪论 基于注释的视频分类需要人工对视频进行标注，工作量巨大并严重受人主观因素 的影响，所以其应用范围受到限制。基于内容的视频分类能利用视频的视觉、音 频内容对视频自动分类，不受人主观因素影响并且分类精度高，是目前的主要研 究方向。 视频分类中的一个重要因素是待分类的视频的范围。般来说，输入的视频 分为窄范围和宽范围两种1 3 】。s m e u l d e r s 等人在文献中提到“窄范围视频在视频 外观的所有有关方面具有有限的可变性”【6 】。如果输入视频的范围变化有限，就 能更好的定义视频的语义特征，分类工作就更加具体。例如，一般监控视频是在 特定的控制条件下拍摄的，其视频内容在各自的类别中有较强的相似性，所以它 们的视频范围比较窄。相反地，s m e u l d e r s 等人认为“对于具有相同语义特征， 宽视频输入范围的视频在其外观上具有无限制且不可预知的可变性”【6 j 。如果所 输入的视频的范围相对来说没有约束，分类方法就是那些可以将视频划分到预先 定义的类别中的技术。宽范围的视频一般是指广播视频，即那些具有广泛输入范 围的各种主流娱乐视频，例如电影、卡通等。广播视频具有最大的类内多样性， 最主要的就是视频类别的数目和视频类别的变化【3 1 。 1 2 2 不同级别的视频分类 自动视频分类在概念上主要分为两类：其一是数字视频的固有特性分类，广 播视频的分类级别如图1 2 所示。 圈1 - 2 广播视频分类级别 f i g u r e1 - 2g e n e r a lc l a s s i f i c a t i o no fb r o a d c a s tv i d e o 3 北京1 = 业大学工学硕士学位论文 视频的固有特性一般是指编辑效果，主要包括摄像机的平移，缩放，旋转等 编辑效果，能够在精确的意义上和故事情节有关系，但其本身不作为故事情节的 一部分。其二是视频语义分类，即从视频固有的语义内容对视频进行分类。从语 义的角度来讲，视频又可以被划分为类型( g e n r e ) 、事件( e v e n t ) 、对象( o b j e c t ) 三个 级别，这是几乎所有多媒体视频中都会出现的元素。 视频数据是由不同的类型组成的，一个视频类型就是视频可能属于的类别， 例如，电影、体育、新闻和卡通等等。而类型本身由包含着子类型，例如，体育 类又可以细分成足球、篮球、游泳、赛车等。视频类型具有层次性，可以被看成 一种树形结构，相同级别的类型是互斥的，比如足球类视频不能成为篮球类的。 观众常常对一个给定的视频类型有不同的认识，一个视频的类型通常通过观察视 频的内容决定，并且往往归结为观众主观观点和语义的微妙差别。然而当进行自 动分类过程时，研究者必须谨慎地选取那些相对容易定义和一般被广泛认可的类 型1 7 j 。视频分类研究的历史表明，经常被选择的类型包括卡通、新闻、音乐、广 告和体育等【3 1 。 视频类型分类最早是在1 9 9 5 年由f i s c h e r 等人提出的，将视频分为新闻、广 告、卡通、网球和赛车等类型，使用了三步法研究方法：首先，提取基础的声音 和视觉统计特征，包括视频片段中的场景颜色统计信息、运动、内容模式和声音 等属性；然后，利用这些已有的低级特征去推导高级类型属性，例如场景长度， 摄像机和对象运动强度以及语言、音乐和噪声等等；最后，这些属性被用来决定 视频类型【8 j 。t r u o n g 等人提出的分类方法包括了所有的流行类型。该方法中通过 对编辑效果、运动和颜色的研究提出了一套可计算视频特征，然后使用决策树算 法进行视频类型的检验1 9 】；c h e n 等人提出了基于知识的视频内容分类方法，通 过检查五种视频类型的许多视频后，形成了知识库中的分类规则，实现了基于规 则库知识的视频内容分类系统【io l ：z h o u 等人提出了有监督的基于规则的视频分 类系统，使用自动视频分割、注释和摘要技术进行无缝隙的信息浏览和更新】。 首先检测视频场景，为每一个场景提取运动、视觉和声音特征，然后通过联合使 用低级特征和知识库中的分类规则得出更高的语义。该系统通过受监督的学习导 出分类规则：r o a c h 等人只针对一种视频类型进行视频分类，提出了一个卡通视 频分类方法【l 引。该方法使用视频中前景对象的运动特征，能够把视频分为卡通 类和非卡通类。 每一段视频又包含很多事件，因此有许多对事件类型进行分类的方法研究。 s h e a r e r 等人将新闻视频分为主持人镜头、内容提要、旁白等场景事件【1 3 1 ；h a e r i n g 等人提出了一个在有限视频输入范围内的结合静态和动态特征的分类方法，用事 件检测发现野生动物视频中的狩猎活动【1 4 】：y o w 等人通过对足球视频内容的分 析，通过跟踪足球运动划射门事件进行检测l l5 】；c h a n g 和l e e 等人对排球比赛中 第1 章绪论 的事件进行分类【i6 l ；z e l n i k m a n o r 和i r a n i 对一些不易定义的相似事件进行检测， 例如暴力、恐怖等场景的检测【l7 1 。 每个事件最终是由大量的对象组成，对象是分类级别中最低的一层，它直接 影响了视频的语义信息，其中人脸是最常被检测的对象【l 引。对象的检测需要很 好的结构特征提取，一般有两种方法实现：第一是使用基于规则的方法，在特征 提取的过程中引入人的理解和先验知识，例如人的五官结构；第二是使用模式学 习方法，即先对给出的对象的多个样本进行学习。 1 2 3 基于内容的视频分类技术难点 近年来，人们对视频分类技术的研究已经取得了一些研究成果，提出了许多 基于内容的视频分类方法和系统，包括从低级的、有限检测范围的事件检测方法 到高级的、较宽检测范围的类型分类方法1 3 j 。总体来看，这些系统需要研究的主 要技术大都包括视频分割方法，视频特征提取和数据处理、视频分类方法三个方 面。通过分析目前基于内容的视频分类算法，其研究难点还是在于如何有效地消 除视频低层特征和高级语义之间的鸿沟，主要包括： ( 1 ) 为了将视频分割为易于管理的段，必须有效地检测出镜头边界检测。镜 头变换方式主要有突变和渐变，其中镜头渐变的方式比较复杂，因此难以有效地 进行检测识别，是目前研究的难点； ( 2 ) 原始视频数据没有很好的结构，需要采用视频特征化的方法对视频进行 处理，即从视频中提取出各种特征对视频进行表示。选择适当的特征对视频进行 表示是视频分类成功的关键，所以特征的选择和有效的提取方法成为一个研究重 点： ( 3 ) 视频分类算法很多，一种算法难以适应各种视频分类的要求。对于视频 类型分类方面的一些算法还有许多不足，比如可扩展性不好，不能形成有效的分 类规则，不适合在线分类应用等。因此需要研究一些通用性较强且健壮的视频类 型分类算法。 1 3 论文的研究内容与安排 本文的研究内容主要针对基于内容的视频分类中视频分割方法、视频特征提 取和视频分类方法等关键技术展开的，研究内容框图如图1 3 所示。 北京工业大学工学硕上学位论文 图1 - 3 本文研究内容的框图 f i g u r e1 - 3t h ef r a m e w o r ko fp r o p o s e dr e s e a r c hc o n t e n t 视频是由一系列图像和声音组合而成的多媒体序列，即包括视觉和听觉两个 方面。本文的主要研究对象是基于视频的视觉信息，概括起来主要包括以下几个 方面： ( 1 ) 视频镜头边界检测 快速准确的视频镜头边界检测是多种视频应用的前提，能够将视频组织为以 镜头为单位的序列，作为进一步视频分析的基础。像素域视频镜头边界检测方法 简单易行、易于理解，并且不依赖于视频的压缩和解压算法，得到了大量的应用。 在现有方法的基础上，本文提出了一种简单而有效的像素域视频镜头边界检测方 法基于因果的自适应双阈值镜头边界检测算法，并进行了实验分析，结果表 明本文提出的算法可以获得较好的检测性能。 ( 2 ) 视频特征提取和数据预处理 由于原始视频数据没有很好的结构，很难在其上直接进行视频分析。一般都 采取视频特征化方法对视频进行处理，即从视频中提取出各种特征对视频进行表 示，视频分类成功的主要因素。在视频镜头分割的基础上，本文分别基于关键帧 和镜头提取了大量的视频特征，将这些特征数据进行处理和组织，为下一步分类 工作提供分类依据。 ( 3 ) 视频分类方法 视频分类算法很多，范围广泛。视频类型分类是在较高的语义层上把视频划 分为预先定义的类型，比如卡通片、新闻、足球比赛和篮球比赛等。本文将研究 如何通过有效的分类算法将视频的颜色、运动等特征映射到视频类型的高级语义 特征上。 论文共分为六部分，安排如下： 第1 章绪论。首先阐明了本课题的研究背景和意义，然后给出论文的主要 研究内容以及论文安排。 第l 章绪论 第2 章数据挖掘和视频分类技术。分别介绍了数据挖掘、视频数据挖掘技 术以及基于内容的视频分类。最后总结了各种常用的视频分类技术。 第3 章视频镜头边界检测和关键帧提取。在总结现有视频镜头分割和关键 帧提取方法的基础上，提出了一种基于因果的自适应双阈值镜头边界检测方法， 并基于镜头提取了关键帧。 第4 章视频特征提取和数据处理。首先简要介绍m p e g 7 标准及其视觉特 征描述方法，然后通过分析视频特征提出了一种基于关键帧和镜头的特征提取方 案，并进行数据处理，实现了一套基于颜色、运动特征的视频镜头描述方案。 第5 章基于数据挖掘的视频镜头分类。给出了本文视频镜头分类系统的整 体框架，提出了一种基于m i c r o s o f t 决策树的视频镜头分类方法并构建了视频镜 头分类模型，最后给出了实验结果与分析。 第6 章总结与展望。对本文主要工作进行总结，并对本课题的下一步工作 和未来发展进行展望。 第2 牵数据挖掘和视频分类技术 第2 章数据挖掘和视频分类技术 2 1 数据挖掘技术概述 随着数据库容量的膨胀，人们面临的问题不再是缺乏足够的信息可用，而是 面对瀚海的数据海洋，难以找到所需的信息。面对“丰富的数据，贫乏的知识 这一挑战，数据挖掘和知识发现技术应运而生。数据挖掘就是从大量的、不完全 的、有噪声的、随机的实际数据中，提取隐藏在其中的、人们事先不知道的、但 又潜在有用的信息和知识的过程。 数据是指有关事实的集合，记录和事物有关的原始信息；模式是一个用语言 来表示的一个表达式，可用来描述数据集的某个子集；知识是对数据包含的信息 更抽象的描述。原始数据可以是结构化的，如关系数据库中的数据：也可以是半 结构化的，如文本、图像甚至是分布在网络上的异构型数据。 本章将介绍数据挖掘的一般过程和功能、视频数据挖掘的内容和体系、以及 基于内容的视频分类常用分类器和方法比较。 2 1 1 数据挖掘的过程 数据挖掘过程可粗略地分为数据清理、数据集成、数据选择、数据变换、数 据挖掘、模式评估和知识表示等几个步骤，如图2 1 所示【1 9 l 。 1 数据清理( 消除噪声和不一致数据) 2 数据集成( 多种数据源可以组合在一起) 3 数据选择( 从数据库中提取与分析任务相关的数据) 4 数据变换( 数据变换或统一成合适挖掘的形式，如通过汇总或聚集操作) 5 数据挖掘( 基本步骤，使用智能方法提取数据模式) 6 模式评估( 根据某种兴趣度度量，识别表示知识的人们感兴趣的模式) 7 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 步骤1 4 是数据预处理的不同形式，为挖掘准备数据。数据挖掘步骤可能与 用户或知识库交互。有趣的模式提供给用户，或作为新的知识存放在知识库中。 典型的数据挖掘系统具有以下主要部分，见图2 2 【1 9 l 。 兰圣! 些至兰! 茎堡三茎堡耋三 一? 。i 匦 。，。 “、 。圄 l 镕e 月 * 目5 囝景 图2 - 2 热型的数据挖掘系统结构 f i g u r e 2 - 2t v p i c a l f r a m e w o o f d a h m i n i n gs y s t e m 第2 章敷据挖掘视频分类技术 212 数据挖掘的任务 通常，数据挖掘任务分为两大类：预攫4 任务和描述任务口。描述任务的目 标是导出并概括数据中潜在联系的模式f 相关、趋势、聚类、轨迹和异常) 。本质 上，描述性数据挖掘任务通常是探查性的。并且常常需要后处理技术验证和解释 结果。预测任务的目标是根据其它属性的值，预测特定属性的值。被预测的属性 一般称为目标变量( t a r g e tv a r i a b l e ) 或因变量( d e p e n d e n tv a r i a b l e ) ，而用来做预测的 属性称为说明变量( e x p l a n a t o r yv a r i a b l e ) 或自变量( i n d e p e n d e n tv a r i a b l e ) 。图2 3 展 示了四种主要数据 ：玉 挖掘任务，包括聚类分析、关联分析、异常检测和预测建模 同。 图2 - 3 四种主要数据挖掘任务 f i g u r e 2 - 3f o u r m a i nk i n d s o f d a t a m i n i n g t a s k s 其中，预测建模用于以说明变量函数的方式为目标变量建立模型。预测检测 任务包括两种：回归( r e g r e s s i o n ) ，用于预测连续的目标变量；分类( c l a s s i f i c a t i o n ) ， 用于预测离散的目标变量。分类是数据挖掘的重要任务之一，数据分类是根据一 个分类模型，在数据库中的对象集合中找到一些共同的属性并把它们分成不同 类型的过程。其目的在于根据历史数据自动创建能预测未来行为的分类规则。在 分类问题中，待产生的类别的数目是事先知道的，而且训练数据中同时包含有属 性数据和类别表示数据。 本文采用数据挖掘技术构建视频镜头分类模型，以完成视频镜头分类任务。 21 3 数据挖掘分类方法和评估 目前，已有的数据挖掘分类方法主要有统计方法、决策树分类法、神经网络 北京t 业大学工学硕 二学位论文 方法、遗传算法、支撑向量机分类 2 1 i 。统计方法一般包括回归分析和贝叶斯分 类法。另外，还有一些其它的分类方法，包括卜最近邻分类、模糊逻辑和粗糙 集方法等。与决策树、神经网络和贝叶斯分类相比，这些方法在数据挖掘系统中 较少应用于分类，像粗糙集分类方法还处于原型阶段。 对于不同的数据类型和应用领域，每种方法都有其优缺点，没有一种分类算 法对所有的数据类型和应用领域都优于其他分类算法。一般可以从以下几个方面 评估分类算法：( 1 ) 预测准确率，由算法生成的分类模型对新数据的预测能力； ( 2 ) 速度，包括创建模型的速度和使用模型的速度；( 3 ) 健壮性，指给定噪声数 据或空缺值的数据，模型正确预测的能力：( 4 ) 伸缩性，给定大量数据，有效地 构造模型的能力；( 5 ) 可解释性，用户对算法产生的分类模式的可理解程度。 2 2 视频数据挖掘 传统的数据挖掘技术面对的是以结构化数据为主的关系数据库、事物数据库 和数据仓库。随着数据处理工具、先进的数据库技术以及w w w ( w o r l dw i d ew e b ) 技术的迅速发展，大量的形式各异的复杂类型的数据，如非结构化数据、超文本 与多媒体类型的数据不断涌现。 视频数据挖掘是多媒体数据挖掘的一个重要组成部分，属于复杂类型的数据 挖掘。视频数据挖掘与其他数据挖掘的重要区别是，视频挖掘过程是随视频数据 流的自适应处理，要求挖掘算法尽量不对视频数据作假设要求，但是又确实能挖 掘到确凿、有用的视频特征、语义信息、模式和知识。 2 2 1 视频数据挖掘内容 一般视频数据挖掘的内容包含4 类：视频分割、视频分类、视频索引和摘要 以及视频检索【r ，1 。 视频分割( v i d e os e g m e n t a t i o n ) 是进行多种视频应用的前提。其目标是将视频 流划分为一套有意义的且可管理的片段( 一般是镜头) ，以作为视频索引的基本元 素，所以视频分割又被称为自动镜头边界检测【2 2 1 。在镜头检测中还要识别出镜 头间切换方式。每一个镜头可用选择出的关键帧来表示，并通过提取空间和时间 特征进行索引。视频分割是后续视频分析的基础，具有十分重要的位置。 视频分类( v i d e oc l a s s i f i c a t i o n ) 就是根据视频表现内容的不同，将它们划分到 实现预定义的类别中。它是许多视频应用的基础，比如视频数据库、数字图书馆、 视频点播等。最早的视频分类是由人工进行的，由观看者根据他们的主观意识对 视频进行捅述，然后基于这些描述对视频进行分类，和传统的基于关键字的数据 库技术相似。它们与观众的主观认识密切相连，受人为影响大，因而不够精确。 第2 章数据挖掘和视频分类技术 为了客观反映视频的视觉内容，人们提出了基于视频内容的分类方法( c b v c ， c o n t e n t b a s e dv i d e oc l a s s i f i c a t i o n ) 。 视频索引( v i d e oi n d e x i n g ) 就是为视频附加上基于内容的标签的过程，它对基 于内容的视频存取、浏览和检索是很有必要的。视频摘要( v i d e o a b s t r a c t i n g ) 就是 从原始视频抽取出来、比原始视频更短、能够反映原始视频的精华内容的一系列 帧或运动图像，它们主要用于视频浏览、多媒体文档管理、电影营销、数字电视 杂志、家庭娱乐等方面，具有很重要的应用价值。 视频检索( v i d e or e t r i e v a l ) 就是在大量的视频数据中找出所需要的视频片段。 其方法是用查询视频的特征向量与已提取出并保存在视频数据库中已经索引过 的视频的特征向量相比较。在视频数据索引的基础上就可以进行基于内容的视频 检索( c b v r ，c o n t e n t b a s e dv i d e or e t r i e v a l ) 。视频检索有广泛的用途，包括气象 预报、t v 制作、针对视频的w e b 搜索引擎以及电子商务等。 本文主要对的视频分割和视频分类两部分内容进行阐述，在后续内容中将对 视频分割方法和实现视频分类的过程进行详细的介绍。 2 2 2 视频数据挖掘体系 视频数据挖掘体系一般包括视频数据预处理、视频数据多维分析和视频挖掘 等几个模块。各模块功能如下： ( 1 ) 视频数据预处理 将视频数据分成物理上的镜头单元是特征提取的第一步。镜头分割主要是根 据视频帧的物理特性，如颜色、纹理等，判断镜头边界。在镜头分割的基础上， 提取关键帧，一些静态的特性可以直接从关键帧中提取。 ( 2 ) 视频数据的多维分析 视频数据库的知识包括原始的视频数据，自动提取特征的规范描述以及人工 输入的特征，还有视频的领域知识和通用知识，并且可以不断更新。若将其中的 每一个知识属性作为一个维度，维数过多，模型构建过于复杂。可根据实际需要 选取高效、实用的视频多维数据。 ( 3 ) 在数据多维分析的基础上，采取一些数据挖掘的方法能发现隐含在视频 数据中的有用信息和模式。 2 3 基于内容的视频分类方法 基于内容的视频分类方法是根据视频的语义内容将其分到不同的类别，视频 分类方法总体上可以被分为两类：基于规则的方法和基于统计学习的方法。基于 规则的方法需要使用到领域知识来检测视频片段的语义概念，这种方法广泛应用 北京t 业大学工学硕：l 学位论文 于一些专门的领域。z h a n g 等人利用基于规则的方法来识别新闻视频b 3 1 。这种方 法需要建立规则库，需要为每一条规则确定一个可信度因数，构建完整的知识库 是非常必要的。另外，只利用了人类预知的规则，在不同的视频模型中隐含的规 则会被忽略。所谓统计学习的方法就是通过使用统计模型和分类器对已有标注的 视频进行学习，然后再进行视频的分类。这种方法对于明显的和隐含的视频特征 规则都可以进行挖掘。 在视频分类研究中，一个很重要的问题就是分类器的选择。现有的视频分类 分类器主要包括：贝叶斯分类器、神经网络、支撑向量机( s v m ) 、决策树( d e c i s i o n t r e e ) 、高斯混合模型( g m m s ) 和隐马尔科夫模型( h m m s ) 【4 ，5 ，9 ，1 2 ，2 4 3 6 1 。因篇幅有限， 本文主要介绍了与本文工作直接相关s v m 和决策树两种分类器。 2 3 1s v m 分类 支撑向量机, ( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是v a p n 像根据统计学习理论提出 的一种新的学习方法，适合小样本分类问题【3 5 】。s v m 建立在计算学习理论的结 构风险最小化的原则之上，可以提高学习机的泛化能力。 图2 4 给出了最优分类面的示意图，图中实心点和空心点分别表示两类训练 样本，h 是分类线，h l ，h 2 分别表示各类中离分类线最近的样本且平行于分类 线h 的超直线，它们之间的距离称为分类间隔( m a r g i n ) 。当h 满足最优分类超平 面的条件时，h 就是最优分类超平面，凰，胁上的点称为支撑向量，因为它们 支撑了最优分类面。 喝 o o 图2 - 4 线性两类划分最优超平面 f i g u r e2 - 4o p t i m a lh y p e r p l a n eo fal i n e a r l ys e p a r a b l et w oc l a s sp r o b l e m 支撑向量机的基本思想是：通过内积函数( 也称核函数) 定义的非线性变换输 入向量变换到一个高维特征空间，然后在高维特征空间空间中构造最优分类超平 面。其原理结构如图2 5 所示，它类似于一个神经网络，其输入向量是 第2 章数据挖掘和视频分类技术 x = ( 五，x ：，_ ) ：每一个中间层节点对应于属于样本与一个支撑向量的内积；输 出是若干个中间层节点的线性组合【3 5 】。 2 3 2 决策树分类 图2 - 5s v m 示意图 f i g u r e2 - 5m o d e lo fs v m y 决策树( d e c i s i o nt r e e ) 技术是用于分类和预测的主要技术。决策树方法是利 用信息论中的信息增益寻找示例数据库中具有最大信息量的属性字段，建立决策 树的一个节点，再根据该属性字段的不同取值建立树的分枝；在每个分枝集中重 复建立树的下一个节点和分枝的过程。它是一种树结构，如图2 6 所示，其中每 个内部节点( i n t e r n a ln o d e ) 代表对每个属性的一次测试，分枝边代表一个测试结 果，叶子( l e a o 代表某个类( c l a s s ) 或者类的分布( c l a s sd i s t r i b u t i o n ) ，最上边的节 点是根节点。对一个未知的样本进行分类，用样本的属性值在决策树上进行测试， 从根到叶子节点之间就会形成一个决策路径。 图2 - 6 决策树分类模型示意图 f i g u r e2 - 6 i l l u s t r a t i o no fad e c i s i o nt r e e 北京t 业大学工学硕士学