【論文読み会】3D Registration with Maximal Cliques

2023年度論文読み会#10 (3Dデータ論文読み会#4) 極大クリークを用いた点群レジストレーション 京都大学物理工学科卒 上野裕太 元論文 3D Registration with Maximal Cliques https://arxiv.org/abs/2305.10854 0

• https://arxiv.org/abs/2305.10854

3D Registration with Maximal Cliques 目次 01 論文の概要 02 先行研究 03 提案手法 04 実験結果 1

1. 論文の概要 2

1. 論文の概要 1.1 点群レジストレーション この論文のタスクは→点群レジストレーション 点群レジストレーションとは？ ● 2つの異なる視点からの点群を並進・回転させ、上手く重なるようにすること なぜ必要？ ● 物体を1度に360度スキャニングするのは困難 ● 複数回に分けて、上手く統合する必要がある 用途 ● 3Dオブジェクトデータの作成、SLAMの自己位置推定 https://en.wikipedia.org/wiki/Point-set_registration 3

• https://en.wikipedia.org/wiki/Point-set_registration

1. 論文の概要 1.2 論文手法 この論文では何を提案した？→幾何学的な点群レジストレーション手法  NNを使わない幾何学的な手法  極大クリーク（Maximal Clique）を用いて位置合わせの候補点を抽出  NNを用いた局所特徴量抽出フレームワークと組み合わせるとより精度向上  3DMatch/3DLoMatchデータセットにおいて点群レジストレーションのSoTAを達成 4

1. 論文の概要 1.3 データセット U3M：https://link.springer.com/article/10.1007/s11263-005-3221-0 ● 「A novel representation and feature matching algorithm for automatic pairwise registration of range images」で用いられたオブジェクトスケールデータセット 3DMatch：https://3dmatch.cs.princeton.edu/ ● 「3DMatch: Learning Local Geometric Descriptors from RGB-D Reconstructions」で用いられた屋内 スケールデータセット 3DLoMatch：https://arxiv.org/abs/2011.13005  「PREDATOR: Registration of 3D Point Clouds with Low Overlap」で用いられた屋内スケールデータセ ット  3DMatchのうち、overlap（2つの点群の重なり領域）が10~30%のものだけを集めた KITTI dataset：https://www.cvlibs.net/datasets/kitti/ ● 自動運転用に用いられる屋外スケールデータセット 5

• https://link.springer.com/article/10.1007/s11263-005-3221-0
• https://3dmatch.cs.princeton.edu/
• https://arxiv.org/abs/2011.13005
• https://www.cvlibs.net/datasets/kitti/

1. 論文の概要 補足：3DLoMatchのデータ例 6

1. 論文の概要 補足：書籍紹介 「詳解3次元点群処理」  点群レジストレーションや局所特徴抽出、 PointNetのことなどが実装と共に乗っている  理論と共に書いていてわかりやすいのでオススメ 7

2. 先行研究 8

2. 先行研究 2.1 ICP 「Least-Squares Fitting of Two 3-D Point Sets (1987)」で提案された古典的なレジストレーション手法 ● 近傍点探索により2つの点群間の初期対応関係を求める ● 特異値分解により回転・並進を行う同次変換行列を求める ● 同次変換行列により変換された点群で再び近傍点探索により対応関係を求める ● 2乗平均誤差（MAE）などが収束するまで以上の工程を繰り返す 点群には、 ノイズなどが含まれる ノイズの原因 外光、センサ特性、オクルージョン ソース ターゲット 9

