基于混合算法的點云配準方法研究

任偉建, 高夢宇, 高銘澤, 張 鵬, 劉 丹

(1. 東北石油大學 a. 電氣信息工程學院； b. 黑龍江省網絡化與智能控制重點實驗室, 黑龍江 大慶 163318；2. 中國石油管道局工程有限公司 設計分公司, 河北 廊坊 065000； 3. 中國海洋石油集團有限公司 東方石化有限責任公司, 海南 東方 572600； 4. 中國石油天然氣股份有限公司 遼河油田分公司鉆采工藝研究院, 遼寧 盤錦 124010)

0 引 言

點云配準是將來自不同角度的點云數據匹配到同一坐標系的過程[1], 此過程采用了剛性變換的方法, 它是三維重建中最重要且最困難的步驟, 直接影響著三維重建的精度與效率, 在該領域中得到了諸多學者的熱切關注, 同時也在三維建模、計算機視覺、逆向工程、SLAM等[2]諸多領域中有非常廣泛的應用。目前, 比較主流的配準算法是迭代最近點算法, 即ICP (Iterative Closest Point) 算法, 該算法是Besl等[3]于1992年提出的, 其基本思想是通過旋轉、平移使兩個點集之間的距離最小。算法第1步根據計算出的不同點云間的歐氏距離進行不同點對的匹配工作; 第2步在獲取已匹配點對的基礎上, 求取兩組點對坐標變換的參數; 第3步使用最小二乘迭代法求取目標函數, 并使結果最小直至滿足設定條件。不同于基于其他特征的配準算法, 在運用ICP算法配準過程中, 點對的匹配度高, 但其仍存在一些缺點。ICP算法對初始點云的位置條件要求嚴苛, 收斂速度慢且易陷入局部最優。對于ICP算法的不足, 國內外研究人員對此進行了改進, Greenspan等[4]在ICP算法中引入最近鄰域問題, 提高了最近點的搜索速度, 而Batlle等[5]、 Du等[6]的仿射法都只解決了部分問題, 仍存在配準精度低等問題。為提高配準的精度, 筆者引入人工螢火蟲算法和粒子群算法并對其進行改進, 利用改進后的新算法對點云進行初始配準。

1995年Kennedy等[7]提出粒子群優化算法(PSO： Particle Swarm Optimization), 該算法是一種基于鳥群覓食行為的新興智能仿生算法。由于群體中的粒子相互之間會發生規律性運動, 產生的群體性智能可作為粒子群優化算法運行的理論依據, 使其在一定區域內完成優化搜索工作。粒子群算法在擁有結構簡單、 全局搜索的能力強等優勢的同時, 仍會由于過早收斂使搜索結果陷于局部最優, 并在運行時出現迭代暫停的現象。人工螢火蟲算法(GSO： Glowworm Swarm Optimization)[8]是近年來比較新穎的一種仿生算法, 它模擬了在一定范圍內螢火蟲發光越強吸引同伴越多的現象。該算法具有良好的全局搜索能力, 同時也存在著耗時多、 精度低等缺點。針對粒子群算法和人工螢火蟲算法存在的不足, 研究者們已做出了部分改進, 文獻[9]通過融合模式搜索, 加快算法收斂效率, 并求得精度較高的解; 文獻[10]針對粒子群算法過早收斂且易陷于局部最優等缺陷, 將混沌序列引入初期粒子群, 從而構建新型的混沌粒子群混合優化算法; 文獻[11]引入動態調整自適應步長的策略改進人工螢火蟲算法; 文獻[12]將引入混沌序列后的粒子群和經過權重修正的自適應策略相融合, 從而加速算法收斂。但是, 針對人工螢火蟲算法或粒子群算法的單一改進不能突顯出算法真正的優勢, 使其具有一些局限性。因此, 筆者利用優勢互補思想, 將粒子群算法與改進后的人工螢火蟲算法結合, 搜索全局最優解, 在加快算法收斂速度的同時提高解的精度。

