孫永偉,孫殿柱,朱昌志,朱宗偉

(山東理工大學 機械工程學院,山東 淄博 255091)

隨著三維數(shù)字化激光掃描技術的發(fā)展,逆向工程中處理的點云數(shù)據(jù)通常具有海量規(guī)模,且存在大量冗余信息,采用切片技術可在準確反映產(chǎn)品型面特征的同時,有效提高參數(shù)曲線、曲面的重構(gòu)效率.目前通常將點云數(shù)據(jù)向距離最近的切片投影,獲取投影數(shù)據(jù)作為切片數(shù)據(jù).文獻[1-2]通過對點云進行隨機采樣計算點云密度,由該密度確定切片位置.由于采樣點的選取具有很大隨機性,所得數(shù)據(jù)不能有效反映點云的型面特征,且采用 Christofides算法進行排序,時間復雜度達到 O(n4),算法運行效率低.文獻[3-5]基于過點云兩極值點的直線將切片數(shù)據(jù)分為兩部分,根據(jù)點在直線上的投影對兩部分數(shù)據(jù)分別排序,然后合并,得到有序的切片數(shù)據(jù)序列,并采用角偏差法和弦高差法對排序后的數(shù)據(jù)進行精簡,該算法可克服文獻[1-2]算法在點云數(shù)據(jù)處理方面效率低的問題,但只適用于沒有重復投影點的切片點云,不能有效處理具有多重輪廓的復雜散亂點云數(shù)據(jù).針對上述問題,本文采用 R*S樹建立散亂點云動態(tài)索引,基于該索引快速獲取切片位置與切片鄰域數(shù)據(jù),將切片鄰域數(shù)據(jù)向切片投影獲取切片數(shù)據(jù),并為切片數(shù)據(jù)建立極坐標系.分別基于極角閾值與極徑閾值實現(xiàn)切片數(shù)據(jù)區(qū)域劃分與輪廓分離,通過依次連接各區(qū)域相同輪廓數(shù)據(jù)形心,獲取精確有序的單輪廓或多輪廓切片數(shù)據(jù).

1 切片數(shù)據(jù)獲取

在切片數(shù)據(jù)獲取過程中,可采用 R*S樹[6-8]為散亂點云數(shù)據(jù)建立動態(tài)索引,以實現(xiàn)數(shù)據(jù)點的快速定位與準確查詢,從而提高切片數(shù)據(jù)獲取效率.例如對圖1所示的散亂點云構(gòu)建 R*S樹動態(tài)索引,各層結(jié)點 MBR如圖2所示,該結(jié)構(gòu)由 3種結(jié)點組成,最上層為根結(jié)點,最底層為葉結(jié)點,其余為內(nèi)部結(jié)點.除根結(jié)點外,每個結(jié)點的子結(jié)點數(shù) n滿足m≤n≤M,其中 m和 M分別為結(jié)點的最小、最大子結(jié)點數(shù),通?？扇?8和 20.

圖1 點云數(shù)據(jù)Fig.1 Points data

圖2 散亂點云的動態(tài)空間索引結(jié)構(gòu)Fig.2 Spatial index structure of scattered points

基于散亂點云動態(tài)索引,采用深度優(yōu)先遍歷算法獲取與切片相交的葉結(jié)點,依據(jù)葉結(jié)點與切片的位置關系確定下層切片的位置,并將葉結(jié)點包含的數(shù)據(jù)作為切片鄰域數(shù)據(jù),將鄰域數(shù)據(jù)向切片投影獲取切片數(shù)據(jù).

假設切片平行于 xoy平面,法矢 n指向 z軸正方向.獲取點云在 z軸上的最小值 zmin和最大值 zmax采用式(1)計算初始切片位置：

采用式(2)計算其余各層切片位置：

其中,εj為與切片相交的葉結(jié)點中各頂點到切片的距離,可由式(3)計算,n為與第 i層切片相交的各葉結(jié)點中位于切片正側(cè)(即 εj＞0)的葉結(jié)點頂點數(shù)：

式中：v為與切片相交的葉結(jié)點 MBR的頂點.

切片位置確定后,令 V={vj|j=1,2,…,8}為葉結(jié)點 MBR的頂點集合,q為切片內(nèi)的任意一點,根據(jù)式(3)判斷葉結(jié)點與切片的位置關系,若 εj≤0,表示 vj位于切片的負側(cè),若 εj＞0,表示 vj位于切片的正側(cè).若索引結(jié)點 8個頂點的 εj同時為正(或負),表示結(jié)點與切片相離,否則相交.

