王育堅，廉騰飛，吳明明，高 倩

(北京聯(lián)合大學(xué) 信息學(xué)院，北京 100101)

基于八叉樹與KD樹索引的點云配準(zhǔn)方法

王育堅，廉騰飛，吳明明，高 倩

(北京聯(lián)合大學(xué) 信息學(xué)院，北京 100101)

針對點云配準(zhǔn)算法中KD樹多維查詢效率較低的問題，提出一種基于八叉樹和KD樹多層索引結(jié)構(gòu)的點云配準(zhǔn)方法。首先為模型點云數(shù)據(jù)建立八叉樹全局索引，然后在八叉樹葉子結(jié)點構(gòu)建局部數(shù)據(jù)的KD樹索引。對傳統(tǒng)的ICP點云配準(zhǔn)算法進行改進，通過葉子結(jié)點的全局索引值快速定位局部點云數(shù)據(jù)塊，利用局部KD樹索引加快最近點的搜索，計算最近點時利用歐氏距離閾值、點對距離差值和法向量閾值剔除部分噪聲點。實驗表明，改進算法提高了點云配準(zhǔn)的效率和精度。

點云配準(zhǔn)；八叉樹；KD樹；ICP算法

三維重建在計算機視覺、虛擬現(xiàn)實、3D打印和逆向工程等方面有著廣泛的應(yīng)用，點云數(shù)據(jù)配準(zhǔn)方法的優(yōu)劣直接影響三維重建的效果。利用三維掃描儀多次掃描物體表面，得到不同視角下的三維點云數(shù)據(jù)，將掃描得到的多片點云數(shù)據(jù)進行配準(zhǔn)，即可得到完整的模型[1]。點云配準(zhǔn)包括粗配準(zhǔn)和精配準(zhǔn)，粗配準(zhǔn)的目的是為精配準(zhǔn)提供良好的初值，縮小相鄰點云之間的旋轉(zhuǎn)誤差和平移誤差。精配準(zhǔn)的目的是找到最合適的旋轉(zhuǎn)矩陣和平移矩陣，使得相鄰點云配準(zhǔn)的誤差最小。

目前應(yīng)用最廣泛的點云配準(zhǔn)算法是迭代最近點(Iterative Closest Point，ICP)算法[2]及其改進算法。ICP算法作為一種基于純粹幾何模型的配準(zhǔn)方法，人們提出了多種改進方案[3]，改進的基本思路主要體現(xiàn)在點云數(shù)據(jù)模型設(shè)計和最近點搜索策略兩個方面[4-5]。例如，在點云數(shù)據(jù)模型設(shè)計方面，利用Delaunay三角剖分[6]、KD樹[7]等對ICP算法進行改進。在實際應(yīng)用過程中，對于數(shù)據(jù)量很大的點云數(shù)據(jù)，ICP算法配準(zhǔn)耗時較長，影響了算法效率。本文基于八叉樹和KD 樹的多層索引結(jié)構(gòu)，提出一種點云精配準(zhǔn)的改進方法。

1 點云數(shù)據(jù)結(jié)構(gòu)

1.1 八叉樹結(jié)構(gòu)和KD樹結(jié)構(gòu)

八叉樹結(jié)構(gòu)是一種規(guī)則的數(shù)據(jù)結(jié)構(gòu)，利用樹形結(jié)構(gòu)對模型進行遞歸，按X，Y，Z3個不同方向，將所要表示的三維空間實體分割成8個大小相等的子立方體。然后根據(jù)每個子立方體中所含的目標(biāo)來決定是否對子立方體繼續(xù)進行8等分的劃分，一直劃分到每個子立方體被一個目標(biāo)所充滿，或沒有目標(biāo)，或其大小已成為預(yù)先規(guī)定的體素為止。八叉樹分解是將三維空間實體逐級分解，最終形成八叉樹體素表示的結(jié)構(gòu)。八叉樹的主要優(yōu)點是可以方便地實現(xiàn)物體的并、交、差等集合運算，適用于不同形狀物體的建模。

