Research On Image-Feature-based Rapid Nearest Neighbor Retrieval Algorithms

With the rapid development of Internet,images and videos are taking the dominant role of texts.Due to the recent fast progresses of mobile networks,image-based applications become more and more popular.Among numerous image applications,image retrieval is fundamental and plays a critical role in real applications.Especially when the number of images is exponentially increasing recently,fast image retrieval is more important and more challenging.In front of this challenge,the traditional nearest neighbor image retrieval algorithm cannot simultaneously achieve fast speed and high precision.To resolve this issue,we propose a nearest neighbor retrieval algorithm based on product quantization and inverted indexing structure,which can obtain the desired high precision and fast speed and provide a promising image retrieval solution.Now we give the details of our work as follows.By combining the inverted indexing and quantization strategies,we make a good use of the classification property of the inverted indexing structure and significantly improve the speed of image retrieval.Our work regarding quantization is described below.We start with the product quantization method,analyze the relationship among quantization error,query vector and the quantized vector,and provide a distance estimation method,based on which a restricted threshold strategy is proposed to reduce the traverse operations and improve the retrieval speed.Specifically we apply the triangle inequality to compute an upper threshold on the real distance between image vectors,then iteratively improve that threshold until it approaches the real distance.Then that obtained threshold is implemented to restrict the traverse range.Under the inverted indexing structure,instead of visiting a given number of image vectors,we first compute the distance between each image vector and the query vector,and stop any further traverse operations if the computed distance is above the threshold.Compared with the original method,our method is more robust for different datasets,and can efficiently reduce traverse operations and improve the retrieval speed with pretty high search precisionOur improved nearest neighbor retrieval algorithm is implemented to solve the similar image retrieval problem of large scale databases.Aiming at that similar image retrieval question,we optimize image representation and image retrieval method.As for image representation,we fine-tune a convolutional neural network and extract image features from the fine-tuned network,which yields better performance than some traditional image features.We introduce a multi-feature based re-ordering strategy into the similar image retrieval process.More specifically,we uses the color histogram feature to re-order the first retrieved images,efficiently avoid the problem of large color difference among top-ranked retrieved images and,therefore,improve the retrieve performance.