Delaunay三角剖分下的视频指纹算法

李晓雨,聂秀山,2,董 飞,尹义龙,2

1(山东财经大学 计算机科学与技术学院,济南 250014)

2(山东大学 计算机科学与技术学院,济南 250014)

3(山东师范大学 传媒学院,济南 250014)

1 引 言

近年来,随着信息技术和通信技术的发展,手机、平板电脑等移动设备得以迅速普及,用户可以随时随地的拍摄视频,并将视频上传到互联网,这就使得网络上视频的数量以几何式的速度激增,在这种情况下,互联网上经常出现盗用他人视频、未经作者允许随意再次上传视频等不道德、不合法的行为发生.因此,在面对这些海量视频时,如何保护原作者版权,如何监管视频非法拷贝,如何过滤重复视频等一系列的问题成为亟待解决的难题.为解决这一系列的问题,研究者提出了视频指纹这一概念.将视频指纹类比于人的指纹,人的指纹可以唯一的代表一个人,并且可以通过指纹来追溯到特定的人,视频指纹为视频内容的标识,是从视频内容中提取的视频特征表示,可以唯一代表相应视频内容.视频服务管理机构可以通过视频指纹来追溯某一特定视频,也可以通过比对视频指纹来判断视频内容是否相似,进而为解决视频非法拷贝和重复视频检索提供技术支撑.因此,对视频指纹技术的研究具有较大的应用价值.

自视频指纹的概念提出以来,视频指纹相关技术的研究取得了很多成果,现有的视频指纹算法大体可分为三类:

第一类是基于空域的方法,这类方法主要以视频中每一帧的空域属性为基础,使用亮度、灰度等鲁棒性较好、复杂度较低的特征来生成视频指纹.Oostveen[1]等学者将视频帧分块,以各亮度块的偏微分特征作为视频指纹.Lee[2]等学者将视频帧分块,而后计算每块的亮度梯度生成视频指纹.

第二类是基于时域的方法,这类方法主要使用视频相邻帧在时间上的关系来生成视频指纹.Chen[3]提出了一种基于时域顺序的视频指纹方案,对视频帧分块,求每一块的像素均值,并通过定义一个时域窗口,对窗口内每一帧相同位置的块进行排序,从而构造视频指纹.Radharkrishan[4]提出利用帧与帧之间亮度差分生成视频指纹的方法.

第三类是基于变换域的方法,这类方法主要使用视频帧在变换域中的属性生成视频指纹.Cosku[5]等通过三维离散余弦(3D-DCT)变换,将视频变换到变换域,并利用频率特征生成视频指纹.其他研究者还提出了诸如基于奇异值分解[6]、极坐标傅里叶变换[7]等变换域技术生成视频指纹的方法.

以上的三类方法都各有优劣.基于空域的视频指纹算法所采用的空域特征在全局几何变换，如旋转、放射变换等情况下具有较好的鲁棒性,且复杂度较低,但视频的帧与帧之间顺序排列、密切相关,当改变帧与帧之间的顺序时就会出现较大的误差,使视频指纹性能大幅下降.基于时域的视频指纹算法能够体现视频帧与帧之间的相互联系,在对比度变化、添加噪声等基于空域的视频算法表现较弱的视频攻击下具有良好的鲁棒性,但由此类方法生成的视频指纹内部分量之间高度相关,对于局部信息非常敏感,一个分块内容的改变可能导致视频指纹的大幅变动,使得算法性能下降.基于变换域的视频指纹算法所使用的的频率特征能够在旋转、裁剪等几何变换中保持稳定,具有良好的鲁棒性,但由于此类方法使用的傅里叶变换、小波变换等变换域技术常具有较高的复杂性,对实际应用不利.随着对视频指纹相关技术研究的深入,研究者不再单一的使用某一种特征来生成视频指纹,而是根据实际需求,结合不同类型的特征来生成性能更好的视频指纹[8-10].Lee[11]等提出了一种将空间域与变换域结合的方法,该方法首先将视频帧分块,计算各块梯度方向质心(CGO),然后根据双对称增强算法和滤波量化器生成视频指纹.

