基于3D-Harris與FPFH改進的3D-NDT配準(zhǔn)算法

范 強，劉 鵬，楊 俊，周沛希

基于3D-Harris與FPFH改進的3D-NDT配準(zhǔn)算法

范 強1，劉 鵬1，楊 俊2，周沛希1

(1. 遼寧工程技術(shù)大學(xué)測繪與地理科學(xué)學(xué)院，遼寧 阜新 123000；2. 遼寧師范大學(xué)城市與環(huán)境學(xué)院，遼寧 大連 116029)

針對傳統(tǒng)點云配準(zhǔn)三維正態(tài)分布變換(3D-NDT)、迭代最近點(ICP)算法在未給定初始配準(zhǔn)估計的情況下配準(zhǔn)效果不佳、配準(zhǔn)時間長、誤差較大的缺陷，提出了精準(zhǔn)且相對高效的點云匹配算法。首先，運用3D-Harris算法識別每一幅點云的關(guān)鍵點，并以此為基本點建立局部參考框架，計算快速點特征直方圖(FPFH)描述子；之后，使用最小中值法(LMeds)中的對應(yīng)估計算法排除不準(zhǔn)確的點對應(yīng)關(guān)系，得到含有對應(yīng)三維特征關(guān)系的特征點對。計算粗配準(zhǔn)所需的變換矩陣，完成初步匹配。隨后，根據(jù)3D-NDT算法將點云數(shù)據(jù)空間體素化，運用概率分布函數(shù)完成最終的點云進行精確地匹配。使用改進配準(zhǔn)將3組分別從網(wǎng)絡(luò)下載的較少噪聲、大規(guī)模與Kinect V2.0采集的較多噪聲、大規(guī)模的2組重疊度不同的點云數(shù)據(jù)匹配到同一個空間參考框架中，并通過精度分析對比經(jīng)典3D-NDT，ICP等算法。實驗結(jié)果證明，該算法在迭代次數(shù)較低時，可使室內(nèi)場景點云數(shù)據(jù)完成精度較高的配準(zhǔn)且受噪聲影響較小，但如何將算法的復(fù)雜度適當(dāng)降低，縮短配準(zhǔn)時間需要更進一步的研究。

三維正態(tài)分布變換；3D-Harris特征點；快速點特征直方圖；最小中值法；點云配準(zhǔn)

近年來，空間三維信息采集技術(shù)的發(fā)展和點云數(shù)據(jù)處理領(lǐng)域逐漸成為研究熱點[1]。以及應(yīng)運而生的Kinect等一系列傳感器[2]，使得對三維影像的研究更加方便、快捷。在三維數(shù)據(jù)的各領(lǐng)域研究中，對同一區(qū)域不同角度或多測站間點云的配準(zhǔn)是整個研究領(lǐng)域中重要的環(huán)節(jié)之一?？焖倬珳?zhǔn)的點云匹配算法可以為三維重建、識別地物、智能導(dǎo)航等帶來充足的信息量。截至目前，對三維點云數(shù)據(jù)的自動配準(zhǔn)技術(shù)并不是十分完善，國內(nèi)外諸多學(xué)者對該領(lǐng)域進行了各種嘗試以及深入的研究[3-4]。在眾多的算法中比較經(jīng)典的算法是由BESL和MCKAY[5]于1992年提出的最近點迭代法(iterative closest point，ICP)，當(dāng)給定初始位置與相對姿態(tài)接近時，該算法的配準(zhǔn)效果較好[4]；彭真等[6]針對強噪聲且密度不均勻的點云進行高效、高精度配準(zhǔn)的問題，提出了一種基于關(guān)鍵點提取與優(yōu)化ICP的點云配準(zhǔn)算法；趙夫群[7]提出了將幾何屬性與k-d樹改進的ICP算法相結(jié)合的配準(zhǔn)方法。但大量實驗證明，ICP算法在運算時間上存在較大缺陷，在處理大型的三維點云數(shù)據(jù)時顯得十分吃力。之后三維正態(tài)分布轉(zhuǎn)換(3D-normal distribution transform，3D-NDT)算法[8]被提出，其可應(yīng)用于點云匹配以及相近性掃描數(shù)據(jù)處理的相關(guān)領(lǐng)域中[9]。3D-NDT算法在處理大數(shù)據(jù)量的三維數(shù)據(jù)過程中，具有的精度高、速度快等特點深受歡迎[9-10]。雖然相較于ICP算法，3D-NDT算法有了相當(dāng)大的進步，但其同樣需要提供前期配準(zhǔn)估計。對于2種算法而言，3D-NDT算法較適合處理三維掃描設(shè)備所提供的數(shù)據(jù)[9]。未匹配的點云如果沒有提供初始的匹配估計，最終的匹配誤差較大。王慶閃等[11]通過將3D-NDT算法與ICP算法結(jié)合增加了配準(zhǔn)的精度，但在運行時間方面有較大缺陷。趙凱等[12]提出一種新的區(qū)域生長聚類正態(tài)分布變換(normal distributions transform with region growing clustering，RGC-NDT)算法。本文提出的算法首先運用3D-Harris算法結(jié)合快速點特征直方圖(fast point feature histograms，F(xiàn)PFH)計算配準(zhǔn)初始值，然后用3D-NDT進行精準(zhǔn)匹配。

