融合遺傳算法和ICP的地面與車載激光點云配準

閆利 , 譚駿祥 , 劉華 , 陳長軍     

武漢大學測繪學院, 湖北 武漢 430079

基金項目：國家重點研發計劃（2016YFC0802500）

之一作者簡介：閆利(1966-), 男, 教授, 博士生導師, 研究方向為攝影測量、遙感和三維激光掃描技術。E-mail:lyan@sgg.whu.edu.cn

微信號：MeetyXiao
添加微信好友, 獲取更多信息
復制微信號

通信作者：譚駿祥, E-mail: lyan@sgg.whu.edu.cn

摘要：車載激光掃描可快速獲取大場景點云，由于存在視場限制和遮擋，需地面激光點云作補充。車載與地面點云分別位于大地坐標和局部坐標系統，本文提出結合遺傳算法（genetic algorithm，GA）和（iterative closed point，ICP）的自動點云配準 *** 以統一基準。ICP采用局部優化，效率較高，但依賴初始解；GA為全局優化 *** ，但效率低。融合策略為當GA配準趨于局部搜索時，采用ICP完成配準。GA配準以地面激光掃描儀內置GPS測量粗略位置限定優化搜索空間。為提高GA配準精度，提出了更大化歸一化匹配分數之和（normalized sum of matching scores，N *** S）配準模型。實測數據試驗驗證了N *** S模型的有效性，GA配準均方根誤差（root mean square error，RMSE）為1~5 cm；融合配準比GA配準效率高約50%。

關鍵詞：車載激光掃描    地面激光掃描    點云配準    遺傳算法    ICP    

Registration of TLS and MLS Point Cloud Combining Genetic Algorithm with ICP

YAN Li , TAN Junxiang , LIU Hua , CHEN Changjun     

Abstract: Large scene point cloud can be quickly acquired by mobile laser scanning (MLS) technology, which needs to be supplemented by terrestrial laser scanning (TLS) point cloud because of limited field of view and occlusion.MLS and TLS point cloud are located in geodetic coordinate system and local coordinate system respectively.This paper proposes an automatic registration method combined genetic algorithm (GA) and iterative closed point ICP to achieve a uniform coordinate reference frame.The local optimizer is utilized in ICP.The efficiency of ICP is higher than that of GA registration, but it depends on a initial solution.GA is a global optimizer, but it's inefficient.The combining strategy is that ICP is enabled to complete the registration when the GA tends to local search.The rough position measured by a built-in GPS of a terrestrial laser scanner is used in the GA registration to limit its optimizing search space.To improve the GA registration accuracy, a maximum registration model called normalized sum of matching scores (N *** S) is presented.The results for measured data show that the N *** S model is effective, the root mean square error (RMSE) of GA registration is 1~5 cm and the registration efficiency can be improved by about 50% combining GA with ICP.

Key words: mobile laser scanning     terrestrial laser scanning     point cloud registration     genetic algorithm     ICP    

車載激光掃描(mobile laser scanning，MLS)能快速獲大場景點云數據，在道路交通領域有應用價值和潛力^[1-2]，如道路信息調查^[3]和智能駕駛高精度三維地圖制作^[4]。MLS硬件系統發展很快，形成了多種類型的商業化產品，該系統必要組件包括激光掃描儀、高精度POS系統和高精度時間同步控制系統^[5]。由于MLS測量存在視場限制和遮擋，需要將地面激光掃描(terrestrial laser scanning，TLS)點云數據作為補充。MLS點云位于大地坐標系，TLS點云位于局部坐標系，需要進行坐標轉換。本文采用TLS與MLS點云配準以完成基準統一。

點云自動配準一般按“初始配準”和“精配準”兩步進行^[6]。點云精配準最著名的算法是ICP算法^[7-9]。最小二乘3D(least-squares 3D，LS3D)表面配準^[10]近些年也被采用。ICP和LS3D均使用局部優化算法，局部優化收斂性依賴于初始轉換參數。初始配準為精配準提供初始值，研究最多的是特征匹配。特征匹配通過在重疊區自動提取特征建立對應關系，所采用的特征需要具有旋轉和平移不變性，如曲率和點標簽^[11]、旋轉圖像(spin image)^[12]、快速點特征直方圖(FPFH)^[13]。文獻[14—15]對已有特征描述子進行了總結，并比較了它們的性能，結果表明特征提取 *** 需謹慎選擇。點云特征匹配面臨分布不均勻、噪聲、部分重疊、數據量大、重復結構等諸多問題，加上無法準確度量同名對應關系的幾何質量，特征匹配的優化往往耗時且容易失敗^[16]。

