王太學，江智，江德港，李柏林，郭彩玲

(1.西南交通大學 唐山研究生院，河北 唐山 063000；2.西南交通大學 機械工程學院，成都 610031；3.唐山學院 河北省智能裝備數(shù)字化設計及過程仿真重點實驗室，河北 唐山 063000)

0 引言

點云配準是將不同視角下獲得的點云數(shù)據(jù)經(jīng)過一定的旋轉(zhuǎn)平移變換到同一坐標系下的過程，廣泛應用于計算機視覺[1]、三維重建[2]等領域。

目前國內(nèi)外學者已經(jīng)對點云配準進行了大量研究。最經(jīng)典的點云配準算法是Besl等[3]提出的迭代最近點(iterative closest point，ICP)算法，該算法的配準前提是要求輸入點云有較好的初始位置，才能實現(xiàn)精確配準，但是算法本身需要多次迭代，收斂速率較慢，并且容易陷入局部最優(yōu)。針對經(jīng)典ICP算法的缺點，相關學者對ICP算法進行了改進。趙夫群等[4]將三維點云轉(zhuǎn)換成二維方位角，通過二維圖像和三維點的映射關系進行坐標變換，最后基于奇異值分解完成了ICP算法的精配準；嚴劍鋒等[5]基于點云的幾何特征利用點云的曲率提取特征點，通過匹配特征點對完成粗匹配，為ICP算法提供較好的初值，提高了配準精度和可靠性。點特征直方圖(point feature histogram，PFH)和快速點特征直方圖(fast point feature histogram，F(xiàn)PFH)[6-7]雖然在點云配準的過程中也能提高點云配準的精度，但是當點云體積密度較大時，點云配準效率會大大降低。馬偉麗等[8]通過隨機抽樣一致性算法結(jié)合四元數(shù)法計算配準參數(shù)，完成了全局最優(yōu)參數(shù)的點云精確配準，配準效率卻有待提高；He等[9]提出一種基于PointNet++與ICP算法相結(jié)合的點云配準算法，同時提取多個點云特征，實現(xiàn)了點云的快速魯棒配準，但是對于稀疏點云的適應性較差；Magnusson等[10]提出了3D-NDT(three-dimensional normal distributions transform)算法，把三維體素內(nèi)的點云數(shù)據(jù)集轉(zhuǎn)換成連續(xù)可微的概率分布函數(shù)，通過得分法實現(xiàn)點云的配準；Aiger等[11]提出了4PCS(4-points congruent sets)算法，算法無需初始位置和濾波去噪，并允許存在離群值；在4PCS算法的基礎上，Mellado等[12]提出了super4PCS(super three-dimensional normal distributions transform)算法，運用仿射變換不變性，利用共面四點完成點云匹配；Chetverikov等[13]提出一種trimmed ICP(TrICP)算法，通過尋找最小重疊參數(shù)實現(xiàn)點云的精確匹配，但是需要具有良好的初始位置估計值。

基于以上學者的研究現(xiàn)狀，為了改進ICP算法需要較好的初值和收斂速度較慢的問題，本文提出一種基于主軸基向量間的關系進行主軸校正的方法，利用兩組點云的三個點云主成分坐標軸對應基向量間的關系進行主軸校正，為ICP算法輸入較好的初值，接著針對具有部分重疊的點云提出一種改進ICP算法，利用最近鄰算法搜索重疊點云部分的有效對應點對，利用有效點對進行求解最優(yōu)變換參數(shù)完成點云的精確配準。

1 點云粗配準

1.1 主軸方向分析

PCA(principal component analysis)算法[14]是一種用于降維的統(tǒng)計方法，主要的作用是用來簡化數(shù)據(jù)集，通過線性變換求取數(shù)據(jù)集的主成分，從而實現(xiàn)降維。兩組點云數(shù)據(jù)經(jīng)過PCA算法處理后得到了初始的旋轉(zhuǎn)和平移矩陣。雖然其主軸基本共線，但仍然存在主軸方向相反的可能性[15]，需要對主軸方向校正才能為精配準提供較好的初值。

設兩組點云P和Q經(jīng)過PCA變換后得到的坐標軸分別為upvpwp、uqvqwq，原點分別為Op和Oq，其中u、v、w分別表示第一坐標軸、第二坐標軸和第三坐標軸。當對點云進行旋轉(zhuǎn)和平移變換后，主軸方向出現(xiàn)相反的情況有7種，如表1所示，定義類別Ci(i=1，2，…，7)。其中“1”表示兩組點云的兩個對應坐標軸方向相同，“-1”表示兩組點云的兩個對應坐標軸方向相反。

表1 主軸方向相反情況

經(jīng)過PCA后以兩組點云的質(zhì)心為原點建立相對坐標系，可能出現(xiàn)的點云坐標系情況如圖1所示，其中圖1(a)為點云Q的坐標系，圖1(b)至圖1(h)為點云P經(jīng)過PCA后可能出現(xiàn)坐標軸反向的類型。

