基于NMF和SURF的视频帧间复制粘贴伪造盲检测

李晓丽 杜振龙

(南京工业大学计算机科学与技术学院，南京, 211816 )

基于NMF和SURF的视频帧间复制粘贴伪造盲检测

李晓丽 杜振龙

(南京工业大学计算机科学与技术学院，南京, 211816 )

针对视频帧间复制粘贴伪造，本文提出一种基于非负矩阵分解(Nonnegative matrix factorization, NMF)和加速稳健特征(Speed-up robust features, SURF)的帧间复制粘贴伪造盲检测算法。通过对视频帧进行小波变换，提取低频系数矩阵进行非负矩阵分解，将得到的系数矩阵作为视频帧的特征表示衡量帧间的相似性，根据相似度变化趋势判断视频帧间的连续性，从而确定疑似伪造复制粘贴序列的首帧及尾帧，并通过SURF特征匹配进行二次判定。实验结果表明，本文所提出帧间伪造检测算法对连续多帧的复制粘贴伪造具有较好的检测效果，避免了逐帧比对，降低了时间复杂度。

非负矩阵分解；SURF；帧间复制粘贴；视频伪造

引 言

视频帧间复制粘贴通过向视频帧序列复制粘贴一定数目的帧，达到添加或掩盖视频目标、改变视频内容[1]和延长物体运动时间等目的。视频帧间复制粘贴包括单帧多次复制粘贴和连续帧复制粘贴两类[2]。单帧多次复制粘贴通常把帧连续复制多次，所产生的复制粘贴视频不包含运动信息变化;连续多帧复制粘贴把包含目标物体的连续帧复制粘贴，所生成的视频存在重复内容。本文所讨论的视频帧间复制粘贴盲检测不依赖任何先验知识，从连续多帧复制粘贴的视频检测出复制粘贴的帧。针对连续帧的复制粘贴帧间视频伪造，提出了一种基于非负矩阵分解(Non-negative matrix factorization,NMF)[3]和加速稳健特征(Speeded up robust features, SURF)[4]的帧间复制粘贴盲检测算法。算法通过对视频帧进行小波变换，提取低频分量进行非负矩阵分解。用非负矩阵分解的系数矩阵作为帧特征表示，度量帧间的相似性。根据相似度变化趋势判断帧连续性，从而确定出疑似伪造复制粘贴帧序列的首帧及尾帧,通过SURF特征匹配方法进行判定,所提帧间盲检测算法对连续多帧的复制粘贴伪造具有较好的检测效果。传统方法采用模板匹配算法先确定疑似帧位置再判定帧序列的长度[5]，其算法复杂度为O(n2) 。传统算法的时空主要消耗在帧匹配过程，用同样的匹配精度处理候选帧和帧序列。本文从帧直方图变化明显位置确定疑似复制粘贴帧序列的首帧和尾帧，用SURF特征匹配给出首帧和尾帧对应的源帧。文献[6]根据物理定律推算视频物体的运动轨迹，并根据视频物体运动与推演的运动是否一致鉴定视频的真实性。该方法需要从视频恢复视点、几何等信息，计算量较大。利用视频的光照[7,8]、获取设备[9,10]等属性也可鉴定视频是否经过伪造，基于这些属性的视频真实性检测包括属性确定和属性检验两个阶段，属性确定依赖样本帧，其可信度与样本数量有关。

1 视频帧间复制粘贴伪造盲检测

连续多帧复制粘贴会在视频中产生多个视频序列，检测重复出现的帧序列可定位复制粘贴帧序列。复制粘贴帧序列多为包含兴趣物体的连续帧序列，首帧和尾帧界定了帧序列[11]。本文利用帧间相似度的变化判定疑似复制粘贴伪造序列的首帧和尾帧，通过对疑似序列的首帧和尾帧进行SURF特征匹配，确定视频中是否存在连续多帧的复制粘贴伪造。衡量帧间的相似度需要提取帧特征。由于帧特征的维数较高，影响处理效率，本文把小波变换和非负矩阵分解方法相结合，综合提取视频帧的局部特征，降低特征空间的维数，既保证了特征分量的非负性，又更好地获取了帧主要特征，具有更强的特征表示能力。为进一步确认视频的复制粘贴帧，本文采用SURF特征匹配的方法进行判断，确定复制粘贴类型，算法流程如图1所示。

