范　瑛（山東天啟智能工程有限公司,濟(jì)南　250000）

?

激光三維掃描的點(diǎn)云拼接技術(shù)研究

范瑛
（山東天啟智能工程有限公司,濟(jì)南250000）

摘 要:三維點(diǎn)云拼接是三維面型反求中的關(guān)鍵和難點(diǎn)。提出了一種特征點(diǎn)三維點(diǎn)云拼接技術(shù)。整個(gè)拼接過程由粗拼接和精拼接兩部分組成。通過引入被測物的特征點(diǎn)，分析了坐標(biāo)變換矩陣的求解方法，首先，粗略拼接的初始變換矩陣由SVD算法求解，其次，兩片點(diǎn)云之間的最近點(diǎn)通過SNN算法加速搜索，從而，利用改進(jìn)的最近點(diǎn)迭代算法實(shí)現(xiàn)了精確拼接，最后，給出了程序設(shè)計(jì)思路。

關(guān)鍵詞：三維點(diǎn)云拼接；特征點(diǎn)；SVD ；SNN; 最近鄰迭代

1　引言

激光三維掃描法是曲面形體檢測技術(shù)中一個(gè)十分活躍的分支，在工業(yè)上獲得了越來越廣泛的運(yùn)用。然而，由于實(shí)際測量中，有多種大型物體或者形狀復(fù)雜的物體，這樣一來，物體的三維模型就不能夠直接測量。物體分片測量成為了近年來發(fā)展起來的一種復(fù)雜物體測量技術(shù)，通過獲得物體的局部參數(shù)，然后對多個(gè)局部物理參數(shù)進(jìn)行拼接，得到完整的物體模型。

三維拼接技術(shù)的本質(zhì)就是把不同局部參量的物理參數(shù)所在的局部坐標(biāo)系進(jìn)行變換，合成為同一坐標(biāo)系的一組數(shù)據(jù)[1～2]。迭代最近點(diǎn)匹配（Iterative Closet Point，ICP）算法最早是由由Besl等[3]提出，目前該方法在物體模型拼接中得到了廣泛應(yīng)用，并且衍生了大量改進(jìn)算法。但目前大多數(shù)算法仍然存在許多問題，比如由于數(shù)據(jù)量大造成的拼接速度慢、精度低等缺點(diǎn)。本文在現(xiàn)有算法的基礎(chǔ)上，基于特征點(diǎn)拼接，提出了一種速度快、精度高的改進(jìn)最近點(diǎn)迭代算法，分為粗拼接和精拼接兩個(gè)步驟，可以實(shí)現(xiàn)較好的效果。

2　特征點(diǎn)粗略拼接

2.1特征點(diǎn)對的選取

特征點(diǎn)是三維拼接技術(shù)中非常重要的標(biāo)識點(diǎn)，在該方法中，我們可以將特征點(diǎn)貼于被測物兩個(gè)視角的重疊區(qū)，然后利用三維測量系統(tǒng)對兩個(gè)局部曲面分別進(jìn)行測量, 從而得到兩個(gè)曲面的物理點(diǎn)云數(shù)據(jù)。

2.2坐標(biāo)變換矩陣的獲取

最小二乘法是處理和分析觀測數(shù)據(jù)的一種經(jīng)典方法。對于三維空間兩個(gè)視角下的特征點(diǎn)集和，可由以下的SVD分解法求得旋轉(zhuǎn)矩陣R和平移矩陣T，SVD法可以確保拼接不發(fā)生畸變，而且精度比較高。（1）將式（1）改寫為以下形式：

得到R和T以后，特征點(diǎn)集Y中的任意一點(diǎn)yi都可以通過轉(zhuǎn)換到X中。將兩組數(shù)據(jù)轉(zhuǎn)換到同一坐標(biāo)系下。從而實(shí)現(xiàn)拼接技術(shù)。

3　精確拼接

在上一步粗略拼接的基礎(chǔ)上，根據(jù)上述測量得到的初始特征點(diǎn)匹配點(diǎn)對，采用上述兩個(gè)局部曲面的拼接位置作為初始定位。在精確拼接的迭代匹配中，基于Besl等提出的ICP算法，進(jìn)一步，采用SNN算法，基于距離閾值限制條件，從以上粗略的特征點(diǎn)對中選取精確匹配點(diǎn)對，從而實(shí)現(xiàn)將兩片曲面點(diǎn)云中屬于正確匹配區(qū)域范圍的點(diǎn)加入精確匹配點(diǎn)對集合。最后，利用經(jīng)典的帶系數(shù)修正的四元素(Quaternion) 法[5]作為每一次迭代循環(huán)的最優(yōu)化解析方法。

3.1最近點(diǎn)搜索

現(xiàn)有的ICP算法計(jì)算速度比較慢，主要原因在于搜索策略的選擇，基于現(xiàn)有算法的缺點(diǎn)，我們運(yùn)用一種新的最近點(diǎn)搜索算法——SNN算法[6]。

