CVPR2023最佳論文候選 | MAC: 基于極大團的3D配準

本文作者：3D視覺工坊@Vallee | 來源：3D視覺工坊

GitHub代碼：https://github.com/zhangxy0517/3D-Registration-with-Maximal-Cliques (暫未開源)

3D點云配準(PCR)是計算機視覺中的一個基本問題，其目的是尋找對齊點云對的最優位姿。本文提出了一種基于極大團(Maximal cliques, MAC)的3D配準方法，其關鍵思想是放寬先前的最大團(Maximum clique)約束，在圖中挖掘更多的局部共識信息，以準確地生成位姿假設: 1)構建相容性圖，表示初始對應之間的親和關系；2)在圖中搜索極大團，每個團代表一個共識集。然后，執行節點引導的團選擇，其中每個節點對應于具有最大圖權值的極大團；3)利用奇異值分解(SVD)算法對選取的團計算位姿變換假設，并利用最佳假設進行配準。在U3M, 3DMatch, 3DLoMatch和KITTI上的大量實驗表明，MAC有效地提高了配準精度，優于各種最先進的方法，并提高了深度學習方法的性能。MAC結合深度學習方法在3DMatch / 3DLoMatch上實現了95.7% / 78.9%的配準召回率。

注：團、極大團(maximal cliques)與最大團(maximum clique)的區別參見https://www.jianshu.com/p/dabbc78471d7。

圖1：低重疊點云對上的極大團(maximal cliques)和最大團(maximum clique)的比較。對于內點比例比較低的兩個點云，極大團(MAC)能有效地選擇旋轉誤差(RE)和平移誤差(TE)較小的最優6-DOF變換假設，而最大團在這種情況下是失敗的。

點云配準是3D計算機視覺中的一個重要而基本的問題，在3D定位、3D目標檢測和3D重建中有著廣泛的應用。給定同一物體(或場景)的兩次3D掃描，PCR的目標是估計6-DoF位姿變換，該變換精確地對齊兩個輸入點云。使用點對點特征對應是解決PCR問題的一種流行且穩健的解決方案。然而，由于現有3D關鍵點檢測器和描述符的限制，點云和數據噪聲之間的有限重疊，由特征匹配產生的對應關系通常含有離群點，這給精確的3D配準帶來了巨大的挑戰。

通過處理具有離群對應關系的3D配準問題已經研究了幾十年，我們將它們分為純幾何方法和深度學習方法。對于純幾何方法，隨機樣本一致性(RANSAC)及其變體執行迭代抽樣策略進行配準。盡管基于RANSAC的方法簡單高效，但當離群比例增加時，其性能非常脆弱，并且需要大量迭代才能獲得可接受的結果。同時，提出了一系列基于分枝定界(BNB)的全局配準方法，用于搜索6D參數空間并獲得最優解。這些方法的主要缺點是計算復雜度高，特別是當對應集規模很大且離群比例極高時。對于深度學習方法，一些方法關注于提升配準過程中的某個模塊，例如研究更具區分性的關鍵點特征描述符或更有效的對應關系選擇技術，而其他一些方法則關注以端到端的方式配準。然而，基于深度學習的方法需要大量的數據進行訓練，并且通常缺乏對不同數據集的泛化。目前，在存在嚴重異常值和跨數據集的情況下，實現準確的配準仍然是非常具有挑戰性的。

本文提出了一種基于極大團(Maximal cliques, MAC)的純幾何3D配準方法。關鍵的洞察是放松先前的最大團(maximum clique)約束，在圖中挖掘更多的局部共識信息，以生成準確的位姿假設。我們首先將初始對應關系集建模為相容圖，其中每個節點表示單個對應關系，兩個節點之間的每條邊表示一對相容對應關系。然后，我們在圖中搜索極大團，使用節點引導的團過濾來匹配每個圖節點與包含它的適當的極大團。與最大團相比，極大團(MAC)是一個更松的約束，能夠在圖中挖掘更多的局部信息。 這有助于我們從圖中獲得大量正確的假設。最后，利用SVD算法對選定的團計算位姿變換假設，使用RANSAC家族中流行的假設評估度量來選擇最佳假設來執行配準。

