Zenn
🗺️

地図技術の解剖メモ ~ 方向音痴を救える時代はくるか ~

に公開
map
navigation
Google Map
tech

はじめに

Google Maps をもってしても道に迷う超絶方向音痴の身からすると、恩恵を感じることの難しいシステムである地図アプリケーション。とはいえ、要素技術を理解しておくことは大切なので簡単にまとめておく。

Webマッピングの発展と時代区分

Webマッピング（Web Mapping）の歴史は1990年代初頭から始まり、技術的な進化に伴いいくつかの時代に区分することができる。

Veenendaalらの研究によると、Webマッピングは以下のような時代を経て発展してきたと言えるらしい。

時代 時期 主な特徴 代表的な技術・サービス
静的マッピング 1990年代初頭 静的なHTML画像として地図を公開 Xerox PARC Map Viewer (1993年)
動的マッピング 1990年代後半 サーバー側で動的に地図を生成 CGI, Java, ActiveX
サービス 2000年頃～ コンポーネントベース技術、APIの登場 WMS, WFS, MapQuest API
インタラクティブ 2005年頃～ AJAX技術による応答性の向上 Google Maps API
協調的マッピング 2005年頃～ ユーザー生成コンテンツ、Web 2.0 OpenStreetMap, WikiMapia
デジタルグローブ 2005年頃～ 3D表示、没入型体験 Google Earth, Microsoft Virtual Earth
モバイル・位置情報 2007年頃～ モバイルデバイス、位置情報サービス スマートフォンGPS, LBS
クラウド 2010年頃～ クラウドベースの処理・保存 ArcGIS Online, Google Maps Platform
インテリジェント 2015年頃～ セマンティクス、コンテキスト対応 自動運転向け高精度地図

地図技術の要素技術

タイル技術

タイル技術は地図データを効率的に配信・表示するための基盤技術である。

ラスタータイル

ラスタータイル（画像タイル）は、地図を一定サイズの画像に分割して管理・配信する方式である。

特徴 説明
仕組み 地図を格子状に分割し、各セルを画像として保存
利点 表示が高速、クライアント側の処理が少ない
欠点 データ量が多い、動的スタイル変更が困難
技術例 Google Maps Tiling Scheme (z/x/y), TMS

タイルピラミッドと呼ばれる階層構造を用いることで、ズームレベルに応じた適切な解像度の地図を提供する。ズームレベルをあげればあげるほど分割数が増えるため、比例してタイル数も増加する。

具体的には以下の数式に基づき、必要なタイル数が算出される。

タイル数 = 4^(ズームレベル)

例えば、ズームレベル0では1枚のタイル、ズームレベル1では4枚のタイル、ズームレベル2では16枚のタイルということになる。

ベクタータイル

ベクタータイルは地図データをベクトル形式で分割・配信する方式である。

特徴 説明
仕組み 地物データ（点、線、面）をベクトル形式でタイル化
利点 動的スタイル変更が可能、表示の柔軟性が高い
欠点 クライアント側での処理が必要
技術例 Mapbox Vector Tiles (MVT), GeoJSON Vector Tiles

ベクタータイルではクライアント側でレンダリングするため、同じデータから異なる見た目の地図を生成できる利点がある。また、ラベルの配置や道路の表示などを最適化しやすいメリットもあげられる。

ルーティングタイル

ルーティングタイルは、経路検索に特化した専用のタイル形式である。道路ネットワークのトポロジーや接続情報を効率的に格納し、経路計算ができるように最適化されている。

特徴 説明
仕組み 道路ネットワークを最適化した形でタイル化
利点 オフライン経路計算が可能、通信量削減、プライバシー向上
欠点 属性情報が多いとタイルサイズが大きくなる傾向、更新頻度の問題
技術例 Valhalla Tiles, GraphHopper, OSRM Tiles

ルーティングタイルには以下のような情報が含まれる。

  • 道路セグメント（ノードとエッジ）
  • 接続関係（交差点、ジャンクションなど）
  • 交通規制（一方通行、右左折禁止など）
  • 道路属性（速度制限、道路種別など）
  • 移動コスト（距離、時間など）

