基于佳點集人工魚群的點云配準算法

李書群, 陳 鈺, 楊雨婷, 余 敏, 朱勇超, 屈小川

(1.合肥學院 城市建設與交通學院,安徽 合肥 230601; 2.合肥工業大學 土木與水利工程學院,安徽 合肥 230009; 3.合肥工業大學 管理學院,安徽 合肥 230009)

0 引 言

三維激光掃描技術誕生于20世紀90年代,它通過高速激光掃描測量的方法大面積、高分辨率地快速獲取被測對象表面的三維坐標數據,即點云數據集[1]。該技術雖然已經廣泛應用于變形監測、古建筑保護、智慧城市等多種現代化領域內[2],但是在實際生產過程中,由于目標物規模過大,采集目標物的三維點云數據往往需要多角度、多方位掃描,再通過拼接各個點云數據集以得到完整的目標物體三維點云數據。點云數據拼接的關鍵是點云配準,該技術在醫學影像[3]、逆向工程[4]等領域有重要作用。點云配準又分為粗配準和精配準。目前廣泛應用的點云精配準迭代最近點(iterative closest point,ICP)算法[5],對待配準點云數據集的初始位置姿態要求較高,較大的旋轉會導致在迭代過程中需要重復搜索最近鄰點,影響配準精度[6]。因此,許多粗配準算法被相繼提出,如四點一致集(4-points congruent sets,4PCS)算法[7],該算法雖配準速度較快,但對于平面較大而其他特征不明顯的點云容易配準失敗。

為提高配準效率,文獻[8]提出三維正態分布變換(3D-normal distributions transform,3D-NDT)算法,相比ICP算法,該算法不需要重復計算最近鄰點,效率更高,然而該算法依賴于配準矩陣初值。除此之外,基于群智能算法理論的方法在三維點云配準中也得到了廣泛應用,如基于布谷鳥優化的三維點云配準算法[9]、基于曲率信息的人工蜂群算法[10]等。雖然這類算法能較好地為精配準提供好的初始位姿,但是仍然存在尋優時間較長、收斂速度較慢的缺點。

因此,需要設計一種算法,對目標函數的性質、初值、參數設定的要求不高,有較大的容許范圍,且具有尋優速度較快、具備全局尋優、收斂速度快等優點。文獻[11]提出了一種基于魚類動物行為的群體智能優化算法,可以滿足上述要求,但該算法中人工魚的初始位置是隨機產生的,易陷入局部最優;文獻[12]采用佳點集(good point set,GPS)理論對種群初始化有助于增加種群的多樣性,提升了算法的收斂速度。

針對以上問題,本文提出一種基于佳點集人工魚群的點云配準算法。首先選擇人工魚群算法,采用佳點集理論實現人工魚群中人工魚位置的初始化,避免陷入局部最優;然后將待配準的兩片點云的對應點距離的均方根作為適應度函數,以均方根最小作為本文算法的尋優準則,利用該算法對點云配準中剛性變換矩陣的6個參數進行全局尋優;最后通過尋優得到參數計算剛性變換矩陣,實現兩片點云的粗配準,從而為ICP精配準提供良好的初始位姿。

1 佳點集人工魚群算法原理

1.1 人工魚群算法

人工魚群算法是一種模仿魚群覓食、聚群、追尾行為的群體智能優化算法。通過模擬魚群的覓食過程,由覓食行為、聚群行為和追尾行為來構造尋優策略,從而達到全局尋優的目的。該算法具有全局搜索能力強、魯棒性強等優點。

給定某一區域內N條人工魚,第i條人工魚在D維空間狀態為xi=(xi,1,xi,2,…,xi,D),i=1,2,…,n。該區域內N條人工魚的狀態均隨機生成,人工魚的適應度函數為Y=F({xi|i=1,2,…,N}),包括以下參數:種群規模N、人工魚視野visual、步長step、擁擠度因子δ、嘗試次數trynumber、最大迭代次數L、隨機數Rand(0,1)。算法描述[13]以求解適應度函數最大值為例,標準人工魚群優化算法可描述為:

1) 覓食行為。在當前人工魚xi的感知范圍內隨機選擇某一狀態xj,其適應度函數為Yj,若優于當前人工魚狀態,向該方向移動1步;若達到嘗試次數后仍不滿足條件,則隨機移動1步。

