原創(chuàng) | 文 BFT機(jī)器人

《TEASER: Fast and Certifiable Point Cloud Registration》是一篇由Yang et al. 在IEEE Transactions on Robotics雜志上發(fā)表的研究論文，于2021年4月出版。這篇論文提出了兩種快速且可驗證的點云配準(zhǔn)算法：TEASER和TEASER++，這兩種算法能夠處理高異常值率的情況，并在點云配準(zhǔn)任務(wù)中表現(xiàn)出色。本文對論文內(nèi)容進(jìn)行詳細(xì)的分析解讀，著重介紹了論文的背景、目標(biāo)、方法、實驗結(jié)果和貢獻(xiàn)。

01

背景和目標(biāo)

點云配準(zhǔn)是計算機(jī)視覺和機(jī)器人領(lǐng)域中一個重要的問題，它涉及將兩個或多個點云數(shù)據(jù)集對齊，以獲得它們之間的相對姿態(tài)變換。然而，現(xiàn)實世界中的點云數(shù)據(jù)通常包含噪聲和異常值，這使得點云配準(zhǔn)任務(wù)變得更加困難。

因此，對于處理高異常值率的點云配準(zhǔn)問題，研究人員需要開發(fā)更加魯棒和可靠的算法。目標(biāo)就是解決高異常值率的點云配準(zhǔn)問題，提出兩種快速且可驗證的算法：TEASER和TEASER++。TEASER算法通過求解大規(guī)模半定規(guī)劃問題來實現(xiàn)準(zhǔn)確的魯棒配準(zhǔn)，但計算復(fù)雜度較高。

為了加速配準(zhǔn)過程，作者提出了TEASER++算法，它避免了求解半定規(guī)劃問題，從而大大提高了運(yùn)行速度。此外，作者還引入了“可驗證感知”這一新興研究領(lǐng)域的概念，旨在為機(jī)器感知算法提供更高的可靠性和安全性。

02

工作內(nèi)容

1. TEASER算法

TEASER算法是一種準(zhǔn)確且魯棒的點云配準(zhǔn)算法。它利用估計理論、幾何學(xué)、圖論和優(yōu)化等多個領(lǐng)域的思想，實現(xiàn)了對高異常值率數(shù)據(jù)的魯棒處理。

算法主要包含以下幾個步驟：

• 隨機(jī)選擇一些點對作為初始的匹配對。

  
  

• 根據(jù)初始匹配對構(gòu)建一個大圖，并使用圖論中的最大團(tuán)算法找出最大的一組一致的匹配對。

  
  

• 基于最大團(tuán)中的匹配對，通過最小二乘法計算剛體變換。

  
  

• 利用已估計的剛體變換更新匹配對，并迭代執(zhí)行上述步驟，直到收斂。

然而，由于TEASER需要求解大規(guī)模半定規(guī)劃問題，算法的計算復(fù)雜度較高，不適用于大規(guī)模點云數(shù)據(jù)。

2. TEASER++算法

為了加速配準(zhǔn)過程，作者提出了TEASER++算法，它是TEASER算法的優(yōu)化版本。TEASER++算法在保持準(zhǔn)確性和魯棒性的基礎(chǔ)上，避免了求解大規(guī)模半定規(guī)劃問題，從而大大提高了運(yùn)行速度。TEASER++算法的關(guān)鍵在于使用圖論中的最大團(tuán)算法來尋找一致的匹配對，從而避免了求解半定規(guī)劃問題。

TASER++算法的流程如下：

• 對所有點對計算剛體變換，并將它們構(gòu)建為一個圖。

  
  

• 利用最大團(tuán)算法找出最大一致子圖，即最大的一組一致的匹配對。

  
  

• 利用最大一致子圖來估計剛體變換，并使用最小二乘法進(jìn)行優(yōu)化。

  
  

• 更新匹配對并迭代執(zhí)行上述步驟，直到收斂。

TEASER++算法不僅保持了TEASER算法的準(zhǔn)確性和魯棒性，而且大大提高了運(yùn)行速度，特別適用于處理高異常值率的大規(guī)模點云數(shù)據(jù)。

3. 可驗證感知

本文還介紹了“可驗證感知”這一新興研究領(lǐng)域的概念?？沈炞C感知旨在為機(jī)器感知算法提供更高的可靠性和安全性?？沈炞C感知的關(guān)鍵在于開發(fā)可驗證的算法，即能夠提供對結(jié)果可靠性的證明，從而增強(qiáng)對感知算法的信任。

03

實驗結(jié)果

論文通過多個實驗驗證了TEASER和TEASER++算法的性能。實驗結(jié)果表明，這兩種算法在標(biāo)準(zhǔn)測試數(shù)據(jù)集上優(yōu)于現(xiàn)有的配準(zhǔn)算法，并且能夠在高異常值率下表現(xiàn)出色。

