EN中文

地球信息科学学报 >

2015 , Vol. 17 >Issue 8: 902 - 908

DOI: https://doi.org/10.3724/SP.J.1047.2015.00902

地图点要素注记自动配置中聚类分组的蚁群算法应用

  • 周鑫鑫 ,
  • 孙在宏 ,
  • 吴长彬 , * ,
  • 丁远
展开
  • 南京师范大学虚拟地理环境教育部重点实验室,南京 210046
*通讯作者：吴长彬(1977-),男,福建仙游人,副教授,研究方向为GIS与土地信息系统。E-mail:

作者简介：周鑫鑫(1991-),男,安徽芜湖人,硕士生,研究方向为不动产信息系统及地图制图。E-mail:

收稿日期: 2014-12-15

  要求修回日期: 2015-03-10

  网络出版日期: 2015-08-05

基金资助

国家自然科学基金项目“不动产统一登记驱动下的地籍混合维度空间数据表达模型研究”(41471318)

收起

Automatic Label Placement of Point Feature: Using Ant Colony Algorithm Based on Group Clustering

  • ZHOU Xinxin ,
  • SUN Zaihong ,
  • WU Changbin , * ,
  • DING Yuan
Expand
  • Key Laboratory of Virtual Geographic Environment, Ministry of Education, Nanjing Normal University, Nanjing 210046, China
*Corresponding author: WU Changbin, E-mail:

Received date: 2014-12-15

  Request revised date: 2015-03-10

  Online published: 2015-08-05

Copyright

《地球信息科学学报》编辑部 所有
Fold

摘要

大规模点要素注记自动配置问题是地图注记的难点之一,主要受限于时间效率和注记配置质量。针对该问题,本文首先提出一种椭圆形多方位多级注记待选方位配置方案,使其参数化、多元化。其次,结合点要素空间分布特征,提出一种以聚类分组的蚁群算法,并讨论和优化核心参数,实现大规模点要素的注记快速配置。实验表明,该算法计算效率明显提升,算法性能稳定。针对注记密度在5%~30%随机分布点要素的地图,其相比传统蚁群算法算法效率提高73.2%;同时,该算法的注记结果质量比传统蚁群算法注记结果质量好,注记适应度提升8.0%。实验采用抚顺县集体土地所有权界址点数据进行验证,结果表明效率提升86.7%,且注记适应度提升14.6%。本算法适用于点要素规模大、点簇疏密变化差异大的点要素注记自动配置问题的快速求解。

关键词： 点要素注记; 聚类分组; 蚁群算法; 注记配置方案; 注记适应度评价函数

本文引用格式

周鑫鑫 , 孙在宏 , 吴长彬 , 丁远 . 地图点要素注记自动配置中聚类分组的蚁群算法应用[J]. 地球信息科学学报, 2015 , 17(8) : 902 -908 . DOI: 10.3724/SP.J.1047.2015.00902

Abstract

The problem of Large-scaled Point Feature Cartographic Label Placement (LS-PFCLP) is one of map labeling difficulties, which is mainly limited by time efficiency and labels’ quality. Changing this plight will accelerate the application development of Intelligent Cartography. The article firstly contraposes the form simplification of traditional potential label position scheme and puts forward an oval multi-orientations and multi-levels cartographic potential label position scheme to make a better conformation of the potential label position scheme to the actual demand, and make it parameterized and multiplex. Secondly, the article combines the space distribution features of point features to adopt an Ant Colony Algorithm based on cluster grouping (C-ACA), whose core framework is decreasing the large scale of points to plural mini-scaled point collections through DBSCAN clustering, then integrating Ant Colony Algorithm to C-ACA. In the process of C-ACA’s implementation, we discuss and optimize the core parameters, such as Eps and MinPts of DBSCAN, ant colony size parameters (Pa、ηcj、τcj、Pcjb), and evaluation function of E(bc), to achieve Large-scaled Point Feature Cartographic Label Placement. Experiments show that C-ACA has a great contribution to the efficiency improvement of LS-PFCLP. When compared, with two cases of random points tests and one realistic boundary points case, with techniques such as Ant Colony Algorithm (ACA), the C-ACA has been proven to be an efficient choice, with better performance in both efficiency and quality. In case 1, The C-ACA improves the efficiency by 73.2 percent than normal-ACA, when the label density falls in between 5% and 30%. Moreover, the altered resultant label’ quality is 8.0 percent better than before. In case 2, the result of C-ACA has justified the stability presentation. In case 3, we have used this algorithm to process the boundary points of the collective land ownership data of Fushun county in China, which has improved the efficiency by 86.7% and the quality by 14.6% with outstanding performance. We concluded that the improved algorithm is applicable to LS-PFCLP with points that having massive quantity and greater variations of clustering density.

