张兴忠,李 皓,张三义

(太原理工大学 计算机科学与技术学院,太原 030024)

基于关键帧多特征融合的视频拷贝检测

张兴忠,李 皓,张三义

(太原理工大学 计算机科学与技术学院,太原 030024)

针对视频拷贝检测中检索速度问题,提出一种基于关键帧多特征融合的类局部敏感哈希索引方法,将存在拷贝片段的视频映射到同一个哈希桶中,减少检索的范围,达到提高检索速度的目的。该算法首先对视频进行镜头分割提取关键帧,为了提高检测精度,分别提取了灰度序全局特征、基于关键点的希尔伯特特征、ORB(Oriented FAST and Rotated BRIEF)局部特征,综合利用全局特征和局部特征两者各自的优势;然后根据视频关键帧序列建立了类局部敏感哈希索引,利用建立好的索引获得拷贝检测结果。实验结果表明,该方法在保证检测精度的同时,速度上也有很大提升,具有重要的应用价值。

视频拷贝检测;关键帧;ORB;类局部敏感哈希;关键点希尔伯特

随着信息化社会的高速发展,多媒体尤其是图像和视频已经渗透到了我们的日常生活中,如何对图像、视频进行版权保护成为了一项重要的研究课题,本文研究视频版权保护中,如何在保证高检测精度的前提下实现快速视频拷贝检测。

视频拷贝检测技术可以用于检测视频是否存在拷贝或者重复片段,是数字视频版权保护的关键支撑技术。一般地,视频拷贝检测技术是从提取视频帧的内容来实现拷贝检测,通过比较视频帧内容的相似程度来判断两个视频是否被篡改。

目前基于内容的视频拷贝检测技术[1-2]是基于视频帧特征的方法来实现。全局特征检索方法[1]可以实现快速的拷贝检测且检索效果不错,但是对于复杂性的拷贝效果差。局部特征检索方法[2]可以检测出多种拷贝,但是由于局部特征存在特征描述点较多的问题,匹配速度慢。

笔者提出一种基于关键帧多特征融合的视频索引方法。该方法分别提取了灰度序全局特征、基于关键点的希尔伯特特征和ORB局部特征,综合利用他们各自的特点,同时借鉴局部敏感哈希的思想,将相似的视频即存在拷贝视频片段的视频放到同一个哈希桶中,减少检索的范围,从而达到在保证检索精度的同时,实现快速检索的目的。

1 相关研究

基于内容的视频拷贝检测技术主要包括基于哈希的方法、基于视觉词袋的方法以及降维方法。局部敏感哈希(Local Sensitive Hashing, LSH)算法[3]是一种有效的近似相似性查询技术,通过哈希函数把相似的视频映射到同一个哈希桶中,可以有效减少检索范围并加快检索。文献[4]引用了局部敏感哈希的方法用于网络视频重复检测,加快了检索速度。基于视觉词袋(Bag of Words)[5]的方法通过k-means聚类的方法统计视频关键帧库中出现的所有特征,相近的特征归为一类,将聚类中心作为词袋。利用视觉词袋量化视频关键帧特征,采用词频或直方图来表示图像。除此之外,还有一些降维方法,如文献[6-7]提出采用流行学习中的局部线性嵌入降维的方法降低视频关键帧特征的维度来加快检索速度。

2 视频关键帧及其特征提取

视频关键帧提取采用基于镜头的关键帧提取策略,采用的是文献[9]中基于相邻帧的灰度直方图的方法来提取关键帧,在此基础上添加了去重操作来保证关键帧的精确性。本节主要介绍本文所采用的三种视频关键帧特征的提取技术。

2.1 空间灰度序特征

空间灰度序特征是一种具有排序性质的全局特征。其提取过程首先将视频帧图像分割为n×n个等同的图像块,文中n取3;然后分别计算各图像块的灰度平均值;最后对求得的各个图像块的灰度平均值进行排序,得到的排序编码作为该视频帧图像的灰度序特征。

