结合稀疏编码和金字塔匹配的视频检索

甘 玲，汪子彧

GAN Ling,WANG Ziyu

重庆邮电大学 计算机科学与技术学院，重庆 400065

School of Computer Scienceand Technology of Chongqing University of Postsand Telecommunications,Chongqing 400065,China

互联网及相关技术的高速发展，使得多媒体信息呈海量增长，传统的文本检索只依赖于标签和短文本信息对视频的描述，因而有着很大的局限性。随着用户对检索需求的提高，基于内容的检索成为了研究的热点。研究基于内容的视频检索（Content Based Video Retrieval，CBVR），重在检索视频本身的内容，并使用视觉基础特征作为相似度度量的依据，从而克服了传统的基础属性和文本检索的不足。

基于内容的检索的难点是“语义鸿沟”问题，即基础特征难以表示高层语义。目前对于使用基础特征描述的视频，图像的区分通常采用金字塔匹配方法[1-5]。金字塔匹配方法的意义在于，通过多粒度划分匹配子集合，就能利用基础特征的组合重现一定的语义信息，从而提高检索的准确性。空间金字塔匹配方法[1]（Spatial Pyramid Matching，SPM）和时空金字塔匹配的方法[3]（Spatio-Temporal Pyramid Matching，STPM）均在此基础上提出。此外，近年一些对重复近似识别（Near Duplicates Identification，NDI）的研究[4-5]均使用了金字塔匹配的思想，解决了诸如此类的相似性度量问题。但大多数方法都着力于研究匹配策略，并不涉及研究在方法中结合改进基础特征的表示。以上大部分方法均采用矢量量化方法作对图像基础特征表示，但该方法在特征重建时，会不可避免地丢失一些重要信息，导致检索效率的下降。目前一些研究已经将源自生物视觉感知研究的稀疏编码技术[6-8]融入上述方法中[9]，用于解决矢量量化特征描述不够准确的问题，本文首次通过结合稀疏编码的SPM和STPM方法进行基于内容的视频检索，取得了比原方法更好的检索效果。

1 金字塔匹配

1.1 SPM和STPM

SPM和STPM均继承了金字塔匹配的思想，前者在金字塔的每一级上将图像按空间分布划分成多粒度的子块，然后在各级的子块之间进行匹配；后者将视频的镜头看成一个时空延展的立方体，并按时空粒度划分金字塔的匹配子集合用于匹配。因为视频特征具有较强的时空相关性，所以STPM方法比SPM更适合度量视频的相似度。

如图1所示[3]，视频在金字塔的L层上被分割为不同粒度大小的立方体，L=0层的金字塔其实就是BoF下的匹配。由图1可以看出，在L=1层，将视频分成2×2×2的子块，在L=2层，视频被分成4×4×4的子块，以此类推。每一层上设置的时空立方体的长、宽、高分别为第0层的立方体长、宽、高的1/2L。匹配从各层的对应子块之间开始，最后通过合并各层的匹配结果得到视频的相似度。

图1 STPM层级示意图

1.2 金字塔匹配核

假设X和Y是D维特征空间中的2个向量集合。同时在0，1，…，L级分辨率上，构造一系列的网格，l级上的每个网格在每一维度上有2l个单元，总共有 D=2dl个单元。令分别代表X和Y在l级分辨率下的直方图，同时i)是X和Y第i个区间中的特征的数量。那么在l级下的匹配可以由式（1）的直方图相交函数给出：

因为在l级上的匹配数也包括了l+1级上的匹配数，所以在l级上新增的匹配数为 Γl-Γl+1，l=0，1，…，L-1。为了削弱在大粒度下发现的匹配，每一层的权值被设置为1/2L-l。综上所述，金字塔匹配核的定义如式（2）、（3）所示：

上述直方图相交和金字塔匹配核均为Mercer kernels[1]。

2 本文方法

2.1 算法思想

本文结合稀疏编码方法用于以SPM、STPM等为匹配引擎的视频检索系统。首先对视频基础特征进行采样，然后用稀疏编码方法训练得到的特征密码本对每个视频的特征进行编码，将编码后特征的前c组显著分量分别做c次STPM或SPM计算，并用稀疏编码计算得到的权值合并这c组匹配，作为修正后的匹配结果。

2.2 视频检索的系统框架

本文的工作均基于时空金字塔匹配下的视频检索系统应用[3]。系统结构如图2所示。

