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

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

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

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

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

Contribution:

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

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

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

Content:

1.一致性圖框架

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

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

2.親和矩陣

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

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

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

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

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

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

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

U’是MCP問題形式的解，但是U‘在矩陣M中對應(yīng)的一致性分?jǐn)?shù)很低，大致在0.2左右，所以在親和矩陣中通過加權(quán)方案進行選擇子圖是很好重要的，否則很容易選到低一致性的子圖。

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

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

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

4.CLIPPER算法

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

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

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

5.實驗結(jié)果

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

2）時間變化

3）斯坦福兔子點云

4）不同參數(shù)下的精確率與召回率

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

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

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

Conclusion

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