KD樹是一種把二叉查找樹推廣到多維數(shù)據(jù)的結(jié)構(gòu)，實現(xiàn)多維空間數(shù)據(jù)的組織和存儲。KD樹利用超平面把一個空間劃分成多個不相交的子空間，每一層都將所包含的空間分成兩個子空間，頂層結(jié)點按一維劃分，下一層結(jié)點按另一維劃分，KD樹所有維的屬性在層間循環(huán)。任何一個非葉子結(jié)點的左右子樹也是KD樹，若結(jié)點的左子樹不為空，則左子樹上所有結(jié)點第d維的值均小于根結(jié)點第d維的值；若結(jié)點的右子樹不為空，則右子樹上所有結(jié)點第d維的值均大于等于根結(jié)點第d維的值。

KD樹每一個結(jié)點劃分結(jié)束的條件是結(jié)點中只包含一個數(shù)據(jù)或少于設(shè)定的上限為止。KD樹可以用來建立多維空間數(shù)據(jù)集或數(shù)據(jù)塊的索引。利用KD樹進行數(shù)據(jù)查詢時，每一步結(jié)點的條件判斷只要比較其中的一個維。通過交替比較不同維的屬性值，可以快速查找某個數(shù)據(jù)點的鄰域，不需要知道數(shù)據(jù)之間的任何拓?fù)潢P(guān)系。

1.2 多層索引結(jié)構(gòu)設(shè)計

KD樹通過左右孩子指針建立數(shù)據(jù)關(guān)系，索引指針數(shù)據(jù)占據(jù)了大量的內(nèi)存空間。KD樹采用一分為二的分割方式，由于點云數(shù)據(jù)量巨大，使得樹的深度很大，增加了數(shù)據(jù)查找的時間，但影響KD樹搜索效率的主要因素是回溯[8]。八叉樹結(jié)構(gòu)規(guī)則統(tǒng)一，樹的深度大大降低，對于精確數(shù)據(jù)點查找，其性能較高[9]。但八叉樹的動態(tài)性較差，在數(shù)據(jù)點集分布不均勻的情況下，樹的平衡性不好。

考慮到八叉樹數(shù)據(jù)存儲結(jié)構(gòu)特點和KD樹搜索有效性，提出一種八叉樹與KD樹相結(jié)合的多層索引結(jié)構(gòu)。設(shè)待配準(zhǔn)點云為P，模型點云為Q?；谀Ｐ忘c云Q建立多層索引結(jié)構(gòu)，在上層采用八叉樹結(jié)構(gòu)存儲和管理全局的點云數(shù)據(jù)，在下層利用KD樹組織和存儲局部的點云數(shù)據(jù)，每個局部KD樹索引的信息都保存在八叉樹末端關(guān)聯(lián)的葉結(jié)點中。全局八叉樹和局部KD樹的多層索引結(jié)構(gòu)如圖1所示，其中的虛線框內(nèi)表示八叉樹葉結(jié)點與KD樹的對應(yīng)關(guān)系。

圖1 多層索引結(jié)構(gòu)

根據(jù)這種多層索引結(jié)構(gòu)，首先自上而下采用八叉樹結(jié)構(gòu)對模型點云進行空間分割。根據(jù)模型點云的最小和最大坐標(biāo)，得到一個包圍整個模型的立方體，該立方體作為八叉樹的根結(jié)點。將該立方體分解成8個子立方體，作為8個孩子結(jié)點。根據(jù)配準(zhǔn)精度要求確定八叉樹的分割參數(shù)，得到每個葉子結(jié)點點云所包含最大的點數(shù)。當(dāng)葉子結(jié)點內(nèi)的點云數(shù)目小于最大點數(shù)時，結(jié)束八叉樹的分解，不必像傳統(tǒng)八叉樹那樣直到結(jié)點只有一個數(shù)據(jù)點或有限的數(shù)據(jù)點時才結(jié)束分解。

