基于局部和全局采樣點(diǎn)云數(shù)據(jù)簡(jiǎn)化算法研究

付 瑋，吳祿慎，陳華偉

(1．南昌大學(xué)機(jī)電工程學(xué)院，江西 南昌330031;2．南昌航空大學(xué)航空制造工程學(xué)院，江西 南昌330069)

1 引言

目前，3D激光掃描技術(shù)［1－2］在快速、準(zhǔn)確地獲取點(diǎn)云數(shù)據(jù)方面有了很大的進(jìn)展，但是，如何處理這些龐大的點(diǎn)云數(shù)據(jù)成為基于3D激光掃描技術(shù)的主要問(wèn)題。直接處理大量的點(diǎn)云數(shù)據(jù)，數(shù)據(jù)存儲(chǔ)和處理便成為難以突破的瓶頸。實(shí)際上，并非所有的點(diǎn)云數(shù)據(jù)對(duì)模型重建都有用處，因此，有必要在保證一定精度的前提下，對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行簡(jiǎn)化處理。

一般點(diǎn)云簡(jiǎn)化方法包括:基于曲率和基于空間分割兩大類方法?；谇史椒ㄓ薪嵌绕罘ǎ?］、最小距離法［4］等;基于空間分割方法有均勻網(wǎng)格法［5］、包圍盒法［6］、基于三角網(wǎng)格方法［7］。兩類方法各有局限，基于曲率的簡(jiǎn)化算法雖能很好地保留幾何特征，但是簡(jiǎn)化效率低［8］;基于空間分割的簡(jiǎn)化算法不適用于復(fù)雜特征和多曲率的散亂點(diǎn)云數(shù)據(jù)簡(jiǎn)化［9］。

很多研究學(xué)者在數(shù)據(jù)簡(jiǎn)化的研究中，提出了各種不同的處理方法，Vero和Leon［10］在1997年提出一種用誤差帶(Error Zones)減少多面體數(shù)據(jù)點(diǎn)的方法。Chen Y．H．［7］1999年提出一種通過(guò)減少網(wǎng)格模型中的三角形，從而達(dá)到減少數(shù)據(jù)點(diǎn)的方法。這種方法先直接將測(cè)得的數(shù)據(jù)轉(zhuǎn)換成STL文件，然后通過(guò)減少STL文件的三角形數(shù)量，以實(shí)現(xiàn)減少數(shù)據(jù)量。本文提出了一種有效的點(diǎn)云數(shù)據(jù)簡(jiǎn)化方法，將局部和全局的采樣特征相融合。該方法既考慮了局部點(diǎn)云細(xì)節(jié)，又考慮了點(diǎn)云的全局形狀特征，可以有效的簡(jiǎn)化點(diǎn)云數(shù)據(jù)。對(duì)形狀比較復(fù)雜的曲面(汽車模具等)有比較好的簡(jiǎn)化效果。

2 局部點(diǎn)云特征采樣

本文采用基于點(diǎn)云的網(wǎng)格分割的非均勻網(wǎng)格法來(lái)提取局部點(diǎn)云特征。非均勻網(wǎng)格法［6］是點(diǎn)云簡(jiǎn)化中較常用的方法之一，采用非均勻網(wǎng)格法可以去除大量的數(shù)據(jù)點(diǎn)。該方法可以采用角度偏差法從模型表面點(diǎn)云數(shù)據(jù)中獲取數(shù)據(jù)樣本。

