基于OpenCL的ICP點云并行配準算法

劉 忠 建

(北方工業大學計算機學院 北京 100144)

?

基于OpenCL的ICP點云并行配準算法

劉 忠 建

(北方工業大學計算機學院 北京 100144)

針對當前點云配準算法效率過低的問題，運用OpenCL實現了基于通用GPU的kd-tree并行搜索算法，進而實現了ICP點云并行配準算法。首先建立目標點云的三維空間kd-tree，并使用OpenCL并行加速其搜索算法；然后將并行加速的kd-tree搜索算法運用于ICP算法，同時針對ICP算法的其他部分也使用OpenCL并行加速以確保配準過程盡可能高效。通過實驗驗證了所實現算法的高效性以及健壯性。

OpenCL GPU kd-tree 點云配準 ICP

0 引 言

隨著三維掃描技術的發展成熟與普及，三維應用技術得到了較好的發展。特別是在逆向工程、缺陷檢測、文物保護、醫學手術、3D打印以及游戲娛樂等領域獲得了廣泛的關注與研究。由于部分遮擋等問題，所以為了獲得完整的點云數據，需要進行多次掃描拼接配準。而三維點云配準一直以來都是三維掃描問題中的關鍵技術。

隨著三維掃描器材設備的不斷發展更新，掃描數據量不斷增大，傳統的配準算法隨著數據量的激增效率逐漸降低，無法滿足實時性的需求。圖形處理單元GPU、開放運算語言OpenCL以及計算機視覺與計算機圖形學的發展為解決相關大數據量的問題提供了通用的、高性能的并行計算環境，使得實時解決點云配準問題成為可能。本文基于OpenCL對kd-tree搜索算法并行加速，實現了高效并行的ICP[1]配準算法，對于提高配準算法的效率具有十分顯著的效果。

1 相關工作

點云配準算法通常是指ICP點云配準算法，該算法是通過迭代點云數據X={x1,x2,…,xnx}和Y={y1,y2,…,yny}反復迭代計算旋轉矩陣R與平移向量t，使得對應點的距離和最小，即通過下面的目標函數最小化實現點云的配準工作。

(1)

已有圍繞ICP配準算法做出的很多研究與改進，其中Zhang[2]提出引入kd-tree算法對搜尋對應點起到了很好的加速作用。Granger等[3]提出將最大期望算法EM(Expectation Maximization algorithm)算法應用到ICP中，較好地解決了ICP配準算法初始配準的問題。Rusinkiewicz等[4]對有關ICP配準算法所做的改進作了一個全面的分析與總結。Gold等人[5]提出了一種名為Softassign的配準算法，具有較好的配準效果。但是EM-ICP算法與Softassign算法由于算法本身的原因需要計算兩個點云數量相乘的矩陣，使得算法在點云數量集不斷增大的情況下，可行性與實時性急速降低。Tamaki等人[6]使用了CUDA(compute unified device architecture)對EM-ICP配準算法以及Softassign配準算法進行了并行優化，但實驗所使用的數量級也不能達不到數據量不斷增加的需求，并且CUDA目前只支持NVIDIA系列顯卡，不能做到對絕大多數CPU、顯卡等異構平臺的通用性支持。國內針對點云配準的研究也是基于CUDA的EM-ICP與Softassign算法的研究，其中蔡靜等人[7,8]采用的是下采樣的方法來降低配準數據的數據量。下采樣會對原始數據造成分辨率以及細節的缺失，本文認為這種做法是不太可取的。即使是下采樣過后，采用這兩種算法要求的計算數據量也是相當大的，這也是本文不采用這兩個算法的一個重要原因。

2 ICP配準算法

ICP配準算法即迭代最近點配準算法，是一種基于自由形態曲面的配準算法。對于兩個待匹配的點云數據集X和Y，在數據點集X中找到一點xi與Y點集中一點yi對應，使目標函數式(1)最小。而EM-ICP配準算法[4]由于引入了最大期望算法，它的目標函數為:

(2)

(3)

其中σp是參數，d0是初始已知值，αij為兩點為對應點的概率。同樣，Softassign配準算法[5]中引入了雙隨機矩陣，再運用近似均值優化以及模擬退火算法，其目標函數為：

(4)

因此EM-ICP與Softassign算法所計算的數據量為nx×ny，而ICP所需要計算的數據量為ny。

ICP配準算法如下：

輸入待配準點云數據X={x1,x2,…,xnx}和Y={y1,y2,…,yny}、R0、t0；

輸出配準結果R′和t′。

步驟1R0←I，t0←0；

