基于kd_tree算法和法向量估計(jì)的點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法

王 麗

宿州學(xué)院環(huán)境與測(cè)繪工程學(xué)院，安徽宿州，234000

地面三維激光掃描技術(shù)是近年發(fā)展起來的一種新的獲取空間三維信息的技術(shù)方法，其通過非接觸式掃描快速獲取物體表面信息，掃描的數(shù)據(jù)以離散點(diǎn)云形式存儲(chǔ)。數(shù)據(jù)具有高精度的特點(diǎn)，但同時(shí)包含物體信息的海量點(diǎn)云數(shù)據(jù)為后續(xù)數(shù)據(jù)處理帶來困難，幾十萬甚至上百萬的點(diǎn)云數(shù)據(jù)不僅影響數(shù)據(jù)處理的進(jìn)程，而且還影響結(jié)果的精度。為此，近幾年國內(nèi)外學(xué)者都在保證點(diǎn)云特征和精度的前提下，致力于研究點(diǎn)云數(shù)據(jù)精簡(jiǎn)的算法。如HAMANN等提出對(duì)于不同平面實(shí)體曲線重建點(diǎn)云簡(jiǎn)化方法[1]；WEIR等提出包圍盒算法，實(shí)現(xiàn)點(diǎn)云簡(jiǎn)化[2]；邢正全等提出正方體柵格劃分實(shí)現(xiàn)K近鄰搜索，利用法向量特征實(shí)現(xiàn)點(diǎn)云簡(jiǎn)化[3]；馬振國提出利用kd_tree索引實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)結(jié)構(gòu)劃分，并且結(jié)合點(diǎn)云曲率特征實(shí)現(xiàn)點(diǎn)云簡(jiǎn)化[4]，該方法需手動(dòng)介入，自動(dòng)化程度不夠。本文考慮三維數(shù)據(jù)結(jié)構(gòu)特點(diǎn)，提出一種基于kd_tree索引算法的法向量估計(jì)點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法。該方法利用kd_tree算法構(gòu)建空間數(shù)據(jù)樹結(jié)構(gòu)，搜索每個(gè)點(diǎn)K鄰域點(diǎn)，搜索速度快，可提高數(shù)據(jù)簡(jiǎn)化速度，結(jié)合最小二乘原理擬合每個(gè)鄰域點(diǎn)構(gòu)成的平面，估計(jì)每個(gè)點(diǎn)的法向量，并進(jìn)行法向量方向調(diào)整，計(jì)算每個(gè)點(diǎn)及其鄰域點(diǎn)法向量的夾角，設(shè)定夾角閾值，如果大于閾值，則刪除，從而實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)精簡(jiǎn)。

1 點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法

1.1 kd_tree算法

kd_tree索引算法是Friedman等人于1977年提出的一種數(shù)據(jù)檢索方法，kd_tree是k-dimension tree的縮寫，在K維空間對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行劃分，通過K近鄰查找即KNN算法，實(shí)現(xiàn)每個(gè)點(diǎn)K鄰域點(diǎn)的搜索。kd_tree利用最大方差劃分分裂維數(shù)，根據(jù)分裂維數(shù)所在結(jié)點(diǎn)確定根結(jié)點(diǎn)，通過根結(jié)點(diǎn)將空間數(shù)據(jù)劃分為左右兩個(gè)子空間，利用遞歸方法將左右子空間繼續(xù)劃分，直到所有點(diǎn)劃分完[5](表1)。

1.2 KNN算法

KNN算法，全稱是K-Nearest Neighbor algorithm，即K鄰域算法。本文選取K鄰域是選取距離P點(diǎn)歐式距離最近的K個(gè)點(diǎn)所組成的點(diǎn)的集合。計(jì)算P點(diǎn)的K近鄰點(diǎn)，需求出P點(diǎn)與其余n-1個(gè)點(diǎn)的歐式距離，然后將計(jì)算的歐式距離按值由小到大排序，選取排列在前面的K個(gè)點(diǎn)即為P點(diǎn)的K近鄰點(diǎn)。這種方法簡(jiǎn)單方便，但是對(duì)于海量點(diǎn)云而言，計(jì)算效率非常低，處理速度非常慢。因此本文首先利用kd_tree算法構(gòu)建空間點(diǎn)云數(shù)據(jù)拓?fù)浣Y(jié)構(gòu)，在kd_tree空間樹狀結(jié)構(gòu)上實(shí)現(xiàn)K近鄰搜索，搜索效率明顯提高。

