基于局部熵的點(diǎn)云精簡(jiǎn)算法

董嘉敏 田華

摘 ?要： 針對(duì)目前流行的三維物體激光掃描儀獲取的點(diǎn)云數(shù)據(jù)量大，冗余度高等問(wèn)題，提出一種基于信息熵的點(diǎn)云精簡(jiǎn)算法。首先，定義數(shù)據(jù)點(diǎn)的曲率、點(diǎn)到鄰域點(diǎn)重心的距離、點(diǎn)到鄰域點(diǎn)的平均距離的倒數(shù)，三者乘積為權(quán)值積;然后，使用K?means聚類算法劃分點(diǎn)云數(shù)據(jù)，根據(jù)類內(nèi)估計(jì)曲率差值區(qū)分特征區(qū)域與非特征區(qū)域;最后，針對(duì)特征區(qū)域，利用提出的精簡(jiǎn)方法精簡(jiǎn)點(diǎn)云。實(shí)驗(yàn)結(jié)果表明，該方法計(jì)算相對(duì)簡(jiǎn)單，能夠有效避免孔洞現(xiàn)象，同時(shí)，更好地保留了點(diǎn)云數(shù)據(jù)的原始物理特征。

關(guān)鍵詞： 點(diǎn)云精簡(jiǎn); 信息熵; K?means算法; 特征區(qū)域區(qū)分; 點(diǎn)云數(shù)據(jù); 曲率估計(jì)

中圖分類號(hào)： TN911?34; TP391.9 ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2020）01?0020?04

A point cloud reduction algorithm based on local entropy

DONG Jiamin， TIAN Hua

Abstract： A point cloud reduction algorithm based on information entropy is proposed to deal with the large amount of point cloud data and high redundancy produced by the popular three?dimensional laser scanner. Firstly， the product of curvature of the data points， the distance from the points to the center of gravity of the neighborhood points， and the reciprocal of the average distance from the points to the neighborhood points is defined as the product of weight; secondly， the K?means clustering algorithm is used to classify the point cloud data， and the characteristic region and the non?characteristic region are distinguished according to the estimated curvature difference; finally， for the characteristic region， the proposed reduction algorithm is used to reduce the point cloud. The experimental results show that the calculation process of the proposed algorithm is relatively simple， which can effectively avoid the hole phenomenon， and preserve the original physical characteristics of the point cloud data better.

Keywords： point cloud reduction; information entropy; K?means algorithm; characteristic region distinction; point cloud data; curvature estimation

0 ?引 ?言

三維重建技術(shù)一直是計(jì)算機(jī)視覺(jué)、逆向工程學(xué)和計(jì)算機(jī)圖形學(xué)等熱門研究領(lǐng)域的研究重點(diǎn)[1]。關(guān)于點(diǎn)云技術(shù)三維重建，已經(jīng)有不少的研究工作和成果[2?3]。隨著FreeScanX3等三維物體激光掃描儀不斷推陳出新，點(diǎn)云數(shù)據(jù)的獲得變得更加方便，同時(shí)點(diǎn)云數(shù)據(jù)的精度也非常高。然而，如此密集的點(diǎn)云數(shù)據(jù)中卻存在著大量的冗余數(shù)據(jù)，這些冗余數(shù)據(jù)極大地增加了點(diǎn)云數(shù)據(jù)的存儲(chǔ)開銷和計(jì)算開銷，從而影響到曲面擬合和模型生成等重要后續(xù)工作的效率。綜上所述，點(diǎn)云數(shù)據(jù)的精簡(jiǎn)工作對(duì)于物體的三維重建和繪制工作是非常重要的[4]。

