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