城市建筑群网格模式的图论识别方法

巩现勇,武 芳

1.信息工程大学地理空间信息学院,河南郑州 450052;2.地理信息工程国家重点实验室,陕西西安 710054

城市建筑群网格模式的图论识别方法

巩现勇1,2,武 芳1

1.信息工程大学地理空间信息学院,河南郑州 450052;2.地理信息工程国家重点实验室,陕西西安 710054

建筑群空间分布模式体现了城市的物质形式及其与社会经济功能之间的关系,反映了城市的空间结构特征,对于制图综合和多尺度表达等具有重要意义。结合国内外对该问题的研究,提出基于图论的建筑群网格模式识别方法。首先分析研究网格模式的认知特征和定义。然后利用Delaunay三角网构建建筑群的邻近关系,生成邻近图;从Gestalt视觉准则出发,基于三角剖分模型建立视觉距离;考虑直线模式的直线性、紧凑性等约束条件识别出交叉的多连通直线模式。最后对直线模式建立相交图和方向关系图,通过求解极大完全子图、连接、相交和后期修建等图运算,实现网格模式的识别。试验表明该方法能够识别出明显网格模式,其识别结果符合人类空间认知特点。

制图综合;建筑群;网格模式;模式识别;图论

1 引 言

如何从矢量地图中自动挖掘隐含的知识、关系或内在模式,并指导地图设计编绘和时空数据更新等,一直是困扰地图学者的难题[1-2]。空间分布模式是指核心地理要素在空间分布形态上表现出的可以明确命名且能够识别的形状或排列[2],是空间数据增强的基本内容之一,是多尺度、多时相时空关联的关键技术,对于多模式时空综合、多尺度表达、时空数据更新、时空数据挖掘、空间推理、智能交通系统、区位经济和城市规划等具有重要理论意义和应用价值[1-5]。

空间模式,从所涉及的知识类别出发,有两种:一是空间(多)变量在连续或离散空间中表现出的分布规律性、异常性、时空趋势和时空关联性,属于空间统计范畴,关注语义信息的内涵;二是地理要素在邻近地理空间中所体现出的组织、布局、排列以及功能上显著的空间结构和关系,即本文的研究范畴,称之为地图的空间分布模式,关注空间的外延。建筑群的空间分布是制图综合、多尺度表达和时空数据更新等必须考虑和保持的空间特征,其自动识别则属于空间推理范畴,是时空数据挖掘的研究热点和难点之一[2-5]。在小比例尺地图上,建筑群综合考虑空间和语义特点,主要基于自然属性和网络要素(道路、水系等)划分[6-7];对于中大比例尺的建筑群分布,当前研究多集中于聚群分组,主要包括两个过程[5,8-9]:①基于最小支撑树的空间聚类;②基于Gestalt原则的多参数控制的后期修剪。在此基础上,还有多参数控制法、区域综合法、智能优化法等实现建筑群自动聚群[10-14]。然而,这些研究只是对建筑群进行了初步的粗略聚群,其聚群粒度大小不一,地理意义模糊,不能高效建立时空关联,不能够满足多尺度表达与制图综合等需要;而且聚群结果形态复杂、不规则,大多数不可名状,不能精确刻画建筑群的空间分布特征。因此有必要更进一步探测、识别隐含于建筑群的空间模式信息。文献[15]通过对上述基于图识别方法中的邻近图进行反复修剪,来实现直线模式的挖掘;文献[16]采用直线模板匹配方法进行直线排列结构的识别;文献[17]直接利用邻近关系图识别网格模式用于建筑物典型化。

网格模式是建筑群分布的典型模式之一,常见于规划整齐的城市小区等。本文在前期研究基础之上,基于图论进行建筑群网格模式识别,需要解决以下3个问题:①网格模式的认知特征和定义;②识别建筑群的基本模式——直线型;③利用已有的直线模式进行网格模式的识别。

2 建筑群网格模式的认知特征

