学位论文 > 优秀研究生学位论文题录展示

形状特征描述及聚类算法研究

作　者: 潘鸿飞
导　师: 陈军宁；梁栋
学　校: 安徽大学
专　业: 电路与系统
关键词: 形状识别聚类动态规划中轴变换谱图理论数据降维随机游走模型
分类号: TP391.41
类　型: 博士论文
年　份: 2011年
下　载: 147次
引　用: 0次
阅　读: 论文下载

内容摘要

形状识别与聚类是人工智能、数据检索、计算机视觉和模式识别等领域的基础性研究课题。该课题的研究方向主要是在无先验(已知)类别标准的条件下,以形状的有关特征作为判断依据,实现聚类。而相关特征的选取及其结构分析,一直是形状识别与聚类问题的重点和难点。近年来,通过提取形状特征,以动态规划、谱图理论、中轴变换、数据降维等为手段,研究形状的结构特征的方法,日益受到众多学者的关注,成为相关研究领域的热点。本文在形状结构特征提取、分析以及形状的识别和聚类方面做了较为系统的研究,主要研究内容和创新之处有以下四个方面：1、提出一种基于编辑距离与动态规划的形状识别与检索算法。首先,利用中轴变换提取形状的骨架特征；然后,将该骨架特征点以字符串的形式表示,利用编辑距离算法,比较字符串间的距离；最后,运用动态规划实现形状的识别与检索。该算法利用骨架特征,较好地处理了形状的非刚体形变的问题。而从空间特征到字符串特征的转换,则为解决特征比较问题提供了新的思路,同时也有利于增强算法的鲁棒性。比较实验说明该算法对非刚体形变有较好的识别效果。2、提出了一种基于谱图理论的形状描述、识别与聚类算法。该算法主要研究两个方面的问题：(1)通过提取形状的骨架特征点和图谱分析,以特征值描述形状的结构特征；(2)运用主成分分析,将上述特征值投影到低维空间中,利用该方法实现了形状的聚类。算法以特征点间的空间关系和角度关系为基础,综合应用各种结构信息,增强了算法的鲁棒性。针对公共数据集的仿真实验说明了该聚类算法对具有较大形变的形状仍有较好的聚类效果。3、提出了一种利用Laplace谱特征与多维尺度法相结合的形状识别与聚类算法。首先,提取形状的轮廓点作为特征点,并构造Laplace矩阵；然后,以Laplace矩阵的特征值来刻画图的结构信息；最后,利用多维尺度法,将由各类形状的轮廓点构成的序列图投影至低维空间,在该空间内分析形状的分布情况,实现聚类。在上述算法中,形状的特征由一组向量表示,向量的维数越大,越能充分地反映其结构的特征,但却不利于聚类结果的比较。为了解决该问题,引入了数据降维的方法,实现了三维空间中形状聚类结果的可视化。对比实验的结果说明了该算法有较好的聚类效果。4、提出一种将Laplace矩阵的谱与随机游走模型相结合,用以表示图结构特征的形状聚类算法。针对形状的不同空间结构特征,通过对轮廓点所构完全图的Laplace矩阵的特征值以及图的随机游走模型概率性质的分析,建立了描述轮廓点空间结构特征的数学模型。以此模型为基础,定义状态向量,实现了形状的识别与聚类。随机游走模型可从概率统计的角度分析图的结构特征,增强了数据分析的稳定性。对比实验说明了提出的数学模型能较好地反映形状的空间结构,而在此基础上定义的状态向量则为形状聚类提供了稳定而有效的判断依据。

全文目录

摘要  3-5
Abstract  5-7
目录  7-10
插图清单  10-12
Illustration List  12-14
第一章绪论  14-31
  1.1 引言  14
  1.2 相关算法综述  14-28
    1.2.1 基于轮廓的形状特征描述  15-23
    1.2.2 基于区域的形状特征描述  23-27
    1.2.3 基于谱图理论的形状特征描述和聚类算法的特点  27
    1.2.4 本章小结  27-28
  1.3 论文的主要研究内容  28-29
  1.4 论文的组织结构  29-31
