基于局部型面特征的散點云數(shù)據(jù)獲取

基于局部型面特征的散點云數(shù)據(jù)獲取

0局部型面高效確定在3d工程中，基于云的特性幾何特征來簡化分散的云，可以減少云的冗余，提高網(wǎng)格結(jié)構(gòu)等幾何計算的處理效率。Chen等對點云數(shù)據(jù)進行三角網(wǎng)格化,計算三角面片的法向量,并估算三角面片所在位置的曲率,依據(jù)該曲率精簡點云數(shù)據(jù),該算法可實現(xiàn)散亂點云的非均勻精簡,但需耗費大量的系統(tǒng)資源,運行效率低。洪軍等采用包圍盒和角度-弦高法精簡點云數(shù)據(jù),該方法不能準確計算點云的曲率分布,且只適用于掃描線型點云。周綠等采用拋物面擬合法求解局部曲率,根據(jù)曲率分布精簡點云,該方法可準確估算點云曲率分布狀況,但在獲取點云局部型面參考數(shù)據(jù)時需對點云進行三角剖分,運算量大,算法運行效率低。針對上述問題,本文基于文獻提出的曲率估算方法分析點云型面特征,依據(jù)型面特征,通過調(diào)整局部點集空間范圍及曲率標準差對點云進行精簡。此外,針對文獻索引結(jié)構(gòu)不能有效索引維數(shù)退化的點云數(shù)據(jù)及節(jié)點聚類效率低等問題,改進R*-tree索引結(jié)構(gòu),將數(shù)據(jù)點及索引節(jié)點的最小綁定矩形(minimumboundingrectangle,MBR)統(tǒng)一表示為四維點對象,結(jié)合k-means算法對R*-tree進行節(jié)點分裂,建立點云動態(tài)空間索引結(jié)構(gòu),實現(xiàn)局部型面參考數(shù)據(jù)的快速獲取。該算法可在保留點云型面特征的基礎(chǔ)上,快速有效地對點云進行精簡。1點云動態(tài)域的構(gòu)建通過改進R*-tree建立散亂點云動態(tài)空間索引結(jié)構(gòu),實現(xiàn)點云的動態(tài)維護及局部型面參考數(shù)據(jù)的快速獲取。1.1局部點集平行,影響節(jié)點mbr文獻采用R*-tree建立點云動態(tài)空間索引結(jié)構(gòu),該結(jié)構(gòu)的節(jié)點插入算法基于MBR體積增量,應用于散亂點云的空間聚類分簇時,若點云中的局部點集平行于坐標平面分布,則節(jié)點MBR將由三維退化為二維,導致R*-tree節(jié)點插入失效,破壞了R*-tree節(jié)點的聚合性。為解決該問題,將數(shù)據(jù)點及葉節(jié)點的MBR統(tǒng)一表示為四維點對象(x,y,z,r),其中(x,y,z)為MBR中心坐標,r為MBR的外接球半徑。1.2聚類分簇中心坐標采用k-means算法實現(xiàn)散亂點云的空間聚類分簇。將任意一對節(jié)點的MBR中心作為初始分簇中心,形成兩個初始分簇,將數(shù)據(jù)點添加到與分簇中心最近的初始分簇中。為使節(jié)點MBR均勻,根據(jù)R*-tree定義,當分裂所得某一簇節(jié)點的子節(jié)點數(shù)k小于R*-tree最小子節(jié)點數(shù)m時,將另一簇中距離當前簇較近的m-k個節(jié)點插入到當前簇中,并調(diào)整分簇結(jié)果。采用k-means算法對R*-tree葉節(jié)點進行聚類分簇時,需要迭代定位最終的分簇中心。對于同簇節(jié)點中的N個葉節(jié)點,其四維標準化坐標pi=(xi,yi,zi,ri),i=1,2,…,N,分簇中心坐標(ˉx,ˉy,ˉz,ˉr)(xˉ,yˉ,zˉ,rˉ)計算公式為ˉx=Ν∑i=1xiri/Ν∑i=1riˉy=Ν∑i=1yiri/Ν∑i=1riˉz=Ν∑i=1ziri/Ν∑i=1riˉr=Ν∑i=1ri/Ν}(1)xˉ=∑i=1Nxiri/∑i=1Nriyˉ=∑i=1Nyiri/∑i=1Nrizˉ=∑i=1Nziri/∑i=1Nrirˉ=∑i=1Nri/N???????????????????????????????????????(1)各葉節(jié)點至聚類分簇中心的距離為d=√(xi-ˉx)2+(yi-ˉy)2+(zi-ˉz)2+(ri-ˉr)2(2)d=(xi?xˉ)2+(yi?yˉ)2+(zi?zˉ)2+(ri?rˉ)2??????????????????????????????????√(2)該索引結(jié)構(gòu)由3種節(jié)點組成,最上層的節(jié)點為根節(jié)點,最底層的節(jié)點為葉節(jié)點,其余的節(jié)點為內(nèi)部節(jié)點,內(nèi)部節(jié)點可以由多層節(jié)點構(gòu)成。除根節(jié)點外,每個節(jié)點的子節(jié)點數(shù)n滿足m≤n≤M,其中,m、M分別為節(jié)點的最小子節(jié)點數(shù)和最大子節(jié)點數(shù),通常取8和20。基于四維點表示的散亂點云動態(tài)空間索引結(jié)構(gòu)如圖1所示。2云的局部表面附近2.1局部型面參考點集的生成采用R*-tree的k近鄰查詢算法獲取點云任意點P的k近鄰點Nj(j=0,1,…,k-1),將其與點P組成局部型面參考點集X,逼近生成該點集的微切平面。2.2局部坐標系如圖2所示,設(shè)局部型面參考點集X在微切平面上的投影為X′={P′i|i=0,1,…,k},以點P的投影點P′為原點,以P′與X′中距其最遠的點所構(gòu)成的向量作為u軸,以微切平面的法向軸為w軸,由右手規(guī)則確定v軸,建立局部坐標系C。然后將X′變換到坐標系C下得點集X″={(ui,vi)|i=0,1,…,k}。2.3求點集x的mbr+v向邊邊分別對X″中數(shù)據(jù)點的u坐標和v坐標遞增排序,可得兩個坐標分量序列UC={uci|i=0,1,…,k}和VC={vci|i=0,1,…,k}。在坐標系C下,求點集X″的MBR及其u向邊長lu和v向邊長lv。點集X″中任意數(shù)據(jù)點(ui,vi)的參數(shù)為u′i=(ui-uc0)/luv′i=(vi-vc0)/lv}(3)u′i=(ui?uc0)/luv′i=(vi?vc0)/lv}(3)2.4解析正演矩陣采用n×m階的Bézier曲面逼近點云的局部型面。設(shè)qt∈X,其四維化坐標qt=(xt,yt,zt,rt),t=0,1,…,k,則Bézier曲面可表示為S(ui,yi)=n∑i=0m∑j=0Bi,n(ut)Bj,m(vt)pi,j=qt(4)S(ui,yi)=∑i=0n∑j=0mBi,n(ut)Bj,m(vt)pi,j=qt(4)式中,pi,j為待求Bézier曲面的控制點。設(shè)Di,j(u,v)=Bi,n(u)Bj,m(v)i=0,1,…,n;j=0,1,…,m將式(4)寫為式(5)所示的矩陣形式:D[p1p2…pn]T=[q0q1…qk]T(5)pi=[pi,1pi,2…pi,m]TD=[D0(u0,v0)D1(u0,v0)?Dn(u0,v0)D0(u1,v1)D1(u1,v1)?Dn(u1,v1)???D0(uk,vk)D1(uk,vk)?Dn(uk,vk)]D=???????D0(u0,v0)D0(u1,v1)?D0(uk,vk)D1(u0,v0)D1(u1,v1)?D1(uk,vk)???Dn(u0,v0)Dn(u1,v1)?Dn(uk,vk)???????(6)Ds(ui,vi)=[Ds,0(ui,vi)Ds,1(ui,vi)…Ds,m(ui,vi)]s=0,1,…,n系數(shù)矩陣D的奇異值分解為D=UWVT(7)式中,U為(k+1)×[(m+1)(n+1)]階的列正交矩陣;W為[(m+1)(n+1)]×[(m+1)(n+1)]階半正定對角陣;V為[(m+1)(n+1)]×[(m+1)(n+1)]階正交矩陣。最小二乘Bézier曲面控制點為[p1p2…pn]T=VW-1U-1[q0q1…qk]T(8)3張量積be能er曲面的兩極化反應點云中各點及其近鄰點所構(gòu)成的點集均能以Bézier曲面逼近。遍歷點云數(shù)據(jù),對當前點和其近鄰點所構(gòu)成的點集逼近生成Bézier曲面,由于當前點的參數(shù)值是已知的,可以由下式計算出逼近曲面上對應參數(shù)位置的曲率:c=(Suu?n)(Svv?n)-(Suv?n)2(Su?Su)(Sv?Sv)-(Su?Sv)2(9)c=(Suu?n)(Svv?n)?(Suv?n)2(Su?Su)(Sv?Sv)?(Su?Sv)2(9)n=Su×Sv|Su×Sv|(10)n=Su×Sv|Su×Sv|(10)式中,Su、Sv分別為n×m的張量積Bézier曲面的一階偏導;Suu、Svv、Suv分別為張量積Bézier曲面在u向、v向和uv向的二階偏導。以c作為當前點曲率值的估計。4基于型面特征的疏散點云精制算法采用R*-tree空間查詢算法,查找與點P的距離小于r的數(shù)據(jù)點集Y,該點集的曲率標準差σ為σ=√k∑i=0(ci-ˉc)2/k(11)ˉc=k∑i=0ci/(k+1)(12)曲率標準差越大說明其型面越陡峭,否則越平坦。為保留點云型面細節(jié)特征,在曲率標準差較大區(qū)域?qū)適當調(diào)小,刪除距離點P小于r的點,實現(xiàn)點云的非均勻精簡?；谛兔嫣卣鞯纳y點云精簡算法流程如圖3所示。實際應用中根據(jù)點云的疏密程度確定r,令隨機兩點間的距離為r0,通常r取3r0～4r0時可較好保留點云的型面特征,根據(jù)型面特征的復雜度確定σ0,一般σ0取0.0001時可較好保留點云的型面特征。5點云精制算法制定三組實驗方案驗證本文算法的有效性,測試環(huán)境為:聯(lián)想啟天2800臺式計算機(處理器為IntelPⅣ2.4GHz,內(nèi)存256MB),操作系統(tǒng)GNU/Linux。方案一分別采用Bézier曲面及拋物面逼近圖4所示點云的局部點集,計算點集到兩逼近曲面的距離。點到Bézier曲面的最大距離是12.0μm,平均距離是4.2μm;點到拋物面的最大距離是46.5μm,平均距離是32.5μm。采用Bézier曲面可更準確地擬合點集曲面,基于該曲面可更準確地計算點集曲率。方案二采用文獻算法及本算法對米老鼠點云進行精簡。圖4a為米老鼠原始點云,點數(shù)為20631;圖4b為采用文獻算法對米老鼠點云精簡后的結(jié)果,點云點數(shù)為5430;圖4c為采用本文算法在r=1mm、σ=0.005時的精簡結(jié)果,點云點數(shù)為5235。從圖4c中可以看出,本文算法在曲率較大區(qū)域保留了較多點,在曲率較小區(qū)域保留了較少點,更好地保留了點云的型面特征,顯著減小了點云冗余度。文獻算法和本文算法對米老鼠點云精簡所耗時間分別為3.683s和0.672s。方案三采用本文精簡算法,通過調(diào)節(jié)r與σ的取值(表1)對維納斯點云進行精簡,結(jié)果分別如圖5b～圖5d所示。結(jié)合圖5及表1分析可知,r越大,