近年來(lái)，許多學(xué)者對(duì)點(diǎn)云精簡(jiǎn)的研究做出了貢獻(xiàn)并取得了很大的成功。根據(jù)對(duì)點(diǎn)云數(shù)據(jù)精簡(jiǎn)的原則，現(xiàn)有的點(diǎn)云精簡(jiǎn)方法可以分為兩類：基于網(wǎng)格的簡(jiǎn)化和基于點(diǎn)的簡(jiǎn)化?；诰W(wǎng)格的簡(jiǎn)化方法主要通過(guò)構(gòu)造多邊形網(wǎng)格（三角形網(wǎng)格或四邊形網(wǎng)格），依據(jù)一些規(guī)則來(lái)判定這些網(wǎng)格的重要性，刪除冗余網(wǎng)格的邊來(lái)實(shí)現(xiàn)精簡(jiǎn)。這些方法的不足之處在于網(wǎng)格的生成需要花費(fèi)大量的時(shí)間和存儲(chǔ)。相比較這類方法而言，基于點(diǎn)的簡(jiǎn)化方法直接對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行精簡(jiǎn)而不用構(gòu)建任何網(wǎng)格。文獻(xiàn)[5]采用K均值聚類算法在空間域中將相似點(diǎn)聚集在一起，并使用最大法向量偏差作為聚類分散的度量，將聚集的點(diǎn)集劃分為特征域中的一系列子聚類，提出一種新的劃分和細(xì)分方法，實(shí)現(xiàn)對(duì)點(diǎn)云的精簡(jiǎn);文獻(xiàn)[6]針對(duì)散亂點(diǎn)云簡(jiǎn)化中易丟失幾何特征及潛在曲面形狀信息的問(wèn)題，采用基于泊松分布的區(qū)域生長(zhǎng)法自適應(yīng)檢測(cè)特征點(diǎn)，通過(guò)設(shè)定不同的聚類閾值，運(yùn)用不同的簡(jiǎn)化策略簡(jiǎn)化點(diǎn)云數(shù)據(jù);文獻(xiàn)[7]運(yùn)用多判別參數(shù)混合的方法首先識(shí)別特征點(diǎn)并保留，然后對(duì)剩余點(diǎn)云數(shù)據(jù)K?means聚類，根據(jù)類內(nèi)最大曲率差作為細(xì)分標(biāo)準(zhǔn)，最終完成特征保持的點(diǎn)云數(shù)據(jù)精簡(jiǎn)。

這些不同的基于點(diǎn)的簡(jiǎn)化方法有一個(gè)共同點(diǎn)，就是先評(píng)估點(diǎn)云數(shù)據(jù)中每個(gè)點(diǎn)的重要性，通過(guò)刪除不重要的點(diǎn)完成點(diǎn)云數(shù)據(jù)的精簡(jiǎn)，因此評(píng)估參數(shù)就顯得尤為重要。本文提出一種基于信息熵的點(diǎn)云精簡(jiǎn)算法，針對(duì)以往最小二乘法擬合曲面計(jì)算曲率過(guò)于復(fù)雜耗時(shí)，提出一種新的曲率估計(jì)方法，并定義數(shù)據(jù)點(diǎn)的曲率、點(diǎn)到鄰域點(diǎn)重心的距離、點(diǎn)到鄰域點(diǎn)的平均距離的倒數(shù)，三者乘積為權(quán)值積，以權(quán)值積衡量點(diǎn)的重要性，降低曲率估計(jì)誤差影響，然后結(jié)合K?means聚類算法和權(quán)值積的信息熵保留特征點(diǎn)，完成點(diǎn)云數(shù)據(jù)的精簡(jiǎn)。

1 ?權(quán)值積的計(jì)算

定義曲率[H]、點(diǎn)到鄰域點(diǎn)重心的距離[S]、點(diǎn)到鄰域點(diǎn)的平均距離的倒數(shù)[1A]的乘積為權(quán)值積[w]，即：

[w=H?S?1A] （1）

式中：[1A]與[S]可通過(guò)歐氏距離的簡(jiǎn)單計(jì)算獲得，此處不再贅述。

