MSAC 算法详解及与 RANSAC 对比示例

我们用一个简单的二维线性拟合实验展示 RANSAC 和 MSAC 的差异：

数据特点

• 主直线：y = 2.5x - 1.0
• 内点：添加小噪声
• near-outliers：数量较多、略偏离真实直线，接近 RANSAC 阈值

3. Python3 完整示例

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import numpy as np
import random
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt

# 固定随机种子
np.random.seed(42)
random.seed(42)

# 数据生成
def generate_data():
    X = np.linspace(0, 10, 60)
    y_true = 2.5 * X - 1.0
    y_inliers = y_true + np.random.normal(0, 0.3, size=X.shape)
    X_near = np.linspace(0, 10, 40)
    y_near = 2.5 * X_near - 1.0 + np.random.normal(1.5, 0.5, size=X_near.shape)
    X_all = np.concatenate([X, X_near])
    y_all = np.concatenate([y_inliers, y_near])
    points = list(zip(X_all, y_all))
    return points, X_all, y_all, y_true

# 拟合直线
def fit_line(points):
    xs = np.array([p[0] for p in points])
    ys = np.array([p[1] for p in points])
    a, b = np.polyfit(xs, ys, 1)
    return a, b

# RANSAC
def ransac(points, iterations=200, threshold=2.0):
    best_model = None
    best_inliers = []
    for _ in range(iterations):
        sample = random.sample(points, 2)
        a, b = fit_line(sample)
        inliers = [(x, y) for x, y in points if abs(y - (a * x + b)) < threshold]
        if len(inliers) > len(best_inliers):
            best_inliers = inliers
            best_model = (a, b)
    return best_model, best_inliers

# MSAC
def msac(points, iterations=200, threshold=2.0):
    best_model = None
    best_cost = float("inf")
    for _ in range(iterations):
        sample = random.sample(points, 2)
        a, b = fit_line(sample)
        cost = sum((y - (a * x + b)) ** 2 if abs(y - (a * x + b)) < threshold else threshold ** 2 for x, y in points)
        if cost < best_cost:
            best_cost = cost
            best_model = (a, b)
    return best_model, best_cost

# MSE 评估
def mse(model, points):
    a, b = model
    return np.mean([(y - (a * x + b)) ** 2 for x, y in points])

# 主程序
if __name__ == "__main__":
    points, X_all, y_all, y_true = generate_data()
    ransac_model, ransac_inliers = ransac(points)
    msac_model, msac_cost = msac(points)
    print("=== Model parameters ===")
    print("True line: y = 2.5x - 1.0")
    print(f"RANSAC line: y = {ransac_model[0]:.3f}x + {ransac_model[1]:.3f}")
    print(f"MSAC line: y = {msac_model[0]:.3f}x + {msac_model[1]:.3f}")
    print("\n=== Error comparison ===")
    print(f"RANSAC MSE: {mse(ransac_model, points):.4f}")
    print(f"MSAC MSE: {mse(msac_model, points):.4f}")

    # 可视化保存
    plt.figure(figsize=(8, 5))
    plt.scatter(X_all, y_all, s=10, color="gray", label="data")
    X_plot = np.linspace(0, 10, 100)
    plt.plot(X_plot, 2.5 * X_plot - 1, "k--", label="Ground truth")
    plt.plot(X_plot, ransac_model[0] * X_plot + ransac_model[1], "b", label="RANSAC")
    plt.plot(X_plot, msac_model[0] * X_plot + msac_model[1], "r", label="MSAC")
    plt.legend()
    plt.title("RANSAC vs MSAC (near-outliers visible)")
    plt.xlabel("x")
    plt.ylabel("y")
    plt.tight_layout()
    plt.savefig("ransac_vs_msac.png", dpi=150)
    plt.close()
    print("\nFigure saved to: ransac_vs_msac.png")

4. 运行效果

终端输出示例：

=== Model parameters ===
True line: y = 2.5x - 1.0
RANSAC line: y = 2.549x + -1.312
MSAC line: y = 2.504x + -1.072

=== Error comparison ===
RANSAC MSE: 0.6098
MSAC MSE: 0.5986
Figure saved to: ransac_vs_msac.png

灰色散点：数据 黑色虚线：真实直线 蓝色：RANSAC（被 near-outliers 拉偏） 红色：MSAC（贴近真实线）

5. 总结

1. MSAC 优势：

• 在 near-outliers 或多模型竞争场景下稳健
• 不仅考虑内点数量，还关注残差平方

2. RANSAC 优势：

• 简单快速
• 对内点占比高的任务已足够

3. 可视化实验：

• near-outliers 会显著拉偏 RANSAC
• MSAC 拟合更接近真实模型
• MSAC 是 RANSAC 的自然升级，适用于自动驾驶、点云拟合、相机标定等高精度任务。