基于奇异值分解的视频拷贝检测研究

吴明君，侯艳艳，李庆华

（1.枣庄学院信息科学与工程学院，山东枣庄 277160；2.齐鲁工业大学电气工程与自动化学院，山东济南 250353）

基于奇异值分解的视频拷贝检测研究

吴明君1，侯艳艳1，李庆华2

（1.枣庄学院信息科学与工程学院，山东枣庄 277160；2.齐鲁工业大学电气工程与自动化学院，山东济南 250353）

针对传统的视频拷贝检测算法计算量大、对视频变化敏感等问题，提出一种新的视频指纹算法来产生包含时空域信息的关键帧。采用奇异值分解的方法提取视频关键帧的特征向量，对视频特征序列进行降维。改进的视频拷贝检测算法对噪声、帧平移、帧旋转、丢帧等有很好的鲁棒性。与以往的拷贝算法相比，提高了视频拷贝检测的查全率和准确率，降低了误码率，与源视频具有较高的匹配率。

视频拷贝检测；奇异值分解；特征提取；视频指纹

吴明君，侯艳艳，李庆华.基于奇异值分解的视频拷贝检测研究［J］.河北科技大学学报，2014，35（2）：179-183.

WU Mingjun，HOU Yanyan，LI Qinghua.Study on singular value decomposition based video copy detection［J］.Journal of Hebei University of Science and Technology，2014，35（2）：179-183.

视频信息的暴发性增长使得网络用户可以共享更多的视频，建立有效的视频版权保护和检测机制显得尤为重要。视频水印和视频指纹算法可应用于视频拷贝检测过程，视频水印算法要求在视频中嵌入额外的信息来降低视频感知质量，视频拥有者很难在视频发布前实现，在视频拷贝检测中有很大的局限性。视频指纹算法主要提取具有鲁棒性和区分性的特征信息，通过计算检测视频与原始视频之间的特征距离来检测视频是否为拷贝。视频指纹算法的研究仍然处于初步阶段，许多研究者将图像指纹算法应用于视频拷贝检测，SUNIL等将视频中的帧分成N×M的块，提取每块的梯度特征，所有块的梯度特征组合成该帧特征信息［1］。LAW-TO等提出基于哈希点提取帧特征信息［2］，由于没有考虑视频帧的连续性，增加了产生的哈希函数维数，为了减少哈希函数的维数，许多学者提出基于关键帧的视频指纹算法，将视频分片，提取每片关键帧的高维特征量，通过哈希算法生成低维特征量，ROOVER等提出提取不同径向区的像素方差作为特征量的算法［3］，缺点是对于关键帧衰减和噪声敏感，调整关键帧将不利于视频检测的实现。COSKUN等提出提取视频的时空域特征，将视频序列看成三维矩阵，通过DCT变换提取视频特征，在高斯噪声、改变亮度、取反等几何攻击下保持了良好的性能，但计算复杂度较高［4］。

本文首先根据视频的时空域特征将视频分成片段，然后根据视频片段内的帧间相关性，将片段内帧的组合构成关键帧。最后对关键帧矩阵进行奇异值分解，根据奇异值分布特点，选取前去10个奇异值构成关键帧矩阵的特征量，通过与视频库匹配计算，完成拷贝检测。实验证明改进的视频检测算法比TOM算法［5］具有更高的查准率和查全率。

1 基于奇异值分解的视频拷贝检测算法

1.1 视频预处理

基于奇异值分解的视频拷贝检测算法分视频预处理、片段划分、关键帧选取、特征向量提取及匹配4步实现。

为了保证算法可以抵抗视频缩放和帧率的变化，首先对视频进行预处理，预处理主要通过对视频进行时空域重采样改变帧率和分辨率，统一帧率和帧大小，重采样之前采用低通高斯滤波器对时空域处理以阻止量化噪声［6］。重采样后帧大小设为160×120，160×120适合 MPEG1，AVI，Real Video 512k，Real Video 28k等视频格式，且在降低计算量的基础上，可保证视频的局部不变特性。基于相邻帧之间的相似性，镜头内部相邻帧内容上的差别非常小，帧率为12帧／s能基本保证视频的连贯性［7］。

1.2 视频片段划分

视频由一系列片段组成，片段内的帧之间具有较强的时域相关性［8］。如果提取视频序列每帧的特征值进行检测匹配，会造成特征信息冗余和增加计算复杂度，本文基于Bin-wise平均颜色直方图对视频进行片段划分，依次计算相邻帧之间Bin-wise平均颜色直方图的差值，递归分割视频［9］。算法如下。

1）设视频帧序列为F1，F2，…，Fi，…，Fn，i＝1，2，…，n。

2）计算Fi与后续帧Fi＋1的特征距离di，di小于指定的相似度阈值β，则i＋1，返回2），继续计算；di大于相似度阈值Y，则转到3）计算，直到i＝n－1，停止计算。