2.2 基于关键点的希尔伯特特征

希尔伯特曲线(Hilbert Curve)是由德国数学家David Hilbert在1891年提出,它是一种十分神奇的曲线,该曲线是一种能填充满一个平面正方形的分形曲线,其特点是将一个平面正方形平均划分为n×n的均匀小分块,每个分块是一个小正方形,从正方形四个角的任意一个小分块开始,勾画一条曲线充满平面正方形的每个正方形小分块,如图1所示是一个划分为4×4均匀小分块的希尔伯特曲线示意图。

图1 基于关键点的希尔伯特特征

将希尔伯特曲线引入到视频关键帧的特征提取中,把视频关键帧均匀划分,勾勒一条希尔伯特曲线填充满整个视频关键帧的每个小分块,就可以得到一个视频关键帧的希尔伯特全局特征。

局部特征提取的视频关键帧的局部关键点位置均为可标识该视频关键帧的关键像素点,它们可以有效地代表该视频关键帧。兼顾局部关键点的重要性和希尔伯特曲线的全局完整性笔者提出了基于关键点的希尔伯特特征。

基于关键点的希尔伯特特征的提取流程如下所示:

1) 利用ORB特征提取策略获取视频关键帧的局部关键点位置;

2) 将视频关键帧划分为4×4均匀大小的块,统计各分块中局部关键点的个数和对应的灰度值,并计算出各分块的平均灰度值,如图1中所示计算左图视频关键帧的平均灰度值为右图所示;

3) 对各个分块的平均灰度值采用希尔伯特曲线进行串联,如图1中右图的正方形所示,从左下角小正方形分块开始,用一条不间断且能通过所有均匀小正方形分块的曲线连接起来;

4) 勾画出希尔伯特曲线后,视频关键帧的希尔伯特特征采用平均灰度值可以表示为一个16位的序列,以图1为例该视频关键帧形成的16位的平均灰度值序列则表示为{186,0,78,182,0,0,133,129,110,120,0,0,0,171,0,121},对该灰度值序列采用如下策略转换为二值特征序列。记平均灰度值序列为a[i],0≤i<16,将新生成的二值特征序列记为b[j],0≤j<15,那么序列b的计算过程如式(1)所示,

(1)

得到最终的15位的二值希尔伯特特征为100 100 110 100 010。

2.3 ORB特征

ORB特征是对二值特征描述符BRIEF的改进,它克服了BRIEF特征不具备旋转不变性和对噪音敏感的缺陷。ORB特征提取过程如下。

1) 快速关键点提取。首先采用FAST-9方法检测视频帧的关键点,然后采用Harris角检测方法来对FAST关键点进行排序,选取排序最高的n个关键点;提取视频帧的尺度金字塔,并对金字塔的每层提取FAST特征;最后定位强度质心。

2) 基于旋转的BRIEF(rBRIEF)。BRIEF是从视频帧块的一系列二值强度测试集中构建二值特征描述符。对于一个平滑的图像块p,一个二值测试τ定义如公式(2)所示:

(2)

式中:p(x)是在点x处的p的强度。

ORB特征采用贪婪搜索法从所有可能的二值测试集中寻找既有高变化性(平均值接近0.5)又不相关的特征,直至获得256个测试集。这个算法得到一组不相关的平均值接近0.5的测试集结果,这个结果叫做基于旋转的BRIEF,简称rBRIEF。

3 基于关键帧多特征融合的视频拷贝检测

3.1 类局部敏感哈希索引的建立

类局部敏感哈希索引的示意图如图2所示。初始时哈希桶大小为空,每一个哈希桶有一个代表视频,即该哈希桶中存储的是该代表视频的拷贝视频。每个哈希桶内部包含n个拷贝视频集,数目n是代表视频的关键帧序列数目,每个视频关键帧的视频集合是由存在该视频关键帧的拷贝片段或重复片段的视频集组成。

图2 类局部敏感哈希索引

类局部敏感哈希索引的建立流程图如图3所示,建立过程如下:

