基于图建模的视频指纹方法

摘要

本发明提供了一种基于图建模的视频指纹方法，包括以下步骤：(1)预处理：将视频帧的尺寸标准化并归一化帧率；(2)关键帧的选取：根据二叉树理论来选取视频关键帧；(3)利用图割和能量优化理论提取视频前景图像，利用前景图像四阶累积量的离散余弦变换作为关键帧的特征，进而构成整个视频特征；(4)构造视频指纹：匹配标签和二值化视频指纹；(5)分级匹配，利用匹配标签进行初级匹配，然后利用二值化序列进行精细匹配。实验证明，本发明具有较好的鲁棒性和区分性。

权利要求

1.一种基于图建模的视频指纹方法，其特征在于所述方法包括以下步骤：(1)预处理：将视频帧的尺寸标准化，统一帧率，但是不改变视频内容；

(2)视频关键帧的选取：把视频建模成无向权重图，利用二叉树来选取视频关键帧；

(3)利用图割理论和能量函数优化来提取视频关键帧的前景图像，并利用前景图像的四阶累积量的离散余弦变换作为视频关键帧的特征，进而构成视频的特征；

(4)计算视频特征序列的峭度作为匹配标签，对特征序列进行二值量化作为视频指纹；

(5)对视频指纹进行分级匹配。

2.根据权利要求1所述的基于图建模的视频指纹方法，其特征在于：所述步骤(2)的具体实现步骤是：①以视频帧为顶点，以帧之间的关系来构造边，把视频等价为一个无向权重图；

②利用二叉树选取视频关键帧。

3.根据权利要求1所述的基于图建模的视频指纹方法，其特征在于：所述步骤(3)的具体实现步骤是：①利用图割理论提取视频关键帧前景图像；

②计算前景图像的四阶累积量，并计算四阶累积量的离散余弦变换系数。

4.根据权利要求1所述的基于图建模的视频指纹方法，其特征在于：所述步骤(4)的具体实现步骤是：①由每帧四阶累积量离散余弦变换的变换系数中较大的20个系数构造视频特征向量；

②计算特征向量的峭度，称为视频匹配标签；

③利用密钥把视频特征向量量化成一个二值序列，由视频匹配标签和二值序列共同构成视频指纹。

5.根据权利要求1所述的基于图建模的视频指纹方法，其特征在于：所述步骤(5)的具体实现步骤是：①利用视频匹配标签在视频数据库中搜索，得到一个可疑匹配视频组；

②在可疑匹配视频组中利用视频指纹中的二值序列对视频指纹进行精细匹配，以错误码元数作为两个视频的距离，然后计算误码率若误码率小于给定阈值，则说明两个视频中其一为拷贝。

说明书

基于图建模的视频指纹方法

技术领域

[0001] 本发明涉及一种视频指纹方法，尤其涉及一种基于图建模的视频指纹方法，属于视频、多媒体信号处理技术领域。

背景技术

[0002] 随着计算机与信息技术的发展，互联网已经成为日常生活中不可或缺的一部分，特别是随着多媒体技术的迅速发展，互联网视频网站越来越多，视频内容变的越来越丰富，但随之而来的网络信息安全问题也变的日渐突出。网络用户可以随意的下载、编辑视频并再次上传，由此网络中出现大量“垃圾视频”，据统计，在某些热点视频的检索结果中，视频拷贝的比例甚至高达93％，这大大降低了视频检索的效率。同时，由于互联网上对于海量视频的管理缺乏规划和统一性，常常引起一些诸如知识产权等的纠纷，盗版和非法下载的出现也危害了版权所有者的利益，挫伤了创新的积极性。去除网络中的“垃圾视频”以及打击盗版进行有效的版权管理从本质上来说都是视频内容认证和识别问题。基于内容的视频指纹技术正是解决上述问题的主要方法。

