前言
基于内容的图像检索任务（CBIR）长期以来一直是计算机视觉领域重要的研究课题，自20世纪90年代早期以来，研究人员先后设计了图像的全局特征，局部特征，卷积特征的方法对CBIR任务进行探索和研究，并取得了卓越的成果。
这篇刊登在 TPAMI 2018年5月刊上的综述《SIFT Meets CNN: A Decade Survey of Instance Retrieval》全面调研了十多年来图像检索任务中所使用的图像编码、检索算法，并对比了各种方法在各大数据集上的实验结果，旁征博引，内容详实。如果您刚接触图像检索领域，可以通过本篇文章摸清其概貌；如果您在领域内深耕多年，也可以在本文中查漏补缺，裨益良多。
TPAMI是计算机视觉领域顶级期刊，此文的质量也不必多言，我在此斗胆将这篇综述加以整理，翻译成文，若有不当之处还望指出。
标题：
当SIFT邂逅CNN：图像检索任务跨越十年的探索历程
作者：
Liang Zheng, Yi Yang, and Qi Tian
摘要
在基于内容的图像检索技术（CBIR）发展早期，研究人员大多基于图像的全局特征进行研究。自2003年开始，由于SIFT特征在图像变换（译者注：尺度、方向变化）问题中的优异表现，十多年来基于局部描述算子（如SIFT描述算子）的图像检索方法一直被广泛研究。最近，基于卷积神经网络（CNN）的图像表示方法吸引了社区越来越多的关注，同时这种方法也展现出了令人赞叹的性能。我们领域正处于快速发展时期，本文对实例检索近十多年来的进展进行了综合且全面的调查研究，主要展示了基于SIFT和CNN特征的两类主要方法。对SIFT一类的方法，我们根据字典本大小，将相关文献按照字典的大/中/小规模进行组织。对CNN一类的方法，我们主要依据预训练模型，微调模型和混合模型进行分类和讨论。预训练模型和微调模型方法采用了单通道的图像输入方法而混合模型则采用了基于块的特征提取策略。本篇综述选取了在现代实例检索任务中先前的各类工作，展现了该任务中的里程碑时刻，并提出了关于SIFT与CNN的内在联系的见解。在分析与比较了各种方法在几个数据集上的检索性能后，我们分别讨论了通用实例检索和专用实例检索任务未来的发展前景。
1 介绍
基于内容的图像检索任务（CBIR）是计算机视觉领域一项由来已久的研究课题。CBIR研究在20世纪90年代早期正式开始，研究人员根据诸如纹理、颜色这样的视觉特征对图像建立索引，在这一时期大量的算法和图像检索系统被提出。其中一种简单明了的策略就是提取出图像的全局描述符，这种策略在1990s和2000s早期是图像检索社区研究的重点。然而，众所周知，全局描述符这种方法在诸如光照，形变，遮挡和裁剪这些情况下难以达到预想的效果。这些缺陷也导致了图像检索准确率的低下，也局限了全局描述符算法的应用范围。恰在这时，基于局部特征的图像检索算法给解决这一问题带来了曙光。
本篇综述主要关注于实例级的图像检索任务。在这个任务中，给定一张物体/场景/建筑类型的待查询图片，查询出包含拍摄自不同角度、光照或有遮挡的，含有相同物体/场景/建筑的图片。实例检索不同于类别检索任务，因为后者的目标是检索出同类别的图片。接下来，如果没有特别指出的话，“图像检索”和“实例检索”两个名词可以相互替代。
在图1中我们展示了多年来实例检索任务中的里程碑时刻，并且在图中着重标出了基于SIFT特征和CNN特征算法的提出的时间。2000年可以认为是大部分传统方法结束的时间节点，当时Smeulders等撰写了“图像检索早期发展的终结”这篇综述。三年后（2003），词袋模型（BoW）进入图像检索社区的视野，并在2004年结合了SIFT方法符被应用于图像分类任务。这后来的近10年时间里，社区见证了BoW模型的优越性，它给图像检索任务带来了各种提升。在2012年，Krizhevsky等人使用AlexNet神经网络模型在ILSRVC 2012上取得了当时世界上最高的识别准确率。从那以后，研究的重心开始向基于深度学习特别是卷积神经网络（CNN）的方法转移。
图1：图像检索里程碑
基于SIFT特征的方法大多依赖于BoW模型。BoW模型最初是为解决文档建模问题而提出的，因为文本本身就是由单词组成的。它通过累加单词响应到一个全局向量来给文档建立单词直方图。在图像领域，尺度不变（SIFT）特征的引入使得BoW模型变得可行。最初，SIFT由检测器和描述符组成，但现在描述符被单独提取出来使用。在这篇综述中，如果没有特别指明的话，SIFT往往是指128维的描述符（译者注：OpenCV的SIFT实现也是默认生成128维向量），这也是社区的惯例。通过一个预训练的字典（译者注：补充说明一下，在工业界的项目中，待检索的图像往往有特定的范围，使用特定范围内的有代表性的图片构建出预训练字典可以取得比较好的效果），局部特征被量化表示为视觉词汇。一张图片能够被表示成类似文档的形式，这样就可以使用经典的权重索引方案。
近几年，CNN这种层次结构模型在许多视频相关的任务上取得的成绩远好于手工特征，基于SIFT特征的模型的风头似乎被CNN盖过了。基于CNN的检索模型通常计算出紧密的图像表示向量，并使用欧氏距离或ANN（approximate nearest neighbor）查找算法进行检索。最近的文献可能会直接使用预训练好的CNN模型或微调后应用于特定的检索任务。这些方法大多只将图像输入到网络中一次就可以获取描述符。一些基于图像块的方法则是将图像多次输入到网络中，这和SIFT方法的习惯有些类似；在这篇综述中，我们将这些方法称为混合型方法。
2 方法分类
根据不同的视觉表示方法，本文将检索文献大致分为两类：基于SIFT特征的和基于CNN特征的方法。进一步地，我们将基于SIFT的方法根据编码本大小又分为大，中，小编码本三类。我们注意到，编码本的大小与所选取的编码方法紧密相关。基于CNN的方法分为使用预训练的模型，微调的模型以及混合模型方法。他们的异同点列于表1。
表1：各种图像检索模型的异同点
基于SIFT的方法在2012年之前一直是研究的重点（当然近年来也有不少相关的杰出工作）。这一类方法通常使用如Hessian-Affine这种探测器，同时也使用SIFT这种描述符。编码本将局部特征映射到一组向量中。基于编码本大小，我们将基于SIFT的方法分为如下三类。
使用小型编码本。视觉词汇少于几千个，紧凑编码向量在降维和编码之前生成。
使用中型编码本。鉴于BoW的稀疏性和视觉词汇的低区分度，使用倒排索引和二进制签名方法。准确率和效率间的权衡是影响算法的主要因素。
使用大型编码本。鉴于BoW直方图的稀疏性和视觉词汇的高区分度，在算法中使用了倒排索引和存储友好型的签名方式。在编码本的生成和编码中使用了类似的方法。
基于CNN的方法使用CNN模型提取特征，建立紧凑向量（固定长度）。它们也分为三类：
混合型方法。图像块被多次输入进CNN用于特征提取。编码与索引方法和基于SIFT的检索方法近似。
使用预训练的模型。通过在大规模图像集（例如ImageNet）上预训练的CNN模型进行单通道传播提取特征。使用紧凑编码/池化技术进行检索。
使用微调的模型。在训练图像与目标数据库具有相似的分布的训练集上，对CNN模型进行微调。通过单通道CNN模型，运用端到端的方法提取出CNN特征。这种视觉表示方法提升了模型的区分能力。
3 基于SIFT特征的图像检索系统
3.1 基本流程
基于SIFT特征与CNN特征的图像检索流程如图2所示。
局部特征提取。假设我们有一个含张图片的画廊。指定一个特征检测器，我们从稀疏的感兴趣点或密集的图像块中提取局部描述符。我们用来表示局部描述符，用表示图像中被检测的区域。
编码本的训练。基于SIFT的方法你先训练编码本。编码本中的每一个视觉词汇位于子空间的中心，这称为“沃罗诺伊单元”。更大的码本对应于更精细的划分，从而产生更多区分性的视觉词，反之亦然。假设已有一些局部描述符从无标签的训练集中计算出。例如k-means这样的基准方法就是将个点聚类成簇，得到的个视觉词汇即编码本的大小。
特征编码。一个局部描述符通过特征编码过程被映射到嵌入特征。在使用k-means方法时，可以根据到视觉词汇的距离进行编码。对于大规模的编码本，硬量化和软量化方法都是很好的选择。前者量化得到只有一个非零条目的嵌入特征，后者则是将量化表示为少量的视觉词汇。在汇总所有的局部嵌入特征后就得到了一个全局签名。对于中等规模的编码本来说，可以通过额外的二值签名拉埃保护原始信息。当使用小规模编码本时，大多使用VLAD，FV之类的编码方法（译者注：VLAD可以理解为是BOF和FV的折中，BOF是把特征点做kmeans聚类，然后用离特征点最近的一个聚类中心去代替该特征点，损失较多信息；FV是对特征点用GMM建模，GMM实际上也是一种聚类，只不过它是考虑了特征点到每个聚类中心的距离，也就是用所有聚类中心的线性组合去表示该特征点，在GMM建模的过程中也有损失信息；VLAD像BOF那样，只考虑离特征点最近的聚类中心，同时保存了每个特征点到离它最近的聚类中心的距离；像FV那样，VLAD考虑了特征点的每一维的值，对图像局部信息有更细致的刻画）。
3.2 局部特征提取
局部不变特征针对精准匹配图像局部结构而提出。基于SIFT的方法和大多特征提取步骤类似，都是由特征检测器和描述符组成。
局部检测器。感兴趣点检测器旨在于在多样的图像场景中定位出一系列特征稳定的局部区域。在检索社区中，寻找图像的仿射协变区域（affine-covariant regions）一直是首选方法。它之所以称之为“协变的”是因为检测区域随着仿射变化而改变，因此区域描述符具有不变性。这种仿射协变区域检测器和以关键点为中心的海森检测器（Hessian detector）不同，当然也和以寻找尺度不变区域为目标的高斯差分检测器（DoG detector）。适应于局部强度模式的椭圆区域由仿射检测器探测到。这就确保了相同的图像局部结构即使是因为视角变化而产生形变时也能被检测到，视角形变问题也是图像检索任务中的常见问题。在里程碑事件中，我们也提到了最稳定连通域（MSER）检测器和仿射拓展的海尔-拉普拉斯检测器（ affine extended Harris-Laplace detector）这两种具有仿射不变性的区域检测器。鉴于海森仿射检测器在解决视角变化问题中的优异性能，社区认为它是要优于DoG检测器的。为了解决这些仿射协变区域方向模糊的问题，重力假设方法应运而生。这种方法抛弃了方向估计的思路，并在建筑物数据集上的效果不断改善。在图像检索中也尝试了其他的非仿射检测器，例如拉普拉斯-高斯（LOG）和海尔检测器。对于表明光滑的物体，仅有少量的关键点会产生响应，因此可以用物体边缘作为局部特征描述。
另一方面，针对密集区域检测器也有不少研究。在对比了密集采样图像块和探测图像块两种方法后，Sicre等指出前者表现更优。为了恢复密集采样图像块的旋转不变性，提出了图像块主旋转角方法。各种密集采样策略以及关键点检测器的综合比较可以在《A comparison of dense region detectors for image search and fine-grained classification》这篇文献中查阅到。
局部描述符。局部描述符使用一系列检测区域对局部图像内容进行编码。SIFT描述符一直以来都是大家默认使用的描述符。这种128维的向量在匹配准确率上从众多描述符中脱颖而出。更进一步地，PCA-SIFT描述符将特征向量的维度从128维减少到36维，通过增加特征建立计算量和降低区分度来加快匹配速度。另一种改进方法是RootSIFT，它首先将SIFT描述符进行归一化，随后对每个元素开方。RootSIFT现在是基于SIFT的检索方法惯用方法。除了SIFT之外，SURF描述符也被广泛应用。SURF描述符结合了海森-拉普拉斯检测器和局部梯度直方图。积分图技巧可以用于加速特征的计算（译者注：积分图技巧会对原图像首先生成一张积分图，这种通过空间换取时间的策略，在计算图像的诸如海尔特征时可以大幅提高计算速度）。SURF可以取得和SIFT近乎一样的准确率，同时SURF计算速度更快。文献《A comparison of sift, pca-sift and surf》对SIFT，PCA-SIFT和SURFF进行了比较。为了进一步加快匹配速度，二值描述符用汉明距离替代了欧氏距离。
除了手工特征，一些研究人员也提出了学习式的方案来提高局部描述符特征的区分度。例如，Philbin等提出了一种非线性的变换使得投影SIFT描述符为真实匹配产生更小的差异。Simoyan等更进一步地设计了学习池化区域和线性描述符投影的方案来改进Philbin等的方案。
3.3 使用小规模编码本进行检索
小规模编码本一般包含几千、几百甚至更少的视觉词汇，因此编码本生成以及编码算法的时间复杂度不高。这方面一些有代表性的工作包括BoW、VLAD和FV。我们主要讨论了VLAD和FV模型，同时根据《Multiple measurements and joint dimensionality reduction for large scale image search with short vectors》 这篇文献综合评价了BoW压缩向量。
3.3.1 生成编码本
聚类时的算法复杂度很大程度上依赖于编码本的大小。用VLAD或FV生成打的编码本通常很小，一般是64,128,256。在VLAD中使用平面k-means聚类算法生成编码本。在FV中使用GMM算法，例如，式中表示高斯混合曲线的数目，通过极大似然估计算法训练得到。GMM用个混合高斯分布曲线描述特征空间，这同时也可以表示为，其中，和别表示混合权重，均值向量和高斯曲线的协方差矩阵。
3.3.1 编码方法
因为小规模编码本尺寸小的缘故，相对复杂的和存储信息的方法可以在这上面使用。我们在这个小节中主要调研了FV，VLAD方法及其发展。使用预先训练的GMM模型，FV描述局部特征和GMM中心之间的平均一阶和二阶差异。它的维度是，其中是局部描述符的维度，是GMM编码本的长度。FV通常进行指数归一化（power normalization）以抑制突发性问题。在这一步，FV的每一部分在的非线性变换由参数表征。接下来使用归一化，这样FV就从各方面得到提升。例如，Koniusz等人用每个描述符的空间坐标和相关的可调权重来对其进行扩充。在《Revisiting the fisher vector for fine-grained classification》这篇文献中，更大的编码本（将近4096）表现出比小编码本更好的分类准确率，当然计算花费同时也增大了。为了修正局部区域独立同分布这一假设，Cinbis等人提出了非独立同分布模型，这个工作抑制了突发事件的影响，同时也改进了指数归一化的效果。
VLAD编码方案由Jégou提出，可以认为VLAD是FV的简化版本。VLAD量化将局部特征量化为最近邻视觉词汇，同时记录下两者的距离。由于编码本规模小，因此最近邻检索方案可行。在残差向量被总和池化聚合后进行归一化。VLAD的维度是。同样，研究人员对VLAD在多方面进行了改进。Jégou和Chum提出使用PCA和白化（在表5中表示为）去消除视觉词语共现现象，并且训练多个编码本以减少量化带来的损失。Arandjelovi等从三个方面拓展了VLAD：1）归一化每个粗糙聚类中的残差和，称为内部归一化，2）通过词汇自适应来解决数据集迁移问题，3）用多VLAD模型(multi-VLAD)来解决小目标发掘问题。Delhumeau等提出应该将残差向量归一化，而不是求残差和；他们还提倡在每个Voronoi格内进行PCA降维，而不是像《Aggregating
local image descriptors into compact codes》中所提出的降维方案。《Improving
large-scale image retrieval through robust aggregation of local
descriptors》中提出应该使用软任务和经验性地为每个等级学习最佳权重来改进硬量化方案。
注意到许多常规的方法对VLAD，FV，BoW，局部约束线性编码（LLC）以及单项嵌入这些嵌入方法有益。Tolias等人提出结合SIFT描述符，用方向协变嵌入的方法来对SIFT特征主方向进行编码。它通过在感兴趣的区域内使用几何线索来实现与弱几何一致性（WGC）相似的协方差属性，使得与主方向相似的匹配点被加权，反之亦然。三角嵌入方法只考虑了输入向量的方向而没有考虑其大小。Jégou等人同样也提出了一种限制映射向量之间干扰的民主聚合的方法。除了类似民主聚合的思想，Murray和Perronnin提出，通过均衡池化向量和每个编码表示之间的相似性优化广义最大池化（GMP）方法。
BoW，VLAD和FV的复杂度基本一致。我们忽视线下训练时间和SIFT特征提取时间。在视觉词汇分配这一步中，VLAD（FV）模型中每一个特征（高斯曲线）需要计算和每一个视觉词汇的距离（soft assignment coefficient），因此这一步的计算复杂度为。并且其他步骤的计算复杂度都要小于。考虑到是以求和池化方式进行的嵌入，因此编码过程总的计算复杂度为，其中表示图像中提取的特征的数目。三角嵌入式VLAD的一个变异体，它和VLAD的计算复杂度相似，都是。multi-VLAD的计算复杂度也是，但是它匹配过程的复杂度过大。分层的VLAD的计算复杂度是，其中表示第二个编码本的大小。在特征聚类这一步，GMP和民主聚合方案都有很高的计算复杂度。GMP的复杂度是，式中是特征嵌入的维度， 民主聚类方法的计算复杂度主要来源于Sinkhorn算法。
3.3.3 最似最近邻检索
由于VLAD/FV嵌入的维度相当高，因此研究人员提出了高效的压缩和最似最近邻检索（ANN）算法。例如，主成分分析（PCA）算法常适用于降维任务，特别是使用PCA降维后检索的准确度甚至会提高。对于基于哈希的最似最近邻方法，Perronnin等人使用标准二值编码方法，如局部敏感哈希（LSH）和谱哈希（spectral hashing）。然而，在使用SIFT和GIST特征数据库进行测试时，谱哈希方法被证明要优于乘积量化方法。在这些基于量化的最似最近邻算法中，PQ算法表现得最为出色。关于VLAD和PQ算法的详细研究可以参见《A comprehensive study over vlad and product quantization in large-scale image retrieval》。同样，PQ算法后来也被不断改进。Douze等人提出对聚类中心重新排序，使得相邻的中心具有较小的汉明距离。该方法与基于汉明距离的最似最近邻检索相兼容，这为PQ算法提供了显著的加速。我们参阅了《A survey on learning to hash》作为ANN方法的调研报告基础。
我们还提到一种新兴的ANN算法，群组测试算法。简要地说，该算法将数据库分组，每组都由一个组向量表示。通过查询和组向量之间的比较计算出一个组包含正确匹配的可能性。因为组向量数目远少于数据库向量，因此检索时间大大缩短。Iscen等提出直接找出数据库中最优组向量，而不用精确地分组，这个方案减少了内存的消耗。
3.4 使用大规模编码本进行检索
一个大规模编码本可能含有1百万个甚至更多的视觉词汇。其中一些步骤和小编码本方案比起来有很大的差异。
3.4.1 生成编码本
在将数据分配到大量集群中,近似方法是至关重要的。在检索社区中，两个有代表性的工作是：分层k-means(HKM)和近似k-means(AKM)，如图1和图3所示。HKM方法在2006年提出，HKM分层次地应用标准k-means方法进行特征训练。HKM首先将特征空间中的点划分为几个簇，接着递归地将每个簇划分为更多的群集。在每次递归时，每个点都要被归类为个簇中的某一个，聚类树的深度为，其中是期望得到的聚类簇数目。HKM的计算复杂度是，其中是训练样本数。当很大的时候，HKM的计算复杂度远小于扁平k-means（flat k-means）的计算复杂度（译者注：显然大规模编码本的要远小于）。另一个里程碑式的大规模编码本生成算法是AKM。该方法利用随机K-D树对K聚类中心进行索引，使得在分配步骤中能够高效地使用ANN搜索。
在AMK算法中，分配步骤的花费可以表示为，其中是K-D树中要访问的最近簇的候选数。因此AKM的计算复杂度与HKM相当，并且当K较大时，明显小于扁平k-means算法。实验表明AKM的量化误差要低于HKM，因此它要要优于HKM算法。在大多数基于AKM的方法中，最似最近邻检索算法选用FLANN。
3.4.2 特征编码（量化）
特征编码与编码本聚类是相互交错的，ANN检索对两者都至关重要。在AKM和HKM等一些经典方法中应用的ANN技术可用于聚类和编码中。在大规模编码本中，关键是要平衡量化误差和计算复杂度两者。在编码步骤中，诸如FV，稀疏编码的信息存留式编码方法大都不可行，因为它们的计算复杂度过高。因此，如何在保证量化效率的同时减少量化误差仍是一个极具挑战的问题。
对ANN方法来说，最早的解决方案是沿着分层树结构量化局部特征。不同级别的量化树节点被赋予不同的权重。然而，由于高度不平衡的树结构，该方法优于基于k-d树的量化方法：一个视觉词被分配给每个局部特征，使用从码书构建的k-d树来进行快速ANN搜索。对这种硬量化方案的一种改进是Philbin等人提出的软量化方案，这种方案将一个特征量化为几个最近的视觉词汇。由式指出，每个指定的视觉单词的权重与它到特征的距离呈负相关，其中d是描述符和聚类中心之间的距离。虽然软量化是基于欧几里得距离，但Mikulik等人提出通过无监督的匹配特征集为每个视觉单词找到相关的视觉单词。基于概率模型，这些备选词往往包含匹配特征的描述符。为了减少软量化的存储成本和查询视觉词汇的数量，Cai等提出当局部特征离最近的视觉词汇距离很远时，该特征可以被丢弃而且不会带来性能的下降。为了进一步加速量化，标量量化提出局部特征在没有明确训练的编码本的情况下被量化。浮点向量是二值化的，并且所得的二进制向量的第一维直接转换为十进制数作为视觉词汇。在高量化误差和低召回率的情况下，标量量化使用位翻转（bit-flop）来为局部特征生成数百个视觉词汇。
3.4.3 特征加权
TF-IDF. 视觉词汇在编码本中往往被分配给指定的权重。称为频率与逆文档频率（TF-IDF），这种策略被集成在BoW编码中。TF定义如下：
式中是视觉词汇在图像中出现的次数。另一方面，IDF通过全局统计来表明给定视觉词汇（对文档）的贡献。视觉词汇经典的IDF计算公式如下：
式中是图形数目，表示视觉词汇出现的图像编号。视觉词汇出现在图像中的TF-IDF值为：
改进方案。与视觉单词加权相关的一个主要问题是突变性。它指的是图像中出现重复结构的现象。这个问题往往在图像相似度中占主要位置。Jégou等人提出了几个TF的变种来解决突变问题。一个有效的策略是在TF上进行平方运算。Revaud等人提出了检测在不相关图像中频繁出现的关键点组来降低评分函数的计算值，而不是用相同的单词索引来分组特征。尽管上述两种方法都提出在量化后检测突变组，Shi等人提出在描述符阶段检测它们。检测到的突变描述符经过平均池化并且送往BoW结构中。在改进IDF方面，Zheng等人提出了IDF方法来处理突变情况，同时Murata等人设计了后来被并入到BM25公式的指数IDF。在大多数方案都以抑制突变性为目的时，Torii等人将这个问题视为体系结构的一个显着特征，并在突发性检测后设计新的相似性度量方法。
另一个特征加权策略是数据库端的特征增强，《Better matching with fewer features: The selection of useful features in large database recognition problems》和《Three things everyone should know to improve object retrieval》在这方面进行了研究。两篇文献中的方法都离线构建图像的图结构，通过边缘指示两个图像是否共享同一对象。对第一种方案来说，只有通过几何验证的特征才会被被保留，这降低了存储成本。然后，利用其连接图像的所有视觉字来增强基础图像的特征。第二种方案进一步进行对其进行改进，通过只添加那些被认为在增强图像中可见的视觉词汇，从而干扰性的视觉词被排除。
3.4.4 倒排
倒排是一种提高存储和检索效率的算法，它常被用于大/中等规模的编码本中，结构如图4所示。
图4：倒排索引的数据结构
倒排是一种单一尺寸的结构，其中每一个条目对应编码本中低的一个视觉词汇。每一个视觉词汇都包含一个倒排表，每个倒排表中的索引被称为索引特征或者记录。倒排索引很好地发挥了大规模编码本词汇直方图稀疏性的特点。新的文献提出新的检索方法来适应倒排算法。在基准方案中，图像ID和TF值都被存储在一条记录中。但其他的信息被整合进来时，它们的尺寸应该足够小。例如，在《Contextual weighting for vocabulary tree based image retrieval》中,原始数据在一条记录中被描述符上下文，描述符密度，平均关联日志规模和平均方向差异等属性量化。相似地，方向等空间信息也会被量化。在联合检索的方法中，当倒排索引随着全局一直近邻增长是，单独分割的图片将会被删除以减少内存消耗。在《The inverted multi-index》中提出，原始的单一尺寸倒排索引可以拓展为二维结构来进行替代了SITF特征向量的ANN检索。后来，这种方法被《Packing and padding: Coupled multi-index for accurate image retrieval》改进，融合局部颜色和SIFT描述符进行实例检索。
3.5 使用中等规模编码本进行检索
中等规模编码本一般含有10——200k个视觉词汇。视觉词汇展现了中等区分能力，同时检索时也使用了倒排索引。
3.5.1 编码本的生成与量化
考虑到中等规模编码本和大规模编码本相比，计算成本较低，扁平k-means可以在中等规模编码本的生成中使用。同样也有文献指出使用AKM算法可以在聚类中取得很好的效果。
在量化过程中，最近邻检索用来搜索最近的视觉词汇。实践表明使用高精度的ANN算法可以得到更好的检索效果。和大规模编码本下量化算法的研究热度比起来，中等规模编码本的研究明显低了很多。
3.5.2 汉明嵌入算法及其改进
在中等规模编码本下视觉词汇的区分度介于小规模编码本和大规模编码本之间。因此，对量化过程中带来的信息损失需要进行补偿。最终，汉明嵌入（HE）这个里程碑式的工作成为实践中的主流算法。
HE算法由Jégou等人在论文《Hamming embedding and weak geometric consistency for large scale image search》中提出，它提升了中等规模编码本下视觉词汇的区分能力，也是首次将一个SIFT描述符从维空间映射到维空间：
式中，是一二个投影矩阵，是一个低维向量。通过创建一个高斯随机矩阵同时对它使用分解，矩阵作为最后正交阵的前行，对于二值化，Jegou等人提出在每个Voronoi单元中使用描述符下降法来计算低维向量的中值向量。给定描述符和它的投影向量，HE计算它的视觉词汇，HE二值向量计算公式如下：
其中是第维的HE向量计算结果。二值特征作为特征匹配的第二重校验。当满足以下两个标准时，一对局部特征可以认为是匹配的：1) 它们是同一个视觉词汇；2) 它们的HE哈希值距离很小。HE的扩展方法通过指数函数估计特征和与Hamming距离的匹配强度：
其中，和分别代表特征和的二值向量，计算两个二值向量的汉明距离，是权重参数。如图6所示，HE及其加权版本在2008和2010年准确率大大提高。
HE应用于视频拷贝检测、图像分类和重排序等场合。例如，在图像分类中，例如，在图像分类中，将HE集成到基于线性核的SVM中，有效地提高了了图像块匹配相似度的速度。在图像重排序任务中，Tolias等人使用更低的HE阈值来找到类似于RANSAC得到的（图像局部特征）严格对应关系，并且得到的图像子集更可能包含真正应查得的图像。
有很多工作都对HE提升，特别是从匹配核的角度对HE进行改进。为了减少查询上的信息损失，Jain等人提出一种矢量二值距离比较法。它利用向量到超平面距离，同时保持倒排索引的效率。更进一步地，Qin等人在概率框架内设计一个高阶匹配核函数，并通过假匹配的距离分布自适应地标准化局部特征距离。该方法的思想类似于《Accurate image search using the contextual dissimilarity measure》，其中，根据每个视觉词汇的邻域分布，将字-字距离而不是特征-特征距离归一化。虽然在《Accurate image search using the contextual dissimilarity measure》中，一个词与它的邻居之间的平均距离被规范为几乎为恒定值，但后来在《Triangulation embedding and democratic aggregation for image search》中采用了将单个嵌入向量的贡献民主化的想法。在《To aggregate or not to aggregate: Selective match kernels for image search》中，Tolias等人表明VLAD和HE向量具有相似的性质，并提出了一种新的匹配核函数，它在局部特征聚合和特征到特征匹配之间进行折衷，使用和《Query adaptive similarity for large scale object retrieval》相似的匹配函数。他们还证明了在HE中使用更多比特位（例如128bit）优于原始64比特方案，代价是效率的降低。在《Scalar quantization for large scale image search》中使用了更多的比特位（256），但是这种方法可能使得结果的召回率相对较低。
3.6 其他重要问题
3.6.1 特征融合
局部-局部特征融合。 SIFT特征的一个问题就是它只提供了局部梯度描述，在图像中编码的其他判别信息仍然没有被利用。在图5(B)中，由于一对错误匹配在SIFT空间中的相似性，因此这对匹配没有被HE编码拒绝，但是其他局部（或区域）特征的融合可以纠正这个问题。
图5：错误匹配过滤方法：(A) HE, (B) 局部-局部特征融合, (C) 局部-全局特征融合
将SIFT与颜色描述符耦合是局部-局部特征融合的一个好选择。颜色-SIFT描述符融合特征的使用可以部分地解决不变性和辨别能力之间的权衡问题。在几个基准识别测试集上已经对几个诸如HSV-SIFT，HueSIFT和OpponentSIFT几个融合特征进行了评估。HSV-SIFT和HueSIFT特征都属于尺度，平移不变性特征。OpponentSIFT使用SIFT描述符描述对立的颜色空间中的所有通道，并且对光照颜色变化大的图像具有很强的鲁棒性。在《Evaluating color descriptors for object and scene recognition》中认为OpponentSIFT是当有关数据没有先验知识时的优先选择。在最近的工作中，二进制颜色签名都存储在倒排索引中。尽管现有的图像检索方法在一些数据集上取得了很好的检索精度，但一个潜在不容忽视：照明的密集变化可能会有损颜色特征检索的有效性。
局部-全局特征融合。 局部特征和全局特征从不同的角度来描述图像并互为补充。在图5(C)中，但局部（以及区域）信息不足以判断出一个错误的匹配对时，进一步整合更广的上下文尺度视觉信息是有效的。前期和后期融合是两种可能的方式。在前期融合中，图像邻域关系由如AlexNet中的FC8这样的全局特征挖掘出，并融合在基于SIFT的倒排索引中。在后期融合中，Zhang等人为每种类型的特征创建一个离线图，随后在在线查询期间进行特征融合。在对《Query specific fusion for image retrieval》中的方法进行改进时，Deng等人在《Visual reranking through weakly supervised multi-graph learning》提出增加弱监督锚（weakly supervised anchors）来协助图融合。两个工作都是在排序方面进行研究。对于分数级别的融合，将自动学习的类别的特定属性与预训练的类级别信息相结合。Zheng等人在《Query-adaptive late fusion for image search and person re-identification》中提出通过提取一些特征（局部或全局特征，好的或坏的特征）进行后期特征融合的自适应查询，并且以自适应查询的方式赋给特征相应的权重。
3.6.2 几何学上的匹配问题
BoW模型的一个常见问题是缺乏局部特征间的几何约束。几何验证可以用作各种场景的关键预处理步骤，例如拓展查询，特征选择，数据库端的特征增强，大规模咯物体挖掘等。著名的全局空间验证方法是RANSAC。RANSAC它重复计算每个对应的仿射变换，并通过适合变换的内点数来验证。RANSAC算法有效地重新排列排名最高的图像的子集，但存在效率问题。最终，如何在SIFT为基础的框架下有效、准确地结合空间信息被广泛地研究。
一个好的方法是研究局部特征间的空间上下文。例如，视觉短语在独立的视觉词汇中产生以提供更加精准的匹配规范。估计和聚合整个图像中的视觉词汇共现是一种研究思路，同时也有研究员研究视觉词汇在局部邻域中的聚类。视觉短语也可以通过临近图像块，随机空间分割和局部稳定区域（如MSER）的方式来组成。
另一种策略使用投票机制来检查几何一致性。在投票空间中，具有较大值的容器更可能代表真正的转换。其中一项重要的工作就是弱几何一致性（WGC），这种方法关注匹配特征在尺度和方向上的差异,不同空间则被量化到容器中。Hough投票方法被用来定位在规模或方向上相似或相异的子集。许多后来的研究工作可以看作是WGC的扩展。例如，Zhang等人的工作《Image retrieval with geometrypreserving visual phrases》可以被视为使用x，y偏移量而不是比例和方向的WGC方法。该方法具有目标平移不变性，但由于采用了刚体坐标量化，因此对尺度和旋转变化敏感。为了重新获得目标的尺度和旋转的不变性，Shen等人在《Object retrieval and localization with spatially-constrained similarity measure and k-nn re-ranking》中提出在应用多个变换后，量化查询区域的角度和尺度。Shen等人的这个方法的一个缺点就是，查询时间和存储效率的降低。实现高效的投票方法并减轻量化损失，论文《Hough pyramid matching: Speeded-up geometry re-ranking for large scale image retrieval》提出了霍夫金字塔匹配（HPM）方法，通过分层划分变换空间来分配匹配结果。HPM在灵活性和准确性之间取得了平衡，非常高效。还可以通过允许单个通信对多个容器进行投票来减少量化损失。HPM和这种方法都在速度上快于RANSAC算法，同时也可以被看作是对和HE一起提出的WGC在旋转和尺度不变性上的拓展。在《Pairwise geometric matching for large-scale object retrieval》中提出了一种基于投票的全局方向和尺度的粗略估计方法，以此来检验通过匹配特征得到的变形参数。《A vote-and-verify strategy for fast spatial verification in image retrieval》结合了基于假设的方法（如RANSAC）和基于投票的方法的优点，通过投票和后续的验证、精确微调来确定可能的假设。该方法保有了投票方法的效率，同时因为它的输出是显式变换和一组内值，因此还支持了查询扩展。
3.6.3 拓展查询
作为后处理步骤，拓展查询(QE)对提高检索的准确度很有帮助。简单地说，QE就是采用来自原始排名列表的多个排在前列的图像来发布新的查询，新的查询用于获得新的排名列表。QE可以增加额外的有区分度的特征到原始查询中，因此提高了召回率。
在实例检索任务中，Chum等人是第一个提出研究这项工作的。他们提出了平均拓展查询（AQE）方法，用排名靠前的图像的平均特征来发出新的查询。通常，空间验证用于重排序以及局部特征通过平均池化获得感兴趣区域。AQE被后来许多工作作为标准工具来使用。递归AQE和尺度-带递归QE是对AQE有效的改进，但它们的计算成本更大。四年后，Chum等从学习背景的混淆、扩展查询区域和增加空间验证的角度来改进QE。在《Three things everyone should know to improve object retrieval》中分别使用最靠前和最靠后图片作为训练正负样本。在线训练了一个线性支持向量机。学习到的权重向量用于计算平均查询。其他重要的QE算法的扩展包括基于互惠邻居思想的“hello neighbor”算法，基于排序的权重QE算法，汉明QE算法等。
3.6.4 小目标检索
检索图像中的一小部分对象是一项具有挑战性的任务由于1) 检测到的局部特征数量少，2) 背景噪声过大。TRECVID活动中的实例检索任务和logo检索任务都是小目标检索任务中的重要竞赛/应用。
一般来数，TRECVID任务和logo检索都可以用相似的流程来处理。对于基于关键点的检索方法，局部特征之间的空间上下文对区分目标是至关重要的，特别是对要求苛刻的小目标检索任务来说。其他有效的方法包括突发性处理，考虑查询对象和目标对象之间不同的比率。在第二种方法中，有效的可能区域或多尺度图像块可用作候选对象区域。在《Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations》中，提出了一种基于邻域图的区域扩散机制，以进一步提高小对象的查全率，达到了当时最高水平。
小结
本文是《SIFT Meets CNN: A Decade Survey of Instance Retrieval》的上篇，概述了图像检索任务极其发展历程，介绍了图像检索系统的基本架构和设计难点，详细展示了基于图像局部特征（以SIFT为代表）的检索流程以及核心算法。
在《SIFT Meets CNN: A Decade Survey of Instance Retrieval》的下篇中将介绍基于CNN特征的图像检索系统的流程及关键问题，并在几个常见数据集上测试六个经典检索系统的性能。最后文章将对图像检索领域的发展趋势进行展望，敬请期待。
参考资料
[SIFT Meets CNN: A Decade Survey of Instance Retrieval @TPAMI Volume 40 Issue 5 • May 2018]((https://ieeexplore.ieee.org/abstract/document/7935507/))
[SIFT Meets CNN: A Decade Survey of Instance Retrieval @arxiv](https://arxiv.org/abs/1608.01807)
[VLAD特征(vector of locally aggregated descriptors)](https://blog.csdn.net/happyer88/article/details/47054503)
[乘积量化（Product Quantization）](https://www.cnblogs.com/mafuqiang/p/7161592.html)