Distinctive Image Features from Scale-Invariant Keypoints David G. Lowe – IJCV 2004OverviewSlide 3Motivation …. Why SIFT anyway?Related Work - Corner DetectorsRelated Work - Feature MatchingRelated Work – Stability to ChangesRelated Work – Other FeaturesSIFT – Scale Space Extrema DetectionThe Difference of Gaussian SpaceSlide 11SIFT – Local Extrema DetectionSlide 13Evaluating Edge Responses by Comparing Principle CurvaturesThe Hessian Matrix and Keypoint RejectionSIFT – Orientation AssignmentSIFT – Keypoint DescriptorSlide 18Experiments – Affine ChangeExperiments - Large DatabasesExperiments – Object RecognitionSlide 22Affine SolutionResultsConclusionsFuture WorkDistinctive Image Featuresfrom Scale-Invariant KeypointsDavid G. Lowe – IJCV 2004Brien FlewellingCPSC 643 Presentation 1OverviewIntroductionMotivation for this workRelated WorkCorners and other Local FeaturesInvariant descriptorsSimilar Detection, Different DescriptorOverviewScalar Invariant Feature TransformScale Space Extrema DetectionKeypoint LocalizationOrientation AssignmentKeypoint DescriptorExperiments and TestsAffine Changes, Large Data Bases, Object RecognitionConclusions and Future WorkMotivation …. Why SIFT anyway?Highly Distinctive Features – Good MatchingDetailed Descriptor – High UniquenessInvariance to :Scale – Zoom/ResamplingIn plane RotationPartial Invariance to :Lighting ChangeOut of plane RotationRelated Work - Corner DetectorsMoravec (1981) – Stereo Matching using CornersHarris and Stevens (1988) – Repeatability ImprovementsHarris Corner Detector (1992) – commonly used in Structure from motion Solutions“Large Gradients at a pre-determined scale”Related Work - Feature MatchingZhang and Torr (1995) – Use of correlation, least squares and geometric constraints to match Harris corners over large image ranges and motions.Schmidt and Mohr (1997) – Use of a rotationally invariant feature descriptor for matching images in large databases with Harris corners.Lowe (1999) – Extension of feature descriptors to achieve scale invariance.Related Work – Stability to ChangesCrowley and Parker (1984) – Scale Space Peaks and matching of Tree Structures.Lindberg (1993-94) – Scale Selection for good feature detection performance.(Baumberg, 2000; Tuytelaars and Van Gool, 2000; Mikolajczyk and Schmid, 2002; Schaffalitzky and Zisserman, 2002; Brown and Lowe, 2002). – Affine Covariant FeaturesRelated Work – Other FeaturesNelson and Selinger (1998) – Image ContoursMatas et al., (2002) – Maximally Stable Extremal RegionsCarneiro and Jepson (2002) – Phase Based Local FeaturesSchiele and Crowley (2000) – Multidimensional Histogram DescriptorsSIFT – Scale Space Extrema DetectionScale Space – A 1-parameter function of the image data Gaussian Scale Space - Convolution with a Gaussian Kernel … No False Structure!L(x, y, σ ) = G(x, y, σ) I(x, y)∗G(x, y, σ ) = (1/2πσ2)*exp(-(x2+y2)/(2σ2))Detection of ExtremaD(x, y, σ ) = (G(x, y, kσ) − G(x, y, σ)) I(x, y)∗ = L(x, y, kσ) − L(x, y, σ ).The Difference of Gaussian SpaceFor constant scaling of σ this approximates the Laplacian of Gaussian Approximating the derivative of the Gaussian function with respect to sigma we can obtainSIFT – Scale Space Extrema DetectionConstruct the DOG scale spaceK – factor of separationS – number of S+3 images in the stack for each octaveResample and repeatFor each location compare to its 26 nearest neighbors in scale space retain only minima and maximaSIFT – Local Extrema DetectionSampling of scale space is a balance between density of samples and the arbitrary feature frequenciesTest the reliability of matches over matching tasks vs. sampling frequenciesThe most stable and useful frequencies can be detected with coarse sampling in scale.SIFT – Local Extrema DetectionOnce a Scale Space Extrema is localized:Calculate an interpolated fit for location, scale and ratio of principle curvaturesCompute a local Taylor Series Expansion of the DOG function. Find the Zero crossing of the derivative of this function:Evaluating Edge Responses by Comparing Principle CurvaturesThe DOG space will have a large response to edges.Poorly defined extrema have strong principle curvature along the edge but a weak principle curvature normal to it.We may examine the relationship between principle curvatures by looking at the eigenvalues of the approximated Hessian matrix.The Hessian Matrix and Keypoint RejectionThe Hessian Matrix is approximated using Neighbor DifferencesThe ratio of the square of the trace to the determinant has a special relationship to the eigenvalue ratioSIFT – Orientation AssignmentTo achieve rotational invariance, the local gradient orientations are examined to define a principle direction.A magnitude weighted orientation histogram is calculated using the DOG image of nearest scale.SIFT – Keypoint DescriptorThe keypoint descriptor structures the local image information in the DOG image of nearest scale with respect to the assigned orientation.Inspired by work by Edelman, Intrator, and Poggio (1997), the feature descriptor lists the gradient orientations in a structured vectorSIFT – Keypoint DescriptorThe number of elements in the descriptor vector is calculated by the product of the number of histogram bins and the number of orientation directions typically 4x4x8 = 128Experiments – Affine ChangeThe SIFT descriptor was tested against a database of 40,000 keypoints.The percent repeatability of correct matches vs. affine performs better than 50% for up to 50 degree rotations out of planeExperiments - Large DatabasesExperiments – Object RecognitionThe Process:Match Keypoints Evaluate the Euclidian Distance between Candidate Matches. Retain the minimum if the next best match is not within a threshold standoff distance.Experiments – Object RecognitionWhen searching for the best match a prioritized Best Bin First search is used.For purposes of object recognition a Hough Transform is used to cluster objects in pose spaceLarge Error Bounds, does not account well for affine variations – 4 DOF vs. 6 DOFAffine SolutionWhen a cluster of matches in pose space is identified it is verified geometrically by least
View Full Document