malik recog wkshp

Dense correspondences make object recognition easyJitendra Malik U.C. Berkeley: 

Dense correspondences make object recognition easy Jitendra Malik U.C. Berkeley

Biological Shape: 

Biological Shape D’Arcy Thompson: On Growth and Form, 1917 studied transformations between shapes of organisms

Deformable Templates: 

Deformable Templates Fischler & Elschlager (1973) Grenander (1991) von der Malsburg (1993)

Matching Framework: 

Matching Framework Find correspondences between points on shape Estimate transformation & measure similarity Nearest neighbor classifier model target ...

Shape Context (Belongie, Malik & Puzicha, 2001): 

Shape Context (Belongie, Malik & Puzicha, 2001)

MatchingExample: 

Matching Example model target

Handwritten Digit Recognition: 

Handwritten Digit Recognition MNIST 60 000: linear: 12.0% 40 PCA+ quad: 3.3% 1000 RBF +linear: 3.6% K-NN: 5% K-NN (deskewed): 2.4% K-NN (tangent dist.): 1.1% SVM: 1.1% LeNet 5: 0.95% MNIST 600 000 (distortions): LeNet 5: 0.8% SVM: 0.8% Boosted LeNet 4: 0.7% MNIST 20 000: K-NN, Shape Context matching: 0.63%

EZ-Gimpy Results: 

EZ-Gimpy Results 158 of 191 images correctly identified: 92 % horse smile canvas spade join here

Slide9: 

101 Object Classes Fei-Fei, Fergus, Perona 2004 accordion airplanes anchor ant barrel bass beaver binocular bonsai brain brontosaurus buddha butterfly camera cannon car_side ceiling_fan cellphone chair chandelier cougar_body cougar_face crab crayfish crocodile crocodile_head cup dalmatian dollar_bill dolphin dragonfly electric_guitar elephant emu euphonium ewer Faces Faces_easy ferry flamingo flamingo_head garfield gerenuk gramophone grand_piano hawksbill headphone hedgehog helicopter ibis inline_skate joshua_tree kangaroo ketch lamp laptop Leopards llama lobster lotus mandolin mayfly menorah metronome minaret Motorbikes nautilus octopus okapi pagoda panda pigeon pizza platypus pyramid revolver rhino rooster saxophone schooner scissors scorpion sea_horse snoopy soccer_ball stapler Starfish Stegosaurus stop_sign strawberry sunflower tick trilobite umbrella watch water_lily wheelchair wild_cat windsor_chair wrench yin_yang

Previous Results on 101 Category Dataset: 

Previous Results on 101 Category Dataset Fei-Fei, Fergus, Perona 2004, Generative Model Based Vision Workshop Constellation model, prior from many examples 2 AFC, 85% (15 examples of each class) 101 +bg AFC, 16 % Some classes were used in earlier work Faces, Cars, Motorbikes, Spotted Cats, Airplanes Fergus, Perona, Zisserman CVPR'03 Fei-Fei, Fergus, Perona ICCV‘03

101+bg AFC confusion after warping: 

Samples from 101 classes against 101+background 101+bg AFC confusion after warping Mean diagonal 46% 0% 100%

Correspondence using Geometric Blur : 

Correspondence using Geometric Blur Berg & Malik, CVPR 01 Berg & Malik, 04

Slide18: 

Exemplar Probe

Warped Model: 

Warped Model

Finding Optimal Correspondence: 

Finding Optimal Correspondence Model Target

Representing Putative Correspondences: 

Representing Putative Correspondences Each row or column has exactly one 1. cf. Marr & Poggio ‘76 Points on the model Points on the target

Correspondence as Integer Quadratic Programming: 

Correspondence as Integer Quadratic Programming Model Target subject to (linear) constraints that ensure x represents a valid correspondence cf. Maciel & Costeira ‘03

Geometric Blur Example: 

Sparse Signal Geometric Blur Example

Geometric Blur Example: 

Feature Center Geometric Blur Example Sparse Signal

Geometric Blur Example: 

Geometric Blur Example Sparse Signal Geometric Blur of Signal

Geometric Blur Definition: 

Geometric Blur Definition Blur of a signal I over range of spatial distortions: In practice we consider blur over bounded affine distortions so that: Most useful for sparse signals.

Geometric Blur Example: 

Geometric Blur Example Sparse Signal Sub-Sample Geometric Blur of Signal

Varying Blur Parameters: 

Varying Blur Parameters

Individual Feature Matches: 

Individual Feature Matches

Finding Optimal Correspondence: 

Finding Optimal Correspondence Model Target

