基于稀疏自动编码器的近重复视频检索

随着互联网的迅速发展，网络上产生了大量的近重复视频，如何快速精确地检测出这些近重复视频成为研究的热点。本文提出了一种基于稀疏自动编码器的视频特征提取模型，用于近重复视频检索。先用稀疏自动编码器提取视频关键帧的特征，然后根据视频间匹配的关键帧数占视频所有关键帧数的比例来度量视频的相似性。实验结果表明所提出的方法取得了较好的检索精度。

【关键词】深度学习 自编码器 网络视频 近重复视频检索

1 引言

随着视频分享网站（如YouTube、优酷、土豆网等）的出现，互联网上的视频数量和种类爆炸性地增长。用户可以通过手机、摄像机制作视频或者从网上获取视频，在做过一些改动后重新发布到网上。根据YouTube 2009年5月的统计数据显示，每分钟大约有20小时的新视频上传到该网站，日均浏览量超过2亿次。而到2012年，每天每秒就有长达一小时的视频上传到YouTube，并且日均浏览量达到40亿次。但是在这些海量的网络视频中，存在着大量重复的或者近似重复的视频。Wu等人通过24个关键词对YouTube、Google Video和Yahoo！ Video三个常用视频搜索引擎的搜索结果进行分析，发现在搜索结果中平均存在27%的重复或近似重复的视频。对于某些特定的查询，重复率甚至高达93%。这些大量重复的视频不仅浪费了存储空间，也给视频的有效管理带来不便。而且，用户在网络上搜索感兴趣的视频时返回过多的重复结果，大大降低了用户体验。因此为了提高网络视频的管理、搜索及浏览效率，高效的视频重复检测方法就显得十分必要。

现有的近重复视频检索方法多分为如下3个步骤：首先，从每个视频中提取一系列的关键帧，用这些关键帧代表一个视频；然后，对每一个视频关键帧采用特征提取算法生成一组特征向量；最后，通过关键帧的特征向量计算视频之间的相似度。关键帧的特征表示又分为两类：全局特征和局部特征，分别对应于不同的视频内容表示算法和相似性度量的选取。

本文提出一種用稀疏自动编码器提取关键帧特征的方法，并将该方法用于近重复视频的检测，取得了较好的检测准确度。

2 相关概念

2.1 深度学习

深度学习的概念由Hinton等人于2006年提出，它是机器学习研究中的一个新的领域，其动机在于建立和模拟人脑进行分析学习的神经网络，它模仿人脑的机制来解释数据，例如图像理解，语音识别和自然语言处理等。深度学习中的无监督学习方法，可以通过对深层非线性网络结构的学习，实现对复杂函数的逼近，从而实现对输入数据的分布式表示，具有从少数样本中提取本质特征的强大能力。

自动编码器（AE） 作为深度学习的基本模型之一，可以捕捉输入数据中的重要特征，使训练后的数据可以无限逼近输入数据。为了学习更复杂的非线性函数，在自动编码器的基础上添加稀疏性约束，得到稀疏自动编码器（SAE），它可以通过学习得到更好的特征表示。

2.2 稀疏自动编码器

稀疏自动编码器是一种无监督的学习方法，通过前向传播构建网络结构，采用梯度下降的方法调整权重，利用反向传播算法实现目标值逼近输入值，它是用于降维和特征提取的神经网络，可以提取数据中最主要的隐藏特征（特征的个数通过隐藏节点数确定）。稀疏自动编码器（SAE）是以人工神经网络为基础构建而成的网络，因此稀疏自动编码器可以认为是一种双层神经网络，第一层是由输入层和中间隐层节点组成的编码层，第二层是由中间隐层和输出层节点组成的编码层，其中编码层输入节点的个数与解码层输出节点的个数相等。

稀疏自动编码器（SAE）的神经网络结构包括有m个节点的输入层x={x1，x2，…，xm}，n个节点的中间隐层z={z1，z2，…，zn}，和m个节点的输出层y={y1，y2，…，ym}。y是通过隐层节点z对x进行的重构，其中隐层的维数比输入层小，即n

其中，相邻两层节点之间边的权重用矩阵w（1）={w（1）11，w（1）12，…，w（1）nm}和w（2）={w（2）11，w（2）12，…，w（2）nm}表示，其中w（1）ji表示输入层第i个节点与隐层第j个节点之间的权重。隐层和输出层的偏置项用b（1）={b（1）1，b（1）2，…，b（1）n}和b（2）={b（2）1，b（2）2，…，b（2）m}表示，其中b（1）j是隐层第j个节点的偏置值。隐层第j个节点的输入值定义为公式（1）：