角度可通過(guò)三個(gè)連續(xù)點(diǎn)的方向矢量計(jì)算得到，如圖1所示，(x1，y1)，(x2，y2)，(x3，y3)三點(diǎn)。角度代表曲率信息，角度大，曲率就大;反之，角度小，曲率也小。根據(jù)角度大小，高曲率的點(diǎn)可以被提取出來(lái)。通過(guò)角偏差抽取的點(diǎn)代表高曲率區(qū)域。為準(zhǔn)確地表示零件外形，進(jìn)行點(diǎn)云數(shù)據(jù)簡(jiǎn)化時(shí)，必須保留這些點(diǎn)。這樣，使用角度偏移法進(jìn)行點(diǎn)云提取后，對(duì)曲率小的區(qū)域采用大網(wǎng)格尺寸進(jìn)行點(diǎn)云簡(jiǎn)化，對(duì)曲率大的區(qū)域采用較小網(wǎng)格尺寸進(jìn)行點(diǎn)云簡(jiǎn)化。如圖2所示，分離過(guò)程中網(wǎng)絡(luò)尺寸大于最大網(wǎng)絡(luò)尺寸，網(wǎng)格被進(jìn)一步分割，直到小于最大網(wǎng)格尺寸為止。當(dāng)對(duì)網(wǎng)格中點(diǎn)應(yīng)用中值濾波時(shí)，將產(chǎn)生一個(gè)代表樣點(diǎn)。最后，保留點(diǎn)是由每個(gè)網(wǎng)絡(luò)的中值濾波點(diǎn)和角度偏移提取的點(diǎn)組成向量L。通過(guò)非均勻網(wǎng)格法進(jìn)行點(diǎn)云簡(jiǎn)化，不但有減少點(diǎn)云數(shù)據(jù)的功能，還能有效去除噪聲點(diǎn)，另外，這種方法只是選用其中的某些點(diǎn)，并不改變點(diǎn)的空間位置，可以很好地保留原始數(shù)據(jù)。

圖1 角度偏差法

圖2 非均勻網(wǎng)格法簡(jiǎn)化數(shù)據(jù)點(diǎn)

3 基于體素的全局點(diǎn)云特征采樣

本文提出一種基于空間體素化方法對(duì)點(diǎn)云進(jìn)行全局采樣，可以最大限度地反映點(diǎn)云的全局特征。

體素是體圖形學(xué)中描述體模型的基本數(shù)據(jù)單元。體素化(Voxelization)是從面模型到體模型的轉(zhuǎn)換過(guò)程，其任務(wù)是:將物體的幾何形式表示離散成最接近該物體的體素表示形式，產(chǎn)生體數(shù)據(jù)集，表示模型的空間體素跟表示圖像的二維像素比較相似，可以理解為從二維的點(diǎn)擴(kuò)展到三維的立方體單元。

對(duì)于數(shù)據(jù)量比較大的點(diǎn)云，它的點(diǎn)云分布一般是雜亂無(wú)章的，計(jì)算機(jī)處理這些點(diǎn)云數(shù)據(jù)時(shí)，非常耗費(fèi)時(shí)間，效率比較低，不能達(dá)到實(shí)時(shí)處理的目的。因此，有必要將冗余點(diǎn)或者無(wú)用點(diǎn)去除，而體素化的方法，恰好可以解決這一難題，它可以大大地減少點(diǎn)云的數(shù)據(jù)量。

首先，使用規(guī)則的三維網(wǎng)格來(lái)劃分點(diǎn)云空間，每個(gè)點(diǎn)云都在三維立體單元中，其存儲(chǔ)了每個(gè)體素的質(zhì)心坐標(biāo)和點(diǎn)云數(shù)。體素化方法主要是針對(duì)點(diǎn)云的XYZ坐標(biāo)值的編碼。編碼是采用12位的整數(shù)，它由3部分四位數(shù)組成。每部分表示其中一個(gè)XYZ坐標(biāo)值，將其除以體素大小，便可將坐標(biāo)值轉(zhuǎn)換為體素單元，并且用最小的XYZ坐標(biāo)值來(lái)替代原始點(diǎn)云數(shù)。參見(jiàn)公式(1)。這樣，三部分就可以組成一個(gè)簡(jiǎn)單的編碼。簡(jiǎn)單的編碼原理如圖3所示。

編碼格式:

其中，X，Y，Z分別是體素的坐標(biāo)值，X0，Y0，Z0分別是體素X，Y，Z坐標(biāo)值的最小值;Vs是體素大小。