熟悉和有意义的事物容易成为知觉对象。根据心理学的信息论度量方法,典型的、有意义的空间结构特征是(视觉)信息最集中的地方。结构特征识别是人类对空间信息进行感知、识别和推理的过程,是地图句法学的重要研究内容。建筑群的空间分布具有丰富的几何结构模式,具有整体感、秩序感、均衡感、空间感。人类对建筑群模式的视觉思维认知具有选择性、注视性和结构联想性。研究人类对建筑群模式的空间认知规律,可以有效指导算法设计,为计算机进行建筑群模式的自动识别提供理论依据和技术支持。

网格模式是建筑群的典型模式之一,其拓扑感知关系具有层次性:如图1(a)中,从宏观上看,网格模式由一组近似平行分布的直线排列建筑群与另一组近似平行的直线排列建筑群,以近似正交的方式相交构成;从微观上看,网格模式由一组尺寸、形状等相似的建筑物构成,而建筑物之间的空间分布满足特定的排列方式——直线排列。本文采用自下而上的思想,首先通过建筑群的相似特性(形状、方向和距离)及特定排列规律(直线分布)识别直线模式,然后基于直线模式的特定组合(正交关系)实现网格模式的识别。

直线模式的正确识别是网格模式识别的前提和保障。直线是视知觉拓扑理论的基本要素,是指点在空间内沿相同或相反方向运动的轨迹。建筑群直线模式是城市建筑群在宏观层次上表现出来的一种有规律的空间分布、配置。在中、大比例尺地图上,建筑物表现为几何形态上的多边形,具有方向、形状等几何特征,即本文下述的单个建筑物自身的局部变量。由此,根据单个建筑的局部方向和一个建筑群模式的全局方向两者之间的关系,建筑群直线模式有广义(松弛约束,linear line)和狭义(严格约束,straight line)之分。大量认知研究和试验表明,对于建筑群,狭义的直线模式应满足两方面:①模式群内部的各个建筑的局部方向一致,且模式的全局方向与各建筑物的主方向近似相同(如图1(b))或正交(如图1(c));②模式内各建筑物在形状、大小和方向等方面“相似”。狭义直线模式是视知觉认知的直接结果,其分布形态最容易受人类视知觉的感知和捕获。广义的直线模式是指模式群内建筑的局部方向不一致而其质心大致呈直线分布(如图1(d)),或者虽然局部方向一致但与群模式的全局方向呈“斜直线”分布(如图1(e))。由广义直线模式相交构成的空间群分布在视知觉拓扑层次上不能较好地满足严格意义上的网格模式的定义(如图1(f))。

图1 网格模式的认知特征Fig.1 Cognitive characteristics of grid pattern

3 多连通直线模式信息提取方法和步骤

模式应从几何、拓扑、环境上下文和文化差异等方面保证其易读性、简洁性和可分辨性。直线模式是最简洁、最直接的模式,是网格模式识别的基础。其影响因素至少有:模式与背景、邻近性、相似性、方向性、连通性、连续性、完整和闭合性、同趋势性和简洁性等。其中,模式与背景是视觉选择性的结果,主要解决模式存在的意义和价值,是模式识别的动机;连通性可以用邻近性代替(两目标距离为0);连续性、完整和闭合性可以由邻近性、相似性与方向性得到;同趋势性在静态地图中不存在;构型的简洁性为已知因素,即需要识别的感兴趣的建筑群分布模式。因此在建筑群模式识别时,只考虑邻近性、相似性和方向性[10,18]。文献[8,10,18—19]深入研究了用于建筑群自动聚群的Gestalt原则,都从不同方面验证了利用距离、大小、方向三者的组合能够表达邻近性、相似性和方向性等三者的主要矛盾,并通过不同类型的数据验证了其可行性和有效性。

因此,考虑到人作为认知主体在感知、识别和推理直线模式时主要参考其直线性、紧凑性和相似性等组织规律,此处结合数学方法和几何模型,以建筑物的大小、方向和距离等3个基本参数建立认知意义上的直线模式结构化参数(表1),用以描述模式的形态和结构规则,从而作为约束条件进行直线模式的提取。

表1 直线模式结构化参数Tab.1 Structural parameters for linear pattern

在结构化参数中,局部和全局方向差异对模式的直线构型至关重要。其中,局部方向差异仅能保证相邻两建筑物的方向差异满足直线模式要求,而全局方向差异在整体上使得整个直线模式的局部方向差异的方差满足直线特征,从而避免仅由局部方向差异约束而引起的圆弧形或蛇形排列的出现,如图2(a)、(b)。

