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

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

武漢大學(xué)測繪學(xué)院，湖北 武漢 430079

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

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

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

1 GA簡述

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

標(biāo)準(zhǔn)GA包括3個主要步驟：種群初始化、適應(yīng)度計算和遺傳操作。在確定編碼方式后，進(jìn)行種群初始化生成候選解集。種群是由個體組成的集合{Pop|Ch1，Ch2，…，ChM}。M為個體數(shù)目，其經(jīng)驗值取幾十至幾百。種群初始化方法一般為均勻隨機(jī)生成搜索空間內(nèi)樣本集合。搜索空間是優(yōu)化問題的解域，定義為[-U，U]，U為搜索空間上限。GA優(yōu)化獲得最優(yōu)解的過程是種群進(jìn)化的過程，適應(yīng)度用于評價解的好壞，是選擇操作的依據(jù)。適應(yīng)度函數(shù)是非負(fù)最大的，一般由目標(biāo)函數(shù)轉(zhuǎn)化而來。由于搜索空間、適應(yīng)度函數(shù)定義與實際問題相關(guān)，點云配準(zhǔn)的相關(guān)定義在GA配準(zhǔn)一章闡述。

遺傳操作是模擬生物基因產(chǎn)生下一代的操作，包括選擇、交叉和變異。選擇操作是從父代總?cè)褐羞x擇M個染色體作為子代進(jìn)行進(jìn)化。某一個體被選中的機(jī)會應(yīng)當(dāng)與適應(yīng)度值成比例，適應(yīng)度越高，被選中的概率越大。期望值選擇[26]是一種較好的算法，可以確保適應(yīng)度值較大的個體以較高的概率被選擇。首先，直接復(fù)制∑Numi個個體到下一代

(1)

式中，F(xiàn)i為第i個個體的適應(yīng)度值。復(fù)制后剩余適應(yīng)度值為

(2)

所有個體的剩余適應(yīng)度值用于按適應(yīng)度比例隨機(jī)選擇余下的M-∑Numi個個體。

交叉操作通過雙親染色體的基因值依交叉概率Pc作運(yùn)算產(chǎn)生兩個新的個體，變異操作依變異概率Pm改變?nèi)旧w一個或多個基因值產(chǎn)生新個體。交叉與變異操作與編碼方式有關(guān)。算術(shù)交叉和非均勻變異方法適用于浮點編碼方法[18]，在本文提出的方法中被采用。依經(jīng)驗，Pc取0.6～1的值，Pm不大于0.1。為了讓某一代的最優(yōu)解不被交叉和變異操作破壞，適應(yīng)度值最高的個體直接復(fù)制到下一代群體中。

適應(yīng)度值計算和遺傳操作迭代進(jìn)行，構(gòu)成了GA進(jìn)化過程。GA進(jìn)化的終止條件為以下兩個條件滿足任意一個時：

(1) 最大代數(shù)maxgen：進(jìn)化代數(shù)達(dá)到maxgen時終止；

(2) 最大適應(yīng)度保持不變代數(shù)maxbest：最大適應(yīng)度值已maxbest代(相鄰兩代最大適應(yīng)度值相等)保持不變則終止。為了獲得全局最優(yōu)解，maxgen和maxbest不能過小。

2 配準(zhǔn)方法

2.1 問題描述

點云配準(zhǔn)分解為兩個子問題：如何建立同名對應(yīng)關(guān)系(correspondences，CORRS)；如何利用CORRS構(gòu)造優(yōu)化目標(biāo)函數(shù)估計坐標(biāo)轉(zhuǎn)換參數(shù)。傳統(tǒng)基于特征的配準(zhǔn)是先提取關(guān)鍵點(特征明顯且感興趣的點)，對關(guān)鍵點進(jìn)行描述，再利用相似關(guān)系建立CORRS；采用RANSAC算法剔除錯誤CORRS，并估計最優(yōu)轉(zhuǎn)換參數(shù)。ICP配準(zhǔn)利用距離最近點構(gòu)造CORRS，再利用距離閾值和法向量夾角閾值剔除錯誤CORRS，進(jìn)而估計最優(yōu)轉(zhuǎn)換參數(shù)?；谔卣鞯呐錅?zhǔn)和ICP配準(zhǔn)歸納為4步[27]：點云選擇、CORRS建立、錯誤CORRS剔除、轉(zhuǎn)換參數(shù)估計。點云選擇是選擇部分的點用于配準(zhǔn)，目的是提高配準(zhǔn)效率。基于特征的配準(zhǔn)關(guān)鍵點提取的過程即為點云選擇。ICP配準(zhǔn)則采用下采樣完成點云選擇，應(yīng)用較多的方法為法線空間采樣，它在法向量空間內(nèi)均勻隨機(jī)抽樣，結(jié)果表現(xiàn)為地物特征變化大的地方剩余點較多，變化小的地方剩余點稀少，可有效保持地物特征[9]。

