13

私は、GPS によって記録された多くのトラックを持っています。これは、より正式には、多数のライン ストリングとして説明できます。

ここで、記録されたトラックのいくつかは同じルートの記録である可能性がありますが、GPS システムの不正確さのため、記録が別の機会に行われ、異なる速度で移動して記録された可能性があるという事実は、完全に一致しますが、人間が地図上で見ると、実際に記録されたのと同じルートであると判断するのに十分なほど近くに見えます.

2 つの折れ線の類似度を計算するアルゴリズムを見つけたいです。これを行うための自家製の方法をいくつか考え出しましたが、これが問題を解決するための優れたアルゴリズムを既に持っている問題であるかどうかを知りたいです。

類似の平均が地図上の同じ経路を表すとすれば、類似度をどのように計算しますか?

編集:私が何について話しているのかわからない場合は、次のリンクを参照して、線の文字列とは何かを定義してください: http://msdn.microsoft.com/en-us/library/bb895372.aspx - I'文字列については質問しません。

4

6 に答える 6

12

トラックの各ペアでフレシェ距離を計算します。距離は、トラックの類似性を測定するために使用できます。

数学の警告：フレシェは、あなたの問題に関連する距離空間の分野のパイオニアでした。

于 2008-09-17T15:08:58.533 に答える
3

推定された推定エラーに基づいて最初の行の周りにバッファーを追加し、2 番目の行がバッファー内に完全に収まるかどうかを判断します。

于 2008-09-15T12:53:13.697 に答える
2

「同じルート」を決定するには、正規化されたパス ベクトルの最小セットを作成し、電力差の合計を計算して、合計を品質尺度と比較します。

  1. 経路の全長で GPS ウェイポイントを正規化し、
  2. パスのベクトルを一緒に歩き、各ウェイポイントでの最短ベクトルに基づいて、各パスのパス ベクトルの新しいセットを作成します。
  3. ベクトルの長さを重み付けした正規化されたパスの各ベクトルのエンドポイント間の総電力差を計算し、
  4. 品質尺度と比較します。

差の検出力 (例えば、2 乗の差から始める) と品質測定 (合計検出力の差の割合など) を視覚的に調整します。このアルゴリズムは、パス一致の継続的な品質測定とバイナリ結果を生成します (パスは同じですか?)

Paul Tomblin は次のように述べています。推定された推定エラーに基づいて最初の行の周りにバッファーを追加し、2 行目がバッファー内に完全に収まるかどうかを判断します。

正規化されたベクトル エンドポイントが比較されるときに、アルゴリズムを変更できます。エンドポイントの違いが特定のサイズを超えているかどうかを判断できます (Paul のバッファーのアイデアを実装)。または、エンドポイントが「バッファー」の外側にある場合は、その事実を使用してそのエンドポイントの違いを無視し、サイドトリップを無視した比較を可能にします。

于 2008-09-15T13:13:43.803 に答える
1

1 つの線ストリングを一連の [x,y] ポイント (または [x,y,z] ポイント) と見なす場合、Needleman-Wunschアルゴリズムを使用して、線ストリングの各ペア間の類似性を計算できます。参照されているウィキペディアの記事で説明されているように、Needleman-Wunsch アルゴリズムには、点のペア間の距離を定義する「類似度行列」が必要です。ただし、行列の代わりに関数を使用するのは簡単です。あなたの場合、2Dユークリッド距離関数（またはポイントに標高がある場合は3Dユークリッド関数）を使用して、ポイントの各ペア間の距離を提供できます。

于 2008-09-18T04:01:46.163 に答える
1

LineString A の各点 (Pa) に沿って歩き、Pa から LineString B の最も近い線分までの距離を測定し、これらの距離のそれぞれを平均します。

これは迅速または完璧な方法ではありませんが、有用な数値を使用できるはずであり、実装も非常に迅速です。

ライン ストリングは同様のポイントで開始および終了しますか、それとも範囲が大きく異なりますか?

于 2008-09-15T23:03:18.457 に答える
-2

私は実際、あなたがレーベンシュタイン距離問題に興味があるかもしれないと言った人 (アーロン F) の味方です (そしてこれを引用しました)。彼の答えは、これまでで最高のように思えます。

より具体的には、レーベンシュタイン距離 (編集距離とも呼ばれます) は、文字単位の距離を厳密に測定するのではなく、挿入と削除を実行することもできます。この距離測定に最適なアルゴリズムは、二次時間で計算できます (文字列が長い場合はかなり遅くなります) が、計算生物学者はこれについてかなり優れたヒューリスティックを持っています。BLASTとFASTAをチェックしてください。

あなたの問題では、数字の文字列間の違いを扱っているようで、数字を気にしています。さらに情報を提供していただければ、目的に合った BLAST/FASTA/etc の適切なバリアントをご案内できるかもしれません。いずれにせよ、必要に応じて BLAST と FASTA を調整することを検討してください。それらは非常に単純です。

1 : http://en.wikipedia.org/wiki/Levenshtein_distance、http://www.nist.gov/dads/HTML/Levenshtein.html

于 2008-09-15T18:02:35.310 に答える