（1）

其中，每个隐层节点的输出值aj是通过sigmoid激活函数f（z）的线性表示，即f（z）=1/（1+e-z），aj=f（zj）。输出层的值y，可表示为公式（2）：

（2）

3 基于自编码的近重复视频检索

信息检索的任务，是对用户输入的一个对象，按与输入相关程度输出排序后的一系列对象。对于近重复视频检索系统，其步骤如下：

3.1 关键帧抽取

给定视频数据集V，对于数据集中的每一个视频采用基于镜头的关键帧抽取方法抽取关键帧。假设从视频数据集V中抽取了n个关键帧，接下来就是针对这n个关键帧提供的信息做进一步的处理。

3.2 特征提取

用上一步得到的一部分关键帧对自编码器神经网络进行训练，得到训练好的自编码器网络模型。然后，将每一个关键帧作为自编码器的输入，得到编码后的结果，将此结果作为该关键帧的特征表示。

因此，两个关键帧Si和Sj之间的相似性d（Si， Sj）可以使用对应的特征向量的欧式距离表示：

（3）

其中，Fi = （x1， x2，…，xd）和Fj=（y1， y2，…， yd）为两个关键帧的特征向量。

3.3 视频相似性度量

提取视频每个关键帧的特征后，就可以比较两个关键帧的相似性。而两个视频间匹配的关键帧越多，则这两个视频越相似。为了更好地定量分析，对视频的相似性作如下定义：

假設Vq= {Sq1， Sq2，…，Sqm}表示查询视频，包含m个关键帧；Vd= {Sd1， Sd2， …，Sdn}表示数据库中的一个视频，包含n个关键帧。那么视频Vq和Vd之间的相似性R（Vq，Vd）可以表示为：

（4）

当上式超过给定的阈值，则称Vq和Vd是重复视频。其中Sqk为视频Vq中的任意关键帧，|Vq|是视频Vq中关键帧的个数，函数δ（Sqk，Vd）是个逻辑函数，即视频Vd中是否存在与关键帧Sqk相匹配的关键帧，若查询视频Vq中的关键帧Sqk在视频Vd中存在相匹配的镜头，其函数值为1，否则为0，即：

（5）

其中，T为一个给定的经验阈值，即当查询视频Vq中的关键帧Sqk与视频Vd中最相似的关键帧Sdk距离不大于T时，则这两个关键帧相匹配。

4 实验与分析

为了评价本文方法的有效性，在本章中将给出本文方法及一些其他现有方法的实验结果，包括视频数据集和评价方法的介绍。实验表明，本文方法在指定数据集上取得了较好的近重复视频检测效果。

4.1 视频数据集

本文采用的是网络视频近似重复检索所常用的一个公开数据集，即CC_WEB_VIDEO数据集。CC_WEB_VIDEO是由香港城市大学和卡内基梅隆大学提供的。它通过使用24个关键词（“The lion sleeps tonight”，“Evolution of dance”，“Fold shirt”等）在YouTube、Google Video和Yahoo！ Video上搜索并下载得到，一共有12790个视频。对于每组视频，最流行的视频被用做查询视频，然后人工对剩余视频进行标注，即标注成相似的或不相似的。查询关键词和近似重复视频的个数如表1所示。例如对于查询“The lion sleeps tonight”，一共有792个视频，其中有334个视频与查询视频重复或近似重复。

4.2 评价方法

本文中针对上述实验数据采用了查全率-查准率曲线和平均准确率（MAP）两种评价标准。查全率（Recall）-查准率（Precision）曲线是比较常用的一种评价检索结果的方法。查全率也称召回率，指相关的文档检索出的越多越好，也就是返回的结果中相关的个数占全部相关结果的个数；查准率也称准确率，是指检索出的结果中，相关文档的个数越多越好，也就是返回的结果中相关的个数占检索到的所有结果的比例。查全率和查准率的公式分别为：

（6）

（7）

平均准确率（MAP）反映的是系统在检索全部的和主题相关的文档的性能指标。一般情况下，如果系统检索出的相关文档排序越靠前，系统的平均准确率（MAP）就越高；如果没有检索到任何的相关的文档，则MAP值为零。求解公式如下：

