多尺度点群相似度计算是制图综合领域的重要研究内容，可为自动综合提供终止条件判断及综合质量评价等作用^[1]。针对点群的相似度计算，现有研究主要集中于相似性影响因子^[1]、因子权重的设置^[2]、点群中空白区域的影响^[3]及各因子相似性度量的建模^[4-6]等方面，其中相似因子的建模是关键。Bruns等指出空间目标的几何特征中距离关系、拓扑关系和方向关系是最关键的几个因素^[7]，因此现有研究都重点关注对这3个因子的建模。在现有研究中，主要用点群的标准差椭圆的长短轴之比^[4]、相对局部密度^[5-6]及分布中心的差异等方法计算点群距离相似度^[2]，用拓扑邻居的总数和点数的比值^[4]、拓扑信息量^[8]及一阶邻居的数量等方法计算拓扑相似度^[5-6]，用数据点之间相对角度的标准差^[2]、标准差椭圆长轴的夹角^[4]等方法计算方向相似度。分析发现，这些方法大多采用数理统计的思想，通过统计待度量点群的整体变化信息来度量相似性，但是这种统计的思想对点群的形状及位置差异不够敏感，因此只能描述点群整体的相似度，不能对点群内部细小的变化进行准确度量。另外，现有方法主要用来度量不同专题属性数据^[4]、不同尺度数据^{[1, 2, 4]}这种差异较大的两类数据，而对数量相同的两类差异度较小的数据相似度的计算实验鲜有见到，而这需要依靠更加精确的点群相似性度量模型。

Hausdorff距离是度量两个集合间相似性的有力工具，其计算过程会顾及到点群的整体形状及任意一点的位置，从而得到更加严密的度量结果，已在相似性度量^[9]、图像匹配^[10]等方面进行了广泛的应用，且有学者提出扩展改进^[11]。针对现有点群相似性度量模型的不足，本文提出利用广义Hausdorff距离计算多尺度点群相似度。在传统Hausdorff距离的基础上，研究发展了多尺度点群拓扑Hausdorff距离、方向Hausdorff距离，将其统称为广义Hausdorff距离，并应用于多尺度点群相似度计算。并通过多尺度点群相似度计算实验及点群综合结果评价实验，对本文所述方法的合理性和有效性进行了验证。

1 多尺度点群广义Hausdorff距离及相似性度量模型

对点群进行相似度建模，首先需要确定点群相似性评价因子，本文遵从Bruns等的观点^[7]，从距离、拓扑、方向3个最关键的因素进行考虑，研究多尺度点群相似性度量方法。

1.1 基于Hausdorff距离的距离相似度 1.1.1 Hausdorff距离的定义

假设有两个点集合A={a₁, a₂…a_p}，B={b₁, b₂…b_q}，则这两个点集合之间的Hausdorff距离计算公式为：

$ H(A, B)=\max (h(A, B), h(B, A)) $

(1)

式中，h(A, B)、h(B, A)为单向的Hausdorff距离，表示一个点集中所有点到另一个点集最小距离的最大值，即

