（信号与信息处理专业论文）基于视频时序特征的视频检索技术的研究.pdf

摘要 摘要 随着数字多媒体技术的迅速发展，基于内容的视频检索( 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 ) 技术受到极大的重视并得到广泛应用。如何有效 地对这些视频数据进行组织、表达、存储和管理，以及如何对其进行快速检索和 浏览等已经称为视频领域急待解决的重大课题。由于c b v r 技术具有重大的理 论意义和实用价值，同时鉴于视频信息分析和处理的复杂性，使得c b v r 技术 近年来受到了学术界和工业界的广泛关注。 由于视频自身数据的丰富性和多样性，结构的复杂性，基于内容的视频检索 发展到今天虽然取得了一些成果，但建立的多为实验系统，在实用性上受到一定 的局限。对于如何更好的提取视频时间空间特征以表征视频内容，以及如何设 计高鲁棒性的检索算法，提高检索的查全率和准确度仍然是极具挑战性的课题。 因此，本论文主要针对直接影响视频检索结果的两个关键技术：视频特征提 取和相似性匹配算法展开研究。 本论文在m p e g 7 的视频描述符的基础上，提出了一种新的视频特征视 频时序特征的概念，并设计和采用了相应的特征提取方法和相似性匹配算法，为 基于时一空信息的视频检索的进一步研究提供了良好的试验平台。主要工作包括 以下几个方面： 提出了一种新的视频描述特征视频时序特征，有效地利用了视频的时间 一空间信息，用视频空问特征随时间的变化表征视频内容，具有提取算法简单、 视频特征数据量小等特点。 设计并实现了基于熵的视频帧分割算法和利用图论中位点的最优分割点选 取算法，用以增加视频时序特征的信息量。首先对视频帧进行区域分割，分割成 小的子区域，分别提取每个予区域的视频特征。由于视频帧分割直接影响检索结 果和运行速度，因此采用基于信息熵原理的视频帧区域分割算法。并且，通过对 某类视频( 例如广告，新闻等) 进行大量实验，将视频帧分割结果进行统计分析， 利用图论中位点理论，确定针对某一类型视频的最佳分割方式，提高算法整体检 索速度。 针对常见干扰，设计并实现了相似性匹配算法。针对亮度整体漂移和突变干 扰等常见干扰，采用梯度匹配和异常因子增加算法的鲁棒性，并采用动态时间规 划匹配算法解决由于视频再编辑引起的不同时间尺度问题。试验结果证明本算法 具有很好的查全率和准确度。 关键词基于内容的视频检索；特征提取：视频时序特征；信息熵；相似性 匹配 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 fd i g i t a lm e d i at e c h n o l o g y , c o n t e n t - b a s e dv i d e o r e t r i e v a l ( c b v r ) i se x t r e m e l yf o c u s e da n du s e dw i d e l y i ti sb e c o m i n gt h ee m e r g e n t a n di m p o r t a n ti s s u e sf o re f f i c i e n to r g a n i z a t i o n ，r e p r e n s e n t a t i o n ，s t o r ea n dm a n a g e m e n t o fv i d e od a t aa sw e l la sr a p i dr e t r i e v a la n db r o w s i n go fv i d e od a t a c o n t e n t b a s e d v i d e or e t r i e v a lh a sh u g ev a l u ei nb o t ht h e o r e t i c sa n dp r a c t i c e ，s oa c a d e m ea n d c o m p a n i e sp a ym o r ea t t e n t i o nt oc b v r i nr e c e n ty e a r s b e c a u s eo ft h ed i v e r s i t y ，c o m l e x i t yo fs t r u c t u r eo fv i d e od a t a , t h e r ea r es o m e p r o d u c t i o n si nt h ec b v rt e c h n o l o g y , b u tm o s to ft h ep r o d u c t i o n sa r et e s ts y s t e m s h o wt oe x t r a c tv i d e os p a t i o - t e m p o r a lf e a t u r e st oe x p r e s sv i d e oc o n t e n t ，a n dh o wt o d e s i g nr o b u s ts i m i l a r i t ym a t c h i n ga l g o r i t h mb e c o m ec h a l l e n g i n gi s s u e s o u rr e s e a r c hf o c u s e so nt h ek e yt e c h n o l o g yo ft h ec o n t e n t b a s e dv i d e or e t r i e v a l ： v i d e of e a t u r ee x t r a c t i o na n ds i m i l a r i t ym a t c h i n ga l g o r i t h m 1 1 1t h i sp a p e r t h ev i d e os p a t i o - t e m p o r a lo r d e rf e a t u r en o v e le x t r a c t i o na l g o r i t h m a n dm a t c h i n ga l g o r i t h ma r ep r o p o s e d ，t h o s ep r o v i d e sag o o dt e c h n o l o g i c a lf o u n d a t i o n f o rf u r t h e rr e s e a r c ho ns p a t i o - t e m p o r a li n f o r m a t i o nv i d e or e t r i e v a l o u rw o r km a i n l y i n c l u d i n ga sf o l l o w ： b a s e do nt h e p r o p o s a l o fm p e g - 7v i s u a l d e s c r i p t o r , an e w v i d e o d e s c r i p t c 婿啊d e os p a t i o - t e m p o r a l o r d e rf e a t u r ei s p r o p o s e d t ou s ev i d e o s p a t i o t e m p o r a li n f o r m a t i o ne f f e c t l y t h ev i d e os p a t i o t e m p o r a l o r d e rf e a t u r ei s d e f i n e da st h et e m p o r a lc h a n g ea m o n gt h es t i l lp i c t u r es e q u e n c e t h e r ea l es o m e a d v a n t a g e s ，s u c ha st h ee a s ye x t r a c t i o na l g o r i t h ma n dl e s sv i d e of e a t u r ed a t a i no r d e rt oi n c r e a s e 也ev i d e of e a t u r e s i n f o r m a t i o na n di m p r o v er e t r i e v a l p e r f o r m a n c e ，e n t r o p y - b a s e dv i d e o f x a m ed i v i d i n ga l g o r i t h ma n dd i v i d e dp o i n t s e l e c t i n ga l g o r i t h ma r ep r o p o s e d f i r s t l y , d i v i d et h ef l a m e si n t os o m es u b a r e a sa n d t h e ne x t r a c te a c hs u b a r e a sf e a t u r e s t h ef r a m ed i v i d e da l g o r i t h mi n f l u e n c e st h e a l g o r i t h mp e r f o r m a n c ea n dc o m p u t a t i o nc o s t b a s e do ni n f o r m a t i o nt h e o r y , w es o l v e t h ep r o b l e mb yu s i n gt h ei n f o r m a t i o ne n t r o p y b ya r m i n ga tc e r t a i nk i n do fv i d e o ( s u c ha sa d v e r t i s e m e n t so rn e w s ) ，a b u n d a n c ee x p e r i m e n t sh a sb e e nt a k e nt oa n a l y s e t h ep a r t i c u l a rf r a m ed i v i d i n ga l g o r i t h mi sc o n f i r m e db yu s i n gg r a p ht h e o r yc e n t e r i t a b s t r a c t c o n c e p t i o nt oi n c r e a s et h ep e r f o r m a n c er a t e g r a d sc o m p a r i s o nm e t h o da n de x c e p t i o nf a c t o ra l eu s e dt oe n h a n c ea l g o r i t h m r o b u s t n e s si ns i m i l a r i t ym a t c h i n gm e t h o d a n dd a n a m i ct i m ew a r p i n g b a s e ds i m i l a r i t y m a t c h i n ga l g o r i t h ms o l v e dt h ed i f f e r e n tt i m es c a l ep r o b l e mf o rt h ev i d e or e e d i t e d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mc o u l dp r o d u c eah i g hv i d e o r e t r i e v a lr a t ea n dp e r f o r m a n c e k e y w o r d s ： c o n t e n t b a s e dv i d e o r e t r i e v a l ； f e a t u r e e x t r a c t i o n ； v i d e o s p a t i o t e m p o r a lo r d e rf e a t u r e ；i n f o r m a t i o ne n t r o p y ；s i m i l l a r i t ym a t c h i n ga l g o r i t h m ； i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：1 二盘日期：丑! ! ! f 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：互二鱼导师签名：避日期：z 垄! 垡 第l 章绪论 第1 章绪论 1 1 论文的研究背景及研究意义 随着数字多媒体技术的迅速发展，基于内容的视频检索( c a 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 ) 技术受到极大的重视并得到广泛应用。如何有效 地利用视频的特性来组织和管理视频数据，使人们能够便捷地从海量数据中找到 自己感兴趣的相关视频片断已经成为一种迫切的需求。由于c b v r 技术具有重 大的理论意义和实用价值，同时鉴于视频信息分析和处理的复杂性，使得c b v r 技术受到了学术界和工业界的广泛关注，并成为多媒体处理领域中一个极具挑战 性的研究课题i l j 。 目前应用的系统和研究成果主要针对特定的、结构化程度比较高的视频类型 ( 电视广告、新闻、球类运动等) 进行的。一般是针对特定类型的视频提出检索 的解决方案，根据其特点设计和研究相应的算法，取得了一些较好的成果。但由 于不同的视频类型间具有差异性和局限性，导致了现有的一些技术很难适用于不 同的视频类型，算法的适用性和鲁棒性受到很大制约。 鉴于以上情况，在m p e g - 7 的视频描述符的基础上闭，本论文提出了一种新 的视频特征视频时序特征，其基本思想是利用视频中图像序列特征随时间变 化的值来表征视频的内容，充分利用了视频的时间一空间特性。并且，视频时序 特征考虑到不同类型视频所具有的共性，即视频的内容随时间变化，内容不同的 视频，时序特征也不相同。当视频片断极短时，可能产生时序特征相似的情况， 但视频长度到达一定程度( 初步试验结果为2 5 0 帧以上) 时，时序特征可以充分 表征视频内容以区分其它视频。因此，本论文提出的以视频时序特征作为视频描 述符的方法，具有通用性和可辨识性。 视频特征提取作为视频检索中的关键技术，提取的信息是否能足够表征视频 内容直接关系到检索结果。因此，如何既保证算法的实时性，同时提取足够的视 频信息成为了待解决的问题。在本论文中，为了增加视频时序特征的信息量，采 用了基于熵的视频帧分割算法和利用图论中位点的最优分割点选取算法。首先对 视频帧进行区域分割，分割成小的子区域，提取每个子区域的视频特征。由于视 频帧分割直接影响检索结果和运行速度，因此采用基于信息增益原理的视频帧区 北京工业大学工学硕士学位论文 域分割算法。并且，通过对某类视频( 例如广告，新闻等) 进行大量实验，将视 频帧分割结果进行统计分析，利用图论中位点理论，确定针对某一类型视频的最 佳分割方式，提高算法整体检索速度。 相似性匹配是视频检索中另一个关键技术。在实际生活中，视频在存储和传 输的过程中会引入很多干扰，例如视频灰度的整体漂移、突变干扰等。如何减小 各种干扰对视频检索的影响就成为一个急待解决的问题。本论文在分析视频时序 特征的基础上，采用一种鲁棒性较强的基于梯度的特征相似性匹配算法，增强算 法抗干扰能力，使检索方法能够更好地适应复杂多变的实际环境。并且，针对由 于视频再编辑或者不同帧率产生的不同时间尺度问题，采用基于动态时间规划的 相似性匹配算法，提高了检索的查全率和准确度。 本论文针对视频检索中的关键性技术开展相应的研究，隶属于2 0 0 4 年北京 市教委科技发展计划重点项目“北京文化遗产的数字化保护、存档及检索的关键 技术研究”，以及2 0 0 7 年国家自然基金“支持不同时间尺度的高鲁棒性视频检 索方法的研究”。 1 2 国内外研究现状 由于基于内容的检索技术具有重大的理论意义和实用价值，国内外学术界历 来重视这一领域的研究和开发，有大量的科研人员从事这方面的研究和开发。国 际著名的m p e g 组织在其提出的m p e g - 7 标准中，定义了标准化描述接口，为 多媒体信息进行基于内容检索提供了有效支持，在视频检索的研究中将发挥重要 作用。 视频数据内涵丰富、结构复杂，既具有空间属性又具有时间属性，因此对视 频进行有效的分析和检索非常困难。由于视频实质是由具有一定时间次序的图像 序列构成，研究初期，很多图像检索的方法被应用于视频检索中。目前c b v r 技术的主要特点是通过视频分析提取视频本身包含的客观特征，主要包括颜色、 纹理、形状、空间关系、运动信息、时间顺序等来描述视频内容。这些视频特征 是一些可以独立、客观地直接从视频中获得的信息，通常采用各种统计方法进行 描述0 1 1 4 1 。 国外的大学、研究机构和公司都很重视这方面的研究，m m 公司、m i c r o s o f t 公司、v i r d g e 公司、美国哥伦毕业大学、华盛顿大学、卡内基梅隆大学以及新加 坡国立大学等在图像视频检索领域取得了出色的成绩，并陆续建立了一些具有 代表性的试验原型系统，且部分已投入实际应用。 1 q b i c 系统 2 第l 章绪论 q b i c 系统是i b m 研究中心研究开发的基于内容的检索系统，此系统提供了 对静止图像及视频基于内容的检索手段，是第一个功能齐全的视频数据库系统， 对视频数据库发展有较深远的影响。在q b i c 系统中，静态图像经过对象识别模 块以自动、半自动方式由场景中识别出对象，场景与对象均送入特征提取部分， 从中提取出相关特征( 如颜色、纹理、形状、草图等) 与图像一并送入数据库中； 视频序列送入镜头提取模块，由此模块把视频流分割为镜头序列，并从中提取出 代表帧及运动对象，然后送入特征提取部分，从视频镜头及对象中提取有关特征 送入数据库。在进行查询时，用户可以从查询接口输入以图形化或示例方式表示 的查询对象特征，数据库中存储的对象的内容特征进行比较匹配，寻找出具有相 似特征的图像和视频，查询结果以相似性匹配顺序排列。 2 j a c o b 系统 j a c o b 系统是基于内容的视频数据库查询系统，分为两个功能模块：第一 个模块用于视频数据库中的分段，第二个模块用于数据库查询。视频序列通过镜 头抽取模块划分为镜头，从每一个镜头中抽取一些代表帧，并通过它们的颜色和 纹理特征对镜头加以描述。从视频中抽取的镜头以及从镜头中抽取的代表帧都存 储在镜头数据库中，在进行视频查询时，当一个直接查询或示例查询提交到查询 接口后，匹配引擎通过分析存储在特征数据库中的数据来查找最相似的代表帧， 最终根据用户预先设定的结果匹配数量显示出n 个最接近的代表帧。 3 v i 如a i s e e k 系统 v i s u a i s e e k 系统是由美国哥伦比亚大学图像和高级电视实验室开发的，实 现了互联网上的基于内容的图像、视频检索系统，提供了一套工具供人们在w e b 上查询、检索图像和视频。 4 c o i 汪系统 c o r e 系统是由新加坡国立大学开发的一个基于内容的检索引擎，其显著技 术特色包括：多种特征提取方法、多种基于内容的检索方法、使用自组织神经网 络对复杂特征度量、建立基于内容索引的新方法以及对多媒体信息进行模糊检索 的新技术等 在国内研究方面，1 9 9 9 年在国家科技部的支持和协调下，中国“8 6 3 ”计划 智能计算机系统主题专家组也设立了数字图书馆重点项目：中国数字图书馆示范 工程。以微软亚洲研究院张宏江研究员为代表的研究小组从不同的方面和角度对 c b v r 技术进行了研究，取得了令人瞩目的成果。 国内众多高校和研究机构也有大量学者从事视频信息检索方面的工作，包 括：清华大学、北京大学、中科院、浙江大学等，并建立了一些试验系统。如： 北京工业大学工学硕士学位论文 t v f i 系统( t s i n g h u av i d e of i n di t ) 是清华大学开发的视频节目管理系统。该系统 可提供视频数据入库、基于内容的浏览、检索等功能，并提供多种数据访问模式， 包括基于关键字查询、示例查询、按视频结构浏览及按用户自定义类别进行浏览 等。北京工业大学数字多媒体信息处理研究室多年来致力于基于内容的图像视 频检索方面的研究，在视频特征提取和相似性匹配方面取得了很多成果，目前正 在承担北京市教委重点项目及国家自然基金项目。 由于视频本身的复杂度和多样性，基于内容的视频检索发展到今天虽然取得 了一些成果，但建立的多为实验系统，或者针对特定视频类型及应用，在实用性 上受到很大的局限。因此，对于如何更好的提取视频时间空间特征以表征视频 内容，以及如何设计高鲁棒性的检索算法，提高检索的查全率和准确度仍然是极 具挑战性的课题。 1 3 课题研究的内容及难点 视频检索是对视频内容进行有效查询的关键技术，具体来说就是要从大量的 视频数据中找到所需要的视频片断。由于视频的内容很难直接描述，而且视频本 身是一种流媒体，在视频检索技术出现之前，只能通过快进和快退等顺序的方法 对视频进行人工查找，这是非常繁琐费时的工作。当视频数据量增加到一定程度 时，用人工检索已经不能满足要求，迫切需要自动化的视频检索技术，特别是对 于新兴的多媒体数据库技术。用户通常希望只给出视频样例或特征描述，检索系 统便能自动地查找所需的视频片断，即实现基于内容的视频检索。本论文将针对 基于内容的视频检索的关键技术开展相关的研究工作。 在基于内容的视觉信息检索的基础上，进一步细化出基于内容的视频检索 ( 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 ) 的概念，它是指从视频数据中直接 提取出对象的语义、特征( 如视频中的关键帧、镜头、场景、镜头的运动等) ， 然后根据这些线索对大量存储在数据库中的视频信息进行查找，检索出具有相似 性的视频数据来，c b v r 能从大型分布式数据库中，以用户可以接受的响应时间， 查询到所要求的信息。 视频检索涉及很多关键技术，包括：对视频的结构进行分析，根据分析后的 视频单元提取对应的特征，进行相似性匹配，获得视频相似度的量化值。其中， 视频结构的分析包含三个方面：镜头分割、关键帧提取以及场景构造，视频结构 分析的结果是将视频分割为一定单元镜头，场景：之后，就要对各个镜头，场 景进行特征提取，得到一个尽可能充分反映镜头内容的特征空间；依据该特征空 间，设定相似性评价标准，进行特征的相似性匹配。使用户通过用户图形接口进 4 第1 章绪论 行查询，系统基于特征描述进行查询处理，并将操作结果返回给用户。 基于内容的视频检索系统的效率和性能主要取决于特征的提取和相似性匹 配算法的优劣，因此在本论文中重点针对这两部分进行研究。 1 3 1课题研究的内容 如前所述，由于整个检索系统的效率和性能主要取决于特征的提取和相似性 匹配算法的优劣，本文针对这上述两个关键技术开展研究工作，并且讨论了检索 系统的设计与实现过程。具体内容如下： 提出了一种新的视频特征视频时序特征。 特征选取主要目的是选择合适的视频特征来代表视频片段，有效地提取出视 频片断中所含有的空间信息和时间信息。对于选择的视频特征不仅要求计算 简单，数据量小，同时还需要包含足够的信息量以便区分其它视频。视频特 征通常采用图像视觉特征( 例如：颜色，形状，纹理等) 或者采用提取关键 帧的方法用以描述和检索视频内容。这些方法有很多优点，但没有有效的利 用视频的时间一空间信息。因此，本论文借鉴m p e g - 7 提案中视频描述符的 概念，提出了“视频时序特征”作为新的视频特征。视频时序特征具体定义 为视频空间特征随时间序列的变化，可以充分利用视频的时间一空间信息。 设计了基于信息熵和图论中位点的视频帧区域分割算法。 特征提取必须获得足够的信息量，为了增加视频特征的信息量，提高检索能 力，将视频帧进行区域分割，分割成小的子区，提取每个予区不同颜色空间 的视频特征。视频帧分割算法影响检索结果和运行速度，利用信息增益原理 对视频进行分割。通过对某类视频( 例如广告，新闻等) 进行大量实验，将 视频帧分割结果进行统计分析，利用图论中位点理论，确定针对某一类型视 频的最佳分割方式，提高整体检索速度。 针对不同干扰，设计了相应的相似性匹配算法。 对于不同的视频特征需要实现相应的相似性匹配算法。在设计算法的过程 中，需要考虑算法本身的计算效率以及视频特征的特性。针对视频编辑和传 输过程中引入的噪声对视频特征产生的不良影响( 如：亮度整体漂移、突变 干扰和由于视频再编辑或不同帧率引起的不同时间尺度问题) ，本文采用了 相应的匹配算法。本论文从以下几个方面进行研究：采用梯度匹配算法解决 视频亮度整体漂移的问题；采用异常因子克服突变干扰；针对不同时间尺度 视频匹配问题，借鉴其它领域中类似问题的解决方法，研究能够支持不同时 间尺度的匹配算法。试验结果证明该算法具有较好的检索效果和鲁棒性，能 北京工业大学工学硕士学位论文 在实际系统中得到应用。 1 3 2课题研究的难点 由于视频具有数据量大，结构复杂多变等特性，使得基于内容的视频检索面 临巨大的挑战。为了实现具有高查全率和准确度的检索算法，同时满足用户对于 实时性的要求，本论文研究的主要难点如下： - 如何有效地计算视频时序特征，保证提取后的特征中包含足够多的信息 量，以便区分不同视频，同时兼顾视频特征提取算法的低复杂度要求， 减少计算量并抑制噪声。 一如何针对某一类视频设定有效的分割策略，简化提取步骤，减少用户等 待时间，提高算法效率。 如何有效地解决视频传输过程中信道噪声所引入的大范围亮度漂移和视 频间强干扰等现象所导致的检索算法鲁棒性差的问题。 如何有效解决由于视频再编辑或者不同帧率引起的不同时间尺度问题， 增强检索算法的鲁棒性。 如何设计友好的人机交互界面，使用户能够方便、快捷、准确地找到所 需的视频片段。 1 4 论文的结构安排 如前所述，视频特征提取和相似性匹配是实现基于内容视频检索的基础。因 此，本文主要针对以上两个关键技术展开研究，并提出新的视频特征提取方法和 匹配算法。 本文共分为六章，各章内容及组织如下： 第一章，介绍基于内容的视频检索的发展以及国内外研究现状，给出了课题 的研究目的、意义及本文的主要工作。 第二章，视频检索的关键技术及发展现状。主要回顾了现有视频检索中的关 键技术，针对视频检索的需求，对不同算法进行比较，并对现有技术给出综合评 述。 第三章，提出了一种新的视频特征视频时序特征。介绍了视频时序特征 的基本概念和提取算法。引入了种新的基于熵的视频帧区域分割方案，并对某 类视频进行大量试验，对试验数据进行处理，采用基于图论中位点的最优分割 6 第l 章绪论 点选取算法确定针对某一类视频的最优分割方案。 第四章，针对常见的各类干扰，采用梯度匹配算法解决亮度整体漂移的问题； 针对突变干扰问题采用异常因子，有效地减少上述两种常见干扰对视频检索结果 的影响。 第五章，对于由于视频再编辑或者视频格式具有不同帧率等引起的不同时间 尺度问题，采用动态时间规划匹配算法，提高检索的查全率和准确度。 第六章，结论和今后工作展望。对全文进行了总结，并对本文涉及到的技术 领域进行了展望。 论文最后列出了攻读硕士学位期间参与的项目、发表的学术论文、专利、软 件著作权和所获奖励，最后是致谢、参考文献。 7 北京工业大学硕士学位论文 第2 章基于内容的视频检索的关键技术 基于内容的视频检索作为当前研究领域的热点之一，吸引了大量专家学者开 展相关研究工作。本章针对视频检索系统关键技术的已有研究工作和涉属具体 内容展开讨论。并针对视频检索的需求，对不同算法进行比较，并对现有技术给 出综合评述。 2 1 概述 视频数据是一类包含丰富信息量的多媒体数据。视频由连续的帧构成，帧间 的差异反映了随时间变化的内容，通过连续的若干帧表现在某一个特定空间环境 中发生的事件。由于视频数据是一种非结构化的数据，因此很多学者致力于分析 视频结构并定义视频数据模型，将其分割成独立的结构单元；在此基础上，提取 具有代表性的图像( 成为关键帧或者关键帧序列) ；对关键帧进行特征提取( 如： 颜色、纹理、形状等) 作为视频特征：针对不同情况，设计视频特征相似性匹配 算法，并返回检索结果。 自1 9 9 7 年“基于内容的视频检索”一词在国际上使用开始，视频检索技术 在二十年间得到了长足的进步。新一代的视觉信息检索系统支持根据视觉内容的 检索。对视觉信息的访问不仅在概念层利用关键字进行，而且也在感知层利用对 视觉内容的客观测量和合适的相似模型进行，如图2 1 所示。 图2 1 新一代视觉信息检索系统的工作框图 8 第2 章基于内容的视频检索关键技术 在离线状态，不仅注解员可通过一定的方法对数据库内容进行注释，而且系 统也( 自动地) 对数据库图像或视频进行分析，提取特征，从而提供出在线应用 时所需的多维索引。用户不仅可以借助文字查询方法，也可以借助视觉浏览和( 视 觉) 范例查询方法利用搜索引擎进入索引进行检索，返回的结果仍可以用可视化 的手段显示给用户，使用户能借助相关反馈开始新一轮查询。 2 2 常见的视频检索方式 视频检索早期多借鉴图像检索的方法，并不断的吸取其他领域的技术发展， 如图像处理、人像识别、语音处理等，并且针对视频特点，形成了很多检索方式。 2 2 1 传统的视频检索 基于文本信息的传统视频检索是最早产生的视频检索方式。通过人工、半自 动或者自动的方式，对视频的场景、片段等进行注释。通过文本注释表达视频所 要变现的内容，并将文本作为视频特征存入数据库中，便于用户查询、检索和浏 览。基于文本的视频检索作为传统的检索方式，需要人工手动介入，对视频内容 进行注释，需要大量人工，随着视频数据的几何增长，早已经不能满足人们的要 求。并且传统视频检索方法虽然简单易行，但有几个根本的问题影响对视觉信息 的有效表达。 首先，由于视频内容丰富很难用文字描述或文字标签完全表达，所以这种方 法在查询视频中常出现错误。其次，文字描述是一种特定的抽象，如果标准发生 变化，则文字内容也必须重新制作才能适合查询的要求。最后，目前这些文字描 述大部分是靠观察者添加的，因此受主观因素影响很大，不同的观察者或者同意 观察者在不同条件下对同一幅图像可能给出不同的描述，因而不够客观，难以建 立统一的标准p j 由于传统的方法不能完整客观地概括视频的内容，因而在很多情况下不能满 足实用的要求。为了解决上述问题，需要全面并且客观的提取视频内容。实际上 人们利用图像、视频并不是仅依据视觉质量，而更重要的是视觉内容，因此只有 根据内容进行检索才能更有效地获得视觉信息，同时在掌握视觉内容的基础上， 视频数据库中的信息才能更有效的进行管理。因此，基于内容的视频检索成为近 期学术界和工业界的研究热点，受到各国学者、高校、科研机构和跨国公司的重 视。 9 北京工业大学硕士学位论文 2 2 2 基于字幕的视频检索 视频字幕是基于内容检索研究的一个重要方而，因为字幕中包含着对视频解 释的大量信息，这些信息对于视频图像的理解十分重要。采用基于字幕的特征提 取分为5 个步骤： 1 ) 判断视频数据中是否含有字幕； 选择字幕帧，边缘提取； 3 1 字幕区域一值化； 钔o c r 处理； 5 1 生成视频文本描述。 在视频流中如有字幕，则一般出现在一段连续的帧内，不会只出现在一帧或 几帧内。因为这样人眼将无法识别字幕，字幕要经过一段时间后才会发生改变， 且两段有字幕的视频之间应有一段无字幕的视频。视频检索研究的字幕是后期制 作叠加的字幕。根据叠加字幕的特点，字幕的颜色通常与背景颜色相差较大，存 在明显边缘，且通常在视频帧的底端。因此，基于边缘的方法可以提取字幕轮廓。 字幕区域边缘提取后，对得到的图像进行二值化，得到二值化的文字图像，然后 进行o c r 处理，得到文字的a s c i i 码。根据上述处理过程，可实现基于字幕的 视频特征提取，生成视频片段的注解内容等结果。然后根据用户提交的要求，字 幕内容进行检索。 2 2 3 基于关键帧的视频检索 基于关键帧的视频检索采用关键帧表征视频内容。典型的基于关键帧的视频 特征提取和检索过程包括：首先，对视频的结构进行分析，然后根据分析后的视 频单元提取对应的特征，最后进行相似性匹配，获得视频相似度的量化值。其中， 视频结构的分析包含三个方面：镜头分割、关键帧提取以及场景构造，视频结构 分析的结果是将视频分割为一定单元镜头，场景；之后，就要对各个镜头场 景进行特征提取，得到一个尽可能充分反映镜头内容的特征空间；依据该特征空 间，设定相似性评价标准，进行特征的相似性匹配：最后用户通过用户图形接口 进行查询。系统基于特征的描述处理查询或者根据视频摘要进行浏览，并将操作 结果返回给用户。结构如图2 2 所示。 1 0 第2 章基于内容的视频检索关键技术 图2 2 基于关键帧的视频检索结构框图 到目前为止，基于关键帧的视频检索是发展比较成熟的视频检索方法，有大 量的学者对于镜头分割、关键帧提取、相似性匹配等方面进行研究，取得了很好 的试验结果，下面就针对视频检索( 特别是基于关键帧的视频检索) 的关键技术 展开介绍，并比较不同方法的优劣及适用范围。 2 3 视频检索的关键技术 基于内容的视频检索作为融合了图像处理、人类视觉、语音处理等技术的交 叉学科，形成很多不同的检索策略。下面分别对视频检索中的关键技术：视频结 构化，关键帧提取，视频特征提取、相似性匹配和视频数据索引及摘要技术展开 讨论。 2 3 1 视频结构化 视频数据是由一系列图像按一定顺序组成的，用来表述在时间和空间上由情 节和事件组成的故事或传达特定的视觉内容。基于内容的图像检索技术被大量应 用于视频检索中，但视频是时间相关的连续图像序列，具有时间特性，需要结合 视频数据自身特点设计开发特征提取、匹配算法，而视频结构化则是上述视频检 索技术的基础。 一段视频的典型结构如图2 3 所示。一段视频由一些描述独立故事单元的场 景构成；一个场景由一些语意相关的镜头组成；而每个镜头是由一些联系的帧构 成，并且可以由一个或多个关键帧表示。视频结构化的目的是把视频分为镜头、 场景等不同层次的逻辑单元，以便于在不同结构层次上对视频进行检索和浏览。 北京工业大学硕士学位论文 e 王j e 正工 ff 曰曰曰臼曰臼 一 1ii1i 丽丽丽m 丌_ i 而丽翮 图2 3 视频的典型结构 场景：由一些语意相关的镜头组成，这些镜头不一定在时间上连续。场景描 述了一个独立的故事单元，它是一段视频的语意组成单元。 镜头：由摄影机记录下来的一段连续的帧序列，它是一段视频的物理组成单 元。 帧：视频可以看作是一个连续静态图像的序列，其中的每一副静态图像成为 一帧。 关键帧：能够描述镜头主要内容的帧。根据内容的复杂程度，一个镜头可以 有一个或者多个关键帧。 视频划分是通过镜头切换点的检测( 即：镜头边界检测) 实现的。镜头边界 检测又称为镜头分割或场景转换检测( s c 吼ec h a n g ed e t e c t i o n , s c d ) ，是视频检索 的基础【6 】。大部分视频是通过编辑，由一个个镜头连接而成的，所以很多基于内 容的视频检索处理方法，首先要把视频自动地分割为镜头，以作为基本的处理单 元，这个过程即镜头边界的检测，是实现基于内容视频检索的第一步。 镜头的划分是通过对镜头切换点的检测找出连续出现的两个镜头之间的边 界，把属于同一个镜头的帧聚集在一起的过程。采用不同的编辑方法，就产生了 不同的镜头衔接方式，镜头切换主要有突变和渐变两种方式。突变是指一个镜头 与另一个镜头之间没有过渡，由一个镜头瞬间直接转换为另一个镜头的方法，即 一个镜头猛然切换到另一个镜头，称为直接转换；渐变是指一个镜头到另一个镜 头渐渐过渡的过程，中间没有明显的镜头跳跃。渐变主要包括：淡入、淡出、溶 1 2 獭，臁，锹，帧 第2 章基于内容的视频检索关键技术 解和扫换等。淡入是指画面逐渐加强的方式；淡出是指画面逐渐消失的方式；溶 解指一个画面逐渐消失的同时另一个画面逐渐出现的方式；扫换是指图像从画面 的某一部分开始逐渐被另一个画面取而代之的方式。 突变镜头切换的相邻两帧之间差别很大，所以无论在象素域还是压缩域，检 测突变的方法都比较成熟，检测成功率也高。而镜头渐变( 包括淡入、淡出、溶 解和扫换等) 切换时相邻两个帧之间的差别不是很大，并且帧间结构上具有相关 性，使得渐变检测有一定难度 7 1 镜头边界检测典型方法包括模板匹配法、直方图法、基于边缘的方法和基于 模型的方法等4 种【引。 1 ) 模板匹配法 模板匹配法以两帧对应像素差的绝对值的和作为帧间差，其计算公式如下： j “y n d ( ，) = i 力一( 五力i ( 2 1 ) x - o , y , , o 其中，表示第f 帧视频，d ( ，) 是和的帧间差，l j ( x ，力为第f 帧0 ，力 位置的像素值，m 和n 为帧的宽度和高度。这种方法比较前后两帧对应像素之 间的变化，如果变化超出一个阈值t ，则认为有镜头的切换。 模板匹配法的缺点是对噪声和镜头或物体运动非常敏感，因为它严格地局限 于像素的位置。噪声和物体运动都会使帧间差增大，从而导致错误的场景转换检 测。对此一些研究人员提出了一种改进的方法，即把各帧分为8 x 8 像素的小块， 并对每个块取平均，再用这个平均值对前后帧的对应小块进行比较，这种方法可 以去掉图像中的一些噪声，并对小的物体运动和镜头运动起到补偿作用。 直方图法 直方图法是使用的最多的计算帧间差的方法，它不考虑像素的位置信息，而 是用像素的亮度和色彩的统计值，因而抗干扰能力比模板匹配强。许多流行的算 法均以直方图差异作为帧间差异的度量，但对渐变镜头的检测效果并不理想。 其基本原理是将颜色空问分为一个个离散的颜色小区间，然后计算落入每个 小区间的像素数目。设颜色空间分为n 个区间，l - l u , 是第i 帧落入第k 个颜色空 间的像素数目。帧间差可用下面公式表示： d ( 1 i ，l ) = 1 日旷i ( 2 力 北京工业大学硕士学位论文 颜色直方图法的缺点是，有时会漏掉场景变换，因为两幅图像可能有完全不 同的结构，但其颜色直方图却很接近。与颜色直方图法相似的另一种计算帧闻差 的方法是x 2 直方图法，据介绍这种方法用于镜头转换，检测效果要好于上述两 种方法。两幅图像之差计算公式如下： 姒蛳：妻堕孑型 ) 3 ) 基于边缘的方法 这种镜头边界的检测方法是根据边缘特征计算的，它的基本思想是“在发生 镜头转换时，新出现的边缘应远离旧边缘的位置，同样旧边缘消失的位置应远离 新边缘的位置”。 具体计算过程如下： 首先提取前后两帧视频图像- 和，的边缘图e , 和e s ”，两帧视频图像之间的 差异为：d 渺2m a ) 【( 屯，d 0 ) ，其中，厶是进入像素( 新出现的远离已有边缘的 像素点) 所占的比例，“w 是退出像素( 新消失的远离新边缘的像素点) 所占的比 例，其中以2 p l p m ，p l 为e + t 中离巨中最近边缘像素点的距离大于r 的边缘像 素点的总数，p m 为e i “中的边缘像素点总数；d 02 p 2 p 一，p 2 为巨中离置“中 最近边缘像素点的距离大于r 的边缘像素点的总数，办为岛中的边缘像素点总 数。如果哦扩大于某一个设定的阈值t ，则认为出现了镜头的切变。 舢基于模型的方法 上述方法都是利用帧间差自下而上地进行镜头边界的检测，它对于突变检测 可以取得较好的效果，但是对于渐变则有一定的困难，因为它在很大程度上忽略 了渐变切换中帧与帧之间结构上的相关性。而基于模型的方法是利用对镜头编辑 的先验知识，对各种镜头切变建立一定的数学模型，自项向下地进行镜头切换的 检测，因此这种方法对镜头渐变的检测往往能取得好的效果。 h a m p a p u r 等人通过对视频制作过程的研究，找到了一种可用于镜头边界检 测的视频编辑模型( v i d e o e d i t m o d e l ) 。例如，一个典型的镜头渐变模型可表示为： “x ，y ，f ) = a ( o g i 伍) ，f ) + ( f ) 9 2 ( # ，y ，f )( 2 4 ) 其中，g l ( x ，y ，f ) 是即将逐渐消失的镜头；9 2 ( x ，乃，) 是即将出现的镜头，如 果镜头内无运动或运动很小，即可分别记为g t ( x , y ，0 “蜀( x ，y ) ， 1 4 第2 章基于内容的视频检索关键技术 g e ( x , y , o 2 9 2 y ) 。口( f ) 和( ，) 都是时间的线性函数；假设渐变转换的持续时 间为0 到t 。对于慢转换，它们可表示为： f 1 ，t t ( d = 1 一口( r ) 对于淡出，贝1 1 9 22 0 ；对于淡入，贝l j g l2 0 。在变化的过程中，每幅图 像上所有得像素都以线性规律变化。可定义如下的常量图c i ( c o n s t a n ti m a g e )