1 點云的初始配準(zhǔn)

點云的初始匹配即粗匹配是指在未獲得用于配準(zhǔn)的旋轉(zhuǎn)變換矩陣的情況下，根據(jù)點云數(shù)據(jù)中含有的局部位置特征信息能唯一代表各自點云數(shù)據(jù)的性質(zhì)，提取該點云的特征點，并根據(jù)FPFH原理計算每一個特征點處的特征描述子，進而求解用于將整個點云空間進行空間變換的特征向量以及旋轉(zhuǎn)矩陣，完成點云最初始的點云粗匹配。圖1為點云初始配準(zhǔn)算法的流程圖。

圖1 初始匹配算法流程圖

1.1 3D-Harris提取關(guān)鍵點

3D-Harris算法是針對1988年由HARRIS和STEPHENS[13]提出的Harris檢測算法在三維方向的空間拓展。該算法需對整個點云空間進行三維網(wǎng)格化，將落在每個網(wǎng)格中點的個數(shù)近似看作二維圖像的像素值，并以此為基礎(chǔ)以前、后、左、右、上、下6個為平移方向進行計算，最終求得所有特征點。

1.1.1 Harris基本原理

將[,]平移[,]個單位后，其灰度的變化中(,)為平移后的強度；(,)為原圖像強度。根據(jù)圖像強度可以得到一個特征期望(,)如式(1)，當(dāng)強度恒定時，(,)接近于0，反之，(,)會很大，即

其中，為一個5×5的窗口權(quán)函數(shù)。傳統(tǒng)的函數(shù)將窗口內(nèi)的各個權(quán)值設(shè)為1，其計算精度不高且易受噪聲影響或利用高斯函數(shù)進行加權(quán)，每一次遍歷都要重新計算高斯權(quán)函數(shù)，本文將窗口權(quán)值函數(shù)設(shè)置為梯度分段加權(quán)函數(shù)及將窗口從內(nèi)到外分為5個等級，最中心的權(quán)為10，向外依次賦予權(quán)值7，5，3，1，如此改進Harris算法不僅提高了計算精度，也降低了計算復(fù)雜度。利用二維泰勒公式展開并取其一階近似方程，可得簡化式(2)

將計算的與設(shè)定的進行比較，當(dāng)>即識別為特征點。

1.1.2 3D-Harris提取特征點

提取特征點是前期粗配準(zhǔn)的關(guān)鍵一步，只有提取出一定數(shù)量的特征點，并根據(jù)其的FPFH特征信息才能計算出用于前期配準(zhǔn)的變換矩陣。Harris最終要計算式(3)中的。但在三維點云空間領(lǐng)域中很難獲取到如二維圖像類似的圖像強度，計算矩陣較為困難。

在整個三維點云空間中，以點為中心，以為半徑來建立空間影響區(qū)域，在該區(qū)域內(nèi)將所有的點進行主成分分析(principal component analysis，PCA)，利用最小二乘擬合出一個二次曲面，即

