一種散亂分層點(diǎn)云的有序化精簡(jiǎn)方法

解則曉， 劉靜曉， 潘成成， 張夢(mèng)澤

(中國(guó)海洋大學(xué)工程學(xué)院，山東 青島 266100)

一種散亂分層點(diǎn)云的有序化精簡(jiǎn)方法

解則曉， 劉靜曉， 潘成成， 張夢(mèng)澤

(中國(guó)海洋大學(xué)工程學(xué)院，山東 青島 266100)

針對(duì)激光掃描儀所得點(diǎn)云散亂分層的特點(diǎn)，提出一種有序化的精簡(jiǎn)方法。首先基于已知標(biāo)記點(diǎn)建立三維R-tree和八叉樹(shù)集成的空間索引，快速準(zhǔn)確地獲取局部點(diǎn)云數(shù)據(jù)，保證良好的數(shù)據(jù)檢索效率。然后根據(jù)局部點(diǎn)云數(shù)據(jù)的參考平面法向量信息，選取工件坐標(biāo)系中的一個(gè)坐標(biāo)軸作為參數(shù)化的方向，對(duì)局部點(diǎn)云數(shù)據(jù)進(jìn)行參數(shù)化并擬合二次曲面。最后對(duì)R-tree葉節(jié)點(diǎn)內(nèi)的二次曲面進(jìn)行有序化采樣，使散亂分層的點(diǎn)云變?yōu)閱螌樱玫秸麄€(gè)型面的有序參考點(diǎn)集。應(yīng)用實(shí)例表明，該方法適用于大規(guī)模的、具有復(fù)雜幾何特征且存在一定程度散亂分層的點(diǎn)云，可以有效地提高數(shù)據(jù)點(diǎn)的整體精確度，且不會(huì)丟失點(diǎn)云的細(xì)節(jié)特征，具有較強(qiáng)的實(shí)用性。

數(shù)據(jù)精簡(jiǎn)；有序化；散亂分層點(diǎn)云；標(biāo)記點(diǎn)；3D R-tree

逆向工程在現(xiàn)代制造業(yè)中占據(jù)著重要的地位，三維數(shù)字化技術(shù)是逆向工程中的首要環(huán)節(jié)。作為三維數(shù)字化技術(shù)的重要組成部分，三維數(shù)據(jù)精簡(jiǎn)能夠提高曲面建模的質(zhì)量和效率，具有十分重要的研究意義。

近年來(lái)激光掃描系統(tǒng)以其非接觸、靈活、高速的優(yōu)點(diǎn)得到了快速的發(fā)展，并廣泛應(yīng)用于航空航天、汽車工業(yè)、生物醫(yī)學(xué)等工程領(lǐng)域。激光掃描系統(tǒng)可以快速獲取待測(cè)表面的激光數(shù)據(jù)，經(jīng)其測(cè)得的點(diǎn)云數(shù)據(jù)密度高、數(shù)量大，存在大量的冗余數(shù)據(jù)。此類點(diǎn)云數(shù)據(jù)直接用來(lái)建模會(huì)占用大量的存儲(chǔ)空間和建模用時(shí)，從而降低了建模質(zhì)量和效率。因此在保證建模精度的同時(shí)提取點(diǎn)云數(shù)據(jù)中反映曲面特征的點(diǎn)、去除冗余數(shù)據(jù)即數(shù)據(jù)精簡(jiǎn)，有助于提高建模效率，是逆向工程中的一項(xiàng)關(guān)鍵技術(shù)[1]。

在激光掃描系統(tǒng)掃描過(guò)程中，對(duì)于工件的平緩表面部分，從單一方位一次掃描就可以得到體現(xiàn)其表面特征的數(shù)據(jù)點(diǎn)，此類數(shù)據(jù)點(diǎn)在其局部參考平面的法向量方向上表現(xiàn)為單層；而對(duì)于工件的復(fù)雜表面部分，必須從不同方位多次掃描才能得到充分的數(shù)據(jù)點(diǎn)，由于模型的復(fù)雜性和測(cè)量精度的局限性[2]，不同方位掃描得到的數(shù)據(jù)點(diǎn)被統(tǒng)一到同一三維坐標(biāo)系下后，會(huì)在點(diǎn)云的局部型面的法向量方向上表現(xiàn)出一定程度的散亂分層。