图2 圆弧形和蛇形排列Fig.2 Arc-like and snake-like alignment

文献[15—16]识别出的直线模式具有单连通性,只能满足某个方向的直线模式的识别,不允许模式的相交。这不符合人类“横看成岭侧成峰”的认知心理,亦不能支持网格模式识别。一个建筑物参与多个直线模式时会产生直线模式的相交现象。为允许不同方向相互交叉的直线模式的存在,本文通过以下方法和步骤进行提取:

(1)空间邻近关系捕捉。对建筑物多边形沿线加密,并建立Delaunay三角网,如图3(a)。删除建筑物内部及其凹部的三角元,如图3(b)。对剩余的通视域三角元建立骨架线,实现建筑群剖分,如图3(c)。用图表达邻近关系,图的节点表示建筑物的质心,图的边表明两个建筑物被其之间的通视域三角元直接相连,如图3(d)。此步骤保证了Gestalt原则中的邻近性。

(2)异质性修剪。设置面积比、正对投影长度的阈值δArea和δface;遍历邻近图的所有边,若被其连接的两个建筑物正对投影长度小于δface(图3 (e)虚线),或者面积比小于δArea(图3(f)虚线),则删除该边。其中,利用面积比修剪保证Gestalt原则中的大小相似性,利用正对投影长度修剪保证直线模式的方向性。

(3)构建视觉距离加权图。对于图3(c),定义两个建筑物间的视觉距离为

(4)直线模式提取。经过每个节点的直线模式的数目不可能大于其连通度。记连接点v的连通度为Degree(v),其被访问的次数为Visited-Count(v),设方向和视觉距离容差分别为δorient和δdis,则直线模式的提取算法如下:

步骤1选择一个建筑物作为种子起点v0。

步骤2访问与v0相接的点vi,如果Visited-Count(vi)＝Degree(vi),则结束当前模式链;否者,判断Degree(vi):

步骤2-1 Degree(vi)＝1,若满足直线条件,则此连接点为直线模式的一部分,加入当前模式链表;否则结束当前模式链提取。重新选择种子起点,goto步骤2。Visited Count(vi)加1。

步骤2-2 Degree(vi)＞1,若存在满足直线条件的边,则加入当前模式链表;否则,以此节点为种子起点,新建模式链表,goto步骤2。Visited-Count(vi)加1。

步骤3如果邻近图所有节点均满足Visited-Count(vi)＝Degree(vi),整个图层的直线模式提取过程结束。

注:直线条件是指边内侧夹角与当前模式链表建筑群全局方向差异的百分比在δorient以内,视觉距离差异与当前模式链表建筑群视觉距离的平均值的百分比在δdis以内。

图3 直线模式提取过程Fig.3 Process of linear pattern extraction

以上步骤可初步识别出多连通直线模式,如图3(g)。其优点在于:①识别过程仅涉及距离、大小和方向等参数,参数意义明确,易于理解;②利用节点的连通度控制对邻近图的多次扫描,实现了所有可能方向的直线模式的提取,保证其完备性,且为网格模式识别提供支持;③对同质性修剪之后的邻近图进行视觉距离加权,降低算法的时间复杂度。其中,降低算法的时间复杂度主要体现在步骤2与步骤3的执行顺序上。相较于现有文献[8,15]计算每个边的视觉距离而言,本文先进行同质性修剪,则只需要对邻近图中满足面积比和正对投影长度比的边进行视觉距离的计算。算法运行减少的复杂度等于同质性修剪掉的边的数目。例如对于图3,本文方法减少了10条边(图3(e)修剪掉8条、图3(f)修剪掉2条)的视觉距离的计算代价。

4 基于图论的网格模式识别

图论是研究事物相互关系的抽象代数。网格模式由相互近似正交的直线模式构成。本文在直线模式识别的基础上,根据网格模式的认知特点,通过图论算法识别 “垂直交错”的直线模式,从而提取网格模式。图论关键定义如下。

