一种基于视频指纹的视频检索方法研究

1 研究背景随着信息技术的飞速发展，视频已经成为信息传播的最为直观有效的途径。而近年来大型视频分享网站的发展，为人们共享视频提供了更宽广的平台，视频的数据量呈现出指数增长的趋势。庞大的数据量以及视频信息本身的无序性也使得视频的辨别与检索变得越来越复杂^[1]。如何有效的检索大规模的视频信息成为亟待解决的问题。传统的视频检索多采用基于文本的方式，对于数据量较小，视频内容简单的视频数据库，该方法可以实现简单快速的视频检索。然而，这种方式需要人为的对视频进行文字描述，一方面对于数据量巨大的视频数据库，人为描述工作量巨大，效率很低。另一方面，对于相同的视频，每个人对其内容的理解不同，基于文本的视频检索方式在客观性和准确性方面都有缺陷^[2]。基于视频指纹的检索又称为基于内容的拷贝检测（Content-Based Video Copy Detection）是从原始的视频流中提取出来的少量特征。像人类指纹一样，视频指纹具有很强的区分性，作为视频内容的精简数字化表示，可以客观准确的反映视频内容^[3]。基于视频指纹的视频检索技术是提高视频检索效率的有效途径，以此为基础可以实现视频的版权保护、视频管理、过滤与排序、以及媒体追踪等应用。2 国内外研究现状基于视频指纹的视频检索技术的关键在于视频指纹的提取与匹配。视频指纹的提取一般来说需要满足三个性质：(1)指纹具有较强的鲁棒性；(2)指纹具有较高的独立性；(3)指纹提取方法的高效性^[4]。视频指纹的匹配要满足高效性和精确性两个准则。目前视频指纹的提取主要有以下几种方法，通过改进的Harris检测计算图像的角点信息获得图像特征相似度、改进的帧间差异法提取运动特征获得运动特征相似度，根据图像特征相似度和运动特征相似度的调和因子得到视频片段总的相似度^[5]，该方法具有较好的鲁棒性，但运算量较大，检索效率不高，不能满足大规模视频数据库的检索要求；基于亮度结构化质量评估的视频指纹算法^[6]，将视频转码成具有固定帧率、固定尺寸的视频，以16×16的宏块对视频图像进行分割，计算每个宏块的亮度均值并归一化，得到最终的视频指纹。该方法对有损压缩、尺寸缩放、帧率转换、亮度增强和高斯白噪声干扰具有较好的鲁棒性，但对于分辨率以及插图干扰鲁棒性不强；基于小波变换提取的特征参数也可以用来表征视频内容，形成视频指纹^[6]。小波变换的特有性质，能够很好的抵抗几种特殊的干扰，其中小波的线性性质能够抵抗视频的亮度变化干扰，小波的平移不变性，可以用来处理图像的剪切操作，小波的伸缩不变性能够抵抗尺度变换的干扰，然而小波变换对于帧率变换抗干扰能力较差。视频指纹的匹配方法也是影响视频检索系统检准率与漏检率的重要指标。近年来视频指纹的快速匹配一直没有得到很好的解决，特别是当指纹数据库规模较大的情况下。对于视频指纹本身的数据格式及匹配算法的改进是指纹匹配的重点问题。传统的匹配算法首先累计查询视频和目标视频对应帧的子指纹相似度，直到查询视频最后一帧，其中子指纹是指单帧图像生产的视频指纹，若累计的相似度大于阈值，则认为两视频匹配。该算法的优点是匹配精度高，但非常耗时，效率很低^[7]。为提高匹配效率，首先对视频指纹进行便于比较的存储格式处理，一方面根据视频指纹的依赖关系分块存储以缩小指纹规模，另一方面以树形结构进行搜索匹配。这种方法虽然提高了匹配效率，然而对视频指纹的压缩使得视频指纹的独立性下降，匹配的准确率也因此有所下降。要得到好的检索效果，就要使得匹配算法与视频指纹提取算法相协调，充分考虑视频指纹的特征来选取视频指纹匹配算法，才能同时提高查准率和查全率。3 相关算法理论本文提出的基于视频指纹的视频检索算法的基本流程如图1所示：3.1 视频分割在视频分割阶段，将每一段视频根据其内容分割成若干个连续的小片段，便于下一步提取关键帧。针对视频数据库中的每一段视频，首先进行视频采样，设采样频率为K1 ，即每隔 K1帧选取一帧进行下一步运算。对于某个视频片段 X，经过采样获得n帧，为X={x1,x2,...,xn}

