基于权重的地图匹配技术

大家好，欢迎来到IT知识分享网。

前言

随着生活质量的日益提高，地图相关技术已经渗透到人们生活的各个角落，本文对地图匹配技术，进行简单的概述和实现，为没接触过地图开放的朋友，又想要了解相关技术的提供一个参考信息，内容有误之处，还请大神指点。

一、地图匹配概述

由于GPS技术特性原因，定位结果受客观存在的环境因素影响，我们拿到的原始轨迹数据并不是我们在轨迹结果上看到的那么整洁、规范和有序，如果直接把这些点打到地图上，那么我们的行动轨迹，可能看起来就是这样：

所以信号也有颗不安分的心，这份轨迹数据让人看起来很灰心，因为勺子里面装了一些不该有的东西。那么我们需要通过一系列的技术手段，来保留我们想要的、看起来合理的轨迹，去掉看起来不合理的数据。

这一系列的技术手段，包括降噪、分段、抽稀、路网匹配、轨迹补偿等，如下图

降噪：降噪技术在数据处理方面应用得非常广泛，例如BI、机器学习等领域，数据几乎都需要进行噪点处理，降噪后的数据通常会存在多多少少的失真，这个缺陷可以通过后期的路网匹配来进行修正；

抽稀：浮点运算是个比较消耗CPU性能的计算，我们通常需要对原始数据进行抽稀处理，将原始数据精简为足以还原轨迹的数量即可；

路网匹配：由于信号偏移、降噪处理等因素，导致有些轨迹点是不在道路网上的，当我们把这些点打到地图上以后，会发现我们可能行走在山顶、湖泊、大海，显然这并不合理，所以我们需要结合路网数据，将轨迹拟合到道路网。

二、轨迹预处理

1.降噪

剔除数据中的冗余点和噪音点，通常使用，噪音滤波技术，主要算法包括中值滤波、均值滤波、卡尔曼滤波等；

轨迹压缩技术，通常使用道格拉斯压缩算法；

轨迹分段技术，通常使用网格划分算法，以及角度、密度、速度相似度匹配算法

后续小节将对各个处理节点算法进行一一详解。

1.1 中值滤波

当时由于项目时间原因，中值滤波算法是本次主要降噪算法，该算法在当前版本中，实现成本、学习成本、处理效果是最优选择。

算法原理

1、对坐标点Pi，获取前后n（n为大于2的偶数）个节点的集合R；
2、将R的经度、纬度，分别进行正序排序；
3、分别取经度和纬度的中间值，作为该节点的最终经度和纬度；

图例：

关键代码：

/ 起始索引，前面range个坐标不处理 int startIndex = STEP_SIZE / 2 + 1; // 结束索引，后range个坐标不处理         int endIndex = tracks.size() - STEP_SIZE / 2;         // STEP_SIZE每次处理的坐标个数，除以二即为前后处理的范围         int range = STEP_SIZE / 2;         for (int i = startIndex; i < endIndex; i++) {             UserTrackDTO track = tracks.get(i);             List<Double> lngs = new ArrayList<>();             List<Double> lats = new ArrayList<>();             // 获取预定范围间的所有经度和纬度             for (int j = i - range; j <= i + range; j++) {                 lngs.add(tracks.get(j).getLngDouble());                 lats.add(tracks.get(j).getLatDouble());             }             // 排序             Collections.sort(lngs);             Collections.sort(lats);             // 取中间             track.setLng(String.valueOf(lngs.get(3)));             track.setLat(String.valueOf(lats.get(3)));     }

中值滤波的缺点：对于连续多个噪点的数据处理得并不理想，增加步长会增加时间复杂度和严重失真，后续会考虑引入卡尔曼滤波算法看看效果；

1.2 极值滤波

算法原理
1、计算各个坐标点距离上一个点的距离、速度；
2、按比例移除距离、速度较大的点；
关键代码：

 tracks.get(0).setDistance(0);         for (int i = 1; i < tracks.size(); i++) {             UserTrackDTO lastTrack = tracks.get(i - 1);             UserTrackDTO track = tracks.get(i);             Double distance = DistanceHepler.distance(track, lastTrack);             track.setDistance(distance.intValue());         }         Double maxSize = tracks.size() * 0.80D;         tracks = tracks.stream()                 .sorted(Comparator.comparing(UserTrackDTO::getDistance))                 .collect(Collectors.toList());         tracks = tracks.stream()                 .limit(maxSize.intValue())                 .collect(Collectors.toList());         tracks = tracks.stream()                 .sorted(Comparator.comparing(UserTrackDTO::getIndex))                 .collect(Collectors.toList());

算法原理
（1）在曲线首尾两点A，B之间连接一条直线AB，该直线为曲线的弦；
（2）得到曲线上离该直线段距离最大的点C，计算其与AB的距离d；
（3）比较该距离与预先给定的阈值threshold的大小，如果小于threshold，则该直线段作为曲线的近似，该段曲线处理完毕。
（4）如果距离大于阈值，则用C将曲线分为两段AC和BC，并分别对两段曲线进行1~3的处理。
（5）当所有曲线都处理完毕时，依次连接各个分割点形成的折线，即可以作为曲线的近似。
图例：

关键代码：