1.1 非负矩阵分解

NMF是一种有效的特征提取方法，可提取数据中潜在的特征或结构，并能保持数据分量的非负特性。对于帧矩阵Vn×m，NMF算法通过寻找矩阵Wn×r和矩阵Hr×m，使得V≈WH，从而将矩阵Vn×m分解为两个非负矩阵的乘积，其中W为基矩阵，H为系数矩阵，r为NMF算法的秩。当满足条件(m+n)r≼nm时，可用系数矩阵H替代原数据矩阵V，并作为V的特征表示。由于H的秩小于V的秩，NMF通过数据维数约简降低了数据处理规模。

为了实现对给定矩阵的非负分解，即寻找合适的W和Η，需要构造一个合理的目标函数来度量样本矩阵分解前后的逼近程度，并在非负性约束条件下进行分解。给定帧Vn×m，对其进行非负矩阵分解，则

(1)

用欧氏距离衡量分解前后的差异，定义目标函数为

(2)

NMF算法的求解是一个不断迭代优化的过程，交替求解W和H，最终得到NMF算法的局部最优解为

(3)

(4)

迭代优化求解过程中对目标函数采用梯度下降方法依据式(3)的乘性迭代规则更新。本文对每帧进行非负矩阵分解，以非线性方式约简帧维数，把分解后的低秩矩阵矢量化作为帧的特征表示。采用NMF降低了帧维数，减少了数据存储空间，且能确保数据分量的非负特性。

1.2 SURF特征提取

SURF是一种基于不同尺度空间的，采用积分图像、盒子滤波以及Haar小波变换的特征点提取方法。图像I的一点p(x,y)在像素点p处，尺度为σ的海森矩阵表示为

(5)

(6)

式中：w为权系数，取值0.9，用来平衡解析解与近似解间的误差。为简化计算过程，SURF方法把高斯二阶微分模板与图像的卷积运算转化为盒式滤波方式计算。计算不同尺度盒式滤波的海森行列式响应，在不同尺度空间和位置搜索极值点，即SURF特征点，如图2所示。为保证特征点提取不受图像旋转变化的影响，需对SURF特征点确定主方向。采取以特征点为中心在半径为6s(s为特征点的尺度)的圆形区域内，用特定角度的扇形窗口旋转，统计每个窗口内的Haar小波特征值，把Haar累加值的最大对应方向作为该点的主方向。主方向确定后，以特征点为中心，沿特征点主方向把窗口划分成16个子图像块，对每个子块进行Haar小波变换，提取Haar小波特征。设dx和dy分别表示x和y方向上的Haar小波响应，统计∑dx，∑dy，∑|dx|和∑|dy|构成的4×4×4=64维特征矢量，如图3所示。

图2 SURF极值点搜索 图3 SURF特征向量的构成Fig.2 SURF extreme point search Fig.3 Composition of SURF feature vector

特征匹配即在特征空间中通过距离度量或相似度度量准则衡量特征向量间的相似性。本文采用最近邻搜索方法进行特征匹配，减少了计算量，加速了特征匹配效率。本文利用匹配SURF特征的方法判定视频帧序列是否存在复制粘贴。

1.3 视频帧间复制粘贴伪造盲检测

设Vsource={Fi|1≤i≤N}为视频帧序列，N为视频帧数。依次对每一帧进行1级Harr小波分解，提取Harr小波分解的低频段的低频分量L(k)作为帧代理数据，其中k表示视频帧时间。利用非负矩阵分解方法对L(k)进行特征提取，在非负约束条件下通过迭代优化求解基矩阵W(k)和系数矩阵H(k)，即有

(7)

式中：r为矩阵L(k)的秩，ite为迭代次数。

本文用分解NMF的系数矩阵H(k)作为帧特征，既降低数据特征维数，又减少了数据的存储空间。系数矩阵不能直接作为帧特征，需要量化，其规则为

(8)

式中：x，y分别为矩阵的行、列位置。把Q(k)量化后得到的P(k)作为帧特征，用汉明距ham(P(i),P(j))度量帧间的相似度，距离越大，相似度越小，因此，视频帧间的相似度度量公式为

(9)