筆者針對ICP算法對初始點云位置要求高且易陷于局部最優的不足, 提出一種初始配準加精細配準的點云配準方法。首先, 改進人工螢火蟲算法, 通過引入Logistic映射初始化種群, 并提出一種基于動態分組策略的自適應步長方法, 然后針對粒子群算法易于陷入局部最優的缺點, 利用優勢互補的思想將改進后的人工螢火蟲算法與粒子群算法結合, 把最小二乘迭代后搜索的最優結果作為粒子群算法最初的種群數據, 并利用該算法的優勢搜索全局最優解。其次, 考慮到ICP算法配準需要較好的迭代初始位置才能收斂, 提出將初始配準和精細配準相結合, 在初始配準階段使用改進后的人工自適應螢火蟲-粒子群算法(AAGPSO： Adaptive Artificial Glowworm-Particle Swarm Optimization), 在之后的精細配準階段使用ICP算法, 以提高配準精度與算法效率。對原始ICP配準方法和改進配準方法進行比較和誤差分析表明, 改進后配準方法更加有效。

1 改進的自適應人工螢火蟲粒子群算法

1.1 基本思想

人工螢火蟲算法模仿螢火蟲在一定的區域里發光越強, 吸引同伴越多的現象, 是一種最近幾年發展起來的智能仿生算法[13-14]。該算法能較好地進行局部搜索, 但搜索時間長且準確度低。因此, 為給精細配準提供良好的初值, 提高配準效率和精度, 將人工螢火蟲算法與粒子群算法相結合, 根據優勢互補思想, 提出一種新型的混合算法： 自適應人工螢火蟲-粒子群算法。

在搜索初期, 筆者首先將Logistic映射引入人工螢火蟲算法, 利用混沌運動的遍歷性混沌初始化算法, 將混沌序列引入人工螢火蟲算法能均勻分布初始的螢火蟲種群, 使算法的搜索效果更加顯著, 從而解決人工螢火蟲算法收斂速度慢、 解的精度低的問題。其次將位移權重引入算法, 并對位移權重進行調整, 然后將種群按照適應度值的分布進行分組從而提高算法的運行效率。最后串聯以上算法生成一種新型混合算法為自適應人工螢火蟲-粒子群算法。

自適應人工螢火蟲-粒子群算法在算法前半階段采用已優化的人工螢火蟲算法, 將搜索到的解作為下半階段粒子群算法的初始數據, 再通過粒子群算法搜索全局最優解。優化后的人工螢火蟲算法能搜索到局部最優解, 粒子群算法提高了尋優的效率與精度, 使整體尋優過程得到優化。

1.2 種群初始化

對種群參數進行合理的初始化可增強算法的全局搜索能力, 從而提高所求解的精度。在人工螢火蟲算法運行初期, 由于目標范圍不確定且目標區域廣闊而導致盲目搜索, 無法確定種群位置的最優解, 所以從種群初始位置開始尋找最優解已成為算法的基本操作。但若選擇的初始種群零散分布或集中于某一區域內, 則算法在運行開始后會立即收斂到部分種群集中區域, 這種情況易使算法陷入局部最優解。因此, 筆者引入混沌序列初始化種群, 避免發生算法陷入局部最優區域的問題。

混沌運動[15]是一種確定系統中出現的具有遍歷性的無規則運動, 能在一定的區域里按其自身不重復地遍歷所有的狀態。相比于無序隨機搜索, 利用混沌變量進行搜索更能增強被搜索種群的多樣性。因此, 筆者引入混沌序列, 在一定大小的搜索空間中使初始種群均勻分布, 以使算法所得解更加精準, 豐富搜索種群類別, 提高算法搜索能力。選擇取值范圍為(0,1)的混沌變量an, 范圍為[0,4]的控制參數μ, 通過Logistic映射混沌初始化人工螢火蟲算法, 其迭代式為

an+1=μan(1-an)

(1)

當μ∈[3.57,4.00]時, 可使序列an產生混沌狀態[16]。將螢火蟲的位置信息xi映射為混沌變量an

(2)

則xi=an(xmax-xmin)+xmin

(3)

1.3 自適應步長的調整

