DocumentCode :
3427512
Title :
Fast Subspace Search via Grassmannian Based Hashing
Author :
Xu Wang ; Atev, Stefan ; Wright, John ; Lerman, Gilad
Author_Institution :
Math Dept., Univ. of Minnesota, Minneapolis, MN, USA
fYear :
2013
fDate :
1-8 Dec. 2013
Firstpage :
2776
Lastpage :
2783
Abstract :
The problem of efficiently deciding which of a database of models is most similar to a given input query arises throughout modern computer vision. Motivated by applications in recognition, image retrieval and optimization, there has been significant recent interest in the variant of this problem in which the database models are linear subspaces and the input is either a point or a subspace. Current approaches to this problem have poor scaling in high dimensions, and may not guarantee sub linear query complexity. We present a new approach to approximate nearest subspace search, based on a simple, new locality sensitive hash for subspaces. Our approach allows point-to-subspace query for a database of subspaces of arbitrary dimension d, in a time that depends sub linearly on the number of subspaces in the database. The query complexity of our algorithm is linear in the ambient dimension D, allowing it to be directly applied to high-dimensional imagery data. Numerical experiments on model problems in image repatching and automatic face recognition confirm the advantages of our algorithm in terms of both speed and accuracy.
Keywords :
computer vision; face recognition; image retrieval; Grassmannian based hashing; automatic face recognition; computer vision; fast subspace search; high-dimensional imagery data; image repatching; image retrieval; locality sensitive hash; point-to-subspace query; query complexity; Approximation algorithms; Complexity theory; Computational modeling; Computer vision; Databases; Search problems; Vectors; Grassmannian Based Hashing; Locality Sensitive Hashing; Subspace Search;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Vision (ICCV), 2013 IEEE International Conference on
Conference_Location :
Sydney, NSW
ISSN :
1550-5499
Type :
conf
DOI :
10.1109/ICCV.2013.345
Filename :
6751456
Link To Document :
بازگشت