一种基于SimHash的海量视频检索方法

楚敏南++罗新高++白煜华

摘 要：针对海量视频检索，提出了一种基于SimHash的视频相似性检索方法。该方法的视频特征提取部分首先采用视觉词袋模型将视频关键帧表示为词袋模型向量，然后对高维词袋模型向量建立鲁棒的压缩二值SimHash签名；视频相似帧查找部分首先置换SimHash签名库，并排序得到多张签名表，然后在多张签名表中按照数据量合理利用Bloom Filter算法精确匹配签名表的置换部分，进而根据精确匹配的结果高效查找汉明距离小于阈值的签名，最后利用查找到的签名对相关视频进行相似度计算，排序得到相似视频的查询结果。针对CC_WEB_VIDEO公开数据集的实验表明，该方法对大规模视频的快速检索是非常有效的。

关键词：视频检索；视觉词袋；SimHash；Bloom Filter

中图分类号：TP391.41 文献标识码：A DOI：10.15913/j.cnki.kjycx.2015.18.009

目前，国内外的视频分享网站发展迅速，越来越多的人通过视频分享网站、数字电视和微博等方式收看网络视频节目，并通过视频网站上传自制视频与他人分享，网络视频点播量和观看人数呈爆发式增长态势。因此，如何对海量视频进行快速、有效的相似性检索逐渐成为研究热点。

视频相似性检索的过程为：将视频表示为视频关键帧序列→提取关键帧序列的特征→通过特征匹配完成相似性检索。在大规模视频数据库的条件下，需要高效、快速的特征匹配算法以满足视频检索的实时性要求。目前，具体可采用以下6种方法：①引入min-hash算法对视觉词汇建立min-hash签名，并在检索视频片段时采用滑动窗口依次匹配。②基于梯度方向重心的特征，使用kd-tree查询候选帧，然后匹配特征序列。③基于层次的匹配算法匹配HSV的颜色直方图。对于无法确定是否相似的视频，可匹配局部特征。由于该方法需要确认局部特征，所以，难以满足实时性的要求。④基于LBP（Local Binary Pattern）与条件熵的时空特征方法。虽然该方法考虑了视频数据处理规模过大的问题，但使用倒排索引的方法召回视频存在内存占用过大和返回速率低的问题。⑤基于LSH（Locality-sensitive hashing）算法，结合SURF（Speeded Up Robust Features）的特征，以投票的方式查找相似视频片段。⑥利用LSH对高维向量进行相似性检索，并在P2P（peer-to-peer）环境下实现分布式检索。该方法可应用于需多次检索的海量视频数据库。由于每次检索都必须在节点间进行多次查询，所以时间复杂度过高。

鉴于此，本文提出了一种基于SimHash算法的海量视频快速检索方法。该方法首先提取了视频关键帧的SURF特征，并得到BOVW（bag of words，视觉词袋模型）向量，然后通过SimHash算法建立视频的鲁棒二值签名，并在汉明距离检索中利用Bloom Filter算法进行高效匹配，最终得到相似视频。实验表明，该方法对大规模视频数据库的快速检索非常有效。

1 总体设计方案

本文中提出的方法的总体设计方案如图1所示。整个框架分为2个步骤：①构建视频索引，如图1中的实线所示。通过对特征的提取，将目标视频表示成Bovw特征向量，然后利用SimHash建立特征向量的签名，生成基于Bloom Filter的签名表。②查询相似视频，如图1中的虚线所示。经过特征提取，将查询视频表示为Bovw特征向量，利用基于Bloom Filter的SimHash签名表检索与查询视频对应帧相似的帧集合，根据返回的相似帧进行视频相似度计算，最后重新排序得到相似视频的查询结果。

图1 总体设计框图

2 基于SIMHASH的海量视频检索方法

2.1 视频关键帧的Bovw特征

在视频检索中，要先对视频库建立索引，设目标视频库中有M个视频，对于视频Vi，1≤i≤M，本文先按固定时间间隔（1 s）提取视频关键帧，然后去掉相似度比较大的相邻视频帧，同时，保留每个视频帧的时间序列信息。在此情况下，1个视频帧可表示为e={序号，时间戳，视频帧图像名，视频帧图像}。特征表示部分采用BOVW模型为视频关键帧，进而建立“视觉词库”。由于图像中的特征点和视觉词袋中的视觉词汇并不像文档中现成的单词是直接可见的，因此，需要对图像进行特征提取和通过聚类得到视觉词汇，具体过程如下：①利用SURF算法提取视频关键帧的SURF特征点；②将所有SURF特征点集合在一起，然后使用Kmeans聚类算法对SURF特征点聚类，将相似的点聚成“视觉字典”，生成由N个视觉词汇组成的视觉特征字典；③将从所有关键帧中提取的所有SURF特征划归到最接近的图像视觉字典对象中，从而将视频关键帧映射成1个N维的视觉词袋向量，而视频Vi可表示为多个N维向量的集合。

