随着多媒体技术的发展,互联网上的音视频数量急剧增长。相同内容的音视频文件常常会经过再次编辑,成为许多拷贝版本出现在不同的网站上。基于内容的视频拷贝检测(content based copy detection,CBCD)是通过测量从待检测视频和原始视频中提取的能唯一标识视频内容的特征之间的距离来判断待检测视频是否是原始视频的拷贝。它主要包含了镜头分割、关键帧提取、特征提取和相似性度量这4个部分[1]。近年来,出于保护版权以及避免资源浪费等需要,基于内容的视频拷贝检测技术获得了越来越多研究者的关注,成为了一大研究热点。
Naphade等[2]通过提取和比较图像帧的YUV直方图特征来进行拷贝检测,虽然计算简单,却对图像的颜色变化较为敏感。Hampapur等[3]将图像帧分成m×n个子块,求取每个子块的平均灰度值,再将平均灰度值进行排序,这种方法计算复杂度低,对图像颜色变化鲁棒,但是对图像的局部变化比较敏感。Zhang等[4]提出了基于时域特征的拷贝检测算法,该方法将图像帧分成m×n个子块,得到平均灰度值最大的3个子块的位置,通过比较相邻关键帧的位置变化来进行拷贝检测,该方法对插帧或丢帧不鲁棒。Natsev等[5]提取图像帧的尺度不变特征算子和颜色相关图,该方法鲁棒性较好,但是算法复杂度高,处理时间较长。
本文提出基于分块Harris角点[6]和分块亮度顺序(ordinal measures,OM)[7]的视频拷贝检测算法,该算法结合了局部特征和全局特征,避免了采用单一特征鲁棒性差的问题,能够适应视频图像的重编码、亮度、局部遮挡和水平翻转等变化。此外,还提出了基于最大信息熵的关键帧检测算法,提高了关键帧检测的最优性。实验表明,该算法能有效地提高视频拷贝的检测准确性。
1 算法整体框架图1给出了基于分块Harris角点和分块亮度顺序的视频拷贝检测算法整体框架。第1步,将视频分割成不同的镜头,对于每个镜头提取其关键帧; 第2步,对关键帧图像进行预处理,减轻光照和边框等造成的干扰; 第3步,提取关键帧图像的特征包括分块Harris角点特征和OM特征等; 第4步,将提取到的特征在特征库内进行检索; 第5步,采用基于时序一致性的检验方法,对匹配结果进行二次检验,最终输出结果。
2 具体算法 2.1 关键帧提取算法视频是由镜头所组成,每个镜头的帧图像是相似的,不同镜头的帧图像往往有较大差别。镜头之间的变换主要有突变和渐变这2种[8](见图2),其中线段的长度代表其与前一帧相比变化的大小。对于切变的镜头,它与前一帧的差别往往较大,因而能够通过设定阈值进行区分; 但是对于渐变的镜头,它与前一帧的差别不大,因而单纯通过设定阈值与前一帧相比很难区分,但是在稍长时间里(如 1 s)的变化是很大的,因而本文利用它与前一段时间(如1 s)的变化来分割镜头。
本文采用基于分块亮度顺序的方法,将图像帧分成m×n块,分别统计每一块的平均灰度值,然后按照顺序将这m×n块进行排序,并将排序的结果作为当前图像帧的特征F:
F=[I1,1,I1,2,…,I1,8,I2,1,…,I8,8]
(1)
通过综合比较图像帧与前一帧及前一秒图像帧的变化,对视频镜头进行分割。对于每一个镜头,根据式(2)计算图像的信息熵:
$H\left( p \right) = - \sum\limits_{i,j} p \left( {i,j} \right)\ln p\left( {i,j} \right)$
(2)
采用最大信息熵的方法选取图像的关键帧,可以有效地避免选取关键帧过亮或者过暗的情况,能够在多个相似帧中选取最清晰和信息量最大的结果。
2.2 关键帧图像的特征提取由前所述,采用单一特征在处理视频图像变换时有较大的局限性,全局特征算法简单,速度快,对图像光照、噪声和分辨率等变化具有很好的鲁棒性,但是对图像旋转和位移等变化较为敏感; 局部特征算法较为复杂,速度较慢,对图像旋转和位移等变化具有很好的鲁棒性,但是对噪声比较敏感。由于局部特征与全局特征具有很好的互补性,本文采用了结合局部特征与全局特征的关键帧图像特征提取算法。
1) 基于分块Harris角点的局部特征。
Harris角点检测算子[6]是对Moraves算子的改良和优化。Harris算法的表达式如下:
$M = G\left( {\tilde s} \right) * \left[ {\matrix{
{{g_x}^2} & {{g_x}{g_y}} \cr
{{g_x}} & {{g_y}^2} \cr
} } \right].$
(3)
Harris算法的角响应准则为
R=det(M)-ktr(M)2.
(4)
Harris角点检测算法具有旋转不变性、平移不变性和尺度不变性的特点。此外,该角点的计算量比其他类型的局部特征点的小[9],因此本文采用Harris角点作为关键帧的局部特征。
在实际应用中本文发现Harris角点检测算子在角点的选取上常常过于集中(见图3a),这样提取到的特征不能全面地表达图像的整体信息,且很容易受到台标等添加物的干扰,对图像的裁剪也不鲁棒。为了克服这个问题,本文提出了分块Harris检测算法,如图3b所示。将关键帧分割成2×2的图像块,在每个图像块中分别提取Harris角点,可以看出,分块角点的提取结果更加均匀。
2) 基于OM的全局特征。
与节2.1中关键帧提取算法相同,采用基于OM的算法,将图像帧分成m×n块(本文取m=8,n=8),分别统计每一块的平均灰度值,按照顺序将这m×n块进行排序,并将排序的结果作为当前图像帧的特征F。
OM特征具有非常好的鲁棒性。当图像受到亮度、分辨率和噪声的影响时,OM特征几乎不受影响。
2.3 特征检索视频拷贝检测需要处理大量的数据,因此需要一种高效的特征检索方案。本文使用倒排索引的方法来存储和搜索匹配特征。倒排索引是一种面向单词的索引机制,利用它可以提高检索速度[10]。对于大规模数据,倒排索引是经过大量实践检验的一种高效率的索引方式,能够在很大程度上提高索引的效率。将Harris角点特征与OM特征分别按照特征顺序进行索引,每个特征对应的记录项包括该特征所在的视频文件以及在视频文件中出现的位置。这样,在索引中查找某一特征时,就可以很方便的得到包含该特征的视频及视频中的位置信息。
2.4 基于时序一致性的结果检验
本文采用相关分数矩阵[11]的方法进行帧序列的匹配,以此来排除错误的查询结果,提高检测的准确率。假设输入视频和库内被查询的视频分别有M和N个关键帧,设c(i,j)为输入视频的第i个关键帧与库内被查询视频的第j个关键帧的匹配,d(i,j)为该匹配对的打分,Tm(i)为输入关键帧i的时间戳,Tn(j)为库内被查询关键帧的时间戳。对其中某匹配对c(i,j)计算其时间差:
ΔT=Tn(j)-Tm(i).
(5)
本次实验选取互联网上的1 000个人物、风景和运动场景等主题的视频作为数据库视频,视频时长从2 min至10 min不等,平均时长约5 min。随机选取其中500个视频作为输入视频,并对其进行添加Logo、 光照、分辨率、编码格式等拷贝攻击,作为拷贝视频存于数据库中。接下来分别对本算法的检测精度和时间复杂度进行分析。
图4为本文算法与OM[7]法、 SIFT法[12]的检测结果对比。一个好的视频拷贝检测算法,需要在召回率和准确率两方面都尽可能的高。可以看出,当召回率大于60%时,本文算法准确率优于基于OM和SIFT,其中当召回率为90%时,本文算法的准确率达到了87.3%; 当召回率低于60%时,本文算法准确率略低于OM算法的。由于在实际应用中需要较高的召回率,因此本文算法综合性能最优。
本次实验使用的计算机配置为: Intel Core i5-3230M 2.60 GHz处理器,3.23GB内存,32位Windows XP 操作系统。算法运行平台为Microsoft Visual Studio 2010。表1中给出了本文算法的耗时情况,并与基于OM算法、 SIFT算法进行了对比。
从表1可以看出,OM算法作为基于全局特征的算法,耗时最低; SIFT算法作为基于局部特征的算法,虽然精度有所提高,但是耗时也大大增加。本文算法融合了全局特征和局部特征,并采用级联的方式进行检索,耗时虽然略高于OM算法,但是远远低于SIFT算法。综上所述,本文算法与基于OM与基于SIFT算法相比,在精度和速度上是最优的。
4 结 论本文提出了分块Harris角点和分块亮度顺序的视频拷贝检测算法。该算法结合了局部特征和全局特征,既克服了基于局部特征的高耗时问题,又克服了全局特征的低精度问题。同时,又提出了基于最大信息熵的关键帧提取算法来优化关键帧的选取,并采用了倒排索引的方法提高检索效率。实验表明,本文算法能有效地提高视频拷贝的检测准确性。
[1] | 周志立. 基于内容的视频拷贝检测算法研究[D]. 湖南:湖南大学, 2010.ZHOU Zhili. The Research on Content-based Video Copy Detection Algorithm[D]. Hunan:Hunan university, 2010. (in Chinese) |
[2] | Naphade M R, Yeung M M, Yeo B L. Novel scheme for fast and efficient video sequence matching using compact signatures[C]//Storage and Retrieval for Media Database. San Jose, CA, USA:SPIE, 2000:564-572. |
[3] | Hampapur A, Hyun K H, Bolle R M. Comparison of sequence matching techniques for video copy detection[C]//Proceedings of the Storage and Retrieval for Media Databases. San Jose, CA, USA:SPIE, 2002:194-201. |
[4] | ZHANG Zhijie, ZHANG Ruijie, CAO Chongxiao. Video copy detection based on temporal features of key frames[C]//International Conference on Artificial Intelligence and Education. Dalian, China:IEEE, 2010:627-630. |
[5] | Natsev A, Hill M, Smith J R. Design and evaluation of an effective and efficient video copy detection system[C]//International Conference on Multimedia and Expo. Singapore:IEEE, 2010:1353-1358. |
[6] | Harris C, Stephens M. A combined corner and edge detector[C]//Proceedings of the Fourth Alvey Vision Conference. Manchester, UK, 1988:147-151. |
[7] | Kim C, Vasudev B. Spatiotemporal sequence matching for efficient video copy detection[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2005, 15(1):127-132. |
[8] | 侯卫芹. 基于内容的视频检索关键技术研究[D]. 河北:燕山大学, 2006.HOU Weiqin. Research on the Key Technology of Content-based Video Retrieval[D]. Hebei:Yanshan University, 2006. (in Chinese) |
[9] | Schmid C, Mohr R, Bauckhage C. Evaluation of interest point detectors[J]. International Journal of Computer Vision, 2000, 37(2):151-172. |
[10] | 张博. 基于Lucene倒排索引性能的研究与优化[D]. 昆明:昆明理工大学, 2013.ZHANG Bo. Research on the Optimization of Inverted Index based on Lucene[D]. Kunming:Kunming University, 2013. (in Chinese) |
[11] | Joly A, Buisson C, Frelieot. Content-based copy retrieval using distortion-based probabilistic similarity search[J]. IEEE Transactions on Multimedia, 2007, 9(2):293-306. |
[12] | 张瑞年. 基于SIFT特征的视频拷贝检测技术研究与实现[D]. 河南:解放军信息工程大学, 2012.ZHANG Ruinian. Research and Implementation on Video Copy Detection based on SIFT Features[D]. Henan:PLA Information Engineering University, 2012. |