一般来说,鲁棒性是评价一个视频指纹算法优劣的重要标准.在一定数量的视频中识别出完全相同的、未加修改的视频是比较容易的.但是,当视频经历了亮度、角度、分辨率等参数的变化,或是噪声添加、旋转、平移等操作,导致视频在视觉上出现一定程度的改变后就难以准确的与原始视频进行匹配.因此,视频指纹在经历以上的修改或攻击后的鲁棒性就变得非常重要.为增强视频指纹的鲁棒性,本文充分利用视频的时空信息,从空域特征入手,再与时域特征相结合,进而生成视频指纹.具体来说,在空域方面,对视频帧进行分块,将每一块的灰度均值作为特征描述值.在时域方面,将顺序排列的视频帧的每一块看做一个带有时间序列标志的三维特征点,并对这些特征点的集合进行Delaunay三角剖分.三角剖分后形成一系列相关四面体,将这些四面体的特征值均值作为视频指纹,使视频指纹兼具空域性与时域性.同时由于Delaunay三角剖分具有较好的稳定性,使视频指纹的鲁棒性也得以加强.

本文的主要贡献在于创新性的利用Delaunay三角剖分构建空间四面体,来挖掘视频的时空特征,进而生成视频指纹.Delaunay三角剖分在部分特征点遭受扰动的情况下,剖分后得到的四面体仍具有较好的稳定性,因此,本文算法与现有基于时空信息的视频指纹算法相比,在充分利用视频时空信息的同时,又具有较强的鲁棒性.

2 Delaunay三角剖分下的视频指纹算法

本文算法的框架图如图1所示,主要分为视频预处理、特征点提取,Delaunay三角剖分和视频指纹生成四个部分.首先对视频进行预处理,然后对每一帧进行分块处理,每一块作为一个特征点,每一块的灰度均值作为特征描述值,其次对特征点的集合进行Delaunay三角剖分,得到一个四面体集合,该集合内的四面体不仅包含了同一帧内特征点的相互关联信息,还包含了不同帧之间特征点的相互关联信息,最后把四面体四个顶点的灰度均值作为视频指纹.

图1 本文算法框架图Fig.1 Algorithm frame

2.1 预处理

在生成视频指纹的过程中,由于视频的帧数、分辨率、帧频率等原始数据参数的不同,可能会使得生成视频指纹的长度、规格各不相同,会对视频指纹之间的匹配产生影响,使检测的准确率下降.为了避免这种影响,本文首先要对视频进行预处理操作,使数据库中视频的物理参数在生成视频指纹之前就相互统一.预处理并没有改变视频的内容,因此预处理在视频指纹算法中有着广泛的应用.本文在对视频进行预处理时,首先对视频片段进行均匀采样,采样标准为64帧,然后把采样后的视频帧分辨率统一设置为64×64.

2.2 特征点提取

特征点提取是从视频中提取含有视频帧重要特征的点,特征点对图像畸变具有一定的鲁棒性,在图像、视频匹配中被广泛应用.

为提高算法效率,本文通过像素分块的方式构造特征点,具体做法是:在空域上,对按照标准采样、统一分辨率的视频帧时间序列中的每一个视频帧,按顺序进行分块处理,将每个视频帧均等分块,然后把每一块看做一个特征点,特征点按行的顺序依次排列,分块及提取特征点的方式如图2所示.按照此方法,对不同视频提取的特征点个数相同.

图2 特征点提取Fig.2 Extract feature points

得到视频帧的特征点后,把每个特征点的坐标记为一个三维向量(x,y,z).x代表所在位置的行序号,y代表所在位置的列序号,z代表该特征点所属的视频帧在整个视频帧时间序列中的序号,表示视频帧的时间信息.集合B表示所有特征点的集合:B={B1,B2,…,Bn}.

例如,特征点B1的三维坐标为(1,1,1),则其表示视频帧时间序列中第一帧的第一行、第一列的特征点.

然后计算每一个分块的灰度平均值,并将其作为对应特征点的特征描述值,集合G表示特征值的集合:G={G1,G2,…,Gn}.

2.3 Delaunay三角剖分