本文的主要貢獻如下：

• 提出了一種稱為極大團（MAC）的假設生成方法。與以前的最大團約束相比，極大團能夠在圖中挖掘更多的局部信息。我們證明，即使在存在嚴重異常值的情況下，MAC生成的假設也具有高精度。
• 在MAC的基礎上，提出了一種新的PCR方法，該方法在U3M、3DMatch、3DLoMatch和KITTI數據集上取得了最好的性能。值得注意的是，純幾何的MAC方法的性能優于幾種最先進的深度學習方法。MAC還可以作為模塊插入到多個深度學習框架中，以提升它們的性能。MAC結合GeoTransformer在3DMatch/3DLoMatch上實現了95.7%/78.9%的SOTA配準召回率。

對于要對齊的兩個點云和，我們首先使用幾何或學習描述符來提取它們的局部特征。設和分別表示和中的點。通過匹配特征描述符來得到初始對應集合，式中。MAC從估計和之間的6-DoF位姿變換。

所提出的方法在技術上非常簡單，其流程見圖2。

圖2：MAC的流程: 1.構造初始對應集的圖。2.從圖中選擇一組極大團作為相容集。3.根據相容集生成并評估假設。4.選擇最佳假設進行3D配準。

圖空間比歐氏空間更能準確地刻畫對應關系之間的親緣關系。因此，我們將初始對應關系建模為一個相容圖，其中對應關系由幾何相容的節點和連接節點的邊來表示。在這里，我們考慮兩種構建相容性圖的方法。

• 一階圖(FOG)：一階圖(FOG)基于對應對之間的剛性距離約束來構建，即：和之間的相容性分數為:其中，是距離參數。值得注意的是，如果大于閾值，和形成邊，并且是的權重，否則將被設置為0。因為相容圖是無向的，所以權重矩陣是對稱的。
• 二階圖(SOG)：SC-PCR中提出了一種二階相容性度量，它與全局集合中共同相容的對應關系的數量有關。二階圖 (SOG) 從 FOG 演變而來，其權重矩陣  可以計算為：其中表示矩陣的逐元素相乘。

兩種圖構建方法都可以用于本文的框架。與 FOG 相比，

• SOG 具有更嚴格的邊構造條件以及相鄰節點的相容性程度更高；
• SOG 更稀疏，這有助于更快地搜索團。在 MAC 框架中通過實驗對比了 FOG 和 SOG。

給定一個無向圖 ，團  是  的子集，其中任意兩個節點有邊連接。極大團是一個無法通過添加任何節點來擴展的團。特別地，節點數最多的極大團是圖的最大團。

搜索極大團：為了生成假設，基于RANSAC的方法反復從對應關系集合中隨機抽取樣本。然而，它們不能充分挖掘對應關系之間的親和關系。從理論上講，內點會在圖中形成團，因為內點通常在幾何上是相容的。以前的工作側重于尋找圖中的最大團，然而，最大團是一個非常嚴格的約束，只關注圖中的全局共識信息。相反，我們放松了約束，利用極大團來挖掘更多的局部圖信息。通過使用igraph C++庫中的igraph_maximal_cliques函數，該函數利用修改的Bron-KerBosch算法，可以非常高效地搜索極大團，其最差時間復雜度為，其中是圖的退化度。請注意，在我們的問題中，通常很小，因為在處理點云對應關系時，圖通常是稀疏的。

節點引導的團選擇：在執行極大團搜索過程后，我們得到極大團集合。在實際應用中，通常包含數以萬計的極大團，如果我們考慮所有極大團，這將使其非常耗時。我們提出一種節點引導的團選擇方法，以減少。首先，我們計算每個團在中的權重。給定一個團 ，權重為：其中，表示邊在中的權重。一個節點可能被多個極大團包含，我們只保留權重最大的那個極大團。然后，從剩余的團中刪除重復的團，得到。這背后的動機是使用關于圖節點周圍的局部幾何結構的信息來找到對應節點的最佳一致集合。顯然，極大團的數目不會超過。我們可以將這些極大團直接送到后續階段進行3D配準。然而，當相當大時，保留的極大團的數量仍然可能很大。在這里，我們提出了幾種技術來進一步過濾極大團。

