基于橢球面投影的散亂點云建立三角格網方法

鄭德華,龐逸群,曹 操

(河海大學 土木工程學院,江蘇 南京 210098)

基于橢球面投影的散亂點云建立三角格網方法

鄭德華,龐逸群,曹 操

(河海大學 土木工程學院,江蘇 南京 210098)

空間點云數據建立三角格網是三維激光掃描數據處理中重要的處理內容之一。已有的點云三角格網建立方法的網形結構良好,但存在數據量大、計算效率低的特點。提出借助橢球面進行高斯投影建立點云的空間三角格網建立方法,有效地實現四周型點云數據格網建立過程。結合某礦井點云數據實例,對基于圓柱面和橢球面投影的兩種方法建立的三角格網進行對比,結果表明,利用橢球面投影法建立三角格網能更有效地建立頂部和底部點云數據的拓撲關系。

散亂點云;三角格網;橢球面投影;高斯投影

三維激光掃描目前已廣泛應用于計算機可視化、人工智能以及逆向工程等方面,三角格網貫穿于三維激光點云數據處理的整個過程。S-M Hur等人研究了基于Delaunay三角化過程中實現點云數據的縮減[1],1997年Chen Liang-Chia和 Grier CI L IN提出了將構建的三角格網進行最小二乘自由曲面模型的重建[3]。三角格網的建立在點云數據處理中具有十分重要的作用,研究合適的三角格網建立方法是建立復雜物體模型的一項重要內容。目前許多文獻對此都進行了大量的研究,發現直接在三維空間中利用點與點之間的關系構建三角格網,當點云數據量較大時,構網非常耗時,計算效率低下,且在點密度不均勻或存在噪聲的情況下,難以判斷點對之間的真正鄰接關系。作者提出了利用圓柱面坐標系在可保證點云中各點之間的相對關系不變的前提下,將三維點坐標轉換成可以用來生成平面三角格網的二維坐標[7],實現四周形點云數據的格網構建;張帆等提出了利用球面投影對單站地面激光掃描點云的構網方法[8],但對于多站三維激光掃描數據其適用性仍有待探討。本文將三維點云數據分別采用圓柱面坐標系統和橢球面坐標系統投影至二維平面上,然后利用平面上的坐標計算Delaunay三角形方法建立三維物體表面格網模型,有效地建立了具有頂部和底部點云數據的拓撲關系。

1 橢球面投影法

1.1 橢球面坐標系統

橢球面坐標系[9]是在三維直角坐標系統中定義一個長、短半軸分別為a、b的橢圓繞其短軸旋轉而形成的橢球基準面,橢球面的中心為右手系的原點O(見圖1)。若橢球面坐標系中包含一點P,則在橢球面上一定存在一點P′,P′為P點相對于橢球中心O在橢球面上的投影。圖1中B表示P′點在橢球面上的法線與xoy平面的夾角;L表示PP′連線在xoy平面上的投影與ox軸的夾角。

圖1 橢球面坐標系

在計算過程中,ti前一次迭代值,第一次迭代令

ti=t0。將點云中的點坐標(X,Y,Z)和自定義的橢球的長、短半軸a、b分別代入式(1)、(2)中,計算點在橢球面坐標系統中的坐標(B,L)。

1.2 平面坐標計算

1.2.1 高斯投影坐標計算公式

在高斯投影中,將大地坐標(B,L)轉化成高斯平面直角坐標系下的坐標采用以下公式計算:

1.2.2 平面坐標計算

利用自定義的橢球長、短半軸a、b和橢球坐標系坐標(B,L)直接代入X、l、N、t、η的計算公式,將計算結果代入式(4)即可計算出三維空間點利用橢球面投影后的平面坐標(x,y)。

由高斯投影原理可知,按某一度數劃分投影帶后,不同帶的點通過高斯投影坐標正算公式獲得的平面坐標位于不同的平面直角坐標系中,因此無法保持點與點之間原有的相對位置關系,通過式(5)可將計算獲得的平面點歸化到同一坐標系中。

式中:x、y為歸化前的坐標,x1、y1為歸化后的坐標,a為橢球長半軸,n為分帶度數。

