基于分水岭技术的图像分割算法实现本科学位论文.doc

毕业论文

基于分水岭技术的图像分割算法实现

学生姓名： 马越 学号： 122022328
系 部： 电子工程系
专 业： 电子信息工程
指导教师： 谭艳丽（讲师）

2016年 6 月

诚信声明
本人郑重声明：
所呈交的毕业论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。

本人签名： 年 月 日

毕业设计（论文）任务书
设计（论文）题目： 基于分水岭技术的图像分割算法实现
系部： 电子工程系 专业： 电子信息工程 学号： 122022328
学生： 马越 指导教师（含职称）：谭艳丽（讲师）专业负责人： 张晓娟

1．课题意义及目标
图像分割是图像处理领域中极为重要的领域，是实现图像分析与理解的基础。图像分割，就是按照一定的原则，将一副图像或景物分为若干个互不相交的小区域，即是产生图像基元的过程。

2．主要任务
（1）图像分割原理。
（2）基于分水岭变换的图像分割算法。
（3）基于分水岭变换的图像分割算法与传统分割算法的比较。

3．主要参考文献
[1]陈婷婷.采用模糊形态学和分水岭算法的图像分割研究[D],西南大学,2008.
[2]徐伟,王希常,郑志宽.一种基于改进分水岭算法的图像分割算法[J]．计算机技术与发展,2008,18(12):38—40．
[3]罗勇.改进后的分水岭算法在图象分割中的应用研究[D].哈尔滨:哈尔滨工业大学,2003．

4．进度安排

设计（论文）各阶段名称
起 止 日 期
1
阅读文献，提出方案，完成开题报告

告。

2016年2月29日~4月09日

2
图像分割原理以及分水岭变换算法的学习
2016年4月10日~4月23日

3
将分水岭变换应用于图像分割源代码的实现
2016年4月24日~5月14日

4
程序调试阶段
2016年5月15日~6月04日

5
进一步完善，撰写论文
2016年6月05日~6月25日

太原工业学院毕业设计

基于分水岭技术的图像分割算法实现
摘 要
图像分割是图像处理中一项极为关键的图片处理方式。近年来，提出了一些特定原理、方式与工具相结合的分割方法，其中基于形态学的分割算法是目前使用较为广泛的算法之一。此论文主要采用基于分水岭技术的图像分割算法技术，主要是先将原始图像进行对物体边缘的检测来得到梯度幅值图像，然后对梯度幅值图像进行前景标注和背景标注，再用分水岭算法对梯度幅值图像进行分割。再进行图像分析，从而达到分割图像的效果和目的。
关键词: 分水岭，图像分割，形态学

Image segmentation based on watershed transform
Abstract
Image segmentation is the image processing in an extremely critical image processing method. In recent years, this paper puts forward some specific segmentation method of combining theory, methods and tools, which is based on morphological segmentation algorithm is one of the more widely used algorithm. This paper mainly USES the technology of image segmentation based on watershed algorithm, mainly first of objects on the edge of the original image to get the gradient image, and then to the foreground and background markers of the gradient image, then the watershed algorithm is applied to gradient image segmentation. For image analysis, so as to achieve the effect and purpose of image segmentation.
Key words: watershed， image segmentation，morphology

目 录
第1章 绪 论 1
1.1 课题意义与背景 1
1.2 国内外研究现状 2
1.2.1 数学形态学与图像处理研究现状 2
1.2.2 分水岭算法与图像分割的研究现状 2
第2章 图像分割算法的概述 4
2.1 图像分割的概念 4
2.2 图像分割方法介绍 4
2.2.1 基于区域的分割 4
2.2.2基于阈值的分割 5
2.2.3 基于边缘检测的分割 6
2.2.4 基于聚类分析的图像分割 9
2.2.5基于区域标记与轮廓跟踪的分割 11
2.2.6 基于几何形变模型的分割 13
第3章 分水岭图像分割算法 18
3.1分水岭算法原理 18
3.2分水岭算法特征 19
3.3梯度图像获取 19
3.3.1 图像梯度的概念和定义 19
3.3.2 图像梯度的处理方法 20
第4章 分水岭算法实现与实验分析 22
4.1 分水岭算法实现顺序 22
4.2 分水岭算法实现 22
第5章 总 结 38
参考文献 39
致 谢 40

