作者丨一點(diǎn)人工一點(diǎn)智能

來源丨h(huán)ttps://zhuanlan.zhihu.com/p/501555808

(李建微, 占家旺. 2022. 三維點(diǎn)云配準(zhǔn)方法研究進(jìn)展. 中國圖象圖形學(xué)報(bào), 27(2): 349-367.) [DOI: 10.11834/jig.210243]

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

1.1 ICP及其變體

一些方法致力于提高ICP方法的精度。Chen和Medioni(1992)將點(diǎn)對(duì)點(diǎn)擴(kuò)展到點(diǎn)對(duì)面(pointtoplane，ICP)，通過計(jì)算法線得到一個(gè)切平面，通過最小化點(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)過任意的剛體變換 T?后，兩個(gè)點(diǎn)間的距離就有了一種高斯分布，那么最優(yōu)的變換矩陣就是使對(duì)應(yīng)點(diǎn)間經(jīng)此變換后距離的高斯概率最大的變換矩陣。此方法對(duì)錯(cuò)誤對(duì)應(yīng)具有魯棒性，并且還可以允許添加離群項(xiàng)、測量噪聲和其他概率技術(shù)來增加魯棒性。一些方法致力于擴(kuò)大ICP方法的收斂范圍。

Gold等人(1998)提出RPM(robust point matching)，通過將點(diǎn)對(duì)應(yīng)關(guān)系從一對(duì)一變成一對(duì)多，并通過確定性退火在每次迭代時(shí)逐漸“強(qiáng)化”分配。其中退火參數(shù)較小時(shí)對(duì)應(yīng)更平均，這有助于避免陷入局部最小值，而β增加時(shí)更趨向于只對(duì)應(yīng)某一個(gè)。Yang等人(2013)提出go-ICP?算法，通過分支定界法，在 SE(3)空間內(nèi)，使用八叉樹數(shù)據(jù)結(jié)構(gòu)將初始空間細(xì)分為較小的子空間，用分支定界的方法去除不佳的空間，繼續(xù)細(xì)分滿足門限條件的空間，從而找到全局最優(yōu)變換。該方法盡管解決了局部極小值問題，但對(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算法，通過kd-tree以及根據(jù)上一次最近點(diǎn)搜尋的結(jié)果推斷此次可能的位置，通過最近點(diǎn)高速緩存，加快搜尋。通過解耦，盡可能獨(dú)立地加速平移和旋轉(zhuǎn)，而不會(huì)產(chǎn)生沖突。Pavlov等人(2018)將Anderson加速引入ICP算法(Anderson acceleration iterative closest point，AA-ICP)，利用Anderson算法對(duì)不動(dòng)點(diǎn)問題的加速能力，還提出了兩種啟發(fā)性的策略以應(yīng)對(duì)Anderson算法的不穩(wěn)定性的問題，提高了配準(zhǔn)的收斂速度和魯棒性。ICP算法也可以與特征相結(jié)合，Ren和Zhou(2015)用容易獲得的拐點(diǎn)特征代替點(diǎn)，減少了點(diǎn)的數(shù)量,在大規(guī)模數(shù)據(jù)點(diǎn)云上顯示出優(yōu)勢。

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

1.2 NDT及其變體

NDT點(diǎn)云配準(zhǔn)方法是另一種經(jīng)典的點(diǎn)云配準(zhǔn)方法，是一種利用數(shù)學(xué)分布性質(zhì)刻畫點(diǎn)云數(shù)據(jù)并用其構(gòu)造優(yōu)化目標(biāo)的方法(Magnusson等，2007)。用于點(diǎn)云配準(zhǔn)的3DNDT是受Biber和Strasser(2003)提出的2DNDT算法的啟發(fā)，并將其擴(kuò)展到3D。給定源點(diǎn)云

將最佳的變換作用于源點(diǎn)云，迭代式(6)計(jì)算新的最佳變換。NDT方法對(duì)體素的劃分敏感，可以通過改變體素的大小，對(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均值聚類劃分點(diǎn)云，并且在多個(gè)尺度上進(jìn)行優(yōu)化，K均值聚類解決了NDT算法中出現(xiàn)的成本函數(shù)不連續(xù)問題。多尺度優(yōu)化有利于跨越局部最小值，這也改善了這種方法的收斂性。

Lu等人(2015)提出一種體素大小可變的方法，在將大體素分割為幾個(gè)小的體素的過程中考慮體素內(nèi)點(diǎn)的個(gè)數(shù)，點(diǎn)稀疏時(shí)體素分大些，點(diǎn)密集時(shí)體素分小些。這樣可以將稀疏點(diǎn)聚集為一個(gè)大的體素，將密集的點(diǎn)分散為多個(gè)小體素，從而消除了固定大小的體素之間的點(diǎn)的數(shù)量差異很大的問題，避免了某些稀疏點(diǎn)無法使用的缺陷。

Das和Waslander(2014)提出一種分段區(qū)域生長NDT算法(segmented region growing normal distributions transform，SRG-NDT)，使用基于高斯過程的分割算法從掃描中刪除地平面，然后應(yīng)用效率高的區(qū)域增長算法對(duì)其余點(diǎn)進(jìn)行聚類，不再是按體素進(jìn)行概率密度函數(shù)的計(jì)算，而是從聚類的結(jié)果中計(jì)算概率密度函數(shù)，從而得到比體素方法少得多的概率分布來對(duì)環(huán)境進(jìn)行精確建模，同樣也克服了成本函數(shù)的不連續(xù)性，并且由于除去了地面點(diǎn),從而使速度得到明顯提高。Zaganidis等人(2017)利用點(diǎn)云的平滑度將點(diǎn)云分區(qū)，丟棄掉未劃分進(jìn)分區(qū)的大量點(diǎn)，不在全部點(diǎn)云而是在相同類型的分區(qū)上進(jìn)行NDT，這既減少了點(diǎn)的數(shù)目又為配準(zhǔn)剔除了一些干擾，不僅加快了配準(zhǔn)速度,也提高了魯棒性。

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

1.3 4PCS及其變體

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

很多研究致力于提高4PCS算法的速度。Mel-lado等人(2014)提出super 4PCS算法。在4PCS算法中判斷是否是大致一致共面四點(diǎn)集，只根據(jù)兩條直線被交點(diǎn)分成的兩段的長度的比值，而沒有考慮兩條線之間的夾角，super 4PCS考慮了這一點(diǎn)，這減少了候選大致一致共面四點(diǎn)集的數(shù)量。對(duì)于提取所有距離約等于 d1?或 d2的點(diǎn)對(duì)和夾角匹配，super 4PCS分別借用3D球體與點(diǎn)之間的經(jīng)典入射問題和報(bào)告位于圓上的所有點(diǎn)在單位球上的入射問題的思路，將搜尋速度大幅提高，在數(shù)據(jù)點(diǎn)數(shù)量上達(dá)到一次時(shí)間復(fù)雜性。

Huang等人(2017)提出了volumet-ric4PCS，將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í)。volumetric4PCS在super4PCS的基礎(chǔ)上進(jìn)行改進(jìn)，繼承了其快速的優(yōu)勢。因?yàn)槭欠枪裁嫠狞c(diǎn)集，所以需要6個(gè)點(diǎn)間距離來描述基四點(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 plan-sets，LCP)衡量配準(zhǔn)質(zhì)量，該算法使用最大的公共平面集代替，這使驗(yàn)證速度更快，并對(duì)噪聲更魯棒。Xu等人(2019)提出voxel4PCS，將點(diǎn)云體素化用以提取平面，再將共面平面融合，用平面代替點(diǎn)，用角度關(guān)系代替長度關(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í)間較長，雖然其變體在一定程度上加快了速度，但仍無法滿足一些實(shí)時(shí)性要求高的應(yīng)用。

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

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

