蚁群聚类算法研究及应用

－5009－ 0引言

俗话说“物以类聚，人以群分”，人们在不知不觉中进行着 聚类活动，它是人们认识和探索事物之间内在联系的有效手 段。聚类在数据挖掘中有着重要的地位，它既可以用作独立 的数据挖掘工具，来发现数据库中数据分布的一些深入信息， 也可以作为其它数据挖掘算法的预处理步骤。因此，聚类算 法的研究具有很重要的现实意义。

蚁群算法不依赖于具体问题，具有全局优化能力，因此受 到了广大学者的注意。此后蚁群算法不断被改进并应用于不 同领域。在聚类分析方面，Deneubourg等人受蚂蚁堆积尸体 和分类它们的幼体启发，最早将蚁群算法用于聚类分析，从此 开始了蚁群聚类算法的研究。

本文详细地讨论了现有的蚁群聚类算法的基本原理与性

能，在归纳总结的基础上提出需要完善的地方，以推动蚁群聚 类算法的进一步研究及在更广阔的领域内得到应用。 1聚类概念及数学模型

聚类就是把一组个体按照相似性归为若干类或簇，使得 属于同一类或簇的个体之间的差别尽可能的小，而不同类或 簇的个体间的差别尽可能大。聚类质量是用对象的相异度来 评估，而不同类型变量的相异度的计算方法是不同的，常用的 度量方法是区间标度变量中的欧几里得距离。 聚类的数学描述：设样本集={,=1,2,?,}，其中为 维模式向量，其聚类问题就是找到一个划分={ 1 , 2 ,…,

}，满足= =1

，≠，=，,=1,2,?,，≠，且使 得总的类内离散度和= =1

,最小，其中为的

聚类中心，=1,2,?,；,为样本到其聚类中心的距 离，即,=‖‖。聚类目标函数为各样本到对应 聚类中心的距离总和，聚类中心=1 ，||为的样 本数目。

2蚁群聚类算法分类及应用

由于现实的蚁群运动过程接近于实际的聚类问题，所以 近年来涌现出大量的蚁群聚类算法。这些算法不仅思想、原 理不同，而且算法的特性也根据解决问题的不同而不同，如初 始参数及待聚类数据的要求、聚类形状等。

根据改进方式的不同，蚁群聚类算法可分3类：①基于蚂 收稿日期：2007-10-17 E-mail：05lihua@sohu.com

作者简介：裴振奎(1962－)，男，山东东营人，博士研究生，副教授，硕士生导师，研究方向为机器学习与计算智能；李华(1977－)，女，山

东滨州人，硕士研究生，研究方向为数据挖掘、自然计算；宋建伟(1982－)，女，河北廊坊人，硕士研究生，研究方向为网络安全、计算智能；

韩锦峰(1981－)，女，山西大同人，硕士研究生，研究方向为计算智能、数据库系统理论。 蚁群聚类算法研究及应用

裴振奎，李华，宋建伟，韩锦峰

(中国石油大学(华东)计算机与通信工程学院，山东东营257061)

摘要：聚类作为数据挖掘技术的重要组成部分，在很多领域有着广泛应用。蚁群算法是近几年研究的一种新算法，该算法

采用分布式并行计算和正反馈机制，具有易于与其它方法相结合的优点。根据蚁群算法在聚类中的应用及改进型式的不同，

文章主要介绍了几种基本的流行的蚁群聚类算法，分析了它们的不同之处，并对蚁群聚类算法今后的研究方向作了展望。

关键词：聚类;蚁群算法;信息素;正反馈机制;蚁群聚类算法

中图法分类号：TP301文献标识码：A文章编号：1000-7024(2008)19-5009-05 Investigation and application of ant colony clustering algorithms PEI Zhen-kui,LI Hua,SONG Jian-wei,HAN Jin-feng

(College of Computer and Communication Engineering,China University of Petroleum(East China),

Dongying 257061,China)

Abstract：Clustering is widely used in some fields as a part of important data mining.Ant colony algorithms are novel algorithms in re-

cently years.These methods have several virtues such as distributed parallel computing,positive feedback mechanism and combination

