基于normalized cut的图像分割及其cuda并行实现

《基于normalized cut的图像分割及其cuda并行实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、支妻未交硕士学位论文基于NormalizedCut的图像分割及其CUDA并行实现ImageSegmentationBasedOnNormalizedCutandCUDAParallelImplementation作者：黄先楼导师：于双元北京交通大学2014年3月学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定．特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅．同意学校向国家有关部门或机构送交论文的复

2、印件和磁盘。(保密的学位论文在解密后适用本授权说明)学位论文作者签名：音：气楼签字日期：,201弘年：；月心日导师虢彳羽5D签字目期：沙l￥年、月i日中图分类号：TP391，41UDC：004．93学校代码：10004密级：公开北京交通大学硕士学位论文基于NormalizedCut的图像分割及其CUDA并行实现ImageSegmentationBasedOnNormalizedCutandCUDAParallelImplementation作者姓名：黄先楼导师姓名：于双元学位类别：工学学号：11120444职称：副教授学位级别

3、：硕士学科专业：计算机科学与技术研究方向：分布式计算北京交通大学北尿父迥大字2014年3月致谢本论文的工作是在我的导师于双元副教授的悉心指导下完成的，于双元副教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响．在此衷心感谢三年来于双元老师对我的关心和指导．在交大学习和撰写论文期间，杨永向、李晔、刘雅坤和郭涛等同学对我学习和论文的研究工作给予了热情帮助，在此向他们表达我的感激之情．另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业．jE塞交道态堂亟±堂焦论塞擅蔓摘要图像分割是图像处理和分析中的重要过程，它的

4、输出结果直接影响着后续的处理效果．基于图论的图像分割算法由于有比较完备的数学理论基础，最近获得了广泛研究．NormalizedCut是一种平衡的基于图论的图像分割方法，不仅拥有其它图论图像分割算法的优点，并且解决了Min．Cut算法倾向于分割孤立结点的问题．然而，NormalizedCut存在计算复杂度高，分割速度慢等问题．针对该问题，本论文研究利用CUDA并行计算平台对NormalizedCut图像分割算法进行加速，提高算法在实际应用的执行速度．主要研究内容有：(1)介绍传统的NormalizedCut图像分割算法，目的是挖

5、掘可以进行并行化的过程，研究并行化算法替代耗时的串行执行过程．(2)在将图像映射为相似度矩阵时，论文利用任意两像素点之间的权值与其它像素点无关的特点，启动多个平行线程，每一个线程负责计算两像素点间的权值，这种方法加速相似矩阵计算．(3)利用并行规约算法替代传统的数组求和，设计一种高速并行矩阵乘法替代串行的矩阵乘法，由于数组求和和矩阵乘法在NormalizedCut算法中出现频率高，提高这两种算法的执行性能会显著地提高整体算法的效率．(4)在求解矩阵特征值阶段，论文改进了传统的二分法(Bisection)，使其平行地计算同层区间

6、结点的子区间结点，求解矩阵特征值是整个算法较耗时的过程之一，并行化求解矩阵特征值会对提高整体算法的性能有重要意义．(5)实验结果证实了NormalizedCut并行算法不仅能正确分割图像，而且在性能方面获得了2．34倍的加速．关键词：图像分割：图割；NormalizedCut；CUDA；并行计算分类号：TP391．41IE塞銮逗太堂亟±堂僮途童△垦曼I＆△￡IABSTRACTImagesegmentationisallimportantprocessinimageprocessingandanalysis，whoseoutpu

7、tresultdirectlyaffectsthesubsequentprocessing．Withrelativelycompletetheoryofmathematics，graphbasedimagesegmentationalgorithmisbeingextensivelyresearched．NormalizedCutisoneofbalancingalgorithmsofgraphbasedimagesegmentation，notonlydoesithasalladvantagesofgraphbasedima

8、gesegmentationalgorithm，butalsosolvethedrawbacksthatMin—cutfavorscuttingsmallsetsofisolatednodes．However，thereisahighcomputationalcomplexi