Keypoint-based RecognitionGeneral Process of Object RecognitionGeneral Process of Object RecognitionOverview of Keypoint MatchingGeneral Process of Object RecognitionMatching KeypointsAffine Object ModelAffine Object ModelFinding the objectsMatched objectsView interpolationApplicationsLocation RecognitionFast visual search110,000,000 Images in 5.8 SecondsSlide Number 17Slide Number 18Slide Number 19Key IdeasRecognition with K-treeSlide Number 22Slide Number 23Slide Number 24Slide Number 25Slide Number 26Slide Number 27Slide Number 28Slide Number 29Slide Number 30Slide Number 31Slide Number 32Slide Number 33Slide Number 34Slide Number 35Slide Number 36Slide Number 37Slide Number 38Slide Number 39Slide Number 40Slide Number 41Slide Number 42Slide Number 43Slide Number 44PerformanceMore words is betterSlide Number 47Video Google SystemApplication: Large-Scale RetrievalExample ApplicationsApplication: Image Auto-AnnotationThings to rememberKeypoint‐based RecognitionComputer VisionCS 543 / ECE 549 University of IllinoisDerek Hoiem03/04/10General Process of Object RecognitionSpecify Object ModelGenerate HypothesesScore HypothesesResolutionGeneral Process of Object RecognitionExample: Keypoint-based Instance RecognitionSpecify Object ModelGenerate HypothesesScore HypothesesResolutionA1A2A3Last ClassOverview of Keypoint MatchingK. Grauman, B. LeibeNpixelsNpixelsAfe.g. colorBfe.g. colorA1A2A3TffdBA<),(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 descriptorsGeneral Process of Object RecognitionExample: Keypoint-based Instance RecognitionSpecify Object ModelGenerate HypothesesScore HypothesesResolutionA1A2A3Affine ParametersChoose hypothesis with max score above threshold# InliersAffine-variant point locationsThis ClassMatching Keypoints• Want to match keypoints between:1. Training images containing the object2. Database images• Given descriptor x0, find two nearest neighbors x1, x2with distances d1, d2 • x1matches x0if d1/d2< 0.8– This gets rid of 90% false matches, 5% of true matches in Lowe’s studyAffine Object Model• Accounts for 3D rotation of a surface under orthographic projectionAffine Object Model• Accounts for 3D rotation of a surface under orthographic projectionScaling/skewTranslationHow many matched points do we need?Finding the objects1. Get matched points in database image2. Get location/scale/orientation using Hough voting– In training, each point has known position/scale/orientation wrt whole object– Bins for x, y, scale, orientation• Loose bins (0.25 object length in position, 2x scale, 30 degrees orientation)• Vote for neighboring bins also (so 16 votes per point)3. Geometric verification– For each bin with at least 3 keypoints– Iterate between least squares fit and checking for inliers and outliers4. Report object if > T inliers (T is typically 3, can be computed by probabilistic method)Matched objectsView interpolation• Training– Given images of different viewpoints– Cluster similar viewpoints using feature matches– Link features in adjacent views• Recognition– Featur e matches may bespread over several training viewpoints⇒ Use the known links to “transfer votes” to other viewpointsSlide credit: David Lowe[Lowe01]Applications• Sony Aibo(Evolution Robotics)• SIFT usage– Recognize docking station– Communicate with visual cards• Other uses– Place recognition– Loop closure in SLAMK. Grauman, B. Leibe 13Slide credit: David LoweLocation RecognitionSlide credit: David LoweTraining[Lowe04]Fast visual search“Scalable Recognition with a Vocabulary Tree”, Nister and Stewenius, CVPR 2006.“Video Google”, Sivic and Zisserman, ICCV 2003Slide110,000,000Images in5.8 SecondsSlide Credit: NisterSlideSlide Credit: NisterSlideSlide Credit: NisterSlide Credit: NisterSlideKey Ideas• Visual Words– Cluster descriptors (e.g., K‐means)• Inverse document file– Quick lookup of files given keypointstf-idf: Term Frequency – Inverse Document Frequency# words in document# times word appears in document# documents# documents that contain the wordRecognition with K‐treeFollowing slides by David Nister (CVPR 2006)PerformanceMore words is betterImprovesRetrievalImprovesSpeedBranch factorHigher branch factor works better (but slower)Video Google System1. Collect all words within query region2. Inverted file index to find relevant frames3. Compare word counts4. Spatial verificationSivic & Zisserman, ICCV 2003• Demo online at : http://www.robots.ox.ac.uk/~vgg/research/vgoogle/index.html48 K. Grauman, B. LeibeQuery regionRetrieved framesApplication: Large‐Scale RetrievalK. Grauman, B. Leibe 50[Philbin CVPR’07]QueryResults on 5K (demo available for 100K)Example ApplicationsB. Leibe 51Mobile tourist guide• Self-localization• Object/building recognition• Photo/video augmentation[Quack, Leibe, Van Gool, CIVR’08]Application: Image Auto‐AnnotationK. Grauman, B. Leibe 52Left: Wikipedia imageRight: closest match from Flickr[Quack CIVR’08]Moulin RougeTour MontparnasseColosseumViktualienmarktMaypoleOld Town Square (Prague)Things to remember• Object instance recognition– Find keypoints, compute descriptors– Match descriptors– Vote for / fit affine parameters– Return object if # inliers > T• Keys to efficiency– Visual wor ds• Used for many applications– Inverse document file• Used for web‐scale