12位編碼值儲(chǔ)存在一個(gè)簡(jiǎn)單向量G中。向量長(zhǎng)度等于點(diǎn)云數(shù)N?？紤]到屬于同一體素中的點(diǎn)云有相同的編碼，向量元素根據(jù)它們的數(shù)值大小來(lái)分類。因此，同一體素內(nèi)的點(diǎn)被聚集在一起。如圖3所示。為了獲取更多的采樣點(diǎn)，體素單元網(wǎng)格需要進(jìn)一步細(xì)分，如果體素單元網(wǎng)格的標(biāo)準(zhǔn)偏差大于給定值，則單元網(wǎng)格被繼續(xù)細(xì)分;這個(gè)過(guò)程反復(fù)進(jìn)行直到網(wǎng)格的標(biāo)準(zhǔn)偏差小于給定值;或者網(wǎng)格尺寸達(dá)到用戶設(shè)定的值。通常網(wǎng)格最小尺寸根據(jù)零件復(fù)雜程度選定。

編碼算法過(guò)程:假設(shè)有一個(gè)點(diǎn)，其體素尺寸大小取為0．1 cm。其X坐標(biāo)值為:2468．232;Y坐標(biāo)值為:3578．556;Z坐標(biāo)值為:98．662。其Xmin為:2000;Ymin為:3000;Zmin為:0;根據(jù)公式(1)得:X體素值為:4682;Y體素值為:5785;Z體素值為:986。最后，12位的編碼為:468257850986。表1是對(duì)12個(gè)體素點(diǎn)的編碼。

圖3 體素單元

表1 點(diǎn)云索引及編碼

由表1可以看出，點(diǎn)1，7在A體素中;點(diǎn)4，8，11在B體素中;點(diǎn)2，5，9在C體素中;點(diǎn)3，6，10，12在D體素中。可以將點(diǎn)1，4，2，3(分別屬于體素A，B，C，D)組成一個(gè)向量G，由該矢量代表體素的特征值，其他的值可以濾去，這樣原來(lái)體素中有12個(gè)點(diǎn)，經(jīng)過(guò)此方法后簡(jiǎn)化為4個(gè)點(diǎn)。但是可以完全的表達(dá)點(diǎn)云的全局特征。

4 點(diǎn)云特征的融合

為了獲取更好的簡(jiǎn)化結(jié)果，這里將局部和全局采樣點(diǎn)特征融合在一起。L是局部采樣特征值，G是全局采樣特征值，點(diǎn)云簡(jiǎn)化特征S可以通過(guò)公式(2)來(lái)定義:

其中，T是控制局部采樣點(diǎn)集和全局采樣點(diǎn)集的權(quán)重。如果T過(guò)大，這種方法仍然可以很好地表示全局形狀，但它可能會(huì)失去許多局部的形狀細(xì)節(jié)。當(dāng)T變小時(shí)，可以比較好地表示局部形狀，但全局形狀表示可能會(huì)受到影響。因此，需要通過(guò)實(shí)驗(yàn)找到一個(gè)合適的T值。

5 實(shí)驗(yàn)及誤差分析

5．1 算法實(shí)驗(yàn)

圖4是利用該算法進(jìn)行點(diǎn)云數(shù)據(jù)簡(jiǎn)化的流程圖，首先通過(guò)三維光柵掃描、解相、去包裹、除噪等過(guò)程獲取物體三維點(diǎn)云圖。

圖4 點(diǎn)云簡(jiǎn)化算法流程

通過(guò)非均勻網(wǎng)格法提取點(diǎn)云數(shù)據(jù)曲率比較大的局部特征值;然后運(yùn)用空間體素編碼法提取點(diǎn)云數(shù)據(jù)的全局形狀特征值。最后，使用公式(2)將二者特征值融合，獲取點(diǎn)云簡(jiǎn)化最佳效果值。