通过视频帧分块获取的特征点,其特征描述值仅包含对应分块内的灰度信息,即空间信息,而包含时间信息的视频特征点的坐标尚未得到利用.为了构造既包含空间信息又包含时间信息的视频指纹,就需要利用视频特征点的坐标.将特征点集合看作视频空间中的散点集合,通过Delaunay三角剖分[12],建立视频帧与帧之间的特征点的联系,这种联系能够体现视频的时间信息.

图3 Delaunay三角剖分Fig.3 Delaunay triangulation

Delaunay三角剖分的目的在于将空间内有限的散点集合剖分成互不交叉的、形状均匀的三角网格,如图3所示.这就使得Delaunay三角剖分的结果具有两个特点:一是对同一个散点集进行Delaunay三角剖分后得到的三角网格是唯一的;二是Delaunay三角剖分后形成的三角网格中的每一个三角形的最小角最大,即避免出现狭长的三角形.第一个特点能够在视频特征点之间建立唯一的相互联系,不随重新进行Delaunay三角剖分而改变相互联系.第二个特点能在视频特征点之间均匀地建立相互联系,避免了在极远点之间,即携带时间信息差异较大的点之间建立相互联系.

图4 特征点变动前后Delaunay三角剖分对比Fig.4 Contrast of Delaunay triangulation with feature point changing

同时,Delaunay三角剖分具有较强的鲁棒性.对于一个已知的散点集来说,当改变一个点或部分点的位置之后再次进行Delaunay三角剖分时,除了包含发生变动点的三角网格产生变化外,其他的三角网格保持不变,如图4 所示.视频易受噪声、对比度、旋转等多种因素影响,使部分特征点发生变化,Delaunay三角剖分较强的鲁棒性可以将部分特征点变动引起的整体变动降低,这是这一技术被应用于视频指纹生成的主要原因.

以上特性对于三维的散点集来说同样成立.进行三维的Delaunay三角剖分后得到的三角网格,构成了空间中均匀的四面体,如图5所示.因此,对本文提取的、携带时间信息的三维特征点坐标集合进行Delaunay三角剖分,得到一系列互不交叉、形状均匀的四面体.四面体把视频帧内和帧间的特征点通过四面体的边相互连接起来,一个四面体由视频帧的帧内和帧间特征点共同确定.因此,在一个四面体上,帧内和帧间的关联关系都得到了充分的体现,空域和时域上的信息都得到了有效的表达.

图5 三维Delaunay三角剖分Fig.5 3-D Delaunay triangulation

2.4 视频指纹生成

视频指纹是从视频中提取的、能够标识视频内容,并唯一代表视频的标志.本文希望通过Delaunay三角剖分后得到的一系列既包含时间信息又包含空间信息的空间四面体,来生成兼具时域特征与空域特征的视频指纹.

构成四面体的特征点的特征值为G,四面体的特征值由构成一个四面体的四个特征点的特征值决定,则四面体的特征值定义如下:

(1)

集合T表示Delaunay三角剖分后的所有四面体的特征值,集合T即为视频指纹.

3 实验结果与分析

3.1 实验设定及评价标准

本实验所用视频来源于公开视频数据库CC_WEB_VIDEO (vireo.cs.cityu.edu.hk/ webvideo),该数据库包含体育、新闻、动画等不同类型的视频,视频时长在20秒到20分钟之间.在此数据库的基础上,对数据库中视频分别进行旋转变换、仿射变换、对比度变换、添加图标变换、添加噪声变换,以及综合使用添加图标、仿射变换和改变对比度这三种视频变换方法进行组合变换,从而使一个视频衍生出6种变换后的视频,各种攻击变化的效果图如图6所示.

本文采用漏报概率和误报概率构成的受试者工作特征曲线(ROC曲线)作为评价标准.漏报概率为未能检测出的真实拷贝个数和总拷贝个数的比值.误报概率为检测出的虚假拷贝个数与检测出的拷贝个数的比值.

设总拷贝个数为S,未检测出的真实拷贝个数为N,则漏报概率定义如下:

(2)

设检测出的拷贝个数为R,检测出的虚假拷贝个数为F,则误报概率定义如下:

(3)

