基于二维嵌入快速近邻搜索的草图检索系统

摘要

随着信息技术和互联网的蓬勃发展，多媒体数码设备的广泛使用，我们拥有了超越以往任何时代的图片信息资源。但由于图片信息的丰富性产生了高维度的图片数据，如何对其进行有效的索引和检索是一个迫切需要解决的问题。传统的检索方法依赖图片的文本标注，而人工标注的代价难以承受，且因为标注主观性过强导致效果不佳。因此基于内容的图片检索成了当下研究的热门，它提取图片的特征作为索引依据，通过对特征的近邻搜索来检索对应的图片。
　　 基本的近邻搜索是顺序地扫描数据库，但由于图片特征的高维度，计算所有图片的相似度代价巨大，而传统的近邻搜索算法在面对高维数据时常常失效，当维度高到一定程度时，其搜索效率甚至不如顺序扫描。本文参考了部分前人的研究，针对高维数据提出了基于二维嵌入的快速近邻搜索算法，能够较为高效的搜索准确的近邻。
　　 我们首先提出了结合制高点树结构的点过滤策略，通过数据的嵌入在低维空间上快速的过滤非近邻点，从而缩小搜索空间。为了增强点过滤的效果，我们加入了数据采样算法，通过合理的样本采样，以较小代价获得了对过滤阀值更精确的估计，从而提高了数据点的过滤率。通过这种“采样-过滤-验证”三步骤结合的策略，我们的算法能够较为有效地对高维数据进行准确的快速近邻检索。在研究性数据上的实验结果表明，我们的算法能够有效地处理高维数据，并较为快速地检索出查询点的准确近邻。最后我们将算法应用到草图检索中，并实现了对应的草图检索系统。

目录

声明

摘要

第1章 绪论

1．1 课题背景

1．1．1 近邻搜索算法的应用

1．1．2 基于内容的图片检索系统应用

1．2 本文主要工作

1．3 本文的组织结构

1．4 本章小结

第2章 近邻搜索算法综述

2．1 基于空间划分的近邻搜索

2．1．1 使用K维树的近邻搜索

2．1．2 使用制高点树的近邻搜索

2．2 基于散列的近邻搜索

2．2．1 使用局部敏感散列的近邻搜索

2．2．2 使用谱散列的近邻搜索

2．3 基于聚类思想的近邻搜索

2．3．1 使用分层聚类树的近邻搜索

2．3．2 使用近似向量文件的近邻搜索

2．4 本章小结

第3章 基于二维嵌入的近邻搜索

3．1 基于欧氏距离的二维嵌入

3．1．1 欧氏距离的一个上下界

3．1．2 高维数据的二维嵌入

3．2 基于二维嵌入的最近邻搜索

3．2．1 双制高点树结构的二维嵌入近邻搜索

3．3 实验结果与分析

3．3．1 实验数据介绍

3．3．2 实验结果及分析

3．4 本章小结

第4章 基于二维嵌入搜索的性能分析与提高

4．1 二维嵌入近邻搜索的性能瓶颈分析

4．1．1 双制高点树的性能分析

4．1．2 阀值优化分析

4．2 利用快速近邻采样提高搜索性能

4．2．1 利用聚类采样提高搜索性能

4．2．2 利用随机K维树采样提高搜索性能

4．3 实验结果与分析

4．3．1 过滤效果对比实验

4．3．2 查询时间对比实验

4．4 本章小结

第5章 基于二维嵌入搜索的草图检索系统

5．1 基于草图的图片检索应用介绍

5．2 系统整体架构

5．3 系统实现重点

5．3．1 建立优质图片数据集

5．3．2 图片特征提取

5．3．3 索引与快速检索

5．4 草图检索系统效果展示

5．4．1 上传页面展示

5．4．2 检索结果展示

5．5 本章小结

第6章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