林 松，田林亞，畢繼鑫，施貴剛，朱依民, 聞 亞

(1. 河海大學 地球科學與工程學院，江蘇 南京 211100； 2. 浙江華東測繪與工程安全技術有限公司，浙江 杭州 310014； 3. 安徽建筑大學 土木工程學院，安徽 合肥 230099； 4. 安徽省教育廳 無人機開發(fā)及數(shù)據(jù)應用重點實驗室，安徽 馬鞍山 243031)

隨著三維激光掃描技術的發(fā)展，獲取高精度高密度的點云數(shù)據(jù)已經(jīng)十分普遍，因此掃描得到的點云個數(shù)往往是幾十萬、幾百萬甚至幾億。在現(xiàn)有的計算機硬件下，龐大的數(shù)據(jù)量已經(jīng)成為計算機計算和存儲的負擔。為了提高數(shù)據(jù)處理的效率，在保留數(shù)據(jù)特征且不影響模型重建精度的前提下可以刪除部分點云數(shù)據(jù)，達到點云精簡的目的。

國內外研究學者針對點云精簡的算法進行了大量的研究，文獻[1]提出了包圍盒法，建立空間體素格網(wǎng)，采用每個格網(wǎng)內的中心點代替格網(wǎng)內其他點，之后文獻[2]提出了均勻格網(wǎng)法，文獻[3]提出了非均勻格網(wǎng)精簡點云數(shù)據(jù)，這類基于體素格網(wǎng)的方法原理簡單，但是容易丟失細節(jié)特征。Chen Y H 等[4]提出了一種基于三角格網(wǎng)的點云精簡算法，利用向量加權算法對三角格網(wǎng)片面進行冗余判斷，刪除冗余三角形以達到精簡點云的目的，該方法也未考慮點云特征的問題。近年來，部分學者將曲率值作為判斷數(shù)據(jù)點是否是特征點的依據(jù)[5-6]，李金濤等人[7]提出一種基于曲率分級的精簡方法，對歸一化后的曲率值分級，根據(jù)不同等級的點云數(shù)據(jù)設置不同保留比例，但是基于曲率的點云精簡方法容易在平坦區(qū)域出現(xiàn)空洞，造成數(shù)據(jù)缺失。還有隨機采樣法[8]，其設計一個隨機函數(shù)，保證每個數(shù)據(jù)點有相同的概率被刪除，同樣該方法容易丟失細節(jié)特征，且每次運行的結果不一致，精簡的精度無法控制。H Benhabiles等[9]將聚類分析與由粗到細策略相結合，提出一種能很好的保留銳利邊緣點的方法。陳璋雯等[10]采用模糊熵迭代法精簡點云，該方法雖然能有效的保留點云的細節(jié)特征，但是大量的曲率計算使得該算法的效率不高。

針對傳統(tǒng)的點云精簡方法中容易丟失細節(jié)特征的問題，文中提出了一種基于最優(yōu)鄰域局部熵的點云精簡算法。首先利用主成分分析法(Principal Component Analysis，PCA)[11]計算數(shù)據(jù)點局部鄰域的3個特征值，利用這3個特征值構造維數(shù)特征，其次基于維度特征計算局部鄰域熵，根據(jù)局部熵值確定最優(yōu)鄰域，最后依據(jù)特征值之間的關系和局部信息熵剔除平坦區(qū)域的數(shù)據(jù)點完成點云精簡。

1 基于特征維數(shù)的局部熵

1.1 主成分分析法

主成分分析法是一種設法將原有變量重新組合成一組新的互相無關的幾個綜合變量，同時根據(jù)實際需要從中可以取出幾個較少的綜合變量盡可能多地反映原來變量信息的統(tǒng)計方法，也是數(shù)學上用來降維的一種方法。如圖1所示，在點云數(shù)據(jù)處理中常采用PCA算法依據(jù)某點的鄰域點坐標估計該點的法向量，設P點的鄰域點為Pi=[xiyizi]，由式(1)可得到P點的矩陣M為：

(1)

圖1 主成分分析法

1.2 局部熵

根據(jù)K鄰域內的點集進行主成分分析得到點云數(shù)據(jù)分布的特征值λ1、λ2、λ3(λ1≥λ2≥λ3)，特征值具有以下特性：