當(dāng)利用八叉樹分割點云模型生成葉子結(jié)點后，在八叉樹非空的葉子結(jié)點設(shè)置指針值，指向關(guān)聯(lián)的KD樹。KD樹將八叉樹葉子結(jié)點中的點云數(shù)據(jù)一分為二，劃分為兩個子空間，然后再對每一個子空間進一步進行遞歸劃分，最后得到一棵完整的KD樹，即所有含有點云數(shù)據(jù)的葉子結(jié)點都建立關(guān)聯(lián)的KD樹。創(chuàng)建KD樹采用一種改進的方法，即先對3個軸都進行采樣[7]，然后選擇合適的軸進行劃分，以保證每次劃分都能找到近似最優(yōu)的分割位置。

全局八叉樹是第一層索引，局部KD樹是建立在八叉樹葉子結(jié)點之下的第二層索引。通過分割參數(shù)設(shè)定八叉樹葉子結(jié)點的數(shù)據(jù)量，如果設(shè)置的分割參數(shù)很大，則葉子結(jié)點關(guān)聯(lián)的局部點云數(shù)據(jù)很多，KD樹的深度較大，會降低KD樹的搜索效率；反之，如果將結(jié)點劃得很細(xì)，雖然KD樹的深度降低，但增加了邊界數(shù)據(jù)點的數(shù)量，勢必影響配對的精度。因此，生成八叉樹時要綜合考慮模型的空間形狀、點元數(shù)據(jù)規(guī)模和配準(zhǔn)精度的要求，通過實驗分析得出接近于最佳搜索的分割參數(shù)。

與傳統(tǒng)的KD樹相比，多層索引結(jié)構(gòu)需要額外的空間存儲八叉樹，但由于八叉樹沒有分割到只有一個數(shù)據(jù)點才結(jié)束，八叉樹的深度是可以控制的，需要的附加空間并不大。并且，結(jié)點之間的層次關(guān)系可以根據(jù)結(jié)點編碼得到，配準(zhǔn)時定位八叉樹的葉子結(jié)點并不需要回溯，因此，八叉樹每個結(jié)點可以不存儲其父結(jié)點的指針，減少了模型的存儲空間。

多層索引結(jié)構(gòu)的八叉樹結(jié)點用一個屬性值表示葉子結(jié)點與KD樹的關(guān)聯(lián)，若八叉樹葉子結(jié)點的屬性值為“KD”，表示該葉子結(jié)點鏈接一個局部的KD樹。通過葉子結(jié)點與其對應(yīng)KD樹的根結(jié)點的關(guān)聯(lián)，形成局部KD樹索引。搜索時根據(jù)待配準(zhǔn)點的坐標(biāo)和子立方體空間屬性值快速完成最近點的自適應(yīng)定位，最近點的搜索局限于數(shù)據(jù)點所在八叉樹葉子結(jié)點的包圍盒內(nèi)，避免了回溯八叉樹。

將索引代價較小的八叉樹與KD樹相關(guān)聯(lián)，利用空間分塊策略設(shè)計多層索引，這種索引結(jié)構(gòu)在保證滿足配準(zhǔn)精度的前提下，能夠大大優(yōu)化最近點的搜索性能。建立全局八叉樹和局部KD樹多層索引結(jié)構(gòu)的算法如下：

1)根據(jù)模型點云Q的大小選取一個包圍盒立方體，將該立方體作為八叉樹的根結(jié)點。

2)若當(dāng)前結(jié)點包含的數(shù)據(jù)點數(shù)大于規(guī)定的點數(shù)，采用深度優(yōu)先策略對該結(jié)點進行八叉樹遞歸分解，將立方體分解成8個子立方體。

3)若當(dāng)前結(jié)點包含的點數(shù)小于或等于規(guī)定的點數(shù)，停止分解，該結(jié)點為八叉樹的葉子結(jié)點，生成結(jié)點數(shù)據(jù)域，設(shè)置結(jié)點的“KD”屬性值。

