那些网站可以做宣传/东莞百度推广排名

Random Sample Consensus RANSAC随机采样一致性

Location determination problem  LDP  位置确定问题

Least squares method LSM 最小二乘法

 

Local feature detector有两种错误：
1.classification errors  特征检测器没能正确检测到特征（严重错误 gross error）

2.measurement errors  特征检测器正确检测到特征了，但是把特征的一些参数计算错了，比如位置 （可以理解为由噪声带来，服从正态分布，可以用smoothing的方法最小化这个误差）

 

ransac的核心思想是使用尽量少的初始数据，然后用具有一致性的数据去扩大这个数据集。这个数据集就是我们要找的，可以用来建立model（去除了错误数据）的数据集。

有人做过实验，初始点选取的越少，需要进行的迭代次数越少。所以当然是根据自己的需要选取最少的点。

应该说ransac提供了一种思想和框架，在含有错误数据的数据集里拟合数据或者找到数据之间的映射关系。

比如拟合一个圆，ransac会选取三个点(因为三个点就能确定一个圆了)，计算这个圆的圆心和半径，然后统计足够靠近这个圆的点数（允许measurement error的存在），以此代表当前圆的拟合效果。如果拟合效果足够好，就在选中的点集上应用smoothing technique，例如LSM。

 

上述过程是一个迭代的过程，给定一个点集P，先是随机选取一些点S1，得到一个模型M1，然后让M1在某种误差允许范围内拟合P，被选出来的点集S1*称作S1 的一致性集合。如果#(S1*)>threshold，指的是S1*包含的点数，就用LSM得到一个模型M1*作为最终的模型；如果#(S1*)<threshold，再随机选取另外一些点S2，重复上述过程。

另外，如果迭代多次后，没有更多的点被选中，那么就把当前的点集作为最大的一致性集合。

 

两点注意：

1.如果问题类型确定了，选择初始点集可以确定点数，而不用随机，比如计算两张图的单应性矩阵，8个参数，选4个点就好了。

2.如果S*和M*确定了，又加了一些与S*一致的点，只需要在新的更大的点集上使用LSM。

 

三个参数：
1.error tolerance——判断这个点是不是属不属于当前模型

2.number of subsets to try——初始化模型采样的点数

3.threshold t——判断当前模型可不可取的需要包含的点数

 

关于error tolerance：
这个误差既跟模型有关，也跟数据有关。也跟衡量误差的方法有关。error tolerance通常有实现得来，可以设定为平均测量误差的标准差的2-3倍。

 

关于最大实验（抽样）次数：

找到n个优良点需要实验的次数（抽样的次数）为k

在当前的errortolerance下一个点是不是优良点的概率为w

待研究。。。。。

E(k)=1/wⁿ

k的标准差std(k)=sqrt[E(k²)-E(k)²]=[sqrt(1-wⁿ)]*(1/wⁿ)

Std(k)和E(k)差不多大。我们可以尝试标准差的2-3倍的次数

 

另一个思考的角度是，我们希望以z的概率保证至少有一次随机选取找到的n个点是优良的(误差允许范围内)，那么我们至少需要做k次实验。

即(1-wⁿ)^k=1-z

可以得到k=[log(1-z)]/[log(1-wⁿ)]

 

关于threshold t:

t的设置需要保证1.找到了正确的模型  2.找到了足够的点以进行接下来的smoothing procedure。

 

 

LDP

找到给定场景的two representation之间的联系。通常就是指特征点的坐标，可以是2-D的也可以是3-D的。

以前都是用的least-square的方法，但是它不能解决gross error的问题。

基于RANSAC解决LDP：

Given:
    data – a set of observeddata points
    model – amodel that can be fitted to data points
    n – theminimum number of data values required to fit the model
    k – themaximum number of iterations allowed in the algorithm
    t – athreshold value for determining when a data point fits a model
    d – thenumber 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 selectedvalues from data
    maybemodel = model parameters fittedto maybeinliers
    alsoinliers = empty set
    for every point in data not inmaybeinliers {
        if point fits maybemodel with anerror smaller than t
             add point to alsoinliers
    }
    if the number of elements inalsoinliers is > d {
        % this implies that we may havefound a good model
        % now test how good it is
        bettermodel = model parametersfitted to all points in maybeinliers and alsoinliers
        thiserr = a measure of how wellmodel fits these points
        if thiserr < besterr {
            bestfit = bettermodel
            besterr = thiserr
        }
    }
    increment iterations
}

return bestfit

利用RANSAC进行二维直线拟合的一个例子（matlab）：

function [bestParameter1,bestParameter2] = ransac_demo(data,num,iter,threshDist,inlierRatio)% data: a 2xn dataset with #n data points% num: the minimum number of points. For line fitting problem, num=2% iter: the number of iterations% threshDist: the threshold of the distances between points and the fitting line% inlierRatio: the threshold of the number of inliers %clear all;close all;clc%num =2;%iter = 100;%threshDist = 10;%inlierRatio = 0.5;% Plot the data pointsfigure;plot(data(1,:),data(2,:),'o');hold on;number = size(data,2); % Total number of pointsbestInNum = 0; % Best fitting line with largest number of inliersbestParameter1=0;bestParameter2=0; % parameters for best fitting linefor i=1:iter% Randomly select 2 pointsidx = randperm(number,num); sample = data(:,idx);   % Compute the distances between all points with the fitting line kLine = sample(:,2)-sample(:,1);% two points relative distancekLineNorm = kLine/norm(kLine);normVector = [-kLineNorm(2),kLineNorm(1)];%Ax+By+C=0 A=-kLineNorm(2),B=kLineNorm(1)distance = normVector*(data - repmat(sample(:,1),1,number));% Compute the inliers with distances smaller than the thresholdinlierIdx = find(abs(distance)<=threshDist);inlierNum = length(inlierIdx);% Update the number of inliers and fitting model if better model is found     if inlierNum>=round(inlierRatio*number) && inlierNum>bestInNumbestInNum = inlierNum;parameter1 = (sample(2,2)-sample(2,1))/(sample(1,2)-sample(1,1));parameter2 = sample(2,1)-parameter1*sample(1,1);bestParameter1=parameter1; bestParameter2=parameter2;endend% Plot the best fitting linexAxis = -number:number; yAxis = bestParameter1*xAxis + bestParameter2;plot(xAxis,yAxis,'r-','LineWidth',2);end

reference：

[1] Fischler M A, Bolles R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[M]//Readings in computer vision. 1987: 726-740.

[2] https://en.wikipedia.org/wiki/Random_sample_consensus