如图4所示，帧间视频复制粘贴伪造包括连续多帧不相邻(图4(a))和连续多帧相邻(图4(b))的复制粘贴两类。视频中运动平缓的相邻帧变化呈现平稳状态。帧间相似度变化承载着视频内容变化状况。在帧相似度变化轨迹曲线中，若在某一时刻相似度值出现较大波动，则该时刻对应的视频帧即为疑似复制粘贴视频帧。对于连续多帧不相邻的复制粘贴伪造，复制子序列的首帧与前一帧间的相似度以及尾帧与后一帧间的相似度在整个视频帧间相似度变化轨迹上会出现较大的波动。在图4(a)第6帧与第7帧间的相似度及第9帧和第10帧间的相似度的帧间相似度变化轨迹会出现较大波动，因此，把第7帧与第9帧分别作为疑似伪造视频序列的首帧和尾帧。图4(b)所示的第4帧和第5帧间的相似度也会出现较大的波动，因此把第5帧作为疑似复制粘贴伪造视频子序列的首帧。此种情况下，伪造视频子序列的尾帧与其相邻帧间不会出现较大的波动。图4(b)说明视频帧序列的帧间相似度的变化轨迹只出现一次较大波动，则为连续多帧相邻的复制粘贴伪造。仅通过帧间相似度变化方法检测视频伪造帧序列有时会误检或漏检，本文采用SURF特征匹配方法进一步验证检测到的疑似复制粘贴伪造视频帧。检测疑似复制粘贴帧序列的首帧和尾帧可定位出伪造帧序列。疑似伪造帧序列的首帧和尾帧界定了视频伪造位置，文中称其为疑似复制粘贴伪造帧。设视频的疑似复制粘贴伪造帧为F'，提取帧F'的SURF特征点，用集合T'表示，记录每一特征点的坐标，用集合P表示，再提取剩余帧Fi的SURF特征点，用集合Ti表示，记录其特征点坐标，用集合Ci表示。若F'为复制粘贴帧，则帧序列中存在与F'的特征点个数相同的帧。F'中的特征点均能在Fi中找到与之唯一相匹配的特征点，且特征点集合P和集合Ci间的匹配特征点的距离dis等于零，则可判定为同一视频帧经过复制粘贴得到。匹配SURF特征点可检测出疑似伪造帧序列的首帧、尾帧及首帧和尾帧对应的复制帧。若伪造帧序列的首帧与复制帧序列的尾帧相邻，则帧序列为连续帧相邻的复制粘贴伪造，如图4(b)所示；若不相邻，则为连续帧不相邻的复制粘贴伪造。

2 结果与分析

设实验平台为：4核i7处理器、4 GB内存的联想T430笔记本计算机；Matlab 2012环境，本文实验视频大小为1 280像素×720像素。本文实现了所提的基于非负矩阵分解和SURF的帧间复制粘贴伪造盲检测算法，给出连续多帧相邻的复制粘贴伪造及连续多帧不相邻的复制粘贴伪造检测结果。

2.1 实验数据

实验数据如图5，视频帧序列的帧间相似度大小及变化轨迹如图6所示。

图5 连续9帧的实验数据Fig.5 Nine frames of experimental data

图6 帧间相似度衡量Fig.6 Frame similarity evaluation

图5给出了实验数据的连续9帧，利用NMF算法提取视频帧特征，并对图5的9帧进行帧间相似度衡量，其用直方图表示如图6(a)。图5的相似度变化轨迹如图6(b)所示，从图6可以看出，帧间相似度值比较接近，呈现平稳变化趋势，不存在较大波动，符合视频帧间连续性变化特点。

2.2 连续多帧不相邻的复制粘贴伪造检测

图7给出了对图5进行连续多帧不相邻的复制粘贴伪造数据。图5视频的第2、3和4帧复制粘贴到了第7帧与第8帧之间，执行了连续多帧不相邻的复制粘贴操作，生成了图7的复制粘贴伪造数据。

图7 连续多帧不相邻的复制粘贴伪造Fig.7 Copy-paste manipulation to continuous multiple frames

图8 伪造视频的帧间相似度衡量Fig.8 Similarity evaluations to forged video

