改進人工蜂群算法的點云數據配準優化研究

馬 衛,李微微

(南京旅游職業學院 酒店管理學院,江蘇 南京 211100)

0 引 言

點云配準是計算機視覺后續處理的基礎,是計算機形狀建模、三維物體識別、逆向工程等領域的一個核心問題。由于獲取三維模型點云數據受被測物體測量設備條件限制、遮擋與光照環境影響等常常導致無法將多次測量掃描的模型數據統一到同一個測量坐標系中[1]。三維點云數據模型的配準被視為通過一定策略的坐標變換,使得不同視角下測量獲取的數據模型統一到同一坐標系中的計算過程。目前,點云配準依然存在著一些技術難題[2]。首先,點云數據的高噪聲、離群點等存在的自身不足會影響后續的配準精度;其次,配準的核心是借助一定的策略尋找兩片點云的對應關系,然而由于光線、視角和遮擋等不定因素使得數據采集過程難以精確搜索重疊和缺失的掃描數據;最后,往往最容易忽視的是采集的三維模型點云數據,由于其對初始位置的敏感性帶來了配準性能的未知性,往往直接影響搜索的性能和效率[3]。目前,點云配準算法主要歸為以下幾類：

第一,以ICP算法為代表的配準策略,通過歐氏距離的評判進行優化迭代,以獲取三維點云數據的剛體變換。該方法在對應關系點集確定后再進行最優剛體變換的計算,重復該操作過程,直到收斂條件滿足為止。ICP算法雖然是目前配準領域影響最大、應用最廣的迭代策略,但是依然存在配準過程易陷入局部最優的問題。此外,迭代最近點算法對點云配準的初始位置有嚴重的依賴性,甚至對兩片點云模型的接近程度要求極高,在部分噪聲點、離群點干擾影響的情況下往往難以精確配準,失敗率高。ICP的許多改進策略[4-7]也相繼提出,這些算法在點云選擇、有效配準等方面起到了一定的作用[8]。

第二,一些學者提出了基于統計的配準方法。Tsin和Kanade采用概率密度估計的策略以表示點云分布,發表了核心相關(Kernel Correlation,KC)算法[9]。利用相似度測量來減小點云之間的距離。還有學者應用高斯混合模型(Gaussian Mixture Model,GMM)來表示點云以改進配準精度[10-11]。由于點云配準的數據點集需要兩兩進行比較計算,往往使得計算復雜度高。為了有效解決ICP算法對于初始位置敏感的問題,基于概率論的方法[12-13]被逐步提出。如一致點漂移(Coherent Point Drift,CPD)算法,魯棒性能好,計算效率高,但是往往受初始參數選擇的影響,容易導致局部早熟收斂。為了解決此類問題,魯棒點匹配(Robust Point Matching,RPM)算法[14]和相應的改進策略[15]被不斷提出,這類方法應用了退火算法以減小窮舉搜索時間。但是,當有部分點集缺失或噪聲干擾的情況下,RPM算法的配準策略也無計可施,這一點在文獻[16]中進行了驗證。

第三,基于特征對應的配準方法[17-19]。ICP算法依賴于對應關系,對兩幅點云的初始位置非常敏感。這類方法假設局部描述子提供了一組候選匹配,其中可能包括許多離群點。然后尋求這些對應關系的最大子集,可以使用非剛性形變產生完全一致的有界失真,作為一個約束優化問題,利用迭代加權最小二乘算法進行求解。上述方法的不足是當對應有缺失或誤差時,配準結果將會受到巨大影響。

第四,近年來,為了更好地解決傳統ICP算法易陷入局部最優的不足,一些學者提出了采用群智能優化的策略[20-23]進行三維點云數據配準的方法,從而克服ICP算法容易陷入局部最優的問題。其中,參數自適應進化算法(Self-Adaptive Evolution,SaEvo)[24]、生物地理學優化算法(Biogeography-Based Optimization,BBO)[25]、和諧搜索策略(Harmony Search,HS)[26]等方法為解決三維點云數據配準問題帶來了新的突破途徑,粒子群優化算法(Particle Swarm Optimization,PSO)[27]和采用遺傳算法(Genetic Algorithm,GS)[28]的優化技術以實現較好的粗配準的精度要求,但優化算法仍然存在魯棒性不足、全局搜索性能不高的缺陷。上述策略相比于傳統的配準技術在精度上有所提升,但也帶來了計算量較大、運算效率低等問題。文獻[25]表明,目前的人工蜂群算法在三維深度圖像配準中相比于BBO、HS等其他的進化算法更具優勢。

