C/C++语言实现RANSAC算法

RANSAC（RANdom SAmple Consensus）是一种经典的模型参数估计算法，常用于计算机视觉、机器学习等领域。下面是使用C/C++实现RANSAC算法的代码示例。

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

// 随机取样函数
vector<int> random_sample(int n, int k) {
    vector<int> result;
    for (int i = 0; i < k; ++i) {
        int j = rand() % n;
        while (find(result.begin(), result.end(), j) != result.end()) {
            j = rand() % n;
        }
        result.push_back(j);
    }
    return result;
}

// 计算模型参数函数
vector<double> compute_model(vector<pair<double,double>> data) {
    vector<double> result;
    double x_mean = 0, y_mean = 0;
    for (auto p : data) {
        x_mean += p.first;
        y_mean += p.second;
    }
    x_mean /= data.size();
    y_mean /= data.size();
    double s_xy = 0, s_xx = 0;
    for (auto p : data) {
        s_xy += (p.first - x_mean) * (p.second - y_mean);
        s_xx += (p.first - x_mean) * (p.first - x_mean);
    }
    double slope = s_xy / s_xx;
    double intercept = y_mean - slope * x_mean;
    result.push_back(slope);
    result.push_back(intercept);
    return result;
}

// 计算误差函数
double compute_error(vector<pair<double,double>> data, vector<double> model) {
    double error = 0;
    for (auto p : data) {
        double y = model[0] * p.first + model[1];
        error += pow(y - p.second, 2);
    }
    return sqrt(error / data.size());
}

// RANSAC算法主要过程
vector<double> ransac(vector<pair<double,double>> data, int k, double threshold, int max_iterations) {
    vector<double> best_model;
    int best_score = 0;
    for (int i = 0; i < max_iterations; ++i) {
        vector<int> indices = random_sample(data.size(), k);
        vector<pair<double,double>> sample_data;
        for (auto index : indices) {
            sample_data.push_back(data[index]);
        }
        vector<double> model = compute_model(sample_data);
        double error = compute_error(data, model);
        int score = 0;
        for (auto p : data) {
            double y = model[0] * p.first + model[1];
            if (abs(y - p.second) < threshold) {
                score++;
            }
        }
        if (score > best_score) {
            best_score = score;
            best_model = model;
        }
    }
    return best_model;
}

int main() {
    srand(time(0));
    // 生成测试数据
    vector<pair<double,double>> data;
    for (int i = 0; i < 20; ++i) {
        double x = i + rand() / double(RAND_MAX);
        double y = 2 * x + rand() / double(RAND_MAX) - 0.5;
        data.push_back(make_pair(x, y));
    }
    // 调用RANSAC算法
    vector<double> model = ransac(data, 2, 0.1, 100);
    // 输出结果
    cout << "Best Model: y = " << model[0] << "x + " << model[1] << endl;
    return 0;
}

以上代码实现了一个简单的RANSAC算法，用于拟合一组带有噪声的点，得到最佳的直线模型。其中，函数`random_sample()`用于随机取样，函数`compute_model()`用于计算模型参数，函数`compute_error()`用于计算误差，函数`ransac()`为RANSAC算法主要过程。在主函数中，我们生成了一组带有噪声的点作为测试数据，并调用RANSAC算法进行拟合，输出结果为最佳的直线模型。