7

3D ポイントクラウドで回転軸を自動検出しようとしています。

つまり、小さな 3D ポイントクラウドを取得し、単一の回転軸を選択して、異なる回転角度でポイントのコピーをいくつか作成すると、より大きなポイントクラウドが得られます。

私のアルゴリズムへの入力はより大きな点群であり、目的の出力は単一の対称軸です。そして最終的には、互いの回転であるポイント間の対応を計算します。

大きな点群のサイズは 100K ポイントのオーダーで、作成される回転コピーの数は不明です。

私の場合、回転角度には一定のデルタがありますが、必ずしも 360 度に及ぶとは限りません。たとえば、私は 0、20、40、60 を持っているかもしれません。または、0、90、180、270 を持っているかもしれません。それを検出します）。

これはコンピューター ビジョンの問題のようですが、軸を正確に見つける方法がわかりません。通常、入力は非常にクリーンで、フロートの精度に近くなります。

大きなポイントクラウドを作成するために回転/コピーされた元の小さなポイントクラウドはありません。私は、データがほとんどノイズのない合成データであることを知っています (通常、別のプログラムの出力です)。

残念ながら、軸に沿って点が重複していないため、小さな雲で可能な点の数を簡単に計算することはできません。どの点が軸に沿っているかがわかっていれば、考えられる要因を考え出すことができますが、その場合、問題はすでに解決されています。

--

皆さんの提案に感謝します。私の最終的なアルゴリズムは、k-nn メトリックを使用して一致するポイントのクリークを考え出そうとしているようです。各クリークは軸を与えます。次に、RANSAC を使用して、軸をすべてのクリークの結果に適合させることができます。

4

9 に答える 9

2

次のアプローチが役立つかもしれませんが、それはデータの特定によって異なります。これは、隣接する位置間のギャップが十分に大きく（20度で十分）、小さな点群が表面に近い（最後の点群を克服できる）という仮定に基づいています。ローカル機能マッチング（コンピュータービジョンで一般的な手法）を使用することをお勧めします。

まず、大規模なクラウドの各ポイントについて、ローカル記述子（画像のSIFTやSURFなど）を計算する必要があります。点群で最も人気のあるものはスピン画像です：

Johnson、A。、＆Hebert、M.（1999）乱雑な3Dシーンでの効率的なオブジェクト認識のためのスピン画像の使用。パターン分析とマシンインテリジェンスに関するIEEEトランザクション、21（5）、433–449。Citeseer。http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8816&rep=rep1&type=pdfから取得。

ここでは、高度な変更が使用されます。

Endres、F.、Plagemann、C.、Stachniss、C。、＆Burgard、W.（2009）潜在的ディリクレ割り当てを使用した範囲データからのオブジェクトクラスの教師なし発見。ロボット工学：科学とシステム。米国シアトル。

計算が難しい場合は、識別力を大幅に失うことなく次元を減らす方法を尋ねてください。私は一度それを行いました。

次に、記述子を一致させる必要があります。つまり、高次元空間で各記述子に最も近い隣接ノードを見つける必要があります。小さな雲が3回転した場合、3つの最も近い隣人がいるはずです。ただし、雲の自己交差のため、一致にはおそらくノイズが含まれます。大量の一致にうまく適合する軸を見つける必要があります（すべてではありませんが）。ここでは、RANSACのようなロバストフィッティングを使用できます（見つかった一致に対する軸位置の尤度を定義するために、いくつかの計算を行う必要があります）。他の人が提案した方法とは異なることに注意してください。元のポイントではなく、記述子に基づいて、平面のファミリではなく1つの線だけをフィットさせる必要があります（RANSACは、4〜5の正しいポイントと100Kの外れ値を持つ平面をフィットできない可能性があります）。

また注意してください：

表面を近似しない​​小さなスキャンがある場合は、スピン画像ではなく、別の回転不変記述子を考え出す必要があります。

法線を計算して取得を行うには、次のライブラリを確認してください：http: //graphics.cs.msu.ru/en/science/research/3dpoint/lidark（メジャーリリースは間もなくリリースされます）。

于 2010-04-16T11:19:40.367 に答える
2

以下は、3つ以上のコピーがあることを前提としています。大きな点群の凸包を考えてみましょう。平行な2つの面を見つけます。回転軸はこれらに垂直になります。複数のペアが見つかった場合は、各方向をテストするだけです。

明らかに、軸に応じた最も極端な点が軸上にある場合、これは機能しませんが、一般的なケースでは、これは非常にまれです。

于 2010-04-17T06:43:04.567 に答える
1

