Part 1: Bag-of-words models: Part 1: Bag-of-words models by Li Fei-Fei (Princeton)


Related works: Related works Early “bag of words” models: mostly texture recognition Cula & Dana, 2001; Leung & Malik 2001; Mori, Belongie & Malik, 2001; Schmid 2001; Varma & Zisserman, 2002, 2003; Lazebnik, Schmid & Ponce, 2003; Hierarchical Bayesian models for documents (pLSA, LDA, etc.) Hoffman 1999; Blei, Ng & Jordan, 2004; Teh, Jordan, Beal & Blei, 2004 Object categorization Csurka, Bray, Dance & Fan, 2004; Sivic, Russell, Efros, Freeman & Zisserman, 2005; Sudderth, Torralba, Freeman & Willsky, 2005; Natural scene categorization Vogel & Schiele, 2004; Fei-Fei & Perona, 2005; Bosch, Zisserman & Munoz, 2006


Analogy to documents: Analogy to documents Of all the sensory impressions proceeding to the brain, the visual experiences are the dominant ones. Our perception of the world around us is based essentially on the messages that reach the brain from our eyes. For a long time it was thought that the retinal image was transmitted point by point to visual centers in the brain; the cerebral cortex was a movie screen, so to speak, upon which the image in the eye was projected. Through the discoveries of Hubel and Wiesel we now know that behind the origin of the visual perception in the brain there is a considerably more complicated course of events. By following the visual impulses along their path to the various cell layers of the optical cortex, Hubel and Wiesel have been able to demonstrate that the message about the image falling on the retina undergoes a step-wise analysis in a system of nerve cells stored in columns. In this system each cell has its specific function and is responsible for a specific detail in the pattern of the retinal image.


A clarification: definition of “BoW”: Looser definition Independent features A clarification: definition of “BoW”


A clarification: definition of “BoW”: A clarification: definition of “BoW” Looser definition Independent features Stricter definition Independent features histogram representation


Slide8: Representation 1. 2. 3.


1.Feature detection and representation: 1.Feature detection and representation


1.Feature detection and representation: 1.Feature detection and representation Regular grid Vogel & Schiele, 2003 Fei-Fei & Perona, 2005


1.Feature detection and representation: 1.Feature detection and representation Regular grid Vogel & Schiele, 2003 Fei-Fei & Perona, 2005 Interest point detector Csurka, et al. 2004 Fei-Fei & Perona, 2005 Sivic, et al. 2005


1.Feature detection and representation: 1.Feature detection and representation Regular grid Vogel & Schiele, 2003 Fei-Fei & Perona, 2005 Interest point detector Csurka, Bray, Dance & Fan, 2004 Fei-Fei & Perona, 2005 Sivic, Russell, Efros, Freeman & Zisserman, 2005 Other methods Random sampling (Vidal-Naquet & Ullman, 2002) Segmentation based patches (Barnard, Duygulu, Forsyth, de Freitas, Blei, Jordan, 2003)


1.Feature detection and representation: 1.Feature detection and representation Normalize patch Detect patches [Mikojaczyk and Schmid ’02] [Mata, Chum, Urban & Pajdla, ’02] [Sivic & Zisserman, ’03] Compute SIFT descriptor [Lowe’99] Slide credit: Josef Sivic


Slide14: 1.Feature detection and representation


2. Codewords dictionary formation: 2. Codewords dictionary formation


2. Codewords dictionary formation: 2. Codewords dictionary formation Vector quantization Slide credit: Josef Sivic


Slide17: 2. Codewords dictionary formation Fei-Fei et al. 2005


Slide18: Image patch examples of codewords Sivic et al. 2005


Slide19: 3. Image representation frequency codewords


Slide20: Representation 1. 2. 3.


Slide21: category models (and/or) classifiers Learning and Recognition


Slide22: category models (and/or) classifiers Learning and Recognition Generative method: - graphical models Discriminative method: - SVM


Slide23: 2 generative models Naïve Bayes classifier Csurka Bray, Dance & Fan, 2004 Hierarchical Bayesian text models (pLSA and LDA) Background: Hoffman 2001, Blei, Ng & Jordan, 2004 Object categorization: Sivic et al. 2005, Sudderth et al. 2005 Natural scene categorization: Fei-Fei et al. 2005


Slide24: wn: each patch in an image wn = [0,0,…1,…,0,0]T w: a collection of all N patches in an image w = [w1,w2,…,wN] dj: the jth image in an image collection c: category of the image z: theme or topic of the patch First, some notations


Slide25: w N c Case #1: the Naïve Bayes model Csurka et al. 2004


Slide26: Csurka et al. 2004


Slide27: Csurka et al. 2004


Slide28: Hoffman, 2001 Case #2: Hierarchical Bayesian text models Blei et al., 2001 Probabilistic Latent Semantic Analysis (pLSA) Latent Dirichlet Allocation (LDA)


Slide29: Case #2: Hierarchical Bayesian text models Probabilistic Latent Semantic Analysis (pLSA) Sivic et al. ICCV 2005


Slide30: Case #2: Hierarchical Bayesian text models Latent Dirichlet Allocation (LDA) Fei-Fei et al. ICCV 2005


