Distinctive Image Features from Scale-Invariant KeypointsGoalKey requirements for good featureBrief HistoryHarris Corner Detector:SIFT Algorithm OverviewKeypoint Selection: Scale spaceKeypoint Selection: why DoG’s?Back to picking keypointsVisual representation of processVisual representation of process (cont.)A More Visual RepresentationA More Visual Representation (cont.)Slide 15Slide 16Slide 17Scale space samplingAccurate Keypoint LocalizationThe Taylor Series ExpansionThresholding Keypoints (part 1)Thresholding Keypoints (part 2)Computing the Principal CurvaturesStages of keypoint selectionAssigning an OrientationAssigning an Orientation (cont.)Slide 27Keypoint DescriptorVisual Representation of Keypoint DescriptorKeypoint Descriptor (cont.)Slide 31We now have featuresMatching Keypoints between imagesMatching Keypoints between images (cont.)Slide 35Efficient Nearest Neighbor indexingSlide 37Clustering -Hough TransformModel Verification-Affine TransformationResults (Object Recognition)Results (cont.)Slide 42Slide 43Distinctive Image Features from Scale-Invariant KeypointsRonnie BajwaSameer Pawar ** Adapted from slides found online by Michael Kowalski, Lehigh UniversityGoalExtract distinctive invariant features from an image that can be used to perform reliable object recognition and many other applications.Key requirements for good featureHighly distinctive, with a low probability of mismatchShould be easy to extractInvariance: - Scale and rotation- change in illumination - slight change in viewing angle- image noise - clutter and occlusionBrief HistoryMoravec(1981): –corner detector.Harris(1988): –Selects locations that has large gradients in all directions (corners)–Invariant to image rotation and to slight affine intensity change, but faces problems for scale change.Zhang(1995): –Introduced correlation window to match images in large range motion.Schmid (1997): –Suggested use of local feature matching for image recognition.–Used rotationally invariant descriptor of the local image region.–Multiple feature matches accomplish recognition under occlusion & clutter.Harris Corner Detector:direction of the slowest changedirection of the fastest change(max)-1/2(min)-1/2“Edge” 2 >> 1“Flat” 2 ~ 1~0 “Corner” 2 ~ 1 ~ LargeSIFT Algorithm OverviewFiltered approach 1. Scale-space extrema detection–Identify potential points: invariant to scale & orientation.–Difference-of-Gaussian function2. Keypoint localization–Improve the estimate for location by fitting a quadratic–Extrema thresholded for filter out insignificant points.3. Orientation Assignment-Orientation assigned to each keypoint and neighboring pixels based on local gradient. 4. Keypoint Descriptor construction–Feature vector based on gradients of local neighborhoodKeypoint Selection: Scale spaceWe express the image at different scales by filtering it with a Gaussian kernelKeypoint Selection: why DoG’s?Lindeberg(1994) and Mikolajczyk (2002) found that the maxima and minima of the scaled Laplacian provides the most stable scale invariant features We can use the scaled images to approximate this:Efficient to compute–Smoothed images L needed later so D can be computed by simple image subtractionBack to picking keypoints1. Supersample original image2. Compute smoothed images using different scales σ for entire octave3. Compute doG images from adjacent scales for entire octave4. Isolate keypoints in each octave by detecting extrema in doG compared to neighboring pixels5. Subsample image 2σ of current octave and repeat process (2-3) for next octaveVisual representation of processVisual representation of process (cont.)A More Visual RepresentationOriginal ImageStarting ImageA More Visual Representation (cont.)First Octave of L imagesA More Visual Representation (cont.)Second OctaveThird OctaveFourth OctaveA More Visual Representation (cont.)First Octave difference-of-GaussiansA More Visual Representation (cont.)Scale space samplingHow many fine scales in every octave?Extremas can be arbitrary close but very close ones are unstable. After subsampling and before finding scaled images of the octave, prior smoothing of 1.6 is doneTo compensate the loss of higher spatial frequencies, original image is doubled in sizeAccurate Keypoint LocalizationFrom difference-of-Gaussian local extrema detection we obtain approximate values for keypointsOriginally these approximations were used directlyFor an improvement in matching and stability fitting to a 3D quadratic function is usedThe Taylor Series ExpansionTake Taylor Series Expansion of scale-space function D(x,y,σ)–Use up to quadratic terms –origin shifted to sample point– offset from this sample point–to find location of extremum, take derivative and set to 0xxDxxxDDxDTT2221)(Tyxx ),,(^xxDxDx 122Thresholding Keypoints (part 1)The function value at the extrema is used to reject unstable extrema–Low contrast–Evaluate–Absolute value less than 0.03 at extrema location results in discarding of extremaxxDDxDT21)(Thresholding Keypoints (part 2)Difference-of-Gaussian function will be strong along edges–Some locations along edges are poorly determined and will become unstable when even small amounts of noise are added–These locations will have a large principal curvature across the edge but a small principal of curvature perpendicular to the edge–Therefore we need to compute the principal curvatures at the location and compare the twoComputing the Principal CurvaturesHessian matrix–The eigenvalues of H are proportional to principal curvatures–We are not concerned about actual values of eigenvalue, just the ratio of the two yyxyxyxxDDDDHyyxxDDTr )(Hr2)()(xyyyxxDDDDet HrrrrDetTr22222)1()()()()( HHStages of keypoint selectionAssigning an OrientationWe finally have a keypoint that we are going to keepThe next step is assigning an orientation for the keypoint–Used in making the matching technique invariant to rotationAssigning an Orientation (cont.)Gaussian smoothed image, L, with closest scale is chosen (scale invariance)Points in region around keypoint are selected and magnitude and orientations of gradient are calculatedOrientation histogram formed