Key words： the point feature cartographic label; cluster grouping; ant colony algorithm; label cartographic pattern; the label fitness evaluation function

1 引言

地图注记是传递地图信息的主要方式之一[1]。点要素注记配置问题（The Point Feature Cartographic Label Placement Problem,PFCLP）,是地图注记配置问题的重要组成部分之一[2]。Joe Marks证明PFCLP问题是NP-hard问题[3]。NP-hard是在多项式时间内只能找到近似解的问题,且当问题规模增大时,问题求解的复杂度急剧增加。目前,PFCLP问题研究主要围绕降低注记冲突和提升注记质量展开,国内外学者针对点要素注记配置做了诸多研究,主要有：聚类搜索算法、模拟退火算法、神经网络算法、禁忌搜索算法、遗传算法、回溯法,以及网格算法等[4-10],对于“提升PFCLP配置效率”问题研究较少。Ribeiro和Lorena的研究团队提出了一种采用拉格朗日松弛解进行点要素冲突图构建,并加以运用[11-12]。国内学者郭庆胜提出在地图要素稠密时,可以某种标准进行聚类分析提升效率[13]。樊红结合点要素空间分布特征,提出了最大注记相关组的思路,并将全局遗传算法搜索转变为分块遗传算法搜索,以降低问题计算复杂度。针对大规模点状要素注记配置效率低下的问题,本文融合密度聚类和蚁群算法,实现了大规模点要素注记优化注记配置,提升问题求解速度和注记结果质量。

2 注记配置方案

点要素注记配置方案的注记待选方位生成多采用 n 方位配置方案 ( n ∈ N + ) ,一般情况下n常取4、8、16,且以右上方为最佳待选方位,如图1所示。该配置方案简洁、明了,符合读图习惯,但没有给出数学表达方式且形式单一。本文提出一种椭圆形多方位多级注记待选方位配置方案数学公式,该公式符合注记外接矩形长、宽一般不相等,且注记距点要素越近可配置注记面积越小。第i个点要素坐标位置 ( X i , Y i ) ,则其位于第L级的第k个注记待选方位中心点 ( X iL k , Y iL k ) 如式（1）所示。
X iL k = X i + w i sc os 2 πk L d Y iL k = Y i + h i s sin 2 πk L d k ∈ [ 1 , L ] （1）
式中, w i 为i点要素的注记宽度; h i 为i点要素的注记高度;s为L级的偏移量, s ∈ R ; L d 为L级的待选方位数, L d ∈ N + 。参数s、 L d 可根据地图点要素复杂程度和制图者制图经验来选定。
Fig. 1 The 4 directions’ cartographic pattern

图1 4方位注记配置示意图

图2为椭圆形2级多方位配置示意图,参数选定规则为{L=1:s=0.7, L d =4; L=2:s=1.4, L d =8}。此外,当 L 增大时,可采用注记引线加以标示要素与注记关联。该方法实现参数完备化,统一了点要素注记配置方案,符合地图制图规律和制图美学。
Fig. 2 The oval multi-orientations and multi-levels’ cartographic annotation-allocation pattern

图2 椭圆形多方位多级注记待选方位配置方案示意图

3 基于聚类分组的蚁群算法

3.1 算法设计思想

