• RANSAC鲁棒算法

RANSAC过程与通常的光滑技术相反：不是用尽可能多的点去获得一个初始解并在以后消除无效点，RANSAC是使用满足可行条件的尽量少的初始数据集并在可能时用一致性数据集扩大它。

目标：一个模型与一个含有野值的数据集S的鲁棒拟合
算法：

1. 随机地从S中选择s个数据点组成的一个样本作为模型的一个示例；（备注：s的个数需要大于模型最小的个数即可，比如模型是直线则用两个点+，模型为平面则用三个点+……）
2. 确定在模型距离阈值t内的数据点集Si,Si,称为采样的一致集并定义S的内点
3. 如果Si的大小（内点数目）大于某个阈值T，用Si的所有重估计模型并结束
4. 如果si的大小小于阈值T，则重复上面的过程
5. 经过N次试验选择最大一致集Si，用Si的所有重估计模型。

三个问题：
以直线拟合为例：

• 什么距离阈值，如何选取？
  目的是希望选择的距离阈值t使点为内点的概率是 α \alpha α，该计算需要直到内点到模型的距离的概率分布，在实际中距离阈值通常靠经验选取，但是如果假定数据点的误差是服从零均值、标准差为 σ \sigma σ的高斯分布，在此中情况就可以利用距离的平方和服从*度为m的卡方分布确定，m为模型余维度，点的内点概率为 α = 0.95 \alpha=0.95 α=0.95时，距离阈值 t 2 = F m − 1 ( α ) σ 2 t^2=F_m^{-1}(\alpha)\sigma^2 t2=Fm−1​(α)σ2

• 采样多少次为宜？
  保证由s个点组成的随机样中至少有一次没有野值的概率为p，通常p取0.99，假定 ω \omega ω是任意选择的数据点为内点的概率，那么 ϵ = 1 − ω \epsilon = 1-\omega ϵ=1−ω 为野值的概率，那么至少需要N次选择，每次s个点，其中 ( 1 − ω s ) N = 1 − p (1-\omega^s)^N=1-p (1−ωs)N=1−p，从而
  N = l o g ( 1 − p ) / l o g ( 1 − l o g ( 1 − ϵ ) s ) N=log(1-p)/log(1-log(1-\epsilon)^s) N=log(1−p)/log(1−log(1−ϵ)s)

• 一致集多大适宜？
  -根据经验，给定数据中野值的假定比例后，如果一致集大小接近期望时迭代就可以终止

自适应地决定采样次数，通常数据中野值所占比例 ϵ \epsilon ϵ是未知的，对此情形，算法从 ϵ \epsilon ϵ最坏的估计开始，当发现更大的一致集时就把元估计更新，例如，如果最坏的估计是 ϵ = 0.2 \epsilon=0.2 ϵ=0.2，但一旦发现内点的一致集占数据的80%,那么估计更新为 ϵ = 0.2 \epsilon=0.2 ϵ=0.2从而调整采样次数