Clipper: 開(kāi)源的基于圖論框架的魯棒點(diǎn)云數據關(guān)聯(lián)方法(ICRA2021)

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

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

代碼已開(kāi)源: https://mit-acl.github.io/clipper

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

Contribution:

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

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

提出了一種多項式時(shí)間算法，用于求解基于投影梯度上升的松弛公式，可擴展到大型數據關(guān)聯(lián)問(wèn)題。

Content:

1.一致性圖框架

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

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

2.親和矩陣

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

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

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

因為M是二分矩陣，所以上述問(wèn)題可以簡(jiǎn)化為一個(gè)最大團問(wèn)題(MCP問(wèn)題):

因為MCP問(wèn)題是一個(gè)NP問(wèn)題，因此，隨著(zhù)問(wèn)題規模的增長(cháng)，依賴(lài)于求解上述優(yōu)化形式的算法在計算上變得難以處理。

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

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

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

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

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

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

4.CLIPPER算法

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

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

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

5.實(shí)驗結果

1）誤差規模變化:

2）時(shí)間變化

3）斯坦福兔子點(diǎn)云

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

5）離群點(diǎn)比例和運行時(shí)間的關(guān)聯(lián)

6）關(guān)聯(lián)對和運行時(shí)間的關(guān)聯(lián)

7）離群點(diǎn)比例和精確率召回率的關(guān)聯(lián)

Conclusion

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