1) 输入一个视频,如果哈希桶为空,则将该视频放入哈希桶1,并将该视频作为哈希桶的代表视频,建立该视频关键帧序列的拷贝视频集合;如果哈希桶不为空,则转入步骤2进行处理;

2) 将输入视频遍历每个哈希桶,计算与每个哈希桶代表视频的相似度,如果与某哈希桶代表视频相似,则采用基于公共视频帧序列[9]的方法,计算出相似的视频关键帧序列,放入对应的视频关键帧的拷贝视频集中;

3) 如果输入视频未执行,则继续执行步骤1和2,直到所有视频遍历完毕;

4) 所有视频遍历完成后,还需要进行整合处理。因为一些哈希桶代表视频的拷贝视频集仅有一个视频,说明属于特例,不存在该视频的拷贝,在此处的处理方法是将哈希桶中仅有一个视频的哈希桶整合为一个哈希桶,剩下的哈希桶保持不变。

图3 索引建立流程图

3.2 检索流程

输入一个查询视频,遍历哈希桶计算与每一个哈希桶代表视频的相似度,如果与某代表视频相似,则说明该哈希桶中存在查询视频的拷贝视频,采用基于公共视频帧的方法计算出代表视频中存在拷贝片段的关键帧序列,融合公共视频关键帧对应的拷贝视频集,添加到视频拷贝结果集合。继续遍历哈希桶直至遍历完毕,将每个哈希桶的结果去重求并集得到最终的视频拷贝检测结果。

4 实验结果及分析

本文实验均在3.4 GHz, 4G内存,Windows 7操作系统下用C++语言实现,采用OpenCV2.4.8标准库。数据集选取自CC_WEB_VIDEO[10]数据集,选用8组视频进行测试,每组视频均存在各种拷贝。

用准确率、召回率和检索时间作为评测指标。

1) 准确率Precision的计算公式如式(3)所示,

Precision=QC/PResult .

(3)

式中:QC表示检索结果中包含的正确的检索结果数;PResult表示检索结果数目。

2)召回率Recall的计算公式如式(4)所示,

Recall=QC/RResult .

(4)

式中:QC表示检索结果中正确的检索结果数;RResult表示检索集中总共的准确结果数。

3) 检索时间。完成一次检索消耗的时间即从开始检索到检索结束耗费的时间。

图4 召回率比较

为了验证本文提出的方法的有效性,与文献[1]中灰度序的方法和bag-of-words检索方法(下面简述为BOW-300)进行了比较。采用k-means聚类算法,字典数目选为300,匹配采用基于动态规划方法。图4、图5和表1为采用三种方法对召回率、准确率和检索时间比较。

图5 准确率比较

从图4召回率的结果可以看出,文献[1]灰度序方法和BOW-300的召回率可以保持很高的水平,多组实验结果均为100%,比本文的方法要好,但是从图5准确率的结果来看,虽然灰度序的方法和BOW-300的方法召回率很高,但是准确率很低,并不如本文的方法。准确率和召回率是两个折衷的评判标准,两者均保持较高水平,检索结果才更有说服力,本文的方法在召回率和准确率两个指标上表现均稳定,保证了较高的检索精度。

从表1的结果来看,本文的方法与文献[1]灰度序全局特征的方法相比慢了点,这是由于灰度序是一种全局特征方法,特征维度低,故而检索速度快,但是文献[1]灰度序方法牺牲了精度,BOW-300的方法时间耗费较长是由于虽然通过聚类方法减少了特征维数,但是相似度的计算和匹配过程仍然耗费了很多时间。本文的方法平均检索时间相对其他两种方法是一个折衷的提升,由于采用了基于关键帧多特征融合的拷贝检测算法,以哈希桶为检索单元,在保证检索精度的同时,缩小检索范围,检索时间获得较大提升。

表1 检索时间的比较 s

5 结论

