劇透: 它們現在好多了!
關於作者
Dmytro Mishkin 是捷克布拉格理工大學的博士後，在影像匹配和計算機視覺和深度學習諮詢領域工作。
OpenCV RANSAC 已經死了。長壽的 OpenCV USAC!
去年，包括我在內的來自 UBC、谷歌、布拉格理工大學和 EPFL 的一組研究人員發表了一篇論文“跨越寬基線的影像匹配: 從論文到實踐”，該論文除了其他資訊外，還表明 OpenCV RANSAC 用於基本矩陣估計很糟糕: 它非常不準確而且很慢。從那時起，我的同事 Maksym Ivashechkin 在 2020 年的整個夏季都致力於改進 OpenCV RANSACs。他的工作作為 OpenCV 4.5.0 版本 的一部分發布。
現在是時候對它們進行基準測試了。讓我們開始吧!
RANSAC
首先讓我們回顧一下 RANSAC 是用來做什麼的。這個縮寫代表 RANdom SAmple Consensus，這是一種演算法，於 1981 年被提出，用於在存在離群值的情況下對模型引數進行穩健估計——也就是說，存在噪聲和錯誤的資料點。
該技術在計算機視覺中最廣泛的應用是用於相對相機姿態和透視變換估計。顯然，它在 OpenCV 中可用，並且在其 教程 中有介紹。
自從最初的論文發表以來，數百名研究人員提出了一系列改進，使 RANSAC 速度更快、更精確、更穩健。
基準測試
儘管有了這些改進，但沒有“下游指標”評估，說明 RANSAC 如何影響相機姿態估計系統的效能。這就是“跨越寬基線的影像匹配: 從論文到實踐”和一系列 CVPR 影像匹配挑戰賽 的作用。它們使用最先進的運動結構演算法從數千張影像重建場景，並獲得每張影像的精確相機姿態。這些相機姿態被用作真值來評估影像匹配管道的不同部分，包括 RANSACs。
在我們的測試中，我們在 影像匹配挑戰賽 2021 資料集的驗證子集上運行了基準測試——PragueParks、GoogleUrban 和 Phottourism。我們檢測了 RootSIFT 特徵，使用最佳互斥 SNN 比例測試將其匹配，然後將它們饋送到經過測試的 RANSACs 中。將得到的基準矩陣轉換為相對姿態，並與真值姿態進行比較。您可以在論文“跨越寬基線的影像匹配: 從論文到實踐”中檢視詳細資訊。
對於所有 RANSACs，我們首先透過網格搜尋確定最佳內點閾值，而迭代次數 (max_iter) 設定為合理的 100k。然後，在修復此最佳閾值後，我們將迭代次數從 10 變化到 10M。這給了我們一條準確度-時間曲線。
評估的方法
在這裡，我們主要評估了在 OpenCV 中實現的 RANSAC 方法，但也添加了一些基線。包含的非 OpenCV 方法如下：
- PyRANSAC – 來自 pydegensac 包的 LO-RANSAC 實現。它應該大致等效於基本的 OpenCV RANSAC。LO 代表“區域性最佳化”，用於改進中間結果。
- DEGENSAC – 來自 pydegensac 包，基於該方法的原始實現，該方法在 CVPR 2005 年論文“不受主導平面影響的雙檢視幾何估計”中提出。當 基準矩陣 的形式的相對相機姿態是從所有位於同一平面的對應關係中估計的時，結果通常不正確。DEGENSAC 檢測並修復了此類情況。該演算法是 Image Matching Challenge 2020 和 2021 的預設選擇。
OpenCV 方法，以需要傳遞到 cv2.findFundamentalMatrix 函式的標誌命名，如下所示
- RANSAC — OpenCV (原始) RANSAC 實現，來自庫的先前版本，沒有花哨的功能。
- USAC_DEFAULT – 在演算法方面等同於上面的 DEGENSAC，但在實現細節上有所不同。
- USAC_FAST – 與上面的 USAC_DEFAULT 相同，但具有不同的硬編碼引數，並且由於在區域性最佳化步驟中使用的迭代次數少於 USAC_DEFAULT，因此可能工作速度更快——它還使用 RANSAC 分數來最大化內點數並更早地終止。
- USAC_ACCURATE — 實現最近的 圖割 RANSAC。它使用能量最小化圖割演算法，而不是簡單的區域性最佳化。它有時允許從包含離群值的樣本中估計正確的模型。
- USAC_MAGSAC — 它實現了另一種最近的演算法: MAGSAC++。它受到深度學習解決方案的啟發，使用迭代重新加權最小二乘最佳化與軟閾值相結合，以利用大致正確但精度不高的對應關係。
所有 OpenCV USAC 方法還使用 SPRT 測試 來加速評估。
結果
以下是所有 3 個數據集的結果。曲線越左越高越好。虛線垂直線標記了 1/25 秒（“即時”）和 0.5 秒（挑戰限制）時間預算。圖例顯示了方法名稱以及資料集的最佳內點閾值: Phototourism、GoogleUrban 和 PragueParks。
1. 第一個也是最主要的結論——所有新標誌都比舊的 OpenCV 實現 (綠色曲線，最差結果) 好得多，而舊的 OpenCV 實現仍然是預設選項。
2. 使用 10k 迭代次數和 USAC_ACCURATE (紅色曲線) 可以在 0.01 秒內獲得很好的結果。
3. 對於小型/中型時間預算 (小於 0.1 秒/影像)，所有 OpenCV 高階 USACs 都比 pydegensac (藍色曲線) 更好。
4. 對於更高的預算，最好的方法是 OpenCV USAC_MAGSAC 和 pydegensac 包中的 DEGENSAC。
5. 使用“USAC_FAST”標誌沒有意義——始終使用 USAC_DEFAULT、USAC_ACCURATE 或 USAC_MAGSAC 更好。
6. USAC_MAGSAC 是唯一一種在所有資料集中最佳閾值都相同的方法。對於實踐來說，這是一個寶貴的特性，因為它需要最少的調整。我建議將其用作預設解決方案
如果您對單個數據集的結果感興趣，請繼續閱讀。
Phototourism
GoogleUrban
PragueParks
為什麼在同一個集合上進行調整和評估?
確實，在同一個資料集上調整和評估方法沒有任何意義。但是，請允許我為我的選擇辯護。以下是論點：
1. 我不想損害測試集的完整性，測試集是正在進行的比賽 影像匹配挑戰賽 2021 的基礎，該比賽包含現金獎勵。因此，我不想洩露上述測試集的資訊，這是我的主要最佳化目標。我也不能在“訓練子集”上調整閾值，因為 GoogleUrban 和 PragueParks 都沒有這樣的引數。
2. 我們更關注速度與準確度的粗略權衡，而不是方法的精確排名——您資料集上的數字無論如何都會不同。很可能這些方法在驗證集上存在很小的準確度差距，但在測試集上會發生變化——正如我們 原始論文 中 DEGENSAC 和 MAGSAC 所發生的那樣。但是，在驗證集上表現不佳的方法神奇地在測試集上勝過所有人的可能性非常小。同樣，請參閱原始論文中的 PyRANSAC 與 DEGENSAC。
結論
新的 OpenCV RANSACs 速度很快，並且具有可比的準確度，您可以放心地選擇其中之一。我推薦 USAC_MAGSAC，因為它對內點閾值最不敏感。
使用正確的 RANSACs，享受快樂 🙂