受生物昆蟲群體行為的啟發,仿生群智能優化策略是通過仿生模擬自然界種群行為進而提出的解決工業、生產等各類問題的優化方法。能有效解決傳統優化方法受約束條件限制的局限性,全局搜索能力強,目前,已逐步應用于三維點云配準優化問題,并受到國內外學者的廣泛關注。

由于ICP算法對初始點云位置有較高的要求,表現為對初始位置敏感,搜索過程易陷入局部最優,一些學者對此進行了深入研究[29]。比如,先求解各點曲率形成特征點進行初始匹配,再采用傳統的迭代最近點精配準的方法,效果較好,這類策略對特征提取的精度提出了更高的要求。受上述思想的啟發,該文對輸入的點云模型進行均勻采樣,將采樣后的點云通過固有形狀特征點(Intrinsic Shape Signature,ISS)方法進行特征點提取,然后基于異步學習的二階振蕩人工蜂群算法進行點云配準的優化,經過迭代優化求解后得到的解視為配準變換矩陣的最優解,將變換矩陣作用于原始模型,實現點云模型的粗配準,然后再利用ICP算法進行精配準。該策略可以有效地克服ICP算法對初始配準嚴重依賴的缺陷,能實現較好的配準精度,具有一定的應用價值。主要貢獻如下：

(1)提出了一種改進的異步學習二階振蕩人工蜂群算法完成對點云的初始配準,提高對點云配準空間的全局搜索能力,解決配準對應關系難以尋找、搜索難度較大的問題;

(2)提出了一種用于三維點云配準空間的由粗到精coarse-to-fine的配準算法,可以有效降低點云配準對初始位置的嚴重依賴。

1 二階振蕩人工蜂群算法的點云配準

1.1 點云配準模型

P和Q分別表示數據模型中的待配準點云和目標點云,數學形式表示為：P={pi|pi∈R3,i=1,2,…,m}和Q={qi|qi∈R3,i=1,2,…,n},式中m和n表示點云P和Q中點的數量。三維點云數據配準的目標是通過一定的空間變換使P和Q離差平方和最小[30]。

為了將多個視角下采集的點云數據統一到同一個坐標系下,需要對點云數據集進行空間變換的計算,采用向量T以表示三維空間幾何模型的變換矩陣,如式(1)所示。另外,變換的向量矩陣T有參數6個,其中,Vx、Vy、Vz分別表示沿著3個坐標軸的平移量,α、β、γ為繞3個坐標軸的旋轉角。變換矩陣T表示為：

T=RxRyRzV

(1)

(2)

(3)

(4)

(5)

根據優化策略進行空間變換,點云P和Q的對應點之間的距離理想值為0,然而受噪聲點和測量誤差等因素的干擾,點云P和Q的對應配準則無法達到理想值。進而,點云配準問題可視為一個全局最優化問題,即為求解最優的三維空間內兩片點云的剛體變換矩陣[31]。人工蜂群算法被視作求解優化問題極具優勢的一類群智能優化方法,具有很好的尋優精度和求解性能。相比于早期的遺傳算法、粒子群算法、蟻群算法等元啟發式進化策略具有一定的優勢。

1.2 點云簡化與特征點提取

為了更好地描述點云配準過程和更有效地進行特征點提取,對于輸入的兩片點云,首先按一定比率參數進行均勻采樣,從而降低點云后續運算的數據處理量,提高運算效率。