with certain heuristics.Some kinds of basic and popular ant colony clustering algorithms are introduced,the differences of them are

analyzed and the direction for study of ant colony algorithms based on application and improving modality in clustering.

Key words：clustering;ant colony algorithm;pheromone;positive feedback mechanism;ant colony clustering algorithm

计算机工程与设计2008年10月 Oct.2008

第29卷第19期

Vol.29 No.19 Computer Engineering and Design－5010－

蚁行为特征的聚类算法，如：蚂蚁觅食原理为基础的聚类、受 蚂蚁堆积尸体启发的聚类等。这类算法大多是根据具体情况 对系数、参数及公式等的改进。②多种群的蚁群聚类算法，这 类算法主要是将上述的单种群扩大为多种群，以完善聚类效 果、提高速度。③与其它方法结合，通过优势互补来改善聚类 效果、提高聚类质量、缩短聚类时间，如与K-Means算法结合 [1]

，

与遗传算法结合的算法等。

蚁群聚类算法应用很广，从Deneubourg发现蚂蚁能将分 散在蚁穴各处的蚂蚁尸体按一定规律垒堆起来，并依此提出 了基于蚂蚁的聚类基本模型开始。之后，Lumer和Faieta在此 基础上提出了用于聚类分析的LF算法 [2]

，并将其应用到数据 分析当中。Monmarché [1]

引入AntClass系统，交替使用蚁群聚类

和k均值算法修正误差，获到“高质量”的聚类。Ramos等人 [3] 、

Handl等人 [4]

将LF算法用于文本聚类。Kuntz和Snye则对每

对图像节点的非相似度值函数做了修改，将之用于图像的分 割，韩彦芳等人 [5]

从模糊角度出发结合蚁群特点提出了用于图 像分割的蚁群聚类算法。吴斌等人 [6]

将基于蚁群的聚类算法

用于客户关系管理中的客户行为分析以及Web文档聚类。翁 怀荣等人 [7]

引入随机扰动和感觉知觉特征以指导信息素的更

新，并将改进后的蚁群聚类算法用到企业人力资源管理中。总 之，随着蚁群聚类算法研究的深入，其应用领域也在不断扩大。 3算法分析

3.1基于蚂蚁行为特征的聚类算法 3.1.1基于蚂蚁觅食原理

蚂蚁觅食主要分搜索和搬运食物两步。蚂蚁移动时在所

经路径留下信息素，通过感知信息素的强弱进行非直接通信， 形成正反馈加强搜索。在该算法中，一般将数据视为具有不 同属性的蚂蚁，聚类中心即蚂蚁所要寻找的“食物源”，数据聚 类过程被看作是蚂蚁寻找食物源的过程。 基本思想 [8]

：假设待聚类对象为={|=( 1 , 2

,…,),=

1,2,?,}，算法首先进行初始化，将设置各个路径的信息素 0=0，半径，统计误差，代表对象等参数。计算对象到 之间的加权欧氏距离 = =1 2

及各路径上的信息素 = ｛ 1, 0,>

，将对象合并到的概率为 =(1)

式中：={≤,=1,2,?,,+1,?,}，、——控制参数的 常量，——权值。如果> 0 ， 0

——阈值常数，则将合 并到的领域。

该方法的优缺点：不需要预先设置聚类数，但由于簇半径 已经给出所以聚类规模受到了限制；代表对象对运行效率 及聚类结果影响较大，选择不当将陷入局部最优解；若待聚类 数据大时，算法的执行速度慢。为了缩短算法时间，文献[9]改 进了算法，使蚂蚁在空载时搜索数据对象，负载时搜索簇相结 合，既能扫描所有数据元素，又能利用信息素痕迹引导蚂蚁快 速返回到簇，加速算法收敛。但这种方法也存在问题：不再将 数据都视为蚂蚁，这就需要确定蚂蚁数。蚂蚁数目的大小影 响聚类的性能和收敛速度：太少，收敛速度变慢；太多则使聚 类性能变坏。其次，蚂蚁转移以信息素的大小作为依据，因此 算法容易陷入局部最优解。目前，基于蚂蚁觅食原理的聚类 算法是用的较多的蚁群聚类算法，但仍然存在如上所述的问 题，因此还有待进一步改进。 3.1.2蚁堆形成原理

