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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、合并相似的剛性變換

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

五、從每一類(lèi)提取剛性變換

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

編輯：黃飛