基于感知哈希和切块的视频相似度检测方法

吴 悦，雒江涛，刘 锐，胡钟尹

（1.重庆邮电大学通信与信息工程学院，重庆 400065；2.重庆邮电大学电子信息与网络工程研究院，重庆 400065）

0 引言

视频应用在近年来呈现爆发式增长，但是类似于涉案金额高达2.3 亿元的“2·15”系列电影侵权案的视频侵权行为却层出不穷。由于鉴别视频侵权问题的关键是检测两个视频的相似度，因此只要能够准确检测两段视频的相似度，则能有效支持侵权的鉴别。除了鉴别视频侵权问题外，通过视频相似度检测方法可以得到多张图像帧在时空与信息上的相关性与互补性，以此生成质量较好的融合图片，因此解决视频相似度检测问题也为图像融合的理论研究奠定了良好的基础。

现有的相似视频检测方法主要分为视频层次检测、图像层次检测和音频层次检测三类方法。

在视频层次检测方法中，检测两个视频是否完全相同的最基本的方法就是利用MD5 信息摘要算法［1］，对比两个视频的MD5值是否相等，但是该方法无法检测到篡改后的视频。基于标题、标签和描述内容的检测方式［2-4］则通过人为对视频内容进行高度概括，后续利用机器学习的方法对视频进行分类；但该方法需要大量的人工辅助才能完成，并且由于每个人对视频的理解不同，产生的标签和描述也有所不同，导致最终的鉴别效果做不到客观一致。因此大多数基于视频层面的相似视频研究是通过学习结合外观和时间等特征［5-7］来进行的。例如，文献［5］中结合时间和如颜色、纹理等感知视觉特征以及一个计算索引和查询文档之间逻辑推断的匹配框架；但由于考虑了时间、视觉特征、时间和特征之间的对应关系三方面的因素，所以计算速度比较缓慢，且上述利用深度学习的方法，前期需要大量时间和样本训练网络模型，网络复杂、参数繁多。

在图像层次检测方法中，文献［8］中提出了对图像帧进行基于光流的视频复制移动伪造检测算法；但计算复杂度太大，效率太低。基于视频的图像特征来进行相似视频检测的方法，主要是通过对比视频图像帧的形状、颜色以及纹理［9］等视觉特征；但这一类方法只针对形状、颜色等图像特征相似的视频，如果相似视频更改了原始视频的颜色、形状，则会使得图像帧特征差异大，影响结果的判断。文献［10］中使用密集连接卷积网络来提取关键帧的深度特征，然后使用分类相关分析的特征融合算法来分析提取的参数特征，从而提高检测精度；但是由于该方法没有采用相应的视频数据集进行训练，导致存在一定漏检情况。目前，大部分的基于图像的视频相似度对比方法都是对图像特征进行哈希编码得到图像或者视频指纹，后续对这些指纹进行相似度度量。在多特征哈希（Multiple Feature Hashing，MFH）［11］方法中，作者利用得到的多个特征的哈希码进行加权求和，得到最后的多特征哈希码。文献［12］中通过自学习哈希（Self-Taught Hashing，STH）算法得到代表图片帧的哈希序列，后续使用STH 串的欧几里德空间上的余弦相似度构建局部相似度图，得到两视频相似度；文献［13］中提出了一种基于拉普拉斯算子的特征向量的光哈希（SPectral Hashing，SPH）方法，得到哈希序列之后，利用汉明距离计算两视频之间的相似度。但是多特征哈希、自学习哈希以及光哈希三种方法仅仅使用了各单个特征之间的关系，并没有充分利用多特征之间的关系，因此不同特征表示的联系没有挖掘出来，使得最终的检索效果没有达到最优。

在音频层次检测方法中，主要是通过对比两个视频中的图像联合音频或字幕来获得两视频的相似度。基于频谱可见度图来检测音频相似度［14］的方法通过可见度图的方式，既可捕获信号的谐波含量，同时又对宽带噪声具有弹性，因此可以测量两音频数据中谐波信号的相似性。文献［15］中提到通过深度残差网络对端到端视频进行字幕识别，但是基于识别字幕的相似视频检测方法只能适用于有字幕的相似视频对比。

