探测信息模型支持下的点注记配置方法

乔俊军，胡冯伟，张海文,2

(1. 武汉大学测绘学院，湖北 武汉 430079； 2. 深圳市勘察研究院有限公司，广东 深圳 518026)



探测信息模型支持下的点注记配置方法

乔俊军1，胡冯伟1，张海文1,2

(1. 武汉大学测绘学院，湖北 武汉 430079； 2. 深圳市勘察研究院有限公司，广东 深圳 518026)

摘要：针对点注记自动配置问题，首先对注记备选位置及其优先级进行了分析与研究，提出了一种自主探测算法，该方法的探测信息模型顾及了背景要素压盖、注记的指代明确、配置均匀，以及尽量配置到所属的行政区划等原则；在此基础上，通过初始配置获得全局较优注记位置，再配置获得局部最优注记位置，冲突压盖检测获得全局最优注记位置；对两个试验样区进行了注记配置试验，结果表明在注记难度增加的情况下，该方法仍能获得较好的注记效果。

关键词：压盖权重；备选位置；探测信息量；探测区；注记配置

随着国家1∶100万、1∶50万、1∶25万基础地理信息数据库建设完毕，为自动生产等比例尺或通过制图综合生产小比例尺地图创造了有利条件。然而注记配置尤其是点注记配置制约了地图的生产效率。究其原因，一是注记配置的工作量很大，约占整个地图生产的59%[1];二是注记配置看似是一项再简单不过的工作，但随着对问题认识的深入，其配置过程中的复杂性、多变性、实施的灵活性及得到满意成果的困难性成为了制图自动化的难点之一。因此注记自动配置便成为制图自动化的一个亟待解决的问题。

20世纪70年代，Yoeli最先开展了注记自动配置研究[2]，40多年来，国内外学者针对注记自动配置研究已经取得了不少研究成果。在点注记配置方面，游涟根据最小注记尺寸，将整个地图空间分成若干地图子空间，巧妙地将注记之间的压盖问题转化为子空间的重叠问题，使得注记配置的质量优于当时所见的文献[3]。樊红基于神经网络模型求取点要素注记配置的最优解，有效克服了传统冲突-回溯法效率不高的问题[4]。Yammoto成功地将禁忌搜索(TS)算法应用于点注记自动配置的过程，并取得了较好的注记效果[5]。郑春燕通过引入地图目标等级，加入注记本文不能压盖点要素这一限制条件，建立了一个更为完善的目标函数，对TS算法进行了完善，并通过试验证明了TS算法比当时的一些智能优化算法效果显著[6]。彭珊鸰将蚁群算法引入到点注记配置的过程中，并证明了此法具有较高的搜索效率，基本解决了注记的冲突问题。

但目前所见的点注记配置算法，包括目前最好的maplex智能标注系统，都较少考虑注记的指代明确、配置均匀及注记尽量配置到所属的行政区划内等规则。因此，本文提出一种自主探测算法，该方法的探测信息模型可顾及背景要素压盖、注记的指代明确、配置均匀及尽量配置到所属的行政区划等原则；通过利用该模型，计算各备选位置的探测信息量，结合备选位置的优先级，确定最终注记位置。

一、点注记配置理论

关于点注记配置规则，文献[7—8]已进行了详细介绍，下面重点探讨注记备选位置及其优先级问题。

1. 注记备选位置

Francois[8]将注记配置算法的流程分为3步：①搜索注记备选位置；②对注记备选位置进行评价；③选择最优注记位置。从这3步中可以看出，注记备选位置直接关系到注记质量的优劣。

若注记备选位置与点要素可接受的最近距离为r1，可接受的最远距离为r2，则形成的备选区如图1所示。

图1　注记备选区

注记备选区可看成由无数个圆组成的集合，这些圆又称为备选圆。在计算机中，与利用有限个点描述一段光滑曲线的原理相似，本文也利用有限个备选位置来描述备选圆，如图2所示。

2. 备选位置优先级

一个备选圆可由多个备选位置来描述，备选位置越多，备选圆描述得越精确。传统的8个备选位置较难精确描述备选圆，本文对其进行了扩展。以3字数注记为例，用40个备选位置来描述备选圆，其优先级顺序如图2所示。

图2　备选位置优先级

图2(b)中，(5)～(12)备选位置是在图2(a)(2)、(3)备选位置的基础上进行水平平移的结果，每次平移半个字符。各备选位置的优先级遵循以下原则：

1) 半径小的备选圆上的备选位置优先级高于半径大的备选圆，因为前者的备选位置与点要素距离更近，指代性更好。

