邵正偉， 席 平

（北京航空航天大學機械工程及自動化學院，北京 100191）

在逆向工程中，非接觸式測量方法獲取的被測物的數(shù)據(jù)一般具有無序、海量的特點[1]。無序的特點是指每個數(shù)據(jù)點只具有三維坐標值的信息，而沒有明確的空間鄰域信息，不利于鄰域數(shù)據(jù)點的搜索，而鄰域數(shù)據(jù)點的搜索速度正是影響散亂數(shù)據(jù)處理和曲面重構效率的主要因素之一。海量的特點是指測量數(shù)據(jù)過密，這不但會影響曲面的重構速度，而且在重構曲面的曲率較小處還會影響曲面的光順性。因此，在進行曲面重構前，需要建立數(shù)據(jù)的空間鄰域關系和精簡數(shù)據(jù)。文中應用八叉樹編碼的空間鄰域劃分方法，并在此基礎上提出了一種新的點云數(shù)據(jù)均勻精簡方法。

1 點云精簡方法

近年來，人們做了很多關于數(shù)據(jù)精簡方面的研究，主要包括曲率精簡和均勻精簡兩類方法。在曲率精簡方法中，洪軍[2]先利用包圍盒法構造分割面，然后利用分割面將點云處理成掃描線結構，再利用角度、弦高聯(lián)合準則法逐線精簡；周綠[3]使用了拋物面擬合法求解局部曲率，再根據(jù)曲率偏差對點云進行精簡。在均勻精簡方法中，萬軍[4]通過以某一點定義采樣立方體，求立方體內(nèi)其余點到該點的距離，再根據(jù)平均距離和用戶指定保留點的百分比進行精簡，該方法由于沒有預先對點云數(shù)據(jù)劃分空間鄰域，在檢索采樣立方體過程中，需要對全部點云數(shù)據(jù)進行判斷，因此處理海量數(shù)據(jù)時計算量較大，且不能根據(jù)指定的點距精簡點云。

針對以上方法的不足，文中提出新的均勻精簡方法的原理是：

（1）根據(jù)指定的點距，應用八叉樹編碼法對點云進行空間鄰域劃分，把點云數(shù)據(jù)的空間包圍盒（最小外接立方體）劃分為多個指定點距d0邊長的子立方體，具體方法見2節(jié)；

（2）分別對每個子立方體進行數(shù)據(jù)精簡，如圖1所示，若在劃分后的某兩個相鄰子立方體中存在8個數(shù)據(jù)點p1～p8，保留每個子立方體中距中心點最近的點p3和p7。由于相鄰子立方體中心點的距離為d0，所以精簡后點云中p3和p7之間的距離也近似為d0。

圖1 點云子立方體

2 空間鄰域劃分

在對散亂數(shù)據(jù)進行精簡、濾波、特征提取等處理過程中，需要獲取數(shù)據(jù)點在其型面對應點處的單位法矢、微切平面及曲率值等信息，這就需要搜索數(shù)據(jù)點的k近鄰，即在數(shù)據(jù)點集中尋找k個與該點歐氏距離最近的點。一般的搜索方法就是窮舉法：計算某點與點集中其余點的歐氏距離，并按從小到大排序，選取排在前面的K個點為該點的k個最近鄰點。對于海量點數(shù)據(jù)，這種搜索方法耗時極大，因此，為點云建立良好的空間鄰域結構是提高數(shù)據(jù)點 k近鄰搜索速度的關鍵。

下面介紹一種在逆向工程中常采用的空間鄰域劃分方法——八叉樹法。

2.1 八叉樹法原理

八叉樹結構是區(qū)域四叉樹向三維空間的推廣，是通過遞歸分割點云空間的方式實現(xiàn)的。首先構造點云數(shù)據(jù)的空間包圍盒（外接立方體），并把它作為數(shù)據(jù)點云拓撲關系的根模型；再將外接立方體分割成大小相同的8個子立方體，每個子立方體均視為根節(jié)點的字節(jié)點；如此遞歸分割，直至最小子立方體的邊長等于給定的點距，將點云空間hu劃分為2的冪次方個子立方體。

在八叉樹劃分過程中，子立方體的編碼與其所在的位置有關[5]。如圖2所示，規(guī)定：在x軸上位于x中分面右側的子節(jié)點編碼均比左側相鄰節(jié)點編碼加1；在y軸上位于y中分面前側的均比后側的相鄰節(jié)點位置碼增加2；在z軸上位于z中分面上側的均比下側的相鄰節(jié)點位置碼增加4。

圖2 八叉樹空間劃分模型

