馬 衛(wèi),李微微

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

0 引 言

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

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

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

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

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

受生物昆蟲群體行為的啟發(fā),仿生群智能優(yōu)化策略是通過仿生模擬自然界種群行為進(jìn)而提出的解決工業(yè)、生產(chǎn)等各類問題的優(yōu)化方法。能有效解決傳統(tǒng)優(yōu)化方法受約束條件限制的局限性,全局搜索能力強(qiáng),目前,已逐步應(yīng)用于三維點(diǎn)云配準(zhǔn)優(yōu)化問題,并受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。

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

(1)提出了一種改進(jìn)的異步學(xué)習(xí)二階振蕩人工蜂群算法完成對(duì)點(diǎn)云的初始配準(zhǔn),提高對(duì)點(diǎn)云配準(zhǔn)空間的全局搜索能力,解決配準(zhǔn)對(duì)應(yīng)關(guān)系難以尋找、搜索難度較大的問題;

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

1 二階振蕩人工蜂群算法的點(diǎn)云配準(zhǔn)

1.1 點(diǎn)云配準(zhǔn)模型

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

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

T=RxRyRzV

(1)

(2)

(3)

(4)

(5)

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

1.2 點(diǎn)云簡(jiǎn)化與特征點(diǎn)提取

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

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

ISS特征點(diǎn)提取算法的具體步驟如下：

(1)確定局部坐標(biāo)系：設(shè)點(diǎn)云數(shù)據(jù)有N個(gè)點(diǎn),任意一點(diǎn)pti坐標(biāo)為(xi,yi,zi),i=0,1,…,N-1,對(duì)三維點(diǎn)云中的任一點(diǎn)pti定義其所在的局部坐標(biāo)系,設(shè)定搜索半徑rISS;

(2)權(quán)值計(jì)算：點(diǎn)云中計(jì)算權(quán)值本質(zhì)上是為了生成多個(gè)當(dāng)前點(diǎn)pti到周圍點(diǎn)ptj的向量,理想情況下pti的法線應(yīng)垂直于這些向量。對(duì)點(diǎn)云數(shù)據(jù)中每個(gè)點(diǎn)pti所在rISS半徑范圍內(nèi)點(diǎn)的權(quán)值進(jìn)行計(jì)算：

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

(6)

(3)計(jì)算協(xié)方差矩陣：計(jì)算三維點(diǎn)云中每個(gè)點(diǎn)pti的協(xié)方差矩陣：

(7)

(5)標(biāo)識(shí)特征點(diǎn)：設(shè)置條件閾值ε1和ε2,滿足式(8)的任一點(diǎn)即被標(biāo)記為ISS特征點(diǎn)。

(8)

1.3 改進(jìn)的人工蜂群算法

1.3.1 基本的人工蜂群算法

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

1.3.2 基于二階振蕩擾動(dòng)策略的人工蜂群算法

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

(1)搜索機(jī)制。

傳統(tǒng)的ABC的搜索機(jī)制主要表現(xiàn)為隨機(jī)搜索,其全局尋優(yōu)能力強(qiáng)。但由于其指導(dǎo)能力不足,使得早熟收斂,易陷入局部最優(yōu)。GABC算法受PSO的啟發(fā),提出改進(jìn)的搜索方程,如式(9)所示。

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

(9)

其搜索策略取決于當(dāng)前位置(在上面方程的第一項(xiàng))、隨機(jī)鄰域搜索(第二項(xiàng))以及全局最優(yōu)位置指導(dǎo)搜索(第三項(xiàng))。式(9)中搜索策略的第二項(xiàng)為隨機(jī)選擇一只蜜蜂位置進(jìn)行逼近,第三項(xiàng)則為按全局最優(yōu)位置指導(dǎo)搜索,該兩項(xiàng)易存在同時(shí)異向搜索,使得算法擾動(dòng)異常,缺乏指導(dǎo)不利于群體進(jìn)化。在求解復(fù)雜函數(shù)優(yōu)化問題中表現(xiàn)出迭代后期搜索能力不足,早熟收斂的缺陷。對(duì)于一種進(jìn)化算法,其搜索策略直接影響著全局搜索能力的優(yōu)劣。為此,該文借鑒二階振蕩微粒群[40]的搜索策略在GABC算法的思想上改進(jìn)人工蜂群算法的搜索能力。充分利用ABC算法易與其他技術(shù)相結(jié)合的優(yōu)勢(shì),增強(qiáng)搜索能力。改進(jìn)的搜索策略如式(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)異步變化學(xué)習(xí)因子。

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

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