2) 在同一备选圆上，备选位置与基本备选位置越近，优先级越高，如(13)和(21)备选位置，因(13)更接近第一备选位置，因此(13)的优先级更高。

3) 在同一备选圆上，假设存在两个备选位置B1和B2，基本备选位置J1和J2，并且B1与J1的接近程度和B2与J2的接近程度相同，若J1的优先级高于J2，那么B1的优先级高于B2。如图2中(13)和(15)备选位置。

4) 在同一备选圆上，若两个备选位置与同一基本备选位置的接近程度一样，那么看其与其他基本备选位置的接近程度，如(13)、(14)备选位置，两者与第一基本备选位置的接近程度一样，但由于(13)更接近第二基本备选位置，因此(13)的优先级更高。

二、自主探测算法

1. 地图要素空间分布量化

根据注记规则，在保证注记指代清晰的前提下，绝大部分要考虑注记与要素的压盖问题。因此，本文以赋予压盖权重的方式将地图各要素的重要性进行量化。假设经纬线要素的压盖权重W=1，省界的压盖权重W=10，那么注记与10条经纬线压盖等同于与1条省界压盖，这表明压盖了10条以下经纬线的注记位置要优于压盖了1条省界的注记位置。当某个要素的压盖权重为0时，注记可以任意压盖该要素。

地图类型不同，则权重设置有所不同，同一地图，不同的压盖权重，其注记质量也会不同。因此，如何给每个图种确定唯一的权重，以及如何实现注记质量的最大化，假设最大权重为Wmax，最小权重为Wmin，权重设置应符合以下原则：

1) 对于绝对不能压盖的要素，其压盖权重应设为最高Wmax。

2) 对于需要考虑压盖的，且重要性最低的要素，其压盖权重应设为最低Wmin。

3) 其他需要考虑压盖的要素权重，应介于Wmax与Wmin之间，具体数值依赖于制图目的、要素内容等条件。

2. 探测信息模型

(1) 注记初始配置的探测信息模型

假设以某一点要素P为中心，以R为搜索半径，搜索到n个点要素，P点到这n个点的距离分别为si(i=1,2,…,n)，如图3(a)所示。同时P点第j个备选位置(矩形)的几何中心到这n个点的距离分别为li，如图3(b)所示。那么该备选位置的探测信息量(detection information)DIj为

(1)

式中，WP为搜索到点的压盖权重；K为备选位置探测到的注记种类数；mZ,i为备选位置探测到的第i类注记的数量；W为相应的压盖权重。

图3　初始配置的探测信息量

(2) 注记再配置的探测信息模型

假设存在一点要素P，点P的第j个备选位置上存在第一、二、三探测区A、B、C，A探测非注记要素，B探测注记要素，C探测点要素，如图4所示(夸张显示)。则该备选位置的探测信息量DIj为

(2)

图4　三探测区

式中，K1为A探测到的线、面(不包括行政区划)种类数之和；mi为相应的第i类要素的个数；K2为B探测到的注记种类数；mB,i为相应的第i类注记的个数；K3为A探测到的点种类数；K4为C探测到的点种类数；mA,i和mC,i分别为相应的第i类点要素的个数；W为相应要素类的压盖权重，其中Warea为行政区划的压盖权重；d为降权系数，d>1；Sj为A与当前点要素所在的行政区划相交的面积；SA为A的面积；[]表示是否添加该项值。d值作用如图5所示。

图5　d值的作用

p1、p2、p3为同类点要素，图5(a)中的两个图形为p1点第二备选位置上的A、C探测区，图5(b)中的两个图形为p1点第一备选位置上的A、C探测区。若d≤1，则DI1≤DI2，则p1点的第一备选位置为最优注记位置，致使p1点的注记压盖p3点，如图5(b)所示。这是不允许的。因此令d>1，即降低C探测区探测到的点要素压盖权重，则DI1>DI2，从而能够使p1点的注记配置到第二备选位置上，避免压盖点要素。

3. 自主探测算法

算法的基本思想是二次配置加一次检测。

初始注记配置即根据式(1)计算各备选位置的探测信息量，确定初始注记位置。由式(1)可知，li越小，DIj就越大，因此初始注记配置可使得注记最大程度地远离密集的点要素，从而提供了一个较好的初始注记位置。

