图像检索：基于内容的图像检索技术（三）

大规模图像检索特点

无论是对于相同物体图像检索还是相同类别图像检索，在大规模图像数据集上，它们具有三个典型的主要特征：图像数据量大、特征维度高以及要求相应时间短。下面对这三个主要特征逐一展开说明：

(1) 图像数据量大。得益于多媒体信息捕获、传输、存储的发展以及计算机运算速度的提升，基于内容的图像检索技术经过十几年的发展，其需要适用的图像规模范围也从原来的小型图像库扩大到大规模图像库甚至是海量图像数据集，比如在上世纪九十年代图像检索技术发展的早期阶段，研究者们在验证图像检索算法性能的时候，用得比较多是corel1k，该图像库共1000张图片，与今天同样可以用于图像检索的最流行的图像分类库imageNet数据集相比，其量级已经有了成千上万倍的增长，因而图像检索应满足大数据时代的要求，在大规模图像数据集上应该具备伸缩性。

(2) 特征维度高。图像特征作为直接描述图像视觉内容的基石，其特征表达的好坏直接决定了在检索过程中可能达到的最高检索精度。如果前置特征未表达好，在构建后置检索模型的时候，不但会复杂化模型的构建，增加检索查询的响应时间，而且能够提升的检索精度也是极其有限的。所以在特征提取之初，应该有意识的选取那些比较高层特征。如果将局部特征表达方式也作为”高维”的一种，那么特征的描述能力跟特征的维度高低具有较大的关联，因而在特征描述方面大规模图像检索具有明显的特征维度高的特性，比如词袋模型BoW、VLAD、Fisher向量以及CNN特征。为了对这些高维的特征有一个维度量级的定量认识，本文以词袋模型构建的特征向量为例，在牛津大学建筑物图像数据集上试验了特征维度(在数值上跟聚类单词数目大小相等)对检索精度的影响，从图1.2中可以看到，词袋模型的特征维度是非常高的。因此，面向大规模图像数据集检索的另一个典型特点是图像特征描述向量维度高。

(3) 要求响应速度快。对于用户的查询，图像检索系统应该具备迅速响应用户查询的能力，同时由于大规模图像数据量大、特征维度高，直接采用暴力搜索(Brute Search) 索引策略(也称为线性扫描)难以满足系统实时性的要求，图1.2右图所示的是在牛津大学建筑物图像数据集上平均每次查询所耗费的时间，可以看到在图像数量仅有4063张的牛津大学建筑物图像集，其查询时间在单词数目为100万且重排深度为1000的条件下就需要耗费1 秒左右的时间，并且整个程序还是运行在一台高配的服务器上，因此，大规模图像检索需要解决系统实时响应的问题。

基于哈希的图像检索技术其具体框架如图1.4所示，按步骤可以分为特征提取、哈希编码、汉明距离排序以及重排四个步骤：

(1) 特征提取。对图像数据库中的图像逐一进行特征提取，并将其以图像文件名和图像特征一一对应的方式添加到特征库中；

(2) 哈希编码。哈希编码可以拆分成为两个子阶段，在对特征进行编码之前需要有哈希函数集，而哈希函数集则通过哈希函数学习阶段而得到，因此这两个子阶段分别为哈希函数学习阶段和正式的哈希编码阶段。在哈希函数学习阶段，将特征库划分成训练集和测试集，在训练库上对构造的哈希函数集H进行训练学习；正式的哈希编码阶段时，分别将原来的特征xi代入到学习得到的哈希函数集H

中，从而得到相应的哈希编码。值得注意的是，如果设计的哈希算法已经经过实验验证有效，那么在实际的应用系统中，在划分数据集的时候，可以将整个图像库既作为训练集也作为图像数据库，从而使得在大规模图像上学到的哈希函数具备较好的适应性；

(3) 汉明距离排序。在汉明距离排序阶段，对于给定的查询图像，逐一计算查询图像对应的哈希编码到其他各个哈希编码之间的汉明距离，然后按从小到大的顺序进行相似性排序，从而得到检索结果；

(4) 重排。针对步骤(3)汉明排序后的结果，可以前M个结果或者对汉明距离小于某一设置的汉明距离d

的结果进行重排。一般地，在重排的时候采用欧式距离作为相似性度量得到重排后的结果。因此，从这里可以看到，哈希过程可以看作是筛选候选样本或是粗排序的过程。在采用哈希方法进行大规模图像检索的应用系统中，通常会有重排这一步，但是在设计哈希算法的时候，对性能进行指标评价直接采用的是汉明距离，也就是在评价哈希算法性能的时候，不需要重排这一步。

随着视觉数据的快速增长，面向大规模视觉数据的基于内容的图像检索技术不论是在商业应用还是计算机视觉社区都受到了极大的关注。传统的暴力(brute-force) 搜索方法(又称线性扫描)通过逐个与数据库中的每个点进行相似性计算然后进行排序，这种简单粗暴的方式虽然很容易实现，但是会随着数据库的大小以及特征维度的增加其搜索代价也会逐步的增加，从而使得暴力搜索仅适用于数据量小的小规模图像数据库，在大规模图像库上这种暴力搜索的方式不仅消耗巨大的计算资源，而且单次查询的响应时间会随着数据样本的增加以及特征维度的增加而增加，为了降低搜索的空间的空间复杂度与时间复杂度，在过去的十几年里研究者们找到了一种可供替代的方案— 近似最近邻(ANN, Approximate Nearest Neighbor)搜索方法，并提出了很多高效的检索技术，其中最成功的方法包括基于树结构的图像检索方法、基于哈希的图像检索方法和基于向量量化的图像检索方法。