海量散亂點云out-of-core快速均勻精簡算法

聶樂魁，孫殿柱，薄志成，尹遜剛

NIE Le-kui, SUN Dian-zhu, BO Zhi-cheng, YIN Xun-gang

（山東理工大學 機械工程學院，淄博 255049）

0 引言

在逆向工程中，為精確表示實物的空間信息，由光柵投影式三維測量儀等掃描設備獲得點云數據規模趨于海量，甚至超出通用計算機主存儲器的容量，導致點云數據無法進行可視化及交互性操作，需要對其進行精簡處理[1～3]。

目前，點云數據的精簡算法分為均勻精簡算法與保形精簡算法。Sun等[5]采用包圍盒法來簡化測量散亂點云數據，Martin等[6]提出均勻網格法，利用中值濾波計算包圍盒的中值點來精簡采樣數據，能夠快速均勻精簡點云，但損失部分點云的幾何特征。Chen等[4]對采樣數據進行三角化，計算三角面片的法向量，并估計其曲率，基于曲率去除部分三角面片從而精簡采樣數據，能夠很好地保留點云的幾何特征，但精簡速度過低。為能夠快速顯示與操作點云數據，應采用均勻精簡算法對點云進行精簡。但當精簡海量散亂點云時，現存的均勻精簡方法都將無法使用，而利用out-of-core的動態存儲與加載特性可有效解決點云數據規模及計算過程中產生的數據量超出計算機主存儲器容限的問題[1,2]。

為能夠快速有效精簡超出主存容限的海量散亂點云數據，本文算法通過改進CR樹的結點分裂算法，將CR樹上溢結點的子結點包圍盒集轉換為包圍盒的中心點集，利用CR樹與數據庫SQLite相結合實現海量散亂點云的主存-輔存分級存儲，計算CR樹目標結點層中每個結點的均值點，將距離均值點最近的樣點作為精簡結果，根據所選結點層的不同實現海量散亂點云不同程度的精簡，該算法能夠快速均勻地對海量散亂點云進行精簡，并且構建的動態索引可為后續工作所使用。

1 海量散亂點云的分級存儲機制

CR樹采用k均值聚類算法，將結點兩路分裂改進為多簇分裂，結點插入代價與R樹相仿，而查詢性能與R*樹相近，適合于數據密集型環境[7]。其結點分裂算法采用式(1)將N的子結點集{ni}轉化為點集{pi}：

式中B(ni)表示N中任一子結點n的包圍盒，V(x)表示包圍盒x的容積，C(x)表示包圍盒x的中心點。

利用上述方法所得點集往往與包圍盒集的真實分布并不相符。如圖1所示，對四個包圍盒采用式(1)轉換后的點集不能體現包圍盒的位置分布，若應用k均值算法[7]將圖1中的點集劃為2個分類，可能會出現兩個較大的包圍盒被歸為一類而兩個較小的包圍盒被歸為另一類的結果，這顯然并非理想的結果。

圖1 上溢結點不合理的點集表示

本文算法將采用包圍盒中心點集進行聚類計算，以使上溢結點的分裂問題能較大程度得以簡化，即采用式(2)將上溢結點N轉化為點集{pi}：

鑒于CR樹良好的動態索引性能，將其與數據庫SQLite相結合，分別把索引結點與點云數據存放到計算機主存儲器與輔存儲器中，實現點云數據的分級存儲，從而能夠有效的管理超出主存容限的海量點云數據，圖2為分級存儲機制的結構示意圖。

圖2 海量點云數據的分級存儲機制

CR樹與數據庫SQLite相結合構建點云數據的分級存儲機制具體步驟如下：

1）初始化：i←1，新建根結點N；

2）讀取點云文件中第i行點數據1i，若1i為非空，則跳轉至3），否則，分級存儲機制構建完成；

3）應用CR樹選擇子樹算法獲取葉結點Nleaf，構建點鏈表point_l，并使Nleaf→point_l ；

4）將Nleaf對應輔存儲器中的數據表data_l利用SQLite加載到主存儲器中，并將data_l從輔存儲器中刪除，將除表頭數據外的其他數據拷貝到point_l中；