注记再配置即根据式(2)计算各备选位置的探测信息量，确定局部最优注记位置，其中第一探测区探测非注记要素，范围最小，其主要作用是顾及要素压盖，保证图面清晰；第二探测区探测注记要素，范围较大，其主要作用是确保注记不拥挤，如图6所示，如果图6(a)中“湾里区”位置的第二探测区探测到其下方很近的距离存在其他注记，从而能够避免图6(a)实现图6(b)的注记效果；第三探测区探测点要素，范围最大，其主要作用是确保注记指代准确，如果图6(c)中“金城镇”位置的第三探测区探测到其右侧很近的距离存在其他点要素，从而能够避免图6(c)实现图6(d)的注记效果。

由于点要素密集程度未知，注记再配置并不能完全保证零冲突及注记不压盖点要素，因此还需进行冲突压盖检测。

自主探测算法流程如下：

1) 选择考虑压盖的地图要素，并根据压盖权重的设置原则进行权重设置。

图6　第二、三探测区作用

2) 设置探测参数：一是点符号尺寸，这与地图设计有关；二是注记初始配置中的搜索半径R；三是注记再配置中的d值。

3) 注记初始配置：首先选取第一个点要素，根据备选位置的优先级，在第一备选位置上只生成第一探测区，第一探测区的尺寸由下式计算得到(单位为m)

(3)

式中，H为探测区的高度；W为探测区的宽度；3.527 78×10-4为ArcGIS中1∶1比例尺的字号为1的文字的高度；z为注记字大；scale为地图比例尺;n为注记字数。

然后根据搜索半径R搜索点要素，并利用式(1)计算当前备选位置的探测信息量。当计算出当前点要素所有备选位置的探测信息量后，选取其中最小值。若该值唯一，相应的备选位置就是初始注记位置；若不唯一，相应优先级最高的备选位置就是初始注记位置。其他点要素依次类推。

4) 注记再配置：首先选取第一个点要素，并删除该点要素的初始注记。然后根据备选位置的优先级，在第一备选位置上生成第一、二、三探测区，接着通过空间分析探测地图要素，并利用式(2)计算当前备选位置的探测信息量。当计算出当前点要素所有备选位置的探测信息量后，选取其中最小值。若该值唯一，相应的备选位置就是局部最优注记位置；若不唯一，相应优先级最高的备选位置就是局部最优注记位置。3个探测区的形状如图7所示(夸张显示)。其中,D为最小点符号的外接圆直径，其他点要素依次类推。

5) 冲突压盖检测：首先选取第一个注记，通过空间分析判断该注记是否存在冲突或压盖了点要素。如果存在，则删除该注记，对相应的点要素进行注记再配置，过程同步骤4)；如果不存在，则保留该注记。直到对所有的注记都进行了冲突压盖检测。

图7　第一、二、三探测区

三、试验结果与分析

本文在ArcGIS Engine环境下对自主探测算法进行了试验。选择了两个试验样区，由于不同的选取资格，试验样区1注记保留到县级行政中心；试验样区2注记保留到镇级行政中心，且道路的分类更多。因此，随着试验注记密集程度的增大及注记环境的复杂，致使试验样区2的注记配置难度高于试验样区1。

试验中令最大压盖权重为100，最小压盖权重为2，具体见表1、表2。

表1　试验样区1的要素压盖权重

表2　试验样区2的要素压盖权重

注：经纬线的压盖权重为2。

1. 配置试验

(1) 试验样区1注记配置试验

试验样区位于108°06′E—116°24′E，28°39′N—33°40′N，比例尺为1∶210万，点要素及注记信息见表3。

表3　点要素及注记信息

试验目的主要是在考虑注记尽量配置到所属的行政区划内的条件下，将自主探测算法与maplex智能标注系统进行对比，配置结果如图8、图9所示。

图8　maplex智能标注系统的注记结果

图9　自主探测算法的注记结果

(2) 试验样区2注记配置试验

试验样区位于114°44′E—119°40′E，29°12′N—37°47′N，比例尺为1∶64万，点要素及注记信息见表4。

表4　点要素及注记信息

试验目的是在考虑注记指代明确、配置均匀的规则下，将自主探测算法与maplex智能标注系统进行对比，配置结果如图10、图11所示。

图10　maplex智能标注系统的注记结果

图11　自主探测算法的注记结果

2. 结果分析

1) 就试验样区1而言，相比于maplex智能标注系统的注记结果，自主探测算法能够尽量保证注记配置到所属的行政区划。以黄石市为例，作为地级行政中心，本应配置到所属的行政区划内，但maplex却配置到了黄冈市的区划内，这是不允许的；而自主探测算法做到了这一点，不仅配置到所属的行政区划内，还保证了最小程度的背景要素压盖，这使得注记配置较为合理。