對于一個正立方體包圍盒空間進行遞歸八等分，假設剖分層數(shù)為n，則八叉樹空間模型可以用n層八叉樹表示，八叉樹空間模型中的每個立方體與八叉樹中的結點一一對應，它在八叉樹空間模型中的位置可由對應結點的八叉樹編碼Q表示

其中 qm為八進制數(shù)表示該節(jié)點在其兄弟節(jié)點之間的序號，而qm+1表示qm節(jié)點的父節(jié)點在其同胞兄弟節(jié)點間的序號。這樣，從q0到qn-1完整地表示出八叉樹中的每個葉子節(jié)點到樹根的路徑。

2.2 點云數(shù)據(jù)編碼

點云數(shù)據(jù)編碼的步驟為：

（1）確定點云八叉樹剖分層數(shù)n，滿足

其中 d0為精簡的指定點距，dmax為點云包圍盒的最大邊長。

（2）確定點云數(shù)據(jù)點所在子立方體的編碼，假設數(shù)據(jù)點 P ( x , y,z )，所在子立方體的空間索引值為(i, j,k )，Q為與子立方體相對應的結點的八叉樹編碼。三者的關系可由公式(3)～(5)表示[6-8]

其中 (xmin,ymin,zmin)表示與根節(jié)點對應的包圍盒的最小頂點坐標值，[…]為取整操作符。

將索引值(i , j,k )轉換為2進制表示方式

則子立方體對應的八叉樹編碼可由公式(1)表示。同時，如果已知子立方體對應的八叉樹編碼Q，也可以反求出數(shù)據(jù)點所在子立方體的空間索引值(i , j,k )

其中 (qm%2)表示對qm除以 2所得余數(shù)，[qm/2]表示對qm除以2所得結果取整數(shù)。

在搜索數(shù)據(jù)點的k近鄰時，可在數(shù)據(jù)點所在的子立方體及其周圍相鄰的 26個子立方體中搜索。若空間某子立方體的索引值為(i , j,k )，則其周圍 26個子立方體的索引值可由(i ±δ, j ±δ,k±δ)表示，δ ∈ {0 , 1}。因此，經(jīng)過八叉樹劃分后的點云，只需要在局部進行k近鄰搜索，明顯提高了搜索速度。

3 應用實例

基于八叉樹編碼的均勻精簡算法的流程如圖3所示，在UG軟件平臺上使用C++語言二次開發(fā)了點云數(shù)據(jù)的預處理模塊，如圖4所示。并針對渦輪葉片模具的測量數(shù)據(jù)進行精簡，圖5所示為初始測量點云，包含數(shù)據(jù)點24500個，圖6所示為指定精簡距離為 2mm的精簡后點云，包含數(shù)據(jù)點 4607個，精簡后的點云在空間分布均勻，適合數(shù)據(jù)的后續(xù)處理。

圖3 算法流程圖

圖4 點云數(shù)據(jù)的預處理模塊

圖5 初始測量點云

圖6 精簡后點云

4 結 論

本文提出的點云精簡算法能對逆向工程測量的海量數(shù)據(jù)做出快速有效的精簡，算法具有以下特點：

（1）從空間整體角度考慮點云的均勻精簡，精簡效果較好；

（2）由于精簡前對點云進行了空間劃分，因此算法簡潔、高效；

（3）用戶通過設定精簡點距，可以靈活實現(xiàn)點云精簡。

[1]孫肖霞, 孫殿柱, 李延瑞, 等. 反求工程中測量數(shù)據(jù)的精簡算法[J]. 機械設計與制造, 2006, (8): 37-38.

[2]洪 軍, 丁玉成, 曹 亮, 等. 逆向工程中的測量數(shù)據(jù)精簡技術研究[J]. 西安交通大學學報, 2004, 38(7):661-664.

[3]周 綠, 林 亨, 鐘躍先, 等. 曲面重構中測量點云精簡方法的研究[J]. 中國制造業(yè)信息化, 2004, 33(5):102-104.

[4]萬 軍, 鞠魯粵. 逆向工程中數(shù)據(jù)點云精簡方法研究[J]. 上海大學學報, 2004, 10(1): 26-29.

[5]張傳明, 潘 懋, 徐繪宏. 基于分塊混合八叉樹編碼的海量體視化研究[J]. 計算機工程, 2007, 33(14):33-35.

[6]范 茵, 汪德宗. 八叉樹編碼的三維物體截面之比計算[J]. 數(shù)據(jù)采集與處理, 1999, 14(1): 47-51.

[7]趙 強. 基于BSP樹的點云精簡方法研究[D]. 西安:西北工業(yè)大學, 2007.

[8]孫肖霞. 基于UGII的反求工程數(shù)據(jù)處理技術研究與系統(tǒng)開發(fā)[D]. 淄博: 山東理工大學, 2006.