點云特征提取精簡方法研究

田 贏，陳裕漢，吳學群，劉 洋，韓 嘯，張豫寧

（1.昆明理工大學 國土資源工程學院，云南 昆明 650093；2.滇西應用技術大學 地球科學與工程學院，云南 大理 671000）

0 引言

隨著三維激光掃描技術的發(fā)展，點云數(shù)據(jù)現(xiàn)已被廣泛應用于多個領域，尤其是在物體的三維建模上。但原始點云數(shù)據(jù)量往往很龐大，且存在較多冗余點，如果直接對原始點云數(shù)據(jù)進行三維重建，不但不會明顯提高精度，而且會加大計算機的運行負擔，降低建模效率。因此，在盡可能保留模型特征的同時，對原始點云數(shù)據(jù)進行精簡是很有必要的。

近年來，針對點云精簡方法的研究，國內(nèi)外學者已做了大量工作?，F(xiàn)有的傳統(tǒng)方法包括：包圍盒法［1-2］、均勻/非均勻網(wǎng)格法［3］、隨機采樣法［4］、曲率采樣法［5］、局部熵法［6］、三角網(wǎng)格法［7］、聚類法［8］、概率分布法［9］等。其中，均勻網(wǎng)格法是先找到能包圍點云中所有點的立方體，然后將該立方體進一步細分成更小的立方體，并計算每個小立方體的中值點，之后用該中值點替代小立方體內(nèi)的點。均勻網(wǎng)格法運行速度快，但由于其對點云的特征點和非特征點進行無差別的精簡，所以導致精簡后的模型容易缺失特征信息。曲率采樣法依據(jù)在模型的不同位置處點云模型表面曲率的不同對點云進行精簡，此方法能夠保留一些特征點，但仍存在不足。Song 等［10］提出一種針對點云的全局聚類簡化方法，其根據(jù)指定的數(shù)據(jù)約簡比，找到原始輸入數(shù)據(jù)集的一個子集，然后通過輸入點集與簡化點集的最小幾何偏差得到全局最優(yōu)解。但該方法的缺點是時間復雜度高，近似的點—面距離可能會給出不精確的值。Markovic 等［11］利用一種基于ε 不敏感支持向量回歸（ε-SVR）的方法識別點云中的特征點，但該方法無法直接簡化非結(jié)構(gòu)化點云。Leal 等［12］介紹了一種通過估計點云的局部密度來簡化3D 點云的方法，該方法對異常值和噪聲具有魯棒性。付永健等［13］利用點云中的每個點及其近鄰點建立擬合曲面對鄰域點進行比較，從而完成點云的精簡，但該方法對領域點的個數(shù)比較敏感。賀一波等［14］根據(jù)點云的均方根曲率，利用k-means 聚類算法精簡點云，該方法對點云模型特征點保留較好，但對聚類數(shù)比較敏感。李佩佩等［15］單純地運用二分K-means 算法提取大于曲率閾值的點作為最終的精簡點，但此算法只適用于表面變化較大的點云模型，對于有較多平坦區(qū)域的點云模型則會產(chǎn)生較多空洞。

本文結(jié)合了閾值提取和二分K-means 聚類算法來控制特征點提取數(shù)量，可以方便地改變精簡后特征點與非特征點比例，同時使精簡率的控制也變得更加靈活。

1 本文方法介紹

1.1 基于法向量夾角提取整體特征點

點的法向量是重要的幾何性質(zhì)，被許多學者廣泛用于尋找折疊點和邊界點以及高質(zhì)量的曲面。在點云模型不同位置處點的法向量與其鄰近點法向量之間的夾角是不同的，本文利用這一特性提取點云模型的整體特征點。首先計算點云模型中每個點的法向量。對于法向量的計算，首先對原始點云構(gòu)建KD-Tree［16］，然后選取點云中的每一點，對其鄰近點進行搜索，將包含該點的鄰近點擬合成曲面，之后計算領域集的協(xié)方差矩陣，求出該矩陣的特征值與對應的特征向量。由主成分分析法可知，最小特征值對應的特征向量即為該擬合曲面的法向量［17］。具體為：假設采樣點Pi的鄰域集為P={P1，P2，…，Pk}，首先依據(jù)式（1）計算領域集的重心。

