Hamming embedding and weak geometric consistency for large scale image search
Hervé Jegou, Matthijs Douze, 和 Cordelia Schmid 在 ECCV 2008 上发表了一篇论文]；这篇论文已被引用 779 次；阅读时间为 2015 年 4 月 6 日至 7 日左右。
文章三大贡献：
- 可将bag-of-features视为一种投票机制，并通过数学表达式的形式化地描述匹配过程。
- 我们设计了一种称为Hamming Embedding的技术，在聚类过程中即使k值较小也能维持descriptors的判别能力。
- 通过弱几何一致性与几何变换先验相结合的方式筛选出不满足条件的匹配点。
一、bag-of-features理解成voting
在match阶段，假设已计算出query image的descriptors，接下来：
s_j=0 代表初始化时与 dataset 中图片 x_j 的匹配度指标设为 0；
对于 query 图片中的每个描述子定义为 y_i 而图片中的每个描述子则定义为 x_{i,j} 其中符号 {g_j} \left( \right) 在当前上下文中暂未明确定义。此处定义函数 f\left( {{x_{i,j}},{y_{{i'}}}} \right) 用于衡量两个描述子之间的匹配程度在未加权的 bag-of-features 模型中该函数可表示为：
f\left( {{x_{i,j}},{y_{i'}}} \right) = {\delta _{q({x_{i,j}}),q({y_i})}}
其中 q\left( x \right) 表示对描述子 x 进行最近邻 kernel 匹配。
上述公式的含义是：在 query 图片中的每个描述子与图片中的每个描述子进行对比，在未加权的 bag-of-features 模型中如果两个描述子的 kernel 匹配则计分增加 1。
这一过程可等价于计算两个 bag-of-features 向量之间的内积在此等式中归一化因子 m' 在检索结果中并未产生显著影响。
然而实验研究表明当归一化因子设为 \sqrt{m'm_j} 时检索性能得到明显提升。
对于带 TF-IDF 加权的 bag-of-features 模型由于在文档库中出现频率较低的词汇通常具有更重要的语义意义而频繁出现的词汇类似于中文阅读中的 "的" 或 "是" 则显得相对不那么重要因此匹配函数应重新定义为：
f\left( {{x_{i,j}},{y_{{i'}}}} \right) = w(x_{i,j}) \cdot w(y_i)
其中权重函数 w(\cdot) 可用于体现不同词汇的重要性差异。
二、Hamming Embedding
在执行k-means聚类时，较小的k值会导致Voronoi单元较大。具体而言，在受到噪声干扰的情况下（即描述子带噪声），该区域内的样本会被正确划分为同一单元的概率较高。然而这反而降低了描述子的区分能力；而当k值较大时，则能够较好地保持描述子的区分能力。尽管如此，在这篇文章中提出了当k较小时一种基于单元内划分机制（称为Hamming Embedding），该方法能够在一定程度上平衡描述子的区分能力和抗噪声性能。2维数据平面的划分示意图如下：
off-line步骤 ，构造正交矩阵并计算HE阈值：
随机生成一个维度为d_b \times d的正交投影矩阵{P}；
使用QR分解的方法生成该矩阵的具体实现方式：
M = randn(d); [Q, R] = qr(M); P = Q(1:d_b, :);
；
对原始数据进行正交变换操作：
\widetilde{data} = P \times data；
；
针对每个原始特征向量确定其对应的核函数或核方法：
q\left( {{x_i}} \right)；
这一过程可借助FLANN算法来实现；
；
计算HE阈值的具体步骤如下：
遍历给定的数量级范围内的所有值，
检查对应的Voronoi单元是否存在描述点，
如果存在，则计算并存储该单元中所有投影向量组件的中位数，
最终得到的HE阈值矩阵具有维度{d_b} \times k，
其中k表示代码本的数量。
on-line步骤 ：
-
对每个descriptor计算x的最近kernel；
-
P \times x，计算投影后的z；
-
计算与对应kernel的HE阈值的Hamming距离h，及各维度上判断大小；
-
如果$h
-
sort(score, 降序)，结果为检索序列。
在实验中并未采用原始的{f_{tf - idf}}({x_{i,j}},{y_i})，而是去掉了tf部分，即
实验发现只考虑IDF项的这种改进，可以得到更高的检索精度。
三、弱几何一致性（Weak Geometrical Consistency）
RANSAC可用于该任务领域，但其计算效率较低。因此通过引入一种基于简单模型的方法来估算匹配对的一致性即利用这些特征中的尺度和方向信息来进行几何一致性估计从而有效地解决RANSAC算法中时间复杂度较高的问题。描述子在提取过程中通常会包含主方向及其对应的尺度信息。当一张图像发生旋转或缩放变化时这些特征将相应地发生一致性变化弱几何一致性方法正是利用这种一致性变化来进行再排序。见图展示的是匹配点主方向角度差的分布情况其中用红色标记标注的匹配点将最终被排除在外。
对上一阶段的结果进行re-ranking，在这一过程中评估两个图像间的相似度能够进一步优化。
涉及两个变量时，在简化处理下将二维转化为一维进行处理，并假设方向差异与尺度差异的变化相互独立，则上述公式可简化为：
在理想条件下，在考虑直方图仅在一个维度上有非零值或仅有少数几个维度上有非零值的情况下，
从直观上看，在相似度较高的图像中所生成的直方图通常会呈现出明显的峰值特征。
于是我们定义相似度得分为通过峰值匹配点进行投票计算的结果。