计算机视觉基本原理——RANSAC
Reference：
1.计算机视觉基本原理——RANSAC
1. RANSAC简介
RANSAC(RAndom SAmple Consensus,随机采样一致)算法是从一组含有“外点”(outliers)的数据中正确估计数学模型参数的迭代算法。“外点”一般指的是数据中的噪声，比如说匹配中的误匹配和估计曲线中的离群点。所以，RANSAC也是一种“外点”检测算法。RANSAC算法是一种不确定算法，它只能在一种概率下产生结果，并且这个概率会随着迭代次数的增加而加大（之后会解释为什么这个算法是这样的）。
RANSAC主要解决样本中的外点问题，最多可处理50%的外点情况。
2. 基本思想
RANSAC通过反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点，并用下述方法进行验证：
- 一个模型适用于假设的局内点，即所有的未知参数都能从假设的局内点计算得出。
- 用1中得到的模型去测试所有的其它数据，如果某个点适用于估计的模型，认为它也是局内点。
- 如果有足够多的点被归类为假设的局内点，那么估计的模型就足够合理。
- 然后，用所有假设的局内点去重新估计模型，因为它仅仅被初始的假设局内点估计过。
- 最后，通过估计局内点与模型的错误率来评估模型。
这个过程被重复执行固定的次数，每次产生的模型要么因为局内点太少而被舍弃，要么因为它比现有的模型更好而被选用。
对上述步骤，可以简单总结为以下步骤：
N：样本个数 K：求解模型需要的最少的点的个数（对于直线拟合来说就是两个点，对于计算Homography矩阵就是四个点）
- 随机采样K个点
- 对该K个点拟合模型
- 计算其他点到拟合模型的距离。如果小于一定阈值，该点被当作内点，统计内点个数
- 重复M次，选择内点数最多的模型
- 利用所有的内点重新估计模型（可选）
3. 范例
RANSAC用于拟合直线：
1.随机选取
K
=
2
K=2
K
=
2
个点：
2. 拟合一条直线：
3. 统计内点个数，内点为绿色，此时的内点个数为9：
4. 重复上述过程M次，找到内点数最大的模型
5. 利用所有的内点重新估计直线
4. 迭代次数推导
迭代的次数，是可以估算出来的。假设“内点”在数据中的占比为p：
p
=
n
i
n
l
i
e
r
s
n
i
n
l
i
e
r
s
+
n
o
u
t
l
i
e
r
s
p=\frac{n_{inliers}}{n_{inliers}+n_{outliers}}
p
=
n
i
n
l
i
e
r
s
+
n
o
u
t
l
i
e
r
s
n
i
n
l
i
e
r
s
那么我们每次计算模型使用N个点的情况下，选取的点至少有一个外点的情况(采样失败的概率）就是：
1
−
p
K
1 – p^K
1
−
p
K
也就是说，在迭代k次的情况下，
(
1
−
p
K
)
M
(1-p^K)^M
(
1
−
p
K
)
M
就是
M
M
M
次迭代计算模型都至少采样到一个“外点”去计算模型的概率。那么能采样到正确的K个点去计算出正确模型的概率是：
z
=
1
−
(
1
−
p
K
)
M
z = 1 – (1-p^K)^M
z
=
1
−
(
1
−
p
K
)
M
通过上式，可以求得：
k
=
l
o
g
(
1
−
z
)
l
o
g
(
1
−
t
n
)
k = \frac{log(1-z)}{log(1-t^n)}
k
=
l
o
g
(
1
−
t
n
)
l
o
g
(
1
−
z
)
“内点”的概率
p
p
p
通常是一个先验值。然后
z
z
z
是我们希望RANSAC得到正确模型的概率。如果事先不知道
p
p
p
的值，可以使用自适应迭代次数的方法。也就是一开始设定一个无穷大的迭代次数，然后每次更新模型参数估计的时候，用当前的“内点”比值当成
p
p
p
来估算出迭代次数。