2. 先行研究 2.1 ICP 「Least-Squares Fitting of Two 3-D Point Sets (1987)」で提案された古典的なレジストレーション手法 ● 近傍点探索により2つの点群間の初期対応関係を求める ● 特異値分解により回転・並進を行う同次変換行列を求める ● 同次変換行列により変換された点群で再び近傍点探索により対応関係を求める ● 2乗平均誤差（MAE）などが収束するまで以上の工程を繰り返す 初期対応関係 𝑠𝑠 𝒑𝒑1𝑠𝑠 , 𝒑𝒑1𝑡𝑡 , 𝒑𝒑2𝑠𝑠 , 𝒑𝒑𝑡𝑡2 , … , 𝒑𝒑𝑁𝑁 , 𝒑𝒑𝑡𝑡𝑁𝑁 𝒑𝒑𝑠𝑠 ∈ 𝑃𝑃 𝑠𝑠 : ソースの点 𝒑𝒑𝑠𝑠 ∈ 𝑃𝑃 𝑠𝑠 : ターゲットの点 近傍点探索は、kd-treeを用いると高速化することができる 参考： https://qiita.com/RAD0N/items/7a192a4a5351f481c99f 10

• https://qiita.com/RAD0N/items/7a192a4a5351f481c99f

2. 先行研究 2.1 ICP 「Least-Squares Fitting of Two 3-D Point Sets (1987)」で提案された古典的なレジストレーション手法 ● 近傍点探索により2つの点群間の初期対応関係を求める ● 特異値分解により回転・並進を行う同次変換行列を求める ● 同次変換行列により変換された点群で再び近傍点探索により対応関係を求める ● 2乗平均誤差（MAE）などが収束するまで以上の工程を繰り返す 目的関数 𝑇𝑇 = 𝑅𝑅 0 𝑁𝑁 𝒕𝒕 1 𝑇𝑇 ∗ = argmin � 𝒑𝒑𝑡𝑡𝑖𝑖 − 𝑇𝑇𝒑𝒑𝑖𝑖𝑠𝑠 𝑇𝑇 𝑖𝑖=1 𝑇𝑇 ∗ を構成する𝑅𝑅∗ , 𝒕𝒕∗ を求める 𝝁𝝁𝑝𝑝𝑠𝑠 𝑁𝑁 1 = � 𝑝𝑝𝑖𝑖𝑠𝑠 , 𝑁𝑁 𝑖𝑖=1 𝒒𝒒𝑖𝑖𝑠𝑠 = 𝒑𝒑𝑖𝑖 − 𝝁𝝁𝑝𝑝𝑠𝑠 , 重心を求める 2 𝑁𝑁 1 𝜇𝜇𝑝𝑝𝑡𝑡 = � 𝒑𝒑𝑡𝑡𝑖𝑖 𝑁𝑁 𝑖𝑖=1 𝒒𝒒𝑡𝑡𝑖𝑖 = 𝒑𝒑𝑖𝑖 − 𝝁𝝁𝑝𝑝𝑡𝑡 𝑁𝑁 𝐻𝐻 = � 𝒒𝒒𝑖𝑖𝑠𝑠 𝒒𝒒𝑡𝑡𝑖𝑖 𝑖𝑖=1 T 𝐻𝐻の特異値分解を𝐻𝐻 = 𝑈𝑈Λ𝑉𝑉 T として、 𝑅𝑅∗ = 𝑉𝑉𝑈𝑈 T 𝒕𝒕∗ = 𝝁𝝁𝑡𝑡𝑝𝑝 − 𝑅𝑅𝝁𝝁𝑝𝑝𝑠𝑠 参考： https://qiita.com/shirokumaneko/items /ff1a1a8020d48299573b 11

• https://qiita.com/shirokumaneko/items

2. 先行研究 2.1 ICP 「Least-Squares Fitting of Two 3-D Point Sets (1987)」で提案された古典的なレジストレーション手法 ● 近傍点探索により2つの点群間の初期対応関係を求める ● 特異値分解により回転・並進を行う同次変換行列を求める ● 同次変換行列により変換された点群で再び近傍点探索により対応関係を求める ● 2乗平均誤差（MAE）などが収束するまで以上の工程を繰り返す 新しい対応点 12