初始化：

參數(shù)設(shè)置：種群規(guī)模SN及其他參數(shù)MCN, limit,c1,c2;

隨機(jī)產(chǎn)生SN初始種群{Xi|i=1,2,…,SN};

計(jì)算適應(yīng)度值f(Xi);

設(shè)置{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

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

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

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

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

If Cycle

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

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

Else

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

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

End

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

采用貪婪選擇機(jī)制評(píng)價(jià)新的候選解;

End

跟隨蜂階段：

計(jì)算跟隨概率;

產(chǎn)生新的候選解;

采用貪婪選擇機(jī)制評(píng)價(jià)新的候選解;

偵查蜂階段：

If max(triali)>limit then

根據(jù)偵查蜂隨機(jī)生成一個(gè)新解代替Xi;

End

保存當(dāng)前最好的食物源位置;

Cycle=Cycle+1;

End while

End

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

此外,跟隨蜂搜索機(jī)制仍采用傳統(tǒng)ABC算法的隨機(jī)搜索機(jī)制,有利于加強(qiáng)全局隨機(jī)搜索能力。引入了異步變化學(xué)習(xí)因子的二階振蕩進(jìn)化方程的SOABC算法,其更為高效地提高人工蜂群搜索的多樣性,提升搜索性能,使優(yōu)化算法在搜索早期全局探測(cè)性能好,迭代振蕩;在搜索的后期聚焦小范圍內(nèi)的尋優(yōu)以實(shí)現(xiàn)逐漸收斂的過程。搜索前期其表現(xiàn)為全局探測(cè)搜索,搜索后期則為精度搜索。

1.3.3 SOABC算法在點(diǎn)云配準(zhǔn)中的應(yīng)用

采用三維激光掃描儀以采集物體表面信息的點(diǎn)集合被俗稱為點(diǎn)云,一般為離散數(shù)據(jù),不同視角下掃描的數(shù)據(jù)難以完全對(duì)應(yīng),故點(diǎn)云數(shù)據(jù)的配準(zhǔn)即為尋找同區(qū)域點(diǎn)云數(shù)據(jù)的最佳的對(duì)應(yīng)位置,該位置需要在配準(zhǔn)過程中采用相應(yīng)的準(zhǔn)則來衡量。

本節(jié)將文中算法應(yīng)用到點(diǎn)云配準(zhǔn)優(yōu)化中,采用參數(shù)編碼和歸一化處理將SOABC算法的目標(biāo)函數(shù)映射為食物源的位置,將二階振蕩擾動(dòng)策略的人工蜂群算法對(duì)點(diǎn)云模型進(jìn)行目標(biāo)函數(shù)的優(yōu)化,全局優(yōu)化函數(shù)為：

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

(16)

基于二階振蕩擾動(dòng)策略的人工蜂群算法以采集點(diǎn)云數(shù)據(jù)間的最短距離為評(píng)價(jià)準(zhǔn)則,滿足點(diǎn)云間均方根數(shù)值的配準(zhǔn)精度要求為：

(17)

其中,S為兩片點(diǎn)云P和Q配準(zhǔn)的重疊數(shù)據(jù)集,誤差值RMS(P,Q)以評(píng)判采集數(shù)據(jù)點(diǎn)云配準(zhǔn)間的精度,精度越高結(jié)果值越小。在SOABC人工蜂群算法粗配準(zhǔn)的基礎(chǔ)上,利用ICP策略實(shí)現(xiàn)三維點(diǎn)云數(shù)據(jù)的精細(xì)配準(zhǔn),采用k-d tree以尋找最優(yōu)點(diǎn)集,從而加快點(diǎn)云配準(zhǔn)的速度。

2 實(shí)驗(yàn)結(jié)果及分析

在本節(jié)中,研究由粗到精的三維點(diǎn)云配準(zhǔn)算法。為了便于比較,實(shí)驗(yàn)數(shù)據(jù)集選用了文獻(xiàn)[19]中測(cè)試的模型和場(chǎng)景數(shù)據(jù),采用了斯坦福大學(xué)經(jīng)典的4個(gè)模型數(shù)據(jù)(“Bunny”“Happy Buddha”“Dragon”和“Armadillo”)和點(diǎn)云庫(kù)網(wǎng)站中的1個(gè)室內(nèi)場(chǎng)景數(shù)據(jù)(“Apartment”)作為實(shí)驗(yàn)測(cè)試的數(shù)據(jù)集,如圖1所示。另外,采用了多個(gè)視角下的含離群點(diǎn)噪聲的點(diǎn)云數(shù)據(jù)。

圖1 實(shí)驗(yàn)數(shù)據(jù)集

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

2.1 點(diǎn)云特征提取

為了降低點(diǎn)云配準(zhǔn)的計(jì)算量和提高配準(zhǔn)的效率,實(shí)驗(yàn)中采用均勻采樣以簡(jiǎn)化點(diǎn)云。首先對(duì)采樣參數(shù)的設(shè)置進(jìn)行實(shí)驗(yàn)確定。經(jīng)過4組模型數(shù)據(jù)和1組場(chǎng)景數(shù)據(jù)的采樣測(cè)試進(jìn)行模擬實(shí)驗(yàn),最終設(shè)置采樣參數(shù)為0.1,能較好地保持點(diǎn)云數(shù)據(jù)的完整性,減少三維點(diǎn)云后續(xù)配準(zhǔn)的計(jì)算量。

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

2.2 改進(jìn)的人工蜂群算法粗配準(zhǔn)性能

在本部分,驗(yàn)證了文中算法SOABC在不同的模型和視角下的粗配準(zhǔn)性能,將SOABC與傳統(tǒng)的ABC算法進(jìn)行了比較,SOABC的參數(shù)設(shè)置為L(zhǎng)imit=D*SN,D=6,c1max=c2max=0.5,c1min=c2min=2.5。實(shí)驗(yàn)在相同的條件下進(jìn)行統(tǒng)一測(cè)試,種群規(guī)模SN設(shè)置為20,最大迭代次數(shù)為100。實(shí)驗(yàn)結(jié)果如圖2和表1所示。

表1 配準(zhǔn)統(tǒng)計(jì)

圖2 ABC和SOABC算法點(diǎn)云配準(zhǔn)性能比較

圖2中展示了4個(gè)視角下,Dragon和Armadillo兩個(gè)模型數(shù)據(jù)兩兩配準(zhǔn)的結(jié)果。ABC和SOABC兩個(gè)算法在4個(gè)模型數(shù)據(jù)上進(jìn)行了配準(zhǔn)精度的比較,改進(jìn)的優(yōu)化算法尋優(yōu)性能提升明顯,搜索精度更高。從表1和圖2的結(jié)果不難看出,SOABC相比于傳統(tǒng)ABC在配準(zhǔn)的精度上更為優(yōu)異。

2.3 粗精配準(zhǔn)的有效性實(shí)證

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

圖3 視角1& 2下的點(diǎn)云配準(zhǔn)

模型數(shù)據(jù)和場(chǎng)景數(shù)據(jù)的實(shí)驗(yàn)結(jié)果在圖3中進(jìn)行了展示,同時(shí)對(duì)不同視角下的采集數(shù)據(jù)進(jìn)行配準(zhǔn),從而完成了較好的粗精配準(zhǔn)過程,配準(zhǔn)效果較好。具體的配準(zhǔn)精度和配準(zhǔn)耗時(shí)如表2、表3所示,達(dá)到了理想的配準(zhǔn)精度閾值要求,應(yīng)用價(jià)值好。

表2 配準(zhǔn)精度統(tǒng)計(jì)

表3 配準(zhǔn)時(shí)間統(tǒng)計(jì)

2.4 與其他群智能優(yōu)化算法的比較

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

實(shí)驗(yàn)結(jié)果如表4所示。

表4 文中算法與其他算法的配準(zhǔn)比較

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

2.5 算法的魯棒性能比較

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

實(shí)驗(yàn)結(jié)果表明,傳統(tǒng)ICP直接配準(zhǔn)魯棒性不足,對(duì)初始位置敏感,配準(zhǔn)容易陷入局部最優(yōu)。文中算法能有效解決上述問題,精度上優(yōu)于ICP算法,能有效降低對(duì)點(diǎn)云配準(zhǔn)初始位置的敏感性要求,全局優(yōu)化性能好,配準(zhǔn)精度高。

3 結(jié)束語

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