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

Vol.

14, No.8 ?2003 Journal of Software 软件学报1000-9825/2003/14(08)1409 一种通过视频片段进行视频检索的方法 ? 彭宇新 1,2+ , Ngo Chong-Wah3 , 董庆杰 1,2 , 郭宗明 1,2 , 肖建国 1,2

1 (北京大学 计算机科学技术研究所,北京 100871)

2 (北京大学 文字信息处理技术国家重点实验室,北京 100871)

3 (香港城市大学 计算机科学系,香港) An Approach for Video Retrieval by Video Clip PENG Yu-Xin1,2+ , NGO Chong-Wah3 , DONG Qing-Jie1,2 , GUO Zong-Ming1,2 , XIAO Jian-Guo1,2

1 (Institute of Computer Science and Technology, Peking University, Beijing 100871, China)

2 (National Key Laboratory of Text Processing Technology, Peking University, Beijing 100871, China)

3 (Department of Computer Science, City University of Hong Kong, Hong Kong, China) + Corresponding author: Phn: 86-10-62752426, Fax: 86-10-62981438, E-mail: [email protected] http://www.icst.pku.edu.cn Received 2002-11-25;

Accepted 2003-03-20 Peng YX, Ngo CW, Dong QJ, Guo ZM, Xiao JG. An approach for video retrieval by video clip. Journal of Software, 2003,14(8):1409~1417. http://www.jos.org.cn/1000-9825/14/1409.htm Abstract: Video clip retrieval plays a critical role in the content-based video retrieval. Two major concerns in this issue are: (1) automatic segmentation and retrieval of similar video clips from video database;

(2) similarity ranking of similar video clips. In this paper, motivated by the maximal matching and optimal matching in graph theory, a novel approach is proposed for video clip retrieval based on matching theory. To tackle the clip segmentation and retrieval, the retrieval process is divided into two phases: shot-based retrieval and clip-based retrieval. In shot-based retrieval, a shot is temporally partitioned into several sub-shots based on motion content. The similarity among shots is measured according to the color content of sub-shots. In clip-based retrieval, candidates of similar video clips are selected by modeling the continuity of similar shots. Maximal matching based on Hungarian algorithm is then adopted to obtain the final similar video clips. To rank the similarity of the selected video clips, four different factors: visual similarity, granularity, interference and temporal order of shots are taken into consideration. These factors are modeled by optimal matching based on Kuhn-Munkres algorithm and dynamic programming. Experimental results indicate that the proposed approach is effective and efficient in retrieving and ranking similar video clips. Key words: content-based video retrieval;

clip;

similarity;

maximal matching;

optimal matching 摘要: 视频片段检索是基于内容的视频检索的主要方式,它需要解决两个问题:(1) 从视频库里自动分割出与查 询片段相似的多个片段;

(2) 按照相似度从高到低排列这些相似片段.首次尝试运用图论的匹配理论来解决这两个 ? 第一作者简介: 彭宇新(1974-),男,贵州都匀人,博士生,主要研究领域为基于内容的视频检索.

1410 Journal of Software 软件学报 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]相比,无论是检索的准确性........