散亂點(diǎn)云切片數(shù)據(jù)快速獲取與優(yōu)化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

T為切片數(shù)據(jù)點(diǎn)集合,該集合中數(shù)據(jù)點(diǎn)個(gè)數(shù)為n,采用式(4)計(jì)算 T中數(shù)據(jù)點(diǎn)中心坐標(biāo) O0：

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

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

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

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

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

圖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ù)點(diǎn);2)部分輪廓出現(xiàn)迂回現(xiàn)象,即同一輪廓數(shù)據(jù)在同一扇形區(qū)域多次出現(xiàn).多輪廓切片數(shù)據(jù)優(yōu)化具體步驟如下：

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

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

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

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

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

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

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

3 算法時(shí)間復(fù)雜度分析

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

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

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

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

4 實(shí)例應(yīng)用

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

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

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

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

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

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

5 結(jié)論

本文算法和相關(guān)算法相比具有以下特點(diǎn)：

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

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

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

4)在進(jìn)行數(shù)據(jù)精簡(jiǎn)的同時(shí),完成了數(shù)據(jù)點(diǎn)之間的排序,建立了數(shù)據(jù)之間的拓?fù)溧徑P(guān)系,為參數(shù)曲線、曲面重構(gòu)奠定重要基礎(chǔ).

[1]劉云峰,柯映林.反求工程中的混合切片技術(shù)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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]柯映林,王青.反求工程中點(diǎn)云切片算法研究[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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]蓋紹彥,達(dá)飛鵬,雷明濤,等.三維重構(gòu)中的雜亂點(diǎn)云排序問題研究[J].計(jì)算機(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]龔友平,陳國(guó)金,陳立平.基于切片方法的截面數(shù)據(jù)處理[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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ù)的自動(dòng)細(xì)化算法[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版),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)格曲面模型動(dòng)態(tài)空間索引結(jié)構(gòu)研究[J].中國(guó)機(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ù)點(diǎn)云型面特征分析算法的研究與應(yīng)用[J].機(jī)械工程學(xué)報(bào),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)化技術(shù)[J].中國(guó)機(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.