在人工螢火蟲算法運算過程中, 螢火蟲移動的步長會影響算法的收斂效果[17]。螢火蟲個體較小的移動步長雖會使所求得的解更加精確, 但會在一定程度上降低算法的運行速率; 當步長值較大時, 種群個體移動較快, 可得到較好的收斂效果, 加快了算法運行速率, 但較大步長易使個體錯過最優位置, 使解的精度較低。因此, 筆者選擇基于動態分組策略對步長進行自適應調整, 在保證算法收斂速度的同時將解的精度提高。設人工螢火蟲的位移慣性權重為ωs, 依據粒子群算法中慣性權重調節粒子速度的原則, 將人工螢火蟲算法位置更新為

(4)

其中s為移動步長,xi(t)為第i只螢火蟲在時刻t位置。

調整自適應步長時, 種群質量不同, 賦予的權重也不同。對比個體平均適應度值, 將種群分為3類： 優秀種群、 一般種群和較差種群。對于優秀種群, 往往選取較小的移動步長并賦予較小權重, 從而加速算法全局收斂; 對于一般種群, 種群個體的位移權重始終被設置為固定值, 從而平衡全局搜索和局部搜索能力; 對于較差種群, 將其剔除, 并以一般種群的最優個體為圓心, 螢火蟲感知范圍為半徑, 隨機生成與所剔除的種群數相匹配的新種群, 從而達到豐富種群的種類、 增強算法的全局性的效果。

步長的自適應調整策略的具體步驟如下。

1) 對第1組優秀種群動態調整位移權重

(5)

其中ωs_min是已經定義的位移權重的最小值。

2) 使第2組一般種群的位移權重保持為固定值。

3) 剔除第3組較差種群, 以一般種群中比較優異的個體為圓心, 螢火蟲感知范圍rs為半徑, 隨機生成新種群代替被剔除的較差種群。

1.4 自適應人工螢火蟲粒子群算法流程

通過上述思想, 將人工螢火蟲算法與粒子群算法相結合, 得改進后的自適應人工螢火蟲-粒子群算法的流程圖如圖1所示。

圖1 AAGPSO算法流程圖Fig.1 AAGPSO algorithm flow chart

2 基于ICP優化算法的點云配準

2.1 基于權重策略剔除噪聲點與誤匹配點對

點云數據配準[18]即在兩個點云集中找到一一對應的數據點, 并將其轉換到同一個坐標系中, 獲得一個完整的三維點云數據的計算過程。在進行點云數據配準時, 根據位置與方向不同將其分為兩階段, 即初始配準和精細配準[19]。初始配準即全局配準, 在初始配準過程中, 兩片重疊率低的點云數據被拉近, 減小點云之間的旋轉和平移造成的誤差, 從而為后續的精細配準打下基礎。

在點云配準過程中, ICP算法默認最好配準效果是待匹配點云的對應點是一一對應的, 沒有其他干擾存在, 但在算法實際配準的過程中, 點云之間若存在未完全包含關系, 則會出現許多噪聲點和誤匹配點對, 造成較大配準偏差[20]。

基于ICP算法配準偏差較大的特點, 筆者提出一種基于權重策略的噪聲點與誤匹配點對解決辦法。該方法首先通過限制距離權重, 計算待匹配點對的歐氏距離, 去除低于閾值的噪聲點, 其次通過限制特征權重, 計算匹配點法向量之間的夾角, 去除低于閾值的錯誤匹配點對。具體描述如下。

1) 限制距離權重。對應點對之間的距離信息在確定對應點對的同時將被獲取, 當獲取的兩個對應點對之間的距離過大時則認為該對應點對是噪聲點。所以筆者對距離權重進行限制, 即距離越大其權重越小的思想, 將噪聲點去除, 設定閾值ε1, 則引入的距離權重

(6)

其中d(pi,xi)為對應點pi和xi的歐式距離,dmax為對應點pi和xi之間的最大距離。如果計算得出的距離權重wd小于事先給定的閾值ε1時, 則該對應點對被判定是噪聲點且在點云中刪除該點對。

2) 限制特征權重。雖然限制距離權重可確定點云中的噪聲點并對噪聲點進行適當的去噪處理, 但在對應點對中依舊有一部分無法去除的噪聲點。雖然點云中的對應點集所處的坐標系不同, 但待匹配的點云之間的空間拓撲關系大概一致, 都可經過平移和旋轉而進行變換?；谝陨显? 筆者使用特征權重, 即特征越一致其權重就越大的思想, 將誤匹配的點對去除。其中方向一致性特征權重

