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

近似最近邻搜索

基于树结构的最近邻搜索方法和基于哈希的最近邻搜索方法在理论计算机科学、机器学习以及计算机视觉中是一个很活跃的领域，这些方法通过将特征空间划分成很多小的单元，以此减少空间搜索的区域，从而达到次线性的计算复杂度。

基于树的图像检索方法将图像对应的特征以树结构的方法组织起来，使得在检索的时候其计算复杂度降到关于图像库样本数目n的对数的复杂度。基于树结构的搜索方法有KD-树8、M-树9等。在众多的树结构搜索方法中，以KD-树应用得最为广泛，KD-树在构建树的阶段，不断以方差最大的维对空间进行划分，其储存对应的树结构则不断的向下生长，并将树结构保存在内存中，如图2.1右图示例了一个简单的KD-树划分过程：在搜索阶段，查询数据从树根节点达到叶节点后，对叶节点下的数据与查询数据进行逐一比较以及回溯方式从而找到最近邻。虽然基于树结构的检索技术大大缩减了单次检索的响应时间，但是对于高维特征比如维度为几百的时候，基于树结构的索引方法其在检索时候的性能会急剧的下降，甚至会下降到接近或低于暴力搜索的性能，如表2.1所示，在LabelMe数据集上对512维的GIST特征进行索引的时候，单次查询Spill树(KD-树的变形)耗时比暴力搜索用时还要多。此外，基于树结构的检索方法在构建树结构的时候其占用的存储空间往往要比原来的数据大得多，并且对数据分布敏感，从而使得基于树结构的检索方法在大规模图像数据库上也会面临内存受限的问题。

相比基于树结构的图像检索方法，基于哈希的图像检索方法由于能够将原特征编码成紧致的二值哈希码，使得基于哈希的图像检索方法能够大幅的降低内存的消耗，并且由于在计算汉明距离的时候可以使用计算机内部运算器具有的XOR异或运算，从而使的汉明距离的计算能够在微秒量级内完成，从而大大缩减了单次查询响应所需要的时间。如表2.1所示，在LabelMe图像数据集上，相比于暴力搜索方法以及基于树结构的搜索方法，通过将图像的特征编码后进行搜索，在编码位数为30比特时基于哈希的搜索方法单次查询时间比暴力搜索以及基于树结构的方法降低了将近4个数量级，并且特征维度由原来的512维降低至30维，因而极大的提高了检索的效率。

基于哈希的图像检索方法其关键之处在于设计一个有效的哈希函数集，使得原空间中的数据经过该哈希函数集映射后，在汉明空间其数据间的相似性能够得到较好的保持或增强。由于未经编码的特征在数域上是连续的，而哈希编码得到的是一个二值哈希码，也就是说从数域上来讲哈希函数集是一个将数值从连续域变换到离散域的过程，因而会导致在优化哈希函数集时往往难于求解10，从而使得设计一个有效的哈希函数集极其不易。在过去的十几年里，尽管设计有效的哈希函数集面临很大的挑战，但研究者们仍然提出了很多基于哈希的图像检索方法，其中最经典的哈希方法是局部敏感哈希方法11(LSH, Locality Sensitive Hashing)。

局部敏感哈希被认为是高维空间(比如成百上千维)快速最近邻搜索的重要突破，它在构造哈希函数的时候采用随机超平面的方法，即使用随机超平面将空间分割成很多子区域，每一个子区域可以被视为一个”桶”，如图2.1右图所示。在构建阶段，局部敏感哈希仅需要生成随机超平面，因而没有训练的过程；在索引阶段，样本被映射成二进制哈希码，如图2.1右图示意的二进制哈希码，具有相同的二进制哈希码的样本被保存在同一个“桶”中；在查询阶段，查询样本通过同样的映射后可以锁定查询样本位于哪个“桶”中，然后在锁定的”桶”中将查询样本与该“桶”中的样本进行逐一的比较，从而得到最终的近邻。局部敏感哈希其有效性在理论分析中得到了保证，但是由于局部敏感哈希在构造哈希函数过程中并没有利用到数据本身，使得在应用局部敏感哈希时为了获得较高的精索精度常常采用很长的编码位，但在长编码位数下会降低相似样本在哈希离散过程中的碰撞概率，从而导致检索的召回率会出现比较大的下降，因此出现了多个哈希表的局部敏感哈希。在相同的编码长度下，相比于只有一个哈希表的局部敏感哈希(即单哈希表局部敏感哈希)，多哈希表局部敏感哈希中的每一个哈希表的编码长度减小为单哈希表局部敏感哈希编码长度的L分之一倍(假设L为多哈希表局部敏感哈希)，因此多哈希表局部敏感哈希能够获得比具有相同编码长度的单哈希表局部敏感哈希更高的召回率，但无论是多哈希表局部敏感哈希还是单哈希表局部敏感哈希，它们的编码都不是紧致的，从而使得它们在内存使用效率方面并不是很有效。