1)λ1≥λ2≥λ3時，判定局部鄰域為線型。

2)λ1≈λ2≥λ3時，判定局部鄰域為平面。

3)λ1≈λ2≈λ3時，判定局部鄰域為曲面。

圖2 維數(shù)特征與熵函數(shù)取值分布圖

因此可以依式(2)定義維數(shù)特征[12]，維數(shù)特征描述了局部點云數(shù)據(jù)的空間分布特征。

(2)

根據(jù)香農提出的信息熵理論，可以依據(jù)式(3)定義局部熵函數(shù)[13]，其中：

Ef=-a1Dln(a1D)-a2Dln(a2d)-a3Dln(a3D).

(3)

則維數(shù)特征與熵函數(shù)取值分布如圖2所示。從局部熵函數(shù)可以看出Ef越小，表明其中一種維度特征越明顯，說明局部數(shù)據(jù)點的空間分布特性越相近[14]。

2 基于最優(yōu)鄰域局部熵的點云精簡算法

點云精簡的主要目的是保留特征點以保留細節(jié)特征，現(xiàn)有的精簡算法通過某點的曲率來判定該點是否為特征點，通常認為曲率值大的點是特征點，曲率值小的點是非特征點，并刪除。曲率值小的點往往是平坦區(qū)域的數(shù)據(jù)點，所以精簡的過程主要是過濾局部曲面較為平坦的點集，主要剔除平面或近似平面內的部分點集。根據(jù)某點鄰域內的點集計算局部熵，若局部熵值小于閾值，且3個特征值關系符合平面特征，則將該點刪除，以此完成點云的精簡。

2.1 最優(yōu)鄰域的局部熵

不同的鄰域大小計算得到的局部熵值不同，為了充分體現(xiàn)局部數(shù)據(jù)點的空間分布特性，應該找出不同鄰域下局部熵值最小的K值，即滿足式(4)。因此對于不同的K值，滿足Ef最小時所對應的鄰域大小稱為最優(yōu)鄰域。

K=argmin(Ef).

(4)

因此可以設置最大K值Kmax、最小K值Kmin和步長Δk，計算在區(qū)間[Kmin,Kmax]內的局部熵，并找出在該區(qū)間內Ef的最小值Efmin，用Efmin作為該點最優(yōu)鄰域的局部熵。

2.2 算法軟件實現(xiàn)

基于最優(yōu)鄰域局部熵的點云精簡算法的流程如下：

1)首先設置K值的取值范圍[Kmin，Kmax]和步長Δk，采用主成分分析法計算Ki鄰域下Pi點的3個特征值λ1、λ2、λ3，并依據(jù)式(2)、式(3)計算局部熵值，保存每次步長計算得到的局部熵值到鏈表E。

2)查詢鏈表E中最小熵值對應的K值，將其標記為Pi點的最優(yōu)鄰域，并保存該鄰域下的3個特征值到鏈表T。

3)遍歷所有點，每個點的最優(yōu)鄰域局部熵值和最優(yōu)鄰域特征值都保存在鏈表E和鏈表T中，剔除鏈表E中局部熵值小于閾值，且鏈表T中對應的特征值符合平面特征的點。

3 點云精簡算法驗證

3.1 模擬數(shù)據(jù)實驗

3.1.1 實驗一

采用模擬點云數(shù)據(jù)A如圖3(a)所示進行實驗，模擬數(shù)據(jù)中包含平面點云和曲面點云兩種。其中模擬數(shù)據(jù)為均勻數(shù)據(jù)，故采用統(tǒng)一的K值，取K=15，不確定度閾值為0.2，分離出曲面點如圖3(b)所示，提取的平面點如圖3(c)所示，實驗表明基于局部熵值和3個特征值能找出平面點云數(shù)據(jù)。

圖3 模擬數(shù)據(jù)A實驗

3.1.2 實驗二

采用另一種模擬數(shù)據(jù)B如圖4(a)所示，同樣取K=15，不確定度閾值為0.2，分離出曲面點如圖4(b)所示，提取的平面點如圖4(c)所示，結果表明本文的方法不僅能夠剔除平面中的點云，還能剔除部分曲面曲率較小的點。因此對需要精簡的對象中每個點云計算其最優(yōu)鄰域的局部熵，若其最優(yōu)鄰域的局部熵值小于給定的閾值，并且3個特征值滿足λ1≈λ2≥λ3時，則可將該點刪除。

