| The traditional approach to recognition has been to represent objects by shape. The technique of parametric eigenspace allows us to represent objects by their appearance, rather than shape. In this technique, a set of learning images is first obtained. The image set is compressed to obtain a low-dimensional subspace, called the eigenspace, in which the image set is represented as a continuous appearance manifold. Given an unknown input image, recognition is performed by projecting the input image to eigenspace and identifying the point on the manifold, closest to the projected point. The closest point search is the classical high dimensional nearest neighbor problem.; We propose a search algorithm to solve this problem efficiently. Rather than searching for the closest point, our algorithm searches for the closest point within distance {dollar}epsilon.{dollar} Analysis of the proposed search algorithm reveals that in high dimensional spaces, the complexity is approximately {dollar}O((n + 1)epsilon ),{dollar} which means that it is only linearly dependent on {dollar}epsilon{dollar} and the number of database points, n. This is much better than the exponential dependence on the number of dimensions d, typically observed in competetive search techniques, such as k-d tree. To substantiate our claims, we carried out a comprehensive series of benchmarks that compare our algorithm to other search techniques such as k-d tree, R-Tree, Yunck's search technique, to name a few. The proposed search algorithm, along with the parametric appearance technique, leads to a simple and fast solution to usually difficult problems in computer vision and other areas.; As examples, a real-time recognition system with 100 complex objects, a real-time visual positioning and tracking system, a temporal object inspection system, and video compression applications are described. We present a complete set of experiments that demonstrate the practicality of these applications. The generality of the proposed ideas have led to the development of a comprehensive software library for appearance matching (SLAM). SLAM has allowed many researchers to apply the ideas of parametric appearance matching to applications other than the ones that we describe. |
