楊秀峰，靳海亮，臧文乾

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

0 引言

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

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

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

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

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

1.1 k近鄰計(jì)算

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

1.2 法向量計(jì)算

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

可得到3×3矩陣C:

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

1.3 投影

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

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

圖1 旋轉(zhuǎn)投影

1.4 徑向排序

1.5 Delaunay近鄰計(jì)算

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

圖2 Delaunay近鄰點(diǎn)計(jì)算

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

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

2.1 算法框架

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

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

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

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

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

圖4 文家溝三維點(diǎn)云模型

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

3 總結(jié)與展望

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

表1 運(yùn)行時(shí)間結(jié)果對比

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

［2］ 王先澤，李忠科，馬亞奇，等.基于Delaunay三角剖分和區(qū)域生長的散亂點(diǎn)云重構(gòu)［J］.四川工兵學(xué)報(bào)，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.