本文作者：3D視覺(jué)工坊@Vallee | 來(lái)源：3D視覺(jué)工坊

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

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

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

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

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

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

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

本文的主要貢獻(xiàn)如下：

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

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

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

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

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

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

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

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

給定一個(gè)無(wú)向圖 ，團(tuán)  是  的子集，其中任意兩個(gè)節(jié)點(diǎn)有邊連接。極大團(tuán)是一個(gè)無(wú)法通過(guò)添加任何節(jié)點(diǎn)來(lái)擴(kuò)展的團(tuán)。特別地，節(jié)點(diǎn)數(shù)最多的極大團(tuán)是圖的最大團(tuán)。

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

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

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

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

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

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

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

我們?cè)趫D 3 中進(jìn)行了大量的比較。在這里，測(cè)試了以下方法，包括 SAC-COT、OSAC、SAC-IA、RANSAC、SC-PCR、FGR、GO-ICP 和 PPF，其中前四個(gè)是基于 RANSAC 的方法。RMSE 閾值范圍為 0.5 pr 到 5 pr，步長(zhǎng)為 0.5 pr。結(jié)果表明，MAC 表現(xiàn)最好，并且明顯優(yōu)于所有測(cè)試的 基于RANSAC的估計(jì)器，例如 SAC-COT、OSAC、SAC-IA 和 RANSAC。基于 MAE 評(píng)估準(zhǔn)則的MAC 的配準(zhǔn)性能在 U3M 上是最好的。

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

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

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

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

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

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

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

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

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

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

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

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

團(tuán)過(guò)濾的不同方法：我們測(cè)試了兩種過(guò)濾方法的有效性，法向量一致性和團(tuán)排序。

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：3D Registration with Maximal Cliques