根據(jù)的計算公式，計算的和的偏導(dǎo)，近似成圖像強度，并在該區(qū)域內(nèi)利用曲面積分來解算出矩陣中的各個元素，如式(5)~(7)

利用微積分知識可以計算得到，，的值，即

最后計算Harris響應(yīng)值，進而判斷關(guān)鍵點。

1.1.3 3D-Harris算法流程

(1) 體素化整個點云空間；

(2) 從體素開始，計算建立局部坐標(biāo)系，方向為法向量方向，軸、軸與軸垂直，軸方向在平面內(nèi)任意，軸在平面內(nèi)與軸垂直；

(3) 根據(jù)體素內(nèi)點云個數(shù)求解點云的梯度；

(4) 計算相關(guān)矩陣；

(6) 采取非極大值抑制對進行處理，將大于閾值的局部極大值點作為角點。

1.2 FPFH快速點特征直方圖

FPFH[14]是對PFH[15]算法的改進，能快速地提取含有局部特征的描述子，并可以與關(guān)鍵點相結(jié)合。其具有較好的魯棒性、時效性。表1中FPFH特征向量的維度為33，在較少維度的情況下反映特征信息，降低了算法的計算復(fù)雜度。

表1 各種特征描述子對應(yīng)的特征向量的維度

算法流程：

(1) 迭代點云，計算法線；

(2) 點云中的每個點P，遍歷P周圍半徑為的球體內(nèi)的所有相鄰點，將該點集合命名為P；

(3) 將P與其相鄰的點進行關(guān)聯(lián)。對于該區(qū)域中的一對點1和2，將法向量與1和2相連矢量夾角小的點設(shè)置為源點P，另一個點設(shè)置為目標(biāo)點P；

(4) 計算3個特征(PFH的4個特征中除去P與P之間的距離，其表示目標(biāo)點P處的平均曲率)，并組合放入存儲單元中；

(5) 計算查詢點P的簡化特征直方圖SPFH；

(6) 將相鄰的SPFH之間的空間距離添加到P的SPFH中，構(gòu)成FPFH。

1.3 LMeds刪除錯誤對應(yīng)

在獲取了FPFH的特征向量之后，為了判斷點云之間的重合部分，需要找到各點云之間的近似特征，進而完成點云初步的匹配工作。為了使匹配具有較高的精確性和準(zhǔn)確度，采用了對應(yīng)關(guān)系估計、求解各個點云數(shù)據(jù)之間的相互對應(yīng)關(guān)系，最終得到其交集作為最后的相互關(guān)系匹配對。

由于數(shù)據(jù)在攝取過程中存在噪聲的影響，3D-Harris算法會產(chǎn)生一些錯誤特征點，最終導(dǎo)致對應(yīng)匹配關(guān)系也會出現(xiàn)錯誤的匹配，且對后續(xù)的求解變換矩陣造成很大的負面影響。所以，采用了最小中值法(least median of squares，LMeds)[16]刪除錯誤對應(yīng)關(guān)系，此操作不但能夠節(jié)省配準(zhǔn)所需的時間，同時也可以提高變換矩陣的計算準(zhǔn)確度。

1.4 計算變換矩陣完成初始配準(zhǔn)

使用LMeds算法刪除了錯誤的點云對應(yīng)關(guān)系，獲得較高準(zhǔn)確度的匹配點對進而完成了點云的初始配準(zhǔn)后，獲取了點云匹配的旋轉(zhuǎn)矩陣和平移特征向量，即

如果點云和上分別有一個同名點，即關(guān)聯(lián)點對(,,)和(,,)，則兩者之間的數(shù)學(xué)關(guān)系如下

2 3D-NDT點云配準(zhǔn)算法

2.1 3D-NDT算法原理

(1) 將點云空間劃分為大小相等的單元要素(cell)，并將點云放入所有的體素之中；

(2) 計算每個cell的概率分布函數(shù)中的參數(shù)，即

其中，為點云落在某個cell中的點的個數(shù)。

(3) 將下一幅的scan中的每一個點按照變換矩陣進行變換；

(4) 矩陣進行變換計算，相對應(yīng)的概率分布函數(shù)如式(16)所示，將整個點云空間用一組正態(tài)分布函數(shù){(,)}進行表示，最終形成一個分段式平滑空間函數(shù)，即

