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

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

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

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

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

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

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

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

本文的主要貢獻如下：

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

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

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

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

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

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

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

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

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

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

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

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

從上一步過濾的每個極大團代表一組一致的對應(yīng)關(guān)系。對每個一致性集使用SVD，可以獲得一組 6-DoF 位姿假設(shè)。

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

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

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

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

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

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

• MAC可以極大地增強現(xiàn)有的深度學(xué)習(xí)方法;
• MAC對樣本數(shù)量不敏感。

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

在物體、室內(nèi)場景和室外場景數(shù)據(jù)集上的配準實驗一致地驗證了MAC在不同的應(yīng)用場景下具有良好的泛化能力。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文提出了MAC，用極大團約束從對應(yīng)關(guān)系中生成精確的位姿假設(shè)來求解PCR問題。在所有測試的數(shù)據(jù)集上都達到了最先進的性能，并且可以結(jié)合到深度學(xué)習(xí)的方法中來提高它們的性能。

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

參考文獻：3D Registration with Maximal Cliques