（计算机应用技术专业论文）基于克隆选择和统计学习的视频检索.pdf

摘要 摘要 视频包含了最丰富的信息而与此同时也意味着它需要巨大的存储容量和存在着 复杂的语义内容。用传统的手工索引和顺序查找方法在大量的视频数据中查找所需的 视频片断是一项繁琐且耗时的工作，很难满足视频数据库的性能需求。而用户所需要 的是通过内容进行查找，即通过些给定的样例或特征描述便可得到所期望的视频片 断。由于视频数据的复杂结构和时问上的多变性使得通过内容对视频进行索引成为大 家关注的热点和难点问题。研究人员已经提出了各种各样的方法与技术试图解决这个 难题。基于内容的视频索引中的主要步骤有视频分割、关键帧的选择、静态特征与动 态特征的提取以及视频聚类等。论文中，我们在视频分割、关键帧选择方面做了以下 主要工作： 1 、讨论了视频镜头边缘检测问题并对镜头分割中的常用算法进行了分析。 2 、我们在分析、对比原有视频字幕提取算法的基础上提出了一种基于支撑矢量 机的小波域视频字幕检测与提取算法。它利用小波变换域中的统计特征和支 撑矢量机分类器，使得算法有较强的鲁棒性和普适性。 3 、视频的关键帧表示适合于在有限的存储空间或传输带宽条件下对视频进行检 索与浏览，因此生成与具体条件相适应的关键帧就显得至关重要。为此，本 文提出了一种条件约束的关键帧选取算法，它可以根据具体的要求动态调整 所生成关键帧的帧数。 4 、通过分析视频关键帧构建了一个适合关键帧表示的数学模型，在这个模型的 基础上我们提出了一种基于多克隆选择的视频关键帧选取算法，该算法把选 取关键帧的问题转化为一个优化的问题并用多克隆选择算法求解，仿真实验 表明本文的算法是可行的且有效的。 关键词：视频检索、关键帧、直方图、特征提取、文本检测 a b s l r a c t a b s t r a c t v i d e oc o n t a i n st h em o s ta f f l u e n ti n f o r m a t i o nb u t i m p l i e sh u g es t o r a g e a n d c o m p l i c a t e d s e m a n t i c s t os e a r c hf o rr e q u i r e df r a g m e n t sa m o n g h u g eq u a n t i t yo f v i d e o i sa t e d i o u sa n dt i m ec o n s u m i n gt a s kf o rt r a d i t i o n a lm a n u a li n d e x i n ga n ds e q u e n t i a ls e a r c h i n g m e t h o d sw h i c hc e r t a i n l yc a r ln o tm e e tt h ep e r f o r m a n c er e q u i r e m e n t so fv i d e od a t a b a s e s w h a tt h eu s e r sw a n ti st oq u e r yb yc o n t e n t s ，t h a ti s ，t og e tt h ed e s i r e df r a g m e n t so fv i d e o w i t h j u s ts o m eg i v e ne x a m p l e s o rf e a t u r ed e s c r i p t i o n s b e c a u s eo f t h ec o m p l i c a t e ds t r u c t u r e a n dt e m p o r a lv a r i a t i o no fv i d e od a t a , i ti s v e r yd i m c u l t t oi n d e xv i d e o b yc o n t e n t r e s e a r c h e r sh a v ew o r k e do u tv a r i o u sm e t h o d sa n dt e c h n i q u e st os o l v et h ep r o b l e m t h e e s s e n t i a l s t e p s f o rc o n t e n tb a s e d v i d e o i n d e x i n g a r ev i d e o s e g m e n t a t i o n ，k e yf r a m e s e l e c t i o n ，s t a t i ca n dd y n a m i cf e a t u r ee x t r a c t i o na n dv i d e oc l u s t e r i n g i nt h i sp a p e rw e h a v e d o n et h ef o l l o w i n gg r o u n d w o r ka r o u n dt h i sf i e l d ： l 、d i s c u s st h ep r o b l e mo fv i d e os h o t se d g ed e t e c t i o na n ds u m m a r i z ee x i s t i n ga l g o r i t h m s i nt h ef i e l d 2 、b a s e do nt h ee x i s t i n ga p p r o a c h e sw er e p r e s e n tan e wv i d e oc a p t i o ne x t r a c t i o na l g o r i t h m 州d e oc a p t i o nd e t e c t i o na n de x t r a c t i o ni nw a v e l e td o m a i nb a s e do ns u p p o r tv e c t o rm a c h i n e i t u t i l i z e ss t a t i s t i c a lf e a t u r e si nw a v e l e tt r a n s l a t i o nd o m a i na n ds u p p o r tv e c t o rm a c h i n e c l a s s i f i e rt oa c h i e v ear o b u s ta n du n i v e r s a lp e r f o r m a n c e 3 、v i d e or e p r e s e n t a t i o nb yk e yf r a m e si ss u i t a b l ef o rt h ep u r p o s eo fv i d e or e t r i e v a la n d b r o w s i n gi nl i m i t e ds t o r a g eo rt r a n s m i s s i o nb a n d w i d t he n v i r o n m e n t s i nt h i sc a s e ，t h e t o t a lk e yf r a m en u m b e r d e p e n d i n g o nt h ec o n c r e t ec o n d i t i o n si so f g r e a t i m p o r t a n c e s o ， w e r e p r e s e n tak e yf r a m ee x t r a c t i o na l g o r i t h mi nc o n s t r a i n e dc o n d i t i o n ，w h i c hw e c a n e a s i l ya d j u s tt h ek e y f r a m en u m b e r a c c o r d i n g t oa c t u a lr e q u i r e m e n t s 4 、b ys t u d y i n gk e yf r a m ee x t r a c t i o nq u e s t i o n sw e b u i l dam a t h e m a t i c a lm o d e la n db a s e d o nt h em o d e lan e wk e yf r a m ee x t r a c t i o na l g o r i t h mi sr e p r e s e n t e d i tt u r n sk e yf r a m e e x t r a c t i o ni n t oa no p t i m i z a t i o np r o b l e m w ea p p l yp o l y c l o n a ls e l e c t i o na l g o r i t h mt o s o l v et h em o d e l i ti ss h o w nt h a tt h ea l g o r i t h mi sf e a s i b l ea n de f f e c t i v ew i t ht h er e s u l t s o f c o m p u t e r s i m u l a t i o n s k e yw o r d s ：v i d e or e t r i e v a l ，k e yf r a m e ，h i s t o g r a m ，f e a t u r ee x t r a c t i o n ，t e x t d e t e c t i o n 声明 y 6 9 5 6 8 6 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文( 保密的论文 在解密后遵守此规定) 。 本人签名 导师签名：日期 第一章绪论 第一章绪论 这一章主要介绍信息检索的发展历史，基于内容的视频检索发展的动机、现状和 方向，最后列出了本文的内容提要和安排。 1 1 课题研究背景 学者c a l v i nm o o r e s “1 于1 9 5 1 年首次提出“信息检索”的概念，主要描述了如下 过程：客户提交一个找寻信息的请求，然后通过某种转换或计算得到与客户请求相似 或相关的资料。 可以说最初的“信息检索”仅仅是对纯文本文件内容进行操作，并没有考虑到信 息载体会以图像、声音、文字和光电等形式表现的多媒体数据。然而随着多媒体技术 和w e b 技术的发展，包括图像、视频、音频等的多媒体信息大量涌现，对这些海量 的而且包含大量非结构化信息的数据如何组织、表达、管理、查询和检索就成为迫切 的需求。近年来，基于内容的视频与图像数据库检索技术已成为一个研究的热点，也 成为未来信息高速公路、数字图书馆等项目中的关键技术。视频检索就是要从大量的 视频数据中找到所需的视频片断。例如从一场比赛近两个小时的录像带中如何能把射 门镜头迅速提取出来，如果用传统的视频检索通过快进或快退等顺序的方法进行人工 查找，不仅耗时而且非常繁琐，这显然无法满足巨容量的多媒体数据库的要求。而用 户则希望只要给出一个射门的例子或是特征描述，系统就能自动检索到所需的射门视 频片断点，即实现基于内容的视频检索( c b v r , c o n t e n t - b a s e d v i d e o r e t r i e v a l ) 。目前， 基于内容的视频检索的工作主要集中在识别和描述图像的颜色、纹理、形状、空间关 系的基础上，对视频数据进行镜头边缘检测、关键帧选取以及故事情节的重构。由此 可见，这是一门涉及面很广的交叉学科，涉及到图像处理、心理学、脑科学、计算机 视觉、信号处理、统计方法学、模式识别、数据库、计算机网络、视频通信、和人机 交互等诸多方面的理论，还需从认知科学、人工智能、数据库管理系统、人机交互、 信息检索等领域引入新的媒体数据表示和数据模型，从而设计出可靠、有效的检索算 法、系统结构以及友好的人机界面0 1 。基于内容的视频检索具有如下特点0 1 ： 1 突破了传统的基于表达式检索的局限，直接对视频信息进行分析，抽取特征 利用这些特征建立索引进行检索； 2 提取特征方法多种多样。图像特征如颜色、纹理、形状轮廓、位置、空间关 系等： 基于克隆选择和统计学习的视频检索 3 基于内容的视频检索是一种近似匹配。在检索的过程中，它采用相似性匹配 的方法逐步求精来获得查询的结果。即查询是一个迭代过程，不断减小查询 结果的范围，直到定位到目标。这一点与常规数据库检索的精确匹配方法有 明显不同： 4 大型数据库( 集) 的快速检索。在实际的多媒体数据库( 集) 中，数据量巨 大，种类繁多，因此要求c b v r 技术也能像常规的信息检索技术样，快 速地实现对视频信息的检索“1 。 1 2 课题研究现状 基于内容的视频检索一经提出，便得到国内外信息领域科技人员的广泛重视并迅 速成为一个非常活跃的热点研究领域。基于内容的视频检索的发展也得到许多国际学 术组织的重视和关注，在国际上每年召开的有关多媒体技术的学术大会中，有许多重 要的系列大会都开辟了基于内容的视频检索主题和分会，而i e e e 和s p i e 都组织了 专门的基于内容的多媒体信息检索会议。这些都极大地推动了基于内容的视频检索的 发展。虽然当前的c b v r 技术的研究还不成熟，但是当前已经有一些实验性的视频 检索原型系统被开发出来。尽管它们的性能还不足以应用于商业目的，但其理论价值 值得参考，比较典型的系统有： 1 、q b i c q b i c ( q u e r y b yi m a g ec o n t e n t ) 是由i b m 公司著名的a l m a d e n 实验室开发的。它 可能是目前应用最广的图像视频检索系统，如旧金山现代艺术博物馆以及法国文化 部等机构。虽然q b i c 只提供了3 种属性的检索功能：颜色属性、形状属性和纹理属 性，但它的检索效率非常高。颜色特性的查询包括颜色百分比查询和颜色分布查询， 利用颜色百分比查询，用户可以找到具有相似颜色及比率的图像，而利用颜色分布查 询可进一步找到不仅颜色相似且颜色分布也相似的图像。纹理特性是对图像中线条的 粗糙性、对比性、方向性三者的综合考虑。形状属性查询包括对象形状查询和轮廓查 询。q b i c 除了上面的基于内容特性的检索，还辅以文本查询手段。例如为旧金山现 代艺术博物馆的每幅作品给予标准描述信息：作者、标题、日期，许多作品还有内容 的自然描述。 2 、，i r v i r a g e 公司的v 1 r ( v i s u a l i n f o r m a t i o n r e t r i e v a l ) 图像引擎提供了四种可视属性 检索( 颜色、成分、纹理和形状) 。每种属性被赋予0 到1 0 的权值。通过颜色特性检 索是最简单明了的，该软件对选出的基础图像的色调、色彩以及饱和度进行分析然 第一章绪论 后在图像库中查找与这些颜色属性最接近的图像。成分( c o m p o s i t i o n ) 特性指相关颜 色区域的近似程度。用户可以设定一个或多个属性权值来优化检索。要达到最佳平衡 度需要反复试验，但检索过程是相当快的。在结果显示矩阵中可以选择查看3 、6 、9 、 1 2 、1 5 或1 8 个简图。通过对四个属性权值的调整，显示出不同的检索结果。简图是根 据相似度降序排列。点击简图标题将得到该图像的一些详细说明，包括v i r a g e t 十算出 的相似比。 3 、v i d e o q 是一套全自动的面向对象基于内容的视频查询系统。它拓展了基于关键字或是主 题浏览的传统检索方式，提出了全新的基于丰富视觉特征和时空关系的查询技术，可 以帮助用户查询视频中的对象。其目的在于探究视频中潜在的所有视觉线索并用于面 向对象基于内容的视频查询中。v i d e o q 所具有的特征如下： 全自动切分并跟踪视频中任意形状的对象； 提供包括颜色、纹理、形状和运动在内的丰富视觉特征库； 基于多对象时空关系( 包括绝对位置和相对位置) 的视频检索： 除了通过用草图来查询之外，用户还可以浏览视频库或选择采用关键字来查询视 频。其中视频根据各自的主题被分类保存，以便于用户的浏览和定位。每一段视频还 同时用手工进行标注，以使用户可以通过输入简单的关键字来查找视频。 4 、w e b s e e k w 曲s e e k 是一个面向w w w 基于内容的图像视频查询和分类系统。w e b s e e k 通过一个w e b 自动收集网络中的图像和视频。该引擎能够对视频或图像自动分析和建 立索引，并可以将它们归入一定的主题类别中。该系统的创新之处在于它能够有机的 结合文本和视觉特征来提供对图像视频的查询和分类。整套系统包括了某些功能强 大的模块，主要有基于内容的图像检索功能，根据用户相似度反馈的查询优化，视觉 信息的自动提取，查询结果视频图像的缩略显示，图像视频的主题浏览功能，基于 文本查找功能以及对查询结果的操作( 如插入、删减、合并等) 。 全新的算法被用于自动对任意图像视频进行语义层次上的主题分类。一个图像 视频类别以半自动的方式在w e b s e e k 原型系统中被构造出来。该分类算法探索了视 觉特征( 如颜色、纹理和空间层次) 与文本特征( 如相关的h t m l 标识符、标题和文 章) 之间最优的结合点。 另外还有许多类似的系统，例如加利福尼亚大学s a n t ab a r b a r a 分校的n e t r a 、伊 利诺依大学的m a r s 、c m u 的i n f o m e a i a 等。 尽管对视频检索的研究十分活跃，许多有价值的方法也被提出。但它们离实际应 基于克隆选择和统计学习的视频检索 用还有很大的距离，还有许多问题需要解决和面对如： 1 、视频相关反馈 在视频检索中引入相关反馈的方法可以把用户也作为检索中的一部分，能够得到 使用户更满意的检索效果，但是视频相关反馈还有很多问题需要解决，如：多少次反 馈是必须的，而多少次反馈将是多余的。由于对视频检索没有一个有效的量化评判标 准，现在对检索结果的评判还是基于人们自己的主观感觉，所以在检索中并不能判断 多少次相关反馈对用户而言是足够的。 还有，在相关反馈中如何使用表达用户的反馈意见? 在现有的研究中总是假设用 户的反馈意见可以使用视频特征权值来表达，所咀通过修改权值进行再检索，得到用 户满意的检索结果。但是，用户对一个视频数据的评价并不是可以用视频的颜色、纹 理、和形状等特征来完全反映的。一般而言用户对视频数据的评价还是一个主观感受。 缸何把用户的主观感受表达出来，是一个很棘手的问题。 2 、联合多特征进行检索 视频数据只是多媒体数据中的一部分，多媒体本质是视频、音频和文本等信息的 融合。在视频数据流中，视频、音频和文本数据都会同时以某种组合出现。如何把音 频和文字信息更有效的利用起来，辅助视频分析，进行视频检索也成为很有意义的研 究方向。而且对于同一种特征，也有不同的表示方法，例如，同样是颜色特征，可以 有直方图特征、颜色矩、颜色集、主颜色等多种特征表示法，它们从不同的角度表示 视频特征，而如何有机地组织这些特征，使应用能够调用合适的特征或特征组合来支 持查询，并按照用户的查询要求合并各种特征的检索结果，是一个值得研究的课题。 另外基于内容的检索也应该结合其它学科领域的成果，如传统的基于文本的信息 检索技术、人工智能等领域中的方法，像布尔检索模型、多个异构特征查询表达和检 索执行、分类和聚类算法、用户交互行为的机器学习等。目前的基于内容的检索系统 要充分利用文本描述属性。基于内容检索系统目前不很成熟，而且有时并不是用户关 心的内容，因此要充分利用现有的文本检索功能并集成到基于内容的检索系统中，以 向用户提供完备的检索能力。 3 、智能化的人机界面 这一技术涉及到用户对内容的感知表达、交互方式的设计、用户如何形成并提交 查询等方面。人在系统中是主动的，除了提供示例和描绘查询基本接口之外，用户的 查询接口应提供丰富的交互能力，使用户在主动的交互过程中表达对媒体语义的感 知，调整查询参数及其组合，最终获得满意的查询结果。用户的查询接口应该是直观 易用的，底层的特征选择对用户是透明的。这里涉及到如何把用户的查询表达转换为 第一章绪论 可以执行检索的特征矢量，如何从交互过程中获取用户的内容感知，以便选择合适的 检索特征等问题。 4 、面向w e b 检索 在当今的信息时代，多媒体内容是人们通信的重要部分。图像、视频和图形内容 组成了当今1 5 的w w w 内容，而且还在飞速增长。w w w 以其生动形象的内容作 为出色的传播方式逐渐代替传统打印电视传播方式。大规模的图像视频媒体的存储 站也已经随时可以访问，可用的数据内容也是形式多样( 新闻、对话、音乐片、和运 动场面) 。为了更好的组织和检索这些几乎是无限的信息十分需要基于w 曲的搜索 工具。对基于文本信息。目前搜索引擎是有办法的，而对w e b 上的视频，虽然己做了 较好的工作，但仍需要技术上的突破使视频搜索引擎能与基于文本的相媲美。 5 、个性化检索 在互联网中每个人的兴趣爱好是不相同的因此对相同信息，不同人的关注程度是 不一样的。在视频检索中要考虑个人检索习惯，提供个性化检索功能。前面提到的视 频反馈本质上给用户提供了一个表达个性的机制，但由于现有的相关反馈假设每个人 的检索评价都是通过视频特征表达的，所以这样的个性化反而失去了“个性化”。在 检索中每个人的个性化就是信息偏好，而这种信息偏好需要对用户处理数据的习惯进 行分析才能知道，也就是机器学习的过程。如何利用机器学习原理模拟用户的个性化 检索十分重要特别是面向w w w 的视频检索系统。 6 、性能评价与非阈值处理 需要有一套能够表达各种场景和事物的标准测试数据来评价检索的效率和效果， 这是一项复杂的工作，要收集大量有代表意义的视频数据，以便能够测试各种算法的 效率。在此基础上，定义标准的性能评价准则，如检索率、查准率、查全率、响应时 间等。这样就可以利用标准的检索性能评价准则来全面检验算法的性能。 在视频检索算法中人们使用了大量的阈值。可以说，这些事先设定的阈值决定了 视频分割和检索性能的好坏。由于这些阈值是从视频数据中测试得到的，它们可以发 挥作用。但是，过多使用阈值也有很大局限性：在一个应用中所使用阚值或阈值组合 在另外的应用中可能效果不好。为了减少过多使用阚值对视频处理所造成的局限性 可以使用两种途径：一是对过多的阈值进行简化；二是使用能够对视频时序特征进行 模拟的模型，实现视频分析。 1 3 课题研究的意义 随着计算机技术、网络技术和多媒体技术的发展和信息需求的不断增长，多媒体 基于克隆选择和统计学习的视频检索 信息已经成为各类信息系统的主要数据来源形式，而在多媒体数据中视频数据占有很 大比重。数字化视频在各个方面的应用越来越普遍，并且每天都有大量视频信息产生， 人们对其进行系统管理和方便快速的检索提出了要求。在这样的条件下，由于传统和 现有的搜索引擎只能完成基于纯文字的检索任务，使得信息检索面临很大挑战：知识 与信息表示形式日趋丰富，如果以多媒体形式存在，传统文字信息检索将基本失去用 武之地。基于此基于内容的视频检索就显得越来越重要。 基于内容的视频检索技术的应用领域非常广泛，本质上这种技术将对媒体的处理 和管理深入到了媒体这一级，使得用户可以更自由地操纵和处理各种媒体信息。早期 对面貌特征和指纹的识别和管理、全文信息检索等都是基于内容检索的一些的尝试。 现在基于内容的视频检索已经发展到更广阔的领域，渗透至国防科技、公共事业管理、 公共安全、国家安全、交通管理、医药卫生、工农业生产、机械制造加工以及娱乐教 育等各个领域。在交通监控系统中，对安装在多个交通路口获取的实时交通监控视频 流进行运动特征分析，挖掘出交通状况和拥塞模式，为交通控制和指挥机关提供决策 支持。在医药领域，利用基于内容的图像检索技术对医学病理图像进行检索，辅助医 生的诊断和治疗。工业生产中，利用这项技术对加工的产品进行质量检测，在新研制 的汽车维修和零件销售中，进行网上选购和订货。农业生产中对农作物进行病虫害的 监测和防治工作。军事领域中，开发智能导弹自动选择目标实施攻击。数字图书馆的 应用，对大规模多主题的视频资料进行分类、聚类等分析，以改善视频的分类与索引。 综上所述，多媒体数据库基于内容的视频检索有着广泛的发展前途，本课题基于以往 研究的成功经验和结果，探讨视频流中文本字幕的自动定位、提取以及视频关键帧选 取的一些方法。 1 4 论文的组织 论文的内容安排如下： 第一章对基于内容的视频检索技术的发展背景和研究现状进行了论述，并指出广 泛展开基于内容的视频检索相关课题研究的必要性和紧迫性，同时给出了论文的 组织结构； 第二章介绍基于内容视频检索的系统结构，给出了一些常用的基本概念和定义， 简要介绍了c b v r 中的一些相关技术，包括镜头边缘检测、关键帧选取、特征提 取以及视频聚类等； 第三章给出了工作中需要用到的一些数学理论的基础知识，简要介绍它们的一些 典型应用，具体包括小波分析的基础理论、统计学习理论以及克隆选择算法等。 第一章绪论 第四章视频流里的文本字幕包含了丰富的语义信息，对于视频内容的理解、索引 和检索具有重要的作用。为此本章在分析、对比原有视频字幕提取算法的基础上 提出了一种基于支撑矢量机的小波域视频字幕检测与提取算法。给出了算法的具 体过程、步骤和仿真实验的结果。 第五章关键帧是从原始的视频文件中抽取的一些静止图像，它们可以概括表示各 个镜头的内容。一方面利用关键帧我们可以方便地对整个视频文档内容进行快速 浏览：另方面，可通过提取每个关键帧的视频特征并建立索引可以实现对视频 内容的检索。经过恰当选择的关键帧既有助于视频的检索与选择，同时又能使视 频清单有更吸引入的视觉效果。为了获得关键帧，在本章我们提出了两种方法。 一种是条件约束的视频关键帧方法，另一种是基于多克隆选择的选取方法： 第六章对论文中所涉及到的工作做了一下总结，并对进一步的研究给出了具体的 研究方向和目标。 基于克隆选择和统计学习的视频检索 第二章c b v r 的系统结构及相关技术 在这一章我们首先介绍了视频检索领域常用的一些基本概念，接下来描述了 c b v r 的整个系统结构并着重讨论了视频结构化的问题，最后简要介绍了视频检索中 一些常用的关键技术。 2 1 基本概念与定义 视频是由一系列被称为“帧”的单个静止图像前后连续组成的，一般帧采样率为 2 4 3 0 帧秒时也就是每秒钟给人播放2 4 3 0 幅图像，给人就造成一种非常平滑的视 频运动，就有视频中的人或物体正在“动”的感觉，而低于1 5 帧秒时就会有停顿感。 c b v r 以视频为研究对象，以视频结构化检索为目的。为了便于下面的论述这里先给 出些c b v r 中常用名词的定义： 定义1 帧( f r a m e ) ：帧是视频流中的基本组成单元，每帧均可看成一个独立的 图像。视频流数据就是由连续图像帧构成的，在p a l 视频格式中，视频采样频率为 2 5 帧秒，n t s c 制式中，视频采样频率为3 0 帧秒。 定义2 镜头( s h o t ) ：摄像机拍下的不间断帧序列，是视频数据流进一步结构化的 基础结构层。一般来讲，同一组镜头中视频帧的图像特征保持稳定。镜头是对视频流 进行处理的最小物理单元，而视频帧是视频流的基本单元，它蕴含了少许的语义内容。 由于在同一组镜头中，属于同一组镜头的图像帧之间的特征保持稳定，如果相邻图像 帧之间的特征发生了明显变化，认为发生了镜头变化，需要对视频数据进行切分。对 视频数据流进行结构化时，首先要找出每个独立的镜头单元，一组组独立的镜头单元 就构成了视频数据流。 定义3 关键帧( k e yf r a m e ) ：关键帧是可以用来代表镜头内容的图像。在切分出 来镜头结构后，关键帧被用来代表各个镜头的特征，进行进一步的结构化。在一组视 频镜头中，一般关键帧数目远远小于镜头所包含的图像帧数目。 定义4 场景( s c e n e ) ：语义上相关和时间上相邻的若干组镜头组成了一个场景，场 景是视频所蕴含的高层抽象概念和语义的表达。由于镜头是由关键帧组成的，所以场 景可以使用属于这个场景的若干镜头所对应的关键帧来表示。 定义5 组( g r o u p ) ：组是介于物理镜头和语义场景之间的结构。例如一段采访录 像，镜头在主持人与被采访者之间频繁切换，整个采访属于个场景，而那些关于主 持人的所有镜头属于一组，关于被采访者的所有镜头属于另一组。 第二章c s v r 的系统结构及相关技术 2 2c b v r 的系统结构 一个完整的视频检索素统如图2 1 所示，它包括两个子系统：数据库生成子系统 和查询子系统，每个子系统由相应的功能模块和部件组成。 图2 1 完整的视频检索系统 视频数据是一个二维图像流序列，它是非结构化的。在上述系统中，要实现基于 内容的视频检索，首先必须对这种非结构化的图像流进行处理，使之成为结构性的 数据，才能提取出各种特征从而达到基于内容检索的目的。这是实现一个高效的视频 检索系统的基础和关键，下面我们对此作进一步的讨论。 2 3 视频内容结构化 视频结构化过程即是对视频流中的连续帧序列进行切分，把一个连续视频流按其 内容展开的不同，将它分成若干语义段落单元。视频流的结构化方法能够从一部很长 的视频中抽象出视频内部隐含的情节发展结构，它为大数据量视频的导航和浏览提供 了一种非常好的手段。 由于视频流有成千上万个图像帧组成，要为每一帧图像建立关于图像底层特征的 索引在时间上和空间上效率都很低，也没有必要。而且，用户对视频进行检索和浏览 时，往往也不需要看整个视频流。所以，在视频结构化过程中，将整个视频划分为若 干级的层次结构，分别对不同层次的视频信息建立索引。一般来说在视频结构化过程 中，可以把连续视频流分割成包括镜头、组和场景等视频单元。具体过程如图2 2 所 示。 在结构化过程中，连续的视频图像帧通过镜头边缘检测被分割成长短不一的镜头 单元；然后对每个镜头单元提取关键帧得到可以表征每个镜头单元的关键帧。由于镜 头长短不一，所以提取的关键帧数目也不一样。接着分析视频关键帧得到视频组；最 基于克隆选择和统计学习的视频检索 后在视频组的基础上得到视频场景。通过这个结构化过程就可以得到视频目录并用它 来作为原始的无结构视频数据流的索引。用户通过浏览视频目录，可以快速了解整段 视频数据所表达的内容，而不用顺序浏览视频数据中所有的图像帧序列。当然，在不 目的应用中视频结构化过程不一定严格遵守上述层次结构。如有的视频结构层次中没 有“组”的概念。而有的系统中则提出了类似于“镜头”的视频段结构。 提篡特量一 桎一t 击一 枧舞* 一 图2 2 视频结构化过程框图 2 4c b v r 中的一些关键技术 基于内容的视频检索其实就是结构化视颏内容并提供检索的过程。结合图2 i 、 图2 2 可以看出在c b v r 中主要包括镜头边缘检测、关键帧选取、特征提取以及视频 聚类等主要内容和技术。 2 4 1 镜头边缘检测 镜头是视频数据的基本单元，大部分视频是通过编辑由一个个镜头连接而成的。 所以基于内容检索的视频处理首先要把视频自动地分割为镜头，以作为基本的索引单 元，这个过程就称为镜头边缘的检测，也叫场景转换检铡( s c e n ec h a n g ed e t e c t i o n ， s c d ) 它是实现基于内容的视频检索的第一步。目前，学界已经提出了大量快速有 效的镜头边缘检测算法，本论文没有涉及到这一方面，但是由于它是视频检索的第一 步，论文中的其它部分需要用到该步骤，故在此对其稍作详细介绍。镜头间的切换主 要有突变和渐变两种，突变是指一个镜头与另一个镜头之间没有过渡，由一个镜头的 瞬间直接转换到另一个镜头的方法，即一个镜头猛然切换到另一镜头也叫直接切换。 直接切换可使画面的情节和动作发生直接的跳跃，不存在时间上的差异。给人以轻快、 第二章c b v r 的系统结构及相关技术 利索的感觉。渐变是指一个镜头到另一镜头的渐渐过渡过程，没有明显的镜头跳跃。 渐变包括淡入( f a d ei n ) 、淡出( f a d eo u o 、慢转换( d i s s o l v e ) 、扫换( w i p e ) 等。将画 面逐渐加强称为淡入，将画面逐渐关闭消失称为淡出；一个画面消失的同时另一个画 面逐渐出现称为慢转换：图像从画面的某一部分开始逐渐地被另一画面取而代之的方 式称为扫换。常用的镜头边缘检测( 镜头分割) 算法有以下几类： 基于灰度的镜头分割方法 l 、直接灰度差方法 该方法直接计算两帧灰度差。 爿f ( x ，力一五( x ，力l ( 2 1 ) 其中一( x ，y ) ，正( x ，y ) 分别代表第1 帧和第2 帧像素( x ，y ) 的灰度，则总的帧差为： f d = m l n ( t y ) ( 2 2 ) 。7 其中m x n 为图像的尺寸。如果总的帧差大于某一设定阈值，则存在镜头突变。 2 、改进方法1 州 该方法只计算方法1 中帧灰度差大于某一阈值z ，即： = 。嚣p 五 ( 2 - 3 ) 3 、改进方法2 ”1 上述两种方法都对相机及物体运动敏感。因此文 5 提出先用3 x 3 平滑滤波，然 后再计算帧差。 基于边缘的镜头分割方法”3 边缘特性可用于镜头分割，首先计算出帧间的总体位移，以此进行配准，然后计 算边缘的数量和位置。帧差由边缘变化的百分比表示，即边缘从一帧到另一帧移进和 移出的比例。由于该方法是先进行配准，然后才进行边缘比较，因此该方法对于运动 是稳健的。但是帧差的计算比较复杂。设见为k 帧中与k + l 帧中最近边缘的距离大于 给定阈值五的边缘像素数目的百分比；同样设a + 为k + l 帧中与七帧中最近边缘的距 离大于给定阈值石的边缘像素数目的百分比，则帧差为： f d = m a x ( p k ，a + 1 ) ( 2 4 ) 基于彩色直方图的分割方法 基于克隆选择和统计学习的视频检索 设日( ，七) 表示帧，颜色直方图中对应颜色为k 的象素点总数。k e o ，】，n 是 离散值域区间的最大值。对于r g b 色彩空间图像每帧都有三个颜色直方图，分别对 应红、绿、蓝三种基本色的直方图。 1 、简单的直方图差 相邻图像帧厂与之间最简单的直方图差定义为： d ( f ，f 。) = i h ( f ，j ) - h ( f ，j ) i ( 2 5 ) 2 、带权重的直方图差 在两个直方图比较中，有可能某些颜色对于比较的结果更重要，因此应该给这些颜色 赋予更大的权重，对于带权重的直方图差表示为： d ( f ，f ) = = r d ( f ，f ) “+ g - - d ( f ，f ) ”一+ b - d ( f ，f ) ( 2 6 ) sj s 其中，g ，6 分别是属于红、绿和蓝颜色的亮度，s 定义为( r + g + b ) 3 3 、均值化后的直方图差 直方图均值化的目的是产生一个均衡酌直方图h u ) a ( f ，) = i h u ，g ) 一h 盯。，g ) j ( 2 7 ) 其中得到均值化的直方图h 。( ，) 和计算日( _ ，) 的思路类似，把像素点的值v 用k 表示。 v , , = i n t 詈老啦- 1 ) + o 5 】 ( 2 8 ) 肛l 蒜丢以 力 ( 2 - 9 ) 。是w 的最d , i e 值。 4 、直方图求交 直方图求交是计算两帧图像，和，之间的相似度a ( f ，f 。) 的常用方法，两幅图像 和f 之间的直方图差j f ) 定义为： 第二章c b v r 的系统结构及相关技术 届“= s ( ，f ) - - e m i n ( h ( f ，) ，h ( f ，朋 ( 2 - 1 0 ) 借助s ( f ，f ) 可以如下定义d ( f ，f 。) ： d ( 厂，厂) ；l 尘或者d ( 厂，厂) ：厶尘 ( 2 1 1 ) ，)h ( f + ，) 按照上述方法，对于不相似的两幅图像进行相似度匹配，将发现其相似值很小。如果 对相同两幅图像进行直方图求交然后计算其相似性，将发现这两幅图像的相似度为1 。 5 、直方图平方差 与单纯的直方图差相比，直方图平方差方法可以放大相邻两帧之间的差别： 圳卜芸型铲( 2 - 1 2 ) 或者 珂胁姜鲤铲( 2 - 1 3 ) h ( f ，j ) 或h ( f ，) 作为分母起到归一化的作用，也可以用： 姒门= 薹嚣溅( 2 - 1 4 ) 来求取两幅图像帧之间的直方图平方差。 压缩域差法 a r m a n ，h s u 和c h i u 通过提取视频压缩域特征来检澳9 镜头边缘是否出现。在这种 方法中，不对图像解压，而是直接j p e g 压缩图像帧的d c t 系数作为帧相似度衡量的 标准。 一般来说在对视频图像处理时，要对图像解压，因为传统的颜色等特征是定义在 像素基础上的，也就是非压缩域基础上的。这样基于压缩域的视频镜头检测可以省去 解压步骤，直接从原始视频数据流中提取特征，从而加快检测速度。 矩不变量法【9 l 图像矩不变量具有比例、旋转、和过渡不变性的特点，是用来表示图像帧的好方 法，可以用来进行镜头边缘检测。这里，图像厶，力的矩定义为： 基于克隆选择和统计学习的视频检索 = x y q f ( x ，y ) 也可以从归一化的图像中心矩定义矩不变量： = 了1 ( x 一班( y 一讲，( x ，y ) 2 元毒手婶“) j 【y 一 。八t 其中，= l + ( p + q ) 2 ，；= 脚l 。，多= m o l 。 ( 2 一1 5 ) ( 2 1 6 ) 从相邻图像帧厂和提取了矩不变特征就可以计算这些矩不变特征的欧拉距离 d ( f ，f 。) 。如果d ( f ，f ) 超过一定阈值则认为，和，间出现了镜头转换。 运动矢量法 镜头缩放运动的出现可以用来进行镜头边缘检测。u e d a ，m i y a t a k e 和y o s h i z a w a 1 0 1 通过块匹配得到的运动矢量特征来检测是否镜头是由于摄像机镜头前后移动引起焦 距变化或摄像机角度转变造成的。 s h a h r a r y b q 用基于区域像素差计算得到的运动矢量特征来判断镜头中是否含有大量的 像机或者对象运动。由于摄像机运动常被不正确的当作渐变，而这种方法判断镜头缩 放等运动达到镜头边缘检测目的。 2 4 2 特征提取 视频分割成镜头后就要对各个镜头进行特征提取，得到个尽可能充分反映镜头 内容的特征空间，这个特征空间将作为视频聚类和检索的依据。特征提取包括关键帧 中的视觉特征和镜头的运动特征的提取。常用特征有颜色特征、纹理特征、形状特征、 运动特征等。 颜色特征“”“ 颜色是一种重要的视觉信息属性，颜色特征具有对于旋转、平移、尺度变化，甚 至各种形变都不敏感、并且计算简单的特点，因此成为在图像索引与检索中应用最广 泛的一个特征。常用的颜色特征形式有颜色直方图( c o l o r h i s t o g r a m ) 、颜色矩“”( c o l o r m o m e n t s ) 、颜色集“”( c o l o rs e t s ) 、颜色聚合向量o “( c o l o rc o h e r e n c ev e c t o r ) 、颜 色相关图“”( c o l o rc o r r e l o g r a m ) 等。在目前基于颜色的视频索引技术中较为成熟的方 法是颜色直方图法。颜色直方图是给定一个离散的颜色空间。把它分为玎个区域，每 个区域取它的中心色作为代表，计算落入每个区域内像素的个数，就得到了颜色直 方图一一个盯维的特征空间。传统的r g b 颜色模型的可分辨色差是非线性的，且没有 直感，所以在计算颜色直方图前，往往将r g b 空间通过非线性变换形成其它更直观、 第二章c b v r 的系统结构及相关技术 更容易接受的颜色空间( 如h s v 空间) 。 纹理特征“2 “”“”1 纹理是与物体表面材质有关的图像特征，也是基于内容的检索系统中的一个主 要特征。纹理分析方法主要分为两类，即结构方法和统计方法。结构方法是假定纹理 模式由纹理基元按一定的规则排列组成，对纹理的分析就是要确定这些基元并定量分 析它们的空间排列。它采用句法分析方法，但只适用于规则的结构纹理分析：统计方 法是找出图像的数值特征，它又可进一步分为传统统计方法( 即基于模型的方法) 和基 于频谱分析的方法。通常对纹理特征的提取都采取将结构方法和统计方法相结合，以 取得较好的效果。 形状特征珏6 “2 4 “ 形状分析首先需要采用合适的图像分割算法把不同对象从图像中分割出来，再用 各种方法进行匹配测量。形状特征表示的一个重要准则是要求对位移、旋转、缩放的 不变性，通常形状的表示可以分为基于边界和基于区域两类。它们分别采用傅里叶描 述和矩不变量表述特征，另外新的研究方向有弹性变形模扳和边界方向直方图。 运动特征 运动特征是视频镜头