高质量、高效率地图制图是测绘公益性服务保障的重要任务，其基于不同比例尺的基础地理信息数据，按照制图规范，通过尺度转换、符号映射等，实现地理要素数据的快速符号化、自动注记及图廓整饰等。在数据尺度转换的过程中，尤其当比例尺缩小时，会造成地图负载量过大，引起符号冲突、注记压盖等问题，影响地图的可视化表达效果，导致读图困难^[1-2]。因此，在数据尺度转换的过程中，为了实现地图负载均衡，需要进行要素选取。居民地是地图上重要的地理要素，在中小比例尺地图中，对地图负载量影响较大的是不依比例的乡镇及村庄居民点。本文以不依比例居民点选取为例，研究基于最优信息熵约束的居民地点状要素选取方法。

针对居民点选取，现有的大多数算法如居民地空间比率算法、分布系数法、重力模型算法和圆增长算法等^[3-7]，属于基于点的增量式选取算法，优先保存地图上相对重要的点，但未考虑居民点的拓扑和空间分布特征。沈婕等^[8]基于路划网眼划分兴趣点来进行两者之间的拓扑关系维护。Zhou等^[9]提出了基于云平台点要素综合约束构建方法，在云计算环境下提高了点选择的效率。艾廷华等^[10]提出了基于Voronoi图的点群综合算法，很好地保持点群空间分布特征，并使点群的度量得到有效传递，但其未考虑点的属性意义。遗传算法和神经网络等智能算法^[11-12]将点群综合作为一个优化问题来处理，虽然能保持综合前后的密度对比以及排列规律，但是点群的属性特征并未考虑。因此，需要研究一种新的居民点选取方法，在保证行政级别优先性、地图拓扑一致性和度量合理性的同时，使地图的负载量在一定尺度下达到合理。

信息熵是一种信息量测度方法，本文使用信息熵对居民点选取结果的信息量进行度量，将信息熵与信息模糊度进行融合，基于最优信息熵约束对居民地点状要素进行选取，实现了维护拓扑一致性、级别优先性、度量合理性的居民地点状要素选取。总体思路是在居民点要素的选取中综合考虑居民点要素的行政级别属性、居民点与道路的相接关系及点群的空间分布特征。在语义关系约束下，优先保留行政级别高的居民点；在拓扑关系约束下，尽可能保留道路首端或末端的居民点，避免出现断头路；在度量关系约束下，整体上保留居民点群空间分布的疏密特征，在效果上通过最优信息熵约束，达到图幅信息量的负载均衡等。

1 约束定义

在居民点选取过程中必须维护其与邻近要素空间完整性约束，如空间关系的合理性、语义关系合理性、点群空间分布的合理性等。本文将居民点之间的空间完整性约束归结为最优信息熵约束、度量关系约束、语义关系约束与拓扑关系约束。

1.1   最优信息熵约束

Shannon^[13]提出了信息熵的概念，基于概率论建立了语法层次的信息量度量，将排除冗余后的平均信息量定义为信息熵；Sukhov^[14]采用统计采样的方法完成了地图信息量化测量工作，提出了符号信息熵的概念；Neumann^[15]提出了一种通过对偶图计算符号类型统计分布的拓扑信息熵计算方法；Li等^[16]提出拓扑信息熵、几何信息熵和专题信息熵的定量计算方法；Knopfli^[17]将地图符号感知的不确定性称为模糊度，解决了符号之间的感知相似性问题；Bjørke^[18]进一步定义了两个相邻地理要素值域为[0, 1]的感知相似度函数，成功地将信息论应用在地图综合领域，提出了一种基于熵的地图评估框架。

在居民点选取中，由于尺度的变化，从大比例尺到小比例尺，经过要素选取后，信息量必然减少，为确保地图尺度转换后的地图信息负载均衡，本文提出将最优信息熵作为一种约束条件来度量选取后的居民地点状要素信息量，利用居民地点要素的Voronoi图，计算每一个居民地点要素的空间分布概率及其与邻近点的相似度函数，进而计算选取后居民地点群的信息熵和信息模糊度，将居民地点群的信息熵减去信息模糊度得到该点群的有效信息量。有效信息量越大，说明信息模糊度越小。当有效信息量最大时，信息熵和信息模糊度的值达到最优匹配，称此信息熵为最优信息熵。

1.2   度量关系约束