针对上述方法中的多特征间关系难以建立合适的关联、时间复杂度高等局限性，本文基于对比视频最直接的图像特征，设计出一种基于感知哈希（perceptual Hashing，pHash）［16］和切块的视频相似度快速检测方法，并分别在自己构造的数据集和公开数据集CC_WEB_VIDEO［17］进行了对比实验，验证了该方法有可行性。

1 基于切块和感知哈希的方法原理

动态视频由多个图像帧组成，图像作为视频很重要的一部分，是视频最直观的特征。因此，通过视频中关键图像帧的相似度检测可以判断原始视频和被测视频是否为相似视频。

感知哈希（pHash）算法是使用离散余弦变换（Discrete Cosine Transform，DCT）来得到图片的低频成分从而计算出能代表图片的数字指纹（以下简称指纹），及一个64 位的pHash二进制序列。作为检测相似图片最常用的算法，如果将其应用在检测相似视频上，在n个指纹和m个指纹比较时，最多可能会遍历对比n×m次，无法高效地检测相似视频。因此为了提高现有基于感知哈希视频相似度检测方法的速率，本文在传统的基于感知哈希的视频相似度检测方法［18］中引入抽屉原理［19］的思想，通过切块进而提出一种视频相似度的快速检测方法。该方法的基本思想是通过切块排除完全不可能相似的指纹，减少不必要的对比，从而加快哈希指纹的对比过程。

根据抽屉原理的推广形式，设把n×m+1个元素划分至n个集合(P1，P2，…，Pn)中，其中P1，P2，…，Pn表示这n个集合对应包含的元素个数，则：至少存在某个集合Pi，其包含元素个数值Pi大于或等于m+1。

基于切块的构思，定义两个汉明距离在设定阈值H内的指纹为相似指纹，将一个视频指纹平均切成d个等长的块。根据上述推广，两个相似的指纹至少有d-H块是完全相等的，可以得出：有d-H块完全相等的两指纹有可能相似，但d-H块不完全相等的一定不可能相似，从而排除一些不可能相似的指纹。

对比过程如图1 所示。其中，图1 中倒排索引表中的Value代表某一个组合方式中指纹块的值，Id则代表包含该值的指纹编号。对切分的d个指纹块随机取出d-H块，对这些指纹块组合形成的值构建倒排索引（从值Value 即能找到包含该值的所有的完整指纹Id）。把被测视频的指纹同样切分、随机取出d-H块，去倒排索引里查找这些指纹块组合形成的值是否存在：存在即说明该完整指纹可能与包含其的完整指纹相似，进而把两完整指纹进行对比，汉明距离小于H的即为相似指纹（关键帧）；不存在则说明这两组完整指纹一定不相似，再比较下一指纹块形成的值。

图1 基于切块的快速对比过程Fig.1 Fast comparison process based on dicing

假设按位对比两个指纹所用时间为τ，在切分块数为d、汉明距离为H(H＜d)的已知条件下，对比N个指纹所需的大致时间T如式（1）所示：

需要注意的是，由于指纹在进行切块操作后，形成的是数量不定的不同值，即生成的倒排索引的关键词以及文档的数量也不定，因此所需时间并不是简单的关于时间的线性函数，式（1）仅仅是求出对比N个指纹所需的大致时间。

可以看出，在d＜2 的情况下，T＜N×τ，即能达到比时间缩短的效果。

2 基于切块的相似视频检测方法

基于感知哈希和切块的相似视频检测方法主要包含关键帧提取单元、指纹集生成单元、指纹切块单元、倒排索引建立单元、指纹对比单元以及相似度判定单元。

基于感知哈希和切块的视频比对方法流程如图2 所示。首先利用帧间差分算法来实现视频中的关键帧提取，再利用感知哈希算法来提取关键帧中的指纹，最后通过切块的思想对比指纹，从而计算两个图像帧的相似度可以在图像对比方面判定所给的视频是否为相似视频。

