經(jīng)過一周的綜述撰寫，深感點云算法應(yīng)用之浩瀚，只能仰仗前輩們的文章作一些整理：

點云硬件：

點云獲取技術(shù)可分為接觸式掃描儀、激光雷達、結(jié)構(gòu)光、三角測距（Triangulation）、以及立體視覺等多種。最近二十年，點云獲取設(shè)備有突飛猛進發(fā)展。

經(jīng)過20多年的發(fā)展，三維激光掃描硬件在穩(wěn)定性、精度、易操作性等方面取得了長足的進步，尤其在機載/車載/地面三維激光掃描方面進展顯著，其中具有代表性的三維激光掃描硬件研制廠商包括：Riegl、Leica、Optech、Velodyne、北科測繪、海達數(shù)云等。此外還有美國NASA的ICESat和中國資源三號02星搭載的激光雷達。

點云軟件：

目前，工業(yè)界和學術(shù)界已經(jīng)開發(fā)了多種針對點云處理的商用軟件和開源軟件。商業(yè)化的軟件主要有TerraSolid公司的TerraSolid（基于Microstation平臺開發(fā)，功能強大）、Trimble公司的Realworks、Leica公司的Cyclone、Bentley公司的Pointtools、Orbit GT公司的Orbit Mobile Mapping等，以及國內(nèi)科研院所和公司開發(fā)的一些工具軟件，如武漢天擎的LiDAR Suite、西安煤航的LiDAR-DP以及北京數(shù)字綠土的LiDAR 360等。其重點主要集中在點云數(shù)據(jù)的管理、面向DEM生產(chǎn)的濾波[1]、三維建筑物提取及重建[2]、森林垂直結(jié)果參數(shù)提取[3]等方面。

此外，還有一些開源、自由的點云數(shù)據(jù)處理軟件，包括以下幾款：

Lastools：國際知名度高，C++編寫，分模塊，部分模塊開源，底層IO庫，壓縮庫都開源。

OPALS：維也納技術(shù)大學攝影測量研究組開發(fā)的軟件，學界最好。同樣是底層庫+功能模塊的結(jié)構(gòu)，可支持幾乎任何一種激光雷達數(shù)據(jù)，處理效率很高。支持C++/Python二次開發(fā)。

BCAL LiDAR tools：一個ENVI插件，支持LiDAR格式點云的可視化、處理，IDL編寫。

CloudCompare：C ++開發(fā)，依賴于QT和OPENGL。支持基于插件的擴展機制。可拔插操作，可二次開發(fā)與源程序互不影響。富有活力，經(jīng)常更新。

FUSION：開源軟件，功能很多，在forestry和ecology學界比較有名，可以計算多種LiDAR metrics。

相對三維激光掃描硬件設(shè)備的快速發(fā)展而言，三維點云的智能化處理發(fā)展較為落后，點云處理的智能化水平、軟件界面友好性、專業(yè)化應(yīng)用數(shù)據(jù)接口方面還有待提高。

點云算法：

點云處理可以分為低中高三個層次。低層次處理主要包括濾波以及關(guān)鍵點的檢測；中層次處理包括點云的特征描述和分割、分類；高層次處理有配準、SLAM圖優(yōu)化、三維重建等。與傳統(tǒng)的測量方式相比，三維激光掃描數(shù)據(jù)采集速度快、采樣頻率高，但也導致點云數(shù)據(jù)具有高冗余、誤差分布非線性、不完整等特點，給海量三維點云的智能化處理帶來了極大的困難。

濾波：

常用的濾波方法主要有直通濾波、體素法濾波、統(tǒng)計濾波、半徑濾波、條件濾波、雙邊濾波、高斯濾波、隨機采樣一致性濾波以及基于頻率的濾波。

除了以上比較常見的濾波算法，從LiDAR點云中去除地物點而保留地形點是點云濾波的一個重要環(huán)節(jié)。發(fā)展至今，算法可以歸為以下幾大類：

⑴布料模擬濾波

布料模擬濾波（Cloth Simulation Filtering，CSF）是一種物理模擬算法。該算法先將地表點云翻轉(zhuǎn)，然后讓一塊由格網(wǎng)構(gòu)成的虛擬布料放置于翻轉(zhuǎn)后的點云表面最高處，使其自由落下，布料節(jié)點在重力和鄰近節(jié)點相互作用力的影響下會產(chǎn)生位移，會貼附于地形表面上。運算完成后，當布料上某節(jié)點的高程小于或等于對應(yīng)點的高程，則將用點云的高程為該節(jié)點賦值，并將其標記為不可移動點。最后，計算密集匹配點云與布料節(jié)點的高差，大于閾值的被視為非地面點高差，反之則被視為地面點[5-6]。

⑵基于坡度的濾波算法

Vosselman[7]提出地面點間坡度值較小，計算各個點與周圍鄰近點間的坡度值，根據(jù)閾值可以判斷是否為地面點；Sithole[8]坡度閾值不再是固定常量，根據(jù)地形坡度的變化而變化；張皓[9]等采用坡度、坡度增量、最小坡度、最大坡度四個參數(shù)共同進行濾波判斷。

問題：計算量大、占內(nèi)存；依賴閾值。

⑶基于形態(tài)學的濾波算法

形態(tài)學濾波原理：非地面點在形態(tài)學開運算前后高程變化較大，而地面點在形態(tài)學開運算前后高程變化小，通過設(shè)定閾值可將非地面點剔除（形態(tài)學腐蝕再膨脹）。

關(guān)鍵在于濾波窗口的選擇，Zhang[10]提出經(jīng)典的漸進式形態(tài)學濾波，窗口有小變大，對應(yīng)不同的高度閾值；此后學者在該方法基礎(chǔ)上進行改進，Hui[11]等結(jié)合克里金插值計算各層級局部區(qū)域的地形起伏度，以此為濾波準則進行優(yōu)化。

問題：濾波窗口不好選取，漸進變化窗口效果不錯，但大窗口易將地形起伏點誤判為地物點。

⑷基于曲面擬合的濾波算法

原理：通常采用一定的插值擬合方法建立一個粗糙地形曲面，設(shè)定濾波準則，如點到曲面的距離，將不滿足條件的點逐步剔除。持續(xù)迭代，直到所有的地形曲面的精度達到所需的分辨率。

Kraus和Pfeifer[12]采用線性預(yù)測的方法，設(shè)定權(quán)重函數(shù)，在森林區(qū)域效果良好；Mongus和Zalik[13]提出了一種無參數(shù)的多層級漸進加密點云濾波法；Hu[14]等同樣采用TPS插值法，但在各層級進行擬合曲面時，計算各層級局部區(qū)域的彎曲能量，實現(xiàn)濾波閾值的自動計算。

優(yōu)缺點：不需要過多的參數(shù)設(shè)置，自適應(yīng)能力強，但多層級迭代，每一層級的濾波結(jié)果都會受到上一層的影響，初始地面不準確，就會出現(xiàn)誤差的傳遞與累積。內(nèi)插方法也有很大影響。

⑸基于不規(guī)則三角網(wǎng)的濾波算法

原理：利用TIN模型中的地物臨近點云高程突變關(guān)系，研究利用高差臨界值條件和滿足該條件的臨近點數(shù)量等參數(shù)來過濾地物點。

Axelsson[15]提出經(jīng)典的漸進加密不規(guī)則三角網(wǎng)（PTIND）濾波算法，簡稱PTD算法：首先獲取地面種子點，建TIN并進行迭代加密。在每次迭代過程中，都對其余各點到所在三角形的反復(fù)角和反復(fù)距離進行閾值判斷，滿足條件的點加入TIN，迭代至無點。Zhang和Lin[16]將光滑約束分割法與PTD方法相結(jié)合，減少地形凸起區(qū)域的細節(jié)誤差。隋立春[17]等首先對各個格網(wǎng)內(nèi)的點云按升序進行排序，然后按照排序順序再對TIN進行加密，有效減小Ⅱ類誤差；吳芳等[18]在選擇地面種子點之前首先去除非地面點的影響，保證契合原有地形。

漸進加密不規(guī)則三角網(wǎng)算法近年來表現(xiàn)最為穩(wěn)健。在復(fù)雜地形中效果良好，誤差低；但處理時間稍長，初始TIN對后續(xù)濾波影響很大；PTD算法對低位噪聲敏感，極易將低位噪聲點或低勢地物點誤判為地面點。

⑹基于分割的濾波算法

通常包含兩步，一是采取某種分割方法對點云進行分割，二是基于分割結(jié)果按照某種設(shè)定的規(guī)則進行點云濾波。

點云聚類分割的方法有很多：掃描線、Mean Shift分割法、區(qū)域生長法、、隨機抽樣一致等。濾波判斷的標準大多為地面點聚類區(qū)域低于地物點聚類區(qū)域。Lin和Zhang[19]首先采用區(qū)域生長法將點云分割成不同的部分，再設(shè)定規(guī)則選擇地面種子點，建TIN，PTD算法迭代；Tovari和Pfeifer[20]首先對點云進行分割，對分割后的每一部分計算殘差值，并根據(jù)殘差值對屬于同一部分的點云設(shè)置相同的權(quán)重，再按照Kraus和Pfeifer提的方法進行迭代濾波。

優(yōu)缺點：能獲得更好的點云濾波效果，原因在于點云聚類分割，點云塊能夠提供更多的語義信息，更有利于后續(xù)的濾波判斷；分割后的點云能準確地到達地形斷裂線或者高程跳躍邊緣。但過分依賴聚類分割的結(jié)果。

⑺基于機器學習的濾波算法

基于機器學習的濾波算法將點云濾波視為二分類問題。采用某種機器學習算法，如條件隨機場、支持向量機、Adaboost等對訓練樣本進行訓練獲取訓練模型，然后采用此訓練模型對點云進行0（地面點），1（非地面點）標記。

Lu等[21]建立了一種基于離散和連續(xù)隱含隨機變量的條件隨機場模型，以區(qū)分地面點和非地面點；Jahromi等[22]提出了一種基于人工神經(jīng)網(wǎng)絡(luò)（ANN）的算法：分別采用半自動化獲取訓練樣本和人工獲取訓練樣本兩種策略。Hu和Yuan[23]采用卷積神經(jīng)網(wǎng)絡(luò)（CNN）通過對點云進行深度學習實現(xiàn)濾波，該方法將點云濾波問題轉(zhuǎn)化為圖像的分類問題，通過對1.728*10的7次方個標記的點云進行訓練學習，可以獲得1.5*10的八次方個參數(shù)的深度卷積神經(jīng)網(wǎng)絡(luò)模型，現(xiàn)有濾波算法中精度最高。

缺點：需要大量的標記點云作為訓練樣本，耗費大量人力，占用大量計算機資源，耗時；訓練樣本要求覆蓋所有地形特征，很難實現(xiàn)。

⑻基于偽掃描線的濾波算法

偽掃描線：指將水平面上二維離散分布的激光點重新組織成一堆線狀連續(xù)分布點序列的一種數(shù)據(jù)結(jié)構(gòu)。基本思想：兩點之間的高度差是由自然地形的起伏和地物的高度共同引起的。若兩個鄰近點之間的高度差越大，那么這個高度差是由自然地形引起的可能性就越小，更有可能是較高點位于地物上而較低點位于地面上。

優(yōu)點：算法簡單，有效減少計算量并且保證了準確性，同時只需兩個濾波參數(shù)，較容易實現(xiàn)自動化；總能保證每個濾波窗口都包含有地面點，準確地提取出地形點；在平坦區(qū)域，效果非常好，在地形陡峭地區(qū)，誤差控制在較小范圍。

缺點：當?shù)孛纥c較少的時候，這類方法會失效；濾波窗口大小的選取還不能完全自動化，尤其在高程變化劇烈的區(qū)域和城市地區(qū)。

⑼基于多分辨率方向預(yù)測的濾波算法

方向預(yù)測法的思想：對于某一距離范圍，若當前點與所有方向預(yù)測值的差值均大于該距離條件下的最大高差限差，則該點為地物點，否則為地面點。

優(yōu)缺點：此算法可以實現(xiàn)復(fù)雜尺寸的地物目標的剔除處理，由于數(shù)據(jù)集再數(shù)據(jù)量上的減少，地面點提取的效率有很大提高。對于附屬在斜坡上的建筑物會出現(xiàn)濾除不完全的情況，需要結(jié)合航片等輔助數(shù)據(jù)源來提高濾波精度。多分辨率平滑處理可以得到格網(wǎng)數(shù)據(jù)集，但格網(wǎng)之間存在縫隙，降低了精度，需要利用點云數(shù)據(jù)和格網(wǎng)數(shù)據(jù)集進一步做點云濾波處理。

⑽小結(jié)

總體而言，在訓練樣本足夠多的情況下基于深度學習的點云濾波算法能獲得最好的濾波效果，但其較為復(fù)雜的樣本標記和較長的處理時間會限制算法進一步發(fā)展；相較而言，基于分割的濾波算法因為能獲得更多聚類后的語義信息可以獲得更高的濾波精度，此外漸進迭代方式的算法也有較好的結(jié)果。

關(guān)鍵點特征線提取

點云數(shù)據(jù)的幾何特征主要是指對反映被測物體三維形態(tài)和紋理特征有關(guān)鍵性影響的點、線、面。不同的對象需要的特征提取方式不同，即便是同一對象也需要依照不同需求提取不同的特征。

在點云特征提取方式上，現(xiàn)有算法可以分為基于全局特征的方法和基于局部特征的方法兩類，全局特征利用點云上所有點的信息構(gòu)建特征描述子。然而由于復(fù)雜場景下的物體遮擋、數(shù)據(jù)分辨率變化、噪聲干擾、背景影響以及視點變化等，使得獲取的點云具有顯著的多樣性。這些多樣性使得局部特征比全局特征更加勝任現(xiàn)實世界中的點云表示。局部特征提取通常包括關(guān)鍵點檢測和局部特征描述兩個步驟，其構(gòu)成了三維模型重建與目標識別的基礎(chǔ)和關(guān)鍵。

本節(jié)主要闡述關(guān)鍵點和特征線的提取算法。

3.2.1 點云的關(guān)鍵點提取算法

點是三維點云數(shù)據(jù)中最基本的幾何形狀的特征基元，將三維模型模型表面具有代表性和描述性的點集定義為特征點，例如邊界點、尖銳點，以及相鄰曲面的公共點。關(guān)鍵點的數(shù)量相比于原始點云或圖像的數(shù)據(jù)量減小很多，與局部特征描述子結(jié)合在一起，組成關(guān)鍵點描述子，常用來表示原始數(shù)據(jù)，而且不失代表性和描述性。

⑴ISS算法（Intrinsic Shape Signatures）

利用協(xié)方差矩陣建立模型：把pi和周圍點pj的坐標相減：本質(zhì)上這生成了許多從pi->pj的向量，理想情況下pi的法線應(yīng)該是垂直于這些向量的。利用奇異值分解求這些向量的空間，擬合出一個盡可能垂直的向量，作為法線的估計。