在居民地点状要素选取中，点群的空间分布特征是点要素选取后需要保留的重要信息，一般利用点群密度来表示。点群密度可以定义为特定数目的居民点所占用的分布空间，为计算方便，本文将其转化为相邻点间的欧氏距离约束。在计算几何中，Delaunay三角网中的三角形的边是具有邻近关系的点对连接，表达了点的影响范围^[19-20]。本文基于Delaunay三角网计算居民点的一阶邻近点，居民点M_i与其一阶邻近M_i+1之间的欧氏距离计算公式为：

设$ {d}_{0} $为两个一阶邻近居民点无法分辨出的最大距离$ , $即当$ {t}_{i} $ < $ {d}_{0} $时，表示两个相邻点在视觉上无法分辨，可以认为在该比例尺下两个点在视觉上完全重合；设$ {d}_{1} $为可以分辨两个相邻点的最小视距，当$ {t}_{i}>{d}_{1} $时，两个相邻点在视觉上没有任何重叠，可以完全区分开。本文假定居民点选取后的目标比例尺为1∶500 000，制图规范规定居民点的符号大小为1.2 mm，因此为保证选取后的视觉效果，取$ {d}_{0} $=2 mm，$ {d}_{1} $=10 mm。

本文将Delaunay三角网确定的一阶邻近居民点间的距离D作为度量关系约束值，以$ {D}_{0}={d}_{0}\times \frac{500\mathrm{ }000}{1\mathrm{ }000\mathrm{ }000}=1\mathrm{ }\mathrm{k}\mathrm{m} $为初始值，以$ {D}_{1}={d}_{1}\times \frac{500\mathrm{ }000}{1\mathrm{ }000\mathrm{ }000}=5\mathrm{ }\mathrm{k}\mathrm{m} $为计算的上限值，不断迭代，取得最优信息熵所对应的D值即为最终的度量关系约束值。

1.3   语义关系约束

在居民地点状要素的选取中，居民点的取舍主要取决于居民点要素的行政级别属性。其等级用分类代码表示：AA代表国名，AB代表省(直辖区、自治区、特别行政区)行政地名，AC代表自治州、盟、地区行政地名，AD代表地级市行政地名，AE代表县级市行政地名等，依次类推。

在居民点的取舍中，可根据语义关系约束建立以下规则：当设相邻居民点M_i的等级大于点M_i+1的等级时，删除点M_i+1；反之，则删除点M_i。

1.4   拓扑关系约束

GIS中拓扑关系是指用结点、弧段和多边形所表示的实体之间的邻接、关联、包含和连通关系。居民点群的拓扑关系约束主要考虑居民点与邻近点及居民点与邻近道路线要素的拓扑关系。本文主要考虑以下两种情况：(1)居民点是否重合，若两个不同等级的居民点重合，将会导致注记压盖，因此，需要视情况删除等级低的居民点；(2)居民点是否在邻近道路线要素的端点上，若删除与道路端点相接的居民点，将会导致出现断头路的情况，因此，与道路两端相接的居民点为必须保留的点。

2 算法设计

最优信息熵约束的居民地点状要素选取方法的总体算法流程如图 1所示。

图  1  总体算法流程图

Figure  1.  Flowchart of Overall Algorithm

下载: 全尺寸图片 幻灯片

基于以上约束实现居民地点状要素选取，需要3个步骤：(1)基于改进的平面扫描算法的要素拓扑一致性维护，目的是去除居民点群中的重合点并检测居民点与道路的邻接关系；(2)基于Delaunay三角网的点要素选取，旨在保证居民点优先级的基础上，利用度量约束实现居民点的选取；(3)利用Voronoi图计算信息熵，即对选取结果进行评价，如果不符合预期值，则不断迭代调整度量关系约束值(即D值)，并返回第(2)步重新执行，直到取得最优信息熵，算法结束。

2.1   基于改进的平面扫描算法的居民点拓扑一致性维护

利用语义关系约束与拓扑关系约束判断重合点与断头路，若直接进行点点、点线两两判断，其计算量大且效率低，时间复杂性为O(n²)。为了提高效率，本文采用改进的平面扫描算法^[21]。

