基于GPU并行處理的地形三維重建技術(shù)研究

楊秀峰，靳海亮，臧文乾

(1.河南理工大學(xué)，河南 焦作454000;2.中國科學(xué)院遙感與數(shù)字地球研究所，北京100101)

0 引言

隨著計算機(jī)科學(xué)和計算機(jī)圖形學(xué)的發(fā)展，三維地形的應(yīng)用范圍不斷擴(kuò)大，越來越多的涉及虛擬與現(xiàn)實、戰(zhàn)場環(huán)境仿真、土地管理與利用、地理信息系統(tǒng)、娛樂與游戲等大規(guī)模的三維地形應(yīng)用中，因此，如何快速的實現(xiàn)大規(guī)模的地形重建是一個值得研究的問題［1］。

近年來，很多學(xué)者對基于點云的三維重建技術(shù)進(jìn)行了研究。目前基于點云的三維重建技術(shù)大致可劃分為基于Delaunay三角剖分的方法、基于隱式曲面的方法和基于區(qū)域增長的方法［2］。在眾多基于Delaunay三角剖分的方法中，Amenta［3］等人提出的基于中軸逆變換的Power Crust算法最具代表性。針對點云密度不均勻、帶孔洞以及尖銳特征的任意點云，該方法都可重建出精密網(wǎng)格模型而不需要任何后期再處理，但是該算法需要進(jìn)行復(fù)雜的三維Delaunay三角化處理，時間復(fù)雜度相當(dāng)高，因此難以處理大規(guī)模地形的三維重建?；陔[式曲面的方法的核心是如何選取適當(dāng)?shù)碾[曲面模型，其中比較著名的算法有Carr［4］等人提出的基于徑向基函數(shù)的方法，Alexa［5］等人提出的基于移動最小二乘的方法和Kazhdan［6］等人提出的基于泊松方程的方法。這類方法能夠較好的處理帶有噪聲的點云數(shù)據(jù)，但是容易丟失點云模型的原始數(shù)據(jù)信息和過渡平滑地物細(xì)節(jié)，并且針對大規(guī)模的點云，處理時間長。基于區(qū)域增長的方法一般都是從一個初始種子三角形出發(fā)，根據(jù)一定的判斷原則添加點，不斷向周邊擴(kuò)張直到所有數(shù)據(jù)點都被處理。其技術(shù)難點在于初始三角形的確定和新加入三角形點的判斷。該方法可以實現(xiàn)大規(guī)模點云的三維重建，但是點云的重建質(zhì)量過分依賴種子三角形的選取，并且在點云密度不均勻的情況下容易產(chǎn)生孔洞。Bemardin［7］提出的基于α-shape理論的滾球法(Ball Pivoting Algorithm，BPA)是比較著名的。目前，除了對上述單一方法的研究外，針對各種方法的融合使用也進(jìn)行了大量的研究。王先澤［2］等人提出了一種基于Delaunay三角剖分和區(qū)域生長相結(jié)合的方法。首先對點云模型進(jìn)行Delaunay三角剖分，然后從區(qū)域的邊界邊上添加新的三角面片，直到生成一張完整的三角網(wǎng)格模型。該方法在重建效率上有所提高，并能在一定程度上避免狹長三角形的產(chǎn)生從而提高生成網(wǎng)格的質(zhì)量，但是針對大規(guī)模點云的重建，耗時仍是難以克服的問題。

整體而言，無論是單一的方法，還是多種方法的融合使用都無法有效的解決大規(guī)模點云三維重建的耗時問題。因此，本文提出一種基于GPU并行化的局部平面投影的地形三維重建方法，實現(xiàn)了三維地形的快速重建。

1 基于局部平面投影的地形三維重建算法

基于局部平面投影的方法是一種降維的三角剖分計算，在二維平面上實現(xiàn)三維重建。首先計算每個點的鄰域信息，然后將每個點的鄰域點投影到過該點的切平面上進(jìn)行該點局部的Delaunay三角剖分，最后返回三維空間合并網(wǎng)格以及網(wǎng)格法向歸一化調(diào)整。在本文基于點云的地形三維重建中主要包括k近鄰計算、法向量計算、投影、徑向排序和Delaunay近鄰計算。

1.1 k近鄰計算

k近鄰計算一直是計算機(jī)圖形學(xué)、機(jī)器學(xué)等領(lǐng)域的難點，特別當(dāng)點云數(shù)據(jù)量大時，k近鄰計算更是一個耗時的工作。因此，選擇一個好的k近鄰計算方法對于提高整個算法性能是至關(guān)重要。近似最近鄰(approximate nearest neighbor，ANN)算法庫是近年來運用比較廣泛的一種k近鄰計算方法，它是基于kd樹搜索的一種方法，相對與傳統(tǒng)的方法在性能上有75%提高，因此本文采用ANN算法庫實現(xiàn)點k近鄰。

1.2 法向量計算

法向量是點云具有的一個重要的局部特征，是進(jìn)行點云處理必不可少的信息。本文中法向量的求解采用平面擬合的方法，主要用于鄰域點的投影和排序，以及網(wǎng)格法向歸一化調(diào)整。假設(shè)一點為p，其k近鄰集合為Q={qi}，i=1，2，3，…，k，令=qi-p，應(yīng)用最小二乘法，該點的法向量使得式(1)最小:

可得到3×3矩陣C:

容易證明，對于協(xié)方差矩陣C，其最小特征值對應(yīng)的特征向量進(jìn)行單位化可作為法向量的近似值。

1.3 投影

如圖1所示，假設(shè)T為過某點的切平面，Q'= {q'i}，i=1，2，3，…，k為該點的領(lǐng)域點在其切平面上的投影點集合，則q'i可由在與所確定的平面內(nèi)旋轉(zhuǎn)得到