基于上述原則,采用深度優(yōu)先遍歷方法,獲取與切片相交的葉結(jié)點,將其包含的數(shù)據(jù)點作為該切片鄰域數(shù)據(jù),如圖3所示,具體步驟如下：

1)輸入 R*S樹根結(jié)點;

2)若輸入結(jié)點為葉結(jié)點,判斷該結(jié)點與切片的位置關系,獲取切片鄰域數(shù)據(jù);

3)若結(jié)點為根結(jié)點或內(nèi)部結(jié)點,則循環(huán)獲取當前結(jié)點的子結(jié)點,返回 2).

圖3 切片鄰域數(shù)據(jù)Fig.3 Slice neighborhood data

將獲取的切片鄰域數(shù)據(jù)向切片投影得到切片數(shù)據(jù),如圖4所示,將切片數(shù)據(jù)存儲到序列 T={pi|i=0,1,2,…,n-1}中,n為 T中數(shù)據(jù)點的個數(shù),pi=(xi,yi,zi).

圖4 切片鄰域數(shù)據(jù)投影點Fig.4 Projection points of slice neighborhood data

2 切片數(shù)據(jù)優(yōu)化

投影法獲取的切片數(shù)據(jù)為具有一定寬度的點云帶,存在大量冗余數(shù)據(jù),且切片數(shù)據(jù)之間沒有明顯的拓撲鄰近關系,在保留截面特征數(shù)據(jù)點的同時對其進行精簡與排序,實現(xiàn)切片數(shù)據(jù)的優(yōu)化,以適用于參數(shù)曲線與曲面重構(gòu)[9].

為實現(xiàn)切片數(shù)據(jù)精簡,可將切片數(shù)據(jù)點轉(zhuǎn)換至極坐標系下并將其劃分為多個區(qū)域,對每個較小區(qū)域分別進行輪廓分離及特征數(shù)據(jù)提取,在保證數(shù)據(jù)信息完整性的同時實現(xiàn)切片數(shù)據(jù)的精簡,然后依次連接各區(qū)域相同輪廓特征數(shù)據(jù),得到精確有序的切片數(shù)據(jù)點序列.

T為切片數(shù)據(jù)點集合,該集合中數(shù)據(jù)點個數(shù)為n,采用式(4)計算 T中數(shù)據(jù)點中心坐標 O0：

如圖5所示,以 O0為極坐標原點,以 O0為起點作一條平行于 X軸的射線,作為極軸,建立切片數(shù)據(jù)極坐標系,獲取切片數(shù)據(jù)點極徑 r及極角 θ.

圖5 切片數(shù)據(jù)的極坐標表示Fig.5 Polar of slicing data

根據(jù)散亂點云輪廓特征,所獲取的切片數(shù)據(jù)可分為單輪廓與多輪廓切片數(shù)據(jù),如圖6所示,下面針對這 2種切片數(shù)據(jù)類型分別進行精簡與排序處理.

2.1 單輪廓切片數(shù)據(jù)優(yōu)化

對于單輪廓切片數(shù)據(jù),輪廓形狀較為簡單,可對其進行極角區(qū)域劃分處理,即基于切片數(shù)據(jù)極角,將切片數(shù)據(jù)劃分為多個扇形區(qū)域.如圖7所示,每個扇形區(qū)域的極角步長為 ρ,采用式(4)計算各區(qū)域切片數(shù)據(jù)形心,將其作為切片數(shù)據(jù)特征點,依次連接各區(qū)域特征點,所得序列即為優(yōu)化后的切片數(shù)據(jù)點序列.

圖7 切片數(shù)據(jù)區(qū)域劃分Fig.7 Zoning of slicing data

2.2 多輪廓切片數(shù)據(jù)優(yōu)化

多輪廓切片數(shù)據(jù)體現(xiàn)為：1)同一扇形區(qū)域內(nèi)具有不同輪廓上的數(shù)據(jù)點;2)部分輪廓出現(xiàn)迂回現(xiàn)象,即同一輪廓數(shù)據(jù)在同一扇形區(qū)域多次出現(xiàn).多輪廓切片數(shù)據(jù)優(yōu)化具體步驟如下：