[0003] 基于内容的视频指纹(Content Based Video Fingerprinting：CBVF)，又被称为视频哈希(Video Hashing)，与数字视频水印不同，它不需要在视频发布或传播之前，人工地在视频对象中嵌入附加信息，因此，CBVF对于尚未发布和已经发布的视频都有效；同时，由于不需要在视频上嵌入附加信息，CBVF解决了数字视频水印技术中水印的不可见性和鲁棒性之间的矛盾，从而提高了CBVF对于常见攻击的鲁棒性。利用CBVF技术不但可以在视频检索中搜索到多余的视频拷贝，并将其屏蔽，而且有助于规范数字视频版权、传播等的管理；同时，从另一个方面，也可以通过CBVF来对商业视频及其视频拷贝进行跟踪分析，以获得有价值的营销策略信息。因此，在个人视频制作与网络传播日益流行的情况下，CBVF具有重要的理论价值和应用价值，近年来已经成为了多媒体信息处理领域的研究热点，各种算法也相继被提出，目前的视频指纹算法大多都是基于关键帧的，但是关键帧的选取依赖于镜头的分割，且镜头分割是一个复杂的过程，镜头分割的好坏对关键帧的影响很大。本发明提出了一种基于二叉树理论的关键帧选取的方法，该方法避开了镜头的分割，且具有成熟的图论理论支持。另一方面，前景图像是人关注的主要对象，而目前的视频指纹算法恰恰忽略了人的关注特性，本发明正是基于前景图像这一人的关注对象来提取视频指纹的，这也是本发明的优势之一。

[0004] 视频由大量的帧组成，帧格式各种各样，但是从宏观的角度来看，可以把视频的每一帧当作高维空间中的一个点，点的坐标由帧的某种属性决定，点与点之间根据帧的关系连线就可以构成一个图。因此，视频可以看作高维空间里的一个权重图。另一方面，视频帧由若干像素组成，若以像素点为图顶点，像素点之间关系定义边，则帧也可以看作一个权重图，本发明从图建模的角度入手，利用图论相关理论来提取关键帧。视频的前景图像反映了视频的主要内容，同时前景图像也是人的主要关注对象，本发明利用前景图像构造视频指纹。

发明内容

[0005] 本发明针对现有视频拷贝检测技术存在的不足，提供一种具有较好的鲁棒性和区分性的基于图建模的视频指纹方法。

[0006] 本发明的基于图建模的视频指纹方法，包括以下步骤：

[0007] (1)预处理：将视频帧的尺寸标准化，统一帧率，但是不改变视频内容；

[0008] (2)视频关键帧的选取：把视频建模成无向权重图，利用二叉树来选取视频关键帧；

[0009] (3)利用图割理论和能量函数优化来提取视频关键帧的前景图像，并利用前景图像的四阶累积量的离散余弦变换作为视频关键帧的特征，进而构成视频的特征；

[0010] (4)计算视频特征序列的峭度作为匹配标签，对特征序列进行二值量化作为视频指纹；

[0011] (5)对视频指纹进行分级匹配。

[0012] 所述步骤(2)的具体实现步骤是：

[0013] ①以视频帧为顶点，以帧之间的关系来构造边，把视频等价为一个无向权重图；

[0014] ②利用二叉树选取视频关键帧；

[0015] 所述步骤(3)的具体实现步骤是：

[0016] ①利用图割理论提取视频关键帧前景图像；

[0017] ②计算前景图像的四阶累积量，并计算四阶累积量的离散余弦变换系数。

[0018] 所述步骤(4)的具体实现步骤是：

[0019] ①由每帧四阶累积量离散余弦变换的变换系数中较大的20个系数构造视频特征向量；

[0020] ②计算特征向量的峭度，称为视频匹配标签；

[0021] ③利用密钥把视频特征向量量化成一个二值序列，由视频匹配标签和二值序列共同构成视频指纹。

[0022] 所述步骤(5)的具体实现步骤是：

[0023] ①利用视频匹配标签在视频数据库中搜索，得到一个可疑匹配视频组；

[0024] ②在可疑匹配视频组中利用视频指纹中的二值序列对视频指纹进行精细匹配，以错误码元数作为两个视频的距离，然后计算误码率若误码率小于给定阈值，则说明两个视频中其一为拷贝。

[0025] 上述方法首先利用二叉树和优化理论对视频进行关键帧提取，然后利用图割理论提取视频前景图像，以高阶累计量的离散余弦变换系数作为视关键帧特征，利用关键帧的特征向量构造视频指纹。

[0026] 本发明具有较好的鲁棒性和区分性，利用图建模的方式选取关键帧，利用图割理论提取关键帧的前景图像生成视频指纹，把视频分析问题等价为图分析问题，从而成熟的图论理论可应用其中，为视频分析和视频指纹的生成提供了可靠的理论基础和分析工具。

附图说明

[0027] 图1是本发明方法的步骤框架示意图。

[0028] 图2是二叉树提取关键帧的示意图。

[0029] 图3是利用图割理论提取前景图像示意图，其中(a)是原始图像，(b)是提取的前景图像。

