Hamming Embedding汉明嵌入

简介

汉明嵌入，针对BoVW的改进。

综合转载以下文章：

• Hamming Embedding 汉明嵌入简介
• Hamming embedding and weak geometric consistency for large scale image search
• 基于局部特征和视觉上下文的图像检索系统
• [TPAMI重磅综述]SIFT与CNN的碰撞：万字长文回顾图像检索任务十年探索历程（上篇）
• Hamming embedding and weak geometric consistency for large scale image search

BoVW理解成voting

在match阶段，假设已计算出query image的descriptors，接下来：

$s_j=0$，表示初始化时与dataset中图片$x_j$的匹配值为0；
对query图片中每个descriptor，记为${y_i}$，对图片${x_j}$的每个descriptor，记为$x_{i,j}$，有

$$s_j = g_j\left({\sum\limits_{i'=1..m'}{\sum\limits_{i = 1..m_j} {f\left( {x_{i,j},y_{i'}} \right)} } } \right)$$

稍后再解释${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)$为描述子的最近kernel。

上步公式的解释：query图片中的每个descriptor与图片$x_j$的每个descriptor进行比较，未加权的bag-of-features中，如果两个描述子的kernel相同则+1。现在考虑${g_j} \left( \right)$，令为归一化操作。可以表示为

$$s_j = \frac{1}{m'm_j}\left({\sum\limits_{i'=1..m'}{\sum\limits_{i = 1..m_j} {f\left( {x_{i,j},y_{i'}} \right)} } } \right)=\sum_{l=1...k}\frac{m_l'}{m'}\frac{m_{l,j}}{m_j}$$

这等价为两个bag-of-features向量之间的内积。这个等式中，归一化因子$m′$没有影响到检索结果。不过实验发现${g_j} \left( \right)$令为除以$\sqrt{m’m_j}$可以得到更好的精度。

对于TF-IDF加权的bag-of-features，认为在所有文档中出现的次数低的相对而言是重要的，出现的很多的证明类似于文本检索中的“的”、“是”等相对而言重要性很低，匹配函数可以重新定义为

$$f_{tf-idf}(x_{i,j},y_i)=(tf-idf(q(y_i)))^2\delta_{q(x_{i,j}),q(y_i)}$$

$tf-idf$代表权重。

Hamming Embedding

在k-means聚类时，k较小时Voronoi cell较大，描述子带噪声时划分到正确cell的概率高，然后这也减少了描述子的区分能力；当k较大时能保留描述子良好的区分性，但受噪声的干扰明显。所以文章提供了当k值较小时一种cell内部划分机制，称之为Hamming Embedding，能兼顾描述子区分能力和抗噪声能力。2维数据平面的划分示意图如下：

off-line步骤

构造正交矩阵并计算HE阈值。

1. 随机构造一个正交投影矩阵$P_{d_b \times d}$，用QR分解

   M = randn(d);
   [Q, R] = qr(M);
   P = Q(1:d_b, :);

2. 将原始数据投影，$\widetilde{data} = P \times data$
3. 计算每个原特征向量最近kernel，记为$q\left( x_i \right)$，可以用FLANN；
4. 计算HE阈值，循环codebook_size，如果该Voronoi cell中有描述点，则thr(:, i) = median(投影向量)，最终的HE阈值矩阵是$d_b×k$，$k$为codebook size。

on-line步骤

1. 对每个descriptor计算$x$的最近聚类中心；
2. $P \times x$，计算投影后的$z$；
3. 按照 $$b_i(x)=\left\{ \begin{aligned} 1 &\space if \space z_i> \tau_{q(x),i}\\ 0 &\space other \end{aligned} \right.$$ 得到$x$的二进制向量，也就是汉明编码的表示；
4. 定义汉明匹配函数 $$f_{HE}(x,y)=\left\{ \begin{aligned} (tf-idf(q(x)))^2 &,\space if \space q(x)=q(y)和h(b(x),b(y))\le h_t\\ 0 &,\space other \end{aligned} \right.$$
5. 在实验中并未采用原始的${f_{tf - idf}}({x_{i,j}},{y_i})$，而是去掉了tf部分，即 $$f_{HE}(x,y)=\left\{ \begin{aligned} (idf(q(x)))^2 &,\space if \space q(x)=q(y)和h(b(x),b(y))\le h_t\\ 0 &,\space other \end{aligned} \right.$$ 实验发现只考虑IDF项的这种改进，可以得到更高的检索精度。