馬 衛(wèi)

(南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 江蘇 南京 210093)(南京旅游職業(yè)學(xué)院酒店管理學(xué)院 江蘇 南京 211100)

0 引 言

逆向工程是通過(guò)激光掃描等技術(shù)從樣品原件獲取三維數(shù)據(jù)并進(jìn)行預(yù)處理，然后對(duì)預(yù)處理的點(diǎn)云數(shù)據(jù)通過(guò)曲面分塊、數(shù)據(jù)擬合等操作實(shí)現(xiàn)三維重建。點(diǎn)云數(shù)據(jù)配準(zhǔn)是逆向工程中的一個(gè)核心問(wèn)題，是計(jì)算機(jī)視覺(jué)所有后續(xù)處理的基礎(chǔ)，其配準(zhǔn)結(jié)果在三維測(cè)量的精度和后續(xù)數(shù)據(jù)處理中起著至關(guān)重要的作用。

在三維重建過(guò)程中，獲取三維物體表面的真實(shí)數(shù)據(jù)卻因受測(cè)量設(shè)備、自遮擋與環(huán)境等因素的影響，實(shí)際測(cè)量過(guò)程中獲取的點(diǎn)云數(shù)據(jù)只是實(shí)體表面的部分?jǐn)?shù)據(jù)，且易導(dǎo)致平移或旋轉(zhuǎn)錯(cuò)位[1]，故需對(duì)被測(cè)物體在不同視角下進(jìn)行多次測(cè)量，并將各個(gè)視角下的點(diǎn)云數(shù)據(jù)合并到統(tǒng)一的坐標(biāo)系下，形成最終完整的點(diǎn)云數(shù)據(jù)，方便后續(xù)可視化等操作。點(diǎn)云數(shù)據(jù)配準(zhǔn)的實(shí)質(zhì)是把在不同的坐標(biāo)系中測(cè)量得到的數(shù)據(jù)點(diǎn)云進(jìn)行坐標(biāo)變換，以得到統(tǒng)一坐標(biāo)系下的整體數(shù)據(jù)模型。這給點(diǎn)云配準(zhǔn)帶來(lái)了許多挑戰(zhàn)[2]：(1)數(shù)據(jù)本身存在高噪聲、離群點(diǎn)等會(huì)影響配準(zhǔn)的精度；(2)在數(shù)據(jù)采集過(guò)程中，因三維掃描儀的自遮擋、視角和光線等問(wèn)題，存在數(shù)據(jù)獲取的缺失或部分重合等問(wèn)題，導(dǎo)致后期配準(zhǔn)對(duì)應(yīng)關(guān)系難以尋找，搜索難度較大；(3)點(diǎn)云數(shù)據(jù)的初始位置對(duì)配準(zhǔn)的性能影響較大。

最近鄰迭代配準(zhǔn)ICP(Iterate Closed Point)算法[3]則是當(dāng)前點(diǎn)云數(shù)據(jù)配準(zhǔn)過(guò)程中最具代表性、應(yīng)用最廣泛的剛性配準(zhǔn)算法。該算法以四元數(shù)配準(zhǔn)算法為基礎(chǔ)，在兩片點(diǎn)云中搜索相互對(duì)應(yīng)的歐氏距離最短的最近點(diǎn)對(duì)，通過(guò)不斷搜索迭代優(yōu)化，最終得到兩片點(diǎn)云剛體變換的最優(yōu)參數(shù)。ICP算法由于簡(jiǎn)單而被廣泛應(yīng)用，但卻易于陷入局部最優(yōu)。同時(shí)，該算法特別依賴于點(diǎn)云配準(zhǔn)的初始位置，當(dāng)兩片點(diǎn)云模型的初始位置變換較大，且當(dāng)存在噪聲點(diǎn)和離群點(diǎn)時(shí)則極易導(dǎo)致配準(zhǔn)失敗。為了解決這一系列問(wèn)題，許多學(xué)者提出了改進(jìn)策略[4-7]，如：基于概率論和統(tǒng)計(jì)的配準(zhǔn)策略[8-12]，基于特征對(duì)應(yīng)的配準(zhǔn)方法[13-14]，基于尺度迭代最近點(diǎn)的配準(zhǔn)方法SICP(Scaled Iterative Closest Point)[15]。ICP的改進(jìn)策略從不同程度上提高了原始算法的抗噪能力和配準(zhǔn)精度，但始終無(wú)法從本質(zhì)上解決其對(duì)初始位置敏感的缺陷。

