1. 定义

根据一组包含异常数据的样本数据集，计算出数据的数学模型参数，得到有效样本数据的算法

从一组含有“外点”(outliers)的数据中正确估计数学模型参数的迭代算法
“外点”一般指的的数据中的噪声，比如说匹配中的误匹配和估计曲线中的离群点

2. 功能

利用RANSAC剔除错误匹配，配对提取关键的特征，即可用于图片拼接和物体识别定位

在模型确定以及最大迭代次数允许的情况下，RANSAC总是能找到最优解
对于包含80%误差的数据集，RANSAC的效果远优于直接的最小二乘法

3. 流程

RANSAC是通过反复选择数据集去估计出模型，一直迭代到估计出认为比较好的模型

具体的实现步骤可以分为以下几步：

选择出可以估计出模型的最小数据集
使用这个最小数据集来计算出数据模型
将所有数据带入这个模型，计算出“内点”的数目
比较当前模型和之前推出的最好的模型的“内点“的数量，记录最大“内点”数的模型参数和“内点”数
重复以上步骤，直到达到最大迭代次数或者内点数目大于一定数量，即当前模型已经足够好了，迭代结束

利用知乎计算机视觉基本原理——RANSAC 中的一张图可视化一下流程：
在这里插入图片描述

4. 迭代次数推导

这里有一点就是迭代的次数应该选择多大？
这个值其实是可以估算出来的

假设“内点”在数据中的占比为 t

[公式]

那么每次计算模型使用N个点的情况下，选取的点至少有一个外点的情况就是
在这里插入图片描述
即在迭代 k 次的情况下， 1 - t^n 就是 k 次迭代计算模型都至少采样到一个“外点”去计算模型的概率
那么能采样到正确的N个点去计算出正确模型的概率就是：

通过上式，可以求得

[公式]

5. 实现直线拟合

import numpy as np
import matplotlib.pyplot as plt
import random
import math# 设置数据量
pionts_sum = 100# 设置数据准确概率和希望的得到正确模型的概率
P_set, P_expect = 0.6, 0.6# 分配正常和噪声数据
pionts_line_sum = int(pionts_sum * P_set)
pionts_noise_sum = pionts_sum - pionts_line_sum# 产生 x=[0, 10]间隔相等的直线数据
A, B = 7, 10
X_min, X_max = 0, 10
X = np.linspace(X_min, X_max, pionts_line_sum)
Y = A * X + B# 直线随机差值和可接受的差值
line_sigma = 0.1
allow_sigma = 1# 添加直线随机噪声
random_x, random_y = [], []
for i in range(pionts_line_sum):random_x.append(X[i] + random.uniform(-line_sigma, line_sigma))random_y.append(Y[i] + random.uniform(-line_sigma, line_sigma))# 添加随机噪声
for i in range(pionts_noise_sum):random_x.append(random.uniform(X_min, X_max))random_y.append(random.uniform(int(min(Y)), int(max(Y))))# 散点图的横纵轴
RANDOM_X = np.array(random_x)
RANDOM_Y = np.array(random_y)# 初始迭代最大次数
iters = 100# 最好模型的参数估计和内点数目
Best_A, Best_B = 0, 0
point_inner_sum = 0# 开始迭代
count = 0
while count < iters:count += 1# 随机在数据中红选出两个点去求解模型sample_index = random.sample(range(pionts_sum), 2)x_1, y_1 = RANDOM_X[sample_index[0]], RANDOM_Y[sample_index[0]]x_2, y_2 = RANDOM_X[sample_index[1]], RANDOM_Y[sample_index[1]]# 求解出a，ba = (y_2 - y_1) / (x_2 - x_1)b = y_1 - a * x_1# 计算内点数目point_inner_count = 0for index in range(pionts_sum):y_estimate = a * RANDOM_X[index] + bif abs(y_estimate - RANDOM_Y[index]) < allow_sigma:point_inner_count += 1# 计算当前内点比值P_now = point_inner_count / pionts_sum# 判断当前的模型是否比之前估算的模型好if point_inner_count > point_inner_sum:# 用当前的内点比值当成内点的概率iters = count + math.log(1 - P_set) / math.log(1 - pow(P_now, 2))point_inner_sum = point_inner_countBest_A, Best_B = a, b# 判断是否当前模型已经符合期望if P_now > P_expect:breakprint("迭代完成，共迭代{}次，当前内点比值：{}".format(count, P_now))# 最佳估计
Y = Best_A * RANDOM_X + Best_B# 新建标题RANSAC区域图
fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
ax.set_title("RANSAC")# 设置轴名称
ax.set_xlabel("x")
ax.set_ylabel("y")# 画散点图
ax.scatter(RANDOM_X, RANDOM_Y)# 画估计直线图
ax.plot(RANDOM_X, Y, linewidth=5, color='g')text = "Best_A = {:.2f} Best_B = {:.2f}".format(Best_A, Best_B)
plt.text(int(X_max / 2), int(max(Y)), text, fontdict={'size': 10, 'color': 'r'})
plt.show()