眾所周知，曲率是曲面的基本信息，反映曲面的局部幾何特征。因此根據(jù)曲率的大小可以反映面的彎曲程度。在三維歐氏空間中，一般使用高斯曲率來(lái)反映某點(diǎn)的彎曲程度。一般實(shí)現(xiàn)方法是將此點(diǎn)和鄰域內(nèi)的點(diǎn)擬合成曲面，再求取曲面的主曲率和高斯曲率。設(shè)[P]點(diǎn)為點(diǎn)云中的一點(diǎn)，使用K?D樹算法尋得[P]點(diǎn)的8近鄰[（P1，P2，…，P8）]。

1.1 ?傳統(tǒng)最小二乘法求解曲率[8]

建立二次曲面的參數(shù)方程：

[ru，v=i，j=02qijuivj] （2）

令：

[ ?a=[a00 a01 a02 a10 a11 a12 a20 a21 a22] ?b=[b00 ?b01 ?b02 ?b10 ?b11 ?b12 ?b20 ?b21 ?b22] ?c=[c00 ?c01 ?c02 ?c10 ?c11 ?c12 ?c20 ?c21 ?c22] ?l=[u0v0 ?u0v1 ?u0v2 ?u1v0 ?u1v1 ?u1v2 ?u2v0 ?u2v1 ?u2v2] ?Q=[a ?b ?c]] （3）

式（2）可改寫為：

[r（u，v）=[x（u，v）y（u，v）z（u，v）]=[lTalTblTc]=lTQ] ? （4）

引入兩個(gè)矩陣：

[B=x0y0z0x1?y1?z1?xkykzk， ? ? ? l=lT0lT1?lTk] （5）

待測(cè)點(diǎn)[P]的坐標(biāo)為[（x0，y0，z0）]，這里[k=8]。逼近曲面和數(shù)據(jù)點(diǎn)的誤差函數(shù)為：

[Ω=lQ-B] ? （6）

運(yùn)用最小二乘法，推導(dǎo)出系數(shù)矩陣[Q]為：

[Q=（lTl）-1lTB] （7）

從而求出曲面[r（u，v）]的偏導(dǎo)數(shù)[ru]，[rv]，[ruu]，[ruv]，[rvv]，曲面的單位法矢[n]為：

[n=ru×rvru×rv] （8）

曲面的第1、第2基本量為：

[E=r2u，F(xiàn)=rurv，G=r2，L=nruu，M=nruv，N=nrvv] （9）

求出高斯曲率[K]和平均曲率[H]為：

[K=LN×l2EG-F2， ? ?H=LG-2MF+NE2（EG-F2）] （10）

由于三維掃描的數(shù)據(jù)量往往很大，因此對(duì)每個(gè)點(diǎn)擬合曲面將會(huì)耗費(fèi)大量的內(nèi)存和時(shí)間，所以本文根據(jù)點(diǎn)云間的三角拓?fù)潢P(guān)系提出一種新的曲率估計(jì)方法。

1.2 ?新的曲率估計(jì)方法

如圖2所示，首先找到待測(cè)點(diǎn)[P]的8近鄰[P1～P8]，根據(jù)這9個(gè)點(diǎn)最小二乘擬合確定平面[S]，向量[α]表示平面[S]的法向量。估計(jì)曲率的計(jì)算過(guò)程如下：

1） 首先連接[P]與其余8個(gè)點(diǎn)，分別得到向量：[PP1]，[PP2]，[PP3]，[PP4]，[PP5]，[PP6]，[PP7]和[PP8]。

2） 向量[α]與向量[PP1]的余弦值為：

[cosθ1=α×PP1α·PP1] ?（11）