1)基于切片數(shù)據(jù)極角將切片數(shù)據(jù)劃分為多個扇形區(qū)域,依次對各扇形區(qū)域數(shù)據(jù)進行如下操作：令該扇形區(qū)域數(shù)據(jù)集合為 S,任取 S中數(shù)據(jù)點 P,其極徑為 rP,將 P加入臨時序列 V,依次令 S中其他數(shù)據(jù)點為 P′,極徑為 rP′,取極徑閾值為 μ,若 |rP′-rP|＜μ,則將 P′加入序列 V,采用式(4)計算 V中數(shù)據(jù)形心,將 C加入集合 U.若 S=V,則返回,否則,令 S=S-V,置空集合 V,繼續(xù)執(zhí)行上述步驟.

2)取 U中任一數(shù)據(jù)點 C,其極徑為 rC,將其添加到序列 M,C所在區(qū)域為 S.

3)依次令 S下一區(qū)域(取極角增大的方向為正方向)內(nèi)形心點為 P,極徑為 rP,若 |rC-rP|＜μ,執(zhí)行 4),若不存在滿足上述條件的形心點,說明該輪廓數(shù)據(jù)已經(jīng)全部分離或者發(fā)生迂回,執(zhí)行 5).

4)將 P加入序列 M中,令 P所在區(qū)域為 S,P為 C,rC=rP返回 3).

5)依次令 S上一區(qū)域內(nèi)形心點為 P,極徑為 rP,若 |rC=rP|＜μ,則將 P加入序列 M中,令 P所在區(qū)域為 S,P為 C,rC=rP,迭代執(zhí)行該步驟.

6)若 U=M,程序結(jié)束,否則,令 Mi=M(i初值為 0),i=i+1,U=U-M,返回 2).

上述步驟基于極徑閾值實現(xiàn)切片數(shù)據(jù)輪廓分離,以區(qū)域形心點作為數(shù)據(jù)特征點,并依次連接,實現(xiàn)切片數(shù)據(jù)的精簡與排序,所得序列 Mi及 M中數(shù)據(jù)即為精確有序的切片數(shù)據(jù)點序列,可直接用于后續(xù)的曲線與曲面擬合.

3 算法時間復雜度分析

設散亂點云中數(shù)據(jù)點數(shù)為 n,本文算法時間復雜度分析如下：

1)設 R*S樹動態(tài)索引各結(jié)點單元中最大子結(jié)點數(shù)為 M,樹的層數(shù),則建立散亂點云動態(tài)索引的時間復雜度為

2)基于散亂點云動態(tài)索引獲取切片數(shù)據(jù)的過程分為 3步：切片位置的確定、切片鄰域數(shù)據(jù)的獲取及切片數(shù)據(jù)的計算,設切片層數(shù)為 k,獲取切片數(shù)據(jù)的時間復雜度為 k(M+M2+… +ML-2)+8ML-2+

3)設切片數(shù)據(jù)的個數(shù)為 N,采用坐標法劃分出的區(qū)域數(shù)為 k,則單層切片數(shù)據(jù)精簡與排序的時間復雜度是其中 ni為第 i個扇形區(qū)域中數(shù)據(jù)點個數(shù).

4 實例應用

采用本文算法和文獻[4]算法對圖6(a)所示切片數(shù)據(jù)進行處理,效果如圖8所示,切片時間分別為：0.263和 0.351;表1、2分別為本文算法和文獻[4]對切片數(shù)據(jù)處理后的誤差分析計算結(jié)果,本文算法與文獻[4]相比,絕對誤差、負向偏差及正向偏差分別減少 55%、37%和 54%.由圖8及表1、2可知本文算法處理后的切片數(shù)據(jù)分布比較均勻,可更為有效的用于曲線、曲面擬合.

圖8 兩種算法切片數(shù)據(jù)處理效果Fig.8 Slice data processing of two algorithms

表1 本文算法切片數(shù)據(jù)誤差分析計算結(jié)果Table 1 Error analysis of slicing data of this article

表2 文獻[4]算法切片數(shù)據(jù)誤差分析計算結(jié)果Table 2 Error analysis of slicing data of article 4

采用本文算法對圖6(c)所示點云模型進行切片處理,切片位置分布如圖9(a)所示,對切片數(shù)據(jù)進行精簡與排序,得到的數(shù)據(jù)點序列如圖9(b)所示,采用最小二乘法擬合為 B樣條曲線,效果如圖9(c)所示.由圖可以看出,本文算法可有效處理復雜型面的散亂點云數(shù)據(jù),處理后的數(shù)據(jù)可以有效表達模型型面特征.文獻[4]以切片數(shù)據(jù)在直線上投影點的坐標值進行排序,不能有效處理此類多輪廓切片數(shù)據(jù).