給定待配準(zhǔn)點云S的匹配點Si，基準(zhǔn)點云T的點Ti，點云配準(zhǔn)首先建立S和T的對應(yīng)關(guān)系(Si，Tj)，再根據(jù)對應(yīng)關(guān)系建立目標(biāo)函數(shù)并估計最優(yōu)轉(zhuǎn)換參數(shù)。這里，S為TLS點云，T為MLS點云。點云配準(zhǔn)采用的變換模型如下[27]

Tj=t+RSi

(3)

式中，S是待配準(zhǔn)點云，Si=[SxiSyiSzi]T為第i個配準(zhǔn)點；基準(zhǔn)點云T，Tj=[TxjTyjTzj]T為對應(yīng)點；t=[txtytz]T為平移向量；R表示旋轉(zhuǎn)矩陣，是x、y、z軸三個旋轉(zhuǎn)角α、β、γ的函數(shù)。

傳統(tǒng)配準(zhǔn)方法的優(yōu)化目標(biāo)為CORRS距離平方和最小，即MSE度量

(4)

式中，N為CORRS數(shù)目。

2.2 GA配準(zhǔn)

GA本身是一種全局的啟發(fā)式的優(yōu)化方法，它在整個轉(zhuǎn)換參數(shù)空間自適應(yīng)搜索最優(yōu)解。這里將GA配準(zhǔn)概括為4個步驟(如圖1所示)：總?cè)撼跏蓟忘c云選擇，待配準(zhǔn)點云轉(zhuǎn)換，適應(yīng)度計算，遺傳操作。后3個步驟迭代計算，構(gòu)成GA進(jìn)化過程?？?cè)撼跏蓟虶A進(jìn)化已作了描述。在預(yù)處理后，點云數(shù)據(jù)量仍然較大，很多點位于地面，需用點云選擇提高配準(zhǔn)效率。GA配準(zhǔn)點云選擇方法與ICP配準(zhǔn)相同，即為法線空間采樣法。

GA配準(zhǔn)建立CORRS的方法為先對待配準(zhǔn)點云進(jìn)行轉(zhuǎn)換，然后用鄰近點搜索距離最近點建立CORRS。點云轉(zhuǎn)換和鄰近點搜索需要對總?cè)好恳粋€體分別進(jìn)行，為計算最耗時的階段。點云轉(zhuǎn)換和適應(yīng)度計算對個體的計算是獨(dú)立的，可以采用多核并行運(yùn)算，本文采用OpenMP編程[28]作加速。

傳統(tǒng)配準(zhǔn)采用最小化形式的目標(biāo)函數(shù)E估計最優(yōu)參數(shù)，GA配準(zhǔn)依最大化形式的適應(yīng)度F進(jìn)行優(yōu)化。F由E轉(zhuǎn)換而來，常用方法為負(fù)指數(shù)函數(shù)作轉(zhuǎn)化函數(shù)

F=e-E

(5)

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

(6)

式中，dth為距離閾值，它是重疊區(qū)域CORRS的最大距離。Silva模型將CORRS分為兩類：重疊區(qū)域內(nèi)為內(nèi)點和非重疊區(qū)域內(nèi)為外點。該模型意味著通過最小化MSE同時最大化內(nèi)點數(shù)目得到最優(yōu)轉(zhuǎn)換參數(shù)。

2.3 搜索空間

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

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