2. 先行研究 2.1 ICP 「Least-Squares Fitting of Two 3-D Point Sets (1987)」で提案された古典的なレジストレーション手法 ● 近傍点探索により2つの点群間の初期対応関係を求める ● 特異値分解により回転・並進を行う同次変換行列を求める ● 同次変換行列により変換された点群で再び近傍点探索により対応関係を求める ● 2乗平均誤差（MAE）などが収束するまで以上の工程を繰り返す MAE (Mean Average Error) 𝑁𝑁 𝑀𝑀𝑀𝑀𝑀𝑀 = � 𝒑𝒑𝑖𝑖𝑠𝑠 − 𝒑𝒑𝑡𝑡𝑖𝑖 MSE (Mean Squared Error) インライア数 ● 𝑖𝑖=1 𝑁𝑁 𝑀𝑀𝑀𝑀𝑀𝑀 = � 𝒑𝒑𝑖𝑖𝑠𝑠 − 𝒑𝒑𝑡𝑡𝑖𝑖 𝑖𝑖=1 2 誤差が一定値以下の点はいくつあるか 13

2. 先行研究 2.2 ICPの問題点 ● 初期対応点が上手くとれているかに精度が大きく依存する ● 大きくずれていたり、ノイズが多いと局所解に収束してしまう ● 大まかな位置合わせが出来ると嬉しい ● 局所特徴量による対応付け ● 点数が増えると計算量が多くなる ● 全ての点を使わず限られた点の対応関係のみを用いる ● キーポイントの抽出 局所特徴量 ● 同じ物体の同じ対応した点同士なら同じような特徴量が得られる ● 視点や向きの違い、オクルージョン、ノイズなどに頑健なことが求められる キーポイント 物体上で同じ場所を示す 対応する2点の局所特徴 量は同じ ● 点群の中でも特徴的なパターンを持ち、他の点との区別がつきやすい点 14

2. 先行研究 2.3 局所特徴量（FPFH） FPFH (Fast Point Feature Histograms) (2009) https://ieeexplore.ieee.org/document/5152473 ● PFHをより高速化したもの PFH ● ある特徴点𝒑𝒑のPFHは，その𝑘𝑘個の近傍点での全ての組み合わせ(𝒑𝒑𝑖𝑖 , 𝒑𝒑𝑗𝑗 )に対して以下を計算する 𝛼𝛼 = 𝒑𝒑𝑗𝑗 − 𝒑𝒑𝑖𝑖 × 𝒏𝒏𝑖𝑖 � 𝒏𝒏𝑗𝑗 𝒏𝒏𝑖𝑖 � 𝒑𝒑𝑗𝑗 − 𝒑𝒑𝑖𝑖 𝜙𝜙 = 𝒑𝒑𝑗𝑗 − 𝒑𝒑𝑖𝑖 𝜃𝜃 = arctan ● 𝛼𝛼, 𝜙𝜙, 𝜃𝜃のヒストグラムを計算する 𝒏𝒏𝑖𝑖 × 𝒑𝒑𝑗𝑗 − 𝒑𝒑𝑖𝑖 × 𝒏𝒏𝑖𝑖 � 𝒏𝒏𝑗𝑗 , 𝒏𝒏𝑖𝑖 × 𝒏𝒏𝑗𝑗 ● 計算量は𝑂𝑂 𝑘𝑘 2 15

• https://ieeexplore.ieee.org/document/5152473

2. 先行研究 2.3 局所特徴量（FPFH） FPFH (Fast Point Feature Histograms) (2009) https://ieeexplore.ieee.org/document/5152473 ● FPFHでは特徴点𝒑𝒑と近傍点𝑘𝑘個の間のみで先ほどのパラメータ𝛼𝛼, 𝜙𝜙, 𝜃𝜃を計算しヒストグラム化する ● このヒストグラムをSPFH(Simplified Point Feature Histogram)と呼ぶ ● FPFHはSPFHを用いて以下のように計算される 1 1 FPFH 𝒑𝒑 = SPFH 𝒑𝒑 + � SPFH 𝒑𝒑𝑖𝑖 𝑘𝑘 𝜔𝜔𝑖𝑖 ● 𝜔𝜔𝑖𝑖 は何かしらの距離関数を用いた距離パラメータ ● 計算量は𝑂𝑂(𝑘𝑘) 𝑘𝑘 𝑖𝑖=1 16

