徐秀川,花向紅,龔子楨,郝 旦

(1.武漢大學 測繪學院,湖北 武漢 430079;2.武漢大學 災害監(jiān)測與防治研究中心,湖北 武漢 430079)

基于球面投影的散亂點云三維建模算法實現與效果分析

徐秀川1,2,花向紅1,2,龔子楨1,2,郝 旦1,2

(1.武漢大學 測繪學院,湖北 武漢 430079;2.武漢大學 災害監(jiān)測與防治研究中心,湖北 武漢 430079)

介紹基于球面投影的散亂點云三維建模算法步驟,運用VC++編程語言結合OpenGL圖形接口實現該算法,并結合實例說明球面投影法相對于圓柱面投影法、橢球面投影法在三維建模中的優(yōu)勢。

球面投影法;散亂點云;Delaunay三角網;三維建模

三維激光掃描技術是目前測繪領域中一個新的研究熱點,其中散亂點云數據建模主要采用基于體剖分、基于面剖分和基于面投影3種方式建立?；诿嫱队笆窍葘⑷S空間數據投影到平面上進行平面構網,再映射到三維空間最終達到三維建模目的。這種方法相對于基于體剖分和基于面剖分構造三角網出錯率較低,構網效率相對較高。而基于面投影法分為基于平面投影、臨近區(qū)域切平面投影、圓柱面投影法。平面投影法只適用于平坦點云;臨近區(qū)域切平面投影處理復雜的點云時,生成的格網有重疊現象,不利于結構復雜的大型點云的數據處理;由于圓柱面投影法是將空間點沿著半徑方向投影到圓柱面上,頂部和底部數據點的投影易產生重疊,無法維持點云中原有的點之間的相對位置關系。針對圓柱面投影法的缺陷,曹操提出橢球面投影法,該方法是沿著橢球中心將各點投影到橢球面上,這就避免了點的重疊,然后根據高斯投影投影到平面上,在平面上構造Delaunay三角網后再映射成三維空間三角格網。橢球面投影雖然避免了圓柱面投影的缺陷,但是由于該方法需要涉及到迭代計算,且正算公式復雜,應用橢球面投影法建網效率明顯低于圓柱面投影法,且隨著點數的增多,這種差異越明顯。為此,本文從提高橢球面投影效率的角度出發(fā),提出球面投影法。詳細論述了基于球面投影的散亂點云三維建模算法步驟,并結合實例證明球面投影法相對于圓柱面投影法、橢球面投影法在三維建模中的優(yōu)勢。

1 基于球面投影的散亂點云三維建模的實現

基于球面投影的建模方法的基本思路是:經過數據配準[1],由三維激光掃描儀獲得的點云原始坐標都轉化為統一空間坐標系下的坐標(Xi,Yi,Zi)。以球面為媒介將空間散亂點云(Xi,Yi,Zi)投影到平面上,得到相應二維坐標(xi,yi),在平面內通過Delaunay算法構造平面三角網,最后將平面三角格網映射到空間完成三維建模。

1.1 散亂點云投影到平面

圖1為球面坐標系,O為球心,且盡量定位在掃描對象的幾何中心,球的半徑 r大小可根據計算簡便需要任意選擇,OX、OY、OZ軸構成右手坐標系,投影方向沿著球心指向各點。

圖1 球面坐標系

設 P(X,Y,Z)為任一點云數據,經投影后在球面上有唯一的 P′與點 P對應。球面坐標用(L,B)表示,與大地測量中大地經度與大地緯度定義類似,L表示OP′連線在XOY平面上的投影與OX軸的夾角(0°＜L≤360°),B 表示直線 OP′與 XOY面的

為大地經度與中央子午線的差值;t=tan B,r為球半徑。

雖然掃描對象不像地球那樣龐大,但考慮到計算結果的準確性,從盡量減小變形的角度出發(fā),仍然對球面進行分帶投影,選用6度帶投影。然而不同帶的點通過正算式(3)獲得的平面坐標并不在同一個平面直角坐標系中,這樣就不能保證點與點之間原有的相對位置關系,通過式(4)可將計算所得的平面點歸化到統一坐標系中。x、y為歸化后的坐標。

1.2 Delaunay生長算法構造平面三角網

經過以上各步驟的投影后,就將空間點云數據投影到統一的平面坐標系中,根據各平面點坐標(xi,yi),可由Delaunay生長算法構造平面三角網。其基本步驟如下:

1)創(chuàng)建點point表,邊list表,三角形 triangle表,point表存儲各點坐標信息及順序點號,list表存儲邊號、兩個端點點號、對面點點號以及各邊的usetime值。Triangle表存儲三角形順序號、三條邊順序號。

2)構建初始基線:在點point表中選擇順序點號點為1的點 A作為初始點,然后遍歷所有點,找到距點A最近的點B,連接后作為初始基線。將該邊放入邊表edge中,并將該邊的usetime值設為1。如圖2(a)所示。

圖2 Delaunay生長算法示意圖

3)構建核心三角形:運用Delaunay法則搜尋第3點,具體的做法是:遍歷所有點,查找距此初始基線距離最短的點,可由余弦定理求該邊對應角最大的點為第3點。將新形成的兩個邊放入邊表list表尾,邊usetime值均設為1,三角形放入三角形列表triangle中。如圖2(b)所示。