利用特征值之間關(guān)系來形容該點的特征程度。顯然這種情況下的特征值是有幾何意義的，特征值的大小實際上是橢球軸的長度。橢球的的形態(tài)則是對鄰近點分布狀態(tài)的抽象總結(jié)。試想，如果臨近點沿某個方向分布致密則該方向會作為橢球的第一主方向，稀疏的方向則是第二主方向，法線方向當然是極度稀疏（只有一層），那么則作為第三主方向。如果某個點恰好處于角點，則第一主特征值，第二主特征值，第三主特征值大小相差不會太大。如果點云沿著某方向致密，而垂直方向系數(shù)則有可能是邊界。總而言之，這種局部坐標系建模分析的方法是基于特征值分析的特征點提取。

⑵Trajkovic關(guān)鍵點檢測算法

角點的一個重要特征就是法線方向和周圍的點存在不同，而此算法的思想就是和相鄰點的法線方向進行對比，判定法線方向差異的閾值，最終決定某點是否是角點。并且需要注意的是，本方法所針對的點云應(yīng)該只是有序點云。本方法的優(yōu)點是快，缺點是對噪聲敏感。

⑶3DHarris算法

在二維中是取一個窗口，然后移動窗口：

1.兩個特征值都很大，則為角點（兩個響應(yīng)方向）。

2.一個特征值很大，一個很小，則為邊緣（只有一個響應(yīng)方向）。

3.兩個特征值都小，則為平原地區(qū)（響應(yīng)都很微弱）。

在點云中是建立一個方塊體，以體內(nèi)數(shù)量變化確定角點。如果在點云中存在一點p：

1、在p上建立一個局部坐標系：z方向是法線方向，x,y方向和z垂直。

2、在p上建立一個小正方體。

3、假設(shè)點云的密度是相同的，點云是一層蒙皮，不是實心的。

a、如果小正方體沿z方向移動，那小正方體里的點云數(shù)量應(yīng)該不變。

b、如果小正方體位于邊緣上，則沿邊緣移動，點云數(shù)量幾乎不變，沿垂直邊緣方向移動，點云數(shù)量改變。

c、如果小正方體位于角點上，則兩個方向都會大幅改變點云數(shù)量。

⑷NARF算法

NARF全稱normal aligned radial feature(法線對齊的徑向特征)。是一種3D特征點檢測和描述算法。能提取到 borders points 和其對應(yīng)的 shadow points，提取到的特征點都是位于物體的外輪廓(邊緣)上，更加具有穩(wěn)定性和可重復(fù)性。對特征點Normal的估計只使用共面點，因而對Normal的估計更加穩(wěn)定。所有操作都是基于2D的range image，計算量相比于直接操作點云要小。

對點云而言，場景的邊緣代表前景物體和背景物體的分界線。所以，點云的邊緣又分為三種：前景邊緣，背景邊緣，陰影邊緣。三維點云的邊緣有個很重要的特征，就是點a 和點b 如果在 rang Image 上是相鄰的，然而在三維距離上卻很遠，那么多半這里就有邊緣。

1.這個點在某個平面上，邊長為 s 的方窗沒有涉及到邊緣。

2.這個點恰好在某條邊緣上，邊長 s 的方窗一半在邊緣左邊，一半在右邊。

3.這個點恰好處于某個角點上，邊長 s 的方窗可能只有 1/4 與點處于同一個平面。

將該點與不同點距離進行排序，得到一系列的距離；若這個數(shù)列存在某個階躍跳動（可能會形成類似階躍信號），那么發(fā)生階躍的地方應(yīng)該是有邊緣存在。

⑸SIFT3D算法

尺度不變特征轉(zhuǎn)換(Scale-invariant feature transform,SIFT)是David Lowe在1999年發(fā)表，2004年總結(jié)完善。該算法通過求一幅圖中的特征點（interest points,or corner points）及其有關(guān)scale和orientation的描述子得到特征并進行圖像特征點匹配。

首先構(gòu)建尺度空間，目的是為了模擬圖像數(shù)據(jù)的多尺度特征；為了尋找尺度空間的極值點，每一個采樣點要和它所有的相鄰點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應(yīng)的9×2個點共26個點比較，以確保在尺度空間和二維圖像空間都檢測到極值點。一個點如果在尺度空間本層以及上下兩層的26個領(lǐng)域中是最大或最小值時，就認為該點是圖像在該尺度下的一個特征點；然后去除不好的特征點：本質(zhì)上要去掉尺度空間局部曲率非常不對稱的像素；上一步中確定了每幅圖中的特征點，為每個特征點計算一個方向，依照這個方向做進一步的計算，利用關(guān)鍵點鄰域像素的梯度方向分布特性為每個關(guān)鍵點指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。

3.2.2 點云的特征線提取算法

在特征線提取方面，大部分學者主要針對網(wǎng)格模型進行相關(guān)特征線提取方法的研究，對點云模型的特征線提取研究相對而言較少，主要原因在于點云數(shù)據(jù)量大，本身沒有自然拓撲連接關(guān)系，而且還可能存在噪聲、數(shù)據(jù)缺失等問題，所以在點云數(shù)據(jù)上提取特征線比較困難。但是，利用點云數(shù)據(jù)提取特征線，由于不需要重建網(wǎng)格數(shù)據(jù)，具有所需時間少，而且數(shù)據(jù)容易獲取的優(yōu)勢。

目前，基于點云模型的特征線提取的方法可以分為基于幾何特征、基于協(xié)方差分析和基于投影映射的三類方法。

⑴基于幾何特征的方法

此方法是利用點云的幾何信息，比如法向量、曲率、Voronoi圖等來提取特征曲線。Demarsin[1]等首先利用法向量估計的而信息對點云數(shù)據(jù)進行分割，對于每個分割后的區(qū)域內(nèi)的點集，利用最小生成樹的算法進行特征曲線的提取。Yang B[2]等提出的方法首先將根據(jù)曲率選擇視覺突出點進行聚類，并未每個點賦予權(quán)重，然后提出描述點云形狀特征的波峰線。劉倩[3]等提出的方法在高斯映射的基礎(chǔ)上，對曲率值進行分析，主要是用來提取模型中較為尖銳部分的特征曲線，對于模型中的一些細微特征沒有辦法識別出。Merigot[4]等通過計算本地 Voronoi 圖獲得鄰域信息，然后計算曲率，但是 Voronoi 圖容易受到噪聲點的影響。

⑵基于協(xié)方差分析的方法

基于協(xié)方差分析的方法是根據(jù)協(xié)方差矩陣的特征值，通過對特征值進行計算分析，可以用來表示模型局部曲面的彎曲程度。Gumhold等[5]對局部鄰域構(gòu)建協(xié)方差矩陣，計算得到特征值，根據(jù)其比例關(guān)系，將特征點分為邊界點，棱點，角點，構(gòu)建最小生成樹，提取出特征曲線。上述方法需要高質(zhì)量的點云，而且對細微特征不敏感。Nie J[6-7]等首先利用 PCA 計算曲面變化度，并根據(jù)符號曲面變化度絕對值識別潛在特征點，對其進行分割, 然后根據(jù)曲面變化度與設(shè)置的距離權(quán)重不斷將邊界點進行細化，最終采用最小生成樹的算法將特征點進行連接，得到特征曲線。但該方法隨著噪聲程度增加，特征線易出現(xiàn)斷裂和缺損。

⑶基于投影映射的方法

基于投影映射的方法是經(jīng)過擬合得到模型的局部曲面，并將特征點投影在該曲面上。Daniels[8]等利用魯棒移動最小二乘法，擬合每個點鄰域的曲面，再將特征點投影到不同曲面的交線上，以提取特征線。但是因為該方法是在移動最小二乘的基礎(chǔ)上實現(xiàn)的，算法運行的時間過長，代價略高。龐旭芳[9]等通過擬合局部二次曲面計算曲率，然后找到與特征點距離最短的潛在特征線，并把特征點投影在該條線上，得到增強后的特征點。這種方法可以提取到模型上平緩和細微的特征，但是最終得到的特征曲線中有部分特征線之間有裂縫。

點云特征描述

一個良好的特征描述子應(yīng)能包含所在局部表面的主要形狀信息以提供足量的鑒別力。此外，一個良好的特征描述子還應(yīng)對噪聲、遮擋、背景干擾、點密度變化以及視點變化等穩(wěn)健。現(xiàn)有的局部特征描述算法可以分為基于點特性、基于直方圖以及基于變換的算法三類。

3.3.1 基于點特性的方法

這類方法直接采用關(guān)鍵點局部鄰域內(nèi)部分或全部點上的幾何屬性集合對其局部鄰域進行描述[45]。

Stein和Medioni[1]采用關(guān)鍵點的測地鄰域點法向量分布構(gòu)建splash特征描述子。給定關(guān)鍵點p，首先采用測地半徑r獲得網(wǎng)格上的一個環(huán)狀切線，進而采用點p處的曲面切平面及法向量n構(gòu)建一個局部參考坐標框架（Local Reference Frame，LRF）。采用該LRF，將點p的法向量與環(huán)狀切線上點的法向量的關(guān)系（即角度距離）采用一個三維矢量進行表示。接著，采用直線段對該三維曲線進行擬合，并以三維直線段的曲率和扭轉(zhuǎn)角（torsion angle）構(gòu)建特征描述子。實驗結(jié)果表明，該算法對噪聲穩(wěn)健。

Chua和Jarvis[2]提出了point signature特征描述子。Sun和Abidi[3]受人類指紋的啟發(fā)，提出了一種 point’s fingerprint 特征描述子。給定關(guān)鍵點p，首先以與點 p的測地距離相同的點構(gòu)成一個測地圓（geodesic circle），采用一系列不同的測地距離從而獲得一個測地圓集合。進而采用點p的法向量和切平面構(gòu)建一個LRF，并將這一系列測地圓投影到切平面上以獲得一組二維等值線。采用這些二維等值線以及測地圓上的法向量和半徑變化量等構(gòu)成特征描述子。Sun和Abidi認為該算法優(yōu)于 point signature 和 spin image 特征，且其計算量相對較小。

Malassiotis和Strintzis[4]通過對關(guān)鍵點p的鄰域點散布矩陣進行特征值分解從而構(gòu)建一個LRF，然后在z軸方向與點p距離為d的位置放置一個虛擬針孔相機。該相機朝向點p，且該相機坐標系的x軸和y軸分別與點p處局部參考坐標系的x軸和y軸對齊。進而將局部鄰域點投影到虛擬相機的成像平面并記錄這些點到成像平面的距離從而獲得 snapshot 特征描述子。snapshot 特征描述子對自遮擋穩(wěn)健且易于計算，其獲得了比 spin image更好的成對點云配準結(jié)果。類似的，文獻[5]首先定義一個LRF并采用一個規(guī)則的柵格對局部表面進行擬合，并采用局部表面在該柵格上的深度值作為局部特征描述子。最后，采用主成分分析（Principle Component Analysis，PCA）對該特征描述子做進一步壓縮。

Castellani等[6]通過順時針地將關(guān)鍵點p的一環(huán)（1-ring）鄰域點連接起來，接著將二環(huán)及三環(huán)鄰域點連接，不斷重復(fù)該過程直到測地半徑達到閾值r為止，從而獲得關(guān)鍵點p周圍的一個順時針回形線。在該螺旋線上提取采樣點的顯著級別、最大曲率、最小曲率以及表面法向量變化量等屬性，進而采用離散時間隱馬爾科夫模型（Hidden Markov Model， HMM） 記錄該螺旋線上的信息，從而獲得 HMM 特征描述子。該 HMM 描述子對旋轉(zhuǎn)、非均勻采樣以及網(wǎng)格分辨率變化等十分穩(wěn)健。實驗結(jié)果表明其匹配性能優(yōu)于spin image和3D shapecontext 特征描述子。

Steder 等[7, 8]首先將關(guān)鍵點p的鄰域表面與該點的法向量對齊，然后采用一個星狀模式圖（star pattern）放置到該對齊的表面上。該星狀模式圖的每個束線即對應(yīng)于Normal Aligned Radial Feature（NARF）特征描述子的一個值。NARF描述子記錄了每個束線上的點變化量。為使得該特征描述子具有對旋轉(zhuǎn)的不變性，該算法從特征描述子中提取一個唯一確定的方向并依據(jù)該方向?qū)μ卣髅枋鲎舆M行移位操作。該 NARF 特征描述子的特征匹配性能優(yōu)于spin image 特征描述子。

3.3.2 基于直方圖的方法

這類方法首先利用點云的某些信息（如點坐標、幾何屬性）定義直方圖的一個或多個維度，然后采用鄰域點的幾何或拓撲測量值（如點數(shù)、 網(wǎng)格面積）對直方圖中的相應(yīng)單元格進行累加從而獲得直方圖統(tǒng)計以實現(xiàn)對局部表面的描述[9]。這類方法可進一步細分為基于空間分布直方圖、 基于幾何屬性直方圖以及基于方向梯度直方圖的方法。

⑴基于空間分布直方圖的方法

這類方法依據(jù)局部鄰域點的空間分布（如點坐標）獲取直方圖統(tǒng)計以實現(xiàn)局部表面描述。這類方法首先在關(guān)鍵點上定義一個局部參考坐標框架或參考坐標軸，然后在該坐標系下將三維鄰域空間劃分成多個單元格，通過統(tǒng)計每個單元格上的空間分布測量值（如點數(shù)、網(wǎng)格面積）獲得特征描述子。這類算法主要需解決兩個問題，一是如何構(gòu)建 LRF，二是如何對鄰域空間進行劃分。

spin image特征描述子對剛性變換、 背景干擾以及遮擋穩(wěn)健[10]，且在點云配準、三維目標識別以及三維模型重建等多個場合得到了廣泛應(yīng)用。spin image已成為了三維局部特征描述子評估的事實基準[11-15]。但是，spin image依然存在許多缺陷：首先，spin image 特征對數(shù)據(jù)分辨率變化和非均勻采樣敏感；其次，由于該特征的計算過程需要將三維點云投影到二維空間，因而維度信息的丟失使得其鑒別力有限。后續(xù)有大量算法對 spin image 特征描述子的各個方面進行改進，典型例子如基于面的spin image[16]、spin image signature[17]、多分辨率spin image[18]、球形spin image[19]、尺度不變spin image[20]、以及顏色spin image[21]。

Frome 等[22]將二維 shape context 特征描述子擴展到三維點云，從而獲得三維形狀上下文（3D Shape Context， 3DSC）特征描述子。該算法采用關(guān)鍵點 p 的法向量 n 作為局部參考坐標軸，并將球形鄰域空間劃分成一系列單元格。為獲得對旋轉(zhuǎn)的不變性， Tombari 等[23]對 3DSC 進行了改進，通過給每個關(guān)鍵點賦予一個可重復(fù)且唯一確定的 LRF 以獲得單值形狀上下文（Unique Shape Context， USC） 特征描述子。實驗結(jié)果表明， 相比于 3DSC， USC 對存儲的要求顯著降低，且特征匹配的性能有所提高。此外，Sukno 等[24]亦提出一種對水平面旋轉(zhuǎn)具有不變性的非對稱模式形狀上下文（Asymmetry Patterns Shape Context，APSC）。實驗結(jié)果表明 APSC 獲得了與 3DSC 相當?shù)男阅堋ΧS shape context的另一種改進是內(nèi)蘊形狀上下文（Intrinsic Shape Context， ISC）特征描述子， 該描述子具有對等距形變的不變性。