生物学研究显示，蚂蚁能将群体中死亡的蚂蚁聚集成堆。 工蚁对不同的蚂蚁尸体分别放置，小的蚁堆通过吸引工蚁将 更多的尸体放置其中。待聚类的个体逐个被拾起，并根据周 围的环境将个体再逐一放下。

基本思想：假设所有的数据对象都随机地分布在二维的 与数据集成比例伸缩的网格中，处于网格中的两个对象和 之间的距离(又叫相异度),=0，反之则为1，得到一个二

进制相异度矩阵。设若干个蚂蚁在此二维网格上移动，反复 执行拾起或放下对象的操作。如果蚂蚁某一时刻在位置处

发现了对象，则在处与相似的对象的局部密度为 =max{0, 1 2 [1 , 1+1 max ]}(2)

式中：——对象领域中出现其它对象时的平均相似 度。参数为相异度比例，位置的领域 ×

的面积为×。

蚂蚁速度均匀分布于[1, max

]，其中是一个蚂蚁在一个时间单

元内沿给定的网格轴线行走的网格单元数。

每次循环蚂蚁拾起和放下对象的原则：如果蚂蚁没有负

载，即没有搬运对象，则随机从邻近的单元拾起一个对象，拾 起概率为 = 1 1 + 2 (3)

如果蚂蚁有负载，则它随机的选择邻近的空单元放下该

对象，或者如果负载对象与邻近对象相似也放下该对象，放下 概率为 = ｛ 2,< 2 1, 2 (4) 其中 1 、 2

都为一个阈值常数。蚂蚁拾起或放下负载对象受局

部相似密度影响，局部相似度大，则拾起概率就小、放下概 率大，负载对象不易被移走；反之亦然。同时，蚂蚁的移动速 度也将影响拾起或放下对象。

该算法是基于网格和密度的聚类方法 [8]

，高维数据空间首

先映射到某一低维网格空间，映射要确保簇间距离不小于簇 内距离。算法优点：不需要预先设定聚类的簇数，同时由于是 基于密度的聚类方法，还可以发现任意形状的簇。缺点：随机 的拾起、移动和放下对象，因此算法的收敛速度很慢；网格的 精细度影响聚类结果的精细度，且存在能否搜索到所有对象 的问题。

3.1.3蚂蚁自我聚集行为的聚类

蚂蚁通过自我聚集行为构建的树状结构，称为蚂蚁树 (AntTree) [10]

。树中的节点是蚂蚁表示的数据，蚂蚁能够达到树

的任何地方并能粘在任何位置上。起初，蚂蚁被放在一个相 当于树根的固定点上，蚂蚁在这棵树上或已经固定在树上的

蚂蚁身上移动，来寻找适合的位置，由于受到对象间的作用，－5011－ 蚂蚁更趋于固定在树枝的末端。树的结构和蚂蚁表示的数据 之间的相似性引导它的移动，当所有蚂蚁都在树上固定后，就 获得了数据集的划分。

基本思想：规定每只蚂蚁只有一个父亲节点，最多有 max

个孩子结点。对每只蚂蚁都定义一个相似度阈值()和相 异度阈值()，并由进行局部更新，用来判断蚂蚁表示 的数据与其它蚂蚁表示的数据的相似或相异程度。

蚂蚁的局部行为：第一个蚂蚁直接连接到上，对后来的蚂 蚁分两种情况： (1)在支点上。设 +

为支点上且与最相似的蚂蚁，若 和 +

足够相似，即, +

≥，则它就连接在支点上，意

味创建了一棵新子树，该子树上的蚂蚁将尽可能的与以 0 为根

的其它子树上的蚂蚁不同，其中,=11 =1 2 ，

表示相似度尺度；若 0

已经有 max

孩子结点，则向 +

移动。假 如和 +

