复杂结构的聚类学习及图像分割研究

论文摘要

所谓复杂结构,形象地说,即指隐藏于数据集内的聚类:i)分布形状各异,除了紧性云状的凸分布之外,更多的是流形状的非凸分布; ii)含有大量噪声或野值; iii)重叠或相交;iv)密度分布非常不均;v)规模相当大。最典型的例子就是数字图像数据。从数据形态而言,它们外在地表现为“类内相似性”小于“类间相似性”,这违反常规意义下“聚类”的目的。因此,现有的聚类算法大都无法对此获得满意的聚类或分割结果。于是,复杂结构的聚类学习成为了当今数据挖掘和图像分割应用领域的研究热点和主流之一。本文针对这种“类内相异、类间相似”的复杂结构聚类问题进行了较深入的思考和研究,提出了相应的快速有效的复杂结构聚类算法,并将部分算法成功地应用于灰度图像分割,其创新性研究成果主要分为两部分:第一部分.复杂结构的聚类:(1)提出了一个基于结构连通的启发式聚类算法,具体包括:1)充分挖掘数据的结构性信息,引出邻域密度指标和基于多项式核的邻域密度指标,将数据分为质心、毂和野值;2)构建质心点之间的连通性,建立一个基于路径的规范化结构性度量,进行启发式聚类;3)实验分析表明该算法抗噪性能较强、能快速有效地发现多种形状的聚类、并能有效分离重叠聚类。(2)提出了两个基于结构一致的紧性准则聚类算法,具体包括:1)建立基于密度一致的相似性准则;2)建立基于流形一致的相似性准则;3)定义相应的两种相似性矩阵,分别嵌入到模糊C均值和基于规范化割的谱聚类算法中;4)实验分析表明改进后的两个紧性准则聚类算法抗噪性能较强、能有效地发现密度不均的多种形状的聚类、并能分离交叉聚类。第二部分.复杂结构的图像分割:(1)提出了一个基于灰度邻域的有向树图像分割算法,具体包括:1)构造基于灰度邻域的密度因子,将所有灰度分为稠密灰度(具有繁殖能力)和稀疏灰度(不具有繁殖能力);2)寻找稠密灰度为根结点构建有向树,生长在同一棵有向树上的灰度对应的像素集合为一个分割区域;3)该算法具有独立于图像大小的计算复杂度;4)实验分割结果表明该算法对初始根结点的选取鲁棒,并能很好地保留图像中的细节内容。(2)提出了一个基于尺度的一致连通树图像分割算法,具体包括:1)构造出关于各个像素点的邻域一致性因子,将所有像素分为种子像素(具有繁殖能力)和非种子像素(不具有繁殖能力);2)定义一致连通性分割准则,引出等价类和一致类的概念,从理论上保证任意一幅图像可分;3)寻找种子像素为根结点构建一致连通树,生长在同一棵一致连通树上的像素集合为一个分割区域;4)该算法具有线性于图像大小的计算复杂度;5)实验分割结果表明该算法能很好地实现语义分割:一个感兴趣目标完整地只对应一个分割区域。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.1.1 聚类问题的本质
• 1.1.2 聚类问题的理论化
• 1.1.3 聚类问题的应用化
• 1.2 聚类学习的基本步骤
• 1.3 复杂结构的聚类学习
• 1.4 本文的主要研究工作
• 第一部分 复杂结构的聚类学习
• 第二章 背景知识及相关工作
• 2.1 引言
• 2.2 相似性度量
• 2.3 最优划分方法
• 2.3.1 基于准则函数的聚类算法
• 2.3.2 基于相似性的启发式聚类算法
• 2.4 本章小结
• 第三章 基于结构连通的启发式聚类算法
• 3.1 引言
• 3.2 数据的结构性描述和结构性信息
• 3.2.1 数据的结构性描述
• 3.2.2 邻域密度指标（NDI）
• 3.2.3 基于多项式核的邻域密度指标（PKNDI）
• 3.3 连通性和正规化的结构性度量
• 3.3.1 基于质心的连通性
• 3.3.2 规范化的结构性度量
• 3.4 基于结构连通的启发式聚类算法及其数值实验
• 3.4.1 算法描述
• 3.4.2 基于欧氏距离的结构连通聚类算法的数值实验分析
• 3.4.3 基于多项式核的结构连通聚类算法的数值实验分析
• 3.5 本章小结
• 第四章 结构一致性的紧性准则聚类算法
• 4.1 引言
• 4.2 基于密度一致准则的相似性矩阵
• 4.2.1 k 邻域和局部密度
• 4.2.2 密度一致的相似性矩阵
• 4.2.3 密度一致相似性矩阵的有效性
• 4.3 基于密度一致的紧性准则聚类算法
• 4.3.1 基于密度一致准则的谱聚类算法及其数值实验分析
• 4.3.2 基于密度一致准则的FCM 算法及其数值实验分析
• 4.4 基于子空间邻域的聚类算法
• 4.4.1 基于子空间邻域的相似性矩阵
• 4.4.2 子空间邻域谱聚类算法及其数值实验分析
• 4.4.3 子空间邻域FCM 算法及其数值实验分析
• 4.5 本章小结
• 第二部分 复杂结构的图像分割
• 第五章 基于灰度邻域的有向树图像分割算法
• 5.1 引言
• 5.2 灰度邻域密度因子
• 5.3 GNDT 分割算法
• 5.4 参数分析及实验结果比较
• 5.4.1 GNDT 算法的参数分析
• 5.4.2 图像分割实验结果比较
• 5.5 本章小结
• 第六章 基于尺度的一致连通树图像分割算法
• 6.1 引言
• 6.2 一致连通性分割准则
• 6.2.1 邻域一致性因子
• 6.2.1.1 方形邻域
• 6.2.1.2 邻域一致性因子
• 6.2.2 一致连通性分割准则
• 6.2.2.1 种子像素
• 6.2.2.2 一致连通性分割准则
• 6.3 CCT 分割算法
• 6.3.1 CCT 分割算法
• 6.3.2 CCT 算法的参数分析
• 6.3.3 CCT 算法的复杂度分析
• 6.4 实验结果及分析
• 6.4.1 人工图像的分割结果比较
• 6.4.2 自然灰度图像的分割结果比较
• 6.4.3 “噪声”类解释
• 6.4.4 分割实验评价
• 6.5 本章小结
• 第七章 结束语
• 7.1 总结
• 7.2 展望
• 参考文献
• 致谢
• 博士期间的研究成果及发表的学术论文
• 攻读博士学位期间参加科研项目情况