论文笔记：SIFT Meets CNN: A Decade Survey of Instance Retrieval_基于深度学习的图像检索研究开始时间

一、基本信息

标题：SIFT Meets CNN:
A Decade Survey of Instance Retrieval
时间：2017
出版源：IEEE Transactions on Pattern Analysis and Machine Intelligence
论文领域：图像检索综述，SIFT，CNN
引用格式：L. Zheng, Y. Yang and Q. Tian, “SIFT Meets CNN: A Decade Survey of Instance Retrieval,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 5, pp. 1224-1244, 1 May 2018, doi: 10.1109/TPAMI.2017.2709749.
链接：https://arxiv.org/abs/1608.01807

二、研究内容

2000年，可以认为是大部分传统方法结束的时间节点，当时Smeulders等撰写了“图像检索早期发展的终结”这篇综述。
2003年，词袋模型（BoW）进入图像检索社区的视野，并在2004年结合了SIFT方法符被应用于图像分类任务。这后来的近10年时间里，社区见证了BoW模型的优越性，它给图像检索任务带来了各种提升。
2012年，Krizhevsky等人使用AlexNet神经网络模型在ILSRVC 2012上取得了当时世界上最高的识别准确率。从那以后，研究的重心开始向基于深度学习特别是卷积神经网络（CNN）的方法转移。

各种图像检索模型的异同点：

SIFT

使用小型编码本。

视觉词汇少于几千个，紧凑编码向量在降维和编码之前生成。

编码方法

BoW（Bag of words）

BoW方法的核心思想是提取出关键点描述子后利用聚类的方法训练一个码本，随后每幅图片中各描述子向量在码本中各中心向量出现的次数来表示该图片，该方法的缺点是需要码本较大
参考这篇文章解释

VLAD（vector of locally aggregated descriptors）

VLAD算法可以看做是一种简化的FV，其主要方法是通过聚类方法训练一个小的码本，对于每幅图像中的特征找到最近的码本聚类中心，随后所有特征与聚类中心的差值做累加，得到一个k * d的vlad矩阵，其中k是聚类中心个数，d是特征维数(如sift是128维),随后将该矩阵扩展为一个(k*d)维的向量，并对其L2归一化，所得到的向量即为VLAD。

算法可以分为如下几步：
1.提取图像的SIFT描述子
2.利用提取到的SIFT描述子（是所有训练图像的SIFT）训练一本码书，训练方法是K-means
3.把一副图像所有的SIFT描述子按照最近邻原则分配到码书上（也即分配到K个聚类中心）
4.对每个聚类中心做残差和（即属于当前聚类中心的所有SIFT减去聚类中心然后求和）
5.对这个残差和做L2归一化，然后拼接成一个K*128的长向量。128是单条SIFT的长度

FV（Fisher Vector）

FV方法的核心思想是利用高斯混合模型(GMM)，通过计算高斯混合模型中的均值、协方差等参数来表示每张图像。该方法的优点是准确度高，但缺点是计算量较大。

基于Fisher Vector的图像学习的完整过程应该描述为下面几个步骤。
选择GMM中K的大小
1.用训练图片集中所有的特征（或其子集）来求解GMM（可以用EM方法），得到各个参数；
2.取待编码的一张图像，求得其特征集合；
3.用GMM的先验参数以及这张图像的特征集合按照以上步骤求得其fv；
4.在对训练集中所有图片进行2,3两步的处理后可以获得fishervector的训练集，然后可以用SVM或者其他分类器进行训练。参考这篇文章解释

总结

BOF、FV、VLAD等算法都是基于特征描述算子的特征编码算法，关于特征描述算子是以SIFT为基础的一类算法，该类算法能得到图片的一系列局部特征，该类特征对旋转、缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性，但是该类特征产生的特征矩阵一般都较为庞大，因此需要利用特征编码算法对其进行编码，以便后续构建索引，实现图像检索。

BOF、FV、VLAD都需要对SIFT得到的特征进行聚类，得到一个码本，利用码本，将原始的N维特征向量映射到K维的空间中，不同之处在于映射方法不同。

BOF（Bag Of Features）：建立码本时采用K-means，在映射时，利用视觉词袋量化图像特征，统计的词频直方图，该词频直方图即为编码后的特征向量，损失的信息较多。BOF是把特征点做kmeans聚类，然后用离特征点最近的一个聚类中心去代替该特征点，损失较多信息；

FV（Fisher Vector）：FV是对特征点用GMM建模，GMM实际上也是一种聚类，只不过它是考虑了特征点到每个聚类中心的距离，也就是用所有聚类中心的线性组合去表示该特征点，在GMM建模的过程中也有损失信息。

VLAD（vector of locally aggregated descriptors）：VLAD像BOF那样，只考虑离特征点最近的聚类中心，VLAD保存了每个特征点到离它最近的聚类中心的距离； 像Fisher vector那样，VLAD考虑了特征点的每一维的值，对图像局部信息有更细致的刻画； 而且VLAD特征没有损失信息。