。针对采样图像集合X ，首先进行图像之间的相似性度量。本文采用分块色彩直方图来计算图像之间的距离。每帧图像首先被分成了2 x 2 块，针对每一个块，将RGB三个色彩通道分别分成20等份，并分别统计这20等份中的像素个数，从而获得色彩直方图的统计参数。基于RGB三个色彩通道分块直方图计算任意两帧图像中之间的距离：

其中hist_i,_s,_t (p)为第i帧图像在第t分块下s通道中第p个区间的统计值, hist_i,_s,_t (p)为第j帧图像在第t分块下s通道中第p个区间的统计值。根据任意两个图像之间的距离，我们进一步计算两个图像之间的相关性：w(x_i,x_j)=exp(-d(x_i,x_j)?/σ?) (2)其中 σ是计算 的参数w(x_i,x_j)，其取值方法为：σ =0.05 x max{w(x_i,x_j)} (3)接下来，应用归一化分割的方法进行视频分割。为此，需要计算每连续两帧视频之间的归一化分割值，其计算方法由公式4给出：

通过以上过程可以获得以任意连续两帧之间作为分割点的分割度量，如公式8所示：最后将该分割度量值小于-20的位置设置为一个视频分割点，同时将相距不超过4个采样帧的视频分割点合并，以减小错误的分割。3.2 关键帧提取关键帧提取部分是为了选取出最具有代表性的视频帧用于每一个视频片段的描述，旨在减小视频指纹提取过程中产生的冗余信息。经过上述过程对进行视频分割后，对于每一个子视频片段，应用之前计算的分块色彩直方图距离选取与该片段内其他帧最相似的图像作为一个关键帧，即第i个视频片段中第s个分割 Clip_s中的关键帧的选取方法由公式9给出：假设第i个视频片段获得了n_i个关键帧，记为： ，为了进一步体现每个关键帧的重要程度，最终要为每一个关键帧赋予一定权重，其权重通过每个关键帧所在视频分割段长度来决定与视频总长度的比值得到，如公示10所示：3.3 视频指纹提取视频指纹提取部分旨在提取出对该视频内容具有较强描述能力的视频指纹。图2中给出了视频指纹提取的流程图。如3.2所述，对于第i个视频获得的n_i个关键帧 分别进行特征提取。首先进行图像放缩，使得该图像的最长边不超过600像素，使图像尺度的到统一，如图3所示：

图3图像放缩

对缩放后的图像进行密集采样，每个图像获得大概1000左右采样点，并对每个采样点进行SIFT特征的提取，如图4所示。

图4图像密集采样

本文所采用的视觉特征字典是提前训练得到的，视觉特征字典的维数为1024维。对每个采样点的特征进行统计，统计过程中应用语义词袋方法进行描述。为得到独立性较强的视频指纹，本文采用对图像进行多次分块统计的方法，具体是将图像分别分成1*1、2*2、4*4块，每种分块方式为一层，如图5，6所示，从而获得具有分层空间结构的图像特征。然后将每一层获得的特征拼接在一起，每一幅图像可以获得 维的特征

图5图像分层特征提取方法

图6特征统计

对于每一副图像所获得的21504维的视觉特征。进一步应用独立成分分析方法进行特征降维，最终将视觉特征降到200维，记为 ?ea_i,_t{t = 1:n1}，其中n₁=200。用于某一关键帧的描述，对于每个关键帧，都按照以上方法提取视觉特征，最后将得到由关键帧的视觉特征串组成的视频指纹。3.4 视频指纹匹配对于待检索视频，同样先获取关键帧，为了更好的保存其数据内容，并不通过视频分割方法，而是直接采用视频采样获得n_q个代表帧组成的关键帧序列 ，我们令视频采样率为K2 ，即每经过 帧选取一帧作为关键帧。然后用3.3节提到的方法提取关键帧的视觉特征，最终也会得到视频指纹。应用串匹配方法进行视频指纹串的匹配。计算待检索视频Q 中第s个关键帧Kf_q,_s 与基准视频片段 Clip_s中第t个关键帧 Kf_i,_t之间的欧式距离：

d(Kf_q,_s ， Kf_i,_t) =norm（?ea_q,_s ，?ea_i,_t） (11)

