JISE


  [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


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

  Retrieve PDF document (JISE_200802_15.pdf)