Re-ranking With Two Level Hashing

The Internet has grown rapidly over the past few decades.After the deployment of Web2.0,User Generated Content(UGC)is produced and cumulated exponentially.Image retrieval is one of the most important applications on the Internet and has developed from keyword based image retrieval to content based image retrieval.In practice,content based image retrieval methods are usually implemented using high-dimensional approximated nearest neighbor searches.However,when facing large scale databases,traditional techniques(e.g.K-D Tree)fail to process online high-dimensional approximated nearest neighbor search.In recent years,hashing-based coding algorithms have been proved to be a great success in both theory and practice.Hashing based coding methods only require sub-linear computational complexity when facing large scale databaseA lot of hashing-based approximated nearest neighbor search methods have been proposed in recent years.The major challenge of these hashing researches is the trade-off between the similarity preservation and the code length.A long binary code preserves a lot of image similarity information while decreases the recall rate and increases the computational complexity.A short binary code yields a high recall rate and low computation complexity while dramatically decreases the retrieval precision.Almost all existing methods do not explicitly address this dilemma.To handle this dilemma,we proposed a re-ranking method with a two-level hashing algorithm.Though using two different query processes,it preserves a high image relevance while keeping computational complexity as small as short binary code's.At the first level,the proposed query sensitive mapping and the conditional dissimilarity are used to select a small amount of “good” hash functions to implement a query sensitive filtering to retrieve most of the irrelevant images using a short code.At the second level,the full-length code is directly used to re-rank the retrieved images,such that images similar to the query will be moved to the front of the retreival list.Owing to the much smaller amount of images to be processed,the computational cost of using long code will be small.Experimental results on several benchmarking databases show the validity of the proposed method.