1CSE486, Penn StateRobert CollinsLecture 15Robust Estimation : RANSACCSE486, Penn StateRobert CollinsRECALL: Parameter Estimation:General Strategy• Least-Squares estimation from point correspondencesLet’s say we have found point matches between two images, andwe think they are related by some parametric transformation (e.g. translation; scaled Euclidean; affine). How do we estimate theparameters of that transformation?But there are problems with that approach....CSE486, Penn StateRobert CollinsProblem : OutliersLoosely speaking, outliers are points that don’t “fit” the model.outlieroutlierCSE486, Penn StateRobert CollinsBad Data => OutliersLoosely speaking, outliers are points that don’t “fit” the model.Points that do fit are called “inliers”outlieroutlierinliersCSE486, Penn StateRobert CollinsProblem with OutlierscompareLeast squares estimation is sensitive to outliers,so that a few outliers can greatly skew the result.Least squaresregression withoutliersSolution: Estimation methodsthat are robust to outliers.CSE486, Penn StateRobert CollinsOutliers aren’t the Only ProblemMultiple structures can alsoskew the results. (the fit procedureimplicitly assumes there is only oneinstance of the model in the data).2CSE486, Penn StateRobert CollinsRobust Estimation• View estimation as a two-stage process:– Classify data points as outliers or inliers– Fit model to inliers while ignoring outliers• Example technique: RANSAC(RANdom SAmple Consensus)M. A. Fischler and R. C. Bolles (June 1981). "RandomSample Consensus: A Paradigm for Model Fitting withApplications to Image Analysis and AutomatedCartography". Comm. of the ACM 24: 381--395.CSE486, Penn StateRobert CollinsRansac ProcedureCSE486, Penn StateRobert CollinsRansac ProcedureCSE486, Penn StateRobert CollinsCount = 4Ransac ProcedureCSE486, Penn StateRobert CollinsRansac ProcedureCSE486, Penn StateRobert CollinsCount = 6Ransac Procedure3CSE486, Penn StateRobert CollinsRansac ProcedureCSE486, Penn StateRobert CollinsCount = 19Ransac ProcedureCSE486, Penn StateRobert CollinsRansac ProcedureCSE486, Penn StateRobert CollinsCount = 13Ransac ProcedureCSE486, Penn StateRobert CollinsCount = 4Count = 6Count = 19Count = 13Ransac ProcedureCSE486, Penn StateRobert Collins(Forsyth & Ponce)sssNNdddTT4CSE486, Penn StateRobert CollinsHow Many Samples to Choose?1 - (1- ( 1 - e ) ) = psNe = probability that a point is an outliers = number of points in a sampleN = number of samples (we want to compute this)p = desired probability that we get a good sampleSolve the following for N:Where in the world did that come from? ….CSE486, Penn StateRobert CollinsHow Many Samples to Choose?1 - (1- ( 1 - e ) ) = psNe = probability that a point is an outliers = number of points in a sampleN = number of samples (we want to compute this)p = desired probability that we get a good sampleProbability that choosing one point yields an inlierCSE486, Penn StateRobert CollinsHow Many Samples to Choose?1 - (1- ( 1 - e ) ) = psNe = probability that a point is an outliers = number of points in a sampleN = number of samples (we want to compute this)p = desired probability that we get a good sampleProbability of choosing s inliers in a row (sampleonly contains inliers)CSE486, Penn StateRobert CollinsHow Many Samples to Choose?1 - (1- ( 1 - e ) ) = psNe = probability that a point is an outliers = number of points in a sampleN = number of samples (we want to compute this)p = desired probability that we get a good sampleProbability that one or morepoints in the sample were outliers(sample is contaminated).CSE486, Penn StateRobert CollinsHow Many Samples to Choose?1 - (1- ( 1 - e ) ) = psNe = probability that a point is an outliers = number of points in a sampleN = number of samples (we want to compute this)p = desired probability that we get a good sampleProbability that N sampleswere contaminated.CSE486, Penn StateRobert CollinsHow Many Samples to Choose?1 - (1- ( 1 - e ) ) = psNe = probability that a point is an outliers = number of points in a sampleN = number of samples (we want to compute this)p = desired probability that we get a good sampleProbability that at leastone sample was not contaminated (at least one sample of spoints is composed of onlyinliers).5CSE486, Penn StateRobert CollinsHow many samples?Choose N so that, with probability p, at least one randomsample is free from outliers. e.g. p=0.991177272784426958588163543320847293973724167461465726171264572341713953435191197433171176532250%40%30%25%20%10%5%sproportion of outliers eCSE486, Penn StateRobert CollinsExample: N for the line-fitting problem• n = 12 points• Minimal sample size s = 2• 2 outliers: e = 1/6 => 20%• So N = 5 gives us a 99% chance of getting a pure-inlier sample– Compared to N = 66 by trying every pair of pointsfrom Hartley & ZissermanCSE486, Penn StateRobert CollinsAcceptable consensus set?• We have seen that we don’t have to exhaustively samplesubsets of points, we just need to randomly sample N subsets.• However, typically, we don’t even have to sample N sets!• Early termination: terminate when inlier ratio reachesexpected ratio of inliers( ) ∗(total number of data points)eT−=1CSE486, Penn StateRobert CollinsRANSAC: Picking Distance Threshold d• Usually chosen empirically• But…when measurement error is known to be Gaussian withmean 0 and variance s2:– Sum of squared errors follows a χ2 distribution with m DOF, where mis the DOF of the error measure (the codimension)– (dimension + codimension) = dimension of parameter space• E.g., m = 1 for line fitting because error is perpendicular distance• E.g., m = 2 for point distance• Examples for probability p = 0.95 that point is inlier5.99 s2Homography, camera matrix23.84 s2Line, fundamental matrix1d2ModelmCSE486, Penn StateRobert CollinsAfter RANSAC• RANSAC divides data into inliers and outliers and yieldsestimate computed from minimal set of inliers with greatestsupport• Improve this initial estimate with Least Squares estimationover all inliers (i.e., standard minimization)• Find inliers wrt that L.S. line, and compute L.S. one more time.from Hartley & ZissermanCSE486, Penn StateRobert CollinsPractical Example• Stabilizing aerial imagery using RANSAC- find corners in two images- hypothesize matches using NCC- do RANSAC to find matches consistent with anaffine transformation- take the inlier set found and estimate a fullprojective transformation