optimization - GPS トラックの簡素化/最適化

Question

（ gpsdgpxlogger(1)のクライアントとして提供されている）によって作成された GPS トラックがあります。GPS 受信機は 1 秒ごとに座標を更新します。gpxlogger のロジックは非常に単純です。GPS から受信した位置 ( 、、) とタイムスタンプ ( ) をn秒 (私の場合はn = 3 ) ごとに書き留めます。latloneletime

数時間分のトラックを書き留めた後、gpxlogger は、数千のポイントを含む数メガバイトの GPX ファイルを保存します。その後、このトラックを地図上にプロットし、OpenLayersで使用してみます。それは機能しますが、数千のポイントがあるため、マップの使用は雑で遅い経験になります.

最適ではない点が数千あることは理解しています。ほとんど何も失わずに削除できるポイントが無数にあります。ほぼ直線を構成するポイントがいくつかあり、それらの間を同じ一定の速度で移動している場合、最初と最後のポイントを残して投げることができます。他のものを遠ざけます。

そのようなトラックの単純化/最適化ジョブにgpsbabelを使用することを考えましたが、残念ながら、単純化フィルターはルートでのみ機能します。つまり、タイムスタンプなしでパスの幾何学的形状のみを分析します(つまり、速度がほぼ一定であることを確認しません)。

トラックを最適化するために利用できる既製のユーティリティ/ライブラリ/アルゴリズムはありますか? それとも、gpsbabel の巧妙なオプションが欠けているのでしょうか?

score 13 · Accepted Answer

はい、前に述べたように、Douglas-Peucker アルゴリズムは 2D 接続パスを単純化する簡単な方法です。しかし、指摘したように、すべてのポイントに関連付けられた固有の時間次元で GPS トラックを適切に単純化するには、3D ケースに拡張する必要があります。Douglas-Peucker の PHP 実装を使用して、私自身の Web アプリケーションでこれを行いました。

アルゴリズムがどのように機能するかを少し理解していれば、アルゴリズムを 3D ケースに拡張するのは簡単です。A から Z までのラベルが付けられた 26 のポイントで構成される入力パスがあるとします。このパスの最も単純なバージョンには、A と Z の 2 つのポイントがあるため、そこから開始します。A と Z の間の線分を想像してください。残りのすべての点 B から Y をスキャンして、線分 AZ から最も離れた点を見つけます。最も遠い点が J であるとします。次に、B と I の間の点をスキャンして、線分 AJ から最も遠い点を見つけ、点 K から Y までをスキャンして、線分 JZ から最も遠い点を見つけます。すべてが望ましい距離しきい値内にあります。

これには、いくつかの単純なベクトル操作が必要です。論理的には、3D でも 2D と同じプロセスです。Douglas-Peucker アルゴリズムが言語に実装されている場合は、2D ベクトル演算が実装されている可能性があり、それらを拡張して 3 次元を使用する必要があります。

ここで 3D C++ 実装を見つけることができます: 3D Douglas-Peucker in C++

x 座標と y 座標はおそらく緯度/経度で表され、z (時間) 座標は UNIX エポックからの秒数で表されます。この不一致は、適切な時空間関係を決定することで解決できます。たとえば、1 平方マイルのマップエリアで 1 日のアクティビティを表示したいとします。この関係を 1 マイル x 1 マイル x 1 日の立方体として想像すると、時間変数を事前にスケーリングする必要があります。度から表面距離への変換は簡単ではありませんが、この場合は単純化して 1 度を 60 マイルとします。1 マイルは 0.0167 度です。1 日は 86400 秒です。単位を同等にするために、タイムスタンプのプリスケール係数は .0167/86400、つまり約 1/5,000,000 です。

たとえば、同じ 1 平方マイルのマップエリア内の GPS アクティビティを 2 日間にわたって表示したい場合、時間分解能は半分の重要性になるため、さらに 2 倍に縮小して 1/10,000,000 にします。楽しむ。

score 3 · Accepted Answer

Ramer-Douglas-Peucker複雑なポリゴンを滑らかにするためのアルゴリズムを見てください。また、Douglas-Peucker線の単純化アルゴリズムは、ポイントを減らすのに役立ちます。

score 2 · Accepted Answer

OpenSource GeoKarambola Java ライブラリ (Android の依存関係はありませんが、Android で使用できます) には、単純化/縮小 (3D/高度を認識) のルーティングと追跡の両方を行う GpxPathManipulator クラスが含まれています。ポイントに破棄されないタイムスタンプ情報がある場合。 https://sourceforge.net/projects/geokarambola/

これはインタラクティブに動作するアルゴリズムです

このアルゴリズムは、許容誤差が満たされるか、ポイントの最大数 (関数の両方のパラメーター) に達するまで、最大の XTD (クロストラック距離) エラーを持つポイントを排除することによって、ポイント数を減らすことに基づいています。

トラックの単純化のような実行中のストリームの代替アルゴリズム (私はそれを「ストリームプリフィケーション」と呼んでいます) は、次のとおりです。GPS ポイントがバッファーに追加されるたびに、GPS センサーが提供するポイントの小さなバッファーを保持します (高度含む) バッファー内のすべてのポイントの最大 XTD (クロストラック距離) を、最初のポイントとバッファーの (新しく追加された) 最後のポイントを結ぶ線分まで計算します。XTD が最大のポイントが最大許容 XTD エラー (25m で素晴らしい結果が得られました) に違反する場合は、そのポイントでバッファーをカットし、選択したポイントとして登録してストリーム化されたトラックに追加し、そのカットポイントまでバッファリングし、続行します。トラックの最後で、バッファーの最後のポイントもソリューションに追加/フラッシュされます。このアルゴリズムは、AndroidWear スマートウォッチで実行できるほど軽量であり、動きが遅くても速くても、同じ場所で長時間放置しても最適な出力が得られます。重要なのは、トラックの形状だけです。あなたは何分/キロメートルも行くことができ、あなたが直線（+/-許容XTDエラー偏差内の回廊）で移動している限り、streamplifyアルゴリズムは2つのポイントのみを出力します：最後のカーブとエントリーからの出口のポイント。次のカーブで。