目前國(guó)內(nèi)外數(shù)據(jù)精簡(jiǎn)技術(shù)大多是針對(duì)單層點(diǎn)云提出。如 Weir等[3]提出的包圍盒法簡(jiǎn)單高效，但是選取靠近包圍盒中心的點(diǎn)來(lái)代替該包圍盒中的所有點(diǎn)，無(wú)法保證精簡(jiǎn)后的點(diǎn)云保持初始的曲面特征。Martin和Varady等[4]提出的基于“中值濾波”原理的均勻網(wǎng)格法，該法需要將點(diǎn)云空間分割成均勻網(wǎng)格，確定點(diǎn)云投影面，計(jì)算網(wǎng)格中數(shù)據(jù)點(diǎn)到投影面的距離，選擇距離居中的數(shù)據(jù)點(diǎn)代替網(wǎng)格中其他點(diǎn)，該法多應(yīng)用于點(diǎn)云曲面垂直于坐標(biāo)軸的情況，運(yùn)算速度快，但對(duì)于具有復(fù)雜曲面的點(diǎn)云精簡(jiǎn)效果不佳。Lee等[5]提出的三維網(wǎng)格法可以用于表面特征復(fù)雜的點(diǎn)云，但首先要對(duì)點(diǎn)云進(jìn)行三角網(wǎng)格化處理，再根據(jù)向量加權(quán)算法對(duì)已生成的三角網(wǎng)格進(jìn)行刪除，運(yùn)算過(guò)程較為復(fù)雜。Lee和 Huang[6]采用 K均值聚類的自適應(yīng)精簡(jiǎn)算法，該算法能夠合理分布點(diǎn)云數(shù)據(jù)，但是對(duì)噪聲敏感。陳璋雯和達(dá)飛鵬[7]提出的基于模糊熵迭代的精簡(jiǎn)算法，本質(zhì)上屬于曲率采樣法，需要求取每個(gè)數(shù)據(jù)點(diǎn)的曲率，根據(jù)數(shù)據(jù)點(diǎn)曲率計(jì)算點(diǎn)云最小模糊熵，由模糊熵決定曲率劃分閾值，對(duì)于曲率小于閾值的數(shù)據(jù)點(diǎn)進(jìn)行稀釋，大于閾值的數(shù)據(jù)點(diǎn)重新進(jìn)行模糊熵迭代。該方法雖然能保留點(diǎn)云細(xì)節(jié)特征以逼近點(diǎn)云原型，但是算法效率不高。

本文研究的點(diǎn)云數(shù)據(jù)來(lái)自一種新型激光掃描儀——基于標(biāo)記點(diǎn)的流動(dòng)式三維掃描儀[8]，該掃描儀利用標(biāo)記點(diǎn)對(duì)系統(tǒng)進(jìn)行實(shí)時(shí)定位，將提取的激光數(shù)據(jù)轉(zhuǎn)換到固定的工件坐標(biāo)系下。其測(cè)量過(guò)程是一個(gè)不斷將激光數(shù)據(jù)向工件坐標(biāo)系轉(zhuǎn)換的過(guò)程，最終可以得到整個(gè)工件的點(diǎn)云數(shù)據(jù)。當(dāng)在不同高度不同角度對(duì)復(fù)雜工件的某個(gè)部位進(jìn)行掃描時(shí)，測(cè)得的激光數(shù)據(jù)被轉(zhuǎn)換到工件坐標(biāo)系下后會(huì)表現(xiàn)出一定程度的散亂分層。這類點(diǎn)云幾何特征復(fù)雜、存在大量冗余數(shù)據(jù)且表現(xiàn)出一定的散亂分層，既不能直接用于模型重建，用已有的精簡(jiǎn)算法又難以達(dá)到理想的精簡(jiǎn)效果，因此針對(duì)具有該特點(diǎn)的點(diǎn)云，提出一種散亂分層點(diǎn)云有序化精簡(jiǎn)算法。

本文方法主要分3步進(jìn)行：

