在地理信息科学（geographical information science, GIS）领域，骨架线和形状中心点是面状目标的两种抽象表达^[1-2]，骨架线和形状中心点在地图制图综合^[3-4]、地图注记配置^[5-6]、多尺度地图匹配^[7]，以及空间方位关系计算^[8]等多个方面有着重要应用。在GIS中，中心点一般使用面状目标的形心来代替^[9]，在面要素注记领域，通常采用区域内部最大空间的中心位置来代表形状中心^[10-11]。传统的形状中心提取方法对于复杂形状的凹多边形容易出现中心点不在视觉中心甚至不在多边形内部的问题。为了解决这个问题，有研究提出使用面状目标的主骨架线进行中心点的判断和计算^[12]。此方法在一定程度上解决了凹多边形形状中心计算问题，但是该方法阈值参数的选择过于主观，对于不同数据参数的选择不一样，而且对形状中心也缺乏形式化定义。

面状目标的骨架线是对面状目标的一种降维描述方法，可以将其看作是一个图结构，其分支结构特征反映了面状目标各视觉部分之间的拓扑关系，各个视觉部分的延伸特征，如长度、宽度、面积等几何测度则反映了面状目标视觉部分的几何特征^[13-14]。基于这个理论基础，本文将面状目标的骨架线作为平面直线图结构，利用图论节点中心性测度理论来进行形状中心点的定义和计算^[15-16]。通过中国448个地、市区域面状目标进行中心点认识实验，分析本文方法的适用性。本文单纯考虑面状目标的几何形态及其视觉中心位置，不同于有关研究提出的带有社会经济属性的中心点定义^[17-18]。

1 骨架图及相关定义

骨架或者中轴的概念首先在生物学中作为生物体形状的描述方法被提出^[19]，在计算几何领域被广泛地研究，目前存在多种骨架的定义与计算方法^[20]。在地图学和GIS领域，通常采用的是基于多边形边界点的约束三角剖分的骨架定义^[21]。本节将对简单多边形的骨架图相关概念进行形式定义和分析。

1.1   简单多边形三角剖分

一般地，多边形P是平面上的分段线性闭合曲线，由一组点的循环序列(p₀，p₁…p_n-1)定义，这些点称为P的顶点，顺次连接顶点的直线段叫做P的边p_ip_{(i+1) modn}。一个多边形是简单的，当且仅当它的顶点互不相同，且边只在公共端点相交。本文的研究对象是不自相交且不含洞的简单多边形构成的面状目标。

任意简单多边形都存在三角剖分^[22]，记作T_P。这种剖分并不唯一，在多种剖分中，文献[20]分析了三角剖分的类型对骨架形态的影响。在地理信息领域的工程应用和科学研究方面使用比较广泛的是基于约束Delaunay三角剖分的骨架线^[21]。简单多边形P的任意一个三角剖分中，按照构成每个三角形所含对角线边的条数可以将一个三角剖分的所有三角形分为3类^[20-22], 如图 1所示。

图  1  三角剖分示意图

Figure  1.  Triangulation Decomposition

下载: 全尺寸图片 幻灯片

1.2   三角剖分骨架图及相关定义

三角剖分骨架图是依据§1.1中所描述的3种类型的三角形构造不同的骨架顶点和边得到的，其定义如下。

定义1  P的三角剖分骨架图G_P：连接T_P中1类三角形对角线边中点与其对顶点，连接2类三角形两条对角线边的中点，连接3类三角形内心与其3条对角线边的中点，由此构造的平面直线图称为P的三角剖分骨架图。

由定义1可知，该骨架图G_P的顶点（骨架点）有3种类型，即对角线边的中点、三角形的内心和多边形P的顶点。一个骨架点，如果只有一个相邻的顶点则称为端点；如果只有两个相邻的顶点则称为连接点；如果有3个相邻的顶点则称为结合点，如图 1所示。

定义2  骨架枝、骨架路径：任意两个连通的骨架点之间的最短路径称为一条骨架枝，如果两个骨架点之间的骨架枝不经过任何结合点，称两个骨架点直接相邻；骨架图上一对端点s、t之间的骨架枝称为骨架路径，记为p_s、t，如图 2所示，红色的骨架枝为示例多边形的所有骨架路径。

图  2  一个多边形骨架图中的所有骨架路径

