正規分布の変換

正規分布変換( NDT )は、2003 年にテュービンゲン大学で働いていた Peter Biber と Wolfgang Straßer によって導入された点群登録 アルゴリズムです。

このアルゴリズムは、まず最初のポイント クラウドに区分 正規分布を関連付け、特定の空間座標でクラウドに属するポイントをサンプリングする確率を与え、次に、変換パラメータの関数としてそのような分布上の 2 番目のポイント クラウドの尤度を最大化することにより、2 番目のポイント クラウドを最初のポイント クラウドにマッピングする変換を見つけることによって、2 つのポイント クラウドを登録します。

このアルゴリズムはもともと、同時位置推定とマッピング（SLAM）と相対位置追跡における2Dポイントクラウドマップマッチングのために導入されましたが^{[1] 、3Dポイントクラウドに拡張され[2] 、}コンピュータービジョンとロボット工学の分野で広く応用されています。 NDTは非常に高速で正確なため、大規模データへの適用に適していますが、初期化の影響を受けやすく、十分に正確な初期推測値を必要とするため、通常は粗い位置から細かい位置への位置合わせ戦略で使用されます。^{[3] [4] [5]}

ポイントクラウドに関連付けられた NDT 関数は、空間を規則的なセルに分割することによって構築されます。各セルについて、セル内に含まれるクラウドのポイントの平均と共分散を定義することができます。セル内の特定の空間位置でポイントをサンプリングする確率密度は、正規分布によって与えられます。 ${\displaystyle \textstyle \mathbf {q} ={\frac {1}{n}}\sum _{i}\mathbf {x_{i}} }$${\displaystyle \textstyle \mathbf {S} ={\frac {1}{n}}\sum _{i}\left(\mathbf {x} _{i}-\mathbf {q} \right)\left (\mathbf {x} _{i}-\mathbf {q} \right)^{\top }}$${\displaystyle n}$${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}$${\displaystyle \mathbf {x} }$

${\displaystyle e^{-{\frac {1}{2}}\left(\mathbf {x} -\mathbf {q} \right)^{\top }\mathbf {S} ^{-1}\left(\mathbf {x} -\mathbf {q} \right)}}$。

2つの点群は、回転行列と並進ベクトルを用いたユークリッド変換 によってマッピングできる。${\displaystyle f}$ ${\displaystyle \mathbf {R} }$${\displaystyle \mathbf {t} }$

${\displaystyle f_{\mathbf {R} ,\mathbf {t} }(\mathbf {x} )=\mathbf {R} \mathbf {x} +\mathbf {t} }$

回転角度と移動コンポーネントによってパラメータ化され、2 番目のクラウドから 1 番目のクラウドにマッピングされます。

アルゴリズムは、最初の点群の非破壊検査に基づく損失関数に関して、2番目の点群を最初の点群にマッピングする変換のパラメータを 最適化することによって2つの点群を登録し、次の問題を解決します。

${\displaystyle \arg \min _{\mathbf {R} ,\mathbf {t} }\left\{-\sum _{i}\operatorname {NDT} \left(f_{\mathbf {R} ,\mathbf {t} }\left(\mathbf {x_{i}} \right)\right)\right\}}$

ここで、損失関数は、 2番目のクラウド内のすべての点に変換を適用し、各変換された点でのNDTの値を合計することによって得られる否定尤度を表します。損失は区分的に連続かつ微分可能であり、勾配ベースの方法で最適化できます（元の定式化では、著者はニュートン法を使用しています）。 ${\displaystyle f_{\mathbf {R} ,\mathbf {t} }(\mathbf {x} )}$

セルの離散化の影響を減らすために、空間を複数の重なり合うグリッドに分割し、空間方向に沿ってセルサイズの半分ずつシフトし、特定の位置での尤度を各グリッドによって誘発される非破壊検査の合計として計算する手法があります。^[1]

• Biber, Peter; Straßer, Wolfgang (2003)。「正規分布の変換: レーザースキャンマッチングへの新しいアプローチ」。2003 IEEE/RSJ 国際インテリジェントロボットおよびシステム会議 (IROS 2003) の議事録 (カタログ番号 03CH37453)。第 3 巻。
• Cheng, Liang; Chen, Song; Liu, Xiaoqiang; Xu, Hao; Wu, Yang; Li, Manchun; Chen, Yanming (2018). 「レーザースキャンポイントクラウドの登録：レビュー」.センサー. 18 (5). Multidisciplinary Digital Publishing Institute: 1641. Bibcode :2018Senso..18.1641C. doi : 10.3390/s18051641 . PMC  5981425 . PMID  29883397.
• Dong, Zhen; Liang, Fuxun; Yang, Bisheng; Xu, Yusheng; Zang, Yufu; Li, Jianping; Wang, Yuan; Dai, Wenxia; Fan, Hongchao; Hyyppä, Juha (2020). 「大規模な地上レーザースキャナーポイントクラウドの登録：レビューとベンチマーク」. ISPRS Journal of Photogrammetry and Remote Sensing . 163. Elsevier: 327–342. Bibcode :2020JPRS..163..327D. doi :10.1016/j.isprsjprs.2020.03.013. S2CID  216449537.
• Li, Leihui; Wang, Riwei; Zhang, Xuping (2021)。「ポイントクラウドレジストレーションに関するチュートリアルレビュー：原理、分類、比較、および技術的課題」。工学における数学的問題。2021年。Hindawi。
• Magnusson, Martin (2009)。3次元正規分布変換: 登録、表面分析、ループ検出のための効率的な表現(Ph.D.)。エレブルー大学。

• 「NDT アルゴリズムを使用して 2 つの点群を登録する」。MathWorks。