# RANSAC Edge detection gives a lot of fragmented lines. A simple solution is to use least squares solution to find a line through these segments. But it has issues like: - Fitting performance is affected by the slope - Fails completely for vertical lines - Not robust to outliers RANSAC (Random Sample Consensus, Fischler & Bolles 1981) - Randomly select two samples (minimal number for a line) and check how many other samples fall close to the line (within a distance threshold). Choose the line which has the most number (thus consensus) - Similar concept to Median (excluding extreme values or outliers) Algorithm: (similar to [[Support Vector Machines (SVM)]]) 1. Sample (randomly) the number of points required to fit the model (#=2) 2. Solve for model parameters using the minimum set of samples 3. Score by the fraction of inliers within a preset threshold of the model Repeat 1-3 until the best model is found with high confidence ## Advantages - Robust to outliers - Applicable for large number of parameters ## Disadvantages - Computational time grows quickly with fraction of outliers and number of parameters - Not good for getting multiple line fits ## Common applications - Computing a rotation and translation between two images (will be used later for fundamental matrix in 2 view geometry) --- ## References