1、算法簡介
隨機抽樣一致算法(RANdom SAmple Consensus,RANSAC)。它是一種迭代的方法，用來在一組包含離群的被觀測數據中估算出數學模型的參數。 RANSAC是一個非確定性算法，在某種意義上說，它會產生一個在一定概率下合理的結果，其允許使用更多次的迭代來使其概率增加。此RANSAC算法在1981年由Fischler和Bolles首次提出。
RANSAC的基本假設是 “內群”數據可以通過幾組模型參數來敘述其數據分布，而“離群”數據則是不適合模型化的數據。 數據會受噪聲影響,噪聲指的是離群，例如從極端的噪聲或錯誤解釋有關數據的測量或不正確的假設。 RANSAC假定，給定一組（通常很小）的內群，存在一個程序，這個程序可以估算最佳解釋或最適用於這一數據模型的參數。
2、范例
這裡用一個簡單的例子來說明，在一組數據點中找到一條最適合的線。 假設，此有一組集合包含了內群以及離群，其中內群為可以被擬合到線段上的點，而離群則是無法被擬合的點。如果我們用簡單的最小平方法來找此線，我們將無法得到一條適合於內群的線，因為最小平方法會受離群影響而影響其結果。而RANSAC，可以只由內群來計算出模型，而且概率還夠高。 然而，RANSAC無法保證結果一定最好，所以必須小心選擇參數,使其能有足夠的概率。
3、概述
在數據中隨機選擇幾個點設定為內群
計算適合內群的模型
把其它剛才沒選到的點帶入剛才建立的模型中，計算是否為內群
記下內群數量
重復以上步驟多做幾次
比較哪次計算中內群數量最多,內群最多的那次所建的模型就是我們所要求的解
這裡有幾個問題
一開始的時候我們要隨機選擇多少點(n)
以及要重復做多少次(k)
4、參數確定
假設每個點時真正內群的概率為 w
w = 內群的數目/（內群數目+外群數目）通常我們不知道 w 是多少, w^n是所選擇的n個點都是內群的機率, 1-w^n 是所選擇的n個點至少有一個不是內群的機率, (1 − w^n)^k 是表示重復 k 次都沒有全部的n個點都是內群的機率, 這邊定算法跑 k 次以後成功的機率是p，那麼,
1 − p = (1 − w^n)^kp = 1 − (1 − w^n)^k所以如果希望成功機率高，p = 0.99, 當n不變時，k越大,p越大, 當w不變時，n越大,所需的k就越大, 通常w未知,所以n 選小一點比較好。
5、應用
RANSAC常被用在電腦視覺 ，例如，對應點問題 和 估算立體攝影機雙眼相對點的基本矩陣。
6、C實現源碼
[cpp] view plaincopyprint?float Ransac
(
Point2D32f* points,
size_t Cnt,
float *line,
int numForEstimate,
float successProbability,
float maxOutliersPercentage
){
//1 − p = (1 − w^n)^k
//p =
//float outlierPercentage = maxOutliersPercentage;//估計值
float numerator = log(1.0f-successProbability);
float denominator = log(1.0f- pow(1.0-maxOutliersPercentage, numForEstimate));
//隨機抽取一定比例的點
int ransac_times = (int)(numerator/denominator + 0.5);
printf("ransac_times： %d\n", ransac_times);
int numDataObjects = Cnt;
//int numForEstimate = Cnt*0.1;
int maxVoteCnt = 0;
float tempLine[4];
float inliersPercentage = 0.0;
int *Chosen = new int[numDataObjects];
Point2D32f *subPoints = new Point2D32f[numForEstimate];
int pointCnt = 0;
int voteCnt = 0;
for(int i = 0; i < ransac_times; i++)
{
//隨機抽取
//randomly select data for exact model fit ('numForEstimate' objects).
memset(Chosen,0,numDataObjects*sizeof(int));
int maxIndex = numDataObjects-1;
for(int j = 0; j < numForEstimate; j++)
{
int selectedIndex = rand() % numDataObjects;
Chosen[selectedIndex] = 1;
}
//擬合
pointCnt = 0;
for(int k = 0; k < numDataObjects; k++)
{
if(Chosen[k])
{
subPoints[pointCnt].x = points[k].x;
subPoints[pointCnt].y = points[k].y;
pointCnt++;
}
}
FitLine2D(subPoints, pointCnt, tempLine);
float a = tempLine[1]/tempLine[0];
float b = tempLine[3] - a*tempLine[2];
//擬合完整之後要對擬合的結果進行鑒定，選出最優的結果
voteCnt = 0;
for(int k = 0; k < Cnt; k++)
{
//如果在直線上或者附近
if(abs(points[k].y - a*points[k].x - b) < 2)
{
voteCnt++;
}
}
if(voteCnt > maxVoteCnt)
{
maxVoteCnt = voteCnt;
inliersPercentage = (float)maxVoteCnt/Cnt;
// printf("a: %f\tb%f\tpercent: %f\n", a, b, inliersPercentage);
for(int m = 0; m < 4; m++)
{
line[m] = tempLine[m];
}
}
//當inliers的比例比較高的時候就可以直接取該值作為最優解
// if(inliersPercentage > 0.2)
// {
// return inliersPercentage;
// }
}
return inliersPercentage;
}
float Ransac
(
Point2D32f* points,
size_t Cnt,
float *line,
int numForEstimate,
float successProbability,
float maxOutliersPercentage
){
//1 − p = (1 − w^n)^k
//p =
//float outlierPercentage = maxOutliersPercentage;//估計值
float numerator = log(1.0f-successProbability);
float denominator = log(1.0f- pow(1.0-maxOutliersPercentage, numForEstimate));
//隨機抽取一定比例的點
int ransac_times = (int)(numerator/denominator + 0.5);
printf("ransac_times： %d\n", ransac_times);
int numDataObjects = Cnt;
//int numForEstimate = Cnt*0.1;
int maxVoteCnt = 0;
float tempLine[4];
float inliersPercentage = 0.0;
int *Chosen = new int[numDataObjects];
Point2D32f *subPoints = new Point2D32f[numForEstimate];
int pointCnt = 0;
int voteCnt = 0;
for(int i = 0; i < ransac_times; i++)
{
//隨機抽取
//randomly select data for exact model fit ('numForEstimate' objects).
memset(Chosen,0,numDataObjects*sizeof(int));
int maxIndex = numDataObjects-1;
for(int j = 0; j < numForEstimate; j++)
{
int selectedIndex = rand() % numDataObjects;
Chosen[selectedIndex] = 1;
}
//擬合
pointCnt = 0;
for(int k = 0; k < numDataObjects; k++)
{
if(Chosen[k])
{
subPoints[pointCnt].x = points[k].x;
subPoints[pointCnt].y = points[k].y;
pointCnt++;
}
}
FitLine2D(subPoints, pointCnt, tempLine);
float a = tempLine[1]/tempLine[0];
float b = tempLine[3] - a*tempLine[2];
//擬合完整之後要對擬合的結果進行鑒定，選出最優的結果
voteCnt = 0;
for(int k = 0; k < Cnt; k++)
{
//如果在直線上或者附近
if(abs(points[k].y - a*points[k].x - b) < 2)
{
voteCnt++;
}
}
if(voteCnt > maxVoteCnt)
{
maxVoteCnt = voteCnt;
inliersPercentage = (float)maxVoteCnt/Cnt;
// printf("a: %f\tb%f\tpercent: %f\n", a, b, inliersPercentage);
for(int m = 0; m < 4; m++)
{
line[m] = tempLine[m];
}
}
//當inliers的比例比較高的時候就可以直接取該值作為最優解
// if(inliersPercentage > 0.2)
// {
// return inliersPercentage;
// }
}
return inliersPercentage;
}
7、優缺點
RANSAC的優點是它能魯棒的估計模型參數。例如，它能從包含大量局外點的數據集中估計出高精度的參數。RANSAC的缺點是它計算參數的迭代次數沒有上限；如果設置迭代次數的上限，得到的結果可能不是最優的結果，甚至可能得到錯誤的結果。RANSAC只有一定的概率得到可信的模型，概率與迭代次數成正比。RANSAC的另一個缺點是它要求設置跟問題相關的閥值。
RANSAC只能從特定的數據集中估計出一個模型，如果存在兩個（或多個）模型，RANSAC不能找到別的模型。
