李建微，占家旺

福州大學(xué)物理與信息工程學(xué)院，福州 350116

0 引 言

3維數(shù)據(jù)是一種現(xiàn)實物理世界的重要表達方式，有多種表現(xiàn)形式，包括深度圖像、多邊形網(wǎng)格和點云(Guo等，2014)等。3維點云數(shù)據(jù)獲取設(shè)備如激光雷達等產(chǎn)品的成熟和普及以及計算機運算能力的提升，使點云數(shù)據(jù)得到了廣泛應(yīng)用。點云配準技術(shù)是點云數(shù)據(jù)處理中一個極具挑戰(zhàn)性的研究方向，因為點云是一種非結(jié)構(gòu)化的數(shù)據(jù)形式，存在遮擋和噪聲(Duan等，2021)以及較大的數(shù)據(jù)量(Sultani和Ghani，2015)，并且需要精確快速地完成。本文主要研究點云的剛性配準，即可以只通過平移和旋轉(zhuǎn)操作將點云配準，而沒有縮放和變形。點云配準技術(shù)是多個領(lǐng)域的重要技術(shù)，包括移動機器人的同步定位和制圖(simultaneous localization and mapping，SLAM)、自動駕駛中使用的高精度地圖構(gòu)建和環(huán)境感知、森林結(jié)構(gòu)參數(shù)評估、自動城市建模、增強現(xiàn)實(augmented reality，AR)的景物檢測、醫(yī)學(xué)檢測的圖像合成、施工監(jiān)控和竣工建模等眾多應(yīng)用場景。這些應(yīng)用場景往往需要很高的配準精度，有些則需要很快的配準速度。精度高且速度快的配準算法能夠極大地提高這些應(yīng)用的性能。

點云配準算法在20世紀70年代就已有研究。ICP(iterative closest point)是一種最經(jīng)典的點云配準算法(Besl和Mckay,1992)，通過迭代對應(yīng)點搜尋和最小化點對整體距離以估計變換矩陣。因為是非凸的，所以容易陷入局部極小值。當點云配準需要較大的旋轉(zhuǎn)平移時，ICP往往無法得到正確的結(jié)果。NDT(normal distributions transform)是另一種經(jīng)典的精配準方法，通過最大化源點在目標點體素化后計算出的正態(tài)分布的概率密度上的得分進行配準(Magnusson等，2007)。ICP、NDT算法及其變體需要點云已經(jīng)大致對齊，或者是有IMU(inertial measurement unit)、GNSS(global navigation satellite system)、里程計等先驗位姿，否則需要粗配準為其提供一個初始位姿(Ilci和Toth，2020)。簡單的點與點的對應(yīng)不具有魯棒性，所以接下來很多工作都致力于尋找更加魯棒的對應(yīng)，如點對面、面對面和特征對特征。通過這些對應(yīng)關(guān)系估計配準參數(shù)，這些對應(yīng)關(guān)系提高了點云配準的正確率，降低了對正確初始位姿的依賴。具有更多信息的對應(yīng)關(guān)系可以用于點云粗配準，典型的粗配準由特征檢測、特征描述和特征匹配等構(gòu)成(Bueno等，2017)。特征檢測減少總的點數(shù)，保留獨特性高的部分；特征描述旨在將高維的特征信息轉(zhuǎn)換為低維度但卻依然易于分辨和對比的描述子；特征匹配尋找特征之間的對應(yīng)關(guān)系，一旦建立對應(yīng)關(guān)系配準問題就變成了一個凸問題，變換估計就變得更容易。另一種粗配準的方法基于全等四點集(4-points congruent sets)(Aiger等，2008)，在剛性變換下，部分點的變換也是全部點的變換，通過驗證多組全等集得到最佳變換。傳統(tǒng)的非學(xué)習(xí)點云配準方法對硬件要求低、易于實施、可解釋性強且不需要耗時的訓(xùn)練過程，但是卻存在容易陷入局部極小值或通用性不好的問題，使用手工特征區(qū)分對應(yīng)關(guān)系，受設(shè)計者經(jīng)驗和參數(shù)調(diào)整能力的影響很大。另外粗配準方法往往都比較耗時，在一些實時應(yīng)用中可能會遇到瓶頸。

近年來，深度學(xué)習(xí)取得了很多進展，越來越多的算法都通過深度學(xué)習(xí)獲得了性能上的進步，深度學(xué)習(xí)在點云配準任務(wù)中也得到了廣泛應(yīng)用(Liu等，2019)。很多算法都獲得了速度提升，并且表現(xiàn)出對噪聲、低重疊以及遮擋的魯棒性。基于學(xué)習(xí)的方法在性能提高上表現(xiàn)出的潛力使其成為當前點云配準領(lǐng)域熱門的研究方向。在點云上進行學(xué)習(xí)需要克服點云的噪聲和遮擋，更大的挑戰(zhàn)在于點云的非結(jié)構(gòu)化、無序性和不規(guī)則性，這就不利于將成熟的結(jié)構(gòu)化的圖像方法推廣到點云上。于是，基于體素的方法、基于多視圖的方法和在原始點云直接進行學(xué)習(xí)的方法得以用于點云上的學(xué)習(xí)(Bello等，2020)。基于學(xué)習(xí)的點云配準與非學(xué)習(xí)的方法有很多共通之處，很多基于學(xué)習(xí)的點云配準算法都是在非學(xué)習(xí)的配準算法的基礎(chǔ)上，用網(wǎng)絡(luò)代替其中的一部分，或是完全由網(wǎng)絡(luò)組成端到端的算法，所以基于學(xué)習(xí)的方法往往是非學(xué)習(xí)方法和深度學(xué)習(xí)理念的結(jié)合。多數(shù)基于學(xué)習(xí)的點云配準方法是基于特征的，但是學(xué)習(xí)到的特征對比人工設(shè)計的特征具有更好的通用性、魯棒性和描述能力?；趯W(xué)習(xí)的方法還能夠?qū)W到更高級、更多層次的描述符，對特征選取和特征表示以及點密度和測量角度差異更加魯棒(Dong等，2020)。通過GPU(graphics processing unit)的并行計算能力，基于學(xué)習(xí)的點云配準方法具有速度上的優(yōu)勢，特別是在粗配準方面有很大優(yōu)勢。但是基于學(xué)習(xí)的方法對比非學(xué)習(xí)方法往往需要更多的計算資源，有實時要求但計算資源很有限時，不適合使用基于學(xué)習(xí)的方法。

在點云配準方面已有綜述性工作，Pomerleau等人(2015)總結(jié)了ICP及其改進算法；Díez等人(2015)專注于點云的非學(xué)習(xí)粗配準方法；Cheng等人(2018)將點云配準的方法分為精配準方法和粗配準方法，但是都沒有涉及基于學(xué)習(xí)的方法；Dong等人(2020)也將點云配準的方法分為精配準方法和粗配準方法，并且涉及了一些基于學(xué)習(xí)的粗配準方法，但是篇幅較小。目前還沒有檢索到中文的點云配準方法的綜述總結(jié)基于學(xué)習(xí)的方法。本文將點云配準方法分為非學(xué)習(xí)的方法和基于學(xué)習(xí)的方法，并將非學(xué)習(xí)方法分為經(jīng)典方法和基于特征的方法，將基于學(xué)習(xí)的方法分為結(jié)合非學(xué)習(xí)方法的部分學(xué)習(xí)方法和直接的端到端學(xué)習(xí)方法。目前，點云配準技術(shù)仍然很受重視,并且在繼續(xù)快速發(fā)展，并不斷取得新的進步。

1 非學(xué)習(xí)的點云配準方法

1.1 經(jīng)典點云配準方法

1.1.1 ICP及其變體

標準 ICP 算法，即點對點—迭代最近點(point to point iterative closest point，P2P-ICP)算法的數(shù)學(xué)模型為：給定源點云P={p1，p2，p3，…，pm}?R3和一個與之對應(yīng)的目標點云Q={q1，q2，q3，…，qn}?R3，其中m和n分別為源點云和目標點云的點的個數(shù)。

