CVPR2007 tutorial bag of words

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