Slide31: Case #2: the pLSA model


Slide32: Case #2: the pLSA model Slide credit: Josef Sivic


Slide33: Case #2: Recognition using pLSA Slide credit: Josef Sivic


Slide34: Maximize likelihood of data using EM Observed counts of word i in document j M … number of codewords N … number of images Case #2: Learning the pLSA parameters Slide credit: Josef Sivic


Slide35: Demo Course website


Slide36: task: face detection – no labeling


Slide37: Output of crude feature detector Find edges Draw points randomly from edge set Draw from uniform distribution to get scale Demo: feature detection


Slide38: Demo: learnt parameters Codeword distributions per theme (topic) Theme distributions per image Learning the model: do_plsa(‘config_file_1’) Evaluate and visualize the model: do_plsa_evaluation(‘config_file_1’)


Slide39: Demo: recognition examples


Slide40: Performance of each theme Demo: categorization results


Slide41: category models (and/or) classifiers Learning and Recognition Generative method: - graphical models Discriminative method: - SVM


Discriminative methods based on ‘bag of words’ representation: Zebra Non-zebra Decision boundary Discriminative methods based on ‘bag of words’ representation


Discriminative methods based on ‘bag of words’ representation: Discriminative methods based on ‘bag of words’ representation Grauman & Darrell, 2005, 2006: SVM w/ Pyramid Match kernels Others Csurka, Bray, Dance & Fan, 2004 Serre & Poggio, 2005


Summary: Pyramid match kernel: Summary: Pyramid match kernel optimal partial matching between sets of features Grauman & Darrell, 2005, Slide credit: Kristen Grauman


Pyramid Match (Grauman & Darrell 2005): Pyramid Match (Grauman & Darrell 2005) Histogram intersection Slide credit: Kristen Grauman


Pyramid Match (Grauman & Darrell 2005): Histogram intersection Pyramid Match (Grauman & Darrell 2005) Slide credit: Kristen Grauman


Pyramid match kernel: Pyramid match kernel Weights inversely proportional to bin size Normalize kernel values to avoid favoring large sets Slide credit: Kristen Grauman


Slide48: Example pyramid match Level 0 Slide credit: Kristen Grauman


Slide49: Example pyramid match Level 1 Slide credit: Kristen Grauman


Slide50: Example pyramid match Level 2 Slide credit: Kristen Grauman


Example pyramid match: Example pyramid match pyramid match optimal match Slide credit: Kristen Grauman


Summary: Pyramid match kernel: Summary: Pyramid match kernel optimal partial matching between sets of features number of new matches at level i difficulty of a match at level i Slide credit: Kristen Grauman


Object recognition results: Object recognition results ETH-80 database 8 object classes (Eichhorn and Chapelle 2004) Features: Harris detector PCA-SIFT descriptor, d=10 Slide credit: Kristen Grauman


Object recognition results: Object 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 Slide credit: Kristen Grauman


What about spatial info?: What about spatial info? ?


What about spatial info?: What about spatial info? Feature level Spatial influence through correlogram features: Savarese, Winn and Criminisi, CVPR 2006


What about spatial info?: What about spatial info? Feature level Generative models Sudderth, Torralba, Freeman & Willsky, 2005, 2006 Niebles & Fei-Fei, CVPR 2007


What about spatial info?: What about spatial info? Feature level Generative models Sudderth, Torralba, Freeman & Willsky, 2005, 2006 Niebles & Fei-Fei, CVPR 2007


What about spatial info?: What about spatial info? Feature level Generative models Discriminative methods Lazebnik, Schmid & Ponce, 2006


Invariance issues: Invariance issues Scale and rotation Implicit Detectors and descriptors Kadir and Brady. 2003


Invariance issues: Scale and rotation Occlusion Implicit in the models Codeword distribution: small variations (In theory) Theme (z) distribution: different occlusion patterns Invariance issues


Invariance issues: Scale and rotation Occlusion Translation Encode (relative) location information Sudderth, Torralba, Freeman & Willsky, 2005, 2006 Niebles & Fei-Fei, 2007 Invariance issues


Invariance issues: Scale and rotation Occlusion Translation View point (in theory) Codewords: detector and descriptor Theme distributions: different view points Invariance issues Fergus, Fei-Fei, Perona & Zisserman, 2005


Slide65: Model properties Intuitive Analogy to documents


Slide66: Model properties Olshausen and Field, 2004, Fei-Fei and Perona, 2005 Intuitive Analogy to documents Analogy to human vision


Slide67: Model properties Intuitive generative models Convenient for weakly- or un-supervised, incremental training Prior information Flexibility (e.g. HDP) Li, Wang & Fei-Fei, CVPR 2007 Sivic, Russell, Efros, Freeman, Zisserman, 2005


Slide68: Model properties Intuitive generative models Discriminative method Computationally efficient Grauman et al. CVPR 2005


Slide69: Model properties Intuitive generative models Discriminative method Learning and recognition relatively fast Compare to other methods


Slide70: No rigorous geometric information of the object components It’s intuitive to most of us that objects are made of parts – no such information Not extensively tested yet for View point invariance Scale invariance Segmentation and localization unclear Weakness of the model