Mian 等[25]提出了一種 3D tensor 特征描述子。該算法首先選擇一對滿足特定幾何約束的點構(gòu)建局部參考坐標系，進而在該坐標系下進行空間三維柵格劃分，并計算點云網(wǎng)格與每個柵格單元的相交面積從而得到 3D tensor 特征描述子。由于該算法采用表面面積而非點個數(shù)來獲得直方圖， 因此其對噪聲和分辨率變化較為穩(wěn)健。實驗結(jié)果表明該算法優(yōu)于 spin image，其缺陷之一在于 LRF 的構(gòu)建過程涉及網(wǎng)格頂點對的組合爆炸問題，因此運算量較大。

Zhong[26]提出了一種內(nèi)蘊形狀特征（Intrinsic Shape Signature， ISS）描述子。該算法首先對鄰域點的協(xié)方差矩陣進行特征值分解從而構(gòu)建 LRF， 進而采用離散球面網(wǎng)格將球形鄰域空間劃分成均勻分布的柵格。通過統(tǒng)計每個柵格單元內(nèi)的點密度加權(quán)和從而獲得 ISS 特征描述子。車輛識別實驗結(jié)果表明，該算法在存在噪聲、遮擋和背景干擾時的性能優(yōu)于 spin image和3DSC。

⑵基于幾何屬性直方圖的方法

這類算法依據(jù)關(guān)鍵點局部鄰域的幾何屬性（如法向量及曲率）進行直方圖統(tǒng)計從而獲得特征描述子。

Yamany 和Farag[14]采用單形角近似估計自由形狀表面上的曲率，將關(guān)鍵點鄰域的單形角累加到一個二維直方圖中，從而得到 surface signature 特征描述子。實驗結(jié)果表明 surface signature 優(yōu)于splash、 point signature 和 spin image 特征描述子。

Chen 和Bhanu[27]通過將關(guān)鍵點鄰域的點數(shù)累加到一個二維直方圖中從而獲得 Local Surface Patches（LSP）特征描述子。LSP 特征描述子直方圖的一維為鄰域點的形狀指數(shù)值， 另一維為關(guān)鍵點 p 法向量與鄰域點法向量的夾角。實驗結(jié)果表明 LSP 在三維目標識別應(yīng)用中能獲得與 spin image 相當?shù)男阅埽?LSP 的計算效率更高。

Flint 等[28]通過將關(guān)鍵點鄰域的點數(shù)累加到由表面法向量夾角定義的一維直方圖中從而獲得 THRIFT 特征描述子。Flint 等在其后續(xù)工作[29]中對該算法進行了改進， 改進的算法采用關(guān)鍵點法向量與鄰域點法向量的夾角計算加權(quán)直方圖。實驗結(jié)果表明THRIFT 對噪聲和點密度變化較穩(wěn)健。

Taati等[30]對點云上每個點q的鄰域點協(xié)方差矩陣進行主成分分析從而獲得該點的 LRF 及三個特征值。在此基礎(chǔ)上，利用每個點 q 的 LRF 和特征值獲得一系列位置屬性值、 方向?qū)傩灾岛蜕⒉紝傩灾担M而采用特征選擇算法從這些屬性中選取部分屬性，并將關(guān)鍵點 p 的鄰域點屬性值累加到一個直方圖中，從而得到可變維度局部形狀描述子（Variable Dimensional Local Shape Descriptor，VD-LSD）。Taati 和Greenspan[31]亦給出了基于模型幾何形狀和傳感器特性實現(xiàn)最優(yōu)特征描述子選擇的方法。實驗結(jié)果表明，VD-LSD 在多個數(shù)據(jù)集上的識別率優(yōu)于 spin image特征描述子。

Rusu 等提出了一種用于局部表面描述的 Point Feature Histograms（PFH） 特征描述子。對于關(guān)鍵點 p 鄰域內(nèi)的一個點對，首先計算其 Darboux 框架，進而采用文獻[32]的方法計算由法向量以及點對距離向量等得到的四個測量值。最后，將所有點對的測量值累加到一個長度為16的直方圖中，即得到 PFH 特征描述子。為提高 PFH 的計算效率， Rusu 等[33]僅將興趣點與其鄰域點之間（而非所有鄰域點對） 的四個測量值累加到一個直方圖中，從而得到 Simplified Point Feature Histogram（SPFH）。最后將關(guān)鍵點 p 的所有鄰域點 SPFH 進行加權(quán)求和得到 Fast Point Feature Histograms（FPFH） 特征描述子。FPFH 保留了 PFH 中的絕大部分鑒別信息，且其計算復(fù)雜度明顯降低。

Tombari 等[9]首先為關(guān)鍵點 p 構(gòu)建一個 LRF， 進而在該坐標系下將球形鄰域空間進行柵格化以獲得多個三維柵格單元。在每個柵格單元上， 依據(jù)落入該單元的點的法向量與關(guān)鍵點法向量的夾角將這些點累加到一個直方圖中。最后，將所有柵格單元內(nèi)的直方圖串聯(lián)起來以獲得總的 Signature of Histograms of Orientations（SHOT）特征。SHOT 特征描述性強，計算效率高，且對噪聲穩(wěn)健。實驗結(jié)果表明在各種噪聲強度下的 SHOT 性能均優(yōu)于 spin image 及 point signature 特征描述子。然而，該算法對數(shù)據(jù)分辨率變化較為敏感。此后，Tombari 等[34]結(jié)合形狀信息和顏色信息提出了Color-SHOT（CSHOT）特征描述子。實驗結(jié)果表明，將顏色（紋理）信息融合到幾何特征描述子中有利于進一步提高其性能。

⑶基于梯度方向直方圖的算法

這類方法依據(jù)關(guān)鍵點的鄰域點梯度方向構(gòu)建直方圖從而獲得特征描述子。

Hua等[35]將三維點云網(wǎng)格映射到二維規(guī)范化域中，并將表面的平均曲率和保角因子投影到一個兩通道的形狀矢量圖像中。對于每個通道，采用與尺度不變特征變換（Scale Invariant Feature Transform， SIFT）類似的方法提取特征描述子。首先將每個二維平面劃分成 16個子區(qū)域，并在每個子區(qū)域中依據(jù)梯度方向獲得一個八單元的直方圖。最后，將兩個通道中的所有直方圖串聯(lián)起來便得到最終的描述子。實驗結(jié)果表明，該特征描述子較為穩(wěn)健且可良好應(yīng)用于點云匹配。

Zaharescu 等[36]首先在點云網(wǎng)格的頂點上定義一個標量函數(shù) f 并計算該函數(shù)的梯度 ?f ，該標量函數(shù)可以為曲率、法向量、密度以及紋理（強度）等。進而在每個關(guān)鍵點 p 處計算一個 LRF并將梯度向量投影到該坐標系三個相互正交的平面上，并將每個平面劃分成四個子區(qū)域。在每個子區(qū)域中，依據(jù)梯度方向 ?f 構(gòu)建一個八單元的直方圖。最后，將三個平面上所有子區(qū)域中得到的直方圖連接起來便得到最終的網(wǎng)格方向梯度直方圖（Mesh Histograms of Oriented Gradients，MeshHOG）特征描述子。MeshHOG 的有效性已通過剛性和非剛性物體的特征匹配得到驗證。但是，MeshHOG 并不能應(yīng)用于存在較大形變的物體。

Hou 和Qin[37]首先在點云網(wǎng)格的每個點上定義一個標量函數(shù) f 并計算其梯度?f。進而采用極坐標系 [d(q) , θ (q)] 對每個鄰域點q進行表示，其中 d(q) 為從點p 到 q 的測地距離，θ (q) 為在局部切平面上從點 q 到 p 的主方向的極坐標角。接著，將該二維參數(shù)化平面分成九個子區(qū)域，并在每個子區(qū)域中依據(jù)梯度 ?f 的方向構(gòu)建一個八單元的直方圖。最后將九個子區(qū)域中得到的直方圖串聯(lián)起來便得到了最終的特征描述子。匹配結(jié)果表明，該方法能獲得比 MeshHOG更高的召回率和精度，且對存在較大等距形變的物體亦能得到較好的結(jié)果。

3.3.3 基于變換的方法

這類方法首先將點云從空間域變換到其它域（比如譜域），進而采用該變換域中的信息實現(xiàn)對關(guān)鍵點局部鄰域的描述。

Hu 和Hua[38]首先對局部表面點進行Laplace-Beltrami 變換從而獲得局部表面的譜， 進而依據(jù)其譜分布構(gòu)建直方圖作為特征描述子。實驗結(jié)果表明該特征描述子可很好地實現(xiàn)相似形狀的匹配。此外，該特征描述子亦對剛性變換、等距形變以及尺度變化等具有不變性。Sun 等[39]提出了一種熱核特征（Heat Kernel Signature，HKS）描述子。該算法將網(wǎng)格M當做一個黎曼流形，并將熱核 K t (p, q) 限制在時域，即 K t (p, p) 。K t (p, p) 即為所求的 HKS 特征描述子。該特征描述子可看做是多尺度的高斯曲率，其中時間參數(shù) t 給出了尺度信息。HKS 是三維形狀的內(nèi)蘊屬性， 其對等距形變具有較好的不變性。在后續(xù)研究中， Bronstein 和Kokkinos[40]提出了一種尺度不變 HKS 特征描述子用于非剛性形狀檢索，Kovnatsky等[41]提出了一種包含光度信息的 HKS 特征描述子。

Knopp等[42]將二維圖像中的加速穩(wěn)健特征（Speeded Up Robust Feature，SURF）描述子推廣到三維點云領(lǐng)域，得到 3D SURF 描述子。該算法首先將點云體素化以得到三維體圖像， 并對該體圖像進行Haar小波變換，并采用關(guān)鍵點p鄰域的 Haar小波響應(yīng)獲得關(guān)鍵點 p 的局部參考坐標系。接著，將關(guān)鍵點鄰域劃分成N b × N b × N b個單元，在每個單元中提取向量 v =( ∑ h x ,∑h y ,∑h z ) ，其中h x、h y和h z分別為沿 x、y和z軸的 Haar小波響應(yīng)。最后，將 N b × N b × N b個單元中的所有向量串聯(lián)起來以獲得 3D SURF 描述子。

綜上所述，可得到如下簡要結(jié)論：

①在三大類局部特征描述算法中，基于直方圖的方法得到了最廣泛地研究。在基于直方圖的方法中，基于幾何屬性直方圖和基于梯度方向直方圖的方法均依賴于曲面的一階或者二階微分，因此這些方法對噪聲較為敏感。

②為獲得對剛性變換的不變性，大部分算法借助于 LRF 構(gòu)建。這些算法首先在關(guān)鍵點上構(gòu)建局部參考坐標系，進而將局部鄰域點轉(zhuǎn)換到該坐標系下。因此，LRF 的可重復(fù)性及穩(wěn)健性對特征描述子的性能有很大的影響。

③為獲得對等距形變的不變性，部分算法采用測地距離（或其 k 環(huán)近似）代替歐氏距離，另有部分算法則通過將點云變換到某個特定的域中以獲得不變性，如 Laplace-Beltrami 譜域或時域。

④鄰域大小對特征描述子的性能有較大影響。一個大的鄰域半徑可使特征描述子記錄更多的形狀信息，但同時也使特征描述子對遮擋和背景干擾更加敏感。部分算法為其特征描述子配置了相應(yīng)的自適應(yīng)關(guān)鍵點檢測子。但事實上，可將任意兩個關(guān)鍵點檢測子和局部特征描述子進行搭配以尋找具有最優(yōu)性能的組合。

⑤現(xiàn)有特征描述子難以同時獲得高鑒別力、對噪聲/數(shù)據(jù)分辨率/逸出噪聲等干擾的強穩(wěn)健性以及高計算效率。

點云分割與分類

點云分割與分類識別是三維目標檢測的基礎(chǔ)，也是目前的研究熱點。三維點云分割是分類識別的基礎(chǔ)。點云的分割與分類有一定區(qū)別，點云分割是根據(jù)空間，幾何和紋理等特征點進行劃分，使同一劃分內(nèi)的點云擁有相似的特征。點云分割的目的是分塊，從而便于單獨處理。點云的分類是為每個點分配一個語義標記，將點云分類到不同的點云集，同一個點云集具有相似或相同的屬性，如法向量、曲率、樹木、人等。

3.4.1 點云分割

三維點云的分割方法有很多種，一般主要有四種：基于邊緣、區(qū)域增長、聚類、顏

色RGB值的分割方法，以下分別介紹。

⑴基于邊緣的分割方法

Milroy[1]提出了一種新的確定邊界方式，即首先確定邊界點然后用能量等高線將各適界點連接起來即為邊界，其中將正交截面模型中曲率最大值點作為邊界點。劉勝蘭[2]提出了利用三角網(wǎng)格模型中主方向上主曲率為極值的頂點為特征點并且以此為起點做出特征線的提取方法。張強[3]將局部臨近點網(wǎng)格化，先將三角面片頂點的法向量調(diào)整為同一個方向，點的法向量是用加權(quán)平均相鄰三角面片的法向量替代的，然后利用平面點云的同向性和共面性對點云數(shù)進行分割。龔友平通過估算曲率的極值尋找邊界點，把邊界點連線從而構(gòu)建邊界。Woo[4]使用八叉樹對空間網(wǎng)格進行細分和法矢標準差的提取，實現(xiàn)了三維點云的分割。

基于邊緣的分割方法速度快，對尖銳的邊界比較敏感，但確定邊界僅使用局部數(shù)據(jù)，所對于散亂的三維點云不能準確找到其邊界，分割結(jié)果達不到一定標準。

⑵基于區(qū)域增長的分割方法

該種分割方法實質(zhì)是把相同特征的點劃分為一個區(qū)域，而區(qū)域主要通過自上而下、自下而上兩種方式不斷迭代增長。自上而下方法是先選擇種子片面或種子點，并且按一定準則向外延伸，確定鄰近點是否在相同面，持續(xù)到鄰域巧不存在連續(xù)點集，形成連接集合。而自下而上方法是先假設(shè)所有的點都在同一個面，擬合過程中誤差不符合要求時，就把原集合分為兩個集合。Kuo[5]等提出的DBRB（Delaunay-based Region-growing Algorithm）算法，該算法同時有Delaunay和區(qū)域增長的優(yōu)點，先利用Delaunay構(gòu)建三角片，角片為種子，不斷擴大，其實質(zhì)是通過迭代不斷擴大三角片區(qū)域直到區(qū)域的邊界。梁學章[6]等提出一種三角網(wǎng)絡(luò)曲面的區(qū)域增長算法，先對點云進行預(yù)處理以達到數(shù)據(jù)精簡的目的，然后在點云中選擇新的匹配點構(gòu)成新的三角形并連續(xù)更新邊界以達到分割區(qū)域的不斷增長。