（8）

其中，q表示查询集，N表示查询集的个数，mi表示相关文档的个数，Precision（Rij）表示返回的结果中第j个相关文档在返回结果的位置与该文档在返回结果中的位置，即

（9）

4.3 实验结果

为了评价检索效果，本节将对我们提出的方法与现有的典型方法进行比较，即基于HSV颜色直方图全局特征的近重复视频检索方法以及全局特征和局部LBP特征结合的近重复视频检索方法。我们做了三个对比实验，分别是：

（1）基于全局签名的方法（Sig-CH）：该方法使用HSV颜色直方图作为视频关键帧的特征，将一个视频所有关键帧特征的平均值作为该视频的全局签名。在这里简称这种方法为GF方法。

（2）基于局部特征的分层比较方法：该方法首先使用颜色直方图检测出很大概率与被检视频重复的视频并过滤掉极度不相似的视频，在使用基于LBP局部特征的关键帧比较方法检测出其它近重复视频。在这里简称这种方法为HF方法。

（3）基于深度学习稀疏自动编码器的方法：即本文使用的方法。

本文从MAP值和P-R曲线分析算法。MAP值的比较见表2所列，P-R曲线的比较如图2所示。

表2：MAP值的比较

方法 MAP

GF 0.892

LF 0.952

本文方法 0.955

从表2中可以看出，本文方法的MAP值结果最好。从图2中可以看出GF在这些方法中效果最差，本文方法效果最好，LF方法效果次之。

5 结束语

本文利用深度学习中的稀疏自编码器模型，自动地从视频关键帧中学习图像的特征，将学习到的特征应用于近重复视频检测任务上，并将该方法与基于视频全局HSV颜色直方图的方法以及全局特征与局部LBP特征相结合的方法进行了比较。实验表明，本文提出的方法近重复视频检测的效果要优于其它两种方法，具有较好的检索准确性。

参考文献

[1]Wikipedia.YouTube[EB/OL].http：//en.wikipedia.org/wiki/Youtube.

[2]Wu X，Ngo C W，Hauptmann A G，et al. Real-Time Near-Duplicate Elimination for Web Video Search With Content and Context[J].IEEE Transactions on Multimedia，2009，11（02）：196-207.

[3]WU Xiao，NGO C，HAUPTMANNA.CC_WEB_VIDEO：near-duplicate Web video dataset[EB/OL].http：//vireo.cs.cityu.edu.hk/webvideo/.

[4]Hinton G E，Osindero S，Teh Y W.A fast learning algorithm for deep belief nets.[J].Neural Computation， 2006，18（07）：1527-1554.

[5]王雅思.深度学习中的自编码器的表达能力研究[D].哈尔滨工业大学，2014.

[6]Coates A，Ng A Y.The Importance of Encoding Versus Training with Sparse Coding and Vector Quantization[C]// International Conference on Machine Learning，ICML 2011，Bellevue， Washington，USA，June 28-July. 2011：921-928.

[7]Baccouche M， Mamalet F，Wolf C，et al.Spatio-Temporal Convolutional Sparse Auto-Encoder for Sequence Classification[J].Networks，2012， 18（05）.

[8]Coates A， Ng A Y， Lee H. An Analysis of Single-Layer Networks in Unsupervised Feature Learning[J]. Journal of Machine Learning Research， 2011（15）：215-223.

[9]Mukherjee S，Ashish K，Hui N B，et al. Modeling Depression Data：Feed Forward Neural Network vs.Radial Basis Function Neural Network[J].American Journal of Biomedical Sciences，2014.

[10]Needell D，Srebro N，Ward R. Stochastic gradient descent，weighted sampling，and the randomized Kaczmarz algorithm[J].Mathematical Programming，2016，155（01）：549-573.

[11]Yuan J，Duan L Y，Tian Q，et al. Fast and Robust Short Video Clip Search for Copy Detection[C]// ACM Sigmm International Workshop on Multimedia Information Retrieval， Mir 2004，October 15-16，2004，New York，Ny，Usa.2004：61-68.

[12]Wu X，Hauptmann A G，Ngo C W. Practical elimination of near-duplicates from web video search[C]// ACM International Conference on Multimedia.ACM，2007：218-227.

作者简介

王飞飞（1991-），男，安徽省阜阳市人。硕士研究生学历。研究方向为深度学习。

作者單位

合肥工业大学 安徽省合肥市 230009