點(diǎn)云配準(zhǔn)分為粗配準(zhǔn)和精配準(zhǔn)。粗配準(zhǔn)是在滿足降低配準(zhǔn)搜索維度的前提下，實(shí)現(xiàn)兩片點(diǎn)云的位置在同一坐標(biāo)系下的粗對(duì)齊。為了克服ICP算法對(duì)初始位置敏感的缺陷，一些基于群智能優(yōu)化策略[16-19]的粗配準(zhǔn)方法相繼提出，如：參數(shù)自適應(yīng)進(jìn)化算法[20]SaEvo(Self-Adaptive Evolution)、人工蜂群算法ABC(Artificial Bee Colony)、和聲搜索算法HS(Harmony Search)、生物地理學(xué)優(yōu)化算法BBO(Biogeography-Based Optimization)[21]等。這類方法為解決三維點(diǎn)云配準(zhǔn)問(wèn)題提供了新的思路和突破口，如基于粒子群算法PSO(Particle Swarm Optimization)[22]和基于遺傳算法GA(Genetic Algorithm)[23-24]的粗配準(zhǔn)技術(shù)可以為精配準(zhǔn)提供良好的初始位置，但全局優(yōu)化能力和配準(zhǔn)的魯棒性還不夠。相比于傳統(tǒng)的配準(zhǔn)方法，這類優(yōu)化方法有利于提高配準(zhǔn)精度，但又存在搜索時(shí)間長(zhǎng)、運(yùn)算效率低等問(wèn)題。雖然這些策略使用群體方式在求解空間內(nèi)加強(qiáng)尋優(yōu)搜索，但還是存在易陷入全局最優(yōu)的不足。針對(duì)上述問(wèn)題，本文提出一種布谷鳥(niǎo)全局優(yōu)化的三維點(diǎn)云配準(zhǔn)算法。

布谷鳥(niǎo)搜索算法(Cuckoo Search，CS)最早于2009年提出，是一種元啟發(fā)式全局優(yōu)化方法[25]，該方法模擬布谷鳥(niǎo)尋窩產(chǎn)卵的繁殖機(jī)理并基于萊維飛行(Lévy flights)而形成的一種搜索策略，從而表現(xiàn)出較好的全局優(yōu)化性能，算法參數(shù)設(shè)置少，全局尋優(yōu)速度快，與其他智能優(yōu)化算法相比具有較好的搜索性能。目前，該算法廣泛應(yīng)用于神經(jīng)網(wǎng)絡(luò)、工程設(shè)計(jì)和全局最優(yōu)化等領(lǐng)域[26-27]。

利用CS算法較強(qiáng)的萊維飛行全局搜索能力從而避免搜索過(guò)程陷入局部最優(yōu)。CS算法不僅具有較好的全局勘探能力，還大幅提高了局部搜尋的開(kāi)發(fā)性能，且適用于求解點(diǎn)云配準(zhǔn)優(yōu)化問(wèn)題。本文以對(duì)應(yīng)點(diǎn)距離最小為適應(yīng)度函數(shù)，將布谷鳥(niǎo)優(yōu)化算法作為尋優(yōu)策略實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的粗配準(zhǔn)，再利用ICP進(jìn)行精細(xì)配準(zhǔn)。計(jì)算機(jī)仿真實(shí)驗(yàn)結(jié)果表明，本文算法取得很好的搜索結(jié)果，尋優(yōu)率和精度顯著提高，效果令人滿意。

1 算法設(shè)計(jì)

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

點(diǎn)云數(shù)據(jù)配準(zhǔn)的兩個(gè)點(diǎn)集為待配準(zhǔn)點(diǎn)云P和目標(biāo)點(diǎn)云Q，其數(shù)學(xué)表示形式分別為：P={pi|pi∈R3,i=1,2,…,m}和Q={qi|qi∈R3,i=1,2,…,n}，其中m和n為兩片點(diǎn)云中點(diǎn)的數(shù)量。尋找兩個(gè)點(diǎn)集的空間變換，應(yīng)用最小二乘法使目標(biāo)函數(shù)值最小，目標(biāo)是使兩者離差平方和最小。