• 法向量一致性：在極大團中，我們發現每個對應之間滿足法向量一致性。給定兩個對應和這四個點上的法向量，則可以計算出這四個點上的法向量之間的角度差：。如果和法向量相容，則以下等式應成立：其中是用于確定角度差是否相似的閾值。
• 團排序：用團的權重按降序組織。排名前的應該更有可能產生正確的假設，這使得控制假設的數量變得靈活。

從上一步過濾的每個極大團代表一組一致的對應關系。對每個一致性集使用SVD，可以獲得一組 6-DoF 位姿假設。

• 等實例SVD：從對應關系估計位姿變換通常使用 SVD 實現, 實例相等意味著所有對應的權重相等。
• 加權SVD：給對應關系加權在最近的PCR方法中很常用。可以通過求解相容性圖構造的相容矩陣的特征向量來得到對應權重。在這里我們將 的主特征值作為對應權重。

MAC的最終目標是估計最優6-DoF剛體變換(由旋轉和平移組成)，使以下目標函數最大化：其中，而表示的分數。我們在這里考慮了幾個RANSAC假設評估指標，包括平均誤差(MAE)、均方誤差(MSE)和內點數。實驗中將對不同指標的表現進行比較。選出來的最好的假設將被用來進行3D配準。

數據集：考慮了四個數據集，即物體尺度的數據集U3M、場景尺度的室內數據集3DMatch和3DLoMatch以及場景尺度的室外數據集KITTI。U3M有496個點云對。3DLoMatch是3DMatch的子集，其中點云對的重疊率在10%到30%范圍，這是非常具有挑戰性的。對于KITTI，我們遵循PointDSC和SC-PCR，得到555對點云進行測試。評估準則：我們遵循SAC-COT的方法，使用均方根誤差(RMSE)度量來評估U3M物體尺度數據集上的3D點云配準性能。此外，我們還使用旋轉誤差(RE)和平移誤差(TE)來評價場景數據集上的配準結果。通過參考Deep Global Registration中的設置，當3DMatch和3DLoMatch數據集上的RE≤15°，TE≤30 cm，以及KITTI數據集上的RE≤5°，TE≤60 cm時，認為配準成功。我們將數據集的配準準確率定義為成功案例與待配準的點云對數量的比例。實現細節：用C++實現，基于點云庫(PCL)和igraph庫。對于U3M，我們使用Harris3D(H3D)關鍵點檢測器和方向直方圖(SHOT)描述符來進行初始對應生成，與[42]中一樣。對于3DMatch和3DLoMatch數據集，我們使用快速點特征直方圖(FPFH)描述符和全卷積幾何特征(FCGF)描述符來生成初始對應集。對比實驗部分的主要步驟是構建SOG，搜索節點引導的極大團，用等實例SVD生成假設，用MAE進行評估。3.2小節中的相容性閾值和距離參數的默認值分別為0.99和10pr；如果輸入匹配超過5000，則將設置為0.999以減少計算量。這里‘pr’是一種叫點云分辨率的距離單位[42]。法向量是使用PCL的NormalEstment類用20個最近鄰點計算的。在搜索極大團時，團大小的下界被設置為3，沒有定義上限。所有實驗均使用Intel 12700H CPU和32 GB RAM。

我們在圖 3 中進行了大量的比較。在這里，測試了以下方法，包括 SAC-COT、OSAC、SAC-IA、RANSAC、SC-PCR、FGR、GO-ICP 和 PPF，其中前四個是基于 RANSAC 的方法。RMSE 閾值范圍為 0.5 pr 到 5 pr，步長為 0.5 pr。結果表明，MAC 表現最好，并且明顯優于所有測試的 基于RANSAC的估計器，例如 SAC-COT、OSAC、SAC-IA 和 RANSAC。基于 MAE 評估準則的MAC 的配準性能在 U3M 上是最好的。