(1)

(2)

求出的T*可以再代入式(1)，通過式(1)和式(2)迭代尋找最近點，并通過最小化點間歐氏距離平方和估計變換矩陣，當達到要求的誤差或超過設(shè)置的迭代最高次數(shù)則終止迭代，通過將每一次的T*施以矩陣的乘法獲得最終的變換矩陣。這種方法在面對點云巨大、具有大量噪聲和離群值、點云密度變化和點云結(jié)構(gòu)復(fù)雜時沒有良好的表現(xiàn)。研究者提出了許多ICP的變體以應(yīng)對這些挑戰(zhàn)。

一些方法致力于提高ICP方法的精度。Chen和Medioni(1992)將點對點擴展到點對面(point to plane,ICP)，通過計算法線得到一個切平面，通過最小化點到切平面的距離達到配準效果，這使其對點云的噪聲有更好的適應(yīng)性。Segal等人(2009)提出了一種面對面(generalized iterative closest point，GICP)的方法，將迭代最近點和點對面ICP算法結(jié)合到一個概率框架中，將點對點和點對面方法都變成了它的一種特殊情況。該方法在兩個點上建立高斯分布，這樣對于經(jīng)過任意的剛體變換T后，兩個點間的距離就有了一種高斯分布，那么最優(yōu)的變換矩陣就是使對應(yīng)點間經(jīng)此變換后距離的高斯概率最大的變換矩陣。此方法對錯誤對應(yīng)具有魯棒性，并且還可以允許添加離群項、測量噪聲和其他概率技術(shù)來增加魯棒性。一些方法致力于擴大ICP方法的收斂范圍。Gold等人(1998)提出RPM(robust point matching)，通過將點對應(yīng)關(guān)系從一對一變成一對多，并通過確定性退火在每次迭代時逐漸“強化”分配。其中退火參數(shù)較小時對應(yīng)更平均，這有助于避免陷入局部最小值，而β增加時更趨向于只對應(yīng)某一個。Yang等人(2013)提出go-ICP算法，通過分支定界法，在SE(3)空間內(nèi)，使用八叉樹數(shù)據(jù)結(jié)構(gòu)將初始空間細分為較小的子空間，用分支定界的方法去除不佳的空間，繼續(xù)細分滿足門限條件的空間，從而找到全局最優(yōu)變換。該方法盡管解決了局部極小值問題，但對初始化仍然很敏感。Liu等人(2020)提出MVGICP(multi-scale voxelized generalized iterative closest point)，在迭代的大尺度到小尺度的體素上計算體素內(nèi)的均值和方差，然后將其代入GICP模型中，并利用高斯牛頓方法得到變換矩陣，然后繼續(xù)以更小的體素進行迭代。較大的體素可以更加全局地粗略配準點云，而較小的體素可以進一步提高配準結(jié)果的精度。并且也不需要最鄰近搜索，因此可以顯著提高計算效率。另一些方法致力于提高ICP的效率，Simon等人(1995)提出一種基于解耦加速的ICP算法，通過kd-tree以及根據(jù)上一次最近點搜尋的結(jié)果推斷此次可能的位置，通過最近點高速緩存，加快搜尋。通過解耦，盡可能獨立地加速平移和旋轉(zhuǎn)，而不會產(chǎn)生沖突。Pavlov等人(2018)將Anderson加速引入ICP算法(Anderson acceleration iterative closest point,AA-ICP)，利用Anderson算法對不動點問題的加速能力，還提出了兩種啟發(fā)性的策略以應(yīng)對Anderson算法的不穩(wěn)定性的問題，提高了配準的收斂速度和魯棒性。ICP算法也可以與特征相結(jié)合，Ren和Zhou(2015)用容易獲得的拐點特征代替點，減少了點的數(shù)量，在大規(guī)模數(shù)據(jù)點云上顯示出優(yōu)勢。

ICP是最簡單常用的配準算法，ICP及其多數(shù)變體都依賴于良好的初始位姿，以防止陷入局部最優(yōu)。很多算法減輕了這種依賴，但是卻不能徹底解決這種依賴。由于對應(yīng)匹配的配準策略，不正確的對應(yīng)對配準影響很大但是卻非常普遍，從而限制了配準的準確性。

1.1.2 NDT及其變體

NDT點云配準方法是另一種經(jīng)典的點云配準方法，是一種利用數(shù)學(xué)分布性質(zhì)刻畫點云數(shù)據(jù)并用其構(gòu)造優(yōu)化目標的方法(Magnusson等, 2007)。用于點云配準的3D NDT是受Biber和Strasser(2003)提出的2D NDT算法的啟發(fā)，并將其擴展到3D。給定源點云P={p1，p2，p3，…，pm}?R3和目標點云Q={q1，q2，q3，…，qn}?R3，經(jīng)典的NDT算法對目標點云進行體素化，然后計算體素內(nèi)的點的均值μ和方差Σ，具體為

(3)

(4)

這樣可以得到一個描述體素內(nèi)點分布情況的概率密度函數(shù)，并且不需要在每次迭代時重新計算。具體為

(5)

最佳的變換矩陣使源點云在其對應(yīng)的概率密度函數(shù)中的整體似然達到最大，具體為

(6)

將最佳的變換作用于源點云，迭代式(6)計算新的最佳變換。NDT方法對體素的劃分敏感，可以通過改變體素的大小，對收斂精度和速度進行調(diào)整。但是因為其成本函數(shù)會由于點跨越體素邊界而不再連續(xù)，因此優(yōu)化收斂性較差。Das和Waslander(2012)提出一種多尺度K均值NDT(multi-scale K-means normal distributions transform，MSKM-NDT)，根據(jù)K均值聚類劃分點云，并且在多個尺度上進行優(yōu)化，K均值聚類解決了NDT算法中出現(xiàn)的成本函數(shù)不連續(xù)問題。多尺度優(yōu)化有利于跨越局部最小值，這也改善了這種方法的收斂性。Lu等人(2015)提出一種體素大小可變的方法，在將大體素分割為幾個小的體素的過程中考慮體素內(nèi)點的個數(shù)，點稀疏時體素分大些，點密集時體素分小些。這樣可以將稀疏點聚集為一個大的體素，將密集的點分散為多個小體素，從而消除了固定大小的體素之間的點的數(shù)量差異很大的問題，避免了某些稀疏點無法使用的缺陷。Das和Waslander(2014)提出一種分段區(qū)域生長NDT算法(segmented region growing normal distributions transform，SRG-NDT)，使用基于高斯過程的分割算法從掃描中刪除地平面，然后應(yīng)用效率高的區(qū)域增長算法對其余點進行聚類，不再是按體素進行概率密度函數(shù)的計算，而是從聚類的結(jié)果中計算概率密度函數(shù)，從而得到比體素方法少得多的概率分布來對環(huán)境進行精確建模，同樣也克服了成本函數(shù)的不連續(xù)性，并且由于除去了地面點，從而使速度得到明顯提高。Zaganidis等人(2017)利用點云的平滑度將點云分區(qū)，丟棄掉未劃分進分區(qū)的大量點，不在全部點云而是在相同類型的分區(qū)上進行NDT，這既減少了點的數(shù)目又為配準剔除了一些干擾，不僅加快了配準速度，也提高了魯棒性。

與ICP類算法一樣，NDT算法也是一種可以達到精配準的方法，并且因其不需要顯式計算最近鄰近對應(yīng)點，所以NDT算法比ICP算法更快。但是NDT及其變體依然需要良好的初始位姿，否則也容易陷入局部極值。

1.1.3 4PCS及其變體

