CS294‐43: Visual Object and Activity RecognitionActivity RecognitionProf. Trevor DarrellSpring 2009Spring 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 f Obj t C t D t ti ICCV'05 B iji Chi 2005[M F it ]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 IEEEclassification 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:•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 q• 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 RecognitionComputer 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 jg g ppvector 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.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 featurespgPrevious strategies: • Match features individually, vote on small sets to verify [SchmidLoweTuytelaarset al ][Schmid, Lowe, Tuytelaarset al.]• Explicit search for one-to-one correspondencesp[Rubner et al., Belongie et al., Gold & Rangarajan, Wallraven & Caputo, Berg et al., Zhang et al.,…]• Compare frequencies of prototype features[Csurkaet al.,Sivic&Zisserman,[Csurkaet al., Sivic& Zisserman, Lazebnik & Ponce]Partially matching sets of featuresygOptimal match: O(m3)Optimal match: O(m)Greedy match: O(m2log m)Pyramid match: O(m)(m=num pts)We introduce an approximate matching kernel that makes it practical to compare large sets of features bdthi til dbased on their partial correspondences.&C &[Previous work: Indyk & Thaper, Bartal, Charikar, Agarwal & Varadarajan, …]Pyramid match: main ideaFeature space partitions serve to “match” the local descriptors within successively wider regions.descriptor spacespacePyramid match: main ideaHistogram intersection counts number of possiblecounts number of possible matches at a given partitioning.Pyramid match kernelmeasures difficulty of a th tl lnumber of newly matched pairs at level• For similarity, weights inversely proportional to bin sizematch at level y, g y p p(or may be learned)• Normalize these kernel values to avoid favoring large sets[Grauman & Darrell, ICCV 2005]Pyramid match kernelOptimal match: O(m3)Pyramid match: O(mL)optimal partial matchingHighlights of the pyramid match• Linear time complexity• Formal bounds on expected error•Mercer kernel•Mercer kernel• Data-driven partitions allow accurate th i hihdi f tmatches even in high-dim. feature spaces• Strong performance on benchmark object recognition datasetsRecognition results: Caltech101 datasetCaltech-101 dataset•101 categories•101 categories 40-800 images per class Data provided by Fei-Fei, Fergus, and PeronaRecognition results: Caltech101 datasetCaltech-101 datasetJain, Huynh, & Grauman (2007),y, ( )Recognition results: Caltech101 datasetCombination of pyramid match and correspondence kernels Caltech-101 dataseturacyAccuNumber of training examples[Kapoor et al. IJCV 2009]Pyramid match kernel: examples ofti d liti bthextensions and applications by other groupsL=0L=1 L=2Spatial Pyramid Match KernelLazebnik, Schmid, Ponce, 2006.Dual-space Pyramid Matching Hu et al., 2007. Representing Shape with a Pyramid Kernel Bosch & Zisserman, 2007.Scene recognitionShape representationMedical image classificationPyramid match kernel: examples of ti d liti bthextensions and applications by other groupswavesit downwavesit 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.Action recognition Video indexingRobot localizationVocabulary-guided pyramid matchocabu a ygu ded py a d atcUniform bins•Tune pyramid partitionsVocabulary-id dbiTune pyramid partitions to the feature distributionguidedbins• Accurate for d > 100• Requires initial corpus of features to determine pyramid structure• Small cost increase over uniform bins: kLdistances against bin gcenters to insert points[Grauman & Darrell, NIPS 2006]Approximation qualityETH80 images sets of SIFT featuresd=8d=128ETH-80 images, sets of SIFT featuresVocabulary-guided pyramidguided pyramid matchd=8d=128Uniform bin pyramid matchpyApproximation qualityETH-80 images, sets of SIFT featuresBin structure and match countsBin structure and match countsd=3d=8d=13d=23d
View Full Document
Unlocking...