数据库技术・Ｄａｔａ Ｂａｓｅ Ｔｅｃｈｎｉｑｕｅ 基于稀疏自动编码器的近重复视频检索 文／王飞飞 的视频内容表示算法和相似性度量的选取。 随着互联网的迅速发展，网 络上产生了大量的近重复视频， ｌｎｐｕｔ Ｌａｙｅ￣ｒ ｔｐｕｔ Ｌａｙｅ１＂ 本文提出一种用稀疏自动编码器提取关 键帧特征的方法，并将该方法用于近重复视频 如何快速精确地检测出这些近重 复视频成为研究的热点。本文提 的检测，取得了较好的检测准确度。 出了一种基于稀疏自动编码器的 视频特征提取模型，用于近重复 ２相关概念 视频检索。先用稀疏自动编码器 提取视频关键帧的特征，然后根 据视频间匹配的关键帧数占视频 ２．１深度学习 所有关键帧数的比例来度量视频 的相似性。实验结果表明所提出 深度学习的概念由Ｈｉｎｔｏｎ等人于２００６年 的方法取得了较好的检索精度。 提出，它是机器学习研究中的一个新的领域， 其动机在于建立和模拟人脑进行分析学习的神 经网络，它模仿人脑的机制来解释数据，例如 【关键词】深度学习自编码器网络视频近 图像理解，语音识别和自然语言处理等。深度 重复视频检索 学习中的无监督学习方法，可以通过对深层非 线性网络结构的学习，实现对复杂函数的逼近， 从而实现对输入数据的分布式表示，具有从少 数样本中提取本质特征的强大能力。 １引言 自动编码器（ＡＥ）作为深度学习的基本模 随着视频分享网站（如ＹｏｕＴｕｂｅ、优酷、 型之一，可以捕捉输入数据中的重要特征，使 土豆网等）的出现，互联网上的视频数量和种 训练后的数据可以无限逼近输入数据。为了学 类爆炸性地增长。用户可以通过手机、摄像机 习更复杂的非线性函数，在自动编码器的基 制作视频或者从网上获取视频，在做过一些改 础上添加稀疏性约束，得到稀疏自动编码器 动后重新发布到网上。根据ＹｏｕＴｕｂｅ ２００９年 （ＳＡＥ），它可以通过学习得到更好的特征表示。 ５月的统计数据显示，每分钟大约有２０小时 ２．２稀疏自动编码器 的新视频上传到该网站，曰均浏览量超过２亿 次。而到２０１２年，每天每秒就有长达一小时 稀疏自动编码器是一种无监督的学习方 的视频上传到ＹｏｕＴｕｂｅ，并且日均浏览量达到 法，通过前向传播构建网络结构，采用梯度下 ４０亿次。但是在这些海量的网络视频中，存 降的方法调整权重，利用反向传播算法实现目 在着大量重复的或者近似重复的视频。Ｗｕ等 标值逼近输入值，它是用于降维和特征提取的 人通过２４个关键词对ＹｏｕＴｕｂｅ、Ｇｏｏｇｌｅ Ｖｉｄｅｏ 神经网络，可以提取数据中最主要的隐藏特征 和Ｙａｈｏｏ！Ｖｉｄｅｏ三个常用视频搜索引擎的搜 （特征的个数通过隐藏节点数确定）。稀疏自 索结果进行分析，发现在搜索结果中平均存在 动编码器（ＳＡＥ）是以人工神经网络为基础构 ２７％的重复或近似重复的视频。对于某些特定 建而成的网络，因此稀疏自动编码器可以认为 的查询，重复率甚至高达９３％。这些大量重复 是一种双层神经网络，第一层是由输入层和中 的视频不仅浪费了存储空间，也给视频的有效 间隐层节点组成的编码层，第二层是由中间隐 管理带来不便。而且，用户在网络上搜索感兴 层和输出层节点组成的编码层，其中编码层输 趣的视频时返回过多的重复结果，大大降低了 入节点的个数与解码层输出节点的个数相等。 用户体验。因此为了提高网络视频的管理、搜 稀疏自动编码器（ＳＡＥ）的神经网络结构 索及浏览效率，高效的视频重复检测方法就显 包括有ｍ个节点的输入层ｘ＝｛ｘ１，ｘ２，…，ｘ ），ｎ 得十分必要。 个节点的中间隐层ｚ＝｛ｚ ，ｚ：，…，ｚ ｝，和ｍ个节 现有的近重复视频检索方法多分为如下３ 点的输出层ｙ＝｛ｙ ，ｙ２，…，Ｙ ｝。Ｙ是通过隐层节 个步骤：首先，从每个视频中提取一系列的关 点Ｚ对ｘ进行的重构，其中隐层的维数比输入 键帧，用这些关键帧代表一个视频；然后，对 层小，即ｎ＜ｍ。其模型如图１所示。 每一个视频关键帧采用特征提取算法生成一组 其中，相邻两层节点之间边的权重用矩阵 特征向量；最后，通过关键帧的特征向量计算 ｗ‘’ ＝｛ｗ ”１ｌ，Ｗ ”ｌ２，…ＩＷ‘”ｎｍ｝和Ｗ ＝｛ｗ ｌｌ，Ｗ １２，… 视频之间的相似度 关键帧的特征表示又分为 ，Ｗ（２）ｎｍ）表示，其中Ｗ ｊｉ表示输入层第ｉ个 两类：全局特征和局部特征，分别对应于不同 节点与隐层第ｊ个节点之间的权重。隐层和 １９４・电子技术与软件工程Ｅｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ＆Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ 图１：ＳＡＥ神经网络模型 输出层的偏置项用ｂ“ ＝｛ｂ ｌ，ｂ ，…，ｂ ’ ｝和 ｂ‘ ｛ｂ。 ｌ，ｂ。 ，…，ｂ。 ｝表示，其中ｂ 。是隐层 第Ｊ个节点的偏置值。隐层第Ｊ个节点的输入 值定义为公式（１）： 弓 ” ” （１） 其中，每个隐层节点的输出值ａｊ是通过 ｓｉｇｍｏｉｄ激活函数ｆ（ｚ）的线性表示，即ｆ（ｚ）＝ｌ／ （１＋ｅ。 ，ａｊ＝ｆ（ｚｊ）。输出层的值Ｙ，可表示为公 式（２）： ｙ＝∑略 １ ａｊ＋６ … ＼‘／ ３基于自编码的近重复视频检索 信息检索的任务，是对用户输入的一个 对象，按与输入相关程度输出排序后的一系列 对象。对于近重复视频检索系统，其步骤如下： ３．１关键帧抽取 给定视频数据集ｖ，对于数据集中的每一 个视频采用基于镜头的关键帧抽取方法抽取关 键帧。假设从视频数据集Ｖ中抽取了ｎ个关 键帧，接下来就是针对这ｎ个关键帧提供的信 息做进一步的处理 ３．２特征提取 用上一步得到的一部分关键帧对自编码 器神经网络进行训练，得到训练好的自编码器 网络模型。然后，将每一个关键帧作为自编码 器的输入，得到编码后的结果，将此结果作为 该关键帧的特征表示。 Ｄａｔａ Ｂａｓｅ Ｔｅｃｈｎｉｑｕｅ・数据库技术 表１：利用２４个查询从ＹｏｕＴｕｂｅ、ＧｏｏｇｌｅＶｉｄｅｏ和Ｙａｈｏｏ！Ｖｉｄｅｏ上搜索到的视频集 因此，两个关键帧ｓ 和Ｓｉ之间的相似性 本文采用的是网络视频近似重复检索 出 ｄ（ｓ．，ｓｊ）可以使用对应的特征向量的欧式距离 所常用的一个公开数据集，即ＣＣ ＷＥＢ 篝 表示： ｄ（ ， ）：ｄ（ ，弓）＝Ｊ∑：～ ： ＠ —ｙ ） （３ｊ）／ 其中，Ｆ ＝（ｘ。，ｘ２，…，）【ｄ）和Ｆｊ＝（ｙ ，Ｙ２，…，ｙｄ） 为两个关键帧的特征向量。 ３．３视频相似性度量 提取视频每个关键帧的特征后，就可以 比较两个关键帧的相似性。而两个视频间匹配 的关键帧越多，则这两个视频越相似。为了更 好地定量分析，对视频的相似性作如下定义： 假设Ｖｑ＝｛ｓ ｑｌ，ｓｑ２，…，ｓｑ ｊ表示查询视频， 包含ｍ个关键帧；Ｖｄ＝｛Ｓｄ】，Ｓｄ２，…，Ｓｄｌ，）表示数 据库中的一个视频，包含ｎ个关键帧。那么视 频Ｖ 和Ｖｄ之间的相似性Ｒ（Ｖｑ，Ｖ ）可以表示 Ｒ（Ｖｑ，Ｖｄ）： ＩＶｑ‘ ｌ ４． ）／２ （４） 当上式超过给定的阈值，则称ｖ口和ｖｄ 是重复视频。其中ｓ 为视频Ｖ。中的任意关 键帧，ｌＶ １是视频Ｖ 中关键帧的个数，函数 ａ（ｓ。 ，ｖｄ）是个逻辑函数，即视频ｖｄ中是否存 在与关键帧ｓ 相匹配的关键帧，若查询视频 Ｖ 中的关键帧Ｓｑｋ在视频Ｖ 中存在相匹配的 镜头，其函数值为１，否则为０，即： ）：（１．ｉ ｎｄｈ（…Ｓｑｋ，Ｓａ 。￣ （５） 其中，Ｔ为一个给定的经验阈值，即当查 询视频ｖ口中的关键帧Ｓｑｋ与视频Ｖｄ中最相似 的关键帧Ｓ 距离不大于Ｔ时，则这两个关键 帧相匹配。 ４实验与分析 为了评价本文方法的有效性，在本章中 将给出本文方法及一些其他现有方法的实验结 果，包括视频数据集和评价方法的介绍。实验 表明，本文方法在指定数据集上取得了较好的 近重复视频检测效果。 ４．１视频数据集 ＶＩＤＥＯ数据集。ＣＣ ＷＥＢ ＶＩＤＥＯ是由香 （９） 港城市大学和卡内基梅隆大学提供的。它 ４．３实验结果 通过使用２４个关键词（“Ｔｈｅ ｌｉｏｎ ｓｌｅｅｐｓ ｔｏｎｉｇｈｔ”，“Ｅｖｏｌｕｔｉｏｎ ｏｆｄａｎｃｅ”，“Ｆｏｌｄ ｓｈｉｒｔ”等） 为了评价检索效果，本节将对我们提出 在ＹｏｕＴｕｂｅ、Ｇｏｏｇｌｅ Ｖｉｄｅｏ和Ｙａｈｏｏ！Ｖｉｄｅｏ上 的方法与现有的典型方法进行比较，即基于 搜索并下载得到，一共有１２７９０个视频。对于 ＨＳＶ颜色直方图全局特征的近重复视频检索 每组视频，最流行的视频被用做查询视频，然 方法以及全局特征和局部ＬＢＰ特征结合的近 后人工对剩余视频进行标注，即标注成相似的 重复视频检索方法。我们做了三个对比实验， 或不相似的。查询关键词和近似重复视频的个 分别是： 数如表１所示。例如对于查询“Ｔｈｅ ｌｉｏｎ ｓｌｅｅｐｓ （１）基于全局签名的方法（Ｓｉｇ—ＣＨ）： ｔｏｎｉｇｈｔ”，一共有７９２个视频，其中有３３４个 该方法使用ＨＳＶ颜色直方图作为视频关键帧 视频与查询视频重复或近似重复。 的特征，将一个视频所有关键帧特征的平均值 ４．２评价方法 作为该视频的全局签名。在这里简称这种方法 为ＧＦ方法。 本文中针对上述实验数据采用了查全率一 （２）基于局部特征的分层比较方法：该 查准率曲线和平均准确率（ＭＡＰ）两种评价 方法首先使用颜色直方图检测出很大概率与被 标准。查全率（Ｒｅｃａｌ１）．查准率（Ｐｒｅｃｉｓｉｏｎ） 检视频重复的视频并过滤掉极度不相似的视 曲线是比较常用的一种评价检索结果的方法。 频，在使用基于ＬＢＰ局部特征的关键帧比较 查全率也称召回率，指相关的文档检索出的越 方法检测出其它近重复视频。在这里简称这种 多越好，也就是返回的结果中相关的个数占全 方法为ＨＦ方法。 部相关结果的个数；查准率也称准确率，是指 （３）基于深度学习稀疏自动编码器的方 检索出的结果中，相关文档的个数越多越好， 法：即本文使用的方法。 也就是返回的结果中相关的个数占检索到的所 本文从ＭＡＰ值和Ｐ—Ｒ曲线分析算法。 有结果的比例。查全率和查准率的公式分别为 ＭＡＰ值的比较见表２所列，Ｐ—Ｒ曲线的比较 如图２所示。 查样＝ ㈤ 表２：ＭＡＰ值的比较 查准率＝ 返回的相关结果数 方法 ＭＡＰ 平均准确率（ＭＡＰ）反映的是系统在检 ＧＦ ０．８９２ ＬＦ ０．９５２ 索全部的和主题相关的文档的性能指标。一般 本文方法 ０．９５５ 情况下，如果系统检索出的相关文档排序越靠 从表２中可以看出，本文方法的ＭＡＰ值 前，系统的平均准确率（ＭＡＰ）就越高；如 结果最好。从图２中可以看出ＧＦ在这些方法 果没有检索到任何的相关的文档，则ＭＡＰ值 中效果最差，本文方法效果最好，ＬＦ方法效 为零。求解公式如下： 果次之。 Ｍ （ｑ） Ｐｒｅｃ ｎ（％）（８） ５结束语 其中，ｑ表示查询集，Ｎ表示查询集的个 本文利用深度学习中的稀疏自编码器模 数，ｒｎａ表示相关文档的个数，Ｐｒｅｃｉｓｉｏｎ（Ｒ￣）表 型，自动地从视频关键帧中学习图像的特征， 示返回的结果中第Ｊ个相关文档在返回结果的 将学习到的特征应用于近重复视频检测任务 位置与该文档在返回结果中的位置，即 上，并将该方法与基于视频全局ＨＳＶ颜色直 Ｅｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ＆Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ电子技术与软件工程・１９５ 数据库技术・Ｄａｔａ Ｂａｓｅ Ｔｅｃｈｎｉｑｕｅ 方图的方法以及全局特征与局部ＬＢＰ特征相 结合的方法进行了比较。实验表明，本文提出 的方法近重复视频检测的效果要优于其它两种 方法，具有较好的检索准确性。 参考文献 ［１】ｗｉｋｉ ｐｅｄｉａ。ＹｏｕＴｕｂｅ［ＥＢ／ＯＬ】．ｈｔｔＰ：／／ ｅｌ１．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｙｏｕｔｕｂｅ． ［２】Ｗｕ Ｘ，Ｎｇｏ Ｃ Ｗ，Ｈａｕｐｔｍａｎｎ Ａ Ｇ，ｅｔ ａ１． Ｒｅａｌ—Ｔｉｍｅ Ｎｅａｒ—Ｄｕｐｌｉｃａｔｅ Ｅ１ｉｍｉｎａｔｉｏ１３ ｆｏｒ Ｗｅｂ Ｖｉｄｅｏ Ｓｅａｒｃｈ Ｗｉ ｔｈ Ｃｏｎｔｅｎｔ ａｎｄ Ｃｏｎｔｅｘｔ［Ｊ】．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｍｕｌｔｉｍｅｄｉａ，２００９，１１（０２）：１９６—２０７． （ａ）ＧＦ方法 ［３】ＷＵ Ｘ ｉ ａｏ，ＮＧＯ Ｃ，ＨＡＵＰＴＭＡＮＮＡ．ＣＣ—ＷＥＢ— ＶＩＤＥＯ：ｎｅａ ｒ—ｄｕＰｌ ｉ ｃ ａｔ ｅ Ｗｅｂ ｖｉ ｄｅｏ ｄ ａｔ ａ ｓ ｅｔ【ＥＢ／０Ｌ】．ｈｔｔ Ｐ：／／ｖｉ ｒ ｅ ｏ． ｃｓ．ｃｉｔｙｕ．ｅｄｕ ｈｋ／ｗｅｂｖ ｉ ｄｅｏ／ Ｏ ｓ ｎｄｅ ｒｏ Ｓ．Ｔｅｈ Ｙ Ｗ．Ａ ［４】Ｈｉｎｔｏｎ Ｇ Ｅ． ｆａ ｓｔ １ ｅａｒｎｉ ｇｏｒｉｔｈｍ ｆｏｒ ｄｅｅＰ ｎｇ ａ１ｂｅｌｉｅｆ Ｒｅｔ ｓ． ［Ｊ】Ｌ ＣｏｍｐｕｔａｔｉＯｌｌ， Ｎｅｕｒａ ２００６．１ ８（０７）：１ ５２ ７—１５５４． ［５］王雅思．深度学习中的自编码器的表达能 力研究【Ｄ］．哈尔滨工业大学，２０１４． ［６】Ｃｏａｔｅ ｓ Ａ，Ｎｇ Ａ Ｙ．Ｔｈｅ Ｉｍｐｏｒｔａｆｌｃｅ ｏｆ Ｅｎｃｏｄｉｎｇ Ｖｅｒ ＳＵＳ Ｔｒａｉｎｉｎｇ ｗｉｔｈ Ｓｐａｒ ｓｅ Ｃｏｄｉｎｇ ａｎｄ Ｖｅｃｔｏｒ Ｏｕａｎｔｉｚａｔｉｏｎ【Ｃ】／／ Ｉｎｔｅｒｎａｔ ｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ，Ｉ ＣＭＬ ２ ０１ １，Ｂｅ １ ｌ ｅ ｖｕ ｅ， Ｗａ ｓ ｈｉ ｎ ｇｔ ｏｎ，Ｕ ＳＡ，Ｊｕｎ ｅ ２ ８～Ｊｕ１ Ｙ． ２０ｌ１：９２１—９２８． （ｂ）ＬＦ方法 ［７］Ｂａｃｃｏｕｃｈｅ Ｍ，Ｍａｍａｉ ｅｔ Ｆ，Ｗｏｉｆ Ｃ，ｅｔ ａ１．Ｓｐａｔｉｏ－Ｔｅｍｐｏｒａｌ Ｃｏｎｖｏ１ｕｔｉ ｏｎａ１ Ｓｐａ ｒ ｓｅ Ａｕｔｏ－Ｅｎｃｏｄｅｒ ｆｏｒ Ｓｅｑｕｅｎｃｅ Ｃ１ ａ ｓ ｓｉｆｉ ｃａｔｉ ｏｎ［Ｊ】．Ｎｅｔｗｏ ｒｋ ｓ，２ ０１ ２， １８（Ｏ５）． 【８】Ｃｏａｔｅｓ Ａ，Ｎｇ Ａ Ｙ，Ｌｅｅ Ｈ．Ａｎ Ａｎａｌｙｓｉｓ ｏｆ Ｓｉ ｎ ｇＩ ｅ—Ｌ ａ Ｙ ｅ ｒ Ｎｅｔｗｏ ｒ ｋ ｓ ｉ ｎ Ｕｎ ｓｕｐｅｒｖｉ ｓｅｄ Ｆｅａｔｕｒｅ Ｌｅａｒｎｉｎｇ［Ｊ】． １ｏｕｒｎａ１ ｏｆ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ Ｒｅｓｅａｒｃｈ， ２ ０１１（１ ５）：２１ ５－２２３． ［９］Ｍｕｋｈｅｒｊｅｅ Ｓ，Ａｓｈｉ ｓｈ Ｋ，Ｈｕｉ Ｎ Ｂ，ｅｔ ａ１． Ｍｏｄｅｌｉｎｇ Ｄｅｐｒｅｓ ｓｉｏｎ Ｄａｔａ：Ｆｅｅｄ Ｆｏｒｗａｒｄ Ｎｅｕ ｒ ａ１ Ｎｅｔｗｏ１ ｋ ｖ ｓ。Ｒａｄｉ ａｌ Ｂａ ｓｉ ｓ （ｃ）本文方法 图２：各方法检索实验结果 Ｓｅａｒｃｈ ｆｏｒ Ｃｏｐｙ Ｄｅｔｅｃｔ ｉｏｎ［Ｃ］／／ＡＣＭ Ｓｉ ｇｍｍ Ｉｆｌｔ ｅｒｎａｔｉ ｏｎａＩ Ｗｏ ｒｋ ｓｈｏｐ ｏｎ Ｍｕｌｔｉｍｅｄｉａ ＩｎｆｏｒｍＲｔｉｏｎ Ｒｅｔ ｒｉｅｖａ１． Ｍｉ ｒ ２ ０ ０４，Ｏｃｔｏｂｅ ｒ Ｉ ５—１ ６，２ ０ ０４，Ｎｅｗ Ｍｕｌｔｉｍｅｄｉａ．ＡＣＭ．２００７：２１ ８－２２７ Ｆｕｎｃｔｉｏｎ Ｎｅｕｒａ１ Ｎｅｔｗｏｒｋ［Ｊ］．Ａｍｅｒｉｃａｎ Ｊｏｕｒｎａ１ Ｏｆ Ｂｉｏｍｅｄｉｃａ１ Ｓｃｉｅｎｃｅｓ．２ ０１４． ［１ ０］Ｎｅｅｄｅｌｌ Ｄ，Ｓ ｒ ｅｂ ｒ ｏ Ｎ，ｗ ａ ｒｄ Ｒ． Ｓｔｏｃｈａ ｓｔｉｃ ｇｒａｄｉｅｎｔ ｄｅｓｃｅｎｔ，ｗｅｉｇｈｔｅｄ ｓａｍｐ１ ｉｎｇ，ａｎｄ ｔｈｅ ｒａｎｄｏｍｉｚｅｄ Ｋａｃｚｍａｒｚ 作者简介 王飞飞（１ ９９１－），男，安徽省阜阳市人。硕 Ｙｏｒｋ，Ｎｙ，Ｕｓａ．２００４：６１—６８． 士研究生学历。研究方向为深度学习。 ａ１ｇｏｒｉｔｈｍ【Ｊ】．Ｍａｔｈｅｍａｔｉｃａｌ Ｐｒｏｇｒａｍｍｉ ｎｇ，２０１ ６，１ ５５（Ｏ１）：５４９—５７３． 【ｉ ２】ｗｕ Ｘ，ＨａｕＰｔｍａｎｎ Ａ Ｇ，Ｎ ｇ ｏ Ｃ Ｗ． Ｐ ｒａ ｃｔｉ ｃａｌ ｅｌｉｍｉｎａｔｉ ｏｎ ｏｆ ｎｅａ ｒ— 作者单位 合肥工业大学安徽省合肥市２ ３０００９ ［１１】Ｙｕａｎ Ｊ，Ｄｕａｎ Ｌ Ｙ，Ｔｉ ａｎ Ｑ，ｅｔ ａ１． Ｆａ ｓｔ ａｎｄ Ｒｏｂｕ ｓｔ Ｓｈｏｒｔ Ｖｌｄｅｏ Ｃ１ｉ Ｐ ｄｕｐＩ ｉｃａｔｅｓ ｆｒｏｍ ｗｅｂ ｖｉｄｅｏ ｓｅａｒｃｈ［Ｃ】／／ ＡＣＭ １ｎｔ ｅｆｎａｔｌ ｏｎａ１ Ｃｏｎｆｅ ｒｅｎｃｅ ｏｎ １９６・电子技术与软件工程Ｅｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ＆Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ
