王敏

摘要：三維點(diǎn)云配準(zhǔn)在逆向工程中應(yīng)用廣泛，能為古建筑保護(hù)實(shí)現(xiàn)三維建模提供精確的數(shù)據(jù)依據(jù)。針對(duì)大規(guī)模多視角古建筑點(diǎn)云數(shù)據(jù)進(jìn)行配準(zhǔn)，研究了FPFH特征提取的串行算法，設(shè)計(jì)了三類并行方案，分別為利用基于CPU的并行編程標(biāo)準(zhǔn)OpenMP進(jìn)行并行優(yōu)化加速、利用基于GPU的并行計(jì)算架構(gòu)CUDA進(jìn)行并行優(yōu)化加速，以及利用CPU/GPU的異構(gòu)并行，結(jié)合OpenMP和CUDA的特點(diǎn)應(yīng)用于特征子求取。實(shí)驗(yàn)結(jié)果表明，第三種方案能合理設(shè)計(jì)并優(yōu)化特征子求取，獲得較為理想的加速比。

關(guān)鍵詞關(guān)鍵詞：點(diǎn)云配準(zhǔn)；FPFH；并行計(jì)算；CUDA；OpenMP

DOIDOI：10.11907/rjdk.171848

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2017）011002904

0引言

古建筑保護(hù)需要使用逆向工程，主要是利用測(cè)試儀器獲取的多視點(diǎn)數(shù)據(jù)加上它們之間的原始坐標(biāo)變換關(guān)系，進(jìn)行點(diǎn)云數(shù)據(jù)間的配準(zhǔn)。隨著掃描儀測(cè)量精度不斷提高，點(diǎn)云數(shù)據(jù)規(guī)模將變大。

針對(duì)配準(zhǔn)算法、點(diǎn)云配準(zhǔn)算法，應(yīng)用最為廣泛的是由Besl和Mkcya[1]提出的最近點(diǎn)迭代（Iterative Closest Point，ICP）算法，通過(guò)迭代搜索兩片點(diǎn)云之間的最近點(diǎn)，建立對(duì)應(yīng)的匹配關(guān)系。然而，搜索過(guò)程相當(dāng)耗時(shí)且會(huì)陷入局部極值。尤其是針對(duì)解決多視點(diǎn)的配準(zhǔn)，為了解決這類問(wèn)題，學(xué)者們提出了許多基于幾何特征的改進(jìn)配準(zhǔn)算法，如Rusu、Radu等[2]提出了點(diǎn)特征直方圖PFH（Point Feature Histograms），后來(lái)又提出了快速點(diǎn)特征直方圖FPFH（Fast Point Feature Histograms）[3]，并在PCL點(diǎn)云庫(kù)中實(shí)現(xiàn)了相應(yīng)算法[4]。

隨著GPU/CPU異構(gòu)并行技術(shù)的快速發(fā)展，GPU浮點(diǎn)計(jì)算能力與CPU相比提高了幾個(gè)數(shù)量級(jí)。特別是英偉達(dá)的統(tǒng)一計(jì)算架構(gòu)CUDA（Compute Unified Device Architecture）[5]提供了更直觀的編程模型和優(yōu)化原則[6]。為更加合理地利用GPU/CPU異構(gòu)并行技術(shù)，解決點(diǎn)云配準(zhǔn)過(guò)程中可并行FPFH算法的時(shí)間成本隨點(diǎn)云規(guī)模變大而加大的問(wèn)題，進(jìn)行了如下工作：首先，分析點(diǎn)云配準(zhǔn)算法中串行實(shí)現(xiàn)的具體步驟，計(jì)算出配準(zhǔn)算法中特征描述子的時(shí)間消耗比；其次，設(shè)計(jì)了3種方案，即使用CPU并行的OpenMP[7]、GPU并行的CUDA技術(shù)以及將兩種技術(shù)結(jié)合的方案；最后，利用PCL（Point Cloud Library）點(diǎn)云庫(kù)實(shí)現(xiàn)程序，并通過(guò)標(biāo)準(zhǔn)點(diǎn)云文件進(jìn)行實(shí)驗(yàn)，求取加速比并進(jìn)行分析對(duì)比。