(1) 建立點(diǎn)云的空間拓?fù)浣Y(jié)構(gòu)，即空間索引的建立。考慮到基于八叉樹(shù)的R-tree索引[9-11]能夠提供穩(wěn)健高效的空間查詢能力，針對(duì)流動(dòng)式三維掃描儀在測(cè)量中所使用的標(biāo)記點(diǎn)的三維坐標(biāo)精確已知[12-15]，且標(biāo)記點(diǎn)均勻分布的特點(diǎn)，提出了一種基于已知標(biāo)記點(diǎn)建立點(diǎn)云空間索引的方法：①對(duì)點(diǎn)云空間進(jìn)行三維網(wǎng)格劃分，以包含標(biāo)記點(diǎn)的三維網(wǎng)格為中心對(duì)所有的三維網(wǎng)格而非數(shù)據(jù)點(diǎn)進(jìn)行聚類；②對(duì)于包含數(shù)據(jù)點(diǎn)的三維網(wǎng)格，根據(jù)設(shè)定的扇出條件對(duì)其進(jìn)行八叉樹(shù)分裂，直至所有的葉節(jié)點(diǎn)都收斂。該索引結(jié)構(gòu)的創(chuàng)建速度快，葉節(jié)點(diǎn)無(wú)重疊，便于快速準(zhǔn)確地獲取局部點(diǎn)云數(shù)據(jù)。

(2) 確定參數(shù)化和采樣方法，擬合二次曲面。針對(duì)曲面特征復(fù)雜的點(diǎn)云數(shù)據(jù)，提出一種局部點(diǎn)云參數(shù)化的方法。獲取以 R-tree的葉節(jié)點(diǎn)為中心的27個(gè)相同大小的空間網(wǎng)格內(nèi)的數(shù)據(jù)點(diǎn)，將其作為局部點(diǎn)云數(shù)據(jù)擬合參考平面，根據(jù)參考平面的法向量方向確定點(diǎn)云數(shù)據(jù)參數(shù)化和有序化采樣的方向，對(duì)局部點(diǎn)云進(jìn)行參數(shù)化后并擬合二次曲面。

(3) 對(duì)擬合的二次曲面進(jìn)行有序化采樣。根據(jù)局部參考平面的方向量信息，提出一種雙有序的采樣方法。根據(jù)采樣點(diǎn)與 R-tree頁(yè)節(jié)點(diǎn)的位置關(guān)系決定其取舍，最終可得到整個(gè)型面的單層有序點(diǎn)集。

實(shí)驗(yàn)結(jié)果表明該精簡(jiǎn)算法效率高，能夠在較高程度上保持點(diǎn)云原有的幾何特征，且不會(huì)丟失點(diǎn)云的細(xì)節(jié)特征，精簡(jiǎn)后的點(diǎn)云空間分布均勻有序，能夠大幅改善散亂分層點(diǎn)云的偏差，整體上提高數(shù)據(jù)的精確度。

1 有序化精簡(jiǎn)算法

針對(duì)散亂分層點(diǎn)云的有序化精簡(jiǎn)算法主要由3部分組成：建立散亂分層點(diǎn)云的空間拓?fù)浣Y(jié)構(gòu)、局部二次曲面的擬合和有序化采樣。算法流程如圖1所示。

圖1 算法流程圖

1.1 散亂分層點(diǎn)云空間拓?fù)浣Y(jié)構(gòu)的建立

點(diǎn)云的局部數(shù)據(jù)點(diǎn)能夠反映工件的局部型面幾何特征，因此快速準(zhǔn)確地獲取局部點(diǎn)云數(shù)據(jù)，是點(diǎn)云有序化精簡(jiǎn)的首要問(wèn)題。本文借助已知標(biāo)記點(diǎn)對(duì)點(diǎn)云建立三維 R-tree和八叉樹(shù)集成的空間索引。基于已知標(biāo)記點(diǎn)對(duì)三維網(wǎng)格而非數(shù)據(jù)點(diǎn)進(jìn)行聚類，然后對(duì)三維網(wǎng)格進(jìn)行八叉樹(shù)分裂，使該空間索引結(jié)構(gòu)兼具靜態(tài)方法的高效性和動(dòng)態(tài)方法的靈活性。

聚類完成后形成k個(gè)緊湊獨(dú)立的立方體簇，每個(gè)立方體簇外接空間矩形則為 R-tree的一級(jí)內(nèi)部節(jié)點(diǎn)。通過(guò)計(jì)算得到每個(gè)立方體中數(shù)據(jù)點(diǎn)的個(gè)數(shù)，將包含數(shù)據(jù)點(diǎn)的立方體作為 R-tree的二級(jí)內(nèi)部節(jié)點(diǎn)。設(shè)定扇出參數(shù)，即每個(gè)節(jié)點(diǎn)允許包含的最大和最小數(shù)據(jù)點(diǎn)個(gè)數(shù)，采用八叉樹(shù)剖分各立方體，直至所有的葉節(jié)點(diǎn)收斂。葉節(jié)點(diǎn)收斂條件為：葉節(jié)點(diǎn)中數(shù)據(jù)點(diǎn)個(gè)數(shù)小于最大數(shù)據(jù)點(diǎn)個(gè)數(shù)或邊長(zhǎng)等于最小網(wǎng)格尺寸slmin。圖 2為一工件實(shí)物圖及采用標(biāo)記點(diǎn)建立點(diǎn)云的三維R-tree空間索引結(jié)構(gòu)。

