Feature Matching and RANSACProject #3 ShowcaseProject #3 ShowcaseProject #3 ShowcaseProject #3 ShowcaseProject #3 ShowcaseProject #3 ShowcaseProject #3 ShowcaseProject #3 ShowcaseProject #3 ShowcaseProject #3 ShowcaseProject #3 ShowcaseProject #3 ShowcaseProject #3 ShowcaseProject #3 ShowcaseMulti-Scale Oriented PatchesDescriptor VectorDetections at multiple scalesMOPS descriptor vectorFeature matchingFeature matchingWhat about outliers?Feature-space outlier rejectionFeature-space outlier rejectionFeature-space outliner rejectionMatching featuresRAndom SAmple ConsensusRAndom SAmple ConsensusLeast squares fitRANSAC for estimating homographyRANSACExample: Recognising PanoramasWhy “Recognising Panoramas”?Why “Recognising Panoramas”?Why “Recognising Panoramas”?Why “Recognising Panoramas”?Why “Recognising Panoramas”?Why “Recognising Panoramas”?Why “Recognising Panoramas”?Why “Recognising Panoramas”?OverviewRANSAC for HomographyRANSAC for HomographyRANSAC for HomographyProbabilistic model for verificationFinding the panoramasFinding the panoramasFinding the panoramasFinding the panoramasHomography for RotationBundle AdjustmentBundle AdjustmentMulti-band BlendingResultsFeature Matching and RANSAC15-463: Computational PhotographyAlexei Efros, CMU, Fall 2005with a lot of slides stolen fromSteve Seitz and Rick Szeliski© Krister ParmstrandProject #3 ShowcasemromProject #3 ShowcaseheegunlProject #3 ShowcasejmacalliProject #3 ShowcaselmsProject #3 ShowcasecmcameroProject #3 ShowcaseslimProject #3 ShowcasecmcameroProject #3 ShowcasenvyasslimProject #3 ShowcaselmsProject #3 ShowcasemromProject #3 ShowcaseheegunlProject #3 ShowcasebhoncmcameroProject #3 ShowcasechenyuwuProject #3 ShowcaseslimMulti-Scale Oriented PatchesInterest points• Multi-scale Harris corners• Orientation from blurred gradient• Geometrically invariant to rotationDescriptor vector• Bias/gain normalized sampling of local patch (8x8)• Photometrically invariant to affine changes in intensity[Brown, Szeliski, Winder, CVPR’2005]Descriptor VectorOrientation = blurred gradientRotation Invariant Frame• Scale-space position (x, y, s) + orientation (θ)Detections at multiple scalesMOPS descriptor vector8x8 oriented patch• Sampled at 5 x scaleBias/gain normalisation: I’ = (I – μ)/σ8 pixels40 pixelsFeature matching?Feature matching• Exhaustive search• for each feature in one image, look at all the other features in the other image(s)• Hashing• compute a short descriptor from each feature vector, or hash longer descriptors (randomly)• Nearest neighbor techniques• k-trees and their variantsWhat about outliers??Feature-space outlier rejectionLet’s not match all features, but only these that have “similar enough” matches?How can we do it? • SSD(patch1,patch2) < threshold• How to set threshold?Feature-space outlier rejectionA better way [Lowe, 1999]:• 1-NN: SSD of the closest match• 2-NN: SSD of the second-closestmatch• Look at how much better 1-NN is than 2-NN, e.g. 1-NN/2-NN• That is, is our best match so much better than the rest?Feature-space outliner rejectionCan we now compute H from the blue points?• No! Still too many outliers…• What can we do?Matching featuresWhat do we do about the “bad” matches?RAndom SAmple ConsensusSelect one match, count inliersRAndom SAmple ConsensusSelect one match, count inliersLeast squares fitFind “average” translation vectorRANSAC for estimating homographyRANSAC loop:1. Select four feature pairs (at random)2. Compute homography H (exact)3. Compute inliers where SSD(pi’, H pi)< ε4. Keep largest set of inliers5. Re-compute least-squares H estimate on all of the inliersRANSACExample: Recognising PanoramasM. Brown and D. Lowe, University of British ColumbiaWhy “Recognising Panoramas”?Why “Recognising Panoramas”?1D Rotations (θ)• Ordering ⇒ matching imagesWhy “Recognising Panoramas”?1D Rotations (θ)• Ordering ⇒ matching imagesWhy “Recognising Panoramas”?1D Rotations (θ)• Ordering ⇒ matching imagesWhy “Recognising Panoramas”?• 2D Rotations (θ, φ)– Ordering ⇒ matching images1D Rotations (θ)• Ordering ⇒ matching imagesWhy “Recognising Panoramas”?1D Rotations (θ)• Ordering ⇒ matching images• 2D Rotations (θ, φ)– Ordering ⇒ matching imagesWhy “Recognising Panoramas”?1D Rotations (θ)• Ordering ⇒ matching images• 2D Rotations (θ, φ)– Ordering ⇒ matching imagesWhy “Recognising Panoramas”?OverviewFeature MatchingImage MatchingBundle AdjustmentMulti-band BlendingResultsConclusionsRANSAC for HomographyRANSAC for HomographyRANSAC for HomographyProbabilistic model for verificationFinding the panoramasFinding the panoramasFinding the panoramasFinding the panoramasParameterise each camera by rotation and focal lengthThis gives pairwise homographiesHomography for RotationBundle AdjustmentNew images initialised with rotation, focal length of best matching imageBundle AdjustmentNew images initialised with rotation, focal length of best matching imageMulti-band BlendingBurt & Adelson 1983• Blend frequency bands over range
View Full Document