步驟2for k=1，…，maxIterations do;

步驟3for each point yiin Y do;

步驟4尋找到最近的點xikin X：

步驟5end for;

步驟6建立對應于Y的Xk={x1k,x2k,…,xnyk}數據集;

步驟7利用四元數計算R′和t′;

步驟8Rk←R′，tk←t′;

步驟9end for。

有些研究學者認為ICP算法的關鍵問題不在于它的配準速度而在于其配準的精度，即ICP一直存在的初始位置的問題。當兩個點云的初始位置距離很遠或者重疊部分不是特別好時，ICP配準算法的效果是相當差的，這也是很多學者傾向于認為配準點云實際上是一種粗配準(又叫預配準)的原因。另一個角度而言，構建一個模型或者一個空間的掃描建模時，是可以控制相鄰點云數據的重疊以及距離的。因此，本文認為ICP算法在做掃描點云配準時還是優于其他配準算法，這也是本文用ICP算法做點云配準的主要原因。

3 kd-tree算法

kd-tree是一種分割k維數據空間的數據結構，主要應用于多維空間關鍵數據的搜索(如：范圍搜索和最近鄰搜索)。kd-tree是二進制空間分割樹的一種特殊情況。kd-tree由Zhang[2]首先引入到ICP算法中，用于最近鄰搜索。kd-tree算法分為兩個部分，第一部分為創建kd-tree，第二部分才是本文的目的:搜索最近鄰的節點。

創建kd-tree分為遞歸算法與非遞歸的算法，為提高效率，本文采用的是非遞歸算法。而搜索算法也是采用非遞歸式的搜索，因此本文將搜索算法分為兩個步驟，即先向下搜索直到葉子節點，找到第一個最近鄰參照節點，隨后利用父節點信息對滿足條件的節點進行回溯搜索。

4 基于OpenCL的并行算法

開放計算語言OpenCL是一個為異構平臺編寫程序的框架，此異構平臺可由CPU、GPU或其他類型的多核處理器組成。OpenCL為開發人員提供了基于任務分割和數據分割的并行計算機制以及一套支持C99標準的內核API與控制API，以幫助開發人員在GPU上運行一個并行的內核函數，充分提高算法運行效率。

4.1 GPU下的kd-tree算法

kd-tree的數據結構大大地方便了單個數據在k維空間中進行搜索，但是當需要搜索的數據量非常大時，kd-tree的搜索還是會比較遲緩的。因此，為了進一步提高算法的效率，將kd-tree算法運用OpenCL移植到GPU上，通過并行對多個數據同時進行搜索來達到提高算法效率的目的。

為方便地將kd-tree的節點數據傳輸到GPU下，使用一個數組的形式來存儲kd-tree的節點，將當前節點的子節點用一個整型數組來存儲它們的序號，以方便查找。同樣為了方便回溯查找可能的最近鄰節點，設置一個整型數據位表示父節點的序號。采用數組結構存儲kd-tree的節點主要是考慮到滿足GPU下全局內存的管理。對于GPU下建立kd-tree，本文方法會比直接使用CPU下的kd-tree繁瑣一點。首先，利用輸入的樣本集在CPU下建立kd-tree；然后將CPU下的kd-tree節點轉換為GPU下所支持的數組存儲形式；最后將kd-tree傳輸到GPU的全局內存中，用于搜索使用。下面主要介紹GPU下的最近鄰搜索算法。

本文所使用的kd-tree搜索算法分為三個步驟：第一步，從根節點向下根據kd-tree特性采用二分搜索；第二步，逐個比較葉子節點中所包含的樣本數據集，選取最近鄰節點；第三步，如果分支節點與待查詢節點距離小于第二步中得到的最近鄰節點與待查詢節點距離，采用回溯查找的策略以確定最近鄰節點，否則返回第二步中的結果。

GPU下的kd-tree最近鄰搜索算法如下：

輸入將kd-tree、點云數據集X和Y加載到GPU的全局內存；

輸出對應點點集與對應點點集所對應的歐氏距離。

步驟1分配n個線程，n為查詢的點集數量；

步驟2在GPU中為輸出分配相應的存儲空間；

步驟3對每一個線程并行執行kd-tree搜索程序：

(1) 如果kd-tree是空的，則設距離為無窮大并返回；

(2) 沿kd-tree樹向下搜索直到葉子結點；

(3) 如果分支節點與待查詢節點的距離小于步驟(2)中搜索到的最近鄰節點與待查詢節點的距離，則回溯搜索，以確定最近鄰節點；否則返回步驟(2)中的查詢結果。