2 基于橢球面投影的空間三角格網建立方法

2.1 三角格網建立的基本思路

利用面投影將點云中的所有點投影到二維平面后,空間三角格網的建立則轉化到二維平面上進行。建立三角格網的原則為由鄰近的散亂點組成三角格網時,應盡可能地確保每個三角形三邊長度接近相等,避免出現過大鈍角和過小鈍角的三角形。建立三角格網時,首先建立一個核心三角形,由此三角形的三個邊向外圍建立擴展三角形,建立方法是根據已構三角形的邊與外圍一點構成三角形的外接圓半徑最小建立擴展三角形,然后由原三角形的三個頂點和新搜索的點構成四邊形,若構成凸四邊形則根據連接四邊形對角線短邊來重構兩個三角形以達到優化三角形形狀的目的,若構成凹四邊形則不需進行三角形形狀連接優化。

2.2 三角格網實現方法

根據上述思想,采用數據庫設計方法實現三維空間建立點的三角格網算法。首先在Access數據庫中建立一個數據表格,即原始點云三維坐標point表,在程序中定義了5個向量類模板 vector的變量:ThreeVertex,Twow Vertex,Twoww Vertex, LaterList,TriangleList。XCoor、Ycoor、Zcoor和Intens四個元素分別表示三維激光掃描點的三維坐標和點的反射強度,m_index、X、Y、Z4個元素分別存儲投影前的三維點云坐標的順序點號和對應點的三維坐標,m_pindex、x、y元素分別存儲投影后的二維點云數據的順序點號和對應點的二維坐標, num元素表示在進行擴展三角形時,從 Twow Vertex中選取的滿足條件的點的點號,m_Tindex、m_ point1、m_point2、m_point3四個元素分別用于存儲三角形的序號和相應的三角形三個頂點的序號,m_ Lindex元素用于存儲邊的序號,m_point1、m_ point2分別存儲邊的起點和終點,m_LatDist存儲邊的長度,m_Old Tri、m_New Tri分別用于存儲原三角形和擴展三角形的序號,m_Old Trip t、m_New TriPt分別用于存儲原三角形第三個頂點和擴展三角形第三個頂點的序號,m_CroDist用于存儲Old TriPt和New TriPt兩點的距離。

根據建立的數據結構,利用橢球面投影法實現三維激光掃描點云的空間三角格網建立的步驟:

1)坐標投影轉換。首先,將point表中的點坐標依次存入向量 ThreeVertex中,m_index元素值從1開始依次累加1,表示點的序號;然后,將每個點的三維坐標經過上述的橢球面投影轉換變為二維平面坐標,存儲到向量 Twow Vertex中,其元素m_ pindex的值與向量 ThreeVertex中相對應的點的元素m_index的值一致。

2)構建核心三角形。選取 Twow Vertex向量中的第一個點作為整個建網的開始,遍歷 Twow-Vertex中的所有點找出其最近的點i形成第1個三角形的一條邊。在尋找核心三角形第三點時,根據第三點到該邊的距離最短原則確定,即由余弦定理求取該邊對應角最大的點k作為核心三角形的第3點。首先將核心三角形的3個頂點按選取的先后順序存入到向量 Twoww Vertex,點的序號分別為0、i、k;然后將核心三角形的編號設為0,3個頂點號按選取的順序即:0、i、k,存儲在向量 TriangleList中;最后根據向量 TriangleList中的記錄,將三角形的三條邊作為序號為0、1、2的3個記錄存入向量LaterList,并將各邊的邊長、三角形編號及第3點的序號寫入LatDist、Old Tri和Old TriPt中。

3)利用核心三角形擴展三角形。依次將向量Twoww Vertex中的點與其向下的每一個點組合成邊,如果該邊在向量LaterList中存在,則該邊為進行擴展三角形的基礎,將向量 Twow Vertex中滿足擴展要求的點存入向量Twoww Vertex中。三角形邊擴展過程如圖2所示:0-14-15為核心三角形,按順序以0-14為邊擴展得到3號點,加入到向量Twoww Vertex中;0-15擴展得到5號點,加入到向量 Twoww Vertex中;0-3擴展得到16號點;0 -5得到1號點;0-16得到1號點,加入到向量Twoww Vertex。接著以14號點開始向下遍歷,即以14-15為邊進行擴展得到6號點,依次類推直到所有的點都成為三角格網中的頂點。