为验证本文算法的鲁棒性,将本文提出的算法与近年来较为流行的梯度方向质心(CGO)算法[13]、近似低秩张量(LRTA)算法[14]进行比较,本文实验共分为6组:

第一组实验是对原始视频进行旋转变换,设定旋转参数为视频帧逆时针旋转10度.主要目的是为了检验在旋转攻击下,算法的鲁棒性.

图6 视频帧攻击效果Fig.6 Effect of video frame attack

图7 实验结果Fig.7 Experimental result

第二组实验是对原始视频进行仿射变换,设仿射变换矩阵为[1 0.1 0;0.1 1 0;0 0 1].主要目的是为了检验在仿射变换攻击下算法的鲁棒性.

第三组实验是对原始视频进行对比度变换,设定对比度变换参数为([0.2,0.9],[0,1]),即对比度在0.2以下和对比度0.9以上的值被去除,剩余的值映射到0-1之间.主要目的是为了检验在对比度攻击下算法的鲁棒性.

第四组实验是对原始视频添加分辨率为20×20的图标.主要目的是为了检验在添加图标攻击下算法的鲁棒性.

第五组实验是对原始视频添加均值为0、方差为0.005的高斯噪声,主要目的是为了检验在噪声攻击下算法的鲁棒性.

第六组实验是对原始视频进行包括对比度、添加图标、仿射变换在内的组合变换.对比度变换参数为([0.2,0.9],[0,1]),添加图标的分辨率为20×20,仿射变换矩阵为[1 0.1 0;0.1 1 0;0 0 1].主要目的是为了检验在组合攻击下算法的鲁棒性.

3.2 实验结果与分析

依次进行上述6组实验,并把变换后视频与原始视频的视频指纹进行匹配,绘制ROC曲线.ROC曲线纵坐标表示漏报概率,横坐标表示误报概率.结果如图7所示.

根据这6组实验的结果可以看出,在旋转变换、仿射变换、对比度变换、添加图标这四种视频攻击下,本文提出算法的ROC曲线位于CGO和LRTA算法的左下方如图7(a)-图7(d),说明在以上四种攻击下,其性能都优于CGO和LRTA算法;在噪声攻击下,本文算法的ROC曲线在LRTA算法的左下方,CGO算法的右上方,但距离较小如图7(e),说明漏报概率、误报概率这两个评价指标优于LRTA算法,弱于CGO算法,但差距较小,这是因为本文算法基于视频帧的灰度特征生成视频指纹,添加噪声后对灰度特征影响较大,使算法性能下降,弱于CGO算法;在组合攻击下,本文算法的ROC曲线位于CGO和LRTA算法的左下方如图7(f),说明在综合攻击下本文算法性能优于CGO算法和LRTA算法.综上所述,本文算法具有较好的鲁棒性.

4 结 论

为综合利用视频的空域和时域信息,增强视频指纹的鲁棒性,本文提出了一种Delaunay三角剖分下的视频指纹算法,该算法对视频帧分块后提取的特征点进行Delaunay三角剖分,以每一个剖分所得的四面体为单位计算其对应特征值,生成包含空域与时域信息的视频指纹.实验证明,该算法具有良好的鲁棒性.

Delaunay三角剖分后得到的四面体具有良好的稳定性,该四面体不仅体现了同一帧内特征点的联系,还包含了帧与帧之间在时域上的信息,因此本文提出的算法既具有较好的视频内容代表性又具有较好的鲁棒性.但是当视频的帧数较多时,Delaunay三角剖分得到的四面体的数目较多,从而增加了算法的计算复杂度,因此,本文下一步的工作将重点研究如何从众多的四面体中优选出具有代表性的四面体,在不降低算法鲁棒性能的前提下减小计算的复杂度.

：

[1] Oostveen,Kalker,Haitsma,et al.Feature extraction and a database straregy for video fingerprinting [C].Proc of Recent Advancein Visual Information Systems,Springer-Verlag,2002:117-128.

[2] Lee,Yoo C D,et al.Video fingerprinting based on centrodis of gradient orientations [C].Proc of Int.Conf.Acoust.Speech and Siganl Processing(ICCASSP),IEEE,2006:401-404.

