海量数据下的点位匹配技术研究与应用

章力博，吉建培，韩文立，葛 娟，徐爱峰，张晓磊

(1. 国家测绘产品质量检验测试中心，北京 100830； 2. 天津测绘院，天津 300381；3. 北京天下图数据技术有限公司，北京 100089)



海量数据下的点位匹配技术研究与应用

章力博1，吉建培1，韩文立1，葛 娟1，徐爱峰2，张晓磊3

(1. 国家测绘产品质量检验测试中心，北京 100830； 2. 天津测绘院，天津 300381；3. 北京天下图数据技术有限公司，北京 100089)

以海量数据为研究背景，以点位匹配作为切入口，在GeoHash技术基础上，对该技术进行多重改进，从全新的视角提出了新的算法，将该算法运用到点重复检查中，提出了新的算法策略，并与ArcMap相关功能及传统方法进行比对，给出了不同数量级下的运行效率比对。

点位匹配；GeoHash；GeoHash+；点重叠

随着国民经济的发展，地理信息容纳的范围越来越广，而空间实体对象的粒度越来越细，因此，带来的数据存储大小呈现出成倍的增加趋势，对传统几何算法框架下的数据处理和数据检查提出了新的挑战。

点位匹配即在建立空间索引的基础上，计算点与点的最短距离，并将某点最近的点作为匹配点。该技术作为空间数据几何算法中的基础算法，在很多数据处理和数据检查中起着重要的作用，对于数据生产和质量检查而言，这项技术的效率提升有着重要的意义。随着空间数据量的激增，现有几何算法框架虽然能够完成空间运算，但是执行效率时效性却有待提高。

本文将从全新的视角给出点位匹配的新算法，提出高效率的算法策略，并将该成果运用到数据生产和质量检查的流程中。

一、传统技术

在已有的几何算法框架内，点位匹配的核心是在构建空间索引的基础上通过查询空间索引，计算P1点(x1，y1)与P2点(x2，y2)之间的距离d，公式如下，当d满足要求(di≤Tol，Tol表示限差，并且di=min(d1,d2,…,di,…,dn))，即点位匹配成功。

具体流程如图1所示。

图1 传统点位匹配技术

二、新技术

1. GeoHash技术

(1) 主要思想

GeoHash技术的主要思想就是将二维的点数据转换为一维的数据，对一维的数据进行排序，再通过类似二分查找的方式，实现点位的快速查找。

(2) 主要特点

1) 二维的经纬度转为字符串，如图2展示了某市9个区域的GeoHash字符串，分别为WX4ER、WX4G2、WX4G3等，每一个字符串代表了某一矩形区域。即这个矩形区域内所有的点(经纬度坐标)都共享相同的GeoHash字符串，这样既可以保护隐私(只表示大概区域位置而不是具体的点)，又比较容易做缓存。

2) 字符串越长，表示的范围越精确，精度表见表1。

3) 字符串相似的表示距离相近，这样可以利用字符串的前缀匹配来查询相邻点的信息。

表1 GeoHash精度表

图2 GeoHash图例

(3) 实现方式

该技术的具体实现方式是将二维点坐标转换为字符串，使得位置越接近的点，字符串近似程度越高，将点与点的远近程度转换为字符串的近似程度。相比于传统解决思路，新的方法略去了构建空间索引，查询空间索引的时间，提高了距离计算的精准度。

① 计算二进制编码

在经度或纬度方向上，在满足精度的要求下，不断利用二分法对点的经度及纬度进行逼近，生成二进制编码。比如：地球纬度区间是[-90,90]，某地的纬度为39.928 167，可以通过下面算法对其进行逼近编码：

a. 区间[-90,90]进行二分为[-90,0),[0,90]，称为左右区间，可以确定39.928 167属于右区间[0,90]，给标记为1；

b. 接着将区间[0,90]进行二分为 [0,45),[45,90]，可以确定39.928 167属于左区间 [0,45)，

给标记为0；

c. 递归上述过程39.928 167总是属于某个区间[a,b]。随着每次迭代区间[a,b]总在缩小，并越来越逼近39.928 167；

d. 如果给定的纬度x(39.928 167)属于左区间，则记录0，如果属于右区间则记录1，这样随着算法的进行会产生一个编码10111 00011，序列的长度跟给定的区间划分次数有关。

编码计算过程见表2。

表2 编码计算过程

同理，地球经度区间为[-180,180]，可以对经度116.389 550进行编码，得到编码11010 01011。

② 组 码

将上述2个编码进行错位，生成一个新的编码，将新编码转换为十进制，最后利用Base32编码转换为字符串，生产GeoHash编码。具体步骤见表3。

表3 组码过程

(4) 缺 陷

GeoHash技术是为了解决搜索附近POI信息的问题。如果要适应传统测绘，需要克服以下缺陷：

1)不适应任意坐标。GeoHash技术只适用于大地坐标；而传统测绘采用的坐标系既有大地坐标，也有平面坐标。

2)点匹配不精确。GeoHash的实质是不断利用二分法对封闭二维空间进行分割，将空间分割成小的矩形，但未考虑初始状态下封闭二维空间的形态，若初始状态为狭长二维空间时，则会出现分割的区域过于狭长(如图3(a))，造成虽然GeoHash编码一致，但是实际点位距离偏差很大的结果(如图3(b)的A、B点)，从而带来大量的冗余计算。

图3 点匹配不精准