特征點作為一類特征基元可以較好地反映曲面幾何的形狀特征,不受空間變換的影響,一致性保持較好。其中,特征點提取的方法主要有基于曲面重建的點云特征點提取方法[32]、局部表面面片法(Local Surface Patches,LSP)[33]、關鍵點特性評估法(Quality of Keypoints,KPQ)[34]、固有形狀特性法[35]等,這類方法受數據模型的影響其應用領域不同[36]。文中采用適用于處理均勻分布的固有形狀特性法ISS特征點以提取點云數據。

ISS特征點提取算法的具體步驟如下：

(1)確定局部坐標系：設點云數據有N個點,任意一點pti坐標為(xi,yi,zi),i=0,1,…,N-1,對三維點云中的任一點pti定義其所在的局部坐標系,設定搜索半徑rISS;

(2)權值計算：點云中計算權值本質上是為了生成多個當前點pti到周圍點ptj的向量,理想情況下pti的法線應垂直于這些向量。對點云數據中每個點pti所在rISS半徑范圍內點的權值進行計算：

wij=1/|pti-ptj|,|pti-ptj|

(6)

(3)計算協方差矩陣：計算三維點云中每個點pti的協方差矩陣：

(7)

(5)標識特征點：設置條件閾值ε1和ε2,滿足式(8)的任一點即被標記為ISS特征點。

(8)

1.3 改進的人工蜂群算法

1.3.1 基本的人工蜂群算法

人工蜂群算法(Artificial Bee Colony,ABC)作為一種高效靈活的智能優化算法日益脫穎而出。該算法利用蜂群的角色分工和協作機制,全局尋優能力強。ABC算法與粒子群等智能優化算法性能相比,表現出其控制參數少、性能優越的特性[37-38]。研究表明,該算法性能優異,易與其他技術相結合以改進原算法的性能,具有廣泛的適用性。

1.3.2 基于二階振蕩擾動策略的人工蜂群算法

傳統ABC算法處理約束優化、復合的和一些不可分離函數優化問題時,存在著早熟收斂、后期收斂速度變慢易陷入局部最優解的缺點。這是因為ABC算法的搜索策略具有全局搜索能力強,而存在局部尋優性能相對不足的問題。為了進一步改進ABC算法求解點云配準空間優化問題的性能,有效避免算法求解復雜空間優化問題早熟收斂、搜索性能不足的問題,改進的ABC算法基于全局最優指導人工蜂群(Gbest-guided ABC,GABC)[39]算法的尋優性能的思想。GABC最早由Zhu和Kwong兩位學者提出,該算法受PSO算法搜索方程的啟發,提出利用全局最好解指導搜索,從而取得了更好的搜索效果。該文引入二階振蕩機制優化算法性能,從而達到在算法前期遏制過快收斂、加強鄰域搜索振蕩的目的。并在迭代后期加速收斂,有助于提高搜索精度與效率。為了進一步利用異步變化學習因子指導二階振蕩機制達到平衡優化算法中尋優速度與求解精度的矛盾,實現了一種基于異步變化學習因子指導二階振蕩的人工蜂群算法(Second-order Oscillation of Artificial Bee Colony,SOABC)。該算法利用異步變化學習因子的二階振蕩,在雇傭蜂群覓食搜索初期,增加空間搜索的多樣性,避免搜索過程陷入局部最優,擴大全局搜索范圍;迭代后期能加強搜索,提高求解精度,逐步收斂到最優解。該算法具有簡單,能有效地避免早熟,精度高,且適于高維等特點。

(1)搜索機制。

傳統的ABC的搜索機制主要表現為隨機搜索,其全局尋優能力強。但由于其指導能力不足,使得早熟收斂,易陷入局部最優。GABC算法受PSO的啟發,提出改進的搜索方程,如式(9)所示。

vi,j=xi,j+φi,j(xi,j-xk,j)+ψi,j(yj-xk,j)

(9)