既不足够相似也不足够相异，则用式(5),(6)更新阈值 *(5) +(6)

增加下次连接的概率(，为调解因子)。 (2)在蚂蚁上移动。若的孩子结点少于且与 足够相似(即，≥)，与上其它蚂蚁足够相 异(即， +

<)，则连接到上，否则蚂蚁随机地 向的邻居移动，其中 +

表示上与最相似的蚂蚁。根据

需要更新阈值，寻找合适的位置，当所有蚂蚁都连接好时算法 结束。

这种算法连接后就不再移动，因此算法执行时间相对较 短，但树状结构体一旦形成就不好再调整，因此初始值 0 的选

取至关重要，、调解因子的大小不好掌握也对聚类结果造成 一定的影响。

3.1.4基于化学识别的聚类(AntClust)

对蚂蚁来说，每天都面临相遇时进行识别的问题，因为是 否属于同一个巢关乎巢的安全。蚂蚁幼时由群体中的成年蚂 蚁喂养，通过身体接触接受了其气味并依此建立早期的识别 模板，随着蚂蚁的成长它们自身的化学气味逐渐增强，并因此 影响到与之接触的其它蚂蚁，这样同巢蚂蚁就建立起它们所 共享的气味。 基本思想 [11]

：每只蚂蚁定义如下参数：蚂蚁巢穴属性决

定的标签，用来代表巢。起初蚂蚁不受任何巢穴的影响， 所以=0，随后标签不断变换直到蚂蚁找到最好的巢为 止。模版由蚂蚁的基因和接受阈值组成，前

者对应数据集的对象且在算法过程中不断变化，后者在初始 化阶段获得的，它是蚂蚁与其它蚂蚁相遇期间观察到的最大 相似度,.和平均相似度,.的函数，是动态的，蚂 蚁每次和其它蚂蚁相遇后按式(7)进行修改

← ,.+,. 2 (7)

评价因子反映蚂蚁之间的相遇情况。相同标签的蚂蚁 相遇时增加，反之减少。开始时=0，反映蚂蚁所在巢穴 的规模。 +

表示蚂蚁被接受程度，若具有相同标签的蚂蚁相 遇或两只蚂蚁彼此接受对方， +

增加，否则不接受时减少。蚂

蚁可根据下面公式判断接受与否，设，分别表示两只蚂蚁，则 ,,> ,>(8)

蚂蚁相遇规则：①两只均没巢的蚂蚁相遇并彼此接受时 将创建一个新巢，作为“种子”聚集相似蚂蚁以产生最终的 簇；②没巢的蚂蚁遇到有巢的蚂蚁并且可以别接受时，没巢的 蚂蚁加入；③属于同一个巢的蚂蚁在彼此接受的情况下增加 评价因子和 +

，蚂蚁依感知其巢的大小，根据 +

感知与巢

中其它蚂蚁的接受度；④同巢的两只蚂蚁相遇且不能彼此接 受，减少 + ，当 +

小于一定程度该蚂蚁的标签和重新

被置为0，此时被当作“异类”从巢中被驱逐出去；⑤不同巢的 蚂蚁相遇且彼此接受则合并巢。

该算法无需给定聚类数就能自动实现数据集的聚类；适

用于数字向量、字符串以及多媒体等多种类型的数据。缺点： 大量采用随机策略使蚂蚁达到平衡的效率不高；时间复杂度 难以估计。文献[12]受蚂蚁化学识别系统的聚类算法启发，在 给出有效的聚类评判标准的基础上设计出无参化的聚类算法。 3.1.5受蚂蚁分巢居住行为启发的聚类 该算法 [13]

中，将蚂蚁看成一个行为简单的Agent，代表一

个数据对象。蚂蚁有睡眠和活跃两种状态，并定义了适应度 函数来衡量蚂蚁与其领域的相似度，通过适应度和激活概率 函数决定蚂蚁所处的状态。整个蚂蚁动态地、自适应地、自组

织地形成多个独立的子群体，使不同类别的蚂蚁之间互相分 离，同类蚂蚁紧密排列，从而形成聚类。

