點云數據

點云數據通常表示為N行，至少3列的矩陣，其中N表示點的數量，每一行代表一個點。通常3列分別是點在空間中（x，y，z）的坐標。如果點云數據有除空間中坐標外的附加信息，如來自LIDAR傳感器的點云數據，那么它可能具有每個點的附加值，例如“反射率”，其是在該位置中障礙物反射多少激光光束的量度。 在這種情況下，點云數據可能是N×4陣列。

三維點云配準

點云的配準過程，就是求兩個點云之間的一個旋轉平移矩陣，源點云通過旋轉平移矩陣后，變換成和目標點云矩陣相同的矩陣。

可以表示為以下方程：

其中，pt，ps分別是目標點云和源點云中的一對對應點。
R，T就是我們要求的旋轉平移矩陣。
但是，我們并不知道兩個點云中，點與點之間的對應關系，這也是配準的核心問題。

三維點云配準分為粗配準與精配準兩步。
粗配準就是在完全不清楚兩個點云的相對位置關系的情況下，找到一個這兩個點云近似的旋轉平移矩陣（不一定很精確，但是已經大概是對的了）。
精配準就是在已知一個旋轉平移矩陣的初值的情況下（這個初值大概已經是正確的了），進一步計算得到更加精確的旋轉平移矩陣。

配準的評價標準：比較通用的是LCP(Largetst Common Pointset)（最大公共點集）。給定兩個點集P，Q，找到一個變換T，使得變換后的T（P）與Q的重疊度最大。在變換后的P內任意一點，如果在容差范圍內有另外一個Q的點，則認為該點是重合點。重合點占所有點數量的比例就是重疊度。

（一）粗配準

（1）暴力配準

粗配準中，最簡單粗暴的一個方法就是暴力配準。找到一個剛體變換需要3對對應點，即在點集P中選取3個點，如果我們能找到它們在點集Q中的對應點，即能根據它們的坐標求出旋轉平移矩陣。（具體怎么求：pass）

暴力配準步驟：

• 隨機在點集P中選取3個點，隨機在點集Q中選取3個點。
• 計算旋轉平移矩陣T
• 計算 ||T（P）- Q||<$\delta$的點的個數$k_i$（點集P經過旋轉平移矩陣后，點集中與點集Q的點的距離小于給定的閾值$\delta$的點的個數）
• 遍歷所有的可能性，選取最高的$k_i$作為最后的結果

暴力配準的缺點：時間復雜度高。

假設點集P的大小為n，點集Q的大小為m，分別隨機選取3個點組成關聯對，則在選取3個點時就分別有$A_n^3$和$A_m^3$種可能，點集P中選取的任意一種可能，均需遍歷點集Q中的所有可能。因此，完成整個算法共需遍歷$A_n^3\times A_m^3=n(n?1)(n?2)m(m?1)(m?2)$種可能。因此，暴力配準的時間復雜度為$O(n^3{m}^3)$。（當n，m足夠大時，-1,-2等都失去了意義）

（2）4PCS（4-Points Congruent Sets）（4點全等集）

4PCS的核心原理在于，在剛性變換中，同一平面上的4個點，在經過剛性變換后，其某些比率是穩定不變的。

如圖，{a，b，c，d}四點共面，其中兩條直線的交點為e。在剛性變換中，r1，r2是穩定不變的。

4PCS步驟：

• 在點集P中選取共面四點對作為base B={a，b，c，d}

• 計算比率$r_1$，$r_2$

• 點集Q（n個點）中，每兩個點組成一對（$C_n^2$），對于每一對點$q_1$，$q_2$，計算他們的中間點
  $$e_1=q_1+r_1(q_2?q_1)$$$$e_2=q_1+r_2(q_2?q_1)$$
  
  如圖，每一對點都可以計算出兩個中間點$e_1,e_2$

• 若點集Q中，任意兩對點，一對由$r_1$計算得到的中間點$e_1$和另一對由$r_2$計算得到的中間點$e_2$的距離在允許范圍內，那么可以認為這兩對點可能是base B={a，b，c，d}的仿射對應點。
  
  如圖，此時可認為點集{$q_1$，$q_2$，$q_3$，$q_4$}是base B={a，b，c，d}的仿射對應點

• 可能存在k個這樣的點集，這k個點集再作如下處理：
  （1）根據每個點集與base B，計算出旋轉平移矩陣T
  （2）計算 ||T（P）- Q||<$\delta$的點的個數$k_i$（點集P經過旋轉平移矩陣后，點集T（P）與點集Q，距離小于給定的閾值$\delta$的點的個數）
  （3）遍歷所有k個點集，選取最高的$k_i$作為最后的結果

因此，4PCS算法的時間復雜度包括兩部分，點集Q（n個點）中任意選取兩個點組成一對，計算$e_1,e_2$，需作$A_n^2=n(n?1)次$，在找出的$k$個可能是base B的仿射對應點的四點集中，遍歷檢查，獲得最好的旋轉平移矩陣T。$O(n^2+k)$

（二）精配準
精配準的模式基本已固定為使用ICP算法（Iterative Closest Point）（最近點迭代法）及其各種變種。
ICP算法的步驟：

• （1）ICP算法的核心是最小化一個目標函數：$$f(R,T)=\frac{1}{N_p}\sum _{i=1}^{N_P}|p_t^i?R?p_s^i?T{|}^2$$
  $p_t^i，p_s^i$是一對對應點，總共有$N_p$對對應點，這個目標函數實際上是找到旋轉平移矩陣R，T，使得所有對應點之間的歐式距離的平方和最小。

• （2）尋找對應點。起初并不知道有哪些對應點，因此，在有粗配準獲得的旋轉平移矩陣的初值下，用此旋轉平移矩陣對源點云進行變換，得到一個變換后的點云，將這個變換后的點云與目標點云進行比較，只要兩個點云中存在距離小于一定閾值（ICP算法的一個參數）的點，就認為這兩個點是對應點。（最鄰近點）

• （3）R，T優化。有了對應點后，根據目標函數優化R，T。

• （4）迭代。優化得到了新的R，T，導致變換后的點云的一些點的位置發生了變化，一些最近鄰點對也相應地發生了變化，回到步驟（2）中重新尋找對應點。迭代（2）（3）步驟，直到滿足迭代終止條件，如R，T的變化量小于一定值，或目標函數的變化小于一定值，或最近鄰點對不再改變等（ICP算法的另一個參數）

• （5）迭代終止后，最終獲得精配準的R，T

ICP算法的參數：
（1）距離閾值。兩個點云中距離小于距離閾值的點，才算作對應點。
（2）迭代的終止條件。

至此，完成點云數據的配準。

參考文獻：
[1] Aiger D, Mitra N J, Cohen-Or D. 4-points congruent sets for robust pairwise surface registration[J]. Acm Transactions on Graphics, 2008, 27(3):85.
[2]https://blog.csdn.net/u011600592/article/details/70258097

總結

以上是生活随笔為你收集整理的三维点云配准的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。