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

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

（山東理工大學(xué) 機(jī)械工程學(xué)院，淄博 255049）

0 引言

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

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

為能夠快速有效精簡超出主存容限的海量散亂點(diǎn)云數(shù)據(jù)，本文算法通過改進(jìn)CR樹的結(jié)點(diǎn)分裂算法，將CR樹上溢結(jié)點(diǎn)的子結(jié)點(diǎn)包圍盒集轉(zhuǎn)換為包圍盒的中心點(diǎn)集，利用CR樹與數(shù)據(jù)庫SQLite相結(jié)合實(shí)現(xiàn)海量散亂點(diǎn)云的主存-輔存分級(jí)存儲(chǔ)，計(jì)算CR樹目標(biāo)結(jié)點(diǎn)層中每個(gè)結(jié)點(diǎn)的均值點(diǎn)，將距離均值點(diǎn)最近的樣點(diǎn)作為精簡結(jié)果，根據(jù)所選結(jié)點(diǎn)層的不同實(shí)現(xiàn)海量散亂點(diǎn)云不同程度的精簡，該算法能夠快速均勻地對(duì)海量散亂點(diǎn)云進(jìn)行精簡，并且構(gòu)建的動(dòng)態(tài)索引可為后續(xù)工作所使用。

1 海量散亂點(diǎn)云的分級(jí)存儲(chǔ)機(jī)制

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

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

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

圖1 上溢結(jié)點(diǎn)不合理的點(diǎn)集表示

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

鑒于CR樹良好的動(dòng)態(tài)索引性能，將其與數(shù)據(jù)庫SQLite相結(jié)合，分別把索引結(jié)點(diǎn)與點(diǎn)云數(shù)據(jù)存放到計(jì)算機(jī)主存儲(chǔ)器與輔存儲(chǔ)器中，實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的分級(jí)存儲(chǔ)，從而能夠有效的管理超出主存容限的海量點(diǎn)云數(shù)據(jù)，圖2為分級(jí)存儲(chǔ)機(jī)制的結(jié)構(gòu)示意圖。

圖2 海量點(diǎn)云數(shù)據(jù)的分級(jí)存儲(chǔ)機(jī)制

CR樹與數(shù)據(jù)庫SQLite相結(jié)合構(gòu)建點(diǎn)云數(shù)據(jù)的分級(jí)存儲(chǔ)機(jī)制具體步驟如下：

1）初始化：i←1，新建根結(jié)點(diǎn)N；

2）讀取點(diǎn)云文件中第i行點(diǎn)數(shù)據(jù)1i，若1i為非空，則跳轉(zhuǎn)至3），否則，分級(jí)存儲(chǔ)機(jī)制構(gòu)建完成；

3）應(yīng)用CR樹選擇子樹算法獲取葉結(jié)點(diǎn)Nleaf，構(gòu)建點(diǎn)鏈表point_l，并使Nleaf→point_l ；

4）將Nleaf對(duì)應(yīng)輔存儲(chǔ)器中的數(shù)據(jù)表data_l利用SQLite加載到主存儲(chǔ)器中，并將data_l從輔存儲(chǔ)器中刪除，將除表頭數(shù)據(jù)外的其他數(shù)據(jù)拷貝到point_l中；

5）將1i插入point_l，若point_l中元素的個(gè)數(shù)len≤M，則跳轉(zhuǎn)至7），否則對(duì)Nleaf利用k-means算法進(jìn)行聚類；

6）為聚類產(chǎn)生的每個(gè)葉結(jié)點(diǎn)Nleaf及其所指向的point_l在輔存儲(chǔ)器中利用SQLite構(gòu)建一個(gè)新的數(shù)據(jù)表data_l，并將它們存儲(chǔ)到每個(gè)data_l中，其中表頭為Nleaf，其他為point_l，刪除主存儲(chǔ)器中每個(gè)Nleaf所指向的point_l；

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