2) 聚群行為。計算當前人工魚感知范圍內人工魚的數目nf及其中心位置Xc。若Yc/nf>δYi,說明該位置食物濃度較高且不擁擠,向該方向移動1步;否則執行覓食行為。

3) 追尾行為。搜索當前人工魚視野范圍內狀態最優的人工魚Xmax,若Ymax/nf>δY,向該方向移動1步;否則執行覓食行為。

4) 公告板。記錄最優的人工魚狀態。

1.2 佳點集理論

1.3 佳點集人工魚群算法

合理分布的初始種群有助于算法性能的提升和更好地進行全局尋優。然而,標準人工魚群算法的種群由隨機初始化方法得到,易因初始種群分布不均而陷入局部最優。針對此問題,受佳點集理論的啟發[14],在算法中采用指數序列rk={ek,1≤k≤s}初始化種群。本文采用隨機方法和指數序列方法生成的二維初始種群分布對比如圖1所示,從圖1可以看出,通過指數序列法生成的初始種群分布均勻,能避免因種群初始分布不均造成人工魚群算法陷入局部最優,因此本文采用指數序列方法生成佳點集,從而完成人工魚群算法種群的初始化。

圖1 2種方法生成的種群分布對比

本文采用3種測試函數(Ackley、Rastrigin、Rosenbrock函數)對標準人工魚群算法和佳點集人工魚群算法的性能進行測試。算法參數設置為:人工魚數N=80,人工魚維度D=6,最大迭代次數Tmax=500。測試結果如圖2所示。

圖2 2種算法在不同基準函數下的適應度對比

從圖2可以看出,經過佳點集優化后的人工魚群算法相比標準人工魚群算法的尋優精度更高,在3種測試函數下的收斂精度分別提高了約1、3、10倍。

2 基于佳點集人工魚群算法的點云配準

2.1 點云配準算法

現有激光點云的配置工作,首先需要保證點云數據能夠統一到同一坐標系下,即進行點云配準。該源點云P={pi,i=1,2,…,s},目標點云Q={qj,j=1,2,…,t}。s、t分別為P、Q中點的數量。

點云配準問題的本質是通過尋找到剛性變換矩陣T的6個參數,即坐標軸的平移量(Vx,Vy,Vz)和坐標軸的旋轉角(α,β,γ),使得兩組點云數據的對應點經過空間變換后盡可能重合,即2個點云集對應點對的距離差平方和最小。剛性變換矩陣的表達方式為:

(1)

由于點云數據本身的測量誤差、采樣密度等因素的影響,兩組點云數據經過空間變換后,對應點的距離平方差和無法達到理想歐式距離0。因此,點云配準可以表述為全局最優化問題,即尋找最優剛性變換矩陣T,使得2組點云數據的對應點的距離差平方和最小,即

(2)

結合佳點集人工魚群算法,將對應點的均方根誤差(root mean square error,RMSE)數值作為適應度函數進行全局搜索,RMSE的計算公式如下:

F(T)=RMSE(P,Q)=

(3)

其中:S為兩片點云的匹配點個數;pi為點云P中與qj匹配的點的坐標;RMSE(P,Q)為兩片點云對應點距離的均方根誤差,其值越小,代表配準精度越高。

2.2 點云下采樣與特征點提取

由于點云數據的數據量大,為加快配準過程中的計算速度,提升運算效率,本文采用體素柵格法對點云數據進行下采樣。體素柵格采樣將原始點云進行體素劃分,將每個體素內的重心點P′作為下采樣點。經過采樣后,點云數據得到簡化。

為了進一步提高待配準點云數據在匹配點處的穩定性和速度,采用三維尺度不變特征變換(3D scale invariant feature transform,3D SIFT)特征點提取算法對下采樣后的點云進行特征點的提取。

設經過下采樣后的點云數據有N個點,任意一點的坐標為pi=(xi,yi,zi),i=1,2,…,N,k為尺度調整參數,σ為空間尺度參數,S為高斯金字塔每組層數。計算步驟如下:

1) 將三維高斯函數與點云進行卷積,計算其尺度空間L(x,y,kσ)。

G(x,y,z,kσ)=

(4)

L(x,y,kσ)=G(x,y,kσ)?p(x,y,z)

