ICP 演算法的設計考量

本文為設計 ICP 演算法的筆記，大部分為 [1] 這篇文章的內容。以下為 ICP 演算法的架構：

Range Sensor 的選擇

可以考慮以下幾點來選擇最適合的儀器：

• 室內或室外的場景
• 耗電量或重量
• Field of View

轉換的方程式

轉換方程式為上圖中的 \(T\)，也就是將 P 轉換成 Q。常見的轉換方程式有：

• Rigid transformation (Euclidean transformation)
  
• Similarity transform
• Affine transform
• Orthogonal projection

但大部分的問題都是屬於 rigid transformation。

轉換方程的初始值

也就是上圖中的 \(T_{init}\)。好的初始值非常重要，否則可能會導致 ICP 的結果被卡在 local minima。

• 外部資訊：像是先用演算法估計、人給的 prior、或是用其他 sensor 給的結果。
• Parameter cascade：串聯同一個演算法，但是使用不同的演算法參數，例如 coarse to fine grain 的作法。
• Registration cascade：首先用 descriptor matching 的演算法得到初始值，再優化。

Data Filter - Feature 的優化

這裡的 feature 指的是幾何特徵。除了點以外也可以用切線向量（常用來表示線）、法線向量（常用來表示平面）、曲線等等。但由於曲線對於噪音較為敏感，因此大部分的演算法都是用原始的資料（也就是點）來當作輸入資訊。

Data Filter -  Descriptor 的優化

文章 [2] 列出了設計 descriptor 要考慮的事情：

• Invariance：對於 rotation、scale、affine transformations 仍然得得到相同的 descriptor。
• Robustness：被噪音影響時仍然得得到相同的 descriptor。
• Repeatability：相同物體相同場景之下，無論從哪個方向都能得到類似的特徵。
• Distinctiveness：Descriptor必須夠特別來表示特徵。
• Locality：符合 local planarity 的假設，只表示局部的特徵。
  
• Quantity：Feature 的數量不能太少，得符合應用的要求。
• Accuracy：Feature 的位置必須正確。
  
• Efficiency：是否能符合 real-time 的要求。

以上的假設是由穩定的光源對於物體的折射反射會是相同的，也就是成立於被動接收光源的物體上。主動接收光源的儀器（像是 lidar）並不符合此假設。

Feature 的壓縮

常見的方法有 random sampling、uniform grid、grid projection、octree 等等。

Data Association 的形式

可以直接用 features、descriptors、或是將 features 與 descriptors 結合起來。用 features 要注意的是初始值是否正確，而用 descriptor 則無此限制，但是當物體或場景有重複的特徵時，同樣的 descriptor 會出現在不同的地方。

加速 Data Association 的方法

最常見的方法是用 KD-tree 來搜尋；此外使用 coarse-fine grain 的方法能加速。

處理 Outliers

有三種常見的技巧：

• Rejection：通常是選定一個 threshold，再比較 Euclidean distance 與此值來決定。
  
• Weighting：給每個 feature 一個權重再優化。
  
• Robust Statistics：通常用的是 M-estimators，像是 Huber 或 Cauchy loss。
  

最佳化的計算

首先是計算 distance function，像是點對點、點對面、點對曲線、線對線、面對面等等。實務上點對面方法收斂得較快，但不見得適用於所有的應用。例如在樹很多的地方會導致 surface normal 的估計不準確，因此點對面並不適合於此應用。

參考資料

[1] A Review of Point Cloud Registration Algorithms for Mobile Robotics

[2] Local Invariant Feature Detectors: A Survey

附錄：常見的 loss function 比較

本圖取自於 Ceres Solver 的官方文件。