• https://ieeexplore.ieee.org/document/5152473

2. 先行研究 2.3 局所特徴量（FCGF） FCGF (Fully Convolutional Geometric Features) (2019) https://github.com/chrischoy/FCGF?tab=readme-ov-file ● 3D畳み込みを用いたU-Netにより特徴量を抽出していく ● LossにはHardest-contrastive LossやHardest-triplet Lossを用いる 17

• https://github.com/chrischoy/FCGF?tab=readme-ov-file

2. 先行研究 2.3 局所特徴量（FCGF） FCGF (Fully Convolutional Geometric Features) (2019) https://github.com/chrischoy/FCGF?tab=readme-ov-file ● 3D畳み込みにより特徴量を抽出していく ● LossにはHardest-contrastive LossやHardest-triplet Lossを用いる 18

• https://github.com/chrischoy/FCGF?tab=readme-ov-file

2. 先行研究 2.4 RANSAC ランダムサンプリングした点に対して処理を行い、精度が良くなるまで試行する ● データをランダムにサンプリング ● モデルを学習する ● 全てのデータに対して誤差を計算 ● 誤差をもとにインライアとアウトライアに分ける ● インライアのみでモデルの性能を評価する ● 再びランダムサンプリングして性能を評価を繰り返す https://qiita.com/kazetof/items/b3439d9258cc85ddf66b 19

• https://qiita.com/kazetof/items/b3439d9258cc85ddf66b

2. 先行研究 2.5 その他の手法 キーポイント抽出 ● Harris3D (2011)：輝度の変化をもとにしたコーナー検出 ● D3Feat (2020)：3次元畳み込みネットワークによるキーポイント検出 インライアとアウトライアの区別 ● PointDSC (2021) ● Deep Global Registration (2020) より高精度の局所特徴量抽出 ● SpinNet (2020) : 回転に頑健な特徴量の抽出手法の提案 ● GeoTransformer (2022)：ロバストなスーパーポイントマッチングのために幾何学的特徴を学習 End-to-Endによるレジストレーション ● 3DRegNet (2019)：変換行列を行う回帰もNNを用いて行う 20

3.提案手法 21

3. 提案手法 3.1 手順の概要 ● FPFHやFCGFなどにより局所特徴量を求め、初期対応関係を構築する ● 互換性グラフを構築する ● 互換性グラフの極大クリークを求める ● 極大クリークのうち重要度の高いクリークを選択する ● 各クリークに対してSVDにより同次変換行列を求める ● 各変換についてMAEを計算し、最も誤差の少ないものを選択する 22

3. 提案手法 3.2 初期対応関係 ● FPFHやFCGFなどにより局所特徴量を求め、初期対応関係を構築する 局所特徴量のノルムを計算して、対応関係を構築する ● 対応集合を𝐂𝐂𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 = 𝒄𝒄 とする ● 𝒄𝒄 = 𝒑𝒑𝑠𝑠 , 𝒑𝒑𝑡𝑡 , 𝒑𝒑𝑠𝑠 ∈ P 𝑠𝑠 , 𝒑𝒑𝑡𝑡 ∈ P 𝑡𝑡 , P 𝑠𝑠 はソース点群でP 𝑡𝑡 がターゲット点群 ● ノルムの近い特徴量を探すのはkd-treeを用いると早い 23