其搜索策略取決于當前位置(在上面方程的第一項)、隨機鄰域搜索(第二項)以及全局最優位置指導搜索(第三項)。式(9)中搜索策略的第二項為隨機選擇一只蜜蜂位置進行逼近,第三項則為按全局最優位置指導搜索,該兩項易存在同時異向搜索,使得算法擾動異常,缺乏指導不利于群體進化。在求解復雜函數優化問題中表現出迭代后期搜索能力不足,早熟收斂的缺陷。對于一種進化算法,其搜索策略直接影響著全局搜索能力的優劣。為此,該文借鑒二階振蕩微粒群[40]的搜索策略在GABC算法的思想上改進人工蜂群算法的搜索能力。充分利用ABC算法易與其他技術相結合的優勢,增強搜索能力。改進的搜索策略如式(10)(11)所示。

vi(t+1)=wvi(t)+φ1(pi-(1+ξ1)xi(t)-

ξ1xi(t-1))+φ2(pg-(1+ξ2)xi(t)-

ξ2xi(t-1))

(10)

xi(t+1)=xi(t)+vi(t+1)

(11)

(2)異步變化學習因子。

為了避免二階振蕩對算法搜索蜜源性能的過度消耗,有效提高算法搜索策略的學習能力,該文進一步將權重w、學習因子c1和c2的傳統固定取值改進為異步變化的設定。學習因子c1與c2決定了雇傭蜂本身經驗信息和其他蜂群經驗信息對搜索位置運行軌跡的影響,反映種群之間的信息交流。如果c1為0,則搜索策略中的個體喪失認知能力,必須依靠群體的整體趨向能力進行搜索,一旦面臨復雜的求解問題,表現為早熟收斂。如果c2為0,種群中的個體信息分享能力不足,表現為傳統ABC算法策略的隨機搜索,其搜索到全局最優的性能下降。所以,為了更為有效地控制學習因子的取值范圍,進一步利用異步變化學習因子來更好地平衡二階振蕩機制的搜索效率。

w=μ+η·rand(0,1)

(12)

μ=μmin+ (μmax-μmin)·rand(0,1)

(13)

c1=c1min+ (c1max-c1min)·Cycle/MCN

(14)

c2=c2min+ (c2max-c2min)·Cycle/MCN

(15)

SOABC算法的偽代碼如算法1所示。

算法1：SOABC偽代碼。

Begin

初始化：

參數設置：種群規模SN及其他參數MCN, limit,c1,c2;

隨機產生SN初始種群{Xi|i=1,2,…,SN};

計算適應度值f(Xi);

設置{triali=0|i=1,2,…,SN}

φ1=c1·rand(0,1),φ2=c2·rand(0,1),Cycle=1;

While (Cycle≤MCN)

雇傭蜂階段：

Fori=1 to SN

設置μ=μmin+ (μmax-μmin)·rand(0,1)

w=μ+η·rand(0,1)

c1=c1min+ (c1max-c1min)·Cycle/MCN

c2=c2min+ (c2max-c2min)·Cycle/MCN;

If Cycle

設置ξ1=2·sqrt(φ1)·rand(0,1)/φ1

ξ2=2·sqrt(φ2)·rand(0,1)/φ2;

Else

設置ξ1=2·sqrt(φ1)·(1+rand(0,1))/φ1

ξ2=2·sqrt(φ2)·(1+rand(0,1))/φ2;

End

根據公式(10)生成候選解;

采用貪婪選擇機制評價新的候選解;

End

跟隨蜂階段：

計算跟隨概率;

產生新的候選解;

采用貪婪選擇機制評價新的候選解;

偵查蜂階段：

If max(triali)>limit then

根據偵查蜂隨機生成一個新解代替Xi;

End

保存當前最好的食物源位置;

Cycle=Cycle+1;

End while

End

新的搜索策略主要改進了雇傭蜂的搜索機制,具有較好的全局收斂性,搜索策略中不僅利用了上一代的個體信息,而且利用隨機數ξ的取值來調節全局搜索能力和局部開采能力,使得算法在前期有較強的全局搜索能力,不易陷入局部最優,在找到較好的蜜源后,策略后期注重更為細尺度的搜索,以促進收斂。值得說明的是,算法在搜索過程的早期和晚期,ξ靈活取值,搜索力度可以動態調整,從而有效地提高搜索性能的多樣性,算法的全局優化能力顯著增強。