基于特征的方法沒有用點(diǎn)云中全部的點(diǎn)進(jìn)行配準(zhǔn)，而是只選取點(diǎn)云中比較特殊的一部分進(jìn)行配準(zhǔn)，這種方法可以不需要提供初始位姿，并且具有魯棒性。一個(gè)典型的基于特征的點(diǎn)云配準(zhǔn)方法包括特征檢測、特征描述和特征匹配。

其中，特征檢測使要處理的數(shù)據(jù)量變少，從而加快配準(zhǔn)過程；特征描述將不容易進(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)方法流程

配準(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)特征、線特征和面特征。通過這些特征，大多數(shù)情況下能夠完成配準(zhǔn)任務(wù)，但是當(dāng)物體對(duì)稱性很強(qiáng)或者想提升配準(zhǔn)的性能時(shí)，往往需要其他特征的輔助，紋理特征是主要的輔助特征的形式。

在點(diǎn)云采集設(shè)備中，無論是反射強(qiáng)度還是顏色，都可以將其視為紋理特征，并且能夠找到其與點(diǎn)的空間位置的對(duì)應(yīng)關(guān)系，這是可以方便地使用紋理特征的基礎(chǔ)。紋理特征可以用于確定特征對(duì)應(yīng)關(guān)系，空間位置負(fù)責(zé)計(jì)算變換矩陣。