基于區(qū)域增長的分割方法對由多項式表達的二次曲面分割更加有效。但在使用基于區(qū)域增長的分割方法時，由于需要選擇種子點或者種子片面，很難選擇合適的種子，并且很難區(qū)分光滑邊界，而且由于很難選擇合適的生長準則，受給定閥值影響大。其中自上而下的方法比較適用規(guī)則曲面的區(qū)域分割，自上而下的方法適用于數(shù)據(jù)點較少的。由于三維點云，往往場景很大，比較復(fù)雜，所以基于區(qū)域增長的分割方法適用情況有限。

⑶基于聚類的分割方法

該種分割方法屬于多元統(tǒng)計分析，根據(jù)樣本空間的特征，按照相似性和相似性測量準則對數(shù)據(jù)進行分類，使得同一類中的點有相同或者近似的屬性，不同類別的點的屬性不同。基于聚類的分割方法中常用的算法有：k-means算法，k-medoids算法，OPTIC算法，DENCLUE算法，STING算法，WAVE-CLUSTER算法，模糊聚類FCM。郭瑞[7]提出一種基于點的鄰域信息（灰度值、鄰域均方差、鄰域均值、B值、熵值）的FCM分割算法。針對漸進式聚類，時收斂速度加快，抗噪性增強。Jean Koh[8]利用數(shù)據(jù)點的特征權(quán)值構(gòu)成八維特征向量，其包括：數(shù)據(jù)點的坐標、法矢量、高斯曲率和平均曲率，利用多層自組織特征映射網(wǎng)絡(luò)SOFM對八維特征向量來聚類，達到了區(qū)域分割的目的。劉雪梅[9]則添加法矢量、平均曲率以及高斯曲率來構(gòu)成八維向量作為特征向量。

對于具有明顯的曲面類型的數(shù)據(jù)進行分割，基于聚類的分割方法效果比較好，然而對于復(fù)雜環(huán)境和結(jié)構(gòu)復(fù)雜的物體中，很難直接確定曲面的分類個數(shù)和曲面類型。

⑷基于顏色RGB值的分割方法

為了豐富分割方法，提高分割品質(zhì)，萬燕[10]等提出了一種基于HSV顏色空間的區(qū)域增長算法。該算法先求得區(qū)域增長的種子點同時確定分割的閾值，然后利用網(wǎng)格信息找到種子點的鄰近點集，最后根據(jù)H分量的相似程度分割點云。Zhuo[11]提出了一個無監(jiān)督分割算法平衡RGB-D圖像中顏色和深度特性。輸出部分包含可大可小的分割部分正確地表示了實物在場景中的位置，并且時間小于監(jiān)督分割算法。Steven Hickson[12]提出一種無監(jiān)督分層的分割算法，該算法對深度和顏色的結(jié)合體進行過分割，再用一棵樹去合并過分割的區(qū)域。該方法準確地分割，并且質(zhì)量得到一定提高。盧良鋒[13]將深度學習和RGB、深度進行有效的結(jié)合，該方法提離了物體的識別準確率。

3.4.2 點云分類

依據(jù)獲取特征的方式不同，本文將三維點云分類方法分為三大類：基于點的分類，基于傳統(tǒng)機器學習方法的分類和基于深度學習的分類，并對各方法進行了詳細地總結(jié)。

⑴基于點的分類方法

點簽名法[14](Point Signature)，由 Chua 等人于 1994年提出。該方法根據(jù)每個點的球半徑鄰域與物體的交線 C 所擬合平面的法向量與參考矢量定義旋轉(zhuǎn)角，從而計算簽名距離，即每個點的簽名，通過匹配簽名實現(xiàn)分類。該方法消除了一階導數(shù)的計算過程，但對噪聲數(shù)據(jù)的處理效果較差。也有一些學者利用形狀特征對點云進行識別，如旋轉(zhuǎn)圖像[15-16]和體素網(wǎng)格[17]。如文獻[15]中提出了一種旋轉(zhuǎn)圖像法，通過二維數(shù)據(jù)生成旋轉(zhuǎn)圖以表征三維點云，可用于多目標分類但對大范圍的遮擋物不能進行有效識別。董[17]等人提出了一種用于激光掃描數(shù)據(jù)的多目標的層次化提取方法。該算法：利用點云的多種特征，如顏色，激光反射強度，法向量，主方向等生成超級體素，然后利用體素特征快速實現(xiàn)小規(guī)模場景中的多目標點云的分割分類，但對于沒有樹冠的樹木以及被樹木遮擋的街燈仍出現(xiàn)誤識別問題。

⑵基于傳統(tǒng)機器學習的方法

利用機器學習方法進行點云分類，本質(zhì)就是借助模型進行特征的自學習和分類，國內(nèi)外很多學者貢獻了很多研究成果。常用的監(jiān)督學習方法有：隨機森林[18]，支持向量機(SVM)[19]，馬爾可夫隨機場等。如孫[18]等人提出了一種隨機森林的城區(qū)機載點云識別方法，結(jié)合幾何，紋理，空間等特征用于城市地物分類，實驗結(jié)果表明通過自動篩選特征的方法略優(yōu)于所有特征分類精度。文獻[19]中提出了一種基于特征圖像的 SVM建筑物立面的半自動提取方法。該方法利用三維數(shù)據(jù)生成二維特征圖像，再結(jié)合支持向量機與二維網(wǎng)格屬性對特征圖像進行特征提取以達到分類目標。雖然有效降低計算開銷，但只能提取一般建筑物，不適用于復(fù)雜場景的多目標物提取。

⑶基于深度學習的分類方法

盡管以上方法在一定程度上能實現(xiàn)分類任務(wù)，但是特征的簡單組合，淺層模型很難推廣到大型復(fù)雜三維場景中。隨著以深度學習為代表的人工智能的快速發(fā)展，國內(nèi)外研究者們嘗試將深度學習算法用于距離影像的分類。針對原有網(wǎng)格表示方法提取的低級特征表示不足，泛化性能差，無法滿足應(yīng)用需求。Qi[20]等人首次打破傳統(tǒng)，設(shè)計了一種名為 Point Net 的網(wǎng)絡(luò)，其基本思想直接對點云進行處理，使用對稱函數(shù)解決了點云的順序問題，整合單點特征以形成全局的點簽名，能有效處理室內(nèi)場景中的 3D 物體分類，目標分割和語義場景分割任務(wù)。但是 Point Net 不能捕獲度量空間點的局部特征，限制了其識別細粒圖案的能力和復(fù)雜場景的泛化性能。

為了解決這個問題，設(shè)計了一種名為Point Net++[21]的分層神經(jīng)網(wǎng)絡(luò)。該網(wǎng)絡(luò)步驟為:將點云分割成重疊的局部區(qū)域，從中分層提取局部幾何特征，以形成高層特征。實驗結(jié)果表明，取得了良好的性能。以上方法均未考慮點云顏色等信息，但Roman[22]等人提出了一種 Deep Kd- Networks, 該網(wǎng)絡(luò)可以將數(shù)據(jù)的顏色、反射光強度、法向量屬性作為輸入，利用 kd- tree 將點云結(jié)構(gòu)化，學習樹中每個節(jié)點的權(quán)重，在 Model Net數(shù)據(jù)集的準確率高達 90.6%，但該網(wǎng)絡(luò)對噪聲和旋轉(zhuǎn)敏感，對每個點都需進行上采樣或下采樣操作，會帶來額外的計算開銷。基于以上研究進展，Li[23]等人提出了一種簡單通用的點云特征學習框架——Point CNN。它利用多層感知機從輸入點中學習一種變換陣，將無序點云轉(zhuǎn)換成有序點云，在 Model Net 上準確率為91.7%，但置換矩陣離預(yù)想相距甚遠，點云的順序問題仍是一個難題，同時該方法是針對單一點云模型進行分類，因此面向復(fù)雜場景的點云數(shù)據(jù)分類也是亟待解決的難點。

點云配準

由于三維掃描設(shè)備對物體的視野有一定的局限，或者物體本身的幾何形狀較為復(fù)雜，所以不可能在同一視點上獲得物體的所有數(shù)據(jù)信息。為了獲得被測物體的完整點云數(shù)據(jù)，要將不同視角獲得的面點云數(shù)據(jù)集成起來進行點云配準工作。點云配準的目的是尋找三維剛體變換，使在不同視角下獲取的點云數(shù)據(jù)的三維坐標能夠正確匹配和重疊。配準算法可分為成對點云配準和多視點云配準算法兩類[1]。

3.5.1 成對點云配準算法

成對點云配準算法包含粗配準和精配準兩個步驟，其中粗配準可進一步細分為基于關(guān)鍵點匹配的粗配準算法、基于線匹配的粗配準算法以及基于面匹配的粗配準算法三類。上述三類粗配準算法既可單獨使用，也可組合使用[2]。

⑴基于關(guān)鍵點匹配的粗配準算法

這類方法首先在兩幅點云上提取一系列關(guān)鍵點，并采用每個關(guān)鍵點上的鄰域信息提取局部特征，進而通過特征匹配獲得關(guān)鍵點對集合（point correspondences），最后利用該關(guān)鍵點對集合計算點云間的初始變換關(guān)系。Chua 和Jarvis[3]在點云上提取一系列關(guān)鍵點，并采用 point signature 特征對每個關(guān)鍵點的局部鄰域進行描述。首先將一幅點云上的一個特征與另一幅點云上的特征進行匹配以獲得一個關(guān)鍵點對，進而找到另外兩個滿足特定空間約束的關(guān)鍵點對。得到三個關(guān)鍵點對后便可計算兩幅點云之間的變換關(guān)系。

Johnson和Hebert[4]采用spin image對關(guān)鍵點局部鄰域進行描述，并采用最近鄰法獲得關(guān)鍵點對。該算法對特征對進行聚類并采用幾何一致性算法去除錯誤的關(guān)鍵點對，最后采用滿足幾何一致性的關(guān)鍵點對計算兩幅點云之間的剛性變換關(guān)系。

Yamany和Farag[5]采用 surface signatures 對關(guān)鍵點局部鄰域進行描述，并采用圖像模板匹配及歐氏距離計算獲得關(guān)鍵點對集合。事實上，每三個關(guān)鍵點對組合均可得到一個剛性變換關(guān)系。為此，該算法從關(guān)鍵點對集合中選擇一系列滿足幾何一致性約束的關(guān)鍵點對組合， 并依據(jù)組合內(nèi)點對的空間距離對所有組合進行排序，最后對每個組合得到的剛性變換關(guān)系進行驗證。

Rusu等[6]采用 PFH 特征對關(guān)鍵點局部鄰域進行描述。匹配時，首先從待匹配點云中選擇兩個關(guān)鍵點，并分別找到其在庫點云中的 k 近鄰關(guān)鍵點。通過將待匹配點云上兩關(guān)鍵點之間距離與庫點云上兩候選對應(yīng)點之間距離最小化以獲得精確的對應(yīng)點。接著，繼續(xù)從待匹配點云中選擇新的關(guān)鍵點并重復(fù)上述過程以找到待匹配點云上所有關(guān)鍵點在庫點云上的精確對應(yīng)點。最后采用得到的特征對應(yīng)點對集合計算剛性變換關(guān)系。

Tombari 等[7]采用SHOT作為局部特征描述子并通過特征匹配獲得關(guān)鍵點對集合。得到關(guān)鍵點對集合后，采用絕對方向（absolute orientation）算法[8]和隨機采樣一致性（RANSAC）[9]算法計算點云之間的剛性變化關(guān)系。

⑵基于線匹配的粗配準算法

這類方法首先在點云上提取一系列線條，并利用線條對應(yīng)關(guān)系計算點云之間的變換矩陣。這類方法可進一步細分為基于直線匹配的方法以及基于曲線匹配的方法兩類。

基于直線匹配的方法首先從點云中提取一系列直線段，進而通過直線段匹配計算剛性變換關(guān)系。這類算法通常適用于包含較多平面和直線的物體，如建筑物等。Stamos 和Leordeanu[10]首先從點云中提取一系列平面和直線段，進而利用直線段的長度以及平面面積等信息高效地獲得兩幅點云間的匹配線段對集合。由于線段端點的位置準確度不高，因此文中只采用線段的位置和方向計算變換關(guān)系。理論上只需兩對對應(yīng)線段即可實現(xiàn)點云之間的變換關(guān)系計算，因此從匹配線段對集合中可以得到一系列變換關(guān)系。最后,以能使得平面數(shù)量最大化的變換關(guān)系作為兩幅點云之間的變換關(guān)系。實驗結(jié)果表明該算法可用于大數(shù)據(jù)量下的復(fù)雜形狀點云配準，但該算法對具有對稱形狀的場景點云配準依然存在困難。

Chao和Stamos[11]對文獻[10]的算法進行了改進，提出了一種更加高效且支持用戶交互的算法。該算法通過點云分割和對提取的線段及平面法向量進行聚類以得到每幅點云的三個主方向，從而為每幅點云構(gòu)建一個局部坐標系。通過將兩幅點云的局部坐標系進行對齊從而可快速精確地獲得點云間的旋轉(zhuǎn)變換矩陣。進而通過對旋轉(zhuǎn)后的點云直線段進行匹配從而獲得候選平移向量，最后采用最近鄰分類器對候選平移向量進行聚類，從而將聚類中心作為點云間的平移向量。為了進一步消除對稱三維表面可能帶來的錯誤匹配，該算法引入了一個用戶交互接口，從而可對拼接結(jié)果進行判斷并校正。對大場景（建筑物）的配準結(jié)果表明該算法可以達到毫米級的配準精度。該算法的缺陷在于某些場景（比如自然場景） 下提取直線段可能存在困難。

Vanden Wyngaerd和Van Gool[12]將這類算法進一步推廣到基于曲線的情況，從而通過雙切線匹配實現(xiàn)自由形態(tài)目標點云的配準。雙切線是由雙切點并集構(gòu)成的一對曲線，其可在對偶空間中獲得。當從對偶空間中獲得點云的所有雙切線之后，將兩幅點云之間的雙切線匹配。當?shù)玫揭粚﹄p切線匹配對后，便獲得了四個匹配點對（即對應(yīng)于兩個雙切線線段的端點）。由這四對匹配點對從而可以計算兩幅點云之間的剛性變換關(guān)系，并將點云變換到統(tǒng)一坐標系下以獲得配準誤差，以取得最小誤差的剛性變換關(guān)系用于點云粗配準。文獻[12]認為，相對于基于關(guān)鍵點匹配的算法，此文的算法運算量更小且穩(wěn)健性更強。其缺陷在于，對于某些形狀的物體，其點云上提取的雙切點較少，因而難以獲得較好的配準結(jié)果。

⑶基于面匹配的粗配準算法

