一种新的时序一致性特征的近重复视频检测算法

郭丁云+薛峰+郭旦萍

摘要：针对基于镜头关键帧层次进行近重復视频检测耗时的问题，该文提出了一种新的视频镜头的时序一致性特征，使用该特征对已有研究的级联式近重复视频检测算法进行改进。首先在进行关键帧特征提取之前，在镜头层次利用镜头的时序一致性特征初步滤除掉一些完全不相同的视频，然后再使用全局分块颜色特征和SURF特征，并使用k-d树型索引结构来实现快速最近邻检测，最终逐步检测与查询视频重复或近重复的视频。通过在CC_WEB_VIDEO标准数据集上进行实验，并与现有常用的三种方法比较，结果显示本文方法的检测效果更好，尤其对于那些画面变化较大以及运动场景复杂的视频更明显。

关键词：近重复视频检测；时序一致性特征；分块颜色特征；加速鲁棒特征；k-d树型索引结构

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）31-0160-04

Abstract： Given the existing near-duplicate video detection algorithms are processed by matching features directly in the key frame level， which is very time-consuming， this paper introduces a new cascaded near-duplicate video detection approach using the temporal consistency feature in the shot level to preliminarily filter out some dissimilar videos before extracting features， and combining global blocking color features and SURF feature. Then we use the k-d tree indexing structure to achieve fast detection speed and thus obtain the ultimate videos that are duplicated with the query video step by step. We have verified the approach by experimenting on the CC_WEB_VIDEO dataset， and compared the performance with the existing three commonly used methods. The analysis results show the proposed method can achieve better detection effect， especially for the videos with great frame changes and complex motion scenes.

Key words： Near-duplicate Video Detection； Temporal Consistency Feature； Blocking Color Feature； Speeded Up Robust Feature （SURF）； K-d Tree Indexing Structure

随着各种视频共享网站的普及以及多媒体技术的发展，互联网上的视频数量和种类飞速增长。视频被大量传播和复制造成了很多问题[1]，比如视频盗版、视频冗余等。文献[2]曾指出在来自于社交网站上主要的24类查询中存在着平均27%的重复，最大甚至达到93%。在视频监控领域，需要从成千上万个海量视频中找到用户关心目标的视频，比如穿蓝色上衣的人，对大规模监控视频进行检索必然花费很多精力和时间。在这个大背景下，有关视频检索和视频摘要的研究开始如火如荼地开展起来[3-4]，针对如何在大规模视频集中更加准确又快速地检测出相同或相近的视频或目标，在多媒体搜索和内容分析中变得越来越重要。

目前现存的研究比较深入的近重复检测算法大致如文献[5]中所述。最常用的特征有全局特征、局部特征以及联合这两种特征的分层方法。全局特征中一般利用能够简单描述整个图像颜色分布的颜色直方图，局部特征主要描述图像的区域特征，具有计算简单、对局部遮挡和视觉变换鲁棒性强的特点。在文献[6]中提出了视频直方图这一新的全局签名特征，来描述视频中特征向量的分布情况。文献[7]中由Wu Xiao等人提出了一种分层的方法，结合视频的全局特征和局部特征进行一步步检测，先滤除简单场景的完全不相同的视频，再利用局部特征检测复杂场景的视频。文献[2]中Wu Xiao等人提出了一种结合视频内容和上下文信息的检测方法，将全局签名特征和局部关键点的内容特征与视频的时长、评论、缩略图、访问次数等上下文信息结合起来，以减少大量关键帧比较的计算量。总的来说，这些方法一般都是直接在所有关键帧图像上提取特征，对于大规模视频进行检测，不仅会花费大量时间，还丢失了视频本身在时间上的一致性信息。

基于以上分析，受文献[7]启发，本文首先根据视频本身固有的时间一致性特征，提出一种新的计算视频时序一致性特征的方法，对现有的级联式检测算法进行改进，首先在对视频的关键帧图像进行特征提取之前，先利用镜头的时序一致性特征在镜头层次初步滤除掉一些完全不相同的视频，然后再使用全局分块颜色特征和SURF特征一步步进行更精确的检测，最后使用k-d树型索引结构来实现快速最近邻检测，得到与要检测视频相同或相似的视频的子镜头和对应的关键帧，最终逐步检测与查询视频重复或近重复的视频，具体框架如图1所示。

1 本文算法

1.1 基于边缘轮廓差值法进行镜头边界检测