III

第1章 绪 论
1.1 课题意义与背景
  人类可以通过听觉、嗅觉、触觉、味觉、视觉获取外界信息，它们在人类感受外界信息的过程中各自占据举足轻重的地位。尤其是眼睛所感受到的视觉，视觉的范畴特别广，它不单单仅是可以看到的自然景观，还有人眼所看不到的宏观、微观影像以及大批量的由计算机生成的图像。在21世纪，随着人类社会的进步与科技的发展，信息化时代早已到来。在这么多信息当中如何筛选有用信息，并对信息进行处理是当前人们关注的方向。视觉是我们感觉中高级的感知之一，对外部世界的人类感知的两种方式是听力和视力，尤其是视觉，因为图像信息是一个非常重要的实物资料。因此，图像在人类感知中起着最重要的作用并不奇怪。信息的种类很多，人类在日常生活中所能接触到的最多的信息就是图像信息。图像在人类的信息活动中占据着举足轻重的作用，它在获取信息的同时可以表达信息也可以传递信息等。由于图像有形象生动、直观具体、容易理解等特点，所以在很多领域都起着重要的作用，如：信息科学、计算机科学、天体气象、通信工程、航空航天、医疗、军事、教育等诸多领域中都有涉略[1]。
在数字图像处理中，图像分割是一项重要的技术，也是一个较为重复的的难题，发展至今仍没有找到一个一般（全面）的方法，也没有找到一个可以预见分割算法难易的标准。图像分割就是把图像分成若干个特定的、具有特殊性质的区域并提出感兴趣目标的技术和过程。近年来，随着各科学新理论和新方法的提出，人们也提出了一些特定原理、方式和工具相联结的分割方式，其中基于形态学得分割算法是目前使用较为广泛的算法之一。
图像有许多的多变性，大部分的分割的过程无法依赖pc单独完成，但是手工分割的工作量大的惊人，而且对于修改非常困难，所以，有些人提出了人工和pc相互自动接合定位的方法，并结合各自的优点，来实现对目标轮廓的快速定位。相信这些交互方式的应用，一定可以推动图像目标分割与图像抽取的发展，也会成为一个具有活力且独特的研究领地[2]。
基于标记的分水岭算法是一个经典的图像分割的方法，它因为快捷，高效，精准的分割结果得到人们的注视。分水岭算法操作简单，精确度高，但由于分水岭算法对图像中的噪声弱边缘有一定的影响，表面细微灰度变化，会产生过分割现象。
分水岭分割方式是基于拓扑理论分割的方法，其基本思维看作是对大地测量拓扑风景的图像，在图像像素的灰度值的各点表示的是该点的高，每个局部的边界最小值和其影响区域称为集水盆，并且形成分水岭集水盆。分水岭的概念的形成可以通过模拟浸渍处理进行说明。
对外部世界的人类感知的两种方式是听力和视力，尤其是视觉，因为图像信息是一个非常重要的实物资料。人在探索和图像的使用时，经常对图像的某些部分产生影响，这些目标通常占有一定区域，在图像周围有一定的特征的差异。这些差异可能是非常明显的特征，可以是非常微妙的，这样，人眼不会感觉到它。随着计算机图像处理技术的发展，使得能够通过计算机来访问和处理图像信息[3]。
1.2 国内外研究现状
1.2.1 数学形态学与图像处理研究现状
数学形态学(Mathematical Morphology)产生于1964年，是由法国巴黎矿业学院博士生赛拉(J. Serra)和导师马瑟荣，在从事铁矿核的岩石学分析及预测其开采价值的研究中提出“击中和没击中变换”的理论，并在理论层面上第一次引入了形态学的表达式，建立了颗粒分析方法。他们的工作奠定了这门学科的理论基础，如击中和没击中变换、开和闭的运算、布尔的模型及纹理分析器的原型等。
数字图像处理最早应用于报纸行业。早在二十世纪二十年代早期，巴特兰电缆图像传输系统通过海底传输穿过大西洋，在纽约和伦敦之间传输图像，他将传输时间从1周减少至3h.用计算机成功处理数字图像最早可追溯到20世纪60年代早期，一九六四年美国著名实验室对航天探测器发回的几千张月球照片使用了图像处理技术，如灰度转换、修除噪音等方法进行修正。与此同时，20世纪六十年代后期至七十年代早期，数字图像处理开始应用于医学图片、遥感大地、天文学等方面。
从60年代后期开始到现在，图像处理技术蓬勃发展并得到广泛应用。在工业、医药、生物科学等领域，用对比度增强和伪彩色增强技术来提高视觉效果。从七十年代中期开始，随着pc技术和人工智能的快速发展，数字图像处理向更高层次去发展。随着计算机性能不断提高，通信技术不断发展，这极大地推动了图像处理系统的应用。
1.2.2 分水岭算法与图像分割的研究现状
图像分割是将图像划分成或分割为具有相似特征的区域。图像分割最基本的特征是：单色照片图像的亮度幅度和彩色图像的彩色分量。图像的边缘和纹理也是对分割法很有用的特征。
目前，还没有一个模制的图像分割的理论。因此，图像分割没有标准方法。然而，一些具体的方法，已被广泛使用。因为这些方法都有一个特定的范围，因此它们实际使用的范围是有限的。“考虑灰度色调或纹理特效，一个图像分割的区域对于这些特征应该均匀一致。区域内部特征是简单的，没有空洞的。每一个分段的边缘都应该是圆润无瑕疵的，并且必须精准”[4]。
分水岭算法（Watershed Segmentation）是近年流行起来的一种基于数学形态学的图像分割方式，主要可以应用于图像分割，梯度图片的抽取等。分水岭分割算法把地形学和天文学的思想引入到图像分割中，特别适合相邻区域的分割。灰度图像可以看做是一片地形，像素的灰度值代表该点的地形高度，在地形中有高地、分水线和集水盆地等地貌特征。地形表面上总会有一些局部极小值，又称为低洼，落在这些点的雨水不会流向他处。在一些点上，降落的雨水会沿着地面往低处流，最终流向同一个低洼，把这些点称为与该低洼相关的积水盆地。在另一些点上，降落的雨水可能会等可能地流向不同的低处，将这些点称为分水线。

