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

論文相關內容介紹：

論文標題：? Multi-instance Point Cloud Registration by Efficient Correspondence Clustering

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

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

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

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

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

Fig1：所提出的多實例點云配準方法的流程。從輸入對應關系中構造距離不變矩陣，用于將對應關系聚類到不同的簇并進行后續調整。最后，從每個對應集合中估計與每個實例的剛性變換（Transformations）。

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

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

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

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

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

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

三、迭代聚類調整

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

四、合并相似的剛性變換

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

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

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

編輯：黃飛