式中s =1,... ,n_q ，t=1,... ,n_q， ?ea_q,_s ?ea_q,_s 和?ea_i,_t 分别是关键帧 与 的视觉特征向量，norm( ) 表示求向量 K?_q,_s 和K?_i,_t 之差的2-范数，欧式距离d(Kf_q,_s ， Kf_i,_t) 越小，则表明待检索视频 Q中第s个关键帧K?_q,_s与基准视频片段 Clip_i中第t个关键帧 K?_i,_t间的相似性越大。根据不同的应用需求，阈值T1 可以调整，当 d(Kf_q,_s ， Kf_i,_t) <T1时，认为该两帧完全匹配。只要待检索视频存在一帧与基准视频片段 Clip_i中关键帧Kf_i,_t 匹配，则认为关键帧Kf_i,_t 匹配成功，通过将基准视频中匹配成功的关键帧数比上基准视频的关键帧总数获得基准视频的匹配率。进一步将匹配的关键帧视频指纹串的相似度进行加权，从而获得两个视频序列的综合匹配结果。将匹配的关键帧视频指纹串的相似度进行加权，权值由关键帧所在视频片段的时长获得，加权的目的是为了突出每个关键帧相似度对整个视频序列相似性的贡献不同，关键帧所在视频片段时长越长，其对视频序列的相似性贡献越大，反之贡献越小。由此得到视频序列的相似性，从而获得两个视频序列的匹配结果。权值由公式12得到：其中 Kf_i,_t为基准视频中的第t个关键帧， length(Clip_t)为该关键帧代表的视频分段的时长， length(Video_i)代表基准视频的总时长。若待检索视频的某个关键帧与 Kf_i,_t匹配，则匹配标志flag_t =1 ，否则为flag_t =0 ，该关键帧所代表视频片段与待检索视频某片段的相似度为flag_t x w_k_f(Kf_i,_t) ，那么基准视频与待检索视频总相似度为： ，由此可以得到总的匹配时长为： ，匹配时长与匹配率共同决定待检索视频与基准视频是否匹配。4 实验结果及分析(1) 实验环境设置：视频库是由634个视频组成，视频总时长为36780秒。其中有4个视频作为目标视频，其比特率为570kbps，分辨率为640*480，待检索视频是对目标视频进行的一系列编辑，具体包括：a) 比特率变化：378kbps、768kbps；b) 分辨率变化：320*240、1024*768；c) 拼接：二拼接、三拼接；d) 插图：分别插入不同的干扰图，如图7所示。针对以上几种干扰，帧匹配阈值设为0.08，视频匹配阈值设置为0.5，视频匹配时长阈值设置为20s。(2) 实验结果对于视频总时长为36780(613分钟)秒的视频库，视频指纹的构建时间为45分钟左右，由此可知提取单位时间(每秒)视频的视频指纹所需时间为0.073秒。视频检索的统计结果如表1所示：(3) 实验结果分析本文提出的基于视频指纹的视频检索算法对于比特率变化、分辨率变化、插图、拼接等干扰具有很好的鲁棒性，算法具有很高的检索效率，基本满足实时性的要求。对于所构建的视频库，检准率达到了86.98%，漏检率仅为0.68%。5 小结本文基于视频指纹实现了对大规模视频库的高效准确的检索，对于比特率变化干扰、帧率变化干扰、分辨率变化干扰、插图干扰、视频拼接干扰等外部干扰具有很强的鲁棒新。测试表明，该方法可使检准率达到86.98%，而漏检率只有0.68%，同时本算法具有很快的运算速度，满足实时性的要求。由此可见，本文为大规模视频检索系统的构建提供了理论参考。参考文献[1] Yan R, Hauptmann A G. A review of text and image retrieval approaches for broadcast news video[J]. Information Retrieval, 2007, 10(4-5): 445-484.[2] Petkovic M, Jonker W. Content-based video retrieval by integrating spatio-temporal and stochastic recognition of events [C]. Detection and Recognition of Events in Video, IEEE Workshop on Proceedings, 2001: 75-82.[3] Joly, Alexis, Carl Frélicot, and Olivier Buisson.Robust content-based video copy identification in a large reference database[J], Image and Video Retrieval, Springer Berlin Heidelberg, 2003, 414-424.[4] 张利刚. 基于内容的视频拷贝检测算法的研究[D]. 西安：西安电子科技大学. 2010[5] 段德友，欧阳建权. 一种鲁棒的视频指纹提取和匹配方法[J]. 计算机工程与应用，2011，47(24)：186~190[6] 王大永. 感知视频指纹算法研究[D]. 上海：上海交通大学，2012[7] 闫朝喜. 基于粗细粒度的视频指纹快速检测系统设计与实现[D]. 成都：电子科技大学，2009 编辑：中国新闻技术工作者联合会