基于加权拉普拉斯方法的多层次图分割

发布时间：2023-05-03 11:23

　　图分割是图处理领域中一种重要方法,并且可应用到计算机科学的其它分支,例如计算机视觉、数据挖掘等,具有重要的影响。由于大规模图分割在实践中意义重大,其性质和处理方法不同于小规模的图,因此对于大规模图的研究是一项重要工作。为了提高图分割质量,降低运行时间,本文将多层次图分割框架和谱聚类方法的思想结合起来,提出大规模图上新的图分割方法。本文的主要工作包括如下几个方面:(1)边加权图或是点加权图上的图分割已经得到了充分的研究,双重加权图是一种边和点都带权的加权图,在很多问题中有重要的应用,例如路径规化、最优圈问题等,然而尚未得到充分研究。本文提出了加权拉普拉斯方法,较好地解决了双重加权图上的图分割问题。该方法受谱聚类方法的启发,利用图上的加权拉普拉斯来处理最小割问题,其中加权拉普拉斯是图拉普拉斯的推广。借助这一概念,我们将双重加权图上的最小割问题转化为加权拉普拉斯的特征分解问题,并称为加权拉普拉斯方法。通过计算加权拉普拉斯的前k个最小的特征向量,并对这些向量的各个分量逐一进行聚类,最终能产生双重加权图上的k-分割。通过研究加权拉普拉斯的性质,并利用Eluer-Lagrange方程计算最小割的极...

【文章页数】：63 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第1章 绪论
    1.1 选题背景与意义
    1.2 国内外研究现状
    1.3 本文的主要研究工作
    1.4 本文的组织安排
第2章 图分割和正则图背景介绍
    2.1 图分割
        2.1.1 图的一些基本概念
        2.1.2 图分割经典算法
        2.1.3 图分割近似算法
    2.2 多层次图分割
        2.2.1 粗化算法
        2.2.2 初始聚类算法
        2.2.3 细化算法
    2.3 正则图和正则性引理
    2.4 本章小结
第3章 加权拉普拉斯方法
    3.1 相关理论介绍
    3.2 图拉普拉斯方法在双重加权图上的拓展
    3.3 本章小结
第4章 基于加权拉普拉斯方法的加权谱算法
    4.1 平衡最小割问题、加权割问题和初始聚类问题的等价性
        4.1.1 平衡最小割问题和加权割问题的等价性
        4.1.2 初始聚类问题和加权割问题的等价性
    4.2 加权谱算法
    4.3 准正则图上最小割问题的多项式时间近似算法
    4.4 本章小结
第5章 实验与结果分析
    5.1 实验环境
        5.1.1 KaHIP多层次图分割框架
        5.1.2 实验平台和数据
    5.2 实验结果和分析
        5.2.1 粗化算法实验和分析
        5.2.2 加权谱算法实验与分析
    5.3 本章小结
第6章 总结与展望
    6.1 总结
    6.2 展望
参考文献
致谢
在读期间发表的学术论文与取得的研究成果



本文编号：3806696