Open Collections

Efficient and effective subimage similarity matching for large image databases

University of British Columbia

As network connectivity has continued, its explosive growth and storage devices have become smaller, faster, arid less expensive, the number of on-line digital images has increased rapidly] Correspondingly, efficient and effective content-based retrieval systems for handling image queries have become necessary. In addition, users are often interested in local contents within subimages. In this thesis, we develop Padding and Reduction Algorithms to support subimage queries of arbitrary size based on local color information. The idea is to estimate the best-case lower bound to the dissimilarity measure between the query and the image. By making use of multiscale representation, this lower bound becomes tighter as the scale becomes finer. Because image contents are usually pre-extracted and stored, a key issue is how to determine the number of levels used in the representation. We address this issue analytically by estimating the required CPU and I/O costs, and experimentally by comparing the performance and the accuracy of the outcomes of various filtering schemes. Our findings suggest that a 3-level hierarchy is preferred. We also study three strategies for searching multiple scales. Our studies indicate that the hybrid strategy with horizontal filtering on the coarse level and vertical filtering on remaining levels is the best choice when using Padding and Reduction Algorithms. Using the hybrid search strategy in the multiscale representation with the determined number of levels, the best 10 desired images can be retrieved efficiently and effectively from a collection of a thousand images in about 3.5 seconds.

Thesis/Dissertation

application/pdf

2009-03-25

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/6537

Computer Science

University of British Columbia

UBCV

DSpace