1配準(zhǔn)算法概述

點(diǎn)云配準(zhǔn)是根據(jù)兩點(diǎn)云之間的交集融合兩個(gè)點(diǎn)云的過(guò)程，最終目的是求得坐標(biāo)變換參數(shù)R（旋轉(zhuǎn)矩陣）和T（平移向量），使兩視角下測(cè)得的三維數(shù)據(jù)經(jīng)坐標(biāo)變換后的距離和最小。串行算法的基本思想是對(duì)得到的點(diǎn)云文件進(jìn)行去噪等預(yù)處理，之后計(jì)算點(diǎn)云關(guān)鍵點(diǎn)，以及關(guān)鍵點(diǎn)處的曲面法線；然后估計(jì)曲面的FPFH特征描述子，利用隨機(jī)采樣一致性算法RANSAC（Random Sample Consensus）對(duì)兩片點(diǎn)云進(jìn)行初始匹配；最后，運(yùn)用ICP算法對(duì)點(diǎn)云的初始配準(zhǔn)結(jié)果進(jìn)行二次配準(zhǔn)，進(jìn)一步優(yōu)化配準(zhǔn)結(jié)果，從而實(shí)現(xiàn)點(diǎn)云的精確配準(zhǔn)。配準(zhǔn)過(guò)程最重要的部分是提取關(guān)鍵點(diǎn)與計(jì)算特征描述子，以保證多次迭代求得對(duì)應(yīng)關(guān)系估計(jì)的準(zhǔn)確性和效率，以及后續(xù)流程中剛體變換矩陣估計(jì)的無(wú)誤性。

實(shí)現(xiàn)配準(zhǔn)的具體步驟為：①首先加載兩個(gè)點(diǎn)云數(shù)據(jù)集合，并利用關(guān)鍵點(diǎn)選取標(biāo)準(zhǔn)算法提取關(guān)鍵點(diǎn)；②對(duì)選擇的所有關(guān)鍵點(diǎn)計(jì)算特征描述子；③結(jié)合特征描述子在兩個(gè)數(shù)據(jù)集中的坐標(biāo)位置，根據(jù)兩者之間特征和位置的相似度，估計(jì)它們的對(duì)應(yīng)關(guān)系，初步估計(jì)對(duì)應(yīng)點(diǎn)對(duì)；④除去對(duì)配準(zhǔn)有影響的錯(cuò)誤對(duì)應(yīng)點(diǎn)對(duì)；⑤利用過(guò)濾后的正確對(duì)應(yīng)點(diǎn)關(guān)系估計(jì)剛體變換，完成最終配準(zhǔn)。

3.2CUDA方案

CUDA程序流程[10]如下：

圖5CUDA并行模型方案

CUDA核心代碼分為兩部分：

（1）host端要進(jìn)行的操作：

//在host端設(shè)置設(shè)備

cudaError_t cudaSDStatus=cudaSetDevice（0）；

//之后分配顯存

cudaError_t cudaIStatus=cudaMalloc（&input， input.size（）*sizeof（pcl：：pointXYZ））；

cudaError_t cudaOStatus=cudaMalloc（&output， output.size（）*sizeof（pcl：：Normal））；

//將host數(shù)據(jù)存入顯存

cudaError_t cudaIStatusH2D=cudaMemcpy（input， input， input.size（）

*sizeof（pcl：：pointXYZ），cudaMemcpyHostToDevice）；

cudaError_t cudaOStatusH2D=cudaMemcpy（output，output，output.size（）*sizeof（pcl：：pointXYZ），cudaMemcpyHostToDevice）；

//host程序等待顯存內(nèi)核程序執(zhí)行

pcl：：GPU：：FPFHEstimation：：PointCloud gCloud

gCloud.upload（cloud->points）；//從主機(jī)端到GPU端

//…

使用CUDA封裝好的程序?qū)PU的操作進(jìn)行了封裝，并且有很好的API提供給用戶。

（2）在device端內(nèi)核程序的設(shè)計(jì)分為兩個(gè)內(nèi)核kernel函數(shù)：endprint