要进行近重复视频检测和检索，第一步就是要对视频进行分解，先要进行镜头边界检测，找出视频中不同镜头发生变换的位置，然后再进一步分解视频为镜头片段。本文中采用的是边缘轮廓差值法进行镜头边界检测，具体实现步骤在文献[8]中已有详细说明，在此不再赘述。

1.2 基于帧差欧式距离法进行关键帧提取

对视频进行匹配检测可以看作是对静态图像进行匹配检测，因此在进行镜头边界检测之后就可以提取各镜头中的关键帧图像，然后进行图像的特征提取和比较。本文采用的是基于帧差的欧式距离法来提取各个子镜头中的关键帧，在文献[8]中已有详细说明。

1.3 基于视频镜头连续一致性的时序特征

考虑到视频本身的特征，因为视频是由很多连续时间上的静态帧图像组成的，因此相邻的帧图像之间必然在内容上存在特别强烈的相关性，每个镜头中提取的关键帧应该也存在这样的相关性，而不同视频的镜头和视频中不会具有相同的时序一致性。本文中利用这一时序性質，提出了一种新的计算时序一致性特征的方法来表示视频镜头，在提取关键帧的颜色特征之前，直接在镜头层次上比较，提取出关键帧集中的时间切片特征，快速滤除无关视频，时序一致性特征的生成如图2所示。

具体实现步骤如下：

（1）首先提取出待检测视频与视频库中所有视频的镜头中的关键帧并统计其数目，按照时间顺序将每个关键帧图像分为九块，并计算中间块的颜色特征；

（2）将每个镜头中的关键帧图像中间块的颜色特征构成一个矩阵，可以计算得知该矩阵的行数为关键帧数目，而列数为36，这即可作为该镜头中的时序一致性特征；

（3）将待检测视频各镜头的时序一致性特征作为待检测特征，分别与视频集中所有镜头的时序特征进行比较，在这里采用余弦相似性作为比较指标；

（4）将比较所得的余弦相似度与事先设定的阈值进行比较，如果大于该阈值，即表明两者相似，就取出来这一满足条件的镜头，以进行接下来更细的比较，若小于该阈值，表明两者不相似，进而说明该镜头所在的视频与待检测视频不相似，即可滤除，这样就可以直接在镜头层次进行一次初步滤除，避免进行特征提取和比较时花费大量时间和精力。

1.4 基于重叠图像分块方法进行全局特征提取

为了提高颜色特征提取的完整性，以保留足够丰富的颜色位置信息，本文采用文献[9]中提出的重叠图像分块方法，对图像分为8个区域，在每一区域内统计颜色直方图来获得颜色空间分布，这里不再赘述。

1.5 基于SURF算法进行局部关键点特征提取

鉴于SURF算法[10]中由于使用了积分图像和箱式滤波器，运算速度是SIFT的3倍左右，且对于图像的平移、旋转、缩放以及噪声的影响有很强的鲁棒性，文中采用SURF算法提取局部特征。

1.6 基于k-d树的特征索引与检索

考虑到本文中视频集中视频数量较多，达成百上千个，本文采用的索引结构是k-d树，与一般方法相比，它本身具有的特点就是对于大规模的数据检索有特别明显高效的处理速度，因此使用k-d树型索引结构非常合适。实验中首先从视频库中任意取出部分视频作为训练集，初步建立一个k-d树，对其他视频进行比较，能够在的时间复杂度里获得最相近的视频向量，其所对应的视频即为近重复视频。

2 实验结果与分析

2.1 实验说明

本文实验所用的电脑配置为Intel（R） Core（TM） i3 2.93GHz，2 GB RAM，实验平台为Microsoft Visual Studio 2005。实验中使用的评价方法是大规模视频集进行拷贝检测和近重复检测常用的查准率和查全率。

本文实验中使用的视频集是这类相关研究中普遍使用的公共视频集CC_WEB_VIDEO，是在2006年11月由香港城市大学和卡耐基梅隆大学负责搜集完成的，视频主要来自YouTube、Google Video和Yahoo！Video中人们最常浏览和感兴趣的24类查询的源视频及其近重复视频，如图3所示。

2.2 实验结果

首先要寻找一个查询视频，这里采用文献[7]中的方法进行种子视频的选择，这里不再赘述。将实验结果与基于颜色直方图的全局签名的方法[6]（M_GLOF）、联合视频内容和上下文信息的方法[2]（M_CONTX）及结合全局特征和局部特征结合起来的分层方法[7]（M_HIER）进行比较，文中时序一致性特征方法用CAS_TF表示，得到各方法的查准率-查全率曲线（PR曲线图）如图4所示，在查全率相同时，查准率越高，则这种方法的性能越好。

2.3 结果分析

