相似性是进行分类、感知、归纳和推理的基础，在人类的空间认知活动中有着重要的作用^[1-2]。空间相似性是地理信息科学领域中的重要研究内容，指两个(或多个)空间目标或空间场景之间在某一方面或某几个方面的相同程度^[3]，包括空间目标几何相似性、空间关系相似性以及语义相似性。方向关系作为空间关系的重要内容，用于表达两空间目标间的方位关系，其相似性计算在模式识别^[4]、空间查询^[5]、数据匹配^[6-7]、地图综合质量评估^[8]、空间数据更新质量评估等方面有着广泛的用途。但是，由于方向关系表达的复杂性以及较差的可计算性，使得有关方向关系相似性计算的研究相对较少，这严重限制了其理论发展与应用。

Goyal基于方向关系矩阵提出了一种利用交通运输线性规划原理进行相似性计算的方法^[9]。之后，一些学者对Goyal提出的计算模型进行了改进，郭庆胜^[10]提出了基于栅格数据的方向相似性计算方法，但这个方法需要将矢量数据转换成栅格形式。安晓亚^[11]基于两方向关系矩阵转换移动的方格数最少的原则对两方向关系矩阵进行了相似性度量。但是这些研究仍然存在两个方面的问题：① 计算模型复杂，可执行性较差；② 方向相似性值所表达的两方向间的相似程度与人类对方向差异的认知习惯存在部分偏差。

基于此，本文提出了一种改进的空间方向关系相似性计算模型。

1 空间方向关系表达

空间方向关系模型是表达和计算空间目标间方位关系的重要工具^[12]，也是进行方向相似性计算的基础。目前，国内外许多学者已经提出了大量的方向关系表达模型，如质心模型、2D-String模型、矩形模型、投影模型、锥形模型、方向关系矩阵模型^[13]、方向Voronoi图模型^[14-15]等。与其他模型相比，方向关系矩阵模型和Voronoi图模型考虑了空间目标的形状信息，能够对凹形对象提供较好的方向评估，但是Voronoi图模型计算比较复杂。本文选择方向关系矩阵模型作为表达方向关系的模型。

1.1   方向关系矩阵

经典的方向关系矩阵模型由Goyal在2000年提出。如图 1所示，其基本思想是使用投影法将研究目标B所在的空间域分为东、西、南、北、东南、东北、西南、西北以及和参考目标A位于同一区域的“同一”等9个方向片，分别用E、W、S、N、SE、NE、SW、NW、O来表示。

图  1  参考目标方向片分区

Figure  1.  Partitioning of Spatial Direction Formed Around the Reference Object A

下载: 全尺寸图片 幻灯片

方向关系矩阵使用的是一个3×3的矩阵来表达两空间目标之间的方向关系的，矩阵中每个元素的值根据目标对象与各个方向片的交值来表示。方向关系矩阵分为粗糙方向关系矩阵和详细方向关系矩阵。方向关系的相似性度量是基于详细空间方向关系矩阵实施的。详细方向关系矩阵元素的值是面目标对象B在对应方位区域中的面积与目标对象面积的比值:

1.2   面向群组目标的复杂方向关系矩阵模型

Goyal的方向关系矩阵是针对单个对象设计的，并不能直接应用于由多个面目标组成的面群目标间的方向关系的计算^[16]。然而，在多尺度表达和制图综合中，小比例尺中一对一的方向关系，在相邻较大比例尺中对应的可能是多对多的方向关系。

要计算相邻比例尺数据间对应空间对象间的方向相似性，就必须对方向关系矩阵进行拓展，建立表达有面群参与的复杂方向关系矩阵模型。有面群参与的方向关系计算可分为简单面相对于面群、面群相对于简单面、面群相对于面群三种情况，下面以面群相对于面群的方向关系的计算为例，对方向关系矩阵的拓展方法进行说明，其他两种情况方向关系矩阵的求法可用相似的方法求得。

设参考面群A由简单面目标A₁、A₂、A₃组成，表示为A={A₁，A₂，A₃}，目标面群B由简单面目标B₁、B₂组成，表示为B={B₁，B₂}。首先根据面群A在两坐标轴上的投影将空间分为9个方向片，分别用E、W、S、N、SE、NE、SW、NW、O表示(图 2)；其次，根据子目标对象B_i(i=1,2)位于各方向片的面积比，求出简单面B₁、B₂相对于参考面群A的详细方向关系矩阵Dir(A，B₁)、Dir(A，B₂)；最后，计算组成目标对象各个子对象B_i相对于参考面群的方向关系矩阵的加权和，求出面群B相对于面群A 的方向关系，其中权值为各个子对象B_i的面积与面群B的面积之比。设Dir(A，B)表示面群对象B相对于面群对象A的方向关系矩阵，那么，Dir(A，B)的值为：