圖1 PCA后出現(xiàn)反向坐標軸的類型

1.2 點云主軸校正

對于兩組已經(jīng)進行處理后的點云數(shù)據(jù)，主軸基本對齊后可能出現(xiàn)表1中7種類別的任何一種，主軸校正的關鍵就是確定出現(xiàn)的是哪一類別，針對這一類別進行主軸調(diào)整，得到較好的旋轉(zhuǎn)和平移矩陣初值。

圖2 確定主軸類別流程圖

步驟1：輸入兩組相似點云。

步驟2：利用PCA進行點云數(shù)據(jù)處理，實現(xiàn)主軸對齊。

步驟3：利用SVD分解計算α、β和γ。

步驟4：計算αp·αq，若大于0，計算βp·βq，若大于0，計算γp·γq，若大于0，則主軸方向相同，若小于0，輸出類別為C1；若βp·βq<0，計算γp·γq，若大于0，輸出類別為C2，若小于0，輸出類別為C3；若αp·αq<0，計算βp·βq，若大于0，計算γp·γq，若大于0，輸出類別為C4，若小于0，輸出類別為C5；若βp·βq<0，計算γp·γq，若大于0，輸出類別為C6，若<0，輸出類別為C7。

步驟5：根據(jù)步驟4的判斷結(jié)果，對源點云P與目標點云Q主軸方向相反的坐標軸的基向量取反，即αp=-αp或βp=-βp或γp=-γp，從而完成Up校正，得到新矩陣UP0。

如圖3(a)所示，為兩組點云進行PCA處理后的點云配準情況。從圖中可以看到，兩組點云主軸已經(jīng)基本對齊，但出現(xiàn)了主軸u和w反向的情況。經(jīng)過算法初配準后的結(jié)果如圖3(b)所示，實現(xiàn)了主軸方向的校正。

圖3 點云粗配準圖

2 點云精配準

兩組點云在經(jīng)過粗配準后，初始位置關系已經(jīng)基本相近，運用經(jīng)典ICP算法進行迭代，最小化目標函數(shù)求解最優(yōu)變換參數(shù)R和T即可完成精配準。但是在實際點云數(shù)據(jù)獲取過程中，不同視角下的兩組點云在同一個坐標系下會有一定重疊度但是并不會完全重合[16]，使得ICP算法在應用時受限。

在點云配準的過程中，并不是所有點對對配準的貢獻都相同[17]，非重疊區(qū)域的點在配準的過程中只會找到錯誤點對[18]，因此要剔除錯誤點對的影響。

針對具有部分重疊的點云配準問題，本文提出了改進ICP算法，先將兩組點云進行粗配準，之后利用最近鄰搜索算法尋找最近鄰點組成有效點對，基于有效點對迭代求解最優(yōu)變換參數(shù)完成配準。

2.1 改進ICP算法描述

2.2 改進ICP算法步驟

步驟2：建立兩組點云的點對關系，表達如式(1)所示。

(1)

式中：ck代表一組點對關系；得到兩組點云的有效點對，記為Dl{l=1，2，3，…，s}，s為有效點對的個數(shù)，l為一組有效點對，s≤N且s≤M。

(2)

其中，將粗配準得到的結(jié)果作為第一次迭代的初值，通過以上迭代步驟來獲得最優(yōu)解。

3 實驗實例與分析

為驗證本文算法性能，選取斯坦福大學點云數(shù)據(jù)庫中Bunny模型為實驗對象，其中源點云的數(shù)量為31 797(圖4紫紅色點云)，目標點云的數(shù)量為35 947(圖4藍色點云)。實驗從初始位置和重疊度兩個方面對點云數(shù)據(jù)進行配準實驗，分別驗證算法在粗配準和精配準過程的性能。實驗環(huán)境為Intel Xeon Silver 4110 2.10 GHz CPU，運行平臺為MATLAB R2016a。

3.1 粗配準

為檢驗本文粗配準算法性能，選取基于局部特征的配準算法FPFH、4PCS、PFH和改進PCA算法進行對比分析。圖4(a)為點云的初始位置，圖4(b)～圖4(e)分別為FPFH、4PCS、PFH和改進PCA算法對點云進行粗配準后的結(jié)果，四種算法的均方根誤差RMSE和所用時間如表2所示。

圖4 粗配準測試

表2 粗配準算法結(jié)果對比

從實驗結(jié)果可以看出，本文算法在配準時間和誤差上優(yōu)于其他三種算法。FPFH算法在配準時沒有完全考慮中心點周圍鄰域的所有點對關系，使周圍的一些幾何信息丟失導致匹配誤差較大；4PCS算法精度有所提高，但每次需要隨機采樣，并且點云重疊率低也會導致其配準時間增長；PFH算法需要計算鄰域點所有組合的特征值，使算法復雜度增高，導致算法的配準時間較長且其平移誤差較大。

