CS294‐43: Visual Object and Activity Recognition Prof. Trevor Darrell Spring 2009 March 17th, 2009Last Lecture – Discriminative approaches (SVM, HCRF)Today – Correspondence and Pyramid-based techniquesComparing sets of local featuresPartially matching sets of featuresPyramid match: main ideaSlide 7Pyramid match kernelSlide 9Highlights of the pyramid matchRecognition results: Caltech-101 datasetSlide 12Pyramid match kernel: examples of extensions and applications by other groupsSlide 15Vocabulary-guided pyramid matchApproximation qualitySlide 18Bin structure and match countsRecognition on the ETH-80Slide 21Slide 22Slide 23Next Lecture – Category Discovery from the WebCS294 43: Visual Object and ‐Activity RecognitionProf. Trevor DarrellSpring 2009March 17th, 2009Last Lecture – Discriminative approaches (SVM, HCRF)•Classic SVM on “bags of features”:C. Dance, J. Willamowski, L. Fan, C. Bray, and G. Csurka, "Visual categorization with bags of keypoints," in ECCV International Workshop on Statistical Learning in Computer Vision, 2004. •ISM + SVM + Local Kernels:M. Fritz; B. Leibe; B. Caputo; B. Schiele: Integrating Representative and Discriminant Models for Object Category Detection, ICCV'05, Beijing, China, 2005 [M. Fritz]•Local SVM:H. Zhang, A. C. Berg, M. Maire, and J. Malik, "Svm-knn: Discriminative nearest neighbor classification for visual category recognition," in CVPR '06: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington, DC, USA: IEEE Computer Society, 2006, pp. 2126-2136. [M. Maire]•“Latent” SVM with deformable parts:P. Felzenszwalb, D. Mcallester, and D. Ramanan, "A discriminatively trained, multiscale, deformable part model," in IEEE International Conference on Computer Vision and Pattern Recognition (CVPR) Anchorage, Alaska, June 2008., June 2008. •Hidden Conditional Random Fields:Y. Wang and G. Mori, “Learning a Discriminative Hidden Part Model for Human Action Recognition”, Advances in Neural Information Processing Systems (NIPS), 2008Today – Correspondence and Pyramid-based techniques •C. Berg, T. L. Berg, and J. Malik, "Shape matching and object recognition using low distortion correspondences," in CVPR '05: Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) [K. Kin]•K. Grauman and T. Darrell, "The pyramid match kernel: discriminative classification with sets of image features," ICCV, vol. 2, 2005, pp. 1458-1465 Vol. 2 •S. Lazebnik, C. Schmid, and J. Ponce, "Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories," CVPR, vol. 2, 2006, pp. 2169-2178 [L. Bourdev]•S. Maji, A. C. Berg, and J. Malik, "Classification using intersection kernel support vector machines is efficient," in Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, 2008, pp. 1-8. [S. Maji]•K. Grauman and T. Darrell, "Approximate correspondences in high dimensions," in In NIPS, vol. 2006. •A. Bosch, A. Zisserman, and X. Munoz, "Representing shape with a spatial pyramid kernel," in CIVR '07: Proceedings of the 6th ACM international conference on Image and video retrieval [D. Bellugi]Comparing sets of local featuresPrevious strategies: •Match features individually, vote on small sets to verify [Schmid, Lowe, Tuytelaars et al.]•Explicit search for one-to-one correspondences[Rubner et al., Belongie et al., Gold & Rangarajan, Wallraven & Caputo, Berg et al., Zhang et al.,…]•Compare frequencies of prototype features[Csurka et al., Sivic & Zisserman, Lazebnik & Ponce]Partially matching sets of featuresWe introduce an approximate matching kernel that makes it practical to compare large sets of features based on their partial correspondences.Optimal match: O(m3)Greedy match: O(m2 log m)Pyramid match: O(m)(m=num pts)[Previous work: Indyk & Thaper, Bartal, Charikar, Agarwal & Varadarajan, …]Pyramid match: main ideadescriptor spaceFeature space partitions serve to “match” the local descriptors within successively wider regions.Pyramid match: main ideaHistogram intersection counts number of possible matches at a given partitioning.Pyramid match kernel• For similarity, weights inversely proportional to bin size(or may be learned)• Normalize these kernel values to avoid favoring large sets[Grauman & Darrell, ICCV 2005]measures difficulty of a match at level number of newly matched pairs at levelPyramid match kerneloptimal partial matchingOptimal match: O(m3)Pyramid match: O(mL)Highlights of the pyramid match•Linear time complexity•Formal bounds on expected error•Mercer kernel•Data-driven partitions allow accurate matches even in high-dim. feature spaces•Strong performance on benchmark object recognition datasetsRecognition results: Caltech-101 datasetData provided by Fei-Fei, Fergus, and Perona•101 categories 40-800 images per classJain, Huynh, & Grauman (2007)Recognition results: Caltech-101 datasetSpatial Pyramid Match KernelLazebnik, Schmid, Ponce, 2006.Dual-space Pyramid Matching Hu et al., 2007. Representing Shape with a Pyramid Kernel Bosch & Zisserman, 2007.L=0L=1 L=2Pyramid match kernel: examples ofextensions and applications by other groupsScene recognitionShape representationMedical image classificationwave sit downSingle View Human Action Recognition using Key Pose Matching, Lv & Nevatia, 2007.Spatio-temporal Pyramid Matching for Sports Videos, Choi et al., 2008.From Omnidirectional Images to Hierarchical Localization, Murillo et al. 2007.Pyramid match kernel: examples of extensions and applications by other groupsAction recognition Video indexingRobot localizationVocabulary-guided pyramid matchUniform bins•Tune pyramid partitions to the feature distribution•Accurate for d > 100•Requires initial corpus of features to determine pyramid structure•Small cost increase over uniform bins: kL distances against bin centers to insert pointsVocabulary-guided bins[Grauman & Darrell, NIPS 2006]Approximation qualityUniform bin pyramid matchVocabulary-guided pyramid matchd=8d=8d=128d=128ETH-80 images, sets of SIFT featuresETH-80 images, sets of SIFT featuresApproximation qualityBin structure and match countsData-dependent bins allow more gradual distance ranges in high dimensionsd=3d=8 d=13d=23d=128Recognition on the ETH-80•ETH-80 data set 8 categories 50 images each•One-vs-all SVM with PMK•Features:–Harris
View Full Document
Unlocking...