[0030] 图4是原始视频和各种攻击后的视频：(a)原始视频；(b)加入高斯噪声后的视频；(c)加入椒盐噪声后的视频；(d)遭受模糊攻击后的视频；(e)遭受黑框攻击后的视频(f)遭受logo嵌入后的视频。

[0031] 具体实施方法：

[0032] 下面结合附图对本发明加以详细的说明。

[0033] 本发明的方法按图1所示流程，包括如下具体步骤：

[0034] (1)预处理

[0035] 视频在传输的过程中，因为干扰和攻击会导致视频帧率和分辨率发生变化，为了解决这个问题，增加算法的鲁棒性，首先在预处理的过程中通过重采样的方法，使视频具有相同的帧率，本文实验中统一帧率为5fps。然后对每帧的尺寸标准化，标准化的过程使视频的分辨率改变，但是不改变视频内容。视频指纹的目的是实行视频内容的安全认证，因此，帧率和分辨率的改变不会影响内容认证的效果。在本文方法中，帧放缩处理函数S定义如下：

[0036] fk＝S(Fk) (1)[0037] 其中Fk∈Rm×n和fk∈Rw×h分别代表标准化前后的第k帧，且w＝144，h＝176。

[0038] (2)关键帧选取

[0039] ①把视频转化为无向权重图，把视频的每一帧当作高维空间中的一个点，点的坐标由帧的各种属性决定，点与点之间根据帧之间的关系连线就可以构成一个图。因此，视频可以看作高维空间里的一个无向权重图G＝(V，E)，其中V和E分别代表图顶点集和边集。

[0040] ②利用二叉树选取视频关键帧。在图理论中，图G＝(V，E)通过去除两部分相连的边，被分解为不相交的集合A和B，A∪B＝V，A∩B＝φ。两部分相异程度等于去除边的权重和，此相异程度称为分割(cut)，即为 其中w(i，j)为两点之间边的权重，图分割理论被广泛应用于图像分割等领域——通过最小化分割值得到图像的最优分割。本文定义权重如下：

[0041]

[0042]

[0043] 其中，sim(i，j)和|fj-fi|分别代表第i帧和第j帧亮度相似值和时域距离，k是一个常数。P是两帧相同亮度等级的集合，Hi(u)，Hj(u)分别是第i帧和第j帧在亮度u等级上的归一化直方图的值。从式(2)可以看出，权重的计算充分考虑了视频的时空因素，两帧在时间轴上的距离越远，两帧之间距离越大，同时，两帧的亮度相似值越大，两帧之间的距离就越小。这与实际情况是相吻合的。

[0044] 利用归一化图割理论来最优的得到视频分割的二叉树。二叉树的每个叶节点对应于视频的一个簇，在每个簇中选取固定数量的帧作为关键帧，选取方法如下：

[0045] 对第m个簇中，计算簇内每帧的平均四阶累积量，记为cm，则该簇内所有帧的平均四阶累计量构成序列{cm}1×N，N为簇的数目。计算该序列的均值和方差，分别记为μm和σm，选取该簇中平均累计量约等于μm，μm+σm和μm-σm的三类帧作为关键帧。

[0046] 关键帧的数目和二叉树叶节点的数目以及每簇中选择的帧的数目有关，假设二叉j树共有j层，每簇中选择的帧数为n，则共有n·2 个关键帧。

[0047] (3)视频指纹的生成

[0048] ①视频关键帧前景提取

[0049] 视频的前景内容反映了视频的主要信息和人关注的区域，对基于内容的视频应用来讲，首要任务就是把视频分成运动前景和背景，而前景内容反映了视频的主要内容，对于视频指纹技术来说，准确有效地提取视频的前景内容作来生成视频指纹是非常重要的。

[0050] 本方案采用能量函数优化，并结合网络图中的图割理论来实现视频前景内容的分割。

[0051] 首先，对视频关键帧进行马尔科夫随机场建模，对于视频前景分割问题，设V为视频帧所有像素点的集合，D表示该帧像素值的集合，L＝{0，1}为标号集，0和1分别代表视频的前景和背景，把L中标号以概率P分配给V，构成一个马尔科夫随机场，设像素点vi的标号为xi∈L，所有像素点的标号组成了马尔科夫随机场的一个组态x，一个组态对应于该*帧的一个分割。视频前景的最佳分割就是寻找一个最优组态x，使后验概率P(x|D)最大。
在实际应用中概率P很难确定，根据Hammersley-Clifford定理描述的马尔科夫随机场和Gibbs分布的关系，可以用Gibbs分布来描述P，且 其中E(x)是一个能量函数。根据Hammersley-Clifford定理，视频帧前景分割问题可以转化为如下能量优化问题。

