RANSAC迭代估计

港控/mmm° 2022-11-02 13:19 123阅读 0赞

### RANSAC迭代估计 ###

*  1. 定义
 *  2. 功能
 *  3. 流程
 *  4. 迭代次数推导
 *  5. 实现直线拟合

--------------------

# 1. 定义 #

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

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

--------------------

# 2. 功能 #

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

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

--------------------

# 3. 流程 #

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

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

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

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

--------------------

# 4. 迭代次数推导 #

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

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

![\[公式\]][20210225172906118.png_pic_center]

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

通过上式，可以求得

![\[公式\]][20210225173113155.png_pic_center]

--------------------

# 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，b
        a = (y_2 - y_1) / (x_2 - x_1)
        b = y_1 - a * x_1
    
        # 计算内点数目
        point_inner_count = 0
        for index in range(pionts_sum):
            y_estimate = a * RANDOM_X[index] + b
            if 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_count
            Best_A, Best_B = a, b
    
        # 判断是否当前模型已经符合期望
        if P_now > P_expect:
            break
    
    print("迭代完成，共迭代{}次，当前内点比值：{}".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()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNjE4MzI3_size_16_color_FFFFFF_t_70_pic_center 1]

--------------------

完整代码：  
[CSDN ][CSDN]  
[Github][]

--------------------

谢谢

[_RANSAC]: https://zhuanlan.zhihu.com/p/45532306
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNjE4MzI3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/fc88186bcc6049fc8c7be20f33f4c9fc.png
[20210225172906118.png_pic_center]: /images/20221024/fe15a82539e343dcb6e62bdb62f2deea.png
[20210225172945785.png_pic_center]: /images/20221024/2c3aa565104049bc9b11bae0c78c0753.png
[20210225173042122.png_pic_center]: /images/20221024/7cf696099af7418e8f9054d935f72433.png
[20210225173113155.png_pic_center]: /images/20221024/adce1da4ba14413888e3f4304b8fadf2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNjE4MzI3_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/fc5688e5756f470998d5d3b9ea1b9f94.png
[CSDN]: https://codechina.csdn.net/qq_32618327/a-simple-explanation/-/blob/main/ransac.py
[Github]: https://github.com/JoveH-H/A-simple-explanation/blob/master/ransac.py