(5) 計算所有點的最優(yōu)解，目標(biāo)函數(shù)為

2.2 3D-NDT算法配準(zhǔn)

首先建立一個4行4列矩陣用于存儲變換矩陣。將3D-NDT的最初變換矩陣賦值給單位矩陣。在此基礎(chǔ)上，進行3D-NDT算法匹配2點云。

考慮到算法運行的時間因素，將目標(biāo)點云進行一定程度的縮減。對點云而言，3D-NDT算法使用整個體素化后的空間中的每一個單元格(cell)內(nèi)的統(tǒng)計數(shù)據(jù)。此外，算法可以依據(jù)點云數(shù)據(jù)獲取的大小來使用自適應(yīng)參數(shù)的More-Thuente算法進行搜索，得到最理想的迭代步長，以防止出現(xiàn)過度迭代或局部收斂等問題。

同時，為最小的變換插值設(shè)置閾值，而且分別從長度和角度(以弧度形式表示) 2個方面定義每次變換的最小增量，當(dāng)小于閾值時，即可結(jié)束本次匹配工作。

2.3 逐步點云匹配方法

該算法處理第3組多幅點云數(shù)據(jù)時，將點云逐一匹配，再將所有點云變換到同一個空間參考系下。以第1幅點云為基礎(chǔ)，在點云重疊區(qū)域進行FPFH粗配準(zhǔn)，進行3D-NDT精確配準(zhǔn)得到最終的、最優(yōu)的變換位置；最后將最優(yōu)變換進行累積和不斷更新得到整體的全局轉(zhuǎn)換。再將所有點云按照讀取順序逐一變換到第1次輸入的點云中，最終將所有點云匹配到與第1次讀取點云相同的統(tǒng)一空間參考系下。本次實驗證明，該方法實現(xiàn)的效果較好，可以較好地匹配多幅點云，最終實現(xiàn)場景復(fù)原，3D-Harris-FPFH-3D-NDT算法流程如下：

3 實驗結(jié)果及分析

本次實驗所用數(shù)據(jù)共3組，第1組數(shù)據(jù)是在csdn網(wǎng)站下載的由三維激光掃描儀獲取1組室內(nèi)掃描數(shù)據(jù)，如圖2(a)和(b)所示；第2組為Kinect V2.0傳感器獲取的一個模型羊的點云數(shù)據(jù)如 圖2(c)~(h)所示，該點云模型是重疊度較低的一組數(shù)據(jù)；第3組為采用Kinect V2.0傳感器對實驗室同一場景獲取并進行Tatistical Outlier Removal濾波器濾波后的一組高重疊度點云數(shù)據(jù)，如圖2(i)~(l)所示。具體實驗數(shù)據(jù)參數(shù)見表3。隨后在vs2013開發(fā)環(huán)境下結(jié)合PCL1.8.0點云開發(fā)資源庫[17]完成實驗。

表2 各點云濾波后點數(shù)量

如圖3所示，對點云數(shù)據(jù)運用3D-Harris算法進行關(guān)鍵點檢測。檢測到的特征點個數(shù)見表3。如圖3(a)~(h)所示，可以看出，3D-Harris算法所提取的關(guān)鍵點均位于變化較大的關(guān)鍵位置上，十分適合應(yīng)用于這種室內(nèi)場景。而且在相鄰2幅的相同位置的關(guān)鍵點較多，說明3D-Harris算法是比較穩(wěn)定的。

求解由3D-Harris算法所得到的特征點上的FPFH特征矩陣，在各個關(guān)鍵點處(設(shè)某一個特征點為0)將搜索半徑設(shè)置為(本次實驗=55 mm)。并且先遍歷此區(qū)域內(nèi)的所有點(1,2,···,)，再計

算0與各點對應(yīng)法向量的夾角偏差{(1,1,1), (2,2,2),···,(,,)}。將所有的,,關(guān)鍵要素各自分化成11個子統(tǒng)計區(qū)間，計算特征直方圖然后得到一組33維的特征向量。如圖4所示，橫坐標(biāo)分成0~32個區(qū)域，縱坐標(biāo)為落在每個分量上點的個數(shù)。由于關(guān)鍵點的數(shù)量較多，不能將每1幅點云中的全部特征點的FPFH特征矩陣全部顯示出來，僅展示了1個點的描述子：

