RANSAC算法詳解

1、給定兩個(gè)點(diǎn)pl與p2的坐標(biāo)，確定這兩點(diǎn)所構(gòu)成的直線，要求對于輸入的任意點(diǎn) p3，都可以判斷它是否在該直線上。初中解析幾何知識(shí)告訴我們，判斷一個(gè)點(diǎn)在 直線上，只需其與直線上任意兩點(diǎn)點(diǎn)斜率都相同即可。實(shí)際操作當(dāng)中，往往會(huì)先根 據(jù)已知的兩點(diǎn)算出直線的表達(dá)式（點(diǎn)斜式、截距式等等），然后通過向量計(jì)算即可 方便地判斷p3是否在該直線上。生產(chǎn)實(shí)踐中的數(shù)據(jù)往往會(huì)有一定的偏差。例如我們知道兩個(gè)變量X與Y之間呈線性關(guān)系，Y=aX+b，我們想確定參數(shù)a與b的具體值。通過實(shí)驗(yàn)，可以 得到 一組X與Y的測試值。雖然理論上兩個(gè)未知數(shù)的方程只需要兩組值即可確認(rèn)，但 由于系統(tǒng)誤差的原因，任意取兩點(diǎn)算出的a與b的值都不盡相同。

2、我們希望的是，最后計(jì)算得出的理論模型與測試值的誤差最小。大學(xué)的高等數(shù)學(xué)課程中，詳細(xì) 闡述了最小二乘法的思想。通過計(jì)算最小均方差關(guān)于參數(shù)a、b的偏導(dǎo)數(shù)為零時(shí)的值。事實(shí)上，在很多情況下，最小二乘法都是線性回歸的代名詞。遺憾的是，最小二乘法只適合與誤差較小的情況。試想一下這種情況，假使 需要從一個(gè)噪音較大的數(shù)據(jù)集中提取模型（比方說只有20%的數(shù)據(jù)時(shí)符合模型的）時(shí)，最小二乘法就顯得力不從心了。例如下圖，肉眼可以很輕易地看出一條直 線（模式），但算法卻找錯(cuò)了。RANSAC算法的輸入是一組觀測數(shù)據(jù)（往往含有較大的噪聲或無效點(diǎn)）， 一個(gè)用于解釋觀測數(shù)據(jù)的參數(shù)化模型以及一些可信的參數(shù)。RANSAC通過反復(fù)選擇

3、數(shù)據(jù)中的一組隨機(jī)子集來達(dá)成目標(biāo)。被選取的子集被假設(shè)為局內(nèi)點(diǎn)，并用下述方 法進(jìn)行驗(yàn)證：? 有一個(gè)模型適應(yīng)于假設(shè)的局內(nèi)點(diǎn)，即所有的未知參數(shù)都能從假設(shè)的局內(nèi)點(diǎn)計(jì)算得 出。? 用 1 中得到的模型去測試所有的其它數(shù)據(jù)，如果某個(gè)點(diǎn)適用于估計(jì)的模型，認(rèn)為它 也是局內(nèi)點(diǎn)。? 如果有足夠多的點(diǎn)被歸類為假設(shè)的局內(nèi)點(diǎn)，那么估計(jì)的模型就足夠合理。? 然后，用所有假設(shè)的局內(nèi)點(diǎn)去重新估計(jì)模型（譬如使用最小二乘法），因?yàn)樗鼉H僅 被初始的假設(shè)局內(nèi)點(diǎn)估計(jì)過。? 最后，通過估計(jì)局內(nèi)點(diǎn)與模型的錯(cuò)誤率來評估模型。? 上述過程被重復(fù)執(zhí)行固定的次數(shù)，每次產(chǎn)生的模型要么因?yàn)榫謨?nèi)點(diǎn)太少而被舍棄， 要么因?yàn)楸痊F(xiàn)有的模型更好而被選用。整個(gè)過程

4、可參考下圖：關(guān)于算法的源代碼，Ziv Yaniv曾經(jīng)寫一個(gè)不錯(cuò)的C+版本，我在關(guān)鍵處增補(bǔ)了注釋：C代碼白#in elude#in eludeLi neParamEstimator.hLineParamEstimator: LineParamEstimator (double delta ) : m_deltaSquared (delta * delta ) */* Compute the line parameters n_x,n_y,a_x,a_y*通過輸入的兩點(diǎn)來確定所在直線，采用法線向量的方式來表示，以兼容平 行或垂直的情況*其中n_x,n_y為歸一化后，與原點(diǎn)構(gòu)成的法線向量，a_x,a