2.1 特征檢測方法

對(duì)所有的點(diǎn)求描述符是不合適的，一方面這會(huì)極大地加重計(jì)算負(fù)擔(dān)，另一方面這對(duì)配準(zhǔn)也沒有很大的幫助，因?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)沒有幫助而且是有害的，所以使用特征檢測獲得盡可能保持點(diǎn)云主要特征的部分。衡量特征檢測算法性能的重要指標(biāo)是特征的可重復(fù)性和提取出特征的獨(dú)特性。

點(diǎn)特征是一種最常用的點(diǎn)云特征。

Masuda等人(1996)采用基礎(chǔ)的隨機(jī)采樣法提取關(guān)鍵點(diǎn)，雖然這種方法很簡單并且能有效控制點(diǎn)的數(shù)量，但是其沒有辦法確保采樣的點(diǎn)均勻分布在點(diǎn)云上。

Ka-mousi等人(2016)提出最遠(yuǎn)點(diǎn)采樣法，解決了此問題。但是它們都無法確保選擇到對(duì)配準(zhǔn)有更大幫助的點(diǎn)，也無法保證兩個(gè)點(diǎn)云中提取的關(guān)鍵點(diǎn)有更多相似的位置，即保證檢測的可重復(fù)性。

Rusinkiewicz和Levoy(2001)提出了法向空間采樣方法(normalspace 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)格的Harris3D算法改進(jìn)為更適合點(diǎn)云的變體。Harris3D算法的核心思想在于計(jì)算Harris響應(yīng)并選取在幾何鄰域中有Harris響應(yīng)局部最大值的點(diǎn)作為關(guān)鍵點(diǎn)，其中Harris響應(yīng)是對(duì)各個(gè)方向上的導(dǎo)數(shù)變化趨勢的綜合考量，能夠表達(dá)點(diǎn)周圍的形狀，引入多尺度的概念，在多個(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)集。

除了檢測點(diǎn)特征，線特征作為一種可以有更大距離跨度的信息，也是一種很常用的特征。

Stamos和Allen(2002)提出一種將點(diǎn)云先劃分為平面塊，然后得到平面之間的交線，取線到面邊緣的距離小于一定閾值的線段作為特征。Yang等人(2016)提出一種具有語義的線性特征，首先將地面點(diǎn)云刪除，然后對(duì)點(diǎn)云進(jìn)行一層層的分割，提取點(diǎn)云中的極狀點(diǎn)、交點(diǎn)和頂點(diǎn)，將其連接為3種類型的垂直特征線。Prokop等人(2020)首先通過協(xié)方差矩陣的特征值提取尖銳特征點(diǎn)，然后通過Hough變換提取其中的直線特征。Tao等人(2020)將3維點(diǎn)云投影到重力方向變成2維點(diǎn)云，通過密度約束獲得高密度部分，然后執(zhí)行區(qū)域生長算法得到線特征。

Yang和Zang(2014)則提取曲線而不是直線信息，用點(diǎn)鄰域的協(xié)方差矩陣的最小特征值分析點(diǎn)周圍的幾何曲率，將幾何曲率大的點(diǎn)劃分為若干線性簇，將線性簇?cái)M合為波峰線作為特征。面特征具有更高的信息量并且對(duì)噪聲更不敏感，雖然一些點(diǎn)特征考慮到其一定范圍內(nèi)的點(diǎn)云，相似于面特征，但是其考慮的面的范圍有限。

Brenner等人(2008)應(yīng)用區(qū)域生長法，通過迭代種子區(qū)域選擇和區(qū)域擴(kuò)展兩個(gè)步驟，得到平面特征。Chen等人(2020)用基于RANSAC的平面提取方法，得到平面特征。Xu等人(2019)將點(diǎn)云劃分為體素，計(jì)算體素內(nèi)點(diǎn)的曲率，將滿足平面要求的平面塊組合為平面特征。

得益于圖像領(lǐng)域已有的研究，點(diǎn)云紋理特征的檢測可以方便地借鑒其相關(guān)方法。

