基于数字签名的高效视频拷贝检测算法研究

李小雨 王琳 王辉淇

（广播科学研究院广播科学研究院 北京邮电大学信息与通信工程学院）

【摘要】 为了解决视频特征提取和大型数据库的快速搜索问题，本文提出了一种新的视频拷贝检测算法。该算法基于视频剪辑的时空特征计算视频签名，通过视频签名的距离来衡量视频之间的相似性。为视频签名数据库建立聚类索引表，提高搜索速度。在大型数据库中查询测试的实验结果表明本文算法对视频拷贝检测有较高查全率和正确率。该算法可以作为一种有效的视频跟踪和检测技术应用于数字广播电视的监控领域。【关键词】 视频拷贝检测视频签名时空分布聚类索引表 1 引言随着互联网技术的快速发展，视频信息的传播和获取变得越来越便利。同时由于网络所具有的共享性和开放性，致使数字视频经常遭到恶意攻击、非法侵犯版权和信息篡改。视频拷贝检测作为一种有效的视频跟踪和检测技术，它能够有效地检测出视频内容是否被篡改、被盗版，可以广泛地应用于数字广播电视的监控领域。在基于内容的视频检索（CBVR，Content Based Video Retrieval）领域已经广泛展开了有效的视频相似性度量和高效的视频拷贝检测（VCD，Video Copy Detection）算法研究。视频拷贝检测包括两方面的技术：特征提取和搜索方法。在过去的十年里，研究者们已经提出了大量的图像和视频特征提取算法，例如色矩^[1]，DCT^[2]，差分图像的投影^[3]和SIFT^[4]等。为了提高计算效率，降维法已普遍用于高维特征空间。典型统计模型有混合高斯模型^[5]和ViSig模型^[6]。然而，这些方法计算效率较低，针对海量的视频数据效率并不高。在大量的数据库中建立一个高效的索引是视频拷贝检测的另一个关键问题。基于局部敏感的哈希索引算法（LSH，Locality Sensitive Hashing）^[7]已经被广泛用于高维空间近似最近邻搜索。ViTris^[8]算法可用于视频摘要和构建最佳B+树索引。金字塔技术^[9]将D维的数据空间划分为二维金字塔，然后将每个金字塔切分成几个片段，每一个片段组成一个数据页。现有的LSH技术，通常含有数百个哈希表，对于可扩展的分布式应用和快速查询的大型数据库都并非十分高效。本文提出了一种新的基于视频指纹的高效视频拷贝检测算法，该算法设计了一种简单的基于时空域特征的视频签名。视频剪辑间的相似度通过视频签名的距离来度量。根据聚类索引表（CIT，Clustering Index Table）设计了一种高效的搜索方法。实验结果表明本文提出的算法应用于大量视频数据库场景中具有较好的效果，适用于数字广播电视的监控领域。 2 基于时空域的视频签名一般视频签名是基于图像特征提取，考虑到计算效率，一些低层的特征例如颜色、纹理、边缘通常被作为图像签名。文献^[10]中验证了将YCbCr直方图是一种有效的视频签名，它能够为视频拷贝检测提供有用的信息。由于网络中视频总数量是飞速增长的，考虑到计算效率，数字签名设计应尽可能的简单。在本方案中，将YCbCr的平均值加权求和的结果作为图像签名S，如下式所示。

其中M和N分别是图像的宽度和高度。Yij、Cbij和Crij分别表示图像每一个像素的Y、Cb和Cr分量。实验中所使用的测试序列都是4:2:0采样格式，所以Cb和Cr分量尺寸只有Y分量的1/4。基于空间统计特性的平均值能够提供图像的例如颜色、亮度等重要信息。在图像签名中，设置权重是为了放大Y、Cb和Cr分量的差异。根据人类视觉特性，人们对于红色最为敏感，因此Cr分量权重设置的最大。在本方案中，采用两个时空分布（STD，Spatial Temporal Distribution）统计特性作为视频签名：视频序列的均值和方差，如下式所示。

其中，Si是图像签名，L代表视频序列总帧数。根据时空分布特征，复制的视频通常具有相近的图像签名和时空变化。视频的相似度与图像帧的特征、镜头长度及其变化有关，根据人类视觉特性，拍摄时间对视频相似度影响不大。基于图像签名的STD的统计特性可以表征视频的相似性，可以用作视频签名。根据本文提出的方法计算出的图像签名在坐标轴上是相近的。因此，本文提出的方法是一种统计特征提取策略，能够有效的用于视频拷贝检测。 3 视频拷贝检测由于视频签名是基于STD的统计特性，相似度测量转变为计算视频签名的距离。给定两个视频序列ν1和ν2，它们的视频签名分别是(Vm1,Vd1)和(Vm2,Vd2)。这两个视频的相似度定义如下。