第2章 图像分割算法的概述
2.1 图像分割的概念
图像分割就是把图像分成若干个特定的、具有独特性质的区域并提出感兴趣目标的技术和过程。这里的特征是指图像可以被用作属性标记，他可以分为图像和图形视觉特征两类统计特性。图像的统计特性是指一些人为特征的定义时，他可通过转化，如图像直方图，频谱和其它聚合获得的图像。图形的视觉特性指的是人的视觉的自然特性可以直接感受到，如亮度区域，纹理。图像分割是图像分析的关键步骤，是图像的进一步理解的基础。虽然大量的图像分割方法已经被提出，但大多是针对特定问题的，并不适合所有常见的图像分割算法。
图像分割是一项在图像分析中占据重要地位的技术。在对图像的探索和运用中，人们往往会对图像中的某些部分产生兴趣，这部分称为前景，他们一般对应于图像中较为特有的、具有特有性质的区域。这里的独特性可以是像素的灰度值、物体轮廓曲线等。为了能够识别出和并解析到图像中的目标，需要将他们从图像中分割抽取出来，在此基础上才有可能进一步对目标进行度量和对图片进行利用。
图像分割方法主要有基于区域的分割，基于阈值的分割，基于聚类分析的分割，基于模糊集理论分割图像分割方法等。
2.2 图像分割方法介绍
2.2.1 基于区域的分割
(1)区域生长：
其方法是对生长具有类似特性共同构成该区域的像素，先找到一个种子像素为起点的每个区域的成长进行划分，然后将种子像素和种子像素附近具有相同或相似性质的区域的种子像素合并。这些新的像素作为新的种子像素继续上述内容，相邻像素被接受，直到停止生长[5]。
区域生长实现过程，需要选择出一组能够正确代表区域的种子像素，确定好在生长过程中的相同或者相似性准则，其中相似或者相同准则可以使灰度，彩色、梯度等特性。再指定一个让生长停止的准则条件。所选取出来的像素可以是单个像素，也可以是包含若干个像素的小区域。根据不同的原则来指定不同的生长准则，使用不同的生长准则，在生长的过程中会受到生长准则的影响。区域生长的主要优势是运算容易便捷，在对较匀称的连通区域有很好的分割效果。只不过他的缺点是需要人工地去确定种子像素，对噪音相当敏感，也会导致区域目标中出现常见的问题[6]。
(2)分裂合并法：
图像四叉树：
如果整个图像划分成大小相等的四方形的象限，然后新的区域被进一步划分成四个相等的尺寸更小的象限，不断继续分割下来，得到根部的图像，则新区域被划分成更小的区域或中间节点或叶节点四叉树。
分裂合并分割法：
大致步骤如下：
①将图像R分成4个大小相同的想先区域Ri, i = 1,2,3,4.
②对于任何的Ri，如果P(Ri)=false,则将该Ri再进一步分拆成四个更小的象限区域。
③如果此时存在任意相邻的两个区域Ri和Rk使得P(Rj∪Rk) = true成立，就将Rj和Rk进行合并。
④当无法再进行聚合或拆分时操作停止。
2.2.2基于阈值的分割
阈值分割是一种区域分割技术，他对物体与背景有较强对比，对景物的分割特别有用，因为其简单直接、易于实现，而在图像分割中占具有重要的位置。然而怎样进行阈值选择却是一个难问题，因为在数字化的图像处理中，没用的背景数据和对象物的数据通常会混乱在一起。除此之外，在图像中还有各种噪声。所以必须根据图像的统计特性，即从概率的角度选择合适的阈值。如果图像目标与背景相对应的两个单峰比较接近、方差较小且均值相差较大，则该图像的直方图具有双峰性质。阈值化常可以有效分割具有双峰性质的图像。
灰色阈值分割法是最常用的技术的并行区域，它是图像分割最广泛使用的类别的数目。阈值分割方法实际上是输入图像到输出图像G + F如下转换：
（2-1）
其中，T为阈值，物体的图像元素g(i, j)，背景的图像g(i, j)，可以看出来，阈值的分割算法主要是确定阈值，主要能确定一个合适的阈值就能准确的把图像分割开来。确定了阈值以后，把阈值和像素点的灰度值比较在和像素分割可对各像素并行地进行，分割所得出的结论是直接给出图片的区域。计算简单，运算效率快，这是阈值分割的主要优点。在重视运算效率的场合，它得了广泛的应用。阈值有很多种处理技术，有全局阈值，最佳阈值，自适应阈值等[7]。
利用该系统区域灰度的图像分割方法时，通常认为具有灰度对象和背景的单峰组成分布某个图像，在目标上的相邻像素之间的内部或背景灰度值是高度相关的，但在交界处对象的两侧和背景像素处的灰度值有很大不同。如果上述条件的图像感到满意，那么他就可以被认为是一个基本的直方图对应于目标和背景混合组成两个单峰直方图。
2.2.3 基于边缘检测的分割
确定图像中的对象的边界的另一种方法是在第一次直接检测的每个像素及其周围的状态，它已决定改变该像素是否是物体的边界上。具有所需特性的像素被标记为边缘点。当每个像素的灰度图像用于反映与边缘像素的要求的每个像素的程度，这个图象被称为边缘图像或边缘图。他只能代表未经二进制图像的强度来代表的程度的边缘点的位置。边缘方向，而不是幅度编码被称为含方向的图像边缘图。
边缘图通常是边缘点勾画的所有对象的轮廓，但很少形成边界分割。因此，我们需要另一个步骤即可完成检测过程的对象。
Roberts边缘算子
(2-2)
+ }½
其中f(x, y)是具有整数像素坐标的输入图片。
Sobel边缘算子
下图所示的两个卷积和形成了Sobel算子。图片中的每个pixel点都用这两个核做卷积运算。一个核对垂直边界响应最大，但另外一个对水平边界响应最大。两个卷积运算得到的较大值作为该点的输出值。运算结果是一副边界梯度幅度图像。
-1
-2
-1
0
0
0
1
2
1

