基于二值哈希和量化的近似最近邻搜索研究

发布时间：2020-08-16 19:10

【摘要】：近似最近邻搜索是多媒体与计算机视觉领域的基础研究方向,在大规模图像检索、行人再识别等实际问题中获得广泛研究和应用。给定一个查询样本,近似最近邻搜索方法的目标是以次线性甚至常数时间复杂度从大规模数据集中返回查询样本的最近邻。目前主流的近似最近邻搜索技术可以分为三类,分别是基于树的方法,基于二值哈希的方法和基于量化的方法。由于基于二值哈希的方法和基于量化的方法具有特征距离计算快和内存占用低的优势,近年来获得了更多的研究关注。其中,二值哈希方法将原始高维数据特征投影为低维二值码,而量化方法将原始高维特征投影为码本中最近的码本单词的整数索引。本文基于对二值哈希方法和量化方法的研究,提出了三种近似最近邻检索框架,应用于图像检索任务。(1)基于线性距离约束的哈希通用框架。二值哈希方法通常需要学习一系列的哈希函数来产生规定长度的二值码。本文提出一种基于线性距离约束的哈希通用框架,同时结合了成对保距约束和单点性约束学习哈希函数。本文设计了一种新颖的成对线性保距目标,保证原始的欧氏距离与汉明距离之间具有线性变换关系,充分体现了二值哈希方法的保距原则。基于不同的单点性约束,本文提出了五种方法去实例化该哈希通用框架。(2)深度有监督量化框架。基于量化的方法目前大多采用无监督的方式进行学习,忽略了数据集中样本包含的语义信息,而且通常将特征学习和码本学习分为两个步骤进行,不能保证码本与特征相匹配,影响了近似最近邻检索的准确度。本文提出了一种深度有监督量化框架以解决该问题。该框架将卷积神经网络和量化网络融合到一个统一的深度架构中,同时学习图像的深度特征和码本。基于不同的码本学习方法,本文提出了三种深度有监督量化方法去实例化该深度有监督量化框架。(3)基于生成对抗网络的深度无监督量化框架。目前深度哈希方法较少在无监督情境下应用,其主要原因是类别或标签等语义信息的缺失给深度网络的训练带来难度。然而,在很多实际应用中获取标签或类别等信息的代价是昂贵的甚至是不可能实现的。本文提出了一种新颖的深度无监督量化方法,可以同时学习特征表达和量化器。基于生成对抗网络,量化器中每个聚类中心学习生成一张真实感的图像。优化目标是通过同时在图像空间和特征空间进行聚类中心的优化,使得获得的聚类中心能够自动抓取图像分布,获得区分性信息。综上,本文主要研究图像检索中的二值哈希方法和量化方法,并提出了三种近似最近邻检索框架。在公共数据集上的测试结果表明,所提出框架的实例化方法相对于现有近似最近邻搜索方法获得了较大的检索性能提升。
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2019
【分类号】：TP391.41
【图文】：

哈希,二值,检索方法,最近邻

１．２．２基于二值哈希的方法逡逑基于哈希的方法中最为流行的是二值哈希方法。二值哈希方法的通用流程逡逑如图１．２所示。二值哈希方法需要通过哈希函数将原始高维特征映射为低维汉明逡逑空间中的二值码，原始高维特征之间的欧氏距离被二值码之间的汉明距离近似逡逑代替。由于二值哈希方法在数据库中仅仅需要存储二进制码，因此存储空间占用逡逑比较低；另一方面，二值码之间的汉明距离可以被现有ＣＰＵ架构中的指令高效逡逑地计算，因此汉明距离计算比较快。由于这两方面的优势，二值哈希方法受到越逡逑来越多的关注和研宄。逡逑＼逡逑Ｗ＼逡逑ｔ逦１００逦１0？逡逑Ｏ逦ｏｏｏｔｆ＾ｌ邋００，１１＾逡逑？邋—逦逡逑ｏｉｏ邋ｏｎ逡逑空间存储：高维浮点型向量逦空间栜：低维二值码逡逑ｓｉ离计算：欧氏距离逦距离计算：汉明距离逡逑图像ｓ间逡逑图１．２二值哈希方法流程。逡逑一般来说，二值哈希方法通常需要学习一系列的哈希函数来产生规定比特数逡逑目的二值码。图１．３展示了基于二值

检索方法,最近邻,码本

一旦获得了查询样本的量化结果（即码本单词索引），查询样本与数据逡逑库中每个样本之间的距离计算可以通过查表完成。综上所述，量化方法作为一种逡逑特殊的哈希方法，同样具有距离计算快、存储空间占用低的优势。图１．４介绍基逡逑于量化的近似最近邻检索的基本流程。逡逑数据＇＂库逦／逦数ｉｇ库逡逑线下逦——逡逑ｗ±逦码本—｝逦逡逑°邋＾邋ｓｏ１３逡逑Ｂ３逡逑查询样本邋＾＾邋ｐ逦ｌ＊Ｊ￣囡逐］■—逡逑＇邋Ｖ邋’逦［疆］逦＿逡逑图１．４基于量化的近似最近邻检索方法。逡逑由于码本单词通常是与原始高维特征处于同一空间，均为高维浮点型向量，逡逑因此不同的码本单词对之间距离相等的概率非常低，可以克服二值哈希方法中逡逑不同二值码对具有相同汉明距离的问题。另一方面，量化方法的优化目标没有类逡逑９逡逑

汉明距离,成对数据,欧氏距离,映射图

邋ｊ）邋＝邋Ｌ邋—邋ｂＴｂｊ邋—邋（ｌ＾ｘｉ邋－邋ｂｉ）ｒ（ｌ２，ｘｌ邋—邋ｂｊ）．逦（２．４）逡逑对于该线性保距目标，本文给出一个可视化的解释，见图２．１。从逡逑ＡＮＮ＿ＳＩＦＴ１Ｍ数据集［６６］中随机选取１０，０００对数据点，并计算它们之间的欧氏逡逑距离。然后使用ＩＴＱ方法［９］生成每个数据点的二进制码，码长３２比特，再计算逡逑Ｉ逦每对数据点之间的汉明距离。每对数据点用一个蓝色的圆表示，红色的实线通过逡逑；逦对这些距离对进行最小二乘拟合生成，即本文提出的线性保距目标采用的方法。逡逑所有的数据对分布在红色的实线两边的一个长条形区域中。可以直观地发现：如逡逑果这个长条形区域向中间红色实线收缩，也就是越窄，哈希函数的保距性能越逡逑好。这个收缩操作使得具有相同欧氏距离的数据对有更相似的汉明距离，间接地逡逑实现了保距目标。逡逑与本文的方法相似，ＢＲＥ方法［１Ｑ］也应用了保距约束，但是ＢＲＥ通过最小逡逑化归一化的汉明距离和归一化的欧氏距离之间的偏差实现保距。它可以被看成逡逑本文的线性保距目标在ａ邋＝逦＝邋０时的一个特例

【相似文献】