（计算机应用技术专业论文）基于粗糙集的视频镜头检测研究.pdf

重庆邮电大学硕士论文摘要 摘要 基于内容的视频检索是未来多媒体应用的一个重要方面，而镜头检测 是确定视频中镜头变化的边界，是视频处理的第一个步骤，是随后的高层 内容分析、分类、索引和查询的基础。镜头检测的准确性将直接影响到这 些后续处理的效果。传统的镜头检测方法一般都只是采用简单的帧差异比 较或者先验模型判别，不但需要人为的设定阈值，而且检测的整体效果以 及适应性都不太理想。 基于粗糙集的数据挖掘方法不需要预先给定检测对象的某些属性或 特征的数学描述，可以直接从给定问题的知识分类出发，通过不可分辨关 系和不可分辨类来确定对象的知识约简，导出问题的决策规则，这样就可 以避免阈值的人为设定，改善检测的适应性。本文以粗糙集理论为基础， 提出了一种基于粗糙集的视频镜头检测方法。该方法从m p e g 视频序列中 提取出需要的p 帧信息，包括亮度信息和运动信息，形成包含各个特征属 性的决策表，接着对决策表进行各种处理，包括数据预处理、属性约简、 值约简，提取出镜头检测的决策规则，最后分析并应用这些规则，得到最 终的镜头检测结果。 实验表明本文方法不仅能够克服闪光、复杂运动的影响，而且还可以 有效地检测出视频中的镜头渐变，取得了较好的镜头检测尤其是渐变检测 效果。 关键词：粗糙集；镜头检测；突变；渐变：基于内容的视频检索 重庆邮电大学硕士论文 a b s t r a c t c o n t e n t b a s e dv i d e or e t r i e v a li sa ni m p o r t a n tf i e l do ff u t u r em u l t i m e d i a a p p l i c a t i o n s h o td e t e c t i o ni st h ed e t e r m i n a t i o no fs h o tb o u n d a r y i ti st h ef i r s t s t e po fv i d e op r o c e s s i n ga n dt h eb a s i so ff o l l o w i n g h i g hl e v e lc o n t e n ta n a l y s e s ， c l a s s i f i c a t i o n ，i n d e x i n ga n dq u e r y t h ea c c u r a c yo fs h o td e t e c t i o nw i l la f f e c t t h ee f f i c i e n c yo fs u b s e q u e n tp r o c e s s i n gd i r e c t l y t r a d i t i o n a ls h o td e t e c t i o n m e t h o d sa d o p ts i m p l ef r a m ed i f f e r e n c ec o m p a r i s o n so re m p i r i c a lm o d e l j u d g m e n to n l y ，- a n dr e q u i r em a n u a lt h r e s h o l dv a l u es e t t i n g t h eg e n e r a l e f f i c i e n c ya n da d a p t a b i l i t yo fs h o td e t e c t i o np r o d u c e db yt h e s em e t h o d sa r e n o ta sg o o da se x p e c t e d r o u g h - s e t b a s e d d a t a m i n i n g m e t h o dd o e sn o tn e e d a n yp r e g i v e n m a t h e m a t i c a ld e s c r i p t i o no fo b j e c ta t t r i b u t e sa n dc h a r a c t e r i s t i c s s t a r t i n gw i t h k n o w l e d g ec l a s s i f i c a t i o no fg i v e np r o b l e m s ，r o u g h - s e t b a s e dd a t am i n i n g m e t h o dc a nd i r e c t l yd e t e r m i n et h ek n o w l e d g er e d u c t i o no fo b j e c t sa n de x p o r t r u l e sb yu n d i s t i n g u i s h a b l er e l a t i o n s h i p sa n dc l a s s e s ，t h u s ，a v o i d sm a n u a l t h r e s h o l dv a l u e s e t t i n ga n di m p r o v e s d e t e c t i o na d a p t a b i l i t y t h et h e s i s p r o p o s e sar o u g h - s e t - b a s e dv i d e os h o td e t e c t i o nm e t h o d t h em e t h o df i r s t e x t r a c t sn e c e s s a r yp f r a m ei n f o r m a t i o n ，s u c ha sb r i g h t n e s sa n dm o v e m e n t i n f o r m a t i o n ，f r o mm p e gv i d e os e q u e n c e st of o r mv a r i o u sf e a t u r ea t t r i b u t e s d e c i s i o nt a b l e ，t h e np r o c e s s e st h ed e c i s i o nt a b l eb yd a t ap r e p r o c e s s i n g ， a t t r i b u t er e d u c t i o na n dv a l u er e d u c t i o nt oe x t r a c td e c i s i o nr u l e sf o rs h o t d e t e c t i o n ，f i n a l l y , a n a l y z e st h e s er u l e s a n da p p l i e st h e mt oo b t a i ns h o t d e t e c t i o nr e s u l t s e x p e r i m e n t ss h o wt h a tt h i sm e t h o dc a no v e r c o m et h ei n f l u e n c eo ff l a s h a n dc o m p l e xm o t i o n ，e f f e c t i v e l yd i s t i n g u i s hg r a d u a ls h o tc h a n g e si nav i d e o ， a n da c h i e v e si d e a ls h o td e t e c t i o nr e s u l t s ，o fw h i c ht h eg r a d u a ls h o tc h a n g e r e s u l ti se v e nm o r es a t i s f a c t o r y k e yw o r d s ：r o u g hs e t ，s h o td e t e c t i o n ，a b r u p tc h a n g e ，g r a d u a lc h a n g e ， c o n t e n t b a s e dv i d e or e t r i e v a l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得重医业电太 兰_ 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：易1 节 签字日期：z 。6 7 杉月弓日 学位论文版权使用授权书 本学位论文作者完全了解重庆整虫盍堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权 重庭邮电太堂可以将学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：吗审 签字日期：2 口7 年r 月弓同 翩始胁 签字期：2 口0 7 彳r 月予f 日 1 1 重庆邮电大学硕士论文 第一章绪论 1 1 引言 第一章绪论 随着信息技术的突飞猛进，产生了大量的视频文档。视频文档具有数 据量巨大，抽象程度低等特点，对其进行有效的存储、分段和检索成为目 前需要解决的迫切问题。传统的视频检索解决方案一般采用基于文本的检 索方法。由于标注文本是人工添加的，受主观因素的影响，容易导致错误 和不一致的结果，而且视频文档的数量往往都非常庞大，不可能对所有视 频数据都进行类似的处理。基于内容的视频检索直接对视频中的各种特 征，包括颜色、纹理、形状、运动矢量和亮度等进行分析，抽取其中的语 义特征。利用这些特征来建立索引，不仅可以避免主观错误，而且能够自 动高效地处理视频信息。 镜头是组成视频的基本单元，也是对视频内容进行深入分析和检索的 基础，因此实现一种高效的视频镜头检测方法在基于内容的视频检索中尤 为重要。视频作为一类重要的视觉信息资源，它不仅包含静止图像所包含 的内容，还包含场景中目标运动的信息和客观世界随时间变化的信息。基 于内容的视频信息访问覆盖各种应用领域，并包含多项技术，比如收集信 息，对数据结构化和进行处理，在视频数据库中搜索信息，并发送和显示 给用户等。 由于视频数据与其它数据在形式、结构、内涵等方面都不同，与图像 相比，视频的结构更为复杂，数据量也更大，所以对基于内容的视频检索 的要求也就更高。 事实上，视频中除了包括从每幅帧图中可得到的视觉特征，如颜色、 纹理、形状和空间关系等，还有运动的信息。静止图像的特征信息在基于 内容的图像检索中已有大量的研究1 1 - 4 1 ，而视频中目标和背景的运动信息 作为视频所独有的特征，则是基于内容的视频检索中研究的重点。运动信 息表达了视频图像内容在时间轴上的发展变化，它对于描述理解视频内容 具有相当重要的作用。基f 运动信息可对视频镜头进行检测，进而用于视 频内容的检索。本文也将采用视频的运动信息来进行镜头的检测。 重庆邮电大学硕士论文 第一章绪论 1 2 视频检索及镜头检测技术的发展状况 1 2 1 基于内容的视频检索 信息检索最早出现于半个世纪之前【5 1 。它用来描述将信息用户对一个 信息的要求转换成一个参考集合的过程，在此基础上，用户将有可能快速 的搜索并提取相关的信息。视觉信息的检索是信息技术中一个新的重要研 究领域，它是传统的信息检索的扩展，将视觉媒体也包含在信息检索中。 最早的图像检索概念早在2 0 多年前就提出来了。视频是运动的图像，也属 于图像的范畴，因此图像和视频的检索同属于信息检索的范畴。 第一代视频检索系统允许用户通过字符串属性来访问图像和视频。一 个典型的搜索例子就是搜索“某人某个时间段的所有作品的图像”。它们用 字符串表达与内容无关的元数据，使用如相关模型、框架模型、面向目标 的模型等表达方案。 新一代的视频检索系统支持根据视频内容的检索。对视频的访问不只 是概念层次上利用关键字进行，而且也在感知层利用对视频内容的客观测 量和合适的相似模型进行。在离线状态下，不仅注解员可以通过一定的方 法对数据库内容进行注勇孚，而且系统也能够自动的对数据库的视频进行分 析，提取特征，从而提供出在线应用时所需的索引。用户不仅可以借助文 字查询方法，也可以借助视频的浏览和范例的查询方法，利用搜索引擎进 入索引进行检索，返回的结果仍可以用可视化的手段显示给用户，使得用 户能够借助相关反馈开始新一轮的查询。 1 2 2 视频检索方式简介 当前的视频检索主要有以下几种方式： 1 基于关系型数据库的方式。根据特征字段检索出所需的素材，然后 通过浏览关键帧来定位目标视频。比如通过节目标题、拍摄地点和制作时 间等字段进行检索。但是特征字段所能描述的视频属性是有限的，而且手 工标记的效率很低。 2 基于大段视频注释的全文检索。视频注释。般以文本字段的形式存 放在关系型数据库中，通过编号和视频文件相天联。它虽然最大限度的保 留了视频的高层语义信息，但是却丢失了宝贵的底层视觉信息，不能为用 2 重庆邮电大学硕士论文 第一章绪论 户提供灵活的多维检索。 3 ，基于内容的视频检索。它直接对图像、视频的内容进行分析，抽取 其特征和语义，利用这些内容特征来建立索引，用户可以通过指定的模版 视频，检索出和模版视频在颜色、纹理、运动等特征上相类似的素材。虽 然目前的特征提取技术仍然不成熟，但是基于内容的视频检索是当今视频 检索领域的研究热点。 1 2 3 视频检索原型系统 目前，国际上对基于内容的检索技术进行了很多实际性的研究，取得了 许多成果，一些原型系统已发布在互联网上。下面我们对其中一些具有代表 性的原型系统进行简要的介绍： m a r s ( m u l t i m e d i a a n a l y s i sa n dr e t r i e v a ls y s t e m ) 系统，该系统由美 国u i u c 大学开发，运用计算机视觉、数据库管理系统和信息检索等领域 的知识。m a r s 系统与其它系统的区别在于它的重点不是在于寻找单个的 最佳特征表示，而在于如何将不同的视觉特征组织成有意义的检索体系， 以动态地适应不同的用户及应用场合。m a r s 系统是正式提出相关反馈的 系统，它将相关反馈技术集成到检索的不同层次过程中。 v i d e o q 系统，该系统是哥伦比亚大学研究的一个项目，它扩充了传统 的关键字和主题导航的查询方法，允许用户使用视觉特征和时空关系来检 索视频。它有以下几个特征：集成文本和视觉搜索方法；自动的视频对象 分割和追踪；丰富的视觉特征库，包括颜色、纹理、形状和运动；通过互 联网交互查询和浏览。 q b i c ( q u e r yb yi m a g ec o n t e n t ) 系统，该系统是i b ma l m a d e n 研究中 心开发的第一个商用基于内容的图像及视频检索系统，它提供了对静止图 像及视频信息基于内容的检索手段。其系统结构及所用技术对后来的视频 检索有深远的影响。 c o r e 系统，由新加坡国立大学开发的一个基于内容的检索机。其显 著技术特色包括：多秘特征提取方法、多种基于内容检索方法、使用自组 织神经网络对复杂特征度量、建立基于内容索引的新方法以及对多媒体信 息进行模糊检索的新技术。 v i s u a l s e e k 系统，v i s u a l s e e k 是美国哥伦比亚大学电子工程系与电信 研究中心图像和高级电视实验室共同研究的种在互联网卜使用的基于 内容的剐像视频榆索系统。利用v i s u a l s e e k 工具叮以在互联网上搜索和检 重庆邮电大学硕士论文 第一章绪论 索图像与视频，通过用户接口工具表示出要查询的图像的主要可视特征， 将其送到检索服务器，服务器查找和检索出最佳匹配图像或视频，并返回 给用户。v i s u a l s e e k 自动进行特征抽取，而不是依赖于人工输入的文本和关 键字。它提供可移植、易用并具有可视查询能力的用户接口，使用户容易 直接提交简捷的基于内容的查询，有经验的用户还可以构造更复杂的查 询。 t v - f i ( t s i n g h u av i d e of i n di t ) 系统，是清华大学开发的视频节目管 理系统。这个系统可以提供如下几个功能：视频数据入库、基于内容的浏 览、检索等。t v - f i 提供多种模式访问视频数据，用户既可以使用关键字 进行查询，也可以基于示例进行查询，浏览查询结果时可以采用按视频结 构或按用户自定义类别两种方式进行。 1 2 4 镜头检测 镜头检测亦称镜头分割是一门以多学科理论为基础的综合性技术，它 主要涉及计算机图形学【6 1 、模式识别1 7 1 、认知科学【引、图像处理【9 】等理论， 目前尚未实现完全准确的视频镜头检测。本文以基于内容的视频检索的关 键技术之一，即基于多种视频特征信息的镜头检测作为研究课题。 基于视频特征信息的镜头检测的研究主要包括帧特征信息的提取以 及后续的镜头边界判断。帧特征信息中除了亮度信息，运动信息也是镜头 检测中可利用的一种重要信息。视频的运动包括全局运动和局部运动，前 者是由摄像头的运动所造成的，m p e g 7 【1 0 】标准从摄像头操作的角度对其进 行了详细的规定，一共有六大运动类型：扫视、倾斜、变焦、跟踪、升降、 推拉。后者是指场景中的目标运动，可以看作与全局运动模型不相符合的 部分。m p e g 7 标准推荐了一种运动描述符一参数运动，主要是以2 d 几何 变换来刻画视频中任意形状的目标区域随时间的变化情况，可以描述视频 中的目标运动。实用的全局运动模型都是简化的参数模型，如考虑了扫视 俯仰缩放和摇摆的八参数运动模型，只考虑扫视和缩放的简化四参数模 型，以及用m p e g 的运动向量进行快速估计的四参数模型等。近几年来， 针对未压缩视频序列，提出了一些基于镜头运动模型参数来估计全局运动 的方法，”】。而在压缩域内，t a n 和s a u r 等通过抽取m p e g 码流中宏块的 运动矢量提出了一种快速的镜头运动参数检测算法【14 1 。另外，俞天力等 人建立了一个基于全局运动f 矗息的视频检索系统l l5 1 。局部运动向量场的研 究上主要有三种策略，包括光对视频帧分割之后再计算运动信息【1 6 1 , 先汁 4 重庆邮电大学硕士论文第一章绪论 算运动信息后分w r i t ”】，及同时求得运动向量场和进行运动区域分割l 8 1 。 镜头检测的研究已经开展了数十年，许多学者和研究人员提出了各自 的方法，对视频镜头的检测作了有意的研究与探讨。经过仔细地研究与分 析，我们大致可以将这些方法分为以下四类： ( 1 ) 基于直方图的镜头检测方法：基于直方图的方法是一种较早提 出的方法，它的改进方法有很多，但基本原理一致，都是将帧像素的灰度、 亮度或颜色划分成若干等级，对每个等级进行统计形成直方图来进行比 较。该方法的优点是实现起来简单方便，适用于对检测精度要求较低的应 用，当视频的运动幅度较大或发生镜头渐变时容易出现误检和漏检。 ( 2 ) 基于运动的镜头检测方法：基于运动的方法考虑镜头局部运动 及全局运动的运动情况和特征，通过运动补偿等手段来减少运动对镜头内 帧差变化的影响。此类方法对于切变检测具有较好的效果，但对于渐变检 测，由于复杂性高、难度大，效果并不理想。 ( 3 ) 基于压缩域的镜头检测方法：基于压缩域的方法对视频数据不 解码或只解码一半，对得到的数据如d c t 系数直接进行分析，因为不需 要解码或只进行部分解码，所以此类方法效率较高。但以往提出的方法采 用的特征信息过于单一，而且需要人为的设定阈值，造成检测的效果和适 用性都不太理想。 ( 4 ) 基于数据挖掘的方法：此上各类方法大多都需使用阈值，而阈 值的选取通常都比较困难，采用数据挖掘的方法可以避免阈值的设定，例 如：模糊c 均值聚类法【伸】、无监督聚类方法一k 均值法1 20 1 、基于决策树 的方法1 2 l 】等等。这些方法对于各类视频有较好的适应性，但同样在检测效 果方面有待提高。 以上简要的介绍目前研究人员提出的各类镜头检测方法，在第二章 中，我们还会对这些方法进行较为详细的介绍。 1 3 数据挖掘理论简介 随着数据库技术的不断发展和数据库管理系统的广泛应用，数据库中 存储的数据量急剧增大，在大量的数据背后隐藏着许多重要的信息，如果 能把这些信息从数据库中抽取出来，则可以为我们带来很多潜在的价值， 而这种从海量数据库中挖掘信息的技术，就称之为数据挖掘。数据挖掘的 任务主要是关联分析、聚类分析、分类、预测、时序模式和偏差分析等。 数据挖掘的主要流程如下： 重庆邮电大学硕士论文 第一章绪论 ( 1 ) 确定业务对象：清晰地定义出业务问题，认清数据挖掘的目的是 数据挖掘的重要一步。挖掘的最后结构是不可预测的，但要探索的问题应 是有预见的。 ( 2 ) 数据准备：包括数据的选择以及数据的预处理。数据的选择是 指搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于 数据挖掘应用的数据。数据的预处理是研究数据的质量，为进一步的分析 作准备，并确定将要进行的挖掘操作的类型。包括检查数据的完整性及数 据的一致性、去噪声，填补丢失的域，删除无效数据等。 ( 3 ) 数据的转换：将数据转换成一个分析模型。这个分析模型是针 对挖掘算法建立的。建立一个真正适合挖掘算法的分析模型是数据挖掘成 功的关键。 ( 4 ) 数据挖掘：根据数据功能的类型和和数据的特点选择相应的算 法，在净化和转换过的数据集上进行数据挖掘。 ( 5 ) 结果分析：解释并评估结果。其使用的分析方法一般应视数据 挖掘操作而定，通常会用到可视化技术。 ( 6 ) 知识的同化：将分析所得到的知识集成到业务信息系统的组织 结构中去。 数据挖掘的方法有神经网络方法、遗传算法、决策树方法、粗集方法、 覆盖正例排斥反例方法、统计分析方法、模糊集方法等。 1 4 论文背景和工作内容 随着多媒体压缩技术和计算机性能的显著提高以及宽带网络的飞速 发展，多媒体信息系统包括m p e g 数字视频的运用变得日益广泛，例如数 字图书馆、远程教育、视频点播、数字视频广播、交互电视等。由于m p e g 格式的视频数据量非常大，因此迫切地需要有效的索引、浏览和检索工具。 文本形式的索引方法如关键字，是一种直接表示视觉内容的方法，但是它 需要很多人工的劳动。随着基于内容的视频检索的提出，镜头检测技术已 成为人们关注的焦点。最初的视频镜头检测研究大多都是基于未压缩的视 频。随着多媒体压缩技术的不断发展，大量的视频都是以m p e g 压缩格式 存储，先前的很多处理技术就不能再适用了，除非先将视频解压缩后再处 理。现在已经有一些研究者提出直接作用于m p e g 视频的镜头检测技术。 在压缩域进行视频镜头检测有很多优点：第一，不必进行解爪缩，降低计 算复杂度，同时节省解压缩的时间和解压缩后的存储空间。第：，压缩视 6 重庆邮电大学硕士论文 第一章绪论 频的码率更低，所以处理速度更快，第三，编码的视频流已经包含丰富的 预先计算好的特征，如运动矢量m v 和块的d c t 系数等，这些特征非常 适用于视频镜头的检测。 粗糙集理论2 2 1 是处理不完整数据和不精确知识的强有力的数学工具， 在知识获取、知识分析和决策分析等方面得到了广泛的应用【2 ”，其优点是 不需要预先给定检测对象的某些属性或特征的数学描述，而是直接从给定 问题的知识分类出发，通过不可分辨关系和不可分辨类确定对象的知识约 简、导出问题的决策规则。 利用粗糙集理论的数据处理方法来进行视频镜头的检测，不需要人为 设定阚值，可以大大提高检测的适用性。 本文在这样的研究背景下实现一种基于帧亮度信息以及运动信息的 视频镜头检测方法。该方法将粗糙集理论应用于视频镜头检测。论文的主 要研究内容包括：基于粗糙集理论的视频镜头检测模型的建立、实现以及 仿真试验验证。 本论文工作得到重庆市教委科学技术研究项目( n o k j 0 5 0 5 0 9 ) 基于 m p e g 7 标准和数据挖掘的视频检索和分类、重庆市自然科学基金 ( n o 2 0 0 5 b b 2 0 6 3 ) 面向海量数据的智能挖掘理论及应用研究的资助。 1 5 论文结构 本人在现有的各种视频镜头检测方法的研究基础上，提出一种基于粗 糙集的视频镜头检测方法。该方法从视频中提取各种特征信息，形成包含 所需属性集的二维决策表，再利用粗糙集平台，对决策表进行数据预处理、 属性约简和值约简，提取出镜头检测的决策规则，通过规则匹配，实现视 频镜头的检测。 本论文的组织结构如下： 第一章：绪论。介绍了视频检索及镜头检测技术的发展状况、数据挖 掘理论以及本论文的研究背景和研究工作。 第二章：相关理论与技术简介。详细介绍了本文的相关理论与技术， 包括m p e g 标准、粗糙集理论以及当前各类典型的镜头检测方法，这些方 法包括基于直方图的镜头检测方法、基于运动的镜头检测方法、基于压缩 域的镜头检测方法以及基于数掼l ：挖掘的镜头检测方法。 第三章：基于租糙集的视频镜头检测方法。详细介绍了视频信息系统 的建立、信息数据的提取，属忡集的确定以及决策规则的提取过程。 7 重庆邮电大学硕士论文 第一章绪论 第四章：方法实现与测试。对本文方法进行仿真测试，并进行了对比 实验。 第五章：全文总结与未来工作展望。对本论文的主题进行讨论，总结 研究的贡献，并探讨其中的问题、限制与未来的研究方向。 重庆邮电大学硕士论文 第二章相关理论与技术简介 第二章相关理论与技术简介 2 1m p e g 视频压缩标准 2 1 1m p e g 标准概述 m p e g ( m o v i n g p i c t u r e e x p e r t s g r o u p ) 是i s o 为制定有关动态图像压 缩标准而成立的一个专家组，现已经公砸了多个版本的标准：m p e g l 、 m p e g 2 以及m p e g 4 等。其中m p e g i 是m p e g 标准集的基础，m p e g 2 和 m p e g 4 都是在m p e g l 的基础上所作的改进和扩展，以满足不同的应用要 求和环境。 m p e g 标准是一个通用标准，既考虑了应用要求，又独立于具体的应 用。m p e g 标准可以用于下列数字存储媒体上 2 4 1 ：光盘( c d r o m ) 、数 字录音带( d a t ) 、磁盘以及通信网络( 综合业务数字网、分组交换网以及 局域网等) 。 m p e g 标准不仅考虑了视频数据压缩，而且还考虑了音频数据压缩以 及两者之间的同步问题。作为m p e g 视频压缩算法，必须具有和存储相适 应的性质，即能够随机访问、快退跨进检索、倒放、音像同步、容错能力、 延时限制、可编辑性以及灵活的视频窗口格式，实现这些特性对各种应用 都是非常重要的，因而也构成了m p e g 视频压缩算法的基本特征。 2 1 2m p e g 2 标准的图像组织结构 m p e g 2 是一组用于视音频压缩编码及其数据流格式的国际标准。它定 义了编解码技术及数据流的传输协议，制定了m p e g 2 解码器之间的共同 标准( m p e g 2 编码器之间尚无共同标准) 。 m p e g 2 的图像帧分为三类：i 帧、p 帧和b 帧。 i 帧采用与j p e g 类似的编码方法进行编码，编码时不需要参考其它 帧，压缩比蛀低，可作为随机访问点和其他图像编码帧的参考帧。 p 帧需要利用前面的i 帧或p 帧信息进行编码和解码，同时又是后续 p 帧的参照帧，它利用了瞬时冗余特性，获得较高的i i 缩比。然而只有对 所参照的i 帧和p 帧完成解码后爿能访问p 帧。 9 重庆邮电大学硕士论文 第二章相关理论与技术简介 b 帧需要利用前面和后面的i 帧、p 帧信息进行编码和解码，但它本 身不可以作为参照帧，由于它采用了双向运动补偿预测技术，故它的压缩 比时最高的。 在m p e g 2 视频压缩算法中采用一种叫做画面组( g o p ) 的数据结构。 g o p 中有固定数目的连续帧集合，并保证g o p 的第一帧就是l 帧。一帧 图片是由若干组块成的。一个组块是一系列任意数目的宏块，它按照光栅 扫描顺序从上到下、从左到右在视频流中出现。组块又是由若干宏块构成， 宏块包含一部分亮度分量和一部分色度分量。宏块有三种类型的色差格 式：4 ：2 ：0 ，4 ：2 ：2 和4 ：4 ：4 。一个4 ：2 ：0 宏块由六个块组成。这种结构包括四个 y 块，一食c b 块和一个c r 块；一个4 ：2 ：2 宏块田八个块组成。这种结构包 括4 个y 块，两个c b 块和两个c r 块。一个4 ：4 ：4 的宏块由1 2 个块组成这 种结构包括四个y 块，四个c b 块和四个c r 块。块是源图像数据和重构数 据，是d c t 变化单元，而宏块则是运动补偿和预测的基本单元。 2 1 3m p e g 2 标准的压缩算法 m p e g 2 视频压缩算法采用两种基本技术：一是基于块的运动补偿预 测，以缩减时间冗余：二是基于d c t 的变换编码，以缩减空间冗余。运 动补偿预测技术采用纯预测编码和插值预测编码两种编码方法。剩余的信 号在缩减空间冗余时进一步的被压缩。与运动相关的信息包含在1 6 x1 6 块 中，与空间信息一起进行d c t 变换。为了获得最大限度的编码效率，使 用可变长熵编码器来压缩运动信息。 运动补偿预测是一种降低时间冗余度的有效方法，在许多视频压缩算 法中得到了广泛的应用。运动补偿预测技术假设每一帧图像都是过去某个 帧图像为原型并经过变换得到的。这种变换是局部的，即图像上各点的位 移方向和大小不必相同。运动向量值必须正确编码，因为它是重建图像所 必须的。 m p e g 2 的一个重要特点就是采用了运动补偿插值编码技术。它改善了 随机访问性能，提高了运动视频图像的质量。在时间范畴内，通过对一路 低速率的子信号编码，附加修正项插值，可获得全分辨率信号。而且通过 插值编码，可以获得极高的压缩比。 m p e g 2 的视频编码和解码步骤如下： 1 每个g o p 的第帧总是i 帧，它是按照块顺序编码的，即使用d c t 变换、量化过程和熵编码方法进行中度压缩，并作为参照帧和随机访问点。 重庆邮电大学硕士论文 第二章相关理论与技术简介 2 当g o p 出现b 帧或者p 帧时，将启动运动补偿预测过程，以获得 最佳的压缩比。 3 对于p 帧的编码，运动补偿预测算法使用最近的一个i 帧或者p 帧 作为参考帧。如果在当前帧的宏块与参考帧的宏块之间找到了一个较好的 匹配，则对当前帧的宏块的运动向量和得到的预测误差进行编码；否则， 只对该宏块进行帧内编码。 4 对于b 帧的编码，其处理过程比较复杂，因为必须考虑到四种可能 性：正向预测、反向预测、插值和宏块的帧内编码。如果使用插值预测， 则必须使用前后两个最近的i 帧和p 帧作为参照帧，并产生两个运动向量 和一个预测误差块，并且应当首先传输p 帧和b 帧的参照帧。 5 m p e g 2 标准采用了两种结构的量化器，根据帧内编码和帧间编码不 同的d c t 系数性质采用不同的量化矩阵，通过q 系数来控制编码，以适 应编码器的输出数码率。由于预测误差块主要是高频信号，可以采用粗粒 度的量化器，以降低数码率；帧内编码块的信号频率范围较宽，则应当采 用细粒度的量化器进行精确编码；否则，对于那些光滑边界的块，很小的 误差都会产生可察觉的块边界。因此，为了适应人的视觉特性，必须对量 化器进行修正，重点对图像中的视觉效应敏感部分进行精确编码，以消除 块效应现象。这样，既可以满足图像数码率的要求，又能改善图像质量。 6 m p e g 2 的熵编码过程是通过v l c 熵编码表来实现的。d c t 系数的 编码表是h 2 6 1 标准中所使用的变长码的一个超集。如果在一个处理器中 同时实现这两个标准，则使用一个变长码既可，以减少开销。 在参考帧之间增加一定数量的b 帧，既可以降低b 帧与参考帧之间的 相关性，也可以降低参考帧之间的相关性，b 帧的数量随着视频内容的变 化而变化，但对于大多数视频内容而言，以1 1 0 秒的间隔插入b 帧是合适 的。 m p e g 2 标准对解码过程进行了规定，但是实现解码的方法有很多种。 典型的解码过程是先对位流进行解码，将位流分解成运动信息、量化器步 长、块和量化d c t 系数几个部分。量化d c t 系数经过解码后送入i d c t ， 从i d c t 输出的重建波形还要叠加上预测结果。 2 2 粗糙集理论 粗糙集理论是一种刻划不完整惟和不确定性的数学工具，能有效地分 析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的 重庆邮电大学硕士论文 第二章相关理论与技术简介 知识，揭示潜在的规律。 粗糙集理论近年来受到了国际上越来越多的学者的关注，目前已举办 了几届粗糙集的国际学术会议，成立了粗糙集的国际学术团体，并在 i n t e r n e t 上定期发布电子公告。由于粗糙集能够定量处理不确定的信息和 数据，因此它作为一种具有极大潜力和有效的知识发现工具受到人工智能 工作者的广泛关注。 知识理论的基础概念是分类和范畴，实际上范畴是特征子集对对象的 描述，是给定知识库中可获得的知识。某些范畴在一个知识库中是可定义 的，但在另一个知识库中却不可定义，粗糙集正是对这些无法定义的范畴 进行处理，使其能够近似定义。 粗糙集理论中的知识表达方式一般采用信息表或称为信息系统的形 式。我们定义信息表系统s = ，其中，u 是对象的集合，也称 为论域，r = c u d 是属性集合，子集c = a ，l i = 1 ，m ) 和d = d ) 分别称为 条件属性和决策属性集，u = “，石：， 是论域，a i ( 工，) 是样本x j 在属性口， 上的取值，f ：u r 斗v 是一个信息函数，它指定u 中每一个对象工的属性 值。 在粗糙集理论中，“知识”被认为是一种将现实或抽象的对象进行分类 的能力。所谓知识获取【”1 ，就是要从大量的原始数据信息中分析有用的规 律信息，即是将知识从一种原来的表达形式( 原始数据表达形式) 转换为 一种新的目标表达形式( 人类或者计算机便于处理的形式，如逻辑规则 等) 。 由于粗糙集理论在处理的时候通常都是从决策表开始，因为利用粗糙 集理论进行数据挖掘的首要步骤就是如何将研究领域的信息转化为决策 表。通过定制一些能描述所研究领域的个体特性的属性，将每个样本的属 性值提取出来，最后得到决策表。 从决策表中寻找决策规则的一般步骤如下： ( 1 ) 数据预处理：包括删除重复记录、决策表补齐、数据离散化； ( 2 ) 删除多余属性，求出属性约简； ( 3 ) 删除多余的属性值，得到值约简； ( 4 ) 根据值约简求出逻辑规则。 跟其他数据挖掘的理论和工具相比，粗糙集理论主要应用在对不完 整、不精确信息的表达与处理上，它从新的视角出发对知识进行了定义， 把知识看作是天于论域的划分，并引入代数学中的等价关系来讨论知识。 同其他处理4 i 完整、不精确知识的数学理论相比，粗糙集理论的主要优势 2 重庆邮电大学硕士论文 第二章相关理论与技术简介 在于它不需要任何预备的或额外的先验知识，比如统计学中的概率分布， d e m p s t e r - s h a f e r 证据理论中的基本概率赋值，或者f u z z y 集理论中的隶属 度等，它主要利用集合的上近似集与下近似集，根据集合中存在的不可区 分关系来解决知识的分类问题。 2 3 典型的镜头检测方法 2 3 1 基于直方图的镜头检测方法 基于直方图的方法是最普遍的镜头检测方法，它处理起来简单方便， 而且对于对多数视频，均能达到比较好的效果。现对几种有代表性的算法 进行分析比较。 基于直方图的算法是在基于像素的比较上发展起来的。基于像素的算 法计算两帧中每个对应像素的亮度平均绝对变化值，第k 帧和第k + l 帧的 帧差异值定义为： z 仲，七+ f ) 2 高蒜l i a x , y ) 一( x , y ) l ( 2 - 1 ) 式( 2 1 ) 中m 和n 分别是帧的水平和垂直方向的像素数，l k ( x ，y ) 和 l 川( x ，y ) 分别是第k 帧和第k + l 帧在( x ，y ) 处的亮度值。该算法对帧内各像素 的变化很敏感，在镜头转换时会引起帧差值z 的跳变，但是对镜头内的对 象和摄像机的运动也过分敏感，视频内对象和摄像机镜头的运动都会引起 较大的像素亮度变化，从而使z 值变大，导致视频镜头边界的误判。 解决这个问题的方法是利用帧直方图，基于直方图的算法通常是将相 领域的各个像素的灰度、亮度或颜色等分成n 个等级，再针对每个等级统 计像素数做成直方图比较，对每一帧计算直方图差值如下： 1 上 z ( k ，七+ ，) 2 者i 魂( 0 一+ ，o ) j ( 2 2 ) 其中n 是灰度级数或颜色数等，m 是一帧的像素数。该方法统计了总 体的灰度或颜色分布数量，它对镜头内的运动和摄像机的慢速运动有着良 好的容忍能力，只是在镜头内容快速变换和镜头渐变时可能会引起误检或 漏检。文献【26 】还提到一种交集直方图算法，其算法可以写成： l z ( k ，k + i ) = l 一百1 m i n ( h _ ( 0 ，吃“( f ) ) ( 2 3 ) 重庆邮电大学硕士论文 第二章相关理论与技术简介 m 与n 的定义与式( 2 2 ) 相同，它计算了两帧问有相同灰度或颜色 值的像素数。其本质与直方图差值法是相同的。 上述方法是计算整体的灰度或颜色的变化，而没有考虑镜头内局部的 运动。若局部运动引起灰度或颜色产生较大的变化就会导致误检。为了减 少运动、干扰等引起的帧差值的变化，可以将各帧分块处理，将每个帧分 成4 x 4 个大小相同的块【2 ”，分别比较每个块的颜色直方图，差值最大的块 被剔除，余下块的直方图差值再做帧差值的计算。该方法对检验包含摄像 机镜头的推移和缩放是有改进效果的，但是对检测诸如淡入淡出等特殊效 果就会失效。同时在某些光线变化比较剧烈的情况下，帧差值z 也会受到 较大干扰。 、 在上述算法中，定义好z 后，通常再确定一个阈值t ，若z t ，则镜 头边界存在。而视频镜头的转换有切变与渐变之分，它们的特征是不同的。 通常渐变过程的帧差异值幅度要比切变小，但是渐变有一个持续过程。用 单一的阈值来判断难以适应各种情况。为此z h a n g 等人提出了双阙值的算 法【28 】来分别检测检测镜头切变和渐变，如图2 1 所示： 图2 1 镜头检测帧差异值的分布及各种阈值【2 8 】 若帧差异值大于t k ，则认为发生了镜头切变，若帧差异值小于t k 大 于t l ，则认为开始发生镜头渐变，此时累加后的帧差异值，直到累加值达 到t k ，认为镜头渐变结束。若在累加途中帧差异值回落到t l 以下，则认为 无镜头转换，累加器清零，重新开始判断。该方法考虑到了镜头切变和镜 头渐变的差异。针对它们的特点分别榆测，能满足一般的镜头检测要求。 并且要累计帧差异值到t k j 认为有镜大渐变，因此对突发的噪声有一定的 抗干扰能力。但对于那些变化不很明镀的渐变过程，很可能在累加到t 4 重庆邮电大学硕士论文 第二章相关理论与技术简介 前就停止了，而如果一个渐变过程中的某两个相邻帧变化很小( 小于t ，) ， 就会使累加过程停止，可能造成漏检。以上算法在同一段视频中都采用相 同的阈值，这样，对内容变化较大的视频可能会产生误检，而对内容变化 较小的视频则可能产生漏检。 总的来说，基于直方图的方法比较方便简单，易于实现，计算复杂度 较低，而且在一般的镜头切变的判断上可以得到较好的结果，除了使用图 像的颜色值或亮度来统计直方图，还可采用r g b 、y u v 等三基色来进行 直方图统计，其思想和方法都是类似的，并且被证明是简单有效的镜头切 变检测方法。对于一般的切变和渐变镜头，如果阈值设置得当，直方图算 法可以达到较好的结果。 2 3 2 基于运动的镜头检测方法 为了使镜头内各帧间的帧差值保持在较小的水平以使镜头转换边界 更加容易判断，就需要充分考虑镜头内对象及摄像机的运动，尽量将它们 的影响消除。基于运动的算法充分考虑了同一镜头内对象及摄像机的运动 情况和特征，通过运动补偿等方法来减小对象和摄像机运动造成的镜头内 帧差值的变化。 文献f 29 i 提出了一种块匹配算法，将各帧分块处理，第k 帧的第i 块 b d k ) 和第k + l 帧的相应块b i j ( k + 1 ) 的差异d k k + ( i 1 由下式定义： d i j + ，( d = n f m d ( b j ( | | ) ，6 f ，( 七+ f ) ) j 【1 , n 。d i d a l c 。】 ( 2 4 ) d ( b i ( k ) ，b i j ( k + 1 ) ) 是通过比较两块各像素的亮度来计算的，n 。n d id a t 。为 与第k 帧中b i ( k ) 相对应的第k + l 帧的备选块的数目。在所有块的不相似值 计算好后，归一化得d k k + l ( i ) ，最后得到帧差值： k z ( k ，j + ，) = 乞以川( f ) ( 2 5 ) l - i 其中n b i o 。k 。为总的块数目，c i 为各个块的权重。这样，两帧的各个块 之间经过运动补偿后再计算各个块的帧差值，可以避免由于快速的运动引 起的误判。 该算法是计算每个块中对应像素的亮度差值，虽然对各块进行了运动 补偿，但发生在块中的局部运动会引起误检。若将h 述方法改为计算各个 对应块的平均亮度的变化值，虽然会丢失一些位嚣信息，仃 是可以改善算 法对局部运动的容忍度 3 0 1 。 重庆邮电大学硕士论文 第二章相关理论与技术简介 计算经过运动补偿后的各个块的亮度差超过某一阈值的块的数引2 8 】 可以进一步增强对块内局部运动的容忍度，当此数目超过某