A Graph Match Approach to Typical Letter-like Pattern Recognition in Urban Building Groups
-
摘要: 建筑群空间分布结构对于制图综合和多尺度表达等具有重要意义。结合国内外对该问题的研究，从结构模式识别的角度提出了基于图匹配算法的建筑群典型字母型分布模式的识别方法。首先统计和提取感兴趣的字母型分布模式，选定基元，选取合理的属性信息参数和结构信息参数，利用属性关系图形式语言描述模式，构建模板库。然后对建筑群抽象和降维，将其转化为基于属性关系图表达的场模型。最后通过Ullman图匹配算法求解非精确子图同构问题，从而识别建筑群中的典型字母型分布模式子集。实验表明该方法能够有效识别典型字母型建筑群分布，并为地图综合提供了新思路。Abstract: Map patterns in building groups have great importance in Cartographic Generalization and Multi-Scale Representation. On the basis of related research, a graph match approach is proposed to recognize the typical letter-like patterns in building groups. Typical letter-like pattern templates are extracted and analyzed, and selected as elementary units and described by a Attributed Relational Graph using attribute and structure parameters. A template library was established. Buildings to be abstracted and reduced are translated into Field Model based on the Attributed Relational Graph. Typical letter-like patterns are recognized by solving the imprecise sub-graph isomorphism problem with the Ullman algorithm. Experiments show that this approach is effective, feasible, and practical for typical letter-like pattern recognition and the results agree with human spatial cognition, providing a new concept in cartographic generalization.
-
空间群组结构特征的细节描述一直是制约地图综合的主要因素之一，空间结构保持也是地图综合和多尺度表达的基本要求[1-3]。空间结构是选择综合算法的依据之一，相同空间结构之间的综合知识具有借鉴性和相似性。有认知能力的人倾向于按意义去组织知识[1-2]，典型字母型分布模式是建筑群在空间分布形态上表现出来的可以用字母明确命名且能够识别的排列，如F型、E型排列等，非常容易引起人类的视觉感知分组[3]。如果地图在视觉上的分组与其在心智上的分组相对应，就能大大加强地图传输效果。因此有必要研究建筑群字母型分布模式。
现有的地图结构探测研究多集中于直线型和网格型模式，依据距离、相似性或者要素自身结构等特征[2-15]，没有顾及字母型排列这类特殊构型的建筑物之间的相互结构关系，无法很好地识别字母型空间分布结构。视觉完备准则Gestalt原则局限于整齐、规范的建筑群分布[7-15]，故不适用于字母型分布模式的识别。
地图学从人类空间认知的角度出发，企图让计算机能够模拟人脑的空间认知能力，智能、自动且带有学习能力地进行地图综合，然而，这种思路在短期内是很困难的。受结构模式识别和基于统计语言模型的自然语言处理的启发，笔者认为一种可行的折中方法是：根据人对地图空间结构的认识，从地图中标识出可能的、感兴趣的空间结构，然后让计算机通过某些约束对待检样本进行感兴趣模式的识别，逆向去满足人的空间认知。
从结构模式识别角度来讲，建筑群典型字母型分布模式的识别就是要从复杂、不规则的建筑群特征集中，通过分析、推理等，识别出感兴趣的、已知的确定性的特征结构(即字母型排列)。本文针对建筑群中人们感兴趣的典型字母型分布模式，提出一种基于图匹配算法的自动识别方法。按照结构模式识别系统的构成部分，本文借助属性关系图[16]，主要探讨：模式基元的选择与描述、感兴趣模式的结构关系描述、带有容差的非精确图匹配算法。
1 典型字母型结构及其形式化描述
模式基元的描述包括模式分割和基元及其关系的识别两部分。根据研究问题和目标，首先对模式样本进行统计，抽取模式识别中的特征，并定义基元及其之间的关系。基元是结构模式识别的基础和关键。它对应于文法中的终止符，是构成句子的最基本的单位, 应具备“意义明确、结构简单、易于抽取、便于描述和形式化表达”等特点。基元的确定需要根据识别对象的具体情况、模式的性质以及实现识别系统所具备的技术等因素而定。
本文将建筑物抽象为点，以此作为模式识别系统的基元。建筑物的自身形状、大小、方向等特征参数均以属性值的形式附加到抽象点上。
基元通过一定的结构关系描述方法(如树状或图状的结构化描述)紧凑而方便地对结构模式信息进行描述。在本文研究问题中，基元之间的结构关系表现为建筑物之间呈现的字母型空间分布。由此，典型的字母型分布模式就转化为由基元组成的具有特定结构关系的模式。这种转化使得建筑群中典型字母型分布模式的识别问题转化为结构模式识别问题。
1.1 建筑群典型字母型空间分布模式
城市建筑注重空间系统布局，多数建筑呈群组式分布，具有模数化、序列化等特点，体现了人类之规范、整齐的审美观，以满足人们的生理、心理、行为、审美、文化等需求。典型的字母型分布是建筑群的常见布局，如L型、H型、E型等。本文通过人工标识感兴趣的字母型分布模式，从而构建模板库，作为待识别的感兴趣模式特征。通过调查、分析和总结不同地区的大比例尺地形图，统计和提取建筑群中常见的典型字母型分布模式有如图 1中的8种。
由于综合算法要求的环境上下文是指要素之间的相对分布结构，因此，本文的样本模板理论上具有旋转不变性，即模板整体旋转之后，仍认为与未旋转的模板所属同一类模式。例如，U型模式，其实质可看作是C型逆时针旋转90°的结果；W型模式，其实质可看作是M型逆时针旋转180°的结果。
1.2 模式复杂度得分
进一步研究以上8种模式发现，构成模式的建筑物可能存在重叠或者相互借用的情况，即部分模式之间具有层次包含关系(如表 1)。
表 1 典型字母型模式的层次包含关系Table 1. Typical Letter-like PatternF型 C型 T型 L型 I型 M型 2 4 3 E型 2 1 1 2 2 H型 2 F型 1 1 1 C型 2 1 1) 1个M型包含2个C型、4个L型和3个I型模式。如图 1(h)中的M型模式{ v1, v2, v3, v4, v5 }包含了{ v1, v3, v4 }和{ v2, v4, v5 }等2个C型模式，{ v1, v3 }、{ v1, v4 }、{ v2, v4 }、{ v2, v5 }这4个L型模式，以及{ v1, v2 }、{ v3, v4 }和{ v4, v5 }等3个I型模式；
2) 1个E型包含2个F型、1个C型、1个T型、2个L型和2个I型模式。如图 1(g)中的E型模式{ v1, v2, v3, v4 }包含了{ v1, v2, v3 }和{ v1, v3, v4 }等2个F型模式，{ v1, v2, v4 }这1个C型模式，{ v1, v3 }这1个T型模式，{ v1, v2 }和{ v1, v4 }等2个L型模式，以及{v2, v3 }和{v3, v4 }等2个I型模式；
3) 1个H型包含2个T型。如图 1(b)中的H型模式{ v1, v2, v3包含了{ v1, v2 }和{v2, v3 }这2个T型模式；
4) 1个F型包含1个L型、1个T型和1个I型。如图 1(f)中的F型模式{ v1, v2, v3 }包含了{ v1, v2 }1个L型模式，{ v1, v3 }1个T型模式，以及{v2, v3 }1个I型模式；
5) 1个C型包含2个L型和一个I型。如图 1(e)中的C型模式{ v1, v2, v3 }包含了{ v1, v2 }和{ v1, v3 }2个L型模式，以及{v2, v3 }1个I型模式。
诸如上述的层次包含关系可能会因为模式的识别顺序原因而导致字母型模式的自动识别结果出现二义性。例如首先识别F型、再识别E型，则图 1(d)中的{ v1, v2, v3 }和{ v1, v3, v4}均可被识别为F型模式，而{ v1, v2, v3, v4 }又被识别为E型模式，显然后者更适合人类空间认知的整体感意识，亦更符合地图综合的要求。由此可见字母型模式识别的先后顺序对其结果至关重要。为此，定义一种字母型模式的复杂度得分，用于确定其被识别的先后顺序。
定义1 模式复杂度得分(pattern complexity score，PCScore)是指模式中建筑物之间所有接合点的连接度总和。计算方法如下。
1) 如果接合点包含建筑物的端点，则该建筑物对模式复杂度得分的贡献值为1。如图 2(a)中圆形框标识的接合点的复杂度得分为3。
2) 如果接合点包含建筑物的“形腰”(即非端点)，则该建筑物对模式复杂度得分的贡献值为1.5。图 2 (b)中圆形框标识的接合点的复杂度得分为2.5，其中v4的贡献值为1.5。
3) I型模式没有接合点，其复杂度得分为0。
分别计算上述8种典型字母型模式的复杂度得分如表 2所示。可以看出，复杂度得分高的模式更满足整体感的要求。在字母型模式识别过程中，各种字母型模式按照复杂度得分从大到小的顺序依次尝试探测、识别。对已识别为模式复杂度得分较高的建筑物进行标记，在复杂度得分低的模式识别过程中将不再对其进行识别判断。
表 2 典型字母型模式的复杂度得分Table 2. PCScore of Typical Letter-like Pattern模式类型 M E H F C T L I PCScore 7 6.5 5 4.5 4 2.5 2 0 识别顺序 先→后 1.3 典型字母型分布模式基元的形式化语言基元描述
模式识别的核心问题之一是描述和表达基元特征及其之间的关系。
1) 模式基元描述，是指用于描述模式基元的属性特征。本文的目的是识别隐含于建筑群中的典型字母型分布模式的子建筑群，其依据主要是建筑物之间的大小、方向、距离等因素及其之间的相互组合。因此可用表 3中的属性信息参数描述基元。
表 3 典型字母型模式结构化参数Table 3. Structural Parameters for Typical Letter-like Pattern参数类型 参数 参数含义及计算方法 信息属性 主方向θ 本文采用建筑物多边形的最小面积外接矩形的长轴方向表示。 面积S 描述建筑物的大小。 矩形度M 多边形面积与其最小面积外接矩形面积的比值。 面积比R 描述两个建筑物的大小差异。两个建筑物中较小的面积值除以较大的面积值。 结构信息 投影位置P 参考目标A位于源目标B上的相对位置。A在B上的投影点到B起点的距离除以B的长度。记Bottom=[0, 0.33]，Mid=(0.33, .067]，Top=(0.67, 1]。投影位置与模板相同时P=1，否则P=0。 方向差D 最小面积外接矩形的主方向之差，用于描述两个建筑物之间的方向差异。 正对投影长度比F 描述两个建筑物正对的面积的大小。以两者之一为参考，分别在其主方向及其法方向做两建筑物的投影，求投影的最大重叠长度与在该方向上的总投影长度之比。 2) 文法，是指用于对基元做合成操作以构成模式的规则。确定基元之后，针对每一类型的模式，需要通过文法推断来生成贴切的文法去描述其基元之间的结构关系。文法推断就是将已知类别的多组样本集作为学习的系统参数，通过分析、归纳和演绎等生成各类模式的文法，可以由专家给出或者机器学习获得。本文中通过分析典型字母型分布模式中建筑物之间的关系，用表 3中的结构信息参数描述基元之间的结构关系。由人工给出其文法规则，如D(e1)=90°、F(e3)=1、P(e1)=Mid等。此处记变量Bottom、Mid、Top分别表示投影位置位于上部、中间、底部，具体如表 3。
形式语言是从人类的自然语言、计算机使用的各种语言和数学中的公式语言等抽象概括出来的一种抽象语言。根据需求的不同，模式文法的形式语言有串文法、树文法、图文法、丛状文法、网文法、属性信息增强的语义文法等多种类型。属性关系图是一种有力的模式描述方法，它将统计和结构两种方法结合起来，不仅用图的结构直观描述了模式的结构关系，而且引入属性描述模式的特征，具有较强的描述能力，是应用数学、计算机视觉、模式识别、数据挖掘等领域中常用的描述和分析工具。本文采用属性关系图描述模式基元之间的结构特征，其定义如下。
定义2 属性关系图(attributed relational graph, ARG)可以形式化表达为如下的一个六元组：
$$ \mathit{\boldsymbol{G}} = \left\langle {\mathit{\boldsymbol{V}}, \mathit{\boldsymbol{E}}, {\mathit{\boldsymbol{R}}_\mathit{\boldsymbol{V}}}, {\mathit{\boldsymbol{R}}_\mathit{\boldsymbol{E}}}, {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{V}}}, {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{E}}}} \right\rangle $$ 式中，V ={ v1, v2, …, v|V|}为节点的非空有穷集；| V |表示集合V中元素的个数；E ={e1, e2, …, e|E|}为边的非空有穷集；| E |表示集合E中元素的个数，例如e=＜vi, vj＞，i≠j，表示e为节点vi与节点vj连接所组成的边；RV是节点集V的属性集；RE是边集E的属性集；FV表示V → RV即产生节点集V的属性集RV的映射函数的集合，即描述每个节点的存在条件；FE表示E → RE即产生边集E的属性集RE的映射函数的集合，即描述每个边的存在条件。＜RV, RE, FV, FE＞共同组成图＜V, E＞的形式关联约束，它使得E中的每条边对应于V中的一组节点对。
利用属性关系图描述建筑群分布模式，V和RV共同描述了建筑物的属性特征，E和RE共同描述了建筑物之间的结构关系的存在性，＜V, E, RV, RE＞构成了模式的描述语言，对应于句法模式识别中的字母表和符号串。FV描述了节点集V的存在性的约束条件，表达了属性信息的强度；而FE描述了边集E的存在性的约束条件，表征了结构关系的判断和强弱；＜FV, FE＞共同构成了模式的语法规则，对应于句法模式识别中的文法。
根据属性关系图的定义及典型的字母型建筑群分布模式特点，本文以属性关系图来表示建筑群的分布模式。图 3(b)中的节点代表建筑物，附加有属性信息，边代表相连的两个建筑物具备一阶相邻关系，并附加有结构“强度”信息。以如图 3(a)所示的E型分布为例，黑实心圆点是建筑物的抽象，黑实心点之间的连接用于可视化建筑物之间的相邻情况，表示建筑物之间为一阶相邻。例如在该图中，v1与v2分别代表建筑物A和建筑物B，v1与v2相连接表示建筑物A和B之间的为一阶相邻。E型建筑群分布模式的特点主要表现为:
(1) 建筑物v1与建筑物v2、v3、v4的方向分别近似呈90°；
(2) 建筑物v2、v3、v4在建筑物v1上的投影点位置分别位于v1的上部、中间和底部；
(3) 建筑物v2、v3、v4的正对投影长度比近似为1。
因此，用图论表示E型建筑群分布的关系图如图 3(b)所示，其属性关系图G =＜V, E, RV, RE, FV, FE＞表示为：
$$ \begin{array}{l} \mathit{\boldsymbol{V}} = \left\{ {{v_1}, {v_2}, {v_3}, {v_4}} \right\}\\ \mathit{\boldsymbol{E}} = \left\{ {{e_1}\left( {{v_1}, {v_2}} \right), } \right.{e_2}\left( {{v_2}, {v_3}} \right), {e_3}\left( {{v_3}, {v_4}} \right), \\ \;\;\;\;\;\;\;\left. {{e_4}\left( {{v_1}, {v_3}} \right), {e_5}\left( {{v_1}, {v_4}} \right)} \right\}\\ {\mathit{\boldsymbol{R}}_\mathit{\boldsymbol{V}}} = \left\{ {\theta, S, M} \right\}\\ {\mathit{\boldsymbol{R}}_\mathit{\boldsymbol{E}}} = \left\{ {R, D, F, P} \right\}\\ {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{V}}} = \mathit{\Phi } \end{array} $$ $$ \begin{array}{l} {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{E}}} = \left\{ R \right.\left( {{e_2}} \right) = 1, R\left( {{e_3}} \right) = 1;D\left( {{e_1}} \right) = {90^ \circ }, \\ \;\;\;\;D\left( {{e_2}} \right) = {0^ \circ }, D\left( {{e_3}} \right) = {0^ \circ }, D\left( {{e_4}} \right) = {90^ \circ }, \\ \;\;\;\;D\left( {{e_5}} \right) = {90^ \circ }, F\left( {{e_2}} \right) = 1, F\left( {{e_3}} \right) = 1;\\ \;\;\;\;P\left( {{e_1}} \right) = {\rm{Top}}, P\left( {{e_4}} \right) = {\rm{Mid}}, \\ \;\;\;\;\left. {P\left( {{e_5}} \right) = {\rm{Bottom}}} \right\} \end{array} $$ 2 基于图匹配的字母型分布模式识别方法
2.1 图同构
在各类模式的文法产生之后，就可启动模式识别系统进行感兴趣模式的识别。对于任一给定的待识别模式x，逐一用各类模式的文法G1，G2，…，Gm来进行识别，如果某一文法Gi可以生成x，则它就属于wi类，即x∈L(Gi)。根据文法进行结构模式识别常见的方法有句法分析和句法结构的自动机识别两种。本文采用句法分析方法。
句法分析是指判断输入模式是否与文法推理所得的文法相一致，其本质是一个识别的过程。分别将待识别的建筑群样本群体和感兴趣的字母型分布模式转化为属性关系图G和G'表示，按照感兴趣的字母型模式的图文法规则，从G中识别不同类型的G'，可以通过图匹配的方法求解。由此，问题就转化为“属性关系图的匹配”这一数学问题。即在两个图的节点集和边集之间寻找某种对应关系，这种对应关系满足模板的约束条件，且能够使建筑群图中的子结构映射到模板图上。这种对应关系是一种双射函数，称为图的同构函数。
定义3 图同构。对于图G =＜V, E, RV, RE, FV, FE＞和G' =＜V', E', R'V', R'E', F'V', F'E'＞，双射函数ξ: V → V'称为图G和G'的同构函数，若它满足以下条件：
(1) 对于∀v∈V，存在v'=ξ(v)，使得FV' (v')= FV(v)；
(2) 对于∀v'∈V'，存在v=ξ－1(v')，使得FV(v)= FV'(v')；
(3) 对于任意e=＜v1, v2＞∈E，存在e'=＜ξ(v1), ξ(v2)＞∈E'，使得FE'(e')= FE(e)；
(4) 对于任意e'=＜v'1, v'2＞∈ E'，存在e=＜ξ－1(v'1), ξ－1(v'2)＞∈ E，使得FE (e)= FE' (e')。
同构函数ξ: V → V'是具有保边特性的双射函数。直观来说，若G和G'同构，那么如果G中的节点＜v1, v2＞是相接的，则其在G'中的对应节点＜v'1, v'2＞也是相接的；反之亦然。图同构的本质是指两个图具有相同的结构关系和性质，只不过是它们的节点和边的名称不同而已。从数学上来看，图同构的约束很强。在建筑群典型字母型分布模式识别中，字母型分布可以看作是隐含于建筑群中的特定结构的子集，因此需要将约束条件放宽，允许一个图通过双射函数映射到另一个图的一部分，即子图同构。
定义4 子图同构。对于图G和G'，记G"为G的导出子图(本文中指边导出子图)，若存在一个双射函数ξ: V" → V'，使得G"与G'同构，则称G和G'是子图同构。
定义5 边导出子图。设图E"是E的一个非空子集，以E"为边集，以E"中的边关联的全部节点V"为节点集所组成的图G"称为G的边导出子图。
子图同构能够用于识别较大的图中的某些局部的模式或结构。子图同构的求解过程是一个图匹配的过程。最简单直观的图匹配方法是, 先在两个图中找到一组节点的对应(vi, wj)(其中vi∈ V, wj∈ V')，然后从这个节点vi开始，依次寻找与vi关联的节点和相接的边的对应；如果发现中间的搜索过程不满足子图同构的条件，则返回重新搜索。直到搜索过程结束，如果两个图子图同构，则节点之间的一一对应关系即为所求的双射函数ξ。
建筑群中的典型字母型分布模式的属性和结构参数值不可能完全与模板一致，各个建筑物的属性特征以及建筑物之间的结构关系特征或多或少会与模板有出入。这就要求匹配算法能够允许误差的存在，此时称为非精确图匹配。
2.2 基于Ullman算法的非精确图匹配
利用Ullman算法求解非精确图匹配包括匹配概率矩阵初始化、基于Ullman算法抽取模式等两部分。由于模式模板不具备空间定位功能，建筑群的实际分布模式相对于模板来说可能发生位移、旋转、缩放等，因此图的节点不具有可比性，本文的图匹配算法是基于边的匹配，边之间通过节点相连接形成图的连接关系。
1) 概率矩阵初始化
属性关系图只是对模式知识和空间结构的一种抽象的表达，并不具有空间定位功能，模板的所有连接边和样本的所有连接边均可能存在匹配情况。根据表 3典型字母型分布模式的结构参数，待识别样本的连接边O与模板的连接边T的面积比相似度可表达为：
$$ {S_R} = \min \left( {{R_O}, {R_T}} \right)/\max \left( {{R_O}, {R_T}} \right) $$ (1) 方向差的相似度可表达为：
$$ {S_D} = \left\{ \begin{array}{l} 1 - D/90, {D_T} = 0\\ D/90, {D_T} = 90 \end{array} \right. $$ (2) 正对投影长度比的相似度可表达为：
$$ {S_F} = \min \left( {{F_O}, {F_T}} \right)/\max \left( {{F_O}, {F_T}} \right) $$ (3) 式(1)、式(2)和式(3)可以通过线性加权的方式集成表达为：
$$ {c_{O - T}} = \alpha \times {S_R} + \beta \times {S_D} + \lambda \times {S_F} $$ (4) 式中，α+β+γ=1，为调和系数。对于某个模式而言，如果某一参数项在模板的属性关系图中没有要求约束，则其相似度的值设置为1，在相似度集成时通过调和系数来调节。因此，设匹配矩阵pij为m×n矩阵，其中n=|E|, m=|E'|，则匹配矩阵的初始值为：
$$ {p_{ij}} = \left\{ \begin{array}{l} 0, \;\;\;\;\;\;\;\;\;\;{P_O} \ne {P_T}\\ {c_{O - T}}, \;\;\;\;\;\;{P_O} = {P_T} \end{array} \right. $$ (5) 2) Ullman算法
经典的子图匹配方法Ullman算法为了减少无用搜索，提出了一种提炼搜索过程的策略：采用后向和前向探测的方法减少匹配对之间可能的映射次数。该提炼策略的基本思想为：每次搜索，“提炼过程”只是测试“可能匹配矩阵”中的匹配对是否满足同构条件；若不满足，就去掉这些匹配对。由此，Ullman算法的过程可总结为：从某一候选匹配对的映射开始，进行前向或后向探测，考察余下的所有匹配对是否至少存在一个映射情况满足子图同构条件；若不存在，则返回上一级继续判断另外一匹配对；反之则判断下一匹配对，直到找出所有的结果，算法和中间过程见文献[17]。若模板图G'与待识别的输入图G子图同构，则表明建筑群G中存在G'所表达的类型的模式，输出值ξ就是满足两者子图同构的连接边之间的双射函数。
3 字母型分布模式识别实验与分析
实验数据为中国郑州市部分建筑物，实验区域北至陇海路，东至交通路，南至汝河路，西至淮南街，比例尺为1: 1 000。区域内建筑物空间分布相对简洁、整齐，包含7个街区，共计建筑物374个。参数设置：面积比R的阈值为0.65，正对投影长度比F的阈值为0.6，方向差D为10°；匹配成功概率阈值δp=0.65。研究发现，8种模式中的相邻建筑物的方向具有规则性，其相互关系只有平行和垂直两种。因此，首先根据方向阈值对待识别的属性关系图进行修剪，删除那些既不平行也不垂直的连接边，以提高图匹配算法的效率；然后用本文方法进行模式识别，识别出的典型字母型分布模式和统计结果分别如图 4和表 4所示。
表 4 模式识别结果统计Table 4. Statistics of Typical Letter-like Pattern Result模式类型 M E H F C T L I 不考虑PCScore 1 8 1 18 20 13 56 129 考虑PCScore 1 8 1 2 10 1 14 98 从图 4可以看出，本文算法基本能够识别出模板库中的典型字母型模式。结合表 4发现，在不考虑模式复杂度得分的情况下，模式之间具有重叠，即§1.2节中的模式之间的包含关系，且重叠量与表 1的包含度相一致。
4 结语
结合结构模式识别和基于统计语言模型的自然语言处理的思想，本文方法为地图综合提供了新思路。以建筑物为基元，用属性关系图描述建筑物之间的结构关系，因而能准确刻画字母型分布模式的结构特征。利用Ullman算法实现了非精确图的匹配问题，实现建筑群典型字母型分布模式的自动识别。实验结果表明了该方法的有效性与合理性。从理论上讲，对于已知的确定性的感兴趣模式，如果基元数目确定、结构关系稳定，且能够准确描述其结构关系并给出其模板，本文方法均能有效识别。对于非典型模式，需要进一步研究其结构关系，并重新定义结构模板。
-
表 1 典型字母型模式的层次包含关系
Table 1 Typical Letter-like Pattern
F型 C型 T型 L型 I型 M型 2 4 3 E型 2 1 1 2 2 H型 2 F型 1 1 1 C型 2 1 
下载: 导出CSV
表 2 典型字母型模式的复杂度得分
Table 2 PCScore of Typical Letter-like Pattern
模式类型 M E H F C T L I PCScore 7 6.5 5 4.5 4 2.5 2 0 识别顺序 先→后
下载: 导出CSV
表 3 典型字母型模式结构化参数
Table 3 Structural Parameters for Typical Letter-like Pattern
参数类型 参数 参数含义及计算方法 信息属性 主方向θ 本文采用建筑物多边形的最小面积外接矩形的长轴方向表示。 面积S 描述建筑物的大小。 矩形度M 多边形面积与其最小面积外接矩形面积的比值。 面积比R 描述两个建筑物的大小差异。两个建筑物中较小的面积值除以较大的面积值。 结构信息 投影位置P 参考目标A位于源目标B上的相对位置。A在B上的投影点到B起点的距离除以B的长度。记Bottom=[0, 0.33]，Mid=(0.33, .067]，Top=(0.67, 1]。投影位置与模板相同时P=1，否则P=0。 方向差D 最小面积外接矩形的主方向之差，用于描述两个建筑物之间的方向差异。 正对投影长度比F 描述两个建筑物正对的面积的大小。以两者之一为参考，分别在其主方向及其法方向做两建筑物的投影，求投影的最大重叠长度与在该方向上的总投影长度之比。
下载: 导出CSV
表 4 模式识别结果统计
Table 4 Statistics of Typical Letter-like Pattern Result
模式类型 M E H F C T L I 不考虑PCScore 1 8 1 18 20 13 56 129 考虑PCScore 1 8 1 2 10 1 14 98
下载: 导出CSV
-
[1] 武芳, 钱海忠, 邓红艳, 等.面向地图自动综合的空间信息智能处理[M].北京:科学出版社, 2008:292-305 Wu Fang, Qian Haizhong, Deng Hongyan, et al. Intelligent Spatial Information Processing for Automated Map Generalization[M]. Beijing:Science Press, 2008:292-305
[2] Steiniger S. Enabling Pattern-Ware Automated Map Generalization[D]. Zurich: Zurich University, 2007
[3] Qi Huabin. Detection and Generalization of Changes in Settlements for Automated Digital Map Updating[D]. Hong Kong: Hong Kong Polytechnic University, 2009
[4] 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 doi: 10.1179/174327708X347773
[5] Sester M. Optimization Approaches for Generalization and Data Abstraction[J]. International Journal of Geographical Information Science, 2005, 19(8):871-897 doi: 10.1080/13658810500161179
[6] Regnauld N. Contextual Building Typification in Automated Map Generalization[J]. Algorithmica, 2001, 30(2):312-333 doi: 10.1007/s00453-001-0008-8
[7] Zhang X, Ai T H, Stoter J. et al. Building Pattern Recognition in Topographic Data:Examples on Collinear and Curvilinear Alignments[J]. GeoInformatica, 2013, 17(1):1-33 doi: 10.1007/s10707-011-0146-3
[8] Rainsford D, Mackness W. Template Matching in Support of Generalization of Rural Buildings[M]//Advances in Spatial Data Handling, Berlin Heidelberg, New York: Springer, 2002
[9] Li Z L, Yan H W, Ai T H, et al. Automated Building Generalization Based on Urban Morphology and Gestalt Theory[J]. International Journal of Geographical Information Science, 2004, 18(5):514-534 doi: 10.1080/13658810410001702021?needAccess=true
[10] 艾廷华, 郭仁忠.基于格式塔识别原则挖掘空间分布模式[J].测绘学报, 2007, 36(3):302-308 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200703012.htm Ai Tinghua, Guo Renzhong. Polygon Cluster Pattern Mining Based on Gestalt Principles[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3):302-308. http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200703012.htm
[11] 赵彬彬, 邓敏, 李光强, 等.基于城市形态学原理的面状地物层次索引方法[J].测绘学报, 2010, 39(4):435-440 http://www.cqvip.com/QK/90069X/201004/34961553.html 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 http://www.cqvip.com/QK/90069X/201004/34961553.html
[12] Yan H W, Weibel R, Yang B S. A Multi-parameter Approach to Automated Building Grouping and Generalization[J]. Geoinformatica, 2008, 12(1):73-89 doi: 10.1007/s10707-007-0020-5
[13] 闫浩文, 应申, 李霖, 多因子影响的地图居民地自动聚群与综合研究[J], 武汉大学学报·信息科学版, 2008, 33(1):51-54 http://ch.whu.edu.cn/CN/abstract/abstract1492.shtml 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 http://ch.whu.edu.cn/CN/abstract/abstract1492.shtml
[14] 巩现勇, 武芳.城市建筑群网格模式的图论识别方法[J].测绘学报, 2014, 43(9):960-968 http://mall.cnki.net/magazine/Article/CHXB201409014.htm Gong Xianyong, Wu Fang. The Graph Theory Approach to Grid Pattern Recognition in Urban Building Groups[J]. Acta Geodactica et Cartographica Sinica, 2014, 43(9):960-968 http://mall.cnki.net/magazine/Article/CHXB201409014.htm
[15] 巩现勇, 武芳, 钱海忠, 等.建筑群多连通直线模式的参数识别方法[J].武汉大学学报·信息科学版, 2014, 39(3):335-339 http://ch.whu.edu.cn/CN/abstract/abstract2910.shtml Gong Xianyong, Wu Fang, Qian Haizhong, et al. The Parameter Discrimination Approach to Multi-connected Linear Pattern Recognition in Building Groups[J]. Geomatics and Information Science of Wuhan University, 2014, 39(3):335-339 http://ch.whu.edu.cn/CN/abstract/abstract2910.shtml
[16] 徐柱, 蒙艳姿, 李志林, 等.基于有向属性关系图的典型道路交叉口结构识别方法[J].测绘学报, 2011, 40(1):125-131 http://www.oalib.com/paper/4159276 Xu Zhu, Meng Yanzi, Li Zhilin, et al. Recognition of Structures of Typical Road Junctions Based on Directed Attributed Relational Graph[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(1):125-131 http://www.oalib.com/paper/4159276
[17] 巩现勇. 城市建筑群典型空间分布模式的识别方法研究[D]. 郑州: 信息工程大学, 2014 Gong Xianyong. Research on Typical Map Pattern Recognition in Urban Building Groups[D]. Zhengzhou: Information Engineering University, 2014
-
期刊类型引用(7)
1. 张志义，禄小敏，闫浩文，高晓蓉. 引入方向熵的建筑物群组模式识别方法. 地球信息科学学报. 2024(09): 2077-2092 . 
百度学术
2. 魏智威，丁愫，童莹，程璐，刘洋. 格式塔原则与图形凸分解结合的建筑物群直线模式识别方法. 测绘学报. 2023(01): 117-128 . 百度学术
3. 令振飞，刘涛，杜萍，张耀蓉，杨国林，锁旭宏. 样本数量不平衡下的建筑群模式识别方法研究. 地球信息科学学报. 2022(01): 63-73 . 百度学术
4. 何超树. 散列式居民地要素形态模型与指标设计. 北京测绘. 2022(09): 1215-1219 . 百度学术
5. 行瑞星，武芳，巩现勇，杜佳威，刘呈熠，殷吉崇. 一种建筑群同质二元组直线模式的识别方法. 测绘科学技术学报. 2021(01): 91-96 . 百度学术
6. 行瑞星，武芳，巩现勇，杜佳威，刘呈熠. 建筑群组合直线模式识别的模板匹配方法. 测绘学报. 2021(06): 800-811 . 百度学术
7. 巩现勇，方圆. 居民地聚类分析算法适应性对比研究. 测绘工程. 2020(05): 1-7 . 百度学术
其他类型引用(3)
计量
- 文章访问数: 1463
- HTML全文浏览量: 139
- PDF下载量: 343
- 被引次数: 10
