（计算机应用技术专业论文）基于计算智能的视频检索.pdf

摘要 近年来，随着计算机网络和多媒体技术的高速发展，i n t e m e t 上的信息种类和 数量与r 俱增。如何从这个海量的多媒体信息库中找到需要的多媒体信息已经成 为一个重要的课题。为此，就引发了视频处理的一个新领域：基于内容的视频检索。 本文围绕这一领域主要做了如下工作。 1 、关键帧提取。本文在分析现有关键帧提取算法的基础上提出了基于进化免 疫网络的关键帧提取方法。该方法将视频帧转化为多维空间中的一个点，并采用 进化免疫网络的聚类算法将内容相似的帧归为同一类，然后对每一类都选取出一 帧来作为此镜头的关键帧。仿真结果表明这种方法能较好的概括视频内容，事先 无需人为确定关键帧的数目，并且它可直接推广到对视频片断进行关键帧的提取 而无需对视频进行镜头分割。 2 、运动估计。在分析现有的运动估计块匹配搜索算法的基础上，本文将免疫 克隆选择机理引入到块匹配运动估计的搜索策略当中，提出了基于免疫克隆选择 的块匹配运动估计方法，仿真结果表明该方法可以在实现较为精确的块匹配的同 时保持较低的运算复杂度。 3 、视频分类。在综合颜色和运动特征的基础上，本文采取支撑矢量机对视频 进行分类，同时利用中心距离比值法进行支撑矢量的预选取，仿真实验结果表明 该算法能对视频进行较准确的分类，而且将中心距离比值法引入其中之后，在i ) i f 练速度上有了较大的提高。 关键词：基于内容的视频检索计算智能关键帧运动估计视频分类 a b s t r a ( j r r e c e n t l y , w i t ht h es h a r pd e v e l o p m e n t o fc o m p u t e rn e t w o r k sa n dm u l t i m e d i a t e c h n i q u e s ，t h ea m o u n ta n dt y p e so fi n f o r m a t i o no v e rt h ei n t e m e ta r eg r o w i n gd a yb y d a y h o w t og e tt h ed e s i r e di n f o r m a t i o nf r o mt h eh u g em u l t i m e d i a l i b r a r yi sb e c o m i n g a v e r yi m p o r t a n ts u b j e c t f o rt h i sp u r p o s e ，i te d u c e san e w f i e l da b o u tv i d e o p r o c e s s i n g ： c o n t e n t b a s e dv i d e or e t r i e v a l t h i sp a p e rh a sd 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 d t h i sf i e l d ： 1 、k e yf r a m ee x t r a c t i o n an e wk e yf r a m e e x t r a c t i o n a l g o r i t h m b a s e do n e v o l u t i o n a r ya r t i f i c i a li m m u n en e t w o r ki sp r o p o s e di nt h i sp a p e r i tt u m sv i d e of r a m e s i n t op o i n t si nm u l t i d i m e n s i o ns p a c e ，a n ds i m i l a rf r a m e sw i l lb ed e s i g n a t e dt ot h es a m e c l u s t e r b ye v o l u t i o n a r yi m m u n en e t w o r kc l u s t e r i n g t h e n t h ef r a m ec l o s e s tt ot h e c e n t r o i do ft h ec l u s t e ri se x t r a c t e da sak e y f r a m e e x p e r i m e n t a lr e s u l t sh a v es h o w n t h e r e l i a b l ep e r f o r m a n c eo ft h ep r o p o s e da l g o r i t h m i tc a ne x t r a c tk e yf r a m e sa u t o m a t i c a l l y a n dd o e s n tr e q u i r et h en u m b e ro fc l u s t e r st ob ek n o w nb e f o r e h a n d i na d d i t i o n ，i tc a n b ea p p l i e dt ov i d e o s e q u e n c ed i r e c t l ya n d d o e s n tr e q u i r s h o ts e g m e n t a t i o n 2 、m o t i o ne s t i m a t i o n b a s e do n s t u d y i n ge x i s t i n g b l o c km o t i o ne s t i m a t i o n a l g o r i t h m s ，w ea p p l yi m m u n e c l o n a ls e l e c t i o nt ot h es e a r c h i n g s t r a t e g yo f b l o c km o t i o n e s t i m a t i o na n dab l o c km o t i o ne s t i m a t i o nb a s e do ni m m u n ec l o n a ls e l e c t i o na l g o r i t h mi s p r o p o s e di nt h i sp a p e r s i m u l a t i o nr e s u l t sd e m o n s t r a t et h ea l g o r i t h ma c h i e v e sa c c u r a t e m a t c h i n g i nl o w c o m p u t a t i o n a lc o m p l e x i t y 3 、v i d e oc l a s s i f i c a t i o n b a s e do nt h ec o m b i n e df e a t u r e so fc o l o ra n dm o t i o n ，w e a p p l ys u p p o r t v e c t o rm a c h i n et ov i d e oc l a s s i f i c a t i o n a tt h es a m et i m e ，am e t h o dc a l l e d c e n t e rd i s t a n c er a t i oi su t i l i z e dt os e l e c ts u p p o r tv e c t o r sf r o mg i v e nt r a i n i n ge x a m p l e s ， w h i c hc a nr e d u c et h et r a i n i n gs a m p l e sa n ds p e e ds u p p o r tv e c t o rm a c h i n e i ti ss h o w n t 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 so fc o m p u t e rs i m u l a t i o n s k e y w o r d ：c o n t e n t - b a s e d v i d e or e t r i e v a l c o m p u t a t i o n a li n t e l l i g e n c e k e y f r a m em o t i o ne s t i m a t i o nv i d e oc l a s s i f i c a t i o n y 6 9 5 5 18 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：毖丝日期望堡墨：塑 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期问论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文( 保密的论文 在解密后遵守此规定) 。 本人签名： 导师签名： 日期丝篁：! ：垄 日期 第一章绪论 第一章绪论 目前数字视频技术已得到了广泛的应用，对于视频的管理、控制和检索目前 主要体现在以下方面：基于视频文件的插入、删除( 管理) ，对视频文件的播放、 快进快退( 控制) ，基于视频文件描述即文本信息的检索( 检索) 。所有这些都 不能从视频文件内部进行操作，无法基于视频的实际内容进行处理，而这往往又 是用户所关心的。因此就引发了视频处理的一个新领域：基于内容的视频分析， 可称之为“视频理解”。本章主要介绍基于内容的视频检索技术的发展和研究现 状以及本文的主要工作。 1 1 课题背景及研究意义 9 0 年代以来，多媒体技术发展突飞猛进，多媒体数据呈现出爆炸性的增长， 包括视频、音频、图像等的多媒体信息大量涌现。而在各种多媒体索材( 包括文 本、图形、图像、音频、视频和动画) 中，视频信息以其直观性、生动性和极大 的亲和力倍受人们的青睐。尤其是近年来，随着计算机技术、网络技术、通信技 术、信息编解码技术及大规模集成电路技术的飞速发展，数字视频的存储和传输 技术都取得了重大的进展，因而对这些海量的而且包含大量非结构化信息的数据 如何进行组织、表达、管理、查询和检索就成为迫切的需求。僵传统的数据库技 术中存在了一个难以解决的问题，也就是不同的人感觉到的视觉数据不同，如果 仅用关键词是不可能把人们描述数据的所有可能都包括的，因此基于内容的视频 信息检索技术1 “l ( 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 ) 始终是视频研究 领域中的一个热点问题，也成为未来信息高速公路，数字图书馆等项目中的关键 技术嘲。 1 。2 基于内容的视觉信息检索综述 1 2 1 基于内容的检索 基于内容的检索“1 ( c b r ，f l p c o n t e n t b a s e dr e t r i e v a l ) 是多媒体数据库信息 检索中的- - i 7 新兴的技术。它是指从多媒体数据中直接提取出对象的语义、特征 ( 如图像的颜色、纹理、形状，视频中的镜头、场景、镜头的运动，声音的音色、 基于计算智能的视频检索 音调、响度等) ，然后根据这些线索对大量存储在数据库中的媒体信息进行查找， 检索出具有相似特性的媒体数据来。c b r 能从大型分布式数据库中，以用户可以接 受的响应时间，查询到所要求的信息。 1 2 2 基于内容的检索在视频中的应用【7 - l o 】 人们总是希望可以直接检索到一段包含特定信息的视频片段，例如：足球比 赛中的射门镜头、含有日出景色的片段等。在传统的数据库系统中，信息的检索 一般以数值和字符型为主。视频数据库中集成了大量的非格式化信息，它们具有 数据量大、信息不定长、结构复杂等特点。这些媒体数据都有一些难以用字符和 数字符号描述的内容线索。如某帧图像中某一对象的形状、颜色和纹理，视频中 的运动等。当用户要利用这些线索对数据进行检索时，首先要将其人工转化为文 本或关键词形式。这些转换带有一定的主观性，且极其费时。因而仅仅基于关键 词的检索已不能满足用户的检索要求。数据库及其它信息系统不仅要能对图像、 视频等多媒体信息进行存储以及基于关键字的检索，而且要对多媒体数据内容进 行自动语义分析、表达和检索，基于内容的视频检索正是这样一种应运而生的检 索方法。 基于内容的视频检索提供了这样一种算法；在没有人工参与的情况下，自动 提取并描述视频的特征和内容。这是- - f l 交叉学科，以图像处理、模式识别、计 算机视觉、图像理解等领域的知识为基础，从认知科学、人工智能、数据库管理 系统及人机交互、信息检索等领域，引入新的媒体数据表示和数据模型，从而设 计出可靠、有效的检索算法、系统结构以及友好的人机界面。目前，基于内容的 视频检索研究，除了识别和描述图像的颜色、纹理、形状和空间关系外，主要的 研究集中在视频分割、特征提取和描述( 包括视觉特征、颜色、纹理和形状及运 动信息和对象信息等) 、关键帧提取和结构分析等方面。 基于内容的视频分析，就是要从所有的帧中提取主要内容，并从下至上地对 视频内容进行结构化描述。为了实现这个目标，我们须对视频进行如下处理：视 频分割、特征提取和视频内容的组织。 歪蛰岔皿- 运动信恳 舅澧点头j 蛰垂盆短4 差焦蛆提取，关键帧 l 翌叁塑塑量竖堕，对象信息i 用户浏b 燃构黼i ”“、查询 索引墼茧i 划 图l1 基于内容的视频处理主要过程 图1 1 描述了基于内容的视频处理的主要过程。视频首先被分割成各个镜头， 第一章绪论 3 并对每个镜头进行运动分析( 主要针对摄像机运动和物体运动) 。基于运动分析， 我们可以提取并跟踪镜头中的对象，同时选择或构造关键帧来描述视频内容。然 后，根据提取镜头、关键帧和对象的视觉特征，进行索引。通过视觉特征的相似 度计算，镜头被组织成场景。最终，用户可以通过一种简单的方法浏览和检索视 频。 1 2 3 基于内容检索的特点l l l l 1 ) 、以综合性学科为基础：基于内容检索属于多媒体的综合集成技术。它利 用图像处理、模式识别、计算机视觉、图像理解等学科中的一些方法作为基础技 术，从认知科学、用户模型、图像处理、模式识别、知识库系统、计算机图形学、 数据库管理系统以及信息检索等领域中获得启发，引入新的媒体数据表示和数据 模型，产生出有效、可靠的查询处理算法和可视化查询接口，以及与领域无关的 检索技术和系统结构。 2 ) 、客观性：从媒体内容中提取信息线索。基于内容的检索突破了传统的基 于表达式检索的局限，它直接对图像、视频、音频内容进行分析，抽取媒体语义 和视觉、听觉等特征，利用这些内容特征建立索引，并进行检索。由于突破了传 统的基于文字表达式的局限，避免了用字符标识图像的转化过程，从而大大提高 了检索过程的效率和适应性。 3 ) 、相似性比较：基于内容的检索是一种近似匹配。由于对内容的表达不是 一种精确描述，因此，c b r 采用相似性匹配的方法逐步求精，以获得查询结果，即 不断减小查询结果的范围，直到定位于要求的目标，这是一个迭代过程。这一点 与常规数据库检索中的精确匹配方法不同。 4 ) 、交互性查找：c b r 系统充分发挥人和计算机各自的长处，利用人对于物 体的内容特征比较敏感，而计算机善于从大量数据中标识对象和从事重复性的工 作，把交互操作引入到查询过程中。 5 ) 、直观的查询方式。 6 ) 、应用于大型数据库的快速检索。 1 2 4 基于内容的视觉信息检索的发展 1 9 9 2 年“基于内容的图像检索( c o n t e n t - b a s e di m a g er e t r i e v a l ) ”一词开 始在国际上使用“，国内也很早就开始了耜关研究“”。l o 多年来，这方面的研究 和应用得到了长足的进展“。有人指出，从视觉信息检索系统的演变来看，可分 为两代“。 第一代视觉信息检索系统 从历史上看，第一代视觉信息检索系统允许通过字符串属性访问图像和视频 4 基于计算智能的视频检索 “”。在第一代视觉信息检索系统中，用字符串表达与内容无关的元数据，使用如 相关模型、框架模型、面向目标的模型等表达方案。关键字比较适合于识n 认证 如图像或视频中的有意义实体( 如物、人) ，前后文相关的概念( 眼、鼻) ，或 场景表达( 如教室、j ) ( l 景) 等。 典型的第代视觉信息检索系统的工作框图如图1 2 所示。 圈1 2 第一代视觉信息检索系统的工作框图 在离线状态，注解员通过一定的方法( 多为手工方式) 对数据库内容进行注 解，提供出在线应用时所需的索引。而用户借助文字查询方法利用援索引擎进入 索引进行检索，返回的结果以可视化的手段显示给用户，用户借助相关反馈开始 新一轮查询。 新一代视觉信息检索系统 新一代视觉信息检索系统支持根据视觉内容的检索。对视觉信息的访问不仅 在概念层利用关键字进行，而且也在感知层利用对视觉内容的客观测量和合适的 相似模型进行，如图1 3 所示。 囝1 3 新一代视觉信息检索系统的工作框图 在离线状态，不仅注解员可通过一定的方法对数据库内容进行注释，而且系 统也( 自动地) 对数据库图像或视频进行分析，提取特征，从而提供出在线应用 时所需地( 多维) 索引。用户不仅可以借助文字查询方法，也可以借助视觉浏览 和( 视觉) 范例查询方法利用搜索引擎进入索引进行检索，返回的结果仍可以用 可视化的手段显示给用户，使用户能借助相关反馈开始新一轮查询。 第一章绪论 1 3 国内外研究现状 曰i j 国内外已经开发出多种视频数据检索系统，这些系统虽然大多没有成为 商用化系统但也反映了视频数据检索系统研究的主要成果。目前国内外丌发的 视频检索系统有“8 。2 “； i 、o b o e 系统 q b i c 系统是i b ma l m a d e n 研究中心研究开发的基于内容的检索系统，此系统提 供了对静止图像及视频信息基于内容的检索手段，是第一个功能齐全的视频数据 库系统，对视频数据库发展有较深远的影响。 在q b i c 系统中，静态图像经过对象识别模块以自动、半自动方式由场景中识 别出对象，场景与对象均送入特征提取部分，从中提取出相关特征( 如颜色、纹 理、形状、草图等) 与图像并送入数据库中；视频序列送入镜头提取模块，由 此模块把视频流分割为镜头，并从中提取出代表帧及运动对象，然后送入特征提 取部分，从视频镜头及对象中提取有关特征( 由代表帧中提取颜色、纹理、形状 等特征及从镜头中提取的有关对象运动特征) 送入数据库中。在进行查询时，用 户可以从查询接口输入以图形化或示例方式表示的查询对象特征，与数据库中存 储的对象的内容特征进行比较匹配，寻找出具有相似特，征的图像和视频。查询结 果是以相似性顺序排列的图像集合。 2 、j a c o b 系统 j a c o b 系统是基于内容的视频数据库查询系统，分为两个功能模块：第一个模 块用于视频数据库中的分段，第二个模块用于数据库查询。 视频序列通过镜头抽取模块划分为镜头，从每一个镜头中抽取一些代表帧( r 帧) ，并通过它们的颜色和纹理内容对镜头加以描述。从视频中抽取的镜头以及 从镜头中抽取的r 帧都存储在镜头d b 中。在进行视频查询时，当一个直接查询或示 例查询到达了查询接口，匹配引擎开始通过分析存储在特征d b 中的火速据来查找 最相似的r 帧，最终将根据用户选择的n 值显示出一个最接近的r 帧。 3 、v i s u a l s e e k 系统 美国哥伦比亚大学图像和高级电视实验室开发的。它实现了互联网上的“基 于内容”的图像视频检索系统，提供了套工具供人们在w e b j z 搜索和检索图像 和视频。 4 、c o r e 系统 新加坡国立大学开发的一个基于内容的检索机。其显著技术特色包括：多种 特征提取方法、多种基于内容检索方法、使用自组织神经网络对复杂特征度量、 建立基于内容索引的新方法以及对多媒体信息进行模糊检索的新技术。 6 基于计算智能的视频检索 另外还有许多类似的系统，例如加利福尼亚大学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 d i a 、哥伦比亚大学的v i d e o q 以及清华大学计 算机系结合8 6 3 高技术研究发展项目“w e b _ z 基于内容图像检索”的研究所建立的 i n t e r n e t 网上的图像检索系统等。 1 4 本文主要工作 1 4 1 课题内容 本文主要研究了基于计算智能的视频检索，在现有的研究基础上引入了智能 的信息处理方式，所做的工作主要包括以下几方面： l 、针对现有视频流的特点，对视频流进行结构化分析。包括三方面的内容； 镜头边界捡测技术、关键帧提取技术和场景重构，本文仅对关键帧提取技术进行 了研究。在分析已有关键帧提取技术的基础上并针对视频流的特点提出了基于进 化免疫网络的关键帧提取方法，并与现有的典型提取算法对提取结果进行了比较。 2 、对视频中存在的运动特征进行了分析，着重研究了运动矢量的计算方法。 将免疫克隆选择算法引入到运动矢量的搜索策略当中，提出了一种全新的块匹配 运动估计算法，并与典型的块匹配算法进行了比较。 3 、综合提取视频帧的颜色和运动特征，并引入支撑矢量机来对视频进行语义 上的分类，同时选用了中心距离比值法来对支撑矢量进行预选取。 1 4 2 论文组织 本文共分为七章，各章的内容和组织如下： 第一章绪论。介绍了本课题的发展以及国内外研究现状，给出了课题研究的 目的、意义以及本文的主要工作； 第= 章基于内容的视频检索技术概述。介绍了基于内容的视频检索技术的主 要框架以及其中的各项关键技术。 第三章相关理论基础介绍，分别介绍了人工免疫系统中的免疫克隆选择学说 和进化免疫网络学说以及统计学中的支撑矢量机。 第四章在视频结构分析的基础上，着重对关键帧提取技术提出了新的基于进 化免疫网络的关键帧提取算法。 第五章视频运动特征的提取。针对运动特征是视频所特有的，重点研究了运 动矢量的块匹配搜索算法，提出了一种全新的搜索策略； 第六章语义层次上的视频分类。综合视频的颜色和运动特征，利用支撑矢量 机来实现语义层次的视频自动分类； 第七章总结与展望。对全文的工作进行总结。并指出下一步的研究方向。 第二章c b v r 荚键技术 第二章c b v r 关键技术 2 1引言 7 视频数据是一个二维图像流序列，它是非结构化的。要对视频数据进行计算 机管理并实现基于内容的视频检索技术，首先要对这种非结构化的图像流进彳亍处 理，使之成为结构化的数据，这样才能提取出各种特征从而达到基于内容检索的 目的。基于内容视频检索的主要步骤和其他信息检索一样，也是信息处理和检索 两个步骤。 基于内容的视频处理包括视频结构的分析、视频数据的自动索引和视频聚类 三部分。视频结构的分析是指通过镜头边界的检测，把视频分割成基本的组成单 元镜头，它是实现基于内容检索的第一步，其核心技术就是镜头切变检测； 视频数据的自动索引主要包括关键帧的提取，并以关键帧来表示镜头的内容：视 频聚类就是根据这些特征研究镜头之间的关系，也就是如何把内容相似的镜头组 合起来，形成场景，并作为更高一级的语义特征引入到基于内容的视频检索中。 同时也使得视频数据库的管理更为结构化，提高检索效率。 视频数据处理的一般过程如图2 1 所示。 视额聚类 图2 1 视频数据的处理过程 一般来说，一段视频由一些描述独立故事单元的场景构成：一个场景由一些 语义相关的镜头组成；而每个镜头是由一些连续的帧构成，它可由一个或多个关 键帧来表示。 2 2 视频镜头边界检测 视频镜头( s h o t ) 是视频数据的基本单元。大部分视频是通过编辑由一个个镜 头连接而成的，所以基于内容检索的视频处理，要将视频自动地分割为镜头f 2 l 】， 基丁：计筇智能的视额检索 以作为基本的索引单元。这个过程就称为镜头边界检测，也叫场景切换检测( s c e n e c h a n g ed e t e c t i o n ) ，它是实现基于内容的视频检索的第一步。 镜头检测也可看作是一个分割问题视频时域分割f 2 2 】。考虑到视频大数据 量的特点，实际中分割主要采用基于边界的方法，即主要通过检测镜头间的分界 来确定镜头的转换位置【2 3 】。 镜头实际上是一段时阐的视频信号，在这段时问内，摄像机可以有各种运动 及变焦等操作，但没有摄像机信号的中断，因此，一个镜头内的图像内容不会有 大的变化。但当镜头切换时，视频数据将发生一系列的变化，表现在颜色差异突 然增大，对象形状的改变和运动的不连续性等方面，镜头边界检测的目的就是寻 找这些变化的规律。 镜头边界检测算法的研究是视频分析与检索中最活跃的研究领域之一。镜头 之间的转换方式主要有两大类：突变和渐变。其中渐变的方式类型很多，有些视 频编辑工具可提供1 0 0 多种不同的编辑手段，但实际中9 9 以上的镜头编辑方法 都可归属于3 类，即切变、叠化、淡入淡出【2 4 1 。 视频中镜头的分割还可借助音频来帮助进行i 强2 刚。对于一些特殊的视频节目， 由于其独特的结构特点，还可采用一些特殊方法。如新闻节目一般每个报道单元 以播音员帧开始，并常有字幕出现，这些都可以作为镜头切换的线索来使用1 2 9 1 。 2 3 视频镜头内容表示 个镜头是由多幅图像组成的一个二维图像序列。目前，镜头的表示方法主 要有两类：即关键帧表示法和基于图像拼接技术的背景、目标表示法两类。 2 3 。1 基于关键帧的表示法 关键帧是用于描述一个镜头的关键图像帧，它反映一个镜头的主要内容。关 键帧的选取一方面必须能够反映镜头中的主要时间，因而描述应尽可能地准确全 面；另一方面要便于管理，数据量应尽量地小，且计算不宜太复杂。 关键帧的选取方法很多，比较经典的有帧平均法和直方图平均法。帧平均法 是从镜头中取所有帧在某个位置上像素值的平均值，然后将镜头中该点位置的像 素值最接近平均值的帧作为关键帧。直方图平均法则是将镜头中所有帧的统计直 方图取平均，然后选择与该平均直方图最接近的帧作为关键帧。这些方法的优点 是计算比较简单，所选取的帧具有平均代表意义；缺点是从一个镜头中选取一个 关键帧，无法描述有多个物体运动的镜头。显然，关键帧的选取应与镜头内容的 变化有关，当一个镜头内部存在较大的运动时，用一个关键帧不能很好地代表该 镜头的内容，常需用几个关键帧来表示。 第二章c b v r 关键技术 9 2 3 2 基于图像拼接技术的背景表示法 关键帧是视频镜头的一种方便的表示，它可直接从原始视频数据中抽取出来， 但它不可避免地会出现数掘冗余，若选择不当，还有可能漏掉某些重要的内容。 而融合多幅图像的背景信息，通过图像拼接技术而生成的一幅全景图，则是一种 紧凑且完全的镜头背景内容表示方法。通过这种方法，结合运动目标提取技术， 每个镜头片段都可以用一幅全景图和一些重要的运动目标来共同表示。这种表示 方法具有数据量小、包含信息多的特点，具有较好的应用前景。此外，这种方法 同时还可以获得摄像机运动参数及目标运动轨迹等信息，这些都是理解视频内容 的重要线索。 2 4 镜头聚类和镜头集合描述 借助镜头分割可将视频节目分成一系列镜头，但以镜头为单元划分视频节目 所需面对的单元个数通常被认为过多。因为镜头分割常基于视频特征进行，这表 明镜头内容的语义信息尚未很好地利用。另一方面，镜头主要还是一个物理单元， 还不足以描述有语义意义的时问或活动或者说在镜头层次上，还没有将视频节 目的逻辑关系描述出来。 为此，需要对视频进行更高层的抽象，将内容上有关系的镜头结合起来，以 描述视频节目中有语义意义的事件或活动。这个工作常称为镜头聚类，也有人称 为场景构造、情节分割、镜头聚集等。这样得到的镜头集台体也常用不同的词来 代表，如场景( s c e n e ) 、片断( d i 口) 、情节( e p i s o d e ) 、故事单元( s t o r y u n i t ) 等。 类似于用关键帧代表镜头，也可以使用有代表性的帧来代表镜头聚集体，以 简洁地表达具有语义层次的镜头聚集体。 2 5 视频数据组织和索弓 在镜头检测和镜头聚类的基础上，可以对视频进行进一步的组织，使之便于 搜索，易于交互。在组织基础上可以建立索引，提供查询的可能并帮助进行基于 内容的检索 3 0 3 1 】。 对视频数据来说，可以建立两种索引，一种是基于视觉单元所携带含义的索 引，另一种是基于目标或运动这样一些语义单元的索引。前者可以从关键帧中提 取，而后者一般比较复杂，提取之后需要进一步注释p 2 。3 3 1 。 基丁计算智能的视频检索 2 6 视频运动特征提取 将视频序列分割成各个不同的镜头，对每个镜头提取一组关键帧作为代表， 就可以用图像检索的方法对关键帧进行处理来实现视频内容检索。但事实上，视 频中除了包括从每幅图像中可得到的视觉特征，如颜色、纹理、形状和空间关系 等，还有运动的信息。运动是对序列图像进行分析的一种基本元素，它直接与空 间实体的相对位置变化或摄像机的运动相联系。运动信息是视频数据所独有的， 可用一组参数值或表示空间关系如何随时间变化的符号串来表示。运动信息表示 了视频图像内容在时间轴上的发展变化。它对于描述理解视频内容具有相当重要 的作用。基于运动信息可对视频内容进行分类，也可用于视频内容的检索。 基于运动信息的视频检索也得到了广泛的关注，这里首先要对视频进行分析， 通过提取运动特征构建运动描述符来描述视频内容，从而进一步匹配检索。 不管是基于运动信息的视频分类还是视频内容的检索，很重要的一点就是得 到视频的运动向量，然后根据不同的应用，再对运动向量进行分析，得到适合不 同问题的表示形式。 2 7 基于语义的视频信息检索 现有的视频检索系统在对视频内容描述时大多直接采用了传统的低级视频特 征，如颜色、纹理、形状等。在这样的系统中，对视频的描述一般以统计数据的 形式出现，但事实上，这些统计数据与人对视频的内容理解存在很大的差异。首 先，人对视频内容的理解并不是仅靠统计进行的，人还有学习的能力；其次，视 频内容具有“模糊”的特性，无法用简单的特征向量来描述；最后，人对视频内 容的理解是建立在人类已有知识的基础之上的，丽这些低级特征无法反映这些经 验知识。由于上述原因，很多情况下仅以视频低级特征为检索依据得到的检索结 果不尽人意。 从人的认知角度看，人对视频的描述和理解主要是在语义层次进行的，如何 将视频语义特征结合到检索中是提高检索系统性能的关键所在，已得到了越来越 多的关注。这里的一个关键就是如何获得视频的语义，尽管人们已经提出了一些 方案，如通过在不同层次上对视频内容进行分析和提取p 4 。引，通过将低层特征在 时空中组合起来构成语义单元【3 6 】等等。然而，目前还没有一种完整的基于语义的 视频内容描述方案来支持实际的检索过程。 本文在语义层次的检索方面做了一些尝试工作。 第三章相关理论基础 第三章相关理论基础 3 1 人工免疫系统 人工免疫系统( 灿s ，a r t i f i c i a li m m u n es y s t e m ) 是模仿自然免疫系统功能的一种 智能方法，它实现一种受生物免疫系统启发，通过学习外界物质的自然防御机理 的学习技术，提供噪声忍耐、无教师学习、自组织、记忆等进化学习机理，结合 了分类器、神经网络和机器推理等系统的一些优点因此具有提供新颖的解决问 题方法的潜力1 。其研究成果涉及到控制、数据处理、优化学习和故障诊断等许 多领域，已经成为继神经网络、模糊逻辑和进化计算后人工智能的又一研究热点 f 弛8 】 0 在生物学领域中，免疫学是- - f 3 相对年轻的学科，然而，人类对自然免疫的 认识可以追述到3 0 0 年以前。早在1 7 世纪，我国医学家就创造性地发明了人痘以 预防天花。1 7 9 6 年英国医生e d w a r dj e n n e r “牛痘”的发明，取代了人痘苗，是 公认的现代免疫学开端。法国免疫学家p a s t e u r 发明了减毒细茵疫苗，奠定了经 典免疫疫苗的基础。经过3 0 0 多年的发展，免疫学已经从微生物学的一章发展成 一门独立的学科，并派生出若干分支，例如，细胞免疫学、分子免疫学、神经与 内分泌免疫学、生殖免疫学和行为免疫学等。 事实上，人们对自然免疫系统的认识还不是十分充分，只是在免疫系统理论 上“建立一个合作系统的综合性理论的基础和需要都已很明显”。就现有的免疫系 统理论而言，为学术界所接受，并为工程应用尤其是人工智能领域所借鉴的主要 是b u r n e t 的克隆选择学说和j e r n e 的免疫网络学说。 3 1 2 免疫克隆选择学说 克隆选择是生物免疫系统理论的重要学说。克隆是英文c l o n e 一词的单译，意 为无性繁殖系，即通过无性繁殖( 如细胞丝分裂) 可连续传代并形成群体，常用于 细胞水平的描述。这一概念已经被广泛用于计算机编程【4 9 5 0 1 、系统控制【5 1 】、交互 式并行仿真【5 2 】等领域。克隆选择学说所描述的记忆、学习和进化等特性同样也引 起了人工免疫系统研究者的兴趣，与进化算法相比，相应的成果还不多，c a s t r o 5 ”、 k i m “j 、d u 5 s 等等相继提出了克隆选择算法。但是，相关研究还处在初始阶段，相 关算子还很少。文献【5 6 l 对克隆策略进行更深入的研究，与其他优化算法进行了比 基于计算智能的视频检索 较，并且给出了收敛性证明。根据文献【5 6 j 可知，克隆算法不但能在一定程度上克 服早熟，避免算法陷入局部极小值，而且可以提高算法的收敛速度。 1 _ 克隆选择 1 9 5 8 年b u r n e t 等提出了著名的克隆选择学说，其中心思想为，抗体是天然产 物，以受体的形式存在于细胞表面，抗原可与之选择性地反应。抗原与相应抗体 受体的反应可导致细胞克隆性增殖，该群体具有相同的抗体特异性，其中某些细 胞克隆分化为抗体生成细胞，另一些形成免疫记忆细胞以参加之后的二次免疫反 应。克隆选择是生物体免疫系统自适应抗原刺激的动态过程，如图3 1 所示。 o 记忆细胞 扫参一心 参曲分 血浆细胞 ( 产生大量抗体) 毋心一 心目 图3 1b u r n t 克隆选择学说模式幽 在这一过程中，多克隆是免疫应答特异性的基础。与单克隆只持续表达抗体 一种或少数几种抗原决定簇和表位不同，多克隆性在细胞水平上表现出t c r 和 b c r ( t a n dbc e l la n t i g e nr e c e p t o r ) 结构的极端多样性，因此，直接导致了抗体网络 的多样性、记忆性和特异性。生物学抗体克隆选择过程所体现出的学习、记忆、 抗体多样性等生物特性，正是人工免疫系统所借鉴的。 2 克隆算子 与进化算法一样，人工免疫系统算法同样是依靠编码来实现与问题本身无关 的搜索。不失一般性，这里主要考虑函数的最大化问题。为了解决函数优化问题： m 妒：丌阮，蚝】一月“。一( 蛳) ，m 是优化变量的数目，即x 一扛。，算：x m 。记抗原 f 妒：r “一r 为被优化的目标函数；对于二进制编码，抗体a e s ，s 一 0 , 1 t 代表 所有长度为z 的二进制串组成的集合，抗体群j 一卅。，a ：a 为抗体a 的挥元组， m 是抗体种群空间s 4 的一个点。一般将抗体位串分为m 段，每段长为l i ，b l i ， 留 每段分别表示变贯阮，u i 】f 一1 , 2 ，r a 的二进制代码，采用如下译码方式： 第三章相关理论基础 1 3 驴”等协z h ) 阳， 其中a i l 盯a “为抗体a 的第i 段。 抗体- 抗原亲合力函数，般是目标函数妒的函数，抗体抗体亲合力定义为： d u 一忪一a j i i f ，= 1 , 2 ，h ( 3 2 ) 其中j | 为任意范数，对二进制编玛一般取海明距离，而十进制编码多取为欧 氏距离。记d 一【d 口l 。 f ，- 1 ，2 ，n 为抗体一抗体亲合力矩阵。d 是对称矩阵， 反应了种群的多样性。 在人工免疫系统中，基于上述生物学抗体克隆选择过程，杜海峰等【5 6 1 人给出 基本操作如图3 2 所示的克隆算子( c l o n a lo p e r a t o r ) 。 克隆操作 免疫基因操作 克隧避择操作 竞隆死亡操作 a l ( 七) a 2 ( k ) i 4 0 ) l 以耻) 抗 。形彳n a l i a ： a 244 4 同闩厂同 一ij ”川44 kk t t tt a 1 耻4 - 1 )以( 七十1 )4 ，( 七+ 1 )4 ( 七+ 1 ) ljj l l ( 七+ 1 )a 2 ( 七4 - 1 ) ( 七+ 1 ) ( 七+ 1 ) i ! i3 2 克隆算予的操作过程 克隆操作r ：定义 r 臼 ) ) 叫誓似， ) ) 球即：( t ) ) 砰a 。 ) ) 】7 ( 3 - 3 ) 其中：誓。 ) ) - ，；x a ；( 七)i - 1 ，2 t l ，, - 为吼维行向量，称抗体月，的仉 克隆。 q ；- g ( 。，f ( a 。( t ) ) )( 3 - 4 ) 一般取： q ，一mn 。掣 善，_ ，( 七) ) ( 3 5 ) c m 是与克隆规模有关的设定值；肋( ) 为上取整函数，如表示大于茗的最 小整数。由此可见，对单一抗体而言，其克隆规模是依据抗体抗原亲合度自适应 1 4 基丁计算智能的视频检索 调整的。克隆过后，种群变为： a 7 ( ) 一” ) ，爿： ) ，爿； ) ，爿： ) )( 3 6 ) 其中： 爿让) ； 4 ， ) ，4 2 ) ，4 。j - 1 ) a 口( k ) ；a ( 女)j = 1 , 2 ，q ；- 1 ( 3 - 7 ) 免疫基因操作砰：免疫基因操作主要包括交叉和变异。参考生物学单、多克 隆抗体对信息交换多样性特点的描述，在文献 5 6 1 r 扣定义仅采用变异的克隆算子为 单克隆算子( m o n o e l o n a lo p e r a t o r ) ；交叉和变异都采用的为多克隆算子( p o l y c t o n a l o p e r a t o r ) 。需要说明的是，这里的定义没有完全遵循其免疫学上的意义；因为。即 使对于单克隆算子产生的抗体也不是单一一种抗体，只不过与多克隆算子相比， 其更多地保留了父代的特征。不失一般性，本文主要叙述单克隆算子及其性能分 析，丽多克隆算子的分析只需要考虑交叉操作的作用，对分析结果不会产生本质 的影响【5 1 1 。而且本文所提出的算法只应用了单克隆算子。 依据概率p ：对克隆后的群体进行变异操作，j 谁) - 誓口，( 七) ) ，为了保留抗 体原始种群的信息，变异筹子并不作用到j ( 七) j ) ，即： p 。c 仕，一一；让的- 。州州w 忙”譬p 。州制“耻”2 篓；茎2 - t 篓；( 3 - 8 ， 克隆选择操作r ：v f 。l 2 ，n ，存在变异后抗体， b 一似；( 七) i m a x ，0 ；) ，- 1 ，2 ，吼一1 则b 取代4 ( 七) j ( 七) 的概率为： f 1 ，( 七) ) t ，) p ：_ 脚j 。x “塑堕二旦) f ( a ；佧) ) ：，) 且 ( 七) 不是目前种群的最优抗体 1 0 f ( a 。让) ) ，( 曰) 且4 ( 七) 是目前种群的晟优抗体 ( 3 9 ) a 0 是一个与抗体种群多样性有关的值，一般地多样性越好，a 取值越大，反 之越小。 克隆死亡操作砰：克隆选择后获得相应的新抗体群为： a ( k + 1 ) 一似1 ( 七+ 1 ) ，a 2 ( 七+ 1 ) ，一j 体+ 1 ) ，a 。( 七+ 1 ) 0 - l o ) 兵中4 + 1 ) t 一，( k + 1 ) 一他+ 1 )i - ，且，o 船+ 1 ) ) - i ( a ， + 1 ) ) - m a x f 叫( 七+ 1 ) ) 那么，以概率肌任意死亡卅 + 1 ) 与4 + 1 ) 中的一个。死亡策略既可以是随 机产生一个新抗体代替一触+ 1 ) 或一肚+ 1 ) ，也可以是采用变异或交叉策略重新生 成新抗体代替爿船+ 1 ) 或a i ( k + 1 ) 。 克隆算子作用后获得相应的新抗体群为： a 忙+ 1 ) 一“ + 1 ) 4 仲+ 1 ) 4 ( 七+ 1 ) 等价于生物克隆选择后的记忆细胞和血浆细胞，算子中没有做特别区分。 第三章相芙理论基础 山此可见，克隆的实质是一代进化中，在候选解的附近，根据亲合度的大小， 产生一个变异解的群体。 在进化计算中，对于变异算子有： p 仁- - b = p ，”( 1 一p ，) 。“础 ( 3 1 1 ) 由于肌一般较小，海明距离d ( a ，6 ) 越小，p 口一6 越大，从而变异使得抗体在 其领域内变化，扩大了搜索范围。而在克隆选择算子中，对于抗体a ，的盯克隆个 体都为b 的概率为： 鼻和似，) 一6 ) f 尸“6 c p ： 一，( 1 - p m