论文笔记 - Weighted Component Hashing of Binary Aggregated Descriptors for Fast Visual Search

Abstract

本文要解决的问题：尽管计算汉明距离速度很快，但是特征匹配中的线性搜索的开销会随着二进制描述子的长度以及数据集图片的数量的增加而增大。
本文提出：WeCoHash算法
解决方案：

• what to hash: 利用 image-specific component (i.e. visual word) redundancy [特定图像部分冗余] 以及 bit dependency within each component [每个部分中的 bit 依赖]，来产生具有区分性的 hash 值 for bucketing [存放hash值]
• how to search: 基于 hash 值的统计信息，包括0-2阶统计信息，基于这些统计信息的可适应相关权重 [根据统计信息生成的相关性权重]

实验结果：相同的准确度的情况下，比线性搜索快了至少 20 倍，比 LSH 快至少 10 倍

Introduction

一般最优的图像搜索系统都是基于倒序索引结构的 visual vocabulary 结构，将图像的局部特征量化为 visual words。每一个图像表示成一个Bow直方图的形式，并且使用倒叙索引的形式编排这些图像。
FV 和VLAD 扩展了BoW 方法，利用了局部特征的高阶统计特征。与BoW相比，他们需要的 visual vocabulary 都很少 [hundreds of visual words]

对FV和VLAD进行扩展，将FV和VLAD压缩成为二进制聚合特征描述子，同时保持特征的可区能力，这样可以加快汉明距离的计算速度并且能够减少描述子的存储大小。

为了解决移动端的搜索问题，首先在移动端直接提取二进制聚合描述子，将其发送到服务端，在服务端使用汉明距离进行线性搜索。

尽管在这些方式中汉明距离计算速度很快，但是计算开销会随着描述子的长度以及数据集合的大小的增长而增长，描述子长度的增长带来的是指数级的线性搜索开销。所以本文的目标是设计一种针对大规模搜索的快速的ANN搜索算法。

ANN 搜索方法可以分为三种：

• tree-structured search: randomized KD-trees
• clustering: Hierarchical K-Means, Product Quantization,
• hashing

其中 tree-structured search、clustering 都是针对欧氏空间的实值 (real-valued) 描述子向量，效果不如 二进制 (binary vectors) 向量。
Hash方法，比如LSH，能通过将搜索空间从整个数据集缩小到一个候选图像子集的方式，显著的减少汉明距离的计算开销。

hash方法包含两个步骤：离线的hash表的构建，在线搜索。
每个hash表对应一个hash key，这个 hash key 由整个二进制向量或者二进制向量的一部分构成。每一个 hash key 对应一系列的 buckets 桶，用于倒叙索引，给数据集中的图像建立索引。在线搜索的时候，对于给定的搜索图像的二进制表示向量，根据 buckets 中的碰撞情况，可以得到图像集合的一个子集， 然后使用整个二进制向量进行线性搜索，也就是使用整个查询向量和得到的图像子集中的向量比对，得到最终的结果。

可以通过增加hash key的数量来提高准确率，但这无疑增加了搜索时间和存储开销。本文提出的 WeCoHash方法使用了二进制聚合描述子的统计特性，使用这些统计特性来生成 hash keys 以及 优化策略。

为了解决二进制聚合描述子的优化hash策略，主要研究的问题是 what to hash and how to search。

• what to hash
  是为了离线构建hash表，如何生成具有区分性的hash值。
  首先说明的是，每个hash值都是二进制聚合描述子的一个子集，并不是每个bit对于区分性都表现地一样重要，所以需要去除噪声hash值，根据 hash 值的信息量去除那些图像特定冗余[image specific redundancy]
  第二 使用了图像的全局bit统计特性，那么bit之间的相互依赖可以忽略了。所以可以降低hash 值的维度。
• how to search
  主要是为了最大化搜索准确率，同时最小化候选图像集合

WeCoHash image search framework