点要素通常随机分布,在地理空间上表现为地理要素分布疏密不均,形成点簇、单独点。点簇之间相互独立,且注记位置配置互不干扰。本文按照一种空间密度的聚类方法——DBSCAN算法,（Density Based Spatial Clustering of Applications with Noise）进行聚类分组,将问题空间划分成多个子问题空间,逐一求出近似解。DBSCAN算法将空间点集中每点以给定半径（ Eps ）,搜索大于给定数目（ MinPts ）的点集,构成簇和噪声[14]。其优点是聚类速度快,可生成空间中任意形状的簇;运用难点是确立 Eps 、 MinPts 。
最优组合点注记配置方案近似解求解选取群体智能算法中的蚁群算法（Ant Colony Algorithm）。蚁群算法是基于种群的启发式仿生进化系统[15-16]。蚁群算法的优点在于：正反馈机制、蚂蚁个体简单、采用信息素进行通信,适用于点注记空间优化组合问题[17-18]。但该算法为全局搜索,当问题规模增大时,求解效率急剧下降,不符合大规模点要素问题的解决。结合DBSCAN算法,蚁群算法的缺陷就可有效地得以改善,蚁群算法在各子问题空间中运算时,遍历规模小,可快速收敛。
求解过程中,会形成多个近似解,衡量近似解的质量需确定注记评价函数,子问题空间的评价函数值最优的解将作为子问题空间结果解,各子问题空间结果解组成最终的结果解。本文参照Inhof提出的规则,从注记间冲突、注记和地理要素间压盖、注记方位优先级,以及要素和注记关联性的影响方面评价注记质量[19-20]。并采用注记冲突对注记质量影响最大,其次是注记压盖、要素与注记关联性,最后是注记方位优先级的准则设定各影响权重。此外,本文针对各核心指标（给定半径 Eps 、给定数目 MinPts 、蚁群规模 P a 等）进行了分析。

3.2 算法构建流程

（1）初始化。计算注记宽度和高度,根据式（1）计算点要素注记待选方位;初始化点要素待选注记方位的优先级值和信息值。
（2）聚类分组。采用DBSCAN算法,设置 Eps 和 MinPts ,执行聚类分组;设形成N个点簇、M个噪声点（即独立点要素）。
（3）标注独立点要素注记。根据该点注记方位优先级值,选取优先级值最大的方位存入最终结果集FinalResultList中。
（4）标注点簇中点要素注记。
① 蚁群构建。遵循一个点簇建立一个蚁群且蚁群规模和点簇中点数相同的原则,第a（ a ∈ [ 1 , N ] ）个点簇中有 Q a 个点要素,与之对应的蚁群规模为 P a , P a = Q a ,共建立N个蚁群。
② 蚂蚁搜索。遵循每一只蚂蚁要随机经过对应点簇中点要素且要完全遍历所有点要素的原则,第a个点簇对应的蚁群中的蚂蚁 An t b ( b ∈ [ 1 , P a ] ) , An t b 随机选取a点簇的 Allowe d An t b 的一点,记为 c ( c ∈ [ 1 , Q a ] ) 。 Allowe d An t b = { Q a - tab u An t b } 表明 An t b 允许选址的点集合,其中, tab u An t b 存储 An t b 已经过的城市。
③ 转移概率计算和更新c的信息值。根据点c所对应的待选注记方位优先级值 η cj 和信息值 τ cj ( j ∈ [ 1 , sum ( L d ) ] ) ,采用式（2）计算转移概率 P cj b 。选取 Max ( P cj b ) ( j ∈ [ 1 , sum ( L d ) ] ) 所对应的注记方位为靶注记方位。判断靶注记方位的注记冲突情况,更新靶注记方位信息值,将靶注记方位存入临时结果集中。
P cj b = [ τ cj ] α ∙ [ η cj ] β ∑ j = 1 sum ( L d ) [ τ cj ] α ∙ [ η cj ] β , j ∈ Allowe d An t b 0 , 其他 （2）
④ 修改 tab u An t b 。将点c置入 tab u An t b 。判别 Allowe d An t b 是否为空：若是则表示蚂蚁 An t b 完成该点簇中所有点要素的遍历,记录 An t b 整个遍历过程的冲突数量,用于注记质量评价;若否则返回②,直至完全遍历。
（5）注记质量评价。采用注记质量评价函数 E ( b ) （式（3））评价 An t b 所遍历的点要素集合的注记质量,选取 Max ( E ( b ) ) 对应的结果集存入FinalResultList。其中, E ( bc ) （式（4））表示 An t b 遍历到的点c的单点注记评价函数。
E ( b ) = ∑ c = 1 Q a E ( bc ) Q a （3）
E ( bc ) = w 冲突 E 冲突 ( ic ) + w 位置 E 位置 ( ic ) + w 关联度 E 关联度 ( ic ) （4）