-1
0
1
-2
0
2
-1
0
1

图2.1 Sobel 边缘算子
Prewitt 边缘算子
下图的两个卷积和组成了Prewitt边缘算子。与使用Sobel算子方式是的相同的，图像中的每个点都用这两个和进行卷积运算，取较大值作为输出值。Prewitt算子也产生一幅边界梯度幅度图片。
-1
-1
-1
0
0
0
1
1
1

1
0
-1
1
0
-1
1
0
-1

图2.2 Prewitt 边缘算子
Kisch 边缘算子
Kisch边缘算子由8个卷积和组成。图片中的每个点都用到了八个掩模进行卷积，每个掩模都可以对某个比较特定的边界方向作出了极大反响。全部的八个方向中的最大值作为边界梯度幅度图像的输出值。

+5
+5
+5
-3
0
-3
-3
-3
-3

-3
+5
+5
-3
0
+5
-3
-3
-3

-3
-3
+5
-3
0
+5
-3
-3
+5

-3
-3
-3
-3
0
+5
-3
+5
+5

-3
-3
-3
-3
0
-3
+5
+5
+5

-3
-3
-3
+5
0
-3
+5
+5
-3

+5
-3
-3
+5
0
-3
+5
-3
-3

+5
+5
-3
+5
0
-3
-3
-3
-3