图  2  面群间方位关系描述

Figure  2.  Description of Direction Relations Between Areal Object Groups

下载: 全尺寸图片 幻灯片

式中，；area(B)表示空间对象B的面积。

2 改进的方向关系相似性计算模型

2.1   方向概念间距离的改进

为了计算两个方向关系间的相似性，Goyal引入了“方向距离”的概念，并按照一定的法则定义了任意两方向概念间的方向距离(表 1)，具体的定义方式可参照文献^[9]。在Goyal的定义中，两相同方向概念间的方向距离为0，NW与SE、NE与SW间的方向距离最大都为4。

表  1  方向片之间的方向距离

Table  1.  Distances Between the Basic Directional Tiles

Dist	N	NE	E	SE	S	SW	W	NW	O
N	0	1	2	3	2	3	2	1	1
NE	1	0	1	2	3	4	3	2	2
E	2	1	0	1	2	3	2	3	1
SE	3	2	1	0	1	2	3	4	2
S	2	3	2	1	0	1	2	3	1
SW	3	4	3	2	1	0	1	2	2
W	2	3	2	3	2	1	0	1	1
NW	1	2	3	4	3	2	1	0	2
O	1	2	1	2	1	2	1	2	0

下载: 导出CSV 

| 显示表格

根据Goyal对方向概念距离的定义，“东”与“西”间的方向距离等于“东”与“南”的方向距离(同为2)，小于“东”与“西南”的方向距离3，然而这种大小关系反映的方向差异与人们的认知习惯存在着明显的不一致。造成这种不一致的根源在于Goyal对“东”与“西”间的方向距离定义与人对方向差异的认知不一致。按照人对方向差异的认知习惯，当一个目标绕参考目标旋转180°时，方向变化最大，此时方向最不相似，方向距离也应最大，即两个相反的方向概念之间的距离最大。因此，“东”与“西”、“南”与“北”等方向概念间的方向距离应定义为最大值4。改进后的方向概念距离如表 2所示，加粗数字表示改进的方向距离。改进后的各方向概念间的距离反映的差异大小更符合人们对方向差异的认知习惯。

表  2  改进的方向片之间的方向距离

Table  2.  Improved Distances Between the Basic Directional Tiles

Dist	N	NE	E	SE	S	SW	W	NW	O
N	0	1	2	3	4	3	2	1	1
NE	1	0	1	2	3	4	3	2	2
E	2	1	0	1	2	3	4	3	1
SE	3	2	1	0	1	2	3	4	2
S	4	3	2	1	0	1	2	3	1
SW	3	4	3	2	1	0	1	2	2
W	2	3	4	3	2	1	0	1	1
NW	1	2	3	4	3	2	1	0	2
O	1	2	1	2	1	2	1	2	0

下载: 导出CSV 

| 显示表格

2.2   基于最小元素法求解的方向相似性计算方法

Goyal基于方向关系矩阵模型提出了方向相似性值的计算公式。设D₀、D₁表示两个方向关系矩阵，方向相似性的计算公式为：

式中，d(D₀,D₁)表示方向关系矩阵之间的距离；d_max表示两方向关系矩阵之间的最大距离，可以证明其值为4。

由相似性值的计算公式可知，要计算两方向关系矩阵之间的相似值，就需要求出两方向关系矩阵之间的方向距离。§2.1中已经给出了单要素方向关系矩阵之间的方向距离，对于单要素与多要素方向关系矩阵之间的方向距离，可以通过求加权和得到(具体可参考文献^[9])。但是对于多要素方向关系矩阵之间的方向距离却比较难求，这主要是因为两方向关系矩阵中非零元素的之间如何移动及移动量难以确定。Goyal将两方向关系矩阵的最小转换代价定义为两方向关系矩阵所表达方向的方向距离，并将问题转化成了交通运输最小代价的求解问题，然后以“西北角”算法为基础进行多次迭代优化的方法对最小代价进行求解，这种求解方法运算过程复杂，时间代价较大，限制了方向相似性计算模型的应用。

本文提出利用最小元素法对转换代价进行求解，基本思想是构建两方向关系矩阵的转换问题表(图 3，类似于平衡运输问题表)，优先安排转换问题表中概念距离最小的两方向片之间的转换需求，然后满足概念距离次小的两方向片之间的转换需求，依次进行下去直到转换完毕为止。设D₀、D₁表示两多元素方向关系矩阵，基于最小元素法的方向距离计算步骤如下：

图  3  方向关系矩阵转换问题表

Figure  3.  Transportation Tableau Between Two DRM

下载: 全尺寸图片 幻灯片

