Evaluating multidimensional indexing structures for images transformed by principal component analysis

Raymond T. Ng; Andishe Sedighian

doi:10.1117/12.234809

13 March 1996 Evaluating multidimensional indexing structures for images transformed by principal component analysis

Raymond T. Ng, Andishe Sedighian

Proceedings Volume 2670, Storage and Retrieval for Still Image and Video Databases IV; (1996) https://doi.org/10.1117/12.234809
Event: Electronic Imaging: Science and Technology, 1996, San Jose, CA, United States

Abstract

Content-based retrieval in image management systems requires indexing of image feature vectors. Most feature vectors have a high number of dimensions (15+). This makes indexing difficult since most existing multi-dimensional indexing structures grow exponentially in size as dimensions increase. We approach this problem in three stages: (1) reduce the dimensionality of the feature space, (2) evaluate existing multi-dimensional indexing structures to determine which one can best organize the reduced feature space, and (3) customize the selected structure to improve search performance. To reduce the dimensionality of the feature space without losing much information we apply a statistical technique called principal component analysis (PCA), using Turk and Pentland's eigenimages approach. We then conduct a comparative analysis of a wide range of existing multi-dimensional indexing structures, selecting and implementing three of them (bucket adaptive KD-tree, gridfile, R- tree) for further empirical comparisons. Tests show that the adaptive KD-tree uses the least storage and performs the best during search. Finally, we customize the bucket adaptive KD- tree by implementing techniques that take advantage of the characteristics of the transformed space -- namely, ranked dimensions by decreasing variance, and known dynamic ranges. This prunes the search space and results in very efficient searches. The number of page accesses are reduced significantly, sometimes leading to savings as high as 70%.

Citation Download Citation

Raymond T. Ng and Andishe Sedighian "Evaluating multidimensional indexing structures for images transformed by principal component analysis", Proc. SPIE 2670, Storage and Retrieval for Still Image and Video Databases IV, (13 March 1996); https://doi.org/10.1117/12.234809

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