然后依據(jù)式（2）計算領域集的協(xié)方差矩陣：

求出該矩陣的特征值λ0、λ1、λ2(λ0≤λ1≤λ2)及其對應的特征向量v0、v1、v2，則最小特征值對應的特征向量v0就是采樣點Pi的法向量。之后計算每個點的法向量與其周圍領域點法向量之間的夾角，依據(jù)一定的閾值提取出整體特征點。依據(jù)不同閾值提取的結(jié)果如圖1 所示，其中綠色點為提取出的整體特征點。

Fig.1 Results of global feature point extraction圖1 整體特征點提取結(jié)果

1.2 依據(jù)曲率利用二分K-means聚類算法提取局部特征點

首先計算出點云的平均曲率，然后依據(jù)一定的聚類數(shù)k，利用二分K-means 聚類算法對非整體特征點計算出的平均曲率進行聚類。對生成的每個簇計算其平均曲率，以每個簇的平均曲率為分界點提取出大于平均曲率的點作為初步的局部特征點，將余下的點劃分到非特征點集。之后計算初步局部特征點的平均曲率，將大于平均曲率的點提取為最終的局部特征點。而對于小于閾值的點，則繼續(xù)將其劃分為非特征點。

1.2.1 點云平均曲率計算

點云中每個點的曲率是表征點云表面變化的一個重要評價指標。一般一個點的曲率越大，表明點所在的表面起伏越大，所以依據(jù)曲率可以很好地提取出點云模型中局部變化較大的點。

對于曲率的計算，首先利用KD-Tree 對點云中的每個點進行k領域搜索，然后依據(jù)最小二乘法將目標點與領域點進行曲面擬合。設曲面的參數(shù)方程為：

則曲面的第一基本公式為：

其中，G、E、F稱為該曲面的第一類基本參量。設(u0，v0)為曲面上的任意一點，則其與鄰近點的距離可表達為：

用泰勒公式對其展開為：

式（7）為曲面的第二基本公式，其中L、M、N為第二類基本參量。由式（4）、式（7）可得曲面的高斯曲率K和平均曲率H：

主曲率K1、K2與高斯曲率和平均曲率的關系為：

1.2.2 局部特征點提取

二分K-means 聚類算法是對K-means 聚類算法［18］的改進。該算法首先對每個簇進行二類的劃分，然后計算劃分出的子類誤差平方和與父類誤差平方和的差值，選擇差值最大的那個類為最終待劃分的類。最后對該類進行二類的劃分，并統(tǒng)計此時的簇數(shù)。若沒達到目標數(shù)則繼續(xù)進行上述操作，直到達到指定的類數(shù)。二分K-means 聚類算法克服了K-means 聚類算法收斂于局部最小的局限，在聚類效果上展現(xiàn)出了很好的穩(wěn)定性。

本文依據(jù)點云的平均曲率，利用二分K-means 聚類算法提取局部特征點，具體流程如下：①依據(jù)設定的聚類數(shù)對非整體特征點進行聚類；②計算每個類點云數(shù)據(jù)的平均曲率，對每個類提取出大于平均曲率的點作為初步的局部特征點，將其余的點劃分為非特征點；③計算初步局部特征點的平均曲率，將大于平均曲率的點提取為最終的局部特征點，將余下的點繼續(xù)劃分為非特征點。

提取的局部特征點效果如圖2 所示，其中紅色點為提取出的局部特征點。

Fig.2 Local feature point extraction results圖2 局部特征點提取結(jié)果

1.3 非特征點下采樣

對于非特征點，本文利用改進的體素精簡法對其進行下采樣，具體流程為：①構(gòu)建非特征點數(shù)據(jù)的最小包圍盒，并依據(jù)設置的最小體素的邊長將包圍盒不斷細分為一個個小的體素；②計算體素內(nèi)點云的重心與體素內(nèi)的點到重心的距離，保留離重心最近的點，遍歷每個體素，最終保留下來的點即為簡化后的非特征點。

