3

3D ポイントの 2 つのグループを互いに重ね合わせる必要があります。つまり、座標間の RMSD (二乗平均平方根偏差) を最小化するための回転行列と並進行列を見つけます。

私は現在Kabsch アルゴリズムを使用していますが、対処する必要がある多くのケースではあまり役に立ちません。Kabsch では、両方のデータ セットで同じ数のポイントが必要であり、さらに、どのポイントがどのポイントと位置合わせされるかを事前に知る必要があります。私の場合、ポイントの数は異なりますが、RMSD が最小化されている限り、最終的な位置合わせでどのポイントがどのポイントに対応するかは気にしません。

そのため、アルゴリズムは (おそらく) 2 つのポイント セットのサブセット間の 1-1 マッピングを見つけ、回転と平行移動の後に RMSD が最小化されるようにします。

異なる数のポイントを処理するいくつかのアルゴリズムを知っていますが、それらはすべてタンパク質ベースです。つまり、バックボーンを一緒に整列させようとします (一部の連続したセグメントが別の連続したセグメントと整列するなど)。これは浮動小数点には役立ちません。宇宙で、何のつながりもありません。（わかりました、明確にするために、いくつかのポイントが接続されています。ただし、重ね合わせ中に無視したくない接続のないポイントがあります。）

私が見つけた唯一のアルゴリズムはDIP-OVLで、STRAP ソフトウェア モジュール (オープン ソース) にあります。コードを試してみましたが、動作が不安定なようです。適切な位置合わせが見つかる場合もあれば、単純な X 移動の後、いくつかの点のセットをそれ自体と位置合わせできない場合もあります。

そのような制限に対処するアルゴリズムを知っている人はいますか? パフォーマンスに問題がある場合、最大で ~10^2 から ~10^3 ポイントになります。

正直なところ、使用する目的関数はあまり明確ではありません。RMSD は、対応するポイント間の距離の RMS として定義されます。50 ポイントと 100 ポイントの 2 つのセットがあり、アルゴリズムがセット内の 1 つまたはいくつかのポイントと一致する場合、それらのいくつかのポイント間の結果の RMSD はゼロになりますが、全体的な重ね合わせはそれほど大きくない可能性があります。ポイントのすべてのペア間のRMSDは、より良い解決策ではありません（私は思います）。

私が考えることができる唯一のことは、セットYの各ポイントに対してセットXの最も近いポイントを見つけて（したがって、正確に最小（| X |、| Y |）の一致、たとえばその場合は50）、それらからRMSDを計算することです一致します。しかし、距離計算と 2 部一致の部分は、計算が複雑すぎてバッチで呼び出すことができないようです。その分野での助けも役に立ちます。

ありがとう！

4

3 に答える 3

2

あなたが言ったことは、「クラウドからクラウドへの登録」タスクのように見えます。たとえば、http ://en.wikipedia.org/wiki/Iterative_closest_pointとhttp://www.willowgarage.com/blog/2011/04/10/modular-components-point-cloud-registrationをご覧ください。オープン ソースのPoint Cloud Libraryでデータを操作して、それが機能するかどうかを確認できます。

于 2012-06-25T13:03:25.033 に答える
2

互いに対応する点のペアがわかっている場合は、線形最小二乗法(LLS) を使用して変換行列を復元できます。

LLS を検討する場合、通常はxinの近似値を求めますA*x = b。A転置を使用すると、 の代わりに を解くことができますx。

  1. ソースとターゲットの各ベクトルを「1」で拡張すると、< x , y z , 1>のようになります
  2. 式: A · x i = b i
  3. 複数のベクトルに拡張: A · X = B
  4. 転置: ( A · X ) T = B T
  5. 単純化: X T · A T = B T
  6. P = X T、Q = A T、およびR = B Tに置き換えます。結果: P · Q = R
  7. LLS の式Q ≈ ( P T · P ) -1 · P T · Rを適用します。
  8. 代用バック: A T ≈ ( X・X T ) -1・X・B T
  9. Aについて解き、次のように単純化します。A ≈ B · X T · ( X · X T ) -1

( B · X T ) および ( X · X T ) は、個々のベクトル ペアの外積を合計することによって繰り返し計算できます。

  • B・X T = ∑ b i・x i T
  • X · X T = ∑ x i · x i T
  • A ≈ (∑ b i · x i T ) · (∑ x i · x i T ) -1

行列は 4×4 よりも大きくならないため、アルゴリズムは余分なメモリを使用しません。

結果は必ずしもアフィンではありませんが、おそらく近似しています。さらに処理を加えることで、アフィンにすることができます。

于 2012-06-25T16:56:12.880 に答える