图2 基于感知哈希和切块的视频对比方法流程Fig.2 Flowchart of video comparison method based on perceptual hashing and dicing

2.1 关键帧提取单元

关键帧指的是角色或者物体运动或变化中的关键动作所处的那一帧。高效的视频关键帧提取算法能有效简化处理视频对比问题的计算量。本文采用基于帧间差分的关键帧提取算法［20］对视频的关键帧进行提取。

基于帧间差分的关键帧提取算法流程如算法1 伪代码所示：首先，将所需要对比的视频进行切帧处理得到一个图像帧的集合；接着对集合中相邻两帧的图像进行差分计算，得到平均像素强度；再寻找并提取平均帧间差分强度的局部最大值的图像帧作为视频的关键帧。

算法1 基于帧间差分的关键帧提取算法。

2.2 基于感知哈希的指纹集生成单元

指纹集生成单元的作用是生成能够代表视频的指纹集，该单元的核心就是利用感知哈希算法，通过DCT 将图像从像素域转换为频域，只保留系数矩阵的左上角区域的元素用来计算能够代表图像的哈希值。DCT计算如式（3）所示：

式中：(u，v)代表着像素点的空间位置，e(i，j)是输入图像的像素点，X和Y是e的行数和列数。

详细的感知哈希算法流程如算法2 伪代码所示。为了在保证压缩的图像在保留大多数信息的前提下，简化DCT 的计算过程，提高指纹生成速度，本文将图片尺寸缩小到32×32。得到DCT矩阵后，选取左上角8× 8最能代表图像整体信息的低频成分，通过与DCT 均值比较后，得到最终的64 位图像指纹序列。

算法2 基于感知哈希的图像指纹算法。

通过pHash 算法获得的哈希值只能粗略地获得与平均频率的相对比率，而不能获得真正的低频分量。然而，只要图像的大致结构不被改变，通过该算法获得的指纹就不会改变，因此该算法可以避免颜色直方图和伽马校正的影响。

2.3 指纹切块及倒排索引建立单元

指纹切块单元将感知哈希得到的指纹进行切块操作，平均切成d个等长的块，为后续建立倒排索引做好准备。在确定了汉明距离为H的情况下，对切分后的d个指纹块随机取出d-H块，则共有g个组合方式，计算方法如式（2）所示。

根据倒排索引的结构，针对某一组合方式中的指纹块的值，倒排索引能快速找到包含该值的指纹编号，即对应的若干指纹有相似的可能。因此得到切块之后，对这g个指纹块形成的值构建倒排索引。

2.4 指纹对比及相似度判定单元

指纹对比单元将遍历倒排索引中的元组，找到包含某值的完整指纹，按位比较该值对应的指纹。基于切块的对比算法如算法3伪代码所示。

算法3 基于切块的对比算法。

相似度判定单元中将判定两指纹的汉明距离是否小于阈值H（本文认为汉明距离不大于H的两帧图像是相似的），得到两个视频相似指纹的集合，最后得出两个视频的图像相似度。指纹相似度的计算方式如下：

式中：snum表示原始视频和被测视频中相似指纹个数，n和m分别表示原始视频A指纹和被测视频B指纹的个数。

3 实验结果与分析

为了验证基于切块的相似视频检测方法的有效性，本章将在作者构建的广告数据集上与传统感知哈希的相似视频检测方法进行对比，以验证速度的提升；并在公开数据集CC_WEB_VIDEO［17］上与其他三种主流方法进行准确度和速度的对比。

作者构建的广告数据集中的原始视频主要是由从腾讯视频等视频网站上下载的6 个时长为15～77 s 的广告视频，通过对其添加滤镜、乱序剪辑、添加水印及抽帧等常见视频操作后形成被测视频。

