Object detection and recognition using structured dimensionality reduction

Let O be the space of observations (for example, images), let Q be the set of possible geometric deformations with N degrees of freedom, and let S be a set of known objects. We assume that the observations are constructed by the following procedure: we first choose an object s E S and an arbitrary geometric deformation φ E Q. Next, we define an operator ψ : S x Q -> O that acts on an object and a geometric deformation, producing an observation. The observation is o = ψ(s, φ). For a specific object s E S we will denote by ψs : Q O the restriction of the map to this object. We assume that the N parameters characterizing Q are embedded in some linear space. For example, if Q is the set of functions describing invertible two dimensional affine deformations then Q is of dimension 6 and each geometric deformation is given by φ(x, y) = (ax + by + c, dx + ey + f). For any object (function) g E S the set of all possible observations on this particular function is denoted by S_g. We refer to this subset as the orbit of g under Q. In general, since ψ is not linear, this subset is a non linear manifold in the space of observations. The orbit of each function forms a different manifold. Since in general O has a very high dimension (the number of pixels), one must find an accurate description of S_g in order to enable any further analysis of it. Dimensionality reduction methods rely on dense sampling of S_g to achieve this description using low dimensional patches. We next show that under the above assumptions and for some specific choices of Q there exists a map T : O -> H such that H is a linear space, which we call the reduced space. Moreover, the map T 0 ψs : Q -> H is linear and invertible. These properties hold for every object s E S and the map T is independent of the object. We call such a map T, universal manifold embedding as it universally maps each of the differe- t manifolds, where each manifold corresponds to a single object, into a linear subspace such that the overall map T 0 ψs : Q -* H is linear. Hence, each manifold is mapped into a linear subspace of H whose dimension is identical to that of Q. This universal map allows us to represent the (mapped) observation in a space where the action of Q is linear.