これにより、クライアント側でも効率的な経路計算が可能になる。

例えば、Mapboxのナビゲーションソリューションでは、ルーティングタイルをダウンロードすることで、完全なオフラインナビゲーションを実現している。また、Valhallaは、階層的なタイル構造を採用し、長距離ルートと短距離ルートの両方を効率的に計算できるように最適化されているなど、それぞれに特徴がある。

ジオコーディング

ジオコーディングは住所や地名などのテキスト情報を緯度・経度などの座標情報に変換する技術である。逆ジオコーディングはその逆を行う。

構成要素 説明
住所正規化 入力された住所を標準形式に変換
住所解析 国、都市、番地などの要素に分解
候補マッチング データベースから候補地点を検索
スコアリング 複数候補から最適なものを選択
補間処理 番地などの詳細位置を計算で補間

ジオコーディングの精度を高めるために、以下のような技術が用いられている。

  • あいまい検索（Fuzzy Matching）
  • 自然言語処理を用いた住所解析
  • 機械学習による最適候補の選択
  • 地域特性に応じた住所フォーマットの対応

Google、Mapbox、HEREなどの主要地図サービスはジオコーディングAPIを提供しており、高精度の住所変換サービスを実現している。

地理空間インデックス

地理空間インデックスは膨大な地理データを効率的に検索するための技術である。

代表的なものとして下記に示すようなものがあげられる。

インデックス種類 特徴 用途
グリッドインデックス 空間を均等なグリッドに分割 単純な領域検索
R木 最小外接矩形（MBR）を階層的に構築 範囲検索、近接検索
四分木（Quad Tree） 空間を再帰的に4分割 2次元空間のクエリ
k-d木 点データを交互に軸で分割 最近傍検索
Geohash 緯度経度を文字列にエンコード 位置の簡易表現、近傍検索

他にも独自実装として Google S2 Geometry Library と Uber H3 に触れておく。

Google S2は空間インデックスとジオメトリ演算のためのライブラリで、多くのGoogleサービス（Google Maps、Google Earth）やゲーム（Pokemon GO）などで使用されている。S2の特徴は球面上の空間分割と階層的なインデックスにあり、以下のような特徴を持つ。

  • 球面ジオメトリ
    地球を平面に投影せず、球面上で直接計算するため精度が高い
  • 階層性
    親子関係を持つセルの階層構造により、様々な解像度でのクエリが容易
  • ヒルベルト曲線
    空間的に近い点が数値的にも近いID値を持つよう最適化

例えば、与えられた地点の周辺施設を検索する場合、その地点を含むS2セルとその周辺セルのIDを計算し、それらのセルに含まれる施設だけを検索することで、効率的な近傍検索が実現できる。

次に、H3 はUberが開発し、オープンソース化した六角形グリッドによる空間インデックスシステムである。H3は特に移動分析や需要予測などの用途に最適化されている（らしい）。

特徴 説明
データ構造 地球表面を階層的な六角形グリッドで分割
インデックス表現 64ビット整数による階層的なセル識別子
空間粒度 16レベル（0〜15）の解像度で地球表面を表現
特長 等面積性、等距離性に優れる、集計分析に適している

H3の主な利点は以下の通り。

  • 六角形グリッド
    隣接セルまでの距離が均一で、歪みが少ない
  • 階層性
    親セル1つに対し子セル7つの明確な階層関係（一部のセルで変動するケースあり）
  • 分析適性
    空間集計や密度分析に適した均一なセル構造
  • アドレッシング効率
    コンパクトな表現でグローバルな位置参照が可能

Uberではこの技術を利用し、需要予測、動的料金設定、ドライバー配置の最適化などを行っている。例えば、各六角形セル内の需要と供給のバランスを分析し、リアルタイムで料金調整や配車最適化を行うことができる（らしい）。

経路検索アルゴリズム

経路検索は地図サービスの重要な機能の一つである。主要なアルゴリズムとその特徴は以下の通り。

