基于最優鄰域局部熵的點云精簡算法

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

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

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

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

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

1 基于特征維數的局部熵

1.1 主成分分析法

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

(1)

圖1 主成分分析法

1.2 局部熵

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

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

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

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

圖2 維數特征與熵函數取值分布圖

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

(2)

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

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

(3)

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

2 基于最優鄰域局部熵的點云精簡算法

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

2.1 最優鄰域的局部熵

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

K=argmin(Ef).

(4)

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

2.2 算法軟件實現

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

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

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

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

3 點云精簡算法驗證

3.1 模擬數據實驗

3.1.1 實驗一

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

圖3 模擬數據A實驗

3.1.2 實驗二

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

圖4 模擬數據B實驗

3.2 案例計算與分析

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

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

圖5 龜雕像原始點云數據

圖6 龜雕像點云上半部分不同精簡方法比較

圖7 龜雕像點云下半部分不同精簡方法比較

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

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

圖8 龜雕像點云分塊圖

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

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

4 結束語

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