Regular Articles

Multiresolution descriptor matching algorithm for fast exhaustive search in norm-sorted databases

[+] Author Affiliations
Byung Cheol Song

Samsung Electronics Co., Ltd, Digital Media R&D Center, 416 Maetan-3dong, Yeongtong-gu, Suwon-City, 443-742, Republic of Korea

Jong Beom Ra

Korea Advanced Institute of Science and Technology, Department of Electrical Engineering and Computer Science, 373-1 Kusong-dong, Yusong-gu, Taejon, 305-701, Republic of Korea

J. Electron. Imaging. 14(4), 043019 (November 08, 2005). doi:10.1117/1.2132318
History: Received January 22, 2002; Revised May 25, 2002; Revised November 17, 2004; Accepted June 09, 2005; Published November 08, 2005; Online November 08, 2005
Text Size: A A A

To determine the best match to a query image in a database, conventional content-based image retrieval schemes require the exhaustive search, where the descriptor of the query, e.g., the histogram, must be compared with literally all images in the database. However, the straightforward exhaustive search algorithm is computationally expensive. Thus, fast exhaustive search algorithms are required. We present a fast exhaustive search algorithm based on a multiresolution descriptor structure and a norm-sorted database. First, we derive a condition to eliminate unnecessary matching operations from the search procedure by using a norm-sorted structure of the database. Then, we propose a fast search algorithm based on the elimination condition, which guarantees an exhaustive search for either the best match or multiple best matches to a query. With a luminance histogram as a descriptor, we show that the proposed algorithm provides a search accuracy of 100% with a high search speed.

Figures in this Article
© 2005 SPIE and IS&T

Topics

Databases

Citation

Byung Cheol Song and Jong Beom Ra
"Multiresolution descriptor matching algorithm for fast exhaustive search in norm-sorted databases", J. Electron. Imaging. 14(4), 043019 (November 08, 2005). ; http://dx.doi.org/10.1117/1.2132318


Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).

Some tools below are only available to our subscribers or users with an online account.

Related Content

Customize your page view by dragging & repositioning the boxes below.

Related Book Chapters

Topic Collections

PubMed Articles
Advertisement
  • Don't have an account?
  • Subscribe to the SPIE Digital Library
  • Create a FREE account to sign up for Digital Library content alerts and gain access to institutional subscriptions remotely.
Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).
Access This Proceeding
Sign in or Create a personal account to Buy this article ($15 for members, $18 for non-members).
Access This Chapter

Access to SPIE eBooks is limited to subscribing institutions and is not available as part of a personal subscription. Print or electronic versions of individual SPIE books may be purchased via SPIE.org.