三維點(diǎn)云配準(zhǔn)方法研究進(jìn)展

李建微，占家旺

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

0 引 言

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

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

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

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

1 非學(xué)習(xí)的點(diǎn)云配準(zhǔn)方法

1.1 經(jīng)典點(diǎn)云配準(zhǔn)方法

1.1.1 ICP及其變體

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

(1)

(2)

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

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

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

1.1.2 NDT及其變體

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

(3)

(4)

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

(5)

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

(6)

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

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

1.1.3 4PCS及其變體

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

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

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

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

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

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

1.2 基于特征的點(diǎn)云配準(zhǔn)方法

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

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

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

1.2.1 特征檢測(cè)方法

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

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

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

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

1.2.2 特征描述方法

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

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

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

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

1.2.3 特征匹配方法

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

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

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

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

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

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

表2 基于特征的配準(zhǔn)方法Table 2 Feature-based registration method

2 基于學(xué)習(xí)的點(diǎn)云配準(zhǔn)方法

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

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

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

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

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

2.2 部分學(xué)習(xí)的點(diǎn)云配準(zhǔn)方法

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

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

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

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

2.3 端到端的點(diǎn)云配準(zhǔn)方法

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

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

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

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

3 結(jié) 語(yǔ)

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

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

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