本文提出的基于关键帧多特征融合的视频拷贝检测方法即利用灰度序、基于关键点的希尔伯特特征和ORB特征建立的类局部敏感哈希索引,在保证高召回率和准确率的同时,在检索时间上获得了较大提升。今后的研究考虑为一种鲁棒的视频关键帧特征建立快速的索引方法,快速有效地检测到多种拷贝攻击;另一条思路围绕时空特征,发掘出一种鲁棒的时空特征来表示视频片段,依此来检索视频拷贝片段。

[1] Hua X S,Chen X,Zhang H J.Robust video signature based on ordinal measure[C]∥Image Processing,2004. ICIP′04.2004 International Conference on.IEEE,2004,1:685-688.

[2] Ates T K,Esen E,Saracoglu A,et al.Content based video copy detection with local descriptors[C]∥Signal Processing and Communications Applications Conference (SIU),2010 IEEE 18th.IEEE,2010:49-52.

[3] Lv Q,Josephson W,Wang Z,et al.Multi-probe LSH:efficient indexing for high-dimensional similarity search[C]∥Proceedings of the 33rd international conference on Very large data bases.VLDB Endowment,2007:950-961.

[4] 王洪峰,刘辛.基于位置敏感哈希的网络视频重复检测[J].计算机应用研究,2012,29(5):1954-1958.

[5] Nowak E,Jurie F,Triggs B.Sampling strategies for bag-of-features image classification[M]∥Computer Vision-ECCV 2006.Springer Berlin Heidelberg,2006:490-503.

[6] 聂秀山,刘琚,孙建德,等.基于局部线性嵌入的视频拷贝检测方法[J].电子与信息学报,2011,33(5):1030-1034.

[7] 聂秀山.基于鲁棒哈希的视频拷贝检测技术研究[D].山东大学,2011.

[8] Rublee E,Rabaud V,Konolige K.et al.ORB:an efficient alternative to SIFT or SURF[C].2011,International Conference on Computer Vision(ICCV),2564-2571.

[9] 张三义,张兴忠,郝晓燕.基于ORB和灰度序特征的视频拷贝检测[J].计算机应用研究,2014,31(10):3113-3116.

[10] Xiao Wu,Alexander G.Hauptmann and chong-wah ngo practical elimination of near-duplicates from web video search[C].ACM International Conference on Multimedia (ACM MM’07),Augsburg, Germany,Sep.2007:218-227.

(编辑：朱 倩)

Video Copy Detection Based on Key Frame Multi-feature Fusion

ZHANG Xingzhong,LI Hao,ZHANG Sanyi

(CollegeofComputerScienceandTechnology,TaiyuanUniversityofTechnology,Taiyuan030024,China)

Retrieval speed is an important issue in video copy detection. This paper proposed a fast video copy detection method, which uses a local sensitive hashing index to achive fast retrieval by mapping videos with similar clips into the same buckets, and combines multi-features of key frames to achieve high accuracy. To improve retrieval accuracy, the method extracts key frames by using shot segmentation techniques, and then obtains the Hilbert feature based on key points, ordinal measure feature and ORB (Oriented FAST and Rotated BRIEF) feature from key frames. This allows the method make full use of both local features and global features. The hash index is built by hash the combined features. Experimental results show that this proposed method not only achieves high precision and recall rate, but also has high spead.

video copy detection;key-frames;oriented FAST and Rotated BRIEF (ORB);local sensitive hashing;hilbert feature based on key points

1007-9432(2015)05-0566-05

2015-05-13

国家科技支撑项目子课题:(2012BAH04F02-2)；教育部归国留学人员科研启动基金(2010-1174)；人社部留学人员科技活动项目(2011-508)；山西省国际科技合作计划基金资助项目：中美、中加合作云计算环境下网站系统架构和数据库系统建模技术研究(2012081034-2)

张兴忠(1964-)，男，山西汾阳人，副教授，主要研究方向为嵌入式系统、软件工程、模式识别等，(E-mail)1659898176@qq.com

TP391.41

A

10.16355/j.cnki.issn1007-9432tyut.2015.05.017