[aMMAI] Paper Summary: Lost in Binarization : Query-Adaptive Ranking for Similar Image Search with Compact Codes

Title: Lost in Binarization : Query-Adaptive Ranking for Similar Image Search with Compact Codes

Author: Yu-Gang Jiang, Jun Wang, Shih-Fu Chang

Publication:  ICMR, 2011

Hamming distance lacks in providing good ranking that is crucial for image search – there can be different binary codes sharing equal distance.

This paper proposes a novel approach to compute query-adaptive weights for each bit of the binary codes, which has two main advantages.

First, with the bit-level weights, they are able to rank the returned images at a finer-grained binary code level, rather than at the traditional Hamming distance level.

Second, contrary to using a single set of weights for all the queries, our approach tailors a different and more suitable set of weights for each query.

In this paper, choose the popular bag-of-visual-words (BoW) framework grounded on the local SIFT features.

Three data structure:

1) inverted index: This largely limits the application of inverted files for large scale image search.

2) tree-based index: not suitable for high-dimensional feature

3) binary embedding: SSH&DBN (this paper choose to use)

Learning Class-Specific Weights

Intra-class:

To learn k weight vectors a1,...,ak, where ai corresponds to class i.

ai: nonnegative & sum of all a is 1

Sum the distance from every node in class to the class center cⁱ

Inter-class:

This maintains the class relationship, which is important since the semantic classes under our consideration are not exclusive – in fact some of them are highly correlated (e.g., tree and grass).

Add sij to measure the distance from difference class.

Base on above, the following optimization problem to learn the weights for each class:

Where 入 > 0 is a parameter that controls the balance of the two terms.

Optimization problem can be efficiently solved using an iterative quadratic programming (QP) scheme.

Query-Adaptive Weight:

First using Hamming distance retrieval result to generate query adaptive weights

The query adaptive weights aq are computed vi linear combination

T: most 3 relevant semantic classes to query q

Mi: as the number of images from class T (random selection 500 image)