Contextual weighting and efficient re-ranking for vocabulary tree based image retrieval
View Patent ↗Systems and methods are disclosed to search for a query image, by detecting local invariant features and local descriptors; retrieving best matching images by quantizing the local descriptors with a vocabulary tree; and reordering retrieved images with results from the vocabulary tree quantization.
1. A method to search for a query image, comprising
detecting local invariant features and local descriptors;
retrieving best matching images by incorporating one or more contexts in matching quantized local descriptors with a vocabulary tree;
reordering retrieved images with results from the vocabulary tree quantization;
measuring similarity of local descriptors through image specific descriptor weighting; and
comprising v, where weight w i q is defined based on the node counts along the quantization path of x i , comprising determining
w
i
q
=
∑
v
∈
T
(
x
i
)
ω
(
v
)
∑
v
∈
T
(
x
i
)
ω
(
v
)
×
n
q
(
v
)
,
where ω(v) is a weighting coefficient set to idƒ(v) empirically, where weight w i q depends on the descriptor only, and is shared for all nodes v along the path T(x i ) and where n q (v) represents a number of descriptors in image q that are quantized to v.
2. The method of claim 1 , comprising providing an image specific weighting of local features to reflect the local feature discriminative power in different images.
3. The method of claim 1 , comprising matching local spatial contexts of a feature, including density of neighbor's features, mean scales and orientation differences.
4. The method of claim 1 , comprising reusing local feature quantization provided by the vocabulary tree and contexts to perform a fast re-ranking for top retrieved images.
5. The method of claim 1 , comprising generating inverted index files for the vocabulary tree.
6. The method of claim 5 , comprising training the vocabulary tree offline for local invariant descriptors by hierarchical K-means clustering.
7. The method of claim 5 , comprising indexing database images to tree nodes using the inverted index files.
8. The method of claim 1 , wherein the vocabulary tree comprises inverted index files, comprising accumulating a similarity score of local features and tree nodes (visual words) vote for an image and providing images with highest similarity scores as retrieval results.
9. The method of claim 1 , comprising performing re-ranking to select a subset of local descriptors for SIFT feature matching.
10. The method of claim 9 , comprising adding node weights of matched SIFT features in an intersection of two sub graphs specified by neighborhood relations to a matching score to re-order the top candidates.
11. The method of claim 1 , comprising measuring similarity of local descriptors spatial context statistics.
12. The method of claim 11 , comprising builds two graphs from matched {x′ i } and {y′ j } where x′ i links to x″ i which is in a spatial neighborhood C(x′ i ), where C(ƒ) denotes a neighborhood of one feature given by a disc (u, R).
13. The method of claim 12 , comprising determining an intersection of the two graphs and adding a weighted idƒ(v l′,h′ ) to a matching score sim(q,d m ) to re-order top returned images.
14. The method of claim 12 , comprising determining a final similarity score of two images as
sim
_
(
q
,
d
m
)
=
.
sim
(
q
,
d
m
)
+
∑
{
x
i
′
}
α
(
x
i
′
)
idf
(
v
l
′
,
h
′
)
,
where
α
(
x
i
′
)
=
{
x
i
″
|
x
i
″
∈
C
(
x
i
′
)
and
y
i
″
∈
C
(
y
i
′
)
}
C
(
x
i
′
)
and x″ i matches to y″ i , the ratio of common neighbors of x′ i in the query and its matched feature y′ i in the database image.