基于布谷鳥優化的三維點云配準算法

馬 衛

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

0 引 言

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

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

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

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

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

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

1 算法設計

1.1 點云配準模型

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

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

T=RxRyRzV

(1)

(2)

(3)

(4)

(5)

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

1.2 點云簡化與特征點提取

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

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

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

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

(2)查詢點云數據中每個點pti在半徑rISS周圍內的所有點，計算其權值：

(6)

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

(7)

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

(8)

1.3 布谷鳥優化算法

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

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

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

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

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

算法1CS算法

Begin

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

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

While(nFE

根據萊維飛行機制產生新的位置Xi;

計算新的位置Xi的適應度值Fi;

隨機選擇候選位置Xj;

If(Fi>Fj)

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

End

按發現概率pa丟棄差的位置;

偏好隨機游動產生新的位置進行替代;

最好位置保存;

End while

End

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

(9)

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

(10)

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

1.4 CS算法在點云配準中的應用

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

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

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

(11)

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

(12)

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

在布谷鳥優化算法粗配準的基礎上，采用ICP方法進行精細配準，進一步利用k-D樹快速搜索最近點對，提高點云配準的效率。

2 實 驗

為了驗證本文CS算法在點云配準優化應用上的有效性，選用不同點云庫中的模型和掃描有噪聲的模型進行配準實驗。

2.1 點云庫模型配準實驗

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

表1 實驗測試數據集

表2 實驗數據集說明

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

點云配準中，需要模式搜索趨化的布谷鳥全局優化算法進行目標函數的優化，對于算法的參數設置應考慮種群規模、迭代次數、初始位置(旋轉角度和平移量)對性能的影響。通過實驗和測試，最終參數設置為：布谷鳥巢穴的規模為20，發現概率Pa=0.25。本文實驗設定最大迭代次數并獨立運行30次。

配準算法常常采用兩片點云配準后對應點集間的距離來表示兩片點云的吻合程度，其值越小配準精度就越高，點云數據的單位為mm，為了便于比較，經過算法優化的結果如表3所示。

表3 粗精配準精度結果

2.2 點云簡化與特征點提取

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

表4 點云由粗到精配準結果

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

2.3 布谷鳥優化算法粗配準性能

將CS與傳統的ICP算法進行比較，在種群規模SN=20和最大的迭代次數100的前提下進行實驗。結果如表3和表4所示。

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

2.4 由粗到精配準算法的驗證

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

表3顯示了模型數據的配準結果，以視角1和視角2的配準為例，本文的方法都能達到較好的配準結果，RMS值在配準后滿足配準的精度要求，達到理想的精度數量級。

表3和表5中分別統計了本文算法在測試集數據視角1和視角2視角下的點云由粗到精配準的求解精度和時間統計，從結果上來看，本文算法配準效果較好，有一定的應用價值。

表5 配準時間統計

2.5 算法運行時間和精度的比較

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

表6 本文算法與傳統的ICP在初始位置變換下的配準比較

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

表6中，旋轉角度是指沿三個坐標軸旋轉的角度大小，平移參數表示沿三個坐標軸平移的數值，tICP、tCS、tICP′、tsum分別表示直接用ICP配準時間、本文CS粗配準時間、ICP精配準時間和本文粗精配準總的時間，時間單位為s。

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

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

表7 本文算法與其他算法的配準比較

從表7中可以看出，傳統的ICP算法對初始位置比較敏感，容易陷入局部最優導致配準失敗。本文算法相比于其他群智能優化算法具有較好的精度優勢，表現出較好的搜索性能。

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

3 結 語

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