图2.3 Kirsch边缘算子
Canny 边缘算子：
Canny边缘检测算子是一种很常见的和有限的操作者[8]。 Canny算子是第一灰度图像平滑均匀方差高斯滤波器，然后将滤波图像的每个像素计算梯度大小和梯度方向。用于改进的边缘梯度的方向，如果在梯度方向不超过两个相邻点的梯度大小的当前象素的梯度幅值下，对应的像素会被抑制，使边缘细化，这种方法成为一个非最大抑制。该方法也可与其它的边缘检测算子来优化的边缘相结合。为了促进这一过程中，需要量化梯度方向的8邻域的方向。
Canny算子使用两个振幅的阈值，用于检测边缘梯度大小，低阈值一般取为一半的高阈值。边缘变薄后，开始跟踪具有高门槛轮廓。最后，为了满足起动顺序连续追踪轮廓段，弱门槛的连接边缘强于高门槛边缘像素。
2.2.4 基于聚类分析的图像分割
聚类分割是把给出的样本集合x = {x1, x2, …,xn}按照某一规则分成k个互不相交子集。每个子集中的样本之间相似性较大，不同子集样本之间的相似性较小。采用聚类方法分割图像，不需要训练样本。是一种无监督的统计方法，他通过迭代的知性分类算法来提取各类的特征值，从而达到分割的目的。本聚类方法主要介绍三种，即K_均值、模糊C均值和Mean-Shift等聚类算法。
K_均值聚类：
在一般情况下，聚类算法具有以下三个要素：
(1)选择了一些距离度量来衡量样本之间的相似性;
(2)确定一个聚类结果的质量评价标准功能;
(3)给出一个初步的分类，然后找到准则函数的极值是最好的聚类迭代算法 。
K_均值算法可归纳为如下步骤：
(1)选取某一方式把n个样本分成c个聚类的划分，计算每个聚类的均值u1,u2…un和Jc；
(2)选择一个备选样本x，设其在Xi中；
(3)若Ni = 1,则转至步骤2，否则继续。
(4)计算。
(2-3)
(5)对于所有的j, 若Pk < Pj,则将x从Xi移到Xk中；
(6)重新计算Ui和Uk的值，并修改J；
(7)若连续迭代N次（即所有样本都运算过）Jc不变，则停止，否则转到步骤2.
模糊C均值聚类：
K_均值算法也叫C_均值算法，他是误差平方和准则下的聚类算法，他把每个样本严格的划分到某一类，属于硬划分的范畴。实际上，样本并没有严格的属性，他们在形态上和类属性存在中介性，为了解决这一问题，研究者将模糊理论引入K_均值算法。
将问题的有关符号重新规定如下：{xi, i = 1, 2,…,n}是n个样本组成的样本集合，c是类别的预定数量，用户界面，I =1,2，...，C为中心每个群集，μJ（ⅹⅰ）是第j个类别成员函数的第i个样本。与隶属函数定义的簇损失函数可以写成:
(2-4)
其中，b>1是一个可以控制聚类结果的隶属成都的常数。
算法的步骤如下:
(1)设定聚类数目c和参数b;
(2)初始化各个聚类中心vi;
(3)循环下面的运算法则，一直到各个样本的隶属度值平稳为止:
①用当前的聚类中心根据式计算隶属度函数;
②用当前的隶属度函数update各聚类中心。
Mean-shift聚类分割：
Mean-shift算法是一种核密度估计方法，用来分析复杂多模特征空间，确定特征聚类的非参数密度估计，被广泛采用与图像处理和视觉任务中[9]。
Mean-shift算法寻找密度最大的过程总结如下：
步骤一：计算Mean-shift向量
步骤二：如果||||<，则表示Mean-shift “爬”到局部的概率密度最大值处，算法终止，否则执行步骤三；
步骤三：将新的质心+x为中心点赋予x，以新的x所在的窗口为当前窗口，执行步骤一。
而Mean-shift算法滤波的步骤为如下所述:
步骤一：对每个像素, 初始化为起始步，令j=1,;
步骤二：计算，直到收敛于
步骤三:滤波后的像素赋值为Zi = ().
上述s和r分别表示滤波结果的空间域和颜色域，即滤波后处像素的值收敛于 的像素值。在空间-颜色联合域中，Mean-shift向密度最大的方向运动。
2.2.5基于区域标记与轮廓跟踪的分割
区域标记：
图像分割结果通常是二进制图像，所有的目标区域被赋予相同的灰度值。如果图像有多个目标区域的，要被分析的是每个目标和的大小，形状和其他特征，并且应该被标记区域来区分。区域的标记是指在分配了相同的符号，不同的连通区域给予不同的标签图像同一连接域的所有像素。有标两种常见的方面：递归标记，序贯标记。
递归标记：
递归标记算法如下：
(1)从左至右，从上到下，逐行扫描图像行，找到目标点无人盯防的P，分配到一个新的标签的地步。
(2)递归赋予相同标记，将目标像素点p的附近
(3)相互连接，直到所有的像素标记完成后，中国联通的组件将被标有相同的商标。
(4)重复步骤2，3，找到目标点没有打上递归相同的标记分配到目标点的另一个附近。如果你不能找到目标点没有标记，标记区域已完成。
串行机器上的递归标记算法的运行速度非常耗时，适合处理的并行机上[10]。
序贯标记：
8连通区域的序贯标记算法如下：
(1)从左至右，从上到下扫描图像，找到目标点P未标记；
(2)如果左点P，左上，右上，右上附近四个背景点，给定一个新的标记像素P;如果四个相邻点，两个不同的标号，这使分配给当前像素一个代码，并且这些包括一根两米等价的表，它们是相等的。
(3)在第二扫描图像，每个表和修改最小标记为他的等效表。
(4)顺序连接的区域标记算法与8连通的为同一区域，但在第二步判定仅在上边一点与相邻点的左边。
顺序标记算法通常需要两个扫描图像，因为该算法是仅有的两个图像的操作线，一旦这样，当图像被作为一个文件存储和存储器空间不允许整个图像加载所有，也可以在使用算法。他目标区域图像是非常不规则的，这将导致巨大的等价表。
轮廓提取：
      轮廓提取和轮廓跟踪的目的是获得外部轮廓特征的目标区域形状分析与识别对象的准备。
      二进制图象轮廓抽取算法非常简单，即挖空目的区域的内部点，假设目标像素的图像是白色的，背景的像素是黑色的，如果在图像中的象素是黑的，并且他的八个相邻的黑色点，表明内部点点，否则边界点。内部点的像素值，以确定背景颜色的所有内部点时，执行操作完成所提取的图像的像素分布。
