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
0.6sec
|
Nearest patch
27.7sec
|
Approximate nearest
subspace
1.2sec
|
Nearest subspace
4.2sec
|
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.
Figure 2: The image
used to produce the patch and subspace databases for the approximation
