渋滞ライブカメラの道路マッチング技術

NAVITIME_Tech

2024年3月12日 10:00

こんにちは、ぴーよんです。
ナビタイムジャパンで道路案内の研究開発を担当しています。

今回は、先日リリースされた「渋滞ライブカメラ」機能に使われている、道路マッチングという技術についてご紹介いたします。

渋滞ライブカメラ機能について

「渋滞ライブカメラ」とは、渋滞の発生しやすい道路のライブカメラ映像を確認できる機能です。映像を動画でご覧いただけるため、車の流れを直感的に把握することができます。

詳しくはこちらのプレスリリースをご覧ください。

道路マッチング技術とは

高速道路のルートやデフォルメマップに、ライブカメラのアイコンを乗せて表示するには、それぞれのライブカメラがどの道路と紐づくのか決定する必要がありました。

基本は1つの道路

たとえば、首都高速「竹橋JCT」付近のライブカメラには、池袋線のみが映っていました。都心環状線を通るルートにアイコンを表示する必要はありません。そこで、

原則として、ライブカメラから一定距離以内の1つの道路にマッチさせる

というルールを定めました。これで、池袋線を通るルートのみにアイコンが表示されるようになりました。

この地図では、円がライブカメラから一定距離以内、矢印が方面別の道路、四角形がアイコン表示位置を表しています。

例外のケース

ところが、同じルールを適用すると「下関JCT」付近のライブカメラは中国道のみにマッチしてしまいます。実際には山陽道も映っていたため、

特定のライブカメラに限り、複数の道路にマッチさせる

というルールを追加しました。これで、中国道と山陽道のどちらを通るルートにもアイコンを表示できるようになりました。

さらに別のケースでは、ライブカメラに映る道路が、一定距離よりも遠くに存在していました。そのようなライブカメラは、より大きな距離でマッチさせるようにしました。

なぜこうするのか

ルールという考え方は、不必要に複雑だと思われるかもしれません。しかし、ライブカメラの位置や、道路の形状といったデータは、月日の経過とともに少しずつ更新されていきます。そのたびに人の手でマッチングし直すのでは、機能のご提供に時間がかかってしまいます。そこで、自動的かつ確実にマッチさせるための工夫として、ルールに基づくマッチングを導入しました。

Rustで実現する道路マッチング

ここからは、Rust言語による道路マッチングの実装例をご説明します。

データセット

今回は説明用に、2本の高速道路と1個のライブカメラのみのデータセットを用意しました。先ほどの竹橋JCT付近を模しています。

use geo::{LineString, Point};

// 高速道路の形状リストを用意します
let road_table = vec![
    LineString::from(vec![(139.7588750, 35.6910229), (139.7564920, 35.6927601)]),
    LineString::from(vec![(139.7588750, 35.6910229), (139.7560395, 35.6913693)]),
];

// ライブカメラの座標リストを用意します
let livecam_table = vec![Point::new(139.7572603, 35.6918347)];

実際のサービスでは、全国のデータセットを使用しています。

空間インデックスによる高速化

各ライブカメラを起点として、マッチング候補の道路を検索します。もし総当たりで検索すると、全国のデータセットでは処理時間が長くなります。そこで rstar クレートの空間インデックスを使って高速化します。

use rstar::RTree;

// 道路レイヤーに空間インデックスを作成します
let indexed_roads = RTree::bulk_load(road_table);

// ライブカメラをループします
for livecam in livecam_table {
    // ライブカメラから近い順に10本の道路を取り出します（空間インデックスにより高速化されています）
    for candidate_road in indexed_roads.nearest_neighbors(&livecam).iter().take(10) {
        // ライブカメラから一定距離以内の道路かどうか判定します
        if perpendicular_meter(candidate_road, &livecam).is_some_and(|x| x < 50.0) {
            println!("matched!");
        }
    }
}

perpendicular_meter 関数はこれから実装しますので、現時点ではビルドエラーとなります。

点から線への垂線距離

ライブカメラから一定距離以内の道路を判定するために、ライブカメラから道路への垂線の長さを計算します。geo クレートのアルゴリズムのうち「最近傍点」と「測地線距離」を組み合わせて実現できます。

use geo::{Closest, GeodesicLength, HaversineClosestPoint, Line};

// ライブカメラから道路への垂線の長さ(メートル)を計算します
fn perpendicular_meter(road: &LineString, livecam: &Point) -> Option<f64> {
    // ライブカメラに最も近い、道路上の点
    let closest = match road.haversine_closest_point(livecam) {
        Closest::SinglePoint(p) | Closest::Intersection(p) => p,
        Closest::Indeterminate => return None,
    };

    // 最も近い点が道路の両端の場合は、垂線ではない
    let mut vertex = road.points();
    if [vertex.next()?, vertex.next_back()?].contains(&closest) {
        return None;
    }

    // 垂線の測地線距離を計算します
    Some(Line::new(closest, *livecam).geodesic_length())
}

実行して、"matched!" が1回だけ出力されれば、成功です。なぜなら、今回のデータセットにおいてライブカメラから一定距離以内に存在する道路は1本だけだからです。

一般化すると

ライブカメラと道路のように、複数の地物同士のマッチングを指して、一般に「空間結合」と呼ばれます。ライブカメラは点データ、道路は線データですので、道路マッチングは「点と線の空間結合」と言えます。

まとめ

今回は、渋滞ライブカメラ機能を支える技術と、その考え方をご紹介しました。当社のサービスをご利用くださっている皆さまや、開発者の皆さまのご参考になりましたら幸いです。

ここまでご覧いただき、本当にありがとうございました。