マップマッチング

こんにちは。
マップマッチングとは、地理座標点の並びを与え（図例内の 1, 2, 3）、それらの近傍で対応するグラフのエッジ（＝用意した道路地図のリンク）の繋がった並びを求めるものです（図例内の経路（＝太線））。

• したがって、「近傍探索＋経路探索」ということになります。
• なお与えた地理座標点が道路の位置から離れていること（図例の各垂線（＝点線）の長さ）を一種の誤差（およびその解消）と見なすと、誤差補正処理に相当します。

理論

この問題に対し、Paul Newson and John Krumm (2009) による定式化が近年広く用いられ¹、下記の最小化解を求めます（$N$は与点の総数、$r_i$は各垂線の長さ、$L$は経路の全長）。

\begin{align}
&\min \left(\frac{1}{2} \Sigma_{i=1}^N \left(\frac{r_i}{\sigma}\right)^2 + \frac{L}{\beta}\right)
\end{align}

これは「隠れマルコフモデル」問題と等価であり、$r_i$ の項が emission probability、$L$ の項が transition probability に相当します。解は定数$\frac{\sigma^2}{\beta}$の値に依存します。Viterbi アルゴリズムを用いて効率的に解くことができます²。

• なおマップマッチングの歴史は古く、上記の定式化以前は各種の heuristic な解法が使われていました³。

マップマッチング動作例

horizon⁴（および osm2ch、osmium-tool）を動かし、そのサーバーへ web クライアントで接続し、地理座標点（GPS #1,2,3）の並びを与えました。 日本の高速道路を対象⁵とした例です。

$ wget https://download.geofabrik.de/asia/japan-latest.osm.pbf
$ osmium tags-filter -o japan-motorway.osm.pbf japan-latest.osm.pbf w/highway=motorway,motorway_link
$ osm2ch --file japan-motorway.osm.pbf --out map.csv --geomf geojson --units m --tags motorway,motorway_link --contract=true
$ horizon -h 0.0.0.0 -p 32800 -f map.csv -sigma 50 -beta 30 -maplon 135.4 -maplat 35.2 -mapzoom 5
Extracting edges from 'map.csv' file...
Done in 9.954906378s
Loading graph and preparing engine...
Done in 91ns
 ┌───────────────────────────────────────────────────┐ 
 │                   Fiber v2.30.0                   │ 
 │              http://127.0.0.1:32800               │ 
 │      (bound on host 0.0.0.0 and port 32800)       │ 
 │ Handlers ............. 8  Processes ........... 1 │ 
 │ Prefork ....... Disabled  PID .............. 5948 │ 
 └───────────────────────────────────────────────────┘ 

参考情報

• map-matching (GitHub)
• Go で超高速な経路探索エンジンをつくる (speakerdeck.com)

1. 参考："Matching GPS traces to a map" (Mapbox Blog). ↩

2. Viterbi アルゴリズムはオフライン／オンラインに対応可能です（バッチ／リアルタイム処理）。 ↩

3. 参考：「マップマッチングのアルゴリズム」 ↩

4. horizon (GitHub) は Go で書かれています。 ↩

5. 参考：「日本の高速道路を OSM データから抽出」 ↩