アルゴリズム 特徴 適用場面
ダイクストラ法 単一始点最短経路問題を解く 基本的な経路検索
A*アルゴリズム ヒューリスティクスを用いた探索の効率化 一対一の経路検索
双方向検索 始点と終点から同時に探索 長距離経路の高速化
階層的アルゴリズム 道路網を階層化して探索範囲を限定 大規模ネットワーク

実際の経路検索サービスでは、単純な最短経路だけでなく、以下のような要素も考慮に入れている。というより、入れなければ実用性に欠ける。

  • 交通状況によるリアルタイムな所要時間
  • 時間帯による交通規制の変化
  • 乗り換えを含むマルチモーダルな経路
  • ユーザー嗜好（高速道路優先, 回避など）

交通情報と到着時間予測（ETA）

到着時間予測（Estimated Time of Arrival : ETA）は、経路上での予想所要時間を計算する技術である。Google Mapsなどのサービスでは、機械学習を活用して高精度な予測を実現している。

ETAの精度向上には、以下のようなデータソースと技術が使われている。

データソース/技術 貢献
リアルタイム交通情報 現在の道路状況を反映
履歴交通データ 時間帯・曜日ごとの傾向を把握
イベント情報 特異日の予測に活用
気象データ 天候の影響を考慮
ユーザー走行データ 実走行からのフィードバック
グラフニューラルネットワーク 道路網のグラフ構造を利用した学習

ETA Prediction with Graph Neural Networks in Google Mapsによれば、グラフニューラルネットワーク（GNN）を用いたETA予測システムは、従来のシステムと比較して予測誤差を大幅に削減できることが示されている。このシステムでは、道路ネットワークをグラフとして表現し、各道路セグメントをノードとして扱う。

ETAの予測は以下のような手順で行われる。

  1. 道路ネットワークをグラフとしてモデル化
  2. 各道路セグメントの特徴（長さ、種類、制限速度など）を抽出
  3. 時間帯や曜日などの特徴を追加
  4. グラフニューラルネットワークで道路網全体の構造と区間ごとの特徴量・履歴データを組み合わせて通過時間を予測
  5. 経路全体の所要時間を集計

これにより、「通常10分の道路が事故で30分かかる」といった特異な状況も適切に予測できるようになる。

要素技術の統合と実用システム

前章で説明した要素技術は、独立して存在するものではなく、互いに連携して実際の地図サービスを構成している。

ここでは、これらの技術がどのように連携して機能するかを具体的なユースケースとともに整理する。詳細に踏み込みすぎるとややこしいためハイレベルな（一部厳密性に欠ける）説明にとどめる。

車載ナビゲーションシステム

車載ナビゲーションシステムは、主にオフライン処理を基本としながらリアルタイム交通情報を加味する複合的なシステムである。以下では、車載ナビゲーションシステムにおける経路探索の内部処理フローを眺める。

初期準備とデータ構造

車載ナビゲーションシステムは、あらかじめ車載機内に以下のデータを保持している。

  • 詳細な道路ネットワーク地図データ
  • ルーティング用グラフ（ノードとエッジで構成）
  • 施設情報（POI）データ

これらのデータは通常、タイル形式や専用データベース（SQLiteベースなど）で格納されており、高速アクセスが可能な構造となっている。

経路探索処理の流れ

  1. 現在位置特定（マップマッチング）

    • GPSや車両センサー（ジャイロ・スピードメーター）からのデータを基に、現在地を道路ネットワーク上の適切なリンク（道路区間）に紐付ける
    • 単純なGPS座標ではなく、実際に走行可能な道路上の位置として特定する
    • 進行方向や速度からも最適なリンクを確定する

  2. 交通情報受信

    • 様々な方式でリアルタイム交通情報を取得
      • VICS（日本独自：FM多重放送や光ビーコンなど）
      • ETC2.0（プローブ情報ベース）
      • オンライン接続（スマホテザリングやSIM通信）
    • 道路区間ごとの平均速度、渋滞長さ、規制情報（通行止め、工事中）などを受信

  3. 交通情報マッチング

    • 受信した交通情報を内部の道路リンクIDと突き合わせる
    • 各道路区間（エッジ）に実際の走行コスト（所要時間）を付与
    • 渋滞区間はコストを上げ、スムーズな区間はコストを下げる処理

  4. 経路探索（ルート計算）

    • ダイクストラ法やA*アルゴリズムをベースにした最短経路探索
    • 単純な距離ではなく「時間最短」を基準としたコスト計算
    • A*探索では現在ノードからゴールまでの推定残時間をヒューリスティック関数として使用
    • 高速道路のような主要道路を優先的に探索するContraction Hierarchiesなどの高速化手法も採用

  5. リアルタイム再ルーティング

    • 走行中に新しい交通情報を受信した場合、現在のルートの所要時間を再評価
    • 予定経路の所要時間が閾値以上増加した場合、新たな経路を再計算
    • 自動的に別ルートへのリルートを提案

  6. 経路案内・音声出力

    • 計算されたルートに沿って、曲がるべき交差点などを案内
    • 交差点接近時の音声ガイド（「次の交差点を左折です」）
    • 画面上でルート表示と距離・所要時間カウントダウン

