田 贏，陳裕漢，吳學(xué)群，劉 洋，韓 嘯，張?jiān)?/p>

（1.昆明理工大學(xué) 國土資源工程學(xué)院，云南 昆明 650093；2.滇西應(yīng)用技術(shù)大學(xué) 地球科學(xué)與工程學(xué)院，云南 大理 671000）

0 引言

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

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

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

1 本文方法介紹

1.1 基于法向量夾角提取整體特征點(diǎn)

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

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

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

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

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

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

1.2.1 點(diǎn)云平均曲率計(jì)算

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

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

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

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

用泰勒公式對其展開為：

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

主曲率K1、K2與高斯曲率和平均曲率的關(guān)系為：

1.2.2 局部特征點(diǎn)提取

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

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

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

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

1.3 非特征點(diǎn)下采樣

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

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

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

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

2.1 特征提取實(shí)驗(yàn)分析

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

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

2.2 精簡結(jié)果分析

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

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

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

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

2.3 三維重建效果對比

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

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

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

2.4 精簡誤差對比

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

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

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

本文方法與傳統(tǒng)方法Hausdorff 距離對比的精簡結(jié)果如表1 所示，本文方法與傳統(tǒng)方法信息熵對比的精簡結(jié)果如表2 所示。其中，Bunny、Gargoyles 和Skull 的精簡率都約為50%。從表1 可以看出，曲率采樣法精簡結(jié)果的Hausdorff 距離數(shù)值都較高，這是因?yàn)榍什蓸臃ㄖ槐Ａ羟瘦^大處的點(diǎn)，而對于較平坦區(qū)域的點(diǎn)則會(huì)大量舍去，從而造成精簡后的點(diǎn)云與原始點(diǎn)云差異較大，因此Hausdorff 距離較大。同時(shí)可以看出，不管是Bunny、Gargoyles 還是Skull數(shù)據(jù)集，本文方法相較于傳統(tǒng)方法精簡結(jié)果，Hausdorff 距離都是最小的。如表2 所示，在3 個(gè)數(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é)果

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

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

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

3 結(jié)語

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