基于图论的图像分割和并行化研究

《基于图论的图像分割和并行化研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、劣臻交万方数据硕士学位论文基于图论的图像分割和并行化研究Researchofimagesegmentationandparailelizationbasedongraphtheory作者：刘雅坤导师：于双元北京交通大学2014年3月万方数据学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论

2、文的复印件和磁盘。(保密的学位论文在解密后适用本授权说明)学位论文作者签名：剜删签字日期：2，。／中年≥月≯6日土坫；月獬气亍哗孙；抑签期吐丌-jyr【导字，登万方数据中图分类号：TP39UDC：004．9学校代码：10004密级：公开北京交通大学硕士学位论文基于图论的图像分割和并行化研究Researchofimagesegmentationandparallelizationbasedongraphtheory作者姓名：刘雅坤导师姓名：于双元学位类别：工学学号：11120464职称：副教授学位级别

3、：硕士学科专业：计算机科学与技术研究方向：分布式计算北京交通大学2014年3月万方数据致谢本论文的工作是在我的导师于双元副教授的悉心指导下完成的，于双元副教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来于双元老师对我的关心和指导。于双元副教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给予了我很大的关心和帮助，在此向于双元老师表示衷心的谢意。于双元副教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心的感谢。在实验室工作及撰写论文期间，乔艳茹、雷莹、娄

4、启林等同学对我论文中的研究工作给予了热情帮助，在此向他们表达我的感激之情。另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。万方数据jE立交道太堂亟±堂僮途塞擅噩摘要图像分割是数字图像处理和计算机视觉中重要任务之一。本文研究的基于图论谱聚类分割方法是近几年来的图像分割领域的一个新的研究热点，基于图论的谱聚类基本思想是将一幅图像映射成一个无向加权图，将像素点映射为顶点，相邻的像素之问的视觉信息(比如灰度或距离)的相似度来定义权值。将图像按照某种划分建立特定函数，当函数达到最小值就得到图像

5、的一个最佳分组。该方法具有高度的灵活性，它提供统一框架处理图像的灰度、纹理、噪声，适用于任何数字图像。本论文研究的最小最大割集(Min—maxcut)充分体现了基于图论的谱聚类方法的最优准则，即子图内相似度最大，子图问相似性最小。将这个NP的准则转化为特征方程求解，但是这个方法存在求解大规模矩阵的特征向量的复杂问题，算法随着图像尺寸增大效率大大降低。图像映射为图构建过程中，边的构建方法不再简单的依据四邻域或八邻域，而以某顶点为中，tS,将半径r内所有顶点与其进行关联。相似度计算函数的构造选用考虑了顶

6、点之问的灰度和距离的高斯函数。相似度矩阵更真实反映像素之间的关系。为了降低最小最大割算法中顶点和边的数目，在介绍了分水岭算法的思想和主要缺陷后，将基于数学形态学的分水岭方法引入到最小最大割算法中，提出基于分水岭的最小最大割算法。首先，利用分水岭方法图像预分割，生成的过分割小区域转化为无向图中的顶点，相邻区域间的差异转化为边的权重，再利用最小最大割算法将小区进行合并操作。基于分水岭的最小最大割算法既能消除分水岭的过度分割现象，又能降低图中边的数目，获得图像的全局特征，提高最小最大算法分割效率。文中利用

7、基于GPU的CUDA平台加速最小最大割算法，减少算法的运行时间。根据GPU适合处理计算密度高、计算逻辑相对简单的大规模数据的计算特性，理论上分析了最小最大割算法加速的可行性。根据最小最大割算法实现步骤，设计了基于GPU的最小最大割算法。实现了三对角矩阵k个特征值求解加速和其对应k个特征向量的K—means聚类加速。实验分析得出基于GPU的最小最大割算法加速比在1．5左右，得出的结论是大规模矩阵分块计算提高最小最大割算法加速比的主要途径。关键词：图像分割；图论；最小最大割；并行化分类号：TP39万方数

8、据韭立蔓茧笪太堂亟±堂僮论塞△坠曼!B△￡至ABSTRACTImagesegmentationplaysanimportantroleindigitalimageprocessingandcomputervision．ImageSegmentationbasedongraphtheoryisaprevalentresearchtopicinrecentlyinternationalimagesegmentationarea．Itsbasicideaistomappin