Previous 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


Journal of Information Science and Engineering, Vol. 24 No. 2, pp. 553-571 (March 2008)

Utilization of Principle Axis Analysis for Fast Nearest Neighbor Searches in High-Dimensional Image Databases*

Tian-Luu Wu and Shyi-Chyi Cheng+
Department of Electronic Engineering
National Kinmen Institute of Technology
Kinmen, 892 Taiwan
*Department of Computer Science and Engineering
National Taiwan Ocean University
Keelung, 202 Taiwan

This paper presents an efficient indexing method for similarity searches in highdimensional image database by principal axis analysis. Image databases often represent the image objects as high-dimensional feature vectors and access them via the feature vectors and similarity measure. However, the performance of the existing nearest neighbor search methods is far from satisfactory for feature vectors of large dimensions. An interesting approach to solve the problem is to conduct the similarity search by a filtering mechanism, which represents vectors as compact approximations and skips a large amount of irrelevant matches by first scanning these smaller approximations. In this paper, we introduce the principal axis analysis for constructing a high-dimensional projection line and the projection scores on the line for the vectors in the database are used as the approximations for filtering. We also pay attention to enhance the discriminatory power of the approximations by incorporating the projection scores on multiple principal axes which are orthogonal with each other. Experimental results demonstrate that the performance of proposed indexing scheme is superior to both of the LPC-file method [2] and the sequential scan in terms of elapsed time and the number of disk accesses.

Keywords: high-dimension image database, nearest neighbor (NN) search, principal axis, dimension reduction, filter-based mechanism

Full Text () Retrieve PDF document (200803_15.pdf)

Received October 20, 2005; revised May 12, 2006; accepted November 12, 2007.
Communicated by Chung-Sheng Li.
*The preliminary version has been presented in 2005 IEEE International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS 2005), November, 2004.