4PCS算法是一種經(jīng)典的點云粗配準方法，該方法是基于RANSAC(random sample consensus)算法的理念設(shè)計的(Aiger等, 2008)。給定源點云P={p1，p2，p3，…，pm}?R3和目標點云Q={q1，q2，q3，…，qn}?R3。將點云配準問題變成在Q上尋找所有大致與P中選取的基共面四點集相近似的共面四點集，然后驗證由這些相似共面四點集計算得出的變換矩陣，選取最佳的變換作為最終結(jié)果。具體步驟為：1)在P中選取基共面四點集，計算4點構(gòu)成兩個相交直線的交點并記為e，兩條線段的長度記為d1和d2，并分別計算兩條直線被交點分成的兩段的長度的比值，記為r1和r2；2)在Q中分別尋找所有距離約等于d1或d2的點對，并分別記為R1和R2。根據(jù)r1計算R1中點對可能的交點位置，用交點建立范圍樹結(jié)構(gòu)(range tree structure，RS)。根據(jù)r2計算R2中點對可能的交點位置，并對每個交點在范圍樹結(jié)構(gòu)中尋找大致接近的交點，由此可以確定一個大致一致的共面四點集；3)為每一對一致的共面四點集計算變換矩陣并作用于P，然后計算P中的點到Q中點的距離小于閾值δ的點數(shù)，最佳變換是使最多點靠近的變換。

4PCS算法是一種粗配準方法，不需要提供初始位姿，而能夠為精配準方法提供一個良好的初始位姿。4PCS算法可以應(yīng)對點云的噪聲和遮擋，即使對少量異常值“污染”的點云數(shù)據(jù)，也無需進行過濾和去噪，在大多數(shù)情況中都可以有不錯的表現(xiàn)。4PCS算法的主要問題在于比較慢，提取相似集和驗證變換都比較耗時，4PCS在數(shù)據(jù)點數(shù)量上具有二次時間復(fù)雜性。

很多研究致力于提高4PCS算法的速度。Mellado等人(2014)提出super 4PCS算法。在4PCS算法中判斷是否是大致一致共面四點集，只根據(jù)兩條直線被交點分成的兩段的長度的比值，而沒有考慮兩條線之間的夾角，super 4PCS考慮了這一點，這減少了候選大致一致共面四點集的數(shù)量。對于提取所有距離約等于d1或d2的點對和夾角匹配，super 4PCS分別借用3D球體與點之間的經(jīng)典入射問題和報告位于圓上的所有點在單位球上的入射問題的思路，將搜尋速度大幅提高，在數(shù)據(jù)點數(shù)量上達到一次時間復(fù)雜性。Huang等人(2017)提出了volumetric 4PCS，將4個共面點擴展為非共面點以進行全局配準，之所以使用非共面4點是因為當形狀接近于平面時，還使用共面點會導(dǎo)致太多點滿足與基共面四點集相似，找到這些點集耗時，驗證這些點集也很耗時。volumetric 4PCS在super 4PCS的基礎(chǔ)上進行改進，繼承了其快速的優(yōu)勢。因為是非共面四點集，所以需要6個點間距離來描述基四點集的信息，所以需要找大致滿足6個點間距離的點集合然后驗證，得到最佳變換。Mohamad等人(2014)提出允許4PCS中本應(yīng)該相交的兩條線落在不同的平面上，允許兩個線段之間有任意的距離和任意的分離度，增加分離度的方法使搜索空間有了指數(shù)級的減少，使運行效率比4PCS有了一個很大提高。Fotsing等人(2020)將在完整點云上進行的4PCS改進為將從源點云和目標點云劃分出的平面對之間的4PCS，大幅減少了數(shù)據(jù)量的大小和執(zhí)行時間。在驗證變換時，不同于4PCS使用最大公共點集(large common plansets，LCP)衡量配準質(zhì)量，該算法使用最大的公共平面集代替，這使驗證速度更快，并對噪聲更魯棒。Xu等人(2019)提出voxel 4PCS，將點云體素化用以提取平面，再將共面平面融合，用平面代替點，用角度關(guān)系代替長度關(guān)系作為在剛性變換中不變的關(guān)系判別特征的相似性，實現(xiàn)了更高的魯棒性和速度。4PCS算法的另一種變體是將特征引入4PCS算法。

4PCS算法及其變體作為一種粗配準方法，具有對噪聲、遮擋和異常值的魯棒性，不需要初始位姿。其主要的限制還是在于尋找?guī)缀涡螤钕嗨频狞c集，驗證由這些點集確定的變換矩陣都需要比較大的計算量，導(dǎo)致計算時間較長，雖然其變體在一定程度上加快了速度，但仍無法滿足一些實時性要求高的應(yīng)用。

表1總結(jié)了經(jīng)典的ICP、NDT、4PCS算法及其變體的典型算法和優(yōu)缺點。

表1 經(jīng)典點云配準算法Table 1 Classic point cloud registration algorithm

1.2 基于特征的點云配準方法

基于特征的方法沒有用點云中全部的點進行配準，而是只選取點云中比較特殊的一部分進行配準，這種方法可以不需要提供初始位姿，并且具有魯棒性。一個典型的基于特征的點云配準方法包括特征檢測、特征描述和特征匹配。其中，特征檢測使要處理的數(shù)據(jù)量變少，從而加快配準過程；特征描述將不容易進行對比的特征信息變換成容易對比的信息，從而有利于關(guān)鍵點的匹配；特征匹配用于找到源點云和目標點云的特征之間的正確對應(yīng)關(guān)系，從而計算出變換矩陣(Díez等, 2015)。典型的基于特征的點云配準方法的流程圖如圖1所示，但是并不是所有的方法都是這樣的結(jié)構(gòu)，點云預(yù)處理和特征描述有時不是必要的，而特征匹配和變換估計可能需要多次執(zhí)行。

圖1 典型的基于特征的點云配準方法流程Fig.1 Typical feature-based point cloud registration method process

配準方法與采集設(shè)備和采集方法有著較大的相關(guān)性，除了空間位置，一些點云采集設(shè)備還能提供其他信息。如一些激光雷達可以提供反射強度信息，RGBD(red, green, blue and depth)相機能夠提供顏色信息，得益于這些增加的信息，為基于特征的點云配準方法提供了更多的思路和方向。如果點云只包含位置信息，那么對于其特征的描述最常用的是點特征、線特征和面特征。通過這些特征，大多數(shù)情況下能夠完成配準任務(wù)，但是當物體對稱性很強或者想提升配準的性能時，往往需要其他特征的輔助，紋理特征是主要的輔助特征的形式。在點云采集設(shè)備中，無論是反射強度還是顏色，都可以將其視為紋理特征，并且能夠找到其與點的空間位置的對應(yīng)關(guān)系，這是可以方便地使用紋理特征的基礎(chǔ)。紋理特征可以用于確定特征對應(yīng)關(guān)系，空間位置負責計算變換矩陣。

1.2.1 特征檢測方法

對所有的點求描述符是不合適的，一方面這會極大地加重計算負擔，另一方面這對配準也沒有很大的幫助，因為點云中具有很多相似的點云部分，這會導(dǎo)致不必要的計算量，增加特征匹配數(shù)目和錯誤匹配概率。以信息論的觀點，獨特性不高的區(qū)域是信息量少的區(qū)域也是對點云配準幫助不大的區(qū)域。當然獨特性也要考慮噪聲、遮擋和離群值的影響，因為其產(chǎn)生的特征可能對配準沒有幫助而且是有害的，所以使用特征檢測獲得盡可能保持點云主要特征的部分。衡量特征檢測算法性能的重要指標是特征的可重復(fù)性和提取出特征的獨特性。

