劉 忠 建

(北方工業(yè)大學(xué)計算機學(xué)院 北京 100144)

?

基于OpenCL的ICP點云并行配準(zhǔn)算法

劉 忠 建

(北方工業(yè)大學(xué)計算機學(xué)院 北京 100144)

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

OpenCL GPU kd-tree 點云配準(zhǔn) ICP

0 引 言

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

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

1 相關(guān)工作

點云配準(zhǔn)算法通常是指ICP點云配準(zhǔn)算法，該算法是通過迭代點云數(shù)據(jù)X={x1,x2,…,xnx}和Y={y1,y2,…,yny}反復(fù)迭代計算旋轉(zhuǎn)矩陣R與平移向量t，使得對應(yīng)點的距離和最小，即通過下面的目標(biāo)函數(shù)最小化實現(xiàn)點云的配準(zhǔn)工作。

(1)

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

2 ICP配準(zhǔn)算法

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

(2)

(3)

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

(4)

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

ICP配準(zhǔn)算法如下：

輸入待配準(zhǔn)點云數(shù)據(jù)X={x1,x2,…,xnx}和Y={y1,y2,…,yny}、R0、t0；

輸出配準(zhǔn)結(jié)果R′和t′。

步驟1R0←I，t0←0；

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

步驟3for each point yiin Y do;

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

步驟5end for;

步驟6建立對應(yīng)于Y的Xk={x1k,x2k,…,xnyk}數(shù)據(jù)集;

步驟7利用四元數(shù)計算R′和t′;

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

步驟9end for。

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

3 kd-tree算法

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

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

4 基于OpenCL的并行算法

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

4.1 GPU下的kd-tree算法

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

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

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

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

輸入將kd-tree、點云數(shù)據(jù)集X和Y加載到GPU的全局內(nèi)存；

輸出對應(yīng)點點集與對應(yīng)點點集所對應(yīng)的歐氏距離。

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

步驟2在GPU中為輸出分配相應(yīng)的存儲空間；

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

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

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

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

步驟4將GPU內(nèi)存中的結(jié)果拷貝到內(nèi)存中。

在實驗中，發(fā)現(xiàn)了兩個問題：第一個是當(dāng)數(shù)據(jù)量較大的時候，樹的深度在一定程度上影響著搜索算法的效率。根據(jù)實驗，本文將樹的最大深度定在13層會取得較好的結(jié)果，然后對葉節(jié)點中所包含的樣本數(shù)據(jù)集再采用逐個比較的方式選取最近鄰節(jié)點。第二個問題則是回溯算法的必要性問題。首先ICP算法本身就是一種采用最近鄰近似尋求對應(yīng)節(jié)點以解決配準(zhǔn)問題的一個算法。其次，kd-tree按照二維劃分所找到的近似最近鄰節(jié)點與真實最近鄰節(jié)點的差距十分小?；厮菟惴ㄐ枰伦罱徆?jié)點的可能性也不是特別高。按照以上分析，本文做了關(guān)于回溯算法必要性以及回溯棧大小的影響的實驗。本文將在第5節(jié)給出實驗結(jié)果。

4.2 GPU下的ICP算法

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

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

(5)

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

5 實驗結(jié)果及分析

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

圖1 拍攝數(shù)據(jù)實驗效果

圖2 斯坦福兔子實驗效果

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

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

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

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

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

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

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

5.3 lp-ICP目標(biāo)函數(shù)的影響

根據(jù)Bouaziz等人[9]的方法，為了使算法簡單，本文只使用了文獻(xiàn)[9]中所使用的目標(biāo)函數(shù)來替代本文中使用的目標(biāo)函數(shù)進(jìn)行實驗?？赡苡捎趯嶒炛胁]有使用該文獻(xiàn)所采用的優(yōu)化算法，算法配準(zhǔn)精度的提升并不明顯，但是隨著實驗所取p值的減小，算法的配準(zhǔn)精度整體是提高的。

6 結(jié) 語

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

[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人耳點云配準(zhǔn)的并行Softassign算法[J].計算機工程與設(shè)計,2013,34(10):3629-3634.

[8] 董琳,何揚.基于EM-ICP的三維人臉簡化點云并行配準(zhǔn)算法[J].微型機與應(yīng)用,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。國家自然科學(xué)基金項目(61202229)；北京市自然科學(xué)基金項目(4132018)。劉忠建，碩士生，主研領(lǐng)域：計算機圖形學(xué)。

TP391.41

A

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