图2 基于内容的视频检索框架

首先构建镜头数据库：对输入的视频进行镜头检测，然后从各个镜头中提出基础特征进行训练、编码。最后使用匹配引擎（如：SPM、STPM等）计算视频的相似度，并将编码结果和匹配结果存入数据库。

当用户输入一个查询镜头时，系统通过匹配引擎进行相似性度量，然后返回前k个最相似的结果。

2.3 矢量量化方法和稀疏编码方法

矢量量化方法和稀疏编码方法，都是为了从大量的基础特征中提取出相对重要的信息用于数据类别表示。

2.3.1 矢量量化方法

假设X表示D维空间中的特征集合，例如：

那么矢量化方法，可以使用K-means算法解决式（4）的问题：

其中，V=[v1，v2，…，vk]T是K-means算法的聚类中心，被称为密码本。这个优化问题，可以被重新写成式（5）中求解最优矩阵因子的问题：

其中，Card(um)=1是基数约束，意味着um中只有一个元素非零；‖‖.是L2范式；||um是L1范式，是um中所有元素绝对值的求和。由上式，可以看出um具有非负性。在训练阶段，式（5）的求解同时依赖于U、V；在编码阶段，使用已经训练好的V，求解U。

2.3.2 稀疏编码方法

对于高维的特征来说，Card(um)=1的基数约束，往往过于严格，常常使得重建的特征丢失了一些重要的信息。针对这一问题，可以适当放宽这一约束，让um能够有多个非零元素。这就是稀疏编码的基本原理，如式（6）所示：

其中λ是一个正则化参数，密码本V通常是一个超完备基向量集(K＞D)，式（6）中没有写上非负约束，原因是um的符号来实现。其中 um+=min(0，um)，um-=max(0，um)。同矢量化方法一样，稀疏编码也需要先进行训练，然后进行编码。

2.4 讨论与应用

本文结合稀疏编码进行视频检索的主要原因是：（1）图像块是稀疏信号；（2）稀疏编码可以表示出图像的显著特征；（3）与矢量化方法相比，稀疏编码能够更精确地对特征编码。

实验中使用文献[6]中的高效求解方法求解式（6）中的优化问题，同时为了将稀疏编码融入基于金字塔匹配的检索工作，本文所使用的投影函数F将um每一列中绝对值最大的前c个分量的序号作为该特征的直方图统计表示，同时对这c个分量的绝对值进行加权平均，作为合并匹配结果的权值。即在获得稀疏编码后的矩阵U以后，使用式（7）计算：

F是定义在um每一列上的操作，如式（8）所示：

zcj表示F从|uj|中取出的第c个显著元素的行序号，wcj表示从|uj|中取出的第c个元素值，uij是U中第i行j列的元素，M是密码本的行数，代表显著局部特征的数量。在实验中，使用Zc做c次SPM、STPM运算，然后使用式（9）中计算得到的权值合并匹配结果。

本文中的实验，从视频的图像块中随机抽取了51 200个sift[10]特征用于训练密码本，然后用该密码本对视频特征进行编码、匹配。

3 实验

本文在UCF50视频数据集上，分别对使用矢量量化方法和结合本文方法的关键帧匹配、SPM、STPM的视频检索做了对比实验。

3.1 实验数据

UCF50是美国中佛罗里达大学收集自Youtube等视频网站的视频数据集。视频按行为划分有50类，如：游泳、跳水、荡秋千等，其中每一类视频均包含了大量特殊场景下的镜头，可以作为本文视频检索的实验数据。在实验中按镜头中的行为和场景选取了复杂场景下的20类视频（每一类10个镜头，共200个镜头）作为本文的实验数据。

3.2 实验评价方法

本文的实验使用文献[3]中的二分法判别评价每次检索返回的结果，用NDCG@k评价整体检索质量。

3.2.1 二分法判别

文献[3]中的二分法判别对每次检索的结果评价，可以分为三种情况：（1）正确；（2）错误；（3）不可分。

假设用户输入一个镜头Q，这个镜头属于一个特定的类别，再假设有两个镜头A、B：A和Q为同一类；B和Q不属于同一类。那么检索返回的结果中，A和Q的相似度应该比B和Q的大，即STPM(Q，A)＞STPM(Q，B)。如果在限定返回的 k个结果中，全部满足 STPM(Q，A)＞STPM(Q，B)，则判定为检索成功；如果有 STPM(Q，A)＜STPM(Q，B)，则判定检索错误；除上述两种情况的其他的情况判定为不可分。