[0052] x*＝argminE(x) (4)[0053] 能量函数做如下定义：

[0054]

[0055] 其中h(xi)代表被分配标号点的能量，g(xi，xj)代表有边相连的两点之间的能量。

[0056] 此优化问题的解即为视频帧的前景和背景的最优分割。

[0057] 其次，利用图割理论解决能量优化问题。图G(V，E)是具有非负权重的网络图，具有两个特殊节点s，t，分别称为源和汇。一个s-t割即把顶点集合V分为两个不相交的集合S，T，其中s∈S，t∈T。s-t割的容量记为c(S，T)。

[0058]

[0059] 其中wij是边(i，j)上的权重，具有最小容量的s-t割称为最小割。，能量函数E(x)与标号组态x的s-t割容量相对应。对能量函数E(x)最小化问题也就等价于求此网络图的最小割容量，这个问题用经典的图论算法就可以解决。

[0060] ②计算前景图像的四阶累积量

[0061] 对于不改变视频内容的攻击可以建模成一高斯过程，而高阶累积量具有去高斯性，因此选择高阶累积量作为视频高维空间的特征是具有很强鲁棒性的，本发明取四阶累积量作为高维特征。

[0062] (4)视频指纹的计算

[0063] 对于含有w×h个像素的帧，可以得到w×h个累积量系数，这个数目可能会非常大，为减少计算量，本发明对累积量系数进行离散余弦变换(DCT)变换，取较大的20个系数作为特征。记所有关键帧前景图像累积量的较大的20个DCT系数组成的向量为F＝{fm}。

[0064] 本发明中的视频指纹有两部分指纹组成，分别是匹配标签s和二值化序列h。向量F的峭度s作为匹配标签。峭度的定义如下：

[0065] kurt(z)＝E(z4)-3{E(z2)}2 (7)[0066] 其中，E(·)表示数学期望，z为零均值的随机变量。实际应用中，许多信号如图像、语音等都是非高斯信号，而伴随的加性噪声一般是高斯的。而高斯随机变量的峭度为0，因而利用峭度信息可以提取淹没在高斯噪声中的有用信号，利用峭度作为匹配标签性具有一定的鲁棒性。

[0067] 二值化序列h由二值量化向量F来表示。首先生成一个范围在[0，1]，零均值服从均匀分布的随机序列p＝{pm}作为密钥，根据式(8)，生成哈希序列h＝{hk}。

[0068]

[0069] 其中θ为阈值，计算方法如下：

[0070] θ＝median(|fm*pm|)1≤m≤N-1 (9)

[0071] 视频指纹K由匹配标签s和二值化序列h两部分组成，即K＝{s，h}。

[0072] (5)视频匹配

[0073] 视频指纹匹配是视频认证过程重要的环节之一，本发明按照以下两个步骤实现视频指纹的匹配。

[0074] 第一步，对于待测视频指纹，首先根据匹配标签，在视频数据库中搜索，得到一个候选匹配指纹集合作为可疑匹配视频组，大大缩小了匹配的范围。

[0075] 第二步，在候选匹配指纹集合里，利用视频指纹序列的二值序列对视频指纹进行精细匹配，以错误码元数作为两个视频的距离，然后计算误码率若误码率小于给定阈值，则说明两个视频中其一为拷贝。

[0076] 下面的仿真试验是本发明方法的一个具体例子，通过此例可对本发明方案的性能进行验证。

[0077] 把该方法应用于图(3)(a)所示视频“Football.avi”，设定一个阈值t＝0.2(误码率的阈值，即差错的数目除以码数)，若待测视频与原始视频的哈希序列相比误码率小于t，则说明待测视频是原始视频的一个拷贝，为证明本发明方法能够提高鲁棒性，各种攻击下视频拷贝检测的效果如表1所示。表1体现了在不同攻击下的视频检测误码率。仿真结果也证明了本发明方法的鲁棒性和精确性。

[0078] 表1

[0079]攻击方式 最小误码率
模糊 0.076
噪声 0.023
背景替换 0.034
帧旋转 0.061
Logo嵌入 0.035
放缩 0.046
码率改变 0.13
帧丢弃 0.053
黑框边界 0.121