基本思想：蚂蚁在[0?1]×[0?1]的二维网格空 间中活动，== 0.5

(为上取整函数)，网格上、下

边界相连，左、右相连。将的状态记为，=(，，，)1≤ ≤，这里为数据个数，和为所在位置的坐标，表示

它所在类的类号，反映它当前是出于活跃还是睡眠状态。采 用Moore型领域使蚂蚁在网格的任何一个位置的周围都有8 个邻居，并记为为的邻域。定义当前位置 的适应度函数为为 =max{0, 1 9 (1 ,, )}(9)

式中：,——Agent代表的数据对象和之间的距 离，即相异度。参数的值可由以下公式确定 =[ 1 =1 ,][ 1 =1 ,](10)

蚂蚁在环境中转为活跃态的激活概率 =(11) 参数 +

，称为激活阈值，并作自适应的调整，其增量依 据式(12)调整 =(12)

式中：——常数，——第代Agent的平均适应度。蚂蚁 移动中，用表示聚类规则的集合。的类别信息通过 中以下的规则更新：①到达一个合适的位置变为睡眠

态，其类号改变，取邻域中与其相异度最小的Agent的类号； ②由睡眠态变为活跃态，其类号也改变，以它的标号作 为其在移动期间的类号；③继续保持睡眠态不变，则其类 号保持不变。

该算法通过活跃和睡眠两种状态，克服了蚂蚁数目难确－5012－ 定的问题，同时又不会遗漏待聚类对象；自适应的修改参数， 所以对参数的限制也少，算法参数少。虽然就聚类质量来说

它有了很大的提高，但仍然存在执行时间长的问题。 3.2多种群蚂蚁聚类

受种群之间相互协作的启发，多种群聚类算法通过信息 交换来发现优化结果 [2]

。多种群聚类是在单种群聚类的基础

上，将单种群扩大到多种群的算法，而各种群可采用相同 [14] 或

不同的蚁群聚类算法 [2]

进行聚类。

在文献[14]中，需要预先设置聚类数M，通过选择M个对 象确定初始的聚类中心，采用最近邻法进一步修改聚类中心， 并根据聚类中心确定种群数。在修改后的聚类中心及规定的 搜索周期内，再进一步对待聚类对象进行划分。

采用不同种群聚类主要分两部：一是相异蚁群的各自聚 类；二是将来自不同蚁群的聚类柔和。这里各种群中的蚂蚁 可以不同步速移动，也可以将转化公式中的参数设置为不同 值。每次各种群聚类行为后将各自的结果，通过超图模型合 并，得到新的相似矩阵。同时，将新的相似矩阵作为信息返回 到各蚁群当中，以指导下此的聚类行为。信息交换策略也可 以采用：种群各自传递各自的信息策略、循环交叉传递信息策 略和选择上次循环中聚类质量最好时的信息策略。 图1给出了多种群聚类算法的一种结构 [15]

。图的底层为

3种速度不同的蚁群模块进行聚类，得到初步结果；上层为聚 类组合模块，并将初步聚类结果组合成一个超图；再上层为图 划分模块，采用基于蚁群算法的图划分算法对超图进行二次 划分，得到最终结果。

虽然采用多种群的蚁群聚类算法往往比单种群的算法在 聚类结果上要好，但这一方法与单种群聚类算法相比需要花 更多的时间，各蚁群数量也不好选择，各种群聚类不好控制， 同时需要设置多个参数。 3.3混合的蚂蚁聚类算法 3.3.1与K-Means算法的混合

考虑到K-Means算法有快速收敛的优点，以此改进蚁群

聚类算法，达到缩短算法时间的目的。Monmarché等人提出的 AntClass算法是在蚁堆聚类的基础上，交替使用蚁群聚类和 K-Means算法修正误差以获到“高质量”的聚类。高尚等人 [14,16]

则先利用K-Means算法对数据进行快速分类，根据分类结果 更新信息素，来指导其它蚂蚁选择。该类算法中，蚁群聚类部

分多采用单种群的聚类算法。先采用K-Means算法进行初步 聚类的最大缺点是对聚类数预先设置。结合密度思想的蚁群 聚类算法 [17]