步驟4將GPU內存中的結果拷貝到內存中。

在實驗中，發現了兩個問題：第一個是當數據量較大的時候，樹的深度在一定程度上影響著搜索算法的效率。根據實驗，本文將樹的最大深度定在13層會取得較好的結果，然后對葉節點中所包含的樣本數據集再采用逐個比較的方式選取最近鄰節點。第二個問題則是回溯算法的必要性問題。首先ICP算法本身就是一種采用最近鄰近似尋求對應節點以解決配準問題的一個算法。其次，kd-tree按照二維劃分所找到的近似最近鄰節點與真實最近鄰節點的差距十分小。回溯算法需要更新最近鄰節點的可能性也不是特別高。按照以上分析，本文做了關于回溯算法必要性以及回溯棧大小的影響的實驗。本文將在第5節給出實驗結果。

4.2 GPU下的ICP算法

原始的ICP算法主要包括三大步驟：第一步是利用最近鄰搜索查找對應點；第二步是利用四元數估計變換矩陣；第三步是通過變換矩陣轉換數據。當目標方程達到誤差標準時，退出算法，否則轉到第一步繼續執行。這三個步驟構成了ICP算法的基本結構，除第一步的對應點搜索外，其他兩步包含大量的矩陣操作。第二步包含兩個點云的交叉協方差矩陣與重心的計算都可以使用GPU加速。此外，第三步數據的轉換其實就是兩個矩陣相乘，因此也可以運用GPU加速，以提高算法的效率。

Bouaziz等人[9]提出了一種新的衡量ICP算法的目標方程，稱作lp-ICP。即式(1)可改為：

(5)

該算法在文獻[9]中得到證實，當p∈[0,1]的區間內時，可以有效地減少錯誤的對應點以及噪聲點對算法的影響，以提高ICP算法配準的精度。但由于該文獻采用了一種優化算法，迭代優化次數比較多，算法的執行時間比較長。本文簡單地將這個方法使用在原始的ICP算法中用來排除錯誤對應點以及噪聲點的影響，提高配準的精度。

5 實驗結果及分析

本文將通過三個不同實驗設計來驗證本文所實現的算法，分別驗證本文算法的運行效率與配準的精度。實驗的編譯環境為：Ubuntu 12.04 64位。實驗的硬件環境為：CPU為i7-4770處理器，主頻3.40 GHz；GPU為AMD HD8490顯卡，顯存為1 GB，位寬為64位，主頻為875 MHz，流處理器160個，該顯卡屬于低端顯卡。NVIDIA顯卡只需一個流處理器就能發揮作用，而AMD的顯卡對流處理器定位不一樣，要5個流處理器單元一組才能工作。實驗所用數據為Kinect拍攝的室內場景。實驗數據以及效果如圖1和圖2所示。

圖1 拍攝數據實驗效果

圖2 斯坦福兔子實驗效果

5.1 基于OpenCL下的ICP與CPU下的ICP比較

將本文的算法與未使用OpenCL加速的情況下以及Open PCL(Open Point Cloud Library)中所實現的ICP算法進行了運行效率對比，本文改進后算法具有較好的效率，特別是使用OpenCL并行加速之后的算法，效率有了較大的提升。實驗結果如圖3所示。

PCL-ICP為PCL庫中的ICP算法，KDtree-ICP為本文優化之后使用kd-tree所實現的ICP算法，OpenCL-ICP為本文最后實現的基于OpenCL的ICP算法。由于本文盡可能簡化、優化kd-tree算法，使得該算法更適用于ICP算法，從實驗結果中可以明顯發現改進之后的算法在相同的實驗環境下比PCL庫中所實現的算法有了較好的提高。而從實驗中可以明顯看到使用OpenCL之后的算法的執行效率有了較大的提升，但由于GPU計算核心的限制，在數據量較大時，算法的效率還是不夠理想。如果采用性能更好的顯卡，可以獲得更好的結果。

5.2 回溯棧的大小對算法的影響

本文在實驗中發現回溯棧的大小對算法具有較大的影響。首先從ICP算法本身考慮，ICP算法本身就是通過最近鄰節點近似表示對應點，通過kd-tree進行篩選之后的節點對于搜索點已經是一個十分近似的最近鄰節點，理論上足以用來表示近似最近鄰節點。再從kd-tree的構造上來看，本文并不是將kd-tree一直劃分到只剩下一個節點，而是將樹建到一定的深度就不再往下繼續劃分子樹。因此每個葉子節點中包含有多個數據節點，在搜索過程中當搜索到葉子節點時是采用逐一比較的方法確定最近節點，這樣就再一次從概率的角度縮小了需要再次回溯找到最近鄰節點的概率。實驗所用數據量為298 227，實驗結果如圖4所示。