5、_y為直線上任 意一點(diǎn)*/void LineParamEstimator : estimate (std : vector &datastd : vector ¶meters )parameters . clear ();if (data . size () y - data 0-y;doubleny= data 0- x - data 1-x;原始直線的斜率為K，則法線的斜率為-1/kdouble norm = sqrt (nx*nx + ny*ny);parameters.push_back(nx/norm);parameters.push_back(ny/norm);parame

6、ters.push_back(data 0-x);parameters.push_back(data 0-y); _/*/* Compute the line parameters n_x,n_y,a_x,a_y*使用最小二乘法，從輸入點(diǎn)中擬合出確定直線模型的所需參量*/ &data ,stdvector ¶meters )double meanX, meanY, nx , ny , norm ;double covMatll , covMat12 , covMat21 , covMat22 ; / The entr ies of the symmetric covari nace m

7、atrixint i , dataSize = data . size ();parameters . clear ();if (data . size () x;meanY +=data i - y;covMatll+=data i -x* datai- x;covMat12+=data i -x* datai- y;covMat22+=data i -y* datai- y;meanX /= dataSize ;meanY /= dataSize ;covMat11-= dataSize* meanX meanXcovMat12-= dataSize * meanX mea nYcovMa

8、t22-= dataSize*mea nY*mea nYcovMat21= covMat12;if (covMatll 1e-12 ) nx=1.0 ;ny=0.0 ;else /lamdal is the largest eige nvalue of the covaria nee matrix/and is used to compute the eig ne-vector corresp onding to the smallest/eige nv alue, which isnt computed explicitly.double lamdal = (covMatll + covMa

9、t22 + sqrt ( covMatll - covMat22 )*( covMatll - covMat22 ) + 4*covMat12 *covMat12 ) / 2.0 ;nx = - covMat12 ;ny= lamdal- covMat22 ;norm = sqrt (nx*nx + ny *ny);nx/= n orm;ny/= norm;parameters.push_back(nx);parameters.push_back(ny);parameters.push_back(meanX);parameters . push_back (meanY); _/*/* Give

10、 n the line parameters n_x,n_y,a_x,a_y check if* n_x, n_y dot data.x-a_x, data.y-a_y m_delta*通過與已知法線的點(diǎn)乘結(jié)果，確定待測點(diǎn)與已知直線的匹配程度；結(jié)果越 小則越符合，為*零則表明點(diǎn)在直線上*/bool LineParamEstimator: agree (std : vector parameters,Point2D &data )double signedDistanee= parameters 0*( data . x-parameters 2)+ parameters 1*( data .

11、y- parameters 3);return( signedDistanee*signedDistanee) m_deltaSquared );RANSAC尋找匹配的代碼如下：C代碼離/*/template double Ransac: compute (std : vector ¶meters , Paramete rEsitmator * paramEstimator , std : vector &data , int numForEstimate )std : vector leastSquaresEstimateData ;int numDataObjects= data

12、. size ();int num VotesForBest= -1;int *arr = new int numForEstimate ;/ numForEstimate 表示擬合模型所需要的最少點(diǎn)數(shù)，對本例的直線來說，該值為2short *curVotes = new short numDataObjects ; /one if datai agrees with the current model, otherwise zeroshort *bestVotes = new short numDataObjects ; /one if datai agrees with the best

13、model, otherwise zero/there are less data objects than the minimum required for an exact fitif (numDataObjects numForEstimate )return 0;/計(jì)算所有可能的直線，尋找其中誤差最小的解。對于100點(diǎn)的直線擬合來說，大約需要100*99*0.5=4950次運(yùn)算，復(fù)雜度無疑是龐大的。一般米用隨機(jī)選取子集的方式。computeAIIChoices ( paramEstimator , data , numForEstimate , bestVotes, curVotes

14、, numVotesForBest , 0, data . size(), numForEstimate , 0, arr );/compute the least squares estimate using the largest sub setfor (int j =0; j leastSquaresEstimate (leastSquaresEstimateD ata , parameters );deletearr ;deletebestVotes ;deletecurVotes ;return( double ) leastSquaresEstimateData . size ()/( double ) numDataObjects;在模型確定以及最大迭代次數(shù)允許的情況下，RANSAC總是能找到最優(yōu)解。經(jīng)過我的實(shí)驗(yàn)，對于包含 80%誤差的數(shù)據(jù)集，RANSAC的效果遠(yuǎn)優(yōu)于直接的最小 二乘法。RANSAC可以用于哪些場景呢？最著名的莫過于圖片的拼接技術(shù)。優(yōu)于鏡頭 的限制，往往需要多張照片才能拍下那種巨幅的風(fēng)景。在多幅圖像合成時(shí)，事先會(huì)在待合成的圖片中提取一些關(guān)鍵的特征點(diǎn)