3.2 精配準

為驗證本文算法在不同重疊度下點云的配準性能，選取三組具有不同重疊度的點云與三種精配準算法TrICP、super4PCS、3D-NDT進行對比分析。本文算法能夠自動計算出點云的重疊度，重疊度參數(shù)如表3所示(ε根據(jù)粗配準的結(jié)果設定為0.8)，配準后的結(jié)果如圖5、圖6和圖7所示，不同重疊度下的配準誤差和時間如表3所示。

圖5 重疊度=0.092算法配準結(jié)果

圖6 重疊度=0.684算法配準結(jié)果

圖7 重疊度=0.671算法配準結(jié)果

表3 配準算法的效果比較

根據(jù)配準結(jié)果得出，對于不同重疊度的點云，本文算法在配準的時間和收斂誤差上都明顯低于其他三種算法，經(jīng)過改進的PCA算法粗配準后，利用KD-tree尋找最近點，并利用歐式距離較大的有效點對進行精配準，縮短了配準時間和提高了配準的精度。TrICP算法對點云的初始位置要求較高，在尋找最佳重疊時需多次迭代配準，計算時間較長，并且在初始位置不好的情況下容易陷入局部最優(yōu)得到錯誤匹配結(jié)果。super4PCS算法是對4PCS算法的改進，利用共面四點的仿射不變性進行點云配準。雖然其配準性能較高，但是需要人工選取樣本點，當點云密度增大后算法配準效率會降低。3D-NDT算法對參數(shù)設置較敏感，需要多次手動進行參數(shù)的調(diào)整，而手動調(diào)參的過程也增加了算法時間的開銷。

對比同一算法，從實驗數(shù)據(jù)可以看出，重疊度相差較大的兩組點云，重疊度越大，配準效率越高，而對于重疊度近似的兩組點云，在保證良好初始位置的情況下，其配準效率也會越高。而本文算法在重疊率較低和初始位置相差較大的情況下收斂速度較快，配準精度較高，證明了本文算法的魯棒性。

3.3 牽引座支座點云配準

為驗證算法在實測數(shù)據(jù)上的性能，用FARO Design ScanArm掃描儀從不同方位獲取了汽車牽引座點云數(shù)據(jù)，利用TrICP算法、super4PCS算法、3D-NDT算法和本文算法對實測點云數(shù)據(jù)進行配準，配準結(jié)果如圖8所示，其中圖8(a)為點云數(shù)據(jù)的獲取過程，圖8(b)為獲取兩組點云的初始位置，圖8(c)～圖8(f)分別為四種算法的配準圖，并對局部的配準效果進行了放大，算法的均方根誤差和耗時如表4所示。

圖8 支座點云配準結(jié)果

表4 不同算法對支座點云的配準結(jié)果

從配準結(jié)果和表中所得數(shù)據(jù)可以看出：3D-NDT算法表現(xiàn)最差，由于數(shù)據(jù)為實測數(shù)據(jù)，噪聲不可避免，算法在參數(shù)選取過程中難度增加，誤差增大；TrICP算法較3D-NDT算法在性能上有所提升，但受初始位置影響配準效果仍不理想；super4PCS算法雖然配準誤差較3D-NDT算法和TrICP算法稍有提高，但是隨著點云數(shù)量的增加，導致其選取樣本點的效率降低而匹配時間增加；本文算法在利用歐式距離較大的有效點對配準過程中減少了配準時間并增加了配準精度，配準精度為0.010 05 mm，配準時間為41.012 5 s，配準性能優(yōu)于其他三種對比算法，證明了本文算法的可行性。

4 結(jié)束語

針對ICP算法對點云配準過程中需要輸入較好初值和收斂速度慢的問題，本文提出了一種融合PCA的改進ICP算法。首先利用PCA算法對點云數(shù)據(jù)進行處理實現(xiàn)兩組點云主軸對齊，定義主軸基向量，利用主軸基向量間的關系實現(xiàn)了主軸方向的校正，獲得點云配準的初始位姿。對比FPFH、4PCS、PFH算法，本文粗配準算法所用時間分別提高了20.2%、50.5%、44.4%，配準精度分別提高了66.9%、48.5%、79.4%。在部分重疊區(qū)域的點云配準中，粗配準為精配準提供了較好的初值，本文提出一種利用重疊區(qū)域的有效點對進行ICP配準算法，通過計算有效點對中歐式距離較大的點對來求解最優(yōu)變換參數(shù)，完成精配準。通過在Bunny點云和支座點云配準的實驗表明，在重疊度較低和初始位置相差較大的情況下，本文算法在收斂精度和配準時間上都優(yōu)于對比算法，同時彌補了傳統(tǒng)ICP算法收斂速度慢的不足，并為ICP算法提供了較好初值。但文本算法在點云較稠密或點云數(shù)量較多時，配準誤差較大，之后將著重于研究大數(shù)據(jù)點云的配準準確性。