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

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

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

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

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

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

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

1.1 主成分分析法

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

(1)

圖1 主成分分析法

1.2 局部熵

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

1)λ1≥λ2≥λ3時(shí)，判定局部鄰域?yàn)榫€型。

2)λ1≈λ2≥λ3時(shí)，判定局部鄰域?yàn)槠矫妗?/p>

3)λ1≈λ2≈λ3時(shí)，判定局部鄰域?yàn)榍妗?/p>

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

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

(2)

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

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

(3)

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

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

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

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

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

K=argmin(Ef).

(4)

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

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

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

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

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

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

3 點(diǎn)云精簡算法驗(yàn)證

3.1 模擬數(shù)據(jù)實(shí)驗(yàn)

3.1.1 實(shí)驗(yàn)一

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

圖3 模擬數(shù)據(jù)A實(shí)驗(yàn)

3.1.2 實(shí)驗(yàn)二

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

圖4 模擬數(shù)據(jù)B實(shí)驗(yàn)

3.2 案例計(jì)算與分析

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

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

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

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

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

將龜?shù)裣顸c(diǎn)云分為3部分如圖8所示，1區(qū)域細(xì)節(jié)特征較多，2區(qū)域主要是平面區(qū)域，3區(qū)域包含大量曲面和少量平面區(qū)域。不同精簡方法在3個(gè)區(qū)域的精簡率如表1所示，4種方法在區(qū)域1的精簡率相近，說明4種方法在細(xì)節(jié)較多的區(qū)域的精簡效果相當(dāng)。但是在區(qū)域2這種平坦的區(qū)域，文中的方法和基于曲率采樣的方法的精簡率明顯低于其他兩種方法，且文中的方法精簡率比基于曲率采樣的精簡效果更好。對于區(qū)域3這樣曲面較多的區(qū)域，本文的精簡效果較差，主要是因?yàn)槲闹械木喫惴ㄖ饕峭ㄟ^剔除平坦區(qū)域的點(diǎn)集達(dá)到精簡的目的，這也是文中算法的局限性。

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

圖8 龜?shù)裣顸c(diǎn)云分塊圖

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

表2 不同方法精簡結(jié)果比較

4 結(jié)束語

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