Location hashing: an efficient indexing method for locating object queries in image databases

Queries referring to content embedded within images are an essential component of content-based search, browse, or summarize operations in image databases. Localization of such queries under changes in appearance, occlusions and background clutter, is a difficult problem, for which current spatial access structures in databases are not suitable. In this paper we present a new method of indexing image databases called location hashing that uses a special data structure called the location hash tree (LHT) for organizing feature information from images of a database. Location hashing is based on the principle of geometric hashing and determines simultaneously, the relevant images in the database and the regions within them that are most likely to contain a 2d pattern query without incurring detailed search of either. The location hash tree being a red-black tree, allows for efficient search for candidate locations using pose-invariant feature information derived from the query.