图8给出连续多帧不相邻的复制粘贴伪造视频帧间相似度值和帧间相似度变化轨迹，可以看出第7帧，第10帧的相似度值出现较大波动，如图8所示，因此可判断帧间复制粘贴造成了帧间相似度的波动。本文通过特征匹配检测疑似伪造帧序列的首帧与尾帧。图9给出伪造帧序列的首帧与尾帧的SURF特征点检测结果。图9(a)所示帧的特征点个数为3 562个，图9(b)对所示帧的特征点个数为3 649个。把疑似伪造帧序列的首帧和尾帧与它们界定的帧序列以外的所有视频帧进行SURF特征匹配，检测到图9(a)，(b)分别与原视频帧的第2帧和第4帧具有相同的SURF特征点个数，且能完全匹配。由于检测到的伪造帧序列首帧的前一帧不是尾帧的复制帧，因此，该视频通过连续多帧不相邻的复制粘贴伪造得到，且第8～10帧由第2～4帧复制粘贴得到。

图9 疑似复制粘贴帧的SURF特征点提取Fig.9 SURF feature extraction from forged video

2.3 连续多帧相邻的复制粘贴伪造检测

图10给出连续多帧相邻复制粘贴伪造检测实验数据。图11给出了连续多帧相邻的复制粘贴伪造视频的帧间相似度直方图及变化轨迹。从图11可知，第10帧的帧间相似度发生较大波动，因此第10帧由疑似复制粘贴伪造操作引起。图11的帧间相似度直方图和变化轨迹表明，疑似伪造操作符合连续多帧相邻的复制粘贴伪造，因此第10帧为疑似伪造视频帧序列的首帧。若为连续多帧相邻复制粘贴伪造，则会检测到首帧前一帧为伪造帧序列的尾帧，因而对疑似首帧的前一帧继续检测，提取帧的SURF特征，并进行特征匹配，图12给出了疑似首帧与其前一帧的SURF特征提取结果。图12(a)所示帧特征点个数为3 620个，图12(b) 所示帧的特征点个数为3 397个。对检测到的疑似的首帧与剩余帧进行SURF特征匹配，最终检测到视频序列的第3帧与疑似首帧具有相同的SURF特征点个数和完整的匹配。以相同方式处理疑似尾帧，检测到帧序列的第10～18帧的帧序列为第3～9帧通过复制粘贴生成。

图10 连续多帧相邻的复制粘贴伪造Fig.10 Copy-paste manipulation of continuous multiple frame

图11 伪造视频的帧间相似度衡量Fig.11 Similarity evaluations to forged video

图12 伪造视频的SURF特征点提取Fig.12 SURF feature extraction from forged video

2.4 算法比较

本文算法采用NMF和SURF两次检测判定帧序列的复制粘贴伪造，与传统用特征点或图像特征进行检测的方法相比，降低了特征空间维数和特征匹配次数。实验数据的SURF特征点个数介于3 300至3 700间(平均值为3 500)。设伪造后视频帧序列的帧数为n，其中复制粘贴伪造帧序列长度为m，NMF算法的迭代次数及秩分别取ite=100和r=200，本文所选帧大小为1 280像素×720像素。算法比较如表1所示。

文献[8]对检测的Harris角点构建环形均值特征描述，实验数据每帧Harris特征点个数平均为800，进行帧序列复制检测需匹配n(n-1)次。只利用SURF算法检测视频帧序列提取特征，并进行帧间特征匹配，匹配次数为n(n-1)，计算复杂度为O(n2)。单纯用NMF算法视频帧序列需要对每帧进行非负矩阵分解，用系数矩阵进行匹配，特征维数和匹配次数减小了，因NMF算法对系数矩阵进行了分级量化，因此NMF未能很好地捕捉帧间微小变化。SURF算法特征点并提取特征点描述子，可反映帧间微小变化。因此，单纯利用SURF算法可提高伪造检测的准确度。本文所提算法利用NMF算法根据帧间相似度检测疑似复制粘贴帧，再利用SURF特征匹配检测复制粘贴帧序列，因仅需检测疑似复制粘贴帧序列的首帧和尾帧，因此对于连续多帧不相邻的复制粘贴伪造仅需进行2(n-m)次帧匹配。由于m≼n，本文所提算法的时间复杂度为O(n)。对于连续多帧相邻的复制粘贴伪造，仅需进行(n-m)次帧匹配，与单纯利用文献[8]算法、SURF或NMF算法相比，特征匹配次数降低了一个数量级，时空复杂度由O(n2) 降为O(n)。

表1 算法比较

3 结束语