通过图4中各图进行分析，可得出以下结论：

（1）从图4（a）可以看出，文献[6]中的M_GLOF方法可以很快速又精确地检测出那些具有简单场景或变化很小或者完全相同的视频，比如视频集中的查询9、16、24，但从图4（d）可看出采用本文方法也能够取得同样好甚至更好的检测效果。由于在简单场景或变化很小的视频中增加或删除一些相似的帧图像不会对其颜色直方图产生太大影响，故可以直接通过全局颜色特征进行检测，但是对于场景复杂或经过了很大修改的视频却存在着不同视频有同样颜色分布的情况，因此不能简单靠全局特征检测出来。

（2）从图4（b）中可以很明显地看到，文献[2]中M_CONTX方法效果是最差的，如查询17、18、22，主要是因为在定义近重复视频的时候，我们并没有将视频的标题、缩略图以及长短版本等上下文信息作为视频内容特征，而这种方法恰恰是首先按照视频的持续时间长短来检测视频的，因此就存在着很大的检错可能性。

（3）从图4（c）中可以看出，文献[2]中M_HIER方法对于大多数查询都取得了很好的效果，首先利用全局颜色特征很容易就可以滤除掉一些很明显不相同的视频，剩下的视频再用更精确的局部关键点特征进行检测，不仅提高了检测正确性，还可以大大降低检测时间。

（4）从图4（d）中可以看出，采用本文方法（CAS_TF）取得了不错的检测效果，尤其是对于那些画面变化较大或运动场景复杂的视频更加明显，比如查询13和15，在高的查全率情况下， 大部分查询都取得了与其他三种相比较高的查准率。但也可以看到本方法对于查询22效果非常不好，分析该视频发现，在该视频的开头和结尾部分加入了很多不相关的帧，而本文方法在一开始提取镜头时序一致性特征，按照视频镜头特征进行比较匹配，有可能将该视频作为不相同的视频滤除掉，从而导致查准率较低。

3 结论

通过以上分析可以看出，本文方法（CAS_TF）的性能比其他三种近重复检测算法效果要好，尤其对于那些画面变化较大以及运动场景复杂的视频更明显。不足之处在于本文没有对各检测算法所耗时间进行比较。未来的研究工作主要有两点，一是对各种方法进行检测所耗时间和存储特征的复杂度进行分析，进一步完善该算法，更有力地验证该方法的优势；二是要设计自适应的阈值设置方案，而不用在每次检测时都要人为地设置不同阈值，以进一步提高检测的准确性。

参考文献：

[1] Yan K， Sukthankar R， and Huston L. Efficient near-duplicate detection and sub-image retrieval[C]. Proceedings of ACM International Conference on Multimedia（MM）， 2004： 869-876.

[2] Wu X， Ngo C W， Alexander G H， et al.. Real-Time Near-Duplicate Elimination for Web Video Search With Content and Context[C]. IEEE Transactions on Multimedia， 2009， 11（2）： 196-207.

[3] Hong R C， Tang J H， Tan H K， et al.. Beyond search： event driven summarization for web videos[C]. Proceedings of ACM International Conference on Multimedia（MM）， 2011， 2（3）： 1-21.

[4] Ngo C W， Zhao W L， and Jiang Y G. Fast Tracking of Near-Duplicate Keyframes in Broadcast Domain with Transitivity Propagation[C]. Proceedings of ACM International Conference on Multimedia （MM）， 2006： 845-854.

[5] Shang L F， Yang L J， Wang F， et al.. Real-time large scale near-duplicate web video retrieval[C]. Proceedings of ACM International Conference on Multimedia（MM）， 2010： 531-540. Innovative Computing， Information and Control，2011， 7（4）： 1639-1649.

[6] Lu L， Wei L， Xian S H， et al.. Video Histogram： A Novel Signature for Efficient Web Video Duplicate Detection[J]. Lecture Notes in Computer Science， 2007： 94-103.

[7] Wu X ， A. G. Hauptmann， and Ngo C W. Practical elimination of near-duplicates from web video search[C]. Proceedings of ACM International Conference on Multimedia （MM）， 2007： 218-227.

[8] 郭丁云， 楊艳芳. 一种新的近重复监控视频检测算法[J].微型机与应用， 2013（11）.

[9] 丁宏波. 基于颜色和纹理的图像检索系统的研究与实现[D]. [D]. 北京交通大学， 2008.

[10] Bay H， Tuytelaars T， and Van G L. SURF： Speeded Up Robust Features[J]. Computer Vision and Image Understanding， 2008， 110（3）：346-359.