圖4 模擬數(shù)據(jù)B實驗

3.2 案例計算與分析

采用Riegl-VZ1000對某公園內龜?shù)裣襁M行高密度掃描，掃描點云數(shù)據(jù)如圖5所示。本文算法中設置最大K值Kmax=50、最小K值Kmin=10和步長Δk=2，不確定度閾值為0.2，最終壓縮率為72.60%。

為了對本文方法進行評價，將本文的方法與傳統(tǒng)的基于曲率采樣、包圍盒法和隨機采樣3種方法實驗結果進行比較。采用基于曲率采樣、包圍盒法和隨機采樣3種方法將原始點云數(shù)據(jù)壓縮至72%左右，各方法實驗結果如圖6和圖7所示。

圖5 龜?shù)裣裨键c云數(shù)據(jù)

圖6 龜?shù)裣顸c云上半部分不同精簡方法比較

圖7 龜?shù)裣顸c云下半部分不同精簡方法比較

將龜?shù)裣顸c云分為3部分如圖8所示，1區(qū)域細節(jié)特征較多，2區(qū)域主要是平面區(qū)域，3區(qū)域包含大量曲面和少量平面區(qū)域。不同精簡方法在3個區(qū)域的精簡率如表1所示，4種方法在區(qū)域1的精簡率相近，說明4種方法在細節(jié)較多的區(qū)域的精簡效果相當。但是在區(qū)域2這種平坦的區(qū)域，文中的方法和基于曲率采樣的方法的精簡率明顯低于其他兩種方法，且文中的方法精簡率比基于曲率采樣的精簡效果更好。對于區(qū)域3這樣曲面較多的區(qū)域，本文的精簡效果較差，主要是因為文中的精簡算法主要是通過剔除平坦區(qū)域的點集達到精簡的目的，這也是文中算法的局限性。

文獻[15]、文獻[16]從表面積和總三角形數(shù)兩個參數(shù)來評價精簡的效果，整體的表面積總和以及總三角形個數(shù)并不能體現(xiàn)不同方法保留細節(jié)特征的效果，因此文中根據(jù)雕像的3個區(qū)域采用不同精簡方法后三角形個數(shù)占比來分析不同方法的細節(jié)特征保留效果，如表2所示。本文算法在區(qū)域2處的三角形個數(shù)占比低于其他方法和原始點云的三角形占比，區(qū)域1和區(qū)域3處的三角形個數(shù)占比均高于其他方法和原始點云的三角形占比，說明本文的精簡方法在保存細節(jié)特征較好的同時剔除了更多平坦區(qū)域的數(shù)據(jù)點。

圖8 龜?shù)裣顸c云分塊圖

表1 不同精簡方法在3個區(qū)域的精簡率比較

表2 不同方法精簡結果比較

4 結束語

隨著儀器設備的不斷更新，獲取海量的點云數(shù)據(jù)已經(jīng)非常普遍，海量的點云數(shù)據(jù)給計算和存儲帶來了新的挑戰(zhàn)，龐大的數(shù)據(jù)中有大量的冗余信息需要剔除，因此點云的精簡對于數(shù)據(jù)的進一步應用有著十分重要的意義。點云精簡是點云數(shù)據(jù)預處理過程中重要步驟之一，精簡的效果直接影響后續(xù)數(shù)據(jù)處理的精度，因此精簡過程中需要最大限度的保留細節(jié)特征的同時剔除平坦區(qū)域的點云。文中提出了一種基于最優(yōu)鄰域局部熵的精簡方法，該方法首先通過PCA計算局部區(qū)域的3個特征值，并且基于這3個特征值構造特征維度計算局部信息熵，然后根據(jù)局部信息熵找出最優(yōu)鄰域，最后根據(jù)3個特征值的關系與局部信息熵判斷局部形狀是否符合平面特征。通過與傳統(tǒng)的3種方法實驗比較，文中的方法在同樣壓縮率的情況下能更好的保留細節(jié)特征。