反復最近点

反復最近点法（ICP）^[1]^[2]^[3]^[4]は、2つの点群の差を最小化するアルゴリズムです。ICPは、異なるスキャンから2Dまたは3Dの表面を再構築したり、ロボットの位置を特定して最適な経路計画を実現したり（特に滑りやすい地形のために車輪の走行距離測定が信頼できない場合）、骨モデルを相互登録したりするためによく使用されます。

概要

反復最近点アルゴリズムは、1 つのポイントクラウド (参照またはターゲット) を固定したまま、もう 1 つのポイントクラウド (ソース) を変換して参照に最も一致するようにします。変換 (平行移動と回転の組み合わせ) は、エラーメトリック (通常は一致したペアの座標間の差の二乗の合計) を最小化するために反復的に推定されます。ICP は、必要な固定変換の初期推定を前提として、3 次元モデルを位置合わせする際に広く使用されているアルゴリズムの 1 つです。 ^[5] ICP アルゴリズムは、Chen と Medioni、^[3]および Besl と McKay によって最初に導入されました。^[2]

入力: 参照およびソースポイントクラウド、ソースを参照に合わせるための変換の初期推定 (オプション)、反復を停止するための基準。

出力: 洗練された変換。

基本的に、アルゴリズムの手順は次のようになります。^[5]

ソースポイントクラウド内の各ポイント (通常は密と呼ばれる頂点セット全体、または各モデルからの頂点のペアの選択) について、参照ポイントクラウド (または選択されたセット) 内の最も近いポイントを一致させます。
ルート平均二乗ポイントツーポイント距離メトリック最小化手法を使用して、回転と平行移動の組み合わせを推定します。これにより、各ソースポイントが前の手順で見つかった一致に最もよく位置合わせされます。この手順では、位置合わせの前にポイントに重み付けを行い、外れ値を拒否することもあります。
得られた変換を使用してソースポイントを変換します。
反復します（ポイントの再関連付けなど）。

Zhang ^[4]は、効率的な最近点計算のための修正k -dツリーアルゴリズムを提案している。この研究では、距離分布に基づく統計的手法を使用して、外れ値、遮蔽、出現、消失に対処し、サブセット間のマッチングを可能にしている。

ICPには多くのバリエーションがあり^[6] 、その中でポイントツーポイントとポイントツープレーンが最も人気があります。後者は通常、構造化された環境でより良いパフォーマンスを発揮します。^[7]^[8]

実装

MeshLab は、 ICP アルゴリズムの GNU General Public License 実装を含むオープンソースのメッシュ処理ツールです。
CloudCompare は、 ICP アルゴリズムの実装を含むオープンソースのポイントおよびモデル処理ツールです。GNU General Public License に基づいてリリースされています。
PCL（ポイントクラウドライブラリ）は、 n次元ポイントクラウドと3Dジオメトリ処理のためのオープンソースフレームワークです。ICPアルゴリズムのいくつかのバリエーションが含まれています。^[9]
ICP アルゴリズムのオープンソース C++ 実装は、VTK、ITK、Open3D ライブラリで利用できます。
libpointmatcher は、BSD ライセンスに基づいてリリースされたポイントツーポイントおよびポイントツープレーン ICP の実装です。
simpleICP は、さまざまな言語で ICP アルゴリズムのかなり単純なバージョンを実装したものです。

参照

ポイントセット登録

参考文献

