王嘉琛, 葉周潤, 歐 鑫, 袁 斌, 吳言安, 張樹峰

(1.合肥工業(yè)大學 土木與水利工程學院,安徽 合肥 230009; 2.廣西中馬園區(qū)數(shù)字城市科技有限公司,廣西 欽州 535008; 3.安徽開源路橋有限責任公司,安徽 合肥 230093)

0 引 言

三維激光掃描技術具有數(shù)據(jù)采樣率高、分辨率高等優(yōu)點,近年來在測繪、實景三維中國等領域得到越來越廣泛的使用。三維激光掃描技術的發(fā)展使得掃描儀器的精度越來越高,這也導致點云數(shù)據(jù)量不斷增加,給后續(xù)的點云數(shù)據(jù)處理工作帶來挑戰(zhàn)。點云配準是點云處理技術中的一種,在三維重建、三維定位、姿態(tài)估計中具有至關重要的作用,點云配準的速度是點云數(shù)據(jù)處理中急需解決的問題。目前,點云配準的研究熱點是通過采用并行技術提高其速度[1-3]。

點云配準分為粗配準與精配準。點云粗配準算法主要有以下3種:① 基于全局搜索思想的配準方法,如隨機抽樣一致(random sample consensus,RANSAC)配準算法[4-5];② 基于幾何特征描述的配準方法,如采樣一致性初始配準(sample consensus initial alignment,SAC-IA)算法[6-7];③ 基于正態(tài)分布變換的配準方法,主要算法為正態(tài)分布變換(normal distributions transform,NDT)配準算法[8-9]。

粗配準與精配準是相互關聯(lián)的,粗配準為精配準提供初始位置,精配準能進一步優(yōu)化粗配準結(jié)果,得到更精確的配準效果。點云精配準中最經(jīng)典的算法是迭代最近點(iterative closest point,ICP)算法[10]。但是傳統(tǒng)ICP算法在沒有良好的初始位置時,存在無法實現(xiàn)全局最優(yōu)解的情況;并且ICP算法需要遍歷點云中的所有點,此過程在ICP算法中耗時最長,使海量點云配準效率很低。針對上述不足,國內(nèi)外研究者提出一些改進算法。文獻[11]通過構建KD樹(k-dimensional tree,KD-Tree)加速點云遍歷的過程,減少尋找最鄰近點的耗時;文獻[12]提出廣義迭代最近點(generalized iterative closest point,GICP)算法,與傳統(tǒng)ICP算法相比,GICP算法的魯棒性與精確性更強;文獻[13]提出體素化廣義迭代最近點(voxelized generalized iterative closest point,VGICP)算法,通過體素化擴展GICP算法,避免了高代價的最近鄰搜索;文獻[14]提出一種快速點云配準算法,通過提取點云特征進行粗配準,然后進行ICP精配準,減少配準耗時;文獻[15]利用開放運算語言(open computing language,OpenCL)實現(xiàn)KD-Tree的并行搜索,從而實現(xiàn)并行的ICP配準;文獻[16]利用信息傳遞接口(message passing interface,MPI)實現(xiàn)多幅點云配準并行化。

隨著計算機的中央處理器(central processing unit,CPU)與圖形處理器(graphics processing unit,GPU)的發(fā)展,GPU的算力越來越高,利用GPU的多線程運算能力能有效提高一些傳統(tǒng)算法的效率[17]。針對傳統(tǒng)的ICP算法在大數(shù)據(jù)量點云配準中速度慢的問題,本文利用GPU的多線程能力加速ICP算法中點云遍歷過程,基于GPU實現(xiàn)并行化的統(tǒng)一計算設備架構迭代最近點(compute unified device architecture iterative closest point,CUDAICP)算法,從而減少ICP配準的耗時。

本文配準流程如圖1所示。

1 點云預處理與點云粗配準

1.1 點云預處理

