（计算机软件与理论专业论文）基于人工文本视频帧聚类算法研究.pdf

哈尔滨工程大学硕士学位论文 摘要 随着多媒体技术、计算机通信技术以及互联网的迅速发展，视频的存储 和传输变得简单，并得到了广泛的应用。视频的分析和管理问题越来越重要。 如何提高视频聚类的聚类质量与聚类稳定性成为视频分析和管理的研究热 点。 本文首先给出一种基于人工文本与视觉特征的多模态信息视频帧分割 算法。在视频序列中，提取包含人工文本的视频帧，利用文本特征进行视频 帧的分割，并利用视觉特征对相邻的包含人工文本的视频帧之间的非文本帧 进行视频帧的分割，以精确定位视频帧的分割点。其次针对传统k - m e a n s 算 法中依赖初始值k 的缺点，给出一种改进的k - m e a n s 算法。该改进算法采用 最小最大距离方法自动生成初始聚类中心点和聚类数，有效地解决了传统算 法对初始值k 的依赖。同时，改进的k - m e a n s 算法对初始聚类中心点选取比 较严格，各中心点的距离较远，这样避免了初始聚类中心选自同一个聚类， 一定程度上克服了k - m e a n s 算法限入局部最优状态。 仿真实验表明，基于人工文本与视觉特征的多模态信息视频帧分割算法 提高了视频帧分割点的精确度，对分割出的视频段用改进的k - m e a n s 算法进 行聚类，也提高了聚类的精确度。 关键词：视频聚类；分割；多模态信息；人工文本；视觉特征 哈尔滨工程大学硕十学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fm u l t i m e d i a , c o m p u t e rc o m m u n i c a t i o na n d i n t e r n e t ，i ti ss i m p l et os t o r ea n dt r a n s p o r tv i d e o v i d e oi sw i d e l ya p p l i e d i ti s m o r ea n dm o r ei m p o r t a n tf o rt h ea n a l y s i sa n dm a n a g e m e n to fv i d e o h o wt o i m p r o v et h ec l u s t e rq u a l i t ya n dc l u s t e rs t a b i l i t yo ft h ev i d e oc l u s t e ri sah o tp o i n t i na n a l y s i sa n dm a n a g e m e n to fv i d e o i nt h i st h e s i s ，f i r s t l y , v i d e of r a m es e g m e n t a t i o na l g o r i t h mo fm u l t i m o d a l i n f o r m a t i o nb a s e do na r t i f i c i a lt e x ta n dv i s u a l c h a r a c t e r i s t i c si sp r o p o s e d i nt h e v i d e os e q u e n c e ，t h ev i d e of l a m e sc o n t a i n i n ga r t i f i c i a lt e x ta x ee x t r a c t e d t h e v i d e of r a m e sa r es e g m e n t e dt om a k eu s eo ft h et e x tc h a r a c t e r i s t i c s n ea d j a c e n t n o n - t e x tf r a m e sc o n t a i n i n ga r t i f i c i a lt e x ta x es e g m e n t e dt om a k eu s eo fv i s u a l c h a r a c t e r i s t i c s b yt h ew a y , t h es e g m e n t a t i o np o i n t so f v i d e of r a m e sa r ep r e c i s e l y l o c a t e d s e c o n d l y , a ni m p r o v e d k m e a n s a l g o r i t h m i s p r o p o s e da g a i n s t d e p e n d e n c eo nt h ei n i t i a lv a l u eo fk i nt h et r a d i t i o n a lk - m e a n sa l g o r i t h m i nt h e i m p r o v e da l g o r i t h m ，t h em e t h o do fm i n i m u ma n dm a x i m u m d i s t a n c e si su s e dt o a u t o m a t i c a l l yg e n e r a t et h ei n i t i a ln u m b e ro fc l u s t e rc e n t e r sa n dt h ei n i t i a ln u m b e r o fc l u s t e r s t h ed e p e n d e n c eo nt h ei n i t i a lv a l u eo fki nt r a d i t i o n a la l g o r i t h mi s e f f e c t i v e l yr e s o l v e d m e a n w h i l e ，i nt h ei m p r o v e dk - m e a n sa l g o r i t h m ，i ti ss t r i c tt o s e l e c tt h ei n i t i a lc l u s t e rc e n t e r s t h ed i s t a n c eo ft h ec e n t e r si sf a r s ot h es i t u a t i o n o ft h ei n i t i a lc l u s t e rc e n t e r sf r o mt h es a m ec l u s t e rc a l lb ea v o i d e d t os o m ee x t e n t ， t h el o c a lo p t i m a ls t a t ei nk - m e a n sc a nb ea v o i d e d r e s u l t so fe x p e r i m e n t ss h o wt h a tt h ea c c u r a c yo fs e g m e n t a t i o np o i n t so f v i d e of l a m e si si m p r o v e di nv i d e of r a m es e g m e n t a t i o na l g o r i t h mo fm u l t i m o d a l i n f o r m a t i o nb a s e d0 1 1a r t i f i c i a lt e x ta n dv i s u a lc h a r a c t e r i s t i c s u s ei m p r o v e d k - m e a n sa l g o r i t h mt oc l u s t e rt h ev i d e of r a m ed i v i d e d ，a l s oi m p r o v e dt h ea c c u r a c y o fc l u s t e r i n g k e y w o r d s ：v i d e of r a m ec l u s t e r i n g ；s e g e m e n t a t i o n ；m u l t i m o d a li n f o r m a t i o n ； a r t i f i c i a lt e x t ；v i s u a lc h a r a c t e r i s t i c s 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用己在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：黎浓面 日期：2 卵年乏月工d 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后口解 密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：界旅丽导师( 签字) ：王垫 日期：2 叼年2 月2 d 日) 剜1 年2 月习日 | 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 课题研究的目的和意义 随着多媒体技术、计算机通信技术以及互联网的迅速发展，使得视频的 存储和传输变得简单，广泛应用在人们日常生活当中。比如应用在视频点播、 视频会议、医疗和监视系统中。如何进行视频的分析和管理，从而在海量的 视频数据中查找用户感兴趣的内容显得越来越重要。传统的视频检索只能通 过快进和快退等顺序的方法进行人工查找，无法满足多媒体数据库的需要。 用户往往希望的是：系统根据一些特征描述就能快速自动的查找到对应的视 频片段，即实现基于内容的视频检索。 视频图像中所含的文本信息在一定程度上反映了该图像的部分重要内 容，通常形成对图像内容的简练描述或说明。例如，商业广告中的文本能够 提供诸如产品名称、公司名称等重要信息：在体育比赛的画面中，可以通过 抽取运动员的号码、姓名和球队名称对比赛画面进行注释和索引；新闻图片 中的文本能够说明发生的事件、时间、地点等；在复杂文档的自动处理中， 如股票证书的自动登记处理，可以通过提取文档中特定的文本信息进行股票 登记；医学图像中标注的病情、日期、病人姓名、病例号可以方便医学图像 快速查阅；视频字幕中的人物对话能提供重要的主题信息；景物中的街道路 牌、商店的名称能提供位置信息：在基于对象的图像或视频压缩中，从图像 中提取出文本区域单独进行编码，既可提供更高的压缩率，又可得到更好的 图像质量；在生产自动化中，可以使用零件或产品上的文字来识别零件，如 啤酒瓶上的专有字符“b ，可以判断瓶子是否为用于盛装啤酒的专用瓶；在 集装箱码头，自动提取并识别集装箱的号码，可以判断它是否与报关的号码 相同；身份证字符的自动识别可用于安全管理；支票中的账号、日期、金额 等字符，可用于支票合法性验证及支票图像存档检索等方面；机票字符的自 动识别可用于机场的安全检测；对车辆牌照的提取、识别，其结果可广泛应 哈尔滨工程大学硕士学位论文 用于智能交通领域，包括交通流量检测、交通控制与诱导、机场或港口等出 入口车辆的管理、道口检查站车辆监控、违章车辆管理等等：这些对于帮助 人们理解图像的内容、检索相关图像都有着重要的作用。因此，视频帧中的 人工文本更好地、更可靠地反映了视频帧所包含的语义信息，所以利用视频 帧人工文本特征进行视频帧聚类仍是视频检索的重要研究内容之一。视频帧 聚类能够处理大量的视频，可以较大程度解决视频信息紊乱的现状，方便用 户准确地定位所需要的视频信息。 1 2 国内外研究现状 1 2 1 文档聚类 目前从国内外发展来看，自动文本分类已取得了显著的成效。尤其是美 国、德国及英国等国家对此领域的探讨使文本自动分类在理论和实践上都有 了很大的迸步。相对来说，自动文本聚类刚刚处于起步和发展阶段，文献 1 1 采用层次聚类和平面聚类相结合的技术，力图避免层次聚类较大的计算量和 平面聚类由于初始类中心的随机选取导致的聚类结果的不确定性。基本思想 是随机选取d 篇文档，d 的取值为s g r t ( k n ) ，其中k 为聚类的数目，n 为文档 库中文档的数量；采用层次聚类法对d 篇文档进行聚类，得到( k n ) 个聚类； 将剩余文档分配到距离最近的聚类中。 g s a l t o n 等曾对自动聚类进行了比较深入的研究l z j 。自动聚类研究中最 重要的概念是文本间的距离( 相似性) ，一般可采用欧氏距离法、数量积法、 相关系数法、指数相似系数法、夹角余弦法、最大最小法等对其定义，在此 基础上自动聚类的主要算法主要有：数值矢量法，图分类和逐步聚类法。数 值矢量法包括单遍聚类法，小中取大距离分类法，自上而下的类别精化法和 密度测试法；图分类包括完全子图分类法和单链法；逐步聚类法包括系统聚 类法，i s o d a t a 模糊聚类法和利用最大树作模糊聚类等。 文档聚类也是文本挖掘中一个非常重要的问题，它是将一堆文档中语义 相近的文档聚在一起。文档聚类己经被广泛地应用在很多地方，比如将其应 用在信息检索系统中用以提高信息检索的效率【3 】、用文档聚类来组织搜索引 2 哈尔滨工程大学硕士学位论文 擎返回的结果【4 】、用文档聚类来帮助用户浏览超大规模的文本数据【5 1 、通过 文档聚类来生成w e b 文本的分类层次树 6 1 、还有用文本聚类来帮助用户管理 和组织个人e m a i l 、电子文档等。 文档聚类又是一个非常难的问题，因为一方面聚类本身很困难，没有任 何预知信息，它对所要划分的类是未知的。另一方面，文档数据本身的特点 又让文档聚类难上加难，因为单词之间复杂的语义联系和过高的维度都会导 致聚类性能的急剧下降。 1 2 2 视频检索 基于内容的视频检索是视频数据库系统的一个重要的组成部分。从研究 内容上看，基于内容的视频检索技术研究主要可分为对视频的结构分析和对 视频的语义分析两大类。结构分析又可以细分为镜头和场景层次，而语义分 析也包括颜色、纹理、轮廓等低级语义特征和文字、人脸等高级语义特征等 等。 下面介绍几个比较具有代表性的研究组和他们的研究成果： 胡晓峰教授和李国辉教授所在的研究组【7 1 1 】的研究工作主要集中在视频 的结构分析方面，他们对镜头分割、关键帧提取和镜头聚类等问题进行了研 究和探讨，目前，己经建立了一个视频结构化浏览和查询原型系 统：v d e o w s e r o 。最近，该研究组开始了对音频特征提取和检索方面的研究。 潘云鹤院士和庄越挺教授所在的研究组【1 2 d 6 】主要针对视频检索和视频相 似度衡量等问题进行了研究，提出了一种基于镜头质心特征向量的视频相似 度衡量方法，从而提供了一种从图像序列特征方面来进行视频检索的方法。 另外，该研究组还试图从视频流中的闭路字幕( c l o s e d c a p t i o n ) 中来提取信 息来进行视频检索，比如，他们已建立了一个名为w e b m a r s 的视频信息检索 系统，该系统利用s u n b e l t 公司的字幕捕捉卡t e x t g - r a b b e r 来获取n t s c 制式 模拟视频流中的闭路字幕，然后用普林斯顿大学开发的电子词典系统 w o r d n e t 来进行基于关键词的匹配和检索。 钟玉琢教授所在的研究组【1 7 - 1 9 】主要基于m p e g 压缩视频标准进行了一 系列的研究工作。如研究了对于m p e g 压缩视频流的镜头变换问题，提出一 种基于m p e g 标准的压缩视频流的镜头自动切分算法，该方法通过利用 3 哈尔滨工程大学硕士学位论文 m p e g 数据流中己有的信息，如离散余弦变换( p c t ) 系数和运动向量，只 进行最小程度的解码，来检侧镜头间的边界，从而实现镜头切分。针对实际 视频流中镜头切换方式的复杂性，他们提出了三个不同的算法分别处理不同 情况，并将这三个算法以树形分类器的方式组织在一起。另外，该研究组还 研究了关键帧提取问题，提出了一种从m p e g 压缩视频流中提取关键帧的方 法，该方法利用m p e g 压缩视频流中相邻帧的宏块互异数目来反映帧间的变 化情况，并以此作为提取关键帧的依据。 高文教授所在的研究组【2 0 2 2 】主要进行了复杂背景下的人脸检测与跟踪 系统方面的研究，他们设计并实现了一种基于特征子脸( e i g e n s u b f a c e ) 的 人脸检测与跟踪系统，它首先利用模板匹配的方法进行粗检测( 用一种基于 灰度分布的人脸模板) ，并在此基础上收集有效的反例样本集( 非人脸样本集 ) 来提高识别的精度。目前，该研究组正在进行综合音频特征和图像序列特 征的唇读( l i p - r e a d i n g s p e e c h r e a d i n g ) 研究。 1 3 论文的研究内容及组织 1 3 1论文的研究内容 由于视频帧中人工文本作为本文的视频帧聚类算法依据的特征之一，因 而如何选取视频帧的特征以及如何根据提取的特征进行聚类是本文研究的主 要目标。围绕这一目标，本文对以下几个方面的内容进行了详细的研究。 1 视频特征的选择 本文把人工文本和视频帧中的其他特征结合，即本文的视频特征综合了 人工文本和其他视频特征的多模态方法。 2 聚类算法 本文在对聚类的各种经典算法进行详细分析研究基础之上，对经典 k - m e a n s 聚类算法进行改进。改进算法采用最小最大距离方法自动生成初始 聚类中心点和聚类数。 3 视频聚类 本文分别利用基于视觉特征的视频帧分割算法和基于人工文本、视觉特 4 哈尔滨工程大学硕士学位论文 征多模态方法的视频帧分割算法对视频帧进行分割，并依据人工文本特征利 用改进的k m e a n s 算法对视频段进行聚类。 1 3 2 论文的组织结构 第1 章介绍了课题研究的意义及其涉及的领域。对现有的成果进行分析 和介绍，最后给出了课题研究的主要内容。 第2 章介绍了本课题的相关知识与理论。 第3 章论述和分析了聚类关键技术。 第4 章给出一种综合文本、视觉特征多模态信息的视频帧镜头的分割方 法和k m e a n 聚类的一种改进算法。 第5 章进行仿真实验并对实验结果进行分析。 5 哈尔滨工程大学硕士学位论文 2 1文本聚类 第2 章相关知识及理论 2 1 1文本聚类的任务 文本聚类是完全根据文本内容的自身的特性来组织文本集合，通过特定 的处理和相应的算法将整个集合聚成若干个类，并使得属于同一类的文本尽 量相似( 即内容相关) ，属于不同类的文本差别明显( 即内容无关) 。由于事先 没有关于这些文本信息的分类知识或可以使用的分类表，因此，文本的聚类 处理是一种无监督的学习( u n s u p e r v i s e dl e a r n i n g ) ，其特点可概括为“先有 文本后有类。 文本聚类研究所依据的思想和方法起源于数值分类学的“聚类分析 ( c l s u t e r i n ga n a l y s i s ) 。早期的文本聚类分析主要依靠专业知识和经验，局限 在定性的范围内。后来随着学科的发展与信息量的激增，分类越来越细，需 要分类的文本对象也越来越多，这时仅仅依靠文本的一些特性进行定性划分 也变得越来越困难。于是，作为数值分类学的主要分支，聚类分析技术就被 引入到文本聚类领域。 设s - d l ，d 2 ，d n ) 代表一个文本集，研代表s 的一个子集，则文本聚 类的任务就是将s 分割为k 个子集，并且满足： 七 ii s = u ( 2 1 ) 尚 这个条件很容易满足，但是仅仅这个条件是不够的，因为文本聚类更重 要的是使类内的文本在语义上尽可能相似，而与其他类中的文本尽可能“相 隔 较远或者不同。 6 哈尔滨工程大学硕十学位论文 2 1 2 文本聚类的过程 不同于文本分类，文本聚类没有训练数据，所以没有训练步骤。文本聚 类的过程相对简单，如图2 1 所示，它首先对原始的文本数据进行预处理， 进而表示成文本特征向量，然后采用聚类算法进行聚类，最终得到多个文本 类。 广 厂 广 厂 i 文本数据卜_ 叫文本预处理卜_ 一生成文本特征向量卜一 聚类 图2 1 文本聚类的过程 1 。文本预处理 由于文本数据不同于数据库中的结构化数据，必须把文本表示成为计算 机能够处理的、可体现文本本质特征的形式。文本的内容是人类所使用的自 然语言，计算机并不具有人类的特有智能，因此很难处理其语义。由于文本 信息源的这些特殊性，所以需要对文本进行预处理，抽取代表其特征的元数 据，这些特征可以用结构化的形式保存，作为文本的中间表示形式。空间向 量模型( v e c t o rs p a c em o d e l ，v s m ) 2 3 1 是近年来应用最多且效果较好的方法 之一。 2 生成文本特征向量 当选择表示文本的特征后，就可以依据一定的原则将文本数据表示为特 征空间内的特征向量；同时根据文本数据的特点一高维、稀疏，还要进行相应 的特征选择和抽取【2 4 1 ，这样不但可以降低特征向量的维数，使聚类算法的计 算复杂度大大降低，而且可以去除由于同义词及多义词所产生的噪声和歧义， 进而大幅度提高文本聚类系统的性能。 3 文本聚类算法 当生成文本的特征向量后，文本数据就表示成为便于计算机处理的结构 化形式，即可应用所选择的聚类算法对文本进行聚类处理，生成相应的聚类 结果。 哈尔滨工程大学硕十学位论文 2 2 镜头聚类 2 2 1 镜头聚类模型 镜头记录着一个连续行为的一组视频帧，由于镜头内场景的内容没有较 大的变化，因此镜头表示时空连续行为，单个镜头内的视频图像一般具有相 似的视觉属性 2 5 , 2 6 1 。基于镜头的模型如图2 2 所示，整个视频序列可以分解 为多个镜头的组合。由于镜头内各帧之间的内容具有相似性，因此可以用关 键帧表示镜头的内容，关键帧指镜头中有代表性的一帧或者几帧图像。具有 相似视觉属性的相邻镜头构成场景，在基于镜头表示模型中，关键帧、镜头、 场景构成了视频序列的概括。场景切换检测常用视频图的亮度直方图或颜色 直方图，通过相邻镜头之间亮度直方图或颜色直方图的比率是否超过一门限 来确定相邻镜头之间的相似性，将镜头聚类为场景，以这种方式将相似的镜 头组织成有意义的故事单元。 图2 2 基于镜头的模型 2 2 2 镜头聚类过程 在基于镜头表示的模型中，关键帧、镜头、场景构成了视频序列的概括。 镜头聚类包括：视频镜头检测、镜头关键帧提取、镜头聚类。 视频镜头检测的任务是将输入的视频序列分割为各个镜头，镜头检测的 8 哈尔滨工程大学硕士学位论文 依据是背景是否发生了变化。检测镜头的基本方法是根据视频图像的颜色或 者亮度特征，测量帧间像素差值1 2 7 1 ，统计像素值发生变化的像素数目，如果 像素值发生变化的数目超过一个特定的百分比，就认为发生了镜头切换。 视频检索系统1 2 8 j 采用基于镜头的模型，每一个镜头标识出一个或者几个 关键帧，用于生成视觉内容表，系统自动提取关键帧的特征【2 9 1 ，用户可以基 于这些特征对视频数据库进行查询。文献 2 8 3 0 】中通过构造关键帧的等级， 使得基于内容的索引和浏览更为有效。文献 3 0 】中，时域相邻的关键帧基于 颜色、形状、和亮度映射等特征进行聚类，每一个聚类定义为一个场景。文 献 3 0 3 2 1 均介绍了将视频序列分解成镜头、场景、序列的三层的视频信息 模型，镜头是表示视频信息的最小单元，由具有相似特性的镜头构成的场景， 然后由场景组成序列。 2 3 聚类方法 没有任何一种聚类技术( 聚类算法) 可以普遍适用于揭示各种多维数据 集所呈现出来的多种多样的结构3 3 1 。根据数据在聚类中的积聚规则以及应用 这些规则的方法有多种聚类算法。聚类算法有多种分类方法，聚类算法大致分 成层次化聚类算法、划分式聚类算法、基于密度和网格的聚类算法和其他聚 类算法。图2 3 给出了各种聚类算法之间的层次图。 图2 3 聚类算法层次图 9 哈尔滨工程大学硕士学位论文 2 3 1 划分式聚类算法 划分式聚类算法( p a r t i t i o n i n gm e t h o d ) 的基本思想是给定一个包含n 个对 象的数据集，将数据集划分为k 个子集，其中每个子集均代表一个聚类( k 有多种形式，可以是两个关键帧 之间的距离，也可以是两个关键帧集中各帧距离的一种组合形式【d 7 1 。 根据是否考虑视频中镜头关键帧之间的时序关系，可以把视频镜头的相 似度模型分为两类：考虑关键帧之间的时序关系的相似度度量和不考虑关键 帧之间的时序关系的相似度度量。 ( 1 ) 考虑关键帧之间的时序关系的相似度度量 采用该类相似度度量计算两段视频之间的相似度不仅需要计算关键帧之 间的距离，同时需要考虑相匹配关键帧之间的顺序关系对相似度的影响【6 7 】。 由于这种相似度度量从视觉和运动的角度充分考虑两段视频的相似性，因而 利用该方法计算得到的视频片段相似度值，较为符合人的主观判断。下面简 单介绍几种典型的该类相似度度量。 为了较为准确地反映两段视频之间的相似关系，文献【6 7 】中提出一种视 频片段的相似度计算模型，该相似度度量不仅考虑了待比较视频的关键帧之 间的相似度，还考虑了关键帧的时间序列、它们相互之间的位移以及待比较 视频的长度等因素，定义如下： 设d = d o ，d l 矗1 ) ，d k 砒，d 1 d ，n 1 分别代表两段视频且佗m 。，其 中s i m ( d i , 鳓表示关键帧之间的相似度值，则d 和d 之间的相似度定义为： s i m ( d ，d ) - 删翌竺) 士一，) = 抛( 型一) i 二一 所l + c r 芝一工- l - 1 p 一m ( 3 1 7 ) 甩 其中a 【o ，1 】，声【o ，1 】为控制参数，j i 【o ，n - 1 】且如果f ，i 2 ，则工，j i 2 。 m - i s i m ( d f ，d 夕_ 一 在该相似度公式中，刎研型一夕表示了两段视频内包含的所 朋 有帧的相似度情况，则反映了相似的帧的不同时序关系对视频片段相似度的 影响，f l 兰用于调 刀 l + g x i j , - j h 一1 l i = 1 节不同长度视频片段的相似度值。 哈尔滨t 程大学硕士学位论文 因此，该视频片段相似度公式不仅考虑了组成两段视频的帧之间的相似度， 还考虑了相匹配帧之间的位移以及视频长度对相似度的影响，比较合理地从 视觉上反映出两段视频之间的相似度。 文献【6 7 】提出一种以人的视觉感受为基础的视频片段相似度度量，它首 先将视频分割成镜头，并从中提取关键帧代表镜头，视频片段的相似度就转 换成两个有序关键帧集合的相似度，其定义如下： s i m ( c l ，q ) = x s v + 仇+ f r( 3 - l8 ) d r = i 一( c | ，( a 9 一c 2 ( d ) ) m a x ( c l ( d ) ，q ( 回) f r = i 一( c j ( 力一c 2 ( r ) ) m a x ( c l ( r ) ，c 2 ( 力) 其中母表示视频片段c ，和。之间的视觉相似度，也就是相似关键帧的 个数；d r 是视频片段持续时间的比率，g ( 功表示第i 段视频持续的时间；f r 是视频片段帧率比，“，) 表示第i 段视频的帧率。嘶，则为参数权重， 可以调节这三个方面在视频片段相似度中的所占的比重。该相似度度量从人 的视觉感知角度出发，分析了影响视频片段相似性的三个主要方面：视觉相 似性、持续时间以及播放的帧率。通过将这三个方面对视频相似度的影响综 合起来，产生一个较为符合人的主观判断的相似度度量。 考虑关键帧之间的时序关系的相似度度量因为要考虑对应帧的时序关 系，通常计算比较复杂，会耗费大量的查询时间，但是能较准确地反映视频 片段之间的视觉相似度，较好地符合人的主观感受。 ( 2 ) 不考虑关键帧之间的时序关系的相似度度量 该类相似度度量就是将视频片段简单看成关键帧的集合，两段视频之间 的相似度由它们中相似帧的数量决定【6 7 】。定义如下： 帧之间的相似度定义：设x 、y 为代表两帧的高维特征矢量，d ( x ，y ) ， 表示矢量之间的距离，函数f 为二值断言，那么x 、y 之间的相似度定义为： 厂l 足病歹) ) 枷 s i m ( x , y ) = 和 r ， 将 一，乃，凡j ) 保存为一个子片段，并设胪 月，只，r ) ，r 为r ，转到 s e t p 2 。 在该算法中，距离d 利用直方图的交运算，距离阈值，通过实验得到， 该子片段分割算法能够快速有效将原始视频流分割成具有一定色彩分布差异 的视频片段的集合。 基于视觉特征的视频帧分割算法分割的镜头往往比较零碎，由于视频帧 中包含大量的视觉、语音、文本信息，如果能综合利用视频帧中视觉、语音、 3 3 哈尔滨t 程大学硕士学位论文 文本等多模态信息，就可克服单纯使用视觉特征和听觉特征进行分割的弊端 6 s l 。并且文本信息的利用，可使分割在语义层面进行。这样就会大量减少分 割的数目。但是如何有效地融合多模态信息进行分割，就必须考虑不同媒体 的类型的差异性，保证在各模态独自正确分割的前提下，兼顾各媒体间的同 步和时空的关联问题。为解决此问题本文给出了一种基于人工文本、视觉特 征多模态信息的视频帧镜头的分割算法。 4 1 2 基于人工文本、视觉特征的视频帧分割算法 基于人工文本、视觉特征多模态信息的视频帧分割过程如图4 1 所示： l视频帧序列 0 f提取文本帧 0 1分割文本帧 0 1 分割文本帧分割点之间 的非文本帧 图4 1基于人工文本、视觉特征的视频帧分割 算法描述： 设视频序列由帧集合 f z ，巴”：r ) 构成，由t e x t f r a m e i 存储文本帧在在视 频帧的位置，i 为文本帧的编号，j 为视频帧的编号。 s t e p l ：j = o ，i - l ， s t e p 2 ：j - - j + l ， s t e p 3 ：若j 9 对视频帧巧进行文本提取，判断是否包含文本， 如果包含文本，对变量赋值： t e x t f r a m e i = j ，i = i + l ， 如果不包含文本返回到步骤s t e p 2 ： s t e p 4 ：若j n ，对文本帧迸行分割，初步定位文本帧的分割点 s t e p 5 ：对作为分割点的文本帧与其相邻的前一个文本帧之间的非文 哈尔滨t 程大学硕士学位论文 本视频帧进行分割，以精确定位视频帧的分割点。 4 1 3 算法性能分析 基于视觉特征的视频帧分割算法忽略了视频文本特征在视频聚类方面的 高可靠性，在准确率和可靠性都达不到用户的要求。基于视觉特征的视频帧 分割算法往往会产生较多的虚假分割点，从而严重地影响其应用价值。考虑 到新闻视频中拥有大量的文本，采用多模态融合的方法对新闻视频流进行分 割，大幅地减少了虚假分割点，保证了分割片段内容的完整性。从而避免了 将视频分割支离破碎的弊端，使分割的结果有连贯的语义信息，为基于高级 语义内容的视频聚类和检索打下了甚础。基于人工文本、视觉特征多模态信 息的视频帧分割算法综合了文本特征和视觉特征，准确率和可靠性都有所提 高。 4 。2 相似性测度计算 两帧之间的相似度主要是指两帧视频特征的相似度，可以使用颜色、亮 度、色度、纹理、文本、运动和简单形状等特征对帧之间的相似度进行测量。 第3 章介绍了相似性测度计算相关技术，下面介绍本文采用的相似性测度计 算方法。 4 2 1 视频帧相似性测度计算 1 包含文本的视频帧相似性测度 包含文本的视频帧除了可以用颜色、亮度、色度、纹理、运动和简单形 状等特征对帧之间的相似度进行测量之外，本文使用视频帧的文本特征对包 含文本的视频帧之间的相似度进行测量。 提取视频帧的文本，采用现有的分词系统进行分词，再去掉虚词，同义 词合并等预处理之后，剩下的词作为视频帧的文本特征，文本特征采用向量 空间模型表示视频帧的文本向量，包含文本的视频帧相似性可以采用公式 ( 3 5 ) 进行测度。 2 不包含文本的视频帧相似性测度 不包含文本的视频帧可以采用颜色直方图、颜色主色调、颜色均值、纹 哈尔滨下程大学硕七学位论文 理均值等特征对视频帧之间的相似度进行测量。本文使用视频帧的颜色直方 图对不包含文本的视频帧之间的相似度进行测量。不包含文本的视频帧相似 性可以采用公式( 3 7 ) 进行测度。 4 2 2 视频段相似性测度计算 在经过分割的视频段当中，包含文本的视频帧作为视频段的关键帧，关 键帧的文本向量的均值作为视频段的特征向量，也采用公式( 3 5 ) 作为视频段 相似性测度的计算方法，相似度越小，距离越大，相似度越大，距离越小。 4 3 k - m e a n s 算法改进 4 。3 1传统的k - m e a n s 聚类算法 1 9 6 7 年，m a c q u e e n 首次提出了k m e a n s 算法。该算法的核心思想是找 出k 个聚类中心c l ，e 2 ，c k ，使得每一个数据点弱和与其最近的聚类中心c v 的平方距离和被最小化( 该平方距离和被称为偏差d ) 。 算法描述f 2 5 】： s e t p l 初始化 ：随机指定k 个聚类中心( c l ，c 2 ，咏) ； s e t p 2 分配x i ：对每一个样本x i ，找到离它最近的聚类中心c v ，并将其分 配到岛所标明类； s e t p 3 修正c w ：将每一个“移动到其标明的类的中心； s e t p 4 计算偏差 ：d = m i n d ( x ，。c ，) 2 p = l ，2 ，后j ； f 霉l s e t p 5 d 收敛? ：如果d 值收敛，则r e t u m ( c l ，1 3 2 ，c k ) 并终止本算法； 否则，返回步骤s e t p 2 。 传统的k m e a n s 算法优点：能对大型数据集进行高效分类，其计算复杂性 为o ( t k m n ) ，其中，t 为迭代次数，k 为聚类数，m 为特征属性数，1 1 为待分类的 对象数，通常，k ，m ，t 。，为s 中对象 的个数，t = 2 。 s t e p 2 ：计算其余m ，个对象与j 的距离，与s 的距离 d p ：- m i n 么，l x i e s ，x e e z ，施叠j j s t e p 3 ：计算妇m a x 九k e t , ，x e q e s ) x 尸 x i l m a x ( d i d s t e p 4 ：如果磊谚如，是经验参数取1 2 1 之间，则x i 是第三个聚类中 心。严 勃，x q ，而) ，t = t + l 。否则算法结束。 s t e p 5 ：重复( 2 卜( 4 ) 。 算法2 描述： 3 7 哈尔滨工程大学硕士学位论文 r a s t e p l ：有m 个对象，z = x l ，x 2 ，而) 。计算m 个对象的均值= t l = l s t e p 2 ：x p 、x q 为两个初始聚类中心， 的距离, 阳= m a x 4 , j 胪1 ，2 ， 数，t = 2 。 勃。m a x 如i 产1 ，2 ，m ) ，x p 、x q ，m ) ，s = 劫嘞) 。，为s 中对象的个 s t e p 3 ：计算其余m t 个对象与s 的距离，与s 的距离咖i n 吃f k s , x e e z ，晚诺s ) s t e p 4 ：计算蝣m a x d 。s x e e z ，仨s ) 胪 而l m a x ( 九) ) s t e p 5 ：如果磊毒宁，声是经验参数取l 从l 之间，则x i 是第三个聚类中 心。萨 勃，x q ，而 ，：什1 。否则算法结束。 s t e p 6 ：重复( 3 卜( 5 ) 。 4 3 3 算法性能分析 通过进行第5 章仿真二实验，实验表明传统算法准确率不稳定，平均准 确率较低，效果不是很好。采用改进算法能够得到较高且稳定的准确率，得 到的聚类结果也比传统的k 均值算法得到的聚类结果效果显著，是一个确实 可行的解决聚类问题的方法。虽然改进的算法在确定初始聚类中心点和聚类 数消耗了一些时间，但由于传统算法初值选取的随意性，算法陷入局部最优 的可能性也高于改进的算法。 通过进行第5 章仿真三实验，把k - m e a n s 改进算法应用在基于人工文本、 视觉特征多模态信息方法提取的视频镜头聚类中，实验表明k - m e a n s 改进算 法的聚类结果接近标准的人工聚类结果。 4 4 本章小结 本文给出了一种基于人工文本、 割算法和一种k m e a n s 改进的算法， 视觉特征多模态信息的视频帧镜头的分 并对算法进行性能分析。 哈尔滨工程大学硕十学位论文 第5 章仿真实验与结果分析 为了验证基于人工文本、视觉特征多模态视频帧分割算法、k - m e a n 改进 算法的性能，设计仿真实验，并对实验结果进行分析。 5 1 评价指标 聚类结果的评价方法有很多。这些方法都遵循一个共同的原则【6 9 】，那就 是认为一个好的聚类是使簇内的对象结合得尽量紧密，但同时簇与簇之间尽 量分离。比如其中最简单的一种方法就是计算每一个点到其所在簇中心的距 离之和，然后和值越小说明聚类结果越好。还有一类评价方法是将聚类结果 和标准的分类进行比较，其原则是“与标准分类越接近，那么聚类结果也就 越好 。这类方法因为需要标准类信息，所以不能用于自动聚类评价，但却是 最为有效的评价方法，故本文使用这类方法来对聚类的结果进行评价。这类 方法中常用的有熵( e n t r o p y ) 和查准率( p r e c i s i o n ) 【6 9 1 ，下面对它们进行进 一步的介绍。 熵( e n t r o p y ) 衡量的是每一个聚类的纯度，e n t r o p y 的值越小，表示聚 类结果的纯度越高，也就越好。设g 和g 分别为聚类所得到的簇类的个数和 标准类的个数，设a 为聚类结果中的某一个簇类，并设这个簇类中每一个文 本d 。a ，i = l ，i a i 的标准类标识为l a b e l ( d i ) ，它的值等于标准的类标识 c j ( j = l ，g ) 。e n t r o p y 的计算公式如式( 5 1 ) 所示： g - l ig e n t r o p y = 一导p j k l o g ( p j k ) ( 5 1 ) 厶一、t 一j ， 、 k = l “j = l 1r-1 其中 厶= 南i 协ll a b e z ( d i ) = c _ 。 f 以i e n t r o p y 有一个很大的缺点就是不直观，所以我们还使用了另一个更为直 观的衡量标准一查准率( p r e c i s i o n ) ，因为聚类所得到的簇类往往很杂，每一 个簇类里面的数据可能来自多个不同的标准类，所以这个标准就假设这个簇 哈尔滨工程大学硕士学位论文 类的标准类标识就等于这个簇类中最大的那个标准类的类标识，因此这个簇 类的查准率( p r e c i s i o n ) 就等于这个簇类中最大的那个标准类所占的比例， 其计算公式如式( 5 2 ) ： p r e c 捃f 。彳) = 南m a x 3 p ，i l a b e l ( d ，) = c ji ) ( 5 - 2 ) i - l 整个聚类结果的查准率( p r e c i s i o n ) 的计算则如公式( 5 3 ) 所示： p r p c 括面刀= 兰乓乒p r p c 豇幻以4 ) ( 5 3 ) 智 一7 v 叫 综上所述，由于查准率( p r e c i s i o n ) 简单直观，所以本文中的实验部 分均使用此标准来评价聚类的效果及分割效果。 5 2 仿真实验的设计与实现 仿真实验在一台p c 机上完成。p c 机的配置为c p up 43 0 g h z ，内存 5 1 2 m b ，硬盘1 0 0 g b ，操作系统w i n d o w sx p 。使用m a t l a b7 5 0 3 4 2 进行仿 真实验。 5 2 1仿真一 对一视频帧序列分别利用基于人工文本、视觉特征多模态视频帧分割算 法和基于视觉特征视频帧分割算法，验证基于人工文本、视觉特征多模态视 频帧分割算法的有效性。并分别记录迭代次数、程序的运行时间和准确率。 通过实验效果图，对改进后的算法进行分析。 首先用腾讯q q 软件截取新闻联播视频帧序列，在m a t l a b 环境下，分别 对基于人工文本、视觉特征多模态视频帧分割算法和基于视觉特征的视频帧 分割算法进行仿真实验，验证算法的有效性并给出分割效果图如图5 1 、5 2 和5 3 所示。计算查准率如表5 1 所示。 哈尔滨工程大学硕十学位论文 果。 帧号 图5 1 人工分段结果 图5 1 是用腾讯q q 软件截取新闻联播视频序列进行标准的人工分段结 帧号 图5 2 基于视觉特征的分段结果 4 1 最堋宦馨 最棚厘警 哈尔滨t 程大学硕士学位论文 图5 2 是用腾讯q q 软件截取新闻