CC_WEB_VIDEO 数据集由12 790 个时长为5 s 到10 min的共800 h的视频片段组成，这些视频是从YouTube 等视频分享网站上下载的。根据搜索的关键词分类，该数据集分为24类。在每一类中，将最流行的视频作为原始视频，其他视频作为被测视频，平均有27%的视频与原始视频重复或近似重复，且每个重复版本都是用户自行上传，没有经过额外的人为操作。

本文将根据文献［21］中提到的查准率P、查全率R以及平均准确率均值（mean Average Precision，mAP）对本文所提方法进行评估：

其中：TP代表正确检测到的相关视频数量，FP代表错检视频数量，FN是漏检视频数量。

3.1 预处理

实验首先针对原始视频和被测视频进行关键帧提取预处理，以降低后续比较过程的时间复杂度。

下面分别以名为“1.mp4”、长为15 s 的原始视频，以及添加滤镜及乱序之后名为“1_1.mp4”、长仍为15 s 的被测视频为例，通过OpenCV 中的VideoCaptrue 函数对视频进行逐帧读取，会在内存中得到一个关于该视频的所有图像帧的集合。接着对图像帧集合按照前后两帧的顺序依次进行差分计算，得到一个平均像素强度的集合；与本文给定的阈值0.6 进行对比，得到一个候选的关键帧集合。最后通过查找平均帧间差分强度的局部最大值确定视频的关键帧。图3 和图4 分别是根据查询视频和被测视频形成的关键帧。

图3 “1.mp4”提取的关键帧Fig.3 Key frames extracted from“1.mp4”

图4 “1_1.mp4”提取的关键帧Fig.4 Key frames extracted from“1_1.mp4”

原始视频所截取的关键帧帧数为21，而被测视频所截取的帧数为25，由此可以看出相比原始视频中375的帧数，为后续的相似帧检测降低了时间复杂度。而两个视频提取的关键帧数量不同，是因为被测视频对原始视频进行了乱序操作，改变了帧的顺序，因此在计算相邻帧间的差分值时存在差异，也就导致两个视频最后得到的帧数量不同。

3.2 视频关键帧指纹生成

本节将对上述的关键帧集合做感知哈希算法以提取关键帧指纹集，用于后续的相似度判定。

3.2.1 感知哈希算法鲁棒性验证实验

除本文使用的感知哈希算法外，图像指纹算法最常见的还有均值哈希算法（average Hashing，aHash）和差值哈希算法（difference Hashing，dHash）。均值哈希是将压缩后的图像的像素点与所有像素的均值做大小比较的二值化处理，得到64位指纹；差值哈希是将压缩后的图像的像素点与相邻像素点做差值计算后进行二值化处理，得到64 位的指纹。将感知哈希与均值哈希、差分哈希两种常用哈希算法进行鲁棒性验证对比实验。

对图5（a）所示的第222帧图片进行添加滤镜、更改尺寸、镜像、伽马校正以及更改颜色直方图共五种操作。在6 块Intel Xeon CPU 配置情况下，得到结果如表1 所示，由表中数据分析可得，虽然感知哈希的耗时明显大于均值哈希和差分哈希，但是在五种操作（特别是在添加滤镜、更改尺寸和镜像）下，相似度都高于均值哈希和差分哈希。因此，综合视频处理最常见的五种操作考虑，本文选取鲁棒性较强的感知哈希算法作为指纹集生成算法。

表1 各算法在不同视频处理操作下的性能对比Tab.1 Performance comparison of different algorithms under different video processing operations

图5 视频处理的五种常见操作Fig.5 Five common operations of video processing

3.2.2 指纹生成

得到上述的关键帧集合后，通过感知哈希算法分别得到两个视频关键帧的指纹。

以图3 中所示的原始视频中的第222 帧与图4 中所示的被测视频中的第93 帧为例，首先将得到的关键帧进行尺寸缩小，在这里为了简化DCT 运算过程，将图像缩小为32×32。接着计算该图像帧的DCT，得到一个32×32的DCT系数矩阵图。得到该DCT 系数矩阵之后，本文只保留在左上角的8× 8大小的矩阵，因为它显示了这张图像的最低频成分。然后对所有的关键帧进行如上的步骤，并且计算DCT 的均值。将根据pHash 算法得到的64 个0 或1 的数字组成一个64 位的整数，即得到帧222 与帧93 的一组指纹，如表2 所示。得到需要对比的关键帧的指纹之后，经计算两帧的汉明距离为2，在阈值7之内，证明这两帧的关键帧是相似的。

