A fast multiresolution feature matching algorithm for exhaustive search inlarge image databases

Most of the content-based image retrieval systems require a distance comput ation for each candidate image in the database. As a brute-force approach, the exhaustive search can be employed for this computation. However, this e xhaustive search is time-consuming and limits the usefulness of such system s. Thus, there is a growing demand for a fast algorithm which provides the same retrieval results as the exhaustive search. In this paper, me propose a fast-search algorithm based on a multiresolution data structure. The prop osed algorithm computes the loa er bound of distance at each level and comp ares it with the latest minimum distance, starting from the low-resolution level. Once it is larger than the latest minimum distance, we can remove th e candidates without calculating the full-resolution distance. By doing thi s, we can dramatically reduce the total computational complexity. It is not iceable that the proposed fast algorithm provides not only the same retriev al results as the exhaustive search, but also a faster searching ability th an existing fast algorithms. For additional performance improvement, we can easily combine the proposed algorithm with existing tree-based algorithms. The algorithm can also be used for the fast matching of various features s uch as luminance histograms, edge histograms, and local binary partition te xtures.