[3] Chen L.Stentiford F W M.Video sequence matching based on temporal ordinal measurement [J].Pattern Recognition Letters,2008,29(13):1824-1831.

[4] Radhakrishnan R,Bauer C.Content-baesd video signatures based on projections of difference images[C].Proc of IEEE 9th Workshop on Mulitimedia Signal Processing,IEEE Xplore,2007:341-344.

[5] Coskun B,Bulent S,Nasir M.Spatio-temporal transform based video hashing [J].IEEE Trans on Multi-Media,2006,8(6):1190-1208.

[6] Zoran M,Zoran V.Robustness of SVD watermarks in video sequences encoded with H.264/AVC[C].International Conference on Environmental Science and Technology,2014.

[7] Urvoy M,Goudia D,Autrusseau F.Perceptual DFT watermarking with improved detection and robustness to geometrical distortions[J].IEEE Transactions on Information Forensics & Security,2014,9(7):1108-1119.

[8] Douze M,Jegou H,Schmid C.An image-based approach to video copy detection with spatio-temporal post-filtering [J].IEEE Transactions on Multimedia,2010,12(4):257- 266.

[9] Liu W,Mei T,Zhang Y.Instant mobile video search with layered audio-video indexing and progressive transmission[J].IEEE Transactions on Multimedia,2014,16(8):2242-2255.

[10] Roopalakshmi R,Reddy G R M,A.Novel approach to video copy detection using audio fingerprints and PCA [J].Procedia Computer Science,2011,5:149-156.

[11] Sunil L,Yoo C D,et al.Robust video fingerprinting based on symmetric pairwise boosting [J].Circuits and Systems gor Video Technology,2009,19(9):1379-1388.

[12] Jeandaniel B,Ramsay D,Arijit G.The stability of delaunay triangulations [J].International Journalof Computational Geometry & Applications,2015,23 (04n05):303-333.

[13] Aldahoud A,Singhai R,Kumar P,et al.Video fingerprinting using AED of CGO based signatures[C].IEEE International Conference on Computer Science and Automation Engineering,IEEE,2012:292-295.

[14] Li M,Monga V.Desynchronization resilient video fingerprinting via randomized,low-rank tensor approximations[C].IEEE,International Workshop on Multimedia Signal Processing,IEEE,2011:1-6.

[15] Liu Zhao-qing.Research on several key technologies of image sensing Hash [D].Harbin:Harbin University of Technology,2013.

[16] Caroli M,Teillaud M.Delaunay triangulations of point sets in closed euclidean d-manifolds [J].Annual Symposium on Computational Geometry,2011,6(1):274-282.

[17] Wu B,Krishnan S S,Zhang N,et al.Compact and robust video fingerprinting using sparse represented features[C].IEEE International Conference on Multimedia and Expo.IEEE,2016:1-6.

[18] Yang G,Chen N,Jiang Q.A robust hashing algorithm based on SURF for video copy detection [J].Computers & Security,2012,31(1):33-39.

[19] Wang R B,Chen H,Yao J L,et al.Video copy detection based on temporal contextual hashing[C].IEEE Second International Conference on Multimedia Big Data,IEEE,2016:223-228.

[20] Lee H K,Kim J.Extended temporal ordinal measurement using spatially normalized mean for video copy detection [J].Etri Journal,2010,32(3):490-492.

[21] Qingzhen M A,Wang Y,Zeng Y,et al.Hashing-based image copy detection[J].Ship Electronic Engineering,2014,34(9):96-99.

[22] Dash S,Kramer R M D,O′Dwyer L M,et al.A robust video copy detection system using TIRIDCT fingerprints and DWT statistical features [J].International Journal of Computer Applications,2012,51(6):29-34.

[23] Li M,Monga V.Compact video fingerprinting via structural graphical models[J].IEEE Transactions on Information Forensics & Security,2013,8(11):1709-1721.

[24] Bhogle M P,Chhangani A.Content based copy detection using TIRI-DCT method [J].International Journal of Engineering Sciences & Research Technology,2014,3(7):449-454.

附中文参考文献：

[15] 刘兆庆.图像感知哈希若干关键技术研究[D].哈尔滨:哈尔滨工业大学,2013.