Visual search using local features
Cordelia Schmid
Visual search
…
change in viewing angle
Matches
22 correct matches
Visual search
…
change in viewing angle
+ scale change
Matches
33 correct matches
Application: Search in feature films
Visually defined query “Groundhog Day” [Rammis, 1993]
“Find this
clock”
“Find this
place”
Application: Search of particular locations on the web
Find these landmarks ...in these images and millions more
Why is it difficult?
Want to find the object despite possibly large changes in
scale, viewpoint, lighting and partial occlusion
Scale Viewpoint
Lighting Occlusion
Search algorithm
• Computation of local features for the query image and the
image in the database
vector of I1 I1 I 2 I 2 In
local characteristics
Search algorithm
• Selection of similar descriptors in the database
vector of I1 I1 I 2 I 2 In
local characteristics
Search algorithm
Selection of similar descriptors in the database
a) Similarity measure
– vector comparison using the Mahalanobis or Euclidean distance
dist M (p, q) (p q)T 1 (p q)
b) Search criteria
– within a distance: dist(p,q) < threshold
– k nearest neighbours for each descriptor
Search algorithm
Voting algorithm
I1 I1 I 2 I 2 In
21 1 01
I 1 is the corresponding model image
Search algorithm
Voting algorithm
for each query descriptor p
1) search for the similar descriptors {qi}---each descriptor qi
belongs to an image of the database Ik
2) if one or several descriptors qi belong to Ik, increment the
counter for Ik
Result : argmax counter[Ik] is the most similar image
Comparison of each descriptor to all database ones!
Image search system for large datasets
Image Dataset
(one million images or more)
query
ranked image list
Image search
system
• Issues for very large databases
• to reduce the query time
• to reduce the storage requirements
Solution: fast descriptor search
• Complexity
– O(nd) for n features and d dimensions
– Linear in the number of features / images
Solution: fast descriptor search
• Complexity
– O(nd) for n features and d dimensions
– Linear in the number of features / images
• Speed up individual descriptor vector search
– kd-trees (k dim. tree), approximate nearest neighbor search
– Binary tree in which each node is a k-dimensional point
– Every split is associated with one dimension
kd-tree
kd-tree decomposition
Large scale object/scene recognition
Image dataset:
> 1 million images
query
ranked image list
Image search
system
• Each image described by approximately 2000 descriptors
– 2 109 descriptors to index for one million images!
• Database representation in RAM:
– Size of descriptors : 1 TB, search+memory intractable
Bag-of-features [Sivic&Zisserman’03]
Query Set of SIFT centroids
image descriptors (visual words)
sparse frequency vector
Harris-Hessian-Laplace Bag-of-features
regions + SIFT descriptors processing
+tf-idf weighting
Inverted
• “visual words”: file
querying
– 1 “word” (index) per local
descriptor
– only images ids in inverted file
=> 8 GB fits!
Re-ranked Geometric ranked image
list verification short-list
[Chum & al. 2007]
Indexing local features: inverted file index
•For text documents, an
efficient way to find all
pages on which a word
occurs is to use an
index…
•We want to find all
images in which a
feature occurs.
•To use this idea, we’ll
need to map our
features to “visual
words”.
19
K. Grauman, B. Leibe
Visual words
• Map descriptors to words by quantizing the feature space
– Quantize via k-means clustering to obtain visual words
– Assign descriptor to closest visual word
• Bag-of-features as approximate nearest neighbor search
Bag-of-features matching function
where q(x) is a quantizer, i.e., assignment to visual word and
δa,b is the Kronecker operator (δa,b=1 iff a=b)
Inverted file index for images comprised of visual words
Word List of image
• number numbers
• Score each image by the number of common visual words (tentative
correspondences)
• Dot product between bag-of-features
• Fast for sparse vectors !
Image credit: A. Zisserman K. Grauman, B. Leibe
Inverted file index for images comprised of visual words
Word List of image
number numbers
• Weighting with tf-idf score: weight visual words based on their frequency
Tf: term frequency; idf: inverse document frequency
Image credit: A. Zisserman K. Grauman, B. Leibe
Approximate nearest neighbor search evaluation
•ANN algorithms usually returns a short-list of nearest neighbors
– this short-list is supposed to contain the NN with high probability
– exact search may be performed to re-order this short-list
•Proposed quality evaluation of ANN search: trade-off between
– Accuracy: NN recall = probability that the NN is in this list
against
– Ambiguity removal = proportion of vectors in the short-list
- the lower this proportion, the more information we have about the
vector
- the lower this proportion, the lower the complexity if we perform exact
search on the short-list
•ANN search algorithms usually have some parameters to handle this trade-off
ANN evaluation of bag-of-features
•ANN algorithms
0.7 returns a list of
k=100 potential neighbors
0.6
200
0.5 500
•Accuracy: NN recall
1000
= probability that the
NN recall
0.4 2000
NN is in this list
5000
0.3 10000 •Ambiguity removal:
20000
30000
= proportion of vectors
0.2 50000 in the short-list
0.1
•In BOF, this trade-off
BOW is managed by the
0
1e-07 1e-06 1e-05 0.0001 0.001 0.01 0.1
rate of points retrieved
number of clusters k
Hierarchical clustering
• Hierarchical clustering: allows faster insertion / word
assignment while still allowing large vocabularies
– Vocabulary tree [Nister & Stewenius, CVPR 2006]
25
K. Grauman, B. Leibe
Vocabulary size
• The intrinsic matching scheme performed by BOF is weak
– for a “small” visual dictionary: too many false matches
– for a “large” visual dictionary: many true matches are missed
• No good trade-off between “small” and “large” !
– either the Voronoi cells are too big
– or these cells can’t absorb the descriptor noise
intrinsic approximate nearest neighbor search of BOF is not
sufficient
20K visual word: false matches
200K visual word: good matches missed
Hamming Embedding [Jegou et al. ECCV’08]
Representation of a descriptor x
– Vector-quantized to q(x) as in standard BOF
+ short binary vector b(x) for an additional localization in the Voronoi cell
Two descriptors x and y match iif
where h(a,b) Hamming distance
Hamming Embedding [Jegou et al. ECCV’08]
•Nearest neighbors for Hamming distance those for Euclidean distance
a metric in the embedded space reduces dimensionality curse effects
•Efficiency
– Hamming distance = very few operations
– Fewer random memory accesses: 3 x faster that BOF with same dictionary
size!
Hamming Embedding
•Off-line (given a quantizer)
– draw an orthogonal projection matrix P of size db × d
this defines db random projection directions
– for each Voronoi cell and projection direction, compute the median
value for a learning set
•On-line: compute the binary signature b(x) of a given
descriptor
– project x onto the projection directions as z(x) = (z1,…zdb)
– bi(x) = 1 if zi(x) is above the learned median value, otherwise 0
ANN evaluation of Hamming Embedding
0.7
28 32 k=100 compared to BOW: at least
24
0.6 22 200 10 times less points in the
20 short-list for the same level
0.5 500 of accuracy
18 1000
0.4 2000
NN recall
Hamming Embedding
ht=16 5000
0.3 provides a much better
10000
20000 trade-off between recall and
0.2
30000 ambiguity removal
50000
0.1
HE+BOW
BOW
0
1e-08 1e-07 1e-06 1e-05 0.0001 0.001 0.01 0.1
rate of points retrieved
Hamming Embedding: Example
Compared with 20K dictionary: false matches
Hamming Embedding: Example
Compared with 200K visual word: good matches missed
Bag-of-features [Sivic&Zisserman’03]
Query Set of SIFT centroids
image descriptors (visual words)
sparse frequency vector
Bag-of-features
Harris-Hessian-Laplace
processing
regions + SIFT descriptors
+tf-idf weighting
Inverted
• “visual words”: file
querying
– 1 “word” (index) per local
descriptor
– only images ids in inverted file
=> 8 GB fits!
Re-ranked Geometric ranked image
list verification short-list
[Chum & al. 2007]
Geometric verification
Use the position and shape of the underlying features
to improve retrieval quality
Both images have many matches – which is correct?
Geometric verification
We can measure spatial consistency between the
query and each result to improve retrieval quality
Many spatially consistent Few spatially consistent
matches – correct result matches – incorrect
result
Geometric verification
Gives localization of the object
Geometric verification
• Remove outliers, matches contain a high number of
incorrect ones
• Estimate geometric transformation
• Robust strategies
– RANSAC
– Hough transform
2D transformation models
• Similarity
(translation,
scale, rotation)
• Affine
• Projective
(homography)
Strategy 1: RANSAC
• RANSAC loop:
1. Randomly select a seed group of matches
2. Compute transformation from seed group
3. Find inliers to this transformation
4. If the number of inliers is sufficiently large, re-compute
least-squares estimate of transformation on all of the
inliers
• Keep the transformation with the largest number of
inliers
Problem with RANSAC
• In many practical situations, the percentage of outliers
(incorrect putative matches) is often very high (90% or
above)
• Alternative strategy: robust voting approach based on
Hough transform
Strategy 2: Hough transform
• General outline:
– Discretize parameter space into bins
– For each feature point in the image, put a vote in every bin in the
parameter space that could have generated this point
– Find bins that have the most votes
Image space Hough parameter space
P.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int.
Conf. High Energy Accelerators and Instrumentation, 1959
Strategy 2: Hough transform
• Suppose our features are adapted to scale and rotation
– Then a single feature match provides an alignment hypothesis (translation,
scale, orientation)
– Of course, a hypothesis obtained from a single match is unreliable
– Solution: let each match vote for its hypothesis in a Hough space with very
coarse bins
model
Hough transform details [Lowe’04]
• Training phase: For each model feature, record 2D
location, scale, and orientation of model (relative to
normalized feature frame)
• Test phase: Let each match between a test and a model
feature vote in a 4D Hough space
– Use broad bin sizes of 30 degrees for orientation, a factor of 2 for
scale, and 0.25 times image size for location
– Vote for two closest bins in each dimension
• Find all bins with at least three votes and perform
geometric verification
– Estimate least squares affine transformation
– Use stricter thresholds on transformation residual
– Search for additional features that agree with the alignment
Geometric verification – example
1. Query 2. Initial retrieval set (bag of words model)
3. Spatial verification (re-rank on # of inliers)
Oxford buildings dataset
Automatically crawled from Flickr
Consists of:
Oxford buildings dataset
All Soul's Bridge of
Sighs
Ashmolean
Keble
Balliol
Magdalen
Bodleian University
Museum
Thom
Tower
Radcliffe
Camera
Cornmarket
Ground truth obtained for 11 landmarks
Evaluate performance by mean Average Precision
Measuring retrieval performance: Precision - Recall
• Precision: % of returned images that
are relevant
• Recall: % of relevant images that are
returned
1
relevant returned
0.8 images images
0.6
precision
0.4
0.2
0
0 0.2 0.4 0.6 0.8 1 all images
recall
Average Precision
1
0.8
0.6 • A good AP score requires both high
precision
recall and high precision
0.4
AP
• Application-independent
0.2
0
0 0.2 0.4 0.6 0.8 1
recall
Performance measured by mean Average Precision (mAP)
over 55 queries on 100K or 1.1M image datasets
Mean Average Precision variation with vocabulary size
vocab size bag of spatial
words
50K 0.473 0.599
100K 0.535 0.597
250K 0.598 0.633
500K 0.606 0.642
750K 0.609 0.630
1M 0.618 0.645
1.25M 0.602 0.625