圖2 平面三角格網建立示意圖

由一條邊擴展三角形時,首先要排除與該邊所對的原三角形的頂點位于同側的點。可根據該邊兩個端點坐標構造的直線方程判別式(6)來進行判斷。

將向量LaterList中Old TriPt元素中的三角形頂點所對應的坐標代入式(6),得到函數值F0。由于擴展三角形的頂點必須與擴展邊對應原三角形的頂點分別在擴展邊的兩側,因此,參與擴展三角形的頂點的坐標代入式(6)后得到的函數值F(x,y)的符號應與F0的符號相反。對于滿足以上判斷條件的點,再根據余弦定理獲取擴展邊對應的角最大的點,作為擴展三角形的第3個頂點。將擴展三角形的編號及三個頂點寫入向量 TriangleList,并在向量LaterList中增加兩條新增邊的記錄;然后,將擴展三角形的頂點加入向量LaterList的原記錄的New TriPt元素中,并計算Old TriPt和New TriPt所存放的兩點的距離,將計算結果存放在CroDist元素中。

4)三角格網優化。如果原三角形3個頂點與新擴展的頂點構成凸四邊形,則要判斷CroDist值是否小于LatDist值。當CroDist值小于LatDist值時,原三角形與擴展三角形的圖形結構要進行優化。在進行三角形圖形優化時,只需根據向量LaterList中Old Tri和New Tri值查找到向量TriangleList中相應的兩條記錄,并將重構成的三角形作為兩個記錄分別替換向量TriangleList中相應的記錄。

5)格網映射。經過上述2)、3)、4)過程,實現平面上三角格網建立后,需將平面三角格網映射為三維空間三角格網。由于點間相對位置不變,所以向量TriangleList中保存的每個平面三角形的信息與三維空間三角格網的信息一致,即:三維空間三角形的3個頂點與向量 TriangleList中存儲的三角形的3個頂點相對應。

3 兩種投影法建立礦井基坑格網實例

某礦井基坑深約為 10 m,水平截面約為4.7 m×4.7 m的方形截面,基坑內表面不光滑,并且有一定的起伏。對該基坑進行三維激光數據采集,共獲得了46 365個基坑內表面的點,平均點間隔約為60 mm。為了清晰的反映利用橢球面投影法建立包含頂部或底部數據的空間格網效果,在Access數據庫中分別截取表示基坑底部的三維點(共計2 341個點)和礦井中部一段點云(共計4 000個點)(見圖3(a)、(b)、(c))。對基坑底部的點云分別利用圓柱面投影法和橢球面投影法進行坐標轉換后,生成三維空間的礦井基坑底部三角格網,并通過OpenGL三維圖形函數庫繪制和顯示(見圖3中的(d)和(e));對礦井中部點云先整體繞X軸旋轉90°,然后分別利用圓柱面投影法和橢球面投影法建立三維空間的礦井基坑中部三角格網(見圖3中的(f)和(g))。

從圖3可知,借助面投影法,利用平面建立Delaunay三角形的方法建立點云三角格網,生成的三角形形狀均勻,整體圖形結構合理。對于四周型物體表面的三維激光掃描點云利用橢球面投影法建立三角格網與利用圓柱面投影法建立的三角格網具有相同的網形效果。對于包含頂部和底部數據的點云利用圓柱面投影法實現三維空間三角格網建立時,頂部和底部的點云所生成格網的拓撲關系比較混亂;利用橢球面投影法實現三維空間三角網建立時,生成三角形的形狀較為均勻,整體的網形結構較為合理,能夠較好的保持三維空間點原始的拓撲關系。但利用橢球面投影法實現空間三角格網建立的效率比圓柱面投影法的效率低,且隨著點云數量越多,這種差異越明顯。這是由于在利用橢球面投影法需運用迭代方法計算橢球面坐標B,且坐標值x1和y1的計算較復雜。