2.2 构建SimHash签名

为了高效地检索视频片段，本文利用SimHash建立视频关键帧的BOVW向量签名。将N维的BOVW向量转换为f维SimHash签名S的计算过程为：①将1个f维的向量V初始化为0，f维的二进制数S初始化为0.②将Surf特征聚类中心的N个向量作为特征，利用传统的Hash算法，在每个聚类中心向量上产生1个f位的签名bi，1≤i≤N.③对于j=1～f，如果b的第j位为1，则V的第j个元素加上该特征的权重。否则，V的第j个元素减去该特征的权重。④如果V的第j个元素>0，则S的第j位为1，否则为0，输出S作为签名。

通过以上方法，视频帧可表示为e=（viedo_name，id，time_stamp，SimHash）。其中，viedo_name为视频名；id为此关键帧在视频中的序号；time_stamp为视频帧时间戳；SimHash为该视频帧Bovw向量的签名。

2.3 基于Bloom Filter的汉明距离检索

Bloom Filter是一种快速、高效的匹配算法，其通过k个哈希函数将要存储的变量a映射到m位的容器中。通过上述操作，可快速检测某一条数据元素是否为集合中的成员之一。由此可见，Bloom Filter算法是通过牺牲出错率来换取时间和空间的。在此算法中误判的概率为：

. （1）

式（1）中：n为数据集中元素的个数；k为哈希函数个数；m为分配位向量的大小。

对于两个视频帧，生成L位的SimHash签名后，如果汉明距离≤K，则认为这两个视频帧相似。而查询一个L比特的签名在签名库中是否存在最多K比特不同的签名，这被称为汉明距离问题。基于网页爬虫应用提出了一种汉明距离的查询方法，主要解决重复网页检测问题。建立索引和利用汉明距离的具体步骤如下：

第一步，构建索引。将L位的签名分成r段，r≥K+1，在

签名库建立t张签名表T1，T2，…，Tt，其中， ，每张

签名表关联两个量，即整数bi与置换πi.初始化Bloom Filter结构中为m位的向量，存储n个元素值，对于表T1中的所有签名，将前bi比特的数据生成Bloom Filter结构BFi，因此，t张签名表会对应t个Bloom Filter结构。

第二步，汉明距离检索。对于查询签名sq，可在t张签名表中检索查询SimHash签名。

Input为查询签名sq、t张SimHash签名表T1，T2，…，Tt和t张SimHash表对应的Bloom Filter结构BF1，BF2，…，BFt.

Output为汉明距离在K以内的SimHash签名列表。具体列表如表1所示。

表1 明距离在K以内的SimHash签名列表

1 for j=1～t

2 sq按πj进行置换得到πj（sq），其前bj位为bj_bit，Q集合清空

3 if BF1.contains（bj_bit）=O then next j

4 for each element sx in Tj do

5 if High_bj_bit_equals（sx，πj（sq））then Q+=sx

6 end for

7 for each element sx in Q do

8 if Hamming_Distance（sq，sx） K then Result+=sx

9 end for

10 end for

11 return与sq签名的汉明距离在K以内的集合Result

表1中的3主要使用Bloom Filter算法过滤不在签名表集合中的数据；4～6可实现二分查找；7～9可计算汉明距离在K以内加入的Result集合。

2.4 视频的相似度计算

对于待查询的视频，在提取视频关键帧后，提取关键帧的Surf特征，建立词袋模型向量，构建SimHash签名，根据汉明距离检索得出与之相似的视频关键帧，并将相似关键帧按照所属视频统计，计算最终的视频相似度。视频Vi与Vj的相似度采用如下公式计算：

. （2）

式（2）中：KFi和KFj为视频Vi和Vj提取到的关键帧数目；KFi∩KFj为视频Vi与Vj相似关键帧的数量，即通过汉明距离检索得出相似视频关键帧的数目；sim（Vi，Vj）为两个视频的相似度，∈[0，1]，通过计算相似视频关键帧数量占总关键帧的比例计算，其值越高，表示两个视频越相似。

3 实验结果

本文的实验环境如下：硬件采用Lenovo台式机，处理器为Intel Core i3-2130，CPU主频为3.40 GHz，内存为4 G。实验数据集选择CC_WEB_VIDEO，包含12 790个视频，其中，查询视频有24个。视频检索常用的评估参数为查全率R、查准率P和F值，其计算方法如下：