4)針對八叉樹葉子結(jié)點包含的局部點云數(shù)據(jù)創(chuàng)建KD樹。根據(jù)3個軸的采樣選擇劃分的坐標(biāo)軸，將八叉樹葉結(jié)點的點云數(shù)據(jù)一分為二，劃分為兩個平面；再對每個平面進一步遞歸劃分，直到生成KD樹的每一個結(jié)點。生成KD樹后，建立八叉樹葉子結(jié)點與KD樹的索引。

5)將當(dāng)前指針指向八叉樹的下一個結(jié)點，重復(fù)步驟2)，直到處理完所有八叉樹結(jié)點。

2 改進的點云配準(zhǔn)算法

2.1 ICP算法的最近點搜索

ICP算法根據(jù)一定的準(zhǔn)則確立對應(yīng)點集P與Q，通過最小二乘法迭代計算最優(yōu)的坐標(biāo)變換，即旋轉(zhuǎn)矩陣和平移矢量，將一個坐標(biāo)系下的點數(shù)據(jù)變換到另一個坐標(biāo)系，并使得誤差函數(shù)最小。點云配準(zhǔn)可以看作是求解變換矩陣的過程，決定ICP算法坐標(biāo)變換的關(guān)鍵在于能否在模型點云Q中準(zhǔn)確、快速地找到P中待配準(zhǔn)點的最近點。因此，影響ICP算法效率和精度的主要因素是最近點的搜索方法[10]。

研究者基于最近點搜索提出多種ICP的改進方法。文獻[11]提出基于重疊區(qū)域的近似KD樹，在搜索重疊區(qū)域的子結(jié)點時不回溯，提高了搜索效率和精度。文獻[12]基于點云單應(yīng)性假設(shè)提出一種采用點和面對應(yīng)的ICP改進算法，利用單應(yīng)性剔除其余點對，算法具有較好的穩(wěn)健性和收斂性。文獻[13]在K近鄰搜索中使用OKDT正交搜索樹，利用主成分分析方法計算點集方差最大的正交軸方向，按照優(yōu)化KD樹劃分方法劃分子樹，當(dāng)點云數(shù)據(jù)量很大時該方法具有較好的搜索性能。此外，文獻[14]根據(jù)模型點集的各維方差按坐標(biāo)軸排序，能夠快速搜索最近點搜索范圍的邊界。文獻[15]采用點云歐氏距離閾值和方向矢量夾角閾值去噪。文獻[16]提出曲率約束與對應(yīng)點距離約束相結(jié)合的自適應(yīng)噪點剔除策略。文獻[5]首先采用中心重合法實現(xiàn)點云數(shù)據(jù)的粗配準(zhǔn)，然后利用KD樹快速搜索最近點對，完成點云數(shù)據(jù)的精配準(zhǔn)。上述算法都在不同情況下提高了搜索的效率或精度。

2.2 基于KD樹最近鄰搜索算法的改進

通常情況下，計算P中每個點p的最近點，需要計算p與Q中所有點的歐氏距離。局部KD樹是針對八叉樹葉子結(jié)點的點云數(shù)據(jù)塊建立的，通過模型點云的八叉樹和KD樹多層索引可以快速定位p的最近點所在的數(shù)據(jù)塊，可以避免搜索所有點。最近點的搜索過程分為兩步：第一步搜索全局索引層，通過搜索模型點云八叉樹，定位最近點所在的點云數(shù)據(jù)塊，即找到包含最近點的八叉樹葉子結(jié)點；第二步，根據(jù)八叉樹葉子結(jié)點中存儲的信息找到對應(yīng)的KD樹根結(jié)點，即存儲局部數(shù)據(jù)塊的KD樹，然后在局部點云數(shù)據(jù)塊中搜索最近鄰域點。