1) 通过Δ⁰¹= D₀－D₁求出两方向关系矩阵的矩阵差Δ⁰¹，根据矩阵差Δ⁰¹构建如图 3所示的方向关系矩阵转换问题表。s₁、s₂、…、s_n表示矩阵差Δ⁰¹的正元素值，W_i(1≤i≤n)为s_i对应的方向片；d₁、d₂、…、d_m表示矩阵差△⁰¹的负元素值，M_j(1≤j≤m)为d_j对应的方向片；C_ij为方向片W_i与方向片M_j之间的概念距离(表 2)；x_ij(初始值为0)为需要求出的方向片W_i向方向片M_j转移的数值量；m、n表示矩阵差Δ⁰¹中正、负元素的个数，其取值范围都为^{[1, 9]}，且满足4≤m+n≤9。

2) 从构建的方向关系矩阵转换问题表中寻找方向概念距离最小的C_ij，设最小的元素为C_pq，比较s_p和d_q的大小关系：

(1) 若s_p>d_q，则x_pq的值更新为d_q，并划去第q列，同时将d_q值更新为0，将s_p的值更新为s_p=s_p-d_q；

(2) 若s_p=d_q，则x_pq的值更新为s_p，并划去第p行和第q列，并将s_p、d_q的值都更新为0；

(3) 若s_p<d_q，则x_pq的值更新为s_p，并划去第p行，同时将d_q值更新为d_q=d_q－s_p，将s_p的值更新为0。

3) 除去划去的行或列，对于未划去的行和列构成的转换问题表重复步骤2)，直至转换完毕，此时的x_ij的值即为转换代价最小的各个方向片之间的移动量，最后将两方向关系矩阵D₀、D₁的方向距离通过式(4)求得即可。

上面对算法的描述比较抽象，下面以两多元素方向关系矩阵D₀、D₁间的方向距离求解为例(图 4)进行说明：

图  4  最小元素算法的求解过程

Figure  4.  Course of the Computation Based on the Minimum Element

下载: 全尺寸图片 幻灯片

首先求出D₀、D₁的矩阵差Δ⁰¹，并转换为方向关系矩阵转换问题表(图 4(a))；图 4(b)~4(f)为基于最小元素法的求解过程。图 4(b)表示寻找值最小的C_ij为C₁₁，且s₁>d₁，故x₁₁=d₁=0.15，同时划去第一列，更新s₁= s₁-d₁=0.69，d₁=0；图 4(c)表示剩余C_ij中值最小的元素为C₂₂，且s₂>d₂，故x₂₂=d₂=0.01，并划去第二列，更新s₂= s₂-d₂=0.09，d₂=0；图 4(d)表示剩余C_ij中值最小的元素为C₂₄，且s₂>d₄，故x₂₄=d₄=0.06，同时划去第四列，更新s₂= s₂-d₄=0.03，d₄=0；图 4(e)表示剩余中C_ij中值最小的元素为C₂₃，且s₂<d₃，故x₂₃=s₂=0.03，划去第二行，更新s₂=0，d₃= d₃-s₂=0.69；图 4(f)表示最后一步求得x₁₃=s₁=d₃=0.69。

最终求得的各个x_ij的值为x₁₁=0.15、x₁₃=0.69、x₂₂=0.01、x₂₃=0.03、x₂₄=0.06，通过式(4)求得D₀、D₁两方向关系矩阵之间的距离为3.13。再通过式(3)求得D₀、D₁间方向相似性值为0.22。

基于最小元素的方向相似性计算方法能够满足Goyal优化算法的迭代终止条件，且求得的转换代价与Goyal通过迭代求得的转换代价相同，即得到的方向距离是一样的，并没有损失计算结果的精度，但是本算法不需要通过多次迭代，因此算法更为简单。

3 实验分析

为验证改进的方向相似性计算模型的科学性，本文基于ArcEngine平台利用C#编程实现了以上改进的算法。为更好体现本文计算模型的合理性和适用性，实验分为两组，分别从人类方向差异性认知的角度和方向相似性计算在面状空间数据多尺度表达中方向不一致检测中的应用角度对改进模型的正确性和使用价值进行验证。

3.1   认知实验

本文方向相似性的认知实验分为两组数据，如图 5(a)、5(b)。第一组数据图 5(a)中编号为“0”的图和第二组数据图 5(b)中编号为“0”的图分别为两组数据的参考场景，但是第一组数据中的参考场景中目标对象(浅色面状对象)位于参考对象(深色面状对象)的西北方向，第二组数据中的参考场景中目标对象(浅色面状对象)位于参考对象(深色面状对象)的正北方向。每组数据中17个是参考场景中目标对象绕参考对象顺时针旋转到不同位置的场景，分别利用Goyal和本文提出的方向相似性计算模型计算每个场景与对应参考场景的方向相似性值，用S₀和S₁分别表示Goyal模型和本文改进模型计算的方向相似值，如图 5所示。