3. 提案手法 3.3 互換性グラフ ● 互換性グラフを構築する 互換性グラフは以下のように定義される ● 各ペア𝒄𝒄をノードとして，ノード間の距離𝑆𝑆𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 は以下で定義される 𝑆𝑆𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝒄𝒄𝑖𝑖 , 𝒄𝒄𝑗𝑗 = 𝒑𝒑𝑖𝑖𝑠𝑠 − 𝒑𝒑𝑗𝑗𝑠𝑠 − 𝒑𝒑𝑡𝑡𝑖𝑖 − 𝒑𝒑𝑡𝑡𝑗𝑗 ● これを以下の式で，ノードの重みに変換する（重みが大きいほど点間の結びつきが強固） 2 𝑆𝑆𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝒄𝒄𝑖𝑖 , 𝒄𝒄𝑗𝑗 , 𝑑𝑑𝑐𝑐𝑐𝑐𝑐𝑐 は距離パタメータ 𝑆𝑆𝑐𝑐𝑐𝑐𝑐𝑐 𝒄𝒄𝑖𝑖 , 𝒄𝒄𝑗𝑗 = exp − 2 2𝑑𝑑𝑐𝑐𝑐𝑐𝑐𝑐 ● 𝑆𝑆𝑐𝑐𝑐𝑐𝑐𝑐 が一定の閾値𝑡𝑡𝑐𝑐𝑐𝑐𝑐𝑐 以上だとエッジの重みを𝒆𝒆𝑖𝑖𝑖𝑖 = 𝑆𝑆𝑐𝑐𝑐𝑐𝑐𝑐 ，それ以下だと𝒆𝒆𝑖𝑖𝑖𝑖 として隣接行列𝐖𝐖𝐹𝐹𝐹𝐹𝐹𝐹 を構築 ● 𝐖𝐖𝐹𝐹𝐹𝐹𝐹𝐹 からさらに以下の式で𝐖𝐖𝑆𝑆𝑆𝑆𝑆𝑆 を計算 𝐖𝐖𝑆𝑆𝑂𝑂𝑂𝑂 = 𝐖𝐖𝐹𝐹𝑂𝑂𝑂𝑂 ⨀ 𝐖𝐖𝐹𝐹𝐹𝐹𝐹𝐹 × 𝐖𝐖𝐹𝐹𝐹𝐹𝐹𝐹 ● ⨀は行列の要素同士の積を表す 𝒄𝒄𝑖𝑖 𝒆𝒆𝑖𝑖𝑖𝑖 𝒄𝒄𝑗𝑗 24

3. 提案手法 3.3 互換性グラフ 𝐖𝐖𝑆𝑆𝑂𝑂𝑂𝑂 は𝐖𝐖𝐹𝐹𝑂𝑂𝑂𝑂 よりもより疎な行列となる https://arxiv.org/abs/2203.14453 ● 強い結びつきのある部分が強調される 𝐖𝐖𝐹𝐹𝑂𝑂𝑂𝑂 𝐖𝐖𝑆𝑆𝑂𝑂𝑂𝑂 25

• https://arxiv.org/abs/2203.14453

3. 提案手法 3.4 極大クリーク ● 互換性グラフの極大クリークを求める クリーク グラフの極大クリークを求める ● NP困難の問題 ● 修正BronKerboschアルゴリズムにより求める 𝑑𝑑 3 ● 計算量𝑂𝑂(𝑑𝑑 𝑛𝑛 − 𝑑𝑑 3 )で求まる．𝑛𝑛はノードの数．𝑑𝑑はグラフの縮退度 クリーク ● 任意の2ノード間がエッジで結ばれているノードの集合 極大クリーク 極大クリーク ● いかなるクリークにも内包されないクリーク 最大クリーク ● 極大クリークの中でもっとも最大のもの 最大クリーク 26