除兩步配準外，遺傳算法(genetic algorithm，GA)可一步完成配準^[17]。GA是一種全局優化算法，采用在整個解空間全局自適應地搜索更優解^[18]。GA很早被應用于3D醫學點云配準^[19]。文獻[20]分析了GA應用在點云配準中的細節，提出了基于均方誤差(mean square errors，MSE)的配準模型。文獻[21—23]均采用基于MSE的配準模型進行GA配準。MSE度量準則源自局部優化算法，需要轉化為更大化的適應度值用于評價轉換參數的好壞程度。與基于特征的配準相比，GA配準不需要特征提取和描述；與ICP相比，GA配準不依賴于初始轉換參數，但效率更低。論文提出一種結合GA與ICP的高效率自動配準 *** 。

1 GA簡述

GA是一種采用隨機搜索機制的全局優化 *** ，模擬生物進化過程，即保持一個候選解組成的種群，用3個遺傳操作完成進化：選擇、交叉和變異^[18, 24-26]。不同的優化問題，進化操作的解表達形式不同。解轉化為其表達形式的過程稱為編碼，即將搜索空間的解表示為由多個基因組成的可遺傳操作的染色體，形式上為一個向量。解碼是編碼的逆操作。數值優化問題采用數值編碼和解碼 *** ，常用 *** 為二進制和浮點編碼^[26]。前者是將實數解轉為二進制數構成染色體，相應解碼為二進制數染色體轉成實數解；后者直接將實數解作為染色體，無須解碼。實數編碼沒有轉化精度損失，效率更高，也易與經典優化估計 *** 結合使用^[18]。

標準GA包括3個主要步驟：種群初始化、適應度計算和遺傳操作。在確定編碼方式后，進行種群初始化生成候選解集。種群是由個體組成的 *** {Pop| Ch₁，Ch₂，…，Ch_M}。M為個體數目，其經驗值取幾十至幾百。種群初始化 *** 一般為均勻隨機生成搜索空間內樣本 *** 。搜索空間是優化問題的解域，定義為[-U，U]，U為搜索空間上限。GA優化獲得更優解的過程是種群進化的過程，適應度用于評價解的好壞，是選擇操作的依據。適應度函數是非負更大的，一般由目標函數轉化而來。由于搜索空間、適應度函數定義與實際問題相關，點云配準的相關定義在GA配準一章闡述。

遺傳操作是模擬生物基因產生下一代的操作，包括選擇、交叉和變異。選擇操作是從父代總群中選擇M個染色體作為子代進行進化。某一個體被選中的機會應當與適應度值成比例，適應度越高，被選中的概率越大。期望值選擇^[26]是一種較好的算法，可以確保適應度值較大的個體以較高的概率被選擇。首先，直接復制∑Num_i個個體到下一代

 (1)

式中，F_i為第i個個體的適應度值。復制后剩余適應度值為

 (2)

所有個體的剩余適應度值用于按適應度比例隨機選擇余下的M－∑Num_i個個體。

交叉操作通過雙親染色體的基因值依交叉概率P_c作運算產生兩個新的個體，變異操作依變異概率P_m改變染色體一個或多個基因值產生新個體。交叉與變異操作與編碼方式有關。算術交叉和非均勻變異 *** 適用于浮點編碼 *** ^[18]，在本文提出的 *** 中被采用。依經驗，P_c取0.6~1的值，P_m不大于0.1。為了讓某一代的更優解不被交叉和變異操作破壞，適應度值更高的個體直接復制到下一代群體中。

適應度值計算和遺傳操作迭代進行，構成了GA進化過程。GA進化的終止條件為以下兩個條件滿足任意一個時：

(1) 更大代數max_gen：進化代數達到max_gen時終止；

(2) 更大適應度保持不變代數max_best：更大適應度值已max_best代(相鄰兩代更大適應度值相等)保持不變則終止。為了獲得全局更優解，max_gen和max_best不能過小。

2 配準 *** 2.1 問題描述

