地理情報システムは徐々に日常生活に入ってきています。



ほとんどのモバイルデバイスには、GPS / GLONASS受信機が装備されています。 これにより、開発者はユーザー（トラック）の追跡記録を取得できます。 トラックを使用して、地図をナビゲートして友人の位置を通知することから、交通渋滞を構築して交通状況を予測することまで、いくつかの問題を解決できます。



残念ながら、追加の処理を行わない場合、ユーザーの追跡は有益ではないため、外部データと内部アプリケーションマップをリンクする段階が必要です。 これを行うには、特別なデータマッチングアルゴリズム（マップマッチングアルゴリズム）があります。



この記事では、トラックを道路グラフにリンクするアルゴリズムと、 Map @ Mail.ruプロジェクトでのアプリケーションの結果について説明します。



説明するアルゴリズムは、入力されたトラックを処理し、出力で道路グラフのエッジのシーケンスを受信します。これにより、入力データをジオメトリにできるだけ近づけて繰り返します。



道路グラフは、地理情報アプリケーションの基盤の1つです。 内部には、コーティングの種類や車線の数からジオメトリーまで、道路に関するすべての情報が含まれています。 コンピューターのメモリで道路グラフを表す方法はいくつかあります。



最も単純なオプションを考えてみましょう。ノードが交差点で、エッジが道路である方向グラフです。 この単純化により、道路のルールを確認することは難しくなりますが、さらに計算が容易になります。 同様の列に両方向のトラフィックがある道路は、エッジのペアで表されます。 エッジは、パスの分割不可能な単位です。 ただし、エッジは道路の数学的表現です。 マップ上の道路の実際の位置（道路座標のセット）は、グラフのこのエッジの個別のプロパティによって決定されます。これを道路のジオメトリと呼びます。

トラックとは、エラーを含む順序付けられた一連のポイントです。 このエラーのため、ポイントは、グラフのアタッチが必要なエッジ上にはほとんどありません。 GPSデータの平均の法則によると、測位誤差は市の中心部よりもオープンフィールドの方が小さくなっています。 言い換えれば、到着したポイントは隣接するエッジに到達する可能性があります。



カードの目から見ると、モスクワの1つのインターチェンジのように見えます。





そのため、ナビゲーターのバージョンによると、ユーザーは次のように進みます。

バインディングプロセスの追跡

トラック上のポイントをグラフにスナップするには、最も単純な場合、エッジからポイントまでの距離が最小のエッジを見つける必要があります。 残念ながら、実際には（特に都市の中心部で）、このように結び付けられたルートは、互いに接続されていない一連のエッジになることがあります。 バインディングの品質を向上させるために、トラックは、グラフのエッジのジオメトリに沿った、ユーザーのターゲットを絞った動きであると想定しています。 つまり、ルート全体が互いに接続されたリブに沿って通過します。 同時に、ルートの各エッジには、トラック上に単一のポイントではなく、複数のポイントがある場合があります。



したがって、ポイントに最も近いエッジの取得を拒否するため、測定されたエッジがスナップに適しているかどうかを判断できる他の定量的測定値を選択する必要があります。



この場合に使用できる多くの要因があります。

1. ポイントからグラフのエッジのジオメトリまでの距離。 最短距離と、受信者がそのような間違いを犯す可能性の両方を評価します。
2. 動きの方向の一致。 車両の動きベクトルと、ポイントがバインドされているエッジジオメトリの方向との間の角度を推定します。 （この測定値は、GPS受信機の系統誤差に耐性がありますが、ランダムに影響を受けます）。
3. 車両の方向を変える。 車が主要道路をオフにする確率は、一般に、車がそれに沿って移動し続ける確率よりも低くなります（これにより、操縦回数が最小化されます）。
4. あるrib骨から別のrib骨に移行する身体的能力（rib骨の到達）。 この移行を行うために車が移動しなければならない速度の妥当性。

これらの要因に基づいて、尤度評価式が作成されます。 フレシェ距離は 、これらの式の1つとして使用されます。 簡単に言えば、これは、飼い主が道路グラフをたどり、ペットがGPSトラックをたどる場合の犬の綱の最小必要長です。 この推定は、敷設されているトラックの地理的遠隔性のみに焦点を当てています。