为了简化相似度搜索，本文提出聚类索引表（CIT，Clustering Index Table）。索引表根据视频签名的数值除以10，具有近似视频签名的视频剪辑存储到同一张索引表中。CIT有五个属性：视频剪辑文件名、高度、宽度、均值Vm和方差Vd。视频签名Vm提供的是STD的普通统计特性，用于索引聚类；Vd表示视频图像帧的时空变化，用作距离度量的一部分。对于视频拷贝检测，视频可以分为两类：在数据库中的视频和新视频。对于前者，其视频签名已经计算过了。对于后者，需要计算其视频签名并添加到数据库中。给出一个待查询的视频剪辑，先计算出其视频签名，然后再去相应的索引表中进行查询。用这种方法，搜索引擎是在有界的范围内处理每一个视频剪辑，从而避免去搜索大量不相似的视频，搜索效率可以得到较大的提升。由于拷贝的视频剪辑是有限的，利用CIT搜索视频剪辑满足VCD要求。对于完整视频拷贝检测，搜索表的索引是由以下规则决定：如果余数小于5，并且q-1或者q+1存在，搜索索引为q-1和q。否则索引为q和q+1，如下式所示。根据四舍五入原则找到最相近的视频签名，从而找到视频复制源。

图1为本文提出的VCD算法流程图和系统框架图。在特征提取阶段，根据图像签名计算在数据库中的每一个视频剪辑的视频签名。然后，根据视频签名聚类生成索引表，即CIT。在VCD系统中，搜索引擎在相应的CIT中处理每一个视频剪辑，并且返回结果。

(a) 特征提取和索引计算流程图

(b) VCD系统结构图

图1VCD算法流程图和系统

4 实验结果本文采用Matlab7.14对算法进行仿真实验。实验过程中，所采用的计算机为Intel Core i5 2.80GHz，内存为2.99G。视频数据库中含有600个视频剪辑。为了评价检测的准确性，实验过程中采用了查全率（RR，Recall Rate）和正确率（PR，Precision Rate）两个指标，其定义分别如式（6）、（7）所示。拷贝视频剪辑是通过原视频剪辑经过时空变换后产生的。在实验中，使用的时空变换主要有：（1）亮度增强；（2）添加高斯噪声；（3）添加椒盐噪声；（4）旋转；（5）缩放尺寸；（6）翻转；（7）高斯模糊；（8）帧裁剪。变换对比图如图2所示。

图2 时空变换结果对比图

实验过程中，所采用的原始视频尺寸为1920x800。图2（b）亮度增强3%；（c）添加的高斯噪声均值为0，方差为0.005；（d）添加的椒盐噪声其噪声密度为0.01；（d）旋转变换围绕图像中心旋转2个像素；（f）高斯模糊降析函数模板尺寸为7x7，标准差为5像素；（g）视频尺寸缩小为1800x800；（h）对视频剪辑进行水平翻转；（i）剪切5%，裁剪后视频剪辑尺寸为1870x780。实验结果如下表Ⅰ所示，该表中列出了上述8中变换下VCD的查全率和正确率。

表1不同变化下VCD结果

根据表1实验结果可以看出，经过不同的时空变换后，运用本文算法进行视频拷贝检测，其结果具有较高的查全率和正确率。图3所示为随着视频剪辑数增加，VCD用时曲线。从图中曲线可以看出随着视频剪辑数的增加，VCD用时增长并不是十分迅速。适用于大型数据库中进行视频拷贝检测。

图3 视频剪辑数增加VCD用时曲线

5 总结本文提出了一种新的视频拷贝检测算法，该算法基于视频剪辑的时空特征提取视频签名，通过计算视频签名的距离度量视频剪辑之间的相似性。为视频签名数据库建立聚类索引表，能够提高搜索速度。实验结果表明，本文算法对视频拷贝检测有较高的查全率和正确率。可以用于在大型数据库中进行视频拷贝检测，适用于数字广播电视的监控领域。 参考文献:XYang, QTian, ECChang. A color fingerprint of video shot for content identification[J]. Proc. of the 12th annual ACM int'l conf. on Multimedia, 2004:276-279.Gros X N A P. Detecting repeats for video structuring[J]. Multimedia Tools and Applications, 2008, 38:233-252.CBauer R R A. Content-based Video Signatures based on Projections of Difference Images[J]. Proc. of IEEE 9th Workshop on Multimedia Signal Processing, 2007:341-344.Chum O, Philbin J, Isard M, etal. Scalable Near Identical Image and Shot Detection[J]. Proc. of the 6th ACM int'l conf. on Image and video retrieval, 2007:549-556.Vasconcelos N. On the complexity of probabilistic image retrieval[J]. Proc. Eighth IEEE Int'l Conf. on Computer Vision, 2001, 2:400-407.Zakhor S C A A. Efficient video similarity measurement with video signature[J]. IEEE Trans. on Circuits and Systems for Video Technology, 2003, 13:59-74.Lv Q, Josephson W, Wang Z, etal. Multi-probe LSH: efficient indexing for high-dimensional similarity search[J]. Proc. of the 33rd int'l conf. on Very Large Data Bases, 2007:950-961.Shen H, Zhou B O A X. Towards Effective Indexing for Very Large Video Sequence Database[J]. Proc. of SIGMOD, 2005:730-741.Berchtold S, C. B?ohm and H.-P. Kriegel. The pyramid-technique: Towards breaking the curse of dimensionality[J]. Proc. of SIGMOD, 1998:142-153.HT S, BCO, Zhou X. Towards Effective Indexing for Very Large Video Sequence Database[J]. Proc. of the ACM SIGMOD Int'l Conf. on Management of Data, 2005:730-741. 编辑：中国新闻技术工作者联合会