如果所采用的掃描儀不帶內(nèi)置GPS，可采用其他的輔助測量方式獲取設(shè)站位置，如外置GPS或GPS RTK。GPS RTK采用差分GPS定位，精度達(dá)厘米級，則tx、ty、tz的搜索范圍可限定在0.1 m以內(nèi)，即tx，ty，tz∈ [-0.1 m，0.1 m，0.1 m]。無論采用何種輔助測量方式，平移向量的搜索范圍應(yīng)根據(jù)定位精度進(jìn)行設(shè)置。

2.4 NSMS配準(zhǔn)模型

已有GA配準(zhǔn)方法采用基于MSE的配準(zhǔn)模型。MSE度量源自局部優(yōu)化算法，應(yīng)用于全局優(yōu)化精度會受影響。對應(yīng)點滿足di≤dth時為內(nèi)點，增加K個內(nèi)點，目標(biāo)函數(shù)值為

(7)

通過作差計算，如果di≤1，則EK≤E；否則EK>E。當(dāng)dth>1 m(文獻(xiàn)[17]取值為5 m，本文取值2 m)且1E，即增加內(nèi)點目標(biāo)函值增大，與內(nèi)點增加目標(biāo)函數(shù)減小的期望相反。

這里則提出了NSMS配準(zhǔn)模型，該模型直接依距離映射函數(shù)計算F，并將法向量約束引入配準(zhǔn)模型進(jìn)行優(yōu)化。NSMS配準(zhǔn)模型的形式如下

(8)

式中，ni和nj為對應(yīng)點的歸一化法向量；Sc為距離映射函數(shù)，其值稱為匹配分?jǐn)?shù)。Sc需要滿足：0

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

圖2 NSMS模型的匹配分?jǐn)?shù)函數(shù)Fig.2 The matching score function of the proposed NSMS model

Scdi=

(9)

NSMS模型帶兩個參數(shù)dideal和dth。dideal一般較小，本文取0.05 m。如果dth較小，則內(nèi)點較少，總?cè)旱恼w適應(yīng)度值較小，不利于遺傳進(jìn)化，即很難搜索到最優(yōu)解；其值較大，總?cè)旱恼w適應(yīng)度值較大，容易搜索到最優(yōu)解，但分?jǐn)?shù)函數(shù)變化較緩(圖2(b))，個體差異變小，所獲解的精度較低。由于搜索空間已經(jīng)限定，本文取適當(dāng)值dth=2 m。

2.5 GA與ICP融合策略

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

3 試驗與分析

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

點云數(shù)據(jù)量大、含噪聲，且配準(zhǔn)需要法向量，因此對點云進(jìn)行了預(yù)處理。預(yù)處理過程為：剔除掃描距離較大的點，這里距離閾值根據(jù)掃描儀的有效距離設(shè)置為100 m；進(jìn)行均勻間隔下采樣，采樣間隔為2.5 cm；根據(jù)鄰域局部協(xié)方差矩陣估計法向量與曲率估計[30]； 樹葉易隨風(fēng)飄動， 樹葉點

對配準(zhǔn)有影響，其呈散狀分布，曲率大，通過曲率閾值0.05可予剔除，如圖4所示。預(yù)處理后，數(shù)據(jù)1中S的點約占原始的19%，T的點約占原始的58%，效果見圖3(c)；數(shù)據(jù)2中S的點約占原始的9.5%，T的點約占原始的45%，效果見圖3(d)?？梢姡A(yù)處理后點云數(shù)據(jù)量明顯減小，但原有特征信息仍然保留。

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

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

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

藍(lán)色為待配準(zhǔn)點云;紅色為基準(zhǔn)點云圖3 試驗點云Fig.3 The test point clouds

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

圖5 人工選擇特征點進(jìn)行粗配準(zhǔn)Fig.5 Coarse registration by manually selected eigen points

數(shù)據(jù)配準(zhǔn)模型RMSE/cmGA進(jìn)化代數(shù)最小最大平均最小最大平均平均運(yùn)行時間/s數(shù)據(jù)1NSMS1．43．92．893279159160Silva6．39．37．6101232168208數(shù)據(jù)2NSMS2．75．44．389247151506Silva29．216．420．7103251173590