為了驗(yàn)證算法的有效性和正確性，本文分別對(duì)Bunny模型和某型號(hào)汽車模具點(diǎn)云進(jìn)行簡(jiǎn)化，如表2所示三種算法的點(diǎn)云簡(jiǎn)化數(shù)據(jù)。測(cè)試環(huán)境為:Intel core 2．0 GHz，CPU 2G內(nèi)存;根據(jù)實(shí)驗(yàn)，權(quán)值取T=6．5。

表2 實(shí)例點(diǎn)云數(shù)據(jù)

圖5為實(shí)驗(yàn)簡(jiǎn)化效果圖，通過(guò)上面實(shí)驗(yàn)可以得出，本文算法能夠有效簡(jiǎn)化物體的點(diǎn)云數(shù)據(jù)，又能保證物體形狀特征。空間體素編碼法簡(jiǎn)化效率優(yōu)于非均勻網(wǎng)格算法。本文提出的融合算法簡(jiǎn)化效率優(yōu)于非均勻網(wǎng)格算法和空間體素編碼法。Bunny模型和汽車模具在融合算法下，基本保留了模型數(shù)據(jù)的表面特征，簡(jiǎn)化數(shù)據(jù)量最少，而非均勻網(wǎng)格算法，簡(jiǎn)化數(shù)據(jù)明顯較多;采用體素編碼算法，簡(jiǎn)化數(shù)據(jù)比非均勻網(wǎng)格算法少。由此可見(jiàn)，本文融合算法的簡(jiǎn)化效率較好。本算法中的T值根據(jù)模型的曲率和形狀是可調(diào)的。

圖5 簡(jiǎn)化效果圖

實(shí)驗(yàn)還對(duì)本文所提出的算法與文獻(xiàn)［12］算法在點(diǎn)云簡(jiǎn)化時(shí)間上做了比較，本文算法在對(duì)Bunny模型簡(jiǎn)化耗時(shí)0．76 s，對(duì)汽車模具簡(jiǎn)化耗時(shí)0．94 s;而文獻(xiàn)［12］算法對(duì)Bunny模型簡(jiǎn)化耗時(shí)0．87 s，對(duì)汽車模具簡(jiǎn)化耗時(shí)1．03 s。可見(jiàn)，本文算法的簡(jiǎn)化運(yùn)行速度優(yōu)于文獻(xiàn)［12］算法速度，具有較好的實(shí)用性。

5．2 簡(jiǎn)化誤差分析

為了評(píng)價(jià)簡(jiǎn)化點(diǎn)云集的準(zhǔn)確性，在原始點(diǎn)云集和簡(jiǎn)化點(diǎn)云集之間的幾何誤差，Cignoni等［11］開(kāi)發(fā)了Metro工具來(lái)比較曲面直徑的誤差。Pauly等［12］和Miao等［13］采用了相似的方法來(lái)評(píng)估簡(jiǎn)化誤差。本文采用了原始點(diǎn)云集S和簡(jiǎn)化后的點(diǎn)云集S'的最大誤差和平均誤差［14］。