點(diǎn)云配準(zhǔn)的本質(zhì)是將多個(gè)視角下掃描獲取的點(diǎn)云數(shù)據(jù)統(tǒng)一到同一個(gè)坐標(biāo)系下，其過(guò)程是尋找兩片點(diǎn)云數(shù)據(jù)集的一系列空間變換，可以用變換矩陣T來(lái)表示三維空間幾何模型的變換關(guān)系。對(duì)于待配準(zhǔn)點(diǎn)云P和目標(biāo)點(diǎn)云Q，就是尋求三維空間內(nèi)最優(yōu)的變換矩陣T，其表示形式如式(1)所示。變換矩陣T有6個(gè)參數(shù)，包含了坐標(biāo)軸方向的平移量Vx、Vy、Vz和坐標(biāo)軸的旋轉(zhuǎn)角α、β、γ。

T=RxRyRzV

(1)

(2)

(3)

(4)

(5)

待配準(zhǔn)點(diǎn)云P和目標(biāo)點(diǎn)云Q經(jīng)過(guò)一系列空間變換，其對(duì)應(yīng)位置點(diǎn)的理想歐氏距離為最小值0，然而受測(cè)量時(shí)的誤差以及噪聲干擾等其他因素影響，兩片點(diǎn)云經(jīng)過(guò)空間變換無(wú)法到達(dá)理想歐氏距離。所以，點(diǎn)云配準(zhǔn)問(wèn)題實(shí)質(zhì)為求解全局最優(yōu)化問(wèn)題，尋求三維空間內(nèi)兩片點(diǎn)云最優(yōu)的剛體變換矩陣。布谷鳥(niǎo)優(yōu)化算法作為近年來(lái)新提出的一種群智能優(yōu)化方法，在解決復(fù)雜的多維空間優(yōu)化問(wèn)題中，具有很好的全局搜索和局部尋優(yōu)的性能。

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

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

特征點(diǎn)是描述曲面幾何形狀最基本的一種特征基元，在不同的坐標(biāo)系下能保持較好的一致性。目前，特征點(diǎn)提取的方法各異，主要有基于曲面重建的點(diǎn)云特征點(diǎn)提取方法[28]，通過(guò)領(lǐng)域選擇、張量投票和張量分析，降低了算法對(duì)噪聲和采樣質(zhì)量的依賴性。另外還有局部表面面片法LSP(Local Surface Patches)[29]，關(guān)鍵點(diǎn)特性評(píng)估法KPQ(Quality of Keypoints)[30]，固有形狀特性法ISS(Intrinsic Shape Signatures)[31]等，這類方法有不同的適應(yīng)范圍，LSP更適用于三角網(wǎng)格模型，而對(duì)于數(shù)據(jù)量較大的點(diǎn)云，KPQ方法有其一定局限性，本文采用ISS特征點(diǎn)提取算法相比于基于曲面重建的方法，其原理簡(jiǎn)單，便于實(shí)現(xiàn)，適用于分布均勻的點(diǎn)云數(shù)據(jù)的處理。

設(shè)點(diǎn)云數(shù)據(jù)有N個(gè)點(diǎn)，任意一點(diǎn)pti坐標(biāo)為(xi,yi,zi),i=0,1,…,N-1，則ISS特征點(diǎn)提取算法的具體步驟為：

(1)對(duì)點(diǎn)云上的每個(gè)點(diǎn)pti定義一個(gè)局部坐標(biāo)系，并設(shè)定每個(gè)點(diǎn)的搜索半徑rISS；

(2)查詢點(diǎn)云數(shù)據(jù)中每個(gè)點(diǎn)pti在半徑rISS周圍內(nèi)的所有點(diǎn)，計(jì)算其權(quán)值：

(6)

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

(7)

(5)設(shè)置閾值ε1和ε2，滿足式(8)的點(diǎn)即被標(biāo)記為ISS特征點(diǎn)。

(8)

1.3 布谷鳥(niǎo)優(yōu)化算法

基本布谷鳥(niǎo)搜索算法是模擬布谷鳥(niǎo)尋窩產(chǎn)卵的過(guò)程，將布谷鳥(niǎo)孵化寄生、尋窩搜索的生物特性形成理論和搜索策略，算法基于3條理想的規(guī)則[24]：