定义1:在图G＝〈V,E〉中,若从节点vi出发,沿一些边经过一些节点vp1、vp2、…、vpm,到达节点vj,则称节点序列(vp1,vp2,…,vpm)为从节点vi到节点vj的路径(path)。

定义2:在无向图中,若从节点vi到节点vj有路径,则称节点vi与vj是连通的(connected)。

定义3:如果图中任意一对节点都是连通的,则称此图是连通图(connected graph)。

定义4:非连通图的极大连通子图叫作连通分量(connected component)。

定义5:Intersection运算,是指两个或多个图的交集,只有两个或多个图中均存在的边才会保留到Intersection运算结果中。即:对于图G1＝〈V1, E1〉和图G2＝〈V2,E2〉,所有ei∈E1且ei∈E2,则图GIntersection＝{〈vi,ei〉|ei∈E1且ei∈E2}称为G1与G2的Intersection运算的结果。

定义6:Jion运算,是指在图G1＝〈V1,E1〉和图G2＝〈V2,E2〉中,对于所有∀vp∈V1且所有∀vq∈V2,连接vp,vq所组成边ei＝〈vp,vq〉作为Join运算结果图的边。即图GJoin＝{〈vi, ei〉|ei＝〈vp,vq〉,∀vp∈V1且∀vq∈V2}称为G1与G2的Join运算的结果。

由第2节网格模式认知的层次性特点可知,组成网格模式的直线模式之间需要满足以下3点:①每组直线模式近似平行;②两组直线模式近似正交;③两组直线模式具有连接关系(相交或相接)。对应于以上3点要求,利用图论识别网格模式的基本思想是:①根据方向关系图计算近似平行的直线模式组;②选取近似正交的所有直线模式组进行Join运算,得到所有可能的网格模式;③将之与直线模式的连接图进行Intersection运算,保留那些具有连接关系的直线模式组,剔除那些不相交和不相接的直线模式组。通过以上3步可获得初始的网格模式,对其进行后期修剪得出建筑群的网格模式。以图4(a)为例,网格模式提取算法的流程如下:

(1)根据第2节算法提取建筑群的多连通直线模式。建立直线模式的连接图G＝〈V,E〉。图的节点V代表直线模式,节点之间的连接E表示两个直线模式相交或者相接。如图4(a)中,直线模式{1,2,3}与{4,5,6}相交,{8,9,10,11}与{12,13}相交。则此建筑群的连接图如图4(b)所示。该步骤能够保证组成网格的直线模式组均相交或者相接。例如{7}与{1,2,3}虽然存在正交关系,但由于不存在连接关系,因此不能构成网格,将在下文步骤(5)中被排除。

(2)建立建筑群直线模式的方向关系图ORG＝〈OV,OE〉,图的节点OV代表直线模式,节点之间的连接OE表示两相连的直线模式具有近似相同的方向(平行或者共线),两者可以不相交或者不相接。如图4(c)中,直线模式组{1,2,3}、{4,5,6,7}、{8,9,10,11}、{12,13}分别具有近似相同的方向。该步骤提取了所有可能形成网格的直线模式。

(3)提取方向关系图ORG的连通分量ORG_ CC。如果ORG只有一个连通分量,则说明要么不存在网格模式,要么方向阈值设置过大,应考虑重新设置。这是因为若只有一个连通分量,则所有直线模式的角度都近似相同,从而导致无法构成网格。阈值设置为10°时,从图4(c)中提取得到4个方向连通子图A、B、C和D,见图4(c)中虚线椭圆框。该步骤的作用是提取近似平行的直线模式组。

(4)方向关系图分组。对方向关系图ORG的每个连通分量ORG_CC,求解其极大完全子图ORG_CC_max。完全子图是指每个节点都与其他所有节点相连的一种满秩图。该步骤可以剔除某些孤立直线模式,将直线模式强制分为特定组,每个组内的直线模式方向相似(平行或者共线)。图4(c)中的子图A、B、C、D均已是极大完全子图。

