面向大规模图像库的层次化索引机制研究

论文摘要

合理的高维索引机制是提高大规模图像库基于内容检索性能的关键,然而,由于受到“维度灾难”的影响,传统的索引结构在处理高维数据时,性能急剧下降。针对上述问题,本文以大规模图像库的基于内容检索为应用背景,围绕图像特征的“高维”特性,以高维空间的子空间为出发点,研究了图像高维特征数据的索引问题。在相关研究的基础上,论文首先明确了高维数据索引所要解决的主要问题,提出了高维索引的研究框架,然后针对该框架中的相似性度量、聚类和降维分别进行了研究,并最终提出了一个可适用于大规模图像库基于内容检索的高维索引机制。论文的贡献主要体现在以下几个方面:提出了一种基于子空间的高维数据相似性度量方法。传统的度量方式都在数据集的整个特征空间中计算数据之间的相似性。在高维情况下,如果仍然采用这些度量方法,数据特征中的噪声维将对度量的结果产生显著的影响,从而导致度量结果的不准确性。针对该问题,本文提出了一种基于子空间的相似性度量方法,该方法在高维特征空间的一些子空间中度量数据之间的相似性,从而能够克服高维数据中的噪声属性对度量的影响,以获得更准确的相似性度量结果。提出了一种基于密度的子空间聚类方法。在高维空间中,由于数据的稀疏性,传统的聚类方法难以有效地聚类高维数据。针对该问题,本文提出了“维度最大化子空间聚类”的概念,并在此基础上提出了一种基于密度的子空间聚类方法。该方法将子空间聚类的思想与基于密度的聚类思想有机结合起来,充分利用了基于密度的聚类方法能发现任意形状聚类的优点,同时也有效克服了“维度灾难”的影响,算法在聚类的规模与聚类所在的子空间的维数之间进行了合理的折衷,从而使得聚类的结果能够为高维数据索引的建立提供更加完整、准确的依据。提出了基于子空间聚类的高维数据索引结构以及对应的相似搜索算法。基于密度的子空间聚类方法能够形成任意形状的不规则聚类,而传统的基于中心点的聚类表示方法往往无法有效地表示这些聚类。针对该问题,本文基于代表点的思想,采用多个代表点来表示一个聚类,并给出了聚类代表点的选择方法,从而建立了基于子空间聚类的索引结构;在基于该索引结构的相似搜索中,针对样本对象与子空间聚类的匹配问题,提出了样本对象与子空间聚类的匹配方法,该方法通过一个校正因子很好地解决了聚类存在于不同子空间的问题,从而有效地克服了聚类所在的子空间的维数对匹配过程产生的影响,提高了相似检索的合理性。提出了一种基于个体本征维的降维索引机制。传统的降维方法大多从数据集的整体特性出发,把数据集中所有的数据点都降维至一个统一的子空间中,将它们直接用于高维数据的索引将会由于过高的信息损失而影响相似搜索的性能。针对该问题,本文提出了基于个体本征维的降维思想,并针对图像的72维HSV颜色特征,提出了一种基于个体本征维的降维索引方法。相对于子空间聚类而言,该方法从减少相似搜索计算量的角度出发,很好地解决了高维数据的索引问题。综上所述,本文主要针对图像特征数据的高维特性,研究了基于内容图像检索中的高维索引问题。由于“维度灾难”的影响,很难在整个特征空间中来度量高维数据的相似性并据此建立高维数据的索引结构。以此为出发点,本文从子空间的角度分别研究了高维数据的相似性度量和聚类,并从个体本征维的角度研究了高维数据的降维问题。这些研究为克服“维度灾难”的影响提供了有效的手段,并为面向大规模图像库的高维索引机制的建立提供了可行的解决方案,对于相关的研究具有重要的理论及实践上的参考价值。

论文目录

• 图目录
• 表目录
• 摘要
• Abstract
• 第一章绪论
• 1.1 问题的提出
• 1.1.1 引言
• 1.1.2 维度灾难
• 1.1.3 研究意义及应用前景
• 1.2 国内外研究现状
• 1.2.1 基于内容图像检索的国内外研究现状
• 1.2.2 高维索引技术的研究现状
• 1.2.3 研究现状小结
• 1.3 本文的主要工作
• 1.4 论文的内容安排
• 第二章 面向大规模图像库的高维索引研究框架
• 2.1 CBIR 中的相似查询
• 2.2 高维索引面临的问题
• 2.3 CBIR 中的高维索引机制研究框架
• 2.3.1 相似性度量
• 2.3.2 高维索引的创建
• 2.3.3 基于索引的相似搜索
• 2.4 本章小结
• 第三章 高维空间中的相似性度量研究
• 3.1 问题的提出
• 3.1.1 现有度量方式
• 3.1.2 “维度灾难”对高维空间中最近邻特性的影响
• k 度量在高维空间中的不稳定性'>3.1.3 L_k度量在高维空间中的不稳定性
• 3.2 一种适用于高维数据的相似性度量方式
• 3.2.1 子空间中的相似性度量
• 3.2.2 基于网格划分的子空间度量
• 3.2.3 网格划分参数的确定
• 3.3 实验及结论
• 3.4 本章小结
• 第四章 面向大规模图像库的聚类索引机制研究
• 4.1 问题的提出
• 4.1.1 传统的聚类方法及其存在的主要问题
• 4.1.2 基于密度的聚类
• 4.1.3 子空间聚类
• 4.1.4 问题的描述
• 4.2 基于密度的子空间聚类算法研究
• 4.2.1 基于密度聚类的定义在子空间中的扩展
• 4.2.2 密度相连的单调性
• 4.2.3 一种基于密度的子空间聚类算法
• 4.3 基于子空间聚类的索引方法研究
• 4.3.1 基于子空间聚类的索引结构
• 4.3.2 基于聚类索引的相似搜索算法
• 4.4 实验结果与讨论
• 4.4.1 子空间聚类算法运行时间验证
• 4.4.2 基于聚类索引的搜索算法的性能验证
• 4.5 小结
• 第五章 面向大规模图像库的降维索引机制研究
• 5.1 问题的提出
• 5.1.1 引言
• 5.1.2 现有降维方法与数据集的本征维
• 5.1.3 个体本征维
• 5.2 针对图像HSV 颜色特征的降维方法研究
• 5.2.1 HSV 颜色模型
• 5.2.2 一种新的降维方法
• 5.3 基于降维的高维索引机制研究
• 5.3.1 基于降维的高维索引结构
• 5.3.2 基于降维索引的相似搜索算法
• 5.4 实验结果与讨论
• 5.5 本章小结
• 第六章 基于聚类和降维的层次化索引机制及其应用
• 6.1 基于聚类和降维的层次化索引机制
• 6.1.1 CDRI 层次化索引机制
• 6.1.2 实验及结论
• 6.2 CDRI 索引机制在MMDPMS 中的应用
• 6.2.1 MMDPMS 系统总体介绍
• 6.2.2 CDRI 索引机制在系统中的应用
• 6.3 本章小结
• 第七章 总结与展望
• 7.1 本文的主要贡献
• 7.2 进一步的研究方向
• 7.3 展望
• 致谢
• 参考文献
• 攻读博士学位期间发表论文及参与科研情况
• 1. 【论文】
• 2. 【参与的科研项目】