3）将｛F1，F2，…，Fi｝保存为视频子片段，i＋1；返回2）计算。

视频特征距离d利用直方图交计算，视频片段分割算法能够有效地将视频划分成视频片段集合，具有计算复杂度低、效率高的优点。基于整个视频进行片段分割，分割效果不受镜头边界检测效果的负面影响，得到的视频片段具有更好的内部相似性和外部区分性［10］。

1.3 关键帧选取

考虑到视频片段内的帧间相关性，不是选用视频片段某帧作为片段代表，而是将每个视频片段中的帧加权平均得到关键帧，设lm，n，k为第k帧（m，n）象素的亮度值。为了避免不同格式视频颜色特性发生变化，文中采用视频帧的亮度部分作为视频特征，指数函数对于关键帧的时域信息破坏较少，能更好地代表视频的空域信息，具有较好的视觉效果［11］。关键帧对应的象素计算：

1.4 特征向量提取及匹配

关键帧可以看成一个像素矩阵，视频受到扰动时，像素矩阵的奇异值不会发生剧烈变化，奇异值能体现视频的代数特征，具有较好的稳定性，本文采用奇异值分解的方法从像素矩阵中提取标识视频序列的特征向量［12］。

关键帧矩阵A＝M×N，对矩阵A∈Rm×n进行奇异值分解，其中R表示实数域，则存在矩阵U和V满足：

U是M×N阶酉矩阵，V是M×N阶酉矩阵，且满足：

AAT的特征向量为A的左奇异向量；ATA的特征向量为A的右奇异向量，对应的特征值都是A的奇异值的平方。

Σ为半正定对角矩阵：

Σ矩阵非对角线上的元素为0，λi为矩阵A的奇异值，r为矩阵A的秩，对角线上的元素为

λ1，λ2，…，λr－1，λr连同λr＋1，符合λi＝λl＝0（i＝1，2，…，r）按降序排列构成视频关键帧的特征向量，归一化的奇异值对于视频拷贝检测具有很好的鲁棒性，设σi为第i个特征量归一化值：

特征向量维数选取对拷贝检测有很大影响，特征向量维数太大会造成计算量增大，维数太小又很难实现对视频的区分，设特征向量的维数为10。

视频匹配过程将待测视频与原始视频库的特征值进行比较，σj，i为检测视频第j帧的第i个特征量，σ′j，i为 原始视频第j帧的第i个特征量，L（Aj，A′j）为特征向量的距离函数：

d（A，A′）为待测视频与原始视频之间的距离，k为待测视频片段个数，则

若待测视频片段数k与原始视频片段数差别较大时，采用滑动窗方法来进行匹配，以较短的视频长度为滑动窗长度［13］。

2 仿真实验及分析

为分析本文算法的性能，从视频数据库TRECVID的MUSCLE-VCD-2008数据集选取7个视频序列，构成待测视频样本。

视频拷贝检测将检测出所有可能拷贝的帧或片段的检测查全率（Recall）和查准率（Precision）作为视频拷贝检测的指标［14］。计算公式如下。

查全率＝有关联的正确检索结果／所有有关联的结果；

查准率＝有关联的正确检索结果／所有检索到的结果。

视频关键帧前几个奇异值较大，剩下的奇异值一般较小，图1为测试视频和它们对应的前10个归一化奇异值，图2为不同奇异值个数的查全率和查准率。实验证明，奇异值个数为10时，视频拷贝检测算法能得到较好的性能和准确率，当奇异值的个数再增加对视频拷贝检测的性能提高不大，增加了系统复杂度。

本文选取20 min的7个视频样本进行实验，相似度阈值β为0.13，wk＝γk中γ为0.65，表1为本

文算法与TOM算法和OM算法［15］的平均查全率与平均查准率比较。

图1 前10个归一化奇异值对应图Fig.1 First 10 normalized singular value for test video

表1 不同视频的查全率与查准率Tab.1 Recall and precision for different video

图2 不同奇异值个数下的查全率与查准率Fig.2 Recall and precision for different number singular value

为了进一步验证算法的精确性，从处理集合选取高斯白噪声、帧平移、帧旋转、模糊处理、丢帧、帧率改变等攻击方法，对7个视频进行攻击，计算误码率，并且验证是否能从原始视频库中检测出攻击视频。误码率为2个序列不同码字的数目与序列长度的比值，阈值设为0.15，实验结果如表2所示，证明本算法具有较好的区分性和检测精确度。

表2 视频拷贝检测结果Tab.2 Video copy detection results

3 结 语

提出一种基于奇异值分解的视频拷贝检测方法。该方法基于视频帧相似性原理划分视频片段，在关键帧中嵌入片段时域信息，采用抗干扰能力强的归一化奇异值算法计算特征向量，不再采用将视频拷贝检测转化为帧匹配模式来处理问题。实验表明本文提出的视频拷贝检测算法能有效保留视频的时空域特征，较好地区分拷贝视频与原始视频，在保证视频检测准确率的基础上，降低检测的误码率。