(5)初始网格模式信息提取。计算步骤(4)中每个极大完全子图ORG_CC_max的平均方向,利用阈值控制选取方向近似正交的两个极大完全子图进行Join连接运算,其结果与连接图G进行Intersection相交运算。其中Join连接运算的目的是保留所有具有正交关系的直线模式,如图4(d)中所示的{1,2,3}与{4,5,6,7},{8,9,10, 11}与{12,13}分别近似正交;而Intersection运算是为了剔除那些不相交或者不相接的直线模式,如图4(d)中虚线所示的{7}由于与{1,2,3}既不相交也不相接,因此在此运算下被剔除。经过以上两个图运算,剩下来的节点满足相连且正交,如图4(d)中的实线所示。由此便得到了初始的网络InitG,如图4(e)。

(6)网络模式提取。计算Init G的连通分量,每一个连通分量即为一个网格模式。如图4(e)中计算的两个网格模式的连通分量分别为GA＝{1,2,3,4,5,6}和GB＝{8,9,10,11,12,13}。

(7)网络模式后期处理。步骤(6)提取的网格模式可能会存在“毛刺”或者“尾巴”等不合理之处。剔除此类不合理建筑物的处理方法是:将直线模式在线的节点处打断成弧段,循环删除连通度小于2的建筑节点。如图4(f)中斜线填充的建筑物均从GA和GB中被剔除。由此得到网格模式的最终结果如图4(f)所示。

图4 网格模式识别过程Fig.4 Process of grid pattern recognition

本文算法进行网格模式识别主要具有以下优点:①采用“分解—组合”的思想,按照其认知特点的层次性,将网格模式这一复杂的非线性认知概念分解为直线模式这一线性认知概念的正交组合,认知意义更加简洁;②网格模式提取过程仅涉及方向这一类参数,参数的地理含义明确,便于调整;③在直线模式基础之上进行网格模式的识别,充分利用了连续多尺度的数据。对于地图综合和多尺度表达等问题,地理信息的处理顺序是由大比例尺向小比例尺逐级级联渐进进行的,例如由1∶1000综合生成1∶5000数据,再由1∶5000综合生成1∶10 000数据。因此,地理信息聚集的粒度由小到大。直线模式是一组建筑物,而网格模式则是一组直线模式,“建筑物—直线模式—网格模式”是空间域粒度由小变大的层次关系,亦即对应不同比例尺的地图。由直线模式提取识别网格模式,充分利用了上一比例尺的直线模式信息。

5 试验与讨论

5.1 试 验

为检验上述识别方法的有效性,本文基于Arc Engine设计实现了以上算法,并融入课题组试验平台GxGIS。为更好体现本文算法的合理性和适用性,试验分为两组,采用两组不同空间分布特点的数据进行测试。试验中直线模式提取的5种参数的范围均为[0,1],参数设置的指导思想是:面积比阈值和正对投影长度的阈值越大(经验取值[0.6,1]),局部方向差异、全局方向差异和视觉距离容差越小(经验取值[0,0.4]),模式的直线性越强。网格模式提取过程中,方向关系图计算连通分量的方向阈值经验范围为[0°,10°],近似正交是指角度在[80°,100°]内。

试验数据1为某城市1∶10 000地图上的部分建筑群,试验区域包含18个小区,162个建筑物,如图5(a)。该试验区域建筑群方向分布多数相近,但一阶邻域内要素的形状有不同程度的变化;建筑群密集,但不均匀。不同方向、不同大小的建筑物交错相邻分布,存在一定的空间异质性,整体分布上没有全局平稳的特征,但在某些方向上较为平稳,因此在视知觉上呈现出明显的直线模式,网格模式分布现象并不太直观和明显。参考前人经验[4,15],经过反复测试,参数设置如表2。识别出的多连通直线模式如图5(b),提取的网格模式如图5(c)。

试验数据2为德国南部某城市地图上的部分建筑群,数据源自OpenStreet Map,比例尺为1∶3000。试验区域包含12个小区,168个建筑物,如图6(a)。该试验区域建筑群方向分布近似相近,一阶邻域内要素的形状变化较小,建筑群密集且均匀。空间同质性较好,异质性表现不明显,整体上分布平稳,剧烈抖动现象较少。在视知觉上呈现出明显的直线模式和网格模式等分布现象。经过反复测试,参数设置如表2,识别出的多连通直线模式如图6(b),提取的网格模式如图6(c)。

表2 参数设置Tab.2 Advisable parameter setting

