Scale Invariant Feature TransformWhy do we care about matching features?We want invariance!!!Types of invarianceSlide 5Slide 6Slide 7Slide 8How to achieve illumination invarianceHow to achieve scale invariancePyramidsSlide 12Differences Of GaussiansRotation InvarianceSlide 15Affine InvarianceActual SIFT featuresSIFT algorithm overviewSlide 19Actual SIFT stage outputMSER (a one minute survey)Actual MSER outputInitial imageThresholdSlide 25Slide 26Ears and Square (note: not actual algorithm output)How to use these features?But where does the magic end?Credits + ReferencesScale Invariant Feature TransformTom DuerigWhy do we care about matching features?Object RecognitionWide baseline matchingTracking/SFMWe want invariance!!!Good features should be robust to all sorts of nastiness that can occur between images.Types of invarianceIlluminationTypes of invarianceIlluminationScaleTypes of invarianceIlluminationScaleRotationTypes of invarianceIlluminationScaleRotationAffineTypes of invarianceIlluminationScaleRotationAffineFull PerspectiveHow to achieve illumination invarianceThe easy way (normalized)Difference based metrics (random tree, Haar, and sift)How to achieve scale invariancePyramids –Divide width and height by 2–Take average of 4 pixels for each pixel (or Gaussian blur)–Repeat until image is tiny–Run filter over each size image and hope its robustScale Space (DOG method)PyramidsHow to achieve scale invariancePyramids Scale Space (DOG method)–Pyramid but fill gaps with blurred images–Like having a nice linear scaling without the expense–Take features from differences of these images–If the feature is repeatably present in between Difference of Gaussians it is Scale Invariant and we should keep it.Differences Of GaussiansRotation InvarianceRotate all features to go the same way in a determined mannerTake histogram of Gradient directions (36 in paper for 1 every 10 degrees) Rotate to most dominant (maybe second if its good enough, sub-Bin accuracy)Rotation InvarianceAffine InvarianceEasy way: Warp your training and hopeFancy way: design your feature itself to be robust against affine transformations (SIFT method)Actual SIFT featuresRemember the gradient histograms we used for rotation invariance?Same theory, except keep N2 histograms (4 shown, 16 used)Note, use weighted contributions to avoid edge nastinessSIFT algorithm overviewGet tons of points from maxima+minima of DOGS Threshold on simple contrast (low contrast is generally less reliable than high for feature points)Threshold based on principal curvatures (technical term is linyness)SIFT algorithm overviewGradient, histogram, RotateTake old gradient, histogram regions using Gaussian weightingHand off beautiful robust feature to someone who cares (i.e. object recognizer, navigation software (SFM), or stereo matching algorithm)Actual SIFT stage outputMSER (a one minute survey)Maximally Stable Extremal RegionsGo through thresholds, grab regions which stay nearly the same through a wide range of thresholds (connected components then bounding ellipses) Keep those regions descriptors as featuresAs regions are illumination based warp ellipse to circle for affine invarianceActual MSER outputInitial imageThresholdThresholdThresholdEars and Square (note: not actual algorithm output)How to use these features?Distance could be L2 norm on histogramsMatch by (nearest neighbor distance)/(2nd nearest neighbor distance) ratio Object recognize with Hough of pose of points (ie, these three should be in line on object, gee… they are that’s the object all right)But where does the magic end?SIFT is relatively expensive (computationally) and copyrighted (the other type of expensive)MSER doesn’t work well with images with any motion blurInteresting alternatives: –GLOH (Gradient Location and Orientation Histogram)larger initial descriptor + PCA–SURF (Speeded Up Robust Features) possibly faster AND more robust?Credits + ReferencesMSER image from J. Matas, O. Chum, M. Urban, T. Pajdla “Robust Wide Baseline Stereo from Maximally Stable Extremal Regions”, BMVC, 2002SIFT keypoint images from F. Estrada & A Jepson & D. Fleet ‘s SIFT tutorial, 2004 GLOH “A performance evaluation of local descriptors”, Krystian Mikolajczyk and Cordelia Schmid, IEEE tran. On Pattern Analysis and Machine Intelligence, pp 1615—1630, 2005SURF “SURF: Speeded Up Robust Features”, Herbert Bay, Tinne Tuytelaars and Luc Van Gool Proceedings of the 9th European Conference on Computer Vision
View Full Document