（计算机应用技术专业论文）基于内容的视频检索关键技术研究.pdf

摘要 数字视频属于国家重点发展的信息产业领域，随着宽带网络和数字电视的迅 速发展，视频点播、交互电视、视频网站等应用需求将越来越广泛，这些应用将 最终导致大量数字视频数据急剧增加。但时，我们知道数字视频数据的非结构化， 使得现有及将来产生的大量的数字视频无法利用，大量的有价值的数据只能成为 毫无意义的积累，因此研究如何利用视频数据，如何提高视频数据的利用率具有 十分重要的意义。 基于内容的视频检索是当前多媒体领域的研究热点，它综合了数字图像处 理、数字视频处理、多媒体技术、数据库技术等多学科领域，使用视频图像的底 层的、本质的特征作为检索的依据，克服了传统的基于属性或文本检索方式的不 足。论文针对基于内容的视频检索的关键技术展开研究，深入分析与研究了视频 镜头分割技术、关键帧提取技术、特征描述与存储组织及检索系统结构等一系列 重要问题，取得了卓有成效的成果。 在视频镜头分割方面，提出了一种高效的基于i 帧的镜头分割算法，一方面 大大压缩了视频处理的数据量，另一方面，克服了传统的解压缩域中的一些复杂 的运算，从而大幅度提高了镜头分割的效率。 在关键帧提取方面，提出了一种基于i 帧和r s 理论的关键帧提取算法，一方 面，首创性的将r s 理论引入到视频分析，另一方面，利用rs 理论的属性约减理 论，得到真正意义上的关键帧。 讨论与分析了视频数据的存储与组织技术，结合理论研究与制定了本课题所 用的视频训练库与视频测试库的存储组织问题。 根据论文的研究成果，设计并实现了一套视频检索系统体系结构，该结构在 实现常规的属性或文体检索功能的同时，可同时实现基于内容的视频检索。 关键词：镜头关键帧存储组织基于内容视频检索 a b s t r a c t d i g i t a lv i d e ob e l o n g st ot h ef i e l do fi n f o r m a t i o ni n d u s t r yw h i c ht h e c o u n t r yd e v e l o p ss p e c i a l l y w i t ht h er a p i dp r o g r e s so fb r o a d b a n dn e t w o r k a n dd i g i t a lt v ，t h ea p p l i c a t i o n so fv i d e o o n d e m a n d ，i n t e r a c t i v et va n d v i d e ow e b s i t eb e c o m em o r ea n dm e r ep o p u l a r a l lo ft h e s ea p p l i c a t i o n sa r e f a c i n gt h ee m e r g i n gd i g i t a l i z e dv i d e od a t ai nal a r g ea m o u n t b u ta sw e a 1 1k n o w ，v i d e oi n f o r m a t i o ni sn o n s t r u c t u r a l ，w h i c hm a k e s v i d e oi s d i f f i c u l tt ou s e s t u d yt h es u b j e c to fh o wt om a k eu s eo fv i d e od a t a ，a n d h o wt oe n h a n c et h er a t eo fu s i n gv i d e od a t ai sv e r yi m p o r t a n t c o n t e n t b a s e dv i d e or e t r i e v a l ( c b v r ) i sn o war e s e a r c h “h o t s p o t ”i n m u l t i m e d i ad i s c i p l i n e i ti n t e g r a t e st h ec o n t e n to fd i g i t a li m a g e p r o c e s s i n g ，d i g i t a lv i d e op r o c e s s i n g ，m u l t i m e d i at e c h n i q u e ，d a t a t ，a s e t e c h n i q u ee t c c b v ru s e st h ev i d e of e a t u r e sa sar e t r i e v a lc o n d i t i o nt o o v e r c o m et h es h o r t c o m i n g so ft r a d i t i o n a lr e t r i e v a lm e t h o d sb a s e do n a t t r i b u t e s i nt h i st h e s i s ，t h ea u t h o ra i ma tt h es t u d yo fk e yt e c h n i q u e o fv i d e or e t r i e v a l ，d e e p l ya n a l y z et h et e c h n i q u eo fs h o ts e g m e n t ，k e yf r a m e e x t r a c t i n g ，s t o r a g e ，a n ds oo n ，r e c e i v e das e to fe f f e c t i v er e s u l t i nt h ea s p e c to fs h o ts e g m e n t ，an e wa l g o r i t h mi so f f e r e db a s e do n if r a n l e b e c a u s et h ea l g o r i t h mb a s e do nif r a m e t h ed a t ao ft h ev i d e o d a t ai sr e d u c e dg r e a t l y ，a n di to v e r c o m es o m ec o m p l e xo p e r a t i o ni n c o m p r e s s i o nf i e l d ，s oi ta d v a n c e dt h ea v a i l a b l eo ft h ea l g o r i t b m i nt h ea s p e c to fk e yf r a m ee x t r a c t i n g ，an e wa l g o r i t h mi so f f e r e db a s e d o nif r a m ea n dr s t h et h e s i sa p p l yt h er st h e o r yi n t ok e yf r a m ee x t r a c t i n g a tt h ef i r s tt i m e ，a n dm a k eu s eo ft h et h e o r yo fa t t r i b u t er e d u c t i o ni n r s t h et h e s i sd i s c u s s e sa n da n a l y s e st h es t o r a g ea n do r g a n i z a t i o no ft h e v i d e od a t a i nt e r mo ft h et h e o r y ，t h et h e s i ss t u d i e dt h es t o r a g eo ft h i s p a p e ro fv i d e ot r a i n i n g1 i b r a r ya n dv i d e ot e s t1 i b r a r y b a s e do nt h ea b o v et h e o r y ，t h et h e s i sd e s i g n sas i m p l ev i d e or e t r i e v a l s y s t e ma r c h i t e c t u r e ，t h i ss y s t e mn o to n l yr e a l i z et h ev i d e or e t r i e v eb y - t e x ta t t r i b u t ei nt r a d i t i o n ，b u ta l s oc a nr e a l i z et h ev i d e or e t r i e v a l b a s e do nc o n t e n t k e yw o r d ：s h o tk e yf r a m es t o r a g e c o n t e n t b a s ev i d e or e t r i e v a l i v 图目录 图2 1 数据挖掘体系结构图9 图2 2 以信息增益为启发信息构造的判定树1 l 图2 3 后向传播多层前馈网络原理图1 2 图2 4 原始图像2 l 图2 5 频率系数分布2 l 图2 6 恢复图像2 1 图2 7 粗糙集边界图2 5 图3 1 图像的数字化过程3 0 图3 2 视频检索体系结构图3 0 图4 1 镜头分割界面( 1 ) 4 9 图4 2 镜头分割界面( 2 ) 4 6 图4 3 镜头分割界面( 3 ) 4 6 图4 4 镜头分割界面( 4 ) 4 6 图4 5 镜头分割界面( 5 ) 4 7 图5 1 关键帧检索图部分界面5 4 图6 1 颜色直方图( 1 ) 5 8 图6 2 颜色直方图( 2 ) 5 8 图6 3 纹理( 1 ) 5 9 图6 4 纹理( 2 ) 5 9 图6 5 纹理( 3 ) 6 0 图6 6 纹理( 4 ) 6 0 图6 7 典型轮廓图6 0 图6 8 基于内容的视频检索功能模块及实现架构6 2 表目录 表2 1 典型二元变量表1 3 表2 2 信息系统模型表2 6 表4 1 镜头分割实验结果表4 5 表5 1 关键帧提取实验结果表5 4 表5 2 关键帧提取性能评价结果表5 4 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包括其他人已经发表或撰写过的研究成果，也不包含为 获得西北师范大学或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 第一章：绪论 本章简要介绍了课题的研究背景与意义、课题的国内外研究情况以及本论文的 组织安排。 1 1 研究背景与意义 1 1 1 课题的研究背景 随着电子化、信息化进程的不断发展，导致视频数据每时每刻都在急剧增加。 如电子图书馆的视频资料、电视台的节目、视频点播、监控录像资料等等，其主要 原因可总结为三个方面。第一，视频采集设备和采集方法得到迸一步的提高，使得 人们通过视频表达和记录信息成为可能。第二，数字化视频有其特有的优点，如采 集存取容易、可方便地在网络中传输且抗噪声等，给人们的使用带来了极大的方便。 第三，视频数据生动形象，能够携带大量的信息，而且这些信息易于被人感知。如 一帧视频所蕴藏的信息需要几页，甚至几十页的文字来描述，甚者有些图像或视频 的内容就很难用文字来表达，百闻不如一见就是很好的佐证。 目前对大量的视频数据无法利用或利用率不高。目前对视频的利用集中体现在 视频检索，而目前普遍采用的方法是与视频本身无关的人工标注的方法，如对视频 进行内容、标题、作者、时间等的标注，然后以文本的方法进行检索这种方法主 观性很强，没有反映视频的本质特征，而且面对海量数据，这种人工标注的方法显 然可行度很小。 鉴于以上背景，我们必须建立一种有效的机制来组织、管理和访问它们，才能 使用户能够快速检索到自己所需的视频信息。才能更好的对我们得到的视频数据进 行分析、利用和再利用。我们希望计算机能自动处理枯燥冗长的监视录像，发现其 中的异常，从而省去大量的人力劳动我们也希望同学们在电子图书馆能随心所欲 地检索自己需要的视频资料，基至让计算机能自动找出海量视频中的一些隐含的、 人难以发现的信息与相互之间的关联。正是基于以上需求，视频检索和视频数据挖 掘技术应运而生 西北师范大学硕士学位论文 第一章绪论 1 i 2 课题的研究意义： 研究基于内容的视频检索可以解决视频搜索和资源发现问题，在以下领域中得 到广泛应用： 1 电子图书馆、艺术博物馆、网络多媒体搜索引擎、交互电视、远程教育、远 程购物、多媒体编辑等。 2 医学分析、远程医疗系统，特别对远程会诊，基于内容的视频查询可提高效 率并节省大量的费用 3 专利检索、商标注册管理。 4 公安、安全监视系统。 5 地图地理信息系统、地理事件分析。 6 军事侦察作战等应用 7 视频点播 8 家庭视频娱乐 研究基于内容的视频检索可以发现隐含的、有价值的、可理解的视频模式，得 到视频表示的趋向和关联，改善视频信息使用的智能化程度。 1 2 国内外研究情况 视频检索技术为近年来发展起来的一门新兴的交叉科学，具有涉及面广、内容 丰富、跨行业、跨学科的特点。从研究它的方法来看，它与数学、物理学、生理学、 心理学、电子学、计算机科学可以相互借鉴；从研究的范围来看，它与人工智能、 神经网络、遗传算法、模糊逻辑等理论和技术都密切相关。目前对视频检索的研究 现状可总结为以下3 个方面： 1 2 1 研究领域宏观综述 发展迅速：视频检索自1 0 年前正式命名以来，得到国内外信息领域科技人员的 广泛重视，也得到国际学术组织的关注，迅速成为多媒体数据库中研究的热点之一。 在国际上每年召开的许多有关多媒休技术的学术大会中，有许多重要的系列会议都 西北师范大学硕士学位论文第一章绪论 开启了视频信息检索主题和分会，而i e e e 和s p i e 也组织了专门的多媒体信息检索会 议，这些极大推动了视频信息检索的发展。 成果丰富：经过国内外信息领域科技人员1 0 年的深入研究，基于内容的视频检 索研究和应用己取得长足的发展，己有大量理论研究和技术应用研究的论文发表。 许多国际刊物也组织了有关基于内容视频信息检索的专集。国内外也不断有相关的 综述文章发表。 仍有问题：基于内容的视频检索是一个挑战性的课题，涉及很多领域，需要解 决很多前所未有的问题，包括从获取和表达原始数据的方法，到对这些数据和信息 的处理、分析和理解。故还需要广大科研人员的不断努力 1 2 2 研究领域内容综述 视频标注：视频标注是通过人工的方式将某一段视频进行主观的属性标注。然后 以文本的方法进行检索。视频标注技术己相当成熟，但有其固有的不足，第一，要 人工手动完成，工作量极大。第二，主观性很强，不同的人对同一段视频有不同的 理解，必然导致不同的标注结果。 视频摘要：视频摘要以自动或半自动的方式，从原视频中提取有意义的部分，将 它们合并而成的紧凑的、能充分表现视频语义内容的视频概要。视频摘要技术也有 一定的发展，同时给基于内容的视频检索提供了思路，但与真正的基于内容的视频 检索有一定的距离。 基于非压缩域的视频内容检索：基于非压缩域的视频内容检索是以视频的低层 特征为基础进行分析，特征提取等，最后以视频的本质特征为检索依据，完全实现检 索的自动化。基于非压缩域的视频内容检索己有相当的研究成果，但由于其所有算 法均要在完全解压的基础上进行，而视频数据不但数据量很大，而且运算量也很大， 所以在具体实现时并不理想 基于压缩域的视频内容检索：基于压缩域的视频内容检索是在不完全解压或不 解压的前提下以视频流的低层特征为基础进行分析、特征提取等，最后以视频的本质 特征为检索依据，完全实现检索的自动化。由于基于压缩域的视频内容检索在没有解 压或没有完全解压的前提下进行，所以其优点是：第一，大大减小了数据量，第二， 减少了数据运算量，从而大大提高了系统的效率。本文主要研究摹于压缩域的视频 西北师范大学硕士学位论文第一章绪论 内容检索。 1 2 3 研究领域技术综述 基于内容的视频检索关键技术主要有三部分：第一部分为镜头分割，第二部分 为关键帧提取，第三部分为基于特征的视频索引与存储组织。镜头分割的主要思想 为依据两帧图像的特征值的差值与给定阈值进行比较，如果差值大于给定的阙值， 说明两帧的特征变化较大，可以认为两帧为不同的主题，在此两帧之间进行镜头分 割；如果差值小于给定的闽值，则说明两帧的特征变化较小，可以认为两帧为同一 主题，可以继续进行下两帧的比较。除此之外，还有基于以上思想的改进，如可以 进行设定两个阈值进行渐变检测。关于关键帧提取目前较为成熟和可行的思想较为 少见。大都为人工设定、指定关键帧或采用候选关键帧的方法。如可以指定第一帧 或任意选取一帧为关键帧。现有较为合理的一种思想为候选关键帧法，即首先选择 第帧、中闻帧和最后一帧为候选关键帧。然后比较第一帧与中间帧的特征值、中 间帧和最后一帧的特征值，如果两者的差值均大于给定的阈值，则说明两两之间的 差别均较大，所以必须选择三帧为关键帧，如果两者之间的任意一方大于给定阈值， 则选则此两帧为关键帧，否则选择任意一帧为关键帧。基于特征的视频索引与存储 组织目前较多使用树型结构进行组织。本文的视频存储组织也是采用了这种方式。 i 3 现有系统简介 c b v r 技术从提出到现在，在国内外已经取得了许多成就，现在已经有许多原型 系统，其中最为著名的有i b m 公司的q b i c 系统，哥伦比亚大学开发的v i s u a l s e e k 系统 以及v i r a g e 公司开发的v i r a g e 系统等等。除此以外，还有许多原型系统如 u i u c ( u n i v e r s i t yo f1 1 l i n o i sa tu r b a n a - c h a m p a i g n ) 的m a r s ( m u l t i m e d i aa n a l y s i s a n d r e t r i e v a ls y s t e m ) ，m i t 媒体实验室开发的p h o t o b o o k 等等也是其中的优秀代 表。值得一提的是，国内清华大学研制的i n t e r n e t 上静态图像的基于内容检索系统 也具备了相当的水准。 西北师范大学硕士学位论文第一章绪论 1 q b i c q b i c ( q u e r yb yi m a g ec o n t e n t ) ，该图像检索系统是i b m 公司9 0 年代开发的图 像和视频检索系统，主要为其d b 2 大型关系型数据库管理系统提供图像检索功能，并 支持基于网络的图像检索服务。这是一个标准的基于内容的检索系统，用户只需输 入以图像形式表达的检索要求即可检索出一系列相似的图像甚至视频。它提供多个 图像数据库供检索，例如旧金山美术博物馆图像数据库、法国文化部图像数据库、 可视化图书馆等。 q b i c 提供了多种查询方式，用户可以利用系统自身提供的标准范图检索，也可 以绘制简图或通过扫描输入图像进行检索，还可以输入视频镜头和前景中运动的对 象检索。当用户输入图像、简图或视频完成后，o b i c 对输入对象的色彩、纹理、运 动变化等特征进行分析，再根据用户所选择的不同查询方式实施不同的处理。同一 图像采用不同的检索方式完全有可能得到大相径庭的结果，这是由于不同的检索方 法依赖于不同的特征提取与分析模式的原因。系统也提供了标准的范图用以代表 不同的颜色、纹理、形状等等。用户可选择与要检索对象最接近的范图，以它作为 标准来检索相似的图像。事实上，这些标准范图是事先抽取特征信息并存储于特征 索引库中的图像。 q b i c 系统分为两部分：特征提取和数据库查询，前者负责对系统存储的图像进行 多种特征抽取和维护特征索引库，后者负责对用户查询输入的图像进行同样的特征 抽取并把特征信息输入匹配引擎，检索出具有相似特征的图像。 2 v i s u a l s e e k v i s u a l s e e k 是一个面向因特网的图像和视频检索系统，它提供了一系列搜寻和 检索因特网视频和图像信息的工具，其技术内核是一种基于内容的检索机制。整个 系统结构由三部分构成，用户接口、网络与通信处理和服务器程序用户接口是一 个激活了j a v a 功能的网络浏览器，它能够解释j a v a 程序，连接网络地址，显示网页 并且可以存储j p e g 图像。用户与服务器之间的通信完全通过h t t p 协议进行，服务器 端通过公共网关接口( c o m m o ng a t e w a yi n t e r f a c ec g i ) 执行相关程序，用户的查询 请求作为c g i 网络地址参数的一部分通过浏览器的v i s u a l s e e kj a v a 程序提交，服务 西北师范大学硕士学位论文第一章绪论 器接收到查询请求后经过处理，将查询结果按照文本、图像、视频的不同分别以h t m l ， j p f 粥, ，m p e g 等格式返回给用户。 3 清华大学w e b 上基于内容的图像检索系统 清华大学计算机科学与技术系1 9 9 7 年研制了一个i n t e r n e t 环境下基于内容的静 态图像检索系统原型。系统能在i n t e r n e t i n t r a n e t 环境下，通过友好的人机界面， 以颜色、纹理等图像特征或样本图像检索数据库中的图像。目前系统针对1 2 0 0 0 张景 物照片提取了图像的高维特征并建立了索引，它采用j a v a 语言实现人机交互模块， 通过浏览器为检索用户提供友好的界面，从浏览器端发出的检索请求被转换为系统 自身的检索表达式，提交给检索引擎进行处理，表现出了较好的性能。 检索相关模块是指用户检索时用到的程序和文件。包括q u e r y c g i 程序、 o u e r y s e r v e r 程序、初始配置文件和一些界面相关文件。在检索时，用户在本地浏览 器上通过h t t ps e r v e r 访问q u e l y c g i ，并提交捡索请求。q u e r y c g i 为一个c g i 程序， 通过c g i 接口与h t t ps e r v e 通信，它负责提供检索界面，接受用户的检索请求，将检 索请求传送给o u e r y s e r v e r 程序并将o u e r y s e r v e r 程序返回的检索结果以可视的形式 ( 图像的图标或图像本身) 传给用户。q u e r y s e r v e r 程序是一个“精灵”( d a e m o n ) 程序， 绑定于指定端口上，接受o u e r y c g i 传来的检索请求，检索相应的索引文件，处理后 返回检索结果。界面相关文件是一些与检索界面有关的文件，如构成检索界面的 j a v a c l a s s 文件、利用模板提供特征时的模板特征文件等：初始配置文件则是提供 q u e r y s e r v e r 参数的文件，这些参数包括绑定的端口、各特征对应的索引文件名等等， 供q u e r y s e r v e r 启动时初始化使用。 建库相关模块用来建立和维护整个图像库及相关文件，主要包括特征提取和索 引生成两部分。特征提取模块用来对图像库中的图像完成特征的提取，并生成相应 的特征文件；而索引生成模块则用来对得到的特征文件进行处理，根据相似索引 ( s i m i l a r i t y i n d e x i n g ) 的原理生成相应的特征索引树和特征索引文件，供检索时使 用。此外，建库相关模块还包括一些维护图像库( 如完成图像格式转换，生成图标) 的工具。 西北师范大学硕士学位论文第一章绪论 1 4 论文的内容安排 本论文由以下几部分组成： 第一章主要阐述了本课题的研究背景、目前的研究现状，领域的动态及本课题 研究的主要内容。并概述了本论文的构成。 第二章介绍了本课题的基本理论基础和基本方法，分别介绍了数据挖掘技术、 视频数据挖掘基本概念、视频数据库管理系统和粗糙集理论等相关理论。 第三章较为详细的分析与讨论了基于内容的视频检索的基本架构，并对其中的 关键技术进行了分析与讨论。 第四章对基于内容的视频检索中的关键技术镜头识别进行了详细的分析与 研究。并提出了一种高效的基于i 帧的镜头分割算法。 第五章对基于内容的视频检索中的关键技术之二一关键帧提取进行了详细的 分析与研究。并提出了一种高效的基于i 帧和r s 理论的关键帧提取算法 第六章对基于内容的视频检索中的关键技术一视频的存储组织与视频检索系 统架构进行了详细的分析研究。给出了基于内容的视频检索功能模块架构。 第七章对今后的研究工作与研究热点进行了说明。 本文最后对给予指导、帮助的各位老师，同学进行答谢，并介绍了在本研究中 所参考的有关文献、在本研究中发表的有关文章和参与的相关项目。 1 5 本章小结 本章是论文的绪论部分，主要完成了以下工作： 1 简要分析了论文的研究背景与意义 2 较为详细的分析了论文国内外研究现状 3 较为详细的介绍了国内外现有视频检索系统 4 对论文的整体结构进行了安排 第二章：相关概念、技术与理论 本章对研究基于内容的视频检索系统中所涉及的基本技术与相关理论进行了介 绍，包括数据挖掘技术、视频数据挖掘技术、o c t 变换、小波变换及r s 理论。 2 1 数据挖掘技术相关理论 2 1 1 数据挖掘概述 数据挖掘是近年来兴起的一门新的学科，虽然历史较短，但发展速度极快。因 为它结合了数据库、人工智能、数理统计等多学科的综合产物，给它下一个统一、 完整、准确的定义并非容易。目前许多专家试图对它给过精确定义，但均依据它的 某个方面，例如： s a s 研究所( 1 9 9 7 ) ：“在大量相关数据基础之上进行数据探索和建立相关模型的 先进方法”。 b h a v a n i ( 1 9 9 9 ) ：“使用模式识别技术、统计和数学技术，在大量的数据中发现 有意义的新关系、模式和趋势的过程” h a n de ta 1 ( 2 0 0 0 ) ：“数据挖掘就是在大型数据库中寻找有意义、有价值信息 的过程”。我们认为：数据挖掘就是从海量的数据中挖掘出潜在的、有价值的知识的 过程。这些知识对企业与部门的管理者来说是非常有价值的信息，支持企业决策， 可以为企业带来巨大的经济效益。 海量数据的来源主要有两个方面，一方面是人们积累的操作型数据库，包括关 系数据库、事务数据库、高级数据库和高级数据库应用、文本数据库和多媒体数据 库、异种数据库和遗产数据库及w e b 数据库。这一数据来源随计算机硬件技术和数据 库软件技术的成熟在数据挖掘中占有的比重越来越大。另一方面，则是企业花了巨 资而建立的数据仓库( d w ) ，由于综合条件的限制，数据仓库在我国现阶段应用并非 广泛，原因是：一方面企业建立自己的数据仓库需花费相当数量的资金，一般企业 很难负担。另一方面，企业或部门的决策者还没有意识到建立数据仓库的重要性， 不愿意为之而付出高昂的代价。但随着社会的快速发展，数据仓库必然成为数据挖 直北师范大学硕七学位论文 第二章相关概念、技术与理论 掘的最重要的来源。一个典型宏观的数据挖掘体系结构图如下： 2 1 2 数据挖掘的作用 图2 1 数据挖掘体系结构图 数据挖掘被称为数据库中的知识发现在科技社会具有十分重要的作用。从宏观 来讲，数据挖掘可以：( 1 ) 发现大型数据库中的有趣模式。( 2 ) 根据用户的消费习惯 预测用户的消费行为。具体来说，数据挖掘能使：( 1 ) 客商从顾客购买商品中发现内 在的联系，提供打折购物券等提高销售额。( 2 ) 保险公司通过数据挖掘建立预测模 型，辨别出可能的欺诈行为、避免道德风险、减少成本、提高利润。( 3 ) 在制造业中， 半导体的生产和测试中都产生大量的数据。就必须对这些数据进行分析、找出存在 的问题、提高质量。( 4 ) 电子商务也逐渐升温，可以用数据挖掘对网站进彳亍分析、识 别用户的行为模式、保留客户、提供个性化服务、优化网站设计。总之，随着数据 库技术的发展，数据挖掘已成为一种必不可少的数据处理工具，没有这一强大工具， 大量的数据在高层决策者面前只能是“数据丰富而信息贪乏”。 2 1 3 数据挖掘的功能 数据挖掘功能是指数据挖掘任务中要找的模式类型，是数据挖掘研究的核心内 容。从数据分析的角度可以分为两类：描述式数据挖掘和预测式数据挖掘。描述式 数据挖掘以简洁概要的方式描述数据，并提供数据关系的一般性质。主要通过特征 化和区分实现预测式数据挖掘分析数据，建立一个或一组模型，并试图预测新数 据集的行为，主要有关联分析、分类与预测、聚类分析等。 1 概念描述：指产生数据的特征化和比较描述，当被描述的概念涉及对象或类 时，称概念描述为类描述。特征化与比较是实现概念描述的主要方法。特征化指提 西北师范丈学硕士学位论文 第二章相关概念、技术与理论 供给数据汇集的简洁汇总，通过面向属性的归纳删除属性或概化属性、聚集合并相 等的元组、累计对应的计数值、得到理想的规则，是数据挖掘中数据预处理的重要 策略。而比较提供两个或多个数据汇集的比较描述，通过数据收集、维相关分析、 同步概化、最后导出比较的表示。 2 关联规则：关联规则挖掘是数据研究的一个重要且最为活跃的领域，主要目 的是发现大量数据中项集之间有趣的关联。通常用a ；b 的蕴含式来表示，在数据挖 掘中用支持度与置信度作为有趣或相关的度量。 支持度s u p p o r t ：s u p p o r t ( a 4 b ) = p ( a u b ) 可信度c o n f i d e n c e ：c o n f i d e n c e ( a 4 b ) = p ( b 1 a ) ( 1 ) ( 2 ) 满足最小支持度阈值和最小置信度闽值的规则称为强规则，这些阈值一般由用 户或领域专家设定，且在设定过程中带有一定的经验性。 关联规则挖掘的实质是发现某种事件发生时其它事件也会发生的一种内在联 系，这样一种内在联系有时用推理逻辑很难解释，是基于一定的数理统计理论建立 起来的，但这种联系在现实中却有相当的内涵。例如：每天购买啤酒的人也有可能 购买香烟，比重有多大，可以通过关联的支持度和可信度来描述。关联规则挖掘算 法目前均以统计学为基础。a p r i o r i 算法及其改进是较为典型的一种，它使用一种称 为逐层搜索的迭代方法。用以下公式可计算项集的支持度计数。 c o n f l d e n c e ( a j 口) 。尸似i 研s u p p o r t _ c o u n t ( a u b )。 s u p p o r t c o u n t 似) ( 3 ) 3 分类与预测：数据库内容丰富，蕴藏大量信息，可以用来作出智能的商务决 策，这也是数据挖掘的一个重要方面。分类和预测是两种数据分析形式。可以用于 提取描述重要数据类的模型或预测未来的数据趋势。但是，分类是预测分类标号， 而预测则建立连续值函数模型。数据分类一般由两部分组成，第一步。建立一个模 型。描述预定的数据类集或概念集，通过分析由属性描述的数据库元组构造模型。 第二步，使用模型进行分类。分类只是在整个过程中非常重要的一步，实际完整的 分类过程由以下五步组成：( 1 ) 数据清理：旨在消除或减少数据噪声和处理空缺值。 ( 2 ) 相关分析：数据中许多属性可能与分类和预测任务不相关。此外，其他属性可能 是冗余的，因此，这一过程旨在消除学习过程中不相关的或冗余属性。( 3 ) 数据变换： 旨在将不规范数据或不适合分类的数据通过数据概化或数据规范化变成适宜分类的 西北师范大学硕士学位论文第二章相关概念、技术与理论 数据。( 4 ) 比较分类方法：对于提取的分类模型是否可行，要通过准确性、速度、强 壮性、伸缩性和可解释性的检验。( 5 ) 在经过以上步骤后，说明模型是可行的，就可 以利用提取的模型分类。现有数据挖掘对于分类算法主要依据各种理论建立分类模 型，具体表现在以下几个方面： ( i ) 基于数理统计的判定树归纳算法及其加强 判定树归纳分类是分类算法的基础，以自项向下递归方式各个击破构造判定树 为思想，使用基于以下公式的信息增益为启发信息： 忡：，崞n 1 0 9 z ( p n ( 4 ) 鼬。辜等吣 ) ( 5 ) j ( s l j , s 2 j , , s m j ) 一p j , l 。g z ( p q ) ( 6 ) 伽协似) - ，0 - ，：，s ) 一e ) ( 7 ) 一个典型的以信息增益为启发信息构造的判定树如下： ( 2 ) 基于贝叶斯定理的朴素贝叶斯分类及其变形。 p ( h l x ) 。锷产 以上公式为著名的贝叶斯定理公式，公式反映了对于给定的训练集，后验概率 西北师范大学硕士学位论文 第二章相关概念、技术与理论 p ( h l 通过训练集的p o ) 、p o ) 和p o l ) 可以计算，由t - p ( h i 工) 可以计算，则可 以利用训练集的p ( h i x ) 值预测未来，也就是可以对任意随机的未来数据进行分类。 判定树归纳的不足之一是采用贪心算法，在每一步均考虑局部最优，即假定各 个属性之间是相互独立的，但在实际中，这种关联是存在的，而贝叶斯定理恰能计 算出在一定条件下的概率，即从整体而不是从局部去考查两个属性之间的关系，故 在确定判定树的根节点以后，能够计算出在根结点条件下各属性对类别属性的概率 大小，以概率大者作为下一根节点。反复直到确定每个属性的类别为止。这样构造 出的判定树应较i d 3 算法科学 ( 3 ) 后向传播分类 后向传播分类是一种基于神经网络的学习方法神经网络是一组连接的输入、 输出单元，其中每个单元都与一个具体的权值相关，在学习阶段，通过调整神经网 络的权值使得能够预测样本的正确类标号。一个典型的后向传播多层前馈网络原理 图如下： 图2 3 后向传播多层网络原理图 每个点代表个神经元，任意两个神经元之间的连线代表加权连接，在上图中 用w 。w j k 来表示权值，用训练样本x = ( x 。x ：，) 输入输入层，经过长时间的训 练神经元之间的权值，直到产生一个稳定的网络，即权值相对稳定为止 西北师范大学硕士学位论文第二章相关概念、技术与理论 除以上方法外，基于案例的推理、遗传算法、粗糙集和模糊集方法等一些智能 算法也被人们逐渐采用。 4 聚类：指将物理或抽象对象的集合组成为由类似的对象组成的多个类的过 程。在同一类中的对象非常相近，而不同类中的对象有较大的不同。与分类不同的 是，聚类是无指导的学习过程，即没有提取模型这一过程。数据聚类正在蓬勃发展， 有贡献的研究领域包括数据挖掘、统计学、生物学及市场营销。现有聚类分析中基 本采用数据矩阵和相异度矩阵作为对象之闻相异性的量化表示，通常为一个非负数 值，而对于区间标度变量，常用的一种方法是用下列公式计算平均绝对偏差。 s f 。言- m ! z ，- m l | + + i - m id ( 9 ) 1 町。言“，+ j ：，+ + ) ( 1 0 ) 其中的x l ，工可是f 的n 个度量值，m f 是f 的平均值。 对于对称的和不对称的二元变量描述的对象间的相似度可以依下列公式计算简 单匹配系数和j a c c a r d 系数。 m ，) 。生 g 。r + s + t ( 1 1 ) d o ，) 旦 q + 7 - i - 5 ( 1 2 ) 其中，q 是对于对象i 和j 值都为1 的变量的数目，r 是对于i 值为1 而对象j 值为0 的变量的数目，s 是对于对象为0 而对于对象j 值为l 的变量的数目，t 是对于对象i 和j 值都为0 的变量的数目，变量总数为p 。 一种典型的二元变量表如下： 表2 1 典型二元变量表 基于以上理论的各种聚类方法已有相关成熟的算法，目前主要有：( 1 ) 基于划分 的方法( 2 ) 基于层次的方法( 3 ) 基于密度的方法( 4 ) 基于网格的方法( 5 ) 基于模型的方法。 西北师范大学硕士学位论文第二章相关概念、技术与理论 并且有了很好的应用。现在基于模糊集理论和租糙集理论的聚类算法或智能免疫算 法逐渐被人们所重视n 刀 需要注意的是，数据挖掘的各项功能不是独立存在的，在数据挖掘中有时各项 功能相互联系。共同发挥作用，才能构成较为完善的体系。 2 2 视频数据挖掘 2 2 1 视频数据挖掘概述 视频数据是一种特殊的数据，它以数据流的形式存在，是非结构化的。视频数 据生动形象，它能够携带大量的信息，并且这些信息易于被人感知。因此，一直以 来人们对视频数据有浓厚的兴趣。近年来，随着视频采集设备的普及和海量存储设 备价格的下降，可获得的视频数据正在迅速增加。大量的视频监视设备，例如交通、 银行的视频监视系统，每天都产生大量的视频数据；从互联网上我们能得到海量的 娱乐和体育视频；数字电视和网络电视使得电视节目更易于录像，并在计算机上播 放和处理。 面对大量的视频数据，我们希望建立一套行之有效的机制来管理和访问它们， 使用户能够快速检索到自己所需的视频信息。我们也希望计算机能够自动处理枯燥 冗长的监视录像，发现其中的异常，从而省去大量的人力劳动。甚至于能让计算机 能找出海量视频数据中的一些隐含的、人难以发觉的信息和相互关联。基于以上需 求。数据挖掘技术被引入到了视频数据处理领域。 数据挖掘是从海量数据中获取的有效的、新颖的、潜在的、有用的、最终可理 解的模式和过程类似的，我们定义视频数据挖掘为通过综合分析视频数据的视听 特性、时间结构、事件关系和语义信息。发现隐含的、有价值的、可理解的视频模 式，得出视频表示事件的趋向和关联，改善视频信息管理的智能化程度。但是。由 于视频数据的非结构性，传统的基于关系数据库和事务数据库的数据挖掘技术很难 直接应用到视频数据挖掘领域。视频数据挖掘的难点集中体现在视频数据和人能理 解的语义之间的鸿沟。传统的数据挖掘的对象一般是数值数据和文本，而对于视频 数据，计算机理解的难度显然要大得多。而且一般来说，视频数据处理的时间开销 也远远大于数值和文本数据。为了解决这些问题，人们提出了多种适合视频数据挖 西北师范大学硕士学位论文 第二章相关概念、技术与理论 掘的方法和技术。计算机视觉、数字图像处理等方面的技术和传统的数据挖掘技术 结合起来，被引入到视频挖掘领域。 总之，视频数据挖掘是利用数据挖掘的思想，引进一些其它的方法来解决视频 资源的检索与视频资源的定位，提取隐含于大量的视频数据中的潜在的、有用的智 能信息。 2 2 2 视频数据挖掘的分类 视频数据挖掘的研究开始于本世纪初，时间还较为短暂。作为数据挖掘中的一 个研究方向，其技术还并未成熟，也没有经典和公认的分类理论。在这部分中，我 们将从多个角度对视频数据挖掘的工作进行分类，以求对视频数据挖掘技术有较为 深刻的感性认识。 1 基于领域的分类 我们可以按照视频数据挖掘的目标所关联的领域来进行分类。按照这个标准， 我们可以把视频数据挖掘分成交通视频挖掘、医学视频挖掘、娱乐视频挖掘等。从 表面上看，这种分类没有太大的实际意义。但其实不然。某个领域通常有其固有的 特征，这些特征可能决定了视频挖掘的目的和手段。比如交通视频通常是监视视频， 它的画面背景通常是不变的，这个特征有助于简化挖掘过程。另外，体育娱乐视频 中挖掘关心的可能是场景语义( s c e n es e m a n t i c s ) ，比如射门、犯规等；而交通视 频中关心的可能是对象( o b j e c t ) 或对象的移动，比如超速的车辆等。故基于领域 的视频数据研究方法不仅可以大大降低研究的难度，而且在现实生活中有较大的应 用前景。 2 基于挖掘对象的分类 传统数据挖掘的对象是数值数据或文本数据，视频数据挖掘的对象是视频数据。 但是，这并不是说视频数据挖掘是在许多巨大的视频文件上直接挖掘，通常我们需 要对原始视频文件进行切割和剪辑，切割或剪辑之后的结果作为挖掘的直接对象。 由此，我们可以将视频数据挖掘分为两类。 西北师范大学硕士学位论文第二章相关概念、技术与理论 第一类以镜头( s h o t ) 为数据挖掘的基本单位，镜头是视频中连续多个有紧密 关联的帧( f r a m e ) 的集合。单独一帧通常并不能表现出明显的语义，而镜头可携带 最基本的语义信息，而且在有些视频格式中，一些相邻帧的数据是压缩在一起难于 分离的，如j d p e 6 4 和跚，所以我们通常不以帧为挖掘单位。 第二类是以对象( o b j e c t ) 为数据挖掘的基本单位，对象是指视频画面中一个 对人来说有意义的物体。它可能是相对固定的，不随时间变化而改变在画面中的相 对位置，比如字幕；它也可能是运动的，需要我们在多帧影像中跟踪它，如车辆。 以对象为数据