表2 帧222与帧93的指纹序列Tab.2 Fingerprint sequences of frame 222 and frame 93

3.3 视频相似度对比结果及分析

为了验证基于切块的相似视频检测方法的有效性，将本方法与传统的基于感知哈希的方法在从网上下载的6 个广告上进行对比，以验证本文方法在速度上的表现；对其他三个常见方法在公开数据集CC_WEB_VIDEO 上进行了对比实验，以验证本文方法在准确度以及速度上的性能。

3.3.1 与传统的基于感知哈希的方法进行对比

由于图像指纹长度为64 位，为了不丢失图像信息，指纹长度需要能被切块数整除，即切块数应为64的因数（即d取值应为2、4、6、8、16、32）。根据经验，汉明距离H≤5 的两张图片为相似度极高的图片。并且根据式（1），d和H越接近，对比时间越短，因此为了保证对比时间并且能够保证检测到大多数相似图像，综合考虑，本实验采用的切块数d=8，汉明距离H=7。根据6组现有广告得到图6的实验结果，可以看出，本文所提出的基于切块的视频相似度检测方法与传统的感知哈希对比方法相比，能够在准确度一致的前提下，缩短约93%的检测时间。

图6 本文方法与传统方法在广告数据集上的性能对比Fig.6 Performance comparison of the propsed method and traditional method on advertising dataset

总体上，感知哈希算法能够较好地实现视频对比的功能，但是可以看到广告3 不管是在传统算法还是改进算法中的相似度都较低，这是因为感知哈希在改变图像锐度、对比度时检测效果不够优良，因此后续还需进一步寻找更优良的指纹生成算法，以适应更多场景下的视频相似度检测。

3.3.2 与其他方法进行对比

本节将在CC_WEB_VIDEO 数据集中的对所有的视频（包含24 类）进行实验，并将本文方法与在引言部分提到的多特征哈希（MFH）［12］、自学习哈希（STH）［13］以及光哈希（SPH）［14］三种常见的相似视频检测方法进行对比。

从图7 可以看出，相比其他三种常见的方法，本文方法在mAP 上有所提高，分别提高了1.4%、2%和2.3%；而相较于MFH 检测平均每一个视频耗时0.553 s、STH 耗时0.623 s、SPH 耗时0.496 s，本文方法仅用了0.418 s，检测时间分别缩短了24%、32%和16%，提高了检测效率。与采用局部特征的对比方法相比，基于切块的视频相似度检测方法是通过计算关键图像帧之间的相似度来计算视频的相似度，因此更能考虑到绝大多数图像帧，从而能够比上述三种方法的平均准确度有所提高；并且由于优化了传统的遍历对比方法，因此检测时间比其他三种常见方法也有所减短，达到了高效检测相似视频的效果。

图7 各方法在CC_WEB_VIDEO数据集上的性能对比Fig.7 Performance comparison of different methods on CC_WEB_VIDEO dataset

本文实验代码和广告数据集已上传GitHub（https：//github.com/jiangtaoluo/video_sim_detect）。

4 结语

针对现有的视频相似度检测技术需求较多但识别效果局限等问题，本文提出了一种基于感知哈希和切块的视频相似度快速检测方法。本文首先通过基于帧间差分的方法提取视频关键帧，再利用感知哈希算法对比提取出来的关键帧，基于切块数量和汉明距离之间的关系构建倒排索引，从而快速得到两个视频图像帧的相似度。最终在保证准确度的前提下，达到快速检测相似视频的目标。但是由于感知哈希在改变图像锐度、对比度时检测效果不够优良，而前期生成指纹的算法的准确度对后续对比有着显著影响，因此寻找一种优良的指纹生成算法将是需要进一步研究的内容。