圖1中，實(shí)心點(diǎn)為待測(cè)點(diǎn)，空心點(diǎn)為鄰近點(diǎn)。角[θ]的余弦值的大小反映了兩個(gè)向量夾角的大小，由圖1可知，待測(cè)點(diǎn)附近的凹凸情況可由余弦值的絕對(duì)值來(lái)說(shuō)明，若余弦值的絕對(duì)值越大，說(shuō)明兩向量的夾角越大或越小，而這兩種情況都說(shuō)明[P]點(diǎn)附近的曲面凹凸程度越大，是特征區(qū)域。根據(jù)式（11），同樣可得[cos θ2]，[cos θ3]，[cosθ4]，[cos θ5]，[cos θ6]，[cos θ7]和[cos θ8]。令曲率估計(jì)值為：

[H=i=18cos θi] （12）

[H]的大小反映了點(diǎn)云數(shù)據(jù)在待測(cè)點(diǎn)[P]附近的凹凸程度。[H]越大，表明在[P]點(diǎn)附近凹凸程度越大，[H]越小表示在[P]點(diǎn)附近的凹凸程度越小。權(quán)值積的另兩個(gè)參數(shù)，[S]越大說(shuō)明[P]點(diǎn)附近幾何特征越明顯;[1A]越大說(shuō)明[P]點(diǎn)附近點(diǎn)云密度較為稀疏，應(yīng)該保存較多的點(diǎn)以保護(hù)原始點(diǎn)云特征。

完整的待測(cè)點(diǎn)曲率估計(jì)示意圖如圖2所示。

2 ?本文算法

2.1 ?K?means聚類算法

K?means聚類算法是典型的基于歐氏距離的聚類算法。在點(diǎn)云的分割過(guò)程中，能夠保持穩(wěn)定和快速的優(yōu)點(diǎn)。若原始點(diǎn)集是位于[N]維空間中的點(diǎn)集，表示為[Pi]，[i∈{1，2，…，m}]。首先找到[K]個(gè)聚類中心[{C1，C2，…，Ck}]，然后通過(guò)迭代計(jì)算移動(dòng)[K]個(gè)聚類中心，最終使得[D]值最?。?/p>

[D=argmini=1kj=1uPj-Ci] （13）

式中：[u]表示以[Ci]為聚類中心的簇中的點(diǎn)的個(gè)數(shù);[Pj]表示屬于以[Ci]為聚類中心的簇中的點(diǎn)。由于[K?D]樹方法的特殊性，點(diǎn)云依照[K?D]樹劃分后會(huì)非常均勻，即可以由[K?D]樹的葉節(jié)點(diǎn)決定聚類重心，該算法計(jì)算過(guò)程如下：

1） 選定聚類[K]值的大小，[K?D]樹劃分點(diǎn)云數(shù)據(jù)，直到葉節(jié)點(diǎn)的數(shù)目最接近[K]時(shí)，初始的聚類中心選擇[K?D]樹的葉節(jié)點(diǎn);

2） 根據(jù)點(diǎn)到聚類中心的歐氏距離將點(diǎn)云劃分為[K]個(gè)簇;

3） 計(jì)算各個(gè)簇的重心代替原來(lái)簇中心;

4） 按照新的聚類中心重新聚類;

5） 重復(fù)步驟3）和步驟4），直到簇的中心不再發(fā)生變化，得到[K]個(gè)簇。

2.2 ?信息熵理論

信息熵是一種非常重要的系統(tǒng)科學(xué)理論，是系統(tǒng)的一個(gè)狀態(tài)函數(shù)，其含義非常豐富，最初由著名科學(xué)家香農(nóng)（Shannon）于1948年在其《A Mathematical Theory of Communication》一文中提出，又稱為Shannon熵，用來(lái)度量通信中的不確定性和信息量。Shannon給出了信息熵的定量表述[9]：

[H（X）=-Ki=1nPilog Pi] ?（14）

式中：[K]為某個(gè)固定正常數(shù);[Pi]是事件[Xi]出現(xiàn)的概率，滿足條件[0≤Pi（i=1，2，…，n）]和[i=1nPi=1]。

