結合八叉樹結構對ICP算法在點云配準方面的改進

呂明慧

（山東科技大學 山東 青島 266590）

1 引言

隨著三維激光掃描技術的廣泛應用，三維激光掃描儀和它所獲取的點云數據的處理方法也在飛速發展。近些年來，三維激光掃描儀的技術已經初步成熟，獲取被測地物的點云數據的精度和密度都達到了現階段社會發展的要求，但大量的點云數據處理是我們面臨的一大難題。點云數據處理的難度主要體現在點云數據的拼接與配準方面，本文則主要介紹一種在原有ICP算法的基礎上，結合八叉樹結構的點云配準方法。

2 八叉樹

2.1 八叉樹結構

八叉樹結構是由四叉樹結構推廣到三維空間而形成的一種三維數據結構。主要思想就是將一個空間三維模型用一個正方體進行包圍，按照三維直角坐標的方式進行八等份切割，將每一個切割所得到的結構體存儲在其下屬的小區域內，對于每個區域都用相同的方式再向下分割，直到子區域內為空或達到某一規定條件。圖1為八叉樹結構示意圖。

圖1

在應用八叉樹結構進行數據組織時，通常利用Morton碼作為一種較好的編碼方式，還可以應用改進后的Morton碼[1]，一種線性八叉樹地址碼進行編碼。

2.2 八叉樹應用于點云配準

通常的點云配準方式為利用ICP算法進行配準，但ICP算法在有一個較好的初值時能得到比較理想的配準結果，否則此算法會含有較大的誤差。而八叉樹結構則可以較好的解決這個問題。基本思路為在兩個點集中分別以八叉樹結構組織數據，則每一個根節點或是葉節點都有其相應的屬性信息，包括坐標數據和體積數據。我們的目標就是找出兩個點集中最為密合的部分，即在空間位置上相差最小甚至是完全相同的兩個點，那么就可以利用八叉樹結構快速而精確地找到這兩個點。

具體方法為自頂向下分別對兩個點集的同層根節點進行比較，比較每個相對應的根節點，根據根節點內的坐標信息求取其對應的重心坐標，以兩個完全平方和相差最小的重心坐標所在的根節點為目標點進行下一層根節點的比較，用同樣的方法求取重心坐標進行比較，以此類推，依次向下總能求取出兩個相對應的點或點集。用這種方法求解時，為了避免不必要的時間和精度浪費可以設置兩個重心點的相對精度初步得到兩個點集，后續的精度提高可以再利用迭代進行調整。這種得到最鄰近點或點集的方式不僅可以提高精度，還能夠減少處理時間，相比于以往的遍歷每個點的方式所提高的處理速度是指數級的。

3 應用八叉樹結構對ICP算法的改進

3.1 ICP算法

經典的ICP算法的基本原理很簡單，就是要求兩個點云數據之間的變換關系，實質上的不同的坐標系統轉換到相同坐標系統下的計算。坐標系統的轉換一般是利用七參數法，三個平移參數，三個旋轉參數和一個比例縮放因子。而在點云數據中，我們默認比例縮放因子為1，即將問題轉化為求解一個旋轉矩陣和一個平移向量。它們的解算方法即為ICP迭代最近點算法[2-3]。有很多對于此種算法的改進方法，大多是利用去除誤差較大的點對或是給不同的約束條件分配權重來減小誤差，對于ICP算法來說，耗費時間最長的部分就是對應點的計算，接下來將介紹在八叉樹結構的參與下，以迭代方式不斷地改進點集的重心坐標來快速精確定位兩個空間位置最鄰近點甚至是重合點。

3.2 應用八叉樹結構的ICP算法

基于ICP算法的基本原理[4]，有以下的解算步驟：（1）根據參考點集中的點坐標，在待配準點集上搜索相應最近點點集；（2）計算兩個點集的重心位置坐標，并進行點集中心化生成新的點集；（3）由新的點集計算正定矩陣N，并計算N的最大特征值及其最大特征向量；（4）由于最大特征向量等價于殘差平方和最小時的旋轉四元數，將四元數轉換為旋轉矩陣R；（5）在旋轉矩陣R被確定后，由平移向量t僅僅是兩個點集的重心差異，可以通過兩個坐標系中的重心點和旋轉矩陣確定；（6）由參考點集計算旋轉連續兩次距離平方和之差絕對值作為迭代判斷數值；（7）當此數值滿足一定精度要求時，ICP配準算法就停止迭代，否則重復（1）至（6）步，直到滿足條件后停止迭代。

八叉樹結構可以應用于一、二兩個解算步驟，在搜索最近點點集時，不采用遍歷搜索，而是進行前文所說的八叉樹結構搜索提高搜索速度。這個點集可以作為配準的最初點集來使用，有了最初的相對精度較高的起算數據，就可以得到比較好的配準結果了。由這個點集繼續進行ICP算法的后續計算直到計算出第一個旋轉矩陣和平移參數。由于有很多次的迭代，每次迭代都是用八叉樹結構進行查找而不是遍歷每一個點進行歐氏距離的解算，因此它所提高的工作速度是巨大的。接下來進行迭代計算，下面的解算步驟也是八叉樹起到改進作用的主要部分。

由第一次計算的旋轉矩陣和平移參數解算出待配準點集在參考點集坐標系下的坐標值，計算出重心坐標，根據重心坐標取一定半徑的球內的臨近點形成新的點集，對新的點集數據重新按照八叉樹結構進行組織，再與參考點集進行同層次根節點的三維重心坐標差平方和的比較，找出最鄰近的兩個坐標點。這里找出的是兩個相對應的坐標點，而不是兩個點集，由于不斷地進行迭代，所查找的點集的重心位置也在不斷改變，因此靈活性有了很大的提升，避免了有更加匹配的點對而無法發現的情況的發生。經過一定次數的迭代，利用八叉樹結構總是能查找到一對最為臨近甚至是空間位置相同的對應點，此時的迭代條件可以是兩對應點對的相對精度。這樣就完成了一個點對的查找。根據實際掃描情況，一定是有多個配準特征可供選擇，那么只要在兩個點云數據中完成上述三個對應點對的查找就可以解算出不同坐標系的轉換參數，即完成點云數據的配準工作。若是對更多的點集進行比較計算，則可以求解出很多相應的點對，選擇其中誤差最小的幾對數據進行解算即可進一步提高配準精度。

4 結語

這種結合八叉樹的點云配準算法與經典ICP算法的本質上的不同在于它是根據解算查找出的對應點對來精確計算最終的旋轉矩陣和平移參數，而不是直接用點集進行解算。它的優勢體現在兩個方面，一是在每一次迭代計算中都提高了運算速度，二是由重心位置不斷改變的空間球狀點集利用八叉樹結構一步步找出最鄰近點對，提高了配準精度。八叉樹結構特殊的數據組織方式和查找方式是提高點云配準速度和精度的關鍵。