主要貢獻(xiàn)

本文提出了一種使用局部優(yōu)化算法改進(jìn)RANSCA精度的方法，其主要貢獻(xiàn)為：

1、提出了一種考慮空間一致性的內(nèi)點(diǎn)判斷方法，從而改進(jìn)了RANSCA算法的精度；

2、采用圖割算法解決內(nèi)點(diǎn)判斷的優(yōu)化問題，提高了算法的效率。

算法流程

傳統(tǒng)的RANSCA算法主要包括如下步驟：

1、隨機(jī)采樣計算模型需要的最少數(shù)據(jù)；

2、由采樣的數(shù)據(jù)計算出模型參數(shù)；

3、計算其余數(shù)據(jù)對模型的匹配程度；

4、重復(fù)1-3直到找到匹配程度最高的模型。

其中，第三步的判斷方法一般為：分別判斷每一個數(shù)據(jù)與模型的距離是否小于某一個閾值，滿足則定義為內(nèi)點(diǎn)，否則定義為野點(diǎn)。這樣的判斷準(zhǔn)則比較生硬，且沒有考慮數(shù)據(jù)的空間一致性。

本文的主要工作就是改進(jìn)了第三步的準(zhǔn)則。下面將進(jìn)行具體的介紹：

1、基于能量函數(shù)最小化的內(nèi)點(diǎn)判斷

當(dāng)計算得到模型時，內(nèi)點(diǎn)的判斷可以看做一個最小化能量函數(shù)的問題，傳統(tǒng)的RANSCA算法內(nèi)點(diǎn)判斷問題等價于：

其中，

上式中，Lp即為點(diǎn)的真實(shí)標(biāo)簽(內(nèi)點(diǎn)為1，野點(diǎn)為0)，也是需求取的變量。容易看出，上式的解即為：距離小于閾值的點(diǎn)為1，大于閾值的點(diǎn)為0——與傳統(tǒng)的判別方法一致。

由于標(biāo)簽值只有0和1，因此比較生硬，無法更細(xì)致的刻畫點(diǎn)和模型的匹配程度，因此往往引入核函數(shù)(如高斯函數(shù))，此時：

其中，

2、空間一致性

空間一致性是指：在空間上相近的點(diǎn)，往往具有相同的標(biāo)簽(內(nèi)點(diǎn)或野點(diǎn))。本文將這一思想引入RANSCA中。考慮到可能出現(xiàn)野點(diǎn)多于內(nèi)點(diǎn)的情況，提出了如下的準(zhǔn)則：

上式第一行表示：懲罰標(biāo)簽不一致的鄰近點(diǎn)；第二行表示：如果兩個點(diǎn)都為野點(diǎn)，則其與模型的接近程度越大，給予的懲罰越大；第三行表示：如果兩個點(diǎn)都為內(nèi)點(diǎn)，則其與模型越匹配，懲罰越小。

3、GG-RANSCA

整個GG-RANSCA算法如下：

其中為控制局部優(yōu)化的次數(shù)，使得局部優(yōu)化的效果盡可能發(fā)揮最大，本文提出了如下準(zhǔn)則：僅當(dāng)μ12大于一定值時，才進(jìn)行局部優(yōu)化。

μ1，μ2表示對當(dāng)前模型的置信度。

其中的局部優(yōu)化算法為：

圖模型的構(gòu)建算法為：

由于待求解變量的取值為0和1，因此可以使用基于圖割的算法進(jìn)行快速的求解。

主要結(jié)果

作者在仿真和真實(shí)數(shù)據(jù)上進(jìn)行了實(shí)驗，并與經(jīng)典RANSAC, LO-RANSAC , LO+-RANSAC, LO’-RANSAC, and EP-RANSAC等算法進(jìn)行了對比，實(shí)驗結(jié)果如下：

1、2D線段檢測仿真實(shí)驗

該實(shí)驗使用仿真合成的數(shù)據(jù)：在600x600的圖像中，生成一條直線，并采樣100個點(diǎn)，對采樣點(diǎn)加入高斯白噪聲。實(shí)驗數(shù)據(jù)示意圖如下：

圖1. 直線(a)和點(diǎn)畫線(b)擬合算法結(jié)果示例。1000個黑色點(diǎn)是野點(diǎn)，100個紅色點(diǎn)為內(nèi)點(diǎn)。

