Negative evidences and co-occurrences in image retrieval: the benefit of PCA and whitening

Abstract

本文讨论了具有短向量表示的大规模图像检索。我们通过主成分分析（PCA）研究降维，并提出了对其不同阶段的改进。我们展示并明确利用了（i）均值减法 and the negative evidence，即在两个被比较的描述中相互缺失的视觉词，（ii）轴去相关系数和共现现象。最后，我们提出了一种通过多个词汇的联合降维来缓解量化伪影的有效方法。所提出的技术很简单，但与紧凑图像表示的最新技术相比，有了显著和一致的改进。图像分类的补充实验表明，这些方法是普遍适用的。

1.Introduction

本文主要解决了文献[1-4]中很多论文都考虑到的大规模图像搜索和目标识别问题。更准确地说，该任务包括在大型图像数据库中根据视觉相似性查找与查询图像最相似的图像。大多数论文依赖于bag-of-words(BOW)表征[1,5,2,3]或其衍生物，如[4]。由于计算或内存的限制，这些方法只能在一台机器上搜索几百万张图像。在本文中，我们将主要关注更可扩展的方法，根据最近在压缩图像表征方面的工作[6 – 8]，其中图像描述是一个短向量，随后使用二值化[6,9]或产品量化技术[10]对其进行压缩编码。在这种情况下，表现最好的方法是那些从局部特征[7,8]产生代表图像的向量的方法，如Fisher向量[11,12,7]或它的非概率版本，即VLAD描述符[8]。与以更直接的方式从像素[13,6]计算出的全局描述技术相比，这些表示在某种程度上继承了计算它们的局部描述符的不变性属性(视点变化、裁剪等)。

生成短码图像表征的方法通常利用PCA[14]进行降维。观察到，通过PCA reduction，BOW的性能甚至得到了改善。本文对这一现象进行了研究。主成分分析可以看作是一个两步过程(1)以数据为中心，(2)选择一个子空间的去相关(正交)基来最小化降维误差。我们展示了每个步骤对检索都有积极的影响，并且我们提供了对这种行为的解释。在此基础上，我们提出了简单而有效的技术，以进一步提高BOW和VLAD表征的质量。首先，我们考虑negative evidence的作用:给定两个BOW向量，两个向量中jointly missing的一个视觉词在相似性度量中应该得到更重要的信息。我们显示了negative evidence与BOW向量中心(均值减法)的关系。其次，通过利用描述符条目的去相关性，BOW和VLAD表征得到了进一步的改进。提出了两种补充的方法 1)对向量空间进行白化，从而解决了co-currence问题; 2)通过联合降维来考虑多个词汇表。现有技术考虑了多个词汇，例如在层次k-means[2]中，或在[15]的rank聚集技术中。相比之下，我们的方法提高了对描述图像的固定大小的向量的搜索精度。在查询索引结构时，内存和计算复杂度与考虑唯一词汇表时相同。

尽管很简单，但我们在四个流行的基准测试中的结果表明，所提出的技术一致地并显著地改进了基于短向量的最先进的图像搜索。最后，我们将通过在PASCAL VOC’07基准上的实验简要说明，更好的检索表征也能转化为更好的分类结果:我们从BOW获得的短向量，并与线性分类器相结合，显著优于与Chi-square kernel相结合的soft BOW。

4.Co-occurrence over-counting: the benefit of whitening

利用主成分分析(PCA)直接对BOW (VLAD)向量[8]进行降维是一种获得更短图像向量表示的有效方法。这首先执行了数据的隐式中心化(即减去均值)，因此考虑了co-missing的视觉词，从而提高了相似度度量。其次，通过集中第一分量的矢量energy，为降维后的矢量之间的相似性提供了投影前相似度的合理近似。我们采用这种方法从BOW和VLAD表示产生短向量。

但值得注意的是，这种盲目降维忽略了一个重要现象，即co-ocurring问题。Chum等人[24]注意到，在比较两种图像向量表征时，co-ocurring会导致对某些视觉模式的over-count。检测器还可以引入一些人工视觉词的co-ocurring，例如，当一个图像区域从不同的方向[25]被多次描述时，产生两个不同但强烈co-ocurring的描述符。

考虑图像全局描述符(BOW或VLAD)的学习集，根据均值中心化，用矩阵Y = [Y1 | … | Yn] 表示。D维协方差矩阵被估计为 C = Y×Y^⊤。在这个矩阵中捕捉到的co-ocurring的视觉词产生了强烈的对角响应，并倾向于出现一个特征向量与一个包含这些值的大特征值相关联。因此，限制co-ocurring影响的一种有效方法是对数据进行白化，就像[26]独立分量分析中所做的那样，并通过Mahalanobis距离隐式实现。