基于布谷鳥優(yōu)化的三維點云配準(zhǔn)算法

馬 衛(wèi)

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

0 引 言

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

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

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

點云配準(zhǔn)分為粗配準(zhǔn)和精配準(zhǔn)。粗配準(zhǔn)是在滿足降低配準(zhǔn)搜索維度的前提下，實現(xiàn)兩片點云的位置在同一坐標(biāo)系下的粗對齊。為了克服ICP算法對初始位置敏感的缺陷，一些基于群智能優(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]等。這類方法為解決三維點云配準(zhǔ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)精度，但又存在搜索時間長、運(yùn)算效率低等問題。雖然這些策略使用群體方式在求解空間內(nèi)加強(qiáng)尋優(yōu)搜索，但還是存在易陷入全局最優(yōu)的不足。針對上述問題，本文提出一種布谷鳥全局優(yōu)化的三維點云配準(zhǔn)算法。

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

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

1 算法設(shè)計

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

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

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

T=RxRyRzV

(1)

(2)

(3)

(4)

(5)

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

1.2 點云簡化與特征點提取

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

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

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

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

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

(6)

(3)計算每個點pti的協(xié)方差矩陣：

(7)

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

(8)

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

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

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

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

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

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

算法1CS算法

Begin

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

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

While(nFE

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

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

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

If(Fi>Fj)

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

End

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

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

最好位置保存;

End while

End

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

(9)

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

(10)

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

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

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

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

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

(11)

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

(12)

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

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

2 實 驗

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

2.1 點云庫模型配準(zhǔn)實驗

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

表1 實驗測試數(shù)據(jù)集

表2 實驗數(shù)據(jù)集說明

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

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

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

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

2.2 點云簡化與特征點提取

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

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

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

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

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

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

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

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

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

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

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

運(yùn)算時間和精度能夠很好地考量點云配準(zhǔn)算法的性能。為了驗證本文算法在初始位置旋轉(zhuǎn)或者平移變換后配準(zhǔn)的魯棒性，本文選擇Bunny的視角1和視角2進(jìn)行實驗，并進(jìn)一步將本文算法(CS+ICP)與傳統(tǒng)的ICP直接配準(zhǔn)在初始位置變換的情況下進(jì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)角度是指沿三個坐標(biāo)軸旋轉(zhuǎn)的角度大小，平移參數(shù)表示沿三個坐標(biāo)軸平移的數(shù)值，tICP、tCS、tICP′、tsum分別表示直接用ICP配準(zhǔn)時間、本文CS粗配準(zhǔn)時間、ICP精配準(zhǔn)時間和本文粗精配準(zhǔn)總的時間，時間單位為s。

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

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

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

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

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

3 結(jié) 語

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