這類算法通過將兩幅點云的表面進行匹配從而實現(xiàn)配準。

Chung 等[13]采用主成分分析法實現(xiàn)點云粗配準。該算法首先對每幅點云上的點坐標進行主成分分析，從而得到三個主方向。該算法認為，當兩幅點云的重疊區(qū)域較大時，二者的主方向會比較一致，因此可以通過將主方向?qū)R來實現(xiàn)點云的粗配準。該算法比基于關(guān)鍵點匹配和線匹配的算法更加快速。但該算法同樣存在很大的局限性。首先，點云上必須有較多的點；其次，該算法要求兩幅點云有較大的重疊面積；再次，該算法對存在對稱表面的點云效果很差。當主成分分析得到的兩個特征值相差不大時，主方向的順序會混淆，從而使得變換矩陣發(fā)生錯誤。

Chen 等[14]采用 RANSAC 算法實現(xiàn)點云粗配準。該算法首先在一幅點云上隨機選擇三個點，并計算每兩個點之間的距離。然后在另一幅點云上選擇滿足上述距離約束的三個潛在對應(yīng)點，從而構(gòu)成三個點對以得到一個潛在的變換關(guān)系。重復(fù)上述隨機采樣過程，從而可以得到一個變換關(guān)系集合。最后，以獲得點云對應(yīng)點數(shù)最多的變換關(guān)系作為兩幅點云之間的剛性變換。該算法即使在存在大量逸出點時亦能獲得很好的性能。但是該算法只適用于點云中點數(shù)較少的情形，否則隨機采樣的窮舉過程會導致運算量急劇增加。文獻[15]對該算法做了進一步改進以提高運算效率。

Brunnstrom 和Stoddart[16]采用遺傳算法尋找對應(yīng)點對從而實現(xiàn)點云配準。首先，利用點云上點之間的距離和夾角信息定義遺傳算法的擬合函數(shù)，進而確定遺傳算法的交叉概率和突變概率， 并采用遺傳算法不斷迭代直到滿足停止條件為止。遺傳算法停止時，使得擬合函數(shù)最大化的染色體中包含了所需要的點對應(yīng)關(guān)系。然而，這些點對中包含部分錯誤點對， 因此需要依據(jù)點對質(zhì)量選擇其中的部分點對計算點云之間的剛性變換關(guān)系。該算法能獲得很好的匹配結(jié)果，但是其運算量很大，因而難以應(yīng)用于對計算時間要求較高的場合。

Tarel 等[17]首先采用擬合算法獲得點云的隱式多項式模型，進而通過多項式模型實現(xiàn)點云配準。該算法不需要計算點匹配或面匹配，因而計算時間較快。但該算法要求兩幅點云之間有很高的重合度（通常要求重合度大于 85%），因此算法難以推廣到實際應(yīng)用中。

⑷成對點云精配準算法

精配準算法可分為直接配準法以及迭代配準法兩類，而目前主流的算法是迭代配準法。

最經(jīng)典的精配準算法為 ICP 算法[18]，該算法通過最小化點對（亦稱為最近點）之間的距離從而實現(xiàn)點云之間的精配準。對第一幅點云中的每一個點均尋找其在第二幅點云中的最近點，從而可獲得一個最近點對集合，進而計算點云間的變換關(guān)系使得最近點對的平均距離最小。重復(fù)上述過程，直到滿足收斂條件為止。該算法在存在高斯噪聲時亦可以取得很好的性能， 其不足之處在于非重疊區(qū)域會對匹配結(jié)果帶來比較大的影響。此外，當初始配準不準確時，ICP 精配準容易陷入局部極小值[19]。后續(xù)有大量算法對 ICP 的各個方面進行了改進，如文獻[20–23]對 ICP 的運算速度進行了提升，文獻[24, 25]結(jié)合幾何或顏色特征提高 ICP 算法精度，文獻[26–28]側(cè)重于提高算法對逸出點等干擾的穩(wěn)健性，文獻[26]針對 ICP 算法的精度和穩(wěn)健性等進行了一系列改進。

Chen 和Medioni[29]的算法過程與 ICP 類似，其不同之處在于通過最小化點與面之間的距離實現(xiàn)點云之間的精配準。該算法的最小化優(yōu)化函數(shù)為第一幅點云中的點到第二幅點云上的平面的平均距離。對于第一幅點云中的任一點，首先計算該點的法向量與第二幅點云的交點，進而采用第一幅點云中的點與其在第二幅點云中交點的距離作為點到面之間的距離。該算法對非重疊區(qū)域更加穩(wěn)健，且其達到收斂所需要的迭代次數(shù)更少，其缺陷在于點面距離的計算比較耗時。針對該算法的不足之處，后續(xù)有不少算法對其進行了改進[ 30, 31]。

Liu[32]將點云精配準的迭代過程建模成一個馬爾科夫鏈，其首先從用于馬爾科夫鏈的 Lyapunov 函數(shù)中推導了可用于描述熱力學系統(tǒng)成分長拖尾和短拖尾概率分布的熵， 并通過最大化該熵值估計點云間采用最近點準則構(gòu)建的點對概率。將估計的點對概率嵌入到平均場模擬退火算法中以實現(xiàn)全局最優(yōu)化，進而采用加權(quán)最小二乘法實現(xiàn)變換關(guān)系估計。其實驗結(jié)果表明該算法優(yōu)于 ICP 算法以及遺傳算法，其缺陷在于配準過程耗時過長。

3.5.2 多視點云配準算法

多視點云配準算法包含粗配準和精配準兩個步驟， 其中粗配準可進一步細分為序貫粗配準算法和同步粗配準算法兩類。

⑴多視點云序貫粗配準算法

序貫粗配準算法首先將兩幅點云配準，進而將第三幅點云與之前已配準的點云進行配準， 重復(fù)上述過程直到所有的點云均被配準到一個統(tǒng)一的坐標系下，如文獻[33, 34]。由于這類算法每次只將兩幅點云進行處理，因此減少了配準操作所需的內(nèi)存和計算負擔，且每次操作的計算量與待配準的點云總數(shù)無關(guān)。由于配準誤差的不斷傳播，因此簡單的序貫粗配準算法精度較差。

Turk和Levoy首先對物體自上而下掃描從而得到一個基準點云，該點云包含了物體各個方位角的信息。進而將在各個方位角上掃描得到的點云與該基準點云進行配準，從而實現(xiàn)多視點云的配準。該算法巧妙地將多視點云配準問題轉(zhuǎn)化為成對點云配準問題，但其對點云掃描視點有一定的約束，因而應(yīng)用范圍受限[35]。

Masuda等[36]采用 ICP 算法依次將一幅輸入點云與模型點云配準，并依據(jù)輸入點云上的點到配準后模型點云的誤差，將輸入點云上的部分點加入到模型點云中，不斷重復(fù)上述過程從而實現(xiàn)多幅點云的配準。

⑵多視點云同步粗配準算法

同步粗配準算法同時實現(xiàn)所有點云之間的配準，從而使得總的誤差最小化，并使配準誤差均勻分布到各幅點云上，避免了誤差的積累。這類算法需要解決兩個問題：一是獲得點云鄰接關(guān)系，即一幅點云與哪些點云相鄰；二是計算鄰接點云間的剛性變換關(guān)系。

Huber和Hebert[37]首先采用基于spin image 特征的成對點云配準算法將所有點云進行配準，從而獲得一個模型圖。圖的頂點為點云，圖的邊為兩個頂點對應(yīng)的點云間的剛性變換關(guān)系。進而在圖中計算具有姿態(tài)一致性和全局表面一致性的張樹，利用該張樹便可實現(xiàn)點云的多視配準。文獻[38-40]等采用類似的思路，分別采用基于LPHM、EM和SHOT 特征的算法實現(xiàn)兩兩點云對之間的配準，并構(gòu)建能獲得最大對應(yīng)點對數(shù)（或重疊面積）的張樹實現(xiàn)多視點云配準。由于這類算法需要對所有點云對進行配準，時間消耗較大，因而難以實現(xiàn)對大量點云的配準。

Mian等[41]提出了一種連接圖算法用于多視點云粗配準。該算法首先選擇一幅點云作為連接圖的根節(jié)點，并將其它點云與該節(jié)點上的點云進行配準，從而將能配準上的點云作為該節(jié)點的子節(jié)點加入到連接圖中。不斷重復(fù)上述過程， 直到所有點云均已加入到連接圖中， 或者沒有圖像能加入到連接圖為止，從而得到最終的連接圖。該算法采用tensor 特征實現(xiàn)成對點云的配準， 并對配準進行全局一致性驗證。此外，Mian等進一步提出了一種超圖算法。該算法首先采用前述連接圖算法構(gòu)建多個子圖，最后將子圖連接起來構(gòu)成超圖，從而實現(xiàn)多視點云粗配準。該算法的效率優(yōu)于張樹算法。

Ter Haar和Veltkamp[42]提出了一種快速的多視點云配準算法。給定一幅點云，首先找到與其對應(yīng)的左視點云、右視點云以及后視點云。進而對這四幅點云進行驗證，通過驗證的點云組合便可構(gòu)成物體的一個非完整模型，并對該模型進行姿態(tài)歸一化。最后，將得到的多幅非完整模型對齊從而獲得完整三維模型。該算法可在無先驗知識的情況下快速實現(xiàn)多幅點云的配準，其效率明顯優(yōu)于的張樹算法。該算法要求四幅點云構(gòu)成的組合應(yīng)能基本覆蓋物體的完整表面，否則難以實現(xiàn)精確的配準。此外，該算法要求點云均是在相似的姿態(tài)下獲得的。

⑶多視點云精配準算法

多視精配準算法的任務(wù)在于對多視粗配準結(jié)果做進一步優(yōu)化以減少所有點云之間總的配準誤差，并將配準誤差均勻分布到各幅點云上。

Stoddart和Hilton[43]將所有點云對應(yīng)點之間的歐氏距離加權(quán)平方和作為優(yōu)化函數(shù)，并采用梯度下降法迭代求解最優(yōu)的剛性變換關(guān)系。該算法將多視點云配準過程類比于多彈簧系統(tǒng)的平衡過程，將兩幅點云之間的對應(yīng)點集當做一個彈簧，采用剛體力學對彈簧系統(tǒng)進行分析， 從而在系統(tǒng)平衡點位置和方向求解過程中實現(xiàn)了點云變換關(guān)系最優(yōu)化。

Neugebauer[44]將成對點云配準算法擴展到多視點云配準。該算法將所有點云間點到切平面的平均距離作為優(yōu)化函數(shù)，采用最小二乘法對剛性變換關(guān)系進行迭代優(yōu)化，并采用多分辨率點云加速配準過程。在開始迭代時，采用分辨率最低的點云，隨著迭代次數(shù)的增加， 參與配準的點云分辨率不斷提高，從而在保證配準精度的同時提高運算效率。

Benjemaa和Schmitt[45]將ICP 算法從成對點云配準擴展到多視點云配準，采用單位四元數(shù)法實現(xiàn)多視點云的迭代配準。Williams 和Bennamoun[46]將文獻成對點云配準算法擴展到多視點云配準，其基本思路與文獻[45]類似，主要區(qū)別在于該算法采用正交矩陣而非單位四元數(shù)表示旋轉(zhuǎn)矩陣。Nishino和Ikeuchi[47]采用類似的思路，采用共軛梯度法及M-估計器提高算法效率和穩(wěn)健性，同時在尋找對應(yīng)點時加入激光反射強度信息以進一步提高算法精度。

Masuda[48]采用有向距離場（Signed Distance Field，SDF）表示點云，進而基于SDF采樣同時實現(xiàn)多視點云配準和融合。該算法首先將點云融合得到融合形狀，進而將點云與融合形狀配準。雖然開始時融合形狀并不精確，但通過迭代地融合和配準，可使最終的配準結(jié)果趨于準確。該算法的優(yōu)化函數(shù)與變換矩陣、融合形狀以及權(quán)值相關(guān)，點云融合通過計算每個采樣點上的 SDF 均值實現(xiàn)，點云配準通過尋找使得優(yōu)化函數(shù)最小化的變換矩陣實現(xiàn)。由于每幅點云均與融合形狀配準，因此配準過程不會帶來誤差積累。此外，由于每幅點云均為融合形狀的一部分，因此無需考慮點云之間的重疊區(qū)域大小。

激光SLAM

即時定位與地圖構(gòu)建 ( SimultaneousLocalization and Mapping，SLAM) 技術(shù)，是指把機器人放在未知的環(huán)境中，從一個未知位置開始移動對環(huán)境進行增量式地圖創(chuàng)建，同時利用創(chuàng)建的地圖進行自主定位和導航。SLAM技術(shù)可以使機器人實現(xiàn)真正的自主導航。

SLAM是一個龐大且復(fù)雜的工程問題，不同的傳感器通常對應(yīng)著不同的SLAM解決方案，例如，激光傳感器對應(yīng)著激光SLAM，相機類傳感器對應(yīng)著視覺SLAM。通過集成LiDAR掃描儀、IMU（inertial measurement unit）等傳感器可在掃描平臺移動過程中實時獲取位置、姿態(tài)信息以及場景的空間信息。基于SLAM技術(shù)的激光掃描可以高效完成室內(nèi)空間或室外小場景的三維點云數(shù)據(jù)獲取。本節(jié)主要介紹激光SLAM。

3.6.1 激光雷達SLAM定位技術(shù)

常見的移動機器人領(lǐng)域定位有位姿跟蹤和全局定位兩種。位姿跟蹤是指機器人的當前位姿根據(jù)上一時刻的位姿進行遞推計算，要求機器人的初始位姿必須已知。全局定位是指機器人被放在任何環(huán)境的任意位置，不必已知初始位姿，根據(jù)傳感器信息獲取機器人在全局坐標系中的位置。

⑴掃描匹配法

掃描匹配算法是一種位姿跟蹤定位方法。根據(jù)是否依賴于掃描的初始估計，分為半自動掃描匹配和自動掃描匹配。半自動掃描匹配在位姿初始估計的基礎(chǔ)上迭代地使匹配更準確，但缺點是當初始估計不準或沒有初始值時可能會導致匹配失敗；自動匹配方法直接求解掃描的位姿，通常匹配的結(jié)果精度不高。常用的掃描匹配方法有：迭代最近點( Iterative Closest Points，ICP) 算法，隨機抽樣一致( Random Sample Consensus，RANSAC) 算法等。