點特征是一種最常用的點云特征。Masuda等人(1996)采用基礎(chǔ)的隨機采樣法提取關(guān)鍵點，雖然這種方法很簡單并且能有效控制點的數(shù)量，但是其沒有辦法確保采樣的點均勻分布在點云上。Kamousi等人(2016)提出最遠點采樣法，解決了此問題。但是它們都無法確保選擇到對配準有更大幫助的點，也無法保證兩個點云中提取的關(guān)鍵點有更多相似的位置，即保證檢測的可重復(fù)性。Rusinkiewicz和Levoy(2001)提出了法向空間采樣方法(normal-space sampling)，其想法是使法線在所選點之間的分布盡可能廣泛，這樣不會讓所有的點都落在大平面上，在一些小卻獨特的區(qū)域也可以有比較大的機會選中。于是根據(jù)法線在角度空間中的位置對點進行存儲，然后對按角度存儲的點進行均勻采樣，使各個方向法線都能取到。Zhong(2009)提出用一定半徑內(nèi)的協(xié)方差矩陣提取關(guān)鍵點，選擇協(xié)方差矩陣特征值的最小值變化比較大的區(qū)域的點，這樣提取的關(guān)鍵點更有可能是點云中的特殊點。Tian等人(2016)將Sipiran和Bustos(2011)提出的用于多邊形網(wǎng)格的Harris 3D算法改進為更適合點云的變體。Harris 3D算法的核心思想在于計算Harris響應(yīng)并選取在幾何鄰域中有Harris響應(yīng)局部最大值的點作為關(guān)鍵點，其中Harris響應(yīng)是對各個方向上的導(dǎo)數(shù)變化趨勢的綜合考量，能夠表達點周圍的形狀，引入多尺度的概念，在多個尺度下計算Harris響應(yīng)，選擇幾何鄰域和尺度鄰域中具有響應(yīng)局部最大值的點作為關(guān)鍵點。Prakhya等人(2016)提出HoNO(histogram of normal orientations)方法，為每一個點計算法線和HoNO值作為判據(jù)，以去除平面區(qū)域并僅保留輸入點云中的凹凸區(qū)域或其他信息豐富的區(qū)域。然后執(zhí)行修剪步驟，即在一定范圍內(nèi)關(guān)鍵點應(yīng)有最低的HoNO峰度值或該點具有最強的法線變化，滿足條件即視為關(guān)鍵點，從而將顯著區(qū)域減少到最終關(guān)鍵點集。

除了檢測點特征，線特征作為一種可以有更大距離跨度的信息，也是一種很常用的特征。Stamos和Allen(2002)提出一種將點云先劃分為平面塊，然后得到平面之間的交線，取線到面邊緣的距離小于一定閾值的線段作為特征。Yang等人(2016)提出一種具有語義的線性特征，首先將地面點云刪除，然后對點云進行一層層的分割，提取點云中的極狀點、交點和頂點，將其連接為3種類型的垂直特征線。Prokop等人(2020)首先通過協(xié)方差矩陣的特征值提取尖銳特征點，然后通過Hough變換提取其中的直線特征。Tao等人(2020)將3維點云投影到重力方向變成2維點云，通過密度約束獲得高密度部分，然后執(zhí)行區(qū)域生長算法得到線特征。Yang和Zang(2014)則提取曲線而不是直線信息，用點鄰域的協(xié)方差矩陣的最小特征值分析點周圍的幾何曲率，將幾何曲率大的點劃分為若干線性簇，將線性簇擬合為波峰線作為特征。面特征具有更高的信息量并且對噪聲更不敏感，雖然一些點特征考慮到其一定范圍內(nèi)的點云，相似于面特征，但是其考慮的面的范圍有限。Brenner等人(2008)應(yīng)用區(qū)域生長法，通過迭代種子區(qū)域選擇和區(qū)域擴展兩個步驟，得到平面特征。Chen等人(2020)用基于RANSAC的平面提取方法，得到平面特征。Xu等人(2019)將點云劃分為體素，計算體素內(nèi)點的曲率，將滿足平面要求的平面塊組合為平面特征。

得益于圖像領(lǐng)域已有的研究，點云紋理特征的檢測可以方便地借鑒其相關(guān)方法。Zhang等人(2019)將反射強度處理為2維圖像，然后使用尺度不變特征變換(scale-invariant feature transform，SIFT)算法中的特征檢測方法，本質(zhì)上是以高斯函數(shù)差分(difference of Gaussian，DoG)的極值位置對應(yīng)的空間點作為特征點。Wang等人(2016)不將反射強度處理為2維圖像，而是直接使用一個3維高斯函數(shù)來卷積每個點云金字塔層次上的反射強度圖像，相鄰高斯平滑反射強度圖像相減生成DoG 3D，取DoG 3D的極值作為檢測到的特征。更多的紋理特征來自于點云的顏色信息，Liu等人(2007)在RGB表示的紋理圖像中使用DoG方法，并剔除不穩(wěn)定的局部峰值，獲得關(guān)鍵點。Jung等人(2018)使用fast-Hessian detector檢測關(guān)鍵點，功能類似于DoG，使用盒濾波器進行近似計算，檢測速度有了很大提高。Ji等人(2013)使用FAST(from accelerated segment test)特征檢測器，然后根據(jù)Harris測度對其進行排序，選取排在前面的點作為特征點。Yang等人(2020)使用超體素的方法，超體素考慮到了空間坐標、顏色值和局部幾何特征，以超體素的中心作為檢測到的特征點。

1.2.2 特征描述方法

檢測到的特征有時并不適合直接用于特征匹配，因為點云是一種離散的、非結(jié)構(gòu)化的數(shù)據(jù)，并且受噪聲、遮擋和離群值的影響。如果將檢測到的特征表述為描述符，通過描述符可以增加特征的魯棒性，加快特征間的對比和匹配。對于相近的點云分布，其點云描述符應(yīng)該也具有相似性，而對分布不相近的點云，其描述符應(yīng)該也具有不一致性。描述符具有一定的壓縮性，可以將復(fù)雜高維的點云特征壓縮為更簡單的表現(xiàn)形式。典型的描述符有特征簽名和特征直方圖。特征簽名提供數(shù)值結(jié)果作為點的描述符，特征直方圖方法則將點云信息表述為直方圖。得到特征描述符之后就可以進行特征匹配并計算變換。

點特征的描述是點云特征描述中研究較多的方向。Feldmar 和Ayache(1996)提出用點附近計算出的主曲率作為描述符。主曲率表示關(guān)鍵點周圍表面上的最大和最小曲率，并且綜合關(guān)鍵點處的法線與最大和最小曲率對應(yīng)的主方向作為該關(guān)鍵點的描述符。該描述符是剛性變換不變的，但是因為法線方向的歧義性，所以需要考慮法線可能的兩個方向。Chua和Jarvis(1997)提出應(yīng)用主成分分析(principal component analysis，PCA)提取特征，利用數(shù)據(jù)點3D坐標的加權(quán)協(xié)方差矩陣的3個特征向量，分析特征向量得到關(guān)鍵點，將主成分視為點描述符。Frome等人(2004)提出3D形狀上下文描述符(3D shape context，3DSC)，首先對整個點云進行隨機采樣得到N個點，確保選擇的點盡可能在點云中均勻分布，然后建立每個點到其他N-1個點的向量，對空間進行球體劃分，可以選擇殼模型、扇形模型和混合模型，構(gòu)建直方圖描述符。但是這樣的直方圖描述符不是旋轉(zhuǎn)不變的，所以需要執(zhí)行標準化步驟，執(zhí)行將質(zhì)心作為原點的平移和對對象執(zhí)行主軸變換，得到平移旋轉(zhuǎn)不變性。Zhong(2009)提出固有形狀簽名(intrinsic shape signatures，ISS)描述符，使用從基本八面體遞歸計算的離散球形網(wǎng)格，均勻地劃分球形表面，對鄰域協(xié)方差矩陣進行特征值分解得到4個LRF(local reference frame)，參照關(guān)鍵點處的LRF，使用其極坐標對每個鄰居點進行編碼。離散球面網(wǎng)格用于簡化直方圖。Rusu等人(2008)提出點特征直方圖(point feature histograms，PFH)，將關(guān)鍵點周圍一定半徑內(nèi)所有的點全部互相連接，對其中的每一個點，尋找與另一個點構(gòu)成的連線與該點的法線之間有最小夾角的點對，對所有這樣的點對計算參考框架和角度之間的關(guān)系，對每個關(guān)鍵點，根據(jù)周圍一定半徑內(nèi)每對點對的角度信息的值計算直方圖描述符。點特征直方圖(PFH)存在的問題在于其計算量比較大，是一個耗時的操作，于是Rusu等人(2009)提出一種改進的點特征直方圖方法——快速點特征直方圖(fast point feature histograms，F(xiàn)PFH)，要構(gòu)建快速點特征直方圖，首先要計算簡化點特征直方圖(simplifified point feature histogram，SPFH)，不同于點特征直方圖考慮周圍一定半徑內(nèi)所有點之間的關(guān)系，簡化點特征直方圖只考慮關(guān)鍵點和周圍一定半徑內(nèi)點的關(guān)系，直接使用簡化點特征直方圖表示的信息量太少，所以將周圍一定半徑內(nèi)點的SPFH加權(quán)為快速點特征直方圖。