圖3 算法效率的實驗 圖4 回溯棧大小對算法的影響

在實驗中發現，隨著回溯棧的增大，算法的效率會逐漸降低，但是會有一個最高點；而算法配準的精度當回溯棧大于1之后就沒有太大的變化。這樣就剛好驗證了本文之前的假設：kd-tree算法需要回溯更新最近鄰節點的概率比較小，或者說大部分的回溯都是無用的，抑或回溯一次與第一次找到的最近鄰節點已經足以表示近似最近鄰節點。

5.3 lp-ICP目標函數的影響

根據Bouaziz等人[9]的方法，為了使算法簡單，本文只使用了文獻[9]中所使用的目標函數來替代本文中使用的目標函數進行實驗。可能由于實驗中并沒有使用該文獻所采用的優化算法，算法配準精度的提升并不明顯，但是隨著實驗所取p值的減小，算法的配準精度整體是提高的。

6 結 語

點云配準一直都影響著逆向工程、掃描建模以及模式識別等重要領域。本文根據實驗以及算法特性優化kd-tree算法，以使其更適用于ICP點云配準算法。并使用OpenCL平臺，運用通用的GPU并行加速技術，實現并行ICP點云配準算法，在一定程度上提高了算法的執行效率，在實際應用中具有一定的價值。傳統ICP算法由于采用最近鄰查找對應點的算法特性，使得該算法很容易陷入局部最優而導致錯誤的配準結果。但本文并沒有考慮這一影響，所以接下來的工作是如何能夠較好地對任意輸入的待配準數據進行初始配準，使算法在任意輸入下都具有較好的健壯性。

[1] Besl P J,Mckay N D.A method for registration of 3-d shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2):239-256.

[2] Zhang Z Y.Iterative Point Matching for Registration of Free-From Curves and Surfaces[J].International Journal of Computer Vision,1994,13(2):119-152.

[3] Granger S,Pennec X.Multi-scale EM-ICP:A Fast and Robust Approach for Surface Registration[C]//Proceedings of the 7th European Conference on Computer Vision (ECCV2002),2002:418-432.

[4] Rusinkiewicz S,Levoy M.Efficient Variants of the ICP Algorithm[C]//Proceedings of the 3rd International Conference on 3-D Digital Imaging and Modeling,2001:145-152.

[5] Gold S,Rangarajan A,Lu C P,et al.New algorithms for 2D and 3D point matching: pose estimation and correspondence[J].Pattern Recognition,1998,31(8):1019-1031.

[6] Tamaki T,Abe M,Raytchev B,et al.Softassign and EM-ICP on GPU[C]//Proceedings of the 2010 1st International Conference on Networking and Computing.Washington DC,USA:IEEE Computer Society,2010:179-183.

[7] 蔡靜,董琳,孫曉鵬.3D人耳點云配準的并行Softassign算法[J].計算機工程與設計,2013,34(10):3629-3634.

[8] 董琳,何揚.基于EM-ICP的三維人臉簡化點云并行配準算法[J].微型機與應用,2013,32(16):38-41.

[9] Bouaziz S,Tagliasacchi A,Pauly M.Sparse Iterative Closest Point[J].Computer Graphics Forum,2013,32(5):113-123.

PARALLEL REGISTRATION ALGORITHM OF ICP POINT CLOUD BASED ON OPENCL

Liu Zhongjian

(CollegeofComputer,NorthChinaUniversityofTechnology,Beijing100144,China)

In view of the problem of too low efficiency the current point cloud registration algorithm has, by using OpenCL we achieved the general GPU-based kd-tree parallel search algorithm, and then realised the parallel ICP point cloud registration algorithm. First we established the three-dimensional kd-tree of target point cloud, and used the OpenCL to parallelly accelerate its search algorithm. Then we applied the parallelly accelerated kd-tree search algorithm in ICP algorithm, at the same time the OpenCL parallel acceleration was also used aimed at the rest part of ICP algorithm to ensure as much as possible the efficient registration process. Experiments verified the efficiency and robustness of the implemented algorithm.

OpenCL GPU kd-tree Point cloud registration ICP

2015-05-16。國家自然科學基金項目(61202229)；北京市自然科學基金項目(4132018)。劉忠建，碩士生，主研領域：計算機圖形學。

TP391.41

A

10.3969/j.issn.1000-386x.2016.11.043