將簡化后的非特征點與提取出的整體特征點、局部特征點進行融合，即為最終精簡的點云。

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

本文利用PCL 點云庫、Microsoft Visual Studio 2015 開發(fā)平臺，并使用斯坦福點云數(shù)據(jù)集Bunny、Gargoyles、Skull對本文方法進行驗證。為驗證本文所提特征提取方法的有效性，將只利用改進的體素精簡法精簡的點云與本文方法精簡的點云進行對比，然后與傳統(tǒng)的隨機采樣法、曲率采樣法和文獻［15］中的方法在精簡結(jié)果、精簡后三維重構(gòu)模型與精簡誤差3 個方面進行對比。其中，Bunny、Gargoyles、Skull 的原始點云數(shù)據(jù)量分別為35 947、25 039、20 002。

2.1 特征提取實驗分析

本文從整體和局部兩方面對特征點進行約束，只采用改進的體素精簡法精簡的點云與利用本文方法精簡的點云對比如圖3 所示，其中精簡率都約為50%。由圖3 可見，只利用改進的體素精簡法精簡的結(jié)果在邊角等曲率較大處會出現(xiàn)輪廓缺失，如Bunny 的耳朵輪廓、底部邊角處，Gargoyles 的耳朵輪廓、翅膀邊緣處，Skull的頭頂文字、牙齒等處都出現(xiàn)了不同程度的缺失，而本文精簡方法的輪廓卻保存相對完整。

Fig.3 Comparison between the improved voxel reduction method and the proposed method圖3 改進的體素精簡法與本文方法對比

2.2 精簡結(jié)果分析

Bunny 與傳統(tǒng)方法對比的精簡結(jié)果如圖4（a）所示，Gargoyles 與傳統(tǒng)方法對比的精簡結(jié)果如圖4（b）所示，Skull與傳統(tǒng)方法對比的精簡結(jié)果如圖4（c）所示，精簡率都約為50%。如圖4 所示，由于隨機采樣法是對點云數(shù)據(jù)進行無差別的精簡，所以導致Bunny 和Gargoyles 的耳朵輪廓缺失，Skull 的頭頂文字模糊不清，并且Bunny 的背部、Gargoyles 的底盤存在大量小的空洞，Skull 的額頭部分點云分布也不均勻；曲率采樣法由于是提取出曲率較大的點，導致平坦處的點會被大量舍去，所以Bunny、Gargoyles 的耳朵輪廓保存完好，Skull 的頭頂文字也較清晰，但是Bunny 的背部、Gargoyles 的底盤和Skull 額頭處的點云基本都被舍去；本文方法不僅保證了Bunny、Gargoyles 耳朵輪廓的完整和Skull 頭頂文字的清晰，而且使Bunny 的背部、Gargoyles的底盤和Skull額頭處的點云也相對均勻。

Fig.4 Reduction results of the proposed method and traditional methods圖4 本文方法與傳統(tǒng)方法精簡結(jié)果

Bunny 與文獻［15］的方法對比的精簡結(jié)果如圖5（a）所示，Gargoyles 與文獻［15］的方法對比的精簡結(jié)果如圖5（b）所示，Skull 與文獻［15］對比的精簡結(jié)果如圖5（c）所示，其中Bunny的精簡率約為62%，Gargoyles 的精簡率約為69%，Skull 的精簡率約為64%。由于文獻［15］的方法也是提取曲率較大的點，因此Bunny、Gargoyles 數(shù)據(jù)集的耳朵輪廓，Skull 的頭頂文字可以保存得很好，但是Bunny 的背部、Gargoyles 的底盤和Skull 的額頭仍有較大空洞。而本文方法在相同的精簡率下，不但保證了Bunny、Gargoyles 耳朵輪廓和Skull 頭頂文字的清晰，而且使Bunny 的背部、Gargoyles 底盤和Skull額頭處的點云也相對均勻。