1.3 點(diǎn)云法向量估計(jì)

對(duì)于每個(gè)點(diǎn)的法向量估計(jì)，結(jié)合最小二乘原理，對(duì)每個(gè)點(diǎn)的K鄰域點(diǎn)進(jìn)行局部擬合。在點(diǎn)云數(shù)據(jù)密集處，并且搜索半徑不大情況下，每個(gè)點(diǎn)的法向量可以用局部擬合平面的法向量表示[6]。因此，利用最小二乘原理對(duì)每個(gè)點(diǎn)K鄰域點(diǎn)進(jìn)行平面擬合，計(jì)算公式如下：

表1 kd_tree結(jié)構(gòu)構(gòu)建算法表

(1)

式中，n是局部擬合平面p的法向量，d表示擬合平面p到坐標(biāo)原點(diǎn)的距離。

平面p的法向量通過主成分分析法，分析協(xié)方差矩陣A的最小特征值所對(duì)應(yīng)的特征向量，此最小特征向量即為平面p的法向量。其中，協(xié)方差矩陣A公式如下：

(2)

(3)

1.4 點(diǎn)云精簡(jiǎn)

點(diǎn)云數(shù)據(jù)記錄每個(gè)點(diǎn)的三維坐標(biāo)信息，屬性信息可以反映出每個(gè)點(diǎn)所在位置、曲率等信息，曲率的大小反映局部曲面特征點(diǎn)信息的分布情況，曲率大則表明點(diǎn)云局部表面在該點(diǎn)變化劇烈，曲率小則表明點(diǎn)云局部表面在該點(diǎn)變化緩慢，特征不明顯，因此，可以利用曲率大小剔除非特征點(diǎn)[7]。同時(shí)，曲率的大小可以通過鄰域點(diǎn)法向量夾角的大小反映。鄰域點(diǎn)法向量夾角越大，則曲率變化不明顯；反之，如果鄰域點(diǎn)法向量夾角越小，則曲率變化越明顯[8]。因此，可以設(shè)置閾值τ，如果鄰域點(diǎn)法向量夾角小于閾值，則作為特征點(diǎn)保留，將鄰域點(diǎn)法向量夾角大于閾值的點(diǎn)作為非特征點(diǎn)刪除。這樣，實(shí)現(xiàn)利用鄰域點(diǎn)法向量特征實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)精簡(jiǎn)。

通過kd_tree算法實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)空間結(jié)構(gòu)樹狀劃分，搜索每個(gè)點(diǎn)K鄰域點(diǎn)(K一般最小取10，最大取20)，利用最小二乘原理擬合K鄰域點(diǎn)最佳平面[9]，計(jì)算平面法向量即每個(gè)點(diǎn)的法向量，通過法向量夾角大小和閾值比較，實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)精簡(jiǎn)。具體點(diǎn)云精簡(jiǎn)流程如圖1。

圖1 點(diǎn)云精簡(jiǎn)流程圖

2 實(shí)證分析

實(shí)驗(yàn)選取一把椅子點(diǎn)云數(shù)據(jù)，數(shù)據(jù)處理利用MATLAB2012b軟件編程實(shí)現(xiàn)。實(shí)驗(yàn)對(duì)每個(gè)點(diǎn)選取K近鄰點(diǎn)，通過最小二乘原理，擬合P點(diǎn)的平面方程，計(jì)算每個(gè)平面的法向量即為P點(diǎn)的法向量。

本實(shí)驗(yàn)通過對(duì)K值分別取10,15,20三個(gè)數(shù)值進(jìn)行實(shí)驗(yàn)，對(duì)閾值τ選取5°，3°，2°進(jìn)行實(shí)驗(yàn)，表2表示在閾值取5°時(shí)不同K值簡(jiǎn)化后的結(jié)果，表3表示閾值3°時(shí)不同K值簡(jiǎn)化后的結(jié)果。實(shí)驗(yàn)也對(duì)閾值取2°進(jìn)行實(shí)驗(yàn)，但是點(diǎn)云簡(jiǎn)化結(jié)果并不理想。點(diǎn)云簡(jiǎn)化后顯示模型如圖2所示。