因此當點云的數據量較大時,用圓柱面投影法實現空間三角格網的建立在效率上優于橢球面投影;當點云數據為具有頂部和底部數據的情況下,采用橢球面投影法建立空間三角格網在網形上具有明顯的優勢。

4 結束語

采用圓柱面投影法和橢球面投影法將點云數據投影至二維平面上,將復雜的三維問題轉化為二維問題在平面上進行構網,然后格網映射成整體的三維模型,能夠取得較好的構網效果,且具有較高的效率。通過對比實驗表明,對于具有頂部和底部數據的點云數據,利用圓柱面投影法建立三維空間三角格網,頂部和底部的點云所生成格網的拓撲關系比較混亂;利用橢球面投影法實現三維空間三角網建立時,生成三角形的形狀較為均勻,整體的網形結構較為合理,能夠較好的保持三維空間點原始的拓撲關系。但當點云數據量較大時,用圓柱面投影法實現空間三角格網的建立在效率上優于橢球面投影。因此針對不同的點云數據選擇必須不同的投影方法方能有效保證點云構網的精度和效率。

[1]S-M HUR,H-C KIM,S-H LEE.STL File generation w ith data reduction by the delaunay triangulation method in reverse engineering[J].The International Journal of Advanced Manufacturing Technology.2002,19:669-678

[2]H-C KIM,S-M HUR,S-H LEE.Segmentation of the measured point data in reverse engineering[J].International Journal of Advanced Manufacturing Technology, 2002,20:571-580.

[3]CHEN L IANG-CH IA,GRIER C IL IN.A vision-aided reverse engineering app roach to reconstructing free-form surface[J].Robotics&Computer-Integrated Manufacturing.1997,13:323-336

[4]CHO IBK,SH IN HY,YOON YI,et al..Triangulation of scattered data in 3D space[J].Compute Aided Des. 1988,0(5):239-248.

[5]FANG TP,PIEGL L.Delaunay triangulation in three dimensions[J].IEEE Comput Graph App l.1995,15(5): 62-69.

[6]XIANG-YANG L I.Sliver-free tree dimensional delaunay mesh generation[D].PhD Dissertation of the University of Illinois at U rbana Champaign.January,2001.

[7]鄭德華,張云濤.基于物體表面散亂三維激光掃描點的三角形格網建立[J].測繪工程,2004,13(4):62-65.

[8]張帆,黃先鋒,李德仁.基于球面投影的單站地面激光掃描點云構網方法[J].測繪學報,2009,38(1):48-54.

[9]孔祥元,郭際明.大地測量學基礎[M].武漢:武漢大學出版社,2001.

[10]黃淼,張海朝.散亂點云的三角劃分算法研究[J].微計算機應用,2007,28(10):1 039-1 042.

Triangular grid establishment based on disordered point cloud of ellipsoidal surface projection

ZHENGDe-hua,PANG Yi-qun,CAO Cao
(College of Civil Engineering,Hohai University,Nanjing 210098,China)

The spatial point cloud data to establish a triangular grid in 3D laser scan data p rocessing is one impo rtant p rocess.Previousmethods of establishing triangular grid are shape and structurally sound,but have p roblem to calculate the characteristics of low efficiency w ith large amount of points.In this paper, carried out w ith Gaussian ellipsoid p rojection for the establishment of point cloud to establish triangular grid method,effective imp lementation of the surrounding grid-based point cloud data building p rocess. Combination of point cloud data instance of amine,based on cylindrical surface and the ellipsoid p rojection to establish a triangular grid of two methodswere compared;results showed that the use of ellipsoid to establish a triangular grid p rojection method is more effective in building the top and bottom of the points cloud data topology.

disordered point cloud;triangular mesh;ellipsoidal surface p rojection;Gauss p rojection

P226

A

1006-7949(2010)04-0019-05

2009-11-24

江蘇省交通科學研究計劃項目(09Y08)

鄭德華(1972-),男,副教授,博士.

[責任編輯:張德福]