在使用K-Means算法之前使用蚂蚁聚类，得到初始

的聚类中心，以求避免传统聚类算法对初始分割的要求。 3.3.2与遗传算法的混合 该聚类算法 [18]

主要利用了遗传算法的快速全局搜索能力

和蚁群算法的正反馈收敛机制。算法第一步利用遗传算法对 数据进行初步聚类，形成初始聚类中心；第二步利用蚁群算法 完善聚类结构。该算法的基本框架如图2所示。

这类算法中的蚁群聚类算法也主要基于单蚁群的聚类算 法。虽然两算法结合一定程度地相互弥补了对方的不足，但 算法的合点仍是一个问题，同时算法的复杂度和效率也不是 那么理想。

与其它算法结合的蚁群聚类算法，主要也是为了克服原 蚁群聚类算法的效率低及易陷入局部最优的缺点，是今后蚁 群聚类算法改进和研究的主要方向。 4结束语

蚁群聚类算法具有很多特性：并行性、自组织性、鲁棒性 和灵活性，对算法稍作修改就可以应用到很多领域，因此其研 究价值不言而喻。本文主要总结了现今存在的部份蚁群聚类 算法，针对每种基于蚁群的聚类算法分别论述了它们的基本 思想、聚类原理以及主要步骤。在指出了蚁群聚类算法各自 所具有的优点同时，也分析了各自存在的缺点，如：一部分算 法的聚类数仍需预先设置的缺陷、参数过多的问题、算法仍存 在易陷入局部最优的问题及算法执行时间过长的问题等，这 对算法的改进方向提供了依据。 参考文献: [1]MonmarchéN,Slimane M,Venturini G.On improving clustering in numerical databases with artificial ants[C].Lecture notes in Artificial Intelligence,1999:13-17.

[2]Yang Yan,Mohamed S Kamelb.An aggregated clustering ap- proach using multi-ant colonies algorithms[J].Pattern Recogni- tion,2006,39:1278-1289.

[3]Vitorino R,Juan J M.Self-organized stigmergic document maps: 图1多蚁群聚类算法结构 最终聚类结果 图划分 聚类组合 蚁群1 常数

蚁群2 随机数 蚁群3

递减随机数

图2与遗传算法结合的蚁群聚类算法框架 生成若干组合优化解 解码 Y N

满足条件 群体t+2

依次运算：选择、交叉、变异 计算适应度函数 群体t 个体编码

定义目标函数和适应度函数 问题描述

随机将蚂蚁及初始聚类均匀分布在 平面内，初始化所有参数

对每只蚂蚁根据公式计算对象的平 均相似度及对象间的距离

对每只蚂蚁计算拾起、放下概率 对所有对象标识聚类序列号 输出聚类结果－5013－

Environment as a mechanism for context learning[C].Alba E, Herrera F,Merelo J J,et al.Proc of the 1st Int'l Conf On Meta- heuristics,Evolutionary and Bio-Inspired Algorithms,2002:284- 293.

[4]Handl J,Meyer B.Improved ant-based clustering and sorting in a document retrieval interface[C].LNCS 2439,2002:913-923.

[5]韩彦芳,施鹏飞.基于蚁群算法的图像分割方法[J].计算机工程 与应用,2004,40(18):5-7.

[6]吴斌,郑毅,傅伟鹏,等.一种基于群体智能的客户行为分析算法 [J].计算机学报,2003,26(8):913-918.

[7]翁怀荣,张洪伟,钟响,等.基于改进的蚁群算法的聚类分析及其 在HRM中的应用[J].计算机应用,2005,25(8):1908-1912.

[8]张惟皎,刘春煌,尹晓峰.蚁群算法在数据挖掘中的应用研究[J]. 计算机工程与应用,2004,40(28):171-173.

[9]张建华,赵东东,江贺,等.一种基于信息素的蚁群聚类算法[J]. 计算机工程与应用,2006,42(20):157-159.

[10]Azzage H,Monmarche N,Slimance M,et al.AntTree:a new model for clustering with artificial ants[C].IEEE Congress on Evolutionary Computation,2003:8-12.

