本文分享 CVPR 2022 論文『SC^2-PCR: A Second Order Spatial Compatibility for Efficient and Robust Point Cloud Registration』，二階相似性測度，讓傳統配准方法取得比深度學習更好的性能，並達到深度學習的速度。
論文作者：陳志，孫琨，楊帆，陶文兵
通訊單位：華中科技大學，中國地質大學
論文鏈接：https://arxiv.org/abs/2203.14453
項目鏈接：https://github.com/ZhiChen902/SC2-PCR
針對3D點雲配准中的誤匹配消除任務，來自華中科技大學的研究團隊提出了一種基於二階空間兼容性度量的點雲配准方法。具體來說，算法提出了一種二階空間兼容性度量來計算匹配對之間的相似度，考慮了匹配對之間的全局兼容性而不是局部一致性，從而能夠更加準確地度量正確匹配和錯誤匹配之間的差異。論文從概率的角度來分析採樣的有效性，並證明了所提出的二階度量能夠大幅度提高採樣內點集合的概率。相比傳統的隨機採樣策略而言，僅通過少數幾次採樣就能夠得到有效的內點集合估計出點集之間的幾何變換。基於所提出的二階空間兼容性度量，論文設計了一套基於種子點的快速匹配方法。與當前基於學習的方法和非學習的方法相比，均取得了更好的性能。該方法最大的特點是不需要樣本進行學習，因此沒有深度學習方法通常存在的泛化性問題，但具有比深度學習方法更好的性能。在計算效率方面也表現突出，接近當前最快的算法。同時，論文也從實驗驗證了所提出的度量具有很好的可擴展性，可以直接與深度學習框架相結合。三維剛體點雲配准旨在恢復兩個具有重疊區域的點雲之間的剛體變換。它是三維重建、即時定位與地圖構建（SLAM）、虛擬現實等領域的重要基礎，是計算機視覺中的基本問題。當前最常用的方法通過兩步法進行點雲配准：1、先為點雲中的每個點提取局部特徵描述子，並通過特徵匹配建立粗略的點雲對應關係；2、通過穩健的模型估計算法，從含有誤匹配（外點）的粗匹配關係中尋找正確匹配（內點）並估計剛體變換。本研究主要關注如何在粗匹配中含有大量錯誤匹配的情況下進行點雲配准。RANSAC[1]最早採用迭代的策略來進行模型估計。然而，它需要大量的採樣來保證算法的收斂，並且在內點率過低的情況下並不能保證一定能找到正確解。一些方法通過空間兼容性來解決RANSAC的問題，它利用剛體變換的一個性質：空間中任意兩個點經過剛體變換之後長度不變。因此，一階空間兼容性度量認為如果兩個匹配對之間的空間距離差（如圖1（a）中的 或 ）越小，他們的相似度越大。由於正確匹配對（內點）之間的空間距離差理論上應為0，這樣兩個內點的相似性就會比較大，從而在內點之間形成聚類效應。 圖1：一階與二階兼容性度量對比。（a）兩對點雲之間的匹配關係（紅色為錯誤匹配，綠色為正確匹配）（b）一階兼容性矩陣；（c）二值化一階兼容性矩陣；（d）二階兼容性矩陣然而一階兼容性存在模糊性，即外點也有可能與內點有很高的相似度。為了直觀地說明這個問題，我們在圖1（a）中展示了兩對點雲之間的匹配關係（紅色為錯誤匹配，綠色為正確匹配）。同時，我們在圖1（b）中展示了任意兩對匹配對之間的一階兼容性。從圖中可以看出，外點和內點之間可能會存在着很高的相似性（黃色底紋的方格），這就是一階兼容性的模糊性問題。當前一些研究通過傳統方法（如三元組約束）[2,3]或深度學習框架[4,5]來減輕模糊性帶來的問題，雖然一定程度上緩解了這一問題，但是在內點率很低的情況下有時也會失效。在我們的研究中，我們提出一個新的全局測度來度量兩個匹配對之間的相似性。具體來說，我們首先二值化一階空間兼容性測度（1代表兩個匹配對是兼容的），如圖1（c）。然後對於任意兩個兼容的匹配對，我們計算與它們共同兼容的匹配對的個數作為它們的相似性。換句話說，我們計算同時與這兩個匹配對都兼容的匹配的數量作為它們之間新的相似性，而如果它們本身不兼容，那麼就認為它們的相似性為0。由於內點之間都是相互兼容的，因此任意兩個內點之間的相似度至少為所有匹配對中內點的個數（除去這兩個匹配對自身），而內點和外點之間並沒有這樣的性質。如圖1所示，{c1,c2,c3,c4,c5}是內點，而{c6,c7}為外點。從圖1（b）和（c）中可以看出，外點{c6,c7}與某些內點有很高的相似性，而圖1（d）中則抑制了這種情況。具體來說，在圖1（d）中，{c1,c2,c3,c4,c5}之間的相似性不小於3，而外點{c6,c7}與其他點的相似性均小於1。因此，新提出的測度可以更好的區分內點和外點。由於新提出的測度可以被表示為一階測度的乘積形式，因此我們稱這種新提出的測度為二階相似性測度。利用二階測度可以更好地區分內外點。假設在對匹配中有對正確匹配，內點之間的相似性應大於，而外點與內點之間的相似性很小；傳統的算法如RANSAC需要大量的隨機採樣來得到一組沒有外點的集合，而利用所提出的二階兼容性矩陣，在每個內點所對應的行中，我們可以通過尋找top-k個近鄰來得到一個一致性集合。這樣，只要遍歷N行就可以找到M個沒有外點的集合，從而大大提升採樣的穩定性和效率。我們從概率的角度證明了所提出的二階兼容性可以減少錯誤採樣的概率。具體來說，我們定義了一個模糊事件，即外點和內點的相似性比內點之間相似性高這一事件。我們分析了一階兼容性和所提出的二階兼容性的模糊事件概率，可以證明所提出的度量更穩定。方法流程圖如圖2所示。具體來說，方法的輸入是利用特徵描述子生成的粗匹配。我們首先構建逐匹配的矩陣（3.1節）。然後，我們通過譜分解的方式結合局部極大值抑制選擇一些可靠的匹配作為種子點，目的是減少採樣次數來提升算法效率（3.2節）。在這之後，我們通過一個兩階段的採樣方式為每個種子點構造一個一致性集合（3.3節）。最後，我們通過局部譜匹配的方式結合可微的奇異值分解來為每個一致性集合求解一個剛體變換，並選擇最好的估計作為最終結果（3.4節）。3.1 二階兼容性度量為了分析用於採樣的度量的有效性，我們定義了一個模糊性事件的概率：
其中是事件發生的概率，是一個具體的度量。內點和外點之間的相似度，而是兩個內點之間的相似度。當時，外點就會變成內點的近鄰，從而基於度量的採樣就越不穩定。因此該概率值越小，則基於度量的採樣越穩定。我們首先介紹常用的一階兼容性度量SC，它通常被定義為如下形式：
其中為一個單調遞減函數，為兩個匹配對之間的距離差。如前所述，由於剛體變換不改變任意兩點的長度，因此兩個內點之間的距離差理論應為0。然而，由於數據獲取或點雲採樣時引入的噪聲，不是絕對等於0，而只是可能小於一個閾值。為了方便推導，我假設在0到之間均勻分布，並且得到對應的概率密度函數如下：
同時，由於外點是隨機分布的，因此任意兩個外點或者一個外點和一個內點之間是沒有任何關聯的。對於兩個沒有關聯的點之間的距離差（或），我們認為它們是同分布的，並且將它們的分布記為:
其中為和的最大變化範圍。為了直觀地展示它們的分布，我們做出了在3DMatch數據集上函數的經驗曲線，如圖3所示：顯然，遠遠大於，因此我們可以近似在，之間是不變的，假設值為。接下來，我們計算一階兼容性的模糊性概率。根據公式2，3，4可以得出：
以3DMatch數據集為例。近似為10cm，那麼一階兼容性的模糊性概率約為0.1。考慮到外點的數量一般十分龐大，這樣的模糊概率在採樣時不能被忽略。接下來，我們介紹所提出的二階兼容性，它具有如下形式：
我們可以同樣的推導出它的模糊性概率。由於推導過程比較複雜，因此我們僅寫出我們推導出的公式，具體推導過程可以參考原論文的附錄部分：
其中為內點率，為匹配對個數。為概率學中的Skellam分布。根據式5，7中的結論，我們分別做出了一階和二階度量的模糊性概率圖，如圖4所示：圖4：一階和二階度量模糊性概率對比（SC^2-N,N=5000,2500,1000為匹配對個數）從圖中可以看出，所提出的方法可以大大降低模糊性概率值，從而提升採樣的穩定性。3.2 種子點選取如上所述，在矩陣中，內點之間有很高的相似性，那麼只要我們找到一個內點，就可以通過找它的k個近鄰來得到一個一致性集合。顯然，遍歷所有的匹配對一定可以找到一個內點，但是這是不必要的。我們只需要尋找一些可靠的種子匹配對來加速採樣的過程。我們通過譜分解技術來進行種子點的查找。具體來說，我們首先構造匹配之間的相似度矩陣，然後通過譜分解技術確定每個匹配點是正確匹配的一個粗略的置信度，並將這個置信度結合局部極大值抑制操作確定一些種子點。3.3 兩階段採樣在選擇一些種子點過後，我們採用一個兩階段採樣的方式將每個種子點擴充成一個一致性集合。在第一階段，我們在 矩陣中尋找每個種子點的Top-K1近鄰。由於所提出的度量發生模糊性的概率很小，因此當種子點是內點時，它對應的一致性集合里也主要都是內點。
第二個階段進一步剔除第一個階段中可能引入的誤匹配。我們重新在每個一致性集合中構造了一個局部 矩陣，並選擇每個種子點的Top-K2（K2<K1）近鄰作為新的一致性集合。如圖4所示，在 度量中，內點率越高模糊性事件發生的概率越低。所以第二階段在第一階段濾除一部分外點之後進行選擇，可以得到更好的結果。
值得一提的是，我們只考慮了種子點是內點的情況。當種子點是外點時，它也可以形成局部的一致性，尤其是在初始匹配中有一些成片的錯誤匹配時。我們在採樣時保留這些結果，並在最後的模型選擇時再篩選正確的剛體模型。這樣可以防止太嚴格的種子點策略導致有些正確的模型被忽略了。3.4 模型生成與選擇在得到一些一致性匹配集合後，我們採用加權奇異值分解（SVD）來為每個集合估計一個剛體變換。我們在每個集合中構建局部相似度矩陣，並利用譜匹配技術為每個匹配對分配一個權重。然後將這個權重用於SVD分解，從而得到估計的旋轉變換和平移變換。對於每個估計出來的變換，我們使用和RANSAC同樣的內點計數準則來評價模型的質量：
其中[]是艾弗森括號。最後我們選擇得分最高的模型作為最終的剛體變換結果。4.1 數據集和評價指標我們分別在室內配准數據集3DMatch，室內低重疊率配准數據集3DLoMatch和室外數據集KITTI上對方法進行了評測。為了更充分地對方法進行驗證，我們分別將方法與不同的描述子結合，所採用的描述子包括FPFH、FCGF和Predator。評價指標包括配准召回率（RR）、旋轉誤差（RE）、平移誤差（TE）、分類精度（IP）、分類召回率（IR）、分類F1-measure（F1）和運行時間。4.2 總體結果所提出的方法與其他方法的在三個數據集上的對比結果如表1，2，3所示。從表中可以看出，所提出的方法優於傳統方法和基於深度學習的方法，並且在效率上也可以達到接近深度學習方法的速度。
4.3 低內點率配准
在某些極端情況下，描述子建立的匹配中會含有大量的誤匹配，正確匹配的比例可能低於1%。為了驗證在不同內點率下算法的穩定性，我們根據內點率將數據集劃分為六組，並統計了不同方法在這些內點率下的配准召回率，如圖5所示。從圖中可以看出，我們的方法對於低內點率更穩定，尤其是在內點率低於2%時。4.4 與深度學習框架結合
表4：與深度學習框架結合的性能對比（*-gen表示泛化性實驗）
為了驗證所提出的二階兼容性度量的可擴展性，我們將它與當前最好的深度學習方法PointDSC結合。從表4中可以看出，度量可以提升深度學習方法的性能，尤其是泛化性。4.5 消融實驗所提出所有模塊的消融實驗如表5所示。我們以傳統的RANSAC為baseline，逐步添加所提出的模塊。其中：SC為一階兼容性引導的採樣；為二階兼容性引導的採樣；TS為二階段採樣方式；LSM為基於局部譜匹配的姿態估計方式；Seed為引入種子點提高算法效率。
4.6 定性實驗結果
參考文獻[1] Martin A Fischler and Robert C Bolles. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM.[2] Qian-Yi Zhou, Jaesik Park, and Vladlen Koltun. Fast global registration. In European Conference on Computer Vision, pages 766–782. Springer, 2016.[3] Siwen Quan and Jiaqi Yang. Compatibility-guided sampling consensus for 3-d point cloud registration. IEEE Transactions on Geoscience and Remote Sensing, 58(10):7380–7392, 2020.[4] Xuyang Bai, Zixin Luo, Lei Zhou, Hongkai Chen, Lei Li, Zeyu Hu, Hongbo Fu, and Chiew-Lan Tai. Pointdsc: Robust point cloud registration using deep spatial consistency. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15859–15869, 2021.[5] Junha Lee, Seungwook Kim, Minsu Cho, and Jaesik Park. Deep hough voting for robust global registration. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 15994–16003, 2021.
留言列表
留言列表