藍(lán)色為待配準(zhǔn)點云；紅色為基準(zhǔn)點云；綠線框內(nèi)為局部地物放大圖6 GA配準(zhǔn)后點云Fig.6 The point cloud after GA registration

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

1條折線表示1次試驗圖7 GA配準(zhǔn)最大適應(yīng)度Fig.7 The max fitness of GA registration

4 結(jié) 論

為統(tǒng)一地面激光掃描與車載激光掃描點云坐標(biāo)基準(zhǔn)，提出了一種結(jié)合遺傳算法GA與ICP的高效率自動配準(zhǔn)方法：當(dāng)GA配準(zhǔn)趨于局部搜索時，改用ICP完成配準(zhǔn)。本文重點研究了GA配準(zhǔn)，其歸結(jié)為4步：①總?cè)撼跏蓟忘c云選擇；②匹配點云轉(zhuǎn)換；③適應(yīng)度計算；④遺傳操作。GA配準(zhǔn)以地面激光掃描儀內(nèi)置GPS測量粗略位置作為先驗信息限定優(yōu)化搜索空間。筆者提出了最大化的歸一化匹配分?jǐn)?shù)之和(normalized sum of matching scores，NSMS)配準(zhǔn)模型以提高全局配準(zhǔn)精度。通過實測點云數(shù)據(jù)進(jìn)行試驗，結(jié)果表明：GA配準(zhǔn)是有效的，基于NSMS模型的均方根誤差(root mean square error，RMSE)為1～5 cm；NSMS模型的精度和效率均優(yōu)于已有的基于均方誤差(mean square errors，MSE)的Silva模型；融合配準(zhǔn)策略可將效率提高50%左右。GA配準(zhǔn)可以達(dá)到很高的配準(zhǔn)精度，可一步完成點云配準(zhǔn)；也可以作為初始配準(zhǔn)，與精配準(zhǔn)結(jié)合以提高效率。

參考文獻(xiàn)：

[1] WILLIAMS K, OLSEN M J, ROE G V, et al. Synthesis of Transportation Applications of Mobile LiDAR[J]. Remote Sensing, 2013, 5(9): 4652-4692.

[2] 方莉娜, 楊必勝. 車載激光掃描數(shù)據(jù)的結(jié)構(gòu)化道路自動提取方法[J]. 測繪學(xué)報, 2013, 42(2): 260-267.