點云配準分解為兩個子問題：如何建立同名對應關系(correspondences，CORRS)；如何利用CORRS構造優化目標函數估計坐標轉換參數。傳統基于特征的配準是先提取關鍵點(特征明顯且感興趣的點)，對關鍵點進行描述，再利用相似關系建立CORRS；采用RANSAC算法剔除錯誤CORRS，并估計更優轉換參數。ICP配準利用距離最近點構造CORRS，再利用距離閾值和法向量夾角閾值剔除錯誤CORRS，進而估計更優轉換參數。基于特征的配準和ICP配準歸納為4步^[27]：點云選擇、CORRS建立、錯誤CORRS剔除、轉換參數估計。點云選擇是選擇部分的點用于配準，目的是提高配準效率。基于特征的配準關鍵點提取的過程即為點云選擇。ICP配準則采用下采樣完成點云選擇，應用較多的 *** 為法線空間采樣，它在法向量空間內均勻隨機抽樣，結果表現為地物特征變化大的地方剩余點較多，變化小的地方剩余點稀少，可有效保持地物特征^[9]。

給定待配準點云S的匹配點S_i，基準點云T的點T_i，點云配準首先建立S和T的對應關系(S_i，T_j)，再根據對應關系建立目標函數并估計更優轉換參數。這里，S為TLS點云，T為MLS點云。點云配準采用的變換模型如下^[27]

 (3)

式中，S是待配準點云，S_i=[S_xi S_yi S_zi]^T為第i個配準點；基準點云T，T_j=[T_xj T_yj T_zj]^T為對應點；t=[t_x t_y t_z]^T為平移向量；R表示旋轉矩陣，是x、y、z軸三個旋轉角α、β、γ的函數。

傳統配準 *** 的優化目標為CORRS距離平方和最小，即MSE度量

 (4)

式中，N為CORRS數目。

2.2 GA配準

GA本身是一種全局的啟發式的優化 *** ，它在整個轉換參數空間自適應搜索更優解。這里將GA配準概括為4個步驟(如圖 1所示)：總群初始化和點云選擇，待配準點云轉換，適應度計算，遺傳操作。后3個步驟迭代計算，構成GA進化過程。總群初始化和GA進化已作了描述。在預處理后，點云數據量仍然較大，很多點位于地面，需用點云選擇提高配準效率。GA配準點云選擇 *** 與ICP配準相同，即為法線空間采樣法。

圖 1 遺傳算法配準流程Fig. 1 The flow chart of the proposed GA registration
虛線框內為遺傳進化過程

GA配準建立CORRS的 *** 為先對待配準點云進行轉換，然后用鄰近點搜索距離最近點建立CORRS。點云轉換和鄰近點搜索需要對總群每一個體分別進行，為計算最耗時的階段。點云轉換和適應度計算對個體的計算是獨立的，可以采用多核并行運算，本文采用OpenMP編程^[28]作加速。

傳統配準采用最小化形式的目標函數E估計更優參數，GA配準依更大化形式的適應度F進行優化。F由E轉換而來，常用 *** 為負指數函數作轉化函數

 (5)

由于S和T部分重疊，文獻[17, 20]提出在GA配準中使用距離截斷MSE模型對式(4)作修正。距離截斷函數為

 (6)

式中，d_th為距離閾值，它是重疊區域CORRS的更大距離。Silva模型將CORRS分為兩類：重疊區域內為內點和非重疊區域內為外點。該模型意味著通過最小化MSE同時更大化內點數目得到更優轉換參數。

2.3 搜索空間

GA是在整個搜索空間進化搜索更優解的過程。點云配準的搜索空間由轉換參數的上界U確定，即[-U，U]。在任意情況下，α、β、γ的上界為180°，t_x、t_y、t_z是無界的。如果搜索空間過大，GA收斂慢，或早熟(收斂至局部更優)，或退化為隨機搜索。搜索空間越小，GA收斂速度越快，配準效率越高。因此，確定一個有限且盡可能小的搜索空間是必要的。

本文將TLS掃描儀設站粗略位置作為先驗信息限定搜索空間。掃描儀設站的粗略位置可由內置GPS獲取。關于內置GPS的信息量少，可了解的是它采用單點定位方式，定位精度達分米級或米級^[29]。t_x、t_y、t_z的取值在位置誤差范圍內，本文將其設定為10 m。α、β與掃描平臺的水平程度有關，它們的值通常很小，一般在5°以內；γ與北向對準有關，在任意設站時的范圍是[-180°，180°)。因此，轉換參數的搜索空間為(α，β，γ，t_x，t_y，t_z |α，β∈ [-5°，5°]，γ∈ [-180°，180°]，t_x，t_y，t_z∈ [-10 m，10 m])，即U等于[5°, 5°, 180°, 10 m, 10 m, 10 m]。

