03 02 10 Locating and Describing Interest Points Computer Vision CS 543 ECE 549 University of Illinois Derek Hoiem Acknowledgment Many keypoint slides from Grauman Leibe 2008 AAAI Tutorial What 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 objects 1 Identify a Specific Instance Faces Typical scenario few examples per face identify or verify test example What s hard changes in expression lighting age occlusion viewpoint Basic approaches all nearest neighbor 1 2 3 Project into a new subspace or kernel space e g Eigenfaces PCA Measure face features 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 crucial 2 Detect Instance of a Category Template or sliding window Works well when Object fits well into rectangular window Interior features are discriminative Schneiderman Kanade 2000 2 Detect Instance of a Category Parts based Fischler and Elschlager 1973 Felzenszwalb et al 2008 3 Assign a label to a pixel or region Stuf Materials object regions textures etc Approaches Label patches CRF Segmentation Label Regions General Process of Object Recognition Specify Object Model Generate Hypotheses Score Hypotheses Resolution General Process of Object Recognition Example Template Matching Specify Object Model Intensity Template at x y Scanning window Generate Hypotheses Score Hypotheses Resolution Normalized X Corr Threshold Nonmax suppression General Process of Object Recognition Example Keypoint based Instance Recognition Specify Object Model B3 A1 A2 Generate Hypotheses A3 Affine variant point locations B1 Affine Parameters Score Hypotheses Inliers Resolution Choose hypothesis with max score above threshold B2 General Process of Object Recognition Example Keypoint based Instance Recognition Specify Object Model B3 A1 A2 Generate Hypotheses A3 B1 B2 Today s Class Score Hypotheses Resolution Overview of Keypoint Matching 1 Find a set of distinctive keypoints B3 A1 A2 2 Define a region around each keypoint A3 B2 B1 fA fB d f A fB T 3 Extract and normalize the region content 4 Compute a local descriptor from the normalized region 5 Match local descriptors K Grauman B Leibe Main challenges Change in position and scale Change in viewpoint Occlusion Articulation Goals for Keypoints Detect points that are repeatable and distinctive Key trade ofs B3 A1 A2 A3 B1 B2 Localization More Points More Repeatable Robust to occlusion Works with less texture Robust detection Precise localization Description More Robust More Selective Deal with expected variations Maximize correct matches Minimize wrong matches Keypoint Localization Goals Repeatable detection Precise localization Interesting content K Grauman B Leibe Choosing interest points If you wanted to meet a friend would you say a b c Let s meet on campus Let s meet on Green street Let s meet at Green and Wright Corner detection Or if you were in a secluded area a b c Let s meet in the Plains of Akbar Let s meet on the side of Mt Doom Let s meet on top of Mt Doom Blob valley peak detection Choosing interest points Corners Let s meet at Green and Wright Peaks Valleys Let s meet on top of Mt Doom Many Existing Detectors Available Hessian 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 K Grauman B Leibe Hessian Detector Beaudet78 Hessian determinant Ixx I xx Hessian I I xy I xy I yy Iyy Ixy Intuition Search for strong derivatives in two orthogonal directions K Grauman B Leibe Hessian Detector Beaudet78 Hessian determinant Ixx I xx Hessian I I xy I xy I yy Iyy Ixy det Hessian I I xx I yy I xy2 In Matlab I xx I yy I xy 2 K Grauman B Leibe 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 I x2 D I x I y D I D g I 2 I I I x y D y D Intuition Search for local neighborhoods where the image content has two main directions eigenvectors K Grauman B Leibe Harris Detector Harris88 Second moment matrix autocorrelation matrix I x2 D I x I y D I D g I 2 I x I y D I y D det M l 1l 2 trace M l 1 l 2 Iy Ix 2 Iy 2 Ix Iy g Ix2 g Iy2 g IxIy 2 Square of derivatives 3 Gaussian filter g I Ix 1 Image derivatives 4 Cornerness function both eigenvalues are strong har det I D trace I D g IxIy g I x2 g I y2 g I x I y 2 g I x2 g I y2 2 5 Non maxima suppression 32 har Harris Detector Responses Harris88 Effect A very precise corner detector Harris Detector Responses Harris88 So far can localize in x y but not scale Automatic Scale Selection f I i1 im x f I i1 im x How to find corresponding patch sizes K Grauman B Leibe Automatic Scale Selection Function responses for increasing scale scale signature f I i1 im x f I i1 im x K Grauman B Leibe Automatic Scale Selection Function responses for increasing scale scale signature f I i1 im x f I i1 im x K Grauman B Leibe Automatic Scale Selection Function responses for increasing scale scale signature f I i1 im x f I i1 im x K Grauman B Leibe Automatic Scale Selection Function responses for increasing scale scale signature f I i1 im x f I i1 im x K Grauman B Leibe Automatic Scale Selection Function responses for increasing scale scale signature f I i1 im x f I i1 im x K Grauman B Leibe Automatic Scale Selection Function responses for increasing scale scale signature f I i1 im x f I i1 im x K Grauman B Leibe What Is A Useful Signature Function Laplacian of Gaussian blob detector K Grauman B Leibe Laplacian of Gaussian LoG Local maxima in scale space of Laplacian ofGaussian Lxx Lyy K Grauman B Leibe List of x y s Results Laplacian of Gaussian K Grauman B Leibe Diference of Gaussian DoG Diference of Gaussians as approximation of the Laplacian of Gaussian K Grauman B Leibe DoG Efficient Computation Computation in Gaussian scale pyramid Sampling with step 2 Original image 2 1 4 K Grauman B Leibe Results Lowe s DoG K Grauman B Leibe Orientation Normalization Compute orientation histogram Lowe SIFT 1999 Select dominant orientation Normalize rotate to fixed orientation 0 T Tuytelaars