在點云配準前要進行點云預處理,包括點云下采樣與去噪。用體素法進行點云下采樣,進而在保證點云特征的情況下,降低點云數(shù)據(jù)量,提高去噪和粗配準的速度;用統(tǒng)計濾波去噪剔除部分噪聲點、離群點,減少配準過程中出現(xiàn)的誤匹配問題。

1.2 點云粗配準算法

為了避免ICP算法陷入局部最優(yōu)解,本文采用3種點云粗配準方法,即改進的RANSAC配準算法、SAC-IA算法、NDT配準算法,為點云精配準獲得較好的初始位置。

1) 改進的RANSAC配準算法。通過快速點特征直方圖(fast point feature histograms, FPFH)的最近鄰匹配,找到源點云中3個及以上隨機采樣點及其在目標點云中的對應點;用采樣對應來估計假設變換。

2) SAC-IA算法。首先計算源點云和目標點云的方向信息、各自的FPFH,基于FPFH對2幅點云中的點進行配準,然后隨機選擇3對以上匹配點,通過奇異值分解(singular value decomposition,SVD)求解變換矩陣。

3) NDT配準算法。針對點云中每個點計算其法向量與偏移量,通過協(xié)方差矩陣計算特征值與特征向量,并計算出高維特征空間中高斯網(wǎng)格圖,將每個點轉(zhuǎn)換為高維特征空間中的點并進行匹配和配準。

2 點云精配準

源點云經(jīng)過粗配準得到較好的初始位置后,源點云與目標點云沒有完全對齊,還需要精配準進一步優(yōu)化粗配準結(jié)果,得到更精確的配準效果。本文選用ICP算法并對其進行優(yōu)化。

2.1 ICP算法

ICP算法的實質(zhì)是尋找2幅點云中的對應點,最小化其歐式距離d,計算公式為:

(1)

其中:Np為2幅點云對應的數(shù)量;pi為源點云中的點;qi為目標點云中pi的對應點;R、T為需要求解的旋轉(zhuǎn)矩陣與平移矩陣。

ICP算法具體流程為:

1) 給定源點云P、目標點云Q。

2) 遍歷P、Q,尋找P、Q最近點,計算對應點對的歐氏距離d。

3) 利用SVD計算相應的變換矩陣。

4) 對P進行旋轉(zhuǎn)平移得到新的點云P′。

5) 設置閾值d′或者最大迭代次數(shù),若d

經(jīng)過多次迭代,點云P就會越來越接近Q,2幅點云最終趨于完全對齊。

2.2 CUDA架構

近年來,隨著GPU的發(fā)展,GPU計算能力得到極大提升,不僅能處理傳統(tǒng)的圖形計算,而且在數(shù)據(jù)的并行計算上也得到廣泛應用。NVIDIA公司的統(tǒng)一計算設備架構(compute unified device architecture,CUDA)可以有效解決一些復雜的計算。

在 CUDA 的架構下,一個程序可以分成2個部分,分別是對CUDA程序進行控制和管理的主機(Host)端與負責執(zhí)行CUDA核函數(shù)的設備(Device)端。CUDA架構示意圖如圖2所示。圖2中,RAM表示隨機存取存儲器(random access memory)。

并行程序流程為:Host端程序會將數(shù)據(jù)準備好,先在GPU中開辟所需的內(nèi)存空間,復制到GPU的內(nèi)存中,再由GPU執(zhí)行Device端程序,執(zhí)行完成后將運行結(jié)果傳回Host端,最后釋放GPU所開辟的內(nèi)存。

2.3 CUDAICP算法

傳統(tǒng)的ICP算法需要遍歷2幅點云內(nèi)所有點,此過程是傳統(tǒng)ICP算法中耗時最長的,僅使用CPU對大數(shù)據(jù)量點云進行點的遍歷耗時較長,需要利用GPU的多線程計算能力,調(diào)用多個計算單元同時搜索。理論上用GPU可以加速ICP配準的過程。

CUDAICP算法具體流程為:

1) 給定源點云P、目標點云Q。

2) 在GPU上為2幅點云開辟內(nèi)存空間。

3) 將P、Q從主機內(nèi)存?zhèn)鬏斨罣PU內(nèi)存。

