NTTドコモR&Dの技術ブログです。

トップ > データ分析 > HMMマップマッチングとオープンソースツールの活用

HMMマップマッチングとオープンソースツールの活用

データ分析 アドベントカレンダー2025

クロステック開発部で位置情報を活用したサービス開発をしている小倉です。 スマートフォンを始めとするモバイル端末を多くの人が持ち歩くようになった現代において、その端末から取得される位置情報データはますます重要な価値を持っています。 しかし、位置情報データはGPSやWiFi、あるいは携帯基地局情報をもとにしているため、位置の精度が十分ではありません。 数十メートルずれることはよくあり、100メートル以上ずれることもあります。 また、位置情報の取得頻度も限られています。 そのため、計測していない間に大きく移動してしまい、ある場所を訪れたことを見落とす可能性もあります。

そこで、連続的なGPSデータから、どの経路を通過したかを推定する技術であるマップマッチングが研究されてきました。 本稿ではマップマッチングの仕組みの解説し、次にOSSで実装されたツールでマップマッチングを試してみます。

隠れマルコフモデルによるマップマッチング

手法として最も単純なものは、GPS計測点の最も近くの道路上の点を通過したと推定し、その点と、次の推定された点を最短距離で結ぶことです。 しかしこの手法では、交差点付近で複数のUターンを推定してしまいます。 実際はこのようなUターンはしておらず、あくまでGPSの誤差によって付近の道路上に観測されてしまっただけです。 [^AdrianWöltche]

このような問題を解決するため、多くの手法が提案されていますが、現在広く活用されているのが、2009年に発表された隠れマルコフモデル(HMM)による手法です[^NewsonKrumm]。 この手法の発表以降、多くの論文がこの手法を参考にしています。

手法を簡単に説明すると、GPS計測点の付近の道路上の点（候補点）を見つけて、候補点をどうつなげると最も可能性が高いかをビタビアルゴリズムで求め、可能性が最も高い候補点を繋げた経路が、マップマッチングで推定された経路となります。

Valhallaのドキュメントが詳しいので、図を引用しながら説明します。

[^Valhalla]

緑色の点を始点として、その経路を青色の線で示しています。 緑色の点の付近には、2つの道路と、その道路同士が交わる、1つの交差点があります。 緑色の位置にGPSが観測されたとしても、実際に道路上にいる場合、候補点として0、1、2のいずれかの上にいるはずです。 次に、2番目のGPSの点も同様に、GPSの点は道路上にはありませんが、近くの道路を探索し、3、4、5、6の候補点を列挙できます。 1つのGPS観測点につき、一定距離（例えば50m）以内の候補点のみであったり、最もGPSに近い最大k個の候補点のみを列挙することで、候補点があまりにも多くなることを防ぎます。

[^Valhalla]

次に、これらのあるGPSの候補点から、次のGPSの候補点への遷移、さらにその先の候補点への遷移のすべての組み合わせを列挙します。 このようにすると、有向非巡回グラフ (DAG) を構築することができます。 ここから、もっともらしいグラフ上の経路を、遷移確率と放出確率から求めます。

  • 遷移確率: GPS観測点間の距離と、道路上の候補点間の移動距離の差が小さいほど、もっともらしい遷移候補となります。（GPSデータの移動量と矛盾しない道路上の移動経路を高く評価します）
  • 放出確率: 複数ある候補点のうち、GPS観測点から近い距離にある候補点が、もっともらしい候補点となります。

遷移確率や放出確率を求める数式は、論文によって様々なものが提案されていますが、基本的な考え方は上記のようになります。

オープンソースツールを利用したマップマッチング

このHMMの手法が実装されたツールである、Open Source Routing Machine(OSRM)とValhallaを用いて、マップマッチングを実行してみます。 どちらもオープンソースのため、無料で利用することができます。 また、Dockerイメージとして公開されているので、Dockerが利用可能であれば手間をかけずに導入可能です。 道路ネットワークのデータとして、OpenStreetMapのデータを利用します。

OSRM

Open Source Routing Machine(OSRM)は、C++で実装された、OpenStreetMapのデータを利用して道路ネットワークの様々な分析を行うツールです。

まず、OpenStreetMapのデータを取得します。