其中，q^i是qi在切平面上的正交投影

圖1 旋轉(zhuǎn)投影

1.4 徑向排序

1.5 Delaunay近鄰計算

對切平面上的投影點進(jìn)行徑向排序之后，利用二維平面三角剖分原理，從投影點集合中確定每個點的Delaunay鄰近點，從而實現(xiàn)每個點的局部重建。如圖2所示，l2是線段pq'i的垂直平分線，M是其中點，I是 pq'i-1的垂直平分線 l1與pq'i+1的垂直平分線l3的交點。如果I點不在p點與M點之間，則q'i是p點的有效Delaunay鄰近點，然后繼續(xù)下一點的Delaunay近鄰判斷;否則刪除該點，并回溯判斷〈q'i-2，q'i-1，q'i+1〉的有效性從而再次判斷p'i-1是否為有效的Delaunay鄰近點。直到?jīng)]有點標(biāo)記為無效的Delaunay鄰近點，Delaunay鄰近計算完畢。

圖2 Delaunay近鄰點計算

2 基于GPU并行處理的地形三維生成

近年來，圖形處理器(Graphic Processing U-nit，GPU)在通用計算構(gòu)架方面的飛速發(fā)展，使其計算性能不斷提高，計算能力已遠(yuǎn)遠(yuǎn)超過了通用處理器CPU，為加速三維重建提供了新的技術(shù)手段。2007年Nvidia公司正式發(fā)布的CUDA編程模型引發(fā)了GPU通用計算的革命，其將CPU作為主機(jī)，而GPU作為協(xié)處理器或者設(shè)備(device)。在模型中，CPU和GPU協(xié)同工作，其中CPU主要負(fù)責(zé)處理邏輯性強(qiáng)的事物和串行計算; GPU主要負(fù)責(zé)執(zhí)行高度線程化的并行處理，實現(xiàn)大數(shù)據(jù)量的密集運算。

2.1 算法框架

通過對局部平面投影方法的分析，基于CUDA框架實現(xiàn)地形的三維重建中，鄰域點的計算、網(wǎng)格合并和法向歸一化在CPU完成，而針對每一個點的局部重構(gòu)則在GPU中實現(xiàn)，其流程圖如圖3所示。

