Evaluating multidimensional indexing structures for images transformed by principal component analysis
Evaluating multidimensional indexing structures for images transformed by principal component analysis
复制标题
评估通过主成分分析转换的图像的多维索引结构
DOI：
10.1117/12.234809
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
A. Sedighian
中科院分区：
文献类型：
--
作者：
R. Ng;A. Sedighian
图像管理系统中基于内容的检索需要对图像特征向量进行索引。大多数特征向量具有大量维度（15+）。这使得索引变得困难，因为大多数现有的多维索引结构的大小随着维度的增加而呈指数增长。我们分三个阶段解决这个问题：（1）减少特征空间的维度，（2）评估现有的多维索引结构以确定哪一个可以最好地组织减少的特征空间，以及（3）定制所选的结构以提高搜索性能。为了在不丢失太多信息的情况下降低特征空间的维数，我们应用了一种称为主成分分析 (PCA) 的统计技术，使用 Turk 和 Pentland 的特征图像方法。然后，我们对现有的多种多维索引结构进行比较分析，选择并实现其中的三种（桶自适应 KD 树、网格文件、R 树）以进行进一步的实证比较。测试表明，自适应KD树使用最少的存储空间并且在搜索过程中表现最好。最后，我们通过实现利用变换空间特征的技术来定制桶自适应 KD 树，即通过减少方差和已知的动态范围对维度进行排序。这会修剪搜索空间并导致非常有效的搜索。页面访问次数显着减少，有时节省高达 70%。
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%.