29

x/y 座標の軌跡のターニング ポイントを決定するアルゴリズムを考え出そうとしています。次の図は、私が何を意味するかを示しています。緑は軌道の開始点を示し、赤は軌道の最終点を示します (軌道全体は ~ 1500 ポイントで構成されます)。 軌道

次の図では、アルゴリズムが返す可能性のある (グローバルな) ターニング ポイントを手動で追加しました。

可能性のある転換点のある軌道

明らかに、真のターニングポイントは常に議論の余地があり、ポイント間にある必要がある特定の角度に依存します. さらに、転換点は地球規模で定義できますが (黒丸でやろうとしたこと)、高解像度の局所規模で定義することもできます。私はグローバルな (全体的な) 方向性の変化に興味がありますが、グローバルなソリューションとローカルなソリューションを区別するために使用するさまざまなアプローチについての議論を楽しみにしています.

私がこれまでに試したこと：

  • 後続のポイント間の距離を計算する
  • 後続のポイント間の角度を計算する
  • 後続のポイント間で距離/角度がどのように変化するかを見てください

残念ながら、これでは確固たる結果は得られません。おそらく複数の点に沿って曲率を計算しすぎたのでしょうが、それは単なるアイデアです。ここで私を助けるかもしれないアルゴリズム/アイデアを本当に感謝します。コードは任意のプログラミング言語で作成できますが、matlab または python が推奨されます。

編集ここに生データがあります（誰かがそれで遊んでみたい場合に備えて）：

4

5 に答える 5

28

Ramer-Douglas-Peucker (RDP) アルゴリズムを使用してパスを簡素化できます。次に、単純化されたパスの各セグメントに沿った方向の変化を計算できます。方向の最大の変化に対応するポイントは、転換点と呼ぶことができます。

RDP アルゴリズムの Python 実装はgithub にあります。

import matplotlib.pyplot as plt
import numpy as np
import os
import rdp

def angle(dir):
    """
    Returns the angles between vectors.

    Parameters:
    dir is a 2D-array of shape (N,M) representing N vectors in M-dimensional space.

    The return value is a 1D-array of values of shape (N-1,), with each value
    between 0 and pi.

    0 implies the vectors point in the same direction
    pi/2 implies the vectors are orthogonal
    pi implies the vectors point in opposite directions
    """
    dir2 = dir[1:]
    dir1 = dir[:-1]
    return np.arccos((dir1*dir2).sum(axis=1)/(
        np.sqrt((dir1**2).sum(axis=1)*(dir2**2).sum(axis=1))))

tolerance = 70
min_angle = np.pi*0.22
filename = os.path.expanduser('~/tmp/bla.data')
points = np.genfromtxt(filename).T
print(len(points))
x, y = points.T

# Use the Ramer-Douglas-Peucker algorithm to simplify the path
# http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
# Python implementation: https://github.com/sebleier/RDP/
simplified = np.array(rdp.rdp(points.tolist(), tolerance))

print(len(simplified))
sx, sy = simplified.T

# compute the direction vectors on the simplified curve
directions = np.diff(simplified, axis=0)
theta = angle(directions)
# Select the index of the points with the greatest theta
# Large theta is associated with greatest change in direction.
idx = np.where(theta>min_angle)[0]+1

fig = plt.figure()
ax =fig.add_subplot(111)

ax.plot(x, y, 'b-', label='original path')
ax.plot(sx, sy, 'g--', label='simplified path')
ax.plot(sx[idx], sy[idx], 'ro', markersize = 10, label='turning points')
ax.invert_yaxis()
plt.legend(loc='best')
plt.show()

ここに画像の説明を入力

上記では 2 つのパラメーターが使用されました。

  1. RDP アルゴリズムはtolerance、単純化されたパスが元のパスから外れることのできる最大距離を表す 1 つのパラメータを取ります。が大きいほどtolerance、単純化されたパスは粗くなります。
  2. もう 1 つのパラメーターはmin_angle、転換点と見なされるものを定義する です。(ターニングポイントは、元のパス上の任意のポイントであり、単純化されたパス上の入力ベクトルと出力ベクトルの間の角度が より大きくなっていますmin_angle)。
于 2013-01-31T21:55:19.960 に答える
1

あなたが採用したアプローチは有望に思えますが、データは大幅にオーバーサンプリングされています。たとえば、広いガウス分布を使用して x 座標と y 座標を最初にフィルター処理し、次にダウンサンプリングすることができます。

x = conv(x, normpdf(-10 : 10, 0, 5))MATLAB では、とを使用できますx = x(1 : 5 : end)。追跡しているオブジェクトの固有の永続性とポイント間の平均距離に応じて、これらの数値を微調整する必要があります。

次に、スカラー積に基づいて、以前に試したのと同じアプローチを使用して、方向の変化を非常に確実に検出できるようになると思います。

于 2013-01-31T17:58:16.127 に答える
0

別のアイデアは、すべてのポイントで左右の周囲を調べることです。これは、各ポイントの前後に N ポイントの線形回帰を作成することによって実行できます。ポイント間の交差角度がしきい値を下回っている場合は、コーナーがあります。

これは、現在線形回帰にあるポイントのキューを保持し、移動平均と同様に、古いポイントを新しいポイントに置き換えることによって効率的に実行できます。

最後に、隣接するコーナーを 1 つのコーナーにマージする必要があります。たとえば、最も強いコーナー プロパティを持つポイントを選択します。

于 2013-01-31T20:35:27.483 に答える