A Linear Fitting Algorithm Based on Modified Random Sample Consensus
Yujin Min, Yun Tang, Hao Chen, Faquan Zhang · Applied Sciences · 2025
When performing linear fitting on datasets containing outliers, common algorithms may face problems like inadequate fitting accuracy. We propose a linear fitting algorithm based on Locality-Sensitive Hashing (LSH) and Random Sample Consensus (RANSAC). Our algorithm combines the efficient similarity search capabilities of the LSH algorithm with the robust fitting mechanism of RANSAC. With proper hash functions designed, similar data points are mapped to the same hash bucket, thereby enabling the efficient identification and removal of outliers. RANSAC is then used to fit the model parameters of the processed dataset. The optimal parameters for the linear model are obtained after multiple iterative processes. This algorithm significantly reduces the influence of outliers on the dataset, resulting in improved fitting accuracy and enhanced robustness. Experimental results demonstrate that the proposed improved RANSAC linear fitting algorithm outperforms the Weighted Least Squares, traditional RANSAC, and Maximum Likelihood Estimation methods, achieving a reduction in the sum of squared residuals by 29%, 16%, and 8%, respectively.