Binary Hashing And Quantization Methods For Approximate Nearest Neighbor Search

Approximate nearest neighbor(ANN)search is an important research topic in com-puter vision and multimedia fields,and has been widely adopted in many real applica-tions,such as image retrieval,person re-identification,etc.Given a query,ANN search aims to find its nearest neighbors from a large-scale dataset with sub-linear or even constant time complexity.Existing ANN search methods can be roughly divided into three categories:tree based methods,binary hashing based methods and quantization methods.With the efficient distance computation and low memory cost,binary hash-ing and quantization based methods have attracted gradually increasing research atten-tion.Binary hashing methods project original high-dimensional data points into low-dimensional binary codes,while quantization methods map original data points into the integer indices of the nearest codewords in codebook.We explore both of binary hashing and quantization methods,and propose three ANN search frameworks.(1)Linear distance preserving based binary hashing framework.Binary hashing methods usually need to learn a series of hashing functions to generate binary codes with fixed code length.In this thesis,we propose a general binary hashing framework based on a linear distance preserving objective.It simultaneously combines pairwise and point-wise distance preserving objectives to learn hash functions.The proposed linear distance preserving objective aims to preserve the linear transformation between the original Euclidean distance and the corresponding Hamming distance,which fully fits the distance preserving spirit of binary hashing.Based on different point-wise ob-jectives,we propose five methods to realize the proposed framework.(2)Deep supervised quantization framework.Quantization based methods are usually trained in unsupervised way and ignore the semantic information contained in datasets.However,applying supervised information can largely improve the ANN search performance.On the other hand,existing quantization methods conduct fea-ture learning and codebook learning in two separate stages,in which the ANN search performance is determined by the learned feature representation.We propose a deep su-pervised quantization framework to address these problems.It integrates convolutional neural networks and quantization network into a unified deep architecture,which simul-taneously learns deep features and codebook.Based on different codebook construc-tions,we propose three deep supervised quantization methods to realize the proposed framework.(3)Generative Adversarial Network based deep unsupervised quantization frame-work.There are very few deep unsupervised hashing methods adopted in unsupervised cases,because of the lack of label or classification information.However,obtaining su-pervised information is very expensive or even impossible in some real applications.In this thesis,we propose a new deep unsupervised quantization method,which can simul-taneously learn feature representation and quantizer.Each codeword in quantizer learns to generate a plausible image by generative adversarial network.The learning objec-tive is to optimize codewords in both of image space and feature space,which aims to make the generated codewords capture the image distribution and obtain discriminative information.In general,this thesis explores binary hashing methods and quantization methods for image retrieval.In this thesis,we propose three architectures for approximate near-est neighbor search.The experimental results on several public datasets show that the proposed realization methods obtain promising performance compared with existing approximate nearest neighbor search methods.