根據(jù)信息熵理論，本文將信息熵引入點(diǎn)云精簡(jiǎn)算法之中，在數(shù)據(jù)點(diǎn)權(quán)值積的特征表達(dá)上，信息熵理論可用于將某一數(shù)據(jù)點(diǎn)權(quán)值積表征為對(duì)某類特征的隸屬程度。對(duì)于點(diǎn)云中一點(diǎn)[P]，它的信息熵可由下式計(jì)算：

[I（P）=-Pwlog Pw-i=1kPwi] ?（15）

其中：

[Pw=ww+i=1kwi， ?Pwi=wiw+i=1kwi] （16）

式中：[Pw]是點(diǎn)[P]的權(quán)值積概率;[Pwi]是第[i]個(gè)相鄰點(diǎn)的權(quán)值積概率。較大[I（P）]值意味著該點(diǎn)位于凹陷和凸起明顯變化的區(qū)域中，如果移除此點(diǎn)，則局部幾何圖形將發(fā)生變化，因此應(yīng)該保留信息熵較大值的點(diǎn)云數(shù)據(jù)。

2.3 ?保持特征的精簡(jiǎn)算法流程

設(shè)聚類后得到[n]個(gè)簇（[S1]～[Sn]），針對(duì)每一個(gè)簇[Si]，給定權(quán)值[λ]用來(lái)定義點(diǎn)云特征保持度，將權(quán)值積之差與[λ]比較，若[λ]越小則特征保持效果越好，[λ]越大則特征保持越小但精簡(jiǎn)程度更高。算法步驟流程如圖3所示，具體步驟如下：

1） 計(jì)算簇中每個(gè)點(diǎn)的權(quán)值積[wi]，其中，估計(jì)曲率最大值為[Hmax]，最小值為[Hmin];

2） 若簇中[Hmax-Hmin<λ]，則認(rèn)為此簇處于比較平坦的區(qū)域，即用簇中心代替此簇;

3） 若簇中[Hmax-Hmin>λ]，則判斷此簇為特征區(qū)域，計(jì)算此簇中各點(diǎn)權(quán)值積的信息熵，求得平均值，信息熵大于平均值的點(diǎn)予以保留。

通過(guò)以上算法即可實(shí)現(xiàn)對(duì)點(diǎn)云數(shù)據(jù)的精簡(jiǎn)，相對(duì)平滑區(qū)域，使用簇中心替代整個(gè)簇，不會(huì)造成幾何特征的明顯變化;特征區(qū)域由于使用信息熵值來(lái)衡量點(diǎn)的重要性，保留了最重要的點(diǎn)，因此保留了原始點(diǎn)云的幾何特征。

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

本文使用Matlab對(duì)算法進(jìn)行實(shí)現(xiàn)。實(shí)驗(yàn)用到的點(diǎn)云數(shù)據(jù)為斯坦福大學(xué)建立的3D點(diǎn)云數(shù)據(jù)庫(kù)中的斯坦福兔子Buuny和Dragon點(diǎn)云數(shù)據(jù)模型，格式均為PLY。本文算法有兩個(gè)變量需要自行確定，初始聚類數(shù)目[k]和權(quán)值[λ]。本次實(shí)驗(yàn)取初始聚類數(shù)[k]為2 048，[λ]分別取0.6，0.1。

圖4所示為原始點(diǎn)云由Matlab的呈現(xiàn)結(jié)果，其中圖4a）為Buuny模型，共有35 947個(gè)點(diǎn)，圖4b）為有10 248個(gè)點(diǎn)的Dragon模型。為了對(duì)點(diǎn)云原始數(shù)據(jù)和精簡(jiǎn)后數(shù)據(jù)進(jìn)行定量分析，本文采用Geomagic Studio軟件實(shí)現(xiàn)對(duì)點(diǎn)云數(shù)據(jù)的重構(gòu)[10]，依此衡量精簡(jiǎn)結(jié)果的優(yōu)劣。圖5為原始點(diǎn)云數(shù)據(jù)的重構(gòu)結(jié)果。

