留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

最优信息熵约束的居民地点状要素选取方法

刘万增 陆辰妮 霍亮 吴晨琛 赵婷婷 朱秀丽

刘万增, 陆辰妮, 霍亮, 吴晨琛, 赵婷婷, 朱秀丽. 最优信息熵约束的居民地点状要素选取方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(8): 1178-1185. doi: 10.13203/j.whugis20190305
引用本文: 刘万增, 陆辰妮, 霍亮, 吴晨琛, 赵婷婷, 朱秀丽. 最优信息熵约束的居民地点状要素选取方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(8): 1178-1185. doi: 10.13203/j.whugis20190305
LIU Wanzeng, LU Chenni, HUO Liang, WU Chenchen, ZHAO Tingting, ZHU Xiuli. Selection Method of Residential Point Features Constrained by Optimal Information Entropy[J]. Geomatics and Information Science of Wuhan University, 2021, 46(8): 1178-1185. doi: 10.13203/j.whugis20190305
Citation: LIU Wanzeng, LU Chenni, HUO Liang, WU Chenchen, ZHAO Tingting, ZHU Xiuli. Selection Method of Residential Point Features Constrained by Optimal Information Entropy[J]. Geomatics and Information Science of Wuhan University, 2021, 46(8): 1178-1185. doi: 10.13203/j.whugis20190305

最优信息熵约束的居民地点状要素选取方法

doi: 10.13203/j.whugis20190305
基金项目: 

国家重点研发计划 2018YFC0807005

详细信息
    作者简介:

    刘万增,博士,高级工程师,主要从事GIS空间关系、数据库更新及应急制图技术方法研究工作。luwnzg@163.com

    通讯作者: 陆辰妮,硕士. E-mail: libra688@126.com
  • 中图分类号: P283

Selection Method of Residential Point Features Constrained by Optimal Information Entropy

Funds: 

The National Key Research and Development Program of China 2018YFC0807005

