A building aggregation method based on deep clustering of graph vertices

doi:10.11947/j.AGCS.2024.20230316

Abstract

Abstract:

Building element aggregation is pivotal for simplifying spatial structures in cartographic generalization. Conventional rule-based aggregation methods often cannot simultaneously consider the morphological and distributional characteristics of the features, because they are heavily influenced by preset algorithm parameters and lack flexibility in the cartographic generalizing process. To fill these limitations, this paper proposes a building aggregation model based on deep clustering of graph vertices. The model utilizes the Delaunay triangulation network to construct a representation graph model of building groups and combines an autoencoder and graph convolutional network to learn the subdivided triangles’ geometric shapes and spatial distribution features. A self-supervised learning approach is employed to cluster and classify the triangles into the categories of “retain” and “delete”. Consequently, it aggregates buildings intelligently in an end-to-end manner without relying on predefined samples. The experimental results demonstrate that the proposed method reduces reliance on preset aggregation parameters while simultaneously considering building elements’ morphology and distribution features. The aggregation process exhibits a certain degree of flexibility, resulting in aggregated buildings better aligning with the requirements of map visualization.

Key words: cartographic generalization, building aggregation, graph neural network, self-supervised learning

CLC Number:

P283

Zhanlong CHEN, Xiechun LU, Yongyang XU. A building aggregation method based on deep clustering of graph vertices[J]. Acta Geodaetica et Cartographica Sinica, 2024, 53(4): 736-749.

Figures/Tables 14

Fig. 1

Fig. 2

Tab. 1

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Tab. 2

Tab. 3

Fig. 9

Fig. 10

Tab. 4

References 46