(5)

2) 計算相鄰尺度層的高斯差分模型,其中i∈(0,S+2)。

DOGi=L(x,y,z,kσ)-Li-1(x,y,z,kσ)

(6)

3) 計算DOG函數空間上的極值點,將該極值點P″作為3D SIFT特征點。

利用3D SIFT特征點可以對點云的局部空間關系進行更準確地描述,也能在特征點附近建立更為穩定的對應關系。

2.3 錯誤對應關系的剔除

通過將源點云P和目標點云Q進行下采樣及3D SIFT特征點提取后的點云P″和Q″,使用快速點特征直方圖(fast point feature histogram,FPFH)進行局部特征描述[15]。根據P″的FPFH特征,查找Q″中與該特征相似的點作為匹配點對。由于點云數據中存在局部形態相似、噪聲情況,實際匹配過程中會出現許多錯誤的對應關系,造成配準誤差,影響人工魚群尋優的效率,本文綜合距離閾值、隨機采樣一致性(random sample consensus,RANSAC)模型、法向量夾角3種方法剔除錯誤對應關系,以提高算法尋優效率。

2.3.1 基于距離閾值

在通過FPFH特征得到匹配點對后,可以計算出匹配點對的歐氏距離。當對應點對的距離大于設置的距離閾值εd時,認為該對應點對為錯匹配點對并剔除該對應關系[16]。

2.3.2 基于RANSAC模型

RANSAC方法[17]通過在全局范圍內對待匹配對象和場景對象進行隨機采樣,由隨機采樣最小的n個樣本,得到初始參數模型,在包含異常點的樣本集中迭代驗證初始模型;在該驗證過程中,計算待驗證樣本點與初始模型的誤差,小于設置的閾值歸為內點;否則標記為外點。本文通過設置距離閾值εransac和迭代次數iter,將點云P″和Q″作為RANSAC模型的輸入,進行迭代。迭代完成后,認為外點的對應點對為錯匹配點對并剔除該對應關系。

2.3.3 基于法向量夾角

雖然通過距離閾值和RANSAC模型進行錯誤匹配關系的剔除,但仍存在一部分錯誤匹配關系。匹配點對的空間拓撲關系大概一致,因此本文基于匹配點對的法向量夾角進行錯誤對應關系的剔除。由于在點云數據密集處,并且搜索半徑不大情況下,每個點的法向量可以用局部擬合平面的法向量表示[18],方法如下:

1) 選擇M點最近的k個點,通過Kd-tree進行鄰近點搜索,確定M點的鄰近點集W={wi,1≤i≤k},設V為點集W的重心,L為過點M平面的法向量。通過對M的鄰域使用最小二乘法進行局部擬合平面,使得下式最小。

(7)

式(7)最小值的解可以通過求由最小二乘得到的矩陣C的最小特征值對應的特征向量[19]。

(8)

2) 計算經過RANSAC模型剔除后的對應點對的法向量夾角θ。

3) 當θ大于設定的閾值εθ時,則認為對應點對為錯匹配點對并剔除該對應關系。

2.4 佳點集人工魚群點云配準算法步驟

1) 設置算法的相關參數。

2) 對待配準的點云進行下采樣得到P′,利用3D SIFT特征點提取算法對采樣后的點進行特征點提取得到P″。

3) 基于佳點集初始化N條人工魚的初始位置。

4) 使用由人工魚的位置生成的剛性變換矩陣T對P″進行平移旋轉得到T(P″)。

5) 通過FPFH特征描述獲得T(P″)和Q″的對應關系并剔除錯誤對應關系,將剔除錯誤對應關系后對應點距離的均方根誤差作為適應度函數初值,并更新公告板。

6) 每條人工魚分別執行覓食、聚群、追尾行為,更新公告板和每條人工魚的適應度值。

7) 循環步驟4)～步驟6),達到最大迭代次數Tmax或2次適應度值小于設定的閾值后,輸出公告板結果。

佳點集人工魚群點云配準算法流程如圖3所示。

圖3 佳點集人工魚群點云配準算法流程

3 實驗結果及分析

實驗環境設計的代碼均采用C++編寫,使用open-source point cloud library(PCL)開源庫1.11.1,編譯器為Microsoft Visual C++(MSVC) 14.27,未開啟編譯優化。計算機硬件配置為Intel Core@ i5-8400處理器,2.80 GHz CPU,16 GiB內存,操作系統為Windows 10。