此外,跟隨蜂搜索機制仍采用傳統ABC算法的隨機搜索機制,有利于加強全局隨機搜索能力。引入了異步變化學習因子的二階振蕩進化方程的SOABC算法,其更為高效地提高人工蜂群搜索的多樣性,提升搜索性能,使優化算法在搜索早期全局探測性能好,迭代振蕩;在搜索的后期聚焦小范圍內的尋優以實現逐漸收斂的過程。搜索前期其表現為全局探測搜索,搜索后期則為精度搜索。

1.3.3 SOABC算法在點云配準中的應用

采用三維激光掃描儀以采集物體表面信息的點集合被俗稱為點云,一般為離散數據,不同視角下掃描的數據難以完全對應,故點云數據的配準即為尋找同區域點云數據的最佳的對應位置,該位置需要在配準過程中采用相應的準則來衡量。

本節將文中算法應用到點云配準優化中,采用參數編碼和歸一化處理將SOABC算法的目標函數映射為食物源的位置,將二階振蕩擾動策略的人工蜂群算法對點云模型進行目標函數的優化,全局優化函數為：

F(T)=min‖T(Pm)-Qn‖2

(16)

基于二階振蕩擾動策略的人工蜂群算法以采集點云數據間的最短距離為評價準則,滿足點云間均方根數值的配準精度要求為：

(17)

其中,S為兩片點云P和Q配準的重疊數據集,誤差值RMS(P,Q)以評判采集數據點云配準間的精度,精度越高結果值越小。在SOABC人工蜂群算法粗配準的基礎上,利用ICP策略實現三維點云數據的精細配準,采用k-d tree以尋找最優點集,從而加快點云配準的速度。

2 實驗結果及分析

在本節中,研究由粗到精的三維點云配準算法。為了便于比較,實驗數據集選用了文獻[19]中測試的模型和場景數據,采用了斯坦福大學經典的4個模型數據(“Bunny”“Happy Buddha”“Dragon”和“Armadillo”)和點云庫網站中的1個室內場景數據(“Apartment”)作為實驗測試的數據集,如圖1所示。另外,采用了多個視角下的含離群點噪聲的點云數據。

圖1 實驗數據集

ICP算法和SOABC算法分別最大迭代50次和100次,人工蜂群的種群規模設置為20,旋轉角度范圍[0°,360°],平移量范圍[-40 mm,40 mm],實驗采用Matlab R2016b編程實現,計算機處理器配置為Intel Core i5-4300U,8 GB內存。

2.1 點云特征提取

為了降低點云配準的計算量和提高配準的效率,實驗中采用均勻采樣以簡化點云。首先對采樣參數的設置進行實驗確定。經過4組模型數據和1組場景數據的采樣測試進行模擬實驗,最終設置采樣參數為0.1,能較好地保持點云數據的完整性,減少三維點云后續配準的計算量。

實驗進一步模擬了特征點提取的特征提取參數ε1、ε2和搜索半徑范圍rISS的取值設置,根據點云分布的差異不同,搜索范圍rISS分別為0.02和0.2,ε1=ε2=0.6,從而有利于維持采集點云的特征信息,有利于提高自身存在離群點、高噪聲等點云數據的配準精度和魯棒性能。

2.2 改進的人工蜂群算法粗配準性能

在本部分,驗證了文中算法SOABC在不同的模型和視角下的粗配準性能,將SOABC與傳統的ABC算法進行了比較,SOABC的參數設置為Limit=D*SN,D=6,c1max=c2max=0.5,c1min=c2min=2.5。實驗在相同的條件下進行統一測試,種群規模SN設置為20,最大迭代次數為100。實驗結果如圖2和表1所示。

表1 配準統計

圖2 ABC和SOABC算法點云配準性能比較

圖2中展示了4個視角下,Dragon和Armadillo兩個模型數據兩兩配準的結果。ABC和SOABC兩個算法在4個模型數據上進行了配準精度的比較,改進的優化算法尋優性能提升明顯,搜索精度更高。從表1和圖2的結果不難看出,SOABC相比于傳統ABC在配準的精度上更為優異。

2.3 粗精配準的有效性實證