Fig.5 Reduction results of the proposed method and method in literature ［15］圖5 本文方法與文獻［15］方法精簡結(jié)果

2.3 三維重建效果對比

在三維重建效果對比方面，本文分別以約30%、50%、70%的精簡率與傳統(tǒng)方法進行對比，以Bunny 約62%的精簡率、Gargoyles 約69%的精簡率、Skull 約64%的精簡率與文獻［15］的方法進行對比。Bunny 與傳統(tǒng)方法對比的重構(gòu)結(jié)果如圖6 所示，Gargoyles 與傳統(tǒng)方法對比的重構(gòu)結(jié)果如圖7 所示，Skull 與傳統(tǒng)方法對比的重構(gòu)結(jié)果如圖8 所示。Bunny 與文獻［15］方法對比的重構(gòu)結(jié)果如圖9（a）所示，Gargoyles 與文獻［15］方法對比的重構(gòu)結(jié)果如圖9（b）所示，Skull與文獻［15］方法對比的重構(gòu)結(jié)果如圖9（c）所示。

Fig.6 Bunny simplified surface reconstruction results of the traditional method and the proposed method圖6 傳統(tǒng)方法及本文方法的Bunny精簡曲面重構(gòu)結(jié)果

Fig.7 Gargoyles simplified surface re(ccoi)nstruction results of the traditional method and the proposed method圖7 傳統(tǒng)方法及本文方法的Gargoyles精簡曲面重構(gòu)結(jié)果

Fig.8 Skull simplified surface reconstruction results of the traditional method and the proposed method圖8 傳統(tǒng)方法及本文方法的Skull精簡曲面重構(gòu)結(jié)果

Fig.9 Surface reconstruction results of the proposed method and method in literature ［15］圖9 本文方法與文獻［15］精簡方法曲面重構(gòu)結(jié)果

如圖6（a）、圖7（a）和圖8（a）所示，隨機采樣法在各精簡率下模型特征缺失較嚴重，Bunny 的眼部、側(cè)面，Gargoyles 的爪子和Skull 的頭頂文字、額頭標記、牙齒輪廓等細節(jié)特征已模糊不清，且精簡率越低，該現(xiàn)象越明顯。曲率采樣法可以很好地保留模型細節(jié)特征，但對于平坦區(qū)域，則會造成模型嚴重變形。如圖6（b）、圖7（b）和圖8（b）所示，雖然Bunny 的眼睛、側(cè)面，Gargoyles 的爪子和Skull 的頭頂文字、額頭標記、牙齒輪廓等處細節(jié)特征較為明顯，但Bunny 的背部兩邊翹起，中間低洼，已嚴重變形，Gargoyles的腿部向里凹陷，底部向外凸起，而Skull 的頭頂嚴重突起，已失去物體原本的面貌，且隨著精簡率的降低，變形更加嚴重。而本文方法不僅在Bunny 的眼部、側(cè)面，Gargoyles的爪子和Skull 的頭頂文字、額頭標記、牙齒輪廓等處的細節(jié)特征明顯，而且Bunny 的背部相對飽滿，Gargoyles 的腿部無明顯凹陷，底部相對平坦，Skull 的頭顱形狀也未發(fā)生較大變形。

以下是與文獻［15］方法的對比，從圖9（a）、圖9（b）和圖9（c）可以看出，文獻［15］的方法和本文方法都可以保證模型細節(jié)特征突出，但文獻［15］的方法針對較平坦區(qū)域仍會發(fā)生變形，如Bunny 的背部仍然呈現(xiàn)兩邊高、中間低的形態(tài)，Gargoyles 的底部仍然突起，Skull頭顱側(cè)面發(fā)生凹陷，而本文方法沒有上述問題。

2.4 精簡誤差對比