__global__void SpfhKernel<<>>（spfh）；

__global__void FpfhKernel<<>>（fpfh）；

3.3CUDA+OpenMP方案

圖6CUDA+OpenMP并行模型方案

Input：點(diǎn)云數(shù)據(jù)分塊

Output：FPFHEstimation

#pragma omp parallel for schedule（dynamic）//OpenMP并行部分

for （i=0； i<任務(wù)分解； i++）

{

checkCudaErrors（cudaSetDevice（dev_id））；

int tid=omp_get_thread_num（）；

execute（任務(wù)[i]， handles， streams， tid）；

}

cudaDeviceSynchronize（）；//同步

//資源回收

其中execute（任務(wù)[i]， handles， streams， tid）可以在GPU或CPU上執(zhí)行FPFH特征子求取算法。

4實(shí)驗(yàn)結(jié)果分析

4.1實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境為：Intel酷睿i5 6300HQ處理器，主頻2.3GHz，4GB內(nèi)存。

4.2方案一

圖7為Parallel Studio中OpenMP優(yōu)化線程并行過(guò)程的函數(shù)熱點(diǎn)。

圖7OpenMP優(yōu)化線程并行過(guò)程函數(shù)熱點(diǎn)

在本次實(shí)驗(yàn)硬件環(huán)境下，串行程序總共產(chǎn)生了3個(gè)線程，在四核處理器中并行程序總共產(chǎn)生了6個(gè)線程，其中OpenMP產(chǎn)生了3個(gè)線程，以對(duì)特征值進(jìn)行求解。在pcl：normal_estimation并行化程序中，特征值采用FPFH特征子進(jìn)行求解，以及采取kdtree尋找鄰接點(diǎn)，為最耗時(shí)的兩部分。求得加速比為：

S（P）=T串行T并行=141.703115.188=1.23（5）

針對(duì)式（5）中得到的加速比，加速效果不是很明顯，原因如下：①OpenMP啟動(dòng)與銷毀線程需要時(shí)間；②相對(duì)于大規(guī)模點(diǎn)云，本次測(cè)試的數(shù)據(jù)規(guī)模較小，從pcd文件中的POINTS可以看出，點(diǎn)數(shù)約為30多萬(wàn)；③點(diǎn)云特征值描述子占整個(gè)配準(zhǔn)過(guò)程的耗時(shí)比例不大。

4.3方案二

對(duì)于內(nèi)核kernel函數(shù)spfh和fpfh的對(duì)比，結(jié)果過(guò)濾只顯示關(guān)注的設(shè)備利用率時(shí)間與Nsight上函數(shù)的執(zhí)行時(shí)間，可以看出內(nèi)核函數(shù)對(duì)設(shè)備的利用還有很大提升空間。對(duì)于CPU/GPU耗時(shí)的統(tǒng)計(jì)，每次實(shí)驗(yàn)結(jié)果都不一樣，但點(diǎn)云數(shù)目越大，加速比將趨于穩(wěn)定，如表1所示。

表1不同規(guī)模測(cè)試點(diǎn)云CUDA耗時(shí)與加速比

點(diǎn)云規(guī)模1001 00030 000

CPU串行耗時(shí)（s）0.3076.30370.648

GPU并行耗時(shí)（s）1.0011.9815.873

加速比0.303.1812.029

由此得出單獨(dú)利用CUDA平臺(tái)進(jìn)行并行優(yōu)化加速時(shí)，使用PCL封裝的GPU操作將會(huì)帶來(lái)加速比的提升，只需少量顯存空間進(jìn)行申請(qǐng)釋放等額外操作。

4.4方案三

在GPU內(nèi)的FPFH描述子算法建立方案二的基礎(chǔ)上，此方案更加充分利用了CPU并行模型OpenMP，在外層利用OpenMP多線程對(duì)其進(jìn)行了任務(wù)調(diào)度，以對(duì)GPU進(jìn)行操作。實(shí)驗(yàn)結(jié)果如表2所示。

表2不同規(guī)模測(cè)試點(diǎn)云CUDA+OpenMP耗時(shí)與加速比

