导读:本文包含了近似近邻搜索论文开题报告文献综述及选题提纲参考文献，主要关键词:图像检索,近似最近邻搜索,线性保距哈希,深度有监督量化
近似近邻搜索论文文献综述
王敏[1]（2019）在《基于二值哈希和量化的近似最近邻搜索研究》一文中研究指出近似最近邻搜索是多媒体与计算机视觉领域的基础研究方向,在大规模图像检索、行人再识别等实际问题中获得广泛研究和应用。给定一个查询样本,近似最近邻搜索方法的目标是以次线性甚至常数时间复杂度从大规模数据集中返回查询样本的最近邻。目前主流的近似最近邻搜索技术可以分为叁类,分别是基于树的方法,基于二值哈希的方法和基于量化的方法。由于基于二值哈希的方法和基于量化的方法具有特征距离计算快和内存占用低的优势,近年来获得了更多的研究关注。其中,二值哈希方法将原始高维数据特征投影为低维二值码,而量化方法将原始高维特征投影为码本中最近的码本单词的整数索引。本文基于对二值哈希方法和量化方法的研究,提出了叁种近似最近邻检索框架,应用于图像检索任务。(1)基于线性距离约束的哈希通用框架。二值哈希方法通常需要学习一系列的哈希函数来产生规定长度的二值码。本文提出一种基于线性距离约束的哈希通用框架,同时结合了成对保距约束和单点性约束学习哈希函数。本文设计了一种新颖的成对线性保距目标,保证原始的欧氏距离与汉明距离之间具有线性变换关系,充分体现了二值哈希方法的保距原则。基于不同的单点性约束,本文提出了五种方法去实例化该哈希通用框架。(2)深度有监督量化框架。基于量化的方法目前大多采用无监督的方式进行学习,忽略了数据集中样本包含的语义信息,而且通常将特征学习和码本学习分为两个步骤进行,不能保证码本与特征相匹配,影响了近似最近邻检索的准确度。本文提出了一种深度有监督量化框架以解决该问题。该框架将卷积神经网络和量化网络融合到一个统一的深度架构中,同时学习图像的深度特征和码本。基于不同的码本学习方法,本文提出了叁种深度有监督量化方法去实例化该深度有监督量化框架。(3)基于生成对抗网络的深度无监督量化框架。目前深度哈希方法较少在无监督情境下应用,其主要原因是类别或标签等语义信息的缺失给深度网络的训练带来难度。然而,在很多实际应用中获取标签或类别等信息的代价是昂贵的甚至是不可能实现的。本文提出了一种新颖的深度无监督量化方法,可以同时学习特征表达和量化器。基于生成对抗网络,量化器中每个聚类中心学习生成一张真实感的图像。优化目标是通过同时在图像空间和特征空间进行聚类中心的优化,使得获得的聚类中心能够自动抓取图像分布,获得区分性信息。综上,本文主要研究图像检索中的二值哈希方法和量化方法,并提出了叁种近似最近邻检索框架。在公共数据集上的测试结果表明,所提出框架的实例化方法相对于现有近似最近邻搜索方法获得了较大的检索性能提升。(本文来源于《中国科学技术大学》期刊2019-06-05）
王昌旭[2]（2018）在《基于导向性分散伸展图的高效近似最近邻搜索》一文中研究指出近似最近邻搜索问题是数据库、数据挖掘、人工智能等领域中的一个基本问题。一个具有实际应用价值的近似最近邻搜索算法必须同时具有极高的搜索速度以及合理的内存用量。相比于传统的基于树结构、基于哈希和基于量化的搜索算法,基于图索引的近似最近邻搜索算法因其搜索高且速度快的特点,吸引了来自学术界和工业界的大量关注。虽然许多早期的基于图结构的近似最近邻搜索算法算法在理论上具有十分低的搜索时间复杂度,但这些图结构索引的索引构建算法往往具有极高的时间复杂度,从而使其在目前的大数据时代场景中无法有效应用。因此近年来学界提出了诸多新的图结构索引,以期能够降低索引构建的时间复杂度。虽然这些方法取得了许多革命性的进步,但其仍旧不够高效从而限制了其在更大规模数据集上的应用。本文结合近年来的最新研究成果,对图结构索引进行了更深入的探究,以希望能够更有效地解决上述困难。具体来讲,本文从以下四个方面出发对用于近似最近邻搜索的图结构进行了探究:(1)保证图的连通性;(2)降低图中节点的平均出度已获得更快的遍历速度;(3)降低查询在图上的搜索路径长度;(4)减小基于图结构的索引的大小。基于以上四点,本文在理论上提出了一种全新的图结构——单调相对近邻图(Monotonic Relative Neighborhood Graph,MRNG),这种图结构在理论上具有极低的搜索复杂度(接近对数时间复杂度)。但直接构造MRNG的算法复杂度过高,使其在超大规模数据上不具有实际可行性。为此本文提出了另一种全新的称为“导向性分散伸展图(Navigating Spreading-out Graph,NSG)”的图结构用以近似MRNG,从而实现了一种同时具有高效索引构建与搜索性能的全新近似最近邻搜索算法。本文在SIFT1M、GIST1M等多个百万级数据集上对NSG算法进行了充分的实验验证,并在这些数据集上与现有主流算法进行横向对比试验,从而证明NSG在索引构建速度与搜索速度精度等具有巨大的优越性。最后本文提出了一种可用于工业场景的基于NSG的超大规模快速近似最近邻搜索系统设计方案,并在亿级数据集上对其可行性进行了初步验证。(本文来源于《浙江大学》期刊2018-12-28）
杨杰[3]（2018）在《图像检索中基于近似k-近邻图的近似最近邻搜索算法研究》一文中研究指出最近邻搜索作为一个基础性问题,广泛出现在数据库、机器学习、计算机视觉和信息检索等领域。最近邻搜索问题可以被简单定义为,给定查询向量和n个同维的候选向量,要求返回某种距离度量方式下距离查询向量最近的一个或多个候选向量。在许多现实应用中,精确算法往往需要高昂的时间和空间代价,而近似最近邻搜索则以牺牲一定的准确率为代价,显着地降低了对存储空间和查询时间的要求。近似最近邻搜索因其实用性,受到了广泛关注,许多算法相继被提出,包括基于空间分割、基于哈希、基于向量量化和基于近邻图四类算法。然而目前还没有通用的亚线性时间复杂度的近似最近邻搜索算法。在大数据时代,设计高质、高效的近似最近邻搜索算法具有重要的理论意义和实用价值。基于(近似)k-近邻图(k-NX图)的近似最近邻搜索算法是当前的主流算法,一般包括两个步骤:一是对候选向量离线构造k-NN图,二是基于k-NN图采用某种搜索策略返回查询结果。k-NN图的质量和搜索策略极大地影响了算法的效果和效率。本文对k-NN图的构造,以及爬山搜索(GNNS)算法做了改进。主要结果有:(1)发现爬山搜索算法存在冗余计算、收敛速度慢,提出一种改进的爬山搜索(E-GNNS)算法:即在每一轮迭代中,不只对第一个样本,而是对前k个样本都在k-NN图上进行扩展。实验表明,E-GNNS算法在搜索效率和平均召回率上获得了显着提升。(2)在爬山搜索种子点的选择上,采用基于RVQ编码的倒排索引来生成候选种子点,替代原方法的随机种子点。实验表明,在这一策略的支持下,E-GNNS算法能够在相似的搜索时间下,获得超10%的平均召回率的提升。(3)为克服k-NN图构造时效率低下、内存消耗严重的缺点,提出一个基于2-M树的轻量级的构造方法。实验表明,该方法能够在不牺牲后期搜索效果和效率的前提下,显着降低k-NN图构造的时间和内存消耗。(本文来源于《厦门大学》期刊2018-05-01）
杨昕欣,姜精萍[4]（2018）在《基于近似最近邻搜索的并行光流计算》一文中研究指出Barnes近似最近邻算法是当前匹配性能优秀的近似块匹配算法,将其应用于稠密光流的计算中,并与OpenCV中实现的两种稠密光流算法进行对比。针对Barnes算法不易并行化的不足,对Barnes算法中的传播过程进行修改,使其易于在GPU上实现并行加速。实验表明,经并行加速后的光流算法比原算法快两倍以上,而在精确度上与原算法接近,并且都优于OpenCV实现的两种稠密光流算法。(本文来源于《计算机工程与应用》期刊2018年18期）
张婷[5]（2017）在《基于量化的近似最近邻搜索技术研究》一文中研究指出最近邻搜索是机器学习、计算机视觉和信息检索里一个重要的基础性问题。然而,在大规模高维数据环境下,给定查询点,找到其精确的最近邻需要大量的计算及存储空间。近似最近邻搜索算法由于其存储空间少、查找效率高等优点引起了人们的广泛关注。而如何快速、高效、准确地进行近似最近邻搜索是目前学术研究的一个热点和难点。一般来说,近似最近邻搜索的算法在尽可能保证其准确性的情况下主要从两个方面提高搜索速度。第一个是利用特殊的数据结构来减少查询点与数据点的比较次数;第二个是利用紧凑码来加速计算查询点与数据点之间的距离,比如通过哈希算法或量化算法将数据点映射为紧凑码。本文主要从第二个方面——基于量化的近似最近邻搜索算法——研究如何获得更优质的紧凑码来提高查找准确率和查找效率。本文主要研究内容和创新成果如下:1.针对无监督的近似最近邻搜索,本文提出一种组合量化方法。其主要思想是用若干个子中心点之和作为重构点来近似数据点,其中每个子中心点来自不同的子字典,数据点用这些子中心点在各自子字典中的索引值来表示。同时,我们引入近似正交约束条件,使得计算查询点与重构点的距离可以用查询点和这几个子中心点的距离之和来代替进而加速距离计算。与已有的量化方法的对比实验结果表明,近似正交的组合量化可以获得更高的查找准确率。2.本文提出一种稀疏组合量化算法,用以减少组合量化中创建查阅表所需的时间。大规模数据的近似最近邻搜索通常结合倒排表进一步加速搜索。而组合量化在对倒排表返回的数据点进行排序的时候,创建查阅表所需的时间变得不可忽视。针对这一问题,本文提出的稀疏组合量化方法,引入了一个稀疏条件,使得重构字典里的每一个子中心点是一个稀疏向量。其好处是,当创建查阅表需要计算查询点与子中心点的欧氏距离的时候,由于子中心点是一个稀疏向量,可以加速距离计算。在大规模数据集上的近似最近邻搜索表明,稀疏组合量化相比较于组合量化,可以获得更快的查找速度。3.本文提出基于量化的近似最近邻搜索算法用于跨模态最近邻搜索领域中。所谓跨模态最近邻搜索,指的是查询点和数据点来自不同的数据模态,例如用图像查询点去搜索相似的文本数据点,或用文本查询点去搜索相似的图像数据点。本文提出的算法只假设一幅图像和一段文本是一一对应的,而不需要已知图像和文本的类别。该算法首先将来自不同模态的一对数据映射到同一空间中,之后在这个映射后的空间对不同模态的数据通过组合量化进行近似,同时使来自不同模态的一对数据的近似表示尽可能相同。大量的实验比较表明,本文提出的算法在跨模近似态最近邻搜索中可以获得更高的查找准确率。4.针对有监督近似最近邻搜索,本文提出了一种新的量化方法。不同于无监督近似最近邻搜索,量化算法直接在数据库上进行量化,本文提出的算法是使数据点首先通过一个线性变换,之后在线性变换后的数据点上进行组合量化。其优化的目的不仅要使得量化后的近似表达能准确地代表线性变换后的数据点,同时也使得数据点在线性变换后具有类别可分离性,即相同类别的数据点在线性变换后距离很近,不同类别的数据点在线性变换后的空间内相距很远。与现有的有监督近似最近邻搜索算法的实验比较表明,本文提出的算法可以获得更高的查找准确率。综上,本文在无监督的近似最近邻搜索,跨模态的近似最近邻搜索,以及有监督的近似最近邻搜索这叁个领域提出了四个新颖的算法,用于提高近似最近邻搜索的查找准确率以及查找效率。大量实验结果表明了本文提出的方法的查找结果好于已有方法的查找结果。(本文来源于《中国科学技术大学》期刊2017-05-01）
杨定中,陈心浩[6]（2015）在《基于投影残差量化哈希的近似最近邻搜索》一文中研究指出针对投影哈希中投影误差较大,二进制编码时原始信息丢失严重等问题,提出一种近似最近邻搜索方法。该方法通过多阶段量化策略减少编码过程中的投影及量化误差。在每阶段训练时,对前一阶段的量化残差采用投影、按维度训练码书及量化、反投影等运算生成各阶段的子量化器。子量化器按投影后数据的维度提供多个哈希函数,最终的哈希函数由各阶段哈希函数共同构成。在最近邻搜索时,给二进制编码加上权重以便对搜索结果进行重排,提高搜索精度。实验结果表明,基于投影残差量化哈希的近似最近邻的搜索性能优于当前主流的哈希方法。(本文来源于《计算机工程》期刊2015年12期）
高毫林,徐旭,李弼程[7]（2013）在《近似最近邻搜索算法——位置敏感哈希》一文中研究指出寻找查询点的最近邻是信息处理相关领域的主要任务之一。在数据规模较大时需要采用快速检索算法,常用的快速检索算法主要是基于树的算法,但是当数据点维数较高时,这些算法的效率会变低。位置敏感哈希是当前解决高维搜索的最快的算法,文章对汉明空间、欧式空间下的位置敏感哈希算法的实现方案进行了详细分析,对算法中数据点冲突概率、空间时间消耗、参数调整对算法性能的影响进行了详尽的研究和试验,最后讨论算法的优点和缺点,说明了算法应用于视觉聚类的可能性。(本文来源于《信息工程大学学报》期刊2013年03期）
赵璐璐,耿国华,李康,何阿静[8]（2013）在《基于SURF和快速近似最近邻搜索的图像匹配算法》一文中研究指出针对高维特征向量存在的最近邻匹配正确率低的问题,提出了一种基于SURF和快速近似最近邻搜索的图像匹配算法。首先用Fast-Hessian检测子进行特征点检测,并生成SURF特征描述向量;然后通过快速近似最近邻搜索算法得到初匹配点对,再对得出的单向匹配结果进行双向匹配;最后采用鲁棒性较好的PROSAC算法进一步剔除误匹配点对。实验证明了该算法不仅提高了SURF算法匹配的正确率,还保证了算法的实时性。(本文来源于《计算机应用研究》期刊2013年03期）
近似近邻搜索论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
近似最近邻搜索问题是数据库、数据挖掘、人工智能等领域中的一个基本问题。一个具有实际应用价值的近似最近邻搜索算法必须同时具有极高的搜索速度以及合理的内存用量。相比于传统的基于树结构、基于哈希和基于量化的搜索算法,基于图索引的近似最近邻搜索算法因其搜索高且速度快的特点,吸引了来自学术界和工业界的大量关注。虽然许多早期的基于图结构的近似最近邻搜索算法算法在理论上具有十分低的搜索时间复杂度,但这些图结构索引的索引构建算法往往具有极高的时间复杂度,从而使其在目前的大数据时代场景中无法有效应用。因此近年来学界提出了诸多新的图结构索引,以期能够降低索引构建的时间复杂度。虽然这些方法取得了许多革命性的进步,但其仍旧不够高效从而限制了其在更大规模数据集上的应用。本文结合近年来的最新研究成果,对图结构索引进行了更深入的探究,以希望能够更有效地解决上述困难。具体来讲,本文从以下四个方面出发对用于近似最近邻搜索的图结构进行了探究:(1)保证图的连通性;(2)降低图中节点的平均出度已获得更快的遍历速度;(3)降低查询在图上的搜索路径长度;(4)减小基于图结构的索引的大小。基于以上四点,本文在理论上提出了一种全新的图结构——单调相对近邻图(Monotonic Relative Neighborhood Graph,MRNG),这种图结构在理论上具有极低的搜索复杂度(接近对数时间复杂度)。但直接构造MRNG的算法复杂度过高,使其在超大规模数据上不具有实际可行性。为此本文提出了另一种全新的称为“导向性分散伸展图(Navigating Spreading-out Graph,NSG)”的图结构用以近似MRNG,从而实现了一种同时具有高效索引构建与搜索性能的全新近似最近邻搜索算法。本文在SIFT1M、GIST1M等多个百万级数据集上对NSG算法进行了充分的实验验证,并在这些数据集上与现有主流算法进行横向对比试验,从而证明NSG在索引构建速度与搜索速度精度等具有巨大的优越性。最后本文提出了一种可用于工业场景的基于NSG的超大规模快速近似最近邻搜索系统设计方案,并在亿级数据集上对其可行性进行了初步验证。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
近似近邻搜索论文参考文献
[1].王敏.基于二值哈希和量化的近似最近邻搜索研究[D].中国科学技术大学.2019
[2].王昌旭.基于导向性分散伸展图的高效近似最近邻搜索[D].浙江大学.2018
[3].杨杰.图像检索中基于近似k-近邻图的近似最近邻搜索算法研究[D].厦门大学.2018
[4].杨昕欣,姜精萍.基于近似最近邻搜索的并行光流计算[J].计算机工程与应用.2018
[5].张婷.基于量化的近似最近邻搜索技术研究[D].中国科学技术大学.2017
[6].杨定中,陈心浩.基于投影残差量化哈希的近似最近邻搜索[J].计算机工程.2015
[7].高毫林,徐旭,李弼程.近似最近邻搜索算法——位置敏感哈希[J].信息工程大学学报.2013
[8].赵璐璐,耿国华,李康,何阿静.基于SURF和快速近似最近邻搜索的图像匹配算法[J].计算机应用研究.2013