本文利用Hausdorff 距離和信息熵來評定點云精簡精度，Hausdorff 距離可以描述兩個點集之間的相似程度。假設點集A=(a1，a2，…，an)，B=(b1，b2，…，bn)，則可以根據(jù)式（13）求得A、B點集之間的Hausdorff距離。

其中，h(A，B)=max min‖a-b‖，a∈A，b∈B。Hausdorff 距離越小，代表兩數(shù)據(jù)集越相近，精簡精度越高。信息熵可以定量地評定信息量大小，因此可用其評定精簡后點云的特征信息。熵值越大，表示所含的特征信息越豐富。設點集中一點為Pi，鄰域點集為P=（p1，p2，…，p）j，則該點的信息熵可以用式（14）表示。

其中，Ei表示點Pi的信息熵，hi、hj表示點Pi、Pj的曲率概率分布，ci、cj表示點Pi、Pj的平均曲率，則整個數(shù)據(jù)集的信息熵為：

本文方法與傳統(tǒng)方法Hausdorff 距離對比的精簡結(jié)果如表1 所示，本文方法與傳統(tǒng)方法信息熵對比的精簡結(jié)果如表2 所示。其中，Bunny、Gargoyles 和Skull 的精簡率都約為50%。從表1 可以看出，曲率采樣法精簡結(jié)果的Hausdorff 距離數(shù)值都較高，這是因為曲率采樣法只保留曲率較大處的點，而對于較平坦區(qū)域的點則會大量舍去，從而造成精簡后的點云與原始點云差異較大，因此Hausdorff 距離較大。同時可以看出，不管是Bunny、Gargoyles 還是Skull數(shù)據(jù)集，本文方法相較于傳統(tǒng)方法精簡結(jié)果，Hausdorff 距離都是最小的。如表2 所示，在3 個數(shù)據(jù)集上，本文方法的信息熵都是最高的。由此可以看出本文方法相較于傳統(tǒng)方法，保留的特征信息最多。

Table 1 Hausdorff distance reduction results of the proposed method and traditional methods表1 本文方法與傳統(tǒng)方法Hausdorff 距離精簡結(jié)果

Table 2 Information entropy reduction results of the proposed method and traditional methods表2 本文方法與傳統(tǒng)方法信息熵精簡結(jié)果

本文方法與文獻［15］方法Hausdorff 距離對比的精簡結(jié)果如表3 所示，本文方法與文獻［15］方法信息熵對比的精簡結(jié)果如表4 所示。其中，Bunny 的精簡率約為62%，Gargoyles 的精簡率約為69%，Skull 的精簡率約為64%。從表3 可以看出，在相同的精簡率下，本文方法同樣比文獻［15］方法精簡的Hausdorff 距離要小。從表4 可以看出，在3 個數(shù)據(jù)集上，本文方法相比于文獻［15］的方法，信息熵都是最高的。由此可以看出，本文方法具有較高的精簡精度。

Table 3 Hausdorff distance reduction results of the proposed method and the method in reference ［15］表3 本文方法與文獻［15］方法Hausdorff 距離精簡結(jié)果

Table 4 Information entropy reduction results of the proposed method and the method in reference ［15］表4 本文方法與文獻［15］方法信息熵精簡結(jié)果

3 結(jié)語

本文利用法向夾角與基于曲率的二分K-means 聚類算法提取出模型中的特征點，在一定程度上改善了依據(jù)單一閾值提取特征點效果較差的問題。對于非特征點則利用改進的體素精簡法進行大比例的精簡，從而在保證模型完整性的同時，較好地保留了特征點，且重建后的模型細節(jié)特征也較為突出。經(jīng)實驗證明，本文算法在保證精簡率的同時，也具有較高的精簡精度。但是因二分K-means 聚類算法不穩(wěn)定，不能保證每次都能獲得很好的聚類效果，所以導致局部特征點的提取效果也毀譽參半。同時由于本文算法需要計算點云曲率，并對曲率進行聚類劃分，因此時間復雜度會比傳統(tǒng)的精簡方法略高。下一步工作需要對點云特征提取算法的時間復雜度和穩(wěn)定性方面進行深入研究。