Satellite image retrieval application using Locality Sensitive Hashing in l 2 -space

This paper demonstrates the use of the Locality Sensitive Hashing technique operating in Euclidean metric space to build a data structure for Defense Meteorological Satellite Program (DMSP) satellite imagery database. Due to the high dimensionality of these images, their texture feature vectors are used. These features are extracted using pyramidal wavelet decomposition coupled with Gaussian central moments. Families of hash functions are drawn randomly and independently from a Gaussian distribution to create hash tables for these texture feature vectors of the images. The hash tables and the families of hash functions are then used to find similar satellite image matches to any query image in sublinear search time. When tested, our algorithm has proven to be about thirty three times faster than the linear search algorithm. In addition, our algorithm searches less than two percent of the entire database on the average to find the possible similar image matches to any given query without loss of accuracy. 1 2