基于空间不等式过滤的降维索引技术研究

摘要

伴随着信息技术的高速发展，数字图书馆、数字医疗、地理信息系统等应用领域相继出现，人们的日常生产和生活中产生出大量的图像等多媒体信息。基于内容的图像检索技术正是在这样的背景下产生的。基于内容的图像检索实现的是对图像特征向量的相似性检索，这些图像的特征是在人的参与下由计算机自动提取出来的，提取出来的特征向量维数都很高，因此如何快速有效的对这些高维数据进行相似性检索成为了一个重要的研究课题。 降维技术和高维索引技术是高维相似性检索技术中的两个主要的研究方向。由于很多索引结构存在着随维数增加性能迅速下降的现象，因此有必要引入降维技术降低数据的维数。降维技术的目标是从横向约减数据的表示形式；高维索引技术的目标是有效地组织数据集，使得只访问一小部分数据集，就可以找到所需的结果，这实际是一种纵向的对数据集的约减。已有的降维方法有很多，如PCA，KLT，SVD等。针对高维索引的研究也取得了很多的成果，如R树系列、M树、VA-file、Δ树等。 基于对以上方法的分析比较，本文提出了从横向和纵向同时对数据进行约减来解决高维问题的思想。在借鉴了Δ树和M树的基础上，本文提出的解决方案是采用结合了SVD降维及层次索引的复合结构，同时依据高维数据的空间特性，提出了一种新的跨空间不等式过滤的方法。这种基于空间不等式的过滤方法的优势就是通过预计算的办法，在查询时利用空间原有的信息来进行代价很小的过滤，从而有效地减少了距离计算量。实验表明，这种过滤代价几乎可以忽略不计，能够有效地提高索引的查询性能，对于解决高维问题是非常有效的。

目录

文摘

英文文摘

第一章引言

1.1基于内容图像检索概述

1.1.1基于内容的图像检索的产生与发展

1.1.2基于内容图像检索的应用

1.2基于内容的图像检索关键技术

1.2.1特征提取技术

1.2.2降维技术

1.2.3高维索引技术

1.2.4图像内容描述的国际化标准

1.3基于内容图像检索存储系统——Fish数据库介绍

第二章降维技术研究

2.1 PCA变换

2.2 KLT变换

2.3 SVD变换

第三章高维索引技术

3.1 R树系列索引结构

3.2 M-tree

3.3 VA-file系列方法

3.4 △-tree

3.4.1 △-tree的结构

3.4.2 △-tree的建树过程

3.4.3 △-tree的查询

第四章基于空间不等式过滤的索引技术

4.1设计思想

4.1.1二次过滤有效性的数学证明

4.1.2基于空间的不等式过滤方法

4.2设计实现

4.2.1建树过程

4.2.2查询过程

第五章性能评价与测试

5.1测试环境

5.2测试方案

5.3测试结果分析

5.3.1数据集的大小与查询性能

5.3.2过滤百分比与过滤的有效性

5.3.3最近邻查找性能

第六章结束语

参考文献

致谢