對于線特征的描述符，直線的描述較為容易，也較為常用。Stamos和Allen(2002)將線特征用五元組表示，即線特征編號、線起始點、線終端點、線所在平面的法線和線所在平面的大小，只需要源點云和目標點云間各一個這樣的特征就可以估計變換矩陣。Yang等人(2016)使用九元組描述其語義線特征，包括構(gòu)成線的最高點、最低點、點的數(shù)量、線的長度、線的序號、線的類型、線的半徑和線支撐平面的兩個方向。Tao等人(2020)將兩個直線之間的夾角作為特征的描述，對直線方向的歧義問題，將所有線方向的反方向向量也納入夾角的計算。對于面特征，也可以對其提取特征而加快特征匹配的速度。Brenner等人(2008)在提取面特征后，嘗試了面積、周長和邊界框的長寬比等后認為，這些特征不夠可靠，可能會忽略正確的匹配，于是只保留法線和特征平面到原點的距離作為之后步驟的特征。Chen等人(2020)提取4個不平行的平面和2個平面的交線之間的關(guān)系作為特征，構(gòu)成具有8個子特征的描述符，為了應(yīng)對沒有4個不平行的平面的情況，又提出減少1個平面要求的有6個子特征的描述符，只需一個這樣的特征就能確定一個剛性變換。Xu等人(2019)從4個平面的法線與由法線組成的平面的交線之間的角度中構(gòu)建不變特征。

對于紋理特征的描述，可以直接采用經(jīng)典的圖像特征的描述方法，一些研究將紋理特征和幾何特征結(jié)合成新的特征描述符。Zhang等人(2019)直接使用SIFT特征描述方法描述由反射強度生成的強度圖像特征。Liu等人(2007)使用SIFT特征描述方法描述RGB圖像特征，通過2維圖像到3維點云的映射，使描述符同時描述了3維特征點。Wang等人(2016)使用主成分分析確定特征的周圍的包圍盒，將其分為L×J×K個部分，將強度信息加權(quán)加入每個部分，作為該點的特征描述符。Jung等人(2018)使用成熟的SURF(speed up robust features)特征描述符描述檢測到的特征。Ji等人(2013)使用ORB(oriented fast and rotated brief)特征描述方法，具體是使用BRIEF(binary robust independent elementary features)算法計算特征點的描述子，整體速度比SIFT和SURF更快。Yang等人(2020)使用三階顏色矩，表示每個超體素的顏色分布特征，并與中心點的空間坐標相結(jié)合作為描述符。蘇本躍等人(2019)將同態(tài)濾波后的最近8個點由拉普拉斯算子獲得顏色特征，并與幾何特征結(jié)合構(gòu)成魯棒的特征描述符。

1.2.3 特征匹配方法

特征匹配的過程也是一個變換估計的過程，獲得關(guān)鍵點及關(guān)鍵點的描述符后，就可通過描述符之間的對應(yīng)關(guān)系獲得變換矩陣，有對應(yīng)關(guān)系后配準問題就變成了凸問題，有很多方法可以得到變換矩陣，如SVD(singular value decomposition)、最小二乘法等。不同于類似ICP的過程，這里只需要獲得一個粗配準的變換，因此在這里精度不是最重要的考量，對應(yīng)關(guān)系健壯能夠為接下來的精配準提供良好的初值。蠻力匹配方法是最基礎(chǔ)的方法，假設(shè)兩個點云都有n個特征，如果需要3個對應(yīng)特征點以確定2個3D點集合之間的剛性變換，那么對應(yīng)的3個點的數(shù)量就可能達到n6，其中只有一小部分可以確定正確的變換矩陣。這在點云中點的數(shù)量較少時是可行的，但是當點云數(shù)量很大時，這將是一個非常耗時的過程。有了特征提取和特征描述等信息就可以開發(fā)一些搜索策略，從而使特征匹配速度大幅加快，極大地降低計算成本。

隨機抽樣一致算法(RANSAC)通過反復(fù)選擇數(shù)據(jù)中的一組子集來估計模型參數(shù)，將滿足模型的數(shù)據(jù)稱為局內(nèi)點，不滿足的稱為局外點，選取局內(nèi)點數(shù)滿足要求的作為正確估計。將RANSAC思想用于特征匹配是一種經(jīng)典的匹配方法。Chen等人(1999)詳細介紹了一種RANSAC方法，并基于這樣一個事實，即可以僅在兩個點集中各取3個點來確定剛性變換。先在第1個點集上選擇3個點組成目標三點集，為主點af、次點as和輔助點aa，相互之間的距離分別dfs、dsa和daf。然后在第2個點集上尋找與目標三點集形狀相似的候選三點集。尋找候選三點集的具體步驟為：先任選一點bf作為與目標三點集第1個點對應(yīng)的點，然后搜尋另一個點bs，其與bf的距離應(yīng)近似為dfs，如果有這樣的點則繼續(xù)尋找點ba使其滿足到bf的距離約為daf，到bs的距離約為dsa。重復(fù)這個過程，獲得大量近似與目標三點集相似的候選三點集，每一個候選三點集都可以確定一個變換。通過驗證點云中滿足候選三點集確定的變換的點的數(shù)量，最佳的匹配使?jié)M足變換的點的數(shù)量最多，如此就得到了最佳變換矩陣。加入特征的約束，在選點時考慮特征是否相同，通過構(gòu)建搜索樹能夠加快相同特征的搜索速度，并使找到的候選三點集的數(shù)量減少，減輕耗時的驗證環(huán)節(jié)的負擔。該算法具有魯棒性，即使其計算效率不是很高，但是因為其簡單性，可以用于各種特征，從而具有很好的通用性。RANSAC依然是一種應(yīng)用較為廣泛的特征匹配方法。

Gelfand等人(2005)提出用分支定界方法進行關(guān)鍵點的匹配，將坐標均方根誤差驗證轉(zhuǎn)換為距離均方根誤差，從而不需要計算變換矩陣就可以驗證關(guān)鍵點匹配質(zhì)量。該算法創(chuàng)建一個解決方案候選樹，樹中每個分支代表一個可能的點對應(yīng)集合。當將一個可能的候選添加到解決方案中，如果這些可能的候選對象之一未通過閾值測試，并且距離均方根誤差沒有得到改善，那么就“修剪”掉這個對應(yīng)集合的分支，通過探索整棵樹最終找到最佳的對應(yīng)。該方法也具有對噪聲、遮擋和離群值的魯棒性，但是對描述符的性能要求比較高。Theiler等人(2014)引入4PCS算法的思想，將關(guān)鍵點特征應(yīng)用到4PCS算法，從而開發(fā)出K- 4PCS算法。在進行經(jīng)典4PCS算法之前，首先計算關(guān)鍵點特征，將其用于4PCS可以加快相似共面四點集的搜尋速度，并且減少找到的相似共面四點集數(shù)量。Xu等人(2019)將平面作為K- 4PCS的特征，并設(shè)計了以角度而不是距離為度量的特征匹配方式。Ji等人(2017)將進化的方法直接用于角度變換空間的搜索，搜索最優(yōu)角度變換。同樣，進化的方法也可以用于關(guān)鍵點的匹配。Albarelli等人(2011)將博弈論框架用于關(guān)鍵點的匹配，自然選擇過程允許滿足相互剛性約束的匹配點得以幸存，從而消除了所有其他對應(yīng)關(guān)系。收益矩陣(payoff matrix)代表對應(yīng)關(guān)系，隨著進化迭代，某種對應(yīng)方式能夠得到最多的支持，那么其就能夠得到生存，最終的結(jié)果就是在一種變換下能夠使最多的點產(chǎn)生正確的對應(yīng)關(guān)系，也代表著最佳的變換方式。