任意の点を選択し、そこから等距離にある他の 2 つの点を見つけます。これは O(n^2) の最悪のケースを取る必要がありますが、ヒューリスティックはこれを大幅に減らすことができます。これらの 3 点は、円を一意に決定します。1 番目または 3 番目のポイントから同じ距離に 4 番目のポイントがある場合、円に対する信頼度が大幅に向上します。

円の中心は軸上の点であり、円の法線ベクトルは軸の方向ベクトルです。

軸を指定すると、回転間の角度を決定し、他の点で推測を確認できます。もし間違っていたら、別のポイントを選んで最初からやり直してください。

編集：ちなみに、明らかにこれは非決定論的ですが、ポイントデータがあなたが言うほどきれいで、優れたヒューリスティックを使用している場合、それは非常に正確なはずです.

于 2010-04-14T18:47:27.660 に答える
0

クレイジーなアイデア...

同じ軸を中心に同じ点を数回回転させると、すべての点が同じ平面上に配置されます。データセットによっては、ransac メソッドを使用してこの平面を検出できる場合があります。

回転軸はこの平面に対して垂直になり、軸の向きが決定されると、軸の位置を決定するのは比較的簡単になります。

于 2010-04-15T17:28:56.343 に答える
0

1) 大きな点群の重心 C が見つかった場合、元の回転軸はその点を通過する必要があります。

気にしないでください。回転が完全な円にまたがらない可能性があるという要件は見当たりませんでした。20,40,60 の例では、重心は回転軸上にありません。

たぶん、次の参考文献が役立つでしょうか？

「部分サンプリングによる回転面の再構成」 http://portal.acm.org/citation.cfm?id=980064

于 2010-04-14T18:08:54.087 に答える
0

いくつかのポイント:)

  1. 回転しない初期点が 1 つある場合、無限の数の軸があります。
  2. 1回回転した1つの初期点がある場合、無限の数の軸もあります。
  3. 1 つの初期点があり、それを 2 回回転すると、3 つの点が平面を一意に決定するため、軸を見つけることができます。3 つの点 (最初の 1 つ + 回転した 2 つ) のそれぞれから等距離にある点を通る垂直線が軸です。
  4. 360 度回転しても意味がないことに注意してください。
  1. クラウドから任意の 1 点 (P) を選択します。
  2. 点 P の軌跡 (L) をトレースします (P はある軸を中心に回転しているため、L は円である必要があります)。
  3. その中心を通る円(L)の平面に垂直なのが雲の回転軸です。

つまり、剛体の回転軸は、物体の任意の単一粒子の回転軸と同じです。他のすべての点を気にする必要はありません。

于 2010-04-14T18:17:36.453 に答える
0

考慮すべき点が 2 つあります。

  1. 点群の角度範囲。
  2. 回転角度。

ここで、(回転 > スパン) の場合、サブ パターンを探し、その発生に基づいて、より大きなパターンに一致させる必要があるため、解決策はより単純です。

(回転 < スパン) の場合、領域内 (最初の回転の後、最後の回転の前) には、対称角度 = スパン角度の対称点群がまだあるため、エッジ効果を見落とす必要があります。 ; 上記の場合のように。

自分がどのカテゴリーに分類されるかわからない場合は、2 番目のカテゴリーを想定しても安全です。

前に述べたように、RANSAC は、時間がかからず、適切な結果が得られるため、パターン マッチングの最良の手段です。あなたが残した唯一の問題は、初期化中のミニ点群のスパンの推定角度です。この見積もりを行うのは困難です。したがって、十分な計算能力/時間があれば、1 度ずつ繰り返すことをお勧めします。適度な5度から45度まで。結果が収束し始めると、角度の精度が上がります。

于 2010-04-17T07:06:51.237 に答える
0

ステレオ ビジョンで 2 つの画像間のホモグラフィを計算するために使用される手法を見てみましょう。点群のセットに関する問題は、同じオブジェクト/シーンの複数の画像で点を一致させることに似ているようです。RANSAC アルゴリズムを適用して、点群のセット間の変換を計算できるようです。

于 2010-04-14T19:02:58.423 に答える
0

元の点群は小さいため、最も単純なソリューションは RANSAC である可能性があります。

  1. 無作為に3点選ぶ
  2. これらの点の回転軸を計算します (円に垂直で中心を通る線)
  3. 他の点は合っていますか？
  4. そうでない場合は、正しい軸が見つかるまで繰り返します

正しい推定の確率は 1/((n-1)(n-2)) です。ここで、n は元の雲の点の数です。各テストは非常に迅速に実行できるため、これは有用なアプローチになる可能性があります。

于 2010-04-20T21:43:59.903 に答える