mapbox の Map Maching API を使ってGPS誤差を補正しよう!


マップマッチングとは

自動車の走行データ、自転車の走行データなどのGPSデータは、プローブデータと呼ばれます。
これらは往々にして、GPSの誤差により少しずれた位置にプロットされてしまうことがあります。

それを正しく道路の上にプロットされるように修正する作業を、「マップマッチング」と呼びます。カーナビなどに使われている技術です。
イメージとしては以下のような処理を行います。


(株式会社トランスフィールドより引用)

(MapBoxより引用)

もっと詳しく知りたい方は、以下のサイトがわかりやすいです。
- 株式会社トランスフィールド>データ加工・分析>マップマッチング処理手順

マップマッチングのアルゴリズム

以下のように、様々なアルゴリズムが開発されているようです。

幾何解析(Geometric) マップマッチング

•Point to Point
•Point to Curve
•Curve to Curve
•Road Reduction Filter(RRF)

 幾何解析マップマッチング手法はリンクの道路ネットワークデータの形状のみを考慮した手法である。幾何解析手法で最も利用される手法は point to point といわれるマッチング手法である。

 この手法は測位点をネットワーク上の最も近いノードにマッチングするという簡単な手法であり、実行も容易で計算もとても速い.

位相幾何(Topological)解析 マップマッチング

•Weighted topological algorithm
•Simplified algorithm by Meng (2006)
•Algorithm based Various Similarity Criteria by Quddus et at.(2003)

 位相解析マップマッチング手法は幾何的な情報に加え、リンクの接続性、連続性をもとにマッチングを行う。このマッチングでは、連続する測位位置データが道路ネットワーク上のどのリンク上にマッピングされるかを、距離だけでなく、リンクデータと位置データの交差角度、相対角度距離などから決定する (リンク決定フェイズとする)。

 その後、速度と進行方向角度によってリンク上のどの位置にあるのかを決定する (位置決定フェイズとする)。 リンクとリンク上の位置を決定したのち、測位データが現在のリンク上にあるのか、つまり交差点に入ったかどうかを確認する (リンク確認フェイズとする)。

確率的(Probabilistic) マップマッチング

•Elliptical/rectangular confidence region

 確率的手法マップマッチング手法ではセンサーから取得された測位データ周辺に楕円や円形の信頼域を定義することが必要となる。この技術は DR センサからの位置をマッチングさせるのに初めて導入された。 また GPS センサから取得されたデータに対しても利用され、エラー領域は GPS 測位データの誤差分散から導くことが提案された。

高度な技術を利用したマップマッチング

•Kalman filter
•Dempster-Shafer’s mathematical theory of evidence •Flexible state-space model and particle filter •Interacting multiple model
•Fuzzy logic model

カルマンフィルタ、パーティクルフィルタ、DDR などより高度な概念を用いたマップマッチング手法を紹介する。
カルマンフィルタとはシステムや観測値に様々なランダムなノイズがのっているときにそれぞれのノイズの大きさに応じて適切な重みづけを行い、変化していくシステムの状態を精度よく推定するための手法である。

(BinN studies シリーズネットワーク行動学 -都市と移動- からの引用)

もっと詳しく知りたい方は、以下のサイトがわかりやすいです。
- マップマッチングのアルゴリズム

BinN studies シリーズ  『ネットワーク行動学 -都市と移動-』

マップマッチングについては → p.84 - p.106
http://bin.t.u-tokyo.ac.jp/kaken/data/full-20140926.pdf

マップマッチングのサンプルプログラム

Java で書かれたマップマッチングのサンプルも用意されています。
http://bin.t.u-tokyo.ac.jp/kaken/

ちなみにこれらはBinN Studies Unit (BinN:Behavior in Networks)は,2006年東京大学に羽藤英二教授が赴任したことを契機に14号館で発足した都市生活学研究室を母体とする研究グループによって公開されている資料です。

mapbox の Map Matching API を使ってみる!

今回は、mapboxという地図サービスのAPIを利用してマップマッチングを行います。
日本ではソフトバンクのビジョンファンドが投資したことでも話題になりました。

公式Webサイト
Mapbox : Python SDK Map Matching

Map Matching API Tutorial

HELP : Map Matching API

GITHUB
PythonでのMapmaching APIについての説明

取得できるデータの種類

クルマ🚗、歩き、自転車🚲、渋滞情報を考慮したクルマ🚗 
と四種類の中から選択できます!(めっちゃ便利)