最似最近邻检索

分层k-means(HKM)

=HKM方法在2006年提出，HKM分层次地应用标准k-means方法进行特征训练。HKM首先将特征空间中的点划分为几个族，接着递归地将每个族划分为更多的群集。
在每次递归时，每个点都要被归类为 $\bar{k}$个族中的其一个, 聚类树的深度为 $O(\log K)$ 其中 $K$ 是期望得到的聚类族数目。HKM的计算复杂度是 $O(\bar{k}M\log K),$ 其中 $M$是训练样本数。当$K$很大的时候,HKM的计算复杂度远小于扁平K-means

近似k-means(AKM)

在AMK算法中，分配步骤的花费可以表示为，其中v是K-D树中要访问的最近簇的候选数。因此AKM的计算复杂度与HKM相当，并且当K较大时，明显小于扁平k-means算法。实验表明AKM的量化误差要低于HKM，因此它要要优于HKM算法。在大多数基于AKM的方法中，最似最近邻检索算法选用FLANN。



KD树

使用大型编码本。

鉴于BoW直方图的稀疏性和视觉词汇的高区分度，在算法中使用了倒排索引和存储友好型的签名方式。在编码本的生成和编码中使用了类似的方法。

特征编码

ANN搜索算法（Approximate Nearest Neighbor）
ANN的方法分为三大类：基于树的方法、哈希方法、矢量量化方法。brute-force搜索的方式是在全空间进行搜索，为了加快查找的速度，几乎所有的ANN方法都是通过对全空间分割，将其分割成很多小的子空间，在搜索的时候，通过某种方式，快速锁定在某一（几）子空间，然后在该（几个）子空间里做遍历。

倒排

倒排是一种提高存储和检索效率的算法，它常被用于大/中等规模的编码本中。

使用中型编码本。

鉴于BoW的稀疏性和视觉词汇的低区分度，使用倒排索引和二进制签名方法。准确率和效率间的权衡是影响算法的主要因素。
中等规模编码本一般含有10——200k个视觉词汇。视觉词汇展现了中等区分能力，同时检索时也使用了倒排索引。

在中等规模编码本下视觉词汇的区分度介于小规模编码本和大规模编码本之间。因此，对量化过程中带来的信息损失需要进行补偿。最终，汉明嵌入（HE）这个里程碑式的工作成为实践中的主流算法。

匹配问题

• RANSAC它重复计算每个对应的仿射变换，并通过适合变换的内点数来验证。RANSAC算法有效地重新排列排名最高的图像的子集，但存在效率问题。最终，如何在SIFT为基础的框架下有效、准确地结合空间信息被广泛地研究。

• WGC 弱几何一致性 。在投票空间中，具有较大值的容器更可能代表真正的转换。WGC这种方法关注匹配特征在尺度和方向上的差异,不同空间则被量化到容器中

• HPM 霍夫金字塔匹配方法，通过分层划分变换空间来分配匹配结果。HPM在灵活性和准确性之间取得了平衡，非常高效。还可以通过允许单个通信对多个容器进行投票来减少量化损失。HPM和这种方法都在速度上快于RANSAC算法，同时也可以被看作是对和HE一起提出的WGC在旋转和尺度不变性上的拓展

CNN

使用预训练的模型

通过在大规模图像集（例如ImageNet）上预训练的CNN模型进行单通道传播提取特征。使用紧凑编码/池化技术进行检索。

预训练的CNN模型：

CNN滤波器类似局部手工制作的特征中的检测器，但是对于高层次和复杂的刺激，CNN滤波器具有不同于SIFT类检测器的特质。AlxNET已被证明被新的的如具有最大数量参数的VGGNet超越。ResNet和GoogleNet分别赢得了ILSVRC 2014和2015的挑战，表明CNN网络的效果和网络层数成正比。

特征编码与池化

• 一组列特征类似于SIFT特征,因此可以直接使用标准编码方案。常用的方法就是VLAD和FV算法
  池化。
• CNN特征与SIFT的主要区别在于前者在每个维度上都有明确的含义,也就是对输入图像的特定区域的滤波器响应。直接池化技术也可以产生具有区分度的特征。

使用微调的模型

在训练图像与目标数据库具有相似的分布的训练集上，对CNN模型进行微调。通过单通道CNN模型，运用端到端的方法提取出CNN特征。这种视觉表示方法提升了模型的区分能力。
用于微调的CNN结构主要分为两类：

• 基于分类的网络被训练以将建筑分类为预定义的类别。由于训练集和查询图像之间通常不存在类重叠，因此在AlexNet中如FC6或FC7的学习到的嵌入特征用于基于欧氏距离的检索。
• 验证网络可以使用孪生网络（siamese network）结合成对损失函数（pairwise loss）或三元损失函数（triplet loss），这种方法已经被更广泛地用于微调网络任务中