wget http://download.geofabrik.de/europe/germany/berlin-latest.osm.pbf

次に、OSRMをDockerで起動し、ダウンロードした道路ネットワークに対して、前処理を行います。 前処理では、OSMファイルの抽出とエッジ拡張グラフ表現の生成を行います。

docker run -t -v "${PWD}:/data" ghcr.io/project-osrm/osrm-backend osrm-extract -p /opt/car.lua /data/berlin-latest.osm.pbf || echo "osrm-extract failed"
docker run -t -v "${PWD}:/data" ghcr.io/project-osrm/osrm-backend osrm-partition /data/berlin-latest.osrm || echo "osrm-partition failed"
docker run -t -v "${PWD}:/data" ghcr.io/project-osrm/osrm-backend osrm-customize /data/berlin-latest.osrm || echo "osrm-customize failed"

前処理が完了したら、ツールを起動します。

docker run -t -i -p 5000:5000 -v "${PWD}:/data" ghcr.io/project-osrm/osrm-backend osrm-routed --algorithm mld /data/berlin-latest.osrm

ポート5000番で起動しましたので、適当な経路探索クエリを投げてみます。

http://127.0.0.1:5000/route/v1/driving/13.388860,52.517037;13.385983,52.496891?steps=true

クエリへの応答があり、ツールが動作していることを確認できました。 結果は以下のようになっていました。（一部のみ掲載）