ICP 算法通過迭代的方式找出兩個點集的空間位置變化關(guān)系，使對應(yīng)點對的均方差最小化，實質(zhì)是一種基于最小二乘法的最優(yōu)匹配。這種采用最近鄰尋找對應(yīng)點的傳統(tǒng) ICP 方法，存在位姿中旋轉(zhuǎn)估計收斂慢的缺點。后來的研究者不斷將其改進，其中 IDC( Iterative Dual Correspondence) 和 MBICP( Metric-Based ICP) 兩種改進方法中分別引入新的點匹配策略進行了改進。PLICP ( ICP Based on Point-to-Line metric) 算法利用點到線段匹配的方法改善了迭代效率，但魯棒性變差，且更容易受到初始位姿誤差的影響。郭瑞提出了一種極坐標點匹配 規(guī)則 ( ICP Based on Polar Point Matching，PMICP) ，該規(guī)則綜合考慮了旋轉(zhuǎn)和平移的影響，并通過實驗數(shù)據(jù)驗證了該方法相對于傳統(tǒng) ICP 算法及其改進算法的快速性、準確性及魯棒性，可以確保局部地圖緊密一致，但是該方法不能避免匹配誤差的累計，所以不能保 證全局地圖一致，而且PMICP 算法依賴于掃描間相對位姿的初始估計，僅適用于單步定位，也未考慮環(huán)境中的動態(tài)變化。因此研究者又提出了從掃描數(shù)據(jù)中提取的特征完成匹配，即基于幾何統(tǒng)計特征的自動掃描匹配方法( Automatic Scan Matching based on Geometric Statistic Features，GSF-ASM) ，該方法不需要位姿的初始估計，而是在迭代過程中逐漸找到好的對應(yīng)點并逐漸校正位姿估計。此外，通過分割段特征和掃描點特征的匹配過程，過濾掉了環(huán)境變化的區(qū)域，更適應(yīng)動態(tài)變換的環(huán)境。

隨機抽樣一致算法通過反復(fù)在一組數(shù)據(jù)中選擇隨機子集的方法，利用迭代方式估計數(shù)學模型的參數(shù)，能夠有效應(yīng)對環(huán)境中的粗大誤差。隨機抽樣一致算法是一種不確定算法，對參數(shù)的選擇非常敏感，而且只是有一定的概率得到合理的解，因此為了提高精度需要以增加迭代次數(shù)為代價。Yang 等人提出了一種基于多模型的隨機抽樣一致算法，該算法中將模型分為靜態(tài)環(huán)境模型和動態(tài)目標模型等，用于在高動態(tài)環(huán)境中估計車輛的位置。

⑵擴展卡爾曼濾波( Extended Kalman Filter，EKF)定位

Smith 等人[1]在 1987 年提出基于卡爾曼濾波( Kalman Filter，KF) 的 SLAM 算法，卡爾曼濾波器是一種通過預(yù)測和校正過程對線性高斯系統(tǒng)的狀態(tài)進行估計的遞推算法，這是一種經(jīng)典的位姿跟蹤算法。

由于卡爾曼濾波只對線性高斯系統(tǒng)有效，應(yīng)用受到限制，研究者對其改進，提出擴展卡爾曼濾波器定位，應(yīng)用 EKF 對機器人位置和路標位置進行同時估計，EKF 定位適用于非線性高斯系統(tǒng)。EKF方法將機器人的位姿和環(huán)境特征地圖用一個高維狀態(tài)向量表示，對輸入和輸出方程利用泰勒級數(shù)展開形式進行局部線性化，然后對狀態(tài)向量的均值和最小方差進行估計。EKF 算法能有效處理不確定信息，但在每次迭代過程中計算各個特征間的協(xié)方差矩陣，增大了算法復(fù)雜度。EKF 方法基于機器人位姿的不確定性為單模高斯分布假設(shè)，假設(shè)傳感器數(shù)據(jù)在機器人位置上映射為高斯形狀的分布，但由于復(fù)雜的實際環(huán)境無法滿足這種強假設(shè)，所以仍需要不斷的改進。

另一種基于卡爾曼濾波的優(yōu)化方法是無損卡爾曼濾波器( Unscented Kalman Filter，UKF) 。UKF通過近似概率來實現(xiàn)非線性濾波，誤差比 EKF 更小。UKF 通過無跡變換( Unscented Transformation，UT) 將制定權(quán)值范圍內(nèi)的粒子集合帶入所采用的非線性函數(shù)，進一步得到其統(tǒng)計特性。這樣使粒子向后驗概率高的區(qū)域變動，粒子可以更好的近似狀態(tài)變量的后驗概率密度函數(shù)。當計算量在可控的范圍內(nèi)時，使用 UKF 得到的定位結(jié)果要比 EKF 得到的定位結(jié)果更好。

Shojaie 等人發(fā)現(xiàn)，迭代觀測更新過程能有效的減少線性化誤差，同時提高估計精度。由此提出了迭代擴展卡爾曼濾波器( Iterated EKF，IEKF) 、迭代無損卡爾曼濾波器 ( Iterated UKF，IUKF) 和迭代Sigma 點卡爾曼濾波器( Iterated Sigma Point Kalman Filter，ISPKF) 。

Thrun 等人提出一種基于協(xié)方差矩陣的逆來改正機器人位姿的方法。信息濾波 ( Information Filtering，IF) 是另一種針對卡爾曼濾波研究的改進。信息濾波是基于信息矩陣和信息向量的表示方法，本質(zhì)是應(yīng)用信息矩陣代替協(xié)方差矩陣表示不確定性，同時利用信息矩陣的稀疏性進行等時間間隔的執(zhí)行預(yù)測和更新，有效地減少計算量。

⑶馬爾可夫定位

馬爾可夫定位[2]將定位問題視為一個離散的馬爾可夫過程，是一種成功的全局定位方法。基于馬爾可夫假設(shè)，即假設(shè)機器人觀測獨立和運動獨立，F(xiàn)OX 等人最先提出了馬爾可夫定位方法，計算機器人在所在全局環(huán)境的概率分布。馬爾可夫過程中的每一個狀態(tài)對應(yīng)于機器人的每一個離散化的位姿，優(yōu)點是能夠處理多模和非高斯的概率分布，有效解決位姿跟蹤和全局定位問題。馬爾可夫定位通用性較強，可用于任何環(huán)境的定位，但是其效率較差。根據(jù)地圖表示方法的不同，馬爾可夫定位方法可分為拓撲馬爾可夫定位 ( Topological Markov Localization，TML ) 和柵格馬爾可夫定位 ( Grid Markov Localization，GML) 。馬爾可夫定位方法最早應(yīng)用在基于拓撲地圖的定位中。柵格馬爾可夫定位將連續(xù)的機器人位姿空間離散化為均勻的柵格，在柵格上完成數(shù)值積分。但由于計算量與狀態(tài)空間的尺寸和分辨率相關(guān)，這種方法計算量太大。

Burgard 使用八叉樹獲得狀態(tài)空間的變分辨率表示，使計算量和需要使用的內(nèi)存空間得到縮減，解決了來自固定分辨率的限制。吳慶祥等對馬爾可夫定位進行了仿真研究，使用電子羅盤解決對稱環(huán)境中的定位問題。Konolige 等人提出基于傳感器數(shù)據(jù)和地圖相關(guān)性的馬 爾可夫定位方法( Correlation-based Markov Localization，CBML) ，減少了定位過程中的計算量，提高了地圖更新的效率。Kosechka 和 Li 基于機器視覺建立室內(nèi)環(huán)境拓撲地圖。Gutmann 提出一種集成馬爾可夫定位和EKF 的定位方法 ML-EKF。

馬爾可夫是一種基于概率的全局狀態(tài)估計方法，通過傳感器對環(huán)境的測量和自身運動對機器人狀態(tài)進行遞歸的估計，以獲得最接近機器人真實位置的狀態(tài)。此外，馬爾可夫定位可解決在定位初期因初始位置未知和環(huán)境相似性造成的多峰值分布問題，并能從定位失敗中恢復(fù)。從運動控制的方面，馬爾可夫定位結(jié)果直接確定了機器人與環(huán)境的相對位置關(guān)系，例如距離，這也是大多數(shù)機器人系統(tǒng)的重要輸入信息。

⑷粒子濾波定位

Dellater[3]等人和Koller[4]等人提出了蒙特卡羅定位( Monte Carlo Localization，MCL) 方法，這是一種全局定位方法。蒙特卡羅定位是采樣/重要性重采樣 ( Sampling /Importance Re-sampling，SIR) 的一種版本，更為人們熟悉的叫法為粒子濾波( Particle Filter) 定位。粒子濾波的思想是用 N 個帶有權(quán)重的粒子來表示機器人位姿的后驗概率密度分布。根據(jù)系統(tǒng)狀態(tài)的條件概率分布在狀態(tài)空間構(gòu)造一組隨機粒子，根據(jù)觀測信息不斷調(diào)整每個粒子的位姿和權(quán)值，根據(jù)調(diào)整后的粒子信息來校正系統(tǒng)狀態(tài)先前的條件概率分布。

粒子濾波器不受線性高斯系統(tǒng)的限制，可應(yīng)用在任何非線性的隨機系統(tǒng)，但在全局定位中需要較多的粒子，而在位姿跟蹤中，即機器人的初始位姿已知時，只需要很少的粒子就能得到較好的定位效果。粒子濾波的最大問題是會出現(xiàn)由于重采樣過程而導致的粒子耗盡，這時粒子將沒有辦法逼近機器人位姿的真實后驗分布。Koller 和 Kwok 等在定位機器人的過程中自適應(yīng)地調(diào)整樣本數(shù)量來降低計算量，Thrun 等提出 Mixture-MCL 算法，改變樣本的產(chǎn)生方式，在樣本數(shù)量較小的時候，使其產(chǎn)生良好的定位效果。Saarinne 等提出一種基于正態(tài)分布變化的蒙特卡洛定位方法 ( Normal Distributions Transform Monte-Carlo Localization，NDT-MCL ) ，用正態(tài)分布變化作為地圖和傳感器數(shù)據(jù)的表示形式，提高了室內(nèi)機器人定位的精度和可重復(fù)性。

3.6.2 激光雷達SLAM地圖創(chuàng)建技術(shù)

地圖創(chuàng)建是指依靠移動機器人自身攜帶的傳感器，在移動過程中，根據(jù)自身傳感器不斷采集的位姿和環(huán)境信息數(shù)據(jù)，建立環(huán)境地圖的過程。首先機器人根據(jù)傳感器傳回的實時數(shù)據(jù)信息建立局部地圖，然后將局部地圖并入到全局地圖。每次得到的局部地圖既包含全局地圖已有的信息，也有全局地圖沒有的新的環(huán)境信息。在地圖創(chuàng)建過程中，不僅僅實現(xiàn)了對環(huán)境地圖的估計，同時還實現(xiàn)了對移動機器人位姿的估計，也再次說明了定位與建圖相輔相成的過程。地圖表示方法在前文已經(jīng)說明，根據(jù)不同的地圖更新方式，不同的地圖創(chuàng)建方法有其各自的優(yōu)缺點及其需要解決的主要問題。

⑴基于濾波的地圖創(chuàng)建算法

①基于EKF的地圖創(chuàng)建算法

EKF 方法是解決 SLAM 問題的一種經(jīng)典方法，依賴于運動模型和觀測模型的高斯噪 聲假設(shè)。Smith 等人利用 EKF 方法提出的數(shù)學公式至今仍在廣泛使用。EKF-SLAM 采用增廣的系統(tǒng)狀態(tài)空間，濾波過程包括狀態(tài)預(yù)測、狀態(tài)更新和地圖更新，對增廣的系統(tǒng)狀態(tài)和增廣的系統(tǒng)協(xié)方差矩陣進行遞歸的更新替換。其中地圖更新部分，主要是在完成系統(tǒng)狀態(tài)更新后，機器人把當前時刻的位姿和環(huán)境特征狀態(tài)存儲到環(huán)境地圖中。地圖更新主要包括: 匹配成功的特征點更新、新特征的加入、擴展地圖、錯誤特征的刪除。由于 EKF 的限制性，隨后許多研究者對該方法進行了改進。EKF-SLAM 能夠以在線的方式估計地圖的全后驗概率，能夠獲得最可能的地圖和機器人位姿，地圖中維護的不確定性在機器人利用地圖導航的時候有極大的好處。此外，此框架能夠使機器人位姿和所創(chuàng)建的環(huán)境地圖依概率 1 收斂到真實值，其收斂程度由機器人初始不確定性和傳感器觀測的不確定性決定。基于EKF-SLAM 框架，研究人員在不同機器人系統(tǒng)上完成了很多開發(fā)工作。但是由于 EKF-SLAM 框架存在算法一致性限制、數(shù)據(jù)關(guān)聯(lián)限制、計算成本高的限制，因此這種框架只適合建立小規(guī)模地圖。研究者們不斷提出改進，如分割更新、稀疏信息濾波和子地圖方法等，一些研究者將掃描匹配放進了傳統(tǒng)的 EKF-SLAM 的框架內(nèi)。

②基于RBPF的地圖創(chuàng)建算法

Rao-Blackwellized 粒子濾波器 (RBPF) 的基本思路是：在 RBPF 中每個粒子代表了一條可能的機器人估計和地圖，其關(guān)鍵任務(wù)是估計環(huán)境地圖 m 和機器人運動軌跡的聯(lián)合后驗分布。

RBPF 在特征地圖和柵格地圖的 SLAM 中應(yīng)用都比較成功。相對于 EKF-SLAM，ＲBPF 對數(shù)據(jù)關(guān)聯(lián)不敏感，容許錯誤的數(shù)據(jù)關(guān)聯(lián)。即當發(fā)生數(shù)據(jù)關(guān)聯(lián)錯誤時，ＲBPF SLAM 比EKF-SLAM 效果好。RBPF SLAM 系列算法的主要問題是解決由于重采樣造成的粒子多樣性喪失，即粒子耗盡問題。Hahnel 等將 RBPF 和掃描匹配相結(jié)合，通過設(shè)計掃描匹配造成的誤差模型，使掃描匹配最小化航跡推測誤差，降低需要的粒子數(shù)。Grisetti 等對 Hahnel的算法進一步改進，通過同時考慮機器人運動模型和當前觀測的建議分布及采用自適應(yīng)重采樣技術(shù)兩種方法來提高 RBPF性能。Blanco 等使用Kullback-Leibler Distance( KLD) 方法自適應(yīng)確定粒子數(shù)量。朱磊等人將人工魚群算法引入，使粒子分布在重采樣之前就更加接近真實情況，隨后利用定向重采樣方法使新產(chǎn)生的粒子更加接近真實運動。

③基于 Fast SLAM 方法的地圖創(chuàng)建算法

Montemerlo 等[5-6]基于Rao-Blackwellized，提出了Fast SLAM算法。其實質(zhì)是在RBPF-SLAM算法的框架內(nèi)，加入了 EKF 對環(huán)境的特征地圖標識。基本思想是把機器人 SLAM 系統(tǒng)分解為位姿估計和環(huán)境地圖估計兩部分。其中位姿估計采用粒子濾波算法估計機器人路徑，環(huán)境地圖則采用擴展卡爾曼濾波器更新。但上述方法粒子退化現(xiàn)象嚴重，為了解決這個問題 Montemerlo 等人提出了Fast SLAM 2. 0 算法[7]，進一步在重要性權(quán)值計算過程中引入高斯分布函數(shù)，有效的解決了粒子退化現(xiàn)象，提高了算法的精度和有效性。

⑵基于圖優(yōu)化方法的地圖創(chuàng)建算法

