C280 Computer VisionC280, Computer VisionProf. Trevor [email protected]@eecs.berkeley.eduLt 6 LlFtLecture 6: Local FeaturesLast Time: Image PyramidsLast Time: Image Pyramids•Review of Fourier TransformReview of Fourier Transform• Sampling and Aliasingid• Image Pyramids• Applications: Blending and noise removalToday: Feature Detection and yMatching• Local features•Pyramids for invariant feature detectionPyramids for invariant feature detection• Invariant descriptorsMthi•MatchingImage matchingImage matchingSby Diva Sianby swashfordHarder caseHarder caseSby Diva Sian by scgbtHarder still?Harder still?NASA Mars Rover imagesAnsw er below(look for tiny colored squares )Answ er below (look for tiny colored squares…)NASA Mars Rover imageswith SIFT feature matchesFigure by Noah SnavelyLocal features and alignment• We need to match (align) images• Global methods sensitive to occlusion, lighting, parallax eff ects. So look for local features that match well.•How would you do it by eye?[Darya Frolova and Denis Simakov]•How would you do it by eye?Local features and alignment•Detect feature points in both images[Darya Frolova and Denis Simakov]Local features and alignment•Detect feature points in both images•Find corresponding pairs[Darya Frolova and Denis Simakov]Local features and alignment•Detect feature points in both images•Find corresponding pairs•Use these pairs to align imagesp g g[Darya Frolova and Denis Simakov]Local features and alignment• Problem 1:–Detect the same point independently in both imagesno chance to match!We need a repeatable detector[Darya Frolova and Denis Simakov]Local features and alignment• Problem 2:–For each point correctly recogniz e the corresponding one?We need a reliable and distinctive descriptor[Darya Frolova and Denis Simakov]Geometric transformationsPhotometric transformationsFigure from T. Tuytelaars ECCV 2006 tutorialAnd other nuisancesAnd other nuisances…•NoiseNoise• BlurCitift•Compression artifacts•…Invariant local featuresSubset of local feature types designed to be invariant to common geometric and photometric transformations.Basic steps:1)Detect distinctive interest points1)Detect distinctive interest points 2) Extract invariant descriptorsFigure: David LoweMain questionsMain questions•Where will the interest points come from?Where will the interest points come from?– What are salient features that we’ll detect in multiple views?multiple views?• How to describe a local region?H t t bli hdi•How to establish correspondences, i.e., compute matches?Finding CornersKey property: in the region around a corner, idih diimage gradient has two or more dominant directionsCtblddi ti tiCorners are repeatable and distinctiveCH i dMSt h"A C bi d C d Ed D t t “C.Harris and M.Stephens. "A Combined Corner and Edge Detector.“Proceedings of the 4th Alvey Vision Conference: pages 147--151.Source: Lana LazebnikCorners as distinctive interest pointsWe should easily recognize the point by looking through a small windowShifti i d idi tihldiShifting a window in anydirection should give a large change in intensity“edge”:no change“corner”:significant“flat” region:no change inno change along the edge directionsignificant change in all directionsno change in all directionsSource: A. EfrosHarris Detector formulationChange of intensity for the shift [u,v]:2,(,) (,) ( , ) (,)xyEuv wxyIx uyvIxyIntensityShifted intensityWindow functionintensityfunctionorWindow function w(x,y) =Gi1i i d 0 idGaussian1 in window, 0 outsideSource: R. SzeliskiHarris Detector formulationThis measure of change can be approximated by:uvuMvuvuE][),(2IIIwhere M is a 22 matrix computed from image derivatives:2,(, )xxyxyxy yIIIMwxyIIIGradient with respect to x, times gradient with respect to ySum over image region – area we are checking for cornerwith respect to yMHarris Detector formulation2IIIwhere M is a 22 matrix computed from image derivatives:2,(, )xxyxyxy yIIIMwxyIIIGradient with respect to x, times gradient with respect to ySum over image region – area we are checking for cornerwith respect to yMWhat does this matrix reveal?First, consider an axis-aligned corner:What does this matrix reveal?First, consider an axis-aligned corner:12200yxxIIIIIIM220yyxIIIThis means dominant gradient directions align withThis means dominant gradient directions align with x or y axisIf eitherλis close to 0 then this isnota corner soIf either λis close to 0, then this is nota corner, so look for locations where both are large.What if we have a corner that is not aligned with theSlide credit: David JacobsWhat if we have a corner that is not aligned with the image axes?General CaseSince M is symmetric, we haveRRM211002We can visualize M as an ellipse with axis lengths determined by the eigenvalues andlengths determined by the eigenvalues and orientation determined by Rdirection of thedirection of the slowest changedirection of the fastest change(max)-1/2(min)-1/2Slide adapted form Darya Frolova, Denis Simakov.Interpreting the eigenvaluesClassification of image points using eigenvalues of M:2“Corner”dl“Edge” 2>> 11and 2are large,1 ~ 2;E increases in all directions1and 2are small;E is almost constant in all directions“Edge” 1>> 2“Flat” region112regionCorner response function221212)()(trace)det( MMRt t (0 04 t 0 06)“Corner”R>0“Edge” R < 0α: constant (0.04 to 0.06)R > 0|R|ll“Edge” R < 0“Flat” region|R| smallregionHarris Corner Detector• Algorithm steps: –Compute M matrix within all image windows to get their R scores–Find points with large corner responseFind points with large corner response (R > threshold)–Take the points of local maxima of RpHarris Detector: WorkflowSlide adapted form Darya Frolova, Denis Simakov, Weizmann Institute.Harris Detector: WorkflowCompute corner responseRCompute corner response RHarris Detector: WorkflowFind points with large corner response:R>thresholdFind points with large corner response: R>thresholdHarris Detector: WorkflowTake only the points of local maxima ofRTake only the points of local maxima of