圖2 工件實(shí)物圖與工件點(diǎn)云的三維R-tree結(jié)構(gòu)

1.2 局部二次曲面的擬合

1.2.1 局部點(diǎn)云數(shù)據(jù)的參數(shù)化

分層點(diǎn)云的局部數(shù)據(jù)點(diǎn)沿其參考平面法向量方向是散亂分層的，所以描述同一局部特征的數(shù)據(jù)點(diǎn)會(huì)分布在相鄰的 R-tree葉節(jié)點(diǎn)中。以相鄰葉節(jié)點(diǎn)中的任意一個(gè)為中心，由該葉節(jié)點(diǎn)及與之鄰接的26個(gè)同等大小的立方體構(gòu)成的立方體空間，都包含另一個(gè)相鄰葉節(jié)點(diǎn)，因此其內(nèi)部的數(shù)據(jù)點(diǎn)可以完整描述點(diǎn)云的局部型面特征。本文以葉節(jié)點(diǎn)為中心的 27個(gè)立方體空間中的數(shù)據(jù)點(diǎn)集｛Ni｝,i=1,2,…,k 作為局部點(diǎn)云數(shù)據(jù)。

由于二次曲面是局部坐標(biāo)下的參數(shù)表示，需要建立局部坐標(biāo)系。首先利用局部點(diǎn)云數(shù)據(jù)擬合參考平面，得到單位法向量n。然后將葉節(jié)點(diǎn)為中心的 27個(gè)立方體空間的起始點(diǎn)(xo,yo,zo)作為局部坐標(biāo)系的原點(diǎn)。最后選取 3個(gè)工件坐標(biāo)軸中與參考平面法向量n夾角最小的一個(gè)，作為局部坐標(biāo)系的Z軸方向，建立局部坐標(biāo)系oxyz。如在圖3(a)中，參考平面的法向量n與工件坐標(biāo)系的zw軸的角度最小，則局部坐標(biāo)系的z軸與zw軸同向。局部坐標(biāo)系與工件坐標(biāo)系的關(guān)系為：

圖3 參數(shù)平面坐標(biāo)系的建立

參考累加弦長(zhǎng)參數(shù)化的方法[17]，將局部點(diǎn)云數(shù)據(jù)作如下參數(shù)化：①以局部坐標(biāo)系原點(diǎn)為原點(diǎn)，局部坐標(biāo)系x軸和y軸為u軸和v軸，建立參數(shù)平面坐標(biāo)系ouv，如圖3(b)所示。②確定以R-tree的葉節(jié)點(diǎn)為中心的 27個(gè)立方體空間的邊長(zhǎng)l。最終計(jì)算局部點(diǎn)云數(shù)據(jù)的參數(shù)值，｛Ni｝為點(diǎn)云的局部數(shù)據(jù)點(diǎn)集，Ni在局部坐標(biāo)系下的坐標(biāo)為（xi,yi,zi），那么Ni的參數(shù)值為。

1.2.2 局部二次曲面

本文采用二次參數(shù)曲面來(lái)近似表示任意復(fù)雜型面的局部形狀。二次參數(shù)曲面方程為：，其矩陣形式為：

其中，Q是3×3矩陣，其元素是矢量值Qij，。

引入9R空間矢量：

利用 2.1節(jié)得到的局部數(shù)據(jù)點(diǎn)集｛Ni｝的局部坐標(biāo)系坐標(biāo)（xi,yi,zi）及參數(shù)值（ui,vi），引入矢量，其中，，，，并將Q重寫(xiě)為Q=（a b c），那么逼近的二次曲面與數(shù)據(jù)點(diǎn)的誤差函數(shù)為：

二次參數(shù)曲面的擬合就是使誤差函數(shù)最小化的過(guò)程(圖4)，即使局部點(diǎn)云數(shù)據(jù)與二次參數(shù)曲面對(duì)應(yīng)點(diǎn)之間的歐幾里德距離的平方和最小[18]。通過(guò)推導(dǎo)，得到系數(shù)矩陣Q的表達(dá)式：

