基于kd_tree算法和法向量估計的點云數據精簡方法

王 麗

宿州學院環境與測繪工程學院，安徽宿州，234000

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

1 點云數據精簡方法

1.1 kd_tree算法

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

1.2 KNN算法

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

1.3 點云法向量估計

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

表1 kd_tree結構構建算法表

(1)

式中，n是局部擬合平面p的法向量，d表示擬合平面p到坐標原點的距離。

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

(2)

(3)

1.4 點云精簡

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

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

圖1 點云精簡流程圖

2 實證分析

實驗選取一把椅子點云數據，數據處理利用MATLAB2012b軟件編程實現。實驗對每個點選取K近鄰點，通過最小二乘原理，擬合P點的平面方程，計算每個平面的法向量即為P點的法向量。

本實驗通過對K值分別取10,15,20三個數值進行實驗，對閾值τ選取5°，3°，2°進行實驗，表2表示在閾值取5°時不同K值簡化后的結果，表3表示閾值3°時不同K值簡化后的結果。實驗也對閾值取2°進行實驗，但是點云簡化結果并不理想。點云簡化后顯示模型如圖2所示。

表2 閾值τ選取5°實驗結果

表3 閾值τ選取3°實驗結果

圖2 點云模型圖

本實驗選取K=15。根據kd_tree搜索法，選取的每個點15個近鄰點，前三個點近鄰點如表4所示，前三個點法向量估計值如表5所示。

表4 前3個點15近鄰

表5 前3個點法向量

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

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

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

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

圖3 兩種算法在相同簡化率模型比較

3 結 語

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