迭代最近點演算法

迭代最近點演算法，幾乎總是簡稱為 ICP，是一套把一團點平移、旋轉，直到盡可能端正地落在另一團描述同一事物的點之上的方法。點雲不過是空間裡的一群點——對機器人來說，就是它的雷射或深度感測器打到附近表面的那些位置。當兩團這樣的點雲從略有不同的位置描繪同一個房間時，ICP 會找出那個能讓它們彼此基本吻合的移動，而這個移動也正是機器人在兩者之間所做的運動。

它之所以叫「迭代」，是因為它不斷重複兩個簡單的步驟。第一步，對於正在移動的那團點裡的每一個點，它在另一團點裡找出最近的那個點，並姑且把這兩個點當作同一處——這是對「哪個點配哪個點」的一個又快又粗的猜測。第二步，它算出那個能把所有這些猜出來的配對一起拉得最近的「平移加旋轉」，並施加上去。此時兩團點雲貼合得更好了，於是「最近點」的猜測也隨之改善；它再重複一遍，每跑一輪，兩團點雲就貼得更緊，直到幾乎不再移動——這個穩定下來的位置就是答案。

ICP 是掃描匹配背後的標準引擎，也是雷射雷達 SLAM 的支柱，因其只要從一個還不錯的初始猜測出發，就既簡單又精確而備受推崇。它的難處在於：它始終只把每個點和它當前的最近鄰配對，所以如果兩團點雲一開始就相距很遠、或扭得很厲害，它就可能鎖定到錯誤的配對上，並自信地穩定在一個錯誤的答案裡——這個陷阱叫做局部極小值。這也是為什麼機器人通常會先餵給 ICP 一個粗略的初始估計（常常來自車輪計數或上一次掃描），再讓它去把吻合度打磨好。