2 海量散亂點(diǎn)云的快速精簡

CR樹中的k均值聚類算法是一種基于樣點(diǎn)數(shù)據(jù)之間的相似性劃分?jǐn)?shù)據(jù)對(duì)象的算法[7]，建樹過程中該算法已對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行了空間相似性劃分，因此距離結(jié)點(diǎn)所包含點(diǎn)集的均值點(diǎn)最近的點(diǎn)能夠較好的反映該結(jié)點(diǎn)的點(diǎn)集分布趨勢(shì)?；谒鶚?gòu)建的主存-輔存分級(jí)存儲(chǔ)機(jī)制，計(jì)算第h結(jié)點(diǎn)層每個(gè)結(jié)點(diǎn)所包含點(diǎn)集的均值點(diǎn)，將距離均值點(diǎn)最近的點(diǎn)代替該點(diǎn)集?？筛鶕?jù)結(jié)點(diǎn)利用率[7]選取h值。以第h結(jié)點(diǎn)層為目標(biāo)層，精簡具體過程如下：

1）構(gòu)建采樣數(shù)據(jù)的分級(jí)存儲(chǔ)機(jī)制；

2）獲取第h層索引層的結(jié)點(diǎn)集N{ni}；

3）設(shè)i ←1，獲取結(jié)點(diǎn)集N{ni}中結(jié)點(diǎn)個(gè)數(shù)num，初始化集合P{pi}；

4）計(jì)算結(jié)點(diǎn)ni中點(diǎn)集的均值點(diǎn)pm，并獲得距離pm最近的點(diǎn)pmin，將pmin添加到集合P{pi}中，當(dāng)i=num時(shí)，跳轉(zhuǎn)至5），否則，i ←i+1，重復(fù)執(zhí)行4）；

5）P{pi}為按照第h層結(jié)點(diǎn)的聚類結(jié)果對(duì)采樣數(shù)據(jù)的精簡結(jié)果。

在構(gòu)建動(dòng)態(tài)空間索引時(shí)，將點(diǎn)集表示進(jìn)行改進(jìn)，可以有效提高構(gòu)建效率，其中通過調(diào)節(jié)結(jié)點(diǎn)層h的數(shù)值，可靈活調(diào)整采樣數(shù)據(jù)的精簡程度。

3 實(shí)驗(yàn)分析

采用光柵投影式三維測(cè)量儀獲得手臂、半車身模型的點(diǎn)云數(shù)據(jù)，其原始點(diǎn)云如圖3所示，運(yùn)用本文算法對(duì)模型進(jìn)行精簡，根據(jù)文獻(xiàn)[7]建議將上溢參數(shù)設(shè)為M=30。測(cè)試環(huán)境為：CPU 2.50GHz，主存4GB；操作系統(tǒng)為Gentoo Linux，測(cè)試程序?yàn)镃語言。

圖3 半車身模型的原始點(diǎn)云(點(diǎn)數(shù)180,524,735)

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

圖4 車身模型的精簡結(jié)果

4 結(jié)論

1）CR樹與SQLite相結(jié)合構(gòu)建的主存-輔存分級(jí)存儲(chǔ)機(jī)制能有效存儲(chǔ)與管理海量點(diǎn)云數(shù)據(jù)。

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

3）海量數(shù)據(jù)的out-of-core精簡算法不僅可用于交互性顯示與觀察海量點(diǎn)云的幾何特征，而且可作為海量數(shù)據(jù)進(jìn)一步進(jìn)行保形精簡的預(yù)處理工作，同時(shí)其構(gòu)建的動(dòng)態(tài)空間索引結(jié)構(gòu)也可為后續(xù)工作所使用，如三角剖分、拓?fù)溧徲虿樵兊取?/p>

[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]熊輝.大型復(fù)雜模具的點(diǎn)云預(yù)處理技術(shù)研究[D].南昌大學(xué),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.