图  5  认知实验场景及其相似性计算结果

Figure  5.  Scenes of the Cognitive Experiment and the Corresponding Similarity Values for Direction Relations

下载: 全尺寸图片 幻灯片

为了更清楚地表达两种计算模型反映的方向相似性的变化规律，将计算结果以曲线的形式可视化表达出来，如图 6(a)~6(d)，横坐标表示场景编号，纵坐标表示对应场景与参考场景的方向相似性值。图 6(a)、6(b)分别表示第一组实验两种计算模型反映的方向相似性变化情况，可以看出两种模型计算的结果反映的相似性变化规律都是相似性“先变小后变大”；图 6(c)、6(d)分别表示第二组实验两种模型反映的方向相似性变化情况，但两种模型反映的方向相似性差异变化规律却不尽相同：Goyal(图 6(c))反映的相似性变化规律为“先变小后变大、再变小又变大”，本文提出的模型(图 6(d))反映的变化规律为“先变小后变大”，这更符合人类的空间认知。

图  6  方向相似性计算结果的可视化表达

Figure  6.  Statistic Results of Questionnaire

下载: 全尺寸图片 幻灯片

根据认知心理学试验方法的要求，以问卷调查的形式对50名具有不同生活背景的成年人进行了调查研究。问卷要求被调查者对各曲线反映的方向相似性变化规律选择“完全同意”、“同意”、“不同意”中的一个，统计结果如表 3所示，其中T表示选择“完全同意”的人数；G表示选择“同意”的人数；N表示选择“不同意”的人数，认同率是T+G的值与调查总人数的比值。

表  3  调查问卷实验统计结果

Table  3.  Statistic Results of Questionnaire

实验	T	G	N	认同率/%
图 6(a)	24	26	1	98
图 6(b)	24	26	1	98
图 6(c)	1	5	44	12
图 6(d)	19	29	3	94

下载: 导出CSV 

| 显示表格

通过表 3的统计结果可以看出：对于图 5(a)中方向相似性的变化规律，两计算模型的计算结果与人的认知都相一致，但对于图 5(b)中方向相似性的变化规律，Goyal模型的认同率就比较低，而本文提出的改进模型的计算结果反映的变化规律的认同率高达94%。这进一步说明了本文方法更加符合人类的空间认知心理。

3.2   数据多尺度表达中方向不一致性检测

空间数据多尺度表达中的方向一致性与方向相似性有着紧密的联系：被判定为不一致的两方向关系，其相似性值往往比较小。基于此，多尺度空间数据表达中方向不一致的检测问题可转化为方向相似性的计算问题。图 7(a)为某地区只保留了居民地和面状水系的1∶2.5万地形图数据，图 7(b)为该地区对应的1∶5万数据。在方向一致性检测前，需要建立两个比例尺数据间的关联关系。进行检测的方向关系应满足以下两个条件：① 是相邻对象间的方向关系；② 是在两比例尺数据中都存在的对象之间的方向关系。另外，由于方向关系矩阵模型表达的两目标间的方向关系具有不可反性，每对对象间的方向关系需要计算正反两次。

图  7  多尺度表达中方向不一致检测

Figure  7.  Checking of Directional Inconsistency in Multi-scale Spatial Data

下载: 全尺寸图片 幻灯片

利用本文提出的模型对两种尺度数据间对应方向关系的相似性进行了计算，并根据数据质量的要求设定相应的阈值，进行方向不一致性检测。如果两空间目标间在两个尺度数据中的方向关系相似性小于设定的阈值，则认为该方向关系在两个尺度的表达中出现了方向不一致现象。并以0.85作为判断方向一致与否的阈值，该实验数据中共检测出6处不一致的方向关系。为了便于人工纠正，将不一致的方向关系进行了标注，如图 7(b)，用黑色实线段连接与大比例尺中方向关系不一致的两空间对象的质心。

4 结 语

本文在分析当前方向相似性计算模型存在着计算复杂、与人的认知存在部分不一致、应用困难等不足的基础上，对Goyal提出的计算模型进行了改进。

1) 扩展的方向关系矩阵模型能够计算有面群参与的方向关系，这很好地满足多尺度表达中方向相似性的计算，使其能够在空间数据多尺度表达、地图综合等领域中的方向一致性评价方面得以应用。

2) 通过改进各个方向概念之间的方向距离的定义方式，计算得到的方向相似性变化规律的认同率较高，表明改进模型的方向相似性计算结果与人们对方向差异的认知习惯相一致。

3) 基于最小元素法的方向相似性计算模型原理方法简单，与迭代优化的方法相比，降低了计算的复杂度，能够提高计算效率，这对于海量的空间数据处理来说具有十分重要的意义。