PCR方法對比：對純幾何和深度學習方法都做了對比，包括SM、FGR、RANSAC、TEASER++、CG-SAC、SC-PCR、3DRegNet、DGR、DHVR和PointDSC。結果如表1和表2所示。可以得出以下結論:

• 無論使用哪種描述符，MAC在3DMatch和3DLoMatch數據集上的性能都優于所有對比的方法，表明它在室內場景點云的配準能力很強;
• 與深度學習方法相比，MAC在沒有任何數據訓練的情況下仍能獲得更好的性能;
• 除了配準召回(RR)指標外，MAC還獲得了最好的RE和TE指標。這表明 MAC 的配準非常準確，MAC 能夠對齊重疊率很低的數據。

用 MAC 增強深度學習方法：將幾種最先進的深度學習方法與 MAC 集成以進行評估。所考慮的方法是 FCGF、SpinNet、Predator、CoFiNet 和 GeoTransformer，每種方法都在不同數量的樣本（即不同數量的采樣點或對應關系）下進行測試，結果見表3。MAC 在 3DMatch 和 3DLoMatch 數據集上顯著提高了所有測試方法的配準召回率。值得注意的是，SpinNet、Predator和CoFiNet經過MAC提升后的性能超過了GeoTransformer。MAC與GeoTransformer結合，在3DMatch / 3DLoMatch上實現了95.7% / 78.9%的SOTA配準召回。結果表明:

• MAC可以極大地增強現有的深度學習方法;
• MAC對樣本數量不敏感。

表4中對比了DGR、PointDSC、TEASER++、RANSAC、CG-SAC、SC-PCR和MAC的結果。MAC在配準召回性能方面表現最好，無論是使用FPFH還是FCGF描述符。MAC的TE也比最先進的純幾何方法SC-PCR低。請注意，室外點云非常稀疏且分布不均勻。

在物體、室內場景和室外場景數據集上的配準實驗一致地驗證了MAC在不同的應用場景下具有良好的泛化能力。

執行特征匹配選擇：在3D配準之前，一種流行的方法是執行離群點拒絕以減少對應集。這里我們使用幾何一致性(GC)，它獨立于特征空間，并且將最大的一致集群與對應關系之間的相容性關聯起來。

通過對表5的第1行和第2行進行比較，GC對MAC性能產生了負面影響，這可能是因為在此過程中也會去除一些內點。這表明，即使在不經過任何過濾的情況下直接利用初始對應集作為輸入，MAC仍然可以很好地工作。

圖構造的選擇：通過使用不同的圖構造方法來測試MAC的性能。如表5中第1和第3行所示，在3DMatch上，SOG與FPFH結合時比FOG的配準召回率高1.6%，與FCGF結合時比FOG高0.06%。在3DLoMatch上，SOG與FPFH結合使用比FOG高0.12%，與FCGF結合使用比FOG高0.56%。因此，SOG更適合MAC，詳見補充材料。

最大團與極大團對比：為了證明極大團的優勢，我們將 MAC 的搜索策略更改為最大團并測試配準性能。如表 5 中的第 1 行和第 9 行所示，與 FPFH 結合時，應用極大團比最大值高 9.8%，在 3DMatch 上與 FCGF 結合時提高了 5.55%。此外，在3DLoMatch上，使用極大團的配準召回率比使用最大團的配準召回率高8.03%，與FCGF結合的配準召回率高10.45%。這有幾個原因：

• 極大團包括最大團，且額外考慮了局部圖約束，因此搜索極大團可以利用相容性圖中的局部和全局信息；
• 最大團是一個非常嚴格的約束，需要最大化相互兼容的對應關系的數量，但不能保證最優的結果。