(1)每只布谷鳥(niǎo)隨機(jī)選擇寄生巢來(lái)孵化，每次只產(chǎn)生一個(gè)蛋；

(2)寄生巢被隨機(jī)選擇，最好的寄生巢將會(huì)被繼承到下一代；

(3)設(shè)定固定值的寄生巢，寄生巢的主人宿主鳥(niǎo)發(fā)現(xiàn)一個(gè)外來(lái)寄生蛋的概率是Pa[0,1]。

基于上述規(guī)則，宿主鳥(niǎo)可以拋出鳥(niǎo)蛋，或者放棄鳥(niǎo)巢并重新構(gòu)建一個(gè)新巢穴。其基本流程如算法1所示，其中：nFE為當(dāng)前評(píng)價(jià)次數(shù)；MaxNFEs為最大評(píng)價(jià)次數(shù)。

算法1CS算法

Begin

初始化種群n個(gè)宿主巢位置Xi(i=1,2,…,n);

計(jì)算適應(yīng)度值Fi=f(Xi),Xi=(xi1,xi2,…,xiD)T;

While(nFE

根據(jù)萊維飛行機(jī)制產(chǎn)生新的位置Xi;

計(jì)算新的位置Xi的適應(yīng)度值Fi;

隨機(jī)選擇候選位置Xj;

If(Fi>Fj)

用新位置解替代候選位置;

End

按發(fā)現(xiàn)概率pa丟棄差的位置;

偏好隨機(jī)游動(dòng)產(chǎn)生新的位置進(jìn)行替代;

最好位置保存;

End while

End

萊維飛行隨機(jī)游動(dòng)和偏好隨機(jī)游動(dòng)是布谷鳥(niǎo)優(yōu)化算法中兩個(gè)重要的搜索策略，負(fù)責(zé)局部搜索和全局搜索。CS算法在搜索過(guò)程主要包括三個(gè)步驟：(1)布谷鳥(niǎo)先在當(dāng)前位置的基礎(chǔ)上按萊維飛行隨機(jī)游動(dòng)方式產(chǎn)生新的位置，根據(jù)適應(yīng)度函數(shù)的評(píng)價(jià)，通過(guò)貪婪方式選擇較好的搜索位置。(2)為了增加搜索的多樣性，按照一定的概率pa丟棄部分新產(chǎn)生的位置。(3)采用偏好隨機(jī)游動(dòng)方式重新生成與被放棄位置相同數(shù)量的新位置，根據(jù)適應(yīng)度值評(píng)價(jià)，保存較好的搜索位置，完成一輪尋優(yōu)過(guò)程。

(9)

萊維飛行搜索機(jī)制除了隨機(jī)優(yōu)化搜索外，另一特性表現(xiàn)為偏好隨機(jī)游動(dòng)搜索策略，隨機(jī)游動(dòng)的各個(gè)新位置通過(guò)式(10)的混合變異和交叉操作產(chǎn)生。

(10)

在布谷鳥(niǎo)搜索策略中，萊維飛行搜索機(jī)制通過(guò)隨機(jī)游動(dòng)和偏好隨機(jī)游動(dòng)搜索策略達(dá)到全局勘探和局部尋優(yōu)的有效平衡。

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

點(diǎn)云配準(zhǔn)的過(guò)程是將兩個(gè)不在同一坐標(biāo)系下的點(diǎn)云數(shù)據(jù)集經(jīng)過(guò)一系列坐標(biāo)變換后，實(shí)現(xiàn)兩片點(diǎn)云對(duì)應(yīng)部分的重疊，配準(zhǔn)的效果取決于配準(zhǔn)誤差，通常由適應(yīng)度函數(shù)來(lái)體現(xiàn)。迭代最近點(diǎn)搜索采用k-D樹(shù)的方式提高最近點(diǎn)集的搜索速度，降低求解計(jì)算量，提高運(yùn)算效率。

三維點(diǎn)云配準(zhǔn)就是尋找待配準(zhǔn)點(diǎn)云到目標(biāo)點(diǎn)云間的變換矩陣T。在理想狀態(tài)下，變換求解誤差為0。然而由于獲取的點(diǎn)云在三維激光掃描中受環(huán)境或機(jī)器的干擾，獲取的點(diǎn)云數(shù)據(jù)過(guò)程會(huì)產(chǎn)生大量的干擾和噪音點(diǎn)，影響點(diǎn)云配準(zhǔn)的精度，導(dǎo)致存在誤差。受到測(cè)量誤差、噪聲點(diǎn)等影響，對(duì)應(yīng)點(diǎn)之間的距離通過(guò)不斷迭代計(jì)算始終無(wú)法達(dá)到理想位置，因此，點(diǎn)云配準(zhǔn)問(wèn)題實(shí)質(zhì)為全局優(yōu)化問(wèn)題的求解：尋求最優(yōu)的變換矩陣，使得掃描點(diǎn)集P={pi∈R3,i=1,2,…,m}與待配準(zhǔn)點(diǎn)集Q={qj∈R3,j=1,2,…,n}間的歐氏距離最小，將CS算法應(yīng)用到點(diǎn)云配準(zhǔn)優(yōu)化中，對(duì)點(diǎn)云配準(zhǔn)目標(biāo)函數(shù)中的變換矩陣進(jìn)行優(yōu)化，通過(guò)參數(shù)編碼和歸一化處理后對(duì)應(yīng)宿主巢的位置，利用布谷鳥(niǎo)優(yōu)化算法對(duì)點(diǎn)云模型進(jìn)行目標(biāo)函數(shù)的優(yōu)化，其建立模式搜索趨化的布谷鳥(niǎo)全局優(yōu)化函數(shù)為：

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

(11)

配準(zhǔn)算法用配準(zhǔn)后兩片點(diǎn)云對(duì)應(yīng)點(diǎn)之間的均方根(Root Mean Square, RMS)數(shù)值來(lái)表示兩片點(diǎn)云的配準(zhǔn)精度：

(12)

式中：數(shù)據(jù)集S表示點(diǎn)云P和Q的重疊部分。使用CS優(yōu)化的點(diǎn)云配準(zhǔn)算法定義目標(biāo)函數(shù)來(lái)描述配準(zhǔn)精度：RMS(P,Q)表示配準(zhǔn)后的兩片點(diǎn)云之間對(duì)應(yīng)點(diǎn)之間配準(zhǔn)誤差，衡量點(diǎn)云配準(zhǔn)的吻合度，值越小則配準(zhǔn)的精度越高。

在布谷鳥(niǎo)優(yōu)化算法粗配準(zhǔn)的基礎(chǔ)上，采用ICP方法進(jìn)行精細(xì)配準(zhǔn)，進(jìn)一步利用k-D樹(shù)快速搜索最近點(diǎn)對(duì)，提高點(diǎn)云配準(zhǔn)的效率。

2 實(shí) 驗(yàn)

為了驗(yàn)證本文CS算法在點(diǎn)云配準(zhǔn)優(yōu)化應(yīng)用上的有效性，選用不同點(diǎn)云庫(kù)中的模型和掃描有噪聲的模型進(jìn)行配準(zhǔn)實(shí)驗(yàn)。

2.1 點(diǎn)云庫(kù)模型配準(zhǔn)實(shí)驗(yàn)

在本節(jié)中，驗(yàn)證本文所引入CS算法實(shí)現(xiàn)由粗到精的三維點(diǎn)云配準(zhǔn)算法的有效性和可行性。本文的實(shí)驗(yàn)數(shù)據(jù)集包括斯坦福大學(xué)經(jīng)典的3個(gè)模型數(shù)據(jù)(Bunny，Happy Buddha和Dragon)和文獻(xiàn)中的3個(gè)模型數(shù)據(jù)(Hippo，Coati和Angel)，如表1所示，選擇2個(gè)不同視角下的點(diǎn)云，部分?jǐn)?shù)據(jù)含有噪音和離群點(diǎn)，其數(shù)據(jù)集大小如表2所示。

