（计算机系统结构专业论文）视频镜头边界检测和关键帧提取技术研究.pdf

摘要 计算机、网络技术和数字视频技术的不断发展，使得视频数据快速增长，如 何对大量的视频数据进行有效的组织、管理和检索成为视频检索研究领域的热点 问题。 本文主要研究基于内容的视频检索中两个关键技术：镜头边界检测和关键帧 提取技术。首先，本文提出了一种基于联合直方图的镜头边界检测算法。该算法 利用相邻帧帧间联合直方图关于对角线的对称度在同一镜头内很高，而在镜头切 换处很低的特性，定义相邻帧的相似度，通过对相似度做差分突出突变特征，结 合双向搜索的闪光检测法消除闪光对突变检测的影响；同时引入有限自动机提高 渐变检测的鲁棒性，并将突变和渐变检测紧密结合，获得了较好的检测效果。其 次，把联合直方图应用到关键帧提取中，提出了基于联合直方图的关键帧提取算 法。该算法利用联合直方图的对称性定义帧间相异度，对相异度作累积生成累积 曲线，结合检测平面曲线上大斜率点的方法，对视频帧序列分类，从关键类中提 取关键帧，这样提取的关键帧具有动态特点。实验表明，该算法具有较高的压缩 率，并且提取的关键帧较好地代表了视频内容。 关键词：视频检索联合直方图镜头边界检测闪光检测关键帧提取 a b s t r a c t t h ea d v a n c e si nc o m p u t e r , n e t w o r ka n dd i g i t a lv i d e ot e c h n o l o g yh a v er e s u l t e di n a ne x p l o s i o no fd i g i t a lv i d e od a t ai nt h el a s tf e wy e a r s t h eo r g a n i z a t i o n ， s u m m a r i z a t i o na n dr e t r i e v a lo fv i d e od a t ah a v eb e c o m et h ef o c u sr e s e a r c h i nt h i st h e s i s ，w ef o c u so nt h et w ob a s i ct e c h n o l o g i e so fc o n t e n d b a s e dv i d e o r e t r i e v a l ，w h i c ha r es h o tb o u n d a r yd e t e c t i o na n dk e y f r a m ee x t r a c t i o n f i r s t l y , an e w a l g o r i t h mb a s e do nt h ec o - h i s t o g r a mb e t w e e n t w oc o n s e c u t i v ef r a m e si sp r e s e n t e d i n t h ea l g o r i t h m ，t h es i m i l a r i t yi sd e f i n e db a s e do nt h ec o h i s t o g r a ms y m m e t r yw h i c hi s l l i 曲i nt h es a m es h o t ，b u tl o wi nas h o tt r a n s i t i o n t h es i m i l a r i t ye f f e c t i v e l yr e v e a l st h e t r a n s i t i o nc h a r a c t e r i s t i c s t h ed i f f e r e n c eo fs i m i l a r i t i e si su s e dt oe n h a n c et h ea b r u p t t r a n s i t i o nf e a t u r e s ，a n da ne f f e c t i v eb i d i r e c t i o n a ls e a r c h i n gf l a s h l i g h td e t e c t i o n a p p r o a c ht od i s t i n g u i s hf l a s h l i g h t s c e n e sf r o ma b r u p tt r a n s i t i o n s af i n i t e s t a t e a u t o m a t ai su s e dt o i m p r o v et h e r o b u s t n e s si n d e t e c t i n gg r a d u a l t r a n s i t i o n s e x p e r i m e n tr e s u l t ss h o wag o o dp e r f o r m a n c ei nr e c a l la n dp r e c i s i o n s e c o n d l y , an o v e l a p p r o a c hb a s e do nc o - h i s t o g r a mt oe x t r a c tk e y f r a m ei sp r o p o s e d t h ea p p r o a c hu s e s t h es y m m e t r yo fc o - h i s t o g r a mb e t w e e nc o n s e c u t i v ef r a m e st od e f i n et h ed i s s i m i l a r i t y , a n dc l a s s i f i e sf r a m e sb yd e t e c t i n gt h eh i g hs l o p ep o i n t si nac u m u l a t ec u r v eo ft h e d i s s i m i l a r i t y f i n a l l y , k e yf r a m e sa r ed y n a m i c a l l ye x t r a c t e df r o mk e yc l a s s e s t h e e x p e r i m e n tr e s u l t ss h o wt h a tt h ea p p r o a c ha c h i e v e sah i 【g hc o m p r e s s i o nr a t ea n da n e f f i c i e n ts u m m a z a t i o n k e y w o r d ：v i d e or e t r i e v a lc o h i s t o g r a m s h o tb o u n d a r yd e t e c t i o n f l a s h l i g h td e t e c t i o nk e y - f r a m ee x t r a c t i o n 西安电子科技大学 学位论文独立性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：耋圣蟹日期知& 乡、石 日期。弦妖多、扫 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名：盘盔 导师签名：衄越乓 日期如g 型 日期_ 珥 第一章绪论 第一章绪论 从人类信息交流方式的发展历程来看，最初的方式是声音和语言，后来有了 文字和图形，而到了现代的文明时代，照相机和摄像机的出现，尤其是数字化产 品的出现，使得图像和视频成了广受欢迎的信息交流方式。俗语有云，“百闻不如 一见，有研究表明，人类获得的信息有8 0 来自视觉。而视频信息具有直观、 形象、生动的特点，使之成为人类生活中最主要的信息交流方式之一。 近年来，随着计算机技术、网络技术和多媒体技术的迅速发展和信息需求的 不断增长，视频数据在各个方面的应用越来越普遍，并且每天都有大量新的视频 不断产生，从而，对其进行有效的组织管理和快速的检索引起了人们的重视。传 统和现有的检索方式只能完成基于纯文字的检索任务，而对于视频数据就显得力 不从心，这使得信息检索面临着很大挑战。例如，足球教学人员需要查找足球比 赛中的射门动作，在没有行之有效的视频信息检索方法时，就需要有经验的资料 员到仓库中逐一查找视频数据，花上数小时甚至更长时间，通过快进或快退，人 工来回浏览，查找和选定所需镜头，工作量很大，且效率很低。因此，基于内容 的视频检索技术就显得越来越重要。 1 1 研究背景和意义 早在1 9 5 1 年，“信息检索”就已经出现，它用来描述信息用户将一个对信息 的要求转换为一个参考集合的过程【l 】，在此基础上，用户将有可能快速地搜索并 提取出相关信息。可以说，最初的“信息检索”主要是对纯文本内容进行操作， 而未考虑图像、声音和视频等表现形式的多媒体数据。随着时代的进步，图像、 视频和音频等多媒体信息大量涌现，对这些海量的并且包含大量非结构化信息的 数据如何组织、表达、管理、查询和检索成为了人们迫切的需求。近年来，基于 内容的视频与图像数据库检索技术已成为一个研究热点【2 训，也成为未来信息高速 公路、数字图书馆等项目中的关键技术。视频检索的应用十分广泛，如新闻视频 信息的检索、体育运动节目的检索、网络教育视频教学资源的检索，等等。一旦 视频检索技术取得关键性的突破，更大的市场应用便会接踵而来。 视觉信息检索是信息技术的一个新的重要研究内容，其目的在于从视觉数据 库中快速提取与一个查询相关的图像或图像序列【5 】。事实上，视频是运动的图像， 视频属于图像的范畴，而图像和视频的检索同属于视觉信息检索的范畴。简单地 讲，视频检索就是要从大量的视频数据中找到所需的视频片段。目前，市场上视 2 视频镜头边界检测和关键帧提取技术研究 频检索的应用产品还并不能让人完全满意。w w w 站点上对视频信息进行寻找时， 一般的接口采用基于关键字的查询方式，或者采用类似于门户站点的基于层次分 类的浏览查找方式。其搜索结果的呈现方式一般是在一个播放窗口中进行线性的 播放浏览，并提供一定程度的类似v c r ( v i d e oc a s s e t t er e c o r d e r ) 的顺序的快进 快退功能。这种基于关键字的查询方式是人们最为熟悉的因特网上的信息查询方 式，其优点在于对查询请求描述简单，查询响应快，可以表达复杂的高级语义等。 然而，它也存在一些严重的缺陷。首先，人们对视频数据添加文本型的内容描述 数据是一项非常耗时的工作。因为操作人员将对大量待标注的视频内容进行细致 地观看和理解，并从中抽取出合适的供检索用的关键字。其次产生的描述文字往 往带有很强的主观性，往往既不准确，也不完整，这使得当用户键入一个待查找 目标的关键字时，可能关键字提取者采用另一近义词描述待查找目标的关键字， 或没有使用任何关键字来刻画用户键入的关键字所描述的有关方面的属性，导致 内容的漏检、误检等。 基于内容的视频检索技术就是为了解决基于关键字检索存在的问题，它能够 根据视频的语义特征进行检索，以提取出与特征相符或相似的视频数据。当前， 基于内容的视频检索的主要工作集中在对视频数据进行镜头边界检测( 或者叫镜 头分割) 、关键帧选取和场景检测上。为实现基于内容的视频检索，需要综合利用 许多技术和运用多种类型的知识。它范围广泛，从数学与计算机理论基础角度而 言，涉及人工智能、最优化理论、统计方法学、计算视觉和模式识别、图像处理 与分析、信号处理、数据库、计算机网络等学科，此外，还需要从心理学、美学 和人体工程学、认知科学、人工智能、数据库管理系统、人机交互和信息检索等 领域引入新的媒体数据表示和数据模型，进而设计出可靠的、有效的检索算法和 系统结构以及友好的人机界面【6 】【7 】。 1 2 基于内容的视频检索 1 2 1 基于内容的视频检索的发展 “基于内容的图像检索( c o n t e n t b a s e di m a g er e t r i e v a l ，c b i r ) 一词于1 9 9 2 年开始在国际上使用1 8 j ，国内也很早就展开了相关研究【9 】。现在，这方面的研究 和应用得到了长足发展。同时“基于内容的视频检索( 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 ) ”的研究也已开始。有学者指出，从视觉信息检索系统的发展来看，可以 分为两代【l 。 第一代视觉信息检索系统是基于关键字的，通过字符串属性访问图像和视频 【l0 1 。第一代视觉信息检索系统中，用字符串表达与内容无关的元数据，使用如相 第一章绪论 关模型、框架模型、面向目标的模型等表达方案。关键字的比较适合于识别认证， 如图像或视频中的有意义实体( 如人、物) ，前后相关的概念( 眼、鼻) ，或场景 表达( 如教室、风景) 。检索可以基于在文字领域工作的传统的搜索引擎，使用传 统的查询语言( 如s q l ) ，或全文检索。 图1 1 第一代视觉信息检索系统的工作框图 图1 1 是一个典型的第一代视觉信息检索系统的工作框图。注解员在离线状 态下通过一定的方法( 多为手工方式) 对数据库内容进行注解标引，提供出在线 应用时所需的索引。用户则借助文字查询方法利用搜索引擎进入索引库进行匹配 检索，由系统返回可视化的结果给用户，用户可以借助相关反馈开始新一轮的查 询。 对于视频信息，第一代系统借助对视频进行一定形式的编号，即对标签进行 检索，较为简单。但是，它有很多缺点。首先，文字标签难以完整地表达视频的 丰富内容，基于关键字的检索无法满足用户的检索要求；其次，特定的标签只适 合特定的查询要求；再次，这些标签是靠观察者加上去的，因此受主观因素的影 响大，不同的观察者或同一个观察者在不同条件下对同一视频内容可能给出不同 的描述，这样就没有统一标准，不客观；最后，手工注解视频太过耗时，换言之， 这样的方式几乎不可能完成任纠1 1j 。 事实上，人们总是希望可以直接检索到一段包括特定信息的视频片段，比如 篮球比赛中的精彩进球镜头、风景片中的日出日落和战争片中的宏大场面等。也 就是说，重要的是视觉内容。第二代视觉信息检索系统支持基于视觉内容的检索， 对视觉信息的访问不仅在概念层利用关键字进行( 与文字领域类似) ，而且也在感 知层利用对视觉内容的客观测量和合适的相似模型进行，如图1 2 所示。一方面， 注解员可以通过一定的方法对数据库进行注解，另一方面，系统也可以自动地对 数据库图像或视频进行分析，提取特征，从而提供在线应用时所需的( 多维) 索 引。而用户则可以利用文字查询的方法，也可以利用视觉浏览和视觉范例查询借 助搜索引擎进入索引来检索，返回的结果可以可视化地显示给用户，使用户能够 借助相关反馈开始新一轮的查询。 4 视频镜头边界检测和关键帧提取技术研究 图1 2 第二代视觉信息检索系统的工作框图 那么，到底什么是基于内容的视频检索? 基于内容的视频信息检索就是借助 对视频从低层到高层进行处理、分析和理解的过程获取其内容并根据内容进行检 索。它提供这样一种算法，即在没有人工干预的条件下，自动地提取并描述视频 的特征和内容。 为实现基于内容的视频检索，就应当把视频文件分割为由镜头和场景组成的 内容单元，并从中提取出关键帧作为索引项。因此，基于内容的视频检索的核心 在于研究出新的技术自动地分析视频并鉴别出有意义的复合结构，以提取和表达 视频的内容特征【l 。目前，基于内容的视频检索研究，除了识别和描述图像的颜 色、纹理、形状和空间关系外，主要的研究集中在视频镜头边界检测、特征提取 和描述( 包括视觉特征、颜色、纹理和形状以及运动信息和对象信息等) 、关键帧 提取和镜头聚类等方面。 基于内容的视频检索中的视频结构化分析技术，就是要从所有的帧中提取主 要内容，并从下至上地对视频内容进行结构化描述，并建立索引。为此，需要对 视频进行视频镜头边界检测( 镜头分割) 、特征提取和视频内容的组织。 第一章绪论 图1 3 基于内容的视频检索处理主要过程 图1 3 描述了基于内容的视频检索处理的主要过程。视频流首先被分割为若 干镜头，对每个镜头进行运动分析，可以获得运动特征；在每个镜头上提取关键 帧描述镜头的主要内容，并对关键帧做特征提取，生成关键帧特征；对镜头进行 聚类，生成场景故事单元，对其做场景分析生成高层的语义描述。最后，用户可 以对已具有索引的和结构化的视频进行检索和浏览。可以看到，对视频的镜头边 界检测是其后续工作的基础，而关键帧可以比较完整地表达视频内容，同时在很 大程度上压缩视频的数据量，提高检索的效率。 1 2 1 基于内容的视频检索的特点 与基于关键字的检索相比，基于内容的视频检索融合了图像分析与理解、计 算视觉、模式识别等领域的知识和技术，具有如下特点【1 2 - 1 4 ： ( 1 ) 从视频数据中提取信息线索。基于内容的检索突破了传统的基于表达式 检索的局限，直接对视频内容进行分析，抽取特征和语义，利用这些内容特征建 立索引，进行检索。 ( 2 ) 提取的特征丰富多样。包括视频图像的颜色、纹理、形状、位置、空间 关系，视频的声音及字幕信息等。 ( 3 ) 基于内容的检索实质是一种近似匹配。由于对内容的表示不是一种精确 6 视频镜头边界检测和关键帧提取技术研究 描述，因此，c b v r 采用相似性匹配的方法逐步求精，以获得查询结果，即不断 减小查询结果的范围，直到定位到要求的目标，是一个迭代过程。这一点与常规 数据库检索的精确匹配方法有明显的不同。 ( 4 ) 人机交互。特征提取和索引的建立可由计算机自动实现，避免了人工描 述的主观性，同时大大减少了工作量。但相似性度量与人的主观感受有关，因此， 常需要采用人机交互的方法，学习人的主观相似度感受。 ( 5 ) 大型视频数据库的快速检索。实际的视频数据库数据量巨大，因此要求 c b v r 技术也像常规的信息检索技术一样，能快速实现对大型数据库的检索。 1 3 国内外的应用及研究现状 目前，网络上可用的视频搜索引擎都是基于文本关键字的，包括： ( 1 ) a l l t h e w e b ( h t t p ：w w w a l l t h e w e b c o r n ) 正如其名，它搜索的范围广泛， 包括网页、新闻、图片、视频和音频等内容。 ( 2 ) a l t a v i s t a ( h t t p ：w w w a l t a v i s t a t o m ) 可以搜索a l t a v i s t a 的所有图像、音频 和视频。对于视频搜索，它提供更为详细的文件格式选项，如m p e g 、a v i 、r e a l 和f l a s h 等，以提高检索效率。 ( 3 ) l y c o sp i c t u r e sa n ds o u n d s ( h t t p ：m u l t i m e d i a 1 y c o s c o r n ) l y c o s 多媒体搜索 引擎可以搜索网上已经授权使用的图像和网页图像资料，还提供音频和视频剪辑 的搜索。 ( 4 ) g o o g l ev i d e o ( h t t p ：v i d e o g o o g l e c o r n ) 它对视频进行分类，包括热门视 频t o p l 0 0 、 幽默视频、音乐视频、体育视频和动画视频，可以根据用户对内容 类型的不同需求进行检索。 因为基于内容的视频检索是近年来多媒体技术研究中的一个热点，国内外的 研究机构和个人多年来对其投入了很大的精力，已经开发出了具有代表意义的原 型系统，包括： ( 1 ) q b i c 系统【1 5 1 ：i m ba l m a d e n 研究中心研发的q b i c ( q u e r yb yi m a g e c o n t e n t ) 系统是基于内容检索系统的典型代表。允许用户使用例子图像、构建的 草图和简图、选择的颜色和纹理模式、镜头和目标运动及其它图形信息等，对大 型图像和视频数据库进行查询。该系统利用统计直方图和灰度差的方法相结合来 做镜头检测，利用基于图像拼接技术的方法，以2 * 2 的简化仿射矩阵变换来表示 摄像机运动对图像的影响，并据此完成整个背景图的无缝拼接，来表示镜头的内 容。 l m 】。然而，这样的方法有时难以区分镜头切换 和同一镜头中部分区域的变化以及特殊事件( 如闪光) 。前后紧密相连的方法检测 渐变时也有一定的困难。为了缓解或消除上述问题，有学者提出了时间域窗口法， 即通过位于同一个窗口的所有帧的特征来计算帧间连续性1 3 8 】【4 4 1 。 2 3 3 分类方法 分类方法是边界检测的重要步骤，文献 2 1 】 3 5 4 4 对各种分类算法进行 总 结。一般的，可以分为两个类，一类是基于规则的分类法，一类是基于统计学习 的分类法。 1 基于规则分类法 在基于规则的分类法中，一般用式( 2 2 ) 定义分类函数： 啦棚) = r 裟 亿2 、 其中，t 为预先设定的阈值。d ( i j ) 表示帧间连续性，或者是相似度。如果 d ( i ，j ) 超过了阈值t ，分类函数输出0 ，表示在帧i 和帧j 间不存在镜头切换；否则， 分类函数输出1 ，表示发生了镜头切换。早期的算法中，采用启发式的全局阈值 选择法。然而，这样选择的阈值难以满足多样、多类型的视频。为克服这一缺点， 研究者提出了很多局部自适应阈值选择算法【4 2 】。其基本思想是在时域选择一个 滑动窗口，计算此窗口内的局部阈值。因为局部自适应阈值能够更好的利用局部 上下文相关信息，所以性能优于全局阈值，相关实验也证明了这一点。 2 统计学习分类法 镜头边界检测可以看作是模式识别的问题，所以有研究者利用统计学习的方 法来对其处理。这一类方法可以分为两种，即产生分类器( g e n e r a t i v ec l a s s i f i e r ) 第二章镜头边界检测和关键帧提取概述 和判别分类器( d i s c r i m i n a t i v ec l a s s i f i e r ) 。一般的，产生分类器易于结合额外的信 息( 先验知识) ，文献【4 4 】【4 5 】中，就利用了镜头的持续时间来建模提高检测性能， 而判别分类器仅能利用内容变化活动的特征。然而，产生式的方法对先验知识的 假设和条件分布模型依赖程度较高，因此在使用之前，必须确保模型假设的正确 性。如果不能满足上述条件，那么选择基于判别的方法会更好一些。很多种判别 分类算法被应用到镜头边界检测中，包括k 均值【4 6 1 、k n n 47 】和支持向量机( s v m ) 【4 8 】【4 9 1 。基于统计学习的方法，通过交叉确认过程选择模型参数，并在训练的过程 中自动确定分类。使用统计学习法涉及两个主要问题。其一是怎样为分类器构造 特征。c o o p e r l 47 j 和y u a n 等【4 8 】把在特定时间间隔的连续性信号作为特征分别提供 给k n n 和s v m 。f e n g 等【4 9 j 则把滑动窗口内小波变化系数向量作为s v m 的特征。 另一个则是如何获取好的训练集，使之在正样本与负样本间保持相对平衡。因为 在每一个视频序列中，负样本往往比正样本的数量更大，所以要保证训练集在正 负样本间的相对平衡。为解决该问题，y u a n 等【4 8 】采用主动学习策略来处理不平衡 的训练数据。与阈值法相比较，统计学习的方法在做出决策时，采用的方法是识 别镜头转换的模式而非评估内容变化幅度的大小。 2 3 4 典型算法分析 前面主要对当前镜头检测算法中视频内容的表达、视频内容的连续性和分类 方法进行了总结分析，下面则对一些典型算法进行讨论。 l 非压缩域算法 文献 3 9 】采用比较两帧的对应像素的方法，如式( 2 3 ) 所示： mn d ( i ，) = l z ( x ，y ) - f j ( x ，y ) | ( 2 - 3 ) x = 0y = 0 其中f i ( x ，y ) 是第i 帧( x ，y ) 处的灰度、灰度或者色彩值。两帧间的相异度用d ( i ，j ) 表示，并对整帧进行计算。预先设定一个阈值t ，当d ( i ，j ) 超过了t ，就认为出现 了一个镜头切换。正如之前分析的，这样的算法对噪声和运动较敏感，常需做如 运动估计和补偿等预处理。 t o n o m u r a 【5 0 1 采用了基于灰度直方图的算法。分别用h ( f i ，k ) 和h ( f j ，k ) 来表示帧 f i 和f j 的直方图。直方图差见式( 2 4 ) ： n d ( i ，j ) - - x l m ( i , ，k ) - n ( f , ，七) i ( 2 - 4 ) k = l 其中，n 是灰度级总数，k 是某一灰度级。当d ( i ，j ) 大于预设阈值时，则认为 检测到一个突变。显然，这样的方法可以很容易地扩展到r g b 或者h s v 等色彩 1 6 视频镜头边界检测和关键帧提取技术研究 空间。另外，一个采用归一化的可靠的方法是) c 2 检验法，它的相似度衡量如式 ( 2 5 ) ： 刚) = 善鲻掣， ( 2 - 5 ) 虽然该方法增强突变前后的差别，却放大了运动所造成的影响，并且计算量相对 较大。 z a b i h 等提出用边缘变化率检测镜头边界，其基本原理是在镜头发生转换 时，新出现的边缘应远离旧边缘的位置，而旧边缘消失的位置应远离新边缘。边 缘变化率( e d g ec h a n g er a t i o ，e c r ) 定义见式( 2 6 ) ： e c r = m a x ( x ： l c r 一，础仃州) ( 2 - 6 ) 其中，e c r n 是n 1 帧与n 帧之间的边缘变化率。嘞是第n 帧的边缘像素总数， 霹是第n 帧的进入边缘像素总数，而碍是第n 1 帧的消失边缘像素总数。在检 测中用c a n n y 边缘检测算子来对每一帧进行计算。l i e n h a r t i s q 对边缘变化率法和 直方图法做了比较，实验表明，在检测突变时，前者的性能并未超越简单的直方 图法，而计算过程却更为耗时。尽管如此，它却在解决闪光问题时效果明显。 2 压缩域算法 因为越来越多的视频数据是以压缩的形式存储的，如何对压缩形式的视频数 据进行镜头边界检测已经成为一个亟待解决的问题。通常的方法是先解压视频数 据，然后利用像素域中的边界检测技术进行检测。但是，这些方法的主要问题是 解压要花费一定的时间，效率较低。为此，在压缩域中直接进行边界检测的研究 已经展开，但是方法和手段相对较少，效果也并不十分理想。 在m p e g 视频流中，y e o 和l i u t 4 2 】提出了一种基于直流( d c ) 系数的镜头边 界检测算法。我们知道，m p e g 视频帧格式有i 帧，p 帧和b 帧。利用序列中的 每一帧构造d c 帧f d c ，其中，i 帧的d c 系数直接从每一块中获得，而b 帧和p 帧的d c 系数是被估计出来的。d c 帧z d c 和严之间的差值之和作为帧间相似度 d i j ，如式( 2 7 ) - 口，j = d p c ，矿) = k ( w ) 一俨( w ) l ( 2 - 7 ) 其中，f v c ( x ，y ) 是块( x ，y ) 的d c 系数。这种技术的速度较快，但是像素值 类似而密度函数不同的帧之间会造成误检。 l e e 等【5 2 】提出了基于b 帧宏块类型的镜头切换检测方法。b 帧内双向预测的 宏块个数越多，说明帧间的相关度越高，则镜头切换的可能性就越小。 一个自适应的阂值t b n 应用于m p e g 流的第r 1 个b 帧，其中 第二章镜头边界检测和关键帧提取概述 f 上掣口拧卅n l 瓦m = h n n r - k = 0 “ ” ， ( 2 - 8 ) 【0 2 5 ， ，z = 0 它表示第n 个b 帧中双向预测的宏块的个数，n 是b 帧中宏块的个数，n t 是用 于决定自适应阈值的帧数。如果第n 个b 帧中n b n n t b n 】，则表示该b 帧与 其前后的i 、p 帧有较高的相关度，可以推断出该b 帧与其前后的i 、p 帧之间无 镜头变换。如果后向预测宏块的个数n b n 大于前向预测的宏块个数n f n 】，那么 b 帧中大部分宏块的编码来自于其后的i 、p 帧，因此突变发生于当前帧。 3 其他算法 c e m e k o v a 等【5 3 】把信息论的知识引入进来，采用帧间互信息( m u t u a l i n f o r m a t i o n ，m i ) 方法对镜头边界进行检测。互信息量用来衡量帧与帧间转换信 息，当两帧间的内容发生较大变化时，则帧间依赖较低，其互信息量较低。与帧 间差方法相比，它能以更为简洁的方式更好地反映出帧间信息。 b a e 等【5 4 】提出了基于隐马尔科夫模型( h m m ) 的检测算法。提取音频和视频 特征，用h m m 分类器检测，比之传统检测方法，能够避免镜头误检和过度地分 段。但是它需要的训练数据集巨大，算法过于复杂。 4 渐变检测 渐变检测是镜头检测中的遇到一个难题。到目前为止，还没有任何一个渐变 检测算法能够和突变检测算法的性能相匹敌。已有的算法中，大多针对某一种特 别的渐变类型取得了较好的效果。但是，没有一个方法是适用于多种渐变类型的。 这里对一些典型的渐变检测算法进行分析总结，以便于寻找更好的解决方案。 最为著名的渐变检测算法是z h a n g 等【3 9 】提出的双阈值比较法 ( t w i n c o m p a r i s o n ) 。双阈值比较法设定两个阈值l ( 较大的阈值) 和z ( 较小的 阈值) ，当前后两帧差超过l 时，判定为突变。如果没有超过t 却超过巧，就判 定为可能的渐变起始帧，继续检查其后各帧，如果仍超过z ，就把帧差累加起来， 直至前后两帧差小于乃，此时若累加帧差超过了l ，判定为渐变终结帧；如果没 有超过l ，就认为由其他原因造成，而不是渐变。该方法的缺点在于难于选择l 和z 。在双阈值比较法的基础上，基于滑动窗1 2 1 的自适应阈值法也被提了出来。 该方法在检测帧附近设定一个长度为n 的滑动窗口来自适应的选取阈值z ，无需 使用l 来控制渐变长度。但是该算法要求渐变过程中每一帧间差都要大于巧，所 以当渐变过程中出现个别帧间差小于z 时，就会截断渐变过程。 f e m a n d o 等【5 5 】通过分析淡入淡出时灰度和颜色空间上的变化特征，建立数学 模型来检测。设有图像a 和b ，视频信号由两者共同决定，只是所占比例不同。 对于溶解过程，可以这样认为，图像a 从1 0 0 降低到o ，图像b 从o 增加到1 0 0 。 1 8 视频镜头边界检测和关键帧提取技术研究 对于淡入，不必考虑图像a ，而淡出则不必考虑图像b 。以一个淡入过程为例， 可以用数学方程式( 2 9 ) 来描述： 鼠( x ，y ) = z ( x ，y ) 1 - ( 孚) c + 孚k 训) 岛( x ，y ) 0 刀 厶 厶疗 ( 厶+ f ) ( 2 9 ) ( 厶+ f ) 刀厶 其中，s 。( x ，y ) 是结果视频信号，矗( x ，y ) 是图像a ，g 。( x ，y ) 是图像b ，c 是淡入 开始时的一个固定值，l l 是视频图像a 序列长度，l 2 是视频图像b 序列长度，f 是淡入序列长度。 这种基于数学模型的方法的要点是对不同的渐变效果，需要不同的渐变数学 模型。因此，算法的局限性较大，一种算法往往只能检测一种或几种渐变方式。 此外，对运动和噪声的干扰较敏感，因此只有当视频序列中含有的运动较少时， 才会有较好的检测效果。通常，在检测前对图像进行平滑处理可以降低噪声和运 动对检测的影响。 l e e 掣5 2 】在m p e g 上采用基于b 帧的宏块类型来检测渐变。定义非相似度 d i s n 来检测渐隐和淡入淡出，同时通过m v 与摄像机的运动特征进行模板匹配 来避免摄像机运动引起的误识别。当选取帧的d i s n i k 乇于阈值，且选取的运动既 不是静止的也不是摄像机的运动时，该帧可作为渐变边界。 l i n 等阳与c h u a 等旧发掘特征空间上的多分辨率边缘现象，提出了时域多分 辨率分析法( t e m p o r a lm u l t i r e s o l u t i o na n a l y s i s ，t m r a ) 。算法先提取视频特征，然 后计算特征小波系数，并设定一个自适应阈值，一次性统一检测突变和渐变，但 其计算量太大。 2 4 关键帧提取 从2 3 节的镜头级视频结构化分析过程的讨论中，我们知道获取关键帧是其 中的重要步骤。事实上，关键帧表达是一个简单而有效的视频内容抽象方法，可 用于视频浏览和检索，主要的挑战在于如何以符合知觉和有意义的方式用关键帧 来表达视频内容。基本上，有两种不同的方法来达到此目的，即关键帧选取和关 键帧构造。关键帧选取是指直接从镜头中选取帧表达视频内容过程，而关键帧构 造是从给定的图像序列构造新的图像的过程。关键帧选取的方法吸引了众多研究 者的关注，因为这在实践中是有效的，而且从统计上来说也能很好地降低镜头中 的冗余信息。关键帧构造的方法，虽然更符合人的直觉，但是需要有运动标注以 及分割作为前提，而这通常被认为是很难的问题，这里不对其进行讨论。 针对关键帧的特点，提取关键帧是有两个基本原则：第一，所选帧必须能够 第二章镜头边界检测和关键帧提取概述 1 9 反映镜头中的主要事件，描述应尽可能准确完全，所以一般采用保守原则，宁可 错选，也不能少选；第二，为了便于管理，数据处理量尽可能小，计算不宜过于 复杂。下面对关键帧提取方法进行探讨。 2 4 1 基于镜头的方法 早期提取关键帧的尝试主要是采用颜色特征。一个简单的提取关键帧的想法 是把每个镜头的首帧作为关键帧的方法【5 引，文献 5 9 贝j j 把每一镜头的首帧和末帧 作为关键帧。在基于镜头的方法中，比较经典的有帧平均法和直方图平均法。帧 平均法是从镜头中取所有帧在某个位置上像素值的平均值，然后将镜头中该点位 置的像素值最接近平均值的帧作为关键帧。直方图平均法则是将镜头中所有帧的 统计直方图取平均，然后选择与该平均直方图最接近的帧作为关健帧。一个比较 有效的方法是z h a n g 等【3 l j 提出的利用颜色直方图来提取关键帧。此外，y e u n g 等 1 6 0 采用了通过计算特征空间的最大距离来提取关键帧的方法。 这些方法的优点是计算比较简单，无论镜头内容如何，关键帧的数量始终不 变，所选取的帧具有平均代表意义。缺点是只从一个镜头中选取一个关键帧，无 法处理运动速度较高的镜头。一般说来，从镜头中选取一帧或固定数目的关键帧 的方法并不是很好，因为当处理变化很少的镜头时，这样选取的关键帧过多，而 对于运动较多的镜头，用一两个关键帧又无法充分描述其内容。 2 4 2 基于内容分析的方法 在拍摄视频影像时，由于场景中目标的运动或摄像机本身的操作( 如变焦、 摇镜头等) 的影响，一个镜头仅用一幅关键帧不能很好地代表该镜头的内容，常 需用几幅关键帧。原则上讲，关键帧应能提供一个镜头的全面概要，或者说应能 提供一个内容尽量丰富的概要。从这个角度说，关键帧的提取可看作一个优化过 程。根据信息论的观点，不同( 或相关性较小) 的帧图像比类似的帧图像携带更 多的信息。所以当需要提取多幅关键帧时，用于关键帧提取的准则主要是考虑它 们之间的不相似性。 从理论上说，由于镜头是由时间上连续、内容上相关性很高的帧图像组成的， 因此选取其中最不相关的几帧作为镜头关键帧才能包含最多的信息。一种简单的 方法将镜头的第一帧定为关键帧，并将第一帧设为参考帧；然后计算各后续帧与 参考帧的差异，当差异值大于预定的阈值时，则选该后续帧为关键帧；再将刚选 出的关键帧设为参考帧，继续重复上述检测过程，直到当前镜头的结束帧。下面 是基于此方法的一种比较简单有效的算法，该算法可以根据镜头的不同特点，自 2 0 视频镜头边界检测和关键帧提取技术研究 动提取l 到3 帧图像作为关键帧【6 l 】。 设s = f l ，f 2 ，f n 是其中的一个镜头，共n 帧，取f l ， f n a 和f n 候选关键 帧。定义帧间差为式( 2 1 0 ) ： d ( z ，乃) = l z ( x ，y ) - f ：( x ，y ) l ( 2 一l o ) x ，y 提取关键帧时，先计算两两候选关键帧之间的距离，d ( f l ，f n 2 ) 、d ( f i ，f n ) 和 d ( f w 2 ，f n ) ，并将它们与一个预定的阈值t 比较，按如下规则确定关键帧： 1 ) 如果它们都比t 小，说明它们之间比较接近，此时取为f n a 关键帧； 2 ) 如果它们都比t 大，说明它们之间差距较大，此时将这三帧都取为关键 帧； 3 ) 其它情况下，取距离最大的两帧图像作为关键帧。 基于内容分析的方法可以根据镜头内容的变化程度选择相应数目的关键帧， 然而其缺点是所选取的帧不一定具有代表意义，而且在有镜头运动时，容易选取 过多的关键帧。 2 4 3 基于运动分析的方法 文献【6 2 】通过分析光流( o p t i c a lf l o wa n a l y s i s ) 来计算镜头中的运动量，在 运动量取局部最小值处选取关键帧，它反映了视频数据中的静止，往往表示一种 强调的实际情况。这种方法首先用h o m s c h u n c k 法计算光流，对每个像素光流分 量的模求和，作为第k 帧的运动量m ( k ) ，如式( 2 1 1 ) ： m ( 七) = i q ( f ，尼) i + i q ( f ，七) i ( 2 一i i ) 其中，o 。( i ，j ，k ) 是帧内像素( i ，j ) 光流的x 分量，o y ( i ，j ，k ) 是帧内象素光流的 y 分量。然后寻找m ( k ) 的局部最小值。从k = o 开始，扫描m ( k ) ：k 曲线，找到两 个局部最大值m ( k o 和m ( k 2 ) ，m ( k 2 ) 的值与m ( k 0 的值至少相差p ( 由经验决定) ， 如果m ( k 3 ) - - - m i n ( m ( k ) ) ，k l k k 2 ，则k 3 为关键帧。然后k 2 把作为当前的k l ，继续 寻找下一个k 2 。w o l f 的这种基于运动的方法可以根据镜头的结构选择相应数目 的关键帧。如果先把图像中的运动对象从背景中取出，再计算对象所在位置的光 流，可以取得更好的效果。 2 4 4 基于聚类的方法 可以通过对视频帧进行聚类来选取关键帧。k 均值聚类( k m e a nc l u s t e r i n g ) 和模糊c 均值聚类( f u z z yc - m e a nc l u s t e r i n g ) 是两个常用的聚类算法。在k 均值 聚类算法的每次迭代中，每一个样本都被认为是完全属于某一个聚类的，故分类 第二章镜头边界检测和关键帧提取概述 2 l 是清晰的。而对于模糊c 均值聚类算法来说，放宽了这个条件，假定每一个样本 是模糊“隶属 ( f u z z ym e m b e r s h i p ) 于某一聚类的，故而是模糊分类。h a n j a l i c 和z h a n g 6 3 j 采用了带有聚类有效性分析的分割聚类算法以选取关于镜头的最优 聚类数。聚类的结果是根据聚类间和聚类内距离测度而得出的最优结果。其中， 跟聚类矩一t 二, ( c e n t r o i d ) 最近的帧被选为关键帧。虽然聚类是有效的，但聚类维数问 题需要小心地处理。作为原则，用于聚类的帧数应该数倍于特征空间的维数。j o s h i 等科】将模糊聚类方法应用到只带有渐变镜头的短视频序列上，对于每一个镜头， 处于质心的帧便会被选为关键帧。他们的方法有两个主要问题：一是聚类数须预 先指定，而实际上聚类数是很难预先知道的；二是如果在一个长的视频序列中有 越多的突变镜头，就可能产生越多的错误聚类。故此法对于带有突变镜头的长视 频序列是不合适的。c h i c h u nl o 等【6 5 】将直方图与聚类结合提出了基于直方图的 模糊c 均值聚类算法( h b f c m ) ，这种方法不需预先设阈值。算法主要分为三个 步骤，首先是特征提取阶段，这里的特征主要是帧间直方图的差别，第一阶段提 取的特征作为第二阶段的输入进行聚类；与以前的方法不同，这里的聚类的个数 是三个而不是两个，二分法会错误地将帧放入不属于它的聚类中，比如对那些难 以检测镜头变化中的帧也就是增加了一个可能的转换帧聚类；第三阶段即是关键 帧的选取。 2 4 5 基于压缩域的方法 在压缩域直接提取关键帧可以在一定程度上降低计算复杂度。c a l i c 和 i z q u i e r d o t 6 6 】从m p e g 视频流中通过提取宏块类型信息获得特征向量，然后利用高 斯滤波拟制噪声，再使用离散轮廓改良法( d i s c r e t ec o n t o u re v o l u t i o n , d c e ) 简 化特征曲线。