Figure  2.  All Skeleton Paths of a Skeleton Graph

下载: 全尺寸图片 幻灯片

定义3  拓扑骨架图:将骨架图的端点和结合点作为图的顶点，直接相邻的顶点之间的骨架枝作为边，得到拓扑骨架图，如图 1所示。

骨架图的端点表达了面状区域的视觉特征点，端点与端点之间的骨架枝（骨架路径）表达了视觉特征点之间的连通特征。端点与结合点之间的骨架枝表达了面状区域的视觉特征部分，结合点反映了面状区域视觉特征部分之间的拓扑衔接关系。面状目标的这些特征都可以通过拓扑骨架图来表达。

定义4  长度、宽度、面积：骨架边的长度为骨架边的几何长度，覆盖面积为对应剖分三角形的面积，宽度为面积与长度的商。

如图 3所示，红色线段$\overline {{P_1}{P_2}}, {\rm{}}\overline {{P_3}{P_4}}, {\rm{}}\overline {C{P_5}}, \overline {C{P_6}}, \overline {C{P_7}} $为骨架边，蓝色线段$\overline {{W_1}{W_2}}, \overline {{W_3}{W_4}}, \overline {{W_5}{W_6}} $为宽度。2类三角形宽度可以定义为三角形单元的非对角线边上的高$\overline {{W_3}{W_4}}$。3类三角形对应的3条骨架边覆盖面积相等，为三角形总面积的1/3。容易知道，3类三角形通过内心与各个顶点的连线将三角形分成3个子区域，3个子区域的骨架边与1类三角形是等同的，其定义和计算一致，使得$\overline {{W_1}{W_2}}, \overline {{W_5}{W_6}} $的几何长度符合定义4。

图  3  骨架边覆盖长度、宽度定义示意图

Figure  3.  Cover Length, Width of Skeleton Edge

下载: 全尺寸图片 幻灯片

2 形状中心点的定义与计算

文献[12]提出了一种基于形状主骨架线的综合判断法，通过面状目标形状的凹凸性、分支均衡性等特性综合选择不同的点作为形状中心点。综合判断法考虑到了形状骨架在形状中心计算中的重要作用，但是在进行参数阈值选择时过于主观，针对不同类型的数据，参数选择不具有稳定性，也不能保证所得到的形状中心一定在区域内部。本文对文献[12]的研究思路进行拓展，通过多边形的三角剖分建立多边形的骨架结构图，在骨架图结构的基础上，从拓扑和几何测度两个角度分别对图节点的中心性进行定义，定量化评判三角剖分子区域的中心性程度，进而计算形状的中心点。一般认为，端点之间的骨架路径重叠度高的部分，即区域连贯性较强的部分，视作居间中心区域。区域内部到视觉特征点邻近的区域，即与各个视觉特征点亲近性较强的部分，视作邻近中心区域。

2.1   骨架图顶点居间中心性与邻近中心性

在图论中，居间中心性是一种基于最短路径的对图中节点的中心性测度，由通过一个顶点的所有最短路径数目来表达。居间中心性越高，说明网络结构中通过该节点的信息流越大，在图结构中具有重要的控制作用。相应地，本文考虑到视觉特征点之间的骨架路径反映了形状视觉特征部分的连贯性，是人对形状进行认知识别的重要结构，由此定义骨架图中节点的居间中心性为经过该节点骨架路径的数目。

定义5  骨架图节点V的居间中心性：经过V的骨架路径的数目。计算公式如下：

式中，C_b(V)为V的居间中心性；；p_{s, V, t}表示连接端点s、t并且经过顶点V的路径。

定理1  居间中心性最大的顶点是结合点。

证明：所有度为2的顶点，其居间中心性一定小于其最邻近3度顶点的居间中心性。如果某个2度顶点居间中心性大于其邻近顶点，那么至少存在一条通过该分支的骨架路径不经过3度顶点，这显然不成立，因此，定理得证。

由定理1可知，面状区域三角剖分骨架图顶点居间中心性最大的必定处于结合点，或者说是分支三角形处，那么在寻找最大居间中心性节点时，可以只考虑结合点，这就可以在骨架拓扑图上进行计算。由于骨架拓扑图是骨架图的进一步抽象表达，有更少的边和节点，在此基础上进行图节点的居间中心性计算，效率会更高。

