Random Sample Consensus
- greedy
motivation
- how do we identify false edge pixels w/o iterating over all pairs like Hough Transform
- how do we eliminate false positive edge pixels without comparing it with every other edge pixel?
overview
- avoid impact of noisy outliers - look for inliers
- estimate the best line
- randomly sample a subset of points and calculate a line
- since edges can be noisy, we say that the line is an “inlier” if it is somewhere between boundary lines
- inliers calculated using distance from the point to the line
- remove the inlier points so that we don’t consider them again
algorithm
for k iterations
- select a seed subset of points to perform model estimate (group of edge points)
- compute hyperparameters (a,b) from seed group
- find inliers
- if num inliers is best so far, save parameters and inliers
if num inliers in best line < m, return no line
else, re-calculate final parameters with all inliers?
refining parameters
- find line that minimizes distance of all points to that line
- random - doesn’t get all lines while Hough Transform does