節點引導的團選擇：我們對比了使用和不使用節點引導(NG)團選擇進行極大團搜索的性能。對比表5中的第1行和第4行，在3DMatch上，使用NG在與FPFH結合時召回率提高0.37%，與FCGF結合時提高0.5%。此外，在3DLoMatch上，使用NG可以使FPFH的召回率提高0.23%，FCGF的召回率提高0.73%。值得注意的是，在NG提高召回率的同時，平均RE和平均TE也在下降。例如，在3DLoMatch上，使用FPFH，NG使平均RE減少0.1°，平均TE減少0.11 cm。NG有效地減少了后續步驟中的計算次數，并保證了準確的假設。

團過濾的不同方法：我們測試了兩種過濾方法的有效性，法向量一致性和團排序。

• 法向量一致性（NC）：對比表5中的第1行和第8行，NC略微降低了MAC的性能。
• 團排序：第10行到第14行表明，配準召回率隨著的增加而增加，這表明越大，產生的團的子集生成的假設越正確。值得注意的是，將設置為100已經可以獲得很好的性能。

采用等實例或加權的SVD：表5的第1行和第5行顯示了等實例和加權SVD的比較。加權SVD略遜于等實例的SVD，這表明MAC中的樣本已經非常一致，不需要額外的加權策略。

不同的假設評估指標：這里我們比較了三種評價指標，包括MAE、MSE和Inlier count，用于MAC假設的評價。如第1、6、7行所示，MAC和MAE的性能最佳。在表5中，與常用的Inlier計數指標相比，MAE在與FPFH結合時召回率提高了0.24%，在3DMatch上與FCGF結合時提高了0.31%。此外，MAE在與FPFH結合時有1.74%的改善，在3DLoMatch上與FCGF結合時與Inlier Count相比有0.05%的改善。MAE在降低RE和TE方面也非常有效。例如，在3DLoMatch上，MAE與FPFH相比，平均RE降低0.35°，平均TE降低0.49 cm。

與RANSAC的假設進行比較：我們通過將RANSAC和MAC的假設與真實變換進行比較來評估生成的假設的質量。結果如表6所示。與RANSAC隨機選擇對應關系并從沒有幾何約束的對應關系集生成假設相比，MAC有效地從相容圖中的極大團生成更令人信服的假設，充分利用了圖中的共識信息。

MAC的性能上限：給定一個理想的假設評估度量，只要能夠生成正確的假設，就可以對齊點云對，這可以測試MAC的性能上限。我們改變生成正確假設的數量的判斷閾值，并在表7中報告結果。

令人印象深刻的是，MAC-1在3DMatch/3DLoMatch上的配準召回率為98.46%/91.24%。這表明，即使在低重疊的數據集上，MAC也能夠為大多數點云對產生正確的假設。此外，我們還可以推斷，通過更好的假設評估度量，可以進一步提高MAC的性能。

MAC的時間消耗：我們使用Predator生成不同大小的對應關系來測試MAC的時間消耗，如表8所示。可以看到：

• 一般情況下，當對應數小于1000個時，MAC只需幾十毫秒即可完成3D配準。即使使用2500個對應關系的輸入，時間消耗也約為0.29秒。請注意，MAC僅在CPU上實現。
• 隨著對應關系數量從250個增加到2500個，由于計算花費的時間增加了，構建圖的時間成本也增加了。
• 當對應關系數量達到5000個時，MAC配準的時間開銷會大幅增加。輸入大小的顯著增加使得尋找極大團的過程更加耗時。然而，MAC對輸入對應集合的勢（元素個數）不敏感，如表3所示。因此，使用稀疏輸入作為MAC可以在提高配準效率的同時產生出色的性能。

本文提出了MAC，用極大團約束從對應關系中生成精確的位姿假設來求解PCR問題。在所有測試的數據集上都達到了最先進的性能，并且可以結合到深度學習的方法中來提高它們的性能。

局限：如表7和表1所示，MAC產生的假設準確，但可能找不到它們。在未來，可以開發一種利用語義信息的更令人信服的假設評估技術。

參考文獻：3D Registration with Maximal Cliques