董嘉敏 田華

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

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

中圖分類號： TN911?34; TP391.9 ? ? ? ? ? ? ? ? ? 文獻標識碼： 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 ?引 ?言

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

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

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

1 ?權值積的計算

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

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

式中：[1A]與[S]可通過歐氏距離的簡單計算獲得，此處不再贅述。

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

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

[Ω=lQ-B] ? （6）

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

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

從而求出曲面[r（u，v）]的偏導數(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ù)量往往很大，因此對每個點擬合曲面將會耗費大量的內(nèi)存和時間，所以本文根據(jù)點云間的三角拓撲關系提出一種新的曲率估計方法。

1.2 ?新的曲率估計方法

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

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

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

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

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

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

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

完整的待測點曲率估計示意圖如圖2所示。

2 ?本文算法

2.1 ?K?means聚類算法

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

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

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

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

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

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

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

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

2.2 ?信息熵理論

信息熵是一種非常重要的系統(tǒng)科學理論，是系統(tǒng)的一個狀態(tài)函數(shù)，其含義非常豐富，最初由著名科學家香農(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ù)信息熵理論，本文將信息熵引入點云精簡算法之中，在數(shù)據(jù)點權值積的特征表達上，信息熵理論可用于將某一數(shù)據(jù)點權值積表征為對某類特征的隸屬程度。對于點云中一點[P]，它的信息熵可由下式計算：

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

其中：

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

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

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

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

1） 計算簇中每個點的權值積[wi]，其中，估計曲率最大值為[Hmax]，最小值為[Hmin];

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

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

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

3 ?實驗結果及分析

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

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

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

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

4 ?結 ?語

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

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

參考文獻

[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] 陳龍，蔡勇，張建生.自適應K?means聚類的散亂點云精簡[J].中國圖象圖形學報，2017，22（8）：1089?1097.

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

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

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

作者簡介：董嘉敏（1993—），男，山西運城人，碩士研究生，研究方向為虛擬現(xiàn)實。

田 ?華（1983—），女，山西晉城人，博士，碩士生導師，主要研究方向為計算材料。