Andrew M.Fraser

Portland State University and Los Alamos National Laboratory

Nicolas W.Hengartner, Kevin R.Vixie, and Brendt E.Wohlberg

Los Alamos National Laboratory

Los Alamos, NM 87545

USA

Abstract—We present a technique for combining prior knowledge about transformations that should be ignored with a covariance matrix estimated from training data to make an improved Mahalanobis distance classifier. Modern classification problems often involve objects represented by high-dimensional vectors or images (for example, sampled speech or human faces). The complex statistical structure of these representations is often difficult to infer from the relatively limited training data sets that are available in practice. Thus, we wish to efficiently utilize any available a priori information, such as transformations of the representations with respect to which the associated objects are known to retain the same classification (for example, spatial shifts of an image of a handwritten digit do not alter the identity of the digit). These transformations, which are often relatively simple in the space of the underlying objects, are usually non-linear in the space of the object representation, making their inclusion within the framework of a standard statistical classifier difficult. Motivated by prior work of Simard et al., we have constructed a new classifier which combines statistical information from training data and linear approximations to known invariance transformations. When tested on a face recognition task, performance was found to exceed by a significant margin that of the best algorithm in a reference software distribution.

The task of identifying objects and features from image data is central in many active research fields. In this paper we address the inherent problem that a single object may give rise to many possible images, depending on factors such as the lighting conditions, the pose of the object, and its location and orientation relative to the camera. Classification should be invariant with respect to changes in such parameters, but recent empirical studies [1] have shown that the variation in the images produced from these sources for a single object are often of the same order of magnitude as the variation between different objects.

Inspired by the work of Simard et al. [2] [3], we think of each object as generating a low dimensional manifold in image space by a group of transformations corresponding to changes in position, orientation, lighting, etc. If the functional form the transformation group is known, we could in principle calculate the entire manifold associated with a given object from a single image of it. Classification based on the entire manifold, instead of a single point leads to procedures that will be invariant to changes in instances from that group of transformations. The procedures we describe here approximate such a classification of equivalence classes of images. They are quite general and we expect them to be useful in the many contexts outside of face recognition and image processing where the problem of transformations to which classification should be invariant occur. For example, they provide a framework for classifying near field sonar signals by incorporating Doppler effects in an invariant manner. Although the procedures are general, in the remainder of the paper, we will use the terms faces or objects and image classification for concreteness.

Of course, there are difficulties. Since the manifolds are highly nonlinear, finding the manifold to which a new point belongs is computationally expensive. For noisy data, the computational problem is further compounded with the uncertainty in the assigned manifold.

To address these problems, we use tangents to the manifolds at selected points in image space. Using first and second derivatives of the transformations, our procedures provide substantial improvements to current image classification methods.

Here we outline our approach. For a more detailed development, see [4]. We start with the standard Mahalanobis distance classifier

where C_w is the within class covariance for all of the classes, μk is the mean for class k, and Y is the image to be classified. We incorporate the known invariances while retaining this classifier structure by augmenting the within class covariance C_w to obtain class specific covariances, C_k for each class k. We design the augmentations to allow excursions in directions tangent to the manifold generated by the transformations to which the classifier should be invariant. We have sketched a geometrical view of our approach in Fig. 1.

Denote the transformations with respect to which invariance is desired by τ(Y, θ), where and are the image and transform parameters respectively. The second order Taylor series for the transformation is

where R is the remainder,

Fig. 1. A geometrical view of classification with augmented covariance matrices: The dots represent the centers μk about which approximations are made, the curves represent the true invariant manifolds, the straight lines represent tangents to the manifolds, and the ellipses represent the pooled within class covariance C_w estimated from the data. A new observation Y is assigned to a class using The novel aspect is our calculation of where α is a parameter corresponding to a Lagrange multiplier, and is a function of the tangent and curvature of the manifold (from the first and second derivatives respectively) with weighting of directions according to relevance estimated by diagonalizing C_w.

We define

(1)

Where C_θ,k is a dim(Θ)×dim(Θ) matrix. We require that C_θ,k be non-negative definite. Consequently is also non-negative definite. When is used as a metric, the effect of the term is to discount displacement components in the subspace spanned by V_k, and the degree of the discount is controlled by C_θ,k. We developed [4] our treatment of C_θ,k by thinking of θ as having a Gaussian distribution and calculating expected values with respect to its distribution. Here we present some of that treatment, minimizing the probabilistic interpretation. Roughly, C_θ,k characterizes the costs of excursions of θ. We choose C_θ,k to balance the conflicting goals

We search for a resolution of these conflicting goals in terms of a norm on θ and the covariance C_θ,k. For the remainder of this section let us consider a single individual k and drop the extra subscript, i.e., we will denote the covariance of θ for this individual by C_θ.

If, for a particular image component d, the Hessian H_d has both a positive eigenvalue λ₁ and a negative eigenvalue λ₂, then the quadratic term θ^THθ is zero along a direction e₀ which is a linear combination of the corresponding eigenvectors, i.e. We suspect that higher order terms will contribute to significant errors when γ≥ min so we eliminate the canceling effect by replacing H_d with its positive square root, i.e. if an eigenvalue λ of H_d is negative, replace it with −λ. This suggests the following mean root square norm

(2)

Consider the following objection to the norm in Eqn. (2). If there is an image component d which is unimportant for recognition and for which H_d is large, e.g. a sharp boundary in the background, then requiring to be small might prevent parameter excursions that would only disrupt the background. To address this objection, we use the eigenvalues of the pooled within class covariance matrix C_w to quantify the importance of the components. If there is a large within class variance in the direction of component d, we will not curtail particular parameter excursions just because they cause errors in component d.

We develop our formula for C_θ in terms of the eigendecomposition

as follows. Break the dim(Θ)×dim(γ)×dim(Θ) tensor H into components

(3)

Then for each component, define the dim(Θ)×dim(Θ) matrix

(4)

and take the average to get

(5)

Define the norm