2. 95007部队,广东 广州 510071
2. 95007 Troops, Guangzhou 510071, China
1 引 言
自动制图综合是制图和GIS领域一直没有得到根本解决的问题。由于建筑物空间分布和空间认知的复杂性,建筑物综合是自动制图综合中的一个难题。大比例尺和中等比例尺地图中的建筑物通常符号化为离散分布的多边形。随着地图比例尺的缩小,地图上的要素会变得拥挤而不易辨识。因此,许多建筑物必将被删除、合并、简化等。通过对人工制图综合过程的研究发现,建筑物综合包含两个连贯的步骤:第1步是将建筑物划分为不同的群组,即建筑物聚类;第2步是针对不同的建筑物群组执行不同的制图综合操作[1]。自动建筑物综合就是用计算机程序模拟这两个步骤。建筑物聚类是根据聚类规则将地图中的建筑物要素划分到不同的群组中。
2 建筑物聚类的研究现状诸多学者对建筑物聚类和综合的理论方法进行了深入研究。文献[2, 3]提出了构建和存储邻近图的模型和建筑物群典型化的方法。文献[4, 5]提出了基于Gestalt理论的3个原则实现建筑物聚类和综合的方法。文献[4, 5, 6, 7, 8]按建筑物顶点的Delaunay三角网与建筑物的关系,对建筑群进行分割和降维。文献[9]提出了多种无参数层次聚类图建立的邻近层次关系模型。文献[10]以点状空间目标群为例论证了利用邻近图对点状要素群进行层次聚类的可行性。文献[11]研究了Gestalt原理、Delaunay三角形和Voronoi图等技术,结合城市形态学和Gestalt理论提出了基于城市形态学的全局约束和基于Gestalt原理的局部约束的建筑物聚类方法。文献[1]将约束分层次地引入到建筑物聚类过程中,提出了基于分级约束的建筑物聚类方法。
建筑物聚类的约束条件(准则)可以分为两类:一类是基于城市形态学方法的全局约束准则,将道路和河流等线状要素的网络结构和线状要素与建筑物之间的关系作为全局约束条件,进行建筑物聚类;另一类是基于Gestalt原理的局部约束准则,根据Gestalt理论研究影响聚类的直观因素。应用于地图自动综合的Gestalt准则至少有8种,分别是[4, 5, 11]:邻近性(proximity)、相似性(similarity)、同向性(common orientations/directions)、连续性(continuity)、连通性(connectedness)、闭合性(closure)、同趋向性(common fate)、同区域性(common region)。其中前3个Gestalt准则是与建筑物的空间分布相关的因素。
3 自组织特征映射(SOM)神经网络SOM神经网络[12, 13, 14]是芬兰学者Kohonen提出的一种自组织竞争人工神经网络,由输入层和输出层(又称竞争层)组成。输入层与竞争层的神经元之间是全连接。竞争层神经元可以按照一维或者二维网络形式排列成一个神经元矩阵。图 1是二维竞争层的SOM网络结构。
SOM网络的基本工作原理是:网络采用无监督学习方式,将输入的n维空间数据映射到一个较低维(通常为一维或二维)的输出空间,同时保持数据原来的拓扑逻辑关系。SOM网络通过对待聚类输入模式的反复学习,捕捉各个输入模式中所含的模式特征,根据其特有的网络结构和学习规则,邻近的各个竞争层神经元彼此侧向交互作用,相互竞争,不断调整相关竞争层神经元与输入层神经元间的连接权值,在竞争层获得对输入模式的响应,实现功能相近的竞争层神经元在空间分布上的聚集,并以若干个神经元同时反映聚类结果。
SOM网络不需要大量的样本数据和人工干预,能够对数据进行自动聚集,智能化程度较高。SOM算法采用仅调整获胜神经元邻域内的神经元权值的学习训练方式,可以使特征相似的输入模式映射到竞争层的获胜神经元位置也是邻近的。这样在对数据进行压缩处理的同时保持了原始数据之间的拓扑关系和度量关系,可以实现制图综合中描述参数相似的建筑物的聚类。并且,SOM的自组织、自适应特点不需要预先设计聚类类别数目,通过确定竞争层的网格边长就可以较好地控制聚类的粒度问题。在不确定建筑物群聚类类别数目的情况下可以对建筑物群进行聚类。
4 基于SOM的建筑物智能聚类方法建筑物综合需要在水系、道路、湖泊等线状或面状要素的约束下进行,避免综合后与线状或面状地物要素发生冲突。同时,建筑物数量众多,建筑物综合处理时应尽量减少参与处理的建筑物数量。本文提出了基于SOM的建筑物群智能聚类方法,主要包含3个处理步骤,如图 2所示。
4.1 数据预处理在数据预处理阶段,主要利用建筑物多边形图层数据和线状要素图层(如道路、水系图层)数据进行建筑物多边形的相关参数计算。
本文中描述建筑物多边形的相关参数主要包括:
(1) 建筑物的重心坐标(centroid)根据建筑物多边形的数据计算每个建筑物的重心坐标。
(2) 相邻建筑物间的最短距离MinDisB2B,建筑物B1(p1,p2,…,pn,p1),建筑物B2(q1,q2,…,qm,q1)。建筑物B1的节点pi(i=1,2,…,n)到B2轮廓线段Lj(qj,q(j+1)mod(m))(j=1,2,…,m)的距离dij,建筑物B1的节点pi到B2轮廓线的最短距离di=1(dij),则建筑物B1到B2的最短距离d12=(di)。同理,建筑物B2到建筑物B1的最短距离为d21。相邻建筑物B1与B2之间的最短距离MinDisB2B选取d12与d21中数值较小者。
(3) 建筑物与邻近道路等线状要素的位置关系LocateB2L,沿线状要素的走向,计算建筑物B位于邻近线状要素L的左侧或右侧。建筑物B(p1,p2,…,pn,p1),道路R(r1,r2,…,rx)。若(rj,pi)与(rj,rj+1)的叉积大于0,则点pi在线段(rj,rj+1)的右侧;若叉积小于0,则点pi在线段(rj,rj+1)的左侧。
4.2 基于SOM进行建筑物群初步聚类当SOM网络的输入模式中各分量的值位于0和1之间时,可以使SOM网络的计算效果最好。本文选取建筑物重心centroid二维坐标归一化后的数据作为建筑物群初步聚类SOM网络的输入模式Ak=[a1k a2k … aNk],其中,k=1,2,…,p,p为待聚类的建筑物数量,N为输入层神经元数量,此处N=2。
文献[15]中描述SOM网络竞争层神经元数量M可以在满足SOM网络的模型结构的原则下任意设定。本文的竞争层神经元数量根据待聚类建筑物的数目和SOM网络的模型结构进行设置。
建筑物群初步聚类过程如下:
(1) SOM网络初始化,设置SOM网络竞争层神经元和输入层神经元之间的连接权向量Wj=[w1j w2j … wij],j=1,2,…,M,M为SOM网络竞争层神经元数目,wij为[0,1]区间内的随机值,i=1,2,…,N;并设置初始邻域半径σ(0)=6.0,初始学习率α(0)=0.1,训练迭代计数t=0。
(2) 随机选取一个待聚类输入模式Ak=[a1k a2k],提供给SOM网络的输入层神经元。
(3) 寻找获胜神经元:计算Ak与Wj的欧拉距离dkj=‖Ak-Wj‖,从中选出距离最小的神经元作为获胜神经元c,即dkc=(dkj)。
(4) 调整连接权值,对获胜神经元c邻域内任一被激活的神经元j的连接权向量Wj按照公式wij(t+1)=wij(t)+hcj(t)aik-wij(t)进行调整。其中,邻域函数;学习率函数α(t)=;T为训练迭代总次数;邻域半径函数σ(t)=σ0×0.2(t/T)。
(5) 重复步骤(2)~(4),直到没有新的输入模式。
(6) 训练迭代计数t=t+1,更新学习率α(t)以及邻域半径σ(t)。
(7) 重复步骤(2)~(6),直到训练迭代计数t达到预定的训练迭代总次数T。
SOM网络训练结束后,得到基于SOM网络的建筑物群初步聚类结果,即建筑物群类簇。
4.3 基于行列扫描的建筑物群精细聚类理想的SOM聚类结果是类簇间隔明显,界定分割线清晰。当分割线不明显时,需要对SOM网络的初步聚类结果进一步处理,完成建筑物群类簇的精细聚类划分。本文在SOM网络初步聚类结果的基础上,提出了基于行列扫描的类簇划分方法。
该处理方法的基本思路是:在有道路网等线状要素的情况中,在全局约束和Gestalt因素局部约束准则指导下,对SOM网络竞争层的m×m个神经元构成的二维平面网格进行行列扫描,实现对初步聚类结果的划分;在无道路网特别是河流等线状地物要素不构成封闭网络结构(多边形)的区域(尤其是郊区或城镇),仅在Gestalt因素约束准则指导下进行初步聚类结果的划分。
首先以行为主,依次扫描SOM网络竞争层的二维平面网格中每个格网单元。扫描到A单元时,以A格网单元为中心按照圈层向外扩张搜索,如图 3。当搜索到某一圈层中某个格网单元时,判断两个格网单元中聚类的建筑物间的最短距离MinDisB2B小于规定的建筑物群组内最短距离阀值,且建筑物与邻近道路等线状要素的位置关系LocateB2L中建筑物在同一个线状要素的同侧,就可以确定A格网单元与当前搜索到的网格单元属于同一群组,则终止对A格网单元的圈层扩张搜索,继续扫描下一个格网单元;如果判断条件不满足,则继续圈层搜索。如果圈层搜索完毕也不能确定A格网单元的群组属性,则将新的群组属性赋予A格网单元,继续扫描下一个格网单元。
根据行扫描结果,建立建筑物群组编号索引,记录每个群组中所包含的SOM竞争层的格网单元编号。建筑物群组编号与建筑物的编号关系如图 4。例如,编号Bp、Bp+q等建筑物聚集在SOM网络竞争层的第Cj编号的格网单元中,该格网单元属于第Gi个群组。
在此基础上,对SOM竞争层平面网格进行列扫描,即从左下角的格网单元开始按照以列为主的方式扫描格网单元。与行扫描类似,当扫描到C单元时,如图 5,以C格网单元为中心按照圈层向外扩张搜索,调整每个格网单元的群组属性,得到最终的建筑物群聚类结果。
经过以上3步(数据预处理、基于SOM的建筑物群初步聚类、初步聚类结果的行列扫描精细聚类)就实现了建筑物群的智能聚类。
5 试 验 5.1 试验1试验1使用城区大比例尺建筑物要素和道路要素矢量地图,其特点是建筑物与道路密集分布。图幅范围:长1400 m,宽1100 m。其中包含361个建筑物,70条道路。
根据待聚类的建筑物数目设置输出层神经元数目为M=m×m=40×40。建筑物智能聚类划分结果在SOM网络竞争层网格中的展示如图 6(a),图中空白格网单元表示没有建筑物聚集在该格网单元位置,被红色线条包围的相同颜色格网单元代表同一个建筑物群组中聚类在这些格网单元位置的建筑物。建筑物群聚类结果展示在地图中的效果如图 6(b),相同颜色的建筑物属于同一个聚类群组。
5.2 试验2
试验2使用城乡结合区域的建筑物要素矢量地图,该区域既有建筑物密集区,也有建筑物零散分布区。图幅范围:长2800 m,宽4900 m;其中包含3475个建筑物。
在建筑物零散分布的区域没有道路等线状要素地物,因此试验2是在没有线状要素约束,仅考虑Gestalt因素约束条件下实现基于SOM的建筑物智能聚类。根据待聚类的建筑物数目设置输出层神经元数目为M=m×m=100×100。聚类效果如图 7所示,图中黑色较粗的轮廓线表示聚类群组边界示意,轮廓线内相同颜色的建筑物属于同一个聚类群组。
6 结 论通过分析地图制图综合、SOM神经网络等特征,以特大城市大比例尺地图建筑物要素为例,本文提出基于SOM的建筑物智能聚类方法,实现具有地图认知能力的建筑物要素自动聚类。
基于SOM的建筑物智能聚类方法依据建筑物地理位置、相邻建筑物之间距离,以及建筑物与邻近线状要素(道路、河流等)的空间关系等影响因子,实现建筑物智能聚类。在建筑物要素密集而且规则分布的城区,该智能聚类方法能够在线状要素(如道路)约束下将距离较近的建筑物划分在一个群组内。在建筑物零散分布的郊区或农村,缺少道路约束的条件下,该方法也能根据建筑物之间的距离进行聚类,符合制图要求。
下一步的工作将着重进行如下研究:增加建筑物的相关描述参数作为SOM网络的输入,如建筑物的方向、形状、面积以及高度等,使建筑物的描述更加细致,聚类群组划分更加精确;同时相应调整SOM网络的相关参数,如邻域大小、初始权值、学习率等,研究相关参数对建筑物群聚类结果的影响。
[1] | QI H B, LI Z L. An Approach to Building Grouping Based on Hierarchical Constraints[C]//Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Beijing:[s.n.], 2008: 449-454. |
[2] | REGNAULD N. Contextual Building Typification in Automated Map Generalization[J].Algorithmica,2001,30:312-333. |
[3] | REGNAULD N. Spatial Structures to Support Automatic Generalization[C]//Proceedings of International Cartographic Conference.Coruoa:[s.n.], 2005. |
[4] | YAN Haowen, WEIBEL R, YANG Bisheng. A Multi-parameter Approach to Automated Building Grouping and Generalization[J]. Geoinformatica, 2008, 12(1): 73-89. |
[5] | 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(l): 51-54. (闫浩文, 应申, 李霖. 多因子影响的地图居民地自动聚群与综合研究[J]. 武汉大学学报:信息科学版, 2008, 33(l): 51-54.) |
[6] | AI Tinghua, ZHANG Xiang. The Aggregation of Urban Building Clusters Based on the Skeleton Partitioning of Gap Space[C]//Proceedings of the European Information Society, Lecture Notes in Geoinformation and Cartography.[S.l.]:Springer,2007: 153-170. |
[7] | AI Tinghua, GUO Renzhong. Polygon Cluster Pattern Mining Based on Gestalt Principles[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 302-308. (艾廷华, 郭仁忠. 基于格式塔识别原则挖掘空间分布模式[J]. 测绘学报, 2007, 36(3): 302-308.) |
[8] | QIAN Haizhong, WU Fang, ZHU Kunpeng, et al. A Generalization Method of Street Block Based on Dimension-reducing Technique[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(1): 102-107. (钱海忠, 武芳, 朱鲲鹏, 等. 一种基于降维技术的街区综合方法[J]. 测绘学报, 2007, 36(1): 102-107. ) |
[9] | ANDERS K H. A Hierarchical Graph-clustering Approach to Find Groups of Objects[C]//Proceedings of ICA Commission on Map Generalization, 5th Workshop on Progress in Automated Map Generalization.Paris: IGN, 2003:28-35. |
[10] | GUO Qingsheng, ZHENG Chunyan, HU Huake. Hierarchical Clustering Method of Group of Points Based on the Neighborhood Graph[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2):256-261. (郭庆胜, 郑春燕, 胡华科. 基于邻近图的点群层次聚类方法的研究[J]. 测绘学报, 2008, 37(2): 256-261.) |
[11] | 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, 18 (5): 513-534. |
[12] | QIN Xiao, YUAN Changan. Text Clustering Method Based on Genetic Algorithm and SOM Network[J]. Computer Application, 2008, 28(3): 757-760. (覃晓, 元昌安. 基于遗传算法和自组织特征映射网络的文本聚类方法[J]. 计算机应用, 2008, 28(3): 757-760.) |
[13] | XU Yangbin. A SOM-based Text Clustering and Apply to Search Result[D]. Xi’an: Xidian University, 2007. (徐仰彬. 基于SOM的文本聚类及其在搜索结果中的应用[D]. 西安: 西安电子科技大学, 2007.) |
[14] | CHEN Tao. Word Clustering Based on Self-organizing Map[D]. Beijing: Tsinghua University, 2004. (陈涛. 基于自组织映射神经网络的词自动聚类[D]. 北京: 清华大学, 2004.) |
[15] | JIANG Bin, HARRIE L. Selection of Streets from a Network Using Self-organizing Maps[J]. Transaction in GIS, 2004, 8(3): 335-350. |
[16] | STEINIGER S, TAILLANDIER P, WEIBEL R. Utilising Urban Context Recognition and Machine Learning to Improve the Generalisation of Buildings[J]. International Journal of Geographical Information Science, 2010,24(2): 253-282. |
[17] | YING Shen, GUO Renzhong, YAN Haowen, et al. Framework Design and Implementation of Model-oriented Cartographic Generalization[J]. Acta Geodaetica et Cartographica Sinica, 2002,31(4): 344-349. (应申, 郭仁忠, 闫浩文, 等. 面向模型的大比例尺制图综合框架设计与实现[J]. 测绘学报, 2002,31(4): 344-349.) |
[18] | YOU Xiong. The Action of Visual Sensation and Perception on Cartographic Generalization[J]. Acta Geodaetica et Cartographica Sinica, 1992, 21(3): 224-232. (游雄. 视觉感知对制图综合的作用[J]. 测绘学报, 1992, 21(3): 224-232.) |
[19] | SUN Qianhu. Research on Buildings Clustering Methods Based on Multi-constraints[D]. Changsha: Central South University, 2011. (孙前虎. 基于多约束的建筑物群聚类方法研究[D]. 长沙: 中南大学, 2011.) |
[20] | GUO Qingsheng, LI Hongsheng, LIU Jiping. BuildingsProgressive Typification Based on Weighted Mesh Simplification[J]. Geomatics and Information Science of Wuhan University, 2005, 30(4): 293-296. (郭庆胜, 李洪省, 刘纪平. 基于加权网格简化的建筑物群渐进式典型化[J]. 武汉大学学报:信息科学版, 2005, 30(4): 293-296.) |