# A Linear Fitting Algorithm Based on Modified Random Sample Consensus
## 2 Common Linear Fitting Algorithm
### Random Sample Consensus  
The RANSAC algorithm is an iterative robust parameter estimation method used to fit the parameters of a mathematical model from a dataset. Its core concept involves repeatedly sampling data points randomly for model fitting. In each fitting iteration, inliers and outliers are identified based on the model's fitness, progressively converging towards the optimal model.  
A unique feature of RANSAC is its non-deterministic nature; during each iteration, the random selection of sample data may yield different fitting results. However, with sufficient iterations, RANSAC can enhance the probability of obtaining a reasonable fitting outcome. Each iteration generates a fitting result, and the algorithm assesses the model's validity by evaluating its compatibility with other data points in the dataset. Therefore, by setting a high number of iterations and an appropriate inlier threshold, a high-quality model estimate can be achieved. RANSAC is more robust compared to traditional methods such as least squares, especially in the presence of outliers, ensuring the accuracy and stability of the model.  
Many approaches in object pose estimation rely on predicting 2D-3D keypoint correspondences using RANSAC. As RANSAC is non-differentiable, correspondences cannot be directly learned in an end-to-end fashion. Reference [22] introduces a differentiable RANSAC layer into a well-known monocular pose estimation network. Reference [23] proposes a novel methodology that combines convolutional neural networks (CNNs) with the RANSAC algorithm, enhancing the accuracy and reliability of ring detection, even in the presence of noise or natural image variations. Reference [24] employs a feature-based registration approach using interest point detection and matching, enhanced using novel transformation recovery techniques by adjusting random sample consensus (RANSAC). By prioritizing coverage of matched points over the entire image, this method significantly boosts registration robustness. References [25; 26] present a novel scheme for robot localization as well as map representation that can successfully work with large-size and incremental maps. The work combines two works on incremental methods, iLSH and iRANSAC, for appearance-based and position-based localization. LSH uses a continuous representation of datapoints, and searches points that are near from the query point in \(l_{2}\) space. It is mainly used to solve the problem of incremental data.  
The iterative process of the RANSAC algorithm for fitting model parameters consists of several key steps:  
1. In each model fitting iteration, a subset of samples is randomly selected from the observed dataset to construct a candidate model based on the chosen samples.
2. The candidate model is used to evaluate all other data points in the dataset, determining which points best match the model. Based on the evaluation results, data points are classified as inliers (points that fit the model) or outliers (points that do not fit the model).
3. If the number of inliers in the current model exceeds that of the previous model, the current model is updated to be the best model.
4. These steps are repeated until either a predefined maximum number of iterations is reached or the best model satisfying the criteria is found. After completing all iterations, the best model is output.  
Figure 1 illustrates the iterative process and results of RANSAC. In a two-dimensional dataset containing outliers, RANSAC iteratively refines its fitting, accurately fitting a line  
that reflects the overall trend of the dataset while effectively eliminating the interference of outliers, thereby ensuring the fitting accuracy of the line model.