Zhang等人(2019)將反射強(qiáng)度處理為2維圖像，然后使用尺度不變特征變換(scale-invariantfeaturetransform，SIFT)算法中的特征檢測方法，本質(zhì)上是以高斯函數(shù)差分(differenceofGaussian，DoG)的極值位置對(duì)應(yīng)的空間點(diǎn)作為特征點(diǎn)。

Wang等人(2016)不將反射強(qiáng)度處理為2維圖像，而是直接使用一個(gè)3維高斯函數(shù)來卷積每個(gè)點(diǎn)云金字塔層次上的反射強(qiáng)度圖像，相鄰高斯平滑反射強(qiáng)度圖像相減生成DoG3D，取DoG3D的極值作為檢測到的特征。

更多的紋理特征來自于點(diǎn)云的顏色信息，Liu等人(2007)在RGB表示的紋理圖像中使用DoG方法，并剔除不穩(wěn)定的局部峰值，獲得關(guān)鍵點(diǎn)。Jung等人(2018)使用fast-Hessian detector檢測關(guān)鍵點(diǎn)，功能類似于DoG，使用盒濾波器進(jìn)行近似計(jì)算，檢測速度有了很大提高。

Ji等人(2013)使用FAST(from accelerated segmenttest)特征檢測器，然后根據(jù)Harris測度對(duì)其進(jìn)行排序，選取排在前面的點(diǎn)作為特征點(diǎn)。Yang等人(2020)使用超體素的方法，超體素考慮到了空間坐標(biāo)、顏色值和局部幾何特征，以超體素的中心作為檢測到的特征點(diǎn)。

2.2 特征描述方法

檢測到的特征有時(shí)并不適合直接用于特征匹配，因?yàn)辄c(diǎn)云是一種離散的、非結(jié)構(gòu)化的數(shù)據(jù)，并且受噪聲、遮擋和離群值的影響。如果將檢測到的特征表述為描述符，通過描述符可以增加特征的魯棒性，加快特征間的對(duì)比和匹配。

對(duì)于相近的點(diǎn)云分布，其點(diǎn)云描述符應(yīng)該也具有相似性，而對(duì)分布不相近的點(diǎn)云，其描述符應(yīng)該也具有不一致性。描述符具有一定的壓縮性，可以將復(fù)雜高維的點(diǎ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)周圍表面上的最大和最小曲率，并且綜合關(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)格用于簡化直方圖。

Rusu等人(2008)提出點(diǎn)特征直方圖(point feature histograms，PFH)，將關(guān)鍵點(diǎn)周圍一定半徑內(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ù)周圍一定半徑內(nèi)每對(duì)點(diǎn)對(duì)的角度信息的值計(jì)算直方圖描述符。點(diǎn)特征直方圖(PFH)存在的問題在于其計(jì)算量比較大，是一個(gè)耗時(shí)的操作，于是Rusu等人(2009)提出一種改進(jìn)的點(diǎn)特征直方圖方法———快速點(diǎn)特征直方圖(fast point feature histograms，FPFH)，要構(gòu)建快速點(diǎn)特征直方圖，首先要計(jì)算簡化點(diǎn)特征直方圖(simplifified point featur ehistogram，SPFH)，不同于點(diǎn)特征直方圖考慮周圍一定半徑內(nèi)所有點(diǎn)之間的關(guān)系，簡化點(diǎn)特征直方圖只考慮關(guān)鍵點(diǎn)和周圍一定半徑內(nèi)點(diǎn)的關(guān)系，直接使用簡化點(diǎn)特征直方圖表示的信息量太少，所以將周圍一定半徑內(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)使用九元組描述其語義線特征，包括構(gòu)成線的最高點(diǎn)、最低點(diǎn)、點(diǎn)的數(shù)量、線的長度、線的序號(hào)、線的類型、線的半徑和線支撐平面的兩個(gè)方向。Tao等人(2020)將兩個(gè)直線之間的夾角作為特征的描述，對(duì)直線方向的歧義問題，將所有線方向的反方向向量也納入夾角的計(jì)算。對(duì)于面特征，也可以對(duì)其提取特征而加快特征匹配的速度。