图论中邻近中心性是另一种图中节点的中心性测度，通过计算节点到图中其他所有节点的最短路径长度的总和的倒数求得。如果一个节点中心性越高，那么它与其他所有节点的距离越近。借鉴此思想，考虑骨架点到各个视觉特征点邻近性感受的均衡性，本文定义骨架图节点到骨架图端点的骨架枝长度标准差的倒数作为骨架图节点的邻近中心性。

定义6  骨架图节点V的邻近中心性：V到各个端点s的骨架枝的带权长度d_w(V, s)标准差M的倒数。计算公式如下：

其中，C_c(V)为V的邻近中心性；骨架枝对应边的权w可以取长度、宽度或者面积。

邻近中心性反映了骨架图上各个顶点到骨架端点，也就是所有视觉特征点的邻近性。本文考虑长度、宽度、面积3种权重，在具体计算时，可以根据需要选择不同的权重。比如，主要考虑形状的延展长度时，可以考虑长度权重；若是考虑骨架分支的粗壮程度时，则使用宽度权重；综合考虑分支的延展性和粗壮程度时，可以使用面积权重。文献[12]所采用的分支面积方差最小是本文定义的面积权特例。

2.2   区域中心点计算与特征

通过计算骨架图中结点的中心性得到三角剖分骨架图上各个节点的中心性程度，对其进行排序，得到中心性程度最大的点即可作为区域的形状中心点。居间中心点的计算基于骨架拓扑图，只需要计算结合点的中心性进行排序即可。本质上，骨架所有的端点之间均可连通，只需要计算骨架拓扑图上端点两两之间的路径，并统计各个结合点在所有路径中出现的次数即可得到所有结合点的中心性指数。对于邻近中心点，需要基于骨架图计算所有节点（除端点外）到骨架端点的路径带权长度，因此，得到的中心点可能是结合点，也可能是骨架图上的连接点。面状要素中心点的计算步骤如图 4所示，首先通过骨架提取算法得到面状目标的骨架图表达，然后基于定义1、定义2分别计算各个骨架节点的中心性指标，选取中心性最大的节点作为面状要素的中心点。

图  4  中心点计算步骤

Figure  4.  Procedure of Center Point Extraction

下载: 全尺寸图片 幻灯片

两种中心点反映的是不同的面状区域中心特征：居间中心反映的是面状区域各个视觉部分间的拓扑连接性较强的区域，属于拓扑结构重要性强的中心点；邻近中心反映的是面状区域内部到各视觉特征点的几何邻近特征，属于几何邻近特征重要性强的中心点。由于剖分三角形均在多边形内部，通过以上方法计算出来的中心点一定在多边形内部。同时，通过中心性评价得到的中心点位于面状区域的拓扑中心，或者骨架几何测度中心位置，能保证较好的视觉中心特征。骨架图节点的居间中心性以及邻近中心性的示意图见图 5。邻近中心性分别展示了长度、宽度、面积3种不同权重情况下的中心性的度量；并设定边界点的中心性为0，通过线性插值获得区域邻近中心性的模式分布图。

图  5  两种中心性实例

Figure  5.  Two Centrality Cases

下载: 全尺寸图片 幻灯片

2.3   特殊情况讨论

由于图形的多样性，可能会出现图 6(a)中的情况，面状区域骨架为H型，25、57号顶点的居间中心性按照定义无法区分，这时可计算二者的邻近中心性进行进一步区分。由计算可知，25号节点在任何权重类型的邻近中心性都比57号点强，由图 6(a)也可以看出25号点处于3种权重类型邻近中心点一侧，说明其综合的中心性较强。前文讨论中提到，对于多边形不存在分枝三角形的情形，表明多边形线性延伸特征明显，这时候只需要考虑骨架图节点的邻近中心性，如图 6(b)所示的C型面状区域，其中长度权与宽度权邻近中心点重合。

图  6  特例情况

Figure  6.  Special Cases

下载: 全尺寸图片 幻灯片

3 认知实验与讨论

本文提出的中心点计算方法是在已有形状中心计算方法无法满足要求时的一种较好的替代方法。本节将通过一组真实数据的认知实验分析不同类型中心点在不同区域形状下的表现。

3.1   实验设计与分析