图5 网格模式识别试验结果Fig.5 Experiment results of grid pattern recognition

图6 网格模式识别试验结果Fig.6 Experiment results of grid pattern recognition

5.2 讨 论

5.2.1 跨街区形成模式

由于没有考虑道路、水系等其他具有网络特征的要素的空间分割和限制,单图层的建筑群模式识别允许跨街区组成直线或者网格模式,如图5(b)、(c)与图6(b)、(c)。城市空间的形态划分,一方面是应用多尺度表达的层次划分方法,需要从地理尺度、影像分辨率、地图载负量限制等方面考虑其合理性和适用性[20-21];另一方面需要兼顾建筑群的空间分布和形态等自然地理特征。为此, AGENT项目组利用多图层协同辅助的方法,提出了基于区域划分的思想,对水系、道路、境界等进行关联,形成拓扑网络,将待综合区域进行形态划分[6]。本文试验中以城市主干路网形成的街区为参考网络要素,其划分结果如图5(d)、图6(d)。

5.2.2 阈 值

首先,对于不同类型的模式,阈值由模式的特征决定,例如直线模式的直线性、紧密性,网格模式的垂直相交关系等。其次,对于同一种模式,不同的数据由于空间分布状况不同,可能需要对阈值进行微调,但必须符合模式的视觉特征约束。因此对于不同的数据,阈值不会发生太大的变化。例如5.1节两组不同的试验数据,虽然其参数阈值设置是不同的,但变化并不大(表2)。如图7中,若仅考虑正对投影长度比而忽略其他因素对多连通直线模式的影响,图7(a)、(b)、(c)分别为正对投影长度比阈值取0.95、0.85、0.8的试验结果。对比图7发现,随着正对投影长度比阈值的放宽,直线模式的曲率越大,即由严格约束的狭义直线向松弛约束的广义直线过度。最后,对于退化现象比较严重的直线模式,参数阈值因对模式形态的关注点不同而不同。例如只关注建筑群质心位于同一条直线,不考虑形状、方向等因素影响的退化直线模式。如图8中椭圆框出的4个建筑物的主方向分别为121.68°、120.54°、10.31°和13.5°,当方向阈值放宽至0.08时,由于椭圆框中的要素的质心排列与其下方的直线模式为近似直线,因而被纳入成为直线模式的一部分。

图7 正对面积比影响Fig.7 Facing ratio effect

图8 直线退化现象Fig.8 Degeneration of line pattern

5.2.3 形状信息

建筑群分布模式对建筑群的形状有很强的依赖性。基于大多数建筑物的规则性考虑,本文将建筑物抽象为其最小面积外接矩形,用于描述其方向和正对投影长度,在一定程度上造成了形状信息的损失。如何用定量化模型描述形状一直是GIS必须面对的难题[22]。对于少数的矩形度较小的非规则建筑物影响较大,其分布模式的退化现象较严重,可以放宽对形状参数(如面积比和正对投影长度比)的限制,如图8中示例。

5.2.4 方向的度量

不同的方向度量方法也可能会对识别结果产生影响。文献[23]对现有的各种度量方法进行了深入剖析,并对较典型的Longest edge、Weighted Bisector、Smallest MBR、Wall average和Statistical weighting等5种方法进行了详细的对比,认为Smallest MBR方法最优,被研究和认同的范围较广[23]。即本文采用的最小面积外接矩形方法。对于方向度量方法的影响:首先,每种度量方法计算的方向肯定是唯一的、不变的;其次,建筑群模式识别的方向约束为两个建筑物之间的相对方向。因此,只要选定某种方向度量方法,则在模式识别过程中,方向容差的阈值δorient是可以固定的。但由于不同的度量方法计算所得的建筑物的方向可能不同,因此会影响识别结果。

5.2.5 进一步分析和评估结果的可靠性