{
  "code": "Ok",
  "routes": [
    {
      "legs": [
        {
          "steps": [
            {
              "intersections": [
                {
                  "out": 0,
                  "entry": [true],
                  "bearings": [174],
                  "location": [13.38882, 52.517034]
                },
...

それでは、PythonからGPSデータを与えて、マップマッチングを実行します。 ベルリン周辺の3点のGPSデータを、始点をt=0とした時間とともに入力します。

import requests

BASE_URL = "http://127.0.0.1:5000"

trace = [
    (13.388860, 52.517037, 0),
    (13.397634, 52.529407, 60),
    (13.428555, 52.523219, 120),
]


def osrm_match_trace(points, profile="driving", use_timestamps=True):
    coord_str = ";".join(f"{lon},{lat}" for lon, lat, *rest in points)

    params = {
        "geometries": "geojson",
        "steps": "false",
        "radiuses": ";".join(["50"] * len(points)),
    }

    if use_timestamps and all(len(p) == 3 for p in points):
        ts_str = ";".join(str(p[2]) for p in points)
        params["timestamps"] = ts_str

    url = f"{BASE_URL}/match/v1/{profile}/{coord_str}"

    resp = requests.get(url, params=params, timeout=10)
    resp.raise_for_status()
    data = resp.json()

    if data.get("code") != "Ok":
        raise RuntimeError(f"OSRM error: {data}")

    return data


data = osrm_match_trace(trace)
matching = data["matchings"][0]
geom = matching["geometry"]  # GeoJSON LineString
coords = geom["coordinates"]  # [[lon, lat], ...]
len(coords), coords[:3]

実行結果は以下のとおりです。

(12, [[13.388642, 52.518036], [13.387228, 52.527168], [13.393668, 52.528491]])

Jupyter NotebookでPythonを実行している場合、以下のプログラムでNotebook上に地図とマッチされた経路が表示されます。

import folium

# OSRM の geometry は [lon, lat] なので folium 用に [lat, lon] に並び替え
line_latlon = [(lat, lon) for lon, lat in coords]

# 地図の中心を最初の点に
center_lat, center_lon = line_latlon[0]
m = folium.Map(location=[center_lat, center_lon], zoom_start=13)

# マッチした経路（線）
folium.PolyLine(
    locations=line_latlon,
    weight=5,
    opacity=0.8,
).add_to(m)

# 元の GPS 点もプロット（trace をそのまま表示）
for i, (lon, lat, ts) in enumerate(trace):
    folium.CircleMarker(
        location=[lat, lon],
        radius=4,
        popup=f"pt{i}, t={ts}",
    ).add_to(m)

m

3点の入力から、見事に通過したと思われる道路を探索できました。

Valhalla

Valhallaも同様に、Dockerでツールを起動してHTTP APIで探索が可能です。 また、マルチモーダル（複数の交通手段を組み合わせた探索）にも対応しています。 Valhallaの中でも、特にマップマッチングを行うツールをMeiliと呼びます。

今度は、アンドラ公国（スペインとフランスの間に位置する小国）の道路データをダウンロードし、Dockerを起動します。

mkdir custom_files
wget -O custom_files/andorra-latest.osm.pbf https://download.geofabrik.de/europe/andorra-latest.osm.pbf
docker run -dt --name valhalla -p 8002:8002 -v $PWD/custom_files:/custom_files ghcr.io/valhalla/valhalla-scripted:latest

初回起動後は前処理が実行されますが、しばらくするとアクセス可能になります。 それではPythonからクエリを投げてみましょう。

import requests

VALHALLA_URL = "http://localhost:8002"

# アンドラ・ラ・ベリャ周辺の適当な3点（lat, lon, time）
shape = [
    {"lat": 42.5078, "lon": 1.5210, "time": 0},
    {"lat": 42.5090, "lon": 1.5245, "time": 60},
    {"lat": 42.5110, "lon": 1.5280, "time": 120},
]

payload = {
    "shape": shape,
    "costing": "auto",          # 車が前提。徒歩なら "pedestrian"
    "shape_match": "map_snap",  # GPSトレースのマップマッチングモード
    "use_timestamps": True,
    "trace_options": {
        "search_radius": 100,   # 探索半径を拡大
        # "gps_accuracy": 50,   # 必要なら
    },
}

resp = requests.post(f"{VALHALLA_URL}/trace_route", json=payload, timeout=60)
print(resp.status_code)
print(resp.text[:300], "...")
resp.raise_for_status()

data = resp.json()
data["trip"].keys()

実行結果:

200
{"trip":{"locations":[{"type":"break","lat":42.5078,"lon":1.521,"original_index":0},{"type":"break","lat":42.511,"lon":1.528,"original_index":2}],"legs":[{"maneuvers":[{"type":1,"instruction":"Drive southwest on Carrer Doctor Nequí.","verbal_succinct_transition_instruction":"Drive southwest. Then Ma ...

実行結果はPolyline6というエンコードされた文字列で返ってくるため、polylineパッケージを使ってデコードします。

import polyline

leg = data["trip"]["legs"][0]
encoded = leg["shape"]              # 例: "c`{~F...`@"
precision = 6                       # Valhallaは polyline6

decoded_coords = polyline.decode(encoded, precision=precision)
# decoded_coords は [(lat, lon), (lat, lon), ...] のリスト
len(decoded_coords), decoded_coords[:3]

実行結果:

(145, [(42.507793, 1.521005), (42.507597, 1.52044), (42.507584, 1.520418)])

最後に地図上に表示します。

import folium

# 地図中心をマッチ済みラインの最初の点に
center_lat, center_lon = decoded_coords[0]

m = folium.Map(location=[center_lat, center_lon], zoom_start=15)

# マッチされた経路（折れ線）
folium.PolyLine(
    locations=decoded_coords,  # (lat, lon) のリスト
    weight=5,
    opacity=0.8,
).add_to(m)

# 元の生GPS点もプロットして比較
for i, pt in enumerate(shape):
    folium.CircleMarker(
        location=[pt["lat"], pt["lon"]],
        radius=4,
        fill=True,
        popup=f"raw pt {i}, t={pt['time']}",
    ).add_to(m)

m

マッチングされた経路が表示されます。

まとめ

本記事では、隠れマルコフモデル(HMM)を用いたマップマッチングの仕組みと、OSRMとValhallaという2つのオープンソースツールを使った実装方法を紹介しました。 どちらのツールもDockerで簡単に導入でき、OpenStreetMapのデータを使って実用的なマップマッチングを実現できます。

近年、マップマッチングの分野ではDeep Learningベースの手法が急速に広まりつつあります。 HMMによる手法と比較して精度が良く、特に疎なGPSデータに対しても高い性能を発揮します。 一方で、Deep Learning手法は学習に大量のデータが必要という課題があるため、HMMベースの手法も依然として重要であり、現在も研究が続けられています。

位置情報データの活用がますます進む中で、マップマッチング技術は今後も重要な役割を果たしていくでしょう。

参考文献