|
Ronen Basri: Research |
|
Nearest subspace search
Linear and affine subspaces are commonly used to describe the 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. We have proposed an efficient solution to the approximate nearest subspace problem. 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. 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. What lies ahead? Our reduction to nearest neighbors with point maintains the monotonicity of the distances to the subspaces in the database, but adds an undesired offset. This offset is inherent—we proved that no reduction to points can be done without an offset. But this does not rule out other approaches to solve the nearest subspace problem. |
|
In ANS given a dataset of subspaces and a query point we seek an efficient way to find the nearest subspace to the query. |
|
The two original input images (middle and right) are reconstructed from database patches extracted from the scenery picture (left). We show two reconstructions by approximate nearest subspace (ANS) of patches against approximate nearest patch (ANN). |
|
Our approximate nearest subspace algorithm was presented in |