选择需要选取的居民点数据和道路数据，设点集P包含n个居民点数据，点集L包含m条道路的2m个端点数据。将点集P和点集L合成一个点集Q，将点集Q中每一个点q_i的x坐标值按照从小到大的顺序排序(x₁，x₂…x_n+2m)；选择直线x=x₁沿x方向进行扫描，当扫描到第i个点与第i+1个点的x、y坐标都相等时(i=1，2…n+2m)，进行点类型判断。若两个点的类型均为居民点，则表明q_i与q_i+1为重合点，进一步判断两个点的语义关系，若第i个点的等级高于第i+1个点的等级，则保留q_i；反之，保留q_i+1。若第i个点类型为居民点，第i+1个点类型为道路端点，或第i个点类型为道路端点，第i+1个点类型为居民点，则表明q_i或q_i+1是在道路两端的点，为必须保留的重要点。扫描结束后，将点集Q中类型为居民点且需要保留的点选择出来，得到点集Q₁。

定义点集Q的数据结构为(x，y，type，class，isMarked，remain)，x、y分别为点的横纵坐标；type代表点的类型；class是居民点的等级；isMarked的值为0或-1，该值初始化为0，isMarked=-1代表该点为重合点；remain的值为0或1，0代表删除该点，1代表保留该点。

2.2   基于Delaunay三角网的居民点要素选取

通过预处理过程得到了包含n₁个离散点的点集Q₁。

如图 2(a)所示，运用逐点插入法来构建点集Q₁的Delaunay三角网，可得到包含m个三角形的三角形列表T；初始度量约束值$ \mathrm{取}D={D}_{0} $；为了优先考虑等级高的点，按照等级字段排序后遍历点集Q₁。

图  2  利用Delaunay三角网选取点要素的基本原理

Figure  2.  Principle of Point Feature Selection Based on Delaunay Triangulation

下载: 全尺寸图片 幻灯片

如图 2(b)所示，假设点Q_1j为等级最高的点，则由以点Q_1j为顶点的所有三角形组成的三角形集为Q_1jT，逆时针搜索点Q_1j的一阶邻近点P₁、P₂、P₃、P₄、P₅、P₆，计算点Q_1j与其一阶邻近点的距离，若其距离大于$ D $，说明该区域居民点密度较小，需要保留该一阶邻近点；反之，进入下一步判断。当点Q_1j与其一阶邻近点的距离小于$ D $时，则需判断该一阶邻近点否为重要点，若是，则保留该点；否则，删除该点。点集Q₁遍历结束后，得到点集Q₂。

2.3   基于Voronoi图的信息熵计算

将选取后居民点集合X的信息熵表示为H(X)^[13]，则：

式中，P(x_i)为居民点x_i的分布概率；n为地图中的居民点总数。

居民点x_i的分布概率P(x_i)的计算是信息熵计算的基础。由于点群的Voronoi图是对空间目标影响区域的剖分，定义了点群目标的空间分布特征^[21-24]，某点剖分区域面积越大，则认为该点占有或影响的空间越大，其分布概率也就越大。因此，本文采用基于Voronoi图剖分的信息熵度量方法^[16]，将居民点的Voronoi剖分单元面积与制图区域总面积之比作为该点的分布概率，不仅反映了实体对空间占有的分布，同时，也体现出地物之间的邻接关系^{[2, 16]}。

建立的居民点群的Voronoi图如图 3所示。对整个制图区域进行剖分，假设S是整个区域的面积，且被分割为n个面积为S_i的子区域，其中，i=1，2…n，n为居民点群个数，则每个居民点的分布概率为：

图  3  居民点群的Voronoi图

Figure  3.  Voronoi Diagram of Residential Point Group

下载: 全尺寸图片 幻灯片

则式(2)可以改写为：

设信息模糊度为H(X|Y)^[17]，其定义为：

式中，x_i为第i个居民点；y_j为x_i给定范围内的第j个相邻点；$ P\left({y}_{j}\right) $为居民点y_j的分布概率；$ P\left({x}_{i}\right|y) $通过归一化对居民点x_i与y_j的相似度函数的集合进行条件概率计算，其定义为：

式中，$ \mathop \sum \limits _{i=1}^{n}P\left({x}_{i}\right|y)=1 $；$ \mu \left({x}_{i}\right|y) $为居民点x_i与y_j的相似度函数^[18]。

在本文提出的选取方法中，居民点x_i和y_j之间的欧氏距离t造成它们视觉分离，按照§1.2的度量关系约束定义，定义相似度函数$ \mu \left(t\right) $为：

则式(5)可改写为：

则有效信息量$ R\left(X\right) $可通过式(4)$ ~ $式(8)得到，即：

