摘要本文介绍一种基于图模型的图像分割方法。该方法以成对区域对比准则作为边界依据，在两个区域之间有较低权值时将两个区域合并。算法使用贪心策略，但可以得到符合需求的全局特征。我们利用一种通过排列和路径压缩的并查集森林来实现该算法。算法有着可以在忽略高变化区域细节特征的同时保留低变化区域的细节特征的重要性。它以O(m log m)的时间复杂度运行，m为图中边的条数，并且在实践中的也得到了预期的快速并准确的效果。最后，本文讨论了该算法在道路场景中的应用。64196

毕业论文关键词：图像分割，道路场景理解，聚类，感知组织，图论算法

毕业设计说明书（论文）外文摘要

Title    Graph-Based Image Segmentation                  

Abstract This paper will introduce a method for image segmentation based on graph. This method evaluate where there is evidence for a boundary between two components in a segmentation by the pair-wise region comparison and it will merge two regions even if there is a single low weight edge between them.. Although this algorithm makes greedy decisions it produces segmentations that satisfy global properties. Our implementation maintains the segmentation using a disjoint-set forest with union by rank and path compression. Algorithm has an important characteristic of the method that is its ability to preserve detail in low-variability image regions while ignoring detail in high-variability regions and it runs in O(m log m)

time for m graph edges. Algorithm in practice is expected to quickly and accurately to effect. Finally, the paper discusses the application of the algorithm in the road-scene.

Keywords : image segmentation, road-scene understanding, clustering, perceptual organization, graph algorithm

目 录

1 绪论 1

1.1 论文选题依据 1

1.2 图像分割的定义 1

1.3 图像分割技术分类 2

1.4 图模型的建立 2

1.5 聚类和区域合并技术 3

1.6 本文的主要内容安排 3

2. 基于图模型的图像分割 4

2.1 目标 4

2.2  成对区域对比法 4

2.3  算法 5

2.4  算法的特点 6

2.5  算法的实现 6

2.5.1   图像的读取、存储和表示 6

2.5.2   高斯平滑 7

2.5.3   图模型的建立 8

2.5.4   并查集 9

2.5.5   区域合并 10

2.6  算法复杂度分析 11

3. 基于图模型的图像分割实验结果的分析 11

4. 对道路场景的分割 16

结  论 21

致  谢