圖9 本文算法切片數(shù)據(jù)處理效果Fig.9 Slice data processing of this article

5 結(jié)論

本文算法和相關算法相比具有以下特點：

1)采用 R*S樹建立散亂點云動態(tài)索引,基于該結(jié)構(gòu)快速獲取切片數(shù)據(jù),有效提高了切片數(shù)據(jù)獲取效率;

2)通過極角區(qū)域劃分獲取區(qū)域形心點,并以形心點作為切片數(shù)據(jù)特征點,有效濾除了大量冗余數(shù)據(jù),提高了切片數(shù)據(jù)精度;

3)基于距離閾值對不同輪廓切片數(shù)據(jù)進行分離,可有效處理各種多輪廓切片數(shù)據(jù)點云,數(shù)據(jù)適應性強;

4)在進行數(shù)據(jù)精簡的同時,完成了數(shù)據(jù)點之間的排序,建立了數(shù)據(jù)之間的拓撲鄰近關系,為參數(shù)曲線、曲面重構(gòu)奠定重要基礎.

[1]劉云峰,柯映林.反求工程中的混合切片技術[J].計算機輔助設計與圖形學學報,2003,15(3)：741-745.LIU Yunfeng,KE Yingli.Hybrid slicing technology in reverse engineering[J].Journal of Computer Aided Design＆Computer Graphics,2003,15(3)：741-745.

[2]柯映林,王青.反求工程中點云切片算法研究[J].計算機輔助設計與圖形學學報,2005,17(8)：1798-1802.KE Yinglin,WANG Qing.Research on point cloud slicing technique in reverse engineering[J].Journal of Computer Aided Design＆ Computer Graphics,2005,17(8)：1798-1802.

[3]蓋紹彥,達飛鵬,雷明濤,等.三維重構(gòu)中的雜亂點云排序問題研究[J].計算機與現(xiàn)代化,2003,98(10)：33-35.GAIShaoyan,DA Feipeng,LEIMingtao,et al.Research on sortingmethod of 3-D reconstruction of unorganized point-clouds[J].Computer and Modernization,2003,98(10)：33-35.

[4]龔友平,陳國金,陳立平.基于切片方法的截面數(shù)據(jù)處理[J].計算機輔助設計與圖形學學報,2008,20(3)：321-325.GONG Youping,CHEN Guojin,CHEN Liping.Point data processing based on slicing method[J].Journal of Computer-Aided Design＆Computer Graphics,2008,20(3)：321-325.

[5]龔友平,金濤,童水光.截面切片數(shù)據(jù)的自動細化算法[J].浙江大學學報(工學版),2008,42(2)：337-340.GONG Youping,JIN Tao,TONG Shuiguang.Auto-thinning method for slice pointdata[J].Journal of Zhejiang University(Engineering Science),2008,42(2)：337-340.

[6]孫殿柱,劉健,李延瑞,等.三角網(wǎng)格曲面模型動態(tài)空間索引結(jié)構(gòu)研究[J].中國機械工程,2009,23(13)：1542-1545.SUN Dianzhu,LIU Jian,LI Yanrui,et al.Research on dynamic spatial indexing structure of triangu lar mesh surface model[J].Chinese Journal of Mechanical Engineering,2009,23(13)：1542-1545.

[7]孫殿柱,范志先,李延瑞,等.散亂數(shù)據(jù)點云型面特征分析算法的研究與應用[J].機械工程學報,2007,43(6)：133-136.SUN Dianzhu,FAN Zhixian,LIYanrui,et al.Research and application of surface feature analysis for scatter data points[J].Chinese Journal of Mechanical Engineering,2007,43(6)：133-136.

[8]ZHU Qing,GONG Jun,ZHANG Yeting.An efficient 3-D R-tree spatial indexmethod for virtual geographic environments[J].ISPRS Journal of Photogrammetry and Remote Sensing,2007,62(3)：217-224.

[9]劉云峰,柯映林.反求工程中切片數(shù)據(jù)處理及斷面特征曲線全局優(yōu)化技術[J].中國機械工程,2006,42(3)：124-129.LIUYunfeng,KEYinglin.Slicing data processingand global optimization of feature curve in reverseengineering[J].Chinese Journal of Mechanical Engineering,2006,42(3)：124-129.