Approximate Nearest Subspace Search
with Applications to Pattern Recognition

Ronen Basri1    Tal Hassner1    Lihi Zelnik-Manor2

1. Dept. of Computer Science and Applied Math.
Weizmann Institute of Science

2. Dept. of Electrical Engineering
California Institute of Technology


Abstract:  Linear and affine subspaces are commonly used to describe appearance of objects under different lighting, viewpoint, articulation, and identity. A natural problem arising from their use is - given a query image portion represented as a point in some high dimensional space - find a subspace near to the query. This paper presents an efficient solution to the approximate nearest subspace problem for both linear and affine subspaces. Our method is based on a simple reduction to the problem of nearest point search, and can thus employ tree based search or locality sensitive hashing to find a near subspace. Further speedup may be achieved by using random projections to lower the dimensionality of the problem. We provide theoretical proofs of correctness and error bounds of our construction and demonstrate its capabilities on synthetic and real data. Our experiments demonstrate that an approximate nearest subspace can be located significantly faster than the exact nearest subspace, while at the same time it can find better matches compared to a similar search on points, in the presence of variations due to viewpoint, lighting etc.

Reference:  R. Basri, T.Hassner and L. Zelnik-Manor, Approximate Nearest Subspace Search with Applications to Pattern Recognition, CVPR'07, In print.

Click here for the PDF (1,513kb)

Click here for the CVPR'07 presentation slides (4,688kb)

Click here for the supplementary material PDF (2,632kb)

Click here for the BibTex

Errata: The Yale-Face experiments were run with ANN epsilon value of 10, and not 100 as reported.

Example result - subspaces for image approximation:

Approximate nearest patch Nearest patch Approximate nearest subspace Nearest subspace
Approximate nearest patch
Nearest patch
Approximate nearest subspace
Nearest subspace

Figure 1: Approximating the intensities of a query image by those of a separate database image (Figure 2, below). Results are presented for approximate nearest patch search, exact patch search, approximate nearest subspace search, and exact nearest subspace search. Please see text for more details.

Database image

Figure 2: The image used to produce the patch and subspace databases for the approximation


Copyright: no material is allowed to be copied or used in any way without written permission of the authors.

Last update 26th of June, 2007

eXTReMe Tracker