影響KD樹最近鄰搜索效率的主要因素是回溯，八叉樹結(jié)點存儲了相關(guān)的數(shù)據(jù)信息，不需要回溯就可以定位包含最近鄰域點的局部點云塊。八叉樹中的每一個結(jié)點都對應(yīng)一個空間包圍盒，根據(jù)待配準(zhǔn)點坐標(biāo)pi(xi,yi,zi)與包圍盒的空間位置和大小，確定需要繼續(xù)搜索的八叉樹葉子結(jié)點。設(shè)最近鄰域點qj(xj,yj,zj)所在子立方體的空間索引值為(a,b,c)，與子立方體對應(yīng)的結(jié)點的八進制編碼為q=qn-1…qj…q1q0，qj(j=0, 1, … ,n-1 )表示葉結(jié)點到根結(jié)點的路徑。根據(jù)式(1)可以得到八叉樹中最近鄰域點所在子立方體的全局索引值。

(1)

在局部KD樹搜索最近鄰域點時，對于位于分割子體邊界上的點，搜索的結(jié)果有可能是錯誤的，可以將邊界點作為噪聲點處理，由于點云數(shù)據(jù)量巨大，這樣處理提高了配準(zhǔn)速度，而對精度沒有太大的影響。研究表明，如果允許有少量錯誤的搜索結(jié)果，KD樹的搜索效率會得到很大的提高[10]。

改進算法利用歐氏距離閾值剔除噪聲點[15]。通過模型點云八叉樹葉子結(jié)點關(guān)聯(lián)的KD樹，搜索與點pi歐式距離最近的3個點s1，s2和s3；若pi與s1，s2，s3構(gòu)成的平面的距離超出閾值E，則剔除該對應(yīng)點；否則，以這3個點中距離pi最近的點sj作為對應(yīng)點。閾值為E=c*d，其中c為控制系數(shù)，d為點云中相鄰點間的平均距離。此外，邊界噪聲點也有可能形成多個對應(yīng)點對，可以比較兩組對應(yīng)點對p1和q1，p2和q2，若出現(xiàn)式(2)情況，即它們之間的差超過F，則視為噪聲點，也予以剔除。

|dist(p1-p2)-dist(q1-q2)|≥F.

(2)

利用歐氏距離閾值雖然剔除了大量的噪聲點，但對應(yīng)點對仍然存在噪聲點?？紤]到待配準(zhǔn)點云和模型點云雖然處于不同的坐標(biāo)系，但其空間拓?fù)潢P(guān)系應(yīng)該一致，點云之間除了有平移量，還有旋轉(zhuǎn)量。因此，對匹配點對的法向量夾角設(shè)置一個閾值，以進一步剔除錯誤的點對。

(3)

應(yīng)用最小二乘法，可以得到以下3*3矩陣A。

(4)

可以證明，A的最小特征值對應(yīng)的特征向量即可作為法向量ni的近似值。

通過以上方法得到兩個對應(yīng)點集中各點的法向量。對于任意對應(yīng)點對pi和qj，它們的法向量分別為ni和nj。兩者的法向量差別越大，夾角的余弦值越小，即ni·nj就越小。因此，根據(jù)式(5)對向量夾角余弦設(shè)置閾值，即將法向量的乘積小于G的點對視為噪聲點，予以剔除。

ni·nj≥G.

(5)

2.3 算法步驟

改進的點云配準(zhǔn)算法的主要步驟如下：

1)針對模型點云Q建立八叉樹與KD樹多層索引結(jié)構(gòu)。

2)迭代初始化：選擇初始目標(biāo)點集P0=P，設(shè)定最大迭代次數(shù)Kmax，給定法向閾值V。

3)根據(jù)待配準(zhǔn)點云Pk中的每個點pi的坐標(biāo)pi(xi,yi,zi)和八叉樹子立方體包圍盒的空間位置及大小(x,y,z,l)，在八叉樹中定位最近點qi所在的葉子結(jié)點。