轮廓跟踪：
可以基于4连通方向码和8连通方向码分别跟踪出4联通的轮廓和8联通的轮廓。但对于大多数区域，不一定存在垄断的4联通轮廓，会导致基于4个方向码的轮廓失败。假设要处理的是一个二值图像，图像只有一个目标区域联通，则轮廓跟踪算法如下：搜索方向被定义为一个可变目录，用于搜索方向代码记录为邻接从正在使用的点边界的下一个边界点的电流搜索。
步骤二：最后搜寻到的边缘点作为当前边缘点，在其附近3×3，并且他的初始搜寻方向搜寻新边缘点在逆时针方向上设置如下：
基于以下四个方向的轮廓上，使得Direction=(Direction+4.0) mod 5.0，将上一个边缘点到当前边缘点的搜寻方向按照顺时针方向旋转1个方向；
基于以下八个方向的轮廓上，若上一次搜寻到边缘点的方向为odd，则使Direction=（Direction+7.0）mod 9.0, 将上一次的搜寻方向按照顺时针旋转2个方向；若Direction为even，则使得Direction=（Direction+8.0）mod 10.0,将上一次的搜寻方向按照顺时针旋转1个方向。
步骤三：如果搜索是第一个边缘点到边缘点B，然后停止搜索，跟踪到底，否则，重复步骤而继续搜寻。
其次是搜索到的边界点序列构成被跟踪的边界。第一步有一个“检测标准”，其作用是找到第一个边界点所通过的指导方针;步骤二使用的“跟踪指导方针”，其作用是找到所有的边界点的两个条件。
2.2.6 基于几何形变模型的分割
图像处理领域有两类主要的形变模型，参数活动模型和几何形变模型。前面提到的Snake模型是参数活动模型的代表，该类模型不能自动处理轮廓线的拓扑变化，对于结构较为多样的图片需要活动轮廓模型可以自行改为拓扑结构，但参数活动轮廓模型却不易满足这种需求，这一缺点也严重束缚了他在图像分割中的应用。
几何形变模型由Caselles和Malladi分别独立提出，他是以曲线演变原理和水平集方式为基础的。几何形变模型的轮廓线有水平集函数的零水平集来表示，模型通过update水平集函数达到是轮廓线运动的目的，即使轮廓线发生了分裂与合并等变化，水平集函数仍然是一个有用的数学函数。与参数活动轮廓模型相比，几何形变模型具有自动处理轮廓线拓扑变化的优势，可以同时分割多个目标，并分割具有复杂结构的目标。因而，已被广泛的应用于实际的图像处理系统中，尤其是医学图像处理系统。
水平集方法及其数值实现：
(1)水平集方法原理：
(2-6)
其中，d((x,y),C(s,t))表示坐标(x,y)到曲线C(s,t)的距离。
给定一个水平集函数(x,y,t)，用其零水平及来表示演化曲线C(s,t)，则有: (C(s,t),t) = 0; (2-7)
对上式t求导，利用全微分原理，可以得到:
(2-8)
根据上式，在零水平集的内部是负的，在外部是正的，则曲线C的内向单位法向量N可以通过下式计算:
(2-9)
将曲线的演变函数及内向单位法向量n的计算迭代式子带入(2-7)式中，可以得到:
(2-10)
将式子（2-10）进一步改写，则得到与曲线演化方程相对应的水平集方程:
(2-11)
这样，给出的轮廓曲线的偏微分方程及轮廓曲线出是时刻的水平集函数,可以保证水平集函数随时间的运动满足(C(s,t),t) = 0的条件，即的零水平集始终是轮廓曲线方程, 则(2-11)式称为轮廓曲线方程的欧式表达，是一种Hasmildeton-Jacoasbi类型的偏微分方程。
(2)水平集方法的数值实现:
在图像分割应用中，水平集方程中的速度项V通常包含以下三种形式的速度，即:
V = (2-12)
其中 = 表示常值速度；表示曲率速度； 表示水平速度，这里和a即可以表示常值，也可以表示函数，U=(u，v)表示一个向量场。将（2-12）、（2-9）带入（2-11），可以得到一个“完整”的应用与图像分割的水平集方程:
(2-13)
由于水平基函数在运动过程中始终保持为一个函数，因此，可以用离散网络来表达水平集函数。设图像离散网络的间隔为h，离散后I(x,y)的大小为M*N像素，节点ij中的i{1,2,…,M}, j。Δt为时间间隔，并设在n时刻节点ij处的水平基函数为,则方程可以离散化为：
(2-14)
其中，表示n时刻速度函数为与网络点ij处的值。采用逆向有限差分法，可得到最终的离散化形式为：