圖4 局部數(shù)據(jù)點(diǎn)擬合二次曲面示意圖

1.3 有序化采樣

局部二次曲面可以準(zhǔn)確地描述復(fù)雜型面的局部形狀，因此對(duì)局部二次曲面進(jìn)行采樣得到的數(shù)據(jù)點(diǎn)可以作為點(diǎn)云隱含型面上的參考點(diǎn)。為了使參考點(diǎn)在點(diǎn)云型面上的分布均勻有序，本文提出一種有序化的采樣方法。該方法是一種對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行局部雙向有序化的過(guò)程，具體方法是依據(jù)點(diǎn)云局部參考平面的法向量信息，從不同的坐標(biāo)軸方向?qū)植慷吻孢M(jìn)行采樣。比如工件坐標(biāo)系的xw軸(yw軸或zw軸)與點(diǎn)云局部參考平面法向量的夾角最小，則將葉節(jié)點(diǎn)的中軸線定義為過(guò)葉節(jié)點(diǎn)中心并與xw軸(yw軸或zw軸)平行的直線。計(jì)算葉節(jié)點(diǎn)的中軸線與局部二次曲面的交點(diǎn)，如果交點(diǎn)位于葉節(jié)點(diǎn)的內(nèi)部，那么將該交點(diǎn)作為點(diǎn)云的有序參考點(diǎn)；否則，該交點(diǎn)將不被采用。

由局部坐標(biāo)系和工件坐標(biāo)系的關(guān)系可知，在工件坐標(biāo)系下，無(wú)論葉節(jié)點(diǎn)的中軸線方向如何，其在局部坐標(biāo)系下都與z軸同向，如圖4所示。因此有序化采樣的計(jì)算過(guò)程為：令 u= 0.5， v= 0.5，按式(4)求取W，那么中軸線與局部二次曲面在局部坐標(biāo)系下的交點(diǎn) r（u, v），可由

得出。將交點(diǎn) r（u, v）轉(zhuǎn)換至工件坐標(biāo)系下，就可以得到點(diǎn)云型面上的一個(gè)有序參考點(diǎn)。

由于有序參考點(diǎn)是葉節(jié)點(diǎn)的中軸線與局部二次曲面的交點(diǎn)，可根據(jù)葉節(jié)點(diǎn)中軸線的方向即與工件坐標(biāo)系的xw軸、yw軸或zw軸平行，將參考點(diǎn)的有序類型分為yz有序、zx有序或xy有序。經(jīng)有序化采樣得到的參考點(diǎn)集，在由同一有序類型的參考點(diǎn)組成的非臨界區(qū)域，參考點(diǎn)在其有序方向上等間隔均勻分布；在不同有序類型區(qū)域間的臨界區(qū)域則由不同有序類型的參考點(diǎn)平滑過(guò)渡(圖5)。

圖5 有序化采樣示意圖

2 實(shí)驗(yàn)與分析

為驗(yàn)證本文提出的方法的可行性，使用基于標(biāo)記點(diǎn)的流動(dòng)式三維掃描儀采集了 3個(gè)不同工件的點(diǎn)云數(shù)據(jù)，分別從大規(guī)模數(shù)據(jù)精簡(jiǎn)、算法精度及大曲率數(shù)據(jù)精簡(jiǎn)等3個(gè)方面進(jìn)行了實(shí)驗(yàn)。

2.1 大規(guī)模數(shù)據(jù)精簡(jiǎn)實(shí)驗(yàn)

為驗(yàn)證算法具備精簡(jiǎn)大規(guī)模數(shù)據(jù)的能力，選取圖2(a)中工件的點(diǎn)云進(jìn)行精簡(jiǎn)實(shí)驗(yàn)，工件尺寸為1047.6 mm×512.1 mm×317.7 mm，點(diǎn)云的數(shù)據(jù)點(diǎn)數(shù)量為4 272 370個(gè)，由圖6可明顯看出，工件的點(diǎn)云含有大量冗余數(shù)據(jù)，數(shù)據(jù)點(diǎn)空間分布不均勻，通過(guò)局部放大圖可以看出數(shù)據(jù)點(diǎn)的空間分布散亂無(wú)序，并存在一定程度的分層。為了同時(shí)驗(yàn)證算法的精簡(jiǎn)效果及效率，將本文算法與文獻(xiàn)[4]中的均勻網(wǎng)格法和文獻(xiàn)[7]中的曲率采樣法的精簡(jiǎn)結(jié)果進(jìn)行對(duì)比。實(shí)驗(yàn)中將最小網(wǎng)格尺寸設(shè)置為3 mm。

