基于图论的图像分割算法分析-控制理论与控制工程专业论文.docxVIP

Research of Image Segmentation Algorithms based on Graph Theory A Thesis Submitted to Chongqing University in Partial Fulfillment of the Requirement for the Degree of Master of Engineering By Tian Shasha Supervised by Prof. He Zhongshi Major: Computer Software and Theory College of Computer Science of Chongqing University,Chongqing, China April, 2011 重庆大学硕士学位论文中文摘要 重庆大学硕士学位论文 中文摘要 I I 摘 要 图像分割是指将一幅图像分成各具特性的区域并提取出目标的技术和过程， 它在不同的应用领域中有着不同的称谓，是图像处理过程中的关键技术之一，同 时也是一个难题。图像分割将图像中有意义的特征部分提取出来，是进一步进行 图像识别、分析和理解的基础。 到目前为止，已有很多种图像分割方法，但是还没有一种普遍适用于各种图 像的有效方法。图像分割的实现可以分为三个阶段：图像预处理阶段、核心算法 实现阶段、后期处理阶段。图论方法在聚类优化问题中应用研究开始于 20 世纪 60 年代前后，该方法在图像处理与分析方面的应用开始于 20 世纪 80 年代以后。本 文主要是对基于图论的图像分割方法进行研究。本文的主要工作如下： ① 介绍了图像分割的研究现状以及基于图论的图像分割研究现状。同时还简 单介绍了图及其相关的概念，并介绍了近一二十年出现的常用的图分割算法。还 介绍了图分割和图像分割的关系。 ② 提出了一种基于分水岭和等周的分割算法 FWTI（First Watershed Then Isoperimetric）。FWTI 算法是一种结合了分水岭算法和等周算法两种方法的算法， 该算法先用分水岭算法对图像进行初始分割，然后再以分水岭分割后的小区域为 节点构造图，进而再用等周算法在区域间对图像进一步分割。FWTI 算法中，自动 选择基点，是一种全自动的分割技术。实验结果表明，FWTI 算法不仅有利于克服 分水岭算法的过分割问题，相对于原等周算法还提高了分割速率。 ③ 提出了一种融合块结构的等周分割算法。该算法在对图像进行构造图之 前，先对原图像构造块，然后再以这些块区域为节点构造图，进而再用等周算法 对图像进行分割。全自动分割方法无法自动识别图像中的目标区域，本文中通过 人为选择基点来标记前景，进而通过半自动方法完成对目标区域的分割。该算法 是一种半自动分割技术。实验结果表明，块结构的使用可以减少图中的节点数和 边数，所以相对于原等周算法提高了分割速率。 关键词:图论，图像分割，等周算法，分水岭算法，块结构 重庆大学硕士学位论文英文摘要 重庆大学硕士学位论文 英文摘要 II II ABSTRACT Image segmentation is a technology and process that segments the image into regions with different characteristics. It has different names in different areas. It is a key technology in the image processing and also a problem. It can extract the meaningful parts of the image and it is the foundation of further recognition, analysis and understanding of the image. Up to now, there are lots of image segmentation methods, but still not a method for all kinds of images. The implementation of image segmentation can be divided into three stages: image preprocessing stage, the core algorithm stage, and the post-processing stage. Clustering optimization based on graph theory can trace back to the 1960s,