Shape Matching and Object Recognition using Shape Contexts Jitendra Malik U.C. Berkeley (joint work with S. Belongie, J. Puzicha, G. Mori)OutlineBiological ShapeDeformable Templates: Related WorkMatching FrameworkComparing PointsetsShape ContextSlide 8Shape ContextsComparing Shape ContextsSlide 11Thin Plate Spline ModelMatching ExampleOutlier Test ExampleSynthetic Test ResultsSlide 16Terms in Similarity ScoreObject Recognition ExperimentsShape Similarity: Kimia datasetQuantitative ComparisonHandwritten Digit RecognitionPowerPoint PresentationResults: Digit RecognitionCOIL Object DatabaseError vs. Number of ViewsPrototypes Selected for 2 CategoriesEditing: K-medoidsSlide 28Human body configurationsAutomatically Locating KeypointsResultsTrademark SimilaritySlide 33Mori, Belongie, Malik (CVPR 01)Representative Shape ContextsSnodgrass ResultsSlide 37ConclusionComputer Vision GroupUniversity of California BerkeleyShape Matching and Object Recognition using Shape ContextsJitendra Malik U.C. Berkeley(joint work with S. Belongie, J. Puzicha, G. Mori)Computer Vision GroupUniversity of California BerkeleyOutline•Shape matching and isolated object recognition•Scaling up to general object recognitionComputer Vision GroupUniversity of California BerkeleyBiological Shape•D’Arcy Thompson: On Growth and Form, 1917–studied transformations between shapes of organismsComputer Vision GroupUniversity of California BerkeleyDeformable Templates: Related Work•Fischler & Elschlager (1973)•Grenander et al. (1991)•Yuille (1991)•von der Malsburg (1993)Computer Vision GroupUniversity of California BerkeleyMatching Framework•Find correspondences between points on shape•Estimate transformation•Measure similaritymodel target...Computer Vision GroupUniversity of California BerkeleyComparing PointsetsComputer Vision GroupUniversity of California BerkeleyShape ContextCount the number of points inside each bin, e.g.:Count = 4Count = 10...Compact representation of distribution of points relative to each pointComputer Vision GroupUniversity of California BerkeleyShape ContextComputer Vision GroupUniversity of California BerkeleyShape Contexts•Invariant under translation and scale•Can be made invariant to rotation by using local tangent orientation frame•Tolerant to small affine distortion–Log-polar bins make spatial blur proportional to r Cf. Spin Images (Johnson & Hebert) - range image registrationComputer Vision GroupUniversity of California BerkeleyComparing Shape ContextsCompute matching costs using Chi Squared distance:Recover correspondences by solving linear assignment problem with costs Cij[Jonker & Volgenant 1987]Computer Vision GroupUniversity of California BerkeleyMatching Framework•Find correspondences between points on shape•Estimate transformation•Measure similaritymodel target...Computer Vision GroupUniversity of California Berkeley•2D counterpart to cubic spline:•Minimizes bending energy:•Solve by inverting linear system•Can be regularized when data is inexactThin Plate Spline ModelDuchon (1977), Meinguet (1979), Wahba (1991)Computer Vision GroupUniversity of California BerkeleyMatchingExamplemodel targetComputer Vision GroupUniversity of California BerkeleyOutlier Test ExampleComputer Vision GroupUniversity of California BerkeleySynthetic Test ResultsFish - deformation + noise Fish - deformation + outliersICP Shape Context Chui & RangarajanComputer Vision GroupUniversity of California BerkeleyMatching Framework•Find correspondences between points on shape•Estimate transformation•Measure similaritymodel target...Computer Vision GroupUniversity of California BerkeleyTerms in Similarity Score•Shape Context difference•Local Image appearance difference–orientation–gray-level correlation in Gaussian window–… (many more possible)•Bending energyComputer Vision GroupUniversity of California BerkeleyObject Recognition Experiments•Kimia silhouette dataset•Handwritten digits•COIL 3D objects (Nayar-Murase)•Human body configurations•TrademarksComputer Vision GroupUniversity of California BerkeleyShape Similarity: Kimia datasetComputer Vision GroupUniversity of California BerkeleyQuantitative ComparisonrankNumber correctComputer Vision GroupUniversity of California BerkeleyHandwritten 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%Computer Vision GroupUniversity of California BerkeleyComputer Vision GroupUniversity of California BerkeleyResults: Digit Recognition1-NN classifier using:Shape context + 0.3 * bending + 1.6 * image appearanceComputer Vision GroupUniversity of California BerkeleyCOIL Object DatabaseComputer Vision GroupUniversity of California BerkeleyError vs. Number of ViewsComputer Vision GroupUniversity of California BerkeleyPrototypes Selected for 2 CategoriesDetails in Belongie, Malik & Puzicha (NIPS2000)Computer Vision GroupUniversity of California BerkeleyEditing: K-medoids•Input: similarity matrix•Select: K prototypes •Minimize: mean distance to nearest prototype•Algorithm: –iterative–split cluster with most errors•Result: Adaptive distribution of resources (cfr. aspect graphs)Computer Vision GroupUniversity of California BerkeleyError vs. Number of ViewsComputer Vision GroupUniversity of California BerkeleyHuman body configurationsComputer Vision GroupUniversity of California BerkeleyAutomatically Locating Keypoints •User marks keypoints on exemplars•Find correspondence with test shape•Transfer keypoint position from exemplar to the test shape.Computer Vision GroupUniversity of California BerkeleyResultsComputer Vision GroupUniversity of California BerkeleyTrademark SimilarityComputer Vision GroupUniversity of California BerkeleyOutline•Shape matching and isolated object recognition•Scaling up to general object recognition–Many objects (Mori, Belongie & Malik, CVPR 01)–Gray scale matching (Berg & Malik, CVPR 01)–Objects in scenes (scanning or segmentation)Computer Vision GroupUniversity of California Berkeley Mori, Belongie, Malik (CVPR 01)•Fast Pruning–Given a query shape, quickly return a shortlist of candidate matches–Database of known objects will be large: ~30000•Detailed Matching–Perform