前言
仍然是昨天的問題，別人問到最小二乘、霍夫變換、RANSAC在直線擬合上的區(qū)別。昨天梳理了霍夫變換，今天打算抽空梳理一下RANSAC算法，主要包括：
1）RANSAC理論介紹
2）RANSAC應(yīng)用簡介；
內(nèi)容為自己的學(xué)習記錄，其中很多地方借鑒了別人，最后一起給出鏈接。
一、RANSAC理論介紹
普通最小二乘是保守派：在現(xiàn)有數(shù)據(jù)下，如何實現(xiàn)最優(yōu)。是從一個整體誤差最小的角度去考慮，盡量誰也不得罪。
RANSAC是改革派：首先假設(shè)數(shù)據(jù)具有某種特性（目的），為了達到目的，適當割舍一些現(xiàn)有的數(shù)據(jù)。
給出最小二乘擬合（紅線）、RANSAC（綠線）對于一階直線、二階曲線的擬合對比：
可以看到RANSAC可以很好的擬合。RANSAC可以理解為一種采樣的方式，所以對于多項式擬合、混合高斯模型（GMM）等理論上都是適用的。
RANSAC的算法大致可以表述為（來自wikipedia）：
Given: data – a set of observed data points model – a model that can be fitted to data points n – the minimum number of data values required to fit the model k – the maximum number of iterations allowed in the algorithm t – a threshold value for determining when a data point fits a model d – the number of close data values required to assert that a model fits well to data Return: bestfit – model parameters which best fit the data (or nul if no good model is found) iterations = 0 bestfit = nul besterr = something really large while iterations < k { maybeinliers = n randomly selected values from data maybemodel = model parameters fitted to maybeinliers alsoinliers = empty set for every point in data not in maybeinliers { if point fits maybemodel with an error smaller than t add point to alsoinliers } if the number of elements in alsoinliers is > d { % this implies that we may have found a good model % now test how good it is bettermodel = model parameters fitted to all points in maybeinliers and alsoinliers thiserr = a measure of how well model fits these points if thiserr < besterr { bestfit = bettermodel besterr = thiserr } } increment iterations } return bestfitRANSAC簡化版的思路就是：
第一步：假定模型（如直線方程），并隨機抽取Nums個（以2個為例）樣本點，對模型進行擬合：
第二步：由于不是嚴格線性，數(shù)據(jù)點都有一定波動，假設(shè)容差范圍為：sigma，找出距離擬合曲線容差范圍內(nèi)的點，并統(tǒng)計點的個數(shù)：
第三步：重新隨機選取Nums個點，重復(fù)第一步~第二步的操作，直到結(jié)束迭代：
第四步：每一次擬合后，容差范圍內(nèi)都有對應(yīng)的數(shù)據(jù)點數(shù)，找出數(shù)據(jù)點個數(shù)最多的情況，就是最終的擬合結(jié)果：
至此：完成了RANSAC的簡化版求解。
這個RANSAC的簡化版，只是給定迭代次數(shù)，迭代結(jié)束找出最優(yōu)。如果樣本個數(shù)非常多的情況下，難不成一直迭代下去？其實RANSAC忽略了幾個問題：
每一次隨機樣本數(shù)Nums的選取：如二次曲線最少需要3個點確定，一般來說，Nums少一些易得出較優(yōu)結(jié)果；
抽樣迭代次數(shù)Iter的選取：即重復(fù)多少次抽取，就認為是符合要求從而停止運算？太多計算量大，太少性能可能不夠理想；
容差Sigma的選取：sigma取大取小，對最終結(jié)果影響較大；
這些參數(shù)細節(jié)信息參考：維基百科。
RANSAC的作用有點類似：將數(shù)據(jù)一切兩段，一部分是自己人，一部分是敵人，自己人留下商量事，敵人趕出去。RANSAC開的是家庭會議，不像最小二乘總是開全體會議。
附上最開始一階直線、二階曲線擬合的code(只是為了說明最基本的思路，用的是RANSAC的簡化版):
一階直線擬合：
| 123456789101112131415161718192021222324252627282930313233343536373839404142 | clc;clear all;close all; set(0,'defaultfigurecolor','w');%Generate dataparam = [3 2];npa = length(param);x = -20:20;y = param*[x; ones(1,length(x))]+3*randn(1,length(x));data = [x randi(20,1,30);... y randi(20,1,30)];%figurefiguresubplot 221plot(data(1,:),data(2,:),'k*');hold on;%Ordinary least square meanp = polyfit(data(1,:),data(2,:),npa-1);flms = polyval(p,x);plot(x,flms,'r','linewidth',2);hold on;title('最小二乘擬合');%RansacIter = 100;sigma = 1;Nums = 2;%number selectres = zeros(Iter,npa+1);for i = 1:Iteridx = randperm(size(data,2),Nums);if diff(idx) ==0 continue;endsample = data(:,idx);pest = polyfit(sample(1,:),sample(2,:),npa-1);%parameter estimateres(i,1:npa) = pest;res(i,npa+1) = numel(find(abs(polyval(pest,data(1,:))-data(2,:))<sigma));end[~,pos] = max(res(:,npa+1));pest = res(pos,1:npa);fransac = polyval(pest,x);%figuresubplot 222plot(data(1,:),data(2,:),'k*');hold on;plot(x,flms,'r','linewidth',2);hold on;plot(x,fransac,'g','linewidth',2);hold on;title('RANSAC'); |
二階曲線擬合：
二、RANSAC應(yīng)用簡介
RANSAC其實就是一種采樣方式，例如在圖像拼接（Image stitching）技術(shù)中：
第一步：預(yù)處理后（據(jù)說桶形變換，沒有去了解過）提取圖像特征（如SIFT）
第二步：特征點進行匹配，可利用歸一化互相關(guān)(Normalized Cross Correlation method, NCC)等方法。
但這個時候會有很多匹配錯誤的點：
這就好比擬合曲線，有很多的誤差點，這個時候就想到了RANSAC算法：我不要再兼顧所有了，每次選取Nums個點匹配 → 計算匹配后容差范圍內(nèi)的點數(shù) → 重復(fù)實驗，迭代結(jié)束后，找出點數(shù)最多的情況，就是最優(yōu)的匹配。
利用RANSAC匹配：
第三步：圖像拼接，這個就涉及拼接技術(shù)了，直接給出結(jié)果：
參考：
RANSAC：https://en.wikipedia.org/wiki/Random_sample_consensus
圖像拼接：http://blog.csdn.net/xiaoch1222/article/details/53510895
http://www.cnblogs.com/xingshansi/p/6763668.html
