大规模图像检索中高维索引技术研究

发布时间：2017-03-26 23:02

  本文关键词：大规模图像检索中高维索引技术研究，由笔耕文化传播整理发布。

【摘要】：大规模图像检索(Large-scale Image Retrieval)旨在从大规模图像库中快速、准确地查找与查询图像内容相似的图像,已在多媒体检索、版权保护和网络信息监控等领域得到广泛的应用和飞速的发展。大规模图像检索系统一般采用特征提取技术将图像的视觉内容描述为高维特征数据,从而将图像检索问题转化为高维数据的相似性度量问题。在网络大规模图像检索背景下,特征数据动辄上百维且特征规模在千万级以上,因此高维索引技术是影响大规模图像检索性能的关键。“维数灾难”问题导致传统的树型索引性能急剧下降,且大规模数据环境下内存资源也成为影响系统性能的瓶颈。如何对大规模高维特征数据建立有效的索引,以满足检索性能和内存资源的要求,是一个极具挑战的研究热点与难点问题。为实现大规模数据环境下高效率、高精度和低内存消耗的高维索引,本文围绕分布式局部敏感哈希索引、数据依赖的多索引哈希算法和二进制层次索引技术等关键问题进行了较为深入的研究,取得了如下成果：(1)分布式局部敏感哈希索引局部敏感哈希索引是目前比较通用的近似最近邻查询算法。由于该算法在建立哈希表时对数据空间进行均匀划分,而真实数据并不呈均匀分布,因此其不能有效处理数据非均匀分布问题,进而影响其查询性能。本文首先提出数据依赖的局部敏感哈希索引算法,该算法具有两层结构。在第一层,通过训练数据集得到一系列聚类中心,然后根据聚类中心把待索引的数据集划分成一个个类,从而使得每类中的数据呈近似均匀分布。在第二层,对每一类中的数据建立哈希表。对于查询数据,首先把它映射到相似的类中心,然后在每一类的哈希表中进行近似最近邻查询。为了进一步提升索引的性能,提出优化的分布式局部敏感哈希算法。在国际基准测试数据集上的实验结果表明,与通用的E2LSH算法相比,数据依赖的局部敏感哈希索引算法在保持高查询精度的同时可以使查询速度提升48倍,并且分布式实现可以使查询速度得到进一步提升。(2)数据依赖的多索引哈希算法多索引哈希是目前使用广泛的针对二进制码的精确查询索引算法。由于多索引哈希基于数据集中的二进制码呈均匀分布这一假设,不能有效处理非均匀分布的数据集；且在计算海明距离时为二进制码的每一位赋予相同的权重导致距离度量模糊。针对这一问题,本文提出数据依赖的多索引哈希算法。首先把二进制码划分为多个连续不重合的子串,并通过协方差矩阵计算二进制码每位之间的相关性,为每一个子串学习得到自适应投影向量。在为每个子串建立哈希表时,使用投影向量对子串进行投影从而得到哈希表中的下标。采用自适应投影的方法可以使得哈希表中的元素接近于均匀分布,进而提升查询速度。本文进一步利用协方差矩阵提出查询结果重排序算法,通过为二进制码的每一位赋予不同的权重对查询结果进行重排序。在大规模数据集上的实验表明,与多索引哈希算法相比数据依赖的多索引哈希算法可以使查询速度提升36.9%-87.4%,查询精度提升22.2%。(3)二进制层次索引技术为了进一步提高索引的查询速度,研究者提出二进制码近似查询算法,其中层次聚类树得到广泛应用。但是该算法随机选取类中心并且使用整个二进制码建立索引,影响查询性能。针对这一问题,本文提出二进制层次索引技术。首先提出一种新的聚类方法,通过二进制码的相对距离选取类中心实现对数据集的均匀划分。然后提出二进制码压缩技术,利用均方差的特性衡量二进制码每位的区分性,生成短小且区分性高的二进制码,并根据压缩二进制码建立层次聚类树。最后采用粗筛选与精确过滤相结合的方式,进行索引查询。在十亿级数据集上的实验表明,本文算法在保证精度的前提下明显提高了查询速度,并且大幅度降低内存消耗。本文的研究工作在分析现有高维索引技术不足的基础上,通过对上述关键问题的深入研究,提高了高维索引在应对大规模高维数据的性能,从而为大规模图像检索提供良好的技术基础,具有广阔的应用前景。
【关键词】：高维索引 分布式局部敏感哈希 数据依赖的多索引哈希 二进制层次索引
【学位授予单位】：中国海洋大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP391.41
【目录】：