查询返回结果的例子如图3所示。

图3 查询返回结果的例子

图3 为一次查询和返回前5个结果的例子，第一行为从输入的查询镜头中提取的3帧，下面的5列，每一列均取自检索返回的结果的3帧。按照二分法判别，这是一次成功的查询，因为输入查询的是水上摩托艇的镜头，而返回的5个结果中，所有水上摩托艇的镜头按照相似度排序，均在其他镜头（图中其他镜头为：皮划艇，游泳）之前。注意到图2中，也将匹配数结果归一化，作为查询得分。

3.2.2 NDCG@k

NDCG@k（Normalized Discounted Cumulative Gain at top k Ranks）是一种信息检索和测量结果准确率的度量标准。NDCG@k公式如式（10）所示：

NDCG@k将检索得到的1到k个结果用一个评价函数s（p）进行计算。s（p）代表第p个结果的检索效果。在实验中，s（p）的设置和文献[3]相同，根据返回镜头和查询镜头是否在同一类别下，s（p）=1或者0。参数Z是一个用于归一化的因子，它是理想化的DCG（Discounted Cumulative Gain）值。

3.3 实验结果

从每个视频镜头中，提取典型的8帧作为一个镜头的代表（因为在实际应用中，该算法也往往是针对关键帧的集合进行操作），然后对这8帧提取稠密SIFT特征来进行稀疏编码，密码本V的维度设置为200×128（其中，200是一个常规的经验取值，且该维度大于特征维度符合超完备基向量集的条件。128为sift特征描述符的维度）。

用二分法判别对200次查询中每次返回5个结果的统计情况如表1所示。

表1 二分法判别的实验比较结果 （%）

由表1中可以看出分别对关键帧、SPM和STPM使用矢量量化方法和稀疏编码方法进行比较实验。从实验结果可以看出，使用了稀疏编码后，基于关键帧的匹配虽然没有提高检索的正确率，但减少了不可分率。而SPM、STPM方法均增加了检索的准确率。尤其是基于STPM的视频检索，效果显著增强。

图4 每次查询的NDCG@k值

图4 中每一个数据点是200次查询返回k个结果的NDCG@k均值，对使用了稀疏编码方法和矢量量化方法的实验分别用实线和虚线表示。可以看出在k＜10的情况下，使用稀疏编码的STPM、SPM的检索效率均高于使用矢量量化方法时的效率。

4 结束语

金字塔匹配方法给出了一种快速高效的视频、图像检索的解决方案。本文首次结合稀疏编码和金字塔匹配用于基于内容的相似视频检索，在线性时间复杂度增加的基础上，取得了比用矢量量化方法的SPM、STPM更精确的检索效果。在未来的工作中，将会使用更大的数据集（例如：在线数据集）来测试该方法的效率，同时尝试使用合并的一些其他基础特征，提高检索的准确性。

[1]Kristen G，Trevor D.The pyramid match kernel：discriminative classification with sets of image features[C]//ICCV，2005：1458-1465.

[2]Lazebnik S，Schmid C，Ponce J.Beyond bag of features：spatial pyramid matching for recognizing natural scene categories[C]//CVPR，2006：2169-2178.

[3]Choi J，Jeon W，Lee S C.Spatio-temporal pyramid matching for sports videos[C]//ACM Multimedia，2008.

[4]Xu Dong，Chang Shih-Fu.Visual event recognition in news video using kernel methods with multi-level temporal alignment[C]//CVPR，2007：1-8.

[5]Xu Dong，Cham T J.Near duplicate image identification with spatially aligned pyramid matching[C]//TCSVT，2010：1068-1079.

[6]Mairal J，Bach F.Online learning for matrix factorization and sparse coding[J].Machine Learning Research，2010，11.

[7]Mairal J，Bach F.Discriminative learned dictionaries for local image analysis[C]//CVPR，2008：1-8.

[8]Olshausen B A，Field D J.Sparse coding with an overcomplete basis set：a strategy employed by V1[J].Vision Research，1997，37：3311-3325.

[9]Yang Jianchao，Yu Kai.Linear spatial pyramid matching using sparse coding for image classification[C]//CVPR，2009：1794-1801.

[10]Lowe D.Object recognition from local scale-invariant features[C]//ICCV，1999.