實(shí)驗結(jié)果如下：

圖2. 擬合出的直線的平均角度誤差隨噪聲強(qiáng)度的變化曲線。對于每一個噪聲強(qiáng)度，算法跑1000次。線的類型和野點(diǎn)數(shù)量為(a)直線，100%，(b)直線，500%，(c)虛線，100%，(d)虛線，500%。

表1. 在直線擬合和基本矩陣估算實(shí)驗中，能得到正確解所需的最小內(nèi)點(diǎn)采樣比率。對于直線擬合實(shí)驗，實(shí)驗結(jié)果為所有實(shí)驗的平均值——在三個不同的野點(diǎn)率(100%，500%，1000%)和不同噪聲強(qiáng)度(0-9個像素)各運(yùn)行1000次，因此總共運(yùn)行了15000次。對于基本矩陣估算實(shí)驗，實(shí)驗結(jié)果為AdelaideRMF數(shù)據(jù)集上運(yùn)行1000次的平均結(jié)果。

2、基于真實(shí)圖像數(shù)據(jù)的單應(yīng)矩陣、仿射矩陣、基本矩陣以及本質(zhì)矩陣的估計

具體實(shí)驗條件及實(shí)驗參數(shù)設(shè)置，請查閱原文。實(shí)驗結(jié)果為：

表2. 基本矩陣估算的數(shù)據(jù)集為：kusvod2 (24 對圖片), AdelaideRMF (19 對圖片) 和Multi-H (4 對圖片)；單應(yīng)矩陣估計數(shù)據(jù)集為：homogr (16 對圖片) 和EVD (15 對圖片)；本質(zhì)矩陣估算數(shù)據(jù)集為：strecha (467 對圖片),仿射變換估計數(shù)據(jù)集為：SZTAKI Earth Observation(52對圖片)。因此，本文總共在597張圖片中測試了提出的算法。前三列顯示了數(shù)據(jù)集、問題(F/H/E/A)、圖片對的數(shù)量。后五列為在99%置信度60FPS計算速度的限制下的測試結(jié)果(EP-RANSCA不受速度限制，因為它不能實(shí)時運(yùn)行)。對于其他列，實(shí)驗不設(shè)置時間限制，且置信度設(shè)為95%。結(jié)果為1000次運(yùn)行的平均值。LO是局部優(yōu)化的次數(shù)，括號中為圖割算法運(yùn)行的次數(shù)。模型的幾何誤差記錄與第二行；平均的處理時間和需要的樣本數(shù)記錄在第三和第四行。對于基本矩陣和本質(zhì)矩陣幾何誤差為Sampson距離，對于單應(yīng)矩陣和仿射矩陣，幾何誤差為投影誤差。

Abstract

A novel method for robust estimation, called Graph-Cut RANSAC1, GC-RANSAC in short, is introduced. To separate inliers and outliers, it runs the graph-cut algorithm in the local optimization (LO) step which is applied when a so-far-the-best model is found. The proposed LO step is conceptually simple, easy to implement, globally optimal and efficient. GC-RANSAC is shown experimentally, both on synthesized tests and real image pairs, to be more geometrically accurate than state-of-the-art methods on a range of problems, e.g. line fitting, homography, affine transformation, fundamental and essential matrix estimation. It runs in real-time for many problems at a speed approximately equal to that of the less accurate alternatives (in milliseconds on standard CPU).

【泡泡機(jī)器人SLAM】公眾號。

泡泡機(jī)器人SLAM的原創(chuàng)內(nèi)容均由泡泡機(jī)器人的成員花費(fèi)大量心血制作而成，希望大家珍惜我們的勞動成果，轉(zhuǎn)載請務(wù)必注明出自【泡泡機(jī)器人SLAM】微信公眾號，否則侵權(quán)必究！同時，我們也歡迎各位轉(zhuǎn)載到自己的朋友圈，讓更多的人能進(jìn)入到SLAM這個領(lǐng)域中，讓我們共同為推進(jìn)中國的SLAM事業(yè)而努力！

商業(yè)合作及轉(zhuǎn)載請聯(lián)系liufuqiang_robot@hotmail.com

總結(jié)

以上是生活随笔為你收集整理的efficientransac_【泡泡图灵智库】基于图割优化的RANSAC算法（CVPR）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。