(2-15)

其中分别由下列式子计算:
(2-16)
(2-17)
(2-18)
(2-19)
(2-20)
经差分方程，可以应用迭代的方式来不断update水平基函数，抽取update后水平集函数的零水平集，即可获得update后的轮廓曲线图像。轮廓曲线的曲率可以运用中值差分的算法来进行数值的运算，即令h=1,用和来近似。而单位内法向量可以按照下式计算[11]：
+
(2-21)
然后
(2-22)
(2-23)
上式的含义是每次迭代时，令水平及移动范围不能超过一个网络宽度。
水平集算法的快速实现
窄带法最初由Choop提出，Adalstasdeinsson和Sethsdian给出了细致的实现思想。基本想法是只update与零水平及周围很狭小的一个带状区域水平集函数的值。阴影边界内部的轮廓曲线是目前的零水平集，外面的曲线是窄带外边缘点，里面的曲线是内部边缘点，update水平集方程的时候，只对带状阴影内部的点update。
当前零水平集由于窄带宽度一般比较狭小，窄带内需要update的激活点较少，update水平基方程的工作量即将减少。但是，窄带法存在的漏洞是经过几次循环后，零水平集的position会超出窄带的范畴，因而，需要经常update窄带状水平集函数，update的项目主要有update窄带的内外边界点，以保持窄带的有效范畴；重新初始化水平集方程，使得保持为符号距离方程。update的方式和窄带的宽度是相关的，如果窄带宽度很窄，一次循环后，零水平集就有可能超出窄带范畴，则需要每次update，这将增加工作程度；如果窄带的宽度很宽的话，则需要update的窄带内网格点比较多，工作程度量也增加，比较合适的窄带宽度2a=11~17(网格点间距和采样点间距)。下面是窄带法update水平集函数的基本流程。
步骤1：构造窄带。
由初始化轮廓曲线产生窄带内的符号距离方程，将窄带内所有点记为激活点。
标记窄带的边界点。
将远离窄带得点标记为远点，并对d0以外的远处的点给出较大的正SDF值，对d0内部的原点给出了较大的SDF值。
步骤2:迭代轮廓曲线运动方程。
update激活点的Φ。
提取update后的Φ的零水平集曲线dn，检测是否达到窄带边缘点，若达到，则依据目前的dn按步骤1重新构建窄带和SDF，然后继续循环。
收敛检查。

第3章 分水岭图像分割算法
分水岭算法其实就是对于整体形态进行分割的算法，是对图像做梯度分割处理。这样处理的目的是要将图像分割成不同类型的特殊个体，来分析物体的边缘灰度变化情况。梯度分割处理可以很好的描述图像中物体边缘的灰度变化情况。所以，先将原始图像进行对物体边缘的检测来得到梯度图像，在用分水岭算法对梯度图像进行分割。