圖6 工件點(diǎn)云及局部放大效果圖

分別使用 3種方法對(duì)工件的點(diǎn)云隔點(diǎn)讀取后進(jìn)行精簡(jiǎn)運(yùn)算，精簡(jiǎn)后點(diǎn)云效果圖如圖 7所示。由圖7可知3種方法所得點(diǎn)云的數(shù)據(jù)冗余情況較于精簡(jiǎn)前都有了很大的改善，基本上消除了分層，但前兩種方法所得點(diǎn)云仍散亂無(wú)序，而本文方法所得點(diǎn)云空間分布均勻有序。將 3種方法所得點(diǎn)云進(jìn)行三維網(wǎng)格化并平滑著色，可以看出經(jīng)本文方法精簡(jiǎn)后工件表面較于其他兩種方法更加平整光滑。由表1可知，采用本文方法對(duì)400多萬(wàn)點(diǎn)云數(shù)據(jù)進(jìn)行精簡(jiǎn)，精簡(jiǎn)率達(dá)到 98%以上，所用時(shí)間為127.61 s，在3種方法中用時(shí)最短，證明本文算法的速度較快。綜合分析圖7和表1可知，本文方法在保證精簡(jiǎn)后曲面平滑度的前提下能夠滿足點(diǎn)云精簡(jiǎn)率和精簡(jiǎn)速度的要求，表明本文算法實(shí)用有效，精簡(jiǎn)效果好，精簡(jiǎn)效率高。

圖7 不同方法所得點(diǎn)云及著色圖

表1 不同方法對(duì)大型工件點(diǎn)云精簡(jiǎn)結(jié)果比較

2.2 算法精度驗(yàn)證實(shí)驗(yàn)

為驗(yàn)證本文算法的精度能夠滿足應(yīng)用要求，用掃描儀對(duì)一個(gè)球體(圖8)進(jìn)行掃描，分別利用不同方法對(duì)得到的球面點(diǎn)云進(jìn)行精簡(jiǎn)，在逆向工程專業(yè)軟件Imageware12.1中對(duì)精簡(jiǎn)前后的球面數(shù)據(jù)點(diǎn)擬合球體，對(duì)比不同方法所得點(diǎn)云擬合球體的幾何特征及點(diǎn)云到擬合球體的幾何偏差，并給出點(diǎn)云到擬合球體的偏差分布圖。實(shí)驗(yàn)中將最小網(wǎng)格尺寸設(shè)置為1 mm，實(shí)驗(yàn)結(jié)果如表2及圖9所示。

由圖9可知，由于存在測(cè)量誤差，初始點(diǎn)云到擬合球體的偏差分布非常不均勻，且整體上偏差較大。采用不同方法精簡(jiǎn)后，點(diǎn)云偏差分布都得到明顯的改善，但是前兩種方法的球面上正負(fù)偏差交叉分布，且球面上存在偏差較大的點(diǎn)。經(jīng)本文方法精簡(jiǎn)后的點(diǎn)云偏差較于前兩種方法更為均勻，大部分偏差保持在0.1 mm以內(nèi)，球面上不存在偏差較大的點(diǎn)，點(diǎn)云的整體球面度較好。

圖8 球體實(shí)物圖

圖9 點(diǎn)云到擬合球體偏差分布圖

表2 不同方法對(duì)球體點(diǎn)云精簡(jiǎn)效果對(duì)比

由表2可知，3種方法都大幅減少了冗余數(shù)據(jù)，精簡(jiǎn)后擬合的球心坐標(biāo)和球體半徑基本保持不變，說(shuō)明 3種算法都能在較高程度上保持初始點(diǎn)云的幾何特征；但是本文方法相對(duì)于其他兩種方法，得到的型面參考點(diǎn)到擬合球面的幾何最大偏差、平均偏差及標(biāo)準(zhǔn)偏差都為最小，說(shuō)明本文方法對(duì)點(diǎn)云偏差的改善更加明顯，能夠整體上提高數(shù)據(jù)的精確度。

2.3 大曲率數(shù)據(jù)精簡(jiǎn)實(shí)驗(yàn)