Brenner等人(2008)在提取面特征后，嘗試了面積、周長和邊界框的長寬比等后認(rèn)為，這些特征不夠可靠，可能會(huì)忽略正確的匹配，于是只保留法線和特征平面到原點(diǎn)的距離作為之后步驟的特征。Chen等人(2020)提取4個(gè)不平行的平面和2個(gè)平面的交線之間的關(guān)系作為特征，構(gòu)成具有8個(gè)子特征的描述符，為了應(yīng)對(duì)沒有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圖像特征，通過2維圖像到3維點(diǎn)云的映射，使描述符同時(shí)描述了3維特征點(diǎn)。Wang等人(2016)使用主成分分析確定特征的周圍的包圍盒，將其分為 L*J*K個(gè)部分，將強(qiáng)度信息加權(quán)加入每個(gè)部分，作為該點(diǎn)的特征描述符。Jung等人(2018)使用成熟的SURF(speed up robust features)特征描述符描述檢測到的特征。

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)成魯棒的特征描述符。

點(diǎn)云學(xué)習(xí)教程：面向自動(dòng)駕駛領(lǐng)域的3D點(diǎn)云目標(biāo)檢測全棧學(xué)習(xí)路線！(單模態(tài)+多模態(tài)/數(shù)據(jù)+代碼)

2.3 特征匹配方法

特征匹配的過程也是一個(gè)變換估計(jì)的過程，獲得關(guān)鍵點(diǎn)及關(guān)鍵點(diǎn)的描述符后，就可通過描述符之間的對(duì)應(yīng)關(guān)系獲得變換矩陣，有對(duì)應(yīng)關(guān)系后配準(zhǔn)問題就變成了凸問題，有很多方法可以得到變換矩陣，如SVD(singular value decomposition)、最小二乘法等。

不同于類似ICP的過程，這里只需要獲得一個(gè)粗配準(zhǔn)的變換，因此在這里精度不是最重要的考量，對(duì)應(yīng)關(guān)系健壯能夠?yàn)榻酉聛淼木錅?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í)的過程。有了特征提取和特征描述等信息就可以開發(fā)一些搜索策略，從而使特征匹配速度大幅加快，極大地降低計(jì)算成本。

隨機(jī)抽樣一致算法(RANSAC)通過反復(fù)選擇數(shù)據(jù)中的一組子集來估計(jì)模型參數(shù)，將滿足模型的數(shù)據(jù)稱為局內(nèi)點(diǎn)，不滿足的稱為局外點(diǎn)，選取局內(nèi)點(diǎn)數(shù)滿足要求的作為正確估計(jì)。將RANSAC思想用于特征匹配是一種經(jī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è)解決方案候選樹，樹中每個(gè)分支代表一個(gè)可能的點(diǎn)對(duì)應(yīng)集合。當(dāng)將一個(gè)可能的候選添加到解決方案中，如果這些可能的候選對(duì)象之一未通過閾值測試，并且距離均方根誤差沒有得到改善，那么就“修剪”掉這個(gè)對(duì)應(yīng)集合的分支，通過探索整棵樹最終找到最佳的對(duì)應(yīng)。該方法也具有對(duì)噪聲、遮擋和離群值的魯棒性，但是對(duì)描述符的性能要求比較高。Theiler等人(2014)引入4PCS算法的思想，將關(guān)鍵點(diǎn)特征應(yīng)用到4PCS算法，從而開發(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)的匹配，自然選擇過程允許滿足相互剛性約束的匹配點(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)系，也代表著最佳的變換方式。

上述方法適合于需要通過多對(duì)特征對(duì)應(yīng)關(guān)系才能確定變換的條件下，對(duì)于一些線特征和面特征只需要更少的對(duì)應(yīng)特征就能確定變換矩陣。

Stamos和Allen(2002)設(shè)計(jì)的線特征兩兩之間就可以確定一個(gè)變換矩陣，通過閾值過濾線的長度和平面大小的比率不滿足條件的特征，再通過閾值驗(yàn)證其他對(duì)是否匹配，迭代找到最佳匹配。Yang等人(2016)將得到的語義線特征組合為三角對(duì)，用結(jié)合線特征的三種約束獲得相似的三角對(duì)，用幾何一致性測試除去一些錯(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)即可確定變換矩陣，通過建立kd-tree尋找近似特征，又通過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)方法中各種形式的特征的特征檢測、特征描述和特征匹配的經(jīng)典方法。

本文僅做學(xué)術(shù)分享，如有侵權(quán)，請(qǐng)聯(lián)系刪文。

3D視覺工坊精品課程官網(wǎng)：3dcver.com

1.面向自動(dòng)駕駛領(lǐng)域的多傳感器數(shù)據(jù)融合技術(shù)