^ Arun, Somani; Thomas S. Huang; Steven D. Blostein (1987). 「2つの3Dポイントセットの最小二乗フィッティング」. IEEE Pattern Analysis and Machine Intelligence . 9 (5): 698–700. CiteSeerX 10.1.1.467.9356 . doi :10.1109/TPAMI.1987.4767965. PMID 21869429. S2CID 8724100.
^ ab Besl, Paul J.; ND McKay (1992). 「3D 形状の登録方法」. IEEE Transactions on Pattern Analysis and Machine Intelligence . 14 (2): 239–256. doi :10.1109/34.121791.
^ ab Chen, Yang; Gerard Medioni (1991). 「複数の距離画像の登録によるオブジェクトモデリング」Image Vision Comput . 10 (3): 145–155. doi :10.1016/0262-8856(92)90066-C.
^ ab Zhang, Zhengyou (1994). 「自由形状曲線および曲面の登録のための反復ポイントマッチング」International Journal of Computer Vision . 13 (12): 119–152. CiteSeerX 10.1.1.175.770 . doi :10.1007/BF01427149. S2CID 14673939.
^ ab Rusinkiewicz, Szymon; Marc Levoy (2001). ICP アルゴリズムの効率的なバリエーション。3D デジタルイメージングおよびモデリングに関する第 3 回国際会議の議事録。ケベック市、ケベック州、カナダ。pp. 145–152。doi :10.1109/IM.2001.924423 。
^ Pomerleau, François; Colas, Francis; Siegwart, Roland (2015). 「モバイルロボットのためのポイントクラウド登録アルゴリズムのレビュー」.ロボティクスの基礎と動向. 4 (1): 1–104. CiteSeerX 10.1.1.709.2212 . doi :10.1561/2300000035. S2CID 62361231.
^ Kok-Lim Low (2004 年 2 月)。「点対平面 ICP 表面レジストレーションの線形最小二乗最適化」(PDF)。Comp.nys.edu.sg 。技術レポート TR04-004、ノースカロライナ大学チャペルヒル校コンピューターサイエンス学部。2017年 2 月 27 日閲覧。
^ François Pomerleau、Francis Colas、Roland Siegwart、およびStéphane Magnenat。実世界のデータセットでのICPバリアントの比較。Autonomous Robots、34(3)、133〜148ページ、DOI: 10.1007/s10514-013-9327-2、2013年4月。
^ Holz, Dirk; Ichim, Alexandru E.; Tombari, Federico; Rusu, Radu B.; Behnke, Sven (2015). 「ポイントクラウドライブラリへの登録：3Dでの位置合わせのためのモジュラーフレームワーク」IEEE Robotics Automation Magazine . 22 (4): 110–124. doi :10.1109/MRA.2015.2432331. S2CID 2621807.

[arun1987-1] Arun, Somani; Thomas S. Huang; Steven D. Blostein (1987). 「2つの3Dポイントセットの最小二乗フィッティング」. IEEE Pattern Analysis and Machine Intelligence . 9 (5): 698–700. CiteSeerX 10.1.1.467.9356 . doi :10.1109/TPAMI.1987.4767965. PMID 21869429. S2CID 8724100.

[autogenerated239-2] Besl, Paul J.; ND McKay (1992). 「3D 形状の登録方法」. IEEE Transactions on Pattern Analysis and Machine Intelligence . 14 (2): 239–256. doi :10.1109/34.121791.

[autogenerated145-3] Chen, Yang; Gerard Medioni (1991). 「複数の距離画像の登録によるオブジェクトモデリング」Image Vision Comput . 10 (3): 145–155. doi :10.1016/0262-8856(92)90066-C.

[zhang_IJCV_1994-4] Zhang, Zhengyou (1994). 「自由形状曲線および曲面の登録のための反復ポイントマッチング」International Journal of Computer Vision . 13 (12): 119–152. CiteSeerX 10.1.1.175.770 . doi :10.1007/BF01427149. S2CID 14673939.

[rusinkiewicz145-5] Rusinkiewicz, Szymon; Marc Levoy (2001). ICP アルゴリズムの効率的なバリエーション。3D デジタルイメージングおよびモデリングに関する第 3 回国際会議の議事録。ケベック市、ケベック州、カナダ。pp. 145–152。doi :10.1109/IM.2001.924423 。

[reviewPointCloud-6] Pomerleau, François; Colas, Francis; Siegwart, Roland (2015). 「モバイルロボットのためのポイントクラウド登録アルゴリズムのレビュー」.ロボティクスの基礎と動向. 4 (1): 1–104. CiteSeerX 10.1.1.709.2212 . doi :10.1561/2300000035. S2CID 62361231.

[7] Kok-Lim Low (2004 年 2 月)。「点対平面 ICP 表面レジストレーションの線形最小二乗最適化」(PDF)。Comp.nys.edu.sg 。技術レポート TR04-004、ノースカロライナ大学チャペルヒル校コンピューターサイエンス学部。2017年 2 月 27 日閲覧。

[8] François Pomerleau、Francis Colas、Roland Siegwart、およびStéphane Magnenat。実世界のデータセットでのICPバリアントの比較。Autonomous Robots、34(3)、133〜148ページ、DOI: 10.1007/s10514-013-9327-2、2013年4月。

[PCL-Tutorial-9] Holz, Dirk; Ichim, Alexandru E.; Tombari, Federico; Rusu, Radu B.; Behnke, Sven (2015). 「ポイントクラウドライブラリへの登録：3Dでの位置合わせのためのモジュラーフレームワーク」IEEE Robotics Automation Magazine . 22 (4): 110–124. doi :10.1109/MRA.2015.2432331. S2CID 2621807.