［1］ SUNIL L，YOO C D.Robust video fingerprinting for content-based video identification［J］.Circuits and Systems for Video Technology，2008，18（7）：983-988.

［2］ LAW-TO J，BUISSON O，GOUET-BRUNET V，et al.Robust voting algorithm based on labels of behavior for video copy detection［A］.14th Annual ACM International Conference on Multimedia［C］.New York：［s.n.］，2006.835-844.

［3］ de ROOVER C，de VLEESCHOUWER C，LEFEBVRE F，et al.Robust video hashing based on radial projections of key frames［J］.Signal Processing，2005，53（10）：4020-4037.

［4］ COSKUN B S，MEMON N.Spatiotemporal transform based video hashing［J］.Multimedia，2006，8（6）：1190-1208.

［5］ HUA Xiansheng，XIAN Chen，ZHANG Hongjiang.Robust video signature based on ordinal measure［A］.ICIP′04.2004 International Conference on Image Processing（Volume：1）［C］.［S.l.］：［s.n.］，2004.685-688.

［6］ TRUONG B T，VENKATESH S.VideoAbstraction：A system atic review and classification［J］.ACM Trans on Multimedia Computing，Communications and Applications，2007，3（1）：1-37.

［7］ YUAN Jinhui，WANG Huiyi，XIAO Lan，et al.A form al study of shot boundary detect ion［J］.IEEE Trans on Circuits and System for Video Technology，2007，17（2）：168-186.

［8］ 黄 敏，赵 艳，王海瑶，等.基于数字水印技术的电子签章算法研究［J］.河北工业科技，2012，29（3）：149-154.

HUANG Min，ZHAO Yan，WANG Haiyao，et al.Electronic signature algorithm based on digital signature and digital watermarking technology［J］.Hebei Journal of Science and Technology，2012，29（3）：149-154.

［9］ 李春华，秦志英.一种基于 DCT的图像灰度水印算法［J］.河北工业科技，2012，29（3）：334-337.

LI Chunhua，QIN Zhiying.A gray level image watermarking algorithm based on DCT［J］.Hebei Journal of Science and Technology，2012，29（3）：334-337.

［10］ ESMAEILI M M，FATOURECHI M，WARD R K.A robust and fast video copy detection system using content-based fingerprinting［J］.Information Forensics and Security，2011，6（1）：213-226.

［11］ NIE Xiushan，LIU Ju，SUN Jiande.Robust video hashing for identification based on MDS［A］.2010 IEEE International Conference on Acoustics Speech and Signal Processing（ICASSP）［C］.Dallas：［s.n.］，2010.1834-1837.

［12］ NIE Xiushan，LIU Ju，SUN Jiande，et al.Robust video hashing based on double-layer embedding［J］.IEEE Signal Processing Letters，2011，18（5）：307-310.

［13］ TIAN Y，JIANG M，MOUL X，et al.A multimodal video copy detection approach with sequential pyramid matching［A］.IEEE International Conference on Image Processing［C］.Brussels：Belgium，2011.11-14.

［14］ WU Xiao，LI Jintao，TANG Sheng，et al.Video copy detection based on spatio-temporal trajectory behavior feature［J］.Journal of Computer Research and Development，2010，47：1871-1877.

［15］ KIM C，VASUDEY B.Spation temporal sequence matching for efficient video copy detection［J］.Circuits and Systems for Video Technology，2005，15（1）：127-132.

Study on singular value decomposition based video copy detection

WU Mingjun1，HOU Yanyan1，LI Qinghua2
（1.College of Information Science and Engineering，Zaozhuang College，Zaozhuang Shandong 277160，China；2.College of Electrical Information and Control Engineering，Qilu University of Technology，Jinan Shandong 250353，China）

According to the problems of heavy computation load and sensitivity to video variation in conventional video copy detection algorithms，a novel video fingerprinting algorithm is presented to produce the key frame that contains the time and spatial information.The singular value decomposition is used to extract feature vectors of key frames，and then to reduce the dimension of video feature sequence.The improved video copy detection algorithm has good robustness against noise，frame shifting，frame-rate conversion and frame lost，etc.Compared with previous copy algorithms，the video copy detection recall and precision are improved with high matching rate to the source video，while the error rate is reduced.

video copy detection；singular value decomposition；feature extraction；video fingerprinting

TP391

A

1008-1542（2014）02-0179-05

10.7535／hbkd.2014yx02012

2013-12-12；

2014-01-19；责任编辑：李 穆

国家自然科学基金（41204025）

吴明君（1958-），男，山东蓬莱人，教授，主要从事视频图像处理方面的研究。

E-mail：wmjnet＠uzz.edu.cn