上述方法適合于需要通過多對特征對應(yīng)關(guān)系才能確定變換的條件下，對于一些線特征和面特征只需要更少的對應(yīng)特征就能確定變換矩陣。Stamos和Allen(2002)設(shè)計的線特征兩兩之間就可以確定一個變換矩陣，通過閾值過濾線的長度和平面大小的比率不滿足條件的特征，再通過閾值驗證其他對是否匹配，迭代找到最佳匹配。Yang等人(2016)將得到的語義線特征組合為三角對，用結(jié)合線特征的三種約束獲得相似的三角對，用幾何一致性測試除去一些錯誤的對應(yīng)，用剩下的對應(yīng)計算變換矩陣。Tao等人(2020)使用兩個直線構(gòu)成的直線對的角度尋找匹配的直線對，以此確定一個不考慮重力方向上運動的變換，遍歷尋找最佳對應(yīng)關(guān)系。Brenner等人(2008)使用面特征構(gòu)成三元組估計變換矩陣，但是在計算變換矩陣之前，先計算三元組的三重積，并按降序排序，因為三重積越大計算的平移誤差就越小，并且當同一個變換出現(xiàn)預(yù)定次數(shù)時就停止迭代。Chen等人(2020)設(shè)計了面特征，只需要一對對應(yīng)即可確定變換矩陣，通過建立kd-tree尋找近似特征，又通過kd-tree尋找相似變換，得到一些相似變換的均值，減少要驗證的變換數(shù)量。

紋理特征的特征匹配方法與點特征的特征匹配方法有很多共通之處，因為較多的紋理特征和點特征一樣屬于局部特征。Zhang等人(2019)使用RANSAC確定正確的從反射強度圖像中提取的特征的正確匹配關(guān)系。Wang等人(2016)使用CTNC(closest to next closest)技術(shù)，即對于每一個特征，與其最相似的和第二相似的特征滿足一定的比例要求才認為其是正確的匹配特征。Liu等人(2007)在確定匹配關(guān)系時，引入對極幾何的約束，基于RANSAC的思路，尋找使最多特征點滿足對極幾何的約束的特征匹配。為了應(yīng)對RGBD相機的視點對SURF特征的影響，Jung等人(2018)利用3維點云生成不同視點的2維合成圖像，再生成不同分辨率的縮放圖像，這樣產(chǎn)生大量重復(fù)的特征匹配關(guān)系，然后投票選擇重復(fù)多的匹配關(guān)系作為最終的特征匹配。Yang等人(2020)使用權(quán)值權(quán)衡顏色特征和空間特征，并以此作為特征距離度量，當兩點云的空間位置相差較大時，采用顏色特征比空間特征更準確，當點云大致對齊時，更適合利用空間特征匹配點云的幾何細節(jié)。蘇本躍等人(2019)使用迭代最近特征的方法，迭代估計特征匹配關(guān)系和變換矩陣。

表2總結(jié)了基于特征的點云配準方法中各種形式的特征的特征檢測、特征描述和特征匹配的經(jīng)典方法。

表2 基于特征的配準方法Table 2 Feature-based registration method

2 基于學(xué)習(xí)的點云配準方法

隨著深度學(xué)習(xí)的發(fā)展，基于學(xué)習(xí)的點云配準方法得到廣泛研究和深入發(fā)展?；趯W(xué)習(xí)的方法對比非學(xué)習(xí)方法，最大優(yōu)勢在于相同配準性能下計算速度可以更快以及能學(xué)習(xí)到更高級的特征，從而達到更高的魯棒性?；趯W(xué)習(xí)的點云配準方法大量借鑒了非學(xué)習(xí)的點云配準方法的思想和深度學(xué)習(xí)方法在處理其他問題中的思想。根據(jù)配準方法的結(jié)構(gòu)是完全由網(wǎng)絡(luò)組成還是將非學(xué)習(xí)方法的一部分組件替換為基于學(xué)習(xí)的網(wǎng)絡(luò)，將基于學(xué)習(xí)的點云配準方法分為部分學(xué)習(xí)的方法和端到端的學(xué)習(xí)方法。部分學(xué)習(xí)的方法優(yōu)勢在于靈活性，可以容易地用于其他點云任務(wù)如點云分類、分割和檢測，也能夠?qū)⑵渌蝿?wù)中用到的網(wǎng)絡(luò)直接用于點云的配準，這樣比較簡單的網(wǎng)絡(luò)在一些應(yīng)用中也更容易部署。而端到端的學(xué)習(xí)方法優(yōu)勢在于統(tǒng)一性，不用借助其他方法就能直接實現(xiàn)點云配準，準備訓(xùn)練的數(shù)據(jù)和評價訓(xùn)練的結(jié)果更加容易，也更有利于整體性能的提升。

2.1 在點云上學(xué)習(xí)的方法

將深度學(xué)習(xí)用于點云是一個具有挑戰(zhàn)性的問題，因為點云是非結(jié)構(gòu)化的，點之間的關(guān)系不是明確的，點的分布密度也可能各不相同。在點云上進行學(xué)習(xí)的方法分為3類，即基于體素的方法、基于多視圖的方法和基于原始數(shù)據(jù)的方法?；隗w素的方法將點云轉(zhuǎn)換為結(jié)構(gòu)化的3D體素結(jié)構(gòu)，并將其與3D卷積核進行卷積，用類似圖像深度學(xué)習(xí)的方法卷積、池化和連接層進行學(xué)習(xí)(Maturana和Scherer，2015；Meng等，2019；Zhou和Tuzel，2018)。盡管基于體素的方法表現(xiàn)出良好的性能，但由于大多數(shù)體素中都沒有或者只有少量的點，這樣的稀疏性會導(dǎo)致很高的無效內(nèi)存消耗和計算量，從而導(dǎo)致無法將點云進行更加細致的體素劃分。另一種方法基于多視圖，將3維非結(jié)構(gòu)化的點云通過在多個方向上的投影轉(zhuǎn)換為2維結(jié)構(gòu)化的圖像的集合，然后對其用圖像深度學(xué)習(xí)方法處理并整合(Qi等，2016；Su等，2015；Kanezaki等，2018)。不同于基于體素的方法，基于多視圖的方法可以進行更加細致的劃分，數(shù)據(jù)量不會太大即可包含豐富的紋理信息。多視圖方法的限制在于視點的選擇和不同視點的整合比較困難。在點云上學(xué)習(xí)目前最流行、應(yīng)用最廣泛的方法是基于原始數(shù)據(jù)的方法。其中，PointNet是最為經(jīng)典的一種基于原始數(shù)據(jù)的點云學(xué)習(xí)方法(Charles等，2017)。為了能夠直接在點云上進行學(xué)習(xí)，引入可學(xué)習(xí)參數(shù)并且參數(shù)由每一層中的所有點共享的多層感知器(muti-layer perception，MLP)和為了使其輸出與輸入順序無關(guān)的對稱函數(shù)。在PointNet中，MLP層將點特征從3維轉(zhuǎn)換為1 024維，將maxpooling函數(shù)作為對稱函數(shù)，獲得與輸入順序無關(guān)的全局1 024維特征。PointNet取得了很好的性能，結(jié)構(gòu)圖如圖2所示。但是PointNet得到的是一個全局特征，而無法捕獲本地特征，一些情況下其魯棒性會下降。為此，研究者提出了許多能夠捕獲本地特征的方法。

