最好用的地图匹配框架——基于HMM的Valhalla

地图匹配

就是将点映射到路段上的技术啦，懂得都懂哈~
因为本人是做城市计算移动轨迹方面的研究，所以经常要对一些车辆轨迹进行地图匹配，但是由于懒得自己实现地图匹配算法啦，【比较经典且有效的方法就是我们大名鼎鼎的HMM啦！详细可见：《hidden-markov-map-matching-noise-sparseness》】
今天就是来介绍一个宝藏框架，基于C++实现的Valhalla，有专门的API可以调用，方便各个小白使用啦！！

参考链接

先搬上一些参考链接：

先展示效果

作者检查过很多，效果真的很好！
效果图

环境说明

因为框架的使用方式是服务器处理请求返回结果的方式，所以要用到以下的环境：

服务器：VMware + ubuntu 16.04 （配置的时候记得虚拟硬盘搞大一点，要不然后面再扩容感觉比较麻烦，我是虚拟机小白~）

使用教程

1. 下载完虚拟机以后的一些准备

记得换源！！如果不知道换源是什么的话，自行搜下“ubuntu16.04换源”，换源是为了让你更快地下载东西哈~推荐清华源哈！

换源以后记得先执行
sudo apt-get update
sudo apt-get upgrade

记得给github配置代理，自行搜下“github配置代理”

2. 安装

1. 安装vallhala，如失败请参考网页：https://github.com/valhalla/valhalla

# 打开终端输入以下命令
sudo add-apt-repository -y ppa:valhalla-core/valhalla
sudo apt-get update
sudo apt-get install -y valhalla-bin

2. 测试测试valhalla是否下载成功，如失败请参考网页（可能需要v屁恩）：https://gis-ops.com/valhalla-part-2-how-to-run-valhalla-on-ubuntu/

# 打开终端输入以下命令
valhalla_build_config
valhalla_build_admins
valhalla_build_tiles -h
valhalla_service

valhalla_build_config 会返回一连串 JSON。
valhalla_build_admins 会返回“Unable to parse command line options because: the option ‘–config’ is - required but missing”。
valhalla_build_tiles -h 会返回一连串“ valhalla_build_tiles 3.0.9 and a few more lines explaining the tool.”（版本可能不同，用于地图匹配的话无影响）
valhalla_service 会返回 “… [ERROR] Usage: valhalla_service config/file.json [concurrency].”
如果上述输出都一样，那么说明安装成功了

3. 安装一些依赖

# 打开终端输入以下命令
sudo apt-get update
sudo apt-get install -y curl jq unzip spatialite-bin

4. 下载脚本文件且设置工作目录

# 打开终端输入以下命令
git clone https://github.com/valhalla/valhalla.git ~/valhalla/
# 如果这个仓库没了就换成https://github.com/kingsleyljc/valhalla.git
cd ~/valhalla/scripts/
mkdir valhalla_tiles && mkdir conf

5. 下载osm地图

# 打开终端输入以下命令，下面以下载albania地图为例
# 其它地图可以去https://download.geofabrik.de找
curl -O https://download.geofabrik.de/europe/albania-latest.osm.pbf

如果想自定义地图，即选定范围的地图，请选择进入osm网页自行选择：https://www.openstreetmap.org/export
由于从官网下载的地图文件格式是osm的，Valhalla框架所需要的地图格式是pbf的，所以需要将osm转为pbf。步骤见地图文件.osm格式与.pbf格式相互转换
将转换好的pbf文件移动到~/valhalla/scripts/目录下即可。

6. 准备配置文件

# 在~/valhalla/scripts/目录下
valhalla_build_config --mjolnir-tile-dir ${PWD}/valhalla_tiles --mjolnir-tile-extract ${PWD}/valhalla_tiles.tar --mjolnir-timezone ${PWD}/valhalla_tiles/timezones.sqlite --mjolnir-admin ${PWD}/valhalla_tiles/admins.sqlite > ${PWD}/conf/valhalla.json

7. 建立管理区域

要用到上面下载的地图albania-latest.osm.pbf啦！

# 在~/valhalla/scripts/目录下
valhalla_build_admins --config ./conf/valhalla.json albania-latest.osm.pbf（这里可以换成你自己的地图）

8.构建路由块

cd ~/valhalla/scripts/
valhalla_build_tiles -c ./conf/valhalla.json albania-latest.osm.pbf（这里可以换成你自己的地图）
find valhalla_tiles | sort -n | tar -cf "valhalla_tiles.tar" --no-recursion -T -

9.开始跑

valhalla_service ~/valhalla/scripts/conf/valhalla.json 2

10.测试是否运行成功

# 新开一个终端测试一下
curl http://localhost:8002/route \
--data '{"locations":[
              {"lat":41.318818,"lon":19.461336},
              {"lat":41.321001,"lon":19.459598}
           ],
         "costing":"auto"
        }' | jq '.'

开始地图匹配

1. 获得虚拟机的ip地址

在这里插入图片描述

2. 请求

请求方式：POST
即：http://192.168.111.134:8002/trace_attributes（记得换成你自己的ip）
主体如下：

{
  "shape": [
    {
      "lat": 22.752249,
      "lon": 113.82164,
      "type": "via"
    },
    {
      "lat": 22.751839,
      "lon": 113.823448,
      "type": "via"
    },
    {
      "lat": 22.751617,
      "lon": 113.823814,
      "type": "via"
    },
    {
      "lat": 22.751587,
      "lon": 113.823929,
      "type": "via"
    }
  ],
  "costing": "auto",
  "search_radius": 150,
  "format": "osrm"
}