4)通過八叉樹的葉子結(jié)點找到包含局部點云的KD樹，基于KD樹搜尋數(shù)據(jù)點集Pk中每一個點pi的最近點，得到對應(yīng)點集Qk。

5)利用歐氏距離閾值和點對距離差值剔除部分噪聲點。

6)根據(jù)法向量閾值剔除錯誤的匹配點對。

7)利用四元數(shù)法對式(6)進行最小化，求出旋轉(zhuǎn)矩陣Rk和平移矢量Tk。

(6)

8)根據(jù)旋轉(zhuǎn)矩陣Rk和平移矢量Tk得到新的數(shù)據(jù)點集：Pk+1=RkPk+Tk。

9)R=RkR,T=RkT+Tk，重復(fù)進行步驟3)～8)，直至前一次最近點之間的距離與后一次最近點之間的距離滿足條件：dk-dk+1

10)利用變換矩陣參數(shù)R和T將初始目標(biāo)點云數(shù)據(jù)變換到參考點云所在的坐標(biāo)系，完成點云數(shù)據(jù)的配準(zhǔn)。

設(shè)模型點云Q有N個數(shù)據(jù)點，待配準(zhǔn)點云P有M個數(shù)據(jù)點，模型點集中數(shù)據(jù)點的總數(shù)N與八叉樹一個葉子結(jié)點包含的數(shù)據(jù)點之比為K(分割參數(shù))，模型點云八叉樹深度為h?？梢运愠觯瞬鏄涿總€葉子結(jié)點包含的點數(shù)為N/K，葉子結(jié)點數(shù)為K，將八叉樹簡化為滿八叉樹處理，可以計算出八叉樹深度為

h≥|log8K|+1.

(7)

對于有M個數(shù)據(jù)點的待配準(zhǔn)點云P，對應(yīng)八叉樹的搜索時間為O(Mlog8K)；在局部模型點云塊KD樹中搜索最近點，時間為O(Mlog2(N/K))。因此，搜索最近鄰的總時間為