1. 提取特征聚合描述子 FV（或者 VLAD）
2. 对提取的描述子二值化，生成高维的二进制聚合描述子
3. 使用 WeCoHash 解决 what to hash and how to search
   3.1. offline: 将二进制聚合描述子分解成不连续的部分。对给定的二进制聚合描述子，挑选出那些统计特性比较靠谱的部分 component selection，然后使用 bit selection 解相关比特选择[de-correlated bits selection] 来产生降低了维度的哈希值 dim-reduced hash value
   3.2. online: 计算可适应权重 Adaptive Relevance Weighting ，引入 score weighting 提高搜索性能

Relate Works

Aggregated Descriptors

BoW 利用了局部特征的0-阶统计特性，即统计了局部特征的个数形成了直方图。虽然很多方法对 BoW 进行了改进，但是问题仍然存在：存储开销、大的索引表[大规模图像集合情况下]
FV 利用了局部特征的高阶统计特性，使用 GMM 高斯混合模型来估计局部特征的分布特性。对于一个给定的图像，与高斯函数的参数（平均值和方差）有关的所有局部特征的梯度向量被聚合成一个向量表示。最终通过连接所有高斯函数的一阶和二阶聚合特征得到FV

Binary Aggregated Descriptors

基本想法是先建立一个中间描述子，然后将其二值化。也有直接将原始描述子二值化的方法。

Hashing Binary Vectors for ANN Search

根据二进制向量的长度，hashing 算法可以分为两类：Single key Hashing and Multiple keys Hashing

• Single key Hashing：向量长度比较小，l≤32$l\le 32$，所有构建一个hash表
• Multiple keys Hashing：构建多个hash表 l>>32$l>>32$

weighted component hashing

problem definition

将一副图像表示成二进制聚合描述符 b∈{0,1}l$b\in \{0,1{\}}^l$，那么可以使用汉明距离计算描述符之间的相似性。hashing 的目标就是构建一张或者多张hash表，对得到的二进制聚合描述子建立索引，并且使得再图像搜索中更为有效。

• what to hash 生成第 i 个hash key function hi$h_i$，它是从图像的聚合描述子 b 中选取一部分 b(i)$b(i)$ 得到
  hi(b)=b(i),b(i)∈{0,1}z$$h_i(b)=b(i),b(i)\in \{0,1{\}}^z$$
  ，bits 选取的好坏直接影响着搜索准确度以及hash表的存储大小
• how to search 是通过匹配带查询图像和图像集合中每个 hash 值 b(i),i∈[1,s]$b(i),i\in [1,s]$ 得到相似值 sj$s_j$,
  sj=∑i=1ss(bq(i),bj(i)),j∈[1,n]$$s_j=\sum _{i=1}^{s}s(b^q(i),b^j(i)),j\in [1,n]$$
  ， s 和 n 分别代表 hash keys(hash tables) 的个数以及图像数据集合的大小。

Binary Aggregated Descriptors

X={x1,...,xt}$X=\{x_1,...,x_t\}$ 表示从图像中提取到的局部特征集合，本文使用了SIFT (RootSIFT)
RootSIFT 对SIFT中的每个元素使用了平方根。使用 PCA 将 128 维的 RootSIFT 映射到 d 维度。

FV 在训练集上使用了有 k 个高斯函数 (visual word) 的GMM来估计局部特征的分布。qi={wi,μi,σ2i}$q_i=\{w_i,{\mu }_i,{\sigma }_i^2\}$
对于每个高斯函数，关于 μi${\mu }_i$ 的梯度向量被聚合成一个 d 维度的向量

其中γ(x,i)=ωipi(x)/∑kj=iωjpj(x)$\gamma (x,i)={\omega }_i{p}_i(x)/\sum _{j=i}^k{\omega }_j{p}_j(x)$
所以 g=(g(1),...,g(k))$g=(g(1),...,g(k))$

可以通过将FV中的GMM替换为k-means聚类得到VLAD。相应的，g(i)=∑x∈Xi(x−μi)$g(i)=\sum _{x\in X_i}(x-{\mu }_i)$

将得到的聚合描述子二值化可得
sgn(gi)=1,$sgn(g_i)=1,$ if gi>0$g_i>0$ otherwise 0

