（计算机软件与理论专业论文）基于watershed算法的聚类技术研究.pdf

中文摘要 摘要 随着信息技术的发展，聚类技术在数据挖掘、信息检索、图像分割、模式 识别等许多领域都得到了广泛的应用，其中无监督分类法更是一个充满挑战的 研究方向。 本文提出了一种基于分水岭变换的聚类算法，这种方法把著名的分水岭算 法融入到聚类技术中，它的基本思想是：在数据空间中建立一个个合适的网格， 根据数据的分布情况在网格上定义密度函数，然后把每个网格的密度当作其灰 度值，从而把数据空间转换成了数字灰度图像，再对其进行分水岭算法处理得 到聚类结果。作者对随机产生的正态分布的多个样本集的综合情况进行了实验， 聚类结果表明该算法能够自动获得聚类的个数，而且正确识别率稍低于k m e a n s 算法；对于k m e a n s 算法无法解决的同中心的多个样本集聚类问题，本文提出 的方法也收到了较好的效果。 这种方法最大的特点就是能够自动地得到聚类的数目，而无需用户指定， 实现了一种完全无监督聚类方法。本文通过进行两组实验，得到了比较满意的 结果，从而证明了该算法的可用性。 关键字：聚类，分水岭算法，k m e a n s 算法，无监督聚类 a b s t r a c t a b s t r a c t w i t ht l l ed e v e l o p m e n to fm ei o 眦a t i o nt e c h n 0 1 0 9 y ，c l u s t e r i n gt e c h n o l o g yh a s b e e na p p l i e di ns e v e m lc o n t e x t s ，f o re x a m p l e ，d a t am i l l i n g ，i n f 0 册a t i o nr e 砸e v a l ， i m a g es e g m e n t a t i o na 1 1 dp a t t e mr e c o g l l i t i o l l ，e t c a n du n s u p e r v i s e dc l a s s i f i c a t i o ni s u n d o u b t e d l yac h a l l e n g i n gr e s e a r c ha r e a i nt t l i sp a p er ，ac i u s t e r i n ga i g o r i m mi sp m p o s e dw 王l i c hi sb a s e do nm ew a t e r s h e d t r a n s f o n n i tm e l t st l l ew e l l - k n o w nw a t e r s h e da l g o r i t h r ni n t oc l u s t e r i i l gt e c h n 0 1 0 9 y t h eb a s i cc o n c e p t i o ni sb u i l d i n gas u i t a b l el a t t i c eo nt 1 1 ed a t as p a c e ，a n dd e f i n i n ga d e n s i t yf u n c t i o no ni ta c c o r d i n gt ot h ed i s 廿i b u t i o no ft h ed a t a ，t h e nr e g a r d i n gd e n s i t y v a l u eo fe v e 珂c e l la st h eg r e yv a l u ea n dr e s u l t i n gi nac o n v e r s i o nt o d j 百t a lg r e y i m a g e t h ea u t l l o rm a d ee x p e r i m e n t so ns e v e r a ln o n n a ld i s t r i b u t i o ns a m p l e sw | i i c h w e r eg e n e r a t e dr a i l d o m l y ，c l u s t e r i n gr e s l l l t ss h o w e dm a tm ep r o p o s e d 印p r o a c hc a t l d e t e 皿咀i n et b en 岫b e ro fc i u s t e r sa u t o m a t i c a i l y ，a n dm ea c c u r a c yw a ss i i g h t i yw o r s e t h a nt 1 1 a to fk m e a n sa l g o r i t h m ；n e v e r t h e i e s s ，w i t ht w oc o n c e n t r i cc l u s t e r s ，w h i c h m ek m e a i l sa l g o r i m mi sn o ta b l et od e a lw i t h ，t h ep r o p o s e d 印p m a c hr e c e i v e dg o o d r e s u l t t h em a i nc h a r a c t 硎s t i co ft h j sm e t h o di st h ec a p a b i l i t yo fd e t e 肋i n et h en u r n b e r o fc l u s t e r sa u t o m a t i c a l l y ，a 1 1 dd o n tn e e du s e r sd e f i n i n r e s u l t i n gmac o m p l e t e i y u n s u p e r v i s e dc l u s t e r i n ga p p r o a c h i nt l i i sp 印e r ，w ep e 怕衄e dt h ea p p r o a c ht ot w o 掣o u p so fd a t a ，a n dr e c e i v e dg o o dr e s u l t s ，t h e r e b y 山ea v a i l a b i l i t yo f 廿l i sm e t h o dw a s v e 一e d 1 ( e y w o r d ：c l u s t e r i n g ，w a t e r s h e da l g o r i t h m ，k i e a n sa i g o r i t h m ，u n s u p e n r i s e d c i u s t e r i n g i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和屯子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送变论文的复印什和电子版；在不以赢利为日的的前 提下，学校可以适当复制呛文的部分或全部内样用_ 丁学术活动。 学位论文作者签名：白如珍 工帅乒i ! ，月j j 口 经指导教师同意，本学位论文属丁保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月同 各密缎的最长保密年限及书写格式规定如下 内部5 年( 最长5 年，可少r5 年) 秘密1 0 年( 最长1 0 年，可少于1 0 年j 机密2 年( 最长2 0 年，可少丁2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：囟吱日玲 2 。一6 年岁月弓1 日 第一章聚类分析概述 第一章聚类分析概述 随着科学技术的飞速发展，聚类技术在许多研究领域得到了广泛应用， 比如数据挖掘、d n a 模拟、信息检索、图像分割、信号压缩与编码及机器学 习等等，尤其在数据挖掘领域，聚类分析已成为一个重要的研究方向。与分 类有所不同，聚类的目标是在没有任何先验知识的前提下，根据数据的相似 性将数据集合成不同的簇( 或类) ，使得相同簇中的元素尽可能相似，不同 簇中的元素差别尽可能大，因此又被称为非监督分类( u n s u p e r v i s e d c l a s s i f i c a t i o n ) 。聚类既可以是一个独立工具，也可以是己知模式算法的 一个预处理过程。 本章将首先介绍聚类分析的概念以及相关的基础知识，然后对现阶段的 聚类技术做一个总体描述，并介绍聚类算法研究面l 临的挑战。 1 1 1 什么是聚类 第一节聚类的概念 聚类“1 ( c l u s t e r i n g ) 就是将对象集合分割成为多个类( 也叫簇， c l u s t e r ) ，使得同一类中的对象之间具有较高的相似性( s i m i l a r i t y ) ，而 不同类中的对象具有较大的相异性( d i s s i m i l a r i t y ) 。 1 1 2 评价聚类好坏的标准 一个好的聚类算法应该产生具有如下特性的聚类结果：类内的对象之间 高度相似( h i g hi n t r a c l a s ss i m 订a r i t y ) ，而属于不同类的对象之间很少 相似( 1 0 wi n t e r c l a s ss i m i l a r i t y ) 。但是如何评价一个聚类结果的好坏， 到目前为止还没有一个统一的标准，现在人们常常从以下几个方面来评价一 个聚类算法的优劣”1 ： l 、处理大的数据集合的能力； 2 、处理任意形状、不同类型数据的能力： 第一章聚类分析概述 3 、算法是否独立于输入顺序： 4 、处理数据噪声( 脏数据) 的能力： 5 、是否需要预先知道聚类个数，是否需要用户给出领域知识； 6 、算法处理具有多属性的数据的能力，即算法是否对数据维数敏感； 评价一个聚类算法的好坏，一般从以上几个方面综合衡量。 第二节聚类分析方法及其分类 目前常用的聚类分析算法主要有以下几种类型：基于划分的聚类、层次 聚类、局部方法和模型方法等。下面就对这几类算法分别作一下介绍。 1 2 1 基于划分的聚类 基于划分的聚类算法的基本思想是：对于一个包含n 个数据对象的数据 集，构建k ( k 1 ： 4 、通过随机采样消除异常数据，即若一个聚类增长太慢就去除它； 5 、对部分聚类进行再聚类落在每个新获得聚类中的代表点根据收缩因 子n 移向聚类中心，这些点用于代表并描绘聚类的边界； 6 、对聚类的数据标记上相应的聚类号。 c u r e 算法对含有异常数据对象进行分析时也能够获得较高聚类质量， 允许聚类具有复杂的形状和不同的大小，并且只对数据进行一遍扫描。 1 2 3 基于密度的方法 基于密度的方法的主要思想是：只要邻近区域的密度超过某个阂值，就 继续聚类，最终相对高密度的区域被相对低密度的区域分割开来形成簇。该 方法可以发现任意形状的簇，并有效过滤噪声点。代表算法有：d b s c a n 算 3 第一章聚类分析概述 法、o p t i c s 算法、d e n c l u e 算法、d b c l a s d 算法、c l i q u e 算法等。 基于密度的方法最著名的是d b s c a n ( d e n s i t y b a s e ds p a t i a l c 1 u s t e r i n go fa p p l i c a t i o n sw i t hn o i c e ) ”3 算法。d b s c a n 算法通过不断 生长有足够高密度的区域来进行聚类。它基于这样的思想：在一个数据空间 中，高密度区总是被低密度区所分割。它能够从含有噪音的空间数据中发现 任意形状的聚类。d b s c a n 算法将一个聚类定义为一组密度连接的点集。 基于密度的聚类算法对于任意形状特性的数据集具有很好的适应能力， 但是最初的算法是要用户来确定参数，这大大限制了它的自适应能力。 1 2 4 基于网格的方法 基于网格的方法把对象空间量化为有限数目的单元( c e l l ) ，从而形成网 格结构，然后在这个网格结构上进行所有的聚类操作。该类方法的执行时间 独立于数据对象的数目，即只与单元数目有关，因此速度很快。代表算法有： s t i n g 算法、w a v e c l u s t e r 算法、0 p t i g r i d 算法等。 1 2 5 基于模型的方法 基于模型的方法的基本思想是：事先为每个簇假定一个模型( 可以是数 据点在空间中的密度分布函数或者其它) ，然后寻找数据对给定模型的最佳 拟合。该方法基于如下假定：目标数据集是根据潜在的概率分布生成的。该 方法主要有两种。：统计学方法和神经网络方法。统计学方法有c o b w e b 算 法、c l a s s i t 算法、a u t o c l a s s 算法；神经网络方法有竞争学习法和自组织 特征映射法( s o m ) 。 1 2 6 综合方法( s y n t h e t i c a lm e t h o d ) 前面介绍了几类不同的聚类算法及其典型代表，现在许多的方法都是将 不同方法进行综合，以此来获得不同算法的优点，从而得到更好的聚类结果。 d e n c l u e ( d e n s i t yb a s e dc l u s t e r i n g ) 1 就是结合了划分方法、层次方法和 局部方法的一个综合方法。s t i n g “方法也结合了基于网格的方法和自上而 下的方法。在现在交叉学科蓬勃发展的今天，不同算法之间的融合与渗透也 第一章聚类分析概述 必将持续发展。 上述部分聚类算法可能同时属于多个类别，这里将它们分在主要所属的 类别中。 第三节聚类分析的应用 聚类分析的应用相当广泛“”。在商务上，聚类能帮助市场分析人员从消 费者信息库中发现不同的消费群体，并且用购买模式来刻画不同的消费群体 的特征；在生物学上，聚类可以被用来辅助研究动植物的分类，可以用来分 类具有相似功能的基因，还可以用来发现人群中的一些潜在的结构；聚类还 可以用来从空间数据库中识别出具有相似特征的空间对象；可以从保险公司 的数据库中发现汽车保险中具有较高索赔概率的群体；还可以用来分类万维 网上不同类型的文档或分析w e b 日志以发现特殊的访问模式等。 第四节聚类算法研究面临的挑战 聚类算法在实际应用中面临许多方面的挑战。： ( 1 ) 可伸缩性( s c a l a b i l i t y ) 。实际应用要求聚类算法能够处理大数据 集，且时间复杂度不能太高( 最好是多项式时间) ，消耗的内存空间也有限。 目前，为了将算法拓展到超大数据库( v l d b ) 领域，研究人员己经进行了许多 有益的尝试，包括增量式挖掘、可靠的采样、数据挤压( d a t as q u a s h i n g ) 等。其中，数据挤压技术首先通过扫描数据来获得数据的统计信息，然后在 这些统计信息的基础上进行聚类分析。比如b i r c h 算法中使用c f 树就是属 于数据挤压技术。 ( 2 ) 能够处理不同类型的属性。现实中的数据对象己远远超出关系型数 据的范畴，比如空间数据、多媒体数据、遗传学数据、时间序列数据、文本 数据、万维网上的数据、以及目前逐渐兴起的数据流。这些数据对象的属性 类型往往是由多种数据类型综合而成的。 ( 3 ) 能够发现任意形状的簇。 ( 4 ) 尽量减少用于决定输入参数的领域知识。 ( 5 ) 能够处理噪声数据及孤立点。 第一章聚类分析概述 ( 6 ) 对输入数据记录的顺序不敏感。 ( 7 ) 高维性( h i 曲一d i m e n s i o n a l ) 。一个数据集可能包含若干个维。较高 的维数给聚类分析带来两个问题：首先，不相关的属性削弱了数据汇聚的趋 势，使得数据分布非常稀疏。尽管这种情况在低维空间中并不多见，但是随 着维数的增加，不相关属性的出现概率及数量也会增加，最后导致数据空间 中几乎不存在簇。其次，高维使得在低维中很有效的区分数据的标准在高维 空间中失效了。譬如在高维空间中，数据点到最近邻点的距离与到其他点的 距离没有多少分别，从而导致最近邻查询在高维空间中不稳定，此时若根据 接近度来划分簇，结果是不可信的。 ( 8 ) 能够根据用户指定的约束条件进行聚类。 ( 9 ) 聚类结果具有可解释性和可用性。 第五节本论文的组织 聚类分析既可以作为单独的挖掘工具以发掘数据源的数据分布信息，也 可以作为其它数据挖掘算法的一个预处理步骤，因此研究如何提高聚类算法 的性能具有重要的意义。本文针对目前聚类算法的一些不足，提出了一种基 于分水岭变换的聚类算法，它能够在不需要知道聚类数目等先验知识的情况 下，把数据自动分成类，而且能够很容易地扩展到n 维空间，很好地解决了 聚类分析对先验知识的依赖性及对高维数据的敏感性。 在后续章节中，第二章首先介绍了分水岭算法的提出，第三章介绍与分 水岭算法有关的概念及分水岭算法的数学描述，第四章将给出分水岭算法的 程序实现以及分割图像的实验，第五章讲述分水岭聚类算法的实验及结果分 析，并对本文做出总结与展望。 第二章w a t e r s h e d 算法的提出 第二章w a t e r s h e d 算法的提出 第一节w a t e r s h e d 算法的提出 w a t e r s h e d ，对应的中文名称叫做“分水岭”。分水岭是个地理名词，著 名的美国大峡谷就是一个例子“”，流经过它的水一部分注入了大西洋，另一 部分则注入了太平洋，从而把美国分成了两部分。还有，秦岭就是我国长江、 黄河两大水系的分水岭，它的南面是长江，北面是黄河。 在数学形态学领域，分水岭算法( 也叫分水岭变换) 是图像分割的一种 方法。它最初是由d i g a b e l 和l a n t u 6 j o u l 提出的，后来被b e u c h e r 和l a n t u 6 j o u l 加以改进。一般来说，图像分割是把图像中的独立物体与图像的背景 分开的处理过程，即把图像分割成一个个在某些属性上相似的独立区域，比 如说灰度值相近的区域“。 第二节分水岭的定义 分水岭变换可以被划分为基于区域( r e g i o n _ b a s e d ) 的图像分割算法。 在图像处理尤其是数学形态学领域，灰度图常常被看作地形学概念。在给定 图像i 的地形学表示中，每个象素点的灰度值代表该点的海拔高度。这种表 示方法对于后面定义局部最小点、盆地及分水岭等概念很方便。一种直观的 定义分水岭的方法是： 假想往一个由数字图像转换成的地形沙盘上喷水，在这个地形沙盘上肯 定存在这样一些点，喷到它们上的水会流向不同的方向。那么，我们就把这 样的点组成的封闭曲线叫做分水岭。如图2 1 所示： 第二章w a t e r s h e d 算法的提出 水 图2 1 分水岭示意图 分水岭点 另外还有种用浸没( i m e r s i o n ) 思想定义分水岭的方法： 假想在地形沙盘的每个翁地的最低点打一个洞，然后把这个沙盘浸没在 水里。根据连通器的原理，每个盆地里的水位都是一样的。当沙盘浸没的越 来越深时，水位逐渐升高。当来自不同盆地的水将要汇合时，就建一个坝 ( d a m ) 。水位涨到最高点时，结束这个过程。这个地形沙盘从而被这些堤坝 分成许多区域( 或盆地) ，这些堤坝连成的封闭曲线就叫做分水岭线，简称 分水岭。如图2 2 所示： 分水岭点( 坝) 图2 2 分水岭示意图二 第二章w a t e r s h e d 算法的提出 第三节分水岭算法的步骤 用分水岭算法模拟图像分割时，通常采用两种方法：一种是先找到盆地， 然后通过对图像“求补”找到分水岭，即不属于任何盆地的部分就是分水岭； 另一种方法是把图像完全分割成盆地，然后通过边缘检测的方法找到分水 岭。 更进一步讲，分水岭变换大体分为以下几步：首先把一幅灰度图像转换 成地形沙盘，图像上每一个点的灰度值作为沙盘上相应点的海拔高度；然后 给沙盘中的每个盆地一个唯一的标号，并不断地扩展每个标号，直到找到所 有的分水岭点为止。 分水岭算法实现起来比较复杂，但如果我们采取并行的机制来实现的 话，算法的速度会得到飞跃性的提高。虽然目前有许多并行程序设计的模型， 但是在分水岭算法的问题上，大多数的实现都是采用消息传递的机制 ( m e s s a g e p a s s i n gp r o g r a m i n g ) 和共享内存( s h a r e m e m o r yp r o g r a 岫i n g ) 的方法来实现的“。 对于本文研究的基于分水岭算法的聚类问题来说，首先要保证算法的正 确性，算法的执行速度可以放在次要地位，所以不采取并行的机制，因此本 文将把主要的精力放在单处理器系统中分水岭算法的实现方面上。 第四节分水岭算法的结果实例 下面是一个用分水岭算法对数字灰度图像进行分割的例子，以助于我们 对分水岭算法有一个比较直观的认识。 图2 3 分水岭算法结果示意图：( a ) 原图；( b ) 分水岭变换后的图 9 第三章分水岭算法的数学描述 第三章分水岭算法的数学描述 本章从介绍图的有关基础知识入手，引入一些与分水岭算法的定义相关 的数学概念及定义“，然后在此基础上给出分水岭算法的数学描述。 3 1 1 图( g r a p h ) 第一节相关的数学定义 一幅图( g r a p h ) 可以表示为g = ( 矿，e ) ，其中v 是图中所有点的集合， 而e 是f 的子集，其中f = ( v ，v 2 ) i v v 。v ，v v ：v ) 。图可分为无向图 ( u n d i r e c t e dg r a p h ) 和有向图( d i r e c t e dg r a p h ) 。在无向图中v 和v ，是 无序的，而在有向图中则是有序的。在无向图中顶点对( v ，v ，) 被称作边 ( e d g e ) ，而在有向图中被称作弧( a r c ) 。无论在无向图还是有向图中边 p = ( v l ，v 2 ) 都被称作与v l 和v 2 相邻( i n c i d e n t ) 。同时，我们也可以说v l 和v 2 与e = ( v 。，v ：) 相邻，或者说点v 和v ，相邻。 所有与点v 相邻的点的集合被定义为，( 力。在图g = ( 矿，e ) 中一条从顶 点p 到顶点g 的长为，的路径( p a t h ) 7 r 是由点( p 0 ，n ，口+ n ) 的序列组成 的，其中= p ，p ，= q ，并且v f 【o ，) 都有( v ，v 。) e 。路径万的长度表 示为彪愕f ( 万) 。 当一条路径万中的所有点都不相同时，万被称作是简单路径( s i m d l e p a t h ) 。如果在顶点p 和顶点g 中至少存在一条路径丌时，我们可以说顶点p 和顶点q 是相连的( r e a c h a b l e ) 。 在一个无向图中，如果任意两个顶点之间都是相连的话，那么这个无向 图就被称作是连通的( c o n n e c t e d ) 。 如果存在两幅图g = ( 矿，e ) 和g = ( 矿，e ) ，其中矿矿，e e 并且e 。 中的元素只和矿1 中的点相邻，那么，我们就可以说图g 1 是图g 的子图 ( s u b g r a p h ) 。一个图g 的连通部件( c o n n e c t e dc o m p o n e n t ) 是这个图的最 大的子图。 1 0 第三章分水岭算法的数学描述 如果一条路径万= ( p 。，p ，毋+ 所) 中p 。= p ，并且风，n ，p “都不相 同的话，我们就称这条路径为环路( c y c l e ) 。如果一个图中没有环路的话， 我们就称它为非循环图( a c y c l i cg r a p h ) 。一个森林( f o r e s t ) 是一个无向 非循环图，一棵树( t r e e ) 是一个无向连通非循环图。 3 1 2 带权图和带值图 一个带权图( w e i g h t e dg r a p h ) 可以表示为g = ( 矿，e ，w ) ，其中w ：e 寸r 为一个定义域为e 权函数( w e i g h tf u n c t i o n ) 的。一个带值图( v a l u e dg r a p h ) 可以表示为g = ( 矿，e ，厂) ，其中厂：矿j r 为一个定义域为矿的权函数。一个 带值图g 的等级( 1 e v e l ) 为 的部件是顶点集合v 的一个连通部件，其中 v e 矿并且厂( v ) = 。 一个等级为 的部件p 的边界( b o u n d a r y ) 是由这样的一些点p 组成的， 其中p 尸，厂0 ) = 并且p 的邻居g 的灰度值不同于p ，即 ( p ，g ) e ，且厂( g ) 厂( p ) 。一个等级为 的部件p 的低边界( 1 0 w e rb o u n d a r y ) 是它的边界点中的这样一些点p ，其中p 至少有一个邻居g ，使得 ，( g ) 厂0 ) 。一条下降路径( d e s c e n d i n gp a t h ) 是一条值不增长的路径。 我们用丌：( p ) 代表从顶点p 起始，到某个顶点口终止且，( g ) 厂( p ) 的所有 下降路径的集合。 3 1 3 极小区域( m i n i m u m ) 如果从一个等级为矗的部件p 的边界中找不出任何一个低边界，那么这 个部件就称为等级为 的局部极小区域( r e g i o n a lm i n i m u m ) ，简称极小区 域。下图显示了极小区域、分水岭与盆地的关系： 盆地 排i 孕” 极小区域 图3 1 极小区域、盆地与分水岭“5 第三章分水岭算法的数学描述 3 1 4 数字网格 数字网格( d i g i t a lg r i d ) 是一种特殊的图。我们通常使用方形网格 d c z 2 ，这里的顶点被称作像素( p i x e l ) 。当d 确定时，d 的大小就是它 所包含的点的个数。对于一幅图g = f 矿，e 1 来说，数字网格d 中的像素集可 以是v ，而数字网格中的边e 可以是规定连通性的z 2 z 2 的某个子集。通常， 人们会选择这幅图的4 连通集或者8 连通集来作为与之对应的数字网格的边 集合。 在数字网格中，两个相邻的点p 和q 之间的距离d ( p ，q ) 是通过与它们之 间的边e ( p ，q ) 相关联的一个非负的权值来决定的。这样，我们就可以将一幅 图转换为一幅带权图。非相邻像素点p 和q 之间的距离被定义为从点p 到点 q 的所有路径中最小路径长度( 取决于网格的图形结构，即连通性) 。 3 1 5 数字图像 一幅数字灰度图像可以表示为一个三元组g = ( d ，e ，厂) ，其中( d ，e ) 是 一幅图( 通常是数字网格) ，映射厂：d 寸n 为d 中的每个点p 赋予一个整数 值。 对于一幅二值图来说，映射f 的值域中仅有两个数，那就是0 和1 。其 中，0 代表背景( b a c k g r o u d ) ，而l 代表前景( f o r e g r o u n d ) ，或者根据具体 情况反过来表示也可以。 对于d 中的每个点p 来说，f ( p ) 表示该点的灰度值或者海拔。对于灰度 级图像来说，f ( p ) 的取值范围通常为l o ，2 5 5 l 。 这样，我们就可以定义一幅数字图像中的一个在等级h 上的阈值点集 ( t h r e s h o l ds e t ) t h = p d 陋0 ) h ，而在等级h 上的一个高地( p l a t e a u ) 或者是水平区域( f l a tz o n e ) 就是在该等级上的阈值点集的连通区域。 3 1 6 测量学距离的概念 假定4 e ，这里= 彬或= z 4 ，a 和b 是区域爿中的两个点，那么在 区域a 中这两点之间的测量学距离d 。( a ，b ) 就是该区域中连接两点的最短路 径的长度。如果区域b 是区域a 的子区域，则定义点a 和区域b 的测量学距 第三章分水蛉算法的数学描述 离为： 丸( 口，b ) = 戤。( 以( 口，6 ) ) 假设区域b 被分割成骨个连通部件e ，其中f _ 1 ，j j 。那么对于每个连 通部件e 来说，它在区域a 中的测量学扩展区域( 筘d 出s j g 月订“朗c e z 伽p ) 就可以定义为： ( 墨) = p e 爿1 w e 【1 t 】、 f ) ：九( p ，e ) ot h e n 4 0 ： i f l a b p 】= m a s ko r l a b 【p = w s h e d t h e n 4 l ： 肠6 眵】+ 一抽6 【训 4 2 ：e l s ei f 蛔6 【p 】肠6 q t h e n 4 3 ：，口6 l p w s h e d 4 4 ：e n d i f 第四章分水岭算法的设计与实现 4 5 ： e l s ei f 肠6 p = m a s kt h e n 4 6 ： 肠6 m + w s h e d 4 7 ：e n d j f 4 8 ： 4 9 ： 。l s 。i f 陆6 纠3m a s ka n dd i s t q _ 0t h e n产q 是一个高地像素点+ 咖f 棚+ 一c 船f + l ；肋谢( g g “p “p ) 5 u ： e n d i f 5 1 ： 口d f o r 5 2 ： e n d l o o p 5 3 ： 唪在第h 级寻找新的局部最小点并开始扩展+ 5 4 ： f o r a p dw “h 砌p 】= 向d o 5 5 ： d i s t p 】- _ 0 幸把距离重置为o + 5 6 ：i fl a b p 】= m a s kt h e n pp 是一个新的局部最小点+ 5 7 ： c u r l a b 一c u r l a b + l ；p 创建一个新的标号+ ， 5 8 ：刑i o _ a d d ( p ，q u e u e ) ；j a b p + 一c u r l a b 5 9 ：w h i l en o tn f j _ e m p t y ( q u e u e ) d o 6 0 ： q + _ n f 0 一r e m o v e ( q u e u e ) 6 1 ：f o ra l l r g 国) d o 严考察q 的邻居+ 6 2 ： i f l a b 【r = m a s kt h e n 6 3 ： n f b _ a d d ( l q u e u e ) ：l a b r 】+ 一c u r l a b 6 4 ：e n d i f 6 5 ： e n d f o r 6 6 ：e n dw h i l e 6 7 ：e n d i f 6 8 ：e n d f o r 6 9 ：e n d f o r 7 0 ：幸浸没过程结束( e n df 1 0 0 d i n g ) + 由上述代码可以看出，这个算法大致分两步进行： ( 1 ) 排序的过程( s o r t i n gs t e p ) ：为了能够直接得到某个灰度级的像素点， 对图像中的所有点按灰度值由小到大排序。 ( 2 ) 扩展的过程( f l o o d i n gs t e p ) ：从局部最小点开始，逐级地扩展每个盆 2 第四章分水岭算法的设计与实现 地，直到所有的点都获得标号为止。 在扩展的过程中，我们使用了一个先入先出的队列( f i f oq u e u e ) 数据结 构。在该数据结构上，我们可以进行如下操作： 舻一日甜( p ，g “p “e ) ：把像素点p 添加到队列g “e “e 的尾部。 伽一r 硎o w ( g “e “p ) ：返回队列中的第一个元素。 加一f 疗f f ( g “p “p ) ：初始化对象口u e 卯为一个空队列。 加一e 御砂( q “e “8 ) ：判断队列q “e u e 是否为空，如果为空则返回t r u e ， 否则返回f a l s e 。 为了实现这些操作，最有效的是一种方法是使用“循环”队列。在这种 数据结构中，我们使用h e a d 和t a i l 两个指针来访问数组所代表的f i f 0 队 列。每次往队列中加入一个元素时，只要把它存入t a i l 指针所指向的地址 即可，同时t a i l 值递增。当达到数组的最大长度时，t a i l 指针循环回到数 组的开始。类似的，h e a d 是指向数组当前第一个元素的指针，每次从队列 中移出_ 个元素后h e a d 值递增。当h e a d 值达到数组最大长度时，它也会循 环回数组的开始。为了充分利用内存，也可以考虑使用“动态( d y n a m i c ) ” 队列，但是它通常会降低执行的速率，所有很少使用。 在扩展盆地的过程中，我们采用一种广度优先的策略，从每个局部最小 点开始扩展，直到所有的最小点及其与之对应盆地都被赋予一个唯一的标号 为止。具体的执行过程是：在执行第h 级扩展时，先把该层的所有点都用 m a s k 标号，接着把那些有已经被标号( 盆地或分水岭点) 邻居的点加入到 队列中，然后就从这些点开始扩展。那些到至少与两个不同盆地相邻的点被 标为分水岭点w s h e d ，而那些所有路径都到达同一标号的点被该标号对应得 的盆地“吞并”。当扩展过程结束以后，那些灰度值为 但是却还没有被扩 展，也就是标号仍然为心蹦的点是一个新的局部最小值，它们属于一个新 的盆地。所以，这些点会被赋予一个与其它盆地不同的新标号。该算法的时 间复杂度是0 ( n ) 级的，即与输入图像的像素点数目n 成线性关系”1 。 实际上，v i n c e n t s o i l l e 算法并没有完全实现上一章所介绍的分水岭 算法的递归定义，原因如下0 4 1 ( 下面所提及的行号指的是算法4 1 中的行 号) ： 第四章分水岭算法的设计与实现 l 、在第 级，算法仅仅是将那些灰度值等于办的点考虑在了计算过程 中，而并不是像定义中描述的那样，所有灰度值小于等于 的点被标记为 捌船，然后被标号( 第1 7 行) 。 2 、在计算过程中，不只是每个盆地被扩展，而且分水岭点也被扩展。 这个问题是不可避免的，也是上面那点所造成的结果。因为在每一步只考虑 灰度等级等于 的点，所以我们需要来扩展分水岭点来把那些周围只有分水 岭点作为邻居的点识别为分水岭。 3 、一个与两个不同盆地相邻的像素点初始被标记为分水岭点w s 旺d ， 但是如果它属于某个盆地，则它有可能在后来的迭代过程中被赋予该盆地的 标号( 第4 0 4 1 行) 。这样做的目的是为了防止产生“偏差( d e v i a t e d ) ”分水 岭。但是，在我们看来，判断一个算法精确与否主要还是要看它是否完全地 实现了其数学定义。 但是，要完全按照浸没思想来实现分水岭算法并不困难，只要对算法 4 1 稍作修改即可： l 、在第1 7 行，将砌0 ) = a 改为咖0 ) ； 2 、初始化队列时，队列中只应包含那些盆地点，而不应该包含那些分 水岭点。也就是说，将第2 0 行中的7 玎6 ( g ) = 聊 h e d 去掉； 3 、将距离的重置( 第5 5 行，如r r ( p ) 卜o ) 操作改到第1 9 行后面； 4 、第3 6 5 l 行之间的扩展规则也需要做细微的修改。 然而，值得注意的是，通过上述修改，因为需要对分水岭点进行重复判 断才能为其确定标号，算法的理论时间复杂度将会从线性的( 1 i n e a r ) 变成平 方级的( q u a d r a t i c ) ，尽管在实际应用中这样的分水岭点数目可能很小。 现在，我们试图将修改过的n c e n t s o i i l e 算法用一个数学公式表示出 来： i k 。= p d l 厂( p ) = i 。j i 以+ 。= 五u 蚴巩+ ，u ( 亿( 五) 瓦) ，办 k i n ，。) 但是，这个修改后的算法有时候也不能完全精确地实现浸没思想的分水 岭定义，因为公式中的“l ”操作很有可能使盆地变得不连通 ( d i s c o n n e c t e d ) 。事实上，我们很难找到一种算法来精确地实现浸没思想下 弟四章分水岭算法的设计与实现 的分水岭定义。 4 1 2 排序算法 在众多可用的排序算法中，有一种特别适合运用到算法4 1 的排序中， 它就是借助于地址计算的分布式算法“。这个算法是由e j i s a a c 和 r c s i n g l e t o n 提出的。算法首先确定图像各个灰度级的频率分布 ( f r e q u e n c yd i s t r i b u t i o n ) ，然后计算累积频率分布，这样一来就可以直接 访问图像每个灰度级的像素点。 假设图像有n 个像素点，i 。和。分别表示该图像的最小和最大灰度 级。使用这个排序算法仅需要幼次“查找一执行( 1 0 0 ka n dd o ) ”操作，即 只需两次扫描图像即可：第一次扫描用来确定频率分布，第二次扫描用来获 得累积频率分布。相对于图像来说，计算频率分布所需的内存和时间通常是 可忽略不计的，因此这个排序过程是我们处理数据的最佳选择之一。 通过这个排序过程，我们把图像中的所有点都存入了一个有序队列中。 这个有序队列是一个由n 个先入先出的队列组成的数据结构，其中n 代表图 像中不同灰度级的个数。每个先入先出队列中存放的是灰度值为某个固定值 的像素点。分水岭算法从最低的灰度值开始处理，因此较低的灰度级拥有较 高的优先级。 第二节分水岭算法的实现 4 2 1 程序设计语言和开发平台的选择 m i c r o s o f l s u a ls t u d i o6 0 是m i c r o s o f t 公司推出的一款非常出色的、功能非 常强大的集成开发环境，它所包含的m i c m s o r v i s u a lc