一种通过视频片段进行视频检索的方法

Vol.14,No.8©2003JournalofSoftware软件学报1000-9825/2003/14(08)1409一种通过视频片段进行视频检索的方法∗彭宇新1,2+,NgoChong-Wah3,董庆杰1,2,郭宗明1,2,肖建国1,21(北京大学计算机科学技术研究所,北京100871)2(北京大学文字信息处理技术国家重点实验室,北京100871)3(香港城市大学计算机科学系,香港)AnApproachforVideoRetrievalbyVideoClipPENGYu-Xin1,2+,NGOChong-Wah3,DONGQing-Jie1,2,GUOZong-Ming1,2,XIAOJian-Guo1,21(InstituteofComputerScienceandTechnology,PekingUniversity,Beijing100871,China)2(NationalKeyLaboratoryofTextProcessingTechnology,PekingUniversity,Beijing100871,China)3(DepartmentofComputerScience,CityUniversityofHongKong,HongKong,China)+Correspondingauthor:Phn:86-10-62752426,Fax:[phone],E-mail:[e-mail](8):1409~1417.:Videoclipretrievalplaysacriticalroleinthecontent-basedvideoretrieval.Twomajorconcernsinthisissueare:(1)automaticsegmentationandretrievalofsimilarvideoclipsfromvideodatabase;(2)similarityrankingofsimilarvideoclips.Inthispaper,motivatedbythemaximalmatchingandoptimalmatchingingraphtheory,anovelapproachisproposedforvideoclipretrievalbasedonmatchingtheory.Totackletheclipsegmentationandretrieval,theretrievalprocessisdividedintotwophases:shot-basedretrievalandclip-basedretrieval.Inshot-basedretrieval,ashotistemporallypartitionedintoseveralsub-shotsbasedonmotioncontent.Thesimilarityamongshotsismeasuredaccordingtothecolorcontentofsub-shots.Inclip-basedretrieval,candidatesofsimilarvideoclipsareselectedbymodelingthecontinuityofsimilarshots.MaximalmatchingbasedonHungarianalgorithmisthenadoptedtoobtainthefinalsimilarvideoclips.Torankthesimilarityoftheselectedvideoclips,fourdifferentfactors:visualsimilarity,granularity,interferenceandtemporalorderofshotsaretakenintoconsideration.ThesefactorsaremodeledbyoptimalmatchingbasedonKuhn-Munkresalgorithmanddynamicprogramming.Experimentalresultsindicatethattheproposedapproachiseffectiveandefficientinretrievingandrankingsimilarvideoclips.Keywords:content-basedvideoretrieval;clip;similarity;maximalmatching;optimalmatching摘要:视频片段检索是基于内容的视频检索的主要方式,它需要解决两个问题:(1)从视频库里自动分割出与查询片段相似的多个片段;(2)按照相似度从高到低排列这些相似片段.首次尝试运用图论的匹配理论来解决这两个∗第一作者简介:彭宇新(1974－),男,贵州都匀人,博士生,主要研究领域为基于内容的视频检索.1410JournalofSoftware软件学报2003,14(8)问题.针对问题(1),把检索过程分为两个阶段:镜头检索和片段检索.在镜头检索阶段,利用相机运动信息,一个变化较大的镜头被划分为几个内容一致的子镜头,两个镜头的相似性通过对应子镜头的相似性计算得到;在片段检索阶段,通过考察相似镜头的连续性初步得到一个个相似片段,再运用最大匹配的Hungarian算法来确定真正的相似片段.针对问题(2),考虑了片段相似性判断的视觉、粒度、顺序和干扰因子,提出用最优匹配的Kuhn-Munkres算法和动态规划算法相结合,来解决片段相似度的度量问题.实验对比结果表明,所提出的方法在片段检索中可以取得更高的检索精度和更快的检索速度.关键词:基于内容的视频检索;片段;相似度;最大匹配;最优匹配中图法分类号:TP391文献标识码:A随着电视台视频节目的积累,网上数字视频的增加,以及数字图书馆、视频点播、远程教学等大量多媒体的应用,如何在海量视频中快速检索出所需要的资料显得至关重要.传统的基于关键词描述的视频检索因为描述能力有限、主观性强、手工标注等原因,已经不能满足海量视频检索的需求.因此,从20世纪90年代开始,基于内容的视频分析和检索技术成为研究的热点问题.由于基于内容的图像检索的困难性和复杂性,大量的研究主要集中在视频内容的结构分析上,如镜头的分割、关键帧的提取、场景的构造等,视频检索方面的研究则相对较少,而这部分常常是应用的关键.视频检索一般分为镜头检索和片段检索.镜头一般是由摄像机一次摄像的开始和结束的所有帧构成,表示一个物理概念.而片段是由一连串语义相关的连续镜头构成,表示的是一个语义概念.目前视频检索的多数研究集中在镜头检索上[1~4],而片段检索方面的研究则刚刚开始[5~11].实际上,从用户的角度分析,他们对视频数据库的查询通常会是一个视频片段而很少会是单个的物理镜头.从信息量的角度分析,由几个镜头组成的视频片段比单个镜头有更多的语义,它可以表示用户感兴趣的事件,因此,查询的结果也比较有意义.例如,从新闻中检索出感兴趣的事件,从体育节目中检索出喜爱的体育运动,电视台检索某条广告是否播出等.基于这种考虑,本文提出了一种通过视频片段进行视频检索的方法,以满足用户通过视频片段来提交的查询需求.视频片段检索需要解决两个问题:(1)从视频库里自动分割出与查询片段相似的多个片段;(2)按照相似度从高到低排列这些相似片段.目前已有的片段检索方法可以分为两类:(1)把视频片段分为片段-帧两层考虑,片段的相似性利用组成它的帧的相似性来直接度量[5~7];(2)把视频片段分为片段-镜头-帧三层考虑,片段的相似性通过组成它的镜头的相似性来度量,而镜头的相似性通过它的一个关键帧[8~10]或所有帧[11]的相似性来度量.方法(1)的缺点在于,限制相似的片段必须遵守同样的时间顺序,而实际的视频节目并不遵守这种约束,因为后期编辑的结果使得相似的片段完全可能具有不同的镜头顺序,如同一个广告的不同编辑.同时,这种基于每帧的比较,也使得检索速度比较慢.方法(2)的思想比较合理,但这种方法从已有的文献上看并没有很好解决片段检索的问题.文献[8~10]提出了影响视频相似度度量的顺序因子、速度因子、粒度因子、干扰因子,但它的片段是预先分割好的,并没有解决怎样在连续的视频节目里自动分割出多个相似片段的问题.与文献[8~10]相反,文献[11]完全忽略了镜头顺序、粒度、干扰因子的影响,两个片段的相似度仅仅取决于它们相似镜头的数量,因此,即使片段Y的所有镜头仅仅和片段X的一个镜头相似,Y也会被认为与X相似;另外,镜头的相似性是根据两个镜头相似的最长帧序列来判断,这种基于每帧的比较和文献[5~7]类似,片段的检索速度也较慢.针对上述问题,本文提出解决片段检索两个问题的一个新方法.为了分割出相似片段,本文采用了上述方法(2)的思想,把检索过程分为镜头检索和片段检索两个阶段:在镜头检索阶段,考虑了视频中的时间信息,把一个镜头内部随时间变化的内容,分解为几个内容一致的子镜头(sub-shots),这种基于子镜头的比较全面地反映了两个镜头是否相似;在片段检索阶段,通过考察相似镜头的连续性初步得到一个个相似片段,再运用最大匹配的Hungarian算法来确定真正的相似片段.为了排列相似片段,类似于文献[8~10],本文考虑了片段相似度度量的不同因子,不同于文献[8~10],提出用最优匹配的Kuhn-Munkres算法和动态规划算法相结合来度量这些因子的影响.本文首次尝试运用图论的匹配理论来解决视频检索问题,这是因为匹配的思想要求相似镜头必须一一对应(粒度),在这个条件下,求出的最大匹配和最优匹配可以客观而全面地反映两个片段相似的镜头数量和两个片段视觉相似的程度,从而避免了文献[11]中镜头计算的粒度问题.第4节的实验结果表明,与具有同样功能的文彭宇新等:一种通过视频片段进行视频检索的方法1411献[11]相比,无论是检索的准确性,还是检索速度,本文提出的方法都取得了更好的效果.本文第1节首先介绍了本文的理论基础——图论的最大匹配和最优匹配.第2节介绍怎样自动分割相似片段.第3节介绍视频片段的相似度模型.第4节给出了实验结果.第5节是总结.1最大匹配和最优匹配简介最大匹配和最优匹配是图论中的两个经典问题,其中,最大匹配解决的一个典型应用问题如下:假设有n个工作人员x1,x2,…,xn安排做m项工作任务y1,y2,…,ym,如图1所示,其中边eij=(xi,yj)表示xi可以从事yj,如果每个人最多从事其中一项工作,且每项工作只能由一人承担.问:怎样才能让尽可能多的人安排上工作?在上面的工作安排问题中,只着眼于每一工作人员都能安排一份工作,并没有考虑如何更好地发挥工作人员的专长问题.如图2所示,最优匹配解决的典型问题是:假设每个工作人员xi从事yj工作时的效率为ωij,问:怎样合理安排才能使总的工作效率最高?x1x2x3x4…xnx1x2x3x4…xn543…9810y1y2y3y4…ymy1y2y3y4…ymFig.1MaximalmatchingFig.2Optimalmatching图1最大匹配图2最优匹配考虑到最大匹配和最优匹配的不同性质,并且最大匹配的计算复杂度低于最优匹配,在第2节,本文首先运用最大匹配来得到相似片段,然后在第3节,运用最优匹配来计算两个相似片段的视觉因子.2自动分割相似片段2.1镜头检索因为本文以镜头的相似性为基础来讨论片段的相似性,所以,无论是视频库,还是查询片段