圖3 基于CUDA的地形三維重建流程

首先，在CPU上讀取點云數(shù)據(jù)，并調(diào)用ANN算法庫進(jìn)行k近鄰計算。然后，將數(shù)據(jù)傳入GPU中，接下來正式在GPU上進(jìn)行局部平面投影算法。利用CPU控制內(nèi)存分配和啟動內(nèi)核函數(shù)，而針對每一個點的局部平面投影算法的每個步驟都在GPU上執(zhí)行，從而實現(xiàn)了并行處理。最后，在CPU上完成網(wǎng)格合并和法向歸一化調(diào)整。

2.2 算法實現(xiàn)及結(jié)果分析

所采用實驗設(shè)備為:Intel(R)Core(TM) i7CPU，主頻1.6 GHz，Windows7操作系統(tǒng)，顯卡為NVIDIA Quadro FX 880M。分別采用CPU模式下的局部平面投影方法和GPU模式下的局部平面投影方法對文家溝(圖4所示)進(jìn)行了三維地形重建，其結(jié)果如圖5所示，并將2種重建方法的時間進(jìn)行了比對，如表1所示。從統(tǒng)計的結(jié)果可以看出，利用基于GPU的局部平面投影算法重建地形的三維網(wǎng)格比基于CPU的方法有顯著提高，特別在法向量計算和角度計算2個步驟中，分別有30多倍和40多倍速度的提升。

圖4 文家溝三維點云模型

圖5 文家溝三維重建網(wǎng)格模型

3 總結(jié)與展望

面對大規(guī)模地形三維重建耗時的問題，通過GPU并行處理的方式，使大規(guī)模網(wǎng)格生成的時間大幅降低。描述了局部平面投影算法的前提下，提出了一種基于GPU的局部平面投影算法，并基于CUDA框架實現(xiàn)了汶川文家溝三維地形的快速重建。實驗結(jié)果表明，利用基于GPU的局部平面投影算法比傳統(tǒng)的CPU模式下的局部投影算法有顯著的提高，可見，在大規(guī)模地形三維重建中，GPU相對于CPU都有著相當(dāng)大的優(yōu)勢。然而，由于實際點云數(shù)據(jù)的多樣性和復(fù)雜性，總是會有點云稀疏或不均勻的情況，因此，重建過程或多或少都會導(dǎo)致洞的產(chǎn)生，孔洞修補(bǔ)成為必不可少的步驟。下一步工作，如何在GPU上實現(xiàn)孔洞的修補(bǔ)，從而快速、高質(zhì)量的實現(xiàn)大規(guī)模地形的三維重建。

表1 運行時間結(jié)果對比

［1］ 徐 超.三維地形快速生成算法［D］邯鄲:河北工程大學(xué)，2011.

［2］ 王先澤，李忠科，馬亞奇，等.基于Delaunay三角剖分和區(qū)域生長的散亂點云重構(gòu)［J］.四川工兵學(xué)報，2012，33(5):108-111.

［3］ Amenta N，Choi S，Kolluri R K.The power crust，unions of balls，and the medial axis transform［J］.Computing Geometry，2001，19(2):127-153.

［4］ Carr J C，Beatson R K，Cherrie J B，et al.Reconstruction and representation of 3D objects with radial basis functions［C］.Proceedings of the 28thannual Conference on Computer Graphics and Interactive Techniques，2001:67-76.

［5］ Alexa M，Behr J，Cohen-Or D，et al.Computing and rendering point set surfaces［J］.Visualization and Computer Graphics，IEEE Transactions on，2003，9 (1):3-15.

［6］ Kazhdan M，Bolitho M，Hoppe H.Poisson surface reconstruction［C］.Eurographics Symposium on Geometry Processing，2006.

［7］ Bernardini F，Mittleman J，Rushmeier H.The ball-Pivoting algorithm for surface reconstruction［J］.IEEE Transactions on Visualization and Computer Graphics，1999，5(4):349-359.