. （3）

. （4）

. （5）

首先分析SimHash中的L和K进行，在L和K不同情况下的F值如图2所示。

图2 L和K不同情况下的F值

由图2可知，当L=64，K=4时，F值为0.933，为最大值，因此，取L=64，K=4.由于r≥K+1，所以，64位的SimHash签名至少分成5段，则b1=13，b2=13，b3=13，b4=13，b5=12，签名表的个数t=5.签名表对应的Bloom Filter结构具体分析如下。

对于b1，b2，b3，b4，对应段最多可能出现的情况为213=8 192，而b5=12，则最多出现212=4 096.如果存储元素的个数n=8 192，分配位向量为m，哈希函数k个，则误判率Perr的关系如表2所示。

表2 不同m，k情况下的误判率Perr

m 单位/KB Perr k

10 000 1.220 703 0.559 1

20 000 2.441 406 0.319 2

30 000 3.662 109 0.175 3

40 000 4.882 813 0.097 3

50 000 6.103 516 0.054 4

由表2可知，Bloom Filter设置为m=50 000（6.1 KB），误判率Perr为0.054，k设置为4，多消耗内存30.5 KB。

对于上述算法，二分查找的时间复杂度为O（bi），即O（13）。因此，Bloom Filter的时间复杂度为O（4），当查找的前bi比特能精确匹配时，时间复杂度为O（17），否则为O（4）。如果精确匹配的比例为P，则时间复杂度为O（17）×p+O（4）（1-p）=O（13）p+O（4）

表3 设置Bloom Filter检索效果对比

视频数 关键帧数 设置BF耗时/ms 不设置BF耗时/ms

5 8 510 5 7

10 17 020 7 11

100 170 200 49 86

500 851 000 202 377

由表3可知，设置Bloom Filter能明显提高视频检索效率。当视频数在5以下时，检索效率提高不明显；检索视频数为500时，检索效率能提高86%.

下面将本文提出的方法（L=64，K=4）与基于LBP（Local Binary Pattern）的时空特征方法和基于LSH对SURF特征投票查找相似视频片段（SURF-LSH）的方法相比较。采用LBP和SURF-LSH作为对比对象是因为这两种方法比其他方法有更高的查全率和准确率，对比结果如图3所示。

图3 平均查全率、查准率对比曲线

由图3可知，采用LBP时，当查全率>0.7时，准确率明显下降。本文按时间间隔每秒提取视频关键帧，并采用鲁棒的SURF特征构建词袋模型向量，保证了较高的准确率和召回率。

采用SURF-LSH的准确率略高于本文提出的方法，这是因为本文提出的方法采用的是SimHash算法，它在保证检索效率的同时，比SURF-LSH降低了一定的准确率，但通过图4中平均检索时间与视频数量的关系可发现，对于海量视频检索，本文提出的方法更有效。随着视频个数的增加，检索时间也会随之增加，LBP和SURF-LSH的增长速度明显快于本文提出的的方法。

4 结束语

随着海量视频的出现，快速、高效的视频相似性检索变得越来越重要。本文提出了一种基于Bloom Filter算法进行汉明距离检索的方法，该方法可查找SimHash签名库所有签名中汉明距离在K以内的签名，并将所有Bloom Filter结构汇总在一起，组成类似BitMap的结构。因此，在最终查询汉明距离时，只计

算BitMap的并集即可。本文在CC_WEB_VIDEO视频数据集中对上述方法进行了检验，测试结果表明，该方法能将匹配效率提高1倍以上。今后，我们将构建更大规模的视频数据库，并结合分布式处理平台Hadoop实验。

图4 平均检索时间与视频数量的关系

参考文献

[1]Shen Heng tao，Liu Jia jun，Huang Zi.Near-duplicate video retrieval： current research and future trends[J]. IEEE Multimedia，2013，PP（99）：1-10.

[2]Chiu CY，Wang HM.Time-series linear search for video copies based on compact signature manipulation and containment relation modeling[J].IEEE Transactions on Circuits andSystems for Video Technology，2010，20（11）：1603-1613.

[3]Chiu CY，Wang HM，Chen CS.Fast min-hashing indexing and robust spatio-temporal matching for detecting video copies[J].ACM Transactions on Multimedia Computing，Communications，and Applications，2010，6（2）：1-23.

[4]Lee S，Yoo C D.Robust video fingerprinting for content-based video identification[J].IEEE Transactions on Circuits and Systems for Video Technology，2008，18（7）：983-988.

[5]Bloom B.Space/time tradeoffs in Hash coding with allow-able errors[J].Communication of the ACM，1970，13（7）：422-426.

〔编辑：张思楠〕