-
整合不断增长的地理空间数据[1-2]是目前地理信息科学的发展趋势之一。这些数据来自政府、志愿者、科学研究和企业等，形成大量不连通的空间数据岛。空间数据整合能有效防止数据隔离[3]，实现了不同来源空间数据的属性共享和几何精度改进[4-6]，并降低数据的生产成本。地图对齐是空间数据整合的重要内容，将具有特定用途但位置精度不高的空间数据与高精度的空间数据对齐，使前者也能拥有高精度的位置信息，以创造更大的社会和经济价值[7-8]。本文专注于建筑物面实体的对齐方法研究，建筑物面是地形图中的主要面要素类型，也是OSM(OpenStreetMap)数据中的重要组成部分。
地图对齐研究的一个起源是文献[9-10]提出的基于同名点三角剖分的坐标调整方法。该方法首先通过点匹配算法所得的同名点对建立数据之间拓扑同构的Delaunay三角网，然后在三角子区域内进行坐标转换，以缩小位置差异。由于基于同名实体的方法往往能够获得更准确的结果[11-12]，因此识别同名实体和它们对齐所使用的共轭点对成为地图对齐研究的重点[7-8]。实体匹配被定义为识别同名实体的过程，它首先衡量候选匹配之间的相似性，如距离[13]、形状[14]和上下文[15]等，然后决定具有最高相似性的候选匹配为最优匹配[16]，该领域已有大量的成果。但检测同名实体之间共轭点对的研究却相对稀疏，已存在的研究成果主要分为两类。一是基于区域的方法，如文献[17-18]首先通过几何相似性匹配面实体，然后利用迭代最近点(iterative closest points, ICP)检测同名面实体的轮廓上的对应点对；二是基于轮廓的方法，如文献[19]获得匹配后的同名岛屿后，利用离散Frechet距离来匹配同名面实体的对应点对；文献[8]使用了修改的顶点属性串匹配(vertices attributed string matching, VASM)[20]算法检测共轭点对，该算法以最小总编辑成本将目标实体的轮廓转换为参考实体的轮廓；文献[21]指出文献[8]中点编辑操作成本会因启发式设置而产生错误结果，并提出了点编辑操作的成本函数设置方法；文献[7]引入遗传算法来匹配面实体，并提出基于转角函数[22]的变化来匹配点对。然而，基于区域的ICP算法对初始匹配结果非常敏感，可能随着异常值的存在而退化[23]，且匹配时需要先验的对应点对之间的变换模型。而基于轮廓的方法则很难识别1:N和M:N同名实体之间的共轭点对，因此它们之间存在相对复杂的对应轮廓，如文献[7, 19]所提出的方法。为了解决这个问题，文献[8, 21]将1:N和M:N匹配聚合为一对简单的面实体来处理，这不可避免地造成了匹配精度的降低。因此，需进一步改进以解决1:N和M:N同名实体之间共轭点对的识别问题。
本文提出了一种用于空间数据整合的面实体对齐方法，首先基于文献[24]提出的面实体匹配方法来识别整合数据之间的同名实体。为了检测1:N和M:N同名实体之间的共轭点对，本文引入结合了几何相似性的成对约束谱匹配算法[25]。成对约束谱匹配算法是一种经典的基于区域的点模式匹配算法，能够实现不同大小点集之间的匹配，并且对1:N和M:N同名实体中存在干扰点和局部轮廓形变的情况具有良好的抵御能力。然后，利用等价权函数修饰的最小二乘法来对齐同名面实体，该算法能够处理1:N和M:N同名实体中存在弱对应点对和错误对应点对的情况。通过武汉市同一区域的基础测绘数据和谷歌地图数据进行验证，证明本文方法不仅能够识别1:1、1:N和M:N同名实体的共轭点对，而且可获得差异最小化的地图对齐结果。
-
图 1演示了本文方法的流程，主要包含3个部分。一是利用建筑面实体匹配方法识别同名实体，这是地图对齐的前提；二是基于几何相似性的成对约束谱匹配算法识别同名实体之间的共轭点对；三是基于IGG1权重的最小二乘法对齐同名实体。
图 1 本文所提出方法的流程
Figure 1. Workflow of the Proposed Method
-
在面实体匹配中，双向面积重叠技术广泛应用于M:N匹配关系的识别[12, 26-27]中。该方法可描述为：如果数据集A中任意面实体ai与数据集B中面实体bi1, bi2…bih重叠，并且：
$$ \frac{{{\rm{Area}}\left( {{a_i} \cap {b_{ih}}} \right)}}{{\min \left( {{\rm{Area}}\left( {{a_i}} \right),{\rm{Area}}\left( {{b_{ih}}} \right)} \right)}} \ge \gamma $$ (1) 将bi1, bi2…bih聚合为一个面实体bj来看待，此时，如果聚合面实体bj与数据集A中面实体aj1, aj2…ajk(ai∉aj1, aj2…ajk)重叠，并且它们的面积重叠了也满足式(1)，可将ai, aj1, aj2…ajk也聚合为一个面实体来看待；递归上述过程，直到没有新的面实体被聚合。最后可获得一对M:N匹配。通常，在式(1)中设阈值γ=0.3[13, 28]。然而，匹配数据往往存在位置偏差，这可能会扭曲对应实体之间的重叠关系。为了解决这个问题，文献[25]提出了一个设想，即通过对齐待匹配对之间最小外接矩形(minimum bounding rectangle, MBR)来改善同名实体之间的重叠面积。如图 2所示，在图 2(a)中直接通过双向面积重叠技术，错误匹配对(a2:b2)被检测到；如果对齐匹配对a1、a2和b1、b2的MBR(图 2(b))，则通过双向面积重叠技术，正确匹配对(a1, a2:b1, b2)被检测到(图 2(c))。
图 2 改善同名实体之间的重叠面积
Figure 2. Alignment of Corresponding Object-Set Pair by Aligning Their MBRs
在该设想中，需预先获得同名实体的MBR，因此文献[25]提出基于回溯法的MBR组合优化算法和匹配空间域的概念来检测1:1、1:N和M:N匹配的对应MBR。在匹配评估阶段，为了避免神经网络，需要预先进行模型训练，本文提出式(2)来筛选正确的匹配对：
$$ \frac{{{\rm{Area}}\left( {{f^C}\left( {{A^i}} \right) \cap {f^C}\left( {M\left( {{B^i}} \right)} \right)} \right.}}{{\max \left( {{\rm{Area}}\left( {{f^C}\left( {{A^i}} \right)} \right),{\rm{Area}}\left( {{f^C}\left( {{B^i}} \right)} \right)} \right)}} > \rho $$ (2) 式中，Ai={a1…am}和Bi={b1…bn}是候选匹配对；ρ是阈值；fC是将多个离散的面实体组合为一个凸包的函数；M是对齐Ai和Bi的MBR中心点的平移函数。在式(2)中fC将Ai和Bi聚合为一对凸多边形，这避免了Ai、Bi的重叠面积非常小的情况。因为如果将Ai和Bi直接作为一个多边形，则可能为带孔的多边形。此外，匹配过程中会产生很多冗余的候选匹配对，它们之间的构成差异可能仅仅是一个或几个小实体，如图 3所示。
图 3 两个候选匹配的构成仅仅相差一个小实体
Figure 3. Two Matching Pairs with a Difference of Only One Small Object
图 3中候选匹配对1和候选匹配对2都满足式(2)，为了选择最优匹配，本文通过式(3)来进一步筛选：
$$ \begin{array}{*{20}{c}} {\max \left( {\frac{{{\rm{Area}}\left( {{A^{i1}} \cap M\left( {{B^i}} \right)} \right)}}{{\sqrt {{\rm{Area}}\left( {{A^{i1}}} \right) \times {\rm{Area}}\left( {{B^i}} \right)} }},} \right.}\\ {\frac{{{\rm{Area}}\left( {{A^{i2}} \cap M\left( {{B^i}} \right)} \right)}}{{\sqrt {{\rm{Area}}\left( {{A^{i2}}} \right) \times {\rm{Area}}\left( {{B^i}} \right)} }}} \end{array} $$ (3) 可见，式(2)体现了评估方法关注的全局特征，式(3)体现了评估方法关注的局部特征。
-
获得同名实体之后，提取待匹配的轮廓点集，检测其共轭点对。设同名实体对Ai={a1…am}和Bi={b1…bn}，提取它们的轮廓点集分别为P={p1…pnp}和Q={q1…qnq}。P和Q所有可能匹配的点对集合和正确匹配点对集合分别为L和C，C∈L，L的长度为nl(nl≤np×nq)，C的长度nc=min (np, nq)。为获得所有正确点对C，本文采用文献[27]提出的成对双向谱匹配算法来求解，该方法对出格点具有较好的鲁棒性，且能实现不同大小点集的匹配。
设L中任意两个点对a=(pu, qv)，b=(pw, qz)，a, b∈L, a≠b，定义a和b的关联性为pu和qv以及pw和qz的匹配情况的相关性，若a和b的匹配情况是一致性的，则a和b的关联度高；否则，a和b的关联度低。如图 4所示，a=(pu, qv)和b=(pw, qz)具有很高的关联度，而a=(pu, qv)和b′=(pw, qz′)的关联度却很低。成对双向谱匹配算法的基本思想是寻找点对之间全局关联度最大化的集合，如此点对之间的最佳匹配关系也同时被识别。
图 4 成对约束谱匹配算法
Figure 4. Pairwise Constraints Spectral Matching Algorithm
此处，将P和Q所有可能匹配的点对之间的关联度用矩阵M表示，关联矩阵中的元素M(a, b)表示为a和b的关联度。本文定义a和b的关联度为它们之间距离、长度和方向的相似度的加权平均数，这也是本文的关键技术之一。这是因为在地形图中，地理实体是具有空间参考的，并且在大小和形状等特征上存在相似性[29]。即使对于1:N和M:N类型的同名面实体对，其整体上也存在轮廓和结构上的相似性[30]。a和b的距离相似度计算公式为：
$$ {S_d}\left( {a,b} \right) = 1 - \frac{{{\rm{HD}}\left( {{l_{{p_u}{p_w}}},{l_{{q_v}{q_z}}}} \right)}}{{{d_\tau }}} $$ (4) 式中，dτ是距离阈值，可取缓冲距离；lpupw是点pu和点pw连接的线段，lqvqz是点qv和点qz连接的线段; HD(lpupw, lqvqz)是线段lpupw与lqvqz的Hausdorff距离。a和b的长度相似度计算公式为：
$$ {S_l}\left( {a,b} \right) = 1 - \frac{{\left| {\left| {\overrightarrow {{p_u}{p_w}} } \right| - \left| {\overrightarrow {{q_v}{q_z}} } \right|} \right|}}{{\max \left( {\left| {\overrightarrow {{p_u}{p_w}} } \right|,\left| {\overrightarrow {{q_v}{q_z}} } \right|} \right)}} $$ (5) a和b的方向相似度计算公式为：
$$ {S_c}\left( {a,b} \right) = \frac{{\left| {\overrightarrow {{p_u}{p_w}} \times \overrightarrow {{q_v}{q_z}} } \right|}}{{\left| {\overrightarrow {{p_u}{p_w}} } \right| \times \left| {\overrightarrow {{q_v}{q_z}} } \right|}} $$ (6) $$ \begin{array}{*{20}{c}} {\mathit{\boldsymbol{M}}\left( {a,b} \right) = {w_1}{S_d}\left( {a,b} \right) + {w_2}{S_l}\left( {a,b} \right) + }\\ {{w_3}{S_c}\left( {a,b} \right)} \end{array} $$ (7) 式中, w1、w2、w3为权重系数，分别取值为0.3、0.4和0.3；M(a, b)∈[0, 1]，M(a, b)=0表示无相关性，M(a, b)=1表示绝对相关，矩阵中对角元素M(a, a)=0。在计算中，若a和b的几何相似度很低，或a和b不可能关联，如pu=pw，但qv≠qz的情况，则令M(a, b)=0。由于可能匹配的点对保持在一定邻域范围内，因此定义匹配点对$ \left| \overrightarrow{{{p}_{u}}{{q}_{v}}} \right|\le {{d}_{\tau }} $。最终，M是一个稀疏对称正矩阵。
从统计上看，所有正确匹配点对之间应是强关联的(M(a, b)值大)，不正确匹配点对仅在偶然的情况下才会与正确匹配点对相容，因为不正确匹配点的位置是随机的和非结构的。换言之，正确匹配点对之间存在强关联聚类，即SC表示所有共轭点对的相关度，${{S}_{C}}=\sum\limits_{a, b\in C}{\mathit{\boldsymbol{M}}(a, b)} $取得最大值。对于该类问题，可采用谱矩阵分解来解，聚类C通过L的nl×1维指示向量x来表示，x(a)=1或x(a) =0，则SC可以表示为：
$$ {S_C} = \sum\limits_{a,b \in C} {\mathit{\boldsymbol{M}}\left( {a,b} \right)} = {\mathit{\boldsymbol{x}}^{\rm{T}}}\mathit{\boldsymbol{Mx}} $$ (8) 式(8)的最优解x*可以表示为：
$$ {\mathit{\boldsymbol{x}}^ * } = \arg \max \left( {{\mathit{\boldsymbol{x}}^{\rm{T}}}\mathit{\boldsymbol{Mx}}} \right) $$ (9) 根据Rayleigh-Ritz定理[31]，当x取M最大特征值λmax对应的特征向量时，可获得SC。得到x*后，采用贪婪算法对x*进行二值化。第一步，先取x*中最大值对应的L中点对(pu*, qv*)存储在C中，并排除L中与(pu, qv)相冲突特征点对(pu*, ·)、(·, qv*)和x*中所对应的元素；第二步，继续在x*中取最大值所对应L中的点对，重复第一步，直到L中元素全部被排除。此时，C即为正确匹配的点对集合, 令C={c1, c2…cnc}。
-
获得共轭点对C={c1, c2…cnc}后，本文通过共轭点对调整同名实体之间的位置信息。在已有的研究中[7, 8, 19, 21]，位置信息调整是直接基于共轭点对处理的，但这要求获得的所有共轭点对的一致性较好。由于在1:N和M:N同名实体中，它们之间的部分轮廓形态不可避免地存在较大差异。尽管匹配算法获得了点对之间的最佳匹配，实际上点对中还存在对应关系较弱甚至是错误对应关系。如图 5所示，(a1, a2, a3):(b1, b2)是一个M:N同名实体，c1, c2…c8是通过基于几何相似性的成对约束谱匹配算法检测共轭点对。从图 5中可观察到，c1、c2、c3、c4与同名实体整体的变换存在较高的相似性，定义这一类情况为强对应点对；c5、c6与同名实体整体的变换存在一定的相似性，可能认为同名实体之间发生了随机抖动或局部扭曲，定义这一类情况为弱对应点对；c7、c8与同名实体整体的变换相冲突，为离群点对，定义这一类情况为错误对应点对，应排除出去。
图 5 M:N同名实体点对应示例
Figure 5. Point Correspondences in M:N Match
为了获得更准确的实体对齐结果，本文提出一种基于IGG1权重的最小二乘法的对齐方法。实体平移变换公式如下：
$$ \left[ {\begin{array}{*{20}{c}} \mathit{\boldsymbol{X}}\\ \mathit{\boldsymbol{Y}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} \mathit{\boldsymbol{x}}\\ \mathit{\boldsymbol{y}} \end{array}} \right] + \left[ {\begin{array}{*{20}{c}} {\Delta x}\\ {\Delta y} \end{array}} \right] $$ (10) 式中, (Δx, Δy)是平移向量。由于存在nc个共轭点对，设第i个点对的平移向量为(Δxi, Δyi)，总偏移向量采用最小二乘法进行平差获得，最小二乘法公式为：
$$ \min \sum\limits_{i = 1}^{{n_c}} {w\left( {r_i^{k - 1}} \right){{\left( {r_i^k} \right)}^2}} $$ (11) 式中, $ r_{i}^{k}=\sqrt{{{(\Delta {{x}_{i}}-\Delta \overline{x})}^{2}}+{{(\Delta {{y}_{i}}-\Delta \overline{y})}^{2}}} $; $ \Delta \overline{x}=\sum\limits_{j=1}^{{{n}_{c}}}{w\left( r_{j}^{k-1} \right)\Delta {{x}_{j}}} $; $ \Delta \overline{y}=\sum\limits_{j=1}^{{{n}_{c}}}{w\left( r_{j}^{k-1} \right)\Delta {{y}_{j}}} $; w(rik-1)为权重，其计算公式为：
$$ w\left( {r_i^{k - 1}} \right) = \frac{{P\left( {r_i^{k - 1}} \right)}}{{\sum\limits_{j = 1}^{{n_c}} {P\left( {r_j^{k - 1}} \right)} }} $$ (12) P(rik-1)采用IGG1方案权函数[32]，即：
$$ P\left( r \right) = \left\{ \begin{array}{l} 1,r \le {\sigma _1}\\ \frac{{{\sigma _1}}}{r},{\sigma _1} < r \le {\sigma _2}\\ 0,r > {\sigma _2} \end{array} \right. $$ (13) 式中, r表示与加权平均误差的残差，当r > σ2时，说明该点对可能为错误匹配，设置其权重为0；当σ1 < r≤σ2时，说明其为弱对应点对，设置其权重较小；当r≤σ1时，说明其为强对应点对，该匹配点对对应的局部轮廓变化在可信范围内；σ1、σ2的取值和对应实体的大小进行关联，
$$ {\sigma _1}{\rm{ = }}0.1\sqrt {w\left( {{\rm{MBR}}} \right) \times h\left( {{\rm{MBR}}} \right)} $$ $$ {\sigma _2} = 0.25\sqrt {w\left( {{\rm{MBR}}} \right) \times h\left( {{\rm{MBR}}} \right)} $$ w(MBR)和h(MBR)分别是待对齐实体的MBR的宽和高。
-
本文选取武汉市青山区同一区域基础地图建筑物面数据和谷歌地图建筑物面数据进行实验验证。基础地图数据的比例尺为1:500，包含392个面实体，生产时间为2012年10月；谷歌地图数据的比例尺约为1:800，包含154个面实体，是在第20级谷歌切片地图基础上数字化获得的(见图 6)。它们的空间覆盖范围为3个街区块，面积约为0.18 km2，实验数据叠加在一起的效果如图 7所示。从图 7中可看出，谷歌地图数据和基础测绘地图数据存在明显位置偏移。毫无疑问，基础测绘地图数据具有更高的位置和几何信息，谷歌地图数据存在较大的误差。实验通过Microsoft Visual Studio 2010C#，ArcGIS Engine 10.1和MATLAB实现。在本文匹配方法中，设置缓冲距离dτ=20 m，MBR组合优化算法阈值ε=0.2，ρ=0.6。
图 6 谷歌切片地图数据
Figure 6. Google Map Data
图 7 基础地图数据和谷歌地图数据叠加
Figure 7. Superimposed Map of Base Map and Google Map
在本实验中，实体匹配结果由制图工程师人工检测确认，并将人工匹配结果作为评估自动化方法的标准。本文用TP表示正确匹配对数，FP表示错误匹配对数，FN表示漏匹配对数，则准确率=$ \frac{{{\rm{TP}}}}{{{\rm{TP + FP}}}} \times 100\% $，召回率=$ \frac{{{\rm{TP}}}}{{{\rm{TP + FN}}}}{\rm{ \times 100\% }} $。
表 1显示了基础测绘数据和谷歌地图数据匹配结果(括号内表示匹配对的数量)，准备率和召回率分别为93.3%和94.7%，均大于90%，因此本文基于MBR组合优化算法实现了良好且稳健的匹配。
表 1 基础测绘数据和谷歌地图数据匹配结果
Table 1. Matching Result of Base Map and Google Map
匹配类型(匹配对数量) TP FP FN 1:1(91) 82 2 7 1: N(36) 32 4 0 N:1(3) 3 0 0 M:N(5) 4 1 0 1:0(6) 4 2 0 图 8展示了一个典型区域内实体匹配的结果，显示了16个正确匹配对，1个不正确匹配对和1个错误匹配对。结果说明基于MBR组合优化算法的面实体匹配方法获得了较好的匹配结果。尤其值得注意的是，对于一些位置偏差较大的同名实体，本文的面匹配方法也可以准确识别。图 8中标识的不正确匹配对形状变化较大，漏匹配了一个较小实体；而标识出的漏匹配对形状差异较大，导致MBR组合优化算法未能检测到该匹配对作为潜在匹配对。
图 8 一个典型区域实体匹配结果
Figure 8. Matching Results of a Typical Region
在实体匹配中共获得了135对同名实体，通过基于IGG1的最小二乘法对齐同名实体对，同名实体平均对齐距离为4.650 1 m，标准差为3.101 9 m，最大对齐距离近18 m(17.684 7 m)，最小对齐距离小于0.1 m(0.096 7 m)。图 9显示了对齐距离的分布频率。
图 9 同名实体对齐距离分布频率
Figure 9. Distribution of Aligning Distance from Base Map and Google Map
图 10展示了一个典型区域(典型区域1)共轭点对匹配结果和同名实体对齐结果，显示了6对1:1同名实体对齐过程。结果显示，本文方法对1:1同名实体能够获得较好的共轭点对检测结果和对齐效果。图 10中实体a1和b′1是同名实体，但它们存在较大的位置偏差，通过检测它们的共轭点对来对齐a1和b′1，并得到b′1对齐之后的实体b1，该过程改善了来自谷歌地图的实体的位置信息。图 10中a2和b′2是同名实体，但a2和b′2存在一定的形状差异，通过共轭点和基于IGG1权重的最小二乘法对齐a2和b′2，获得更准确的实体对齐结果(a2和b2)。因此，本文所提出的实体对齐方法相比直接通过形状中心点对齐的方法，更能使同名实体位置信息差异最小化。
图 10 典型区域1内共轭点对匹配结果和同名实体对齐结果
Figure 10. Results of Point Correspondences and Objects Alignment in Typical Region One
图 11展示了一个典型区域(典型区域2)共轭点对匹配结果和同名实体对齐结果，显示了一对1:1的同名实体，一对1:2的同名实体和一对2:3的同名实体对齐过程。结果显示，本文方法对1:N和M:N也具有较好的对齐效果。图 11中实体a1、a2和b′1是一对1:2的同名实体，其中单一实体a1或a2与b′1只存在局部对应，但a1和a2构成的整体和b′1存在较好的对应，因此本文方法检测到b′1和a1的5对共轭点对以及b′1和a2的2对共轭点对。通过检测到的7对共轭点对，对齐a1、a2和b′1，b′1对齐效果为b1，使同名实体位置信息差异最小化。基于几何相似性的成对约束谱匹配算法是基于区域的点匹配算法，可从整体结构上检测存在复杂对应轮廓的匹配的共轭点对，这克服了基于轮廓的点匹配算法的缺点。图 11中实体a3、a4、a5和b′2、b′3是一对3:2的同名实体，同样基于区域的点匹配算法检测到8对共轭点对，但M:N匹配中不可避免存在弱对应点对或错误对应点对，虽然这些点对也满足整体一致性最小。通过所提出的基于IGG1权重的最小二乘法，本文依然可对齐存在弱对应点对或错误对应点对的同名实体，a3、a4、a5和b′2、b′3对齐效果为b2、b3。
图 11 典型区域2内共轭点对匹配结果和同名实体对齐结果
Figure 11. Results of Point Correspondences and Objects Alignment in Typical Region Two
-
随着免费的地理信息数据不断增多，这些数据的有效整合变得越来越重要。本文提出一种用于空间数据整合的地图对齐方法，基于实体匹配和共轭点对来对齐实体，使同名建筑物面实体对位置信息差异最小化。该方法包含3个部分：基于MBR组合优化算法的面实体匹配方法识别同名实体，基于几何相似性的成对约束谱匹配算法来检测共轭点对，以及基于IGG1权重的最小二乘法对齐同名实体。通过实验分析，可以得出结论如下。
1) 本文改进的基于几何相似性的成对约束谱匹配算法可检测存在复杂对应轮廓的匹配的共轭点对，包括1:N和M:N匹配的共轭点对，这克服了基于轮廓的点匹配算法的缺陷。
2) 本文改进的基于稳健估值的最小二乘法可有效解决1:N和M:N匹配中不可避免存在的弱对应点对或错误对应点对的问题，实现同名实体的准确对齐。
本文仅以测绘地图数据和商用地图数据作为实验对象来验证所提出方法的有效性，并不涉及地图数据解密等问题，但所提出的方法可用于众源地理信息的质量改善和评价。此外，还存在一些问题需要进一步研究。首先，基于几何相似性的成对约束谱匹配算法虽然实现了整体结构上的一致性最大化，但在局部结构上可能存在错误对应情况，这需要结合基于轮廓的匹配方法来优化；其次，本文方法仅用于建筑物面的对齐，对复杂的地块、水域等类型的面实体对齐方法的研究将在下一步展开。
-
摘要: 提出了一种用于空间数据整合的建筑物面实体对齐方法，可用来改善空间数据的位置精度。首先，采用基于最小外接矩形（minimum bounding rectangle，MBR）组合优化算法的匹配方法识别整合数据之间的同名实体；然后，提出基于几何相似性的成对约束谱匹配算法检测1：1、1：N和M：N同名实体之间的共轭点对；针对1：N和M：N匹配中不可避免存在弱对应点对和错误对应点对的问题，提出基于IGG1权重的最小二乘法来有效对齐同名实体。将所提出的方法应用于对齐较高位置精度的基础测绘地图数据和较低位置精度的谷歌地图数据中，结果表明，该方法不仅可检测存在复杂轮廓对应的1：N和M：N同名实体的共轭点对，而且可实现它们之间的有效对齐，使同名实体的位置信息差异最小化。Abstract: This paper proposes a building polygon alignment approach for spatial data integration which can be used to improve the spatial data position accuracy. Firstly, this paper uses the minimum bounding rectangle combinatorial optimization algorithm to identify corresponding objects between the integrated data. Then, a pairwise constraint spectrum matching algorithm based on geometric simila-rity is proposed to detect conjugate-point pairs of 1:1, 1:N, and M:N correspondence. The conjugate-point pairs from 1:N, and M:N correspondence inevitably have weak or error corresponding point pair, thus this paper proposes a least-squares algorithm based on the IGG1 weight to align the corresponding objects. The proposed method is applied to align base map data with higher positional accuracy and Google map data with lower positional accuracy. The results show that the proposed method can not only detect conjugate-point pairs of 1:N, and M:N correspondence with complex contours, but also can achieve the accurate alignment between them, and minimize their difference of positional information.
-
Key words:
- building polygon /
- spatial data integration /
- map alignment /
- object matching /
- contour-point pair
-
图 2 改善同名实体之间的重叠面积
Figure 2. Alignment of Corresponding Object-Set Pair by Aligning Their MBRs
图 3 两个候选匹配的构成仅仅相差一个小实体
Figure 3. Two Matching Pairs with a Difference of Only One Small Object
图 9 同名实体对齐距离分布频率
Figure 9. Distribution of Aligning Distance from Base Map and Google Map
图 10 典型区域1内共轭点对匹配结果和同名实体对齐结果
Figure 10. Results of Point Correspondences and Objects Alignment in Typical Region One
图 11 典型区域2内共轭点对匹配结果和同名实体对齐结果
Figure 11. Results of Point Correspondences and Objects Alignment in Typical Region Two
表 1 基础测绘数据和谷歌地图数据匹配结果
Table 1. Matching Result of Base Map and Google Map
匹配类型(匹配对数量) TP FP FN 1:1(91) 82 2 7 1: N(36) 32 4 0 N:1(3) 3 0 0 M:N(5) 4 1 0 1:0(6) 4 2 0 
下载: 导出CSV
-
[1] Xavier E M, Arizalopez F J, Urenacamara M A. A Survey of Measures and Methods for Matching Geospatial Vector Datasets[J]. ACM Computing Surveys, 2016, 49:1-34 http://dl.acm.org/ft_gateway.cfm?id=2963147&ftid=1780068&dwn=1&CFID=675543088&CFTOKEN=63263631 [2] Wiemann S. Formalization and Web-Based Implementation of Spatial Data Fusion[J]. Computers & Geosciences, 2017, 99:107-115 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=f52128928081883028f6a1df0258c742 [3] Wiemann S, Bernard L.Spatial Data Fusion in Spatial Data Infrastructures Using Linked Data[J]. International Journal of Geographical Information Science, 2016, 30:613-636 doi: 10.1080/13658816.2015.1084420 [4] Yuan S, Tao C. Development of Conflation Components[C]. Geoinformatics'99 Conference, Ann Arbor, USA, 1999 [5] Longley P A, Goodchild M, Maguire D J, et al. Geographic Information Systems and Science[M]. New Jersey: John Wiley & Sons Inc, 2001 [6] Tong X, Liang D, Jin Y, et al. A Linear Road Object Matching Method for Conflation Based on Optimization and Logistic Regression[J]. International Journal of Geographical Information Science, 2014, 28(4): 824-846 doi: 10.1080/13658816.2013.876501 [7] Ruiz-Lendínez J, Ureña-Cámara M, Ariza-López F. A Polygon and Point-Based Approach to Matching Geospatial Features[J]. International Journal of Geo-Information, 2017, 6(12):399 doi: 10.3390/ijgi6120399 [8] Huh Y, Yu K, Heo J. Detecting Conjugate-Point Pairs for Map Alignment Between Two Polygon Datasets[J]. Computers, Environment and Urban Systems, 2011, 35: 250-262 doi: 10.1016/j.compenvurbsys.2010.08.001 [9] Saalfeld A. Conflation: Automated Map Compilation[J]. International Journal of Geographical Information Systems, 1988, 2:217-218 doi: 10.1080/02693798808927897 [10] Jensen J, Saalfeld A, Broome F, et al. Spatial Data Acquisition and Integration[J]. Geomorphology, 2011, 41(2-3):171-181 http://d.old.wanfangdata.com.cn/Periodical/dlxxsj201602017 [11] Hecht R, Kunze C, Hahmann S. Measuring Completeness of Building Footprints in OpenStreetMap over Space and Time[J]. ISPRS International Journal of Geo-Information, 2013, 2(4):1 066-1 091 doi: 10.3390/ijgi2041066 [12] Fan H, Zipf A, Fu Q, et al. Quality Assessment for Building Footprints Data on OpenStreetMap[J]. International Journal of Geographical Information Science, 2014, 28: 700-719 doi: 10.1080/13658816.2013.867495 [13] Devogele T. A New Merging Process for Data Integration Based on the Discrete Frechét Distance[C]. Joint International Symposium on Geospatial Theory, Processing and Applications, Ottawa, Canada, 2002 doi: 10.1007/978-3-642-56094-1_13 [14] 安晓亚, 孙群, 肖强, 等.一种形状多级描述方法及在多尺度空间数据几何相似性度量中的应用[J].测绘学报, 2011, 40(4):495-501, 508 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK201101695862 An Xiaoya, Sun Qun, Xiao Qiang, et al.A Shape Multilevel Description Method and Application in Measuring Geometry Similarity of Multi-scale Spatial Data[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(4):495-501, 508 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK201101695862 [15] Kim J O, Yu K, Heo J, et al. A New Method for Matching Objects in Two Different Geospatial Datasets Based on the Geographic Context[J]. Compu-ters & Geosciences, 2010, 36: 1 115-1 122 http://www.sciencedirect.com/science/article/pii/S0098300410001731 [16] Li L, Goodchild M F. An Optimization Model for Liner Feature Matching in Geographical Data Conflation[J]. International Journal of Image and Data Fusion, 2011, 2:309-328 doi: 10.1080/19479832.2011.577458 [17] Gösseln G, Sester M.Change Detection and Integration of Topographic Updates from ATKIS and Geoscientific Data Sets[C]. International Conference on Next Generation Geospatial Information, Boston, USA, 2003 [18] Butenuth M, Von Gosseln G, Tiedge M, et al.Integration of Heterogeneous Geospatial Data in a Federated Database[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2007, 62: 328-346 doi: 10.1016/j.isprsjprs.2007.04.003 [19] 郝燕玲, 唐文静, 赵玉新.基于多评价因素的面状要素合并变换算法[J].计算机辅助设计与图形学学报, 2009, 21(2):237-242 http://d.old.wanfangdata.com.cn/Periodical/jsjfzsjytxxxb200902017 Hao Yanling, Tang Wenjing, Zhao Yuxin. Areal Elements Adjusting Algorithm Based on Multi-eva-luation Factors[J]. Journal of Computer Aided Design & Computer Graphics, 2009, 21(2):237-242 http://d.old.wanfangdata.com.cn/Periodical/jsjfzsjytxxxb200902017 [20] Kaygin S, Bulut M M.Shape Recognition Using Attributed String Matching with Polygon Vertices as the Primitives[J]. Pattern Recognition Letters, 2002, 23(1-3): 287-294 doi: 10.1016/S0167-8655(01)00111-8 [21] Huh Y, Yang S, Ga C, et al. Line Segment Confidence Region-Based String Matching Method for Map Conflation[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2013, 78(4): 69-84 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=c50ee9984b99589dd79058238b7b9e92 [22] Arkin E M, Chew L P, Huttenlocher D P, et al. An Efficiently Computable Metric for Comparing Polygonal Shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(3): 209-216 doi: 10.1109/34.75509 [23] Chui H, Rangarajan A.A New Point Matching Algorithm for Non-rigid Registration[J]. Computer Vision and Image Understanding, 2003, 89 (2-3):114-141 doi: 10.1016/S1077-3142(03)00009-2 [24] 刘凌佳, 朱道也, 朱欣焰, 等.基于MBR组合优化算法的多尺度面实体匹配方法[J].测绘学报, 2018, 47(5):652-662 http://d.old.wanfangdata.com.cn/Periodical/chxb201805012 Liu Lingjia, Zhu Daoye, Zhu Xinyan, et al. A Multi-scale Polygonal Object Matching Method Based on MBR Combinatorial Optimization Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(5):652-662 http://d.old.wanfangdata.com.cn/Periodical/chxb201805012 [25] Leordeanu M, Hebert M. A Spectral Technique for Correspondence Problems Using Pairwise Constraints[C]. The 10th IEEE International Confe-rence on Computer Vision, Beijing, China, 2005 [26] 罗国玮, 张新长, 齐立新, 等.矢量数据变化对象的快速定位与最优组合匹配方法[J].测绘学报, 2014, 43(12):1 285-1 292 http://d.old.wanfangdata.com.cn/Conference/8869641 Luo Guowei, Zhang Xinchang, Qi Lixin, et al. The Fast Positioning and Optimal Combination Method of Chang Vector Object[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(12):1 285-1 292 http://d.old.wanfangdata.com.cn/Conference/8869641 [27] Wang Y, Chen D, Zhao Z, et al. A Back-Propagation Neural Network-Based Approach for Multi-represented Feature Matching in Update Propagation[J]. Transactions in GIS, 2015, 19(6):964-993 doi: 10.1111/tgis.12138 [28] Rutzinger M, Rottensteiner F, Pfeifer N. A Comparison of Evaluation Techniques for Building Extraction from Airborne Laser Scanning[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2009, 2:11-20 doi: 10.1109/JSTARS.2009.2012488 [29] Huh Y, Kim J, Lee J, et al. Identification of Multi-scale Corresponding Object-Set Pairs Between Two Polygon Datasets with Hierarchical Co-clustering[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 88(2):60-68 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=9f564aa5eb3ccdbfbbbeef9b950c54b0 [30] 许俊奎, 武芳, 朱健东, 等.相邻比例尺居民地匹配[J].武汉大学学报·信息科学版, 2014, 39(3):340-345 http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb200806014 Xu Junkui, Wu Fang, Zhu Jiandong, et al. A Multi-to-Multi Matching Algorithm Between Neighborhood Scale Settlement Data[J]. Geomatics and Information Science of Wuhan University, 2014, 39(3):340-345 http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb200806014 [31] 张贤达.矩阵分析与应用[M].北京:清华大学出版社, 2004 Zhang Xianda. Matrix Analysis and Applications[M]. Beijing: Tsinghua University Press, 2004 [32] 杨元喜.等价权原理——参数平差模型的抗差最小二乘解[J].测绘通报, 1994(6):33-35, 29 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK199400002059 Yang Yuanxi. The Equivalent Weight Principle-Robust Least Squares Solution Estimation of Parameters Adjustment Model[J]. Bulletin of Surveying and Mapping, 1994(6):33-35, 29 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK199400002059 -
点击查看大图
图(11) / 表(1)
计量
- 文章访问数: 913
- HTML全文浏览量: 45
- PDF下载量: 211
- 被引次数: 0