為了驗證本文基于佳點集人工魚群算法在點云配準過程上的有效性,首先設置算法的各項參數:種群規模N為5,移動步長step為0.005,嘗試次數trynumber為2,視野visual為0.15。由于本文算法局部最優不嚴重,忽略擁擠度因子δ。人工魚群最大迭代次數Tmax為15。平移量范圍為[-0.04,0.04]m,旋轉角度范圍[0°,360°]。

3.1 點云庫模型數據

本文的實驗數據包括斯坦福大學經典的Bunny、Dragon、Happy Buddha數據集,如圖4所示。其中:Bunny數據集選用bun-zipper點云;Dragon數據集選用dragonUpRight-0視角的點云;Happy Buddha數據集選用happyStandRight-0視角的點云。

圖4 實驗測試數據集

實驗過程中,選取模型中的點云作為源點云數據集,目標點云則通過設置一組平移旋轉參數將源點云中的點通過空間變換得到,空間變換后數據集的大小不變。點云數據集大小見表1所列。

表1 點云數據集

3.2 實驗結果

為了驗證本文提出的基于佳點集人工魚群的點云配準算法的性能,本文對ICP算法與本文算法+ICP算法進行了對比實驗。實驗過程數據見表2所列,配準后的配準實驗對比如圖5所示。表2中:平移參數Vx、Vy、Vz為沿坐標軸進行平移的數值,單位為m;旋轉角度α、β、γ為沿坐標軸進行旋轉的角度大小,單位為 °;t1為本文算法配準時間;t為使用ICP算法配準時間;t2為經本文算法粗配準后使用ICP算法配準的時間;RMSE-coa為本文算法粗配準精度,RMSE-fin為經過粗配準后使用ICP算法精配準的精度。其中ICP算法設置最大迭代次數200次,同時為了配準精度,ICP算法迭代過程中不設置下采樣。

表2 3種數據集按不同算法配準的時間與精度

圖5 傳統的ICP算法與本文算法+ICP算法的配準實驗對比

由表2可知:ICP算法對于初始位姿較好的點云,配準精度尚可,但初始位姿不好的情況下,易陷入局部最優,配準時間顯著增加,甚至配準失敗;而本文算法通過為ICP算法提供一個良好的初始位姿,在達到同等精度或更高精度的情況下,能減少ICP算法的配準時間;Bunny、Dragon、Happy Buddha點云數據集經過本文算法粗配準后再使用ICP算法配準,平均分別耗時2.663、4.958、8.085 s;相比直接使用ICP算法分別減少9.098、4.216、83.924 s。

在(0.02,0.02,0.02,60,45,45)這組平移旋轉參數下,Bunny、Dragon、Happy Buddha點云數據集采用本文算法+ICP算法比直接使用ICP算法的配準精度提高了5個數量級,配準時間分別減少16.692、13.096、118.924 s。而對初始位姿尚可的點云,采用本文算法+ICP算法比直接使用ICP算法進行配準,Bunny和Dragon數據集的配準時間平均約增加5 s,Happy Buddha數據集的配準時間平均約增加2 s,而其精度提高了1個數量級。

采用(0.02,0.02,0.02,60,45,45)這組平移旋轉參數得到目標點云,使用本文算法對Bunny、Dragon、Happy Buddha 3組數據集進行迭代。迭代尋優過程中的對比如圖6所示。

圖6 迭代次數曲線

從圖6可以看出,本文算法只需要迭代4次左右就能實現均方根誤差收斂。

4 結 論

本文利用佳點集改進人工魚群算法中種群初始化行為,增加了種群的多樣性,克服了基本人工魚群算法因初始種群分布不均易陷入局部最優的缺陷,并將該算法運用到點云配準過程中,提出了基于佳點集人工魚群算法的點云配準算法。通過采用取斯坦福大學提供的3組數據集進行由粗到精的配準實驗,并與ICP算法進行比較,發現本文算法對于初始位姿不好的點云,能避免傳統ICP算法因初始點云旋轉角度過大而配準失敗,配準精度可以提高5個數量級,同時縮短配準時間,進而表明本文算法具有較好的有效性與可靠性。