圖2 PointNet結(jié)構(gòu)圖(Charles等，2017)Fig.2 PointNet architecture(Charles et al.，2017)

Qi等人(2017)擴展了PointNet，提出了PointNet++，在局部區(qū)域分層應(yīng)用PointNet，以適應(yīng)性地組合來自多個尺度的特征，提供了本地特征。Wang等人(2019)提出DGCNN(dynamic graph convolutional nerual network)，使用 EdgeConv網(wǎng)絡(luò)模塊提取點云局部鄰域的特征，可以通過堆疊EdgeConv模塊獲得更高層次的特征，所以能夠提取到表示很大范圍的特征，取得了很好的效果。

2.2 部分學(xué)習(xí)的點云配準方法

最初利用深度學(xué)習(xí)解決點云配準問題的嘗試使用了部分學(xué)習(xí)的點云配準方法，該方法直接用基于學(xué)習(xí)的組件替換掉非學(xué)習(xí)點云配準方法中的某個組件，這就可能給原來的算法帶來速度或魯棒性的提升。部分學(xué)習(xí)的點云配準方法最大的優(yōu)勢在于靈活性，能夠與其他方法組合，也可以直接用于其他領(lǐng)域。

Zaganidis等人(2018)提出語義輔助正態(tài)分布變換(semantic-assisted normal distributions transform，SE-NDT)，應(yīng)用PointNet提供全局特征，并與局部特征由分割網(wǎng)絡(luò)連接。分割網(wǎng)絡(luò)輸出該點的類別，從而提供分類語義信息，將其用于NDT算法取得了很好的性能，另外將這種語義輔助信息用在GICP中則得到SE-GICP(semantic-assisted generalized iterative closest point)。Truong等人(2019)也實現(xiàn)了類似的基于語義分割算法的點云配準。

在關(guān)鍵點檢測上，Li和Lee(2019)提出一種基于學(xué)習(xí)的關(guān)鍵點檢測算法——USIP(unsupervised stable interest point)深度學(xué)習(xí)檢測算法，使用特征提議網(wǎng)絡(luò)(feature proposal network)獲取原始點云以及對原始點云進行任意變換后點云的關(guān)鍵點，利用兩種損失，即使兩組關(guān)鍵點間的距離應(yīng)盡可能小的probabilistic chamfer loss和使提取的關(guān)鍵點盡量靠近實際點云的point-to-point loss，借此獲得檢測高度可重復(fù)且精確定位的關(guān)鍵點的能力。Du等人(2019)提出一種可同時學(xué)習(xí)關(guān)鍵點檢測和特征描述的深度學(xué)習(xí)算法，以點云及其相對變換矩陣作為輸入，輸出候選關(guān)鍵點的位置、候選關(guān)鍵點的可能性以及候選關(guān)鍵點的特征描述。通過最小化對應(yīng)關(guān)鍵點的距離和最大化不對應(yīng)關(guān)鍵點的距離以及最大化對應(yīng)關(guān)鍵點的可能性進行學(xué)習(xí)。

多數(shù)的部分學(xué)習(xí)的點云配準方法是基于特征的，而其中大多數(shù)的工作都集中于關(guān)鍵點描述上。Zeng等人(2017)提出一種基于體素上學(xué)習(xí)關(guān)鍵點描述符的網(wǎng)絡(luò)，將關(guān)鍵點周圍劃分為體素并將其輸入ConvNet網(wǎng)絡(luò)，學(xué)習(xí)的目標是對應(yīng)關(guān)鍵點的描述符之間的距離應(yīng)最小化，同時拉開不對應(yīng)關(guān)鍵點之間的距離。該方法使用隨機關(guān)鍵點選擇和RANSAC關(guān)鍵點匹配方法，構(gòu)成完整的點云配準方法，達到了比較好的性能。Elbaz等人(2017)利用學(xué)習(xí)的自動編碼器進行描述符編碼。首先用隨機球面覆蓋集(random sphere cover set)獲得超點集，然后為其確定坐標系，再將其投影為2D圖像，進行過濾和顯著性檢測操作后輸入深度自動編碼器，以原始圖像和解碼后圖像間的像素差別作為損失。獲得描述符后，用RANSAC方法進行點云配準，然后使用ICP算法進行精配準。Deng等人(2018b)提出一種特征提取與特征描述學(xué)習(xí)網(wǎng)絡(luò)PPFNET(point pair feature network)，輸入從點云中均勻采樣的N個局部點云，使用N個共享權(quán)重的PointNet獲得各自特征，將這些局部特征通過最大池化層聚合為一個全局特征后加到每個局部特征中，再通過N個MLP處理得到最終的局部描述符。為了進行訓(xùn)練，通過參考真值計算N個局部點云的距離矩陣再二值化為對應(yīng)矩陣，并構(gòu)建訓(xùn)練得到的特征之間的距離構(gòu)成的特征距離矩陣，利用兩個矩陣計算N-tuple loss并優(yōu)化網(wǎng)絡(luò)參數(shù)，通過RANSAC與特征提取和描述功能綜合為點云配準框架。PPF-FoldNet(point pair feature folding network)(Deng等, 2018a)進一步擴展了該算法。Yew和Lee(2018)提出3DFeat-Net學(xué)習(xí)特征的提取和描述，使用包含錨點和正負點的三元組訓(xùn)練網(wǎng)絡(luò)，使錨點與正點的描述符更接近，與負點的描述符更遠離。為此作者設(shè)計了由3個并行的共享權(quán)重子網(wǎng)絡(luò)組成的學(xué)習(xí)網(wǎng)絡(luò)，點云經(jīng)過聚類后經(jīng)檢測(detector)模塊學(xué)習(xí)權(quán)重和朝向，并在第1階段選擇權(quán)重大的點作為關(guān)鍵點，在下一階段描述符網(wǎng)絡(luò)僅為這些關(guān)鍵點計算描述符。分別對比錨點和正點、錨點和負點的特征，選擇對應(yīng)特征并用權(quán)重加權(quán)獲得損失函數(shù)，用其與RANSAC結(jié)合成完整的點云配準框架測試其性能。Khoury等人(2017)也應(yīng)用三元組訓(xùn)練描述符，得到了CGF(compact geometric features)特征。

2.3 端到端的點云配準方法

目前，很多工作都致力于端到端的點云配準的方法，從點云的輸入到最后的配準結(jié)果都在一個完整的網(wǎng)絡(luò)中實現(xiàn)，端到端的點云配準方法能夠最大程度地發(fā)揮深度學(xué)習(xí)方法的高效和智能，也能夠更好地發(fā)揮GPU的并行計算能力，有更快的速度。在深度學(xué)習(xí)網(wǎng)絡(luò)中，能夠反向傳播是非常重要的，所以在構(gòu)建端到端的點云配準網(wǎng)絡(luò)時，要保證可求導(dǎo)，這樣才能進行學(xué)習(xí)，而很多非學(xué)習(xí)方法中的組件是不可求導(dǎo)的，所以要對其加以改進。端到端的點云學(xué)習(xí)方式在訓(xùn)練數(shù)據(jù)上也比訓(xùn)練關(guān)鍵點檢測器和關(guān)鍵點描述器容易，因為其通過配準的好壞進行評價，而關(guān)鍵點檢測器和關(guān)鍵點描述器的評價相對困難。