表1 實(shí)驗(yàn)測(cè)試數(shù)據(jù)集

表2 實(shí)驗(yàn)數(shù)據(jù)集說(shuō)明

在實(shí)驗(yàn)中，ICP算法和CS算法分別最大迭代50次和100次，旋轉(zhuǎn)角度范圍[0°,360°]，平移量范圍[-40 mm,40 mm]，實(shí)驗(yàn)通過(guò)MATLAB R2012b編程實(shí)現(xiàn)，計(jì)算機(jī)硬件配置為Intel Core i5-4300U，內(nèi)存8 GB。

點(diǎn)云配準(zhǔn)中，需要模式搜索趨化的布谷鳥(niǎo)全局優(yōu)化算法進(jìn)行目標(biāo)函數(shù)的優(yōu)化，對(duì)于算法的參數(shù)設(shè)置應(yīng)考慮種群規(guī)模、迭代次數(shù)、初始位置(旋轉(zhuǎn)角度和平移量)對(duì)性能的影響。通過(guò)實(shí)驗(yàn)和測(cè)試，最終參數(shù)設(shè)置為：布谷鳥(niǎo)巢穴的規(guī)模為20，發(fā)現(xiàn)概率Pa=0.25。本文實(shí)驗(yàn)設(shè)定最大迭代次數(shù)并獨(dú)立運(yùn)行30次。