Graph SLAM 由 Lu 和Milois[8]在1997年提出。Graph中的節(jié)點表示位姿，節(jié)點之間的邊表示由航跡推測得到的位姿間的約束。Graph SLAM 算法包括前端構(gòu)圖和后端優(yōu)化兩部分。前端構(gòu)圖包括特征提取、數(shù)據(jù)關(guān)聯(lián)，后端圖優(yōu)化常用方法有最小二乘法、隨機梯度下降法、松弛法和基于流行的圖優(yōu)化等。Graph SLAM 將地圖創(chuàng)建視為最優(yōu)化問題，首先定義目標函數(shù)和約束條件，然后用數(shù)學規(guī)劃方法求解。Graph SLAM 是在采集完所有傳感器數(shù)據(jù)后，在建立好所有約束條件的前提下進行離線位姿估計和地圖創(chuàng)建的。目前較著名的 Graph SLAM 算法有：PTAM-SLAM、LSD-SLAM、ORB-SLAM、SVO-SLAM 和 RGBD-SLAM 等。

⑶基于其他SLAM技術(shù)的地圖創(chuàng)建算法

Thrun 提出一種基于概率方法的期望最大化( Expectation Maximization，EM ) 算法。期 望( Expectation) 是基于當前相似性最大地圖來估計機器人的位姿；最大化( Maximization) 是基于期望步驟所得到的機器人位姿來估計相似性最大地圖。基于 EM 的 SLAM 方法，將地圖創(chuàng)建轉(zhuǎn)化為概率約束條件下的最大相似度估計問題，然后再估計機器人的位姿，這種方法具有很好的地圖創(chuàng)建和定位性能。但是它是一種非增量的分批算法，且不能實時運行。后來 Thrun 等結(jié)合 EM 算法和增量算法，提出了一種新的實時性算法，該算法主要計算機器人位姿的全后驗概率來確定最相似的位姿，但是由于后驗概率計算的時間復(fù)雜度高，這種算法不能用于大規(guī)模環(huán)境。

3.6.3 激光SLAM展望

隨著人工智能技術(shù)的發(fā)展，將來會考慮將智能化方法引入激光 SLAM 過程，如神經(jīng)網(wǎng)絡(luò)模型、集元理論等在優(yōu)化、分類和可靠性方法都具有優(yōu)勢，這些算法的引入將會讓激光 SLAM 擁有更好的前景。另外，無人駕駛技術(shù)要求地圖高效、準確的反映動態(tài)環(huán)境信息，同時需要地圖與無人車之間擁有更好的交互性，而目前常見地圖表示方法不能滿足這樣的要求，因此研究更高效的適應(yīng)室外非結(jié)構(gòu)環(huán)境下的地圖表示方式，也是未來的發(fā)展方向。此外，基于多種傳感器融合技術(shù)和多車協(xié)作也是未來激光 SLAM 的發(fā)展方向。

隨著無人車技術(shù)的發(fā)展，目前激光 SLAM 技術(shù)是 SLAM 研究領(lǐng)域的熱點，也是無人車實現(xiàn)在 GPS信號失靈情況下進行自我定位的重要保證。由于激光的精度高、速度快及安全性高等特點，激光SLAM 在無人車、無人機和機器人自主導航等方面得到越來越廣泛的應(yīng)用。在無人車技術(shù)領(lǐng)域，隨著激光 SLAM 技術(shù)的不斷探索和發(fā)展，未來的激光SLAM 技術(shù)將會擴展到動態(tài)、三維的非結(jié)構(gòu)環(huán)境應(yīng)用中去，以實現(xiàn)無人車的不依靠 GPS 的全自主導航。

點云三維重建

表面重建算法的任務(wù)在于從多幅點云中構(gòu)建物體的統(tǒng)一曲面表示，下文將對幾種典型的表面重建算法進行評述。

3.7.1 網(wǎng)格縫合法

Boissanat[1]提出了一種用于實現(xiàn)三維點集 Delaunay三角化的算法，Rutishauser等[2]進一步利用該算法實現(xiàn)三維模型網(wǎng)格的生長。該算法通過在點云中尋找與現(xiàn)有模型網(wǎng)格邊緣較近且不重疊的點并將該點加入到模型網(wǎng)格中，從而實現(xiàn)模型網(wǎng)格的更新生長。

Turk 和Levoy[3]提出了一種網(wǎng)格縫合（mesh zippering）法。該算法將點云網(wǎng)格逐一進行縫合，從而得到反映物體完整三維形狀的粗模型，最后將所有點云網(wǎng)格與粗模型對齊并通過求均值以獲得更加精確的三維模型。對于配準的兩幅點云網(wǎng)格，首先沿著網(wǎng)格邊緣將重疊的區(qū)域刪除，進而對其中一幅點云網(wǎng)格的邊緣進行修剪以和另一幅網(wǎng)格良好吻合，并去除得到的小三角形。將所有點云網(wǎng)格縫合從而得到一個粗模型，進而在原始點云上尋找與粗模型上的點滿足幾何一致性的點，將這些點的坐標均值作為最終模型上相應(yīng)點的坐標。該算法可在掃描的同時對點云逐個進行配準，因而可以減少存儲量。當點云網(wǎng)格的配準不精確或噪聲較大時，該算法的性能較差。此外，該算法得到的模型在縫合處有較明顯的接縫[4]。文獻[5]亦采用類似的方法實現(xiàn)三維表面重建。

3.7.2 隱函數(shù)法

這類算法通常構(gòu)建一個隱函數(shù)對三維表面進行描述， 進而通過提取隱函數(shù)的等值面實現(xiàn)三維表面重建。

第一類方法是體素法。該方法在三維體數(shù)據(jù)中構(gòu)建一個隱函數(shù)，并采用移動立方體（Marching Cubes， MC）算法從體數(shù)據(jù)中重建出隱函數(shù)為 0 的表面。這類算法不同變種間的差異主要體現(xiàn)在隱式曲面定義和體數(shù)據(jù)組織上[6]，體素法在三維模型重建中得到了廣泛的應(yīng)用。Curless 和Levoy[7]首先對點云進行體素化，并將每幅點云轉(zhuǎn)化為有向距離函數(shù)。進而將每個體素中來自多幅點云的有向距離函數(shù)加權(quán)求和，從而得到該體素對應(yīng)的累積有向距離函數(shù)。接著，采用 MC 算法在體素柵格中提取累積有向距離函數(shù)等于 0 的等值面，從而實現(xiàn)三維模型重建。實驗結(jié)果表明，該算法可從大量點云中獲得無縫且細節(jié)豐富的高精度三維模型。文獻[8-10]采用類似的方法實現(xiàn)三維表面重建。Johnson 和Sing[6]則采用概率占據(jù)網(wǎng)格方法獲得體數(shù)據(jù)進而采用 MC 算法實現(xiàn)表面重建。該占據(jù)網(wǎng)格基于點的接近性以及傳感器誤差模型實現(xiàn)對三維表面的概率描述，因而可通過調(diào)整誤差模型使得算法適用于不同類型傳感器。

第二類方法是泊松法[11]。該算法為模型構(gòu)建一個示性函數(shù)，該示性函數(shù)在模型的內(nèi)部取值為1，在模型外部取值為 0。然后用示性函數(shù)的梯度場去逼近點云的法向量場，從而將示性函數(shù)的求解轉(zhuǎn)化為泊松函數(shù)的線性求解問題。采用最小二乘問題獲得示性函數(shù)的解后， 采用類似于 MC 算法的方法提取等值面從而實現(xiàn)三維表面的重建。該算法一次考慮所有采樣點，無需采用啟發(fā)式的空間分割或融合，因而對噪聲穩(wěn)健。其次，該算法的隱函數(shù)梯度在所有空間點上都進行了限制，生成的錯誤面片較少，因而對散亂點云穩(wěn)健。但該算法對無完整包絡(luò)的物體（如室外建筑物點云）重建效果較差。

3.7.3 轉(zhuǎn)球算法

Bernardini 等[12]提出了一種用于三維表面重建的轉(zhuǎn)球（ball-pivoting） 算法。該算法假設(shè)點云密集分布在整個曲面上從而使得半徑為 ρ 的球可以在該點云表面上滾動而不會掉到點云內(nèi)部。在每次滾動時，均有三個采樣點支撐住該球。該算法首先選擇三個合適的點構(gòu)成模型網(wǎng)格的種子三角形，該三角形的三個點均在半徑為 ρ 的球表面上。進而將該球繞三角形各邊旋轉(zhuǎn)直到接觸到新點為止。該旋轉(zhuǎn)邊與找到的新點一起便構(gòu)成了一個新三角形， 并將該三角形加入到網(wǎng)格中。重復(fù)上述過程直到所有可旋轉(zhuǎn)的邊均已完成測試，則算法轉(zhuǎn)而尋找下一個種子三角形，直到將所有點遍歷完為止。為應(yīng)對采樣密度不均勻的情形，該算法繼續(xù)采用一個半徑更大的球重復(fù)上述過程。該算法運算效率高，內(nèi)存消耗小，且對噪聲穩(wěn)健。算法具有與點數(shù)成線性關(guān)系的運算復(fù)雜度，其在運算過程中無需將點云的所有點同時導入到內(nèi)存中，且生成的網(wǎng)格亦可增量式的保存到計算機外存中，因此適用于大數(shù)據(jù)點云的網(wǎng)格化。

3.7.4 Power Crust算法

Amenta 等[13]提出了一種 power crust 算法用于三維表面重建。該算法首先由點云計算物體的中心軸，并以包含在物體內(nèi)部的最大球來表示物體，從而對中心軸進行逆變換獲得物體的表面。對于復(fù)雜的三維物體表面，難以準確地計算其中心軸，因此該算法采用點云的 Voronoi 圖和 Power 圖對物體表面和中軸進行分段線性估計，并用一組離散的極點球（polar ball） 近似模擬中軸。接著，將極點球劃分為物體內(nèi)部空間和物體外部空間兩類，最后將這兩部分極點球分離便得到輸出曲面。該算法有很強的理論性， 在實現(xiàn)中心軸估計的同時， 可獲得一個密封（watertight） 的三維網(wǎng)格，其對有銳利邊緣的物體、非均勻采樣的點云以及噪聲干擾亦有較好的效果。此外，該算法對輸入點云無特殊要求，且避免了孔洞填充等后處理操作。該算法的缺陷在于其運行速度較慢。

點云應(yīng)用

三維激光掃描已在許多重大工程和典型領(lǐng)域里得到了廣泛的應(yīng)用。從深空到地球表面，從全球范圍制圖到小區(qū)域監(jiān)測，從基礎(chǔ)科學研究到大眾服務(wù)，三維激光掃描都展現(xiàn)出了與眾不同的優(yōu)勢。基于點云的模型重建與目標識別在軍事和民用領(lǐng)域均有非常廣泛的應(yīng)用前景。

4.1 深空探測

深空探測的目的是促進人類對月球以及更遠天體的科學認識，而距離測量是其中的關(guān)鍵技術(shù)，許多國家采用激光測高儀進行星體地形表面的測量，如1971年美國阿波羅首次進行的月球形狀測量等[1]。

4.2 精確制導自動目標識別

采用激光雷達獲得的點云可有效實現(xiàn)高分辨率的目標成像，實現(xiàn)對小樹林和偽裝網(wǎng)遮擋下的目標檢測與識別。麻省理工學院（MIT）開展了“七巧板（JIGSAW）”項目等研究，進行了機載激光雷達對坦克和裝甲車等地面目標的檢測識別外場試驗[2-3]。該研究成果將成為美國陸軍未來戰(zhàn)場系統(tǒng)（Future Combat Systems，F(xiàn)CS）的一部分。瑞典國防研究局[4]、西班牙國防部[5]以及德國光子與模式識別研究所[6]等都開展了大量相關(guān)研究。

4.3 地球科學應(yīng)用研究

數(shù)字地面模型是各種地學過程研究的基礎(chǔ)，利用三維激光掃描系統(tǒng)觀測地表形態(tài)及其變化，已被廣泛應(yīng)用于各類地學應(yīng)用，例如：全球冰川物質(zhì)平衡[7-8]，地質(zhì)災(zāi)害區(qū)域時空變化監(jiān)測[9-10]，海岸線提取[11-12]，海底測繪及水下目標探測[13]等。

4.4 森林資源調(diào)查

及時準確了解林區(qū)的植被動態(tài)變化是林業(yè)科學研究的基礎(chǔ)。相比光學遙感，激光雷達能夠獲取植被冠層的三維結(jié)構(gòu)；地面激光雷達用于精細地獲取單株數(shù)木的垂直結(jié)構(gòu)[14]，機載激光雷達用于大范圍森林的蓄積量和生物量等生態(tài)參數(shù)的反演[15-17]，星載激光雷達還可以進行全球植被覆蓋及其生態(tài)參數(shù)制圖[18-19]。

4.5 城市形態(tài)分析

城市形態(tài)分析對城市規(guī)劃設(shè)計于管理具有重要意義，傳統(tǒng)手段難以監(jiān)測城市形態(tài)的垂直結(jié)構(gòu)及其演化，激光雷達可以快速獲取城市三維形態(tài)，為更精細的城市形態(tài)分析提供基礎(chǔ)，滿足基于城市形態(tài)的各種應(yīng)用需求，如基礎(chǔ)設(shè)施管理、太陽能潛力估計等[20-21]。

4.6 災(zāi)難救援與應(yīng)急響應(yīng)

采用激光雷達可獲得城市場景的真實三維模型，實現(xiàn)地物分類以及應(yīng)急響應(yīng)。麻省理工學院利用ALIRT機載激光雷達成像研究試驗平臺對太子港進行了三維成像，獲得30m分辨率的城市三維圖像，用于評估道路和橋梁狀況、分析水淹情況、選擇直升機降落場以及規(guī)劃難民安置等[22]。

4.7 無人系統(tǒng)自動導航

高精度地圖是實現(xiàn)自動化駕駛的關(guān)鍵因素。車載激光掃描系統(tǒng)可以高效、快速的獲取道路以及周邊高精度、高密度的三維幾何信息和紋理信息，為高精度地圖的自動化生產(chǎn)提供高質(zhì)量的數(shù)據(jù)支撐[23]。

點云傳感器被廣泛應(yīng)用于各種無人自主系統(tǒng)中。無論是谷歌無人車、普林斯頓大學無人車還是國防科大開發(fā)的無人車，均采用激光雷達或立體視覺獲取點云以生成車輛周圍環(huán)境的三維地圖，并結(jié)合其它傳感器實現(xiàn)車輛、建筑物、行人以及路牌等的檢測識別，最終完成態(tài)勢感知[24,25]。此外，德國弗萊堡大學、英國牛津大學等聯(lián)合開展了用于室外和室內(nèi)場所的機器人自動導航研究，該研究將點云傳感器作為其主要傳感器之一[26]。

4.8 文物三維數(shù)字化