视觉认知易受人类的个体差异性和主观性的影响,如环境、性别、年龄、教育背景和生长环境等。如图9中,由于箭头指向的噪声建筑物的缺失或存在,对建筑群网格模式的认知造成了一定的影响,不同的认知主体可能会产生不同的认知结果。目前,尚无定量的方法来客观评价基于视知觉空间认知的聚群结果的可靠性,这一直是该领域和心理学界的一个难题。国内外仍都是通过人眼观察或者与人工标绘的结果进行对比,从而评价聚群结果的可靠性,如文献[2,4—14]。根据认知心理学试验方法的要求,本文通过问卷调查的方式评价结果的可靠性。调查对象为4名制图生产单位工程师、3名助理工程师、1名地图专业讲师、42名地图专业学生。通过不同区域数据测试的调查结果表明,本文方法的可信度在67%以上。

图9 网格模式的认知影响Fig.9 Cognitive effects of grid pattern

6 结 论

由于矢量数据的离散性和稀疏性等,对其进行空间知识挖掘一直是一个难题。本文首先分析了网格模式的认知特点,界定了直线模式和网格模式的定义。通过参数判别法挖掘隐含于建筑群中的多连通直线模式,利用结构化参数直接对邻近图进行反复修剪,一定程度上克服了现有方法的不足,所提取出的直线模式允许相交现象,更加符合人类空间认知特点,亦为建筑群网格模式识别提供了支撑。依据网格模式垂直相交的特点,通过图论算法,对已识别出的多连通直线模式进行图操作,进而识别网格模式,识别结果基本能够符合人类认知。需要进一步研究的问题主要包括:①视知觉拓扑理论对模式识别的指导意义及其参数化表示;②模式的结构化参数的各种阈值等需要经过反复试验确定;③空间对象的形状定量描述模型。

[1] WU Fang,QIAN Haizhong,DENG Hongyan,et al.Intelligent Spatial Information Processing for Automated Map Generalization[M].Beijing:Science Press,2008: 292-305.(武芳,钱海忠,邓红艳,等.面向地图自动综合的空间信息智能处理[M].北京:科学出版社,2008: 292-305.)

[2] STEINIGER S.Enabling Pattern-ware Automated Map Generalization[D].Zurich:Zurich University,2007.

[3] RUIZ J J,ARIZA F J,URENA M A,et al.Digital Map Conflation:a Review of the Process and a Proposal for Classification[J].International Journal of Geographical Information Science,2011,25(9):1439-1466.

[4] QI Hhuabin.Detection and Generalization of Changes in Settlements for Automated Digital Map Updating[D].Hong Kong:The Hong Kong Polytechnic University,2009.

[5] LI Zhilin,YAN Haowen,AI Tinghua,et al.Automated Building Generalization Based on Urban Morphology and Gestalt Theory[J].International Journal of Geographical Information Science,2004,18(5):514-534.

[6] UNI-ED,IGN.Strategic Algorithms Using Organisations [R].Unizh:ESPRIT/LTR,2001.

[7] WU Fang,QIAN Haizhong,DENG Hongyan,et al.Quality Evaluation Model for Automated Map Generalization[M].Beijing:Science Press,2009:11-64.(武芳,钱海忠,邓红艳,等.地图自动综合质量评估模型[M].北京:科学出版社,2009:11-64.)

[8] 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.)

[9] ZHAO Binbin,DENG Min,LI Guangqiang,et al.A New Hierarchical Spatial Index Based on Urban Morphology.[J].Acta Geodaetica et Cartographica Sinica,2010,39 (4):435-440.(赵彬彬,邓敏,李光强,等.基于城市形态学原理的面状地物层次索引方法[J].测绘学报,2010,39 (4):435-440.)

[10] YAN Haowen,WEIBEL R,YANG Bisheng.A Multiparameter Approach to Automated Building Grouping and Generalization[J].Geoinformatica,2008,12(1):73-89.

[11] BASARANER M,SELCUK M.A Structure Recognition Technique in Contextual Generalization of Buildings and Built-up Areas[J].The Cartographic Journal,2008,45 (4):274-285.

[12] ALLOUCHE M K,MOULIN B.Amalgamation in Cartographic Generalization Using Kohonen’s Feature Sets[J].International Journal of Geographical Information Science, 2005,19(8-9):899-914.

[13] SESTER M.Optimization Approaches for Generalization and Data Abstraction[J].International Journal of Geographical Information Science,2005,19(8):871-897.[14] REGN A ULD N.Contextual Building Typification in Automated Map Generalization[J].Algorithmica,2001, 30(2):312-333.