點(diǎn)云規(guī)模1001 00030 000

CPU串行耗時(shí)（s）0.2976.46771.231

GPU/CUDA并行耗時(shí)（s）3.8174.1734.923

加速比0.081.5514.47

可以看出采用CUDA和OpenMP兩者相結(jié)合的方案，不僅需要少量的顯存空間進(jìn)行申請(qǐng)釋放等額外操作，而且OpenMP的線程開(kāi)銷也會(huì)影響程序運(yùn)行時(shí)間，但兩者的時(shí)間在數(shù)據(jù)規(guī)模變大后影響將變小。同時(shí)，在數(shù)據(jù)規(guī)模在萬(wàn)級(jí)以上時(shí)，其將比僅依靠GPU并行的程序更加高效，可獲得更好的加速比。

5結(jié)語(yǔ)

配準(zhǔn)多視角掃描的點(diǎn)云數(shù)據(jù)是獲得被測(cè)量物體表面完整模型的關(guān)鍵步驟，而三維測(cè)量技術(shù)的發(fā)展使測(cè)量點(diǎn)云的數(shù)據(jù)更精確、數(shù)據(jù)量更大。處理必然帶來(lái)時(shí)間開(kāi)銷，如今隨著異構(gòu)并行技術(shù)的發(fā)展，特別是顯卡并行計(jì)算能力的提高，特別適合點(diǎn)云這類數(shù)據(jù)量大、邏輯結(jié)構(gòu)不復(fù)雜，但數(shù)據(jù)計(jì)算繁重的任務(wù)，有助于在成本減少的情況下提高數(shù)據(jù)處理速度，減少時(shí)間成本。針對(duì)如何高效地利用異構(gòu)并行的問(wèn)題，提出了耗時(shí)FPFH特征描述子，以求取并行優(yōu)化方案，并通過(guò)幾種專業(yè)分析軟件得出運(yùn)行時(shí)間、函數(shù)熱點(diǎn)。結(jié)果表明，CUDA+OpenMP的方案能較好地結(jié)合CPU并行和GPU并行的優(yōu)勢(shì)，減少運(yùn)行時(shí)間，提高加速比，具有較高的實(shí)用價(jià)值。

參考文獻(xiàn)參考文獻(xiàn)：

[1]P J BESL，H D MCKAY. A method for registration of 3D shapes[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence，1992.

[2]R B RUSU，N BLODOW，Z C MARTON，et al. Aligning point cloud views using persistent feature histograms[C]. IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE，2013：33843391.

[3]RADU BOGDAN RUSU，NICO BLODOW，MICHAEL BEETZ. Fast point feature histograms （FPFH） for 3D registration[C]. IEEE International Conference on Robotics and Automation，2009：18481853.

[4]RADU BOGDAN RUSU，STEVE COUSINS. 3D is here： point cloud library （PCL）[C]. IEEE International Conference on Robotics and Automation，2011：14.

[5]NVIDIA. CUDA C programming guide[EB/OL]. www.nvidia.com.

[6]JOHN NICKOLLS，IAN BUCK，MICHAEL GARLAND，et al. Scalable parallel programming with CUDA[J]. Queue，2008，6（2）：4053.

[7]LEONARDO DAGUM，RAMESH MENON. OpenMP： an industrystandard API for sharedmemory programming[J]. IEEE Computational Science & Engineering，1998，5（1）：4655.

[8]陸軍，彭仲濤，董東來(lái)，等.點(diǎn)云FPFH特征提取優(yōu)化配準(zhǔn)算法[J].新型工業(yè)化，2014（7）：7581.

[9]朱德海.點(diǎn)云庫(kù)PCL學(xué)習(xí)教程[M].北京：北京航空航天大學(xué)出版社，2012.

[10]荊銳，趙旦譜，臺(tái)憲青.基于GPU的實(shí)時(shí)三維點(diǎn)云數(shù)據(jù)配準(zhǔn)研究[J].計(jì)算機(jī)工程，2012，38（23）：198202.

責(zé)任編輯（責(zé)任編輯：黃健）