ノイズの多いX、Yデータからパスを決定する方法
https://stackoverflow.com/questions/240473
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
ノイズの多いX、Yポイントのソートされていないリストがあります。ただし、それらは世界を通るパスを形成します。アルゴリズムを使用して、線分を使用してこのデータの近似値を描画します。
これは、線形近似アルゴリズムを使用して線形データの近似値を選択する方法に似ています。私の問題は、道が曲がって世界中を曲がりくねっているので、もっと難しいだけです。 代替テキストhttp://www.praeclarum.org/so/pathfinder.png
これを達成するための標準/堅牢/理解しやすいアルゴリズムを知っている人はいますか？
Q <！> amp; A ：
ノイズが多いとはどういうことですか？パスの理想的な実現があった場合、XおよびY要素にガウスノイズが追加された理想的なパスからポイントのセットがサンプリングされます。そのノイズの平均または標準偏差がわかりません。 std devで推測できるかもしれません...
ポイントは、近似しようとする理想的で複雑なパスの近くにありますが、その上にありませんか？はい。
パスの形状に関するアプリオリ情報はありますか？そのような情報を取得する他の方法はありますか？残念ながらありません。
解決
並べ替えられていないリストでは、各セグメントにどのポイントを含めるべきかが実際にはわからないので、最も近いポイントに行くことができると思います。
1つの方法は、開始ポイントをランダムに選択し、各ステップの次のポイントとして最も近いポイントを選択することです。最初の2つのポイントをセットSに追加します。
RMSが特定の値を超えるまでSのポイントに線を合わせ、Sをクリアして新しい行を開始します。
連続する線の交点は、セグメントの終点になります。
他のヒント
Bezier補間が問題に適合する場合があります。
ただし、これはパスへのポイントの順序付けには対応していません。考慮すべき多くのアプローチがあります：
- 任意の<！> quot;最適な<！> quot;パスのタイプ（たとえば、パス上の各ポイントでの最小方向変更、*すべてのポイントを通る最短パス）は、NPの完全な旅行セールスマンの問題（TSP）。
- <！> quot;合理的な<！> quot;ノードをクラスター化し、クラスター間およびクラスター内でルーティングするパス。もちろん、クラスターが大きいほど、またはクラスターの数が多いほど、この小さな問題は大きなn TSPのように見えます。
- 1つの軸によるポイントの順序付け。 2つ以上の軸がある場合、次元の削減戦略が役立つ場合があります。例えば独立成分分析。
ポイントが互いに近い場合、通常の<！> quot; straight <！> quot;線（直交線）。通常のスムージングアルゴリズムを使用します。世界は平らであると見ることができます。
それらが離れている場合、大円を使用して、地球の丸みを補正する必要がありますポイント間を移動します。そうしないと、直線が長くなります。
ポイントが遠すぎて直線を作成できない場合は、選択します。
さらに、<！> quot; visit <！> quot;する必要があるかどうかを知る必要があります。各ポイント、または単に近くに行く必要があり、その近くにどれだけ近いか。
コースを飛行機、船、または他の旅行者に送る必要がある場合は、おそらく各地点を訪れる必要があります。オブジェクトからGPSデータを取得する場合は、おそらく画面にコースをプロットし、ノイズを除去したいだけです。
編集内容を確認した後： これがプロットしたい軌跡を移動するオブジェクトである場合、x / y値の代わりに方向と速度を滑らかにしたい場合があります。 （測定値（x）を固定し、Y間隔を大きくすると、平滑化がはるかに簡単になります。）
次の場合、データの順序付けの問題に対処する可能性があるヒューリスティックハックがあります
- 十分なポイントがあります
- パス間の予想最小曲率半径と比較して、ポイント間の平均距離が短い
- ポイント間の平均距離は標準に比べて大きくありません。開発者ノイズの
- パスは自己交差していません（幸運になるかもしれませんが、保証はありません）
次のように進みます。
- 開始点（ p1 ）を選択します（ランダムではなく、意味のある方法で）
- あるクラスタリング距離内にあるすべてのポイント、 p1 の r_c を見つけます。 r_c は、予想される旋回半径に比べて小さいが、散布に比べて大きいを選択します。
- このクラスターを C1 と呼びます。
- 検索ポイント q1 C1 の位置の平均。
- C1 の点に線を合わせて、クラスターの端に（またはその少し先に）投影し、元のデータで最も近い点を見つけます。そのポイントに p2 というラベルを付けます。
- データがなくなるまでステップ2〜5を繰り返します。
順序付けられた新しいポイント q1 .. qn のリストができました。
私の頭の上では、非常に粗く、かなり良い条件下でのみ動作します...
ステップ（5）で、新しい投影線が前の投影線の最大角度内にあることを要求することにより、おそらく自己交差動作を改善できます。
ベジェ曲線の問題は、実際にサンプリングしたポイントを通過し、ポイントのサンプルが少し歪んでいる場合でもそうではないことです。ベジエ曲線は実際には数マイル離れている可能性があります。
より良い近似、および元の画像によく似ていると思われる解決策は、です。 Catmull-Rom Spline は、曲線のすべてのポイントを通過するためです。
私のアプローチは、最初にポイントのリストをソートしてから、ベジェ曲線を使用することです。
コツはもちろんソートです。 1つのランダムポイントから始めて、最も近いポイントを見つけます。これら2つが接続されていると仮定します。これらの2つのエンドポイントで、それらに最も近いポイントを見つけます。エンドポイントまでの距離が短い方がそのポイントに接続されていると仮定します。すべてのポイントが接続されるまで繰り返します。
このアプローチにはまだいくつかの問題があると思いますが、おそらくそれを出発点として使うことができます（しゃれを意図しています）。
編集：開始点を変えて何度か実行し、結果の違いを確認できます。これにより、少なくとも、どのポイントが相互に接続されているかについてある程度の自信が得られます。
別の制約を必要としない完全に異なるアプローチですが、詳細はアプリケーションによって異なる場合があります。 <！> quot;密集したポイント<！> quot;がある場合に最適です。パスの周り。
<！> quot; cost <！> quot;を使用します。曲線と点群の間の差を定義する関数。パラメータ化された曲線と標準の最適化アルゴリズムを使用します。 -または- 最初から最後までまっすぐな曲線から始め、遺伝的アルゴリズムを使用して修正します。
一般的なコスト関数は、各点と曲線の間の最小距離を取り、二乗を合計することです。
最適化または遺伝的アルゴリズムを提案するのに十分な経験はありませんが、それができると確信しています：）
次のような遺伝的アルゴリズムを想像できます。 パスはウェイポイントから構築されます。最初から最後まで、N個のウェイポイントを1行に配置することから始めます。 （Nは問題に応じて選択できます）。突然変異は次のとおりです：
- rnd（）<！> lt;の場合、各セグメントx、真ん中に新しいウェイポイントが導入されます。
- 各ウェイポイントで、X座標とY座標はわずかに異なります。
コスト関数に全長を含める必要があります。分割は必要ないかもしれません。または、x（<！> quot; split chance <！> quot;）を減らすには、ウェイポイントを追加する必要があるかもしれません。 （2）を開始点と終了点に適用する場合としない場合があります。
それを試してみるのは楽しいでしょう...
<！> quot; unsorted list <！> quot;ポイントのセットが完了している間、それらがどの順序で移動したかわからないことを意味しますか？
ガウスノイズは基本的に無視する必要があります。元のノイズのないパスを再構築しようとする情報をまったく与えられません。ですから、できることはポイントが正しいと仮定することです。
この時点で、タスクは<！> quot;ポイントセット<！> quot;を介して最適なパスを検索し、<！> quot; best <！> quot;漠然とした。ユークリッド空間で一連の点を順序付けようとするコードをいくつか作成し、より直線になる順序付けを優先しました。メトリックの実装は簡単でしたが、それに基づいて順序を改善する良い方法を考えることができなかったため、より良い配置を探すためにポイントをランダムに交換しました。
つまり、これを行うPLTスキームのコードを次に示します。
#lang scheme
(require (only-in srfi/1 iota))
; a bunch of trig
(define (deg->rad d)
(* pi (/ d 180)))
(define (rad->deg r)
(* 180 (/ r pi)))
(define (euclidean-length v)
(sqrt (apply + (map (lambda (x) (expt x 2)) v))))
(define (dot a b)
(apply + (map * a b)))
(define (angle-ratio a b)
(/ (dot a b)
(* (euclidean-length a) (euclidean-length b))))
; given a list of 3 points, calculate the likelihood of the
; angle they represent. straight is better.
(define (probability-triple a b c)
(let ([av (map - a b)]
[bv (map - c b)])
(cos (/ (- pi (abs (acos (angle-ratio av bv)))) 2))))
; makes a random 2d point. uncomment the bit for a 3d point
(define (random-point . x)
(list (/ (random 1000) 100)
(/ (random 1000) 100)
#;(/ (random 1000) 100)))
; calculate the likelihood of an entire list of points
(define (point-order-likelihood lst)
(if (null? (cdddr lst))
1
(* (probability-triple (car lst)
(cadr lst)
(caddr lst))
(point-order-likelihood (cdr lst)))))
; just print a list of points
(define (print-points lst)
(for ([p (in-list lst)])
(printf "~a~n"
(string-join (map number->string
(map exact->inexact p))
" "))))
; attempts to improve upon a list
(define (find-better-arrangement start
; by default, try only 10 times to find something better
[tries 10]
; if we find an arrangement that is as good as one where
; every segment bends by 22.5 degrees (which would be
; reasonably gentle) then call it good enough. higher
; cut offs are more demanding.
[cut-off (expt (cos (/ pi 8))
(- (length start) 2))])
(let ([vec (list->vector start)]
; evaluate what we've started with
[eval (point-order-likelihood start)])
(let/ec done
; if the current list exceeds the cut off, we're done
(when (> eval cut-off)
(done start))
; otherwise, try no more than 'tries' times...
(for ([x (in-range tries)])
; pick two random points in the list
(let ([ai (random (vector-length vec))]
[bi (random (vector-length vec))])
; if they're the same...
(when (= ai bi)
; increment the second by 1, wrapping around the list if necessary
(set! bi (modulo (add1 bi) (vector-length vec))))
; take the values from the two positions...
(let ([a (vector-ref vec ai)]
[b (vector-ref vec bi)])
; swap them
(vector-set! vec bi a)
(vector-set! vec ai b)
; make a list out of the vector
(let ([new (vector->list vec)])
; if it evaluates to better
(when (> (point-order-likelihood new) eval)
; start over with it
(done (find-better-arrangement new tries cut-off)))))))
; we fell out the bottom of the search. just give back what we started with
start)))
; evaluate, display, and improve a list of points, five times
(define points (map random-point (iota 10)))
(define tmp points)
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 10))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 100))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 1000))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 10000))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
質問への回答から「黄金曲線」を知っているようです。@ jameshが示唆する「黄金曲線」のベジェ曲線を見つけて、それを描くことをお勧めします。
ポイントはいくつありますか？
前述のように、ベジエ曲線は、ポイントが比較的少ない場合に適しています。多くのポイントがある場合は、dmckeeの提案に従ってクラスターを構築します。
ただし、ポイントの順序を定義するための別の制約がまた必要です。ポイントの選択方法については多くの良い提案がありましたが、別の制約を導入しない限り、解決策は可能な解決策を提供します。
考えられる制約：
- 最短パス
- ほとんどの直線セグメント
- 最小総絶対回転
- 方向の優先（つまり、水平/垂直は十字よりも可能性が高い）
すべての場合において、制約を満たすためには、おそらくシーケンスのすべての順列をテストする必要があります。 <！> quot; good guess <！> quot;で開始する場合、他をすぐに終了することができます。