混合型方法。

图像块被多次输入进CNN用于特征提取。编码与索引方法和基于SIFT的检索方法近似。

特征提取

特征提取过程包括图像块检测和描述符生成

图像块检测：

• 第一种检测器是网格化图像块。例如，在《Multi-scale orderless pooling of deep convolutional activation features》中使用了两个尺寸滑动窗口的策略来生成图像块
• 第二类是具有不变性的关键点/区域检测器。例如高斯差分特征点在《Learning to compare image patches via convolutional neural networks》中使用。
• 第三种是区域建议方法，它也同样提供了潜在对象可能的位置信息。Mopuri等人使用选择性搜索策略来提取图像块，而边缘区域方法在《Fisher encoded convolutional bag-of-windows for efficient image retrieval and social image tagging》中使用。

描述符生成：
《Descriptor matching with convolutional neural networks: a comparison to sift》证实了CNN一类的区域描述是有效的，并且在出模糊图像之外的图像匹配任务繁重要优于SIFT描述符。

征编码与索引

混合方法的编码/索引过程类似于基于SIFT的检索，如同在小码本下的VLAD / FV编码或大码本下的倒排索引。

基于SIFT和CNN的方法间的关系

第一，混合方法可被视为从SIFT-到基于CNN的方法的过渡方法，除了将CNN特征提取为局部描述符之外，它在所有方面都类似于基于SIFT的方法。由于在图像块特征提取期间需要多次访问网络，因此特征提取步骤的效率可能会受到影响。

第二，单向CNN方法倾向于将SIFT和混合方法中的各个步骤结合起来。在表5中，“预训练单向网络”一类方法整合了特征检测和描述步骤；在“微调单向网络”中，图像级描述符通常是在端到端模式下提取的，因此不需要单独的编码过程。在《Deep image retrieval: Learning global representations for image search》中，集成了类似“PCA”层以减少区分维数，进一步完善了端到端的特征学习。

第三，出于效率上的考虑，特征编码的固定长度表示方法越来越流行。它可以通过聚集局部描述符（SIFT或CNN）、直接汇或端到端特征计算的方法来获得。通常，诸如PCA的降维方法可以在固定长度的特征表达中使用，ANN搜索方法（如PQ或哈希）可用于快速检索

比较与分析

多年来在Holidays(a), Ukbench(b), Oxford5k©数据集上的最优表现：

多年来性能的改进:

基于CNN的检索模型在图像例检索中迅速显示出其优势。在2012年AlexNet刚提出时，当时的FC特征的性能与SIFT模型相比仍然远不能令人满意。然而，CNN网络结构和微调策略的进步，基于CNN的方法的性能迅速提高，在Holidays和Ukbench数据集上极具竞争力，并且在Oxford5k数据集上的指标略低，但它具的内存消耗更小。

三、未来研究方向

面向通用任务的实例检索

• 第一，需要引入大规模图像数据集。因此，社区迫切需要大规模的图像数据集或一种可以以监督或非监督的方式生成这样一个数据集的有效方法。
• 第二，设计新的CNN网络和学习策略对于充分利用训练数据具有重要意义。Faster R-CNN在实例检索中的引入对更精确的对象定位来说是一个良好的开始。此外，在另一个检索任务中采用微调模型时，迁移学习方法也是非常重要。

面向专用任务的实例检索

例如地点检索，行人检索，车辆检索，标志检索等。在这些任务中的图像具有特定的先验知识。例如在行人检索任务中，循环神经网络（RNN）可以连接身体部分的描述符，在车辆检索任务中，在特征学习期间可以推断视图信息，同时牌照图像也可以提供关键信息。

四、结论与思考

作者结论

本篇综述回顾了基于SIFT和CNN特征的实例检索方法。根据编码本的规模，我们将基于SIFT的方法分为三类：使用大，中，小规模的编码本。基于CNN的方法也被分为了三类：使用预训练模型，微调模型和混合模型的方法。在每个类别下都对先前的方法进行了全面的调研。从各种方法的演变可以看出，混合方法处于SIFT和CNN方法的过渡位置，紧凑编码方法越来越流行，并且实例检索正朝着端到端的特征学习和提取的方向发展。

通过在几个基准数据集上收集的实验结果，对六种方法进行了比较。我们发现CNN微调模型策略在不同的检索任务上都得到了较高准确率，并且在效率上也具有优势。未来的研究可能集中于学习更通用的特征表示或更特定场景的检索任务。

总结

初步了解图像检索流程，对比基于SIFT和CNN的实例检索方法，图像检索系统作为计算机视觉领域的一项关键技术，更加鲁棒的图像特征描述符，更加快速的检索算法都是我们需要继续研究的课题

思考

对于文中提到最大卷积激活（MAC），MAC用单个前向传递来计算全局描述符不是很理解

参考

参考1SIFT
参考2CNN