從圖4可以得知，將局部特征用直方圖表示之后，特征點相較于普通點而言差異量化的效果十分顯著。

圖5(a)~(i)分別顯示了配準(zhǔn)之前、及在循環(huán)次數(shù)相同情況下(本次迭代50次，此時對比效果最佳)，直接應(yīng)用傳統(tǒng)3D-NDT算法，將4幅點云進行配準(zhǔn)和使用本文改進的算法所生成的效果圖。具體細節(jié)對比如圖6(a)~(f)所示，可以看出直接應(yīng)用傳統(tǒng)的3D-NDT算法在一定程度上對多幅點云的配準(zhǔn)會起到一定的作用，但是誤差較大；而本文方法可以在迭代次數(shù)較少情況下，將多幅點云較好地匹配到同一個坐標(biāo)系下。

圖3 各組數(shù)據(jù)的特征點分布示意圖

表3 各組點云數(shù)據(jù)的特征點數(shù)量

圖4 FPFH特征直方圖

為了進一步的檢驗本文所提出算法的精度以及準(zhǔn)確性，本文還與其他一些常用的配準(zhǔn)算法3D-NDT，ICP，SIFT-3D-NDT從計算精度和算法效率進行對比分析，見表4~6，結(jié)果證明當(dāng)?shù)螖?shù)相同時本文算法誤差較小。

除上述所列的傳統(tǒng)特征配準(zhǔn)方法外，文獻[18]還提出了一種新的特征提取配準(zhǔn)方法，即基于協(xié)方差描述子的雷達點云配準(zhǔn)算法，該算法的描述子為一個10為向量，且需包含點云的表面色彩紋理信息，而在本文數(shù)據(jù)中只有第3組數(shù)據(jù)含有表面紋理數(shù)據(jù)。且由于描述子只有10維特征向量，所描述的幾何特征信息較少。如果將RGB信息全部設(shè)置為固定值，特征描述子只能近似為7維向量，不足以作為一個特征描述子來確定對應(yīng)關(guān)系，會產(chǎn)生更多的錯誤對應(yīng)關(guān)系。而在處理第3組數(shù)據(jù)時，由于Kinect生成的數(shù)據(jù)含有較多噪聲，產(chǎn)生的對應(yīng)匹配關(guān)系同樣不理想，匹配精度不足，算法精度與傳統(tǒng)的3D-NDT算法相近。該算法在處理專業(yè)的TLS掃描儀掃描獲取的高精度彩色點云或許會有理想的效果，但對于本文的由Kinect所獲取的室內(nèi)點云數(shù)據(jù)的處理效果不佳。

圖5 各組數(shù)據(jù)結(jié)果對比圖

圖6 各組數(shù)據(jù)結(jié)果細節(jié)對比

表4 第1組數(shù)據(jù)同類算法精度對比

表5 第2組數(shù)據(jù)同類算法精度對比

表6 第3組數(shù)據(jù)同類算法精度對比

通過實驗可以看出，在配準(zhǔn)前，各組點云均散亂堆疊在一起，在直接使用3D-NDT算法進行配準(zhǔn)后，雖然在一定程度上完成配準(zhǔn)，但誤差較大，且容易受到噪聲的影響，由于第2和3組數(shù)據(jù)含有很多噪聲，所以該現(xiàn)象尤為突出。而改進的算法能很好地避免該問題。在對重疊度較低的點云進行配準(zhǔn)方面本文算法也有一定優(yōu)勢。本文算法是基于3D-NDT算法改進而來，先為其提供一個初始值，與3D-NDT算法的斂散性相同，但收斂速度高。故具有很好的全局收斂性。表5~7通過與其他經(jīng)典配準(zhǔn)算法相對比，本文算法克服了無初始變換矩陣時配準(zhǔn)誤差較大的缺點，使精度得以提高。但由于算法的復(fù)雜度增加了，所以算法運行時間有所增加，需進一步解決。

4 結(jié)論與展望