可得二进制聚合描述子 b=(b(1),...,b(k)$b=(b(1),...,b(k)$ with l=kd$l=kd$

Image-Specific Component Selection

并不是所有的hash值都可以表示图片，所以要选择其中的一部分hash key的值。

如公式中表示的，聚合特征描述子包含有针对每个 visual word 的残差向量 g(i)$g(i)$，每个残差向量是根据分配给每个 visual word μi${\mu }_i$的局部特征聚合得到。

但是 分配给每个 visual word μi${\mu }_i$的局部特征 的个数会不同，分配给其的局部特征越少，那么认为其包含的区分能力越小。极端情况下，没有分配给其的局部特征，所以该残差向量则全零，那么这中情况下不应该考虑这个 visual word。由此可以引出 g(i)b(i)$g(i)b(i)$ 都不同

那么一个直观的想法就是从得到的 b(i)$b(i)$ 中选取一个子集，这个子集中的元素具有较高的可信度，也就是区分度。可信度定义为 soft-weighted occurence of the i-th visual word qi$q_i$

for i-th visual word
对于连续的FV，o(qi)$o(q_i)$ 被定义为局部特征的后验概率的和。
o(qi)=γ(x,i)$o(q_i)=\gamma (x,i)$， γ(x,i)=ωipi(x)/∑kj=iωjpj(x)$\gamma (x,i)={\omega }_i{p}_i(x)/\sum _{j=i}^k{\omega }_j{p}_j(x)$

对于离散的VLAD， o(qi)=∑cj=1wj∗#(qi,j)$o(q_i)=\sum _{j=1}^c{w}_j\ast \mathrm{\#}(q_i,j)$

给定一个局部特征，根据这个局部特征对所有的 visual word 排序，第 j 个位置的 visual word 叫做 j-th 近邻 visual word，

#(qi,j)$\mathrm{\#}(q_i,j)$ 代表第 j∈[1,c]$j\in [1,c]$个最近邻visual word 是 qi，i∈[1,k]$q_i，i\in [1,k]$ 的局部特征的个数。wj$w_j$ 是权重，本文设置为 w1=4,w2=2,w3=1$w_1=4,w_2=2,w_3=1$

通过实验验证了， 组件的选择对图像匹配对或者不匹配对的汉明距离分布的影响。
经过组件选择之后，更能区分匹配/不匹配图像对。匹配和不匹配的重叠区域变小了，也就是更能区分了[为什么区分图像对]，证明了去除那些没有作用 noisy 的组件是有必要的。

离线构建 hash tables，对于图像集合中的每个图像，它可以被表示为 b=(b(1),...,b(k))$b=(b(1),...,b(k))$，每个组件对应一个 visual word， 根据 r(i)=o(qi)$r(i)=o(q_i)$ 计算针对每个 visual word 的可信度，选取可信度较高的几个 visual word，然后将这些 visual word 对应的 hash keys (b(i)) 用相同的hash码存储该图像的 image ID，这样就将 图像集合中的每个图像与 visual word 联系起来了，每个图像可得一张表。

在线搜索。对待查询图像同样执行组件选择操作，然后使用选择之后的组件执行查询操作，在实际中，对于所有的图像，选取的组件的个数是相同的。

Globally Optimized Bit Selection

经过组件的选择之后，每个组件（visual word）可以被认为是一个 hash key 并且每个 hash key 的维度与 visual word 的维度相同。理想情况下， d维的 hash key 对应的hash 表中有 2d$2^d$ 个hash values （buckets） 如果d比较大，计算开销和存储开销都会很大。所以提出了 bit选择 进一步降低组件的维度。

一种解决方案是运用 random bit selection, 忽略了 bit 之间的相关性。
如果bit之间的相关性越小，那么这系列bit携带的信息会更多，也就是更能表示这个图像， 类似于 “基”
给定一个组件 b(i)=(b1,...,bd)$b(i)=(b_1,...,b_d)$, 内部的bit之间的相似性为

H(bi,bj)$H(b_i,b_j)$ 和 I(bi;bj)$I(b_i;b_j)$ 分别表示 连接熵(joint entropy) 和 bit对 的交互信息(mutual information)。【附录有定义】

从图a中可以看出，每个bit或多或少都与其他的bit相关。

本文基于mutual information minimization [47]提出了一种 bit选择 的全局优化方法。
对于一副图像的第 i 个组件 b(i)∈Rd$b(i)\in {\mathbb{R}}^d$ 目标是 选择其中的 z (z<d)$(z<d)$个bit 生成一个 hash key hi$h_i$。
hi={u(1),...,u(z)}$h_i=\{u(1),...,u(z)\}$ 其中， u(j)∈[1,...,d]$u(j)\in [1,...,d]$ （是原来的二进制描述子的下标）

全局优化的 bit 选择问题 可以公式化为最大熵问题

也就是说找到使得熵最大的取自 原来二进制描述子中的组件的 z 个值。
u∗(j)$u^{\ast }(j)$ 表示从一个组件中选择的bit的下标
bu∗(j)$b_{u^{\ast }(j)}$ 表示相应的bit值

这是一个组合优化问题，所以使用贪心算法进行求解
首先从组件中选择使得熵最大的单个 bit u(1)$u(1)$

然后进行迭代选择（a+1）个bit

从图4(b) 中可以看出，经过mutual information minimization 方法选取的 bit 之间的相关性更小了。

总结算法：

更详细的理解：

Adaptive Relevance Weighting

为了解决 how to search 的问题，提出了Adaptive Relevance Weighting方法提高在线搜索的性能，主要研究了待查询图像和图像集合中图像的hash value 之间的相关性。
有必要介绍一下 EWH(error weighted hashing) 方法：与LSH不同的是候选图像的选择方式不同，LSH方法中至少在一个 hash key 中，存在一个 数据图像与待查询图像有相同的hash value 才能作为候选图像【hash value 与 hash key 之间的关系？是一种东西码】，也就是 e=0。但是 EWH方法使用的是允许hash value 之间存在 e-bit 的不同。
对每个 hash table， EWH 首先枚举出所有的 hash values {b(r)},0≤r≤e$\{b(r)\},0\le r\le e$ ，这些hash value 与待查询图像 hash value 之间存在 r-bit 的不同，然后给 {b(r)}$\{b(r)\}$ 的bucket 中的所有图像增加一个 加权相似分数 ，对所有的 hash table 都执行这个操作，这样就产生了 根据相似性分数排序得到的图像列表，最后选择相似分数最高的一些图像作为候选图像。但是 相似性权重只与 汉明距离e 有关，而且是是根据经验固定的，hash values 的统计信息也被忽略了。

所以在此基础上，本文提出了一种包含了 hash values 的统计信息的赋权方式。
经过 bit选择之后的 hash value(dim-reduced hash value) bq(i),bj(i)$b^q(i),b^j(i)$ 针对的是待查询图像的第 i 个组件

其中，如果 两个向量之间的汉明距离为 r 那么 其中 #(bq(i),r)$\mathrm{\#}(b^q(i),r)$ 表示的是在第 i 个组件相对应的hash value 的 bucket 中的图像的个数，这个hash value 与 bq(i)$b^q(i)$ 有 r bit 不同。n 是图像集合的数目。

否则

如图所示：

• 【图中下方的 表 不明白 bj(i)$b^j(i)$ 的物理意义是什么？】
  指的是，计算出wr(bq(i),bj(i))$w^r(b^q(i),b^j(i))$ 之后，将这个值 加给 在这个 bucket 种的所有图像， 也就是{x, y, z } 上，最后得到的是 图像集合中所有图像的相似度表

对于每个被选择的组件，这个过程根据与bq(i)$b^q(i)$ 有 r bit 不同生成的所有 hash value ，重复多次。
然后以上过程根据 被选择的组件 重复多次，因为以上过程只是针对被选的一个组件。
这样就会得到 对应组件之间 的相似度

最后根据

s分别代表 hash value 的个数，也就是组件的个数，计算该图像的相似度，
最后的最后，设定一个阈值，然后根据阈值选择候选图像，然后在候选图像中，使用原来的 二进制描述子 计算相似度，得到最为相近的图像。

算法总结：

算法中 Compute using look-up table and add it to that are within the corresponding buckets of hash table 表示给图像集合中的所有图像 累加相似度
.
- 关于 look-up table
因为在线搜索中，我们需要对 所有的 汉明距离 r 以及对所有的 选取的组件 进行迭代计算，不可避免地降低了搜索速度。所以提出了 fast look-up table 方法。
对于每个组件，枚举所有可能的 hash values，然后计算 不同 汉明距离 r 情况下的权重

这样共有 k∗2z∗(e+1)$k\ast 2^z\ast (e+1)$ 个元素在表中。（怎么得到的？？ k 个组件，（e+1）个bit不同，每个组件对应的hash维度为 z，所以有 2z$2^z$ 种选择）

这样在线搜索的时候，根据给定的 query 的hash value 以及 r 可以很快得到 权重 adaptive relevance weight。

EXPERIMENTS

Datasets

• UKbench - 10,200 images with 2,550 objects， all used for reference images
• INRIA Holidays - 1,491 holiday photos, 500 for query, 991 for reference
• Stanford Mobile Visual Search (SMVS) dataset - 4,500 phone camera images, 2,800 queries and 1,700 reference
• FLICKR1M - 作为干扰项, 1 million distractor images, merged with the reference images
• Oxford used for training ‘

Evaluation Criteria

• Search Accuracy:
  
  • mAP
  • STM = (number of times the top retrieved image is relevant)/( number of queries).
• Search time cost
  
  • T=Tbuckets+Tcandidates$T=T_{buckets}+T_{candidates}$
• Memory cost
  
  • S=Sbuckets+Sindices$S=S_{buckets}+S_{indices}$

Comparison Baselines

Comparison with the state of the art

• the exhaustive linear search
• the LSH algorithm
• the Uniform LSH algorithm
• the EWH algorithm
• the MIH algorithm
• the HKM
• the PQ

Implementation Details

Impact of Parameters

• Number of selected components s, fix z and e
  
  • 随着选择的组件的增多， mAP增大，同时 time cost 也增大
• Number of selected bits z， fix s and e
  
  • 随着 z 的减小，search time 显著减小。当 z 比较小的时候，那么buckets （hash key）的个数就会少，那么每个 bucket 中的图像就会增多，就会给 最后的线性搜索带来很大开销；如果 z 比较大，那么查询图像和dataset图像 冲突可能性就会降低，就会造成 mAP 降低。
  • 同时发现，当e设置比较小的时候，可以通过设定阈值 t 来缓和 线性搜索的开销
• search radius e， fix s and z
  
  • 从0增加到2，mAP增加的效果很明显，但是从2到3，mAP增加就不是很明显，同时计算效率大幅度降低(计算时间增加了)。
• on the SMVS dataset

Evaluation of “What to Hash” and “How to Search”

Comparison With the State of the Art

• Performance comparison
  
  • mAP vs search time on INRIA Holidays, SMVS and UKbench

• Effects of the dimensionality of binary aggregated descriptors on search efficiency
  
  • search time vs descriptor dimensionality of WeCoHash, LSH, Uniform LSH, EWH and Linear Search over the UKbench dataset combined with 1 million FLICKR1M.
  • component(visual word) k =128, d = {16,32, 48, 64}

• Effects of database size on search efficiency
  
  • growth of search time with the database size
• Performance evaluation over large-scale experiments.
  
  • the retrieval accuracy, mAP, Top Match (STM), search time
  • LSH, Uniform LSH, EWH, MIH, HKM, PQ and Linear Search combined with 1 million FLICKR1M
    
    
• Memory cost
  
  • Table III
• Accuracy versus efficiency.
  
  

---

refer

• Weighted Component Hashing of Binary Aggregated Descriptors for Fast Visual Search