傳統(tǒng)算法求解所有的特征點(diǎn)的兩兩之間的距離，從而造成計(jì)算數(shù)據(jù)量大，拼接速度慢。而SNN 算法具有計(jì)算速度快的優(yōu)點(diǎn)，首先，它將所有的掃描數(shù)據(jù)按照某一維度進(jìn)行優(yōu)先排序，然后，限定該維的某一d鄰域作為距離閾值，從而只計(jì)算該范圍內(nèi)的任意兩兩點(diǎn)之間的距離，最后根據(jù)計(jì)算結(jié)果相比較的出ICP算法中的最近相鄰點(diǎn)。由于該算法只需要求解距離閾值較小鄰域內(nèi)的點(diǎn)云數(shù)據(jù)，所以大大節(jié)約了拼接時(shí)間，提高了計(jì)算速度。根據(jù)SNN算法，如果掃描數(shù)據(jù)集合中的點(diǎn)在排序維的分布情況比較均勻，即在距離限制閾值d鄰域內(nèi)，其所包含的有效數(shù)據(jù)點(diǎn)的個(gè)數(shù)不超過某一個(gè)與數(shù)據(jù)集合中點(diǎn)的總數(shù)n無關(guān)的常數(shù)，則SNN 算法的時(shí)間復(fù)雜度為。如果通過掃描空間維度得到拼接數(shù)據(jù)，那么掃描后所得到的數(shù)據(jù)必然會按照某一維度自然排序，所以其時(shí)間復(fù)雜度會降為()O n。因此，基于ICP算法中最近鄰點(diǎn)迭代的原則，利用SNN算法進(jìn)行最近鄰點(diǎn)的搜索

方法，可以大大節(jié)約搜索時(shí)間，提高點(diǎn)云拼接效率。

3.2點(diǎn)云之間的距離與收斂性

由Besl提出的ICP算法，點(diǎn)云之間的距離由兩個(gè)數(shù)據(jù)點(diǎn)在三維空間中的歐氏距離決定，但這種度量方法在某些情況下會誤差較大（比如當(dāng)兩個(gè)平行平面滑動時(shí)）[1]。因此，尋求有效的定義兩最近點(diǎn)之間的距離的方法，對提高算法的效率有很大幫助。

鑒于此，本文提出利用兩點(diǎn)之間的均方距離作為最近鄰點(diǎn)之間的距離的度量準(zhǔn)則，假設(shè)和分別為在m1-次迭代中所得到的最近點(diǎn)的數(shù)據(jù)點(diǎn)集。則點(diǎn)集的均方距離定義為

上式中，r為重疊曲面中點(diǎn)云數(shù)據(jù)的個(gè)數(shù)，通過使用該最近點(diǎn)距離度量準(zhǔn)則，可以大大加快算法的收斂速度。

因此，該改進(jìn)的最近點(diǎn)迭代算法程序如下：

（1）初始化并設(shè)置誤差門限S，求解三維數(shù)據(jù)拼接的坐標(biāo)變換矩陣R0和T0，并根據(jù)初始坐標(biāo)變換關(guān)系對兩組點(diǎn)云數(shù)據(jù)進(jìn)行坐標(biāo)變換，最后求得變換后兩組點(diǎn)云數(shù)據(jù)之間的距離。

（2）根據(jù)距離閾值限制條件，由SNN算法搜索出兩組匹配點(diǎn)云中的最臨近匹配點(diǎn)對。

（3）消除無效匹配點(diǎn)對后，對剩余最鄰近匹配點(diǎn)對，進(jìn)而利用帶修正系數(shù)的四元素算法優(yōu)化求解轉(zhuǎn)換參數(shù)R1和T1。

（4）再次利用R1、T1對以上兩組點(diǎn)云數(shù)據(jù)進(jìn)行變換，并求出該變換后兩者之間的距離S2。

（5）如果S2小于初始設(shè)定閾值S，則停止搜索。否則返回步驟(2)，繼續(xù)搜索最鄰近匹配點(diǎn)對 ，直到 Si小于初始設(shè)定閾值為止。

4　結(jié)論

三維點(diǎn)云拼接作為三維物體逆向反求中的一個(gè)關(guān)鍵技術(shù)，其精度直接關(guān)系到三維曲面重建的精度。本文提出了一種改進(jìn)的最近點(diǎn)迭代算法的點(diǎn)云拼接技術(shù)，通過在重構(gòu)曲面引入特征標(biāo)識點(diǎn)，粗略拼接中利用SVD算法求得初始變換矩陣，搜索匹配特征點(diǎn)，從而實(shí)現(xiàn)精確拼接。該改進(jìn)的ICP算法，結(jié)合了SNN算法，大大提高了最鄰近點(diǎn)的搜索速度，有效提高了檢索效率，實(shí)現(xiàn)精確的拼接效果。該方法拼接精度較高，也適合于大型物體，并且具有很好的收斂性。

參考文獻(xiàn):

[1]Chen Y, Medioni G. Object modeling by registration of multiple range images [J].Image and Vision Computing,1992, 10(03):145-155.

[2]李萬松,蘇禮坤.相位檢測面形術(shù)在大尺度三維面形測量中的應(yīng)用[J].光學(xué)學(xué)報(bào),2000,20(06):792-796.

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

[4]Shinji Umeyama. Least-Squares estimation of transformation parameters between two point patterns [J]. IEEE Transactions on Pattern Analysis and Machine Intelligen ce,1991,13(4):376-380.

[5]Horn B K P. Closed-form solution of absolute orientation using unit quaternions[J].J Opt Soc Am,1987, A(04):629-642.

[6]胡建軍,唐常杰,李川等.基于最近鄰優(yōu)先的高效聚類算法[J].四川大學(xué)學(xué)報(bào):工程科學(xué)版,2004,36(06) :93-99.

DOI :10.16640/j.cnki.37-1222/t.2016.01.255