专栏首页AI科技时讯图像检索:基于内容的图像检索技术(四)

图像检索:基于内容的图像检索技术(四)

近似最近邻搜索

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

基于树的图像检索方法将图像对应的特征以树结构的方法组织起来,使得在检索的时候其计算复杂度降到关于图像库样本数目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.

本文分享自微信公众号 - AI科技时讯(aiblog_research),作者:小白菜

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • WWW2020 | 基于GNN和哈希学习的高效推荐系统

    最近看了篇利用哈希技术来提高基于图神经网络的推荐系统检索速度的文章。该文的亮点本人认为主要有以下两点:(1)模型同时学习用户/物品的实值表示和离散表示,用于协调...

    用户3578099
  • 图像检索:基于内容的图像检索技术(三)

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

    用户3578099
  • YOLO 目标检测从 V1 到 V3 结构详解

    在目标检测中,IoU 为预测框 (Prediction) 和真实框 (Ground truth) 的交并比。如下图所示,在关于小猫的目标检测中,紫线边框为预测框...

    用户3578099
  • 数据结构:哈希碰撞的本质及解决方式

    通过哈希函数产生了哈希碰撞,应该如何处理?在学习完哈希碰撞的解决方式之后,我们就可以完整地认识哈希表这种数据结构了。最后,我会带你来了解一个哈希表的常用高级应用...

    码农架构
  • 哈希算法的设计要点及应用场景

    大家好,我是多选参数的程序锅,一个正在 neng 操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇主要介绍了哈希算法相关的内容,包括什么是哈希算法、哈...

    syy
  • AI综述专栏| 大数据近似最近邻搜索哈希方法综述(上)(附PDF下载)

    在科学研究中,从方法论上来讲,都应先见森林,再见树木。当前,人工智能科技迅猛发展,万木争荣,更应系统梳理脉络。为此,我们特别精选国内外优秀的综述论文,开辟“综述...

    马上科普尚尚
  • 哈希表的理论知识

    哈希表又称散列表,若要存储的元素个数为n,设置一个长度为m(m >= n)的连续内存单元,以每个元素的关键字为自变量,通过一个称为哈希的函数把关键字映射为内存单...

    晚上没宵夜
  • [Redis] redis的hash类型底层结构哈希表

    redis hash的底层是压缩列表 和 哈希表两种形式 ,哈希表的形式是下面这样一层层嵌套的 , 转载自公众号 CodeSheep

    陶士涵
  • 朝花夕拾-哈希表(hashTable)

    所以在Aa,BB、Ab,BC时会出现碰撞。通过如下测试代码可以发现,他们的hashCode是相同的。

    皮皮熊
  • 哈希

    我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个...

    对弈

扫码关注云+社区

领取腾讯云代金券