配準(zhǔn)算法常常采用兩片點(diǎn)云配準(zhǔn)后對(duì)應(yīng)點(diǎn)集間的距離來(lái)表示兩片點(diǎn)云的吻合程度，其值越小配準(zhǔn)精度就越高，點(diǎn)云數(shù)據(jù)的單位為mm，為了便于比較，經(jīng)過(guò)算法優(yōu)化的結(jié)果如表3所示。

表3 粗精配準(zhǔn)精度結(jié)果

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

在這次實(shí)驗(yàn)中，需要測(cè)試點(diǎn)云簡(jiǎn)化與特征點(diǎn)提取的尺度對(duì)后續(xù)配準(zhǔn)的影響，從而確定合適的采樣參數(shù)和特征點(diǎn)提取的參數(shù)r、ε1和ε2的設(shè)置。首先測(cè)試點(diǎn)云均勻采樣率，采樣的尺度大小會(huì)影響后期的點(diǎn)云配準(zhǔn)過(guò)程中算法的計(jì)算量，采樣過(guò)高會(huì)影響計(jì)算的效率，采樣太低不能很好地表達(dá)點(diǎn)云數(shù)據(jù)的局部信息，合適的采樣比率對(duì)后期的配準(zhǔn)至關(guān)重要。本文通過(guò)多次實(shí)驗(yàn)，在6組模型數(shù)據(jù)的采樣測(cè)試中，最終確定采樣參數(shù)設(shè)定為0.1，可以有效保持點(diǎn)云數(shù)據(jù)的整體性，降低后續(xù)數(shù)據(jù)處理的運(yùn)算量，實(shí)驗(yàn)結(jié)果如表4所示。

表4 點(diǎn)云由粗到精配準(zhǔn)結(jié)果

在均勻采樣的基礎(chǔ)上，本文進(jìn)一步驗(yàn)證特征點(diǎn)提取，通過(guò)6組模型數(shù)據(jù)的特征提取實(shí)驗(yàn)，確定搜索半徑范圍rISS和特征點(diǎn)識(shí)別閾值ε1和ε2，其中模型數(shù)據(jù)，由于掃描點(diǎn)云的差異性，其搜索范圍rISS分別為0.02、5和10，ε1=ε2=0.6，可以有效保持點(diǎn)云數(shù)據(jù)的固有形狀特征信息，對(duì)于數(shù)據(jù)本身存在高噪聲、離群點(diǎn)等會(huì)影響配準(zhǔn)精度的點(diǎn)云具有較好的魯棒性。

2.3 布谷鳥(niǎo)優(yōu)化算法粗配準(zhǔn)性能

將CS與傳統(tǒng)的ICP算法進(jìn)行比較，在種群規(guī)模SN=20和最大的迭代次數(shù)100的前提下進(jìn)行實(shí)驗(yàn)。結(jié)果如表3和表4所示。