[15] ZHANG Xiang,AI Tinghua,STOTER J,et al.Building Pattern Recognition in Topographic Data:Examples on Collinear and Curvilinear Alignments[J].GeoInformatica, 2013,17(1):1-33.

[16] RAINSFORD D,MACKNESS W.Template Matching in Support of Generalization of Rural Buildings[C]∥Proceedings of the 10th International Symposium on Spatial Data Handling.Berlin:Springer,2002:137-151.

[17] ANDERS K H.Grid Typification[C]∥Proceedings of the 12th International Symposium on Spatial Data Handling.Berlin:Springer,2006:633-642.

[18] Y AN 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.(闫浩文,应申,李霖.多因子影响的地图居民地自动聚群与综合研究[J].武汉大学学报:信息科学版,2008,33(1):51-54.)

[19] AI Tinghua,OOSTEROM P.GAP-tree Extensions Based on Skeletons[C]∥Proceedings of the Advances in Spatial Data Handling.Berlin:Springer-Verlag,2002:501-514.

[20] GOODCHILD M F.Scale in GIS:A Review[J].Geomorphology,2011,130(1-2):5-9.

[21] BREWER C A,BUTTENFIELD B P.Mastering Map Scale: Balancing Workloads Using Display and Geometry Change in Multi-scale Mapping[J].Geoinformatica,2010,14(2): 221-239.

[22] LI Wenwen,GOODCHILD M F,CHURCH R.An Efficient Measure of Compactness for Two-dimensional Shapes and Its Application in Regionalization Problems[J].International Journal of Geographical Information Science,2013, 27(6):1227-1250.

[23] DUCHENE C,BARD S,BARILLOT X,et al.Quantitative and Qualitative Description of Building Orientation[C]∥Proceedings of the Fifth Workshop on Progress in Automated Map Generalization.Paris:ICA,2003.

(责任编辑:宋启凡)

The Graph Theory Approach to Grid Pattern Recognition in Urban Building Groups

GONG Xianyong1,2,WU Fang1
1.Institute of Geospatial Information,Information Engineering University,Zhengzhou 450052,China;2.State Key Laboratory of Geo-information Engineering,Xi’an 710054,China

Map patterns in building groups embody the relationship of the material form of cities and their social-economic function,and reflect the city’s spatial structure,which have great importance in cartographic generalization and multi-scale representation.On the basis of related research home and abroad,a graph theory approach is proposed to recognize the grid pattern in building groups.Firstly the cognitive characteristics and definitions of grid pattern are analyzed.Then neighborhood relationship is captured by proximity graph with the help of Delaunay triangulation,and visual distance model is established considering the Gestalt principles.Multi-connected linear pattern is recognized with constrains such as linear arrangement and compactness.Finally the line pattern intersection graph and similar orientation graph are formed.The candidate grid patterns are extracted through graph operation such as finding maximal complete sub-graph,join,intersection and post-processing.Experiments show that this approach is effective,feasible and practicable for obvious grid pattern recognition with the agreement of human spatial cognitive characteristics.

cartographic generalization;building groups;grid pattern;pattern recognition;graph theory

GONG Xianyong(1988—),male,PhD candidate,majors in pattern recognition,automated cartographic generalization and spatio-temporal data analysis.

WU Fang

P208

A

1001-1595(2014)09-0960-09

国家自然科学基金(41171354;41101362;41171305;41471386);地理信息工程国家重点实验室开放研究基金(SKLGIE2013-M-4-6)

2013-06-05

巩现勇(1988—),男,博士生,研究方向为模式识别、自动制图综合和时空数据分析。

E-mail:gongxygis＠whu.edu.cn

武芳

E-mail:wufang_630＠126.com

GONG Xianyong,WU Fang.The Graph Theory Approach to Grid Pattern Recognition in Urban Building Groups[J].Acta Geodaetica et Cartographica Sinica,2014,43(9):960-968.(巩现勇,武芳.城市建筑群网格模式的图论识别方法[J].测绘学报,2014,43 (9):960-968.)

10.13485/j.cnki.11-2089.2014.0125

修回日期:2014-03-05