日本无码免费高清在线|成人日本在线观看高清|A级片免费视频操逼欧美|全裸美女搞黄色大片网站|免费成人a片视频|久久无码福利成人激情久久|国产视频一二国产在线v|av女主播在线观看|五月激情影音先锋|亚洲一区天堂av

  • 手機(jī)站
  • 小程序

    汽車測(cè)試網(wǎng)

  • 公眾號(hào)

    • 汽車測(cè)試網(wǎng)

    • 在線課堂

    • 電車測(cè)試

FAST-LIO2: 快速直接的激光雷達(dá)-慣性里程計(jì)

2021-09-12 21:53:49·  來源：同濟(jì)智能汽車研究所  
　
編者按：SLAM技術(shù)廣泛應(yīng)用于室內(nèi)或室外、城市或野外等不同的無人駕駛應(yīng)用場(chǎng)景。激光雷達(dá)是最常使用的傳感器之一，激光雷達(dá)可以提取環(huán)境中微小的細(xì)節(jié)特征。然而，
編者按：SLAM技術(shù)廣泛應(yīng)用于室內(nèi)或室外、城市或野外等不同的無人駕駛應(yīng)用場(chǎng)景。激光雷達(dá)是最常使用的傳感器之一，激光雷達(dá)可以提取環(huán)境中微小的細(xì)節(jié)特征。然而，激光不適用于缺少結(jié)構(gòu)特征的環(huán)境中，比如四壁光滑的通道，且純激光算法在快速運(yùn)動(dòng)或復(fù)雜場(chǎng)景下，僅使用激光雷達(dá)測(cè)程容易出現(xiàn)問題。因此，激光雷達(dá)總是會(huì)與慣性測(cè)量單元(IMU)耦合,以提高系統(tǒng)的穩(wěn)健性。
本文譯自：《FAST-LIO2: Fast Direct LiDAR-inertial Odometry》
文章來源：arXiv preprint arXiv:2107.06829, 2021
作者：Wei Xu, Yixi Cai, Dongjiao He, Jiarong Lin, Fu Zhang
原文鏈接：https://arxiv.org/abs/2107.06829
摘要：本文介紹了FAST-LIO2：一種快速、穩(wěn)健且通用的激光慣性里程計(jì)框架。FAST-LIO2建立在高效的緊耦合迭代卡爾曼濾波器的基礎(chǔ)上，有兩個(gè)關(guān)鍵的創(chuàng)新之處，可以實(shí)現(xiàn)快速、穩(wěn)健和準(zhǔn)確的激光雷達(dá)導(dǎo)航（和建圖）。第一個(gè)是不提取特征直接將原始點(diǎn)配準(zhǔn)到地圖（并隨后更新地圖，即建圖），而這使得環(huán)境中的細(xì)微特征能夠被利用，從而提高匹配準(zhǔn)確性，且取消提取特征模塊能夠適應(yīng)有著不同掃描模式的新興雷達(dá)；第二個(gè)主要新穎之處是通過增量k-d樹（ikd-樹）數(shù)據(jù)結(jié)構(gòu)維護(hù)地圖。ikd-tree支持增量更新（即點(diǎn)插入、刪除）和動(dòng)態(tài)平衡。與現(xiàn)有的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)（八叉樹、R*-tree、nanoflann k-d 樹）相比，ikd-樹實(shí)現(xiàn)了優(yōu)越的整體性能，同時(shí)自然地支持在樹上的下采樣。我們對(duì)來自各種開放激光雷達(dá)數(shù)據(jù)集的19個(gè)序列進(jìn)行了詳盡的基準(zhǔn)比較。FAST-LIO2始終能保持更高的準(zhǔn)確度，但是計(jì)算負(fù)載比其他最先進(jìn)的激光慣性導(dǎo)航系統(tǒng)低得多。此外，文章也利用具有小視場(chǎng)角的固態(tài)激光雷達(dá)進(jìn)行了各種真實(shí)世界的實(shí)驗(yàn)。總體而言，F(xiàn)AST-LIO2計(jì)算效率高（例如，在大型室外環(huán)境中高達(dá)100Hz的里程計(jì)和建圖）、穩(wěn)?。ɡ?，在雜亂的室內(nèi)環(huán)境中可靠的姿態(tài)估計(jì)，旋轉(zhuǎn)速度高達(dá)1000度/秒），適用廣泛（即，適用于多線旋轉(zhuǎn)和固態(tài)激光雷達(dá)、無人機(jī)和手持平臺(tái)，以及基于Intel和ARM的處理器），同時(shí)仍能實(shí)現(xiàn)比現(xiàn)有方法更高的精度。我們?cè)贕ithub上開源了FAST-LIO2和ikd-樹的數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)。
關(guān)鍵詞：激光雷達(dá)慣性里程計(jì)，緊耦合迭代卡爾曼濾波，ikd-樹
1 引言
構(gòu)建未知區(qū)域的稠密三維（3D）地圖環(huán)境的實(shí)時(shí)性，同時(shí)在地圖中定位（即SLAM）對(duì)于自主機(jī)器人在未知環(huán)境中的安全導(dǎo)航至關(guān)重要。定位提供了機(jī)器人車載控制器的狀態(tài)反饋，同時(shí)，稠密的3D地圖提供了有關(guān)軌跡規(guī)劃環(huán)境的必要信息（即自由空間freespace和障礙物）?；谝曈X的SLAM[1]–[4]在定位方面非常精確，但是只維護(hù)一個(gè)稀疏的特征地圖，并且會(huì)遭受照明變化和嚴(yán)重的運(yùn)動(dòng)模糊的影響。另一方面，僅利用機(jī)器人上搭載的計(jì)算資源，進(jìn)行基于視覺傳感器的實(shí)時(shí)密集、高分辨率、高精度的建圖[5]–[8]，仍然是一個(gè)巨大的挑戰(zhàn)。
由于能夠提供直接、密集、活躍和精確的環(huán)境深度信息，Lidar（激光雷達(dá)）傳感器已成為對(duì)于機(jī)器人另一種必要的傳感器[9,10]。近十年來，激光雷達(dá)在許多自動(dòng)機(jī)器人中發(fā)揮著越來越重要的作用，如自動(dòng)駕駛汽車[11]和自動(dòng)無人機(jī)[12,13]。在最近激光雷達(dá)技術(shù)發(fā)展中，已經(jīng)實(shí)現(xiàn)了商業(yè)化、輕量批量生產(chǎn)、更具成本效益（成本范圍類似于全球快門相機(jī)）、性能高（在數(shù)百米測(cè)量范圍內(nèi)擁有厘米精度）的固態(tài)激光雷達(dá)[14,15]引起了廣泛的研究興趣[16]–[20]。雷達(dá)成本、尺寸、重量、功率的顯著降低具有使現(xiàn)有和新興機(jī)器人應(yīng)用領(lǐng)域受益的潛力。
采用基于激光雷達(dá)SLAM方法的核心要求是利用有限機(jī)載計(jì)算資源獲得準(zhǔn)確、低延遲的狀態(tài)估計(jì)和密集的3D地圖。然而，高效、準(zhǔn)確的激光雷達(dá)里程計(jì)和地圖繪制仍是有挑戰(zhàn)性的問題：1）當(dāng)前的激光雷達(dá)傳感器每秒產(chǎn)生數(shù)十萬到數(shù)百萬的三維點(diǎn)，利用有限的車載計(jì)算資源處理如此大量的實(shí)時(shí)數(shù)據(jù)，要求具有較高的計(jì)算效率的激光雷達(dá)里程計(jì)方法。2）為了減少計(jì)算量，特征點(diǎn)，例如邊緣點(diǎn)或平面點(diǎn)，通常是基于局部平滑度提取的。但是，特征提取模塊的性能容易受環(huán)境影響。例如，在沒有大量平面或長(zhǎng)邊的結(jié)構(gòu)稀少的環(huán)境中，將導(dǎo)致提取很少的特征點(diǎn)。這種情況在新興固態(tài)激光雷達(dá)典型的小視場(chǎng)角下會(huì)大大惡化 [16]。此外，特征提取也因激光雷達(dá)的不同而有所不同，具體取決于掃描模式（例如，旋轉(zhuǎn)、基于prism[15]、基于MEMS[14]）和點(diǎn)密度。所以采用激光雷達(dá)里程計(jì)方法通常需要很多手動(dòng)提取的工作;3)激光雷達(dá)點(diǎn)通常在連續(xù)運(yùn)動(dòng)按順序采樣，，這個(gè)過程會(huì)產(chǎn)生顯著的運(yùn)動(dòng)失真，影響里程計(jì)和建圖的性能，尤其是當(dāng)運(yùn)動(dòng)很劇烈時(shí)。慣性測(cè)量單元(IMU)可以緩解這個(gè)問題，但引入了額外需要估計(jì)的狀態(tài)量（例如，偏差，外參）；4) 在一次掃描中激光雷達(dá)通常有很長(zhǎng)的測(cè)量范圍（例如，數(shù)百米）但分辨率相當(dāng)?shù)?。點(diǎn)云測(cè)量結(jié)果稀疏地分布在一個(gè)大型3D空間中，所以需要一個(gè)大而密集的地圖來配準(zhǔn)這些稀疏點(diǎn)。此外，該地圖需要支持有效的搜索且同時(shí)實(shí)時(shí)更新新的測(cè)量數(shù)據(jù)。維持這樣的地圖是一項(xiàng)非常具有挑戰(zhàn)性的任務(wù)，且不同于視覺測(cè)量的圖像測(cè)量具有高分辨率，因此只需要稀疏特征圖，在地圖上特征點(diǎn)，只要它落在視場(chǎng)角中總能找到對(duì)應(yīng)關(guān)系。
在這項(xiàng)工作中，我們通過兩個(gè)關(guān)鍵新技術(shù)來解決這些問題：增量k-d樹和直接配準(zhǔn)點(diǎn)。更具體地說，我們的貢獻(xiàn)如下：1）我們開發(fā)增量 k-d 樹數(shù)據(jù)結(jié)構(gòu)ikd-樹，以有效表示大型密集點(diǎn)云圖。除了高效的最近鄰搜索，新的數(shù)據(jù)結(jié)構(gòu)支持增量地圖更新（即點(diǎn)插入、樹上的下采樣，點(diǎn)刪除）和以最小的計(jì)算成本進(jìn)行動(dòng)態(tài)平衡。這些特性使 ikd-樹非常適合應(yīng)用于激光雷達(dá)里程計(jì)和建圖，實(shí)現(xiàn)了100 Hz 里程計(jì)和在計(jì)算受限平臺(tái)的建圖，例如基于 Intel i7 的微型無人機(jī)板載計(jì)算機(jī)和甚至于 ARM 的處理器。Ikd-樹數(shù)據(jù)結(jié)構(gòu)工具箱已經(jīng)在 Github上開源。2) 由于在ikd-樹上計(jì)算效率的提高， 我們直接將原始點(diǎn)配準(zhǔn)到地圖上，這使得幀間配準(zhǔn)即使是在劇烈的運(yùn)動(dòng)和非?；靵y的環(huán)境中也準(zhǔn)確可靠。我們稱這種基于原始點(diǎn)的配準(zhǔn)方法為直接法，類比于視覺SLAM[21]。去除手動(dòng)特征提取使系統(tǒng)自然適用于不同的激光雷達(dá)傳感器；3）我們將這兩個(gè)關(guān)鍵技術(shù)整合到我們最近開發(fā)的一個(gè)完全緊耦合的激光雷達(dá)慣性里程計(jì)系統(tǒng) FAST-LIO [22]。該系統(tǒng)通過使用 IMU的嚴(yán)格反向傳播來修正每個(gè)點(diǎn)的運(yùn)動(dòng)并通過流形迭代卡爾曼濾波器估計(jì)系統(tǒng)的全部狀態(tài)量。為了進(jìn)一步加速計(jì)算，一種新的計(jì)算卡爾曼增益的數(shù)學(xué)等價(jià)公式被用于降低計(jì)算復(fù)雜度狀態(tài)的維度（而非測(cè)量量）。新系統(tǒng)被稱為 FAST-LIO2 并且在Github上是開源的；4）我們開展各種試驗(yàn)去評(píng)估 ikd-tree有效性、直接點(diǎn)配準(zhǔn)法和整個(gè)系統(tǒng)。在18個(gè)不同大小的序列上的實(shí)驗(yàn)表明，ikd-Tree相對(duì)于現(xiàn)有的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)（八叉樹、R*-tree、nanoflann k-d 樹）在激光雷達(dá)里程計(jì)和地圖的應(yīng)用中實(shí)現(xiàn)了卓越的性能。在19個(gè)來自不同激光雷達(dá)數(shù)據(jù)集的序列上詳盡的基準(zhǔn)對(duì)比表明FAST-LIO2始終能保持更高的準(zhǔn)確度，但具有比其他最先進(jìn)激光慣性導(dǎo)航系統(tǒng)的計(jì)算負(fù)載低得多。我們最后展示FAST-LIO2在挑戰(zhàn)由具有非常小的視場(chǎng)角的新興固態(tài)激光雷達(dá)收集的真實(shí)世界數(shù)據(jù)，包括劇烈運(yùn)動(dòng)（如旋轉(zhuǎn)速度 高達(dá)1000度/秒）和結(jié)構(gòu)較少的環(huán)境中。
其余文章組織如下：在第Ⅱ章，我們討論了相關(guān)背景的研究工作。我們分別在章節(jié)Ⅲ，Ⅳ和Ⅴ給出概述系統(tǒng)流程和每個(gè)關(guān)鍵部分的細(xì)節(jié)。第Ⅵ章中展示在開放數(shù)據(jù)集上的對(duì)比。在第Ⅶ章展示實(shí)際實(shí)驗(yàn)。最后是在第Ⅷ章的結(jié)論。
2 相關(guān)工作
A.激光雷達(dá)（-慣性系統(tǒng)）里程計(jì)
3D激光雷達(dá)SLAM的現(xiàn)有工作通常繼承了在[23]中提出的LOAM結(jié)構(gòu)。它由三個(gè)主要部分組成：特征提取、里程計(jì)和建圖。為了減少計(jì)算量，新的一幀點(diǎn)云首先被基于局部平滑度的特征點(diǎn)（即邊和平面）提取模塊加工處理。然后，里程計(jì)模塊（幀間）匹配來自連續(xù)兩幀點(diǎn)云的特征點(diǎn)，獲得粗略但實(shí)時(shí)（如10Hz）的激光雷達(dá)姿態(tài)里程計(jì)。通過里程計(jì)，多幀點(diǎn)云組合成一個(gè)掃描，然后該掃描被配準(zhǔn)并合并到全局地圖（即，建圖）。在此過程中，地圖點(diǎn)被用于構(gòu)建一個(gè)k-d樹，這使得一個(gè)非常有效的k近鄰搜索(kNN搜索)成為可能。然后，LOAM通過迭代最近點(diǎn)(ICP)[24]–[26]方法實(shí)現(xiàn)點(diǎn)云配準(zhǔn)，具體為：在其中每次迭代中，在目標(biāo)點(diǎn)云的一些線或面上選取幾個(gè)和原點(diǎn)云最近的點(diǎn)來實(shí)現(xiàn)ICP的配準(zhǔn)。為了降低k-d樹建設(shè)的時(shí)間成本，算法以規(guī)定的分辨率對(duì)地圖點(diǎn)進(jìn)行下采樣。優(yōu)化的建圖過程通常以低得多的速率(1-2Hz)進(jìn)行。
后續(xù)的激光雷達(dá)里程計(jì)工作保持了一個(gè)類似于LOAM的框架。例如，Lego-LOAM [27]引入了一種減少計(jì)算量的地面點(diǎn)分割方法以及減少長(zhǎng)期漂移的回環(huán)模塊。此外，LOAM-Livox[16]將LOAM適用于新興的固態(tài)激光雷達(dá)。為了處理小視場(chǎng)角和非重復(fù)掃描的問題，即從連續(xù)兩幀點(diǎn)云中提取的特征點(diǎn)幾乎沒有對(duì)應(yīng)關(guān)系，LOAM-Livox通過直接將新的一幀點(diǎn)云直接配準(zhǔn)到全局地圖中來獲得的里程計(jì)。這種直接將一幀點(diǎn)云配準(zhǔn)到地圖的方法提高了里程計(jì)的精度，但代價(jià)是在每一步構(gòu)建中更新地圖點(diǎn)的k-d樹的計(jì)算量增加。
IMU可以通過提供ICP要求的良好的初始位姿來顯著提高激光雷達(dá)里程計(jì)的精度和魯棒性。此外，高頻率的IMU測(cè)量數(shù)據(jù)可以有效地補(bǔ)償激光點(diǎn)云幀中的運(yùn)動(dòng)失真。LION[28]是一種松耦合的激光雷達(dá)慣性SLAM方法，它保留了LOAM中的幀間配準(zhǔn)方法（scan-to-scan registration），并在里程計(jì)中引入了可觀測(cè)性檢查以降低點(diǎn)數(shù)，從而節(jié)省計(jì)算量。更多的緊耦合的激光雷達(dá)慣性融合工作[17,29]–[31]在由固定數(shù)量的最近的激光點(diǎn)云幀（或關(guān)鍵幀）組成的在小尺寸局部地圖中執(zhí)行里程計(jì)。與幀間配準(zhǔn)的方法相比，幀到局部地圖的配準(zhǔn)通常因使用更多最近的信息而更加準(zhǔn)確。更具體地說，LIOM[29]提出了一種緊耦合激光雷達(dá)慣性融合方法，它在里程計(jì)中引入了IMU預(yù)積分。LILIOM[17]開發(fā)了一種新的特征提取方法對(duì)于非重復(fù)掃描的激光雷達(dá)，并在一個(gè)由20幀激光點(diǎn)云組成的小地圖中執(zhí)行幀間配準(zhǔn)以獲得里程計(jì)。LIO-SAM[30]的里程計(jì)需要一個(gè)9軸IMU來產(chǎn)生姿態(tài)測(cè)量，這個(gè)測(cè)量量是在一個(gè)小的局部地圖中進(jìn)行幀間配準(zhǔn)的前提。LINS[31]將緊耦合迭代卡爾曼濾波器和機(jī)器人中心公式引入到里程計(jì)中的激光雷達(dá)姿態(tài)優(yōu)化當(dāng)中。因?yàn)樯鲜龉ぷ鳛榱双@取實(shí)時(shí)的性能通常構(gòu)建小的局部地圖，所以里程計(jì)漂移地很快，需要進(jìn)行低速率的建圖過程，例如建圖細(xì)化（LINS[31]），滑動(dòng)窗口關(guān)節(jié)優(yōu)化（LILI-OM[17]和LIOM[29]）和 因子圖優(yōu)化[32]（LIO-SAM[30]）。與上述方法相比，F(xiàn)AST-LIO[22]引入了一種形式化的反向傳播，它精確考慮一幀點(diǎn)云中的每一個(gè)點(diǎn)的采樣時(shí)間，并通過IMU測(cè)量值驅(qū)動(dòng)的嚴(yán)格運(yùn)動(dòng)學(xué)模型對(duì)運(yùn)動(dòng)畸變進(jìn)行補(bǔ)償。此外，它還采用新的卡爾曼增益公式將計(jì)算復(fù)雜度從測(cè)量維度降低到狀態(tài)維度。這個(gè)新公式在數(shù)學(xué)上被證明等價(jià)于傳統(tǒng)的公式，但計(jì)算量減少了好幾個(gè)數(shù)量級(jí)。計(jì)算的效率顯著提高允許在里程計(jì)中進(jìn)行直接并實(shí)時(shí)的一幀點(diǎn)云到地圖的配準(zhǔn)，并在每一步中更新地圖（即建圖）。它使用所有最近幾幀點(diǎn)云中的點(diǎn)進(jìn)行及時(shí)建圖，這保證了里程計(jì)的精度。但是，為了防止構(gòu)建地圖的k-d樹的時(shí)間越來越長(zhǎng)，系統(tǒng)只能在小型環(huán)境中工作（例如，數(shù)百米）。
FAST-LIO2建立在FAST-LIO[22]的基礎(chǔ)上，因此繼承了緊耦合的融合框架，尤其是利用反向傳播解決運(yùn)動(dòng)失真與利用快速卡爾曼增益計(jì)算提高效率。為了系統(tǒng)地解決計(jì)算量增長(zhǎng)的問題，我們提出了一種新的數(shù)據(jù)結(jié)構(gòu)ikd-樹，它支持在每一步中更新增量地圖和高效的kNN搜尋。受益于計(jì)算量的顯著減少，里程計(jì)是通過將原始激光雷達(dá)點(diǎn)直接配準(zhǔn)到地圖上來執(zhí)行的，從而提高了里程計(jì)和地圖繪制的準(zhǔn)確性和魯棒性，尤其是當(dāng)新的一幀點(diǎn)云中沒有突出特征時(shí)（例如，由于小視場(chǎng)和/或無結(jié)構(gòu)環(huán)境)。與上述均使用特征點(diǎn)的緊耦合激光雷達(dá)慣性方法相比，我們的方法更加輕量級(jí)，并可提高建圖頻率和里程計(jì)的精確性，并且無需為特征提取進(jìn)行參數(shù)調(diào)整。
在我們的工作中直接注冊(cè)原始點(diǎn)的想法已經(jīng)在LION [28]中進(jìn)行了探索，然而，如上所述，LION是一種松散耦合的方法。這個(gè)想法也很類似于[26]中提出的廣義ICP（G-ICP），在其中，一個(gè)點(diǎn)被注冊(cè)到地圖中的小局部平面。這最終假設(shè)環(huán)境是平滑的，因此可以被視為局部平面。然而，廣義ICP的計(jì)算量通常較大[33]。其他基于正態(tài)分布變換（NDT）[34]–[36]的工作也注冊(cè)原始點(diǎn)，但NDT與ICP相比，有著更低的穩(wěn)定性，在某些場(chǎng)景中可能會(huì)失效 [36]。
B.建圖中的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)
為了實(shí)現(xiàn)實(shí)時(shí)建圖，需要一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)來支持增量更新和高效的kNN搜索。通常，kNN搜索問題可以通過為數(shù)據(jù)點(diǎn)建立空間索引來解決，具體可以分為兩類：數(shù)據(jù)分割和空間分割。一個(gè)眾所周知的數(shù)據(jù)分割的實(shí)例是 R-樹 [37]，它基于空間中的數(shù)據(jù)接近度將數(shù)據(jù)聚類成潛在的重疊軸對(duì)齊立方體。各種R樹按照線性、二次和指數(shù)復(fù)雜性分割節(jié)點(diǎn)，所有這些樹都支持最近鄰搜索和點(diǎn)式更新（插入，刪除，和重新插入）。此外，R-樹還支持在給定搜索區(qū)域或滿足給定條件下進(jìn)行搜索目標(biāo)數(shù)據(jù)點(diǎn)。R-樹的另一個(gè)版本是-樹，它的性能優(yōu)于原來的數(shù)[38]。-樹按最小重疊標(biāo)準(zhǔn)進(jìn)行插入，并對(duì)節(jié)點(diǎn)分割算法應(yīng)用強(qiáng)制重插入原則。
八叉樹[39]和k維樹（k-d樹）[40]是兩種眾所周知的數(shù)據(jù)結(jié)構(gòu)，用于分割kNN搜索的空間。八叉樹通過遞歸地將空間分成八個(gè)軸對(duì)齊的立方體來組織三維點(diǎn)云。當(dāng)立方體為空或滿足停止規(guī)則（例如，最小分辨率或最小點(diǎn)數(shù)量）時(shí)，立方體的分割停止。當(dāng)進(jìn)行進(jìn)一步細(xì)分時(shí)，如果必要的話，新點(diǎn)將被插入到八叉樹上的葉節(jié)點(diǎn)。八叉樹支持kNN搜索和框式搜索，后者返回給定軸對(duì)齊長(zhǎng)方體中的數(shù)據(jù)點(diǎn)。
k-d樹是一種二叉樹，其節(jié)點(diǎn)表示一個(gè)軸對(duì)齊的超平面，將空間分割為兩部分。在標(biāo)準(zhǔn)構(gòu)造規(guī)則中，分割節(jié)點(diǎn)被選擇為沿著最長(zhǎng)維度的中間點(diǎn)，以實(shí)現(xiàn)緊湊的空間分割[41]。在考慮建圖中低維和存儲(chǔ)在主存上的數(shù)據(jù)特性時(shí)，比較研究表明k-d樹在kNN問題中取得了最好的性能[42, 43]。然而，在 k-d 樹中插入新點(diǎn)和刪除舊點(diǎn)會(huì)降低樹的平衡性；因此，需要重建以重新平衡樹。使用k-d 樹庫的建圖方法，例如ANN [44]、libnabo[43]和FLANN [45]，完全重新構(gòu)建 k-d 樹以更新地圖，但這會(huì)導(dǎo)致大量計(jì)算。雖然基于硬件的重建k-d樹的方法已經(jīng)在三維圖形應(yīng)用中得到徹底研究[46]–[49]，但所提出的方法嚴(yán)重依賴于計(jì)算資源，而這些資源通常局限于機(jī)器人應(yīng)用的機(jī)載計(jì)算機(jī)。Galperin 等人沒有完全重建樹，而是提出了一種替罪羊 k-d 樹，其中重新構(gòu)建被部分應(yīng)用于不平衡的子樹，以保持整個(gè)樹的松散平衡特性[50]。啟用增量操作的另一種方法是以類似于 [51, 52]的對(duì)數(shù)方法維護(hù)一組k-d樹，并重新構(gòu)建一個(gè)精心選擇的子集。Bkd-樹在主存儲(chǔ)器中維護(hù)了一個(gè)最大大小為M的k-d樹，在外部存儲(chǔ)器中維護(hù)了一組k-d樹，其中第i棵樹的大小為[53]。當(dāng)樹滿時(shí)，算法從到提取點(diǎn)，并插入到第一個(gè)空樹中。最先進(jìn)的nanoflann k-d樹利用對(duì)數(shù)結(jié)構(gòu)進(jìn)行增量更新，而惰性標(biāo)簽只標(biāo)記刪除的點(diǎn)，而不從樹中刪除它們(因此節(jié)省內(nèi)存)[54]。
我們提出了一種基于替罪k-d樹[50]的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，命名為增量k-d樹（ikd-樹），以實(shí)現(xiàn)實(shí)時(shí)建圖。我們的ikd-Tree支持點(diǎn)式插入和樹上的下采樣，這是建圖中的常見要求，而在將新點(diǎn)插入其他動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)之前，必須在外部進(jìn)行下采樣。當(dāng)需要去除給定形狀的規(guī)則區(qū)域（如長(zhǎng)方體）中不必要的點(diǎn)時(shí)，現(xiàn)有的R-樹和八叉樹可以實(shí)現(xiàn)在給定空間內(nèi)搜索點(diǎn)并逐個(gè)刪除它們，而普通的k-d樹使用半徑搜索以獲得點(diǎn)索引。與這種間接且低效的方法相比，ikd-Tree 通過維護(hù)范圍信息和惰性標(biāo)簽直接刪除給定軸對(duì)齊長(zhǎng)方體中的點(diǎn)。標(biāo)記為“已刪除”的點(diǎn)將在重建過程中被刪除。此外，盡管在應(yīng)用部分重平衡方法(例如替罪羊k-d樹[50]和納米樹k-d樹[54])之后，增量更新是可用的，但是當(dāng)重新構(gòu)建大量點(diǎn)時(shí)，使用k-d樹的建圖方法受到間歇性延遲的影響。為了克服這一點(diǎn)，ikd-Tree通過并行重建避免了自身的顯著延遲，同時(shí)保證了主線程的實(shí)時(shí)性和準(zhǔn)確性。
分享到：
 
反對(duì) 0 舉報(bào) 0 收藏 0 評(píng)論 0
滬ICP備11026917號(hào)-25