0.筆者個人體會： 這個工作來自于上海交通大學(xué)，發(fā)表于CVPR 2022。我們知道，三維點云配準(zhǔn)是三維視覺以及點云相關(guān)任務(wù)中的一個關(guān)鍵課題。早期最具有代表性的三維點云配準(zhǔn)的工作是ICP，其根據(jù)點匹配估計輸入點云的相對位姿。近年來隨著深度學(xué)習(xí)技術(shù)的發(fā)展進(jìn)步，基于深度學(xué)習(xí)的三維點云配準(zhǔn)方法成為研究的主流，并隨之誕生了DeepVCP、DGR、Predator等著名的方法。但這個工作重新聚焦于非學(xué)習(xí)的策略，通過聚類策略實現(xiàn)了先進(jìn)的性能。同時，這個工作提出了一個新穎的點云配準(zhǔn)問題設(shè)定，稱為multi-instance point cloud registration，即同時估計某個instance的源點云與多個目標(biāo)instance組成的目標(biāo)點云中的每個instance的相對位姿。 這個工作與一般的多模態(tài)擬合工作有點類似，但不同的是，這個工作展現(xiàn)了更強(qiáng)的對異常值的魯棒性，以及非常高的時間效率。但是，不可避免的是，這個工作同樣存在著一般非學(xué)習(xí)的方法都面臨的制約，即有許多閾值參數(shù)需要給定，這點可能會制約其應(yīng)用?；蛘?，將深度學(xué)習(xí)技術(shù)與本文觀察到的distance invariance matrix的分布規(guī)律相結(jié)合是一個值得探索的方向。

論文相關(guān)內(nèi)容介紹：

論文標(biāo)題：? Multi-instance Point Cloud Registration by Efficient Correspondence Clustering

作者列表：? ?Weixuan Tang and Danping Zou

摘要：我們解決了多實例點云配準(zhǔn)的問題，其是指源點云由一個實例（Instance）的點云構(gòu)成，而目標(biāo)點云由多個不同位姿的實例的點云構(gòu)成的情況下，同時求多個相對位姿變換?，F(xiàn)有的解決方案需要對大量假設(shè)進(jìn)行采樣以檢測可能的實例并排除異常值，但當(dāng)實例和異常值的數(shù)量增加時，其魯棒性和效率會顯著降低。我們提出根據(jù)距離不變矩陣將帶噪聲的對應(yīng)集合直接分組到不同的簇中。通過聚類自動識別其中的實例和異常值。我們的方法魯棒且快速。我們在合成數(shù)據(jù)集和真實數(shù)據(jù)集上評估了所提出的方法。結(jié)果表明，在存在70%異常值的情況下，我們的方法可以正確配準(zhǔn)多達(dá)20個實例，F(xiàn)1得分為90.46%，其性能明顯優(yōu)于現(xiàn)有方法，速度至少快10倍。

主要貢獻(xiàn)： 1）我們針對多實例點云配準(zhǔn)問題提出了一種高效且魯棒的解決方案，在準(zhǔn)確性、魯棒性和速度方面取得了卓越的性能。 2）我們提出了三個指標(biāo)（Mean Hit Recall、Mean Hit Precision和Mean Hit F1）來全面評估多實例點云配準(zhǔn)的性能。 3）我們的解決方案可以潛在地用于3D目標(biāo)的檢測。

問題建模： 多實例點云配準(zhǔn)問題中，源點云X提供了一個3D模型的實例，目標(biāo)點云Y包含該模型的K個實例，其中這些實例是可能僅對3D模型的一部分進(jìn)行采樣的點集。如果我們將第k個實例寫為，則目標(biāo)點云Y可以分解為。這里我們使用來表示點云中不屬于任何實例的部分，即異常值的集合。多實例三維點云配準(zhǔn)的目標(biāo)是找到將源點云實例X?與每個目標(biāo)實例點云對齊的剛性變換。如果我們設(shè)法獲得源實例和每k個目標(biāo)實例之間的對應(yīng)關(guān)系，則目標(biāo)點云中第 k 個實例的位姿可以通過最小化對齊誤差的總和從對應(yīng)關(guān)系集合中求解：

考慮我們已經(jīng)獲得了源點云和目標(biāo)點云之間的對應(yīng)關(guān)系集合。多實例點云配準(zhǔn)任務(wù)的關(guān)鍵是將這些對應(yīng)關(guān)系分類為關(guān)于不同實例的單獨集合，即 這里用于表示異常值的集合。正如我們所看到的，多實例點云配準(zhǔn)不僅需要排除異常對應(yīng)，還需要解決來自不同實例的對應(yīng)的歧義。這項任務(wù)并不容易，因為所有實例看起來都一樣，并且通常存在許多異常值對應(yīng)。

Fig1：所提出的多實例點云配準(zhǔn)方法的流程。從輸入對應(yīng)關(guān)系中構(gòu)造距離不變矩陣，用于將對應(yīng)關(guān)系聚類到不同的簇并進(jìn)行后續(xù)調(diào)整。最后，從每個對應(yīng)集合中估計與每個實例的剛性變換（Transformations）。

方法介紹： 所提出的方法的框架如圖1所示。我們的方法將點對應(yīng)作為輸入。然后通過檢查對應(yīng)關(guān)系之間的距離一致性來構(gòu)造一個不變的一致性矩陣。接下來，通過將列或行向量視為這些對應(yīng)關(guān)系的“特征”，將這些對應(yīng)關(guān)系快速聚集到不同的組中。聚類是通過凝聚聚類有效地完成的，其通過交替合并相似的剛性變換和多次迭代重新分配聚類標(biāo)簽來實現(xiàn)。并且，如果出現(xiàn)對應(yīng)數(shù)量很大的情況，我們可以應(yīng)用下采樣和上采樣操作來進(jìn)一步處理。