FANG Li’na, YANG Bisheng. Automated Extracting Structural Roads from Mobile Laser Scanning Point Clouds[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(2): 260-267.

[3] GUAN Haiyan, LI J, CAO Shuang, et al. Use of Mobile LiDAR in Road Information Inventory: A Review[J]. International Journal of Image and Data Fusion, 2016, 7(3): 219-242.

[4] YANG Bisheng, LIU Yuan, LIANG Fuxun, et al. Using Mobile Laser Scanning Data for Features Extraction of High Accuracy Driving Maps[C]∥Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Prague, Czech Republic: ISPRS, 2016: 433-439.

[5] BARBER D, MILLS J, SMITH-VOYSEY S. Geometric Validation of a Ground-based Mobile Laser Scanning System[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2008, 63(1): 128-141.

[6] SALVI J, MATABOSCH C, FOFI D, et al. A Review of Recent Range Image Registration Methods with Accuracy Evaluation[J]. Image and Vision Computing, 2007, 25(5): 578-596.

[7] BESL P J, MCKAY N D. A Method for Registration of 3D Shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.

[8] CHEN Yang, MEDIONI G. Object Modelling by Registration of Multiple Range Images[J]. Image and Vision Computing, 1992, 10(3): 145-155.

[9] RUSINKIEWICZ S, LEVOY M. Efficient Variants of the ICP Algorithm[C]∥Proceedings of the Third International Conference on 3-D Digital Imaging and Modeling. Quebec City, Quebec, Canada: IEEE, 2001: 145-152.

[10] AKCA D, GRüN A. Least Squares 3D Surface Matching[M]. Zürich: Institut für Geod?sie und Photogrammetrie,

2007.

[11] SEEGER S, LABOUREUX X. Feature Extraction and Registration: An Overview[M]∥GIROD B, GREINER G, NIEMANN H. Principles of 3D Image Analysis and Synthesis. Kluwer: Academic Publishers, 2002: 153-166.

[12] JOHNSON A E, HEBERT M. Using Spin Images for Efficient Object Recognition in Cluttered 3D Scenes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999, 21(5): 433-449.

[13] RUSU R B, BLODOW N, BEETZ M. Fast Point Feature Histograms (FPFH) for 3D Registration[C]∥Proceedings of 2009 IEEE International Conference on Robotics and Automation. Kobe, Japan: IEEE, 2009: 3212-3217.

[14] TOMBARI F, SALTI S, DI STEFANO L. Performance Evaluation of 3D Keypoint Detectors[J]. International Journal of Computer Vision, 2013, 102(1-3): 198-220.

[16] THEILER P W, WEGNER J D, SCHINDLER K. Keypoint-based 4-points Congruent Sets-automated Marker-less Registration of Laser Scans[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 96(2): 149-163.

[17] SILVA L, BELLON O R P, BOYER K L. Precision Range Image Registration Using a Robust Surface Interpenetration Measure and Enhanced Genetic Algorithms[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,

2005, 27(5): 762-776.

[18] 朱燦. 實數(shù)編碼遺傳算法機(jī)理分析及算法改進(jìn)研究[D]. 長沙: 中南大學(xué), 2009.

ZHU Can. The Study on Mechanism and Improvement of Real-coded Genetic Algorithms[D]. Changsha: Central South University, 2009.

[19] JACQ J J, ROUX C. Registration of 3-D Images by Genetic Optimization[J]. Pattern Recognition Letters, 1995, 16(8): 823-841.

[20] SILVA L, BELLON O R P, BOYER K L. Enhanced, Robust Genetic Algorithms for Multiview Range Image Registration[C]∥Proceedings of the Fourth International Conference on 3D Digital Imaging and Modeling. Banff, Alta., Canada: IEEE, 2003: 268-275.

[21] SCHENK S, HANKE K. Genetic Algorithms for Automatic Registration of Laser Scans with Imperfect and Subdivided Features (GAReg-ISF)[J]. Photogrammetrie-Fernerkundung-Geoinformation, 2009, 2009(1): 23-32.

[22] LOMONOSOV E, CHETVERIKOV D, EKRT A. Pre-Registration of Arbitrarily Oriented 3D Surfaces Using a Genetic Algorithm[J]. Pattern Recognition Letters, 2006, 27(11): 1201-1208.

[23] ZHU Jihua, MENG Deyu, LI Zhongyu, et al. Robust Registration of Partially Overlapping Point Sets via Genetic Algorithm with Growth Operator[J]. IET Image Processing, 2014, 8(10): 582-590.

[24] BRINDLE A. Genetic Algorithms for Function Optimization[D]. Alberta: University of Alberta, 1981.

[25] MAN K F, TANG K S, KWONG S. Genetic Algorithms: Concepts and Applications[J]. IEEE Transactions on Industrial Electronics, 1996, 43(5): 519-534.

[26] 周明, 孫樹棟. 遺傳算法原理及應(yīng)用[M]. 北京: 國防工業(yè)出版社, 1999.

ZHOU Ming, SUN Shudong. Genetic Algorithms: Theory and Applications[M]. Beijing: National Defense Industry Press, 1999.

[27] HOLZ D, ICHIM A E, TOMBARI F, et al. Registration with the Point Cloud Library: A Modular Framework for Aligning in 3-D[J]. IEEE Robotics & Automation Magazine, 2015, 22(4): 110-124.

[28] VAN DER PAS R. An Introduction into OpenMP[EB/OL]. http:∥www.nic.uoregon.edu/iwomp2005/iwomp2005_tutorial_openmp_rvdp.pdf.

[29] COLOMINA I C. On Trajectory Determination for Photogrammetry and Remote Sensing: Sensors, Models and Exploitation[C]∥Proceedings of the Photogrammetric Week. Stuttgart, Germany: [s.n.], 2015: 131-142.

[30] PAULY M, KEISER R, GROSS M. Multi-scale Feature Extraction on Point-sampled Surfaces[J]. Computer Graphics Forum, 2003, 22(3): 281-289.