This paper addresses the problem of affine distortions caused by viewpoint changes for the application of image retrieval. We study how to expand the visual words from a query image for better retrieval recall without the sacrifice of retrieval precision and efficiency. Our main contribution is the building of visual dictionaries that retain the mapping relationships between visual words extracted from different viewpoints of the same object. Additionally, in each mapping rule we record the affine transformation in which the two visual words are related, as a compact code of viewpoints relationships. By analogizing the concepts of verb stem and verb tense in text, we use Visual Stems to denote visual words extracted from robust local patches, and record the relationships between their affine variants as visual stem mapping rules, including the geometric relationships coded as Geometric Tenses. In this way, our method augments original visual vocabulary with sufficient and accurate expansion information. In query phase, only the objects corresponding to the same visual stems and coherent geometric tense codes will be regarded as similar ones. Moreover, the mapping rules can be learned offline with only one sample for each object. Experiments show that our method can support efficient object retrieval with high recall, requiring little extra time and space cost over traditional visual vocabularies.

Nearest neighbor search in Euclidean space is a fundamental problem in multimedia retrieval. The difficulty of exact nearest neighbor search has led to approximate solutions that sacrifice precision for efficiency. Among such solutions, approaches that embed data into binary codes in Hamming space have gained significant success for their efficiency and practical memory requirements. However, binary code searching only finds a big and coarse set of similar neighbors in Hamming space, and hence expensive Euclidean distance based ranking of the coarse set is needed to find nearest neighbors. Therefore, to improve nearest neighbor search efficiency, we proposed a novel binary code method called Integrated Binary Code (IBC) to get a compact set of similar neighbors. Experiments on public datasets show that our method is more efficient and effective than state-of-the-art in approximate nearest neighbor search.

Locality Sensitive Hashing (LSH) has been proposed as a scalable and high-dimensional index for approximate similarity search. Euclidean LSH is a variation of LSH and has been successfully used in many multimedia applications. However, hash functions of the basic Euclidean LSH project data points over randomly selected directions, which reduces accuracy when data are non-uniformly distributed. So more hash tables are needed to guarantee the accuracy, and thus more memory is consumed. Since heavy memory cost is a significant drawback of Euclidean LSH, we propose Data-Oriented LSH to reduce memory consumption when data are non-uniformly distributed. Most of existing methods are query-directed, such as multi-probe and query expansion methods. We focused on the hash table construction, and thus the query-directed methods can be applied to our index to improve further. The experiment shows that to achieve the same accuracy, our method uses less time and less memory compared with original Euclidean LSH.