# A Linear Fitting Algorithm Based on Modified Random Sample Consensus
## 3 Modified Random Sample Consensus-Based Linear Fitting Algorithm
### Random Sample Consensus Based on Locality-Sensitive Hashing Algorithm  
The LSH-RANSAC algorithm combines the efficient similarity search of LSH with the robust fitting mechanism of RANSAC, aiming to quickly eliminate outliers in the data and accurately fit the best model. For the observed dataset \(D=(x_{i},y_{i})\), the goal is to fit a line model \(y=ax+b\). The specific process for fitting the linear parameter model using the LSH-RANSAC algorithm is as follows:  
1. The hash function based on random hyperplanes is given by \[h(x)=\text{sgn}(x\cdot\
u)\] (12) where \(\
u\) is a two-dimensional random vector, with each component independently following a standard normal distribution \(N(0,1)\), and \(x\cdot\
u\) is the projection of \(x\) onto \(\
u\). The sgn function is defined as: \[\text{sgn}(x)= \begin{cases}1,&\text{if }x\geqslant 0\\ 0,&\text{if }x<0\end{cases} \] (13) The similarity between two points can be represented using the Euclidean distance function. The hash function projects data points into hash buckets via random hyperplane projections, with the Euclidean distance determining whether the projections of the data points are similar. The Euclidean distance formula in two-dimensional space is given by \[d(x,y)=\sqrt{(x_{1}-y_{1})^{2}+(x_{2}-y_{2})^{2}}\] (14) In this equation, a smaller value of (d(x,y)) indicates a higher similarity between the data points, increasing the probability that they share the same hash value. 2. To enhance the effective mapping of similar data points into the same hash bucket, multiple hash functions are typically employed, representing data points as a vector of multiple binary bits: \[b(x_{i})=\left\{h_{1}(x_{i}),h_{2}(x_{i}),\ldots,h_{k}(x_{i})\right\}\in\{0,1 \}^{k}\] (15) where \(k\) is the number of hash functions. After random hyperplane projection, for the dataset \(D=(x_{i},y_{i})\), we obtain the corresponding binary vector set \(B\): \[B= \begin{bmatrix}b(x_{1})\\ b(x_{2})\\ \vdots\\ b(x_{i})\end{bmatrix} = \begin{bmatrix}h_{1}(x_{1})&h_{2}(x_{1})&\cdots&h_{k}(x_{ 1})\\ h_{1}(x_{2})&h_{2}(x_{2})&\cdots&h_{k}(x_{2})\\ \vdots&\vdots&\ddots&\vdots\\ h_{1}(x_{i})&h_{2}(x_{i})&\cdots&h_{k}(x_{i})\end{bmatrix} \] (16)A threshold \(T\) is set, and for each data point \(x_{i}\), the number of similar data points, i.e., the number of neighbors \(N(x_{i})\) is computed. If \(N(x_{i})<T\), the data point is considered an outlier and is removed. The resulting processed dataset is \(D^{\prime}=\{(x^{\prime}_{i},y^{\prime}_{i})\}\). 4. From the processed dataset \(D^{\prime}=\{(x^{\prime}_{i},y^{\prime}_{i})\}\), a minimal sample set is randomly selected. For line fitting, the minimal sample set requires two data points. 5. The selected subset is used to fit the line model \(y=ax+b\), and the model parameters \(a\) and \(b\) are computed using the following formulas: \[a=\frac{n\sum_{i=1}^{n}x_{i}y_{i}-\sum_{i=1}^{n}x_{i}\sum_{i=1}^{n}y_{i}}{n \sum_{i=1}^{n}x_{i}^{2}-(\sum_{i=1}^{n}x_{i})^{2}}\] (17) \[b=\frac{\sum_{i=1}^{n}y_{i}-a\sum_{i=1}^{n}x_{i}}{n}\] (18) The distance \(d_{i}\) from each point in the dataset to the current fitted line is calculated as \[d_{i}=\frac{|ax_{i}+b-y_{i}|}{\sqrt{a^{2}+1}}\] (19)
6. A threshold \(\theta\) is defined to check whether the distance \(d_{i}\) from each point to the fitted line is less than \(\theta\). If \(d_{i}<\theta\), the data point is an inlier, and the number of inliers for each iteration is recorded. If the number of inliers in this iteration exceeds that of the previous iteration, the model parameters are updated. 7. Steps 5 to 7 are repeated, each time selecting a new subset for model fitting until either the maximum iteration count is reached or the current line model fit is deemed satisfactory (i.e., the number of inliers reaches the predefined threshold \(T\)).