在面向大规模图像检索时，除了采用图像哈希方法外，还有另一类方法，即向量量化的方法，向量量化的方法中比较典型的代表是乘积量化(PQ, Product Quantization)方法，它将特征空间分解为多个低维子空间的笛卡尔乘积，然后单独地对每一个子空间进行量化。在训练阶段，每一个子空间经过聚类后得到k

个类心(即量化器)，所有这些类心的笛卡尔乘积构成了一个对全空间的密集划分，并且能够保证量化误差比较小；经过量化学习后，对于给定的查询样本，通过查表的方式可以计算出查询样本和库中样本的非对称距离12。乘积量化方法虽然在近似样本间的距离时比较的精确，但是乘积量化方法的数据结构通常要比二值哈希码的复杂，它也不能够得到低维的特征表示，此外为了达到良好的性能必须加上不对称距离，并且它还需要每个维度的方差比较平衡，如果方差不平衡，乘积量化方法得到的结果很差。

参考文献

1. LOWE D G. Distinctive Image Features from Scale-Invariant Keypoints, Int. J. Comput. Vis., 2004, 60(2):91–110.
2. BAY H, TUYTELAARS T, GOOL L J V. SURF: Speeded Up Robust Features, Proc. IEEE Int. Conf. Comput. Vis., 2006:404–417.
3. RUBLEE E, RABAUD V, KONOLIGE K, et al. ORB: An Efficient Alternative to SIFT or SURF, Proc. IEEE Int. Conf. Comput. Vis., 2011:2564–2571.
4. CSURKA G, DANCE C, FAN L, et al. Visual Categorization with Bags of Keypoints, Workshop on statistical learning in computer vision, Eur. Conf. Comput. Vis., 2004,1:1–2.
5. JEGOU H, DOUZE M, SCHMID C, et al. Aggregating Local Descriptors into A Compact Image Representation, Proc. IEEE Int. Conf. Comput. Vis. Pattern Recognit., 2010:3304–3311.
6. PERRONNIN F, SÁNCHEZ J, MENSINK T. Improving the Fisher Kernel for Large-Scale Image Classification, Proc. Eur. Conf. Comput. Vis., 2010:143–156.
7. KIAPOUR M H, HAN X, LAZEBNIK S, et al. Where to Buy It: Matching Street Clothing Photos in Online Shops, Proc. IEEE Int. Conf. Comput. Vis., 2015:3343–3351.
8. BENTLEY J L. Multidimensional Binary Search Trees Used for Associative Searching, Commun. ACM, 1975, 18(9):509–517.
9. UHLMANN J K. Satisfying General Proximity/Similarity Queries with Metric Trees, Inf. Process. Lett., 1991, 40(4):175–179.
10. GE T, HE K, SUN J. Graph Cuts for Supervised Binary Coding, Proc. Eur. Conf. Comput. Vis., 2014:250–264.
11. DATAR M, IMMORLICA N, INDYK P, et al. Locality-Sensitive Hashing Scheme Based on p-stable Distributions, Proc. Symp. Comput. Geom., 2004:253–262.
12. DONG W, CHARIKAR M, LI K. Asymmetric Distance Estimation with Sketches for Similarity Search in High-dimensional Spaces, Proc. ACM SIGIR Conf. Res. Develop. Inf. Retr., 2008:123–130.