O(Mlog8K+O(Mlog2(N/K)).

(8)

研究表明[14]，在實例隨機分布的情況下，KD樹最近鄰的深度優(yōu)先搜索的時間為O(Mlog2N)，在最差回溯情況下的時間為O(3MN2/3)。因此，在保證配準(zhǔn)精度的前提下，選擇合適的K值，滿足式(9)就能保證改進后的算法優(yōu)于隨機條件下的傳統(tǒng)KD樹最近鄰搜索算法。

Mlog8K+Mlog2N/K

(9)

即：

log8K

(10)

顯然很容易滿足上述算式，分割參數(shù)K越大，即點云模型分割越細(xì)，時間效率越高，當(dāng)然，前提是需要保證配準(zhǔn)的精度。

3 實驗與分析

為了驗證改進算法的正確性和有效性，分別選擇了三組點云模型進行配準(zhǔn)實驗。實驗的系統(tǒng)環(huán)境為內(nèi)存4G、Window7操作系統(tǒng)，軟件為MATLAB R2014a。第一組實驗選擇經(jīng)典的Bunny模型，圖2(a)為配準(zhǔn)前的點云(灰色部分表示模型點云，黑色部分表示待配準(zhǔn)點云)，待配準(zhǔn)點云包含10 753個點。圖2(b)為傳統(tǒng)ICP算法的配準(zhǔn)結(jié)果，平均配準(zhǔn)時間為26.588 s。圖2(c)為本文改進算法的配準(zhǔn)結(jié)果，平均配準(zhǔn)時間為9.695 s。實驗結(jié)果顯示，采用本文提出的改進算法，配準(zhǔn)速度大大提高，同時配準(zhǔn)精度得到改善。

圖2 Bunny模型配準(zhǔn)

第2組實驗采用David 3D三維掃描儀，從兩個不同角度分別對一個瓶子模型進行掃描，對獲得的兩個點云模型先粗配準(zhǔn)再精配準(zhǔn)。圖3(a)為精配準(zhǔn)前的點云，待配準(zhǔn)點云包含2 473個點。圖3(b)為傳統(tǒng)ICP算法的配準(zhǔn)結(jié)果，平均配準(zhǔn)時間為3.785 s。圖3(c)為本文改進算法的配準(zhǔn)結(jié)果，平均配準(zhǔn)時間為2.327s。第3組實驗采用Cat模型，圖4(a)為配準(zhǔn)前的點云，待配準(zhǔn)點云包含21 530個點。圖4(b)為傳統(tǒng)ICP算法的配準(zhǔn)結(jié)果，平均配準(zhǔn)時間為87. 829 s。圖4(c)為本文改進算法的配準(zhǔn)結(jié)果，平均配準(zhǔn)時間為22.451 s。

對于不同規(guī)模的點云模型分別采用傳統(tǒng)ICP算法、文獻[15]提出的算法和本文提出的改進算法進行配準(zhǔn)，不同規(guī)模點云情況下3種算法的配準(zhǔn)時間如表1所示，3種算法的配準(zhǔn)精度如表2所示?？梢钥闯觯疚氖紫壤冒瞬鏄鋵臻g進行分割，建立局部KD樹索引，有效減少最近鄰搜索時間，使算法的效率有較大的提高，并且在精度上有較好的改善。在數(shù)據(jù)量非常大的海量點云情況下，降低配準(zhǔn)時間的效果更加明顯。

圖3 杯子模型配準(zhǔn)

圖4 Cat模型配準(zhǔn)

表1 不同數(shù)據(jù)規(guī)模點云配準(zhǔn)的時間比較

表2 不同數(shù)據(jù)規(guī)模點云配準(zhǔn)的精度比較

為了分析分割參數(shù)K對最近鄰搜索效率和配準(zhǔn)精度的影響，分別采用有5 456、10 753、21 530個點的點云模型進行實驗。圖5所示是不同分割參數(shù)K對最近鄰搜索時間的影響，圖6所示是不同分割參數(shù)K對配準(zhǔn)精度的影響。顯然，K越大，搜索效率越高，但誤差越大。對于不同形狀的三維點云模型，通過反復(fù)實驗和分析，可以得到接近于最佳效率和精度的分割參數(shù)K值。

圖5 分割參數(shù)K對搜索時間的影響

圖6 分割參數(shù)K對配準(zhǔn)精度的影響

4 結(jié)束語

本文對ICP及其改進的點云配準(zhǔn)算法進行深入研究，針對大規(guī)模點云數(shù)據(jù)配準(zhǔn)KD樹查詢效率較低的問題，提出一種基于八叉樹與KD樹索引的點云精配準(zhǔn)方法。利用八叉樹空間結(jié)構(gòu)特點和KD樹搜索特性，采用歐氏距離閾值、點對距離差值和法向量閾值剔除錯誤點對。將索引代價較小的全局八叉樹與高效的局部KD樹相關(guān)聯(lián)，在保證滿足配準(zhǔn)精度的前提下，能夠不同程度提高配準(zhǔn)算法的時間效率，特別適合于較大規(guī)模的點云模型的配準(zhǔn)。通過算法分析和實驗可以看到，在實際應(yīng)用中，設(shè)置合適的模型點云分割參數(shù)，是影響改進算法配準(zhǔn)效率和精度的關(guān)鍵。

[1] XIE J, HSU Y F, FERIS R S, et al. Fine registration of 3D point clouds fusing structural and photometric information using an RGB-D camera[J]. Journal of Visual Communication & Image Representation, 2015, 32:194-204.

[2] 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.

[3] 劉豐華. 復(fù)雜模型三維點云自動配準(zhǔn)技術(shù)的研究[D]. 天津：天津大學(xué)，2013.

[4] LIU Z X，AN J，JING Y. A simple and robust feature point matching algorithm based on restricted spatial order constraints for aerial image registration[J]. IEEE Transactions on Geoscience and Remote Sensing, 2012, 50(2): 514-527.

[5] 劉江，張旭，朱繼文. 一種基于K-D樹優(yōu)化的ICP三維點云配準(zhǔn)方法[J]. 測繪工程, 2016, 25(6): 15-18.

[6] MULCHRONE K F. Application of delaunay triangulation to the near_est neighbor method of strain analysis[J]. Journal of Structural Geology, 2003, 25(5): 689-702.

[7] 何婧，吳躍，楊帆，等. 基于KD樹和R樹的多維云數(shù)據(jù)索引[J]. 計算機應(yīng)用，2014，34(11):3218-3221.

[8] 楊建思. 一種四叉樹與KD樹結(jié)合的海量機載LiDAR數(shù)據(jù)組織管理方法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版)，2014，39(8): 918-922.