圖6a）和圖7a）為[λ=]0.1時(shí)的精簡(jiǎn)結(jié)果，圖6b）和圖7b）為[λ=]0.6時(shí)的精簡(jiǎn)結(jié)果。Buuny模型精簡(jiǎn)后點(diǎn)的個(gè)數(shù)為7 271，3 571，Dragon模型精簡(jiǎn)后點(diǎn)的個(gè)數(shù)為177 416，8 654。

精簡(jiǎn)后的模型重建結(jié)果如圖8所示。與原始模型進(jìn)行比較，在[λ=]0.1時(shí)可以較好地保留其特征信息;在[λ=]0.6時(shí)，由于精簡(jiǎn)度過(guò)高，會(huì)丟失部分特征信息。

4 ?結(jié) ?語(yǔ)

針對(duì)最小二乘法擬合曲面計(jì)算數(shù)據(jù)點(diǎn)曲率過(guò)于復(fù)雜和費(fèi)時(shí)，本文提出一種新的點(diǎn)云數(shù)據(jù)點(diǎn)曲率估計(jì)方法，并將信息熵的理論引入點(diǎn)云精簡(jiǎn)的過(guò)程中，更好地保留了特征點(diǎn)。經(jīng)過(guò)實(shí)驗(yàn)證明，該算法精簡(jiǎn)效果較好，保留了原始數(shù)據(jù)的基本幾何特征，精簡(jiǎn)后的點(diǎn)云數(shù)據(jù)用于重建，效果良好。

注：本文通訊作者為田華。

參考文獻(xiàn)

[1] THANOU D， CHOU P A， FROSSARD P. Graph?based compression of dynamic 3D point cloud sequences [J]. IEEE tran?sactions on image processing， 2016， 25（4）： 1765?1778.

[2] M BERGER， A TAGLIASACCHI， L SEVERSKY， et al. State of the art in surface reconstruction from point cloud [J]. Eurographics star reports， 2014， 1（1）： 161?185.

[3] NAGAI Y， OHTAKE Y， SUZUKI H， et al. Tomographic surface reconstruction from point cloud [J]. Computers & graphics， 2015， 46： 55?63.

[4] SANCHEZ G， LEAL E， LEAL N. A linear programming approach for 3D point cloud simplification [J]. Iaeng international journal of computer science， 2017， 44（1）： 60?67.

[5] SHI B Q， LIANG J， LIU Q. Adaptive simplification of point cloud using k?means clustering [J]. Computer?aided design， 2011， 43（8）： 910?922.

[6] ZHANG Y， GENG G， WEI X， et al. A statistical approach for extraction of feature lines from point clouds [J]. Computers & graphics， 2016， 56： 31?45.

[7] 陳龍，蔡勇，張建生.自適應(yīng)K?means聚類的散亂點(diǎn)云精簡(jiǎn)[J].中國(guó)圖象圖形學(xué)報(bào)，2017，22（8）：1089?1097.

[8] 周煜，張萬(wàn)兵，杜發(fā)榮，等.散亂點(diǎn)云數(shù)據(jù)的曲率精簡(jiǎn)算法[J].北京理工大學(xué)學(xué)報(bào)，2010，30（7）：785?789.

[9] 姜茸，廖鴻志，楊明.信息熵在軟件領(lǐng)域中的應(yīng)用研究現(xiàn)狀[J].自動(dòng)化技術(shù)與應(yīng)用，2015，34（4）：1?6.

[10] 郭培閃，杜黎明.運(yùn)用Geomagic Studio實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的曲面重建及誤差分析[J].地理信息世界，2015，22（1）：57?60.

作者簡(jiǎn)介：董嘉敏（1993—），男，山西運(yùn)城人，碩士研究生，研究方向?yàn)樘摂M現(xiàn)實(shí)。

田 ?華（1983—），女，山西晉城人，博士，碩士生導(dǎo)師，主要研究方向?yàn)橛?jì)算材料。