本文选择全国448个地、市级行政区划面要素作为实验数据(见图 7)，分别计算每个区域的形心、邻近中心以及居间中心（长度权），并设计了一个在线认知测试实验平台，通过10名地理学和地图制图学专业相关的研究生进行测试，对3种中心点的优劣进行评判选择。每个区域上标注3种中心点，给受试学生的问题是“哪些点可以较好地表达区域的中心位置”，对每个区域的案例可以进行多选。实验案例如图 8所示。

图  7  实验数据

Figure  7.  Experiment Data

下载: 全尺寸图片 幻灯片

图  8  实验案例示意图

Figure  8.  Experiment Cases

下载: 全尺寸图片 幻灯片

测试结果统计见表 1，其中人数比例是指至少有多少比例的人认为某种中心点可以较好地表达区域中心。如表 1中第3行，在所有的448个区域例子中，以形心表达区域形状中心有327个例子超过60%的认可度，以邻近中心表达区域形状中心有114个例子超过60%的认可度，以居间中心表达区域形状中心有13个例子超过60%的认可度。由表 1最后一行可以看出，没有哪一种中心点可以达到100%的认可度，说明区域中心的判断存在一定的主观性，对于不同形状的区域，中心点的选择很难达到一致的认可。同时也说明本文提出的方法在一些案例中具有优势。

表  1  实验测试结果

Table  1.  Experiment Results

人数比例	形心	邻近中心	居间中心
0.2	431	251	96
0.4	379	154	30
0.6	327	114	13
0.8	198	36	2
1	0	0	0

下载: 导出CSV 

| 显示表格

3.2   形状特征与中心点选择

由§3.1统计分析可知，本文提出的中心点计算方法在一些案例中具有优势，本节讨论形状特征对中心点选择的影响。本文选择凸度、矩形度和紧密度这3个区域形状描述子, 如图 9所示。它们的定义分别为：凸度为区域面积与其凸包多边形面积的比值，取值范围是[0, 1]；矩形度为区域面积与其最小外接矩形面积之比，取值范围为[0, 1]；圆形度为区域面积与最小外接圆面积的比值，取值范围是[0, 1]。三者都反映了形状的规则程度，越是接近1表示形状越规则，反之越不规则。本文实验的计算使用了笔者基于Python开发的ShapeAnalyzer工具包(https://github.com/luwei14/ShapeAnalyzer)，该工具包具有基本几何计算模型、形状包络几何计算、形状描述子计算，以及本文提出的形状中心计算等功能。

图  9  形状特征描述子示意图

Figure  9.  Diagram of Shape Descriptors

下载: 全尺寸图片 幻灯片

对每一个区域选择认可度最大的中心点作为最佳选择，在所有的448个区域例子中，有333、102、13个案例的最佳选择分别是形心、邻近中心和居间中心。这表明本文算法在115种情形下对中心性的表达优于传统的形心法，有一定的实用性价值。依据这3组结果，3种最佳选择的案例形状特征描述值箱线分布如图 10所示。由图 10可知，传统的形心计算方法比较适合于区域的凸度、矩形度、紧致度较大的区域；本文算法在3种描述子取值相对较小时表现比较优越，而且居间中心表现优越的形状描述值最小。由此表明，本文方法在面要素形状不规则时具有较好的优势。

图  10  不同中心点形状分布特征

Figure  10.  Shape Descriptor Distribution of Different Center Points

下载: 全尺寸图片 幻灯片

4 结语

本文提出了一种定义和计算简单面状目标中心点的新方法。基于多边形三角剖分骨架图结构，借鉴图论领域的中心性理论，定义骨架图顶点的中心性度量，进而获得中心性较高的骨架顶点作为面状目标的形状中心。不同于传统方法利用区域轮廓坐标均值得到形心，本文方法考虑了各个子区域之间、视觉特征点和视觉特征部分之间的拓扑关系和几何特征，得到的中心点可以保证位于多边形内部，具有较好的视觉中心特征。

由于本文方法依赖于图结构的计算，因此计算中心点的时间复杂度理论上比传统的形心计算方法高，还需进一步研究不同形状特征对中心点选取的影响，给出一个全面的中心点计算方法。同时，可以进一步研究不同应用场景中如何选定合适的中心点。例如，在空间方位关系计算时，居间中心点的适应度可能比邻近中心点强；在进行面要素注记时，宽度权邻近中心点可能更加合适沿着骨架的注记配置；在地图综合中计算面变点时，面积权和长度权邻近中心点会有优势。