第二章基于编辑距离和动态规划的形状识别与检索算法  31-54
  2.1 引言  31-32
  2.2 形状特征的提取和表示  32-36
    2.2.1 骨架特征提取  32-34
    2.2.2 骨架特征表示  34-36
  2.3 相似度计算  36-37
  2.4 动态规划基本理论  37-43
    2.4.1 动态规划的基本概念  38-41
    2.4.2 动态规划的基本方程  41-43
  2.5 Petrakis等提出的动态规划算法  43-46
  2.6 提出的动态规划算法  46-48
  2.7 实验与分析  48-53
    2.7.1 相关参数选择  48-49
    2.7.2 对比实验  49-53
  2.8 本章小结  53-54
第三章基于谱图理论的形状聚类算法  54-79
  3.1 引言  54-55
  3.2 主成分分析算法  55-60
    3.2.1 主成分分析的基本原理  55-56
    3.2.2 主成分分析的计算方法  56-60
  3.3 提出的基于谱图理论的形状聚类算法  60-63
    3.3.1 特征点结构描述算法  60-63
  3.4 实验与分析  63-68
    3.4.1 特征值分布情况分析  64-65
    3.4.2 形状聚类分析  65-68
  3.5 多维尺度算法  68-72
  3.6 提出的基于Laplace谱的形状聚类算法  72-73
  3.7 实验与分析  73-77
    3.7.1 特征值分布  73-74
    3.7.2 形状聚类实验及分析  74-77
  3.8 本章小结  77-79
第四章基于特征模型的形状识别与聚类算法研究  79-103
  4.1 引言  79-80
  4.2 基于奇异值分解的图结构特征描述算法  80-91
    4.2.1 图的相关性质  80-86
    4.2.2 图的表示和图结构的同构  86-90
    4.2.3 提出的基于特征值的图结构特征描述法  90-91
  4.3 提出的基于随即游走模型的图结构特征描述算法  91-95
    4.3.1 随机游走模型  91-93
    4.3.2 图结构特征描述法  93-95
  4.4 提出的算法和对比实验及分析  95-102
    4.4.1 数学模型构建  95-97
    4.4.2 实验  97-99
    4.4.3 实验二  99-102
  4.5 本章小结  102-103
第五章总结与展望  103-106
参考文献  106-116
攻读学位期间发表的学术论文目录  116-117
攻读学位期间参加的科研项目目录  117-118
致谢  118

相似论文

隐式用户兴趣挖掘的研究与实现,TP311.13
图像分割中阴影去除算法的研究,TP391.41
基于图分割的文本提取方法研究,TP391.41
牡丹EST-SSR引物开发及其亲缘关系分析,S685.11
高血压前期证候特征研究,R259
高忠英学术思想与经验总结及运用补肺汤加减治疗呼吸系统常见病用药规律研究,R249.2
K-均值聚类算法的研究与改进,TP311.13
大学生综合素质测评研究,G645.5
大豆品种对腐竹品质的影响及其品质评价体系的初步构建,TS214.2
21个荷花品种遗传多样性的ISSR分析,S682.32
基于聚类分析的P2P流量识别算法的研究,TP393.02
基于混合自适应遗传算法的动态网格调度问题研究,TP393.09
桃杂交后代（F₁）幼苗光合效能评价,S662.1
南通市农业面源污染负荷研究与综合评价,X592
土壤环境功能区划研究,X321
基因表达谱数据聚类分析方法比较与大豆疫霉基因的网络构建,S435.651
大豆杂种优势及其遗传基础研究,S565.1
象草自交后代无性系的饲用价值及生物质能特性初步评价,S543.9
细菌聚类算法及其在图像分割问题中的研究与应用,TP391.41
基于变异粒子群的聚类算法研究,TP18
K-means聚类优化算法的研究,TP311.13