この記事のトラックをバインドするには、増分データバインドアルゴリズムの推定式を使用します（S. Barcatsoulas [2]の研究に基づく）。



この式には、2つの主要なコンポーネントが含まれます。 そして 。



成分 トラックポイントからエッジまでの重み付き距離を考慮し、次の式で計算されます。



どこで

スケーリング係数であり、 ポイントp _iからエッジc _jのジオメトリまでの距離です。



成分 リブのジオメトリの方向とトラックの方向の間の角度を考慮します。



どこで

そして スケーリング係数であり、cos（αi _、j ）は、グラフのi番目のエッジのジオメトリとトラックのエッジに沿った移動方向との間の角度です。

そして -これらは、コンポーネントの重要性に影響するパラメーターです。 アルゴリズムでは、これらのパラメーターの相対的な値が重要です。これにより、比較する際にどの要素の重みが大きくなるかが決まります。



パラメータ そして 記載された要因の変化に対する感度に影響します。



コンポーネントを計算した後、最終的なメトリックは次のように計算されます。







結果が大きいほど、トラックセクションとエッジの一致が良くなります。



武器庫にプロットされたルートの尤度式を使用して、バインディングアルゴリズムを説明できます。

1. , ;
   
   
   
   
2. ;
   
   
   
   
3. . ;
   
   
   
   
4. , . ( , );
   
   
   
   
5. ;
   
   
   
   
6. 2;
   
   
   
   

フォローアップ戦略

選択した式の疑いのない利点は、1つのポイントだけでなく、ルート全体のグラフへのバインドの可能性を評価できることです。 これを使用して、後続のポイントのアカウンティング戦略を実装できます。 ルートの最後のポイントが現在アタッチされていない場合、ルートが選択したエッジに沿って走っていれば、次のポイントのバインドの推定値を計算できます。 その後、尤度推定値の合計を比較できます。 これにより、アルゴリズムが後続の動きを考慮してエッジを選択するため、複雑なジャンクションと交差点でのエラーが回避されます。

パフォーマンスについて少し

1つのトラックをリンクするタスクは信じられないほど高価ではありませんが、実際には、ペアのトラックを結び付ける人はほとんどいません。 原則として、毎秒数千ポイントを管理する必要があります。 したがって、処理速度とバインドの精度を妥協する必要があります。 選択したアルゴリズムでは、パフォーマンスは、各トラックポイントの推定エッジ数と「将来」のポイント推定の深さの影響を受けます。 実践が示しているように、交差点での行動について適切な決定を下すためには、ほとんどの場合、トラックの2〜3ポイントを考慮するだけで十分です。



実際には、推定エッジの数を変更することは困難です。高品質のバインディングでは、最初のエッジを選択した後、すべての出力エッジを評価する必要があるためです。 ただし、尤度スコアが低すぎるオプションを検討しない場合があります。

まとめ

バインディングアルゴリズムの実装により、 プライバシーマッププロジェクトはモバイルユーザーデータの操作を開始するだけでなく、独自のデータを任意のシステムと迅速に調整することができました。 バインディングの新しいサブシステムを使用すると、1つのサーバーで1分以内に、合計で最大55,000ポイントを含むグラフ上のトラックを再カウントできます。 これにより、データは可能な限り迅速にユーザーに表示されます。 アルゴリズムは、内側のグラフの3つのエッジ上のトラックの1点でも定性的な参照を示します。 ただし、記述されたアルゴリズムの最大の効率は、グラフの各エッジ上の1つまたは2つのポイントで長いトラックをバインドするときに達成されます。

関連文献

1. 「マップマッチング。 はじめに” Prof. デビッド・バーンスタイン、ジェームズ・マディソン大学。
2. 「地図照合車両追跡データについて」Sotiris Bracatsoulas、Dieter Pfoser Randall Salas Carola Wank VLDB'05
3. 「フレシェ距離に関する近似マップマッチング」Daniel Chen、Anne Driemel、Leonidas J. Guibas、Andy Nguyen、Carola Wenk。 スタンフォード 2011

---

Maps RamblerのTop100のプログラマー、Lev Dragunov