4) 并行尋找最近點、計算對應點對的歐式距離d。

5) 利用SVD求解對應的剛體變換。

6) 對P做變換得到新的點云P′。

7) 設置閾值d′或者最大迭代次數(shù),若d

8) 釋放GPU上開辟的內(nèi)存。

CUDAICP算法流程如圖3所示。

圖3 本文CUDAICP算法流程

3 實例分析

本文以Windows10系統(tǒng)Microsoft Visual Studio 2017為實驗平臺,利用點云庫(Point Cloud Library,PCL)實現(xiàn)點云預處理與點云粗配準,使用Eigen庫以及CUDA庫實現(xiàn)點云精配準。實驗平臺配置為:Dell工作站,CPU為Intel酷睿i5-10500,GPU為NVIDIA GeForce GTX 1660 SUPER,內(nèi)存為16 GiB。采用房間點云數(shù)據(jù)、帶有樓梯的房間點云數(shù)據(jù)驗證算法的可行性,具體點數(shù)分別為112 605、1 128 055。

2種場景原始點云數(shù)據(jù)如圖4所示。

圖4 2種場景原始點云數(shù)據(jù)

圖4中:紅色點云為源點云;藍色點云為目標點云。

2種場景點云數(shù)據(jù)粗配準結(jié)果見表1所列,配準誤差為均方誤差。

表1 2種場景點云數(shù)據(jù)粗配準結(jié)果

從表1可以看出:對于房間點云,SAC-IA算法相對于RANSAC配準算法和NDT配準算法,具有較低的配準誤差(0.544 m2)和相對較短的耗時(42.94 s);對于帶有樓梯的房間點云,SAC-IA算法表現(xiàn)出較低的配準誤差(0.059 m2),但相對于RANSAC配準算法與NDT配準算法,其耗時略長(69.14 s);NDT配準算法在房間點云數(shù)據(jù)的粗配準中精度低且耗時長,RANSAC配準算法在帶有樓梯的房間點云數(shù)據(jù)粗配準中精度低。因此選擇使用SAC-IA算法得到的初始位置進行點云精配準。帶有樓梯的房間點云數(shù)據(jù)量較大,本文在房間點云、帶有樓梯的房間點云精配準時迭代次數(shù)分別設置為20、5次。2種場景點云數(shù)據(jù)精配準情形如圖5所示。圖5中:紅色點云為變換后點云;藍色點云為目標點云。

圖5 2種場景點云數(shù)據(jù)精配準情形

精配準結(jié)果見表2所列。

表2 2種場景點云數(shù)據(jù)精配準結(jié)果

從圖5、表2可以看出:在房間點云和帶有樓梯的房間點云精配準中,房間點云配準誤差從0.544 m2降到0.085 m2,帶有樓梯的房間點云配準誤差從0.059 m2降到0.017 m2,配準誤差變得更小;相比于傳統(tǒng)的ICP算法,CUDAICP算法在房間點云和帶有樓梯的房間點云配準中耗時分別減少257.16、116 208.86 s,CUDAICP算法表現(xiàn)出明顯的加速效果,對2種場景點云數(shù)據(jù)的配準速度分別提升8.2倍、4.7倍。

4 結(jié) 論

本文針對海量點云精配準時效率低的問題,基于GPU對傳統(tǒng)ICP算法并行化,提出CUDAICP算法。通過對2種場景點云數(shù)據(jù)的粗配準實驗得出,SAC-IA算法在2種場景點云的粗配準中配準誤差較小、耗時較短,因此本文使用SAC-IA算法為精配準提供初始位置,再使用CUDAICP算法進行精配準,得到最終結(jié)果。實驗結(jié)果表明,CUDAICP算法在保證精度與ICP算法基本相同的前提下,可大幅提高點云配準效率,速度提升最高可達8.2倍,具有實際工程應用意義。本文僅關注點云剛性配準,未來研究可拓展到非剛性配準、粗配準方法的適用性及CUDAICP算法的進一步加速。