最近邻搜索与近似最近邻搜索

基于内容的图像检索与基于文本的图像检索的一个不同之处在于，后者是精确查询，而前者属于典型的相似性查询(similarity search)问题，也称最近邻搜索(nearest neighbor search)或邻近搜索(proximity search)。如果将查询图像的特征理解为某个预设空间中的一个点，那么基于内容的图像检索可视为在该预设空间中，寻找与查询点距离最近或者距离值在某个阈值范围内的一组点的相似性查询问题。其中，预设空间可以是任意空间，比如特征空间、高斯核空间、语义空间等；距离可以通过某个距离度量函数定义，比如最常用的欧氏距离、余弦距离等。

精确的最近邻搜索问题的定义如下:

当数据量不大时，可以采用最简单直观的穷举搜索(exhaustive search，或称暴力搜索)。即基于线性扫描方式，将数据库中的候选点与查询点一一计算相似度，最后根据相似度的大小进行排序。然而，当数据量增大时，穷举搜索存在明显的局限性，一是穷举搜索的时间复杂度为线性复杂度O(｜X｜)，在数据规模增大时缺乏可扩展性；二是随着数据量的增加，原始数据的存储空间问题变得十分严峻。这使得穷举搜索无法满足高效搜索需求。

近似最近邻(approximate nearest neighbor search，ANN)搜索技术作为最近邻搜索的实用替代方案，综合考虑了高效的相似性查询涉及的三个核心问题:搜索精度、搜索效率和存储空间。近似最近邻搜索不是精确的相似性查询，而是找出那些在很高概率上属于最近邻的点，付出的计算代价仅为次线性甚至常数时间复杂度，目标是以尽可能低的检索性能换取大幅的检索效率提升。近似最近邻搜索的定义为:

d(r，q)≤(1＋ε)·d(r*，q)，ε＜0(7.1)(www.xing528.com)

式中，q为查询点，r*为精确解，ε为近似误差，d为某种预设距离函数。根据约束条件，可以将近似最近邻搜索算法分为误差约束最近邻搜索(error-constrained NN)和时间约束最近邻搜索(time-constrained NN)。误差约束最近邻搜索通过限制误差实现近似最近邻搜索，如(1＋ε)-近似最近邻搜索，对于任意常数ε＞0，可将搜索的计算复杂度降至O(dlog(P))；时间约束最近邻搜索则通过限制搜索时间实现近似最近邻搜索，在返回的k个近似最近邻尽可能接近k个精确最近邻的同时，使得搜索耗时尽可能小，可以通过缩短距离计算时间(如维度降低)或者减少距离计算次数(如设置计算次数提前终止搜索)来实现。

一类代表性的近似最近邻搜索算法是基于树结构的搜索。基于树结构的近似最近邻搜索的基本思想是采用树结构如KD树、M树、R树、R*树、SR树等对数据空间进行递归划分构建索引。这类搜索算法在处理维数较低的情况时，能大大降低搜索的计算复杂度[比如O(log(P))]，但在处理高维数据时计算性能急剧下降，最差的情况下退化为穷举搜索，即所谓的维数灾难。而目前大多计算机视觉任务都使用高维特征表示图像内容，并使用复杂的距离函数计算高维特征之间的距离，这使得单纯采用树结构的搜索算法力不从心。此外，基于树结构的搜索算法所耗费的内存资源也成为影响系统性能的瓶颈，很多情况下，存储树结构所需的空间甚至超过了存储原始数据的空间。尽管研究人员针对高维度量空间的高额距离计算代价问题，提出一些基于距离的广义度量空间高维索引结构，如VP树和MPV树等，但依然存在存储空间瓶颈的问题。

另一类代表性的近似最近邻搜索算法是基于哈希的搜索。基于哈希的近似最近邻搜索的基本思想是将高维向量映射到低维空间中，生成一个低维的哈希序列(哈希码)来表征图像，通过对比哈希码的距离实现相似性查询。近年来，哈希以其高检索效率和低存储空间的优势，受到了研究人员的广泛关注，现有的大规模图像检索通常是基于哈希实现的。特别是随着深度学习的兴起和蓬勃，结合了深度学习和哈希的深度哈希网络可以端到端学习哈希函数，且充分利用了深度学习强大的图像特征学习能力，已经成为大规模图像高效检索发展的必然趋势。