基于方向相似性的面状矢量数据匹配算法与策略研究

基于方向相似性的面状矢量数据匹配算法与策略研究基于方向相似性的面状矢量数据匹配算法与策略研究 摘要 数据一致性匹配处理技术是空间数据融合中的关键技术 本文采用方向关系矩阵模型进行空数据一致性匹配处理技术是空间数据融合中的关键技术 本文采用方向关系矩阵模型进行空 间方向关系描述 讨论了空间方向相似性计算方法 提出了复杂情况下的匹配策略 最后 以面状目标为间方向关系描述 讨论了空间方向相似性计算方法 提出了复杂情况下的匹配策略 最后 以面状目标为 研究对象 以研究对象 以 1 1 500500 城市规划与房产数据城市规划与房产数据为例 对基于空间方向相似性的矢量数据匹配算法进行了试验为例 对基于空间方向相似性的矢量数据匹配算法进行了试验 与分析与分析 关键词 关键词 数据匹配 数据融合 空间方向关系 空间方向相似性 现实世界中的同一现象往往具有不同的表达形式 数据匹配就是显式地建立这些不同 形式之间的对应关系 数据一致性匹配处理技术是空间数据集成与同化中的关键技术 由 于矢量空间数据语义信息丰富 拓扑关系复杂以及匹配时还要考虑几何形状和位置差异 矢量空间数据自动匹配技术一直是相关研究的难点与热点 矢量空间数据匹配的途径主要包括几何匹配 拓扑匹配和语义匹配 矢量空间数据几 何匹配的基础是空间相似性 本文以空间方向相似度计算为基础 结合双向匹配策略来进 行面状矢量空间数据匹配研究 1 1 空间方向概念描述空间方向概念描述 空间方向存在于地理空间的两个目标之间 是在一定的方向参考系统中从一个空间目 标到另一个空间目标的指向 通常用角度 定量 或东 南 西 北等 定性 术语表示 空间方向关系描述模型可以从定量和定性两个方面进行 就定量方向模型而言 它主要是 运用方向角数据精确地给出目标间的方向关系值 定性方向模型有包括方向关系矩阵模型 在内的 8 种模型 1 3 1 3 我们采用方向关系矩阵模型进行空间方向关系描述 因为该模型对 凹形对象能提供更好的空间方向评估 1 1 空间方向关系描述 空间方向关系描述 关系矩阵模型运用投影法 将目标对象所在的空间分成 9 个独立的方向片 图 1 外 面的 8 个方向片表示了 8 个方向 中心方向片为 O 2 2 空间方向关系矩阵 空间方向关系矩阵 按参考对象进行空间方向分区 A 为参考对象 一个 3 3 方向关系矩阵可表示为 3 3 空间方向距离 空间方向距离 图 2 方向关系矩阵 图 1 参考对象空间方向分区 空间方向距离 7 是空间方向之间的差别 反之就是空间方向相似性 当目标对象方向 改变时 如果在同一个方向片中变换 定义方向距离为 0 如果在 NE 和 SW 方向片之间以 及 NW 和 SE 方向片之间变换 定义方向距离为 4 且为最大方向距离 4 4 空间方向相似性值 空间方向相似性值 两个方向的空间方向相似性值可以定义为 7 1 式中 取 4 图 3 d 指矩阵转换到的最小代价 方向距离 max D 10 DD 0 0 D 1 D 2 2 空间方向相似性计算空间方向相似性计算 采用栅格数据形式 可以有效化简空间方向相似性计算方法 以面状目标为例 一个 面状目标相对于参考面状目标的方向关系矩阵可以转换为该面状目标的所有栅格单元的方 向关系矩阵的集合 1 1 理想情况下的空间方向相似性计算 理想情况下的空间方向相似性计算 将每个栅格单元移动的方向距离累加后除以目标对象的栅格单元总数即得该对象的平 均方向距离 面状目标空间方向相似性值计算公式如下 3 2 n i ipr d n IIS 1 4 1 1 式中 为参考图 为与参考图相比较的图 n为匹配对象中的栅格单元数 为 r I p I i d 每个栅格移动的方向距离 为两幅图相比较的相似值 pr IIS 2 2 不同形状空间目标方向相似性计算不同形状空间目标方向相似性计算 两种不同的数据集 即使是同一目标 其形状也不可能完全相似 因此 前述算法只 是理想情况下的计算方法 对于不同数据集中形状不同的目标的相似性计算 可按下述思 路进行 max 10 10 0 1 D DDd DDSi 图 3 方向片的 4 个邻近方向距离图 B B AA a b 如图 5 以 A 为参照目标 以图 5 a 中的 B 对象栅格数为基准 计算图 5 a 到图 5 b 的空间方向相似性值 计算原则为 与图 5 b 中 B 对象相对照 图 5 a 中 B 对象没有而图 5 b 中 B 对象有的栅 格 移动距离按 0 计算 图 5 a 中 B 对象有而图 5 b 中 B 对象没有的栅格 移动距离按 4 计算 其它情况的移动距离 仍然参照区域的 4 个邻近方向距离图来计算 以图 5 为例 计算过程如下 图 5 a 中 B 对象的栅格数为 16 图 5 b 中对象 B 的栅格单元相对于图 5 a 在 方向片上由 NE 移动到 N 的有 5 个栅格单元 其空间方向相似性值为 1baSim 反过来 以 A 为参照目标 以图 5 b 中的 B 对象栅格数为基准 计算图 5 b 到图 5 a 的空间方向相似性值 图 5 b 中 B 对象的栅格数为 30 图 5 a 中对象 B 的栅格单 元相对于图 5 b 在方向片上由 N 移动到 NE 的有 5 个栅格单元 图 5 b 中 B 对象有 13 个栅格单元在图 5 a 中对象 B 中没有 移动距离记为 4 图 5 b 到图 5 a 的空间方向 相似性值为 2baSim 设定阈值 k 如果与的相似性值都大于 k 则一对一匹配 利 1baSim 2baSim 用同样方法也可对线状目标相似性进行计算 3 3 复杂情况匹配策略 复杂情况匹配策略 上述方法实现了一对一的匹配 对于多对一 多对多的匹配 可采用合适的匹配策略 基本思路如下 现有两幅不同来源存在一定差异的数据集 数据集 A 的面实体集为 数据集 B 的面实体集为 两幅图的实体个数 mi aaaa 21 nj bbbb 21 可能并不相等 即 m 可能不等于 n 实体匹配的目的就是要确定其中一幅图的实体在另一 幅图中对应的同名实体 一对一匹配 对实体 计算 如果 ji ba mi 2 1 nj 2 1 ji baSim ij abSim 两者都大于 K K 为阈值 则说明实体在数据集 ji baSim ij abSim10 k i a B 中的候选匹配实体为 同时实体在数据集 A 中的候选匹配实体为 因此 j b j b i a 为匹配所得同名实体 且的匹配关系是一对一的 如图 6 a ji ba ji ba 92 0 51 164 1 1 1 baSim B 图 5 不同形状目标空间方向相似性计算 525 0 13451 304 1 1 2 baSim 多对一匹配 对实体 且 计算 jti baa mi 2 1 mt 2 1 nj 2 1 ti 如果 两者都大于 K K 为阈值 ji baSim jt baSim ji baSim jt baSim 则说明实体 在数据集 B 中的候选匹配实体为 因此 实体集 10 k i a t a j b ti aa 与实体存在多对一的匹配关系 如图 6 b j b 多对多匹配 对实体 且 rkjti bbbaami 2 1 mt 2 1 ti nj 2 1 且 如果 nk 2 1 nr 2 1 rkj ji baSim ki baSim 都大于 K K 为阈值 则说明和匹配 和 kt baSim rt baSim10 k i a kj bb t a 匹配 因此 实体集和实体集匹配 匹配关系是多对多的 如图 rk bb ti aa rkj bbb 6 c 3 3 基于空间方向相似性的数据匹配流程描述基于空间方向相似性的数据匹配流程描述 我们可以利用上述的空间方向相似性计算方法进行数据匹配 流程描述如下 1 矢量数据栅格化 由于上述相似性算法采用的是栅格数据结构 因此须将两种数据源都转换为栅格数据 2 参考目标的确定 在一定的区域内 选择合适的目标作为参考目标 3 空间方向相似性计算 根据参考目标 采用上述算法 求出其一定位置范围内周围目标的相似性值 图 6 数据匹配策略示意图 a b c 4 数据匹配域值的确定 根据经验 确定合适的相似性值域范围 如果目标的相似性值在相似性值域范围内 则初步确定为待选匹配目标 5 匹配策略 采用合适的匹配策略 完成一对一 多对一 多对多的匹配 5 语义匹配的辅助 如果待选匹配目标不止一对 在待选匹配目标范围 结合语义信息确定待匹配的同名 目标 4 4 试验结果分析试验结果分析 为了验证算法的匹配正确率 以 1 500 城市规划与房产数据的面状对象为例 如图 7 所示 将阈值分别设定为 0 6 0 7 0 8 0 9 并统计正确匹配的对数 得到表 1 由 表 1 可以看出 在阈值较大的时候 比如 0 8 一对一的匹配准确率较高 而阈值较小的 时候 比如 0 3 则多对一 多对多的匹配准确率得到提高 如表 5 2 所示 但这时会有 较多的一对一误匹配 图 7 房产数据 规划数据 表 1 一对一匹配正确率 阈值待匹配数正确匹配数正确率 0 6723853 0 7725881 0 8726185 0 9725171 表 2 多对一