More Information
    Author Bio:

    LIU Wanzeng, PhD, senior engineer, mainly engaged in the research of GIS spatial relationship, database updating and emergency mapping technology.E-mail: luwnzg@163.com

    Corresponding author: LU Chenni, master. E-mail: libra688@126.com
  • 摘要: 实现多种约束下的地图信息的负载均衡是制图综合的难点之一。在中小比例尺地图中,对于乡镇及村庄居民点进行尺度转换,需要综合考虑其行政级别、拓扑和度量关系,以使地图信息负载量在一定尺度下达到合理。提出一种基于最优信息熵约束的居民地点状要素选取方法,在最优信息熵约束下,调整度量关系约束,优先考虑语义关系,保留行政级别高的居民点,对行政级别低的居民点,如果不是道路端点,且不满足度量关系约束,则删除该点,不断迭代,直到满足最优信息熵约束。采用1∶250 000居民地点数据进行实验,实现了维护拓扑一致性、级别优先性、度量合理性的居民地点状要素选取,在有效地保持地图的负载均衡和可读性的同时,实现了地图有效信息量的最大化。采用最优信息熵约束进行居民点选取,在整体上可以保留居民点群空间分布的疏密特征,效果上能够达到图幅信息量的负载均衡。
  • 图  1  总体算法流程图

    Figure  1.  Flowchart of Overall Algorithm

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

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

    图  3  居民点群的Voronoi图

    Figure  3.  Voronoi Diagram of Residential Point Group

    图  4  选取效果对比图

    Figure  4.  Comparison Charts of Selection Results

    图  5  实验结果统计分析图

    Figure  5.  Flowchart of Statistical Analysis

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

    Figure  6.  Rationality Verification of Spatial Distribution of Point Group

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

    Figure  7.  Rationality Verification of Attribute Primary and Secondary Relationship

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

    Figure  8.  Rationality Verification Results of Spatial Relationships

    表  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
  • [1] 王家耀, 钱海忠. 制图综合知识及其应用[J]. 武汉大学学报·信息科学版, 2006, 31(5): 382-386 http://ch.whu.edu.cn/article/id/2452

    Wang Jiayao, Qian Haizhong. Cartographic-Generaliaztion-Knowledge and Its Application[J]. Geomatics and Information Science of Wuhan University, 2006, 31(5): 382-386 http://ch.whu.edu.cn/article/id/2452
    [2] 艾廷华, 何亚坤, 杜欣. GIS数据尺度变换中的信息熵变化[J]. 地理与地理信息科学, 2015, 31(2): 7-11 doi:  10.3969/j.issn.1672-0504.2015.02.002

    Ai Tinghua, He Yakun, Du Xin. Information Entropy Change in GIS Data Scale Transformation[J]. Geography and Geo-Information Science, 2015, 31(2): 7-11 doi:  10.3969/j.issn.1672-0504.2015.02.002
    [3] 晏雄锋, 艾廷华, 杨敏. 居民地要素化简的形状识别与模板匹配方法[J]. 测绘学报, 2016, 45(7): 874-882 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201607018.htm

    Yan Xiongfeng, Ai Tinghua, Yang Min. A Simplification of Residential Feature by the Shape Cognition and Template Matching Method[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(7): 874-882 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201607018.htm
    [4] 高凯, 杨敏, 张跃鹏. 保持空间分布特征的散列式居民地综合选取方法[J]. 测绘科学技术学报, 2015, 32(6): 626-630 doi:  10.3969/j.issn.1673-6338.2015.06.016

    Gao Kai, Yang Min, Zhang Yuepeng. A Method of Automatic Selection of Hash-Style Habitation with Spatial Distribution Characteristics Preserved[J]. Journal of Geomatics Science and Technology, 2015, 32(6): 626-630 doi:  10.3969/j.issn.1673-6338.2015.06.016
    [5] 于艳平, 沈婕, 尚在颖. 点群选取与化简算法时间复杂度研究[J]. 南京师范大学学报(自然科学版), 2012, 35(1): 111-116 https://www.cnki.com.cn/Article/CJFDTOTAL-NJSF201201022.htm

    Yu Yanping, Shen Jie, Shang Zaiying. A Study on the Time Complexity of Point Cluster Selection and Simplification Algorithms[J]. Journal of Nanjing Normal University(Natural Science Edition), 2012, 35(1): 111-116 https://www.cnki.com.cn/Article/CJFDTOTAL-NJSF201201022.htm
    [6] 钱海忠, 武芳, 邓红艳. 基于CIRCLE特征变换的点群选取算法[J]. 测绘科学, 2005, 30(3): 83-85 doi:  10.3771/j.issn.1009-2307.2005.03.025

    Qian Haizhong, Wu Fang, Deng Hongyan. A Model of Point Cluster Selection with Circle Characters[J]. Science of Surveying and Mapping, 2005, 30(3): 83-85 doi:  10.3771/j.issn.1009-2307.2005.03.025
    [7] 闫浩文, 王家耀. 基于Voronoi图的点群目标普适综合算法[J]. 中国图象图形学报, 2005, 10(5): 633-636 doi:  10.3969/j.issn.1006-8961.2005.05.017

    Yan Haowen, Wang Jiayao. A Generic Algorithm for Point Cluster Generalization Based on Voronoi Diagrams[J]. Journal of Image and Graphics, 2005, 10(5): 633-636 doi:  10.3969/j.issn.1006-8961.2005.05.017
    [8] 沈婕, 朱月琴, 吴鹏, 等. 兴趣点选取的路网分割并行计算法[J]. 测绘学报, 2015, 44(S): 54-61 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB2015S1009.htm

    Shen Jie, Zhu Yueqin, Wu Peng, et al. Parallel Compiting Method for POIs Selection Based on Stroke Mesh Decomposition[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(S): 54-61 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB2015S1009.htm
    [9] Zhou Jiemin, Shen Jie, Yang Shuai, et al. Method of Constructing Point Generalization Constraints Based on the Cloud Platform[J]. ISPRS International Journal of Geo-Information, 2018, 7(7), DOI:  10.3390/ijgi7070235.
    [10] 艾廷华, 刘耀林. 保持空间分布特征的群点化简方法[J]. 测绘学报, 2002, 31(2): 175-181 doi:  10.3321/j.issn:1001-1595.2002.02.016

    Ai Tinghua, Liu Yaolin. A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2): 175-181 doi:  10.3321/j.issn:1001-1595.2002.02.016
    [11] 蔡永香, 郭庆胜. 基于Kohonen网络的点群综合研究[J]. 武汉大学学报·信息科学版, 2007, 32(7): 626-629 http://ch.whu.edu.cn/article/id/1933

    Cai Yongxiang, Guo Qingsheng. Points Group Generalization Based on Konhonen Net[J]. Geomatics and Information Science of Wuhan University, 2007, 32(7): 626-629 http://ch.whu.edu.cn/article/id/1933
    [12] 邓红艳, 武芳, 钱海忠, 等. 基于遗传算法的点群目标选取模型[J]. 中国图象图形学报, 2003, 8(8): 970-976 doi:  10.3969/j.issn.1006-8961.2003.08.020

    Deng Hongyan, Wu Fang, Qian Haizhong, et al. A Model of Point Cluster Selection Based on Genetic Algorithms[J]. Journal of Image and Graphics, 2003, 8(8): 970-976 doi:  10.3969/j.issn.1006-8961.2003.08.020
    [13] Shannon C E A. Mathematical Theory of Communication[J]. The Bell System Technical Journal, 1948, 27: 379-423 doi:  10.1002/j.1538-7305.1948.tb01338.x
    [14] Sukhov V I. Information Capacity of a Map: Entropy[J]. Geodesy and Aerophotography, 1967, 10(4): 212-215 http://www.researchgate.net/publication/288166337_Information_capacity_of_a_map_entropy
    [15] Neumann J. The Topological Information Content of a Map: An Attempt at a Rehabilitation of Information Theory in Cartography[J]. Cartographica, 1994, 31(1): 26-34 doi:  10.3138/U626-551H-64K4-9687
    [16] Li Zhilin, Huang Peizhi. Quantitative Measures for Spatial Information of Maps[J]. International Journal of Geographical Information Science, 2002, 16(7): 699-709 doi:  10.1080/13658810210149416
    [17] Knopfli R. Communication Theory and Generalization[C]//Graphic Communication and Design Incontemporary Cartography, New York, USA, 1983
    [18] Bjørke J T. Framework for Entropy-Based Map Evaluation[J]. Cartography and Geographic Information Systems, 1996, 23(2): 78-95 doi:  10.1559/152304096782562136
    [19] 武芳, 巩现勇, 杜佳威. 地图制图综合回顾与前望[J]. 测绘学报, 2017, 46(10): 1 645-1 664 doi:  10.11947/j.AGCS.2017.20170287

    Wu Fang, Gong Xianyong, Du Jiawei. Overview of the Research Progress in Automated Map Generalization[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10): 1 645-1 664 doi:  10.11947/j.AGCS.2017.20170287
    [20] 沈晶, 刘纪平, 林祥国, 等. 集成距离变换和区域邻接图生成Delaunay三角网的方法研究[J]. 武汉大学学报·信息科学版, 2012, 37(8): 1 000-1 003 http://ch.whu.edu.cn/article/id/303

    Shen Jin, Liu Jiping, Lin Xiangguo, et al. A Method for Delaunay Triangulation by Integration of Distance Transformation and Region Adjacency Graphics[J]. Geomatics and Information Science of Wuhan University, 2012, 37(8): 1 000-1 003 http://ch.whu.edu.cn/article/id/303
    [21] 陈军, 刘万增, 李志林, 等. 线目标间拓扑关系的细化计算方法[J]. 测绘学报, 2006, 35(3): 255-260 doi:  10.3321/j.issn:1001-1595.2006.03.012

    Chen Jun, Liu Wanzeng, Li Zhilin, et al. The Refined Calculation Method of Topological Relationships Between Line Objects[J]. Acta Geodaetica et Cartographica Sinica, 2006, 35(3): 255-260 doi:  10.3321/j.issn:1001-1595.2006.03.012
    [22] 刘万增, 陈军, 闫超德, 等. 平面离散点集拓扑邻近稳定区域计算模型[J]. 测绘学报, 2012, 41(1): 127-132 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201201025.htm

    Liu Wanzeng, Chen Jun, Yan Chaode, et al. Model for Calculating Topology Stable Area of the Plan Discrete Points[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1): 127-132 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201201025.htm
    [23] 邹亚锋, 刘耀林, 孔雪松, 等. 加权Voronoi图在农村居民点布局优化中的应用研究[J]. 武汉大学学报·信息科学版, 2012, 37(5): 560-563 http://ch.whu.edu.cn/article/id/204

    Zou Yafeng, Liu Yaolin, Kong Xuesong, et al. Optimization of Rural Residential Land Based on Weighted-Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University, 2012, 37(5): 560-563 http://ch.whu.edu.cn/article/id/204
    [24] 闫浩文, 王邦松. 地图点群综合的加权Voronoi算法[J]. 武汉大学学报·信息科学版, 2013, 38(9): 1 088-1 091 http://ch.whu.edu.cn/article/id/2740

    Yan Haowen, Wang Bangsong. A MWVD-Based Algorithm for Point Cluster Generalization[J]. Geomatics and Information Science of Wuhan University, 2013, 38(9): 1 088-1 091 http://ch.whu.edu.cn/article/id/2740
  • [1] 刘鹏程, 许小峰, 杨敏.  一种顾及符号完整性的矢量瓦片地图改进方案 . 武汉大学学报 ● 信息科学版, 2022, 47(3): 455-462. doi: 10.13203/j.whugis20200033
    [2] 吴建华, 戴鹏, 胡烈云.  一种面向多尺度面状居民地匹配的Voronoi图自适应构建算法 . 武汉大学学报 ● 信息科学版, 2022, 47(2): 304-312. doi: 10.13203/j.whugis20200324
    [3] 李雅彦, 杜清运, 蔡忠亮, 张磊, 张铭晓.  一种采用PostScript成像模型的高质量地图制图方法 . 武汉大学学报 ● 信息科学版, 2018, 43(3): 379-384. doi: 10.13203/j.whugis20150139
    [4] 杨伟, 艾廷华.  运用Delaunay三角网提取OpenStreetMap主干道多边形 . 武汉大学学报 ● 信息科学版, 2018, 43(11): 1725-1731. doi: 10.13203/j.whugis20160294
    [5] 刘远刚, 郭庆胜, 孙雅庚, 杨乃, 郑春燕.  地图自动综合中Beams移位算法的实现与改进 . 武汉大学学报 ● 信息科学版, 2016, 41(4): 450-454,540. doi: 10.13203/j.whugis20140343
    [6] 王邦松, 张继贤, 卢丽君, 黄国满, 赵争.  利用Voronoi图辅助星载干涉雷达配准 . 武汉大学学报 ● 信息科学版, 2016, 41(10): 1339-1343. doi: 10.13203/j.whugis20140549
    [7] 李佳田, 罗富丽, 余莉, 张蓝, 康顺, 林艳.  梯度Voronoi图及其构建算法 . 武汉大学学报 ● 信息科学版, 2016, 41(2): 163-170. doi: 10.13203/j.whugis20140025
    [8] 刘远刚, 郭庆胜, 孙雅庚, 林青, 郑春燕.  地图目标群间骨架线提取的算法研究 . 武汉大学学报 ● 信息科学版, 2015, 40(2): 264-268.
    [9] 胡玮, 陶伟东, 苑振宇, 王结臣.  一种Voronoi图的扫描地图矢量化方法 . 武汉大学学报 ● 信息科学版, 2013, 38(4): 470-474.
    [10] 王新生, 何津, 叶晓雷, 姜友华.  图的谱方法的空间目标形状表达研究 . 武汉大学学报 ● 信息科学版, 2012, 37(11): 1281-1284.
    [11] 张剑清, 许彪, 孙明伟, 张勇.  利用三角网遮蔽检测进行真正射影像制作 . 武汉大学学报 ● 信息科学版, 2012, 37(3): 326-329.
    [12] 沈晶, 刘纪平, 林祥国, 赵荣.  集成距离变换和区域邻接图生成Delaunay三角网的方法研究 . 武汉大学学报 ● 信息科学版, 2012, 37(8): 1000-1003.
    [13] 闫超德, 白建军, 赵仁亮.  基于Voronoi图的点状目标邻近空间分布测度方法 . 武汉大学学报 ● 信息科学版, 2009, 34(1): 48-51.
    [14] 杨勇, 李霖, 王红, 朱海红.  基于国家基础地理信息数据的地图制图系统 . 武汉大学学报 ● 信息科学版, 2008, 33(3): 261-264.
    [15] 艾廷华, 陈涛.  基于三角网的“种子法”多边形生成 . 武汉大学学报 ● 信息科学版, 2004, 29(1): 14-19.
    [16] 陈军, 赵仁亮, 乔朝飞.  基于Voronoi图的GIS空间分析研究 . 武汉大学学报 ● 信息科学版, 2003, 28(S1): 32-37.
    [17] 艾廷华, 郭仁忠.  支持地图综合的面状目标约束Delaunay三角网剖分 . 武汉大学学报 ● 信息科学版, 2000, 25(1): 35-41.
    [18] 李成名, 陈军, 朱英浩.  基于Voronoi图的空间邻近定义与查询 . 武汉大学学报 ● 信息科学版, 1998, 23(2): 128-131.
    [19] 李成名, 陈军.  Voronoi图生成的栅格算法 . 武汉大学学报 ● 信息科学版, 1998, 23(3): 208-210.
    [20] 何宗宜.  视错觉在地图制图中应用的研究 . 武汉大学学报 ● 信息科学版, 1991, 16(3): 22-30.
  • 加载中
图(8) / 表(1)
计量
  • 文章访问数:  353
  • HTML全文浏览量:  173
  • PDF下载量:  51
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-10-24
  • 刊出日期:  2021-08-05

最优信息熵约束的居民地点状要素选取方法

doi: 10.13203/j.whugis20190305
    基金项目:

    国家重点研发计划 2018YFC0807005

    作者简介:

    刘万增,博士,高级工程师,主要从事GIS空间关系、数据库更新及应急制图技术方法研究工作。luwnzg@163.com

    通讯作者: 陆辰妮,硕士. E-mail: libra688@126.com
  • 中图分类号: P283

摘要: 实现多种约束下的地图信息的负载均衡是制图综合的难点之一。在中小比例尺地图中,对于乡镇及村庄居民点进行尺度转换,需要综合考虑其行政级别、拓扑和度量关系,以使地图信息负载量在一定尺度下达到合理。提出一种基于最优信息熵约束的居民地点状要素选取方法,在最优信息熵约束下,调整度量关系约束,优先考虑语义关系,保留行政级别高的居民点,对行政级别低的居民点,如果不是道路端点,且不满足度量关系约束,则删除该点,不断迭代,直到满足最优信息熵约束。采用1∶250 000居民地点数据进行实验,实现了维护拓扑一致性、级别优先性、度量合理性的居民地点状要素选取,在有效地保持地图的负载均衡和可读性的同时,实现了地图有效信息量的最大化。采用最优信息熵约束进行居民点选取,在整体上可以保留居民点群空间分布的疏密特征,效果上能够达到图幅信息量的负载均衡。

English Abstract

刘万增, 陆辰妮, 霍亮, 吴晨琛, 赵婷婷, 朱秀丽. 最优信息熵约束的居民地点状要素选取方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(8): 1178-1185. doi: 10.13203/j.whugis20190305
引用本文: 刘万增, 陆辰妮, 霍亮, 吴晨琛, 赵婷婷, 朱秀丽. 最优信息熵约束的居民地点状要素选取方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(8): 1178-1185. doi: 10.13203/j.whugis20190305
LIU Wanzeng, LU Chenni, HUO Liang, WU Chenchen, ZHAO Tingting, ZHU Xiuli. Selection Method of Residential Point Features Constrained by Optimal Information Entropy[J]. Geomatics and Information Science of Wuhan University, 2021, 46(8): 1178-1185. doi: 10.13203/j.whugis20190305
Citation: LIU Wanzeng, LU Chenni, HUO Liang, WU Chenchen, ZHAO Tingting, ZHU Xiuli. Selection Method of Residential Point Features Constrained by Optimal Information Entropy[J]. Geomatics and Information Science of Wuhan University, 2021, 46(8): 1178-1185. doi: 10.13203/j.whugis20190305
  • 高质量、高效率地图制图是测绘公益性服务保障的重要任务,其基于不同比例尺的基础地理信息数据,按照制图规范,通过尺度转换、符号映射等,实现地理要素数据的快速符号化、自动注记及图廓整饰等。在数据尺度转换的过程中,尤其当比例尺缩小时,会造成地图负载量过大,引起符号冲突、注记压盖等问题,影响地图的可视化表达效果,导致读图困难[1-2]。因此,在数据尺度转换的过程中,为了实现地图负载均衡,需要进行要素选取。居民地是地图上重要的地理要素,在中小比例尺地图中,对地图负载量影响较大的是不依比例的乡镇及村庄居民点。本文以不依比例居民点选取为例,研究基于最优信息熵约束的居民地点状要素选取方法。

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

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

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

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

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

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

      $$ {t}_{i}=\sqrt[]{({X}_{{M}_{i}}-{X}_{{M}_{i+1}}{)}^{2}+({Y}_{{M}_{i}}-{Y}_{{M}_{i+1}}{)}^{2}} $$ (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值即为最终的度量关系约束值。

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

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

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

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

      图  1  总体算法流程图

      Figure 1.  Flowchart of Overall Algorithm

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

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

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

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

    • 通过预处理过程得到了包含n1个离散点的点集Q1

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

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

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

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

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

      $$ H\left(X\right)=-\mathop \sum \limits _{i=1}^{n}P\left({x}_{i}\right)\mathrm{l}\mathrm{n}P\left({x}_{i}\right) $$ (2)

      式中,P(xi)为居民点xi的分布概率;n为地图中的居民点总数。

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

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

      $$ P\left({x}_{i}\right)=\frac{{S}_{i}}{S} $$ (3)

      图  3  居民点群的Voronoi图

      Figure 3.  Voronoi Diagram of Residential Point Group

      则式(2)可以改写为:

      $$ H\left(X\right)=-\mathop \sum \limits _{i=1}^{n}\frac{{S}_{i}}{S}(\mathrm{l}\mathrm{n}{S}_{i}-\mathrm{l}\mathrm{n}S) $$ (4)

      设信息模糊度为H(X|Y)[17],其定义为:

      $$ H\left(X|Y\right)=-\mathop \sum \limits _{j=1}^{k}P\left({y}_{j}\right)\mathop \sum \limits _{i=1}^{n}P\left({x}_{i}\right|y\left)\mathrm{l}\mathrm{n}P\right({x}_{i}\left|y\right) $$ (5)

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

      $$ P\left({x}_{i}\right|y)=\frac{\mu \left({x}_{i}\right|y)}{\mathop \sum \limits _{i=1}^{n}\mu \left({x}_{i}\right|y)} $$ (6)

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

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

      $$ \mu \left(t\right)=\left\{\begin{array}{l}1, t<{d}_{0}\\ 1-\frac{t-{d}_{0}}{{d}_{1}-{d}_{0}}, {d}_{1}\ge t\ge {d}_{0}\\ 0, t>{d}_{1}\end{array}\right. $$ (7)

      则式(5)可改写为:

      $$ H\left(X|Y\right)=-\mathop \sum \limits _{j=1}^{n}\frac{{S}_{j}}{S}\mathop \sum \limits _{i=1}^{n}\frac{\mu \left({t}_{i}\right)}{\mathop \sum \limits _{i=1}^{n}\mu \left({t}_{i}\right)}\mathrm{l}\mathrm{n}\frac{\mu \left({t}_{i}\right)}{\mathop \sum \limits _{i=1}^{n}\mu \left({t}_{i}\right)} $$ (8)

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

      $$ R\left(X\right)=H\left(X\right)-H\left(X\right|Y) $$ (9)

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

    • 为了验证本文方法的有效性,以某区域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

      图 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个优点:(1)保持了居民点群的空间分布特征;(2)顾及了居民地点的行政级别差异;(3)保留了其与道路的空间关系的合理性;(4)实现了地图的有效信息量最大化。基于以上方法,开发了ArcMap插件,用于应急地图及政府工作用图编制,取得了较好的应用效果。

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

参考文献 (24)

目录

    /

    返回文章
    返回