它們不僅可以處理點云配準(zhǔn)問題，還可以用于目標(biāo)姿態(tài)估計、掃描匹配等實際應(yīng)用。同時，作者還提供了一個快速的C++實現(xiàn)供開發(fā)者使用。

在實驗中，TEASER++算法表現(xiàn)出比TEASER算法更快的速度，并且在準(zhǔn)確性和魯棒性方面與TEASER算法相當(dāng)。TEASER++算法還能處理沒有對應(yīng)關(guān)系的點云配準(zhǔn)問題，即使在這種情況下，它的表現(xiàn)仍然優(yōu)于現(xiàn)有的配準(zhǔn)算法。此外，通過證明算法的結(jié)果可靠性，論文還驗證了TEASER++算法的可靠性和安全性，使其成為可驗證感知領(lǐng)域的重要研究方向。

在對比實驗中，作者將TEASER++算法與其他先進(jìn)的點云配準(zhǔn)算法進(jìn)行了比較，包括Go-ICP、RANSAC、Fast Global Registration (FGR)和Generalized-ICP (G-ICP)等。實驗結(jié)果顯示，TEASER++算法在不同數(shù)據(jù)集上均取得了優(yōu)越的配準(zhǔn)性能。特別是在高異常值率的情況下，TEASER++算法明顯優(yōu)于其他算法，這充分說明了它在處理噪聲和異常值時的魯棒性。

此外，論文還對TEASER++算法的運(yùn)行時間進(jìn)行了評估，結(jié)果顯示該算法的運(yùn)行速度非?？?，特別適用于大規(guī)模點云數(shù)據(jù)的配準(zhǔn)任務(wù)。因此，TEASER++算法不僅在準(zhǔn)確性和魯棒性方面表現(xiàn)優(yōu)異，還具備了高效的優(yōu)勢，使得它成為實際應(yīng)用中非常有價值的算法。

04

貢獻(xiàn)

本文的貢獻(xiàn)主要有以下幾點：

1. 提出了TEASER算法和TEASER++算法，這兩種算法能夠處理高異常值率的點云配準(zhǔn)問題，并在準(zhǔn)確性和魯棒性方面表現(xiàn)出色。TEASER++算法作為優(yōu)化版本，在保持準(zhǔn)確性的同時，大大提高了配準(zhǔn)速度，適用于大規(guī)模點云數(shù)據(jù)。

2. 引入了“可驗證感知”這一新興研究領(lǐng)域的概念，探討了機(jī)器感知算法的可靠性和安全性問題。TEASER++算法的可驗證性為可驗證感知領(lǐng)域的研究提供了新的思路和方法。

3. 在多個實驗中驗證了TEASER算法和TEASER++算法的性能，并與其他先進(jìn)算法進(jìn)行了比較。實驗結(jié)果表明，這兩種算法在點云配準(zhǔn)任務(wù)中具備明顯的優(yōu)勢，尤其在處理高異常值率的情況下更為明顯。

4. 提供了快速的C++實現(xiàn)，方便其他研究者和開發(fā)者使用和拓展這兩種算法。

05

結(jié)論

《TEASER: Fast and Certifiable Point Cloud Registration》是一篇在點云配準(zhǔn)領(lǐng)域具有重要意義的論文。通過提出TEASER算法和TEASER++算法，論文解決了高異常值率點云配準(zhǔn)的難題，并在準(zhǔn)確性和魯棒性方面取得了顯著的成果。TEASER++算法作為優(yōu)化版本，不僅保持了準(zhǔn)確性和魯棒性，還大大提高了配準(zhǔn)速度，適用于大規(guī)模點云數(shù)據(jù)。

此外，論文引入了“可驗證感知”領(lǐng)域的概念，強(qiáng)調(diào)了算法可驗證性的重要性，為該領(lǐng)域的研究提供了新的思路和方向。

綜上所述，TEASER算法和TEASER++算法為點云配準(zhǔn)問題的解決提供了有力的工具和方法，并對可驗證感知領(lǐng)域的發(fā)展做出了積極貢獻(xiàn)。該論文的研究成果對于推動計算機(jī)視覺和機(jī)器人領(lǐng)域的發(fā)展具有重要的意義。未來，我們可以期待在這一研究方向上的更多進(jìn)展和應(yīng)用。

作者?| 胡財榮

排版 |?居居手

更多精彩內(nèi)容請關(guān)注公眾號：BFT機(jī)器人

本文為原創(chuàng)文章，版權(quán)歸BFT機(jī)器人所有，如需轉(zhuǎn)載請與我們聯(lián)系。若您對該文章內(nèi)容有任何疑問，請與我們聯(lián)系，將及時回應(yīng)。