博客專欄

EEPW首頁 > 博客 > Clipper: 開源的基于圖論框架的魯棒點云數據關聯方法(ICRA2021)

Clipper: 開源的基于圖論框架的魯棒點云數據關聯方法(ICRA2021)

發(fā)布人:計算機視覺工坊 時間:2021-12-11 來源:工程師 發(fā)布文章

《CLIPPER: A Graph-Theoretic Framework for Robust Data Association》(ICRA 2021 )

基于圖論的點云數據關聯方法,通過尋找最稠密的子圖來尋找一致關聯(內聯),通過投影梯度上升的方法保持低時間復雜度,在斯坦福兔子的嘈雜點與990個異常值關聯和僅10個內部關聯關聯關聯的實例中,該方法成功地在138毫秒內以100%的精度返回了8個內部關聯。

代碼已開源: https://mit-acl.github.io/clipper

Motivation: 點云匹配問題的傳統(tǒng)解決方法是基于高相似性對應對象的傳統(tǒng)線性分配方法,例如匈牙利法或拍賣算法,對高噪聲、高離群值區(qū)域不具有魯棒性,從而會產生不正確的對應。為了提高匹配算法的魯棒性和精確度,作者提出了CLIPPER(一致性連接、剪枝和匹配錯誤矯正)框架,該框架利用對象對之間的幾何一致性概念,可以在極端的離群點存在的情況下下找到正確的對應關系。下圖是CLIPPER算法在不同匹配需求中的應用。

1、.png

Contribution:

提出了一種適用于二元圖和加權圖的內聯關聯選擇優(yōu)化公式。

提出了具有最優(yōu)性保證的NP難優(yōu)化問題的松弛形式。

提出了一種多項式時間算法,用于求解基于投影梯度上升的松弛公式,可擴展到大型數據關聯問題。

Content:

1.一致性圖框架

在有大量離群值和噪聲的情況下進行魯棒數據關聯的過程可以通過一致性圖框架描述。點云配準問題的目標是找到兩組點云之間的旋轉和平移 ,點云點之間關聯的一致性可以在一致性圖的圖論框架中進行評估和表示: 包含有n個關聯對的一致性圖G有n個頂點,即每個頂點都表示一個關聯對,頂點之間的邊表示關聯對間的一致性。下圖展示出了從點云中抽取出一致性關聯圖的過程:

2.png

由于旋轉和平移是保持距離的變換,因此當關聯正確時,一個集合中的點之間的距離應與另一個集合中的點之間的距離相同(在無噪假設中),這個性質可用于評估兩個關聯的幾何一致性,其中G的兩個頂點之間的邊表示關聯匹配的點之間的距離相同,最終上圖中的u1,u2,u4被視為是相互關聯的匹配對。

2.親和矩陣

一個有n個頂點的一致性圖的親和矩陣M是一個nxn的對陳矩陣。對陳線上的值M(i,i)表示關聯i匹配對的數據點之間的相似性,當相似性信息未知的情況下,對陳線的值全部設為1,在這種情況下,M=A+I, A是一致性圖的權重鄰接矩陣。M(i,j)表示第i個匹配對和第j個匹配對之間的幾何一致性(在點云匹配任務中,匹配點之間的距離可以用作幾何一致性的驗證),最終生成的親和矩陣如下:

3.png

3.Clipper算法的優(yōu)化方程

給定代表關聯對的一致性圖和它的親和矩陣后,提出優(yōu)化問題用于查找一致關聯的最密集子集:

4.png

因為M是二分矩陣,所以上述問題可以簡化為一個最大團問題(MCP問題):

5.png

因為MCP問題是一個NP問題,因此,隨著問題規(guī)模的增長,依賴于求解上述優(yōu)化形式的算法在計算上變得難以處理。

將圖的密度定義為邊權重的總和除以頂點數。最稠密子圖是圖頂點及其對應邊的子集,這些頂點及其對應邊具有最高密度。給定一個具有親和矩陣M(具有1個對角項)的圖G ,G 的最稠密子圖可從如下公式獲得:

6.png

可以發(fā)現這個形式和第一個優(yōu)化問題形式很相似,所以第一個優(yōu)化問題形式也可以被解釋為找到一致性連通圖G的最密集的完全連通的子圖。最密集的子圖目標在加權情況下很有用,但是需要與最大邊加權團問題區(qū)分開來,例如,考慮一個加權矩陣M和兩個解的候選U,U’:

7.png

U’是MCP問題形式的解,但是U‘在矩陣M中對應的一致性分數很低,大致在0.2左右,所以在親和矩陣中通過加權方案進行選擇子圖是很好重要的,否則很容易選到低一致性的子圖。

求解第一個公式的主要挑戰(zhàn)是由于問題的二元域和包含u的非線性目標函數導致的問題的組合復雜性,這主要導致在時間有限的情況下很難獲得全局最優(yōu)解,即使是小規(guī)模的點云。一個標準的解決方法是放寬二元域和公式一的約束,以獲得適合快速求解的連續(xù)問題,然后將此解投影回原始問題的域并且約束流形,本文中作者提出的公式一的放寬松弛形式如下:

8.png

直觀地說,當Md(i,j) = ?d時,標量d懲罰目標中ui,uj的聯合選擇量為?2d * ui * uj。因此,隨著 d 的增加,違反約束的u的數量為零。當d>=n的時候,上述形式的解會滿足公式一的約束,即當M(i,j)=0的時候ui * uj=0。

由于公式一是一個NP問題,因此根據初始條件,用于求解公式五的優(yōu)化算法可能會收斂到局部最優(yōu)。為了保證找到全局最優(yōu),需要搜索整個解空間。

4.CLIPPER算法

CLIPPER算法包括兩個步驟, 一是通過使用回溯跟蹤線搜索的投影梯度上升方法獲得公式5的解u; 二是通過選擇 ?ω 最大元素來估計 u 中最密集的聚類,算法偽代碼如下:

9.png

上述算法通過遞增懲罰參數 d( 13 行)并通過梯度上升(7-12 行)求解公式五來尋求可行的子圖。首先投影到u(第9行)到Sn的切線上,并根據這個正交投影移動,為了在搜索空間中快速移動,貪婪地選擇α步長,以便如果有ui要懲罰,漸變步長會導致結果達到正序的邊界(10 行)。在任何一種情況下,如果選擇α太大,則使用回溯行搜索來查找適當的步驟( 11 行)。解被投影回約束流形(12行),梯度上升繼續(xù)。

CLIPPER的最后一步選擇子圖G′(14-15行)中最密集的分量,由于對于所有 Md(i,j) = ?d 元素 ui,uj 在解u中滿足 ui uj = 0,然后,最密集分量的頂點被標識為 U 中最大的 ?ω 元素。

5.實驗結果

1)誤差規(guī)模變化:

10.png

2)時間變化

11.png

3)斯坦福兔子點云

12.png

4)不同參數下的精確率與召回率

13.png

5)離群點比例和運行時間的關聯

14.png

6)關聯對和運行時間的關聯

15.png

7)離群點比例和精確率召回率的關聯

16.png

Conclusion

這篇文章使用幾何一致性概念的魯棒數據關聯的圖理論框架解決點云匹配有問題。實驗證明能夠以低運行時間始終如一地執(zhí)行,并超越最先進的技術,在99%的異常值條件下實現100%的精度,80%的召回率。總體來講是很不錯的,但是具體應用在SLAM中的效果有待嘗試。

*博客內容為網友個人發(fā)布,僅代表博主個人觀點,如有侵權請聯系工作人員刪除。



關鍵詞: AI

相關推薦

技術專區(qū)

關閉