表2 閾值τ選取5°實(shí)驗(yàn)結(jié)果

表3 閾值τ選取3°實(shí)驗(yàn)結(jié)果

圖2 點(diǎn)云模型圖

本實(shí)驗(yàn)選取K=15。根據(jù)kd_tree搜索法，選取的每個(gè)點(diǎn)15個(gè)近鄰點(diǎn)，前三個(gè)點(diǎn)近鄰點(diǎn)如表4所示，前三個(gè)點(diǎn)法向量估計(jì)值如表5所示。

表4 前3個(gè)點(diǎn)15近鄰

表5 前3個(gè)點(diǎn)法向量

表2表示夾角閾值取5°，K值取10,15,20時(shí)，點(diǎn)云簡(jiǎn)化率在80%左右。表3表示夾角閾值取3°，K值取10,15,20時(shí)，點(diǎn)云簡(jiǎn)化率在60%～70%左右。同時(shí)，圖2的(b)(c)圖反映點(diǎn)云在簡(jiǎn)化率83%和65%的椅子模型，和(a)圖原始點(diǎn)云椅子模型比較，可以看出簡(jiǎn)化率為65%的點(diǎn)云模型完全可以反映椅子的特征，同時(shí)，點(diǎn)云簡(jiǎn)化時(shí)間大大縮減。(d)圖反映的是夾角閾值取2°，K值取15近鄰點(diǎn)時(shí)，點(diǎn)云簡(jiǎn)化率在43%時(shí)椅子模型，(d)圖的模型并不理想，所以通過反復(fù)實(shí)驗(yàn)，本文方法K最佳取值可以取15，閾值τ取3°。

為了說明基于kd_tree算法和法向量估計(jì)的點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法的可行性，將法向量估計(jì)方法在K值取15，向量夾角閾值取3°時(shí)的點(diǎn)云簡(jiǎn)化模型和包圍盒算法點(diǎn)云簡(jiǎn)化模型進(jìn)行比較。

包圍盒簡(jiǎn)化方法即是將所有點(diǎn)云數(shù)據(jù)建立成一個(gè)長(zhǎng)方體包圍盒，并根據(jù)一定的分割條件將長(zhǎng)方體包圍盒進(jìn)行劃分，劃分成一定數(shù)量均勻小包圍盒，選取距離小包圍盒中心最近的點(diǎn)云數(shù)據(jù)來取代小包圍盒所有點(diǎn)，完成點(diǎn)云數(shù)據(jù)簡(jiǎn)化。圖3反映包圍盒簡(jiǎn)化方法和法向量估計(jì)的點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法在相同簡(jiǎn)化率時(shí)模型對(duì)比圖。

圖3(a)圖包圍盒算法點(diǎn)云簡(jiǎn)化圖對(duì)于椅子特征部位的反映并不理想，曲線部分通過點(diǎn)云簡(jiǎn)化后，變成直線特征，而圖3(b)基于法向量估計(jì)算法，簡(jiǎn)化后的點(diǎn)云對(duì)于椅子特征部位反映很好，曲線特征明顯。

圖3 兩種算法在相同簡(jiǎn)化率模型比較

3 結(jié) 語

針對(duì)三維激光掃描獲取的海量點(diǎn)云數(shù)據(jù)簡(jiǎn)化工作，基于kd_tree算法和法向量估計(jì)的點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法是一種能夠很好保留研究對(duì)象特征的簡(jiǎn)化算法。通過反復(fù)實(shí)驗(yàn)，證明該方法切實(shí)可行，能夠快速高效實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)精簡(jiǎn)，并對(duì)特征信息能夠很好保留，保證后續(xù)建模模型的精度。同時(shí)，點(diǎn)云數(shù)據(jù)精簡(jiǎn)精度取決于K的取值以及點(diǎn)云向量夾角閾值τ的選取，對(duì)于不同K值以及閾值τ會(huì)產(chǎn)生不同精簡(jiǎn)效果。K值越大，鄰近點(diǎn)云數(shù)據(jù)越多，擬合平面更精確，精度越高，閾值τ選取保證了點(diǎn)云精簡(jiǎn)率，所以要反復(fù)實(shí)驗(yàn)選取合適數(shù)值。