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

王育堅(jiān)，廉騰飛，吳明明，高 倩

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

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

王育堅(jiān)，廉騰飛，吳明明，高 倩

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 改進(jìn)的點(diǎn)云配準(zhǔn)算法

2.1 ICP算法的最近點(diǎn)搜索

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

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

2.2 基于KD樹(shù)最近鄰搜索算法的改進(jìn)

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

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

(1)

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

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

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

(2)

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

(3)

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

(4)

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

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

ni·nj≥G.

(5)

2.3 算法步驟

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

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

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

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

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

5)利用歐氏距離閾值和點(diǎn)對(duì)距離差值剔除部分噪聲點(diǎn)。

6)根據(jù)法向量閾值剔除錯(cuò)誤的匹配點(diǎn)對(duì)。

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

(6)

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

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

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

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

h≥|log8K|+1.

(7)

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

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

(8)

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

Mlog8K+Mlog2N/K

(9)

即：

log8K

(10)

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

3 實(shí)驗(yàn)與分析

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

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

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

對(duì)于不同規(guī)模的點(diǎn)云模型分別采用傳統(tǒng)ICP算法、文獻(xiàn)[15]提出的算法和本文提出的改進(jìn)算法進(jìn)行配準(zhǔn)，不同規(guī)模點(diǎn)云情況下3種算法的配準(zhǔn)時(shí)間如表1所示，3種算法的配準(zhǔn)精度如表2所示。可以看出，本文首先利用八叉樹(shù)對(duì)空間進(jìn)行分割，建立局部KD樹(shù)索引，有效減少最近鄰搜索時(shí)間，使算法的效率有較大的提高，并且在精度上有較好的改善。在數(shù)據(jù)量非常大的海量點(diǎn)云情況下，降低配準(zhǔn)時(shí)間的效果更加明顯。

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

本文對(duì)ICP及其改進(jìn)的點(diǎn)云配準(zhǔn)算法進(jìn)行深入研究，針對(duì)大規(guī)模點(diǎn)云數(shù)據(jù)配準(zhǔn)KD樹(shù)查詢效率較低的問(wèn)題，提出一種基于八叉樹(shù)與KD樹(shù)索引的點(diǎn)云精配準(zhǔn)方法。利用八叉樹(shù)空間結(jié)構(gòu)特點(diǎn)和KD樹(shù)搜索特性，采用歐氏距離閾值、點(diǎn)對(duì)距離差值和法向量閾值剔除錯(cuò)誤點(diǎn)對(duì)。將索引代價(jià)較小的全局八叉樹(shù)與高效的局部KD樹(shù)相關(guān)聯(lián)，在保證滿足配準(zhǔn)精度的前提下，能夠不同程度提高配準(zhǔn)算法的時(shí)間效率，特別適合于較大規(guī)模的點(diǎn)云模型的配準(zhǔn)。通過(guò)算法分析和實(shí)驗(yàn)可以看到，在實(shí)際應(yīng)用中，設(shè)置合適的模型點(diǎn)云分割參數(shù)，是影響改進(jìn)算法配準(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ù)雜模型三維點(diǎn)云自動(dòng)配準(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樹(shù)優(yōu)化的ICP三維點(diǎn)云配準(zhǔn)方法[J]. 測(cè)繪工程, 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樹(shù)和R樹(shù)的多維云數(shù)據(jù)索引[J]. 計(jì)算機(jī)應(yīng)用，2014，34(11):3218-3221.

[8] 楊建思. 一種四叉樹(shù)與KD樹(shù)結(jié)合的海量機(jī)載LiDAR數(shù)據(jù)組織管理方法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(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樹(shù)算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2015, 27(6): 1053-1059.

[12] 韋盛斌, 王少卿, 周常河, 等. 用于三維重建的點(diǎn)云單應(yīng)性迭代最近點(diǎn)配準(zhǔn)算法[J]. 光學(xué)學(xué)報(bào), 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] 祝繼華, 尹俊, 邗汶鋅, 等. 面向低維點(diǎn)集配準(zhǔn)的高效最近鄰搜索法[J]. 模式識(shí)別與人工智能, 2014, 27(12): 1071-1077.

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

[16] 李聰波，肖衛(wèi)洪，杜彥斌，等. 基于改進(jìn)ICP算法的損傷零部件精確配準(zhǔn)方法[J]. 計(jì)算機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61271369)

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

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

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

10.19349/j.cnki.issn1006-7949.2017.08.008

TP391

A

1006-7949(2017)08-0035-06