3) 点位逼近，编码相似度不一定高。GeoHash编码的特性之一为编码从高位到低位，近似程度越高，点位的逼近程度越高；反之，不一定成立，即点位越逼近，GeoHash编码的近似程度不一定越高。例如，P1点坐标为(75.123 456 789 1，45.000 000 000 1)，P2点坐标为(75.123 456 789 1，44.999 999 999 9)，两点非常逼近，但是P1点的编码为“v8j2j2p0p2j2”，P2点的编码为“txvrvrzpzrvr”，两点的GeoHash编码相差太大。

2. GeoHash+技术

(1) 主要思想

GeoHash+技术的主要思想为克服GeoHash的不足，使之能够适应各类测绘地理信息产品的点位匹配技术。

(2) 主要特点

1) 坐标类型的扩展。GeoHash技术目前只适应于大地坐标，不能完全满足测绘的要求，GeoHash+技术不仅适应于大地坐标，也可以适用于平面坐标。

2) 精确的点匹配。在计算GeoHash值之前，需要对初始状态下的封闭二维空间进行规整化处理。为了保证分割的矩形尽量是正方形，依据表1，做出如下优化方法：若GeoHash值的位数是奇数，将初始状态下封闭长宽比控制在2附近；若GeoHash值的位数是偶数，则长宽比控制在1附近。

3) 点注册机制。造成“点位逼近，编码相似度不一定高”的原因在于空间对象的连续性与GeoHash逻辑分割之间的矛盾，分割矩形框的边缘区域特别容易出现这种情况。如图4(a)，A区域与B区域必存在无限接近的点对，但是A、B区域分割轨迹相差太大，因此两个区域的GeoHash编码相差也比较大。

图4 点注册机制

为了解决这个问题，引入点注册机制，形成分割矩形框与点的映射关系 ，即点所在矩形框及相邻矩形框与点的映射关系，1个点除了在所在矩形框内注册，还需要在临近的8个矩形框内进行注册，这样就避免了点位逼近而GeoHash编码近似度不高的问题。

4)更加高效的GeoHash编码比对技术。依据GeoHash编码的特殊性，编码比对从低位开始，逐字符比较，从而避免冗余计算，提高了计算效率。

(3) 精 度

以1∶10 000的图幅号“G49G001083”为例，X方向跨度在6181 m左右，Y方向跨度在4660 m左右。

若GeoHash值的位数为奇数，扩大X方向跨度至9320 m(长宽比为2)，则精度见表4。

表4 GeoHash+精度表1

若GeoHash值的位数为偶数，扩大Y方向跨度至6181 m(长宽比为1)，则精度见表5。

表5 GeoHash+精度表2

三、技术应用

本文以点重叠检查为例，试验采用4个数量级，分别为1万、10万、20万、50万，数据中的每个对象均有一个匹配点，分别采用ArcMap中的GP工具、传统方法和GeoHash+技术3种技术路线。

试验机器配置：处理器为i7，2.5 GHz；内存为4.0 GB；系统类型为Windows7 64位。

1) 利用ArcMap的Point Distance工具运行，效果见表6。

表6 ArcMap工具运行效果 s

2) 传统方法试验流程：首先为4个数据构建空间索引(R树索引)，然后通过空间索引，搜索出疑似匹配点集，再进行距离计算，最后得到匹配点，流程如图5所示。

图5 传统方法试验流程

应用效果见表7。

表7 传统方法运行效果 s

3) GeoHash+技术试验流程：首先将点坐标转换为GeoHash编码，依据GeoHash编码，进行点注册归类，依据注册归类结果，计算距离，最后得到匹配点，流程图如图6所示。

图6 GeoHash+技术试验流程

应用效果见表8。

表8 GeoHash+技术运行效果 s

四、结束语

算法是质检软件的核心，算法的好坏直接影响软件的运行效率和效果。本算法基于GeoHash技术，针对测绘产品质量检查进行了多重改良，将其运用到点重复检查中并进行了效率比对。该算法的运用对于质量检查和拓扑关系构建都有很大的帮助。未来的工作将集中在3个方面：①对百万级、千万级海量数据的支持；②继续研究GeoHash+技术，持续深入改进GeoHash+技术；③与生产结合，期望在伪节点检查、道路连通检查、接边检查、点线拓扑构建、线线拓扑构建等方面取得突破。

[1] 严剑锋，邓喀中.基于特征点提取和匹配的点云配准算法[J].测绘通报,2013(9)：62-65.

[2] 付仲良，刘思远，田宗舜，等.基于多级R-tree的分布式空间索引及其查询验证方法研究[J].测绘通报，2012(11)：42-46.

[3] 郑应新，岳建平，甄宗坤.公共点自动匹配算法研究[J].测绘通报,2013(5)：74-76.

[4] 杨铭，陈建峰.基于CUDA的海量点云数据kNN查询算法[J].测绘通报,2012(S1)：394-398.

[5] 刘润涛.基于序的空间数据索引及查询算法研究[D].哈尔滨：哈尔滨理工大学,2009.

Research and Application of Point Matching Technology Based on Mass Data

ZHANG Libo，JI Jianpei，HAN Wenli，GE Juan，XU Aifeng，ZHANG Xiaolei

2016-06-05；

2016-09-27

公益性行业科研专项(201512018)

章力博(1984—)，男，硕士，高级工程师，研究方向为测绘地理信息产品质量检验与测试。E-mail：zhanglb@sbsm.gov.cn

章力博，吉建培，韩文立，等.海量数据下的点位匹配技术研究与应用[J].测绘通报，2016(11)：122-125.

10.13474/j.cnki.11-2246.2016.0381.

P208

B

0494-0911(2016)11-0122-04