本文針對Kinect V2.0傳感器以及其他來源的室內(nèi)三維點云數(shù)據(jù)的特征，有針對性地提出了3D-Harris-FPFH-3D-NDT點云配準(zhǔn)算法，并將該算法與逐步配準(zhǔn)算法相結(jié)合，將同一場景內(nèi)的事物在不同位置，以不同角度拍攝的多幅點云數(shù)據(jù)進行逐步配準(zhǔn)，最終，達到了預(yù)期要求。通過實驗得到以下結(jié)論，在未得到配準(zhǔn)所需的初始轉(zhuǎn)換估計的情況下，本文算法可以在迭代次數(shù)較低時完成較為精確的多幅點云數(shù)據(jù)的自動配準(zhǔn)。但由于算法增加了2個計算步驟，即3D-Harris、FPFH特征描述子的計算，提高了算法整體的復(fù)雜度。故該算法在如何降低計算復(fù)雜度，縮短運行時間方面需要進一步研究。

[1] 劉俊毅. 彩色圖像引導(dǎo)的深度圖像增強[D]. 杭州: 浙江大學(xué), 2014. LIU J Y. Depth map enhancement under the guidance of color image[D]. Hangzhou: Zhejiang University, 2014 (in Chinese).

[2] 王歡, 汪同慶, 李陽. 利用Kinect深度信息的三維點云配準(zhǔn)方法研究[J]. 計算機工程與應(yīng)用, 2016, 52(12): 153-157. WANG H, WANG T Q, LI Y. Research of 3D point-cloud registration method based on depth information of Kinect[J]. Computer Engineering and Applications, 2016, 52(12): 153-157 (in Chinese).

[3] DU S Y, ZHENG N N, YING S H, et al. Affine iterative closest point algorithm for point set registration[J]. Pattern Recognition Letters, 2010, 31(9): 791-799.

[4] 劉鑫, 許華榮, 胡占義. 基于GPU和Kinect的快速物體重建[J]. 自動化學(xué)報, 2012, 38(8): 1288-1297. LIU X, XU H R, HU Z Y. GPU based fast 3D-bbject modeling with Kinect[J]. Acta Automatica Sinica, 2012, 38(8): 1288-1297 (in Chinese).

[5] BESL P J, MCKAY N D. A method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.

[6] 彭真, 呂遠健, 渠超, 等. 基于關(guān)鍵點提取與優(yōu)化迭代最近點的點云配準(zhǔn)[J]. 激光與光電子學(xué)進展, 2020, 57(6): 68-79. PENG Z, LV Y J, QU C, et al. Accurate pair-wise registration of 3D point clouds based on key point extraction and improved iterative closest point algorithm[J]. Laser & Optoelectronics Progress, 2020, 57(6): 68-79 (in Chinese).

[7] 趙夫群. 基于改進ICP的點云配準(zhǔn)算法[J]. 信息技術(shù), 2017, 41(5): 64-66, 71. ZHAO F Q. Point cloud registration method based on geometric property and improved ICP[J]. Information Technology, 2019, 43(4): 33-38, 71 2020, 57(6): 68-79 (in Chinese).

[8] BIBER P, STRASSER W. The normal distributions transform: a new approach to laser scan matching[C]// Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003). New York: IEEE Press, 2003: 2743-2748.

[9] KIM J W, LEE B H. Robust and fast 3-D scan registration using normal distributions transform with supervoxel segmentation[J]. Robotica, 2016, 34(7): 1630-1658.

[10] MAGNUSSON M, ANDREASSON H, NüCHTER A, et al. Automatic appearance-based loop detection from three-dimensional laser data using the normal distributions transform[J]. Journal of Field Robotics, 2009, 26(11-12): 892-914.

[11] 王慶閃, 張軍, 劉元盛, 等. 基于NDT與ICP結(jié)合的點云配準(zhǔn)算法[J]. 計算機工程與應(yīng)用, 2020, 56(7): 88-95. WANG Q S, ZHANG J, LIU Y S, et al. Point cloud registration algorithm based on combination of NDT and ICP[J]. Computer Engineering and Applications, 2020, 56(7): 88-95 (in Chinese).

