范 強(qiáng)，劉 鵬，楊 俊，周沛希

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

范 強(qiáng)1，劉 鵬1，楊 俊2，周沛希1

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

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

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

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

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

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

圖1 初始匹配算法流程圖

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

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

1.1.1 Harris基本原理

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

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

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

1.1.2 3D-Harris提取特征點(diǎn)

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

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

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

利用微積分知識(shí)可以計(jì)算得到，，的值，即

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

1.1.3 3D-Harris算法流程

(1) 體素化整個(gè)點(diǎn)云空間；

(2) 從體素開(kāi)始，計(jì)算建立局部坐標(biāo)系，方向?yàn)榉ㄏ蛄糠较?，軸、軸與軸垂直，軸方向在平面內(nèi)任意，軸在平面內(nèi)與軸垂直；

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

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

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

1.2 FPFH快速點(diǎn)特征直方圖

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

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

算法流程：

(1) 迭代點(diǎn)云，計(jì)算法線；

(2) 點(diǎn)云中的每個(gè)點(diǎn)P，遍歷P周?chē)霃綖榈那蝮w內(nèi)的所有相鄰點(diǎn)，將該點(diǎn)集合命名為P；

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

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

(5) 計(jì)算查詢(xún)點(diǎn)P的簡(jiǎn)化特征直方圖SPFH；

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

1.3 LMeds刪除錯(cuò)誤對(duì)應(yīng)

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

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

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

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

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

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

2.1 3D-NDT算法原理

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

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

其中，為點(diǎn)云落在某個(gè)cell中的點(diǎn)的個(gè)數(shù)。

(3) 將下一幅的scan中的每一個(gè)點(diǎn)按照變換矩陣進(jìn)行變換；

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

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

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

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

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

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

2.3 逐步點(diǎn)云匹配方法

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

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

圖4 FPFH特征直方圖

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

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

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

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

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

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

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

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

4 結(jié)論與展望

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

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

[2] 王歡, 汪同慶, 李陽(yáng). 利用Kinect深度信息的三維點(diǎn)云配準(zhǔn)方法研究[J]. 計(jì)算機(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]. 自動(dòng)化學(xué)報(bào), 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] 彭真, 呂遠(yuǎn)健, 渠超, 等. 基于關(guān)鍵點(diǎn)提取與優(yōu)化迭代最近點(diǎn)的點(diǎn)云配準(zhǔn)[J]. 激光與光電子學(xué)進(jìn)展, 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] 趙夫群. 基于改進(jìn)ICP的點(diǎn)云配準(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é)合的點(diǎn)云配準(zhǔn)算法[J]. 計(jì)算機(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] 趙凱, 朱愿, 王任棟. 基于改進(jìn)NDT算法的城市場(chǎng)景三維點(diǎn)云配準(zhǔn)[J]. 軍事交通學(xué)院學(xué)報(bào), 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] 李春磊, 常智勇, 莫蓉. 基于改進(jìn)LMedS算法和貪心估計(jì)的相位立體匹配[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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] 朱德海, 郭浩, 蘇偉. 點(diǎn)云庫(kù)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；

國(guó)家自然科學(xué)基金項(xiàng)目(41771178)

National Natural Science Foundation of China (41771178)

范 強(qiáng)(1979-)，男，遼寧錦州人，副教授，博士。主要研究方向?yàn)檫b感信息提取與專(zhuān)題地圖信息系統(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