Asymmetric Hashing For Large Scale Image Retrieval

With the explosive growth of both the number of images available on the Internet, twoproblems in content based image retrieval must be addressed: retrieval speed and storage cost.On the issue of speed, hashing methods are promising due to the sublinear time complexityfor solving large scale retrieval problems. Moreover, The computation of Hamming distancesbetween hash codes of the query and the stored images is very fast and can be accomplishedwith a simple data structure and efficient bit operations. Even the exhaustive computation ofmillions of Hamming distances could take only a second using a single CPU.Most current hashing methods need long codes to get the desirable performance.However, the storage cost of a long hash code for a large scale database is very large and itlimits the number of images being stored in memory. When the memory cannot accommodatehash codes for all images, frequent access to hard disks or a distributed system will be neededwhich is much slower than direct memory access. As a result, queries may collapse becauseof a long response time which severely limits the application of hashing methods with longcodes for large scale databases.To address this problem, we propose the Asymmetric Cyclical Hashing(ACH) to encodethe query and the database images with two distinct hash function to get n=mk bits and k bitscode respectively. A compact hash code is used to reduce the storage requirement, while along hash code is used for the query image to preserve more precise information. The imageretrieval is performed by computing the Hamming distances of the long hash code of thequery and the cyclically concatenated compact hash code of the stored images to yield highprecision and recall rates. Experiments on benchmarking databases consisting up to onemillion images show the effectiveness of the proposed method.