（计算机应用技术专业论文）视频信息检索研究.pdf

复巨人学博上学位论文摘要 摘要 随着互联网和多媒体技术的迅速发展，人们可以访问到的多媒体数据急剧 增长，视频作为多媒体信息中最复杂一种媒体形式，凭借其多样化的表现形 式、丰富的语义内容，以及便捷的记录方式得到了广泛的应用和发展。与此同 时，大容量存储技术的发展，使得数字化视频信息存储的代价越来越低，进而 促进了数字视频信息的大量产生和堆积。面对越来越多的海量视频库，如何快 速有效地进行视频内容分析和检索就成为当前视频信息领域研究的当务之急。 针对大规模视频信息检索的需要，本文从基于低层特征的视频快速检索、 视频语义信息建模以及多模态信息融合视频搜索三个方面对当前视频检索研究 中的若干关键问题进行了深入细致的研究。 在基于低层特征的视频检索方面，本文提出了基于高维索引结构的快速视 频检索算法，该方法利用高维索引结构v a - f i l e 组织视频数据库，设计了两种 不同的子片段分割算法，以及新的包含视觉相似性和时序关系的视频片段相似 度度量，并通过基于限定性滑动窗口的快速查询算法，在一定程度上解决了大 规模视频数据库的快速高效查询问题。 在视频语义信息建模方面，本文将视频高层语义特征提取分成两个部分： 具体概念检测和抽象概念推理。针对抽象概念推理，本文提出了一种新的基于 本体的视频抽象概念检测算法，该方法利用贝叶斯方法以及贝叶斯网络构造抽 象概念检测本体，并利用本体中定义的推理规则完成视频中抽象概念的检测。 该方法从语义信息学的角度对视频内容进行分析，在一定程度上消除了语义鸿 沟的影响，取得了较好的查询结果。 在多模态信息融合的视频检索方面，本文设计了一种基于关系代数的多模 态信息融合的视频检索模型，该模型充分利用视频包含的文本、图像、高层语 义概念等多模态特征，构造了对应于多个视频特征的查询模块，并创新地使用 关系代数表达式对查询得到的多模态信息进行融合。实验证明，利用该视频检 索模型对视频片段进行检索，能够取得优于基于逻辑回归的线性融合的多模型 视频检索方法的查询结果，特别是对于包含复杂语义的多概念综合视频查询更 为有效。 关键字：视频检索、高维索引结构、视频语义信息建模、本体、贝叶斯网络、 多模态信息融合、关系代数表达式 复且大学博j ：学位论文a b s t m c t a b s t r a c t a st i i em o s tc o m p l c xm e d i af b 曲o fm u l t i m e d i a ，v i d c 0i sa p p l i c d 柚dd e v c l o p c d w i d c l yd u et o i t sd i v e 娼i f b n n f c p r c s e n t a t i o i i a _ b u n d a n ts 锄a l i t i cc o n t e m ，柚d n v c n j c n tw a y so fr e r d i n g o nt h co t h e fh a n d ，t h ed e v e l o p m e n ti nc o m p u t i n g t c c h n o l o g i e s ，b m a d b 柚d 姗u n i t i o nn e 啪o r k s ，勰dm a 蹒s t o 船g cd c 、，i c c sh a v e r 鹳u l t c di i il a f g e 砌o 岫t0 fv i d c od a t ab e i i l gg c n e m t e d 锄dm a d ca o o e 豁i b l ei nd i g i t a l 触t h m u g h o u tt h ew o d d a sar 踟n ，t h em a i l it a s k so fv i d i n f o m a t i o n p i o l o s i n g 盯ee f 缸m v ev i d e o n t 朋ta n a l y s i s 柚de l ! f i c i 姐tv i d r c l 一e v a l ht h i sd i s s e r l a t i o n av i d e 0 t r i e v a lm e u 川b a s c d l o wl e v e l 鼬u r e si s p l d p o s e d ns e 砌e st h cp m b l 锄so ff 缸tv i d c h p 砖t r i c v a li nl a r g e 锄o u n tv i d d a 劬a 辩w i t he 骶c t i v co r g 柚i 趵t i o no fv i d f c a t u sd a t a b 勰cb yv j 卜f i l e 锄d 缸t q u e r ya l g o r i t l i l i l sb yr e s t r i 倒s l i d i n gw i n d o w ha d d i t i o n ，w ed e s i g nan e ws i m i l 撕t y m e 勰u f ew h i c hs y i i t h e t i c a l l y n s i d e r st h ev i s u a i s i m i l a f i t y a n dt e m p 0 阳lo r d e r b e 锕e e nv i d c o d i p s s i n c eo n t o l o g y nb cl i s e dt oe x p r e 鹞t h es 锄卸t i cr c l a t i o l l s i l i pb c 腑nc o n c e p t s i nv i d c o s ，w ep l _ 0 p o s eav i d c os e m a n t i ci n f o m a t i o ne x t m c t i a l g 嘣t h l i ib 勰e d 彻 衄t o l o g yf o rv i d n t c n t 鲫a l y s i s 锄dr c l r i c v a i t 钾od i 脏r 朗tm 劬0 d so fb a y c s i 孤 m e t h o d 锄d 王i a y e s i a nn e t 、0 r ka mu s c dt oc o n s 协i c tv i d c os e m 锄t i c 彻t o l o g y ，锄d f e 勰彻j n gm l c sb a s e d 伽伽t o l o g ya 咒印p l i e dt od c t c c it h ea b s 仃a d n c c p t si nt e 珊s o f c o n c t cc o n c 印t si nv i d e o s ha l l u s i 蛐t 0t h c 锄p l e xr e q u i r c m 朗to fq u e i y ，an e wv i d r c i 嫡c 、，a lm o d e l b 罄e d m u l t i m o d a li n 】研m a t i f i l s i 蚰i sb i o u g h tf 0 唧盯di nt h i st h 伪i s ni n d u d e s m u m - m o d e l sl i k et 强t i m a g c ，h i g l l - l c v c ls e m 卸t j cf c a t i l f 豁强仃a c t i 蛐c t c 卸d 璐e s r c l a t i a la l g c b m 懿p i 伪s i o nt of i i m u l t i m o d a lj n f o r m a l i o n 砒t a i n e db ym l i i t i m o d e l s 硎e v a j e x p 洳蜘t a l s u l 协d 锄0 m 瞳m t ct l i a t0 u fm e t h o dc o u l dm a n i f e s tt h e a d v 柚t a g c so fm u l t i l 玳，d a li n f 0 衄a t i o nf i l s i o nb a do n l a t i o n a lc x p ”s s i o ni nv i d 删c v a l ，a n da c h i c v 鼯9 0 0 dp 幽册卸c c 衄o m n p l 强s 锄柚t i cv i d c oi n f o 】m a t i 陀研e v a l k 七y o r d s ： v i d 硎e 、，a l ，h d e x s 仃u c t l i r e ，彻胁l o 盱，b a y 伪i 孤n 咖o r k ， m u l t i m o d a li n f b r n l a t i o nf i l s i o n ，r e l a t i a la i g c b r ae x p r c s s i n 论文独创性声明 本论义是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了 特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明并表示 了谢意。 作者签名：必 日期：塑i ：! 三垫 论文使用授权声明 木人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留送 交论文的复印件，允许论文被套阅和借阅：学校可以公布论文的全部或部分内容， 可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此规定。 作者签名： 毯煎导师签名 i ：蕴盏皿 复日+ 人学博 学位论义绪论 1 1 研究背景及意义 第一章绪论 随着多媒体计算技术的迅猛发展，网络传输速度的不断提高，以及各种视 频压缩技术和大容量存储技术的相继出现，使得视频信息的获取、存储和传播 变得越来越方便，也使得视频作为一种信息记录方式得到了越来越广泛的应 用，从地质探测、科学考察、监控系统到生活录像、电视节目，人们越来越倾 向于采用视频的形式存储各种各样的信息。视频是多媒体信息中最复杂的一 种，是集图像、声音、文本于一体的综合性媒体信息。视频作为信息媒体虽然 具有表现力强、蕴涵信息量大、形象生动等优点，但同时其非结构化的数据格 式、巨大的数据量以及表现内容的不透明等缺点，使得对视频数据的管理和分 析( 如视频数据的浏览、检索) 相当困难。面对海量的视频信息，如何有效地 组织和管理视频数据以实现快速准确地存取，尽可能满足人们的查询需求，已 经成为多媒体研究领域一项重要的研究课题并且具有广泛的应用背景和深远的 研究意义。 随着数字化视频数据量的急剧增加，传统耗时的浏览方式显然己远远不能 满足人们对视频信息的访问和查询需求。基于视频存储技术的快速发展以及人 们对查询的需要，如何快速准确地从海量视频库中找到感兴趣的视频片段已经 成为视频信息领域发展中的关键问题。对于视频的查询需求，人们迫切地希望 通过高层语义描述来实现检索的愿望，如查找足球比赛中的射门镜头、含有日 出景色的片断等。从而对于视频的高层语义特征提取和搜索已经成为近来视频 领域研究的热点问题。伴随着视频检索的深入，视频检索的要求不断增加，包 含多特征、多模态信息、多检索方式的综合视频检索也将越来越受到重视和发 展。 针对多媒体数据的广泛应用，越来越多的高校、科研机构和公司开始致力 于音视频等多媒体信息检索方面的研究，其中比较著名的有由美国n s f 、 a r p a 和n a s a 资助的数字图书馆项目( d i g i t a li j b m r 3 ，) ；英国剑桥大学的视 频邮件检索( d m a i lr c t r i c v a l v m r ) 和多媒体文档检索( m u l t i m c d i a d 0 c i l m e n tr e t r i e v a l m d r ) 项目；m m 的c u e d 系统l l 】；m i c s m 的新闻 视频浏览系统以及c o m p a q 的s p c h b 0 t 项目等。另外，美国n i s t ( n a t i o n a l h s t i t l i t eo fs t 卸d a r d s 觚dt c c h l o g y ) 主办了针对大规模视频检索的国际评测会 复4 大学博j ：学位论文绪论 议t r e c d ，它通过提供统一的测试数据和评估标准，鼓励各个研究机构在大 规模视频信息分析和检索领域的研究1 2 j 。 尽管视频信息检索经过多年的研究和发展，取得了一定的成绩，但面对规 模越来越大的视频信息、用户越来越复杂的查询需求，对于如何进行快速有效 的视频检索、高层语义概念分析，以及多模态信息融合的视频搜索等具有挑战 性的问题，还需要进行进一步的研究和探索。 1 2 视频信息检索的研究现状 视频信息检索是多媒体领域的重要研究课题，是跨越图像处理、计算机视 觉、模式识别、人工智能以及数据库等领域的交叉学科，是对文本、图像、声 音等多种媒体形式的综合分析和查询。 1 2 1 视频信息检索系统框架 视频信息是复杂的无结构的数据流，包含了图像、音频、文本等多种媒体 表示形式，因而对其进行分析和检索需要涉及多种媒体分析方法。针对日益复 杂的视频信息查询要求，单纯的基于低层特征的视频检索方法显然已经不能满 足人们的查询需求，因而越来越多的视频检索系统朝向视频语义分析以及多模 态信息融合的方向发展。 当前视频检索系统的研究大都试图从低层物理特征和高层语义特征两个方 面综合分析得到符合查询要求的视频片段，然后通过有效的多模态信息融合方 法得到最终的查询结果。该类视频检索系统将视频信息检索分成离线和在线两 个部分。离线部分如图1 1 所示，主要包括：视频低层特征组织和语义信息建 模两个模块，用于对视频中包含的低层物理特征和高层语义特征进行提取和组 织，形成视频特征库；在线查询部分如图1 2 所示，主要包括查询题目分析、 多模态信息查询、融合和排序以及用户界面等功能模块。 视频特征数据库的组织 原始视频流 图1 1 视频信息检索框架离线部分 2 圄 复且大学博+ 学位论文绪论 图1 2 视频信息检索框架在线部分 1 ) 低层特征组织 主要是提取视频的低层物理特征并对其建立索引结构。这个部分包含三个 功能模块：视频分割、低层特征提取和索引结构建立。视频库的所有视频流首 先被分割成在时间上连续的视频单元。随后，针对每个视频单元，提取相关的 低层物理特征( 包括颜色、纹理、形状、运动等) 用于描述该视频单元的内 容。为了便于管理和加速查询，采用适宜的索引结构对视频特征进行组织管 理，最终形成视频特征库。良好的数据库组织能够合理地管理海量的高维视频 特征，从而快速地索引到相应的视频特征。 2 ) 语义信息建模 视频语义信息建模，就是利用视频的低层视觉特征或者语音特征分析视频 中包含的高层语义信息，例如分析出包含山、水、船的图片。对视频语义信息 进行建模，首先要对视频进行分割和低层特征提取，然后利用分类器或推理规 则分析得到视频中包含的高层语义特征。从视频中分析得到的高层语义信息可 以用于与文本或语义相关的视频检索。 3 ) 查询题目分析 由于用户提供的查询题目可能包括文字描述信息、样例图片和样例视频等 多种媒体形式，所以需要经过查询题目分析模块将这些查询需求变成查询所需 的关键词或特征向量，用于进一步的查询。 4 ) 多模态信息查询 多模态信息查询包括高层语义特征查询和低层物理特征查询，就是通过用 户给出的查询条件，根据事先提取的视频语义特征查找符合查询条件的视频片 段；或者通过查询处理模块得到的查询特征，使用一定的相似度模型和匹配算 法计算视频特征数据库中的特征数据与用户提供的查询样例之间的相似度，并 根据一定的相似度阈值返回查询结果。 3 复q 大学博上学位论文绪论 5 ) 融合和排序 多模态信息查询的结果只是视频在某一种媒体形式或者查询特征上的查询 结果，为了得到更为丰富和详细的视频内容信息，提高视频查询的准确性，则 需要采用一定的融合策略将根据不同检索模型分别查询得到的多模态查询结果 进行有效的融合以及合理的排序。 6 ) 用户界面 现代多媒体信息系统的一个重要特征就是信息获取过程的可交互性，用户 界面提供给用户一个视频查询结果显示和浏览的可视界面，以及具有丰富交互 能力的查询接口，用户可以通过友好的用户界面观看检索结果，也可以通过标 记查询结果的相关程度，进行相关反馈的学习，将用户反馈的信息返回给融 合、查询甚至查询题目分析的模块，通过机器学习的方法优化查询矢量、调整 相似度模型的参数以及相关阈值，从而进一步提高查询检索精度。一个友好的 用户界面，能够提供用户便捷地浏览视频数据的窗口，具有丰富的交互能力， 能够使用户方便而又快速的检索到自己感兴趣的内容。 视频信息包含多种媒体形式及一定的时空特性，是一种非常复杂的媒体形 式。从而使得视频检索是一项涉及面很广的交叉学科的研究课题，需要利用图 像处理、模式识别、计算机视觉、图像理解等领域的知识作为基础，还需要从 认知科学、人工智能、数据库管理系统、人机交互、信息检索等领域引入新的 媒体数据表示和数据模型，从而设计出可靠有效的检索算法、系统结构以及友 好的人机界面。 经过多年的研究和发展，视频检索领域已经相继出现了许许多多相关的研 究课题，下面就几个与本文研究内容相关的课题的研究情况进行概括总结，其 中包括：基于低层特征的视频信息检索，视频语义信息建模，以及多模态信息 融合的视频检索方法。 1 2 2 基于低层特征的视频检索 传统的视频信息检索技术要求事先对视频信息按设计好的格式进行严格同 义的加工( 包括分类、标记关键词或索引词等人工标注工作) ，然后才能进行 有效的检索。然而，伴随着多媒体和网络技术的发展，导致视频信息量急剧增 加，致使人工标注的方法遇到了极大的挑战，主要表现在以下几个方面：人工 标注量大且成本很高；对包含图像、声音和文本的视频信息很难用恰当的文本 予以描述；人工标注由不同的人完成，会由于人的主观感知不同导致标注的标 4 复口大学博士学位论文 绪论 准不统一，标注结果不精确等。正是由于人工标注视频方法拥有众多不足之 处，因而基于视频低层特征的检索技术应运而生。 基于低层特征的视频检索就是利用听觉、视觉等视频本身的的低层物理特 征实现的视频内容检索。它的基本思路就是按照一定的规则对视频流进行分 割，自动提取可以描述视频内容的特征，然后采用一定的数据结构有效地组织 视频特征数据库，并在其组织结构上进行快速的浏览或检索。下面分别介绍基 于低层特征的视频信息检索中的若干关键问题。 1 2 2 1 视频的分割与表示 视频是无结构的流数据，它的基本组成单位是帧，视频流是具有时序关系 的帧的集合。通常一秒的视频信息约包含2 4 3 0 帧，因此视频若以帧为查询单 位，则会因为巨大的计算量而导致过长的查询时问。而且镜头内部多数的相邻 帧在内容上的差别非常小，也没有必要对每一帧都进行匹配查询。因此，人们 通常将视频分割成合适的视频单元，从分割后得到的视频单元中提取关键帧作 为基本的查询单位进行视频片段的匹配查询。视频分割就是研究如何对视频进 行有效分割，使得分割后的视频单元能够较为准确地表达相对完整的内容，以 便于视频检索和浏览。 很多基于内容的视频检索算法都以镜头为基本单位，经过多年的研究已经 产生了很多优秀的基于非压缩域的镜头分割算法，主要包括以下几类：基于象 素的，基于直方图的【3 hj 7 】，基于统计的以及基于图像特征的闱 1 川方法等。 在基于像素的方法中，通过计算帧间对应象素点之间的灰度差异得到帧 间距。一个点的灰度值被定义为0 2 9 9 r + 0 5 8 冶+ 0 1 1 铀，这里r ，譬，6 为三原色。 基于直方图的方法以及由它派生出的众多方法是目前镜头边界检测使用 最为广泛而且最为有效的一类方法。它的基本思想是通过统计帧图像各 个颜色值出现的频率得到该帧的颜色直方图，随后比较前后帧的直方图 差异来判定两帧之间是否存在着镜头转换。常用的利用颜色直方图计算 帧间差异的方法有：直方图的简单差，直方图的交以及直方图的x 2 差 等。 基于统计的方法是利用数学统计中的矩来表示检测镜头变换。一个帧的 某些矩常量( m 咖e n th l v a r i 卸协) 可以体现出该帧的一些性质来，例如 拉伸变换尺度、旋转变换尺度、平移变换尺度等。基于统计的方法就是 根据从帧中提取的矩常量对镜头变换进行分析。 5 复旦大学博e 学位论文 绪论 基于图像特征的方法主要是根据从图像中提取的颜色、纹理、边缘等低 层特征，利用相邻图片之间的特征变化和差异进行镜头边界的检测。 由于镜头中包含了过多的内容，镜头内部某些帧之间会有较大差异，因而 以镜头为查询单位，在一定程度上会影响查询精度。基于此，文献【1 1 】中提出 用子片段代替镜头作为视频片段查询的基本单位。子片段是镜头内根据颜色特 征相似性聚集在一起的连续帧的集合，子片段内部的帧在视觉上具有更强的相 似性，能够较为准确地表达镜头内部不同的内容。 人类的视觉和听觉系统能够很容易地感知一段视频的内容，但对于计算杌 来说，必须把视频中的图像和音频信息转化成数字特征( 如统计系数、特征矢 量等) 才能对视频的内容进行有效的识别和分析。这种由原始视频数据转换成 数学表示或文字表示的低层物理特征或者高层语义特征的过程称为特征提取。 特征提取是基于内容的视频检索的基础，只有当描述视频内容的特征对于不同 的视频片段具有足够的区分力，视频检索系统才能够得到较高的查询精度。 视频特征提取主要包括高层语义特征提取和低层物理特征提取。高层语义 特征提取主要包括利用o c r 技术实现对关键帧中字符提取【埘，利用人脸检测技 术实现人脸特征的提刚1 3 1 ，利用音频特征进行说话人或者说话内容识别【1 4 】，以 及利用统计模式分类的方法完成高层语义概念提到1 5 1 【1 7 j 等。低层物理特征提取 主要是从视频关键帧中提取颜色、纹理、形状等低层特征以及m p e g - 7 1 1 8 】中定 义的视觉特征描述子。下面着重介绍几种视频检索中较为常用的低层特征。 1 ) 颜色 颜色是衡量视觉对象相似性的重要元素，颜色特征是最早被应用到基于内 容的图像检索系统中的特征。颜色统计常被用来计算图像问的全局或局部差 异。全局的颜色特征包括颜色直方图，颜色矩1 1 9 1 、颜色集【衡j 等。全局的颜色直 方图虽然有计算简单、较强的表示和区分图像的能力等优点，但是没有考虑颜 色在二维空间中的分布特性。因此，又产生了一些能够表现颜色布局的特征， 如把整个图像划分为子块，从每个子块中提取颜色特征的方法i “l ；基于四叉树 的颜色布局表示方法【2 2 l ；基于内容的区域分割及区域颜色布局的表示方法【2 3 l 等。 劫纹理 纹理是所有表面都具有的内在特性，它包含了表面结构的组织以及它们和 周围环境关系的重要信息。在7 0 年代早期，h a r a l i c k 等人就提出了关于纹理特 征的共生矩阵表示l 列，首先根据图像像素之问的方向和距离构筑一个共生矩 6 复旦大学博士学位论文绪论 阵，然后从该矩阵中提取有意义的统计作为纹理信息的表示。在基于人类视觉 感知的心理学研究的推动下，t a 衄u m 等人从完全不同的角度研究纹理的表示， 提出了对纹理视觉特性的近似计算【矧。提取出的六个纹理视觉特性分别为：粗 糙度、对比度、方向性、线度、规则性和粒度。和共生矩阵不同，这些纹理特 性在视觉上都是有意义的。进入9 0 年代初，小波变换【硐的引入及其理论框架的 确立，使小波变换成为纹理表达的重要手段之一 3 ) 形状 在图像或视频检索中，往往要求形状的表示具有对位移、旋转、缩放的不 变性。形状的表示方法主要分为两类：基于边界的和基于区域的。基于边界的 形状表示只利用形状的外边界，而基于区域的则利用整个形状区域。在这两类 表示方法中比较成功的是傅立叶描述子和矩不变量。傅立叶描述子的主要思想 是用傅立叶变换后的形状边界作为形状特征，用较少的参数可以表示较复杂的 边界【明。矩不变量的主要思想是使用基于区域的矩作为形状特征【勰】。近年来， 又有一些新的描述形状特征的方法被提出来，如有限元素法( f i n i t ee l 锄e m m c t h o d ) 【2 9 】、调整函数( t u n i n gf u n d i ) 刚和小波描述子( w a v c l e t d c s 口i p t o r ) 【3 1 l 等。 4 ) m p e g 7 描述予 鉴于视觉特征在图像视频表示和检索中的重要作用，m p e g 组织定义了一 组视觉特征描述子，并将其加入到m p e g 7 标准中。主要包括：可变尺度颜色 描述子( s c d ) 、颜色布局描述予( c l d ) 、颜色结构描述子( c s d ) 、主导 颜色描述子( d c d ) 、纹理浏览描述子( t b d ) 、均匀纹理描述子( 瑚 d ) 、 边缘直方图描述子( e h d ) 、a r t 一基于区域的形状描述子、基于轮廓的形状 描述子等。关于这些视觉描述子的具体定义，参见m p e g 7 标准文档【堋。 视频经过分割得到查询单元，然后从中提取表示各个查询单元的低层物理 特征或者高层语义特征，用于进一步的特征数据库组织和检索。由于这些低层 特征大多以高维向量的形式存在，为了进行快速的查找，就需要采用一定索引 方式对其进行组织管理。 1 2 2 - 2 视频特征数据库的组织与构建 伴随着多媒体技术的快速发展，视频数量也以惊人的速度不断增大，形成 了一些超大规模的视频库。由于视频是无结构的流数据，为了对其进行有效的 管理和查询，就需要提取视频特征来表示视频流。大规模的视频数据必然导致 大规模的视频特征库的出现，为了提高查询效率，需要采用一定的方式对视频 7 复旦大学博士学位论文绪论 特征数据库建立索引。视频特征数据通常由高维向量表示，因而对视频特征建 立索引，就是对高维向量建立索引。 自2 0 世纪7 0 年代开始，随着c a d 、g i s 及医学影像等应用的出现，逐渐 提出了对高维数据及高维数据快速查询的需求。高维数据由于其自身的无序 性、复杂性等特点，使得b + 1 r c e 等传统关系数据库中的索引结构无法适用， 为此人们开始了高维数据索引结构的研究。在过去的几十年中，大量的高维数 据索引结构被相继提出，根据这些索引结构的不同特点，可以大致分类如下： 按结构组织类型划分，包括树形索引结构和非树形索引结构：树形索引 主要是以r - t f c e 【3 2 1 为代表的一系列索引结构，这些结构主要以r 打c c 为 基础，并对其进行适当的改进，包括r t - 【3 3 l 、x 仃【圳等；非树形结 构类主要是以文件过滤为主的索引结构v a - f i l c l 矧及对其进行改进的 l p c ；f 丑c l 删等。 根据划分的对象，可以分为基于数据划分( d a t ap a n i t i 彻i n g ) 和基于空 问划分( s p a c cp 枷t i o n i n g ) 两种索引结构。在基于数据划分的索引结构 中多采用边界矩形构造层次结构，在数据层，距离较近的数据对象聚集 到超矩形中；在索引层，距离较近的超矩形递归地聚类成较大的超矩 形，形成层次目录结构。这类索引结构包括：r 仃优、r + t r c e 、x 仃e c 、 s s t r e c 吲、m 骶e p 8 l 、t v t r 【3 9 】等。基于空间划分的索引结构递归地将 空间分割成不相交子空间，分割的层次构成树结构。这类索引结构包 括：k d b 骶e 【蚰1 、h 仃c e 【4 l j 、l s d h 仃f 4 2 】等。 按照是否对查询数据进行降维操作，可以分为降维的和非降维的方法。 其中降维的方法主要包括利用离散傅立叶变换( d f t ) ，离散余弦变换 ( d c t ) ，离散小波变换( d w t ) 和奇异值分解( s v d ) m 等方法对数 据进行降维处理，再建立索引结构的算法，以及将高维空间中的矢量数 据映射为一维数据，然后利用传统的索引结构建立索引的方法，如 p y 姗i d 1 锄n i q u c l 4 3 1 、i d i s t 柚【4 习、i m i n m 积m 等。非降维的方法则是 r - t r 系列以及v f i i e 等。 根据处理数据的类型，可以分为点数据类和空间数据类。点数据类是指 那些只能处理点数据的索引结构，如k 一t r 【4 7 】、t v t r 等；空间数据 类指既能处理点数据，又可以处理具有一定形状的数据的索引结构，如 r t r 、r 蜘等。 下面重点介绍几类典型的高维索引结构：树形索引结构，基于量化近似的 索引结构和基于降维的索引结构。 8 复q 大学博十学位论文绪论 1 ) 树形索引结构 树形索引结构主要是指由1 9 8 4 年g u l i m 孤在s l g m o d 上提出的r - 1 h e i ”l 索引结构，及在其基础上改进的算法。r 仃e e 是一种类似于b t r 的高维索引 结构，它也是一棵动态平衡树，具有层次结构。它采用原始数据的最小外接矩 ( m b r ) 形来表示数据，可以对高维空间的数据对象以及点数据进行索引和快 速查询。r t f 的查找算法类似于b t r e c ，从根节点出发检查节点中每一个项 是否与要查找的区域相重叠，如果重叠查找该项所指向的子节点，直至叶子节 点。由于在r - t 慨中存放的是数据的最小外接矩形( m b r ) ，这些m b r 可能 相互重叠因而无法保证查找操作只搜索一条路径即可成功，在最坏的情况下， 一次查找操作可能要遍历所有的路径。 r - t r i 出现之后，一系列对r - t r c e 进行改进的基于数据分割的索引结构相 继出现，主要包括r - 1 r c e 【3 3 】、x _ 1 r c e m 、s s 1 r c e 【3 7 1 、t v t r 例、s r l h e 【4 8 1 等，由于这些索引结构都以树形作为主体结构，因此通称为树形索引结构。树 形索引结构多采用边界矩形( 或边界球形) 构造层次结构，数据对象聚集到边 界矩形( 或边界球形) 中，而距离较近的边界矩形( 或边界球形) 又递归地聚 类成较大的边界矩形( 或边界球形) ，最终形成层次目录结构。查询时，树形 索引结构往往采用6 r 鲫动口础6 d 肼d 算法实现七近邻查询。研究表明，树形索 引结构在多维空间( 低于2 0 维的数据空间) 中是非常有效的，然而当维数超过 2 0 后，它们的性能迅速下降，甚至不如顺序扫描，即形成所谓的“维数灾 难d 侧。 2 ) 基于量化近似的索引结构 树形索引结构多采用基于数据分割的方法，这种方法对多维或低维数据有 效，而对于高维的数据性能就会变得很差，也就是会出现所谓的“维数灾难”。 为了克服“维数灾难”，w e b 盯等于1 9 9 8 年在v u ) b 上提出一种基于近似量化的 索引结构v a f 豇c 【3 5 】。v f i l e 不属于传统的基于数据分割的方法，而是基于标 记文件过滤的方法。该方法利用空间分割得到每一个高维向量的近似表示，并 将这些近似表示存在一个近似矢量文件中，称为近似矢量文件( v e c 吼 a p p m x i m a t i f i l e ) 。进行七近邻查询时，只需先扫描比原始数据文件小得多 的近似矢量文件，过滤掉大部分距离较远的矢量，然后将剩下的少量矢量拿到 原始文件中进行精确查询，从而大大提高了查询效率。 除了v f 丑c 外，l p c f n c 【蚓和v q h l d c x 刚两种结构也属于量化近似类索 引结构。在i j p c - f i l e 中，为了使得近似矢量能更准确地表示原来的高维矢量， 增加了极坐标信息，从而提高了查询精度。而v q e x 最大的特点是引入了矢 9 复旦人学博士学位论文绪论 量量化的方法，而不是采用v 砧f i l e 和i j p c f i l c 中的标量量化方法，这种方法 虽然在很大程度上提高了查询效率，但其构造复杂度大大提高，而且需要利用 历史数据生成较好的矢量量化器。 3 ) 基于降维的索引结构 由于高维数据难以表示，且在建立索引结构的时候容易出现“维数灾难”的 问题，因而提出了基于降维的索引结构，这类索引结构通常利用离散傅立叶变 换( d f r ) ，离散余弦变换( d c r ) ，离散小波变换( d w t ) 和奇异值分解 ( s v d ) 等方法对数据进行降维处理，然后再利用对多维特征有效的索引结构 对其进行组织管理。 另外还有一类特殊的基于降维的索引方法，他们首先采用一定的方法将高 维空间中的矢量数据映射为一维数据，然后利用传统的索引结构如b + t f e e 等 实现索引及相似查询。p y m m i d _ t e c h l i i q u e f 4 3 】、_ i d i s t a i i 【4 5 】以及i m i n m 觚1 4 6 l 就是 这种类型的索引结构。 基于降维的方法虽然克服了维数灾难，但普遍存在以下问题：原始数据经 过降维，必然要损失一些数据项，从而降低了查询精度；降维是一种静态的方 法，不利于数据库的动态更新。 虽然存在很多种高维索引结构，但这些方法都有各自的特点和利弊，适用 于不同的应用环境。对于视频来说，通常视频特征都是高达几百甚至上千维的 高维数据，因而必须选择那些能够有效处理高维矢量的数据结构，对视频特征 进行组织和管理。 1 2 2 3 视频相似度度量 在基于内容的视频检索中，系统通过计算两段视频特征之间的距离来获得 相似度，然后按照相似度值由大到小返回视频数据库中与待查视频片段最相似 的视频片段。由于视频片段由若干时间上连续的帧组成，每一帧可提取的特征 又有许多种，如颜色、纹理、形状、运动、语义等，因此不仅需要定义帧之间 不同特征的相似度度量，还需要考虑视频各个层次( 关键帧、镜头、场景、视 频段) 上的相似度度量。在当前视频检索的研究中，相似度度量主要包含两部 分，帧之间的相似度度量和视频片段之间的相似度度量。 由于视频中的帧其实就是图片，所以帧之间的相似度度量也就是图片之间 相似度度量，主要通过计算两幅图片特征间的距离获得相似度。当前较为常用 的图像特征相似度计算方法主要包括： 1 0 复口人学博_ | j 学位论文绪论 1 ) 点的几何距离 将图像的特征矢量看作高维特征空间中的点。比较两个特征是否相似可以 通过计算它们之间的距离得到。特征间距离越小，则图像越相似。常用的几何 距离包括m i n k o w s k j 明氏距离( c i t y b l o c k 距离和e u d i d e 她距离为明氏距离的两 个特例) 、m a h a l a n o b i s 马氏距离，切比雪夫距离和兰氏距离。其中最有效的为 马氏距离，但由于计算量很大，实际中最为常用的是e u c l i d c 柚距离和 c i t y b l o c k 距离。 2 ) 角相似度 特征矢量的角相似度是两个矢量的点积。相似度与矢量的方向有关，而与 矢量的大小无关。 眠) i 斋 ( 1 1 ) 3 ) 直方图交相似度 直方图交相似度由两个特征矢量的各维元素中相似成分多少所决定。一般 用于计算两个直方图间的相似度，是一种常用的相似度计算方法。 跗卜幽噎，童 n 刁 4 ) 点集间的距离 d 维空间两个点集合之间的距离包括：最小距离( 两个集合中距离最近的 两个点之间的距离) ；最大距离( 两个集合中距离最远的两个点之间的距 离) ；平均距离( 两个集合中所有点平均值之间的距离) ；h 卸s d o 耐距离( 一 个集合中的点到另外一个集合中点的最小距离中的最大值) 。在实际应用中， 均值距离和 h u s d o r f = f 距离是两种最常用且性能较好的相似度度量。 5 ) 高斯概率相似度 假定任意两幅图像的特征矢量分别为x ，工( 七为特征的维数) ，定义特 征差分矢量： d z x ，w 矗e 坨x ，石，d 只 ( 1 3 ) 则这两幅图像的相似度可以看作在给定特征差分矢量d 的条件下，两幅图像相 似的概率。即 1 l 复日大学博上学位论文绪论 p ( 4 d ) ip ( d ，爿) p ( 爿) p ( d )( 1 4 ) 假定特征差分矢量d 服从均值为d ，协方差矩阵为的多维正态分布，则， ( 1 5 ) 由于p ( 爿) 为一常量，p ) 可以简化近似为一个常数，则两幅图像的高斯概率 相似度可以近似估计为： p 似d ) - p 一旺。：7 。7 2( 1 6 ) 当对上式取对数时，即得到马氏距离。p ( ) 函数中的变量可以是前面介绍的任 何一种距离。这样，e ( ) 就可以把前面介绍的各种距离函数方便的转化为【d j 】 范围内得相似度。d 表示完全不相似，j 表示完全相似。 距离度量函数d 通常都满足如下距离公理的条件： 自相似性：d ( j ，石) 一0 最小性：d 皤，z ) d ( x ，x ) 对称性：d 僻，x ) td ( 工，x ) 三角不等式：d ( x ，l r ) d ( x ，x ) + d ( z ，y ) 几何距离度量方法的自相似性保证了一个对象同它自身的相似度为一个常 数并且是最相似的；相似性的对称性说明两个对象之间的相似关系是可逆的， 与比较的顺序无关；三角不等式表明了相似度度量具有传递性。在某些情况 下，对称性和传递性在视觉相似度模型中不一定成立。而且特征空间中距离最 近的两幅图像在人类视觉上也不一定是最相似的。因而，寻找与视觉感知一致 的相似度模型是图像和视频信息检索要解决的重要问题之一。 视频片段是具有时间顺序的帧的集合，相似度定义通常比较复杂。在经过 视频分割和特征矢量提取以后，视频就可以表示为一段连续的高维矢量序列， 因此，视频片断之间的相似度定义就可以转化成高维矢量序列之间的相似度计 算。根据是否考虑视频片段中关键帧之间的时序关系，可以把视频片段的相似 复旦人学博1 ：学位论文绪论 度模型分为两类：考虑关键帧之间的时序关系的相似度度量和不考虑关键帧之 1 ) 考虑关键帧之间的时序关系的相似度度量 的距离，同时需要考虑相匹配关键帧之间的顺序关系对相似度的影响【5 1 】- 【朔。由 于这种相似度度量从视觉和运动的角度充分考虑两段视频的相似性，因而利用 该方法计算得到的视频片段相似度值，较为符合人的主观判断。下面简单介绍 片段的相似度计算模型，该相似度度量不仅考虑了待比较视频的关键帧之间的 设d 一成，玉五。 ，d 一仃o ，乱孑一 分别代表两段视频且n = j ，l ，其 中舫” ，d ) 表示关键帧之间的相似度值，则d 和d 之间的相似度定义为： 卜脚c 半高秒詈乃 其中口【o 娜，卢阻】为控制参数， 【o ，玎一1 l 且如果一f ：，则矗t 丘。 1 跏 ，d ) 在该相似度公式中，勉侣洋l - ) 表示了两段视频内包含的所有帧的 相似度情况，!则反映了相似的帧的不同时序关系对视频片段 1 + n + 三沪“一q 相似度的影响，口里用于调节不同长度视频片段的相似度值。因此，该视频 片段相似度公式不仅考虑了组成两段视频的帧之间的相似度，还考虑了相匹配 文献【5 7 】提出一种以人的视觉感受为基础的视频片段相似度度量，它首先 复旦大学博上学位论文绪论 s 妇( c 。，c ：) 一暇品+ 坳。+ 昂 上k 一1 一【ic 1 ( d ) 一c ： ) i 肘缸( c 。似) ，c ： ) ) 】 ( 1 8 ) ( 1 9 ) 最- 1 一【ic 1 ( ，) 一c ：( ，) i 肘缸( c ，( ，) ，c 2 ( r ) ) 】( 1 1 0 ) 其中跏表示视频片段c j 和c 2 之间的视觉相似度，也就是相似关键帧的个 数；d _ r 是视频片段持续时间的比率，o 表示第f 段视频持续的时问；j k 是视 频片段帧率比，c 秒) 表示第f 段视频的帧率。鹏，耽，则为参数权重，可以调 节这三个方面在视频片段相似度中的所占的比重。该相似度度量从人的视觉感 知角度出发，分析了影响视频片段相似性的三个主要方面：视觉相似性、持续 时间以及播放的帧率。通过将这三个方面对视频相似度的影响综合起来，产生 一个较为符合人的主观判断的相似度度量。 考虑关键帧之间的时序关系的相似度度量因为要考虑对应帧的时序关系， 通常计算比较复杂，会耗费大量的查询时间，但是能较准确地反映视频片段之 间的视觉相似度，较好地符合人的主观感受。 2 ) 不考虑关键帧之间的时序关系的相似度度量 该类相似度度量就是将视频片段简单看成关键帧的集合，两段视频之间的 相似度由它们中相似帧的数量决定【5 8 】【5 引。定义如下： 帧之间的相似度定义：设i 、夕为代表两帧的高维特征矢量，d ，罗) 表 示矢量之间的距离，函数，为二值断言，那么i 、萝之间的相似度定义 为： 蛳加器篙裟嚣， m 其中函数，可以设为各种判定条件，例如用距离门限s 定义，如果 d ，歹) t ，则f g ，萝) ) 一加把，否则，( d ，萝) ) t 扣卵。 视频片段之间的相似度定义：令承l ，分别代表两个视频片段，对于z 中的任意一帧i ，如果y 中至少有一帧歹和它相似，即s 砌何，歹) 一1 ，则 称i 为z 中与r 相似的帧，所有x 中与y 相似的帧数量可以标记为： 埘1 ，昏m 忙j ，- l ；同理，所有y 中与工相似的帧数量可标记为 1 4 复且人学博十学位论文 绪论 芦1 l d 一) 1 l ；则盖和】，之间的相似度计算公式为： 螂聊- k 虹钎净 q 均 该类相似度模型计算相对比较简单，能够节约大量的查询时间，但由于只 考虑了相似帧的个数，没有考虑相似帧对应的时序关系，因而查询准确率较第 一种相似度度量差。 一个好的视频片断的相似度模型需要满足以下两个条