C13 - Robust Estimation

• in practice -> correspondences usually contamined by outliers (i.e. mismatches)

• repetitive patterns (i.e. features with same appearance)

• geometric and photometric changes (consistency assumption does not hold in real world…)

• large image noise

• occlusions

• moving objects

• image or motion blur

• inaccurate trajectory caused by noise

• wrong trajectory caused by outliers

• remove outliers and also estaimate the model parameters

• for reliable and accurate localization

• expectation maximization

• ransac

• robust kernel (M-estimator)

• various geometric problems

• whose goals are to estimate the parameters of a model from data

• e.g.:

  • essential matrix estination

  • fundamental matrix estimation

  • PnP

  • homography estimation

• expectaion maximization

• -> general method for model fitting in the presence of outliers

• has iterations

• -> at each iteration, performs E-step and M-step

• E-step:

  • assign each data a weight/outlier ratio

• M-step:

  • compute model parameters based on a weighted (obtained from E step) least-squares fitting

• initialization based on least-squares fitting

• -> simply fit model (i.e. line) to datapoints using least squares of distance

• no information about outliers and inliers -> treat all points equally

• => result obviously affected by outliers

• E-step -> weight assignment

• based on estimatoin -> calculate residual error for each data point

• use residual error to weight each data point (inversely proportional to weight

  • -> high residual error -> low weight

  • -> low residual error -> high weight

  • wi = e^-ri (exp function of negative residual error)

• weight from 0-1 is probability that data is an inlier

• M-step: -> re-estimation of moderl parameters

• formulate weighted least squares loss

• weighted leas squares parameters are new model parametsre

• -> should be better than last iteration…

• alternately perform step 2 and 3 till convergence

• -> accordingily, optimal parameters are obtained

• treat data whose weights are higher than a threshold as inliers

• highly sensitive to initialization

• -> strongly affected by few large error values (i.e. outliers)

• -> EM might converge to wrong soluton if initial solution is far from groundtruth

• random sample consensus (RANSAC)

• ->one of the most popular methods for model fitting in the presence of outliers

• not sensitive to initial condition

• no

• -> returns different result everytime you run it

• estimate model parameters

• remove outliers

• sample minimnal case at random

• -> i.e. line fitting 2 points, plane ditting 8; tsais -> 6

• calcualte model parametesr using sampled data (hypothesizing a model)

• after obtaining model parameters

• -> calcualte resodual error w.r.t. all datapoints

• select data that supports current hypothesis

• for each model (as we sample and fit more than one) associate one set of inliers

• if model computed by true inliers

• -> associated inlier set should have high cardinality

• repeat setp 1-4 k times

• -> hypothesize k models after k samplings

• -> k models associated with k inlier sets

• inlier set maximization

• -> select inlier set with highest cardinality

• calculate final model parameters using optimal inlier set

• -> use all true inliers of optimal inlier set

• -> to compute least squares solition

=> i.e. use only optimal inliers to compute the model parameters a last time -> can further imporve accuracy by noise compensation

-> altough step 6 is often good enough

• i.e. 8 point method vs 5 point method

• -> can be used for both

• but: sampling 5 correct points is more likely than sampling 8 correct points

• => RANSAC prefers to sue minimal solutoin

• yes

• -> if we can guarantee that all chosen points are inliers…

• yes

• L2 loss usually sensitive to outliers (as they are amplified)

• L2 closed form -> can be used for

• => introduction of Huber loss as robust kernel (i.e. loss function)

  
  

• more robust against outliers

• uses L2 in low error regions

• uses L1 loss in high error regions

• avoids outlier amplificatoin

• L1 difficult for derivative computation -> also somewhat compensated by huber

• EM/RANSAC -> iterative to remove outliers

• if outlier count relative low: directly use Huber loss and accept taht outliers are present (huber relative resistant against them…)

• -> huber as choice for robust kernel in photometric error…