Research About Image Retrieval Based On Hashing Technology

With rapid increase of the image dataset scale, how to retrieve an image quickly and correctly has become an important research area in intelligent information processing. Image retrieval technology is divided into offline retrieval and online retrieval according to time requirement. Offline retrieval includes global feature based retrieval and local feature based retrieval. In global feature based retrieval, images are represented with high dimensional vectors, and retrieval procedure costs much time with low efficiency. In local feature based retrieval, images are indicated through visual dictionary, whose generation costs much time and unsuitable for incremental clustering. For online retrieval, time efficiency is very important. Therefore, feature extraction and similarity measure method is urgent. These limitations come down to two key points, that is, high dimension clustering and real time computation, which can be improved by hashing technology. Locality Sensitive Hashing can cluster image global features and generate fast index structure, and it can also cluster local features to generate visual dictionary. General hashing can generate signature features for images or videos, which can be used in real time retrieval. Image retrieval based on hashing technology is studied in this thesis, and the main contributions were listed as follows:1. Fast image clustering is researched, and a new image clustering method based on Locality Sensitive Hashing is presented, aiming to overcome drawbacks of current clustering method in image clustering especially in visual clustering, i.e. long running time, high computation cost and no supporting for incremental clustering in high dimension space. Firstly, clustering priority level of image features is computed to choose the best feature by discrimination index. Secondly, image features are projected to bucket indices by Locality Sensitive Hashing function. Thirdly, images are clustered by merging bucket indices. Experimental results show that this method can cluster images with the advantage of 2~3 order in time efficiency, and achieve the nearly equivalent accuracy compared with k-means algorithm, and it is suitable for incremental clustering, which makes it possible for large scale data clustering in high dimension space.2. Offline image retrieval based on global feature is studied, and a new image retrieval method based on frequency voting in multiple table from E2LSH(Exact Euclidean Locality Sensitive Hashing) is proposed, aiming to relieve the two limitations of E2 LSH, i.e. randomicity in single hashing table retrieval and high main memory cost. Firstly, multiple hash functions are constructed and images are projected to multiple bucket map chains. Secondly, bucket index of query image is computed, and is queried on all bucket map chains to get multiple retrieval vectors. Thirdly, retrieval matrix is constructed by retrieval vectors. Finally, resulting retrieval vector is obtained by frequency item voting of retrieval matrix. Experimental results showed that, the memory cost reduced to less than one over ten compared with the enhanced retrieval accuracy compared with E2 LSH, and the larger the image scale is, the more memory saves.3. Offline image retrieval based on local features is researched, and a new image retrieval method based on ensemble locality sensitive clustering BoVW(bag of visual words) is put forward, aiming to overcome the limitations of current visual dictionary generation method, i.e low efficiency and no supporting for incremental clustering. Firstly, local features of all images are projected to get multiple bucket indices. Secondly, bucket indices are clustered to get base partitions. Thirdly, base partitions are aggregated to obtain final partition, i.e. visual dictionary. Finally, all images are represented by frequency of visual words, image retrieval are performed according the frequency vector. Experimental results show that this method can shorten the clustering time in visual dictionary generation, and enhance the adaptability to dynamic image dataset clustering, and improve the performance of image retrieval based on BoVW.4. Online image retrieval in MPEG(Moving Picture Expers Group) stream is studied, and an online image retrieval method based on robust hashing signature is raised, aiming to relieve limitations of current image retrieval methods, i.e. complicated image representations, high computation cost, long time cots and difficult implementation for real time retrieval. Firstly, the robust hash function is designed, and signature of retrieval image is generated by 2-dimension DCT(Discrete Cosine Transform). Secondly, the signatures of all frames in video stream are extracted. Thirdly, hamming distance is calculated between them, and similarity decision is made. Experimental results show that this method can extract feature and calculate the similarity in real time, and the retrieval time of single image is 0.25 ms, so it is suitable for online image retrieval.5. Online video retrieval is studied, and an online video retrieval method based on video hash signature is proposed to overcome limitations of current video retrieval, i.e. high computation and time cost and difficult implementation for real time retrieval. Firstly, hash function is designed, and the signature of query video is obtained by their frame data count. Secondly, the signature of fixed length video in MPEG stream is acquired. Finally, similarity of the two signatures is computed to perform video retrieval. Experimental results show that this method can extract video feature and calculated similarity real time, and online retrieval can be satisfied.