机器视觉：ransac算法详解

目录

一、说明：

二、算法步骤

三、算法代码

四、其它补充

一、说明：

        在线性回归问题中，采样点具备明显的线性相关性；如下图左。然而有些情性中，噪声很大，线性性散布在非线性点的噪声中，将无法用线性回归 的方法进行直线提取。

         随机样本一致性 (RANSAC) 是一种迭代方法，用于从一组包含异常值的观察数据中估计数学模型的参数，此时异常值不会对估计值产生影响。因此，它也可以解释为一种异常值检测方法。 [1]从某种意义上说，它是一种非确定性算法，它仅以一定的概率产生合理的结果，随着允许更多的迭代，这种概率会增加。该算法于 1981 年由 SRI International 的 Fischler 和 Bolles 首次发布。他们使用 RANSAC 来解决位置确定问题 (LDP)，其目标是确定空间中投射到图像上的点到一组地标中已知地点。

二、算法步骤

RANSAC 算法的输入是一组观测数据值、一种将某种模型拟合到观测值的方法以及一些置信度参数。 RANSAC 通过重复以下步骤来实现其目标：

• 选择原始数据的随机子集。将此子集称为假设的内点。
• 将模型拟合到一组假设的内点。
• 然后针对拟合模型测试所有其他数据。根据某些特定于模型的损失函数，那些很好地拟合估计模型的点被视为共识集的一部分。
• 如果足够多的点已被归类为共识集的一部分，则估计模型相当好。
• 之后，可以通过使用共识集的所有成员重新估计模型来改进模型。

算法步骤说明：

1）给定数据点如图

 2）随机找出2点作为假象拟合连线为L，则任意点与P距离小于阈值s，认为在线上，否则不在线上；显然下图的线上点为4

 3）再次随机抽取两点做为假象拟合线，如下图：显然线上点为7；因此，原先的模型点，被目前的模型点取代。

 4）继续随机抽取两点作为模型，直到线上点数量不再增加为止。最终拟合结果也就得到。

一维度的ransac算法。直线拟合，可以构成曲线拟合，或者曲面拟合。

三、算法代码

# !/usr/bin/env python # -*- coding: utf-8 -*- # @Time : 2021/1/4 18:42 # @Author : shaocanfan # @File : Ransac.py import numpy as np import matplotlib.pyplot as plt import random import math # 数据量。 SIZE = 50 # 产生数据。np.linspace 返回一个一维数组，SIZE指定数组长度。 # 数组最小值是0，最大值是10。所有元素间隔相等。 X = np.linspace(0, 10, SIZE) Y = 3 * X + 10 fig = plt.figure() # 画图区域分成1行1列。选择第一块区域。 ax1 = fig.add_subplot(1,1, 1) # 标题 ax1.set_title("RANSAC") # 让散点图的数据更加随机并且添加一些噪声。 random_x = [] random_y = [] # 添加直线随机噪声 for i in range(SIZE): random_x.append(X[i] + random.uniform(-0.5, 0.5)) random_y.append(Y[i] + random.uniform(-0.5, 0.5)) # 添加随机噪声 for i in range(SIZE): random_x.append(random.uniform(0,10)) random_y.append(random.uniform(10,40)) RANDOM_X = np.array(random_x) # 散点图的横轴。 RANDOM_Y = np.array(random_y) # 散点图的纵轴。 # 画散点图。 ax1.scatter(RANDOM_X, RANDOM_Y) # 横轴名称。 ax1.set_xlabel("x") # 纵轴名称。 ax1.set_ylabel("y") # 使用RANSAC算法估算模型 # 迭代最大次数，每次得到更好的估计会优化iters的数值 iters = 100 # 数据和模型之间可接受的差值 sigma = 0.25 # 最好模型的参数估计和内点数目 best_a = 0 best_b = 0 pretotal = 0 # 希望的得到正确模型的概率 P = 0.99 for i in range(iters): # 随机在数据中红选出两个点去求解模型 sample_index = random.sample(range(SIZE * 2),2) x_1 = RANDOM_X[sample_index[0]] x_2 = RANDOM_X[sample_index[1]] y_1 = RANDOM_Y[sample_index[0]] y_2 = RANDOM_Y[sample_index[1]] # y = ax + b 求解出a，b a = (y_2 - y_1) / (x_2 - x_1) b = y_1 - a * x_1 # 算出内点数目 total_inlier = 0 for index in range(SIZE * 2): y_estimate = a * RANDOM_X[index] + b if abs(y_estimate - RANDOM_Y[index]) < sigma: total_inlier = total_inlier + 1 # 判断当前的模型是否比之前估算的模型好 if total_inlier > pretotal: iters = math.log(1 - P) / math.log(1 - pow(total_inlier / (SIZE * 2), 2)) pretotal = total_inlier best_a = a best_b = b # 判断是否当前模型已经符合超过一半的点 if total_inlier > SIZE: break # 用我们得到的最佳估计画图 Y = best_a * RANDOM_X + best_b # 直线图 ax1.plot(RANDOM_X, Y) text = "best_a = " + str(best_a) + "\nbest_b = " + str(best_b) plt.text(5,10, text, fontdict={'size': 8, 'color': 'r'}) plt.show()

四、其它补充

        确定数据点何时适合模型 t 的阈值，以及断言模型与数据 d 良好拟合所需的接近数据点的数量是根据应用程序和数据集的特定要求确定的，并且可能基于实验评估。

        然而，可以使用理论结果将迭代次数 k 确定为所需成功概率 p 的函数。令 p 为 RANSAC 算法在运行后提供至少一个有用结果的期望概率。如果 RANSAC 在某些迭代中选择估计模型参数的 n 个点时仅从输入数据集中选择内点，则返回成功的结果。令w 为每次选择单个点时选择内点的概率，即：

        一个常见的情况是 w 事先并不为人所知，但可以给出一些粗略的值。假设估计模型所需的 n 个点是独立选择的，是所有 n 个点都是内点的概率，是 n 个点中至少有一个是异常值的概率，这种情况意味着将从该点集估计出一个坏模型。 k 次方的概率是算法永远不会选择一组 n 个点的概率，这些点都是内点，这必须与 {\displaystyle 1-p}1-p 相同。所以，