[1]	武芳, 巩现勇, 杜佳威. 地图制图综合回顾与前望[J]. 测绘学报, 2017, 46(10):1645-1664.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):1645-1664.DOI: 10.11947/j.AGCS.2017.20170287.
[2]	王家耀, 武芳, 闫浩文. 大变化时代的地图学[J]. 测绘学报, 2022, 51(6):829-842.DOI: 10.11947/j.AGCS.2022.20210661.
	WANG Jiayao, WU Fang, YAN Haowen. Cartography: its past, present and future[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(6):829-842. DOI: 10.11947/j.AGCS.2022.20210661.
[3]	高晓蓉, 闫浩文, 禄小敏. 多尺度地图空间居民地语义相似度计算方法[J]. 测绘学报, 2022, 51(1):95-103.DOI: 10.11947/j.AGCS.2022.20210074.
	GAO Xiaorong, YAN Haowen, LU Xiaomin. Semantic similarity measurement for building polygon aggregation in multi-scale map space[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(1):95-103.DOI: 10.11947/j.AGCS.2022.20210074.
[4]	杨好, 何宗宜, 陈华洋, 等. 顾及路网结构保持的城镇居民地自动综合[J]. 武汉大学学报(信息科学版), 2018, 43(6):965-970.
	YANG Hao, HE Zongyi, CHEN Huayang, et al. A method for automatic generalization of urban settlements considering road network[J]. Geomatics and Information Science of Wuhan University, 2018, 43(6):965-970.
[5]	武芳, 杜佳威, 钱海忠, 等. 地图综合智能化研究的发展与思考[J]. 武汉大学学报(信息科学版), 2022, 47(10):1675-1687.
	WU Fang, DU Jiawei, QIAN Haizhong, et al. Overview of research progress and reflections in intelligent map generalization[J]. Geomatics and Information Science of Wuhan University, 2022, 47(10):1675-1687.
[6]	郭仁忠, 艾廷华. 制图综合中建筑物多边形的合并与化简[J]. 武汉测绘科技大学学报, 2000, 25(1):25-30.
	GUO Renzhong, AI Tinghua. Simplification and aggregation of building polygon in automatic map generalization[J].Journal of Wuhan Technical University of Surveying and Mapping, 2000, 25(1):25-30.
[7]	王光霞, 杨培. 数学形态学在居民地街区合并中的应用[J]. 测绘学院学报, 2000, 17(3):201-203.
	WANG Guangxia, YANG Pei. Application of mathematic morphology in uniting blocks of residential area[J]. Journal of Institute of Surveying and Mapping, 2000, 17(3):201-203.
[8]	SHEN Yilang, AI Tinghua, LI Wende, et al. A polygon aggregation method with global feature preservation using superpixel segmentation[J]. Computers, Environment and Urban Systems, 2019, 75:117-131.
[9]	钱海忠, 武芳, 谭笑, 等. 基于ABTM的城市建筑物合并算法[J]. 中国图象图形学报, 2005, 10(10):1224-1233.
	QIAN Haizhong, WU Fang, TAN Xiao, et al. The algorithm for merging city buildings based on ABTM[J]. Journal of Image and Graphics, 2005, 10(10):1224-1233.
[10]	AI Tinghua, YIN Hongmei, SHEN Yilang, et al. A formal model of neighborhood representation and applications in urban building aggregation supported by Delaunay triangulation[J]. PLOS ONE, 2019, 14(7):e0218877.
[11]	王勇, 罗安, 王慧慧, 等. 复杂建筑物最短邻近线多边形聚合法[J]. 测绘学报, 2021, 50(12):1671-1682.DOI: 10.11947/j.AGCS.2021.20200493.
	WANG Yong, LUO An, WANG Huihui, et al. A method of polygon aggregation for complex buildings based on shortest adjacent lines[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(12):1671-1682.DOI: 10.11947/j.AGCS.2021.20200493.
[12]	AI Tinghua, ZHANG Xiang. The aggregation of urban building clusters based on the skeleton partitioning of gap space[M]//FABRIKANT S I, WACHOWICZ M. The European Information Society: leading the way with geo-informationy. Berlin: Springer, 2007: 153-170.
[13]	YAN Haowen, WEIBEL R, YANG Bisheng. A multi-parameter approach to automated building grouping and generalization[J]. GeoInformatica, 2008, 12(1):73-89.
[14]	李安平, 翟仁健, 殷吉崇, 等. 顾及空间结构关系的居民地自动合并方法[J/OL]. 武汉大学学报(信息科学版), 1-17 [2023-08-01].http://ch.whu.edu.cn/cn/article/doi/10.13203/j.whugis20210731.DOI: 10.13203/j.whugis20210731.
	LI Anping, ZHAI Renjian, YIN Jichong, et al. Automatic aggregation of building considering the spatial structure[J/OL]. Geomatics and Information Science of Wuhan University, 1-17 [2023-08-01].http://ch.whu.edu.cn/cn/article/doi/10.13203/j.whugis20210731.DOI: 10.13203/j.whugis20210731.
[15]	YAN Xiongfeng, CHEN Huan, HUANG Haoran, et al. Building typification in map generalization using affinity propagation clustering[J]. ISPRS International Journal of Geo-Information, 2021, 10(11):732.
[16]	郭建忠, 谢明霞, 李柱林. 基于线缓冲区分析的街区合并方法[J]. 地理与地理信息科学, 2011, 27(6):111-112.
	GUO Jianzhong, XIE Mingxia, LI Zhulin. Block merging method based on line buffer analysis[J]. Geography and Geo-Information Science, 2011, 27(6):111-112.
[17]	PENG Dongliang, TOUYA G. Continuously generalizing buildings to built-up areas by aggregating and growing[C]//Proceedings of 2017 ACM SIGSPATIAL Workshop on Smart Cities and Urban Analytics. Redondo Beach: ACM Press, 2017: 1-8.
[18]	樊红, TRAN Quynh An. 大比例尺居民地面状要素的自动无级综合[J]. 武汉大学学报(工学版), 2014, 47(2):271-275.
	FAN Hong, TRAN Quynh An. Multi-level automatic generalization of large scale polygon map residents[J]. Engineering Journal of Wuhan University, 2014, 47(2):271-275.
[19]	黄玉兰, 郭庆胜, 王慧慧, 等. 基于顶点线性插值的建筑物群聚合的简易方法[J]. 地理空间信息, 2022, 20(2):15-21.
	HUANG Yulan, GUO Qingsheng, WANG Huihui, et al. Simple method of building group aggregation based on vertex linear interpolation[J]. Geospatial Information, 2022, 20(2):15-21.
[20]	艾廷华, 郭仁忠, 陈晓东. Delaunay三角网支持下的多边形化简与合并[J]. 中国图象图形学报, 2001, 6(7):703-709.
	AI Tinghua, GUO Renzhong, CHEN Xiaodong. Simplification and aggregation of polygon object supported by delaunay triangulation structure[J]. Journal of Image and Graphics, 2001, 6(7):703-709.
[21]	钱海忠, 武芳. 基于Delaunay三角关系的面状要素合并方法[J]. 测绘学院学报, 2001, 18(3):207-209.
	QIAN Haizhong, WU Fang. A merge operation for area objects based on delaunay triangle-interpolating[J]. Journal of Institute of Surveying and Mapping, 2001, 18(3):207-209.
[22]	郭沛沛, 李成名, 殷勇. 建筑物合并的Delaunay三角网分类过滤法[J]. 测绘学报, 2016, 45(8):1001-1007.DOI: 10.11947/j.AGCS.2016.20150587.
	GUO Peipei, LI Chengming, YIN Yong. Classification and filtering of constrained delaunay triangulation for automated building aggregation[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(8):1001-1007.DOI: 10.11947/j.AGCS.2016.20150587.
[23]	LI Z, YAN H, AI T, et al. Automated building generalization based on urban morphology and Gestalt theory[J]. International Journal of Geographical Information Science, 2004, 18(5):513-534.
[24]	张晶, 周烨, 刘瑜. SDS模型化简合并多边形的一个改进算法研究[J]. 中国图象图形学报, 2006, 11(7):1010-1016.
	ZHANG Jing, ZHOU Ye, LIU Yu. An improved algorithm for SDS model based polygon simplification and aggregation[J]. Journal of Image and Graphics, 2006, 11(7):1010-1016.
[25]	闫浩文, 应申, 李霖. 多因子影响的地图居民地自动聚群与综合研究[J]. 武汉大学学报(信息科学版), 2008, 33(1):51-54.
	YAN Haowen, YING Shen, LI Lin. An approach for automated building grouping and generalization considering multiple parameters[J]. Geomatics and Information Science of Wuhan University, 2008, 33(1):51-54.
[26]	郭庆胜, 黎佳宜, 曹元晖, 等. 建筑物白模多边形的自动合并[J]. 武汉大学学报(信息科学版), 2021, 46(1):12-18.
	GUO Qingsheng, LI Jiayi, CAO Yuanhui, et al. Automatic aggregation of building footprint polygons[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1):12-18.
[27]	ROTTMANN P, DRIEMEL A, HAVERKORT H, et al. Bicriteria aggregation of polygons via graph cuts[EB/OL].[2023-08-01].https://drops.dagstuhl.de/storage/00lipics/lipics-vol208-giscience2021/LIPIcs.GIScience.2021.II.6/LIPIcs.GIScience.2021.II.6.pdf.
[28]	LI Chengming, YIN Yong, WU Pengda, et al. An area merging method in map generalization considering typical characteristics of structured geographic objects[J]. Cartography and Geographic Information Science, 2021, 48(3):210-224.
[29]	艾廷华. 深度学习赋能地图制图的若干思考[J]. 测绘学报, 2021, 50(9):1170-1182.DOI: 10.11947/j.AGCS.2021.20210091.
	AI Tinghua. Some thoughts on deep learning enabling cartography[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(9):1170-1182.DOI: 10.11947/j.AGCS.2021.20210091.
[30]	YAN Xiongfeng, AI Tinghua, YANG Min, et al. Graph convolutional autoencoder model for the shape coding and cognition of buildings in maps[J]. International Journal of Geographical Information Science, 2021, 35(3):490-512.
[31]	LI Pengbo, YAN Haowen, LU Xiaomin. A Siamese neural network for learning the similarity metrics of linear features[J]. International Journal of Geographical Information Science, 2023, 37(3):684-711.
[32]	YANG Min, YUAN Tuo, YAN Xiongfeng, et al. A hybrid approach to building simplification with an evaluator from a backpropagation neural network[J]. International Journal of Geographical Information Science, 2022, 36(2):280-309.
[33]	YAN Xiongfeng, AI Tinghua, YANG Min, et al. A graph convolutional neural network for classification of building patterns using spatial vector data[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2019, 150:259-273.
[34]	ALLOUCHE M K, MOULIN B. Amalgamation in cartographic generalization using Kohonen's feature nets[J]. International Journal of Geographical Information Science, 2005, 19(8/9):899-914.
[35]	ZHANG Liqiang, DENG Hao, CHEN Dong, et al. A spatial cognition-based urban building clustering approach and its applications[J]. International Journal of Geographical Information Science, 2013, 27(4):721-740.
[36]	陈占龙, 龚希, 吴亮, 等. 顾及尺度差异的复合空间对象方向相似度定量计算模型[J]. 测绘学报, 2016, 45(3):362-371. DOI: 10.11947/j.AGCS.2016.20150099.
	CHEN Zhanlong, GONG Xi, WU Liang, et al. A quantitative calculation method of composite spatial direction similarity concerning scale differences[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(3):362-371. DOI: 10.11947/j.AGCS.2016.20150099.
[37]	陈占龙, 覃梦娇, 吴亮, 等. 利用多级弦长弯曲度复函数构建复杂面实体综合形状相似度量模型[J]. 测绘学报, 2016, 45(2):224-232. DOI: 10.11947/j.AGCS.2016.20140633.
	CHEN Zhanlong, QIN Mengjiao, WU Liang, et al. Establishment of the comprehensive shape similarity model for complex polygon entity by using bending mutilevel chord complex function[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(2):224-232. DOI: 10.11947/j.AGCS.2016.20140633.
[38]	WILLIS D E. A source book of gestalt psychology[M]. London: [s.n.], 1999.
[39]	江浩, 褚衍东, 闫浩文, 等. 多尺度地理空间线状目标形状相似性的度量[J]. 测绘科学, 2010, 35(5):35-38.
	JIANG Hao, CHU Yandong, YAN Haowen, et al. Measurement of shape similarity for linear objects in multi-scale geographical space[J]. Science of Surveying and Mapping, 2010, 35(5):35-38.
[40]	JI Pan, ZHANG Tong, LI Hongdong, et al. Deep subspace clustering networks[C]//Proceedings of 2017 International Conference on Neural Information Processing. Red Hook: Curran Associates Inc, 2017: 23-32.
[41]	BO Deyu, WANG Xiao, SHI Chuan, et al. Structural deep clustering network[C]//Proceedings of 2020 Web Conference. New York: ACM Press, 2020: 1400-1410.
[42]	HINTON G E, SALAKHUTDINOV R R. Reducing the dimensionality of data with neural networks[J]. Science, 2006, 313(5786):504-507.
[43]	KIPF T, WELLING M. Semi-supervised classification with graph convolutional networks[EB/OL].[2023-08-01].https://arxiv.org/pdf/1609.02907v3.pdf.
[44]	HARRIE L, STIGMAR H, DJORDJEVIC M. Analytical estimation of map readability[J]. ISPRS International Journal of Geo-Information, 2015, 4(2):418-446.
[45]	邓红艳, 武芳, 翟仁健, 等. 基于多维约束空间的自动制图综合质量评估模型[J]. 中国矿业大学学报, 2006, 35(5):667-672.
	DENG Hongyan, WU Fang, ZHAI Renjian, et al. Quality evaluation model of automated cartographical generalization based on a multi-dimensional constraint space[J]. Journal of China University of Mining & Technology, 2006, 35(5):667-672.
[46]	吴洁, 李霖, 郭仁忠, 等. 数字环境下地图综合结果自动评价模型的研究与应用[J]. 测绘科学, 2002, 27(2):34-39.
	WU Jie, LI Lin, GUO Renzhong, et al. On automatic evaluation model of digital cartographic generalization[J]. Science of Surveying and Mapping, 2002, 27(2):34-39.

参量名称	计算方法	示意图
面积Area(v)	描述三角形大小的参量，通常使用公式Area(v)＝1/2a×h计算
最小外接矩形方向Oritation(v)	三角形最小接矩形在二维平面中的朝向，此处计算为朝向与x轴的夹角，Oritation(v)∈[0,1]
三角形底与高的比值Ratio(v)	三角形的形状可以由三角形底与高的比值，以及底边对角的角度唯一确定^[39](此处计算采用最长边作为底边)，Ratio(v)＝h/a
三角形底边对角的角度Angle(v)	三角形最长边对角的角度(此处计算采用最长边作为底边)，Angle(v)∈(0，π)
多比例尺综合约束距离Tolerant_Dis(v，δ)	描述三角形形态与综合约束距离δ之间的参量。当三角形一边与建筑物原始轮廓重合时，记该边到对角的距离为dis，则Tolerant_Dis(v，δ)＝e^{－max[(dis－δ)，0]}；若三角形有多条边与建筑物轮廓重合，则三边高均小于δ(点加密距离小于等于δ情况下)，因此Tolerant_Dis(v，δ)＝1；若三角形每一条边均不与建筑物轮廓重合，则dis为三边高的均值
三角形之间的距离Distance(u，v)	两三角形重心间的欧氏距离。(x₁，y₁)、(x₂，y₂)分别为两三角形重心坐标，Distan (u,

目标函数组合	准确率/(%)	精确率/(%)	召回率/(%)	F₁分数
无先验知识	85.55	96.16	81.56	0.882 6
	89.02	85.85	100.00	0.923 8
	95.09	96.92	95.66	0.962 9
	97.83	96.85	100.00	0.984 0

目标函数组合	准确率/(%)	精确率/(%)	召回率/(%)	F₁分数
无先验知识	58.09	93.79	51.43	0.664 4
	97.98	97.72	99.82	0.987 6
	75.72	97.10	72.04	0.827 2
	98.70	98.41	100.00	0.992 0

合并方法	δ/m	建筑物数量	建筑物间最小距离/m	建筑物轮廓长度/m	不合理连接面数量	居民地数量变化率/(%)	轮廓长度变化率/(%)	不同阈值下合并结果相似性/(%)
原始数据		119	0.85	9 395.3	—	—	—	—
图顶点深度聚类	7.5	26	9.13	7 652.6	0	78.15	18.55	77.34
图顶点深度聚类	12.5	8	13.76	6 012.3	0	93.28	36.01	77.34
ArcGIS面聚合	7.5	31	7.63	7 927.3	3	73.95	15.62	76.32
ArcGIS面聚合	12.5	9	13.12	6 087.5	2	92.44	35.21	76.32