基于角度-樹非均勻網(wǎng)格法的數(shù)據(jù)點(diǎn)云數(shù)據(jù)預(yù)處理

基于角度-樹非均勻網(wǎng)格法的數(shù)據(jù)點(diǎn)云數(shù)據(jù)預(yù)處理

隨著市場(chǎng)需求的多樣性，逆向工程（resource）已成為核電站產(chǎn)品中不可或缺的重要因素。非接觸式測(cè)量如光柵投影掃描等數(shù)據(jù)獲取速度快，單次掃描能獲上萬個(gè)數(shù)據(jù)點(diǎn)，隨著其測(cè)量精度的提高，非接觸式測(cè)量應(yīng)用愈加廣泛。雖然非接觸方法可快速獲取待測(cè)表面的大量數(shù)據(jù)，但所獲得的測(cè)量數(shù)據(jù)點(diǎn)群密度一般很大，存儲(chǔ)處理或顯示都將消耗大量的時(shí)間和計(jì)算機(jī)資源。因此，在逆向工程中點(diǎn)云測(cè)量數(shù)據(jù)的精簡(jiǎn)是數(shù)據(jù)預(yù)處理的重要工作之一。Martin,Stroud和Marshall提出了均勻網(wǎng)格精簡(jiǎn)算法，現(xiàn)已在圖像處理中得到廣泛應(yīng)用。Lee等對(duì)均勻網(wǎng)格法進(jìn)行了改進(jìn)，提出了非均勻網(wǎng)格精簡(jiǎn)方法，但對(duì)數(shù)據(jù)點(diǎn)云的邊界點(diǎn)不容易確定。本文在此基礎(chǔ)上提出了一種改進(jìn)型的點(diǎn)云精簡(jiǎn)方法，該方法的基本思路是先利用基于八叉樹非均勻網(wǎng)格法，將點(diǎn)云處理成按掃描線存儲(chǔ)的結(jié)構(gòu)化測(cè)量數(shù)據(jù)，再利用角度-弦差法進(jìn)行逐線精簡(jiǎn)。這樣能夠處理一些曲率變化大、具有復(fù)雜特征的散亂點(diǎn)云。1維數(shù)據(jù)的精簡(jiǎn)化激光掃描測(cè)量得到的數(shù)據(jù)通常都是按掃描線進(jìn)行存儲(chǔ)的，按逐行掃描所得的點(diǎn)云數(shù)據(jù)是一維的。雖然這些點(diǎn)在掃描線上的分布密度很大，但由于每條掃描線之間的間距較大，因此對(duì)掃描數(shù)據(jù)的精簡(jiǎn)可以簡(jiǎn)化到掃描線上，即對(duì)一維數(shù)據(jù)的精簡(jiǎn)。如果單獨(dú)用角度閾值來進(jìn)行數(shù)據(jù)精簡(jiǎn)，當(dāng)兩個(gè)相鄰點(diǎn)相距較遠(yuǎn)時(shí)，即使夾角很小，弦高差也可能很大，這時(shí)不能單憑角度小就將其剔除：另外當(dāng)兩個(gè)相鄰點(diǎn)相距較近時(shí)，弦高很小也可能有較大夾角，這時(shí)也不能由于弦差小而將其保留。因此，采用給定的角度誤差和弦高誤差兩個(gè)方面的限制，可以克服上述缺陷，快速有效地精簡(jiǎn)數(shù)據(jù)。2利用雙組分樹狀結(jié)構(gòu)的方法，分為8個(gè)樹狀結(jié)構(gòu)的設(shè)計(jì)和去木處理該方法的模型基礎(chǔ)是八叉樹結(jié)構(gòu)，八叉樹的空間分割模型是利用一個(gè)立方體序列包圍一片數(shù)據(jù)點(diǎn)云所占據(jù)的空間，其方法是首先構(gòu)造出測(cè)量點(diǎn)云的最小外接立方體，并把它作為八叉樹結(jié)構(gòu)的根結(jié)點(diǎn)，然后將該立方體均勻分割成大小相同的8個(gè)子立方體，如圖1所示，每個(gè)子立方體被看作根結(jié)點(diǎn)的子結(jié)點(diǎn)，由此將造型空間遞歸細(xì)分為2的冪次方個(gè)子立方體，這種方法是網(wǎng)格的均勻細(xì)分法，并且已經(jīng)廣泛應(yīng)用在計(jì)算機(jī)圖形學(xué)和圖像處理中，它可以看作是一個(gè)樹狀結(jié)構(gòu)。在八叉樹結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)著1個(gè)立方體，每個(gè)立方體包含8個(gè)子立方體，在均勻細(xì)分中每個(gè)子立方體在x、y方向上的邊長(zhǎng)為上一級(jí)立方體邊長(zhǎng)的一半，所以這8個(gè)子立方體就是上一級(jí)立方體的一次細(xì)分，同一次細(xì)分得到的子立方體屬于同一級(jí)，根據(jù)實(shí)際應(yīng)用的不同，細(xì)分的標(biāo)準(zhǔn)也就不同，在進(jìn)行實(shí)體邊界的擬合中，那些完全在實(shí)體內(nèi)部或者是外部的網(wǎng)格單元就要被刪掉，而那些包含邊界點(diǎn)的網(wǎng)格單元才會(huì)進(jìn)行細(xì)分。3叉樹非均勻網(wǎng)格法的應(yīng)用上述兩種數(shù)據(jù)的直接簡(jiǎn)化算法都具有較高的效率，但鑒于算法自身的特點(diǎn)，其適用范圍均有限制。對(duì)于曲率變化大、附加特征多的表面測(cè)量數(shù)據(jù)，上述兩種直接精簡(jiǎn)算法均難以得到直接應(yīng)用。改進(jìn)的數(shù)據(jù)直接精簡(jiǎn)算法是將二者結(jié)合起來。其基本思路是：首先利用基于八叉樹非均勻網(wǎng)格法，分割初始測(cè)量點(diǎn)云，獲得一條條按掃描線有序排列的測(cè)量點(diǎn)群，然后應(yīng)用角度—弦差法來逐線精簡(jiǎn)，從而得到一個(gè)精簡(jiǎn)后的點(diǎn)云。由于角度—弦差法可以較好地保留特征點(diǎn)，本文算法還可以適用于附加特征較多的表面測(cè)量數(shù)據(jù)，完整的算法過程描述如下。(1）若初始測(cè)量點(diǎn)云為按掃描線存儲(chǔ)的結(jié)構(gòu)化測(cè)量點(diǎn)云，則直接調(diào)用角度-弦差法進(jìn)行數(shù)據(jù)精簡(jiǎn)。若用戶認(rèn)為被測(cè)表面曲率變化較小、附加特征較少，則直接調(diào)用八叉樹非均勻網(wǎng)格法進(jìn)行數(shù)據(jù)精簡(jiǎn)。(2）調(diào)用八叉樹非均勻網(wǎng)格法，構(gòu)造網(wǎng)格單元，刪除空的網(wǎng)格單元，構(gòu)造出掃描線群。當(dāng)數(shù)據(jù)點(diǎn)云進(jìn)行拼接以后，建立一個(gè)可以完全包圍數(shù)據(jù)點(diǎn)云的立方體，然后根據(jù)立方體的最小邊長(zhǎng)和用戶設(shè)定的網(wǎng)格參數(shù)確定原始網(wǎng)格單元的尺寸，由于在網(wǎng)格細(xì)分中這些原始的網(wǎng)格要被分割成8個(gè)子單元，所以應(yīng)該設(shè)定合理的原始網(wǎng)格尺寸。精簡(jiǎn)的誤差增大，曲面擬合誤差相應(yīng)地也會(huì)增大。在基于八叉樹的非均勻三維網(wǎng)格方法中利用法向量和主曲率兩者的偏差作為網(wǎng)格劃分的標(biāo)準(zhǔn)，細(xì)分后的網(wǎng)格單元在x、y方向上的尺寸不同，避免了均勻網(wǎng)格法不能準(zhǔn)確確定邊界點(diǎn)的情況，但其計(jì)算的復(fù)雜程度相應(yīng)增加。網(wǎng)格細(xì)分結(jié)束的標(biāo)準(zhǔn)是網(wǎng)格內(nèi)的δ<δmax和η<ηmax或者是最終的網(wǎng)格內(nèi)僅包含1個(gè)數(shù)據(jù)點(diǎn)。用物體表面的形狀和期望的數(shù)據(jù)精簡(jiǎn)比來設(shè)定兩個(gè)標(biāo)準(zhǔn)參數(shù)：給定的最大法向矢量標(biāo)準(zhǔn)偏差δmax和最大主曲率標(biāo)準(zhǔn)偏差ηmax作為判斷值，如果一個(gè)網(wǎng)格單元中的法向矢量δ>δmax或者主曲率η>ηmax時(shí)，表示這個(gè)網(wǎng)格內(nèi)曲面的形狀變化較大，要對(duì)這個(gè)網(wǎng)格進(jìn)行細(xì)分。(3）調(diào)用角度—弦差法對(duì)每條掃描線點(diǎn)群進(jìn)行精簡(jiǎn)處理，獲得精簡(jiǎn)后的點(diǎn)云。角度弦差法先給定角度誤差限αmax和弦差限dmax，如圖2所示。同時(shí)使用這兩個(gè)誤差參數(shù)來綜合處理密集點(diǎn)云數(shù)據(jù)，將處在這兩個(gè)誤差限內(nèi)的點(diǎn)精簡(jiǎn)掉。αmax要根據(jù)精度要求在0°～15°來選取，精度要求越高，取值越??；同時(shí)也可以根據(jù)實(shí)測(cè)點(diǎn)進(jìn)行校驗(yàn)，從而選用簡(jiǎn)化效果較好的αmax值。dmax的確定則根據(jù)前述掃描線上相鄰點(diǎn)距離正態(tài)分布的μ值，精簡(jiǎn)前點(diǎn)數(shù)量Nb，預(yù)期精簡(jiǎn)點(diǎn)的數(shù)Na按下式確定：具體算法步驟如下：(1）給定出一個(gè)角度誤差限αmax并計(jì)算弦高誤差限dmax;(2）從起點(diǎn)開始取相鄰的3點(diǎn)：P1、P2、P3，計(jì)算與的夾角α，弦高；(3）若α<αmax，且d<dmax成立，則舍去P2，取P3后的一點(diǎn)P4，若P4不存在，說明該掃描線上的點(diǎn)已經(jīng)處理完畢，轉(zhuǎn)第（5）步，若P4存在則置P2=P3,P3=P4，轉(zhuǎn)第（2）步；(4）若α<αmax，且d<dmax不成立，則置P1=P2,P2=P3，取P3后一點(diǎn)P4，若P4不存在，說明該掃描線上的點(diǎn)已處理完畢，轉(zhuǎn)第（5）步，若P4存在則置P3=P4，轉(zhuǎn)第（2）步；(5）判斷是否所有掃描線均已取完，如果沒有則取下一條掃描線，轉(zhuǎn)第（2）步，若已取完則說明測(cè)量精簡(jiǎn)結(jié)束。4基于atos的算法圖3(a）為某汽車引擎蓋板點(diǎn)云，點(diǎn)云數(shù)據(jù)采集由德國(guó)GOM公司光柵式投影掃描儀ATOS完成，數(shù)據(jù)點(diǎn)數(shù)目為403218。按照本文算法精簡(jiǎn)后，得到的點(diǎn)云如圖3(b）所示，數(shù)據(jù)點(diǎn)數(shù)目精簡(jiǎn)為103887。精簡(jiǎn)率為74.2%，精簡(jiǎn)效果顯著，特征也保留完好。5非接觸法分離點(diǎn)云數(shù)據(jù)點(diǎn)云數(shù)據(jù)的精簡(jiǎn)處理是逆向工程實(shí)施過程中的關(guān)鍵步驟之一。好的算法能夠很好地提高后續(xù)工作的效率和質(zhì)量。實(shí)際應(yīng)用表明，采用角度-弦差