如果所采用的掃描儀不帶內置GPS，可采用其他的輔助測量方式獲取設站位置，如外置GPS或GPS RTK。GPS RTK采用差分GPS定位，精度達厘米級，則t_x、t_y、t_z的搜索范圍可限定在0.1 m以內，即t_x，t_y，t_z∈ [-0.1 m，0.1 m，0.1 m]。無論采用何種輔助測量方式，平移向量的搜索范圍應根據定位精度進行設置。

2.4 N *** S配準模型

已有GA配準 *** 采用基于MSE的配準模型。MSE度量源自局部優化算法，應用于全局優化精度會受影響。對應點滿足d_i≤d_th時為內點，增加K個內點，目標函數值為

 (7)

通過作差計算，如果d_i≤1，則E_K≤E；否則E_K>E。當d_th>1 m(文獻[17]取值為5 m，本文取值2 m)且1 < d_i≤d_th時E_K>E，即增加內點目標函值增大，與內點增加目標函數減小的期望相反。

這里則提出了N *** S配準模型，該模型直接依距離映射函數計算F，并將法向量約束引入配準模型進行優化。N *** S配準模型的形式如下

 (8)

式中，n_i和n_j為對應點的歸一化法向量；S_c為距離映射函數，其值稱為匹配分數。S_c需要滿足：0 < S_c≤1，單調遞增。第1個條件使得F是歸一化的，不會隨CORRS數目增大而無限增大；第2個條件使距離越大，分數越小，即對F貢獻越小。

同Silva模型一樣，這里將整個匹配區域也分為重疊區域和非重疊區域。為了保證距離較近的CORRS獲得高的分數，重疊區域又分為理想重疊區域和緩沖區域。重疊區域內兩個區域分段處的距離閾值稱為理想距離d_ideal。在d_ideal處，匹配點被賦予分數高置信度0.95；在d_th處，被賦予分數低置信度0.05。利用負指數函數定義連續的匹配分數函數(如圖 2所示)。

 (9)

圖 2 N *** S模型的匹配分數函數Fig. 2 The matching score function of the proposed N *** S model

N *** S模型帶兩個參數d_ideal和d_th。d_ideal一般較小，本文取0.05 m。如果d_th較小，則內點較少，總群的整體適應度值較小，不利于遺傳進化，即很難搜索到更優解；其值較大，總群的整體適應度值較大，容易搜索到更優解，但分數函數變化較緩(圖 2(b))，個體差異變小，所獲解的精度較低。由于搜索空間已經限定，本文取適當值d_th=2 m。

2.5 GA與ICP融合策略

由于GA采用全局搜索策略，其收斂性不依賴于初始值，但計算效率低，局部收斂慢，因此進一步提出采用GA與ICP相結合的配準策略以提高配準效率。結合方式為：先采用GA配準，當進化到一定代數時，GA已經趨于局部搜索，其獲得的解已接近于更優化解，此時改用ICP進行局部優化。由于局部范圍內的GA適應度比較接近，為控制GA的終止精度，可將GA第2個終止條件中的“相鄰兩代更大適應度相等”改為“相鄰兩代更大適應度之差的絕對值小于e″。e是微小正數，一般取10^-3~10^-2。

3 試驗與分析

為驗證GA配準的有效性，N *** S配準模型的優越性以及GA與ICP融合配準策略的高效性，采用兩組實測數據進行了試驗。圖 3(a)所示為數據1，待配準點云S約1.3千萬點，基準點云T約1.1千萬點；圖 3(b)所示為數據2，待配準點云S約5.2千萬點，基準點云T含1千萬點。兩組數據重疊度均約為50%；使用的地面激光掃描儀為Riegl VZ400，設站粗略位置均通過掃描儀內置GPS獲得。

