LMedS

The outlier-rejection algorithm called Least Median of Squares (LMedS) is conceptually very similar to RANSAC: as in RANSAC, a model is generated from random samples of the input data; however, instead of selecting the model that gathers the largest number of consensus samples (or minimizes a loss function), LMedS selects the model with the smallest median error. All input data are therefore compared with the model, sorted by error, and the median value is evaluated.

The relationship between the probability of detecting inliers and the number of iterations is the same as in RANSAC. However, RANSAC requires two parameters—the number of iterations and the threshold for determining whether an element belongs to the data set—whereas LMedS requires only the former. By construction, however, LMedS tolerates at most 50% outliers.

A good overview of RANSAC, M-SAC, and LMedS techniques can be found in (CKY09).