車載ナビの強みは、通信環境に依存せず、常に安定した経路計算が可能である点にある。最新の車載ナビでは、時間帯別渋滞予測データを考慮したり、ユーザー好みに応じたコストファンクションのカスタマイズ（高速道路優先、一般道優先、料金節約優先など）も可能になっている。

モバイルナビゲーション

モバイルナビゲーション（Google Maps、Apple Maps、Yahoo!カーナビなど）は、車載ナビとは異なるアーキテクチャで構築されている。最大の違いは、経路計算のほとんどをクラウドサーバー側で実行する点にある（オフライン時や簡易再計算は端末側で行う場合もある）。

モバイルナビの処理フロー

  1. 位置特定（端末側）

    • スマートフォンのGPS、Wi-Fi、加速度センサーを使用して現在地を推定
    • 内部のライトウェイトなマップマッチングで道路上の位置を特定

  2. 経路探索リクエスト（端末→サーバー）

    • 出発地点、目的地点、移動手段、経路設定（高速道路の使用有無など）をパラメータ化
    • コンパクトなリクエストパケットとしてサーバーに送信
    • 例
    {
  "origin": {"lat": 35.6895, "lng": 139.6917},
  "destination": {"lat": 35.6580, "lng": 139.7020},
  "mode": "driving",
  "traffic_model": "best_guess"
}

  3. サーバー側での経路計算

    • 巨大なサーバーインフラが完全な道路ネットワークとリアルタイム交通情報を保持
    • Contraction Hierarchies (CH) やALT (A*, Landmarks, Triangle inequality) など最適化されたアルゴリズムで経路探索
    • Google Trafficなどの集約された交通情報を加味した最適経路を計算

  4. 結果返送（サーバー→端末）

    • 計算された経路ポリライン（座標列）
    • 予測所要時間
    • 区間ごとの案内情報（ターン・バイ・ターン指示）
    • データ通信量削減のため高度に最適化・圧縮されたフォーマット
    • 例
    {
  "routes": [{
    "summary": "首都高速3号渋谷線経由",
    "legs": [ *legsは複数区間の詳細情報が入る配列* ],
    "overview_polyline": {
      "points": "a~l~Fjk~uOwHJy@P..."
    }
  }]
}

  5. 経路案内（端末側）

    • 受信した経路データに基づいて画面表示と音声案内を実行
    • 現在位置を継続的に監視して進行状況を更新
    • GPSがルートから大きく外れた場合、「ルート逸脱検知」を行い、サーバーに再リクエスト

まとめ

地図技術は静的な画像表示から始まり、インタラクティブな操作、ユーザー参加型のコンテンツ作成を経て、現在ではAIによる高度な予測や分析を行う段階に到達した。

タイル技術、ジオコーディング、地理空間インデックス、経路検索アルゴリズム、交通情報予測といった要素技術がそれぞれ進化しながら、総合的な地図プラットフォームを形成している。これらの技術は相互に影響し合い、地図サービス全体の発展を支えている。

いずれ超絶方向音痴にとってもやさしいシステムになることを期待したい（特に駅を出てすぐのエリアは電波が悪いので、方角が定まらず詰む。一番欲しいタイミングで精度が悪いので詰む。どうしようもない）。

Discussion