[12] 趙凱, 朱愿, 王任棟. 基于改進NDT算法的城市場景三維點云配準(zhǔn)[J]. 軍事交通學(xué)院學(xué)報, 2019, 21(3): 80-84. ZHAO K, ZHU Y, WANG R D. Urban scene 3D point cloud registration based on impove NDT algorithm[J]. Journal of Military Transportation University, 2019, 21(3): 80-84 (in Chinese).

[13] HARRIS C, STEPHENS M. A combined corner and edge detector[C]//Procedings of the Alvey Vision Conference.Heidelberg: Springer, 1988: 147-151.

[14] RUSU R B, BLODOW N, BEETZ M. Fast point feature histograms (FPFH) for 3D registration[C]//2009 IEEE International Conference on Robotics and Automation. New York: IEEE Press, 2009: 3212-3217.

[15] RUSU R B. Semantic 3D object maps for everyday manipulation in human living environments[J]. KI - Künstliche Intelligenz, 2010, 24(4): 345-348.

[16] 李春磊, 常智勇, 莫蓉. 基于改進LMedS算法和貪心估計的相位立體匹配[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2014, 26(11): 2046-2055. LI C L, CHANG Z Y, MO R. Phase-based stereo matching by using improved LMedS algorithm and greedy strategy[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(11): 2046-2055 (in Chinese).

[17] 朱德海, 郭浩, 蘇偉. 點云庫PCL學(xué)習(xí)教程[M]. 北京: 北京航空航天出版社, 2012: 1-402. ZHU D H, GUO J, SU W. Point cloud library PCL. Beijing: Beihang University Press, 2012: 1-402 (in Chinese).

[18] LI W, WANG C H, WEN C L, et al. Pairwise registration of TLS point clouds by deep multi-scale local features[C]//Neurocomputing, 2019 Nicolas Bonneel and David Coeurjolly. New York: ACM Press, 2019: 13.

Improved 3D-NDT point cloud registration algorithm based on 3D-Harris and FPFH

FAN Qiang1, LIU Peng1, YANG Jun2, ZHOU Pei-xi1

(1. School of Geomatics, Liaoning Technical University, Fuxin Liaoning 123000, China; 2. School of Urban and Environmental Sciences, Liaoning Normal University, Dalian Liaoning 116029, China)

Aimed at addressing the shortcomings of the traditional point cloud registration normal distribution transform (3D-NDT) and iterative closure points (ICP) algorithms, such as poor registration effect, long registration time and serious errors, a precise and relatively efficient point cloud matching algorithm was proposed. First, the 3D-Harris algorithm was used to identify the key points of each point cloud, and the key points were adopted to establish a local reference frame for the basic points and calculate the fast point feature histograms (fpfh) descriptor. Then, the corresponding estimation algorithm of the least median of squares (LMeds) minimum median method was utilized to eliminate the inaccurate point correspondence and obtain the feature point pairs with corresponding 3D feature relationships. The transformation matrix required for coarse registration was calculated to complete the preliminary registration. Subsequently, according to the 3D-NDT algorithm, the point cloud data space was voxelized, and the probability distribution function was employed to complete the final point cloud for accurate registration. Finally, we used this method to match three groups of point cloud files, which were downloaded from the network with less noise and large-scale overlapped with more noise collected by Kinect V2.0 to the same spatial reference frame, and compared the classical 3D-NDT, ICP and other algorithms through accuracy analysis. The experimental results show that the proposed algorithm can achieve the high accuracy registration of point cloud data in indoor scenes with low iteration times and is less affected by noise. However, how to reduce the complexity of the algorithm appropriately and shorten the registration time needs further research.

3D normal distributions transform; 3D-Harris key points; fast point feature histograms; least median of squares; point cloud registration

TP 391

10.11996/JG.j.2095-302X.2020040567

A

2095-302X(2020)04-0567-09

2020-02-20；

2020-04-28

28 April，2020

20 February，2020；

國家自然科學(xué)基金項目(41771178)

National Natural Science Foundation of China (41771178)

范 強(1979-)，男，遼寧錦州人，副教授，博士。主要研究方向為遙感信息提取與專題地圖信息系統(tǒng)。E-mail：120853030@qq.com

FAN Qiang (1979-), male, associate professor, Ph.D. His main research interests cover remote sensing information extraction and thematic map information system. E-mail：120853030@qq.com