文化遺產(chǎn)數(shù)字化保護是人類共同的歷史責任。三維激光掃描可以快速繪制物質(zhì)文化遺產(chǎn)的結(jié)構(gòu)圖和精細的三維模型，大幅提高文化遺產(chǎn)保護的工作效率，并豐富文化遺產(chǎn)成果表現(xiàn)形式[27-28]。

采用點云傳感器對文物進行掃描進而構(gòu)建三維模型有利于重要文物遺產(chǎn)的長期保存和修復(fù)。美國斯坦福大學與華盛頓大學合作開展了“數(shù)字化米開朗琪羅項目”，完成了對其雕刻作品的數(shù)字化三維模型重建[29]。德國NavVis公司完成了德意志博物館船舶展廳的三維全數(shù)字化建模并構(gòu)建了網(wǎng)上三維展示，國內(nèi)相關(guān)單位亦開展了對秦始皇兵馬俑等藝術(shù)作品三維數(shù)字化的探索。武漢市測繪研究院劉永鋒等[38]采用徠卡P40激光掃描儀獲取歷史建筑物內(nèi)外部結(jié)構(gòu)的三維點云數(shù)據(jù)，最終以CAD線劃圖的形式還原了建筑物原貌。

4.9 電力走廊安全巡檢

我國電力資源分布和經(jīng)濟建設(shè)中心不一致，高壓輸電線路區(qū)域地理環(huán)境復(fù)雜，傳統(tǒng)的人工巡檢手段難以適應(yīng)。機載三維激光掃描可以直接獲取電力線及其附屬設(shè)備的幾何形態(tài)參數(shù)[30]，為電力巡檢提供了新的手段[31]。

4.10 海島礁測繪

精確的海島礁基礎(chǔ)地理空間信息是海洋管理、經(jīng)濟開發(fā)、國防安全的重要依據(jù)，傳統(tǒng)測繪手段作業(yè)周期長、成本高，三維激光掃描可以直接觀測目標的三維空間信息，直接生產(chǎn)數(shù)字測繪產(chǎn)品，是島礁高精度測圖的重要手段。

4.11 隧道斷面提取與變形監(jiān)測

荷蘭代爾夫特理工大學 Lindenbergh R 等[32]于 2004 年使用徠卡公司生產(chǎn)的 Leica HDS3000 型三維激光掃描儀對一條約 100 米長的隧道進行了點云掃描及特征點及特征斷面截取，對數(shù)據(jù)精度進行了評定，證明了三維激光掃描技術(shù)在隧道變形監(jiān)測中的可行性。

荷蘭代爾夫特理工大學 Gosliga R V 等[33]在前人研究的基礎(chǔ)上于 2006 年引入圓的幾何模型及最小二乘算法，將三維激光掃描技術(shù)應(yīng)用于圓柱形隧道橫斷面的提取中。

近十余年來，三維激光掃描技術(shù)在隧道變形監(jiān)測中的應(yīng)用逐漸被國內(nèi)業(yè)內(nèi)學者所關(guān)注和認可。同濟大學周奇才[34]等于 2010 年將激光測距技術(shù)引入到地鐵隧道斷面變形監(jiān)測工作之中，激光測距技術(shù)是三維激光掃描技術(shù)的核心，故該項研究為國內(nèi)的三維激光掃描技術(shù)在隧道斷面提取中的研究打下了基礎(chǔ)。武漢大學簡驍[35]等于2011年提出利用三次埃爾米特差值的方法對隧道點云數(shù)據(jù)進行變形曲面擬合，進而比對多期隧道曲面數(shù)據(jù)而達到變形監(jiān)測的目的。武漢大學托雷[36]等于 2013 年對隧道中軸線及斷面提取進行了研究，引入 RANSAC 算法實現(xiàn)隧道連續(xù)斷面的截取并擬合變形曲線，實現(xiàn)了三維激光掃描點云數(shù)據(jù)在隧道變形監(jiān)測中的應(yīng)用。長安大學李雙[37]等于 2015 年提出了利用三維不變矩擬合隧道中軸線并利用二階矩擬合斷面橢圓特征的方法，實現(xiàn)了隧道斷面的連續(xù)提取。

此外，三維激光掃描被逐漸應(yīng)用于橋梁[39]、礦山邊坡[40]的變形監(jiān)測中。

三維點云的進展、挑戰(zhàn)與展望

5.1重要進展

近年來，國內(nèi)外學者在點云處理理論以及數(shù)據(jù)質(zhì)量改善、自動化融合、點云分類和目標提取、按需多層次表達等方法方面進行了深入研究，取得的主要進展如下。

5.1.1廣義點云模型理論方法

針對多源多平臺點云數(shù)據(jù)的融合難、目標提取難和三維自適應(yīng)表達難的嚴重缺陷，文獻[1]提出了廣義點云的科學概念與理論研究框架體系。廣義點云是指匯集激光掃描、攝影測量、眾源采集等多源多平臺空間數(shù)據(jù)，通過清洗、配準與集成，實現(xiàn)從多角度、視相關(guān)到全方位、視無關(guān)，建立以點云為基礎(chǔ)，基準統(tǒng)一，且數(shù)據(jù)、結(jié)構(gòu)、功能為一體的復(fù)合模型。

5.1.2三維點云數(shù)據(jù)質(zhì)量改善

點云數(shù)據(jù)質(zhì)量改善包括幾何改正和強度校正。一方面，由于測距系統(tǒng)、環(huán)境及定位定姿等因素的影響，點云的幾何位置存在誤差，且其分布存在不確定性。利用標定場、已知控制點進行點云幾何位置改正，能夠提高掃描點云的位置精度和可用性。另一方面，激光點云的反射強度一定程度上反映了地物的物理特性，對于地物的精細分類起到關(guān)鍵支撐作用，然而點云的反射強度不僅與地物表面的物理特性有關(guān)，還受到掃描距離、入射角度等因素的影響。因此，需要建立點云強度校正模型進行校正，以修正激光入射角度、地物距離激光掃描儀的距離等因素對點云反射強度的影響[2,3]。

5.1.3多源、多平臺三維點云融合

由于單一視角、單一平臺的觀測范圍有限且空間基準不一致，為了獲取目標區(qū)域全方位的空間信息，不僅需要進行站間/條帶間的點云融合，還需要進行多平臺（如機載、車載、地面站等）的點云融合，以彌補單一視角、單一平臺帶來的數(shù)據(jù)缺失，實現(xiàn)大范圍場景完整、精細的數(shù)字現(xiàn)實描述[4-6]。此外，由于激光點云及其強度信息對目標的刻畫能力有限，需要將激光點云和影像數(shù)據(jù)進行融合，使得點云不僅有高精度的三維坐標信息，也具有了更加豐富的光譜信息[7,8]。不同數(shù)據(jù)（如不同站點/條帶的激光點云、不同平臺激光點云、激光點云與影像）之間的融合，需要同名特征進行關(guān)聯(lián)。針對傳統(tǒng)人工配準法效率低、成本高的缺陷，國內(nèi)外學者研究基于幾何或紋理特征相關(guān)性的統(tǒng)計分析方法[9-10]，但是由于不同平臺、不同傳感器數(shù)據(jù)之間的成像機理、維數(shù)、尺度、精度、視角等各有不同，其普適性和穩(wěn)健性還存在問題，還需要突破以下瓶頸：魯棒、區(qū)分性強的同名特征提取，全局優(yōu)化配準模型的建立及抗差求解。

5.1.4三維點云的精細分類與目標提取

三維點云的精細分類是從雜亂無序的點云中識別與提取人工與自然地物要素的過程，是數(shù)字地面模型生成、復(fù)雜場景三維重建等后續(xù)應(yīng)用的基礎(chǔ)。然而，不同平臺激光點云分類關(guān)注的主題有所不同。機載激光點云分類主要關(guān)注大范圍地面、建筑物頂面、植被、道路等目標[11-16]，車載激光點云分類關(guān)注道路及兩側(cè)道路設(shè)施、植被、建筑物立面等目標[17-20]，而地面站激光點云分類則側(cè)重特定目標區(qū)域的精細化解譯[21]。其中，點云場景存在目標多樣、形態(tài)結(jié)構(gòu)復(fù)雜、目標遮擋和重疊以及空間密度差別迥異等現(xiàn)象，是三維點云自動精細分類的共同難題。

據(jù)此，國內(nèi)外許多學者進行了深入研究并取得了一定的進展，在特征計算基礎(chǔ)上，利用逐點分類方法[22-23]或分割聚類分類方法[17-19]對點云標識，并對目標進行提取。但是由于特征描述能力不足，分類和目標提取質(zhì)量無法滿足應(yīng)用需求，極大地限制了三維點云的使用價值。目前，模擬人腦的深度學習方法突破了傳統(tǒng)分類方法中過度依賴人工定義特征的困難，已在二維場景分類解譯方面表現(xiàn)出極大潛力[24]，但是在三維點云場景的精細分類方面，還面臨許多難題：海量三維數(shù)據(jù)集樣本庫的建立，適用于三維結(jié)構(gòu)特征學習的神經(jīng)網(wǎng)絡(luò)模型的構(gòu)建及其在大場景三維數(shù)據(jù)解譯中的應(yīng)用。綜上，顧及目標及其結(jié)構(gòu)的語義理解，三維目標多尺度全局與局部特征的學習，先驗知識或第三方輔助數(shù)據(jù)引導下的多目標分類與提取方法，是未來的重要研究方向。

5.1.5三維場景的按需多層次表達

在大范圍點云場景分類和目標提取后，目標點云依然離散無序且高度冗余，不能顯式地表達目標結(jié)構(gòu)以及結(jié)構(gòu)之間的空間拓撲關(guān)系，難以有效滿足三維場景的應(yīng)用需求。因此，需要通過場景三維表達，將離散無序的點云轉(zhuǎn)換成具有拓撲關(guān)系的幾何基元組合模型，常用的有數(shù)據(jù)驅(qū)動和模型驅(qū)動兩類方法[25-26]，其中存在的主要問題和挑戰(zhàn)包括：三維模型的自動修復(fù)，以克服局部數(shù)據(jù)缺失對模型不完整的影響[27]；形狀、結(jié)構(gòu)復(fù)雜地物目標的自動化穩(wěn)健重構(gòu)；從可視化為主的三維重建發(fā)展到可計算分析為核心的三維重建，以提高結(jié)果的可用性和好用性。此外，不同的應(yīng)用主題對場景內(nèi)不同類型目標的細節(jié)層次要求不同[28]，場景三維表達需要加強各類三維目標自適應(yīng)的多尺度三維重建方法[29-30]，建立語義與結(jié)構(gòu)正確映射的場景—目標—要素多級表達模型。

5.2面臨挑戰(zhàn)

近年來，星、空、地掃描以及便攜式泛在傳感器（如：RGB-D 深度相機）廣泛運用，不但提高了點云獲取的時效性、顆粒度和覆蓋面，而且?guī)砹它c云的多時相、流形（streaming）和多樣屬性的新特性，從而產(chǎn)生了多維點云數(shù)據(jù)。多維點云本質(zhì)上是對物理世界中地理對象/現(xiàn)象的三維幾何、物理乃至生化特性的多維密集采樣，其不但記錄了地物的三維空間結(jié)構(gòu)特征，同時也記錄了地物目標的物理特性（如波形、反射強度等）。深入挖掘多維點云的內(nèi)在特征對提升多維點云處理的智能化程度，揭示復(fù)雜動態(tài)三維場景的變化規(guī)律至關(guān)重要。盡管點云處理方面已經(jīng)取得了較好的研究成果，但是多維點云的智能化處理方面仍然面臨如下的巨大挑戰(zhàn)：

5.2.1多維點云幾何與屬性協(xié)同的尺度轉(zhuǎn)換

探索不同平臺獲取點云的誤差分布規(guī)律，建立比例尺依賴的特征點質(zhì)量評估模型；研究融合點云物理特性的特征點簇聚合與分層方法；建立基于特征分層的多維點云多尺度整合方法，實現(xiàn)多維點云的時空基準自動統(tǒng)一。

5.2.2多維點云變化發(fā)現(xiàn)與分類

建立統(tǒng)一時空參考框架下多維點云的變化發(fā)現(xiàn)與提取方法，研究基于時間窗口的多維點云與地物三維模型的關(guān)聯(lián)方法，提取地物空間要素的幾何和屬性變化，研究面向地物空間結(jié)構(gòu)變化的可視化分析方法，為揭示空間要素的變化規(guī)律提供科學工具。

5.2.3復(fù)雜三維動態(tài)場景的精準理解

基于機器學習、人工智能等先進理論方法探索多維點云結(jié)構(gòu)化建模與分析的理論與方法，研究建立復(fù)雜三維動態(tài)場景中多態(tài)目標的準確定位、分類以及語義化模型的建立，建立面向多維點云的三維動態(tài)場景中各類要素的特征描述、分類與建模方法，架設(shè)多維點云與地理計 算模型的橋梁。

上述關(guān)鍵挑戰(zhàn)問題的突破將形成完備的廣義點云全三維（覆蓋全、要素全、關(guān)系全）建模的理論與方法體系，從而實現(xiàn)點云處理由“靜態(tài)、可視、量算”到“動態(tài)、模擬、分析”的跨越。

5.3 發(fā)展趨勢與展望

近年來，傳感器、通信和定位定姿技術(shù)的發(fā)展，人工智能、深度學習、虛擬/增強現(xiàn)實等領(lǐng)域先進技術(shù)的重要進展有力推動了數(shù)字現(xiàn)實（digital reality）時代的來臨。激光掃描與點云智能化處理將順應(yīng)數(shù)字現(xiàn)實時代的需求朝以下幾個方面發(fā)展。

⑴三維激光掃描裝備將由現(xiàn)在的單波形、多波形走向單光子乃至量子雷達，在數(shù)據(jù)的采集方面由現(xiàn)在已幾何數(shù)據(jù)為主走向幾何、物理，乃至生化特性的集成化采集。

⑵三維激光掃描的搭載平臺也將以單一平臺為主轉(zhuǎn)變?yōu)橐远嘣椿⒈姲綖橹鞯目盏厝嵝云脚_，從而對目標進行全方位數(shù)據(jù)獲取，當前國家重點研發(fā)計劃重點專項項目：國產(chǎn)空地全息三維遙感系統(tǒng)及產(chǎn)業(yè)化已支持相關(guān)研究。

⑶點云的特征描述、語義理解、關(guān)系表達、目標語義模型、多維可視化等關(guān)鍵問題將在人工智能、深度學習等先進技術(shù)的驅(qū)動下朝著自動化、智能化的方向快速發(fā)展，點云將成為測繪地理信息中繼傳統(tǒng)矢量模型、柵格模型之后的一類新型模型，將有力提升地物目標認知與提取自動化程度和知識化服務(wù)的能力。

⑷虛擬/增強現(xiàn)實、互/物聯(lián)網(wǎng)+的發(fā)展將促使三維激光掃描產(chǎn)品由專業(yè)化應(yīng)用擴展到大眾化、消費級應(yīng)用，滿足網(wǎng)絡(luò)化多維動態(tài)地理信息服務(wù)的需求。