TY - JOUR
T1 - Multiresolution descriptor matching algorithm for fast exhaustive search in norm-sorted databases
AU - Song, Byung Cheol
AU - Ra, Jong Beom
PY - 2005/10
Y1 - 2005/10
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33644649633&partnerID=8YFLogxK
U2 - 10.1117/1.2132318
DO - 10.1117/1.2132318
M3 - Article
AN - SCOPUS:33644649633
SN - 1017-9909
VL - 14
JO - Journal of Electronic Imaging
JF - Journal of Electronic Imaging
IS - 4
M1 - 043019
ER -