$ \left\{\begin{array}{l}{h(A, B)=\max (a \in A) \min (b \in B)\|a-b\|} \\ {h(B, A)=\max (b \in B) \min (a \in A)\|a-b\|}\end{array}\right. $

(2)

式中，‖·‖是点集A和B元素间的欧几里得距离。

1.1.2 多尺度点群距离相似度

对于多尺度点群，设P₀为原始点集，P₁为原始点群通过选取方法得到的综合后的点集，根据基于距离的相似性度量思想^[12-13]，多尺度点群间的距离相似度可以按下式进行计算：

$ \operatorname{Sim}_{\mathrm{dim}}=1-\frac{H\left(P_{0}, P_{1}\right)}{S_{\max }} $

(3)

式中，Sim_dist为距离相似度；S_max为原始点群中任意两点间距离最大值。

1.2 拓扑Hausdorff距离及拓扑相似度 1.2.1 点群的拓扑距离

点群内部点之间的拓扑关系可以分为相邻和不相邻两种，所以点群目标的拓扑关系可以用点的邻居来表达，点的邻居可以是Voronoi邻居、K个最近邻居或定长距离邻居等。本文将点群的拓扑距离看做点与点之间的邻近程度的大小，提出了一种利用Voronoi图计算点群拓扑距离的方法。

定义：设P是二维笛卡尔空间有限凸域上空间目标p₁, p₂…p_n的集合，p_i, p_j∈P，将p_i与p_j之间跨越的Voronoi区域的最少个数k称为空间目标p_i与p_j的拓扑距离，记为d_v(p_i, p_j)，显然有d_v(p_i, p_j)≥0，且当p_i=p_j时，d_v(p_i, p_j)=0。

点群拓扑距离的计算方法如下：依据计算几何，Voronoi图与其直线对偶图Delaunay三角网的边唯一对应^[14]，即两者边的数目相等，因此一个Delaunay三角形的边连接的两个Voronoi区域必是相邻的区域，如图 1所示。因此计算点群中两点的拓扑距离归结为计算Delaunay三角网中对应两点的最短路径，且每段路径的权值为1。Delaunay三角网是一种无向图，因此问题归结为无向图顶点之间的最短路径问题，可用Floyd算法求解^[15]，此处不再赘述。

1.2.2 多尺度点群拓扑相似度

定义：假设有点集合A={a₁, a₂…a_p}，点集B是点集A的子集，即$B \subseteq A $，则点集A、B之间的拓扑Hausdorff距离定义为：

$ H_{t}(A, B)=\max \left(h_{t}(A, B), h_{t}(B, A)\right) $

(4)

式中，h_t(A, B)、h_t(B, A)为单向拓扑Hausdorff距离；H_t(A, B)表示点集A中所有点到点集B所有点的最小拓扑距离的最大值，即：

$ \left\{\begin{array}{l}{h_{t}(A, B)=\max (a \in A) \min (b \in B) d_{v}(a, b)} \\ {h_{t}(B, A)=\max (b \in B) \min (a \in A) d_{v}(a, b)}\end{array}\right. $

(5)

式中，d_v(a, b)是元素a、b间的拓扑距离。同距离相似度计算原理，对于多尺度点群P₀与P₁，有拓扑相似度计算公式：

$ \operatorname{Sim}_{\mathrm{topo}}=1-\frac{H_{t}\left(P_{0}, P_{1}\right)}{T_{\max }} $

(6)

式中，Sim_topo为拓扑相似度；H_t(P₀, P₁)为拓扑Hausdorff距离；T_max为原始点群的最大拓扑距离。

1.3 方向Hausdorff距离及方向相似度

方向关系是在一定的参考框架下，从一个空间目标到另一个空间目标的指向，其描述涉及到3个要素：参考框架、参考目标和源目标，其中参考框架分为内部参考框架、观测参考框架和外部参考框架^[16]。为了对点群方向关系进行描述，本文借助点群最小外包圆建立点群方向关系描述的参考框架，计算点群方向距离，在此基础上实现多尺度点群方向相似度计算。

1.3.1 参考框架的建立

为使点群中点尽可能均匀地分布在参考框架中，以点群最小外包圆的圆心为原点，以水平和竖直方向分别为X轴、Y轴建立点群方向参考框架，如图 2所示。以X轴正方向为起始方向，逆时针方向为正，顺时针为负，则点群中任意一点对应唯一的方向角。点群最小外包圆可以通过随机增量算法^[17-18]、对偶决策算法^[19]及最远点优先渐进算法^[20]等计算，此处不再赘述。对于上述方向框架中的一点(x, y)，其方向角δ计算公式为：

$ \delta=\arctan \left(\frac{y-y_{c}}{x-x_{c}}\right) $

(7)

式中，(x_c, y_c)为点群最小外包圆的圆心坐标，δ∈[-π, π]。

1.3.2 方向距离

定义：设p_i、p_j是二维笛卡尔空间上两个点目标，将p_i与p_j在参考框架下两个方向的夹角称为空间目标p_i与p_j的方向距离，记为d_r(p_i, p_j)，有d_r(p_i, p_j)∈[0, π]。

1.3.3 基于方向Hausdorff距离的方向相似度

定义：设有两个点集合A={a₁, a₂…a_p}，B={b₁, b₂…b_p}，则这两个点集合之间的方向Hausdorff距离定义为：

$ H_{R}(A, B)=\max \left(h_{r}(A, B), h_{r}(B, A)\right) $

(8)

式中，h_r(A, B)、h_r(B, A)为单向的方向Hausdorff距离；h_r(A, B)表示点集A中所有点到点集B的最小方向距离的最大值，即：

$ \left\{\begin{array}{l}{h_{r}(A, B)=\max (a \in A) \min (b \in B) d_{r}(a, b)} \\ {h_{r}(B, A)=\max (b \in B) \min (a \in A) d_{r}(a, b)}\end{array}\right. $

(9)

式中，d_r(a, b)表示元素a、b在同一方向参考框架下的方向距离。同理，对于点群P₀与P₁，有点群的方向相似度计算公式：

$ \operatorname{Sim}_{\mathrm{dir}}=1-\frac{H_{R}\left(P_{0}, P_{1}\right)}{R_{\max }} $

(10)

式中，Sim_dir为方向相似度；H_R(P₀, P₁)为方向Hausdorff距离；R_max为点群的最大方向距离，通常情况可近似设为π。

1.4 多尺度点群总相似度

为了避免加权平均方法计算结果对权值依赖较大的缺点，在没有明显侧重的情况下，可以取距离、拓扑、方向相似度的几何平均值作为多尺度点群总相似度的值，即：

$ \mathrm{SIM}=\sqrt[3]{\mathrm{Sim}_{\mathrm{dist}} \times \operatorname{Sim}_{\mathrm{topo}} \times \mathrm{Sim}_{\mathrm{dir}}} $

(11)

式中，SIM为两点群的总相似度值。

2 实验与分析

实验由两部分组成，一是通过点群的不同组合，验证上述点群相似性度量模型的合理性和有效性，二是将本文所述点群相似性度量模型应用于点群综合结果的评价，整个过程在MATLAB 2014年环境中编程实现。

2.1 多尺度点群相似度计算实验

实验对点群中一定数量的点进行组合，计算不同组合结果与原始点群的相似度，由于组合数随样本数增长过快，因此实验数据不宜过大。从郑州地区某幅1:5万数据中截取56个点状居民地数据进行实验，为了便于描述，按照从1~56的顺序对点进行编号，如图 3所示。假设随着尺度的减小，只能显示4个居民点。为验证本文所述方法的合理性和有效性，依次取出4个点，对所有组合情况进行相似度计算，共计C₅₆⁴=367 290种组合。

2.1.1 多尺度点群距离相似度计算

分别计算各组合的距离相似度，受篇幅原因，本文列举距离相似度最大和最小的3种组合结果(下同)，如图 4、图 5所示。其中选取的点组合用圆圈圈出，短线表示Hausdorff距离对应的两点的连线。

从图 4、图 5可以看出，点群距离相似度最大的3种点组合，选取的4个点分布较均匀，基本能代表原始点群分布的整体趋势；点群距离相似度最小的3种点组合，点分布集中，与原始点群分布差异很大，因此距离相似度计算结果与人的直观感受一致。另外，从结果可以看出，距离相似度最大时存在两种组合，因此单纯以普通Hausdorff距离无法区分这两种组合中哪种组合与原始点群更相似，还需要依靠点群拓扑相似度及方向相似度进一步区分。

2.1.2 多尺度点群拓扑相似度计算

各组合拓扑距离、相似度及组合数量计算结果如表 1所示。

从表 1可以看出，所有组合情况的拓扑Hausdorff距离只有2、3、4、5、6共5种结果，对应的拓扑相似度也只有5种结果，因此，单纯以拓扑相似度区分不同组合的相似性，灵敏度较低。为了对上述计算的距离相似度最大的3种组合进行进一步区分，列出上述3种组合的拓扑相似度结果，如表 2所示。

从表 2可以看出，即使是距离相似度相同的点组合，在拓扑相似度上也存在差别，因此，可以利用拓扑相似度进一步区分整体相似度的大小。

2.1.3 多尺度点群方向相似度计算

如图 6、图 7所示，点群方向相似度最大的3种点组合，4个点在方向上分布较均匀，基本能代表原始点群在方向上的分布趋势。而点群方向相似度最小的3种点组合，点的分布集中，与原始点群分布差异很大。因此，方向相似度计算结果与人的直观感受一致，符合人类认知。

2.1.4 多尺度点群总相似度计算

从图 8、图 9可以看出，总体上，总相似度最大的及最小的3种组合与距离相似度、方向相似度最大及最小的3组较类似，相似度大的组合在整个区域中分布均匀，相似度小的组合分布集中。总相似度在结合了距离、拓扑、方向等因子后，能正确区分出相似度最大的一种组合，即5, 16, 41, 44组合，可以认为该组合在空间关系上与原始点群最相似。

为考察本文所述方法计算点群相似度的灵敏度，绘制各类相似度变化趋势图，如图 10所示。

从图 10中可以看出，距离相似度和方向相似度灵敏度较高，基本能够区分不同组合情况下的相似度，拓扑相似度灵敏度较低，在本文所述实验情况下，只有5种结果。分析发现，这是由于本文拓扑距离是以拓扑邻近为依据进行计算的，原始点群本身点数较少，最大拓扑距离较小(经计算，最大拓扑距离为7)，而拓扑距离又为自然数，造成拓扑相似度可能的结果较少。但是，可以看出，总相似度灵敏度较高，能够明确区分不同组合情况下的相似度。

2.2 点群综合结果评价实验

实验采用上述郑州地区1:5万点状居民地数据，共计706个点，如图 3(a)所示。在进行小比例尺地图生产过程中，由于属性信息缺乏，不能依据属性信息进行选取。因此，本文利用某地图生产系统的两种点要素选取工具进行点群选取，为了进一步比较不同选取结果相似度的差异，新增随机选取作为参照，分别选取了499个点、316个点，如图 11所示(未按比例尺绘出)。计算3种方法所得结果与原始点群数据的距离、拓扑、方向相似度及总相似度，结果如表 3所示。

从表 3中可以看出，总体上，随着选取点数减少，3种方法选取结果各类相似度均逐渐减小，在相同选取数量情况下，地图生产系统的两种选取结果在距离、拓扑、方向及总相似度上比随机选取的相似度大，说明两种选取方法在相似度保持上较好。选取点数为499时，两种方法选取结果在各方面与原始点群的相似度均比较高，总体相似度差别较小，但方法一在距离相似度上较方法二大，而在方向相似度上正好相反，说明两种选取方法在距离和方向保持上各有侧重。选取点数为316时情况类似，但距离相似度变化较大，这是由于随着选取点数的减少，点群Hausdorff距离显著增大导致的。

3 结语

本文将传统Hausdorff距离推广应用到多尺度点群数据的拓扑关系和方向关系度量层面，提出了多尺度点群的拓扑Hausdorff距离和方向Hausdorff距离，构建了一系列相似度计算模型，具有一定的理论和实用价值。需要说明的是，本文提出的拓扑相似度计算方法只适用于多尺度点群，因为拓扑距离是基于原始点群数据的Voronoi图进行度量的，而距离相似度和方向相似度计算方法可以推广应用到不同主题的点群数据，从而研究两类目标之间的相似关系。

本文研究的点群相似度计算方法只用来进行制图综合结果的评价，下一步需要将空间相似关系作为点群选取的约束条件，研究新的点群综合方法。另外，制图综合并不是完全相似的过程，点群选取既要保持密度对比，又要减少密度差别，如何在利用相似性进行制图综合过程约束及结果评价时顾及到制图综合的这种特殊要求是接下来需要考虑的内容。