System and method for efficiently finding near-similar images in massive databases

Abstract

Massive amounts of multimedia data are stored in databases supporting web pages and servers, including text, graphics, video and audio. Searching and finding matching multimedia images can be time and computationally intensive. A method for storing and retrieving image data includes computing a descriptor, such an a Fourier-Mellin Transform (FMT), corresponding to a multidimensional space indicative of each of the stored images and organizing each of the descriptors according to a set similarity metric. The set similarity metric is based on Locality-Sensitive Hashing (LSH), and orders descriptors near to other descriptors in the database. The set similarity metric employs set theory which allows distance between descriptors to be computed consistent with LSH. A target image for which a match is sought is then received, and a descriptor indicative of the target image is computed. The database is referenced, or mapped, to determine close matches in the database. Mapping includes selecting a candidate match descriptor from among the descriptors in the database and employing a distance metric derived from the similarity metric to determine if the candidate match descriptor is a match to the target descriptor.