Fast multiresolution search algorithm for optimal retrieval in large multimedia databases

Byung Cheol Song; Myung Jun Kim; Jong Beom Ra

doi:10.1117/12.373552

23 December 1999 Fast multiresolution search algorithm for optimal retrieval in large multimedia databases

Byung Cheol Song, Myung Jun Kim, Jong Beom Ra

Proceedings Volume 3972, Storage and Retrieval for Media Databases 2000; (1999) https://doi.org/10.1117/12.373552
Event: Electronic Imaging, 2000, San Jose, CA, United States

Abstract

Most of the content-based image retrieval systems require a distance computation for each candidate image in the database. As a brute-force approach, the exhaustive search can be employed for this computation. However, this exhaustive search is time-consuming and limits the usefulness of such systems. Thus, there is a growing demand for a fast algorithm which provides the same retrieval results as the exhaustive search. In this paper, we prose a fast search algorithm based on a multi-resolution data structure. The proposed algorithm computes the lower bound of distance at each level and compares it with the latest minimum distance, starting from the low-resolution level. Once it is larger than the latest minimum distance, we can exclude the candidates without calculating the full- resolution distance. By doing this, we can dramatically reduce the total computational complexity. It is noticeable that the proposed fast algorithm provides not only the same retrieval results as the exhaustive search, but also a faster searching ability than 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 such as luminance histograms, edge images, and local binary partition textures.

Citation Download Citation

Byung Cheol Song, Myung Jun Kim, and Jong Beom Ra "Fast multiresolution search algorithm for optimal retrieval in large multimedia databases", Proc. SPIE 3972, Storage and Retrieval for Media Databases 2000, (23 December 1999); https://doi.org/10.1117/12.373552

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
7 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Databases

Image retrieval

Multimedia

Feature extraction

Distance measurement

Motion estimation

Binary data

Show All Keywords

Keywords/Phrases

Search In:

Publication Years