2.面向自動(dòng)駕駛領(lǐng)域的3D點(diǎn)云目標(biāo)檢測全棧學(xué)習(xí)路線！(單模態(tài)+多模態(tài)/數(shù)據(jù)+代碼)
3.徹底搞透視覺三維重建：原理剖析、代碼講解、及優(yōu)化改進(jìn)
4.國內(nèi)首個(gè)面向工業(yè)級(jí)實(shí)戰(zhàn)的點(diǎn)云處理課程
5.激光-視覺-IMU-GPS融合SLAM算法梳理和代碼講解
6.徹底搞懂視覺-慣性SLAM：基于VINS-Fusion正式開課啦
7.徹底搞懂基于LOAM框架的3D激光SLAM: 源碼剖析到算法優(yōu)化
8.徹底剖析室內(nèi)、室外激光SLAM關(guān)鍵算法原理、代碼和實(shí)戰(zhàn)(cartographer+LOAM +LIO-SAM)

9.從零搭建一套結(jié)構(gòu)光3D重建系統(tǒng)[理論+源碼+實(shí)踐]

10.單目深度估計(jì)方法：算法梳理與代碼實(shí)現(xiàn)

11.自動(dòng)駕駛中的深度學(xué)習(xí)模型部署實(shí)戰(zhàn)

12.相機(jī)模型與標(biāo)定(單目+雙目+魚眼）

13.重磅！四旋翼飛行器：算法與實(shí)戰(zhàn)

14.ROS2從入門到精通：理論與實(shí)戰(zhàn)

15.國內(nèi)首個(gè)3D缺陷檢測教程：理論、源碼與實(shí)戰(zhàn)

重磅！3DCVer-學(xué)術(shù)論文寫作投稿?交流群已成立

掃碼添加小助手微信，可申請(qǐng)加入3D視覺工坊-學(xué)術(shù)論文寫作與投稿?微信交流群，旨在交流頂會(huì)、頂刊、SCI、EI等寫作與投稿事宜。

同時(shí)也可申請(qǐng)加入我們的細(xì)分方向交流群，目前主要有3D視覺、CV&深度學(xué)習(xí)、SLAM、三維重建、點(diǎn)云后處理、自動(dòng)駕駛、多傳感器融合、CV入門、三維測量、VR/AR、3D人臉識(shí)別、醫(yī)療影像、缺陷檢測、行人重識(shí)別、目標(biāo)跟蹤、視覺產(chǎn)品落地、視覺競賽、車牌識(shí)別、硬件選型、學(xué)術(shù)交流、求職交流、ORB-SLAM系列源碼交流、深度估計(jì)等微信群。

一定要備注：研究方向+學(xué)校/公司+昵稱，例如：”3D視覺?+ 上海交大 + 靜靜“。請(qǐng)按照格式備注，可快速被通過且邀請(qǐng)進(jìn)群。原創(chuàng)投稿也請(qǐng)聯(lián)系。

▲長按加微信群或投稿

▲長按關(guān)注公眾號(hào)

3D視覺從入門到精通知識(shí)星球：針對(duì)3D視覺領(lǐng)域的視頻課程（三維重建系列、三維點(diǎn)云系列、結(jié)構(gòu)光系列、手眼標(biāo)定、相機(jī)標(biāo)定、激光/視覺SLAM、自動(dòng)駕駛等）、知識(shí)點(diǎn)匯總、入門進(jìn)階學(xué)習(xí)路線、最新paper分享、疑問解答五個(gè)方面進(jìn)行深耕，更有各類大廠的算法工程人員進(jìn)行技術(shù)指導(dǎo)。與此同時(shí)，星球?qū)⒙?lián)合知名企業(yè)發(fā)布3D視覺相關(guān)算法開發(fā)崗位以及項(xiàng)目對(duì)接信息，打造成集技術(shù)與就業(yè)為一體的鐵桿粉絲聚集區(qū)，近4000星球成員為創(chuàng)造更好的AI世界共同進(jìn)步，知識(shí)星球入口：

學(xué)習(xí)3D視覺核心技術(shù)，掃描查看介紹，3天內(nèi)無條件退款

?圈里有高質(zhì)量教程資料、答疑解惑、助你高效解決問題

覺得有用，麻煩給個(gè)贊和在看~??

總結(jié)

以上是生活随笔為你收集整理的非学习的点云配准方法汇总的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。