Shape MatchingBrandon Smith and Shengnan WangComputer Vision – CS766 – Fall 2007Outline• Introduction and Background• Uses of shape matching• Kinds of shape matching• Support Vector Machine (SVM)• Matching with Shape Contexts• Shape Context• Bipartite Graph Matching• Modeling Transformations• Invariance and Robustness• Results• Questions• Shengnan’s part…Introduction and BackgroundShape matching examplesFruit InspectionFingerprint MatchingHieroglyph Lookup Trademark LookupIntroduction and BackgroundIntroduction and Background• Feature-Based Methods• Brightness-Based MethodsIntroduction and BackgroundFeature-Based MethodsIntroduction and BackgroundBrightness-Based MethodsTwo different frameworks:• Explicitly find correspondences• Build classifiers without explicitly finding correspondences.Introduction and BackgroundSupport Vector Machine (SVM)Introduction and BackgroundApproach:1.Find correspondences between shapes2.Estimate an aligning transform3.Measure similarityMatching with Shape ContextsShape ContextMatching with Shape ContextsShape ContextMatching with Shape ContextsShape Context39Matching with Shape ContextsShape ContextBelongie, et al, PAMI 2002, Shape matching and object recognition using shape contextsMatching with Shape ContextsShape ContextBelongie, et al, PAMI 2002, Shape matching and object recognition using shape contexts KkjijijiijkhkhkhkhppCC12)()()()(21),(pipjMatching with Shape ContextsBipartite Graph MatchingiiiqpCH ),()()()(3NOSolved in about Belongie, et al, PAMI 2002, Shape matching and object recognition using shape contextsMatching with Shape ContextsModeling TransformationsBelongie, et al, PAMI 2002, Shape matching and object recognition using shape contextsMatching with Shape ContextsBelongie, et al, PAMI 2002, Shape matching and object recognition using shape contextsThin Plane Spline (TPS) Model(2D Generalization of Cubic Spline)Matching with Shape ContextsThin Plane Spline (TPS) Model(2D Generalization of Cubic Spline)Matching with Shape ContextsBelongie, et al, PAMI 2002, Shape matching and object recognition using shape contextsMatching with Shape ContextsInvariance and Robustness Belongie, et al, PAMI 2002, Shape matching and object recognition using shape contexts• Invariant under translation and scaling• Insensitive to small affine distortion• Can be made invariant to rotationMatching with Shape ContextsEvaluation and ResultsModel Point SetsDeformation Noise OutliersTarget Point SetsMatching with Shape ContextsEvaluation and ResultsDeformation Noise OutliersBelongie et al. Chui and Rangarajan Iterated closed point*Matching with Shape ContextsEvaluation and ResultsConclusionQuestionsShape and Image MatchingShengnan [email protected]/4/07 Shengnan Wang University of Wisconsin-MadisonToday• The Pyramid Match Kernel: Discriminative Classification with Sets of Image Features- Kristen Grauman & Trevor Darrell- MIT• Matching Local Self-Similarities across Images and Videos- Eli Shechtman & Michal Irani- @ CVPR0711/4/07 Shengnan Wang University of Wisconsin-MadisonSet Representationinvariant region descriptorslocal shape featuresexamples under varying conditions11/4/07 Shengnan Wang University of Wisconsin-MadisonMotivation• How to build a discriminative classifier using the set representation?• Kernel-based methods (e.g. SVM) are appealing for efficiency and generalization power…• What determines the appropriates of a kernel? - Each instance is unordered set of vectors- Varying number of vectors per instance11/4/07 Shengnan Wang University of Wisconsin-MadisonPyramid Match Kerneloptimal partial matching11/4/07 Shengnan Wang University of Wisconsin-MadisonExample pyramid matchLevel 011/4/07 Shengnan Wang University of Wisconsin-MadisonExample pyramid matchLevel 111/4/07 Shengnan Wang University of Wisconsin-MadisonExample pyramid matchLevel 211/4/07 Shengnan Wang University of Wisconsin-MadisonPyramid match kernel11/4/07 Shengnan Wang University of Wisconsin-MadisonExample pyramid matchpyramid matchoptimal match11/4/07 Shengnan Wang University of Wisconsin-MadisonSummary: Pyramid match kernel• linear time complexity: mfeatures of dimension d, L-level pyramid• model-free• insensitive to clutter• positive-definite function• no independence assumption• fast, effective object recognition11/4/07 Shengnan Wang University of Wisconsin-MadisonObject recognition results• ETH-80 database :8 object classes• Features: – Harris detector– PCA-SIFT descriptor, d=10Kernel Complexity Recognition rateMatch [Wallraven et al.]84%Bhattacharyya affinity [Kondor & Jebara]85%Pyramid match84%11/4/07 Shengnan Wang University of Wisconsin-MadisonObject recognition results• Caltech objects database 101 object classes• Features:– SIFT detector– PCA-SIFT descriptor, d=10• 30 training images / class• 43% recognition rate(1% chance performance)• 0.002 seconds per match 11/4/07 Shengnan Wang University of Wisconsin-MadisonLocalization• Inspect intersections to obtain correspondences between features• Higher confidence correspondences at finer resolution levelsobservationtarget11/4/07 Shengnan Wang University of Wisconsin-MadisonFuture work• Geometric constraints• Fast search of large databases with the pyramid match for image retrieval• Use as a filter for a slower, explicit correspondence method• Alternative feature types and classification domains11/4/07 Shengnan Wang University of Wisconsin-MadisonNext• Matching Local Self-Similarities across Images and Videos- Eli Shechtman & Michal Irani- @ CVPR0711/4/07 Shengnan Wang University of Wisconsin-MadisonWhat do they do?How to measure similarity between visual entities (images or videos)What’s new?.VS.• Traditional idea: they share some common visual properties (colors, intensity, gradients, edges or other filter response)• New idea: they share the same local geometry layout. Local self repeat11/4/07 Shengnan Wang University of Wisconsin-MadisonSelf-similarity descriptor Patch Local Similarity MapSelf-similarity descriptorSSD LPC+Max11/4/07 Shengnan Wang University of Wisconsin-MadisonCorresponding Self-similaritydescriptorGF11/4/07 Shengnan Wang University of Wisconsin-MadisonSelf-similarity descriptor• Benefits– self-similarity descriptor: local descriptors, wider applicability– log-polar: accounts for local affine deformations– maximal correlation value: insensitive to