5）將1i插入point_l，若point_l中元素的個數len≤M，則跳轉至7），否則對Nleaf利用k-means算法進行聚類；

6）為聚類產生的每個葉結點Nleaf及其所指向的point_l在輔存儲器中利用SQLite構建一個新的數據表data_l，并將它們存儲到每個data_l中，其中表頭為Nleaf，其他為point_l，刪除主存儲器中每個Nleaf所指向的point_l；

7）i←i+1，返回2）。

2 海量散亂點云的快速精簡

CR樹中的k均值聚類算法是一種基于樣點數據之間的相似性劃分數據對象的算法[7]，建樹過程中該算法已對點云數據進行了空間相似性劃分，因此距離結點所包含點集的均值點最近的點能夠較好的反映該結點的點集分布趨勢。基于所構建的主存-輔存分級存儲機制，計算第h結點層每個結點所包含點集的均值點，將距離均值點最近的點代替該點集?？筛鶕Y點利用率[7]選取h值。以第h結點層為目標層，精簡具體過程如下：

1）構建采樣數據的分級存儲機制；

2）獲取第h層索引層的結點集N{ni}；

3）設i ←1，獲取結點集N{ni}中結點個數num，初始化集合P{pi}；

4）計算結點ni中點集的均值點pm，并獲得距離pm最近的點pmin，將pmin添加到集合P{pi}中，當i=num時，跳轉至5），否則，i ←i+1，重復執行4）；

5）P{pi}為按照第h層結點的聚類結果對采樣數據的精簡結果。

在構建動態空間索引時，將點集表示進行改進，可以有效提高構建效率，其中通過調節結點層h的數值，可靈活調整采樣數據的精簡程度。

3 實驗分析

采用光柵投影式三維測量儀獲得手臂、半車身模型的點云數據，其原始點云如圖3所示，運用本文算法對模型進行精簡，根據文獻[7]建議將上溢參數設為M=30。測試環境為：CPU 2.50GHz，主存4GB；操作系統為Gentoo Linux，測試程序為C語言。

圖3 半車身模型的原始點云(點數180,524,735)

構建半車身模型的CR樹動態空間索引結構，樹的高度為8，取h值分別為5、6、7，建樹時間為1328.25s，精簡時間分別為34.82、37.26、40.05，精簡效果分別為圖4(a)、圖4(b)、圖4(c)所示。

圖4 車身模型的精簡結果

4 結論

1）CR樹與SQLite相結合構建的主存-輔存分級存儲機制能有效存儲與管理海量點云數據。

2）利用距離均值點最近的點代替每簇點集有效提高了精簡效率。

3）海量數據的out-of-core精簡算法不僅可用于交互性顯示與觀察海量點云的幾何特征，而且可作為海量數據進一步進行保形精簡的預處理工作，同時其構建的動態空間索引結構也可為后續工作所使用，如三角剖分、拓撲鄰域查詢等。

[1]Wenzel K,Haala N,Fritsch D.Stereo model selection and point cloud filtering using an out-of-core octree[A].ISPRS-International Archives of the Photogrammetr:Remote Sensing and Spatial Information Sciences[C].2014:373-380.

[2]T.Whelan,L.Ma,E.Bondarev,et al.Incremental and batch planar simplification of dense point cloud maps[C].Conference on Mobile Robotics(ECMR)[C].2013,1:1-13.

[3]熊輝.大型復雜模具的點云預處理技術研究[D].南昌大學,2013.

[4]Chen Y H,Ng C T,Wang Y Z.Data reduction in integrated reverse engineering and rapid prototyping[J].International Journal of Computer Integrated Manufacturing,1999,12(2):97-103.

[5]Sun W,Bradley C,Zhang Y F,et al.Cloud data modeling employing a unified non-redundant triangular mesh[J].Computer-Aided Design,2001,33(2):183-193.

[6]Martin R.R.,Stroud I.A.,A.D.Marshall.Data reduction for reverse engineering[R].[S.1.]:Hungarian Academy of Science,Computer and Automation Research Institute,1996:63-69.

[7]Theodoridis Y,Brakatsoulas S,Pfoser D.Revisiting r-tree construction principles[A].Advances in Databases and Information Systems[C].2002.