How to get good correspondences: 

How to get good correspondences Use rich descriptors that are insensitive to typical transformations Geometric Blur Enforce relational constraints among corresponding features. Integer Quadratic Programming Estimate smooth transformation E.g. Regularized thin plate spline

Warp and Correlate Blurred Oriented Channels: 

Warp and Correlate Blurred Oriented Channels

101+bg AFC confusion after warping: 

Samples from 101 classes against 101+background 101+bg AFC confusion after warping Mean diagonal 46% 0% 100%

Indexing: 

Indexing 15 Example images from each class Support for objects known The distance between a query image and an exemplar is the average minimum distance of the query features to their best match in the exemplar.

Pruning by representative Geom Blur descriptors: 

Pruning by representative Geom Blur descriptors Find best match for the Geom blur descriptor at a few random points and add up cost

Correspondence Warping and Recognition: 

Correspondence Warping and Recognition Consider the top 10 matching exemplars for each query Attempt to find a correspondence between the exemplar and the query image Warp the exemplar using a TPS fit to the correspondence Compare the blurred oriented edge responses using normalized correlation

Best and Worst: 

Best and Worst car side 96.00% metronome 93.75% stop sign 92.00% Motorbikes 92.00% scissors 88.89% yin yang 88.00% strawberry 87.50% revolver 84.00% pagoda 84.00% dollar bill 84.00% … hawksbill 16.00% cannon 16.00% anchor 16.00% lotus 12.00% lobster 12.00% Leopards 12.00% llama 8.00% elephant 8.00% wild cat 0.00% panda 0.00%

All in order Best to Worst: 

All in order Best to Worst car side metronome stop sign Motorbikes scissors yin yang strawberry revolver pagoda dollar bill inline skate watch minaret grand piano garfield tick windsor chair soccer ball menorah umbrella rooster ferry Faces easy mandolin wrench schooner pyramid pizza pigeon mayfly accordion saxophone laptop hedgehog chandelier sea horse airplanes platypus trilobite joshua tree headphone euphonium octopus starfish ketch crocodile head cellphone butterfly gerenuk lamp crab courgar body ceiling fan Faces wheelchair stegosaurus ibis ewer dragonfly buddha brain binocular snoopy water lilly stapler nautilus gramophone flamingo head electric guitar cup courgar face chair barrel ant rhino flamingo dolphin brontosaurus sunflower scorpion kangaroo helicopter emu crocodile crayfish beaver dalmatian camera bonsai bass okapi hawksbill cannon anchor lotus lobster Leopards llama elephant wild cat panda

Other Results: 

Other Results Caltech 101 Class Dataset Fei-Fei, Fergus, Perona 2004 16% correct, given 15 training examples class Berg, Malik 56% whole image / scene retrieval

Automatic Model Building: 

Automatic Model Building Given a number or images containing instances of an object class, find the image feature points that can be well aligned to the other images on average. Sample results…

Automatically Extracted Models: 

Automatically Extracted Models -Find a correspondence and align the image with each of the other (14) training images in turn. -In each alignment, for each feature, record the distance to the best - matching point within a small window -The median distance for each feature point is displayed (above middle) and threshholded at a constant percentage of the minimum (above right)

Automatically Extracted Models: 

Automatically Extracted Models

Automatically Extracted Models: 

Automatically Extracted Models

Automatically Extracted Models: 

Automatically Extracted Models

Automatically Extracted Models: 

Automatically Extracted Models

Comp. complexity of scanning approaches to object recognition: 

Comp. complexity of scanning approaches to object recognition Train a classifier to detect a single object class (e.g. faces, cars) at a given scale Scan picture, looking for that object at different scales Let m be # of models, d complexity of classifier, n # locations in query scene, s # scales  complexity is O(mdns)  Will not scale to thousands of objects.

Shapemes (Mori&Malik’01): 

Shapemes (Mori&Malik’01) A feature that describes a bit of shape as a fixed-length vector (“shapeme”) Calculate for known and query objects, match using nearest neighbor. Can be compared across object categories. Matching still O(mdns)

Representative Shapemes: 

Representative Shapemes Use a small subset of points from query, e.g. randomly chosen points Perform search only for descriptors at those points Good performance because descriptors are rich Still comparing each query shapeme to all objects No longer scanning query scene  O(mds) + O(n)

Locality-sensitive hashing: 

Locality-sensitive hashing Search across object classes by hashing all shapemes together. c is number of collisions Reduces complexity to O(dsc) + O(n).

Towards general object recognition: 

Towards general object recognition Generalization and fine discrimination Interplay of bottom-up and top-down processing