通过调整度量关系约束值D，当R(X)=max[$ H\left(X\right)-H\left(X\right|Y) $]时，地图有效信息量取得最大值，其对应的H(X)为最优信息熵，表示以值D为度量关系约束选取的结果最合理。

3 应用与分析

为了验证本文方法的有效性，以某区域1∶250 000居民点数据和城市道路数据为例，假设综合后目标比例尺为1∶500 000，图 4(a)为选取前居民点的分布情况，有3 421个居民点，其H(X)=7.968。

图  4  选取效果对比图

Figure  4.  Comparison Charts of Selection Results

下载: 全尺寸图片 幻灯片

表 1为利用上述算法计算出的居民点数据在不同的度量约束下的H(X)和R(X)的值。由表 1可以看出，H(X)随着度量约束值的增加而减小，而R(X)随着度量约束值增加呈现先增后减的规律，在度量约束为3 km时得到R(X)的最大值为3.869。

表  1  实验结果

Table  1.  Experimental Results

度量约束值/km	信息量/个	H(X)	H(X|Y)	R(X)
1.0	3 024	7.883	4.119	3.764
1.5	2 687	7.782	4.109	3.673
2.0	2 242	7.617	3.947	3.670
2.5	1 849	7.430	3.670	3.760
3.0	1 516	7.232	3.363	3.869
3.5	1 283	7.066	3.316	3.750
4.0	1 162	6.963	3.311	3.652
4.5	1 102	6.903	3.236	3.667
5.0	1 082	6.880	3.213	3.667

下载: 导出CSV 

| 显示表格

图 5进一步把表 1的数据可视化，可以明显看出，H(X)、H(X|Y)、R(X)随度量约束值的增加而变化的趋势。

图  5  实验结果统计分析图

Figure  5.  Flowchart of Statistical Analysis

下载: 全尺寸图片 幻灯片

图 4(b)为选取后在R(X)最大时的效果，选取后的群点个数为1 516，总体点数减为原来的0.443倍，对应最优信息熵H(X)=7.232，最优度量约束值为3 km。与图 4(a)比较，信息熵虽然减小了，但其有效信息量达到最大，因此，从视觉效果上看，选取后居民点符号间的关系更趋合理，并较好地保持了选取后的居民地点群的总体结构特征。

1) 点群空间分布的合理性。图 6(a)、图 6(b)分别为选取前、选取后的居民点的密度图，灰度值越高代表密度越高，从视觉效果上可以看出，采用本文方法对居民点选取后，较好地保持了原图的密度分布特征。

图  6  点群空间分布的合理性验证展示

Figure  6.  Rationality Verification of Spatial Distribution of Point Group

下载: 全尺寸图片 幻灯片

2) 语义关系合理性。如图 7(a)所示，廊坊市为地级市行政地名，级别为AD，周围部分级别低于AD的居民点没有被选取上。图 7(b)中的结果保留的点的等级均高于周围其他点的等级。

图  7  属性主次关系合理性验证结果展示

Figure  7.  Rationality Verification of Attribute Primary and Secondary Relationship

下载: 全尺寸图片 幻灯片

3) 空间关系的合理性。选取前，重合点情况如图 8(a)所示，两个居民点名称分别为娄村与娄村满族，坐标相同，造成了注记冲突；选取后，重合点保留结果如图 8(b)所示，保留级别更高的娄村满族点。选取前，重要点如图 8(c)所示，名为下场的点为自然村地名(BB)；虽然等级较低，但其与道路邻接而保留下来，重要点保留结果如图 8(d)所示。

图  8  空间关系的合理性验证结果展示

Figure  8.  Rationality Verification Results of Spatial Relationships

下载: 全尺寸图片 幻灯片

4 结语

本文基于最优信息熵约束提出了居民地点状要素选取的迭代优化方法。该方法具有以下4个优点：(1)保持了居民点群的空间分布特征；(2)顾及了居民地点的行政级别差异；(3)保留了其与道路的空间关系的合理性；(4)实现了地图的有效信息量最大化。基于以上方法，开发了ArcMap插件，用于应急地图及政府工作用图编制，取得了较好的应用效果。

本文为了突出最优信息熵约束在居民点选取中的控制效果，将问题进行了简化，信息熵的计算没有考虑图上居民点注记所占用的空间，在一定程度上影响了居民点选取后地图表达的整体效果，今后的研究将对该方法进行拓展和优化。