0x00 导言

文章地址：Visual Geometry Group - University of Oxford

我的批注版地址：Commented Paper

本文旨在解决在大规模图像数据集中依据给定图片做快速（准实时的）目标检索。

0x01 背景知识

此前解决此类问题，有一个标准的方法：首先，使用词袋模型（BoW）来表示一张图片。其次，使用TF-IDF（Term Frequency Inverse Document Frequency）算法计算一个Rank值用于对图像进行排序和召回。

传统的方法有如下几个痛点：特征提取中的丢失，噪音点，描述子比较标准（距离计算方法）不合适，量化或归一化描述子时带来的损失。

0x00 TF-IDF（Term Frequency Inverse Document Frequency）

TF-IDF（Term Frequency Inverse Document Frequency），中文即：词频逆文本指数，是一种用于信息检索的加权技术。这是一种统计方法，用于评估一个词对于一个文件集或者一个语料库中某一份文件的重要程度。字词的重要性与它在文件中出现的次数成正比，与它在语料库中出现的频率成反比。这点其实很好理解，像the, this, that这样的英文词，在文章中很容易大量出现，在语料库中出现的频率也会很高，但是对于文章而言肯定不是最重要的。

在文件djd_j中，某一特定词语tit_i的词频tfij\text{tf}_{ij}可以表示为：

tfij=ni,j∑knk,j\text{tf}_{ij}=\frac{n_{i,j}}{\sum_kn_{k,j}}

其中，ni,jn_{i,j}为这个词在该文件中出现的次数，而分母则是该文件中所有词在该文件中出现次数之和，也就是该文件的词数或字数。

该词的逆向文件频率idfi\text{idf}_i可以表示为：

idfi=log⁡∣D∣∣{d:ti∈d}∣\text{idf}_i=\log\frac{|D|}{|\{d:t_i\in d\}|}

其中，|D|为语料库中的文件总数，∣{d:ti∈d}∣|\{d:t_i\in d\}|为包含该词语的文件数目。

由此，我们就得到了词频逆文本指数的计算公式：

tfidfi=tfi,j⋅idfi\text{tfidf}_i=\text{tf}_{i,j}\cdot\text{idf}_{i}

一个文件内的高频词以及在所有文件集合中的低文件频率，可以产出高权重的TF-IDF指数，因此，其倾向于过滤掉常见的词语，保留重要的词语。

0x01 Query Expansion

Query Expansion即拓展查询，是指在检索的过程中，先进行第一次查询，对于其返回的top K个结果，包括查询样本本身，对它们的特征向量求和再进行平均，得到一个新的向量，然后使用这个新的向量再进行一次查询，以达到提高检索召回率的目的。拓展查询对mAP的提升一般在4%-5%左右，一般是有必要的，一是实现简单，而是提升效果还算明显。

0x02 Spatial Verification

基于词袋模型（BoW）的图像检索，是将图像表示为视觉词汇的向量，然后检索时检索具有相同视觉词汇的图像。由于视觉词汇是通过局部特征聚类得到的，丢失了图像的空间特征。如果仅仅使用视觉词汇来判断图像的相似性，则会产生两张图像提取到的视觉词汇比较相似，但其空间信息却不相同的情况，例如：

而空间验证（Spatial Verification）就是为了过滤掉那些仅仅视觉词汇比较相似而空间信息却不相同的检索结果的，对于上图所示的检索，经过空间验证后的匹配结果如下：

0x03 Norm

在机器学习中，我们使用范数来衡量一个矩阵的大小，一般将任意向量x的lpl_p范数定义为：

∥x∥p=(∑i∣xi∣p)1p\left \| \textbf{x} \right \|_p = (\sum_{i}\left | x_i \right |^p)^\frac{1}{p}

则对于欧几里得范数，也就是l2l_2范数，可以表示为：

∥x∥2=(∑ixi2)12\left \| \textbf{x} \right \|_2 = (\sum_{i}x_i^2)^\frac{1}{2}

从几何上，欧几里得范数也可以看做从坐标原点到该向量所确定点的欧几里得距离。

lpl_p标准化，即为它们的原向量除以它们的lpl_p范数的过程，及：

x′=x∥x∥p\textbf{x}'=\frac{\textbf{x}}{\left \| \textbf{x} \right \|_p}

0x02 主要贡献

0x00 RootSIFT

传统SIFT关键点之间的相似度计算采用的是二者之间的欧几里得距离，本文提出了一种替代方案，使用平方根（Hellinger）核函数来替代欧几里得距离。这能极大地提升计算性能，而且不需要额外的存储空间和特征转换成本。这个稍加更新后的算法我们称之为RootSIFT。

