Efficient High-Dimensional Image Indexing Based  on SVD for Quadratic form Distance

doi:10.11834/jig.20060482

Views : 0 下载量: 210 CSCD: 0

PDF
Export
Share
Collection
Album

Efficient High-Dimensional Image Indexing Based on SVD for Quadratic form Distance
Vol. 11, Issue 4, Pages: 498(2006)
Published：2006
DOI： 10.11834/jig.20060482
稿件说明：

移动端阅览

DOI：

Efficient High-Dimensional Image Indexing Based on SVD for Quadratic form Distance[J]. Journal of Image and Graphics, 2006, 11(4): 498. DOI： 10.11834/jig.20060482.

摘要

向量近似方法（vector approximation file）是解决高维索引中维数灾难问题的一种有效方法，但是它不能直接支持二次式距离上的近邻搜索，为此，提出一种基于奇异值分解（SVD）的二次式距离上的向量近似方法，通过奇异值分解技术将二次式距离变换为欧氏距离形式，对变换后的特征向量进行近似得到近似向量。进行近邻搜索时采用低维过滤算法，先在较高能量的低维子空间内计算近似距离进行过滤，再对过滤结果进行高维距离计算。实验结果表明，低维过滤算法可以过滤掉大部分特征向量，而只有小部分数据需要进行高维距离运算，该方法可以显著提高大型高维图像数据库的近邻搜索性能。

Abstract

Many traditional indexing methods perform poorly in high dimensional vector space.The Vector Approximation File approach overcomes some of the difficulties of dimensionality curse

but it can't support the quadratic form metric.A novel VA-File approach for quadratic form distance is introduced in this paper.By the SVD of similarity matrix

the quadratic form distance can be converted to the Euclidean distance

and the approximation vector can be obtained. The low-dimensional filter algorithm is also applied during the nearest neighbor search.The vectors are first filtered with the low-dimensional approximate distance measure

and then the candidate results are re-computed with high-dimensional distance measure.The experimental results show that it can save the computational time significantly because only a small set of vectors is computed on the high-dimensional distance measure.