[9] WANG Yujian, TAN Shaowei, DONG Weiwei, et al. Research on 3D modeling method based on hybrid octree structure[J]. The Open Electrical & Electronic Engineering Journal, 2014, 8: 323-329.

[10] ARYA S, MOUNT D M, NETANYAHU N S, et al. An optimal algorithm for approximate nearest neighbor searching fixed dimensions[J]. Journal of the ACM, 1998, 45(6): 891-923.

[11] 鄭明玲, 許柯, 劉衡竹, 等. 基于重疊區(qū)域的高性能近似KD樹算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2015, 27(6): 1053-1059.

[12] 韋盛斌, 王少卿, 周常河, 等. 用于三維重建的點云單應(yīng)性迭代最近點配準(zhǔn)算法[J]. 光學(xué)學(xué)報, 2015, 35(5): 31-37.

[13] LIAW Y C, LEOU M L, WU C M. Fast exact k nearest neighbors search using an orthogonal search tree[J]. Pattern Recognition, 2010, 43(6): 2351-2358.

[14] 祝繼華, 尹俊, 邗汶鋅, 等. 面向低維點集配準(zhǔn)的高效最近鄰搜索法[J]. 模式識別與人工智能, 2014, 27(12): 1071-1077.

[15] 鐘瑩, 張蒙. 基于改進ICP算法的點云自動配準(zhǔn)技術(shù)[J]. 控制工程, 2014, 21(1):37-40.

[16] 李聰波，肖衛(wèi)洪，杜彥斌，等. 基于改進ICP算法的損傷零部件精確配準(zhǔn)方法[J]. 計算機集成制造系統(tǒng), 2016, 22(4):1021-1028.

[責(zé)任編輯：張德福]

Point cloud registration based on octree and KD-tree index

WANG Yujian, LIAN Tengfei，WU Mingming,GAO Qian

(School of Information, Beijing Union University, Beijing 100101, China)

A multilayer index structure based on octree and KD tree is reported for low query efficiency problems in multi-dimensional queries of KD tree. First, the octree global index for model point cloud is established. Then, the local data KD-tree indexes are built in the octree leave nodes. To improve the traditional Iterative Closest Point algorithm, the local point cloud data is quickly located based on the global index of leave nodes. Using the local KD tree indexes, the searching speed of closest point is sped up. Part of the noise points are removed by the euclidean distance threshold, the difference of interval of point pair and the normals threshold. Experimental result indicates that the proposed method can improve the efficiency and accuracy of registration.

point cloud registration; octree; KD-tree; ICP algorithm

2016-12-20

國家自然科學(xué)基金資助項目(61271369)

王育堅(1963-)，男，教授.

廉騰飛(1991-)，女，碩士研究生.

著錄：王育堅，廉騰飛，吳明明，等.基于八叉樹與KD樹索引的點云配準(zhǔn)方法[J].測繪工程，2017，26(8)：35-40.

10.19349/j.cnki.issn1006-7949.2017.08.008

TP391

A

1006-7949(2017)08-0035-06