表3中給出兩個(gè)算法在6個(gè)模型數(shù)據(jù)配準(zhǔn)精度上比較的結(jié)果，本文的CS比傳統(tǒng)的ICP求解精度更好，表現(xiàn)出更加優(yōu)異的性能。表4中列舉了6個(gè)模型數(shù)據(jù)在視角1和視角2視角下的配準(zhǔn)結(jié)果，從表3和表4的結(jié)果可以看出，CS算法在粗配準(zhǔn)的精度上表現(xiàn)出了較好的性能。這是因?yàn)槠涓玫娜R維飛行全局搜索機(jī)制使得算法在配準(zhǔn)過(guò)程中很好地達(dá)到全局搜索與局部尋優(yōu)的有效平衡，在點(diǎn)云配準(zhǔn)中表現(xiàn)出更好的搜索效率和求解精度。

2.4 由粗到精配準(zhǔn)算法的驗(yàn)證

為了驗(yàn)證本文配準(zhǔn)策略流程的有效性和魯棒性，實(shí)驗(yàn)分別在6個(gè)模型數(shù)據(jù)進(jìn)行測(cè)試。配準(zhǔn)結(jié)果通過(guò)可視化的方式進(jìn)行呈現(xiàn)，如表4所示，給出輸入點(diǎn)云，進(jìn)行簡(jiǎn)化和特征點(diǎn)提取，然后利用CS進(jìn)行粗配準(zhǔn)，在粗配準(zhǔn)的基礎(chǔ)上進(jìn)行ICP精配準(zhǔn)，最后將變換參數(shù)映射到輸入的點(diǎn)云上得到最終的配準(zhǔn)結(jié)果。同時(shí)使用式(12)均方根差(Root Mean Square Error, RMSE)在對(duì)應(yīng)點(diǎn)間進(jìn)行量化，反映了點(diǎn)云配準(zhǔn)的精度，值越小，配準(zhǔn)效果越好。

表3顯示了模型數(shù)據(jù)的配準(zhǔn)結(jié)果，以視角1和視角2的配準(zhǔn)為例，本文的方法都能達(dá)到較好的配準(zhǔn)結(jié)果，RMS值在配準(zhǔn)后滿足配準(zhǔn)的精度要求，達(dá)到理想的精度數(shù)量級(jí)。

表3和表5中分別統(tǒng)計(jì)了本文算法在測(cè)試集數(shù)據(jù)視角1和視角2視角下的點(diǎn)云由粗到精配準(zhǔn)的求解精度和時(shí)間統(tǒng)計(jì)，從結(jié)果上來(lái)看，本文算法配準(zhǔn)效果較好，有一定的應(yīng)用價(jià)值。

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

2.5 算法運(yùn)行時(shí)間和精度的比較

運(yùn)算時(shí)間和精度能夠很好地考量點(diǎn)云配準(zhǔn)算法的性能。為了驗(yàn)證本文算法在初始位置旋轉(zhuǎn)或者平移變換后配準(zhǔn)的魯棒性，本文選擇Bunny的視角1和視角2進(jìn)行實(shí)驗(yàn)，并進(jìn)一步將本文算法(CS+ICP)與傳統(tǒng)的ICP直接配準(zhǔn)在初始位置變換的情況下進(jìn)行實(shí)驗(yàn)比較。結(jié)果如表6和圖1所示。

表6 本文算法與傳統(tǒng)的ICP在初始位置變換下的配準(zhǔn)比較

(a)初始位置變換后的配準(zhǔn)比較(π/4,-π/4,-π/4,0.04,-0.03,0.04)

表6中，旋轉(zhuǎn)角度是指沿三個(gè)坐標(biāo)軸旋轉(zhuǎn)的角度大小，平移參數(shù)表示沿三個(gè)坐標(biāo)軸平移的數(shù)值，tICP、tCS、tICP′、tsum分別表示直接用ICP配準(zhǔn)時(shí)間、本文CS粗配準(zhǔn)時(shí)間、ICP精配準(zhǔn)時(shí)間和本文粗精配準(zhǔn)總的時(shí)間，時(shí)間單位為s。

