董嘉敏 田華

摘 ?要： 針對目前流行的三維物體激光掃描儀獲取的點(diǎn)云數(shù)據(jù)量大，冗余度高等問題，提出一種基于信息熵的點(diǎ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ū)域;最后，針對特征區(qū)域，利用提出的精簡方法精簡點(diǎn)云。實(shí)驗(yàn)結(jié)果表明，該方法計(jì)算相對簡單，能夠有效避免孔洞現(xiàn)象，同時，更好地保留了點(diǎn)云數(shù)據(jù)的原始物理特征。

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

中圖分類號： TN911?34; TP391.9 ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 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ī)視覺、逆向工程學(xué)和計(jì)算機(jī)圖形學(xué)等熱門研究領(lǐng)域的研究重點(diǎn)[1]。關(guān)于點(diǎn)云技術(shù)三維重建，已經(jīng)有不少的研究工作和成果[2?3]。隨著FreeScanX3等三維物體激光掃描儀不斷推陳出新，點(diǎn)云數(shù)據(jù)的獲得變得更加方便，同時點(diǎn)云數(shù)據(jù)的精度也非常高。然而，如此密集的點(diǎn)云數(shù)據(jù)中卻存在著大量的冗余數(shù)據(jù)，這些冗余數(shù)據(jù)極大地增加了點(diǎn)云數(shù)據(jù)的存儲開銷和計(jì)算開銷，從而影響到曲面擬合和模型生成等重要后續(xù)工作的效率。綜上所述，點(diǎn)云數(shù)據(jù)的精簡工作對于物體的三維重建和繪制工作是非常重要的[4]。

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

這些不同的基于點(diǎn)的簡化方法有一個共同點(diǎn)，就是先評估點(diǎn)云數(shù)據(jù)中每個點(diǎn)的重要性，通過刪除不重要的點(diǎn)完成點(diǎn)云數(shù)據(jù)的精簡，因此評估參數(shù)就顯得尤為重要。本文提出一種基于信息熵的點(diǎn)云精簡算法，針對以往最小二乘法擬合曲面計(jì)算曲率過于復(fù)雜耗時，提出一種新的曲率估計(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ù)的精簡。

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]可通過歐氏距離的簡單計(jì)算獲得，此處不再贅述。

眾所周知，曲率是曲面的基本信息，反映曲面的局部幾何特征。因此根據(jù)曲率的大小可以反映面的彎曲程度。在三維歐氏空間中，一般使用高斯曲率來反映某點(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）

引入兩個矩陣：

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

待測點(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ù)量往往很大，因此對每個點(diǎn)擬合曲面將會耗費(fèi)大量的內(nèi)存和時間，所以本文根據(jù)點(diǎn)云間的三角拓?fù)潢P(guān)系提出一種新的曲率估計(jì)方法。

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

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

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

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

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

圖1中，實(shí)心點(diǎn)為待測點(diǎn)，空心點(diǎn)為鄰近點(diǎn)。角[θ]的余弦值的大小反映了兩個向量夾角的大小，由圖1可知，待測點(diǎn)附近的凹凸情況可由余弦值的絕對值來說明，若余弦值的絕對值越大，說明兩向量的夾角越大或越小，而這兩種情況都說明[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ù)在待測點(diǎn)[P]附近的凹凸程度。[H]越大，表明在[P]點(diǎn)附近凹凸程度越大，[H]越小表示在[P]點(diǎn)附近的凹凸程度越小。權(quán)值積的另兩個參數(shù)，[S]越大說明[P]點(diǎn)附近幾何特征越明顯;[1A]越大說明[P]點(diǎn)附近點(diǎn)云密度較為稀疏，應(yīng)該保存較多的點(diǎn)以保護(hù)原始點(diǎn)云特征。

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

2 ?本文算法

2.1 ?K?means聚類算法

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

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

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

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

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

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

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

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

2.2 ?信息熵理論

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

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

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

根據(jù)信息熵理論，本文將信息熵引入點(diǎn)云精簡算法之中，在數(shù)據(jù)點(diǎn)權(quán)值積的特征表達(dá)上，信息熵理論可用于將某一數(shù)據(jù)點(diǎn)權(quán)值積表征為對某類特征的隸屬程度。對于點(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]個相鄰點(diǎn)的權(quán)值積概率。較大[I（P）]值意味著該點(diǎn)位于凹陷和凸起明顯變化的區(qū)域中，如果移除此點(diǎn)，則局部幾何圖形將發(fā)生變化，因此應(yīng)該保留信息熵較大值的點(diǎn)云數(shù)據(jù)。

2.3 ?保持特征的精簡算法流程

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

1） 計(jì)算簇中每個點(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)予以保留。

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

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

本文使用Matlab對算法進(jìn)行實(shí)現(xiàn)。實(shí)驗(yàn)用到的點(diǎn)云數(shù)據(jù)為斯坦福大學(xué)建立的3D點(diǎn)云數(shù)據(jù)庫中的斯坦福兔子Buuny和Dragon點(diǎn)云數(shù)據(jù)模型，格式均為PLY。本文算法有兩個變量需要自行確定，初始聚類數(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個點(diǎn)，圖4b）為有10 248個點(diǎn)的Dragon模型。為了對點(diǎn)云原始數(shù)據(jù)和精簡后數(shù)據(jù)進(jìn)行定量分析，本文采用Geomagic Studio軟件實(shí)現(xiàn)對點(diǎn)云數(shù)據(jù)的重構(gòu)[10]，依此衡量精簡結(jié)果的優(yōu)劣。圖5為原始點(diǎn)云數(shù)據(jù)的重構(gòu)結(jié)果。

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

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

4 ?結(jié) ?語

針對最小二乘法擬合曲面計(jì)算數(shù)據(jù)點(diǎn)曲率過于復(fù)雜和費(fèi)時，本文提出一種新的點(diǎn)云數(shù)據(jù)點(diǎn)曲率估計(jì)方法，并將信息熵的理論引入點(diǎn)云精簡的過程中，更好地保留了特征點(diǎn)。經(jīng)過實(shí)驗(yàn)證明，該算法精簡效果較好，保留了原始數(shù)據(jù)的基本幾何特征，精簡后的點(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)云精簡[J].中國圖象圖形學(xué)報(bào)，2017，22（8）：1089?1097.

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

[9] 姜茸，廖鴻志，楊明.信息熵在軟件領(lǐng)域中的應(yīng)用研究現(xiàn)狀[J].自動化技術(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.

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

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