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

捅要 摘要 随着大量视频数据的出现，视频管理、视频检索等技术成为研究热点。基于 内容的视频检索系统包含对视频的结构化分析，对描述视频内容的特征提取，按 照特征进行相似性匹配，以及设计用户界面以提供用户进行视频检索四个主要部 分。本文针对视频特征提取，特征匹配，用户界面设计等关键技术展开研究。根 据对已有视频特征的综合比较与分析，本文采用已被m p e g 7 标准接纳的视频指 纹作为表征视频内容的特征。视频指纹描述方法不仅具有提取算法简单、存储数 据量小等特点，而且基于视频指纹的检索算法具有定位准确，检索效率高，且适 用范围广泛等优点。虽然原有的基于视频指纹的方法可以处理很多情况，但是该 方法对于视频传输过程中信道噪声带来的大范围亮度漂移和强干扰容易发漏检， 对于实际应用中经过编辑的视频容易产生漏检或误检。 本文主要的贡献是针对视频指纹存在的缺陷，提出了一种改进的视频指纹描 述方法，设计了新的相似性匹配算法，并实现了一个基于视频指纹特征的视频内 容检索系统。 在视频内容描述方面，在原有视频指纹提出算法的基础上，进一步探讨了在 限定数据量的情况下如何定义视频指纹的分割方案以便充分保留原始视频中的 信息。根据信息论原理，对视频指纹提取算法进行改进，提出了一种新的利用信 息增益来自动选择视频分割方案的视频指纹自适应改进算法，用以解决视频指纹 提取依赖于手动确定关键参数的问题，进一步提高视频指纹的计算效率。 在相似性匹配方面，采用比对视频指纹变化量的方法，取代比较视频指纹本 身，来消除由于视频处理及传输信道噪声引起的亮度漂移的影响。此外，特别增 加了异常因子用于减弱突变干扰的影响。同时，还采用隔行扫描的方法来提高算 法的执行效率：本文进一步通过对获取的特征数据进行分析，针对在测试数据集 中检索指定视频片断这一特点。提出了一种新的视频匹配算法。该算法运行效率 高，能适应于传输信道中存在噪声干扰以及视频编辑所造成的相同内容视频具有 不同时间跨度的干扰情况，例如：常见的慢镜头等情况。通过对视频数据库的中 大量的实验数据的测试，实验结果证明了这些算法有效性；最后本文讨论了一个 实际的视频检索系统设计的关键技术并给出了具体的实现过程。 关键词：基于内容的视频检索；特征提取；视频指纹：动态时间规划算法 a b s tr a e t t h ep r o l i f e r a t i o no fv i d e ec o n t e n tm a k e sv i d e om a n a g e m e n ta n dv i d e er e t r i e v a l s y s t e r nt u r n t ob eo n eo fh o tr e s e a r c ha r e a s at y p i c a lv i d e or e t r i v a ls y s t e r n e n c o m p a s s e sf o u ra s p e c t s t h e ya r e ：v i d e es 缸u c n l r e e x t r a c t i o n v i d e of e a t u r e e x t r a c t i o n f e a t u r em a t c h i n g ，a n du s e ri n t e f f a c ed e s i g n i nt h i sp a p w ed i s c u s st h e k e yt e c h n o l o g i e so ff e a t u r ce x t r a c t i o n , f e a t u r em a t c h i n g ，a n du id e s i g n w i t ha n e x t e n s i v es u l w e yo fv i d e of e a t u r e s w ec h o o s e “v i d e of i n g e r p r i n t s a st h ef e a t u r e e x t r a c t i o na l g o r i t h m t h e 、，i d e of i n g e r p r i n t s ”h a sm a n yf a v o r a b l ef e a t u r e s 、s u c ha s e a s ya n du n i q u ee x t r a c t i o n ，a n dd r a s t i c a l l yv i d e oi n f o r m a t i o nr e d u c t i o n ，t h ev i d e o r e t r i e v a ls y s t e r nb a s e do nv i d e of i n g e r p r i n t sp r o v i d e sa na c c u r a t ea n de f n c i e n tv i d e o r e t r i v a l a n di sw i d e l yu s e di nr e a ls y s t e m s t h ep r o p o s a lo f “d e ef i n g e r p r i n t s ”h a d b e e na c c e p t e db y 毋e g 7a st h em p e ( 7v i s u a ld e s c r i p t o r m a n yp r a c t i c a l s i t u a t i o n sa r eu s i n gi tt or e t r i e v ev i d e o s t h eo r i g i n a lv i d e of i n g e r p r i n t sa l g o r i t h mf u n c t i o n si nm a n ys i t u a t i o n s h o w e v e r , i t s r e s u l ti s g r e a t l yi m p a c t e db yn o i s e si n v i d e o s t w os e r i o u sn o i s e se x i s ti nv i d e o t r a n s m i s s i o n w h i c ha r et h ec o l o ro rb r i g h t n e s so f f s e ta n da b r u p ti n t e n s ed i s t r u b a n c e b e t ho ft h e ml o w e r 血ea c c u r r a c yo ft h ev i d e of i n g e r p r i n t s m o r c o v e r , t h er e e d i t i n g v i d e o sc a u s ee r r o r so nt h ev i d e of i n g e r p r i n t sb a s e dv i d e or e t r i v a lp r o c e s s w jt a c k l et h ep r o b l e m sw i t hi m p r o v e da l g o r i t h m s f i r s t l y , w ep r o p o s ean e w a l g o r i t h mw h i c hc o m p a r e st h ec h a n g eo fv i d e of i n g e r p r i n t si n s t e a do fc o m p a r i n g v i d e of i n g e r p r i n t sd i r e c t l ya n ds e t sa ne x c e p t i o n f a c t o rt od e a lw i t ha b r u p ti n t e n s e d i s t u r b a n c e s a n di n t e r l a c es c a n n i n gi st a k e nc o n s i d e r e dt om a k et h ea l g o r i t h mm o r e e f f i c i e n t s e c o n d l y , w ea n a l y s i st h ec o l l e c t e dv i d e od a t aa n dp r o p o s ean e wa l g o r i t h m t od e t e c tg i v e nv i d e oc o n t e n t sf r o mt h eb r o a d c a s tv i d e e t h ea l g o r i t h mi sd e s i g n e df o r r e a lt i m ec o m p u t a t i o na n dr o b u s m e s st ot r a n s m i s s i o nc h a r m e ln o i s ea n dv i d e o r e e d i t i n g w h i c hi sf r e q u e n t l ys e e no nt vp r o g r a m s f o re x a m p l et h es l o wm o t i o n a l lt h ep r o p o s e da l g o r i t h m sa r ee x t e n s i v e l yt e s t e do nr e a lv i d e ed a t a e x p e r i m e n t s r e s u l t sd e m o n s t r a t et h ee f f e c t i v e n e s so ft h ea l g o r i t h m s f i n a l l y , w ed e s i g nab s s y s t e mf o rt h ev i d e or e t r i e v a l ，a n di d e n t i f yt h ek e yt e c h n e l e g yc o n s i d e r a t i o n sd u r i n g t h ed e s i g np m c e a s ， k e y w o r d s ：c o n t e n t b a s e dv i d e or e t r i e v a l ；f e a t u r ee x t r a c t i o n ；v i d e of i n g e r p r i n t s d y n a m i ct i m ew a r p i n g l i 独创性声明 本人声明所里交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：盘塑皇日期：2 丛：! ：1 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 第1 章绪论 第l 章绪论 1 1 论文的研究背景及研究意义 随着信息技术的迅速发展和普及，以图像、视频和音频为代表的多媒体数据 呈现出爆炸性增长，各种多媒体数据包括文本、图形、图像、音频、视频和动画 等等。视频信息以其直观性、生动性和极大的亲和力起着重要的作用。尤其近年 来多媒体数据制作、存储与传播方面取得的重大技术进展，使得可利用的视频数 据急剧膨胀，已经成为人们日常生活中不可或缺的一部分。视频内容不仅仅局限 于电视、家庭电影等娱乐项目，随着教育培训、学术研究、企业合作解决方案等 新的应用领域的不断出现，视频所涵盏的范围逐渐扩大，增添了许多新的内容。 从视频会议到视频邮件，交互电视，视频点播( v o d ) 以及网络视频，已经深入 到人们生活的方方面面，如：数字图书馆、数字博物馆、视频点播服务、远程教 育、远程医疗等等。 由于视频信息有其自身的特点：第一，信息量大，内容丰富，结构复杂；第 二，数据量大，抽象程度低，所以视频信息带来的信息膨胀也非常严重。因此如 何对这些非结构化的海量数据进行合理的组织、表达、管理、查询和检索就成为 全球学术界和工业界个富有挑战性的热门话题1 4 3 l 4 5 1 3 。因此，有关基于内容 的视频检索( 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 ) 技术的研究和被称为多 媒体内容描述接口的国际标准m p e g 7 的制定已成为当前的研究工作热点”。 本课题针对视频检索中的关键性技术开展相应的研究，隶属于2 0 0 4 年北京 市教委科技发展计划重点项目“北京文化遗产的数字化保护、存档及检索的关键 技术研究”，对于以科技、人文为主题的2 0 0 8 北京奥运具有重要的意义，对于 宣传中国文化，推动北京的“2 4 8 ”重大示范工程，都具有重大意义。 1 2 本论文的研究内容 视频检索是对视频内容进行有效查询的关键技术，具体来说就是要从大量的 视频数据中找到所需要的视频片断。由于视频的内容很难直接描述，丽且视频本 身是一种流媒体，在视频检索技术出现之前，只能通过快进和快退等顺序的方法 ! ! 塞三些查兰三兰塑圭耋堡篁三 对视频进行人工查找，这是非常繁琐费时的工作。当视频数据量增加到一定程度 时，用人工检索已经不能满足要求，迫切需要自动化的视频检索技术，特别是对 于新兴的多媒体数据库技术。用户通常希望只给出视频样例或特征描述，检索系 统便能自动地查找所需的视频片断，即实现基于内容的视频检索。本文将针对基 于内容的视频检索的关键技术开展相关的研究工作。 1 2 i 基于内容的视觉信息检索 基于内容的视觉信息检索( c b r ，即c o n t e n t b a s e di n f o r m a t i o nr e t r i e v a l ) 是多媒体信息检索中的一门新兴技术，也是视觉信息研究中的热点e 基于内容的 视觉信息检索借助对视觉媒体从低层到高层进行处理、分析和理解的过程获取其 内容并根据内容进行检索闭。 1 2 2 基于内容的视频检索 在基于内容的视觉信息检索的基础上，进一步细化出基于内容的视频检索 ( 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 t 能从大型分布式数据库中，以用户可以接受的响应时间， 奁询至g 所要求的信息。 视频检索涉及很多关键技术，但关键步骤通常是如下四个方面：视频的结构 分析，特征提取和相似性匹配，以及高效、友好的人机交互界面。即先对视频的 结构进行分析，然后根据分析后的视频单元提取对应的特征，最后进行相似性匹 配，获得视频相似度的量化值。其中，视频结构的分析包含三个方面：镜头分割、 关键帧提取以及场景构造，视频结构分析的结果是将视频分割为一定单元镜 头场景：之后，就要对各个镜头场景进行特征提取，得到一个尽可能充分反映 镜头内容的特征空间；依据该特征空间，设定相似性评价标准，进行特征的相似 性匹配：最后用户通过用户图形接口进行查询。系统基于特征的描述处理查询， 并将操作结果返回给用户。 整个检索系统的效率和性能主要取决于特征的提取和相似性匹配算法的优 劣。本文重点着眼于这两部分算法的研究。 第1 章绪论 1 2 _ 3 基于内容视频检索的国内外研究现状 由于基于内容检索技术具有重大的理论意义和实用价值，国内外学术界历来 重视这一领域的研究和开发。特别是近几年受网络和压缩技术的推动，原来从事 图像处理、模式识别、计算机视觉和分布式数据库等智能系统的学者纷纷转向这 一领域，形成了一个新的国际性的研究热点。现在每年不仅有大量论文发表，而 且也建立了一些实验系统。 国际学术组织s p i e 已连续多年于春、秋两季分别在美国西部和东部召开与 此相关的专题研讨会，春季会议的主题为“图像与视频数据库的存储与检索” r s t o r a g ea n d r e t r i e v a lf o ri m a g ea n dv i d e od a t a b a s e ) ，秋季会议的主题为“多媒体 存储与档案系统”( m u l t i m e d i as t o r a g ea n da c h i e v i n gs y s t e m ) 。此外，i e e e 、a c m 和i a p r ( 虱际模式识别联合会) 等学会组织也有类似的专题讨论会，由此足以看 出国际学术界对这一问题的重视。表1 2 1 给出一些早期国际方面视频检索系统 及其研究者的情况，系统名栏内的括号为主要特点【2 j 。 i 序号研究者所属单位 系统名参考文献 1a b d e l m o t t a b l c bm p h i l i p s c o n i v - s 1 7 2 c h a n g s e c o l u m b i au w e b s e e kv i d e o q【2 3 3d o e l t l a l l l ld u o f m a r y l a n dm e r i t ，v i d e o t r a i l s 3 4 4e n 西a n dp _ b e u c o r ei b r o w s ef 2 8 5j a i n r v i m g e v i r a g ef 2 9 1 6k a n a d et c a m e g i c m e l l o nu i n f o r m e a l i a 5 0 1 7l i e n h a r t u o f m a n n h e i mm o c a ，v a b s t r a c t 3 5 8 s a w h n e yh s a m o f f ( m o s a i c i n g ) 3 2 】 9 s h a h r a r a yb # 西8 汪 ( p i c t o r i a lt r a n s c r i p i s )【4 4 】 1 0s m 0 1 i a r s f u i i x e r o x f 3 d m i c o n s ) 4 6 】 1 l s u b r a m a n i a nv s u o f m a r y l a n dv i g s ，m a c s f 3 1 1 1 2y e o b l i b m ( y o r k t o w nh t s )( s c e n et r a n s i t i o ng r a p h ) 5 4 比较哥伦比亚大学的v i s u a l s e e k 系统和w e b s e e k ，其中，v i s u a l s e e k 是 视觉特征搜索引擎，w e b s e e k 是面向w e b 的文本图像搜索引擎：加州大学 圣迭哥分校v i r a g e 系统，支持基于颜色、颜色布局、纹理、结构等视觉信息的 检索，支持上述几种原子查询的组合查询，用户能根据自己的意愿调整某个查询 权重；还有西门子公司的c a r a t 数字多媒体档案系统等。当前国内在这一领域 的研究也相当活跃。近年在各种会议、干u 物上发表的论文达百余篇，大批的研究 人员围绕此课题开展先期探索研究。国内方面，清华大学计算机系最近研制了基 于内容的图像检索系统i m g r e t r 和视频检索系统v i d e o b a s e ，北航计算机系也在 基于数据挖掘的图像特征推广、支持空域可分级的图像编码方面进行了有效的研 究。 但基于内容的视频检索技术由于涉及的理论和技术众多，加之视频数据本身 北京工业大学工学硕士学位论文 的特点，目前仍处于实验室研究及成果推广阶段。 1 2 4 课题研究的内容及难点 本文针对基于内容的视频检索的关键技术开展研究工作。主要讨论如何利用 并改进已有的研究成果来设计实现一个可以实际应用的视频检索系统。 1 2 4 1 课题研究的难点 本文研究面向实际应用的视频检索系统所需要的关键技术。一个能够实际应 用的视频检索系统包含一个完整的平台架构，以及在此平台基础上实现的检索算 法。针对这两方面，课题研究的主要难点如下： 视频检索方面：以高效、低复杂度为研究目的，从视频特征提取和相似性匹 配两个关键方面进行研究。 一如何有效的计算视频指纹，提取后的视频指纹中包含足够多的信息量， 以便区分不同视频，同时兼顾视频特征的低复杂度特性，从而减少计算 量和抑制噪声。 一如何有效的解决视频编辑和视频传输过程中信道噪声所引入的大范围亮 度漂移和视频问强干扰，及视频中跳帧等现象所导致的检索算法鲁棒性 差的问题。 如何满足新一代的视频检索技术对于检索算法的新需求：第一，算法应 实时计算；第二，算法应当具有鲁棒性以适应传输信道中存在的噪声干 扰，以及视频编辑所造成的相同内容视频具有不同时间跨度的干扰，例 如：常见的慢镜头等情况。 平台架构方面：以通用性、可扩展性为研究目的，如何实现独立子平台和服 务器的开放式分布系统，并可作为构架视频检索系统的基础。 1 2 4 2 课题研究的内容 如前所述，由于整个检索系统的效率和性能主要取决于特征的提取和相似性 匹配算法的优劣，本文针对这两部分算法开展研究工作并且讨论了检索系统的设 计与实现过程。具体内容如下： 特征选取算法。特征选取主要目的是选择合适的视频特征来代表视频片 段，有效的提取出视频片断中所含有的空间信息和时间信息。对于选择 的视频特征不仅要求计算简单，数据量小，同时还需要包含足够的信息 量以便区分其它视频。本文通过对目前常用的视频特征的分析、比较， 并兼顾上述对于视频特征的要求，采用“视频指纹”1 2 0 ( v i d e o 4 第1 章绪论 f i n g e r p r i n t s ，是一种新型的视频特征，具体指视频帧中某一特征随时间 变化的值的集合。) 作为视频检索特征。并对视频指纹的提取算法展开 研究，提出了一种新的利用信息增益来自动选择视频分割方案的视频指 纹自适应改进算法，用以解决视频指纹提取依赖于手动确定关键参数的 问题，进一步提高视频指纹的计算效率。 特征匹配算法。对于不同的视频特征需要实现相应的视频比对算法。在 设计算法的过程中，需要考虑算法本身的计算效率以及视频特征的特 性。针对视频编辑和传输过程中引入的噪声对视频特征产生的不良影 响，本文提出了相应的匹配算法，保证算法具有足够的鲁棒性并能在实 际系统中得到应用。 视频检索系统。本文建立了一个视频检索平台。文中充分利用视频指纹 的特点，设计并开发了基于v c 平台构造的视频指纹的提取算法模块、 相似性匹配算法模块。算法与基于j 2 e e 平台的实验结果展示系统结合 来实现一个完整的视频检索系统。 1 3 论文的结构安排 论文其余各章内容安排如下： 第二章，视频检索的关键技术及发展现状。主要回顾了现有视频检索中的关 键技术，就其发展现状进行综合评述，并针对视频检索的需求，对不同算法进行 比较。 第三章，视频指纹的定义与提取。介绍了视频指纹的基本概念和提取算法， 在分析原有算法不足的基础上，对其中视频指纹提取部分的算法提出了改进，采 用了一种新的利用信息增益来自动选择视频分割方案的视频指纹自适应改进算 法。 第四章，基于视频指纹的匹配算法。介绍了原有的基于视频指纹特征的匹配 算法，针对其抗干扰能力差等不足，提出了两种改进算法：变化量匹配算法和基 于动态时间规划算法的新的视频指纹匹配算法。针对不同情况，有效的处理了视 频编辑和传输、存储过程中引入的干扰。 第五章，基于视频指纹的视频检索系统设计。介绍了完整检索系统的实现流 程、模块划分、模块功能和实现技术要点。 第六章，结论和今后工作展望。对全文进行了总结，并对本文涉及到的技术 领域进行了展望。 北京工业丈学工学硕士学位论文 论文最后列出了攻读硕士学位期间参与的项目、发表的学术论文、专利、软 件著作权和所获奖励，最后是致谢、参考文献。 6 ；，。 ! ! 塞三些查兰堡圭耋篁篁兰 第2 章视频检索的关键技术及研究现状 2 1 引言 视频检索作为当前研究领域的热点之一，吸引了大量专家学者开展相关研究 工作。本章针对建立一个视频检索系统所需的四个主要方面的已有研究工作和涉 及的具体内容展开讨论，最后介绍了常用的几种检索系统性能评价指标和评价准 则。上述四个主要方面分别是：对视频信息的结构化即视频分割、场景构建和关 键帧提取；对结构化视频提取视频特征；对视频特征进行相似性匹配：视频检索 系统的用户接口设计【3 0 1 。后续的每个小节分别对应一方面内容的进行具体讨论。 2 2 视频结构化 视频的结构化包含三个方面：镜头分割、关键帧提取以及场景构造 3 1 。 2 2 1 镜头分割 镜头分割又称为镜头边界检测，或场景转换检测( s c e n ec h a n g ed e t e c t i o n ， s c d ) ，是视频检索的基础【3 】。大部分视频是通过编辑，由一个个镜头连接而成的， 所以基于内容的视频检索处理，首先要把视频自动地分割为镜头，以作为基本的 处理单元，这个过程即镜头边界的检测，是实现基于内容视频检索的第一步。 镜头分割算法可分为压缩域和非压缩域两类。 在非压缩域，镜头切换时，视频数据将发生一系列的变化，表现在颜色差异 突然增大、新旧边缘的距离、对象形状的变化和运动的不连续性等方面。一般而 言，同一个镜头内的各帧之间差异较小，而不同镜头的帧间差异较大。镜头边界 检测的目的就是寻找这些变化的规律，即寻找帧间差异较大的位置。非压缩域的 片段检测算法就是直接从视频中选择能反映内容变化的特征量，比较相邻两帧的 差异，然后选取适当的阈值，当帧间差异大于阈值时，就认为镜头产生切换【4 。 镜头边界检测方法可分为模板匹配法、直方图法、基于边缘的方法和基于模型的 方法等4 种嘲。 7 第2 章视频检索的关键技术厦研究现状 1 ) 模板匹配法 模板匹配法以两帧对应像素差的绝对值的和作为帧间差，其计算公式如下： i m 。y n d ( j 。，j ，) = 帆训) - i 砖，y ) l ( 2 ，1 ) t 。0 y * 0 其中，i i 表示第f 帧视频，d ( j r ，i j ) 是i i i j 的帧间差，i i ( x , y ) 为第f 帧( x ，y ) 位置的像素值，m 和n 为帧的宽度和高度。这种方法比较前后两帧对应像素之 间的变化，如果变化超出一个阈值t ，则认为有镜头的切换。 模板匹配法的缺点是对噪声和镜头或物体运动非常敏感，因为它严格地局限 于像素的位置。噪声和物体运动都会使帧间差增大，从而导致错误的场景转换检 测。对此一些研究人员提出了一种改进的方法，即把各帧分为8 x 8 像素的小块， 并对每个块取平均，再用这个平均值对前后帧的对应小块进行比较，这种方法可 以去掉图像中的一些噪声，并对小的物体运动和镜头运动起到补偿作用。 直方霉法 直方图法是使用的最多的计算帧问差的方法，它不考虑像素的位置信息，而 是用像素的亮度和色彩的统计值，因而抗干扰能力比模板匹配强。许多流行的算 法均咀直方图差异作为帧间差异的度量，但对渐变镜头的检测效果并不理想。 其基本原理是将颜色空间分为个个离散的颜色小区间，然后计算落入每个 小区间的像素数目。设颜色空间分为n 个区间，爿* 是第i 帧落入第k 个颜色空 间的像素数目。帧闻差可用下面公式表示： d ( i i ，l ) = 旧。一日| i ( 2 2 ) 颜色壹方鼠法的缺点是，有时会漏掉场景变换，圆为两幅图像可能有完全不 同的结构，但其颜色直方图却很接近。与颜色直方图法相似的另一种计算帧闻差 的方法是x 2 直方图法，据介绍这种方法用于镜头转换，检铡效果要好于上述两 种方法。两幄图像之差计算公式如下： 崛，啪：窆掣 ( 2 3 ) 3 ) 基于边缘的方法 这种镜头边晃的检测方法是根据边缘特征计算的，它的基本思想是“在发生 镜头转换时，新出现的边缘应远离旧边缘的位置，同样旧边缘消失的位置应远离 北京工业大学硕士学位论文 新边缘的位置”。 具体计算过程如下： 首先提取前后两帧视频图像or 和。，的边缘图也碍口e i ”，两帧视频图像之间的 差异为：d , y 2 m a x ( d m ，d 一) ，其中，d i 是进入像素( 新出现的远离已有边缘的 像素点) 所占的比例，4 0 v l 是退出像素( 新消失的远离新边缘的像素点) 所占的比 例，其中叱2 p t p m ，n 为e i + t 中离e ，中最近边缘像素点的距离大于r 的边缘像 素点的总数，p ，为e i “中的边缘像素点总数；d w2 p ：，p 一，p 2 为e 中离e “中 最近边缘像素点的距离大于r 的边缘像素点的总数，p 一为也，中的边缘像素点总 数。如果d 形大于某一个设定的阈值t ，则认为出现了镜头的切变。 4 ) 基于模型的方法 上述方法都是利用帧间差自下而上地进行镜头边界的检测，它对于突变检测 可以取得较好的效果，但是对于渐变则有一定的困难，因为它在很大程度上忽略 了渐变切换中帧与帧之间结构上的相关性。而基于摸型的方法是利用对镜头编辑 的先验知识，对各种镜头切变建立一定的数学模型，自顶向下地进行镜头切换的 检测，因此这种方法对镜头渐变的检测往往能取得好的效果。 h a m p a p u r 等人通过对视频制作过程的研究，找到了一种可用于镜头边界检 测的视频编辑模型( v i d e oe d i tm o d e l ) 。例如，一个典型的镜头渐变模型可表示为： f ( x ，y ，f ) = c t ( t ) g l ( x y ，t ) + f l ( t ) 9 2 ( x ，y ，力( 2 4 ) 其中，g l ( 毛y , t ) 是即将逐渐消失的镜头：占2 ( x ，y ，f ) 是即将出现的镜头，如 果镜头内无运动或运动很小，即可分别记为函( 石，弘t ) 4g ，( z ，_ y ) ， 9 2 ( 2 ，y ，f ) “9 2 ( x ，) ，) 。a ( c ) 和卢( f ) 都是时间的线性函数；假设渐变转换的持续时 间为0 到t 。对于慢转换，它们可表示为： f 1 ， 口( f ) = 1 一t t ， l0 ， f l ( t ) = 1 一口( f ) 对于淡出，则g ：2 0 ；对于淡入，则g o 。在变化的过程中，每幅图 像上所有得像素都以线性规律变化。可定义如下的常量图c i ( c o n s t a n ti m a g e ) ： 9 2r 一 枷汀 第2 章视频检索的关键技术及研究现状 昙厂( x , y , t ) a = ( x ，y ，0 = 旦芦_ ( 2 6 ) 假设镜头无运动地线性淡出，即口( ) = 1 - t r ， ( ) 2o ， 9 1 ( z ，y ，t ) “g l ( x ，y ) ，贝u 可以得至0 ： 。z，y，。，：兰笺!兰!攀：一亍1c= 口c 幻c z ， ( z ，) ，r ) = 坚i i i 云i z 。j j j 璺l 一= 一亍口o ) ( 2 7 ) 这样，对于一定的时间t ，得到所有像素均为常数的常量图c i ，检测渐变只 需检测模型的常量图。对于给定的模型，一旦检测到常量图，则认为有一个渐变 过程。 只要模型建立准确，基于模型的方法对于渐变检测往往能得到较好的效果， 但是需要对每种切换类型建立模型，而且建模过程比较复杂。 作为视频检索“前向通道”，视频镜头边界检测的结果将对整个视频检索结 果产生直接的影响。而上述这几类检测方法，对于视频中存在的连续几帧的强于 扰情况仍不能克服，易出现误检，对视频检索的结果造成很大影响。 压缩域中的基于内容的视频检索与非压缩域算法思路大体一致，只是压缩域 中的算法利用了压缩域数据自身特有的特点。b l ，y e o 提出使用所有类型图中的 d c 数据，恢复成缩微图，比较成功地解决了镜头切变检测问题，但b 帧和p 帧 的d c 系数不能直接获得，所以恢复所有的d c 系数计算量较大【5 4 1 。j h m e n g 提出利用m p e g 数据流中运动向量判断切交点，进而利用渐变的数学模型，通 过检测图像序列方差曲线形状( 抛物线) 检测渐变。该算法相比于b 。l y e o 的方法 提高了计算速度，对切变检测比较准确，但对渐变的检测准确性仍然没有明显的 提高，而且计算量较大，易受噪声干扰1 5 4 1 。 2 2 2 关键帧提取 关键帧是用于描述一个镜头的关键图像帧。其作用在于，一方面，反映一个 镜头的主要内容；另一方面，将其反跌在图形用户接口上，可帮助用户更加直观 的观看返回结果。 关键帧的选取一方面必须能够反映镜头中的主要事件，因而描述应尽可能准 确完全，另一方面，为便于管理，数据量应尽可能小，且计算不宜太复杂。 关键帧的选取方法很多，比较经典的有帧平均法和直方图平均法。 1 0 北京工业大学硕士学位论文 1 ) 帧平均法：是从镜头中计算所有帧在某个位置上像素值的平均值，然后将镜 头中该点位置的像素值最接近平均值的帧作为关键帧。 直方图平均法：是将镜头中所有帧的统计直方图取平均然后选择与该平均 直方图最接近的帧作为关键帧。 这些方法的优点是计算比较简单，所选取的帧具有平均代表意义。缺点是， 从一个镜头中选取一个关键帧，无法描述有多个物体运动的镜头。一般说来，从 镜头中选取固定数目的关键帧不是一种好的方法，因为这种方法对于变化很少的 镜头选取的关键帧过多，而对于运动较多的镜头，用一两个关键帧又无法充分描 述【6 】。 有人依据帧间的显著变化来选择多个关键帧。他们计算前一个关键帧与剩余 帧之差，如果差值大于某一个阈值，则再选取一个关键帧 蚰 。这种方法可以根据 镜头内容的变化程度选择相应数目的关键帧，但是所选取的帧不一定具有代表意 义，而且在有镜头运动时，容易选取过多的关键帧。 w o l f 等人通过光流分析( o p t i c a lf l o wa n a l y s i s ) 来选取关键帧。首先，计算镜 头中的运动量，在运动量取局部最小值处选取关键帧，它反映了视频数据中的静 止，往往表示一种强调的实际情况【5 4 1 。这种方法首先用h o r n s c h u n c k 法计算光 流，对每个像素光流分量的模求和，作为第k 帧的运动量肘( 刖，即： ( 七) = 恢( f ，女) + h ( f ，j ，七) f ( 2 8 ) i 其中0 工( f ，j , k ) 是帧k 内像素( f ) 光流的x 分量，g ( ，j , k ) 是帧k 内像素 ( f ，j ) 光流的y 分量。然后寻找m ( 1 j ) 的局部最小值。从k ：0 开始，扫描m ( 庀) t 曲线，找到两个局部最大值吖( t ) 和m ( 七：) ，m ( k o 的值与肠( t ) 的值至少相差 p ( 由经验设定) ，如果m ( 屯) = m i n m ( 七) ，k ， 豇 t 而在另一些实验中 n t ，那么根据公式( 2 1 2 ) ，某些实验结果就会比其它实验结果被赋予较大的 权限。为了避免这个问题，以在一致条件下比较不同的技术，需要提取比相 似视频的总数更多的视频，即总要取n t ，这样不仅可以确定是否所有相似 视频都提取出来了，还可以确定这些视频的排序是否正确。 4 检索率( r e t r i e v i n gr a t i o ) 对一个给定的查询样例视频，所提取的相似视频的数量应该是检索技术 参数的函数。这样定义一个称为检索率的优度准则i 孔。对一个特定的检索技 术，当给定一个查询样例视频进行实验时可给定一组检索技术参数，检索率 可由下式计算： 砺( n ，t ) = 百n l j i = l 厶，mj = 1 氘，k ( 2 1 3 ) 1 7 第2 章视频检索的关键技术及研究现状 其中m 是查询视频的总数，k 是参数集合的总数，n 和t 的含义与检 索效率中的相同，这样定义的检索率与所提取视频的总数t 是有关的。 检索技术的性能依赖于不同的检索参数 2 1 ，对于基于彩色直方图的技 术，它们的性能受到彩色量化间隔的影响，所以需要比较一组间隔的情况。 对于基于矩的技术。3 个权重的相对值确定了检索的性能。所以需要比较一 组权重的情况。对于用k 个设置查询一幅图像的情况，其平均检索率可由 下式计算： 算 啾肌，= 壶姜晋= 去缸 i 叱一 亿 最后，对用k 个设置查询m 个视频的情况，其平均检索率可由下式计 2 7 小结 呷，= 击善盱志善塾 ( 2 1 5 ) 本章详细讨论了建立一个视频检索系统所涉及的关键技术的当前研究现状， 并给出了评价视频检索系统的重要准则。到目前为止，视频检索系统的相关技术 仍然在发展阶段，已有的检索系统往往针对特定应用来进行设计。本文的后续章 节将讨论如何基于视频指纹这一视频特征来实现快速、高效的视频检索算法。 北京工业大学硕士学位论文 第3 章视频指纹的定义和提取算法 3 1 引言 高效视频特征的提取是影响视频检索系统性能的关键因素之一。由于实际的 视频检索内容往往需要实时处理通过信道传输的视频信号，这要求被提取的视频 特征能够进行快速实时的计算，同时要求对传输过程中引入的干扰具有足够的鲁 棒性。 本章主要讨论一种新型的视频特征视频指纹。它是一种已被m p e g 7 采 纳的视频特征【2 0 1 ，由于简单有效，可以满足快速计算要求，在一定范围内得到了 应用。 虽然原有的基于视频指纹的检索算法可以处理很多种情况，但在实际应用过 程中，视频指纹会受到传输过程中的强信号干扰影响，同时提取视频指纹需要的 视频分割方案需要通过人工实验确定，这在很大程度上限制了视频指纹的进一步 应用。 本章首先讨论了视频指纹的定义。之后给出了传统的视频指纹计算方法。在 此基础上，本章给出了一种新的利用信息增益来自动选择视频分割方案的视频指 纹自适应改进算法，来解决视频指纹提取依赖于手动确定关键参数的问题。 3 2 视频指纹的定义 视频可以认为是由一系列静态图像按一定的时间顺序组成的。它不仅含有空 间信息，还含有大量的时间信息，因此视频具有数据量巨大，结构复杂等特点。 目前常用于检索的视频特征包括关键帧、摄像机的运动参数、视频字幕等等，这 些特征有的侧重于提取视频的空间信息，有的侧重于提取时间信息，有的计算算 法复杂，且应用范围存在局限，影响了技术的实用性。 早稻田大学的研究人员提出了一种提取和匹配算法简单的，数据量小，充分 体现视频的时间、空间两方面信息的视频特征视频指纹( v i d e of i n g e r p r i n t s ) 2 0 l ，从而扩展单一视频特征的应用范围，降低视频特征的提取算法复杂