0x01 Discriminative Query Expansion

现有的拓展查询方法，就是对返回的前top K个结果取均值然后再进行二次查询，这依据的是在视觉空间上的先验结果。而在这篇文章中，作者使用线性SVM来训练了一个用于二次检索的权重向量。并经试验发现，这可以显著地提升拓展查询的性能，并保持查询的速度。

0x02 Database-side Feature Augmentation

Better matching with fewer features: The selection of useful features in large database recognition problems这篇文章中所提到的数据增强方法已经非常强大了，但是其没有考虑增强特征的空间形态（spatial configuration）。在这篇文章中，作者发现，如果将增强特征的可见性（visibility）也纳入考虑的话，那这一点点的扩展将会对性能产生显著增强。

0x03 方法论

0x00 RootSIFT: Hellinger distance for SIFT

原生的SIFT比较的是描述子之间的欧几里得距离，RootSIFT在上面做了一点小创新，就是使用Hellinger distance来代替欧几里得距离。

我们现在假设，有2个n维SIFT特征向量x和y，因为SIFT特征均为单位欧几里得范数，也就是∣∣x∣∣2=1||\textbf{x}||_2=1，所以他们之间的欧几里得距离的平方就可以推导为：

dE(x,y)2=∑i(xi−yi)2=∑ixi2+∑iyi2−2∑ixiyi=∣∣x∣∣22+∣∣y∣∣22−2x⊺y=2−2SE(x,y)\begin{align*} d_E(\textbf{x}, \textbf{y})^2&=\sum_i(x_i-y_i)^2 \\ &=\sum_ix_i^2+\sum_iy_i^2-2\sum_ix_iy_i\\ &=||\textbf{x}||_2^2+||\textbf{y}||_2^2-2\textbf{x}^\intercal\textbf{y}\\ &=2-2S_E(\textbf{x}, \textbf{y}) \end{align*}

我们将上式中的x⊺y\textbf{x}^\intercal\textbf{y}称作它们之间的欧几里得相似核（similarity kernel），并记作SE(x,y)S_E(\textbf{x}, \textbf{y})。我们现在就要开始着手把这个欧几里得相似核替换为Hellinger Kernel。

对于2个已经被l1l_1标准化的n维向量x和y（∑inxi=1,xi>0\sum_i^nx_i=1, x_i>0），它们的Hellinger Kernel可以被定义为：

H(x,y)=∑i=1nxiyiH(\textbf{x}, \textbf{y})=\sum_{i=1}^n\sqrt{x_iy_i}

通过Hellinger Kernel来比较两个不同的SIFT特征向量，可以通过如下2步简单的代数运算来完成：其一，对两个SIFT特征向量进行l1l_1标准化，此处将l1l_1标准化后的两个向量记为x’,y’\textbf{x'}, \textbf{y'}；其二，给里面的每个数开平方，即：SE(x’,y’)=x’⊺y’=H(x’,y’)S_E(\sqrt{\textbf{x'}}, \sqrt{\textbf{y'}})=\sqrt{\textbf{x'}}^\intercal\sqrt{\textbf{y'}}=H(\textbf{x'}, \textbf{y'})。因此，使用欧几里得距离来比较两个RootSIFT特征就等价于使用Hellinger Kernel来比较两个l1l_1标准化后的SIFT特征：

dE(x’,y’)2=∑i(xi′−yi′)2=∑ixi′+∑iyi′−2∑ixi′yi′=2−2H(x’,y’)\begin{align*} d_E(\sqrt{\textbf{x'}}, \sqrt{\textbf{y'}})^2&=\sum_i(\sqrt{x'_i}-\sqrt{y'_i})^2\\ &=\sum_ix'_i+\sum_iy'_i-2\sum_i\sqrt{x'_iy'_i}\\ &=2-2H(\textbf{x'}, \textbf{y'}) \end{align*}

这个变换可以在比较两个原有SIFT向量时on-the-fly进行（先变换，再计算欧几里得距离），亦可将原有的SIFT特征通过离线计算映射成新的RootSIFT特征。

综合作者在Oxford5K等数据集上做的对比实验，此项改动对mAP的提升大约在5个百分点左右。

作者在discussion环节针对此改进作出了一个解释：此改进是为了缓解对原有SIFT特征计算欧几里得距离的时候容易被大值支配的现象，就比如说，两个1024维的向量，其中有1023个值的差值都为0，只有一个元素的差值为100万，那最终计算出来的欧几里得距离就为100万。但如果引入l1l_1标准化再开根号的话，那这种支配现象就会被显著缩减。RootSIFT是一种方差稳定的转换（variance stabilizing transformation），同时又对小的二元组的值的差异更加敏感。