论文部分内容阅读
随着互联网和信息技术的快速发展,图像等多媒体信息的应用越来越普遍,它们广泛应用于社会的各个领域,而且信息量也越来越大。如何对这些图像信息进行高效存储和快速的基于内容相似性检索,越来越受到学术界人士的普遍关注。由于图像信息的高维性,它需要不同于普通数据信息的处理技术,而高维索引技术正是加速图像信息检索的有效手段。因此,设计更加有效的高维索引结构,以支持高效的基于内容的相似性检索成为迫切需要解决的关键问题。在这种研究背景下,我们深入研究了与高维信息相关的一些问题,以及已经存在的一些高维索引技术,提出了三种新的索引技术,并通过广泛的实验,验证了我们提出的索引技术的高效性。下面对本文的主要工作和贡献总结如下:
(1)提出了关键维和孪生兄弟节点的概念,以及关键维转移的思想,并在此基础上提出了高维数据空间中基于距离和关键维的两步分割策略和索引技术M+-tree。在索引结构上,M+-tree的每个入口项包含两个指针,分别指向一对孪生兄弟节点的左节点和右节点。在查询中,M+-tree采用两遍过滤方法,即普通兄弟节点间基于距离的过滤和孪生兄弟节点间基于关键维的过滤,其中基于关键维的过滤不需要高维距离计算,只需要进行关键维的比较,代价非常低。孪生兄弟节点间的分割属于无重叠分割,因此,在一定的查询范围内,关键维的过滤能力非常强。针对M+-tree的近邻查询,M+-tree首次提出了基于度量的索引中优先队列访问对查询性能的极大影响,并提出将孪生兄弟节点作为整体进行队列访问,极大地降低了对优先队列的访问。基于这些思想,本文给出了M+-tree的构建、分裂、范围查询以及近邻查询的算法。
(2)提出了两种批量构建M+-tree的方法:基于单步聚类的批量构建技术和基于多步聚类的批量构建技术。其中基于单步聚类的批量构建技术能够实现索引的快速构建,而基于多步聚类的批量构建技术不仅考虑快速构建索引结构,而且把快速的相似性查询作为其另一个重要目标,在充分利用索引空间并快速构建索引结构的前提下,保证了索引空间良好的聚类特性,以及索引相似性查询的有效性。由于我们的批量构建技术是建立在静态构建索引结构基础上的,索引的空间利用率可以达100%。同普通的索引构建方法相比,我们提出的批量构建技术不仅极大地加快了索引的构建速度,而且保证了索引的高效查询性能。
(3)提出了高维数据空间中基于距离和可旋转二元超平面的两步分割策略和索引技术BM+-tree。BM+-tree是在M+-tree的基础上提出的一种改进索引技术。它的提出一方面改进了孪生兄弟节点间的数据分布,使得孪生兄弟节点中包含的数据信息具有更好的聚类特性,另一方面,可旋转的二元超平面使得我们的考察对象能够保留更多的信息,因此,可旋转的二元超平面比关键维具有更强的过滤能力,而且,在某种程度上,避免了关键维过滤中当查询半径增大,过滤能力迅速下降的不足。从而达到进一步提高高维数据查询效率的目的。本文给出了可旋转二元超平面的构建算法以及BM+-tree的构建和查询算法。
(4)提出了假活动子空间的概念,并分析了传统索引技术在进行相似性查询时对假活动子空间访问的极大代价,以及在低维空间中精炼查询空间的可行性。提出了通过空间投影,在低维空间中精炼过滤查询空间的思想。提出了基于最大间隔的空间投影策略,该投影策略能够保证精炼过程的高效性。最后,基于这种思想构建了索引结构MS-tree,以验证这种精炼过滤策略的高效性。我们通过对范围查询的实验,证明了这种精炼过滤策略的高效性。
(5)最后,本文设计并实现了一个基于内容的图像检索系统IBASE。IBASE提供信息的特征提取、索引创建、数据存储以及相似性查询处理功能。用户可以根据自己的需要提交不同的查询请求,通过Web可视化界面查找相似性媒体对象。