在保证上述原则的基础上，该方法还能够使注记配置尽量均匀。以蔡甸区为例，作为武汉市中的一个县级行政中心，maplex的注记结果使得蔡甸区有近一半配置到了汉川市区划内，而且两县级行政中心注记显得较为拥挤，而自主探测算法就解决得较好。

2) 就试验样区2而言，相比于maplex智能标注系统的注记结果，自主探测算法能够尽量保证注记指代清晰，即注记与相应点要素的距离最近，且远离其他点要素，从而视觉上能够迅速分辨出哪个注记指代哪个点要素，从而达到指代清晰的目的。以对比区域中瓜洲镇和世业镇为例，在maplex的注记结果中，两注记与其之间的点要素的接近程度差不多，较难迅速分辨所属关系，致使注记配置的指代性不明确，注记质量不高。而自主探测算法就解决得较好，很容易分辨注记的所属关系，而且避免了背景要素压盖，使得其指代较为明确，注记质量较高。

与此同时，相比于maplex，自主探测算法的注记结果显得更为均匀，以永安镇和真武镇为例，maplex虽然使得两注记都避免了背景要素，但较为拥挤，不太美观。而地图注记配置并不意味着没有压盖就是最好，还要考虑注记之间的均衡性。自主探测算法的注记结果就较为合理。

同时，试验结果中也存在个别不理想的注记配置，如图11中镇江市与江心镇相互冲突。

综上所述，虽然maplex智能标注系统是目前最好的注记配置系统，但仍缺乏考虑一些注记规则，尤其是注记指代清晰、配置均匀、尽量配置到所属的行政区划内等规则。而自主探测算法不仅考虑了这些规则，试验表明其注记质量优于maplex，而且该方法在不同的注记环境下仍可获得较为满意的注记结果。

需要说明的是，目前要素压盖权重的设置仍依赖于制图经验，其科学依据还有待进一步研究，但在同一幅图上，如果把握了地图中要素的重要性程度，即使同一要素的权重设置有所差别，其注记结果也不会有太大差别。

四、结束语

本文首先对注记备选位置及其优先级进行了探讨和分析，通过试验证明了顾及背景要素压盖、注记指代明确、配置均匀及尽量配置到所属的行政区划内等原则的探测信息模型能够大大提高注记质量；并且随着注记难度的增加，自主探测算法仍能获得很好的注记效果，这对数字地图制图效率的提高具有一定的理论和实用价值。同时考虑到权重设置的重要性，下一步将研究权重设置的科学依据及其对注记结果的影响。

参考文献：

[1]杜世宏，王乔，杜道生，等.地名注记自动配置研究[J].地理学与国土研究，2002，18(4)：14-18.

[2]YOELI P. The Logic of Automated Map Lettering[J]. The Cartographic Journal，1972(9):99-108.

[3]游涟，何宏星.地图点状符号及注记的自动配置[J].测绘学报，1993，22(4)：304-308.

[4]樊红，张祖勋，杜道生，等. 基于神经网络模型求取注记配置最优解[J].武汉测绘科技大学学报，1998，23(1)：32-35.

[5]YAMAMOTO M, CAMARA G, LORENA L A N. Tabu Search Heuristic for Point-Feature Cartographic Label Placement[J]. GeoInformatica， 2002， 6(1):77-90.

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

[7]樊红，杜道生，张祖勋.地图注记自动配置规则及其实现策略[J].武汉测绘科技大学学报，1998，24(2)：154-157.

[8]娄倩，张慧霞，郭建忠，等. 地图注记质量评价模型的建立[J].测绘科学，2012，37(1)：125-127.

[9]张红武，张友纯，谢忠，等.用遗传算法解决点状要素的自动注记问题[J].计算机工程与应用，2003(7)：68-71.

[10]IMHOF E. Positioning Names on Maps[J]. The American Cartographer，1975，2(2):128-144.

[11]CHIRIÉ F. Automated Name Placement with High Cartographic Quality: City Street Maps [J]. Cartography and Geographic Information Science，2000，27(2): 101-110.

Point Annotation Labelling Based on the Model of Detecting Information

QIAO Junjun,HU Fengwei，ZHANG Haiwen

收稿日期：2015-09-02； 修回日期： 2015-11-02

作者简介：乔俊军(1961—)，男，高级工程师，主要从事地图学与地理信息工程方面的教学及研究工作。E-mail：623083313@qq.com

中图分类号：P28

文献标识码：B

文章编号：0494-0911(2016)06-0035-06

引文格式： 乔俊军，胡冯伟，张海文. 探测信息模型支持下的点注记配置方法[J].测绘通报，2016(6)：35-40.DOI:10.13474/j.cnki.11-2246.2016.0185.