一、不變性矩陣和兼容性向量

多年來，距離不變性已經(jīng)在 3D 配準(zhǔn)被充分探索，它描述了兩點之間的距離在經(jīng)過剛性變換后保持不變。即，如果且是兩個真正的對應(yīng)，它們應(yīng)該滿足：

通過計算所有對應(yīng)對之間的分?jǐn)?shù)，可以獲得距離不變矩陣（我們令）。距離不變矩陣是對稱的，其中每一列或每一行都是一個向量，描述了給定對應(yīng)關(guān)系和其他對應(yīng)關(guān)系之間的兼容性。 我們將列向量命名為對應(yīng)ci的兼容性向量。我們觀察到，如果兩個對應(yīng)關(guān)系屬于同一個實例，則它們的兼容性向量具有相似的模式。考慮兩個對應(yīng)關(guān)系。對于任何對應(yīng)，由于距離不變性，我們有，。對于其他對應(yīng)關(guān)系，我們很可能有, 。換句話說，有相似的0-1模式。相比之下，如果這兩個對應(yīng)關(guān)系屬于不同的實例，那么它們的兼容性向量就會非常不同。為了更好地理解這一觀察結(jié)果，我們在圖2 中給出了一個簡單的示例。 對應(yīng)的兼容性向量可以被視為該對應(yīng)的特征表示。屬于同一剛性變換的對應(yīng)具有相似的特征。因此，基于這些兼容性向量，我們可以將這些對應(yīng)關(guān)系聚類到不同組中，每個組來自不同的實例或者屬于異常值。

Fig2. 距離不變矩陣中的列向量（兼容性向量）包含與實例相關(guān)的豐富信息。這里,表示第i個和第j個對應(yīng)的兼容性向量，它們都在實例中。我們觀察到與相似。相比之下，與顯著不同，因為第k個對應(yīng)在不同的實例內(nèi)。這里代表異常值的集合。 二、快速對應(yīng)關(guān)系聚類 我們以自下而上的方式對對應(yīng)進(jìn)行聚類，這比現(xiàn)有的譜聚類方法要快得多。一開始，每個對應(yīng)都被視為一個單獨的類，然后重復(fù)合并距離最小的兩個類，直到兩類之間的最小距離大于給定閾值。定義類之間距離的方式會產(chǎn)生不同的算法。這里定義距離如下。設(shè) 為類i和j的表示向量，類間距離定義為

如果兩個類合并，則新類的表示向量通過更新，其中表示對兩個向量的每個維度取最小值。在聚類開始時，將一類（僅包含一個對應(yīng)）的表示向量設(shè)置為該對應(yīng)的兼容性向量。

三、迭代聚類調(diào)整

在聚類之后，我們通過重復(fù)一下步驟進(jìn)一步細(xì)化，直到?jīng)]有變化為止。 Step1. 估計來自每個類的剛性變換，其中對應(yīng)的數(shù)量大于閾值ɑ。 Step2. 合并相似的變換。 Step3. 將類的標(biāo)簽重新分配給每個對應(yīng)的。每個對應(yīng)都分配給其對齊誤差最小的變換。如果對于所有變換的最小對齊誤差都大于內(nèi)點閾值，則將該對應(yīng)標(biāo)記為異常值。 在迭代過程中，對應(yīng)變得越來越聚集，因此我們可以在Step1中調(diào)整ɑ以增加異常值拒絕的強(qiáng)度。我們使用以下策略在每次迭代中更新ɑ： 其中表示第次迭代，N是對應(yīng)的數(shù)量，是舍入取整操作。我們在實驗中設(shè)置和。在我們的實驗中，細(xì)化過程通常在三個迭代內(nèi)收斂，因此它也是高效的。

四、合并相似的剛性變換

有時不同的對應(yīng)類會產(chǎn)生類似的剛性變換，這意味著它們可能屬于同一個實例。在這種情況下，我們需要合并它們。給定兩個估計的變換和，我們計算每個對應(yīng)的對齊誤差，即接下來，如果，我們設(shè)置，否則設(shè)置。因此，我們?yōu)閮蓚€轉(zhuǎn)換獲得了兩個二元集合。合并兩個變換的標(biāo)準(zhǔn)是 如果滿足此標(biāo)準(zhǔn)，我們將丟棄具有更多異常值的其中一個變換。然后，我們根據(jù)所有變換中對齊誤差最小的一個，將簇標(biāo)簽重新分配給每個對應(yīng)。

五、從每一類提取剛性變換

聚類后，我們需要從這些不同類的對應(yīng)集合中提取剛性變換。由于我們不知道目標(biāo)點云中實例的真實數(shù)量，我們需要自動選擇那些內(nèi)點對應(yīng)類。我們首先選擇元素數(shù)大于閾值的內(nèi)點對應(yīng)類，并估計這些類的剛性變換。接下來，我們按這些剛性變換的內(nèi)點對應(yīng)數(shù)，以降序?qū)ζ溥M(jìn)行排序。剛性變換內(nèi)點對應(yīng)越多，它與真實實例相關(guān)聯(lián)的機(jī)會就越高。最后，我們通過以下方式檢查剛性變換和具有最多對應(yīng)內(nèi)點的剛性變換之間的內(nèi)點對應(yīng)數(shù)的下降率 其中表示第k次剛性變換的內(nèi)點對應(yīng)數(shù)。如果，我們忽略第k個剛性變換之后的所有變換。這里可以更改閾值以在召回率和精度之間進(jìn)行權(quán)衡。

編輯：黃飛