本文提出了一种基于NMF和SURF的视频帧间复制粘贴伪造盲检测算法。对小波变换的低频部分进行NMF分解，把NMF系数矩阵作为帧特征。用帧间相似度直方图和变化轨迹检测帧序列疑似伪造的首帧和尾帧；利用SURF特征匹配方法二次判定疑似伪造帧序列，搜索疑似首帧和尾帧的匹配帧以定位伪造帧序列。所提算法较传统单纯利用特征点匹配的方法减少了特征匹配的次数，降低了时间复杂度，缩短了检测时间，提高了检测准确性。本文在检测场景变化剧烈或内容变化较大的视频时检测结果波动较大，需要继续完善和改进。

[1] Huang T, Tian Y, Gao W, Lu J. Mediaprinting: Identifying multimedia content for digital rights management[J]. IEEE Computer, 2010,43(12): 28-35.

[2] Wang W, Farid H. Exposing digital forgeries in video by detecting duplication[C]// Proceedings of the 9th Workshop on Multimedia & Security. Geneva, Switzerland:ACM Press, 2007: 35-42.

[3] Yao H, Qiao T, Tang Z. Detecting copy-move forgery using Non-negative matrix factorization[C]//Proceedings of Multimedia Information Networking and Security． Shanghai：[s.n.], 2011: 591-594.

[4] Bay H, Tuytelaars T, Van Cool L. SURF:Speed up robust features[C]// Proceedings of 9th European Conference on Computer Vision (ECCV)．Marseille, France:Springer Press, 2006:404-417.

[5] 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.

[6] Conotter V, O′Brien J F, Farid H. Exposing digital forgeries in ballistic motion[J]. IEEE Transactions on Information Forensics and Security, 2012,7(1):283-296.

[7] Zhang W, Cao X, Qu Y, Hou Y, et al. Detecting and extracting the photo composites using planar homography and graph cut[J]. IEEE Transactions on Information Forensics and Security, 2010,5(3):544-555.

[8] Zhang J, Su Y, Zhang M. Exposing digital video forgery by ghost shadow artifact[C]//Proceedings of the First ACM Workshop on Multimedia in Forensics. Geneva, Switzerland:ACM Press, 2009: 49-54.

[9] Wang W, Farid H. Exposing digital forgeries in interlaced and de-interlaced video[J]. Information Forensics and Security, IEEE Transactions on, 2007, 2(3): 438-449.

[10] Bayram S, Sencar H T, Memon N. Video copy detection based on source device characteristics: A complementary approach to content-based methods[C]//Proceedings of the 1st ACM International Conference on Multimedia Information Retrieval. Geneva, Switzerland:ACM Press, 2008: 435-442.

[11] Feng J, Gao X B, Yang Y. Key frame reconstruction algorithm for video shot retrieval[J]. Journal of Computer-Aided Design & Computer-Graphics, 2008,20(6):775-780．

Interframe Copy-Paste Forgery Blind Detection Based on NMF and SURF

Li Xiaoli， Du Zhenlong

(School of Computer Science and Technology, Nanjing TECH University, Nanjing， 211816, China)

Interframe and intraframe copy-paste forgery are two typical video forgery means. Interframe manipulation is easily done with the video editing software. An algorithm based on nonnegative matrix factorization(NMF) and speed-up robust featuare(SURF) is proposed for detecting interframe copy-paste forgery. Frames are transformed via wavelet．And low-frequency band is further decomposed by NMF. The NMF coefficient matrix is served as the video frame feature descriptor. The variation of frame similarity is used for locating the forged first and last frames via measuring frame similarity. The starting and ending frames mark the suspicious frame sequence, and these frames are further investigated by SURF. The presented approach avoids frame-by-frame match and decreases the time complexity toO(n). The experiment demostrates that the proposed algorithm performs well for interframe video copy-paste forgery detection.

nonnegative matrix factorization (NMF); speed up robust features(SURF) copy-paste; video forgery

国家自然科学基金(61073098)资助项目;教育部高等学校博士点基金(2011322112003)资助项目;江苏省“六大人才”高峰基金(2012-WLW-023)资助项目。

2015-07-15；

2015-10-12

TP391

A

李晓丽(1971-)，女，博士，副教授，研究方向：信息安全、水信息处理，E-mail：lixl@njtech.edu.cn。

杜振龙(1971-)，男，博士，副教授，研究方向：计算机图形学、数字媒体取证。