Aoki等人(2019)提出PointNetLK算法，源點云和目標點云首先分別通過沒有T-Net的PointNet網(wǎng)絡(luò)獲得全局特征，然后通過LK(Lucas and Kanade)算法估計對齊方式。點云配準要找到一個最佳變化矩陣，因此需要求損失對于變換矩陣的導(dǎo)數(shù)，為了方便計算將其轉(zhuǎn)換為對李代數(shù)的求導(dǎo)。借鑒IC(inverse compositional)方法，使雅可比計算只需執(zhí)行一次，大幅提高了效率，訓(xùn)練目標為網(wǎng)絡(luò)輸出的變換矩陣的逆矩陣與變換矩陣真值的矩陣相乘結(jié)果應(yīng)盡量接近單位陣。Yuan等人(2021)將經(jīng)過聚類和3DFeatNet特征描述層后的特征饋入一個全連接層，所有特征之間兩兩計算權(quán)重，使用SVD方法獲得最終變換矩陣，訓(xùn)練目標與PointNetLK相同。Kurobe等人(2020)使用PointNet獲得特征，然后再將源點云全局特征和目標點云全局特征與局部特征結(jié)合，通過MLP獲得對應(yīng)關(guān)系，使用SVD獲得最終變換參數(shù)。Huang等人(2020)提出一種網(wǎng)絡(luò)，在不需要搜索對應(yīng)關(guān)系的情況下，通過最小化特征空間上的投影誤差解決配準問題，并且保持了配準的過程性。Lu等人(2019)提出DeepVCP(deep virtual corresponding points)算法，使用PointNet++提取特征，通過點云加權(quán)層學(xué)習(xí)每一個點的顯著性，以避免動態(tài)物體干擾，點云特征嵌入DFE(deep feature embedding)層為關(guān)鍵點提取更加精細的局部鄰域特征，通過初始位姿得到預(yù)測對應(yīng)點并將其周圍體素化劃分，從中選擇更好的對應(yīng)點。ICP算法選擇最接近的點作為對應(yīng)點，導(dǎo)致不能求導(dǎo)而無法反向傳播，對此提出對應(yīng)點生成CPG(corresponding point generation)層得到對應(yīng)點，并通過SVD再計算對應(yīng)點引入關(guān)鍵點之間的統(tǒng)一的幾何約束，是一種基于學(xué)習(xí)的精配準方法。Wang和Solomon(2019)提出deep closest point算法，借鑒ICP思想，首先經(jīng)過DGCNN學(xué)習(xí)特征，接著transformer組件使兩點云特征具有來自兩個點云的上下文信息，pointer層避免選擇不可微分的特征對應(yīng)硬分配而是權(quán)重對應(yīng)，最后使用SVD分解獲得變換。Yew和Lee(2020)提出RPM-Net(robust point matching network)，使用PPF(point pair features)作為特征提取模塊的輸入，使用具有確定性退火調(diào)度的軟分配方案，以在每次迭代時逐漸“強化”分配，使用網(wǎng)絡(luò)學(xué)習(xí)預(yù)測最佳退火參數(shù)α、β，通過特征和參數(shù)α、β獲得匹配矩陣，從而估計特征對應(yīng)關(guān)系，使用SVD計算變換參數(shù)。RPM-Net的特點是可以迭代執(zhí)行配準并收斂。

表3總結(jié)了典型的基于學(xué)習(xí)的點云配準方法的典型方法及其特點。

表3 基于學(xué)習(xí)的點云配準方法Table 3 Point cloud registration method based on learning

3 結(jié) 語

本文將點云配準方法總結(jié)為非學(xué)習(xí)的方法和基于學(xué)習(xí)的方法，介紹了經(jīng)典方法、基于特征的非學(xué)習(xí)方法、部分學(xué)習(xí)的方法和端到端學(xué)習(xí)的方法，分析了一些算法的細節(jié)和同類算法的特點。很多經(jīng)典方法及其變體都屬于精配準方法，精配準方法有著比較快的配準速度，常常作為粗配準后的優(yōu)化方法?；谔卣鞯姆菍W(xué)習(xí)和基于學(xué)習(xí)的方法則常常作為粗配準用來提供良好的初始位姿，雖然各種方法差別很大，但是特征往往在其中起到最重要的作用?；趯W(xué)習(xí)的方法成為目前比較熱門的研究方向，對比非學(xué)習(xí)的方法，其相關(guān)的論文發(fā)表量具有更高的增速，但是非學(xué)習(xí)的方法的文獻還是要比基于學(xué)習(xí)的方法的文獻多。目前兩類方法都還有很多可研究內(nèi)容，并有希望取得進一步的突破。

點云配準技術(shù)經(jīng)過多年發(fā)展，已經(jīng)取得了很多成果，并且隨著點云配準技術(shù)的發(fā)展和深入到生產(chǎn)生活中，更多應(yīng)用對點云配準技術(shù)提出了更高的挑戰(zhàn)。主要挑戰(zhàn)有：1)應(yīng)用場景的挑戰(zhàn)。如大規(guī)模的點云、動態(tài)非穩(wěn)定的點云、缺乏特征、重復(fù)特征或?qū)ΨQ的點云，這些應(yīng)用場景對點云配準的可用性和可靠性提出了很高的要求。2)配準性能的挑戰(zhàn)。如要能滿足一些應(yīng)用中高精度的要求，在實時應(yīng)用中需要保證快速配準，達到更高的配準準確率、更高的配準精度配準速度比和更高的配準精度計算負擔比。3)應(yīng)用條件的挑戰(zhàn)。在計算資源有限的設(shè)備上能否達到可以接受的配準效率，在點云只是部分重疊時能否配準成功。4)算法的通用性問題。現(xiàn)有的點云配準方法能夠應(yīng)對一些挑戰(zhàn)，但是現(xiàn)有的點云配準方法仍存在一些缺陷和不足，如很多精配準方法雖然能達到好的配準精度，但是需要一個良好的初始位姿，否則容易陷入局部最優(yōu)。一些粗配準方法不需要初始條件，但是需要更多的計算以找到全局配準參數(shù)，并且配準的精度往往不高，需要結(jié)合精配準以提高其精度?；趯W(xué)習(xí)的方法仍主要集中于簡單物體的配準上，對于復(fù)雜場景、大規(guī)模點云上的研究還不是很多，還缺乏在這些場景下的基準數(shù)據(jù)集。高準確率高精度往往意味著高的時間消耗和大的計算負擔，能達到二者都很優(yōu)秀的配準方法不多。

為了應(yīng)對點云配準面臨的挑戰(zhàn)，提高點云配準算法的性能和實用性，展望點云配準算法未來的發(fā)展趨勢，可能會有以下特點：1)更多地運用點云和特征的高效存儲與索引方法，能夠消除部分信息冗余的點云預(yù)處理與特征表示方法，高效的特征匹配方法和優(yōu)化方法等能夠減少時間消耗的策略；2)可以采用由全局到局部、由粗到精、多尺度的漸進優(yōu)化方法，混合各種方法的特點，融合構(gòu)造新方法；3)尋求更加具有代表性且數(shù)量較少、提取更方便快速、更加魯棒和受離群值、噪聲、采集條件影響更小的特征，提取全局特征，從更大范圍提取局部特征和語義特征；4)對特定的應(yīng)用環(huán)境，構(gòu)造特定的方法，針對性的設(shè)計應(yīng)對策略；5)運用深度學(xué)習(xí)的方法，構(gòu)建更加符合應(yīng)用需求的基準數(shù)據(jù)集、創(chuàng)新的配準網(wǎng)絡(luò)或借鑒其他深度學(xué)習(xí)任務(wù)的思路方法，發(fā)揮深度學(xué)習(xí)在深層次特征、語義提取、理解與辨識和應(yīng)對復(fù)雜場景的能力；6)無監(jiān)督自主地進行點云配準，能夠檢測配準失敗，并自動糾錯或進行其他處理；7)適應(yīng)并應(yīng)用新的點云采集設(shè)備和使用其他輔助設(shè)備，使用新增的信息，融合增進效果。