解則曉， 劉靜曉， 潘成成， 張夢澤

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

一種散亂分層點云的有序化精簡方法

解則曉， 劉靜曉， 潘成成， 張夢澤

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

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

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

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

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

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

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

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

本文方法主要分3步進行：

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

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

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

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

1 有序化精簡算法

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

圖1 算法流程圖

1.1 散亂分層點云空間拓撲結(jié)構(gòu)的建立

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

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

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

1.2 局部二次曲面的擬合

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

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

由于二次曲面是局部坐標(biāo)下的參數(shù)表示，需要建立局部坐標(biāo)系。首先利用局部點云數(shù)據(jù)擬合參考平面，得到單位法向量n。然后將葉節(jié)點為中心的 27個立方體空間的起始點(xo,yo,zo)作為局部坐標(biāo)系的原點。最后選取 3個工件坐標(biāo)軸中與參考平面法向量n夾角最小的一個，作為局部坐標(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)系的建立

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

1.2.2 局部二次曲面

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

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

引入9R空間矢量：

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

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

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

1.3 有序化采樣

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

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

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

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

圖5 有序化采樣示意圖

2 實驗與分析

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

2.1 大規(guī)模數(shù)據(jù)精簡實驗

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

圖6 工件點云及局部放大效果圖

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

圖7 不同方法所得點云及著色圖

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

2.2 算法精度驗證實驗

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

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

圖8 球體實物圖

圖9 點云到擬合球體偏差分布圖

表2 不同方法對球體點云精簡效果對比

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

2.3 大曲率數(shù)據(jù)精簡實驗

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

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

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

圖11 棱線區(qū)域精簡前后點云對比圖

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

圖12 棱線區(qū)域精簡前后截面對比圖

3 結(jié) 論

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

[1] 范 然, 金小剛. 大規(guī)模點云選擇及精簡[J]. 圖學(xué)學(xué)報, 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] 陳璋雯, 達飛鵬. 基于模糊熵迭代的三維點云精簡算法[J]. 光學(xué)學(xué)報, 2013, 33(8): 153-159.

[8] 顧 賓. 基于標(biāo)記點的流動式三維掃描測量技術(shù)的研究[D]. 青島: 中國海洋大學(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] 龔 俊, 柯勝男, 朱 慶, 等. 一種八叉樹和三維 R樹集成的激光點云數(shù)據(jù)管理方法[J]. 測繪學(xué)報, 2012, 41(4): 597-604.

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

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

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

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

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

[16] 汪 中, 劉貴全, 陳恩紅. 一種優(yōu)化初始中心點的K-means算法[J]. 模式識別與人工智能, 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

國家自然科學(xué)基金項目(61571408)

解則曉(1968–)，男，山東臨沂人，教授，博士。主要研究方向為機器視覺和機器人運動控制及機器人測量等。E-mail：xiezexiao@ouc.edu.cn