點云配準FPFH特征子異構并行優化研究

王敏

摘要：三維點云配準在逆向工程中應用廣泛，能為古建筑保護實現三維建模提供精確的數據依據。針對大規模多視角古建筑點云數據進行配準，研究了FPFH特征提取的串行算法，設計了三類并行方案，分別為利用基于CPU的并行編程標準OpenMP進行并行優化加速、利用基于GPU的并行計算架構CUDA進行并行優化加速，以及利用CPU/GPU的異構并行，結合OpenMP和CUDA的特點應用于特征子求取。實驗結果表明，第三種方案能合理設計并優化特征子求取，獲得較為理想的加速比。

關鍵詞關鍵詞：點云配準；FPFH；并行計算；CUDA；OpenMP

DOIDOI：10.11907/rjdk.171848

中圖分類號：TP301

文獻標識碼：A文章編號文章編號：16727800（2017）011002904

0引言

古建筑保護需要使用逆向工程，主要是利用測試儀器獲取的多視點數據加上它們之間的原始坐標變換關系，進行點云數據間的配準。隨著掃描儀測量精度不斷提高，點云數據規模將變大。

針對配準算法、點云配準算法，應用最為廣泛的是由Besl和Mkcya[1]提出的最近點迭代（Iterative Closest Point，ICP）算法，通過迭代搜索兩片點云之間的最近點，建立對應的匹配關系。然而，搜索過程相當耗時且會陷入局部極值。尤其是針對解決多視點的配準，為了解決這類問題，學者們提出了許多基于幾何特征的改進配準算法，如Rusu、Radu等[2]提出了點特征直方圖PFH（Point Feature Histograms），后來又提出了快速點特征直方圖FPFH（Fast Point Feature Histograms）[3]，并在PCL點云庫中實現了相應算法[4]。

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

1配準算法概述

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

實現配準的具體步驟為：①首先加載兩個點云數據集合，并利用關鍵點選取標準算法提取關鍵點；②對選擇的所有關鍵點計算特征描述子；③結合特征描述子在兩個數據集中的坐標位置，根據兩者之間特征和位置的相似度，估計它們的對應關系，初步估計對應點對；④除去對配準有影響的錯誤對應點對；⑤利用過濾后的正確對應點關系估計剛體變換，完成最終配準。

3.2CUDA方案

CUDA程序流程[10]如下：

圖5CUDA并行模型方案

CUDA核心代碼分為兩部分：

（1）host端要進行的操作：

//在host端設置設備

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數據存入顯存

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程序等待顯存內核程序執行

pcl：：GPU：：FPFHEstimation：：PointCloud gCloud

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

//…

使用CUDA封裝好的程序對GPU的操作進行了封裝，并且有很好的API提供給用戶。

（2）在device端內核程序的設計分為兩個內核kernel函數：endprint

__global__void SpfhKernel<<>>（spfh）；

__global__void FpfhKernel<<>>（fpfh）；

3.3CUDA+OpenMP方案

圖6CUDA+OpenMP并行模型方案

Input：點云數據分塊

Output：FPFHEstimation

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

for （i=0； i<任務分解； i++）

{

checkCudaErrors（cudaSetDevice（dev_id））；

int tid=omp_get_thread_num（）；

execute（任務[i]， handles， streams， tid）；

}

cudaDeviceSynchronize（）；//同步

//資源回收

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

4實驗結果分析

4.1實驗環境

實驗環境為：Intel酷睿i5 6300HQ處理器，主頻2.3GHz，4GB內存。

4.2方案一

圖7為Parallel Studio中OpenMP優化線程并行過程的函數熱點。

圖7OpenMP優化線程并行過程函數熱點

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

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

針對式（5）中得到的加速比，加速效果不是很明顯，原因如下：①OpenMP啟動與銷毀線程需要時間；②相對于大規模點云，本次測試的數據規模較小，從pcd文件中的POINTS可以看出，點數約為30多萬；③點云特征值描述子占整個配準過程的耗時比例不大。

4.3方案二

對于內核kernel函數spfh和fpfh的對比，結果過濾只顯示關注的設備利用率時間與Nsight上函數的執行時間，可以看出內核函數對設備的利用還有很大提升空間。對于CPU/GPU耗時的統計，每次實驗結果都不一樣，但點云數目越大，加速比將趨于穩定，如表1所示。

表1不同規模測試點云CUDA耗時與加速比

點云規模1001 00030 000

CPU串行耗時（s）0.3076.30370.648

GPU并行耗時（s）1.0011.9815.873

加速比0.303.1812.029

由此得出單獨利用CUDA平臺進行并行優化加速時，使用PCL封裝的GPU操作將會帶來加速比的提升，只需少量顯存空間進行申請釋放等額外操作。

4.4方案三

在GPU內的FPFH描述子算法建立方案二的基礎上，此方案更加充分利用了CPU并行模型OpenMP，在外層利用OpenMP多線程對其進行了任務調度，以對GPU進行操作。實驗結果如表2所示。

表2不同規模測試點云CUDA+OpenMP耗時與加速比

點云規模1001 00030 000

CPU串行耗時（s）0.2976.46771.231

GPU/CUDA并行耗時（s）3.8174.1734.923

加速比0.081.5514.47

可以看出采用CUDA和OpenMP兩者相結合的方案，不僅需要少量的顯存空間進行申請釋放等額外操作，而且OpenMP的線程開銷也會影響程序運行時間，但兩者的時間在數據規模變大后影響將變小。同時，在數據規模在萬級以上時，其將比僅依靠GPU并行的程序更加高效，可獲得更好的加速比。

5結語

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

參考文獻參考文獻：

[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]陸軍，彭仲濤，董東來，等.點云FPFH特征提取優化配準算法[J].新型工業化，2014（7）：7581.

[9]朱德海.點云庫PCL學習教程[M].北京：北京航空航天大學出版社，2012.

[10]荊銳，趙旦譜，臺憲青.基于GPU的實時三維點云數據配準研究[J].計算機工程，2012，38（23）：198202.

責任編輯（責任編輯：黃?。?