• 摘要5-7
• ABSTRACT7-13
• 1 引言13-20
• 1.1 研究背景与意义13-15
• 1.2 研究现状与存在的问题15-17
• 1.3 研究内容17-18
• 1.4 本文的组织结构18-20
• 2 大规模图像检索中的高维索引技术综述20-55
• 2.1 引言20-21
• 2.2 大规模图像检索21-22
• 2.3 图像特征提取22-38
• 2.3.1 全局特征23-26
• 2.3.2 局部特征26-34
• 2.3.3 二进制特征34-38
• 2.4 高维索引38-53
• 2.4.1 距离度量与相似性查询39-43
• 2.4.2 树型结构的多维索引43-47
• 2.4.3 近似最近邻索引47-51
• 2.4.4 二进制索引51-53
• 2.5 高维索引评测准则53-54
• 2.6 小结54-55
• 3 分布式数据依赖的局部敏感哈希索引55-68
• 3.1 概述55-57
• 3.2 数据依赖的局部敏感哈希索引57-60
• 3.2.1 问题提出57-58
• 3.2.2 数据依赖的局部敏感哈希索引58-60
• 3.3 分布式实现60-62
• 3.3.1 问题提出60-61
• 3.3.2 数据集均衡分配61-62
• 3.4 实验结果62-67
• 3.4.1 实验设置62-63
• 3.4.2 参数选取63-64
• 3.4.3 数据依赖的局部敏感哈希索引有效性验证64-66
• 3.4.4 分布式实现有效性验证66-67
• 3.5 小结67-68
• 4 数据依赖的多索引哈希算法68-84
• 4.1 概述68-70
• 4.2 数据依赖的多索引哈希算法70-75
• 4.2.1 多索引哈希算法70-71
• 4.2.2 问题提出71-72
• 4.2.3 数据依赖的多索引哈希算法72-75
• 4.2.4 哈希表数据分布评估75
• 4.3 查询结果重排序75-76
• 4.3.1 问题提出75
• 4.3.2 位权重计算75-76
• 4.4 实验结果76-83
• 4.4.1 实验设置76-77
• 4.4.2 训练数据对算法性能的影响77-78
• 4.4.3 算法有效性和可扩展性验证78-80
• 4.4.4 重排序性能验证80-81
• 4.4.5 在图像检索上的应用81-83
• 4.5 小结83-84
• 5 二进制层次索引84-100
• 5.1 概述84-86
• 5.2 二进制层次索引86-91
• 5.2.1 问题提出86
• 5.2.2 构建二进制层次聚类树86-88
• 5.2.3 二进制码压缩88-90
• 5.2.4 二进制层次索引90-91
• 5.3 实验结果91-98
• 5.3.1 实验设置91-92
• 5.3.2 参数选取92-95
• 5.3.3 算法有效性验证95-97
• 5.3.4 算法可扩展性验证97
• 5.3.5 在图像检索上的应用97-98
• 5.4 小结98-100
• 6 总结与展望100-103
• 6.1 总结100-101
• 6.2 本课题研究展望101-103
• 参考文献103-110
• 致谢110-112
• 个人简历、在学期间发表的学术论文与研究成果112-113

【参考文献】

中国期刊全文数据库 前4条

1 马艳萍;姬光荣;邹海林;谢洪涛;;数据依赖的多索引哈希算法[J];西安电子科技大学学报;2015年04期

2 ;多媒体技术研究:2012——多媒体数据索引与检索技术研究进展[J];中国图象图形学报;2013年11期

3 袁培森;沙朝锋;王晓玲;周傲英;;一种基于学习的高维数据c-近似最近邻查询算法[J];软件学报;2012年08期

4 张明波,陆锋,申排伟,程昌秀;R树家族的演变和发展[J];计算机学报;2005年03期

中国博士学位论文全文数据库 前1条

1 梁俊杰;大规模图像库的高维索引技术研究[D];华中科技大学;2007年

  本文关键词：大规模图像检索中高维索引技术研究，由笔耕文化传播整理发布。

，

本文编号：269477