score 1 · Accepted Answer

つまらない点は捨てたい。したがって、ポイントがどれだけ興味深いかを計算する関数が必要です。次に、すべてのポイントがどれだけ興味深いかを計算し、 Nを選択してデータセットを十分にスリム化する最も興味のないポイントを捨てることができます。あなたの興味深い定義は、計算が簡単な高加速度（直線運動からの逸脱）に対応しているようです。

score 1 · Accepted Answer

これはおそらく NP 困難です。点 A、B、C、D、E があるとします。

簡単な決定論的アルゴリズムを試してみましょう。ポイント B からライン AC までの距離を計算し、それがしきい値 (1 メートル) より小さいとします。したがって、B を削除します。次に、C を行 AD に同じことを試みますが、それは大きく、CE の場合は D も大きくなります。

しかし、最適解は A、B、E であることがわかります。これは、点 C と D が直線 BE に近く、反対側にあるためです。

1 つの点を削除すると、考えられるすべての解決策を試してみない限り、それが保持すべき点であると確信できなくなりますn^n(サイズが大きくなる可能性があるためn=80、既知の宇宙の原子の最小数よりも多くなります)。 .

次のステップ:ブルートフォースまたは分岐限定アルゴリズムを試します。スケーリングせず、実際のサイズでは機能しません。このステップはスキップしても問題ありません:)

次のステップ: 最初に決定論的アルゴリズムを実行し、メタヒューリスティックアルゴリズム (タブー検索、シミュレーテッドアニーリング、遺伝的アルゴリズム) でそれを改善します。Java には、 Drools Plannerなどのオープンソース実装がいくつかあります。

全体として、制約が 1 つしかないため、最初の単純な決定論的アルゴリズムで (最適ではありませんが) 実行可能なソリューションが得られるでしょう。

この問題の類似点は、セールスマンがすべての都市を訪問することはできず、いくつかの都市を選択する必要がある巡回セールスマン問題です。

score 1 · Accepted Answer

同様の問題に遭遇しました。GPS ユニットがポイントを取得する速度は、必要な速度よりもはるかに大きくなります。ポイントの多くは、互いに地理的に遠く離れていません。私がとったアプローチは、harsine 式を使用してポイント間の距離を計算することです。距離がしきい値 (私の場合は 0.1 マイル) よりも大きくない場合は、ポイントを破棄しました。これにより、ポイント数が管理可能なサイズにすばやく減少します。

あなたが探している言語がわかりません。これは、私が取り組んでいた C# プロジェクトです。下部に、harsine コードがあります。

http://blog.bobcravens.com/2010/09/gps-using-the-netduino/

これでうまくいくことを願っています。

ボブ

score 1 · Accepted Answer

これを試してみてください。無料でオープンソースのオンラインサービスです。

https://opengeo.tech/maps/gpx-simplify-optimizer/

score 0 · Accepted Answer

非常に簡単な方法の 1 つは、十分な数のポイントがなくなるまで、隣接するポイント間に最大の角度 (0° から 180° の範囲で、180° は隣接するポイント間の直線上にあることを意味します) を作成するポイントを繰り返し削除することです。それは、隣接するポイントと完全に一致するすべてのポイントを削除することから始まり、そこから進みます。

各インデックスとその角度のリストを作成し、そのリストを角度の降順で並べ替え、リストの先頭から必要な数を保持し、その短いリストをインデックスの降順、およびポイントのリストからインデックスを削除します。

def simplify_points(points, how_many_points_to_remove)
  angle_map = Array.new
  (2..points.length - 1).each { |next_index|
    removal_list.add([next_index - 1, angle_between(points[next_index - 2], points[next_index - 1], points[next_index])])
  }
  removal_list = removal_list.sort_by { |index, angle| angle }.reverse
  removal_list = removal_list.first(how_many_points_to_remove)
  removal_list = removal_list.sort_by { |index, angle| index }.reverse
  removal_list.each { |index| points.delete_at(index) }
  return points
end

score 0 · Accepted Answer

方向を変えるポイントをキープする必要があると思います。一定方向の間隔のセットにトラックを分割すると、これらの間隔の境界点のみを残すことができます。
そして、Raedwald が指摘したように、加速度がゼロではないポイントを残す必要があります。

score 0 · Accepted Answer

これがどれほどうまく機能するかはわかりませんが、ポイントのリストを取得し、それらの間の距離、したがってルートの合計距離を計算し、解像度の距離を決定してから、各ステップに基づいて位置を線形補間するのはどうですか? ×メートル。つまり、修正ごとに「開始からの距離」の測定値があり、ルート全体の n*x を補間するだけです。（必要なポイントの数を決定し、合計距離をこれで割って解像度距離を取得できます）。これに加えて、おそらく現在のポイント +/- z ポイントを取得し、exp(-k* dist^2/accuracy^2) のような重み付けを適用して、distは生の補間点からの距離で、accuracy は GPS 位置の推定精度です。

optimization - GPS トラックの簡素化/最適化

10 に答える 10

Related

Reference