為了比較的公平性，ICP最大迭代50次，CS初始配準(zhǔn)迭代100次，運(yùn)行時(shí)間和求解精度如表7所示。傳統(tǒng)的ICP在初始位置變換后，往往陷入了局部最優(yōu)，配準(zhǔn)時(shí)間急劇上升，平均耗時(shí)22.79 s，而且配準(zhǔn)失敗，如圖1所示。而本文算法中ICP收斂速度快速，配準(zhǔn)時(shí)間平均為0.74 s，這是因?yàn)椴捎肅S算法保障了ICP配準(zhǔn)的初始位置。雖然CS平均耗時(shí)8.36 s，但這是在最大迭代次數(shù)100的情況下所測(cè)，實(shí)際情況下，多數(shù)配準(zhǔn)只需要50次左右迭代即可滿足ICP精配準(zhǔn)初始位置迭代要求，并且配準(zhǔn)精度顯著提高，達(dá)到理想的配準(zhǔn)精度要求。經(jīng)過(guò)旋轉(zhuǎn)平移變換的兩片點(diǎn)云，整體上粗精配準(zhǔn)的平均時(shí)間在10.84 s，時(shí)間相比于直接ICP配準(zhǔn)降低明顯，而且能有效配準(zhǔn)。

為了進(jìn)一步與已有的群智能優(yōu)化的點(diǎn)云配準(zhǔn)算法相比較，本文選用通用點(diǎn)云庫(kù)SAMPL中的2個(gè)典型點(diǎn)云模型(Frog和Angel’)進(jìn)行比較實(shí)驗(yàn)。兩個(gè)模型分別選用0和40度視角下的兩片點(diǎn)云進(jìn)行旋轉(zhuǎn)90度，并用ICP、BBO、ABC和HS算法進(jìn)行對(duì)比實(shí)驗(yàn)。算法參數(shù)根據(jù)文獻(xiàn)[22]進(jìn)行設(shè)置，ABC、BBO和HS的種群規(guī)模分別為20、100和50，最大迭代時(shí)間統(tǒng)一設(shè)置為20 s。實(shí)驗(yàn)結(jié)果如表7所示。

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

從表7中可以看出，傳統(tǒng)的ICP算法對(duì)初始位置比較敏感，容易陷入局部最優(yōu)導(dǎo)致配準(zhǔn)失敗。本文算法相比于其他群智能優(yōu)化算法具有較好的精度優(yōu)勢(shì)，表現(xiàn)出較好的搜索性能。

通過(guò)多次實(shí)驗(yàn)和配準(zhǔn)效果來(lái)看，當(dāng)兩片點(diǎn)云在沒(méi)有旋轉(zhuǎn)角度和平移的情況下，ICP算法能得到較好的配準(zhǔn)效果，但隨著待配準(zhǔn)點(diǎn)云的初始位置產(chǎn)生旋轉(zhuǎn)和平移變換后，ICP算法很容易陷入局部最優(yōu)，配準(zhǔn)效果大大降低，而采用本文算法進(jìn)行粗配準(zhǔn)則有助于解決該問(wèn)題，降低算法對(duì)配準(zhǔn)初始位置的敏感性。由表6可知，利用本文搜索策略相比于傳統(tǒng)的ICP算法求解精度更優(yōu)，能有效降低對(duì)點(diǎn)云配準(zhǔn)初始位置的要求，不同的初始變換位置下能得到更好的搜索優(yōu)化結(jié)果，配準(zhǔn)效果較好。

3 結(jié) 語(yǔ)

本文采用萊維飛行機(jī)制的布谷鳥(niǎo)全局優(yōu)化算法來(lái)解決點(diǎn)云配準(zhǔn)優(yōu)化問(wèn)題。在整個(gè)配準(zhǔn)過(guò)程中先采用點(diǎn)云簡(jiǎn)化與特征點(diǎn)提取，然后利用CS算法進(jìn)行目標(biāo)函數(shù)的優(yōu)化，獲得點(diǎn)云變換矩陣的全局最優(yōu)解，然后再通過(guò)精配準(zhǔn)獲得最終的點(diǎn)云配準(zhǔn)效果。通過(guò)不同的模型數(shù)據(jù)對(duì)算法的性能進(jìn)行測(cè)試，結(jié)果表明，本文算法在點(diǎn)云配準(zhǔn)優(yōu)化問(wèn)題中，較好地解決ICP算法對(duì)點(diǎn)云初始位置嚴(yán)重依賴的問(wèn)題，且很好地抑制早熟的能力，提高全局尋優(yōu)能力，同時(shí)求解精度也相比于傳統(tǒng)的ICP算法大幅提高，在點(diǎn)云配準(zhǔn)中有很好的魯棒能力，具有較好的應(yīng)用價(jià)值。