結(jié)合八叉樹結(jié)構(gòu)對ICP算法在點(diǎn)云配準(zhǔn)方面的改進(jìn)

呂明慧

（山東科技大學(xué) 山東 青島 266590）

1 引言

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

2 八叉樹

2.1 八叉樹結(jié)構(gòu)

八叉樹結(jié)構(gòu)是由四叉樹結(jié)構(gòu)推廣到三維空間而形成的一種三維數(shù)據(jù)結(jié)構(gòu)。主要思想就是將一個空間三維模型用一個正方體進(jìn)行包圍，按照三維直角坐標(biāo)的方式進(jìn)行八等份切割，將每一個切割所得到的結(jié)構(gòu)體存儲在其下屬的小區(qū)域內(nèi)，對于每個區(qū)域都用相同的方式再向下分割，直到子區(qū)域內(nèi)為空或達(dá)到某一規(guī)定條件。圖1為八叉樹結(jié)構(gòu)示意圖。

圖1

在應(yīng)用八叉樹結(jié)構(gòu)進(jìn)行數(shù)據(jù)組織時，通常利用Morton碼作為一種較好的編碼方式，還可以應(yīng)用改進(jìn)后的Morton碼[1]，一種線性八叉樹地址碼進(jìn)行編碼。

2.2 八叉樹應(yīng)用于點(diǎn)云配準(zhǔn)

通常的點(diǎn)云配準(zhǔn)方式為利用ICP算法進(jìn)行配準(zhǔn)，但I(xiàn)CP算法在有一個較好的初值時能得到比較理想的配準(zhǔn)結(jié)果，否則此算法會含有較大的誤差。而八叉樹結(jié)構(gòu)則可以較好的解決這個問題?；舅悸窞樵趦蓚€點(diǎn)集中分別以八叉樹結(jié)構(gòu)組織數(shù)據(jù)，則每一個根節(jié)點(diǎn)或是葉節(jié)點(diǎn)都有其相應(yīng)的屬性信息，包括坐標(biāo)數(shù)據(jù)和體積數(shù)據(jù)。我們的目標(biāo)就是找出兩個點(diǎn)集中最為密合的部分，即在空間位置上相差最小甚至是完全相同的兩個點(diǎn)，那么就可以利用八叉樹結(jié)構(gòu)快速而精確地找到這兩個點(diǎn)。

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

3 應(yīng)用八叉樹結(jié)構(gòu)對ICP算法的改進(jìn)

3.1 ICP算法

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

3.2 應(yīng)用八叉樹結(jié)構(gòu)的ICP算法

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

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

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

4 結(jié)語

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