Locating and Describing Interest PointsWhat is “object recognition”?1. Identify a Specific Instance1. Identify a Specific Instance2. Detect Instance of a Category 2. Detect Instance of a Category2. Detect Instance of a Category 3. Assign a label to a pixel or regionGeneral Process of Object RecognitionGeneral Process of Object RecognitionGeneral Process of Object RecognitionGeneral Process of Object RecognitionOverview of Keypoint MatchingMain challengesGoals for KeypointsKey trade-offsKeypoint LocalizationChoosing interest pointsChoosing interest pointsMany Existing Detectors AvailableHessian Detector [Beaudet78]Hessian Detector [Beaudet78]Hessian Detector – Responses [Beaudet78]Hessian Detector – Responses [Beaudet78]Harris Detector [Harris88]Harris Detector [Harris88]Harris Detector – Responses [Harris88]Harris Detector – Responses [Harris88]So far: can localize in x-y, but not scaleAutomatic Scale SelectionAutomatic Scale SelectionAutomatic Scale SelectionAutomatic Scale SelectionAutomatic Scale SelectionAutomatic Scale SelectionAutomatic Scale SelectionWhat Is A Useful Signature Function?Laplacian-of-Gaussian (LoG)Results: Laplacian-of-GaussianDifference-of-Gaussian (DoG)DoG – Efficient ComputationResults: Lowe’s DoGOrientation NormalizationHarris-Laplace [Mikolajczyk ‘01]Harris-Laplace [Mikolajczyk ‘01]Maximally Stable Extremal Regions [Matas ‘02]Example Results: MSERAvailable at a web site near you…Local DescriptorsLocal Descriptors: SIFT DescriptorDetails of Lowe’s SIFT algorithmMatching SIFT DescriptorsSIFT RepeatabilitySIFT RepeatabilitySIFT RepeatabilityLocal Descriptors: SURFSlide Number 66Slide Number 67Choosing a detectorComparison of Keypoint DetectorsChoosing a descriptorThings to rememberNext timeLocating and Describing Interest PointsComputer VisionCS 543 / ECE 549 University of IllinoisDerek Hoiem03/02/10Acknowledgment: Many keypoint slides from Grauman&Leibe 2008 AAAI TutorialWhat is “object recognition”?1. Identify a Specific Instance• General objects– Challenges: rotation, scale, occlusion, localization– Approaches• Geometric configurations of keypoints (Lowe 2004)– Works well for planar, textured objects1. Identify a Specific Instance• Faces– Typical scenario: few examples per face, identif y or verify test example– What’s hard: changes in expression, lighting, age, occlusion, viewpoint– Basic approaches (all nearest neighbor)1. Project into a new subspace (or kernel space) (e.g., “Eigenfaces”=PCA)2. Measure face features3. Make 3d face model, compare shape+appearance (e.g., AAM)2. Detect Instance of a Category • Much harder than specific instance recognition• Challenges– Everything in instance recognition– Intraclass variation– Representation becomes crucial2. Detect Instance of a Category• Template or sliding window• Works well when– Object fits well into rectangular window– Interior features are discriminativeSchneiderman Kanade 20002. Detect Instance of a Category • Parts‐basedFischler and Elschlager 1973Felzenszwalb et al. 20083. Assign a label to a pixel or region• Stuff– Materials, object regions, textures, et c.– Approaches• Label patches + CRF• Segmentation + Label RegionsGeneral Process of Object RecognitionSpecify Object ModelGenerate HypothesesScore HypothesesResolutionGeneral Process of Object RecognitionExample: Template MatchingSpecify Object ModelGenerate HypothesesScore HypothesesResolutionIntensity Template, at x-yScanning windowNormalized X-CorrThreshold + Non-max suppressionGeneral Process of Object RecognitionExample: Keypoint-based Instance RecognitionSpecify Object ModelGenerate HypothesesScore HypothesesResolutionA1A2A3Affine ParametersChoose hypothesis with max score above threshold# InliersAffine-variant point locationsGeneral Process of Object RecognitionExample: Keypoint-based Instance RecognitionSpecify Object ModelGenerate HypothesesScore HypothesesResolutionA1A2A3Today’s ClassOverview of Keypoint MatchingK. Grauman, B. LeibeAfBfA1A2A3TffdBA<),(1. Find a set of distinctive key-points 3. Extract and normalize the region content 2. Define a region around each keypoint 4. Compute a local descriptor from the normalized region5. Match local descriptorsMain challenges• Change in position and scale• Change in viewpoint• Occlusion• ArticulationGoals for KeypointsDetect points that are repeatable and distinctiveKey trade‐offsMore PointsMore RepeatableA1A2A3LocalizationMore RobustMore SelectiveDescriptionRobust to occlusionWorks with less textureRobust detectionPrecise localizationDeal with expected variationsMaximize correct matchesMinimize wrong matchesKeypoint Localization• Goals: – Repeatable detection– Precise localization– Interesting contentK. Grauman, B. LeibeChoosing interest points• If you wanted to meet a friend would you saya) “Let’s meet on campus.”b) “Let’s meet on Green street.”c) “Let’s meet at Green and Wright. ”– Corner detection• Or if you were in a secluded area:a) “Let’s meet in the Plains of Akbar.”b) “Let’s meet on the side of Mt. Doom.”c) “Let’s meet on top of Mt. Doom.”– Blob (valley/peak) detectionChoosing interest points• Corners– “Let’s meet at Green and Wright. ”• Peaks/Valleys – “Let’s meet on top of Mt. Doom.”Many Existing Detectors AvailableK. Grauman, B. LeibeHessian & Harris [Beaudet ‘78], [Harris ‘88]Laplacian, DoG [Lindeberg ‘98], [Lowe 1999]Harris‐/Hessian‐Laplace [Mikolajczyk & Schmid ‘01]Harris‐/Hessian‐Affine [Mikolajczyk & Schmid ‘04]EBR and IBR [Tuytelaars & Van Gool ‘04]MSER [Matas ‘02]Salient Regions [Kadir & Brady ‘01] Others…Hessian Detector [Beaudet78]• Hessian determinantK. Grauman, B. Leibe⎥⎦⎤⎢⎣⎡=yyxyxyxxIIIIIHessian )( IxxIyyIxyIntuition: Search for strongderivatives in two orthogonal directionsHessian Detector [Beaudet78]• Hessian determinantK. Grauman, B. LeibeIxxIyyIxy2))(det(xyyyxxIIIIHessian −=2)^(.xyyyxxIII −∗In Matlab:⎥⎦⎤⎢⎣⎡=yyxyxyxxIIIIIHessian )(Hessian Detector – Responses [Beaudet78]Effect: Responses mainly on corners and strongly textured areas.Hessian Detector – Responses [Beaudet78]Harris Detector [Harris88]• Second moment matrix(autocorrelation matrix)K. Grauman, B. Leibe⎥⎥⎦⎤⎢⎢⎣⎡∗=)()()()()(),(22DyDyxDyxDxIDIIIIIIIgσσσσσσσμIntuition: Search for local neighborhoods where the image content has two main