其中，每個(gè)點(diǎn)q∈S，幾何誤差d(q，S')是采樣點(diǎn)q和它在簡(jiǎn)化點(diǎn)云曲面S'上的投影點(diǎn)q－之間的歐幾里德距離。點(diǎn)云簡(jiǎn)化誤差如表3所示。

表3 點(diǎn)云簡(jiǎn)化誤差

使用本文提出的融合算法的最大誤差和平均誤差比非均勻網(wǎng)格算法和體素化編碼法要小。可見(jiàn)其有效性較好。

6 結(jié)論

點(diǎn)云簡(jiǎn)化可刪除大量冗余點(diǎn)云，而常用的非均勻網(wǎng)格法簡(jiǎn)化點(diǎn)云存在簡(jiǎn)化效率不高，容易丟失細(xì)節(jié)信息和關(guān)鍵特征的缺點(diǎn)。本文提出局部和全局特征法簡(jiǎn)化無(wú)序點(diǎn)云，根據(jù)調(diào)整T值靈活控制局部特征和全局特征所占權(quán)重，達(dá)到刪減冗余點(diǎn)云數(shù)據(jù)的最好效果。實(shí)驗(yàn)例證本文算法簡(jiǎn)化點(diǎn)云數(shù)據(jù)既能保留突變區(qū)細(xì)節(jié)特征，又能大量刪除平坦區(qū)冗余點(diǎn)云數(shù)據(jù)，相比非均勻網(wǎng)格法和空間體素法，具有更高的點(diǎn)云簡(jiǎn)化效率，而且簡(jiǎn)化誤差也比較小。

［1］ LIU Weijun，SUN Yuwen．Principal，method and application of reverse Engineering［M］．Beijing:Mechanical industry press，2008．(in Chinese)劉偉軍，孫玉文．逆向工程原理方法及應(yīng)用［M］．北京:機(jī)械工業(yè)出版社，2008．

［2］ ZHANG Guoxiong．Three coordinate measuring machine［M］．Tianjin:tianjin university press，1999．(in Chinese)張國(guó)雄．三坐標(biāo)測(cè)量機(jī)［M］．天津:天津大學(xué)出版社，1999．

［3］ Lee K H，Woo H，Suk T．Point data reduction using 3D grids［J］．The International Journal of Advanced Manufacturing Technology，2001，17(3):735－743．

［4］ LIU Deping，CHEN Jianjun．Point data reduction technique in reverse engineering［J］．Journal of xidiann university，2008，35(2):334－339．(in Chinese)劉德平，陳建軍．逆向工程中數(shù)據(jù)精簡(jiǎn)技術(shù)的研究［J］．西安電子科技大學(xué)學(xué)報(bào)，2008，35(2):334－339．

［5］ Martin R R，Stroud I A，Marshal A D．Data reduction for reverse engineering Reccad deliverable document Icoperunicus project［J］．Computer and Automation Institute of Hungarian Academy of Science，1996，1068:63－6．

［6］ SUN W，Bradley C，ZHANGY F，et al，Cloud data modeling employing a unified non－redundant triangular mesh［J］．Computer Aided Design，2001，33(2):183－193．

［7］ Chen Y H，Neg C T，Wang Y Z．Data reduction integrated reverse engineering and rapid prototyping［J］．International Journal of Computer Integrated Manufacturing，1999，12(2):97－103．

［8］ SUN Dianzhu，ZHU Changzhi，F(xiàn)AN Zhixian．Reduction algorithm for scattered points based on model surface analysis［J］．China mechanical engineering，2009，20(23):2840－2843．(in Chinese)孫殿柱，朱昌志，范志先，等．基于型面特征的三維散亂點(diǎn)云精簡(jiǎn)算法［J］．中國(guó)機(jī)械工程，2009，20(23):2840－2843．

［9］ ZHOU Yu，ZHANG Wanbing，DU Farong．Algorithm for reduction of scattered point cloud data based on curvature［J］．Journal of Beijing Institute of Technology，2010，30(7):785－789．(in Chinese)周煜，張萬(wàn)兵，杜發(fā)榮，等．散亂點(diǎn)云數(shù)據(jù)的曲率精簡(jiǎn)算法［J］．北京理工大學(xué)學(xué)報(bào)，2010，30(7):785－789．

［10］Veron P，Leon J C．Static polyhedron simplification using error measurement［J］．Computer Aided Design，1997，29:287－298．

［11］Cinnoni P，Rocchini C，Scipigno R．Metro:measuring error on simplified surfaces［J］．Computer Graphics Forum 1998，17(2):167－174．

［12］Pauly M，Gross M，Kobbelt L P．Efficient simplification of point－sampled surfaces［C］．Proceeding of the 13thIEEE visualization conference，2012:163－170．

［13］Miao Y，Pajarola R，F(xiàn)eng J．Curvature－aware adaptive re－sampling for point－sampled geometry［J］．Computer－Aided Design，2009，41(6):395－403．

［14］Baoquan Shi，Jin Liang，Qing Liu．Adaptive simplification of point cloud using K－means clustering［J］．Computer－Aided Design，2011，43(1):910－922．