3.3 核心指标的确立

（1）Eps和MinPts
DBScan密度聚类可形成任意形状的簇,适用于PFCLP问题需求。DBScan密度聚类难点之一是确立合适的搜索半径Eps[21-22]。当注记待选方位区域在空间上不重叠时,点要素之间将不存在影响,视为无关联,等价于DBScan密度聚类中的直接密度不可达。由式（1）取最大偏移量值计算得改进Eps的形式： | X 1 - X 2 ≤ 3 w s max 4 AND | Y 1 - Y 2 | ≤ 3 h s max 4 ,其中, s max 为最大偏移量。另外, MinPts 取1,表示只要一点要素在另一点要素领域中,即为核心点。
（2）蚁群规模 P a
蚁群规模 P a 的确立是蚁群算法的难点之一,确立的标准受问题集合复杂度的影响。本研究中,问题集合复杂度同点簇中要素个数呈正比关系,即点簇中点要素 Q a 越大,表明点要素的注记相互间干扰性大、影响越复杂,则解决问题所需的蚂蚁规模越大。故确立 P a = Q a 。
（3） η cj 、 τ cj 及 P cj b
点c所对应的待选注记方位优先级值 η cj 和信息值 τ cj ( j ∈ [ 1 , sum ( L d ) ] ) 在算法第（1）步初始化时,赋初始值,其中, η cj 依据方位优先级从大至小排列,最大值为100,递减量为1; τ cj 统一赋值为10。在算法第（4）步的③步中,更新 τ cj 的规则定为：冲突则减3,不冲突则加2[17]。另外, P cj b 计算中,因 w 冲突 > w 位置 ,为体现出该权重关系,取 α = 0.4 ; β = 0.6 。
（4）评价函数 E ( bc )
式（4）的取值将很大程度影响注记结果,此处对本研究取值加以阐明,其中, w 冲突 = 100 , w 位置 = 1 , w 关联度 = 10 ,此外, E 冲突 ( ic ) 、 E 位置 ( ic ) 、 E 关联度 ( ic ) 如式（5）-（7）所示。
E 冲突 ( ic ) = 1 ，有冲突 0 , 无冲突 （5）
E 位置 ( ic ) = η cMax - η ci （6）
E 关联度 ( ic ) = Dis tan c e ( ic ) Dis tanc e （ Max ） （7）
式中, η cMax 为待选注记优先级最大值; η ci 为所选定的待选注记方位i的优先级值; Dis tan c e ( ic ) 为所选定的待选注记方位i与对点要素c的距离; Dis tan c e （ Max ） 为待选注记与对应点要素c的最大距离。
Fig. 3 Flow diagram of the algorithm

图3 算法流程图

4 点要素注记自动配置的算法实验

