116.891Computer Vision and ApplicationsProf. Trevor. DarrellLecture 7: Features and Geometry– Affine invariant features– Epipolar geometry– Essential matrixReadings: Mikolajczyk and Schmid; F&P Ch 102Last timeInteresting points, correspondence, affine patch trackingScale and rotation invariant descriptors [Lowe]3Images as VectorsLeft RightLwRwmmLwLwrow 1row 2row 3mmm“Unwrap” image to form vector, using raster scan orderEach window is a vectorin an m2dimensionalvector space.Normalization makesthem unit length.4Image MetricsLw)(dwR2),(),(2SSD)()],(ˆ),(ˆ[)(dwwvduIvuIdCRLyxWvuRLm−=−−=∑∈(Normalized) Sum of Squared DifferencesNormalized Correlationθcos)(),(ˆ),(ˆ)(),(),(NC=⋅=−=∑∈dwwvduIvuIdCRLyxWvuRLm)(maxarg)(minarg2*dwwdwwdRLdRLd⋅=−=5Harris detector( )∆∆∆∆=∑∑∑∑∈∈∈∈yxyxIyxIyxIyxIyxIyxIyxWyxkkyWyxkkykkxWyxkkykkxWyxkkxkkkkkkkk),(2),(),(),(2)),((),(),(),(),()),((Auto-correlation matrix• Auto-correlation matrix– captures the structure of the local neighborhood– measure based on eigenvalues of this matrix• 2 strong eigenvalues => interest point• 1 strong eigenvalue => contour• 0 eigenvalue => uniform region• Interest point detection– threshold on the eigenvalues– local maximum for localization6Key point localization• Detect maxima and minima of difference-of-Gaussian in scale space• Fit a quadratic to surrounding values for sub-pixel and sub-scale interpolation (Brown & Lowe, 2002)• Taylor expansion around point:• Offset of extremum (use finite differences for derivatives):Blur27Select canonical orientation• Create histogram of local gradient directions computed at selected scale• Assign canonical orientation at peak of smoothed histogram• Each key specifies stable 2D coordinates (x, y, scale, orientation)02π8SIFT vector formation• Thresholded image gradients are sampled over 16x16 array of locations in scale space• Create array of orientation histograms• 8 orientations x 4x4 histogram array = 128 dimensions9TodayAffine Invariant Interest points [Schmid]Evaluation of interest points and descriptors [Schmid]Epipolar geometry and the Essential Matrix10Affine invariance of interest pointsCordelia SchmidCVPR’03 Tutorial11Scale invariant Harris points• Multi-scale extraction of Harris interest points• Selection of points at characteristic scale in scale spaceLaplacianChacteristic scale :- maximum in scale space- scale invariant12Scale invariant interest pointsinvariant points + associated regions [Mikolajczyk & Schmid’01]multi-scale Harris pointsselection of pointsat the characteristic scalewith Laplacian313Viewpoint changes• Locally approximated by an affine transformationAdetected scale invariant region projected region14State of the art• Affine invariant regions (Tuytelaars et al.’00)– ellipses fitted to intensity maxima– parallelogram formed by interest points and edges15State of the art• Theory for affine invariant neighborhood (Lindeberg’94)xx A→xx21−→LM xx21−→RM)x()x(2121LLRRMRM =),x(LLLM Σ= µIsotropicneighborhoodsrelated by rotation),x(RRRM Σ= µ16State of the art• Localization & scale influence affine neighhorbood=> affine invariant Harris points (Mikolajczyk & Schmid’02)• Iterative estimation of these parameters1. localization – local maximum of the Harris measure 2. scale – automatic scale selection with the Laplacian3. affine neighborhood – normalization with second moment matrixRepeat estimation until convergence17• Iterative estimation of localization, scale, neighborhoodInitial pointsAffine invariant Harris points 18• Iterative estimation of localization, scale, neighborhoodIteration #1Affine invariant Harris points419• Iterative estimation of localization, scale, neighborhoodIteration #2Affine invariant Harris points20• Iterative estimation of localization, scale, neighborhoodIteration #3, #4, ...Affine invariant Harris points21Affine invariant Harris points• Initialization with multi-scale interest points• Iterative modification of location, scale and neighborhood22Affine invariant Harris pointsHarris-LaplaceHarris-Laplace+ affine regionsaffine Harris23affine Harris detectoraffine LaplacedetectorAffine invariant neighborhhood24Image retrieval…> 5000imageschange in viewing angle525Matches22 correct matches26Image retrieval…> 5000imageschange in viewing angle+ scale change27Matches33 correct matches283D Recognition293D Recognition3D object modeling and recognition using affine-invariant patches and multi-view spatial constraints, F. Rothganger, S. Lazebnik, C. Schmid, J. Ponce,CVPR 200330Evaluation of interest points and descriptorsCordelia SchmidCVPR’03 Tutorial631Introduction• Quantitative evaluation of interest point detectors– points / regions at the same relative location=> repeatability rate• Quantitative evaluation of descriptors– distinctiveness=> detection rate with respect to false positives32Quantitative evaluation of detectors • Repeatability rate : percentage of corresponding points• Two points are corresponding if1. The location error is less than 1.5 pixel2. The intersection error is less than 20%homography33Comparison of different detectors[Comparing and Evaluating Interest Points, Schmid, Mohr & Bauckhage, ICCV 98]repeatability - image rotation34Comparison of different detectors[Comparing and Evaluating Interest Points, Schmid, Mohr & Bauckhage, ICCV 98]repeatability – perspective transformation35Harris detector + scale changes36Harris detector – adaptation to scale737Evaluation of scale invariant detectorsrepeatability – scale changes38Evaluation of affine invariant detectors0406070repeatability – perspective transformation39Quantitative evaluation of descriptors• Evaluation of different local features– SIFT, steerable filters, differential invariants, moment invariants, cross-correlation• Measure : distinctiveness– receiver operating characteristics of detection rate with respect to false positives– detection rate = correct matches / possible matches– false positives = false matches / (database points * query points)[A performance evaluation of local descriptors, Mikolajczyk & Schmid, CVPR’03]40Experimental evaluation41Scale change (factor 2.5)Harris-Laplace DoG42Viewpoint change (60 degrees)Harris-Affine (Harris-Laplace)843Descriptors - conclusion• SIFT + steerable perform best•