圖 3 試驗點云Fig. 3 The test point clouds藍色為待配準點云; 紅色為基準點云

      點云數據量大、含噪聲，且配準需要法向量，因此對點云進行了預處理。預處理過程為：剔除掃描距離較大的點，這里距離閾值根據掃描儀的有效距離設置為100 m；進行均勻間隔下采樣，采樣間隔為2.5 cm；根據鄰域局部協方差矩陣估計法向量與曲率估計^[30]；樹葉易隨風飄動，樹葉點對配準有影響，其呈散狀分布，曲率大，通過曲率閾值0.05可予剔除，如圖 4所示。預處理后，數據1中S的點約占原始的19%，T的點約占原始的58%，效果見圖 3(c)；數據2中S的點約占原始的9.5%，T的點約占原始的45%，效果見圖 3(d)。可見，預處理后點云數據量明顯減小，但原有特征信息仍然保留。

圖 4 散狀點剔除Fig. 4 The removal of scattered points點云按高程值渲染

為定量評價GA配準精度，將待配準點云S與其參照點云S_ref的距離均方根誤差RMSE作為衡量指標。S_ref是S的理論值。理論值是未知的，這里通過人工選擇特征點進行粗配準(如圖 5)，再采用ICP精配準獲得S和T之間的轉換參數，將S轉換點云近似作為S_ref。為剔除錯誤的對應關系，ICP配準的對應點距離閾值設為0.2 m，法向量夾角閾值為10°。

圖 5 人工選擇特征點進行粗配準Fig. 5 Coarse registration by manually selected eigen points

因用于配準的點云是依法向量空間隨機選擇且GA采用隨機搜索機制，各組配準試驗均獨立進行了50次，以統計結果進行評估。為剔除錯誤的對應關系，ICP算法的對應點距離閾值設為0.2 m，法向量夾角閾值為10°。試驗運行環境為：Intel Core i7-4790 CPU @ 3.60 GHz，4核心處理器和8 G內存。詳細的GA配準參數見表 1，計算機線程數目等于8。

表 1 GA配準試驗參數Tab. 1 The experimental parameters of GA registration

      采用N *** S模型與Silva模型的GA配準對比試驗結果如表 2所示。N *** S模型的精度和效率均優于Silva模型，平均優化時間高于Silva模型20%左右，RMSE在1至5 cm之間。采用N *** S模型的GA配準效果如圖 6所示。在具有任意北偏角和較大平移值的情況下GA仍然能完成匹配，驗證了 *** 有效。

表 2 GA配準結果統計Tab. 2 The statistical results of GA registration

圖 6 GA配準后點云Fig. 6 The point cloud after GA registration
藍色為待配準點云；紅色為基準點云；綠線框內為局部地物放大

GA更大適應度變化曲線如圖 7所示，在進化初期，適應度變化較快，GA表現全局搜索；當進化至一定階段時，適應度變化緩慢并趨于成熟，GA表現局部搜索。GA配準50%以上迭代位于變化平緩區域，表明局部收斂速度慢。數據1和數據2的GA與ICP融合策略平均運行時間分別為98 s、217 s；平均進化代數為76、67。融合GA和ICP的配準策略效率比GA配準提高了50%左右。

圖 7 GA配準更大適應度Fig. 7 The max fitness of GA registration1條折線表示1次試驗

4 結論

為統一地面激光掃描與車載激光掃描點云坐標基準，提出了一種結合遺傳算法GA與ICP的高效率自動配準 *** ：當GA配準趨于局部搜索時，改用ICP完成配準。本文重點研究了GA配準，其歸結為4步：①總群初始化和點云選擇；②匹配點云轉換；③適應度計算；④遺傳操作。GA配準以地面激光掃描儀內置GPS測量粗略位置作為先驗信息限定優化搜索空間。筆者提出了更大化的歸一化匹配分數之和(normalized sum of matching scores，N *** S)配準模型以提高全局配準精度。通過實測點云數據進行試驗，結果表明：GA配準是有效的，基于N *** S模型的均方根誤差(root mean square error，RMSE)為1~5 cm；N *** S模型的精度和效率均優于已有的基于均方誤差(mean square errors，MSE)的Silva模型；融合配準策略可將效率提高50%左右。GA配準可以達到很高的配準精度，可一步完成點云配準；也可以作為初始配準，與精配準結合以提高效率。
 

【引文格式】閆利, 譚駿祥, 劉華, 等. 融合遺傳算法和ICP的地面與車載激光點云配準[J]. 測繪學報，2018，47(4)：528-536. DOI: 10.11947/j.AGCS.2018.20170235