通過4個模型數據和1個室內場景數據的多次實驗,以測試由粗到精配準性能的有效性和魯棒性。具體驗證流程為點云輸入、點云簡化、特征提取、粗精配準、結果輸出,整個實驗工作流程如圖3所示。實驗中采用式(17)的RMS(P,Q)誤差以衡量點云配準的精度效果。

圖3 視角1& 2下的點云配準

模型數據和場景數據的實驗結果在圖3中進行了展示,同時對不同視角下的采集數據進行配準,從而完成了較好的粗精配準過程,配準效果較好。具體的配準精度和配準耗時如表2、表3所示,達到了理想的配準精度閾值要求,應用價值好。

表2 配準精度統計

表3 配準時間統計

2.4 與其他群智能優化算法的比較

進一步與近年來新提出的群智能優化三維點云配準算法進行比較,為了實驗的公平性,采用通用的點云庫SAMPL中4種典型的點云模型(Tele,Bird,Angel和Frog)進行相同條件下的實驗比較,部分實驗數據直接摘自文獻[41]。點云模型分別選用了0度和40度視角下的兩片點云進行對比實驗。算法參數根據文獻[41]進行設置,DE2014、ABC2016[42]和EABC2020分別為近年來新提出的群智能優化配準策略,其種群規模分別為16,20和20,SOABC為文中策略,種群規模為20,最大迭代時間統一設置為200 s,各算法在是否滿足模型成功配準閾值的條件下獨立運行30次以記錄成功配準的次數。

實驗結果如表4所示。

表4 文中算法與其他算法的配準比較

從表4中可以看出,SOABC算法相比于近年來新提出的群智能優化策略,配準精度和成功率更高,這是由于采用了二階振蕩優化策略使得配準成功次數顯著提高,避免以往的優化策略容易陷入局部最優導致配準失敗的不足。文中算法在點云模型配準中相比于其他群智能優化算法具有一定的精度優勢,表現出較好的搜索性能。

2.5 算法的魯棒性能比較

實驗中,進一步從運算效率、魯棒性能的角度考察算法的運算性能。文中以bunny數據模型為例,測試了將初始位置旋轉、平移變換后配準的魯棒性能。在初始位置變換的情況下,將SOABC+ICP配準與傳統ICP配準進行了比較實驗,實驗中,ICP算法最大迭代次數為50,SOABC初始配準迭代次數為100。在初始位置變換后,傳統ICP配準早熟收斂,出現陷入局部最優的問題,耗時量平均為22.79 s,且配準失敗。SOABC+ICP求解精度高,配準速度快,由于SOABC算法保障了ICP配準的初始位置,ICP配準平均消耗時間0.57 s。盡管SOABC平均耗時為8.36 s,而文中實驗是在最大迭代次數為100的情況下測試而得,實際配準應用僅僅迭代50次左右即可滿足ICP精配準的初始位置要求,并提高了配準精度。總的來看,文中算法粗精配準的平均時間為8.93 s,比直接ICP配準更加有效,精度更優。

實驗結果表明,傳統ICP直接配準魯棒性不足,對初始位置敏感,配準容易陷入局部最優。文中算法能有效解決上述問題,精度上優于ICP算法,能有效降低對點云配準初始位置的敏感性要求,全局優化性能好,配準精度高。

3 結束語

將二階振蕩的思想引入到蜂群算法中,提出了一種基于異步學習因子的二階振蕩人工蜂群算法以解決三維點云數據的配準問題。算法通過點云簡化、特征提取,再利用SOABC智能優化算法進行變換矩陣的全局優化,完成點云數據的粗精配準求解過程。算法性能驗證采用不同模型數據和場景數據的大量模擬實驗,結果表明,提出的基于二階振蕩的人工蜂群算法的點云配準,能有效地避免傳統ICP算法對初始位置敏感性問題,全局搜索能力強,尋優精度高,應用于點云配準有很好的魯棒性能,有一定的應用價值。在處理大數據量和存在噪聲的點云模型中有很好的尋優精度和抗噪能力,在計算時間和尋優能力方面優于傳統的ICP點云配準策略,具有更強的穩定性、適應性和通用性。