wn=n(pi)·n(xj)

(7)

其中n(pi)和n(xj)分別表示對應點對pi和qj的法向量, 其法向量估計方法定義如下。

(8)

最小。

應用最小二乘法, 可得到以下3×3矩陣

(9)

其中F的最小特征值對應的特征向量即可作為法向量n(pi)的近似值。

2.2 改進算法描述

在基于深度圖像的三維重建領域中, 三維點云配準一直是不可缺少的一步。在諸多配準算法中, ICP算法最為著名。但ICP算法仍具有許多局限性有待改進：當點云所包含點的數量大規模增長時, 其搜索時間復雜度隨之增長, 不利于實際應用; 當待匹配的點云初始位置距離較遠時, ICP算法的收斂速度變慢, 算法容易陷入局部最優, 從而降低配準效率及精度; 當直接對不滿足包含關系的點云進行對應點對的搜索時, 可能產生錯誤的匹配點對, 使最終的匹配結果受到影響。

針對以上問題, 筆者對ICP算法進行改進, 提出一種優化的點云配準方法, 在ICP算法中引入AAGPSO混合算法。運用AAGPSO算法確定初始點云位置, 計算更新后的適應度值, 當最佳適應度值增量小于給定的閾值0.01時, 初始配準結束, 然后繼續采用ICP實現精細配準。此方法避免了配準的盲目性, 能對配準過程進行優化, 在保證算法魯棒性的同時, 提高了點云配準的效率和精度。改進后的AAGPSO-ICP混合算法具體實現步驟如下。

Step2 對源點集P構建kd-tree, 并搜索源點集P最近點已確定的對應點對。

搜索具體過程如下。

1) 輸入kd-tree判斷點云數據是否為空, 若為空則返回空值。

2) 進行二叉搜索[21]。首先判斷當前進行搜索的節點, 若不是葉子節點則將該節點與分割軸在當前維度下進行比較, 將小于分割軸的點轉向左子樹比較, 否則轉向右子樹比較。然后在子樹中重復上述方法, 當搜索節點為葉子結點時, 停止搜索比較, 計算該結點與葉子結點之間的距離, 記錄當前最近鄰點的信息, 并保存最近距離。

3) 對搜索過的路徑進行回溯查找, 判斷沒有被訪問的分支中是否存在更接近當前節點的數據點。如果有, 則進入之前未被訪問的分支查找更近的點, 并將最近鄰點更新, 所有分支節點全部檢查完畢后, 輸出最新的最近鄰點及最近距離。

Step3 根據2.1節, 使用距離權重與方向權重剔除噪聲點與誤匹配點對。

Step4 初始化參數m、rx、ry、rz、tx、ty、tz, 其中rx、ry、rz為旋轉變量,tx、ty、tz為平移變量,m為縮放參數。

Step5 計算旋轉變量和平移變量, 令m=1。

Step6 計算旋轉平移變換點集

Xn=RX+T

(10)

計算適應度

f=‖RX+T-Xn‖+‖RN-Nn‖

(11)

其中X為目標點云數據集,R為旋轉變量點集,T為平移變量點集,N為點集X的法向量,Nn為點集Xn的法向量。對上述適應度函數建立兩個約束條件： 1) 對應點對間的距離最小; 2) 法向量間的夾角為零。

Step7 應用新生成的混合算法AAGPSO對粒子的速度和位置進行更新, 計算更新后粒子的適應度值f, 若其小于給定的閾值, 則迭代終止, 輸出點云集Xn, 將其作為精細配準的初始點云集數據; 否則返回Step3重新配準。

Step8 計算源點集Pn在目標點集Xn中的最近點集Yn=C(Pn,X), 將其作為對應點集。

Step9 求解變換矩陣并計算誤差： (qn,dn)=υ(P0,Yn), 其中d表示對應點匹配的均方誤差。源點集在剛體變換向量q的作用下更新至新的位置P0。

Step10 根據求得的變換矩陣更新點云位置, 并判斷誤差向量是否小于給定閾值。若是, 令原點集與目標點集匹配, 得最終配準結果; 否則, 轉至Step8。

