为您推荐:
精华内容
最热下载
问答
  • 5星
    333KB HowardEmily 2021-01-14 12:11:19
  • 5星
    2.87MB Darius_Tanz 2021-09-20 10:56:03
  • 5星
    18.25MB ylcto 2020-12-23 13:59:32
  • 5星
    10.33MB weixin_44573410 2021-01-20 19:58:27
  • 5星
    3.44MB q6115759 2021-03-23 09:49:31
  • 5星
    82.04MB GZXGYZ 2021-03-17 22:28:57
  • 15.61MB Q1321814823 2021-03-07 00:27:12
  • 514KB weixin_39840924 2019-08-16 13:12:07
  • 图像检索基于内容的图像检索技术 背景与意义 在Web2.0时代,尤其是随着Flickr、Facebook等社交网站的流行,图像、视频、音频、文本等异构数据每天都在以惊人的速度增长。例如, Facebook注册用户超过10亿,每月...

     

    背景与意义

    在Web2.0时代,尤其是随着Flickr、Facebook等社交网站的流行,图像、视频、音频、文本等异构数据每天都在以惊人的速度增长。例如, Facebook注册用户超过10亿,每月上传超过10亿的图片;Flickr图片社交网站2015年用户上传图片数目达7.28亿,平均每天用户上传约200万的图片;中国最大的电子商务系统淘宝网的后端系统上保存着286亿多张图片。针对这些包含丰富视觉信息的海量图片,如何在这些浩瀚的图像库中方便、快速、准确地查询并检索到用户所需的或感兴趣的图像,成为多媒体信息检索领域研究的热点。基于内容的图像检索方法充分发挥了计算机长于处理重复任务的优势,将人们从需要耗费大量人力、物力和财力的人工标注中解放出来。经过十来来的发展,基于内容的图像检索技术已广泛应用于搜索引擎、电子商务、医学、纺织业、皮革业等生活的方方面面。

    图像检索按描述图像内容方式的不同可以分为两类,一类是基于文本的图像检索(TBIR, Text Based Image Retrieval),另一类是基于内容的图像检索(CBIR, Content Based Image Retrieval)。

    基于文本的图像检索方法始于上世纪70年代,它利用文本标注的方式对图像中的内容进行描述,从而为每幅图像形成描述这幅图像内容的关键词,比如图像中的物体、场景等,这种方式可以是人工标注方式,也可以通过图像识别技术进行半自动标注。在进行检索时,用户可以根据自己的兴趣提供查询关键字,检索系统根据用户提供的查询关键字找出那些标注有该查询关键字对应的图片,最后将查询的结果返回给用户。这种基于文本描述的图像检索方式由于易于实现,且在标注时有人工介入,所以其查准率也相对较高。在今天的一些中小规模图像搜索Web应用上仍有使用,但是这种基于文本描述的方式所带来的缺陷也是非常明显的:首先这种基于文本描述的方式需要人工介入标注过程,使得它只适用于小规模的图像数据,在大规模图像数据上要完成这一过程需要耗费大量的人力与财力,而且随时不断外来的图像在入库时离不开人工的干预;其次,”一图胜千言”,对于需要精确的查询,用户有时很难用简短的关键字来描述出自己真正想要获取的图像;再次,人工标注过程不可避免的会受到标注者的认知水平、言语使用以及主观判断等的影响,因此会造成文字描述图片的差异。

    随着图像数据快速增长,针对基于文本的图像检索方法日益凸现的问题,在1992年美国国家科学基金会就图像数据库管理系统新发展方向达成一致共识,即表示索引图像信息的最有效方式应该是基于图像内容自身的。自此,基于内容的图像检索技术便逐步建立起来,并在近十多年里得到了迅速的发展。典型的基于内容的图像检索基本框架如上图1.1所示,它利用计算机对图像进行分析,建立图像特征矢量描述并存入图像特征库,当用户输入一张查询图像时,用相同的特征提取方法提取查询图像的特征得到查询向量,然后在某种相似性度量准则下计算查询向量到特征库中各个特征的相似性大小,最后按相似性大小进行排序并顺序输出对应的图片。基于内容的图像检索技术将图像内容的表达和相似性度量交给计算机进行自动的处理,克服了采用文本进行图像检索所面临的缺陷,并且充分发挥了计算机长于计算的优势,大大提高了检索的效率,从而为海量图像库的检索开启了新的大门。不过,其缺点也是存在的,主要表现为特征描述与高层语义之间存在着难以填补的语义鸿沟,并且这种语义鸿沟是不可消除的。

    基于内容的图像检索技术在电子商务、皮革布料、版权保护、医疗诊断、公共安全、街景地图等工业领域具有广阔的应用前景。在电子商务方面,谷歌的Goggles、 阿里巴巴的拍立淘等闪拍购物应用允许用户抓拍上传至服务器端,在服务器端运行图片检索应用从而为用户找到相同或相似的衣服并提供购买店铺的链接;在皮革纺织工业中,皮革布料生产商可以将样板拍成图片,当衣服制造商需要某种纹理的皮革布料时,可以检索库中是否存在相同或相似的皮革布料,使得皮革布料样本的管理更加便捷;在版权保护方面,提供版权保护的服务商可以应用图像检索技术进行商标是否已经注册了的认证管理;在医疗诊断方面,医生通过检索医学影像库找到多个病人的相似部位,从而可以协助医生做病情的诊断……基于内容的图像检索技术已经深入到了许许多多的领域,为人们的生活生产提供了极大的便利。

    基于内容的图像检索技术

    相同物体图像检索

    相同物体图像检索是指对查询图像中的某一物体,从图像库中找出包含有该物体的图像。这里用户感兴趣的是图像中包含的特定物体或目标,并且检索到的图片应该是包含有该物体的那些图片。如1.3图所示,给定一幅”蒙娜丽莎”的画像,相同物体检索的目标就是要从图像库中检索出那些包含有”蒙娜丽莎”人物的图片,在经过相似性度量排序后这些包含有”蒙娜丽莎”人物的图片尽可能的排在检索结果的前面。相似物体检索在英文文献中一般称为物体检索(Object Retrieval),近似样本搜索或检测(Duplicate Search or Detection)也可以归类于相同物体的检索,并且相同物体检索方法可以直接应用到近似样本搜索或检测上。相同物体检索不论是在研究还是在商业图像搜索产业中都具有重大的价值,比如购物应用中搜索衣服鞋子、人脸检索等。

    对于相同物体图像检索,在检索相同的物体或目标时,易受拍摄环境的影响,比如光照变化、尺度变化、视角变化、遮挡以及背景的杂乱等都会对检索结果造成较大的影响,图1.3左图给出了这几种变化的例子,此外,对于非刚性的物体,在进行检索时,物体的形变也会对检索结果造成很大的影响。

    由于受环境干扰比较大,因而对于相同物体图像检索,在选取特征的时候,往往会选择那些抗干扰性比较好的不变性局部特征,比如SIFT1、SURF2、ORB3等,并以此为基础通过不同的编码方式构建图像的全局描述,具有代表性的工作有词袋模型4(BoW, Bag of Words) 局部特征聚合描述符5(VLAD, Vector of Locally Aggregated Descriptors)以及Fisher向量6(FV, Fisher Vector),这一类以类SIFT为基础的图像检索方法,由于结合了类SIFT不变性的特性,并且采用了由局部到全局的特征表达方式,并且在实际应用时在提取SIFT 的时候还可以使用siftGPU加速SIFT提取,因而从整体上来说能够获得比较好的检索效果,但这一类方法通常其特征维度往往是非常高的,如图1.2所示,在牛津建筑物图像数据库上采用词袋模型进行检索,为了获得较高的检索精度,在聚类时聚类数目一般都设置到了几十万,因而其最终表示的特征其维度高达几十万维,因此为它们设计高效的索引方式显得十分必要。

    相同类别图像检索

    对给定的查询图片,相似图像检索的目标是从图像库中查找出那些与给定查询图像属于同一类别的图像。这里用户感兴趣的是物体、场景的类别,即用户想要获取的是那些具有相同类别属性的物体或场景的图片。为了更好的区分相同物体检索和相同类别检索这两种检索方式区,仍以图1.3左图所举的”蒙娜丽莎”为例,用户如果感兴趣的就是”蒙娜丽莎”这幅画,那么检索系统此时工作的方式应该是以相同物体检索的方式进行检索,但如果用户感兴趣的并不是”蒙娜丽莎”这幅画本身,而是”画像”这一类图片,也就是说,用户所感兴趣的已经是对这幅具体的画进行了类别概念的抽象,那么此时检索系统应该以相同类别检索的方式进行检索。相同类别图像检索目前已广泛应用于图像搜索引擎,医学影像检索等领域。

    对于相同类别图像检索,面临的主要问题是属于同一类别的图像类内变化巨大,而不同类的图像类间差异小。如图1.3右图所示,对于”湖泊”这一类图像,属于该类别的图像在表现形式上存在很大的差异,而对于图??????右图下面所示的”dog” 类和”woman”类两张图像,虽然它们属于不同的类,但如果采用低层的特征去描述,比如颜色、纹理以及形状等特征,其类间差异非常小,直接采用这些特征是很难将这两者分开的,因此相同类别图像检索在特征描述上存在着较大的类内变化和较小的类间差异等挑战。近年来,以深度学习(DL, Deep Learning)为主流的自动特征在应用到相同类别图像检索上时,能够极大的提高检索的精度,使得面向相同物体的检索在特征表达方面得到了较好的解决。目前,以卷积神经网络(CNN, Convolutional Neural Network)为主导的特征表达方式也开始在相同物体图像检索上进行展开,并已有了一些相应的工作7,但由于相同物体在构造类样本训练数据时并不像相同类别图像检索那样那么方便,因而相同物体图像检索在CNN模型训练以及抽取自动特征等方面还有待深入。不管是相同物体图像检索还是相同类别图像检索,在使用CNN模型提取自动特征的时候,最终得到的维度一般是4096维的特征,其维度还是比较高的,直接使用PCA等降维的手段,虽然能达到特征维度约减的目的,但在保持必要的检索精度前提下,能够降低的维度还是有限的,因而对于这一类图像检索,同样有必要为它构建够高效合理的快速检索机制,使其适应大规模或海量图像的检索。

    大规模图像检索特点

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

    (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(x)=h1(x),h2(x),…,hK(x)H(x)=h1(x),h2(x),…,hK(x) 进行训练学习;正式的哈希编码阶段时,分别将原来的特征xi(i=1,2,…,N)xi(i=1,2,…,N) 代入到学习得到的哈希函数集H(x)H(x) 中,从而得到相应的哈希编码。值得注意的是,如果设计的哈希算法已经经过实验验证有效,那么在实际的应用系统中,在划分数据集的时候,可以将整个图像库既作为训练集也作为图像数据库,从而使得在大规模图像上学到的哈希函数具备较好的适应性;

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

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

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

    近似最近邻搜索

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

    基于树的图像检索方法将图像对应的特征以树结构的方法组织起来,使得在检索的时候其计算复杂度降到关于图像库样本数目nn的对数的复杂度。基于树结构的搜索方法有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右图示意的二进制哈希码,具有相同的二进制哈希码的样本被保存在同一个“桶”中;在查询阶段,查询样本通过同样的映射后可以锁定查询样本位于哪个“桶”中,然后在锁定的”桶”中将查询样本与该“桶”中的样本进行逐一的比较,从而得到最终的近邻。局部敏感哈希其有效性在理论分析中得到了保证,但是由于局部敏感哈希在构造哈希函数过程中并没有利用到数据本身,使得在应用局部敏感哈希时为了获得较高的精索精度常常采用很长的编码位,但在长编码位数下会降低相似样本在哈希离散过程中的碰撞概率,从而导致检索的召回率会出现比较大的下降,因此出现了多个哈希表的局部敏感哈希。 在相同的编码长度下,相比于只有一个哈希表的局部敏感哈希(即单哈希表局部敏感哈希),多哈希表局部敏感哈希中的每一个哈希表的编码长度减小为单哈希表局部敏感哈希编码长度的LL 分之一倍(假设LL 为多哈希表局部敏感哈希),因此多哈希表局部敏感哈希能够获得比具有相同编码长度的单哈希表局部敏感哈希更高的召回率,但无论是多哈希表局部敏感哈希还是单哈希表局部敏感哈希,它们的编码都不是紧致的,从而使得它们在内存使用效率方面并不是很有效。

    在面向大规模图像检索时,除了采用图像哈希方法外,还有另一类方法,即向量量化的方法,向量量化的方法中比较典型的代表是乘积量化(PQ, Product Quantization)方法,它将特征空间分解为多个低维子空间的笛卡尔乘积,然后单独地对每一个子空间进行量化。在训练阶段,每一个子空间经过聚类后得到kk个类心(即量化器),所有这些类心的笛卡尔乘积构成了一个对全空间的密集划分,并且能够保证量化误差比较小;经过量化学习后,对于给定的查询样本,通过查表的方式可以计算出查询样本和库中样本的非对称距离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. 

     

    展开全文
    weixin_41521681 2020-12-14 22:59:49
  • 166KB phytle0 2020-06-29 11:33:01
  • 作者:赵丽丽 ...基于内容的图像检索(CBIR, Content Based Image Retrieval)是相对成熟的技术领域,在工业界也有广泛的应用场景,如搜索引擎(Google、百度)的以图搜图功能,各电商网站(淘宝、Amazo...
     
    

    基于内容的图像检索(CBIR, Content Based Image Retrieval)是相对成熟的技术领域,在工业界也有广泛的应用场景,如搜索引擎(Google、百度)的以图搜图功能,各电商网站(淘宝、Amazon、ebay)的相似商品搜索,社交平台(Pinterest)的相似内容推荐等。本文从图像检索流程出发,结合我们团队在社交应用中的相似图片、视频检索中的实践经验,介绍构建基于内容的图像检索系统所涉及的算法技术,包括特征提取、索引构建、近邻搜索等技术,供相关领域研发人员参考。

    在介绍视觉内容检索流程前,先来回顾下文本检索流程。

    一、相似文本检索

    image

    构建词库是离线操作,主要对目标数据集中的文本进行解析提取词干信息,建立当前数据集的词库,然后基于词库,对数据集中所有文档提取本文特征。构建词库在整个检索系统生命周期开始阶段实施,一般情况仅执行一次,是针对目标检索文本数据集进行的非频繁性操作。

    构建索引和检索是在线操作。其中,构建索引是在检索服务启动时进行,负责将目标数据集的文本特征以某种方式组织到内存中,方便后续快速检索和距离计算。检索阶段查找目标库中与查询内容query相近的文本结果,该阶段提取query文档的文本特征,同目标库中的各文档的特征向量进行距离计算,对结果进行排序,返回距离最近特征向量对应的文档索引。

    文本检索过程实际上可以理解为文本特征匹配的过程,以上过程文本使用词袋向量(Bag-of-Words,BoW)来表征文本内容。BoW是常用的一种文本特征表示,它通过统计单词在文档中出现的频次来表示一个文档,因其简单有效的优点得到了广泛应用。BoW特征提取过程包括以下几个步骤:

    1. 将文档中的文本解析成单词。
    2. 使用词干表示各单词,去掉常用词。
    3. 统计当前文档中每个单词(词干)出现的频次。
    4. 建立表示该文档的向量,向量的每次元素代表对应位置的单词出现的频次,向量长度等于词库内单词个数。在构建词向量时,通常会引入加权机制。常用的一种加权方式为采用tf-idf (term frequecy-inverse document frequency)。tf-idf的计算方式如下:

    假设词库共有k个单词,当前文档doc用词向量image表示,其中ti的计算方式为image。其中, nid 为词库中第i个单词在文档doc中出现的次数,nd为文档doc包含的单词总数, ni为单词i在整个目标文档库中出现的次数,N为目标库包含的文档总数。可以看出,文档d的词向量中的每个元素是由两项乘积构成,第一项 为词频nid/nd,它会增加在当前文档中出现频次较高的单词的权重;第二项 log(N/ni)会降低在目标库中出现频次较高的单词的权重。

    二、基于内容的图像检索流程

    图像内容检索流程与文本检索流程类似,但二者信息表征方法不同。文本通过词频计算BoW来表征一段文本内容,而图像则使用视觉特征来表示。Google团队2003年[1]提出的视频内容检索方法借鉴文本检索流程,使用局部特征构建视觉词袋向量(Bag-of-Visual-Words,BoVW),也称BoF(Bag-of-Features),来表示图像。这里的视觉单词是指量化后的视觉特征。Video-Google[1]中检索系统也分为构建词库、构建索引和检索三部分。下图是视觉词库构建流程:

    image

    对图像提取若干个局部特征描述子,如sift,对这些描述子进行量化。量化器通常通过聚类得到:对特征描述子集合进行k-means聚类,聚类后得到的k个质心即为视觉单词。描述子desc的量化结果q(desc)为与desc最相近的质心的索引。所有质心构成了视觉词表。图像中的特征单词的词频构成了该图像的向量描述BoVW。假设视觉词表中的单词个数为N,那么BoVW向量的长度为N,向量中的元素为对应单词出现在该图像中的频次或者采用采用td-idf权重更新向量中每个元素值。

    基础得到的视觉词库,计算所有图像(或视频中帧)数据的BoVW向量。检索进程启动时,将目标数据库中所有图像的BoVW向量构建索引。输入一副检索图像,提取该图像的BoVW特征,与目标库向量进行距离比对,查找近邻向量。 最直观的查找方法是蛮力查找即将查询向量q与所有的BoVW向量进行距离计算。这种穷举方式对大数据集或高维向量的查找效率非常低。为改进这个问题,Video-Google[1]提出采用倒排文件IVF结构进行索引构建,IVF索引结构如下图所示。图中i表示每个视觉单词。

    image
    由于词向量通常是很稀疏的,我们无需遍历目标库中的所有文件,因而可以通过建立倒排文件,对每个单词构建一个列表,列表中是所有包含当前单词的图像meta信息。检索时,只需要计算那些与当前查询图像包含相同单词的图像的BoVW向量间的距离即可,即通过减小搜索范围来降低搜索复杂度。

    Video-Google提供了经典的基于内容的图像检索流程,核心技术可以总结为两点:特征提取和近邻查找。后续图像检索基于大多基于此思想,针对不同业务场景下的数据特点,对涉及的特征提取和近邻查找技术进行优化,最终目标是提取能够高效表征图像的特征向量,进行快速视觉内容查找。

    image
    以下分别对近几年面向检索应用的特征提取和快速近邻查找的经典算法技术进行介绍

    三、图像特征提取技术

    图像视觉特征分为多种,从存储形式分为浮点特征和二进制特征,从提取方式上分为传统特征和深度特征。卷积神经网络(CNN)出现之前,大部分特征是基于手工设计的提取算法进行特征提取,如sift、hog、harr、gist等。卷积神经网络在多项视觉任务如分类、检测、分割等表现出 state-of-the-art 的效果,在图像检索领域,基于CNN提取的深度特征同样也表现出远优于传统特征的效果。

    无论是传统特征还是深度特征,从表征内容上可以化分为局部特征和全局特征。如传统特征sift为局部特征,而gist为全局特征;深度神经网络的卷积层输出feature map可理解为局部特征,而全连接层FC输出可视为图像的全局特征。使用局部特征表征图像时,需要将局部特征聚合成为能够表征图像整体信息的全局特征。此外,特征聚合还可以将不同数量的局部特征编码到同一长度,比如不同图像的sift特征个数是不同,使用聚合方法可以使得每张图像的特征表示长度相等。

    3.1 特征Embedding

    前面介绍的video-google使用BoVW向量来表征一副图像,是一种聚合方式。当视觉单词数量较多时,BoVW维度很高,对于类别复杂的大规模图像数据集,维度甚至会高达几百万,实际应用时会严重影响检索性能。此外,原始局部特征如sift具备一定的噪声,其可辨识性(discriminability)是受限的,即来自不相关的两幅图像的两个sift特征很有可能会被匹配成相似。因此,后续有许多局部特征Embedding的方法提出,用来将局部特征聚合生成更强可辨识性的图像特征。这些方法通常会生成比原始局部特征更高维度的向量,尽管如此,Embedding后的向量维度也远远低于BoVW的维度。常用的Embedding方法有VLAD[2]、Fisher Vector[3],Triangular embedding[4]等,已有实验表明这些方法应用于传统局部特征后得到的embedding特征能有效提高图像检索准确率。以下简单介绍VLAD和Fisher Vector的思想。

    VLAD具体思路如下:基于学习数据中的所有局部特征向量x(d维),使用K-means聚类,得到k个质心{c1,c2,…ck};图像的VLAD表示是一个kxd维的向量,向量元素Vi,j,image为质心索引, image 为局部特征向量中每个元素的索引,对每个输入向量x,计算距离它最近的质心向量ci,则v
    i,j为所有距离ci最近的特征向量与ci 之间的差异在对应向量位置j上的累积和,即image。最后,对得到的 Vi,j向量使用L2范式进行归一化。质心数k通常取16~256即可得到较好的效果。

    Fisher Vector[3]可以通俗的将Fisher Vector理解为对高斯混合分布GMM的参数均值、方差和分量权重球偏导得到的梯度向量。其物理含义为:对于两幅不同的输入图像,其特征点的分布可能是相同的,但是其变化方向(梯度)相同的概率非常小,因此可以用分布的梯度来更加准确地表示输入图像。具体细节参见原始论文。Fisher Vector也是对原图像特征进行升维操作,假设原始特征向量维度为d,GMM分量个数为N,Fisher Vector的维度为(1 + d + d)* N - 1 。原始论文非常理论,感兴趣的可以读一下

    以上聚合方法的特征维度比原始特征维度更高,因此若后续对聚合后的特征进行PCA操作,会增加计算复杂度,同时还可能导致数据过拟合。

    3.2 深度特征

    Neural Codes for Image Retrieval[5]这篇文章评估了基于CNN的深度特征应用于图像检时的效果。以下是论文给出的一些结论:

    1. 在分类数据集上训练得到的深度特征应用于不同数据集的检索任务时仍然起作用;
    2. 在检索数据集上finetune分类模型,能够大幅提高检索效果
    3. PCA降维应用于深度特征能够在几乎不降低检索准确率的同时有效压缩特征长度
    4. 借鉴"fisher vector faces in the wild"中的方法学习投影矩阵,进行向量降维(应用于alexnet倒数第二层fc),效果比PCA降维好非常多。[5]在选择用于学习投影矩阵的训练数据时采用如下方式:对目标数据中构建匹配关系图,所有相似的图像对被通过边连接,图构建完成后,采用以下方式选择训练数据图像对:若图像A和图像B不相连,且他们都与图像C相连,那么A和B构成相似图像对,且A和C或者B和C不能组成图像对。这种操作是为了避免训练图像对中出现两幅图像是near-duplicate的情况。投影矩阵的学习过程可以参见“fisher vector faces in the wild”原文。

    深度神经网络卷积层输出的特征(下称深度卷积特征)被认为是代表特定特征感受野得到的局部图像特征,因此每个深度卷积特征可被看作是某种使用传统特征如sift提取得到的局部特征。2015年的这篇论文[6]调研和评估了应用于图像检索时,各种特征聚合方法作用于深度卷积特征得到图像的全局特征表示。论文表明:不同于传统特征如sift,对于深度卷积特征,通过累加求和生成的聚合特征SPoC(sum-pooled convolutional features)的检索效果优于使用VLAD[2],Fisher Vector[3]和Triangular embedding[4]等方法得到的聚合特征的检索效果。注意,论文中作者在导论部分也提到,之前有学术工作表明基于深度卷积特征+Fisher Vector的Embedding方式生成的特征在分类任务上是非常有效的。

    对于输入图像I,SPoC的生成方法如下:

    1. 对输入I进行推理得到最后一个卷积层的输出特征f,对f(维度C x W x H)进行空间维度上的求和,得到维度为C的特征向量image
    2. 大多数图像包含的核心信息在图像的中间部分,因此对上面得到的特征向量image引入位置系数image,即image, 可以通过高斯函数计算加权值。
    3. image进行PCA降维去相关性和白化操作image。其中Mpca是维度为NxC的PCA投影矩阵,投影后image的维度为C。当N==C时,投影仅起去相关性作用;N<C 时,起到降维作用。 diag() 为矩阵奇异值构成的对角矩阵,奇异值是PCA协方差矩阵特征值的平方根,而对角矩阵的逆矩阵的对角元素为原始矩阵对角元素的倒数,因此 ,diag() 操作为PCA白化过程中的标准差归一化操作。
    4. 对 进行L2范式归一化即可得到最终的SPoC聚合特征image 。SPoC特征在进行PCA协方差矩阵和奇异值求解时的计算更加高效,且不会出现以上VLAD等embedding方法导致的数据过拟合现象。SPoC [6]通过实验分析得出一些有意思的结论,以下列出,方便读者在实际落地场景中选择技术方案时参考。
    • 原始sift特征的可辨识性有限,应用于图像检索时,sift特征间的相似性计算结果可信性不大。作为对比,深度卷积特征作为局部特征,相似性计算结果更加可信。(我们实际应用中也发现,传统局部特征存在明显噪声,基于原始特征进行最邻近匹配准确率会低于VLAD embedding后的特征的匹配效果。)
    • 对深度卷积特征进行sum pooling比max pooling有效。
    • 深度卷积特征与传统特征的分布特性不同,前者比后者具有更高的可辨识性,因此可以无需使用面向传统特征的聚合方法VLAD、Fisher Vector、Triangular embedding。
    • PCA降维应用于SPoC特征能够提升检索效果。
    • 对深度网络全连接层输出的特征fc应用VLAD Embedding对检索效果有提升,但对模型使用目标数据进行finetune后得到的fc检索效果优于fc+VLAD [5]。(最后,我们在实际应用中也发现,SPoC特征进行相似重排序明显优于fc特征。)
    3.3 二进制特征

    前面提到特征按照存储方式又分为浮点特征和二进制特征。使用浮点特征表征图像信息,进行距离计算时能够更加细粒度地衡量图像间的差异,缺点是距离计算复杂度较高,此外浮点向量在进行存储时占用空间也更大。相比之下,二进制特征的存储更加高效,且向量间差异通常采用hamming距离衡量,计算复杂度较低。二进制特征的缺点是距离衡量粒度较粗,如对于128维度的二级制特征,图像间差异只存在128个数值范围内。

    实际业务应用时,我们将二进制特征用作减小搜索空间的一种方式,采用多级查找方式,首先对查询图像与目标数据库中的图像的二进制特征进行汉明距离计算,选取top N距离对应的图像,然后再进行浮点向量间的距离计算,优化查找准确率。

    将浮点特征Embedding成二进制特征的方法很多,如spectral hashing[7],读者感兴趣可以参考这篇文章[8]的Introduction部分,此处不赘述。对于深度特征,最简单的embedding方法是将输出特征(sigmoid化的)使用0.5 hard thresholding得到[9]。

    基于深度特征采用0.5 thresholding的方式操作简单,检索效果也可满足实际应用需求。

    四、快速查找技术

    对于大规模高维向量数据集的检索任务,查找性能优化是核心问题。高维向量的检索性能优化通常分两种方式:一是查找优化,比如建立倒排索引,这种方式通过优化检索结构进行性能优化,不改变向量本身;另一种是向量优化,通过将高维浮点向量映射为低维向量,或者映射到汉明空间,以此减少距离计算复杂度;实际应用时,常常结合这两种方式进行检索优化。

    4.1查找优化

    检索任务的最终目标是返回与查询值最相似的结果,通常分为最近邻查找(NN)和近似最邻近(ANN)查找。最近邻查找总能返回与查询值最相近的结果,如穷尽查找法,通过对全部目标向量数据进行遍历和计算得到最接近距离值,复杂度很高。一种优化的NN算法是通过构建K-D树进行查找,但在高维空间K-D树查找效率低效,复杂度近似等于蛮力搜索O(nD)。

    ANN通过减小搜索空间的方式,提高查找效率。相比最邻近查找,ANN能够大幅度提高检索效率,找到近似最近距离的匹配目标。使用ANN检索到的匹配目标有效的原因在于:在实际应用中,如果距离测量准确地捕捉到查询所关注的核心内容,那么距离的细微差别就不重要了。比如我们在进行相似图片查找,真实情况下的最相似结果,和近似相似结果在视觉效果上差距往往很小。事实上,如果ANN的返回结果的质量严重差于真实最近邻查找返回的匹配结果,那么本身这个最近邻查找问题就是不稳定的,解决这样的一个问题也就没有什么意义了[10]。

    LSH[10]是常用的一种近似临近查找方式,通过将原始数据摄影到某种空间后查询大概率最邻近结果,解决高维空间内的海量数据搜索问题。这篇博客[12]给出了LSH的通俗解释:“将原始数据空间中的两个相邻数据点通过相同的映射或投影变换后,这两个数据点在新的数据空间中仍然相邻的概率很大,而不相邻的数据点被映射到同一个桶的概率很小。对原始数据集合中的所有数据都进行hash映射后,我们就得到了一个hash table,这些原始数据集被分散到了hash table的桶内,每个桶会落入一些原始数据,属于同一个桶内的数据就有很大可能是相邻的,当然也存在不相邻的数据被hash到了同一个桶内。因此,如果我们能够找到这样一些hash functions,使得经过它们的哈希映射变换后,原始空间中相邻的数据落入相同的桶内的话,那么我们在该数据集合中进行近邻查找就变得容易了,我们只需要将查询数据进行哈希映射得到其桶号,然后取出该桶号对应桶内的所有数据,再进行线性匹配即可查找到与查询数据相邻的数据。换句话说,我们通过hash function映射变换操作,将原始数据集合分成了多个子集合,而每个子集合中的数据间是相邻的且该子集合中的元素个数较小,因此将一个在超大集合内查找相邻元素的问题转化为了在一个很小的集合内查找相邻元素的问题,显然计算量下降了很多。”

    构建一个hash table可能需要一个或多个hash function。hash function需要满足两个条件:

    1. 如果d(x,y) <= d1, 则h(x)=h(y)的概率至少为p1;
    2. 如果d(x,y) >= d2, 则h(x)=h(y)的概率至多为p2;

    其中d(x,y)表示x和y之间的距离,d1<d2, h(x)和h(y)分别表示对x和y进行hash变换。

    LSH算法框架包括离线建立索引和在线查找两个过程。其中索引建立过程,确定hash table的个数以及每个hash table包含的hash function个数,和具体采用哪种hash function。然后,将目标数据库中的所有数据经过hash function映射到hash table的桶内。在线查找包括两个部分,将查询数据映射到相应桶内和计算与相应桶内的数据的距离。

    4.2 查找优化-Hamming Embedding

    Video-google[1]中使用倒排文件索引,实际上也属于ANN的一种。倒排索引结构将查找过程分成两部分,索引查找和距离重排序(Reranking)。索引查找一般用穷尽法,遍历得到与查询向量相近的视觉单词对应的索引,进而得到要进行Reranking的候选特征向量;对查询图像的特征向量与候选列表向量进行距离计算并对结果重排序,返回最近邻结果。倒排文件通过聚类生成量化器,对原始特征进行量化,建立索引。量化操作可以过滤特征本身的噪声,使得相似的特征能够被匹配到,但是也会引入量化噪声。因此建立量化器时(聚类),选取合适的类簇数K非常重要:当K较小时,查找索引的复杂度较低,但是倒排列表包含候选元素较多,进行距离重排序的复杂度较高,同时量化噪声较大;当K较大时,查找索引的复杂度较大,但进行距离重排序的复杂度较低,量化噪声也较小。

    Hamming Embedding[11],HE使用二级量化方式来平衡量化噪声和检索复杂度。它的核心思想是在传统量化基础上将向量embedding到binary空间,使用hamming距离阈值,减小重排序候选列表的长度。HE使用粗量化器q(coarse quantizer)和细量化器b(fine quantizer),二级量化的方式。每个输入特征x对应两个量化结果q(x)和b(x)。粗量化器使用上述基于聚类的量化方式,质心数k较小,粒度较粗。细量化器是使用投影矩阵将浮点向量embed到二进制向量的过程,投影矩阵使用训练数据学习得到,学习过程如下:

    假设d为原始特征维度,db embed后的二进制特征维度,学习集合image, 为学习集包含的向量个数。

    1. 生成维度为dbxd 的正交投影矩阵P。具体生成方式为:随机产生一个高斯矩阵,对高斯矩阵进行QR正交分解,提取正交矩阵Q的前db行向量构成投影矩阵P。
    2. 对学习集image中的每个向量xi使用矩阵P进行投影,Z=P x xi,得到向量(Zi1,zi2,zi3,…,zidb)。
    3. 对于cluster l,计算其中值投影向量Tl。Tl的每个元素Tl,h 为所有被量化到当前cluster l 的向量经过步骤(2)得到的image的中值,即 image

    Embedding阶段,对目标集合image中的每个向量image执行以下操作。注意image

    1. 粗量化器q量化x,得到量化后向量q(x);
    2. 使用投影矩阵P将x投影到向量image;
    3. 细量化器将image映射到二进制向量 ,计算公式如下:
      image

    对于查询特征x和目标特征y,最终的特征匹配方法定义如下:

    ‘’’

    if q(x) == q(y) && h(b(x), b(y))<= h_t:
    f(x,y) = tfidf(q(x))
    else:
    f(x,y) = 0

    ‘’’
    f(x,y)为x和y的匹配值,h()为汉明距离计算,h_t为距离阈值。下图展示了HE的物理含义。图中voronoi多边形代表粗量化器q划分得到的一级空间,候选向量经过voronoi cell进行初步划分;然后对当前cell内再由binary空间进行二次划分,下图以二维binary特征为例,将每个voronoi cell又划分为四个hamming空间。搜索范围限制在同一个voronoi cell中的同一个hamming空间内。

    image

    为了提高几何仿射变换的检索稳定性,HE论文还提出一种weak geometrical consistency的方式,该方式结合到倒排索引的构建过程中,可以高效执行,此处不赘述。

    结合HE二级量化方式的倒排索引结构中,每个entry对应一个特征即entry per descriptor(但仍存储image id)。在进行检索时,计算每个待查询特征x的二进制向量b(x)与被查询特征y的二进制向量(预先计算且存储)的汉明距离,若距离小于阈值h_t则使用上面公式计算相似距离;否则,认为y与x不匹配,跳过y,不计入image score的计算。

    4.3 查找优化-IMI

    倒排多索引(Inverted Multi-Index,IMI)[13]是对倒排索引的一种改进方法。

    传统倒排索引在面对海量大规模数据如上千万甚至几十亿条数据向量时,构建的索引结构每个特征单词对应的倒排列表中包含的元素(entry)数目巨大,增加了后续reranking的计算量,严重影响检索速度。最直观的改进方法是增加索引特征单词的数量,使得每个索引值对应的倒排列表包含的元素数量相对较少,即缩小reranking的搜索空间,以此优化重排序速度性能。但这种性能优化方式会引入额外的时间开销:首先,索引单词数量越大,构建索引结构的时间开销也越大;其次,检索时,查找与query单词匹配的索引单词的时间开销也会增加。

    为解决以上问题,IMI采用乘积量化(product quantization)的思想构建多索引结构来优化重排序搜索空间。传统的倒排索引结构的索引的存在形式是一维数据,而倒排多索引结构的索引用一个多维度的table。使用倒排多索引结果进行检索时,返回的候选倒排列表更短,同时候选元素与查询单词距离更近,召回率更高。以二维索引table为例,多索引结构比传统索引结构检索效果更优的物理意义如下图所示。对于传统倒排索引结构(一维),属于同一个索引单词的向量位于相同的voronoi cell内,查询时,对匹配到查询向量的索引单词所在的voronoi cell内的所有元素都要参与reranking。以左图中绿色所示查询向量为例,返回候选元素中大部分与查询向量间的距离较远。而右图倒排多索引所示二维空间划分结构所示,绿色查询向量匹配的候选元素更加集中,与查询向量间的距离较近。

    image

    注意下文介绍的向量优化方法[15]使用PQ优化特征向量,降低距离计算复杂度,而IMI将PQ应用于索引构建和查找的过程。二者应用PQ的阶段不同,实际应用中可以将二者结合,使用PQ构建多索引结构,检索时快速匹配到候选索引,在reranking时再应用[15]进行快速距离计算。

    倒排多索引table可以是二维或者更高维度,维度越高,reranking 搜索空间粒度越细,存储开销也越大。二维table在存储空间、检索时间以及检索准确性能之间能达到较好的平衡。下面以二维多索引为例,介绍多索引构建和检索过程。

    • 索引构建.

    假设数据集D包含N个M维特征向量。多维倒排索引将特征向量划分成S个子向量,S=2对应二维倒排索引。最简单的划分方式是按照长度平均划分,比如化分为两个M/2维的向量,对应位置的子向量构成新的数据集D1和D2。划分时要保证D1和D2数据是不相关的。分别对D1和D2进行聚类,生成两个码表U和V,每个码表包含K个特征单词(对应K个类簇)。

    • 检索.

    给定查询向量q,返回T个候选向量。检索分三个阶段:

    Stage 1. 给定查询向量q=[q1,q2],对于q1和q2分别查找并返回码表U和V中距离q1和q2最近的L个码字,按距离升序分别记为r(1),r(2),r(3),…, r(L), 和 s(1),s(2),s(3),…, s(L)。U和V通常包含较少码字,一般为几千个,因此可用穷尽法查找。

    Stage 2. 对stage1返回的列表,计算距离r(i)+s(j),0<I,j<=L,按照距离升序返回TOP距离对应的码字组合(u_i v_j),如下图所示。最终返回的T个候选向量为u_i包含的向量和v_j包含的向量的交集。
    image

    上述过程中,作者提出使用multi-sequence算法进行距离计算和比较。算法基于优先级队列,入队列元素为码字索引对(i,j),优先级数值定义为码字索引(i,j)对应的距离的负值,即优先级priority=-(r(i)+s(j))。算法输出为T个候选向量,具体流程如下:

    1. 输出候选向量列表OUTPUT为空,码字索引组合(1,1)入队列;

    2. 若队列不为空,pop索引组合(i,j),该索引组合为优先级最高即距离最近的索引对,将该索引组合对应的候选元素加入到输出列表OUTPUT中;若OUTPUT长度>=T,程序中止;否则执行步骤3);

    3. 若(i+1,j-1)不在队列中,则将(i+1,j)入队列;若(i-1,j+1)不在队列中,则将(i, j+1)入队列;

    4. 执行步骤2)和3);

    下图示意了multi-sequence算法的执行过程。

    image

    Stage 3. 对OUTPUT列表中的T个候选向量reranking。这个过程可以结合其他快速相似距离计算的方式,比如PQ,比如binary embedding等方式。论文 提出使用PQ一文的ADC算法进行快速距离计算。进一步提高了检索速度。

    倒排多索引(multi-index)与传统索引(standard index)存储和时间开销对比:

    1. 对于大小为K的码表,传统索引需要K个倒排列表W_i, 0<i<=K,而多索引要KK个倒排列表W_i,j 0<i,j<=K,因而multi-index额外引入了存储开销,但所有列表包含的元素数量的总和没有增加,与standard index相同,即共N个元素(这里的元素可能是特征向量或压缩后的特征向量或是image id,feature id等metadata)。实际应用时,N个元素存储在连续空间内,因此,W_i,j只需要存储当前列表在连续空间中的起始位置(用一个整数)即可,存储这些起始索引的空间总开销为KK4,平均每个元素的额外开销为 KK4/N (原始论文中写成了K4/N,应该是笔误)。这部分开销相对于元素本身占用的内存空间可以忽略不计。

    2. 传统倒排索引结构中每个倒排列表中包含的元素数量是相对均匀的,如上上上个图所示,落入每个voronoi cell中的数据个数是接近的,而倒排多索引结构中落入每个grid中的元素数量是不平衡的,有些grid中包含元素个数甚至为0,尽管如此,每个grid内的元素更加密集,因此multi-index表现出更好的检索召回效果。

    3. 使用multi-sequence算法计算top最优索引组合时,会带来额外时间开销,这部分的时间对比如下图所示。但这部分开销相比较后续reranking的操作时间,可以忽略。

    image

    4.4 查找优化-深度特征

    IMI索引方法的需要保证特征向量划分后的多个数据集是不相关的,对于传统特征如sift是满足该条件的。对于这种特征,构成特征向量的不同元素用来描述图片不同区域的特征,可通俗理解为一个128维sift特征的前64维特征提取自图像A区域的特征,后64维提取完全不相交的B区域的特征。然而深度特征并不具备上述可分条件,划分后的数据空间具有较强相关性,因而IMI应用于深度特征具有局限性。

    这篇论文[14]给出了面向海量深度特征数据的快速索引方法,提出了一种非正交的IMI索引方法,Non-Orthogonal Inverted Multi-Index. No-IMI索引结构定义如下:

    NO-IMI包括两个码表,S和T,每个码表的包含K个码字,S称为1阶码表,为原始数据聚类生成。T为2阶码表,为原始数据与各对应1阶cluster的质心(S中码字)之间的残差值聚类生成。如下图中是个蓝色点代表1阶质心,红色点代表2阶质心。与IMI类似,NO-IMI将数据空间划分成KK个单元;但与IMI不同的是,NO-IMI不对向量空间划分,即S和T中码字长度等于特征向量长度D。KK单元的码字为S和T码字的和,即c_i,j = S_i + T_j。每个单元C_i,j包含了距离该单元码字c_i,j最近的所有特征向量。

    image

    No-IMI的聚类过程与Hierachical K-Means有些类似。区别在于:HKM的每个2级聚类是在对应1级cluster下进行的,即在运行期间需要保存K*K个向量数据。但NO-IMI的2级聚类共享所有cluster的残差,因此只需要保存K+K个向量数据,大大节省了运行时内存占用。

    NO-IMI共享所有1级cluster的向量残差需要保证每个cluster的向量残差数据分布是相同的,为了满足这个条件,NO-IMI引入一个KxK大小的权值矩阵alpha-matrix,该矩阵每个元素作用于对应的cluster,如alpha_i,j为第j个二级cluster对应于第i个一级cluster时的权值因子。即c_i,j = S_i + alpha(i,j)T_j。

    NO-IMI索引构建过程包括两部分:码表学习和索引构建。码表学习阶段生成S、T码表和alpha矩阵。论文中将学习目标定义为最小化所有训练数据与其最近的cell的质心的距离的和,如下式所示。为达到这个优化目标,NO-IMI采用block-coordinate descent方法迭代求解S、T和alpha的最优值。在迭代之前,S码表被初始化为原始数据聚类生成的码表;T码表被初始化为对残差数据聚类生成的码表。

    image

    索引构建时,对数据集中的每个特征向量p计算其与c_i,j的距离,得到距离最近的cell的索引

    image

    若采用穷尽法,对每个向量p要组合所有的S和T的码字取值,因此需要计算KK次才能得出最佳索引。仔细观察,上式距离计算公式可进一步分解为4个部分:
    image
    其中,<>为向量内积操作。上式中,第1项和3项的 <p,T_l> 的时间复杂度为O(D
    K);第2项和第4项可以事先计算好存储在loopup表格中,因此这两部分的时间复杂度为O(1)。其中,在选择1级cluster时,可以从K中选取最近的r个cluster进行计算,r<<K,因此第3项alpha*<p,T_l>的时间复杂度为O(r*K),因此最终距离计算的复杂度为O(DK+rK)。

    NO-IMI检索过程. 对于输入查询向量q,检索过程分为返回top L个cell对应的候选向量列表,和对于候选向量reranking两部分。此处只介绍返回top L个cell的过程。reranking操作不是这篇论文大的核心。可参考其他技术方案。

    1. 计算q与一阶码表S中各码字距离,返回top r最小距离和对应码字索引;时间复杂度为O(KD+KLogK)

    2. 计算q与二级码表T中各码字距离,计算(6)中的最终距离;这个步骤返回一个rK大小的数组,包含公式(6)计算得到的q与r个1级K个2级码字的距离;时间复杂度为O(rK)

    3. 对2中的rK个距离排序,返回top L距离的cell的候选向量列表。

    向量优化

    上文介绍的查找优化方法通过减小搜索空间,提高检索效率。另外一种优化检索性能的方式是进行向量的重映射,将高维浮点向量映射到其他空间,映射后的向量可以采用更高效的方式进行距离计算。前面提到的二进制特征embedding的方式,也属于向量优化。

    这里我们详细介绍一种基于乘积量化(Product Quantization)的向量优化方式[15]。PQ在这里用来解决的重排序时的向量间距离的快速计算的问题。它的核心思想是分割向量,对分割后的向量空间建立独立码表;通过将高维向量分割成多个低维向量,达到节省存储空间的目的;通过subvector-to-centroid的查表方式,达到降低计算复杂度的目的。

    在进行介绍之前,先约定以下定义。质心-聚类得到的质心向量;码字-质心向量的索引;码表-各质心和码字对应关系的集合。

    问题提出. 如果我们对所有相似的向量用一个向量(质心)来表示,那么我们可以把各质心间的距离预先计算出来,在实时查询时,只需要找到查询向量和被查询向量各自的质心索引,就可以得到二者的距离,也就可以避免去实时计算距离,对于高维浮点向量,这样能够大大减少重排序时间。这样有效的前提是,质心与其对应类簇的向量都足够接近。假设我们用聚类的方式来得到质心,那么类簇数越多。质心越具有代表性。极限情况下,类簇数等于数据库中向量数目,相当于查询向量与每个向量进行距离计算,量化误差为0。

    假设目标数据库中每个向量用对应质心的索引来表示,质心个数为 k ,编码这些质心索引的码字长度为 l , l=log_2k 。上面提到质心数越多,量化误差越小;假设要学习的质心数 k=2^{64},那么学习到这些质心所需的样本向量数要远远高于 k ,这样带来两个问题:1.使用如此大量级的样本向量学习质心的计算复杂度非常高;2.存储空间占用大,假设每个向量是128维浮点向量,平均每个质心对应的类簇包含的样本向量数为N,那么要存储这些学习样本需要。
    image

    为解决以上问题,PQ借鉴笛卡尔乘积思想对向量进行量化。具体量化方式如下:

    假设输入向量 X=(x_1,x_2,…,x_D),将 X 分割成m个子向量,每个子向量长度为 D^*=D/m 。对每个子向量 X_j,1\leq j\leq m,使用量化器 q_j进行独立量化(即聚类),量化后码字索引(即质心索引)集合为 I_j ,对应子码表 C_j (即质心向量的集合)。NOTE: SUCH product-based approximation works better if the D/m-dimensional components of vectors have independent distributions.

    输入向量 X 的码表 C 定义为各个子码表 C_j 的笛卡尔乘积:
    image
    笛卡尔乘积的定义参见下图:
    image

    假设每个子码表 C_j 包含的质心数相等,均为 k^* 。 那么可以得到,码表 C 包含的质心数 k=k^\times k^… \times k*=(k)^m 。因此,要得到 k 个质心,只需进行m次“对 D^ 维度的向量进行聚类得到 k^* 个质心”,大大降低了计算和存储复杂度。基于笛卡尔乘积,PQ方法的本质在于使用小规模的质心集合中的元素排列组合生成大规模的质心集合。
    image

    以128为向量为例,要学到 k=2^{64} 个质心,当m=8时,只需要对每个维度为 D^*=128/8=16 的子向量学到 k*=28=128 个质心,存储这些学习样本只需要 N * 8 * 16 * 4 * 2 ^8 bytes,远远小于上面原始存储空间需求 N * 128 * 4 * 2^{64} bytes。

    PQ方法相比hamming embedding方法的一个优势在于,PQ的量化空间非常大(质心数),可表示的向量之间的差异远远超过汉明空间能表示的向量差异。如质心数为264时,使用PQ方法,128维度向量的量化取值有264种。

    距离计算. PQ提出两种距离计算方式: SDC(symmetric distance computation)和ADC(asymmetric distance computation)。假设x为查询向量,y为要与之进行距离计算的目标数据库向量。q(x)和q(y)分别为二者的量化结果,即各自对应的质心向量的索引。

    SDC为对称距离计算,即查询向量和数据库向量均质心向量进行距离计算,即d(x,y) ~= d(q(x),q(y))。

    ADC为非对称距离计算,计算查询向量和数据库向量对应质心向量间的距离,即d(x,y) ~= d(x, q(y))

    为提升检索效率,各子向量空间下质心向量间的距离是被预先计算和存储的。

    SDC和ADC的距离计算流程如下:

    image
    image
    可以看出,无论是SDC还是ADC,在进行距离计算时,核心操作只包含查表和加法,大大降低了检索复杂度。SDC和ADC的计算复杂度类似,ADC比SDC多了部分运行时内存需求,即需要实时保存x子向量与各质心间的距离,共mk*个元素的存储空间,实际应用时这部分内存空间可以忽略不计。但是,ADC方法由于使用未量化的查询向量进行距离计算,量化误差相比SDC更小,因此作者建议实际应用时,采用ADC方法。

    检索. PQ采用向量优化的方式,检索时在近似最邻近空间内仍采用穷尽法进行遍历,因此PQ论文提出使用ADC方法结合倒排索引的方法IVFADC(inverted file system with the asymmetric distance computation),进一步缩小检索空间,提升检索性能。IVFADC的检索架构如下图所示。
    image
    IVFADC包含两级量化操作。第一级量化是一个粗粒度量化过程,采用类似于video-google文中的方法,对数据库中的向量进行粗粒度K-means聚类,生成码表和量化器 q_c ,该码表的码字构成了倒排索引结构中的每个节点。第二级量化是对残差向量使用乘积量化器PQ量化,生成码表和量化器 q_p 。

    IVFADC的索引构建过程,即为对数据库中每个向量y执行如下流程的过程。

    image
    检索流程描述如下:
    image
    IVFADC检索复杂度分析:使用倒排索引结构,ADC额外增加的计算时间为粗粒度量化x的时间,假设粗粒度码表包含 k’ 个cluster,那么 q_c(x) 的操作复杂度为 k’D ;而在检索时,若采用穷尽搜索,需要遍历数据库内所有n个元素,而引入倒排索引,仅需要遍历w(n/k’)个元素(此处假设每个倒排列表包含元素数量均衡) 。

    五、工业界案例

    以上对视觉检索流程中涉及的经典算法技术进行了介绍。近两年工业界也陆续开公开了各自视觉检索技术的技术案例,本部分以电商平台ebay[16]和社交凭条Pinterest[17]为例简单介绍。

    ebay基于深度哈希特征的相似图像检索方法,包括特征提取和检索策略以及检索基础架构的技术方案。特征部分,ebay采用基于深度神经网络全连接层输出的sigmoid特征的0.5 threshold映射后的二进制特征。索引部分,ebay采用多级检索方式。对所有商品定义叶子类别,即非常细粒度的类别,细化到如‘运动鞋’、'高跟鞋’等。在深度神经网络进行特征学习的过程,同时进行叶子类别分类的学习,二者共享部分网络特征。如下图所示:
    image

    检索时,1.查询图像仅在相同或相近的叶子类别中进行检索,大幅度减少了目标检索数据量;2,.然后对新的目标检索空间S下的数据进行hamming距离计算,采用穷尽法遍历,返回距离的最相近的Top list L;3.最后,对L中的数据结合商品属性标签进行重排序,返回最终的top相似结果。商品属性包括不同的品牌、颜色等, 通过XGBoost训练得到商品属性预测模型。模型训练的输入是深度特征向量,文中提到使用了ResNet-50的pool5层输出向量。工程架构方面细节可参见论文。此不赘述。

    Pinterest[17]这篇技术论文的公开时间早于ebay,整体内容与ebay类似,从特征到检索架构介绍视觉相似检索。此外,这篇文章提到了实际场景中常遇到的大规模图像数据检索服务的特征更新问题。特征更新主要是解决不影响现有服务运行的前提下高效生成增量特征的问题。增量特征包括两部分:新增图像对应的特征和算法模型更新带来的历史图像数据的特征更新。Pinterest文中按照特征类型、版本和时间分开存储。特征类型如全局特征、局部特征、深度特征、传统特征、浮点特征、二进制特征等;版本对应算法模型更新;每个特征类型的每个版本对应一个feature store,每个feature store包含多个epoch,每个epoch对应新增图像数据的特征提取。在这种存储方案下,对于每天新增图像数据,找到各特征类型的各版本,增加对应时间的feature epoch;对于新的特征或算法模型的更新,生成一个新的feature epoch,遍历所有历史图像数据,生成对应epoch。

    此外,Facebook也在去年开源了其多媒体数据向量聚类和检索库Faiss[18]。Faiss主要解决聚类和检索问题,当前版本的Faiss实现了各种聚类算法和经典的索引构建以及快速查找算法,包括上文介绍的IVF、IMI、PQ、LSH等。Faiss不提供特征提取接口,即开发人员需要针对自己业务场景下的多媒体信息提取特征向量。注意,各种索引构建和查找算法,是依赖于向量分布特性的。比如应用PQ算法时,需要保证划分后的向量空间是独立的,若划分后的向量强相关,那么查找效果可能会较差。也就是特征提取算法和检索算法是相互依赖的。深度特征的分布与传统特征是不同的[6],对于视觉内容的检索问题,当前版本的Faiss提供的方法更适合传统方法提取的特征向量。

    参考文献

    [1]. Video google: a text retrieval approach to object matching in videos, 2003.
    [2]. Aggregating local descriptors in to a compact image representation, 2010
    [3]. Large scale image retrieval with compressed Fisher Vectors, 2010
    [4]. Triangular embedding, 2014
    [5]. Nueral codes for image retrieval, 2014
    [6]. Aggregating deep convolutional features for image retrieval, 2015
    [7]. Spectral hashing, 2018
    [8]. Deep hashing with category mast for fast video retrieval, http://cn.arxiv.org/abs/1712.08315
    [9]. Deep learning of binary hash codes for fast image retrieval, 2015.
    [10]. p-stable LSH: locality-sensitive hashing scheme based on p-stable distributions, 2004.
    [11]. Hamming embedding and weak geometric consistency for large scale image search, 2008.
    [12]. https://blog.csdn.net/icvpr/article/details/12342159
    [13]. The inverted multi-index, 2012.
    [14]. Efficient indexing of billion-scale datasets of deep descriptors, 2016.
    [15]. Product quantization for nearest neighbor search, 2011.
    [16]. Visual search at ebay, 2017.
    [17]. Visual search at Pinterest, 2017.
    [18]. https://github.com/facebookresearch/faiss

    展开全文
    weixin_40100431 2019-01-30 20:42:56
  • 基于内容的图像检索(CBIR, Content Based Image Retrieval)是相对成熟的技术领域,在工业界也有广泛的应用场景,如搜索引擎(Google、百度)的以图搜图功能,各电商网站(淘宝、Amazon、ebay)的相似商品搜索,...

    基于内容的图像检索(CBIR, Content Based Image Retrieval)是相对成熟的技术领域,在工业界也有广泛的应用场景,如搜索引擎(Google、百度)的以图搜图功能,各电商网站(淘宝、Amazon、ebay)的相似商品搜索,社交平台(Pinterest)的相似内容推荐等。本文从图像检索流程出发,结合我们团队在社交应用中的相似图片、视频检索中的实践经验,介绍构建基于内容的图像检索系统所涉及的算法技术,包括特征提取、索引构建、近邻搜索等技术,供相关领域研发人员参考。

    在介绍视觉内容检索流程前,先来回顾下文本检索流程。

    一、相似文本检索

    相似文本检索可以分成构建词库、构建索引和检索三部分,如下图所示。

    #知乎打大括号好难,所以此处用'伪伪代码',凑合看吧
    if q(x) == q(y) && h(b(x), b(y))<= h_t:
      f(x,y) = tfidf(q(x))
    else:
      f(x,y) = 0


    参考文献

    [1]. Video google: a text retrieval approach to object matching in videos, 2003.

    [2]. Aggregating local descriptors in to a compact image representation, 2010

    [3]. Large scale image retrieval with compressed Fisher Vectors, 2010

    [4]. Triangular embedding, 2014

    [5]. Nueral codes for image retrieval, 2014

    [6]. Aggregating deep convolutional features for image retrieval, 2015

    [7]. Spectral hashing, 2018

    [8]. Deep hashing with category mast for fast video retrieval, http://cn.arxiv.org/abs/1712.08315

    [9]. Deep learning of binary hash codes for fast image retrieval, 2015.

    [10]. p-stable LSH: locality-sensitive hashing scheme based on p-stable distributions, 2004.

    [11]. Hamming embedding and weak geometric consistency for large scale image search, 2008.

    [12]. https://blog.csdn.net/icvpr/article/details/12342159

    [13]. The inverted multi-index, 2012.

    [14]. Efficient indexing of billion-scale datasets of deep descriptors, 2016.

    [15]. Product quantization for nearest neighbor search, 2011.

    [16]. Visual search at ebay, 2017.

    [17]. Visual search at Pinterest, 2017.

    [18]. https://github.com/facebookresearch/faiss

    展开全文
    u013066730 2020-06-15 19:11:42
  • 952KB weixin_38546622 2021-02-10 08:19:46
  • 表现SOTA!在准确性和效率上都显著提高,可对大规模数据集进行实时搜索,性能优于CVSE、PFAN等网络。 注1:文末附【Transformer】流群 注2:整理不易,欢迎点赞,支持分享! VisualSparta: Sparse ...文本图像检索

    表现SOTA!在准确性和效率上都显著提高,可对大规模数据集进行实时搜索,性能优于CVSE、PFAN等网络。

    注1:文末附【Transformer】流群

    注2:整理不易,欢迎点赞,支持分享!

    VisualSparta: Sparse Transformer Fragment-level Matching for Large-scale Text-to-Image Search

    • 作者单位:CMU, SOCO(美国公司)
    • 论文:https://arxiv.org/abs/2101.00265

    文本到图像的检索是多模态信息检索中的一项基本任务,即在给定文本查询的情况下从大型且未标记的图像数据集中检索相关图像。在本文中,我们提出了VisualSparta,这是一种新颖的文本到图像检索模型,该模型在准确性和效率上都比现有模型显著提高。
    在这里插入图片描述

    部分细节如下:
    在这里插入图片描述
    在这里插入图片描述

    我们证明VisualSparta能够胜过MSCOCO和Flickr30K中所有以前的方法。它还显示了实质性的检索速度优势,即对于具有100万张图像的索引,与标准矢量搜索相比,VisualSparta的速度提高了391倍。

    主要贡献:
    在这里插入图片描述

    实验结果

    实验表明,对于较大的数据集,这种速度优势甚至更大,因为VisualSparta可以有效地实现为反向索引。据我们所知,VisualSparta是第一个基于Transformer的文本到图像检索模型,可以实现对非常大的数据集的实时搜索,与以前的最新方法相比,其准确性显著提高。
    在这里插入图片描述
    在这里插入图片描述

    CVer-Transformer交流群

    建了CVer-Transformer交流群!想要进Transformer学习交流群的同学,可以直接加微信号:CVer9999。加的时候备注一下:Transformer+学校+昵称,即可。然后就可以拉你进群了。

    强烈推荐大家关注CVer知乎账号和CVer微信公众号,可以快速了解到最新优质的CV论文。

    在这里插入图片描述

    展开全文
    amusi1994 2021-02-17 16:02:27
  • 1.81MB weixin_38743602 2019-09-11 03:15:14
  • 1.68MB weixin_42109639 2021-05-29 01:18:50
  • weixin_40100431 2019-01-31 10:20:44
  • qq_34213260 2020-05-25 15:51:29
  • flyingliufan 2015-09-11 15:26:51
  • mago2015 2018-07-29 13:17:00
  • qq_40369926 2019-05-12 12:57:50
  • qq_43653930 2020-05-24 11:48:06
  • m0_59833680 2021-08-25 11:59:21
  • weixin_44074528 2019-05-09 23:49:39
  • weixin_42578378 2019-05-12 16:56:16
  • github_28260175 2019-06-27 16:36:21
  • 493KB weixin_38732519 2021-05-19 21:21:08
  • weixin_42653918 2019-05-11 20:29:11
  • qq_35912099 2021-07-11 14:26:42
  • 76KB m0_52957036 2020-11-22 12:27:31
  • 768KB weixin_38672807 2021-03-16 20:49:08

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,742
精华内容 11,496
关键字:

基于文本的图像检索

友情链接: 雷达实验.zip