地图注记密度 ρ 是指所有要素所占面积之和与图幅面积的比值,用于描述地图注记的负载程度。一般情况下, ρ = 12 % 为适宜密度, ρ = 35 % 为极限注记密度,已无法阅读[23]。本算法实验设计为3组,实验1分析 ρ = { 5 % 、 10 % 、 15 % 、 20 % 、 25 % 30 % 时注记质量和效率的相比传统蚁群算法的改进结果,如图4所示;实验2分析算法标注的稳定性,采用6组随机 ρ = 20 % 实验数据分析结果;实验3以抚顺县集体土地界址点数据为实验数据,分析该算法实际运用性能,如图5所示。实验1、2指定图廓尺寸为493 m×629 m,注记点位和注记字符串以随机函数生成,点规模{318,636,954,1272,1590,1908};实验3数据选取抚顺县集体土地所有权确权界址点数据,点规模8390个。为便于实验对比,注记配置方案采用{L=1, s=0.7, L d =4}。
Fig. 4 Illustration of experimental data 1

图4 实验1数据示意图

Fig. 5 Illustration of experimental data 3

图5 实验3数据示意图

通过3组实验得出实验结果数据统计表（表1）。A算法即基于聚类分组的蚁群算法,B算法即传统蚁群算法, ρ 即注记密度（%）,A1即点簇数量（组）, T AS 即A算法的总耗时（s）, F A 即采用A算法后的注记结果的适应度评价函数值, T BS 即B算法的总耗时（s）, F B 即采用B算法后的注记结果的适应度评价函数值, ( T BS - T AS ) / T BS 即A算法与B算法效率提升比（%）, ( F B - F A ) / F B 即A算法与B算法提升比（%）。
Tab. 1 The statistical result of the experimental data

表1 实验结果统计表

序号 ρ(%) 点数 A算法 B算法 (TBS-TAS)/TBS (FB-FA)/FB
A1 TAS FA TBS FB
实验1 1 5 318 63 0.38 432 3.06 436 87.58 0.92
2 10 636 132 1.10 2034 12.22 2168 91.00 6.18
3 15 954 163 4.55 3774 26.49 4296 82.82 12.15
4 20 1272 138 10.27 8609 46.36 9762 77.85 11.81
5 25 1590 95 24.92 15 998 67.40 17 187 63.03 6.92
6 30 1908 50 60.12 27 041 95.49 29 068 37.04 6.97
实验2 7 20 1272 124 13.32 9184 49.41 9722 73.04 5.53
8 20 1272 127 12.45 8604 49.64 8883 74.92 3.14
9 20 1272 129 12.64 7878 49.34 8805 74.38 10.53
10 20 1272 138 11.04 8609 46.78 8626 76.40 0.20
11 20 1272 150 12.33 7672 49.36 7794 75.02 1.57
12 20 1272 129 12.66 8457 48.29 10 370 73.78 18.45
实验3 13 0.7 8390 1077 247.60 53 543 1868.22 62 696 86.75 14.60
实验1表明：当点要素注记密度增加时,2种算法总耗时 T AS 、 T BS 都随着增大,如图6所示,但总体表现为A算法总耗时 ( T AS ) 明显低于B算法总耗时 ( T BS ) 。由 A 1 变化可以看出,随着 ρ 增大,点簇数量先增加后减少,表明原有噪声点之间,随 ρ 增大而密度可达,点簇数量增加,之后因点簇间密度可达,点簇规模增大,而点簇数量减少。总之,当 ρ ∈ ( 0,30 % ] ,A算法效率平均提升73.2%,效率提升明显。另外,采用A算法后的注记结果其适应度评价函数值 ( F A ) ,均小于采用B算法后的注记结果的适应度评价函数值 ( F B ) ,即 F A < F B ,由适应度评价函数计算公式可知,其值越小,注记结果质量越好,表明A算法的得到的注记结果优于B算法,提升了注记结果质量,采用公式 ∑ F B - ∑ F A ∑ F B ,计算得出A算法注记结果质量提升8.0%。
Fig. 6 The total time-consumption contrast between A and B

图6 A算法和B算法总耗时对比图

实验2表明：在不同随机分布点要素的情况下,2种算法结果都具备稳定性。通过6组 ρ = 20 % 的实验数据,取结果平均值,A算法的效率比B算法提高74.6%,且注记质量提高7.0%,进一步验证实验1结果的稳定性与准确性。
实验3表明：A算法的实用价值。针对实验3,A算法的效率比B算法提高86.7%, T AS = 247.60 s, T BS = 1868.22 s,效率提升显著。同时,A算法注记质量比B算法提高14.6%,表明采用A算法得到的注记结果质量更好,图7为实验数据3注记配置结果。
Fig. 7 The label result of Fushun County boundary points based on algorithm A

图7 A算法的抚顺县界址点注记配置结果示意图

5 结论

基于聚类分组的蚁群算法计算效率明显高于传统蚁群算法,该算法对注记密度在5%~30%的点要素地图,较传统蚁群算法而言,平均效率提升73.2%,同时,注记质量提升了8.0%。基于聚类分组的蚁群算法对点要素注记配置尤其适用于点规模大、点簇疏密变化差异大的地图,能有效地降低算法迭代计算所耗费的时间和提升注记结果质量。值得进一步研究的是,确定评价各点簇的复杂度方法,从而进一步优化效率和注记质量;同时,将该算法拓展至三维PFCLP问题。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
龙毅,杜清运,邬国锋,等.数字地图制图向地理信息系统发展的若干问题分析[J].地图,2001(2): 1-4.

[2]
Alvim A C F, Taillard E D. POPMUSIC for the point feature label placement problem[J]. European Journal of Operational Research, 2009,192(2):396-413.

[3]
Marks J, Shieber S M.The computational complexity of cartographic label placement[M]. Cambridge, MA: Harvard University, Center for Research in Computing Technology, Aiken Computation Laboratory, 1991.

[4]
Rabello R L, Mauri G R, Ribeiro G M, et al.A clustering search metaheuristic for the point-feature cartographic label placement problem[J]. European Journal of Operational Research,2014,234:802-808.

[5]
杜维. 基于模拟退火算法的地图点状要素注记配置研究[D].武汉:武汉大学,2005.

[6]
Chen Y, Wang Z, Liu X.Automated point feature label placement using backtracking algorithm with an adjacent graph[C]. IEEE 18th International Conference on Geoinformatics, 2010:1-5.

[7]
郑春燕,郭庆胜,刘小利.基于禁忌搜索算法的点状要素注记的自动配置[J].武汉大学学报(信息科学版),2006,31(5):429-431.

[8]
Chen C, Zhang L, Ma J, et al.Adaptive multi-resolution labeling in virtual landscapes[J]. International Journal of Geographical Information Science, 2010,24(6):949-964.

[9]
樊红. 地图注记自动配置的研究[M].北京:测绘出版社, 2004.

[10]
吴长彬,闾国年,刘昱君.基于规则库和网格算法的土地利用现状图自动数字注记[J].测绘学报,2008,37(2):250-255.

[11]
Ribeiro G M, Lorena L A N. Lagrangean relaxation with clusters for point-feature cartographic label placement problems[J]. Computers & Operations Research, 2008,35(7):2129-2140.

[12]
Mauri G R, Ribeiro G M, Lorena L A N. A new mathematical model and a Lagrangean decomposition for the point-feature cartographic label placement problem[J]. Computers & Operations Research, 2010,37(12):2164-2172.

[13]
郭庆胜,王涛.稠密型点状地图要素注记自动配置的智能化渐进式方法[J].武汉测绘科技大学学报,2000,25(4):362-65.

[14]
Ester M, Kriegel H P, Sander J, et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]. In: Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining, 1996,96(34):226-231.

[15]
Colorni A, Dorigo M, Maniezzo V, et al.Distributed Optimization by ant colonies[C]. In: Proceedings of European Conference On Artificial Life, Paris, 1991:134-142.

[16]
Dorigo M, Birattari M.Ant colony optimization[M]. Springer US, 2010:36-39.

[17]
彭珊鸰,宋鹰,吴凡.基于蚁群算法的点状注记智能化配置[J].测绘科学,2007,32(5):80-81.

[18]
彭珊鸰. 地形图注记智能化配置研究[D].武汉:武汉大学,2010.

[19]
娄倩,张慧霞,郭建忠,等.地图注记质量评价模型的建立[J].测绘科学,2012,37(1):362-366.

[20]
Fan H, Zhang Z X, Du D S.Quality evaluation model for map labeling[J]. Geo-spatial Information Science, 2005,8(1):72-78.

[21]
孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.

[22]
Viswanath P, Babu V S.Rough-DBSCAN: A fast hybrid density based clustering method for large data sets[J]. Pattern Recognition Letters, 2009,30(16):1477-1488.

[23]
毛赞猷. 新编地图学教程(第2版)[M].北京:高等教育出版社,2008.

Options
文章导航

/

〈 〉