Profile ID Description
mapbox/driving Car travel times, distances, or both.
mapbox/walking Pedestrian and hiking travel times, distances, or both
mapbox/cycling Bicycle travel times, distances, or both
mapbox/driving-traffic Car travel times, distances, or both as informed by traffic data

受け取るデータ形式

受け取るデータ形式は、
json か geojson を選べます。

ライブラリのインストール

準備としてpip を使って、mapboxのライブラリをインストールします。

pip3 install mapbox

sampleコードを実行してみよう。

sampleデータでは、
2015年4月21日6時00分00秒〜20秒までの5秒ごとの緯度経度のデータが入っています。

makeData.py

#インポート
from mapbox import MapMatcher

service = MapMatcher(access_token="pk.YOUR_ACCESS_TOKEN")

#プローブデータ(GPSデータ)
line = {
         "type": "Feature",
        "properties": {
            "coordTimes": [
                "2015-04-21T06:00:00Z",
                "2015-04-21T06:00:05Z",
                "2015-04-21T06:00:10Z",
                "2015-04-21T06:00:15Z",
                "2015-04-21T06:00:20Z"]},
        "geometry": {
            "type": "LineString",
            "coordinates": [
                [13.418946862220764, 52.50055852688439],
                [13.419011235237122, 52.50113000479732],
                [13.419756889343262, 52.50171780290061],
                [13.419885635375975, 52.50237416816131],
                [13.420631289482117, 52.50294888790448]]}}

# mapmatchingを実行
response = service.match(line, profile='mapbox.driving')
response.status_code
response.headers['Content-Type']

# mapmatchingにより緯度経度を修正したデータ
corrected = response.geojson()['features'][0]
corrected['geometry']['type']
corrected['geometry'] == line['geometry']
len(corrected['geometry']) == len(line['geometry'])

結果の読み方

うまく実行されてそうであれば、
プログラムの最後に
print(corrected)
として、道路にマッチングしているのか確認してみましょう。

{
    "type": "Feature",
    "geometry": {
        "coordinates": [
            [
                13.418802,
                52.500598
            ],
            [
                13.418839,
                52.500649
            ],
            [
                13.418848,
                52.500661
            ],
            [
                13.419122,
                52.501057
            ],
            [
                13.419148,
                52.501096
            ],
            [
                13.419199,
                52.501172
            ],
            [
                13.41921,
                52.501189
            ],
            [
                13.419277,
                52.501287
            ],
            [
                13.419344,
                52.501378
            ],
            [
                13.419365,
                52.501407
            ],
            [
                13.419447,
                52.501519
            ],
            [
                13.41962,
                52.501755
            ],
            [
                13.419982,
                52.502249
            ],
            [
                13.420041,
                52.502334
            ],
            [
                13.420494,
                52.502984
            ]
        ],
        "type": "LineString"
    },
    "properties": {
        "confidence": 0.8208120214518423,
        "distance": 289,
        "duration": 80,
        "matchedPoints": [
            [
                13.418802,
                52.500598
            ],
            [
                13.419148,
                52.501096
            ],
            [
                13.41962,
                52.501755
            ],
            [
                13.420041,
                52.502334
            ],
            [
                13.420494,
                52.502984
            ]
        ],
        "indices": [
            0,
            1,
            2,
            3,
            4
        ]
    }
}

5ヶ所の緯度経度を入力として与えると、
15ヶ所の緯度経度の情報が返ってきました。

Mapboxの地図が持っている道路ネットワークの緯度経度が返ってきたことを示しています。

その中でも、入力の5つの点がどの道路上の点とマッチングしたかは "matchedPoints"の5つの点が表しています。

また、マッチングの信頼性も
"confidence": 0.8208120214518423  と、表示してくれています。

もっと詳しく

mapbox.MapMatcherのより詳しい説明は、
以下のコマンドで確認できます。

import mapbox; help(mapbox.MapMatcher)


 |  Methods inherited from mapbox.services.base.Service:
 |  
 |  __init__(self, access_token=None, host=None, cache=None)
 |      Constructs a Service object
 |      
 |      This method should be overridden by subclasses.
 |      
 |      Parameters
 |      ----------
 |      access_token : str
 |          Mapbox access token string.
 |      host : str, optional
 |          Mapbox API host (advanced usage only).
 |      cache : CacheControl cache instance (Dict or FileCache), optional
 |          Optional caching, not generally needed.
 |      
 |      Returns
 |      -------
 |      Service
 |  
                 -- 以下省略 --

まとめ

マップマッチングのAPIがあることをこれまで知りませんでした。
とても便利なツールですよね。

ぜひぜひ手を動かしてAPIを使ってみてください