面向大规模图片搜索的基于锚图哈希的半监督度量学习算法

发布时间：2020-06-07 19:55

【摘要】：由于因特网和智能终端的普及,人们所面对的数据通常具有海量高维的特征,在大规模数据集里进行快速的相似性搜索有着很重要的应用价值。基于哈希的搜索算法可以把高维的数据映射到低维的二进制编码,在保留原始空间近邻关系的同时提高了计算效率,并且极大地减少了存储空间的占用,因而,基于哈希的相似性搜索技术已广泛应用于机器学习、计算机视觉和多媒体等领域。本文提出了基于锚图哈希的半监督度量学习算法(Semi-supervised Metric Learning Based Anchor Graph Hashing,MLAGH),学习最优的距离度量以保留图片的语义和特征相似性,并在此基础上利用锚哈希技术把相似的图片映射成相似的二进制码元,以便于图片检索。具体学习过程包括:首先,在特征空间中构建图片的相似图,应用分簇算法在相似图中抽样出锚点,并获得样本和锚点的三元组关系。然后,利用样本和锚点的标记平滑性假设和三元组在特征空间中的距离限制构建目标函数,采用随机梯度下降法最小化目标函数以得到最优的距离度量。更进一步,引入惩罚因子减少随机梯度下降的迭代次数以减少算法的时间开销,提高算法的运行效率。最后,在两个公共的大规模图片数据集中进行图片检索实验,并和常用的哈希算法进行性能对比分析,从而验证了本文提出算法在检索的精度和时间开销方面的优越性。
【图文】：

图 1.1 （a）图片最近邻搜索示意图；（b）图片最近邻搜索实际应用示意图应用在图片相似性搜索领域中的技术有线性搜索方法，基于树的搜索方法和基于哈希的搜索方法等。线性搜索方法就是对数据库中的所有图片逐个遍历，找到查询图片的近似图片。这样做可以获得精确的结果，但是效率很低。特别是当数据规模很大时，线性搜索方法就会因为会产生极大的计算复杂度和需要大量的存储空间而变得不再合适。在大数据应用中，图片的相似性搜索通常等价于近似最近邻搜索问题（Approximate Nearest Neighbors，ANN），解决近似最近邻搜索问题的一种传统方式是使用基于树的搜索算法[9]。如果数据库中样本数量为 n，那么基于树的 ANN 搜索的时间复杂度为 O(logn)。在数据的维度较低时，，基于树的搜索方法由于较高的查询效率通常可以获得较好的性能。但是在大数据时代，我们所面对的数据较之以前，不论从数据的数量还是数据本身的特征维度上都在急剧增加。在数据维度很高的情况下，基于树的搜索算法的性能将会急剧下降。这就要求我们要采取更为有效的方式去解决海量高维数据环境下的相似性搜索问题，由于基于哈希的搜索方法相似性搜索的计算效率非常高。而且哈希算法把图片生成的哈希索引码值，而不是图片本身存储到内存中。所

学硕士研究生学位论文 第中的距离较远。从语义标记角度分析，中间图片和右边图片具有相同的语左边图片的语义标记是“自由女神”。所以，无论从特征空间还是语义空间右边图片的相似性都更高，它们和左边图片的相似性都要更低。使用在训到的哈希函数，把图片映射为 8 比特的二进制编码后，可以看到中间图片汉明距离很小，而它们和左边图片编码的汉明距离很大。
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP391.41;TP181

【参考文献】

相关期刊论文 前1条

1 李武军;周志华;;大数据哈希学习:现状与趋势[J];科学通报;2015年Z1期

本文编号：2701920