11

私は 2 つのセットを持っています。各セットは数字のペアのリストです

Set1 =[(x1, y1), (x2, y2), ..., (xN, yN)]
Set2 =[(a1, b1), (a2, b2), ..., (aN, bN)]

XY 平面にプロットすると、Set1 と Set2 は同じ基本形状を持ちますが、set2 のデータ ポイントは、set1 の回転/平行移動/スケーリング/ノイズ/歪んだバージョンです。各セット内のペアの順序はランダムです。set1 のどの点が set2 の対応する点に対応するかを判断する効率的な方法はありますか?

4

2 に答える 2

8

2つの点群の違いを最小限に抑えようとするアルゴリズムのファミリーを探しています。これは解決するのがかなり難しい問題であり、複数の解決策が存在する可能性があります（たとえば、2つの立方体が与えられた場合、機能する可能性のある回転が多数あります）。

特に人気のあるアプローチの1つは、ICP（反復最接近点）アルゴリズムです。これは、候補の推測から開始し、正確性の基準に達するか、時間が経過するまで継続的に改良します。チェックアウトするのに良い出発点かもしれません。

お役に立てれば！

于 2013-01-10T20:32:01.763 に答える
1

はい、Rotations、Scalings、Translations のみを想定して、これを行うことができます (「ノイズ」と「スキュー」の部分を除いて、私にはよくわかりません)。

1 つのアプローチ:

  1. 各セットの重心 (2D 平均) を決定します。
  2. 各セットの最小二乗 (2D) 勾配を決定します。
  3. 各セットの 2D 分散を決定します。
  4. セントロイドの差を移動に、スロープの差を回転(*)に、バリアンスの差をスケールに使用して、最初のセットを再マッピングし、両方のセットが同じセントロイド、スロープ、バリアンスを持つようにします。
  5. 両方のセットを並べ替えてから、ポイントの同等性/類似性を比較します。(あるいは、「ノイズ」/差の尺度として、それらの間の RSM (二乗平均平方根) 差を計算することもできます)。

(*-反射および/または対称性により、回転部分で問題が発生する可能性があることに注意してください。)

于 2013-01-10T20:35:56.360 に答える