工件型面大曲率區(qū)域的點(diǎn)云精簡(jiǎn)效果是檢驗(yàn)精簡(jiǎn)算法的重要標(biāo)準(zhǔn)之一，為驗(yàn)證算法對(duì)大曲率區(qū)域點(diǎn)云精簡(jiǎn)的有效性，選取一個(gè)矩形工件對(duì)其棱線區(qū)域進(jìn)行掃描，如圖10所示。棱線區(qū)域的型面特征滿足大曲率的特點(diǎn)，利用本文提出的算法對(duì)該區(qū)域的點(diǎn)云進(jìn)行精簡(jiǎn)，將精簡(jiǎn)前后的點(diǎn)云效果進(jìn)行對(duì)比，并給出精簡(jiǎn)前后棱線處點(diǎn)云的截面效果圖。實(shí)驗(yàn)中將最小網(wǎng)格尺寸設(shè)置為0.6 mm。

圖10 矩形工件的待掃描棱線區(qū)域

通過(guò)圖11可以看出，精簡(jiǎn)后的點(diǎn)云完整地保留了棱線特征。點(diǎn)云在棱線處的數(shù)據(jù)點(diǎn)在工件坐標(biāo)系下為有序化的臨界區(qū)域，精簡(jiǎn)后棱線區(qū)域的上表面數(shù)據(jù)點(diǎn)的有序類型為xy有序，側(cè)面數(shù)據(jù)點(diǎn)為yz有序，棱線處則由以上兩種類型的有序點(diǎn)自然過(guò)渡。

圖11 棱線區(qū)域精簡(jiǎn)前后點(diǎn)云對(duì)比圖

精簡(jiǎn)前后點(diǎn)云棱線處的橫截面如圖12所示，截面寬度約為0.5 mm?？梢钥闯觯?jiǎn)之前棱線處點(diǎn)云散亂分層，特征模糊。通過(guò)精簡(jiǎn)，棱線特征辨識(shí)度提高，數(shù)據(jù)點(diǎn)變?yōu)閱螌佑行螯c(diǎn)集，較好地保留了大曲率區(qū)域點(diǎn)云的細(xì)節(jié)特征。

圖12 棱線區(qū)域精簡(jiǎn)前后截面對(duì)比圖

3 結(jié) 論

針對(duì)激光掃描儀測(cè)量誤差帶來(lái)的點(diǎn)云散亂分層的問(wèn)題，提出了一種有序化精簡(jiǎn)方法，該方法適用于大規(guī)模的，具有復(fù)雜幾何特征的散亂分層點(diǎn)云的精簡(jiǎn)：①基于已知標(biāo)記點(diǎn)建立三維 R-tree和八叉樹(shù)集成的空間索引，該索引便于快速準(zhǔn)確獲取局部點(diǎn)云數(shù)據(jù)；②利用局部二次曲面逼近局部數(shù)據(jù)點(diǎn)并對(duì)其進(jìn)行采樣，可以有效地降低點(diǎn)云的幾何偏差，提高數(shù)據(jù)點(diǎn)的整體精確度；精簡(jiǎn)后的點(diǎn)云能在較高程度上保持初始點(diǎn)云的幾何特征，且不會(huì)丟失大曲率區(qū)域的細(xì)節(jié)特征；③根據(jù)局部參考平面的法向量來(lái)決定采樣方向，可以使整個(gè)型面的數(shù)據(jù)點(diǎn)均勻有序，為點(diǎn)云的后續(xù)處理提供了便利。

[1] 范 然, 金小剛. 大規(guī)模點(diǎn)云選擇及精簡(jiǎn)[J]. 圖學(xué)學(xué)報(bào), 2013, 34(3): 12-19.

[2] Yau H T, Chen C Y, W ilhelm R G. Registration and integration of multiple laser scanned data for reverse engineering of complex 3D models [J]. International Journal of Production Research, 2000, 38(2): 269-285.

[3] Weir D J, Milroy M, Bradley C, et al. Reverse engineering physical models employing w rap-around B-spline surfaces and quadric [J]. Proceedings of the Institution of Mechanical Engineers, 1996, 210(B2): 147-157.

[4] Martin R R, Varady T. RECCAD, Deliverable Document 1 COPERNICUS Project [EB/OL]. [2015-07-15]. http://ralph.cs.cf.ac.uk/papers/geometry/recrep.pdf#page =119.

[5] Lee K H, Woo H, Suk T. Point data reduction using 3D grids [J]. Advanced Manufacturing Technology, 2001, 18: 201-210.

[6] Lee P F, Huang C P. The DSO feature based point cloud simplification [C]//Computer Graphics, Imaging and Visualization (CGIV), 2011 Eighth International Conference on. New York: IEEE Press, 2011: 1-6.