4)擴展核心三角形:由核心三角形的各邊分別向外擴展新的三角形,具體做法是:在該擴展邊在原三角形中的對應點異側的所有點中,如步驟2)按照余弦定理查找與該邊對應角最大的點,并組成新的三角形,加入 triangle表尾,兩條新邊加入 list表尾,usetime值設為1,已擴展的初始邊usetime值變?yōu)?。如圖2(d)所示。

5)在list表中依次按步驟3)擴展所有usetime值為1的邊,擴展后usetime值變?yōu)?,擴展的新邊順序放到edge表中,usetime均設為1,新三角形加入triangle表中。

6)重復步驟3)、4),直至邊表中所有邊的 usetime值變?yōu)?,或usetime值為1的邊無法再找到滿足擴展要求的點。

7)三角格網優(yōu)化:根據最小內角最大準則,對所建成的三角格網進行優(yōu)化。

1.3平面三角格網映射為空間三角格網

由于投影前后保證了點的相對位置不變,且點表中包含點號信息,將三維點按照平面三角格網確定的拓撲關系根據點號進行連接,可以將平面三角格網映射為空間三角格網,實現空間建模。

2 程序實現與效果分析

根據上述所介紹的基于球面投影的散亂點云三維建模步驟,運用VC++編程語言結合OpenGL圖形接口實現。

2.1 球面投影法與圓柱面投影法效果分析

選取皇冠模型原始數據(共含14443個點云數據),如圖3所示,分別采用圓柱面投影法與球面投影法進行建模,圓柱參數底面圓半徑 R=1,球參數半徑 r=1。其建模效果見圖4、圖5。

圖3 散亂點云

由圖4、圖5可以看出:對于頂部的點云利用圓柱面投影實現空間建模時,頂部點云格網拓撲關系較混亂,而利用球面投影法生成的三角形的形狀較為均勻,網形結構較為合理,能較好地維持原始的拓撲關系?？梢?球面投影法很好地彌補了圓柱面投影法由于投影方式造成的頂部數據投影重疊這一缺陷,可以更好地維持頂部或底部點云的拓撲關系。

2.2 球面投影法與橢球面投影法效果分析

同樣選取圖3所示點云數據,分別采用橢球面投影法和球面投影法構造空間三角格網,橢球面投影法橢球參數長半軸 a=2,短半軸 b=1,球面投影法球參數半徑 r=1。圖6為橢球面投影法建模效果局部截圖,圖7為球面投影法建模效果局部截圖。為了更好地進行效率對比,從原始點云中任意抽取1132、3842個點云數據,分別采用橢球面投影法和球面投影法進行建模,并記錄完成時間,實驗結果如表1所示。

圖6 橢球面投影法效果圖(局部)

圖7 球面投影法效果圖(局部)

表1 點云數據建模效率對比

由表1可以看出:對于相同數量的點云數據,利用球面投影法構造三角格網速度更快,且點云數量越多,這種優(yōu)勢越明顯。由圖6和圖7效果對比可以看出:對于較平坦區(qū)域,橢球面投影法與球面投影法效果類似,但對于表面曲率變化較大的區(qū)域,球面投影法比橢球面投影法構造三角網出錯率更低,建模效果更好。由于球的特殊性,球面投影相對于橢球面投影,投影間的轉換公式簡單且精確,采用球面投影法建模效率更高,且效果更好。

3 結束語

實驗結果表明,基于球面投影的散亂點云三維建模方法,可以避免圓柱面投影過程中造成的頂部或底部點云數據缺失問題,同時,在建模效率及效果方面,球面投影法也優(yōu)于橢球面投影法。球面投影法具有很好的實用價值。

[1]曹操.三維激光掃描數據三角格網建立方法的研究[D].南京:河海大學,2008:33-35.

[2]鄭德華.三維激光掃描數據處理的理論與方法[D].上海:同濟大學,2005:64-70.

[3]孔祥元,郭際明,劉宗泉.大地測量學基礎[M].武漢:武漢大學出版社,2005:156-158,103-104,108-109,112-113.

[4]武曉波,王世新,肖春生.Delaunay三角網的生成算法研究[J].測繪學報,1999,28(1):28-35.

[5]江劍霞,劉少華,吳漢英.VB環(huán)境下不規(guī)則三角網的算法設計與實現[J].四川測繪,2006,29(2):64-67.

[6]蔣紅雯,涂鵬,李國忠.基于生長算法構建Delaunay三角網的研究[J].公路交通科技,2004(12):38-40.

The im plementation algorithm of three-dimensionalmodeling to point cloud based on spherical surface projection and effect analysis

XU Xiu-chuan1,2,HUA Xiang-hong1,2,GONG Zi-zhen1,2,HAO Dan1,2
(1.School of Geodesy and Geomatics,Wuhan University,Wuhan 430079,China;2.Research Center for Hazard Monitoring and Prevention,Wuhan University,Wuhan 430079,China)

The algo rithm of three-dimensional modeling to point cloud based on spherical surface p rojection is introduced in the paper,and the algorithm is achieved through the app lication of VC++combining graphical interfaces OpenGL,and the superiority of spherical p rojection methods against the cylindrical p rojection methods and ellipsoidal p rojection methods is demonstrated by instance.

spherical p rojection methods;point cloud;Delaunay triangulation netwo rk;three-dimensional modeling

TP309

A

1006-7949(2011)03-0005-04

2010-05-07

國家自然科學基金資助項目(40901214);精密工程與工業(yè)測量國家測繪局重點實驗室開放基金資助項目(PF2009-2)

徐秀川(1985-),男,碩士研究生.

[責任編輯劉文霞]