[11]Labroche N,Monmarche N,Venturini G.A new clustering algo-

rithm based on chemical recognition system of ants[C].Lyon, France:Proc of 150 European Conference on Artificial Intelli- gence,2002:345-349.

[12]宋振方.聚类若干问题的分析与研究[D].大连:大连理工大学, 2005.

[13]徐晓华,陈崚.一种自适应得蚂蚁聚类算法[J].软件学报,2006,17 (9):1884-1889.

[14]高坚.基于并行多种群自适应蚁群算法的聚类分析[J].计算工 程与应用,2003,39(25):78-80.

[15]段海滨.蚁群算法原理及应用[M].北京:科学出版社,2005. [16]高尚,汤可宗,杨静宇.一种新的基于混合蚁群算法的聚类方法 [J].微电子学与计算机,2006,23(12):38-41.

[17]刘赏.结合密度思想的蚂蚁聚类算法[D].天津:河北工业大学, 2003.

[18]邹远强,李国徽,赵梓屹.基于遗传和蚁群算法融合的聚类新方 法[J].科学技术与工程,2006,6(23):4700-4704.

的结果作进一步的处理。根据分析，我们去掉连通域小于20 个像素的斑块，最终可以得到比较完整的道路网(如图7所示)。 图7中存在部分道路断裂的现象，这需要在今后的工作中进 一步完整连接。为了验证本方法的适用性，我们另选了两幅 遥感图像进行实验(如图8~图13所示)。从图10和图12中可 以看出比较完整的提取出了公路的轮廓，这进一步验证了本 方法具有一定的实用意义。 3结束语

本文提出了一种基于区域生长型分水岭算法的卫星道路

提取方法。实验表明，该算法能有效地将道路提取出来，具有 一定的实用意义。下一步的工作将考虑将数学形态学的部分 知识运用于图像的预处理或后期对结果的优化处理中，已得 到更完整的道路网络。 参考文献:

[1]HU Xiang-yun,ZHANG Zu-xun,ZHANG Jiang-qing.An ap- proach of semiautomatic road extraction from aerial images based on template matching and neural network[C].Interna- tional Achives of Photogrammetry and Remote Sensing,XXX III(Part B3).Amsterdam:Amsterdam University,2000:994-999. [2]GRAU V,MEWES AUJ,ALCANIZ M.Improved watershed transform for medical image segmentation using prior informa- tion[J].IEEE Transaction on Medical Imaging,2004,23(4): 447-458.

[3]Bieniek A,Moga A.An effiecient watershed algorithm based on connect components[J].Pattern Recognition,2000(3):907-716.

[4]HIEU T,MARCEL M,REIN V.Watersnakes:Energydriven water- shed segmentation[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2003,25(3):330-342.

[5]陈小梅,倪国强,刘明奇.基于分水岭算法的红外图像分割方法 [J].光电子·激光,2001,12(10):1072-1075.

[6]冈萨雷斯.数字图像与处理[M].北京:电子工业出版社,2005: 315-318.

[7]丁伟杰,范影乐,庞全.一种改进的基于分水岭算法的粘连分割 研究[J].计算机工程与应用,2007,43(10):70-72.

[8]张恒,雷志辉,丁晓华.一种改进的中值滤波算法[J].中国图象图 形学报,2004,9(4):408-411.

[9]马爵红,张宇.基于形态滤波器组的图像分割预处理算法[J].计 算机工程,2003,29(19):154-155.

[10]贺兴华,周媛媛,王继阳,等.MATLAB7.X图像处理[M].北京:人 民邮电出版社,2006:108.

[11]卢官明.区域生长型分水岭算法及其在图像序列分割中的应 用[J].南京邮电学院学报,2000,20(3):51-54. 图8原始图像图 9分水岭变换 道路提取结果 图10最后得到的 道路结果

图11原始图像图 12分水岭变换 道路提取结果 图13最后得到的 道路结果

(上接第4988页)

本文来源：https://www.bwwdw.com/article/2jo8.html