[7] 陳璋雯, 達(dá)飛鵬. 基于模糊熵迭代的三維點(diǎn)云精簡(jiǎn)算法[J]. 光學(xué)學(xué)報(bào), 2013, 33(8): 153-159.

[8] 顧 賓. 基于標(biāo)記點(diǎn)的流動(dòng)式三維掃描測(cè)量技術(shù)的研究[D]. 青島: 中國(guó)海洋大學(xué), 2013.

[9] Zhu Q, Gong J, Zhang Y T. An efficient 3D R-tree spatial index method for virtual geographic environments [J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2007, 62(3): 217-224.

[10] 龔 俊, 柯勝男, 朱 慶, 等. 一種八叉樹(shù)和三維 R樹(shù)集成的激光點(diǎn)云數(shù)據(jù)管理方法[J]. 測(cè)繪學(xué)報(bào), 2012, 41(4): 597-604.

[11] 邵正偉, 席 平. 基于八叉樹(shù)編碼的點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法[J]. 圖學(xué)學(xué)報(bào), 2010, 31(4): 73-76.

[12] 邾繼貴, 郭 磊, 葉聲華. 現(xiàn)場(chǎng)條件下大空間三維精密定位原理與方法[J]. 光學(xué)學(xué)報(bào), 2009, 29(7), 1872-1876.

[13] 張維中, 張麗艷, 潘振寬, 等. 一種基于標(biāo)記點(diǎn)的近景攝影測(cè)量系統(tǒng)[J]. 東南大學(xué)學(xué)報(bào): 自然科學(xué)版, 2006, 36(5): 741-745.

[14] 周 玲, 張麗艷, 鄭建冬, 等. 近景攝影測(cè)量中標(biāo)記點(diǎn)的自動(dòng)檢測(cè)[J]. 應(yīng)用科學(xué)學(xué)報(bào), 2007, 25(3): 288-294.

[15] 解則曉, 高 翔, 崔 健. 移動(dòng)式三維測(cè)量用圓形標(biāo)記點(diǎn)提取算法[J]. 中國(guó)激光, 2013, 40(12): 160-105.

[16] 汪 中, 劉貴全, 陳恩紅. 一種優(yōu)化初始中心點(diǎn)的K-means算法[J]. 模式識(shí)別與人工智能, 2009, 22(2): 199-304.

[17] Ma W, Kruth J P. Parameterization of random ly measured points for least squares fitting of B-spline curves and surfaces [J]. Computer-Aided Design, 1995, 27(9): 663-675.

[18] Yang M, Lee E. Segmentation of measured point data using a parametric quadric surface approximation [J]. Computer-Aided Design, 1999, 31(7): 449-457.

A Data Reduction and Ordering A lgorithm for Scattered and Layered Point Cloud

Xie Zexiao, Liu Jingxiao, Pan Chengcheng, Zhang Mengze

(College of Engineering, Ocean University of China, Qingdao Shandong 266100, China)

Concerning the scattered and layered characteristic of point cloud acquired by laser scanners, a data reduction and ordering algorithm is proposed. Firstly the spatial index of point cloud is created based on known marked points using a method integrating Octree and 3D R-tree, ensuring fast and correct access to local data and high efficiency of data retrieval. Secondly one axis of the work coordinate system is selected as the projective direction for parameterizing the local data, which is determined by the normal vector of local reference plane. Then along the selected direction the local data is parameterized and the quadratic surface is approximated. Finally the ordered set of reference points is obtained by sampling the quadratic surface through the R-tree’s leaf nodes, making the scattered and layered point cloud be single layered. Application examples show that the algorithm can improve the overall accuracy of the data as well as maintain the details of point cloud, indicating good validity and practicability in the reduction of scattered and layered large-scale point cloud with complex geometric features.

data reduction; spatial ordering; scattered and layered point cloud; marked point; 3D R-tree

TG 156

10.11996/JG.j.2095-302X.2016030359

A

2095-302X(2016)03-0359-08

2015-08-15；定稿日期：2016-03-13

國(guó)家自然科學(xué)基金項(xiàng)目(61571408)

解則曉(1968–)，男，山東臨沂人，教授，博士。主要研究方向?yàn)闄C(jī)器視覺(jué)和機(jī)器人運(yùn)動(dòng)控制及機(jī)器人測(cè)量等。E-mail：xiezexiao@ouc.edu.cn