3. 提案手法 3.5 クリーク選択 ● 極大クリークのうち重要度の高いクリークを選択する 以下の指標でクリークを選択する ● クリーク𝐂𝐂𝑖𝑖 = 𝐕𝐕𝑖𝑖 , 𝐄𝐄𝑖𝑖 の重みを計算し，各ノードについて最も大きい重みをもつクリークのみ残す 𝑤𝑤𝐶𝐶𝑖𝑖 = � 𝑤𝑤𝑒𝑒𝑗𝑗 𝒆𝒆𝑗𝑗 ∈𝐄𝐄𝑖𝑖 𝑠𝑠 𝑡𝑡 ● 𝒑𝒑𝑖𝑖𝑠𝑠 , 𝒑𝒑𝑗𝑗𝑠𝑠 , 𝒑𝒑𝑡𝑡𝑖𝑖 , 𝒑𝒑𝑡𝑡𝑖𝑖 の法線ベクトル𝒏𝒏𝑖𝑖𝑠𝑠 , 𝒏𝒏𝑗𝑗𝑠𝑠 , 𝒏𝒏𝑡𝑡𝑖𝑖 , 𝒏𝒏𝑡𝑡𝑖𝑖 から角度𝛼𝛼𝑖𝑖𝑖𝑖 = ∠ 𝒏𝒏𝑖𝑖𝑠𝑠 , 𝒏𝒏𝑗𝑗𝑠𝑠 , 𝛼𝛼𝑖𝑖𝑖𝑖 = ∠ 𝒏𝒏𝑡𝑡𝑖𝑖 , 𝒏𝒏𝑗𝑗𝑡𝑡 を求めて以下の条件を満 たすクリークだけを選択する 𝑠𝑠 𝑡𝑡 sin 𝛼𝛼𝑖𝑖𝑖𝑖 − sin 𝛼𝛼𝑖𝑖𝑖𝑖 < 𝑡𝑡𝛼𝛼 , 𝑡𝑡𝛼𝛼 はパラメータ ● クリークの重みの上位N個を残す 27

3. 提案手法 3.6 同次変換行列 ● 各クリークに対してSVDにより同次変換行列を求める ● 各変換についてMAEを計算し、最も誤差の少ないものを選択する 選んだ1つのクリークの点集合に対してICPと同様にSVDを行う ● 候補となる同次変換行列𝑇𝑇が求まる 各クリークからの候補𝑇𝑇の集合から，最もMAEの少ない𝑇𝑇が最終的な結果となる 𝑇𝑇 ∗ = argmin 𝑀𝑀𝑀𝑀𝑀𝑀 𝑇𝑇 𝑇𝑇 ∗ 28

4.実験結果 29

4. 実験結果 4.1 評価指標 ● RE(°)：回転誤差 ● TE(cm)：並進誤差 ● RR(%)：データセットのうち何%がレジストレーションが成功したか レジストレーション成功の基準 ● 3DMatch&3DLoMatch：RE<15°, TE<30cm ● KITTI dataset：RE<5°, TE<60cm 30

4. 実験結果 4.2 3DMatch＆3DLomatchの結果 ● 初期対応関係はFPFHとFCGFの局所特徴量のマッチングにより行う ● MACはDeepLearning系の手法よりもRR, RE, TEともに精度が良い 31

4. 実験結果 4.3 深層学習の手法との組み合わせ ● 特徴量に深層学習の最新手法を用いた場合の精度 ● GeoTransformerよりも精度が高い（SoTA） 32

4. 実験結果 4.4 さまざまなオプションと精度 隣接行列（FOG or SOG） GC: 外れ値除去の実行 MC: 極大クリークの代わりに最大クリーク NG: ノードあたり1つの極大クリーク NC: ??? CR: クリークのランク付け SVDの手法（SVD or W-SVD） 評価指標（MAE or MSE or #inlier） 33

4. 実験結果 4.5 RANSACとの比較 ● RANSACよりも正解のレジストレーションを与える仮説がMACは多い ● FCGFの方がFPFHよりもより正しい仮説を与える 34

4. 実験結果 4.6 実行時間 ● 対応関係が1000より小さいと数十ミリ秒でレジストレーションを実行できる ● 対応関係が増えるとクリーク探索やグラフ構築に時間がかかる ● グラフの作成からクリーク探索・ポーズ推定などはすべてCPU上で行っている 実行環境：Intel 12700H CPU, 32GB RAM 35

4. 実験結果 4.7 まとめ ● 極大クリークを用いることで効率的に仮説を見つけることができる ● NNによる特徴量抽出と組み合わせると精度がとても向上する ● 仮説の評価手法を意味的な手法に今後は置き換えることを考えたい 36

37