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

?

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

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

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

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

1　引言

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

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

2　特征點粗略拼接

2.1特征點對的選取

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

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

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

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

3　精確拼接

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

3.1最近點搜索

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

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

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

3.2點云之間的距離與收斂性

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

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

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

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

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

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

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

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

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

4　結(jié)論

三維點云拼接作為三維物體逆向反求中的一個關(guān)鍵技術(shù)，其精度直接關(guān)系到三維曲面重建的精度。本文提出了一種改進(jìn)的最近點迭代算法的點云拼接技術(shù)，通過在重構(gòu)曲面引入特征標(biāo)識點，粗略拼接中利用SVD算法求得初始變換矩陣，搜索匹配特征點，從而實現(xiàn)精確拼接。該改進(jìn)的ICP算法，結(jié)合了SNN算法，大大提高了最鄰近點的搜索速度，有效提高了檢索效率，實現(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é)報,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é)報:工程科學(xué)版,2004,36(06) :93-99.

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