3 點云配準實驗與誤差分析

為驗證改進后的基于混合算法的點云配準方法的有效性, 首先設置改進算法各項參數。設置螢火蟲初始熒光素值為5, 熒光素揮發系數為0.4, 移動步長為0.3, 熒光素更新率為0.6, 螢火蟲感知半徑為6.12, 粒子群優化算法中設置學習因子為2, 慣性權重為[0.4,0.9]。使用斯坦福大學提供的.ply格式的標準模型, 分別用原始的ICP點云配準算法和改進后的點云配準方法對點云數據進行配準, 分析實驗結果[23-24]。為使實驗數據不受外界因素干擾, 實驗環境統一使用聯想電腦, CPU處理器為i7-6700, 主頻為3.1 GHz, 內存為8 GByte。

3.1 點云模型配準實驗結果分析

通過運用原始的ICP算法和筆者提出的改進后方法分別對fish和bunny點云模型進行點云配準實驗, 其中fish點云模型共有3 164個點, bunny點云模型共有83 341個點。配準實驗效果圖如圖2和圖3所示。

a fish點云的初始位置 b 原始ICP算法配準效果 c 筆者改進方法配準效果圖2 ICP算法與筆者算法對fish點云模型配準效果對比Fig.2 Comparison between the ICP algorithm and new algorithm of fish point cloud model

a bunny點云的初始位置 b 原始ICP算法配準效果 c 筆者改進方法配準效果圖3 Bunny點云模型配準效果對比Fig.3 Bunny point cloud model registration effect comparison

對比圖2b、 圖2c可知, 改進算法比原ICP算法配準效果更佳。原始ICP算法配準后仍存在一些誤差, 而改進方法在原有ICP算法基礎上提高了配準精度。通過對比圖3b、 圖3c可知, 原始ICP算法在配準精度上并不高, 而筆者方法可達到完全重合的效果, 配準精度明顯提升。

通過上述兩個實驗可知, ICP算法和筆者提出的配準方法均能完成點云配準實驗, 但當點云中的點增多時, ICP算法點云配準效果明顯比筆者的方法誤差更大, 配準的完成度更低。筆者提出的配準方法使兩片點云重疊的效果優于原始ICP算法。

3.2 誤差分析

誤差計算使用文獻[22]的方法, 其配準誤差參數

(12)

其中Nc為點云的數據量, 未達配準精度判斷函數

(13)

其中δ為給定精度,d(pi,xi)為兩片點云中的對應點對(pi,xi)經過配準后的距離。

兩種配準方法誤差對比如表1所示。從表1可見, 相比于原有的ICP算法, 筆者提出的方法配準精度大幅提高, 并將配準誤差減小至0.018%。

3.3 配準速度分析

筆者采用Fish和Bunny兩組點云模型進行點云配準[25], 并分別記錄兩類點云數據的匹配時間, 結果如表2所示。

表1 配準誤差對比

表2 配準的運行速度對比

由表2可知, 當點云數量增多時, ICP和筆者算法耗時都比較多, 但點云數量相同時, 筆者提出算法的運行時間要優于原ICP算法, 并且配準效率隨著點云數量的增加而提高。

綜上, 通過對比傳統的ICP算法和筆者算法對相同點云模型配準后的誤差分析和配準速度可見, 筆者提出的AAGPSO算法在傳統ICP算法的基礎上提高了配準精度, 并且加快了算法的收斂速度。

4 結 語

筆者根據優勢互補的思想, 針對粒子群算法易陷入局部最優的問題, 對人工螢火蟲算法改進并與融合粒子群算法, 提出了一種自適應人工螢火蟲粒子群混合算法, 在保證魯棒性的前提下, 加快算法收斂速度, 提高解的精度。然后, 將AAGPSO算法引入ICP算法而產生新的點云配準方法, 利用AAGPSO算法確定點云的初始范圍, 解決了ICP算法在尋優過程中由于點云初始位置的差異過大而陷入局部最優的問題, 縮小對點的搜索范圍的同時加快了配準效率。最后, 通過實驗對原始ICP配準方法和筆者配準方法進行對比與誤差分析, 結果驗證了改進配準方法的有效性。