Method and Apparatus for Object Recognition

This invention relates generally to the field of object recognition and in particular to a neural network method and apparatus for object and/or face recognition.

The need for reliable personal identification methods, particularly for computerized access control has resulted in an increased interest in biometrics, that is, physiological or behavioral characteristics which uniquely identify individuals. Biometric characteristics presently attracting a considerable amount of interest include fingerprints, speech, signature dynamics and face recognition. Of these biometric characteristics, face recognition has the distinct benefit of being a passive, non-intrusive system for verifying a personal identity. (See e.g., R. Chellappa, C. L. Wilson, and S. Sirohey, "Human and Machine Recognition of Faces: A Survey", Proceedings of the IEEE, Vol. 83, pp. 705-740, May 1995).

By way of background, the techniques used in face recognition systems depend largely upon the particular application of the face recognition system. For example, if one desires to find the face of a person within a large database of faces, e.g., in a police database, it is generally not necessary that the face recognition be performed in real-time. As such, these non-real-time systems are only typically required to return a list of the most likely faces in the database. These faces can then be analyzed by a human operator.

In sharp contrast, real-time face recognition applications impose demanding requirements on face recognition systems. Specifically, in those applications where it is necessary to identify a particular person or persons in real-time, e.g., in a security monitoring system, location tracking system, or a security access system, a face must be quickly and accurately recognized, else serious security breaches/consequences may result.

Much prior-art effort has been expended exploring geometrical, feature-based methods of face recognition. In particular, R. Brunelli and T. Poggio in an article entitled "Face Recognition: Features Versus Templates", which appeared in Pattern Analysis and Machine Intelligence, 15(10), pp. 1042-1052; describe a method which computes a set of geometrical features of faces such as nose width and length, mouth position, and chin shape. Others, such as I. Cox, J. Ghosn, and P. Yianilos describe a mixture-distance technique in a technical report entitled "Feature-Based Face Recognition Using Mixture-Distance", NEC Research Institute, Princeton, N.J., October 1995, which achieves a relatively high recognition rate by representing each face with 30 manually extracted distances.

Systems which utilize methods employing precisely measured distances between features are highly dependent upon the particular feature point location method. Unfortunately, current methods for the automatic location of feature points do not provide a high degree of accuracy, are not very robust and therefore do not readily lend themselves to demanding, realtime application of face recognition.

Recently, M. Turk and A. Pentland, in an article entitled "Eigenfaces for Recognition", which appeared in the Journal of Cognitive Neuroscience, Vol. 3, pp. 71-86, 1991, and in U.S. Pat. No. 5,164,992 entitled "Face Recognition System" which issued on Nov. 17, 1992, describe a face recognition scheme in which facial images are projected onto the principal components of an original set of training images. The resulting "eigenfaces" are classified by comparison with known individuals. This linear principle components technique assumes that the faces lie in a lower dimensional space, and hence the sum or average of two faces should also be a face. This assumption fails when applied to an entire face.

Most recently, the prior art has focused on face-recognition techniques which utilize neural networks. Specifically, D. DeMers and G. Cottrell, in an article entitled "Non-linear Dimensionality Reduction", which appeared in Advances in Neural Information Processing Systems 5, pp. 580-587, S. J. Hanson, J. D. Cowan, and C. L. Giles, eds., Morgan Kaufman, San Mateo, 1993, describe a system in which the first 50 principal components of a set of images are extracted and reduced to 5 dimensions using an autoassociative neural network. The resulting representation is then classified using a standard multi-layer perceptron. Unfortunately, the database used by these authors is quite simple, the pictures are manually aligned and there is no lighting variation, rotation, or tilting of the images. As such, the systems and methods disclosed therein are generally not suitable for demanding, realtime recognition applications.

A hierarchical neural network which was automatically grown and not trained with a gradient-descent training algorithm was used for face recognition by J. Weng, N. Ahuja, and T. S. Huang and described in the article "Learning Recognition and Segmentation of 3-D Objects from 2-D Images", which appeared in International Conference on Computer Vision 93, pp. 121-128, 1993. The system disclosed in this article operates on directional edges extracted from the image, thereby ignoring most of the information in the image and introducing dependence on the performance of the edge extraction algorithm. The learning algorithm is incremental and hence cannot learn to extract optimal features for given objects. As such, the system has only been shown to work in very simple discrimination tasks.

Finally, in U.S. Pat. No. 5,386,103 issued to DeBan, et al. in January 1995, the inventors describe a face recognition method and system which projects original images onto eigenvectors of the covariance matrix of a training set. A neural network is subsequently used to compare coefficients with stored values.

Despite initial optimism and promise, however, existing prior art methods and techniques for face recognition suffer from several serious limitations. In particular, "eigenface" methods such as those described by Turk and Pentland, template matching techniques such as the one described by Brunelli and Paggio, and the method and apparatus disclosed by DeBan, et al., are limited due to the requirement of a high degree of correlation between the pixel intensities of the training and test images. Additionally, they are only effective when the query images have the same scale, orientation, and illumination as the training images. Finally, they are not invariant to local deformation in the image, such as a different facial expression.

Consequently, a continued need remains in the art for a method and apparatus which quickly, reliably and accurately recognizes faces.

The above problems are solved and an advance is made over the prior art in accordance with the principles of the present invention which combines a local image sampling technique, a self-organizing map neural network, and a convolutional neural network into a face recognition system.

Specifically, a fixed size window is stepped over one or more entire images in a set of images and local image samples are extracted at each step.

A self-organizing map is trained on a set of vectors generated in the previous step. The self organizing map quantizes the input vectors into a number of topologically ordered values. Alternatively, a Karhunen-Loeve transform may be substituted for the self organizing map whereby the Karhunen-Loeve transform projects the vectors from one space to another space of lower dimension.

Subsequently, the fixed sized window is then stepped over all of the images contained in any training and test sets. The resulting local image samples are passed through the self organizing map at each step, thereby creating new training and test sets in the output space created by the self-organizing map. Each face image input to the system is finally represented by a number of maps, each of which corresponds to a dimension in the self organizing map. Finally, a convolutional neural network is trained on the newly created training set.

Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention are described in detail below with reference to the accompanying drawings.

The teachings of the present invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which:

FIG. 1 is a high-level block diagram of a face recognition system utilizing the teachings of the present invention;

FIG. 2 is a detailed block diagram of the system of FIG. 1 showing alternatives for various functions;

FIG. 3 is a depiction of a local image sampling process;

FIG. 4 shows a two-dimensional self-organizing map having a square neighborhood function which starts as n.sub.c (t.sub.1) and reduces in size to n.sub.c (t.sub.3) over time; and

FIG. 5 is a prior art convolutional neural network for recognizing characters.

A preferred embodiment of the invention will now be described while referring to the figures, several of which may be simultaneously referred to during the course of the following description.

Referring now to FIG. 1, there is shown a flowchart which depicts the high-level processing of images and their subsequent classification. Specifically, images 100 are sampled at image sampling block 110, processed by dimensionality reduction block 120, feature extraction block 130, and classifier block 140 which produces a classification 150 of the processed image(s).

With reference now to FIG. 2, there is shown a system for performing the processing depicted in FIG. 1. In particular, images are sampled and results of the sampling are presented to either a self-organizing map 200, or alternatively, a Karhunen-Loeve Transform module 210 for dimensionality reduction. Classification of the sampled and reduced images is performed by multi-layer perceptron 250, or alternatively hybrid convolutional neural network 260 which includes feature extraction layers 220, and multi-layer perceptron style classifier 230, or nearest neighbor classifier 240. The resulting output of the hybrid convolutional neural network or the multi-layer perceptron is image classification 270.

Two different methods of representing a local image sample have been used and evaluated in the construction of the present invention. In each of the two methods, as shown in FIG. 3, a window is scanned (stepped) over the image and a vector is created for each location of the image stepped over.

The first of the two image representation methods generates a vector from a local window positioned on the image using intensity values corresponding to each point in the window. Specifically, if x.sub.ij is defined to be the intensity at the i.sup.th column and the j.sup.th row of the given image, and the local window is a square having sides 2W+1 long, centered on x.sub.ij, then the vector associated with this window is simply [x.sub.i-W,j-W, x.sub.i-W,j-W+1, . . . , x.sub.ij, . . . , x.sub.i+W,j+W-1, x.sub.i+W,j+W ].

The second of the two image representation methods generates a representation of the local sample by forming a vector from a) the intensity of a center pixel x.sub.ij, and b) an intensity difference between the center pixel and all other pixels contained within a square window. The vector so formed is given by [x.sub.ij -x.sub.i-W,j-W, x.sub.ij -x.sub.i-W,j-W+1, . . . , w.sub.ij x.sub.ij, . . . , x.sub.ij -x.sub.i+W,j+W-1, x.sub.ij -x.sub.i+W,j+W ]. This representation is partially invariant to variations in intensity of an image. The amount of invariance can be modified by adjusting a weight, w.sub.ij, associated with the central intensity component.

The self-organizing map (SOM), described by Teuvo Kohonen in an article entitled The Self-Organizing Map, which appeared in Proceedings of the IEEE, Vol. 78, pp. 1464-1480, in 1990, is an unsupervised learning process which learns the distribution of a set of patterns without any class information. In operation, a pattern is projected from an input space to a position within the self-organizing map and information is coded as the location of an activated node. The SOM is unlike other classification or clustering techniques in that it provides a topological ordering of the classes. Similarity in input patterns is preserved in the output of the process. The topological preservation of the SOM process makes it especially useful in the classification of data which includes a large number of classes. In the local image sample classification, for example, there may be a very large number of classes in which the transition from one class to the next is practically continuous therefore making it difficult to define hard class boundaries.

The SOM defines a mapping from an input space R.sup.n onto a topologically ordered set of nodes, usually in a lower dimensional space. An example of a two-dimensional SOM is shown in FIG. 4. A reference vector in the input space, m.sub.i .ident.[.mu..sub.i1, .mu..sub.i2, . . . , .mu..sub.in ].sup.T .di-elect cons.R.sup.n, is assigned to each node in the SOM. During training, each input, x, is compared to all the m.sub.i, obtaining the location of the closest match according to a particular metric. The input point is mapped to this location in the SOM.

Nodes in the SOM are updated according to the metric and their position in relation to the winning node. For example, nodes may be updated according to:

where t is the time during learning and h.sub.ci (t) is the neighborhood function, a smoothing kernel which is maximum at m.sub.c. Usually, h.sub.ci (t)=h(.parallel.r.sub.c -r.sub.i .parallel.,t), where r.sub.c and r.sub.i represent the location of the nodes in the SOM output space. The node with the closest weight vector to the input sample is r.sub.c and r.sub.i ranges over all nodes. The variable h.sub.ci (t) approaches 0 as .parallel.r.sub.c -r.sub.i .parallel. increases and also as t approaches .infin.. While those skilled in the art can recognize that a number of neighborhood functions may be used, one useful neighborhood function is: ##EQU1## where .alpha.(t) is a scalar valued learning rate and .sigma.(t) defines the width of the kernel. The SOM can be considered a non-linear projection of the probability density p(x).

Self-organizing maps are normally used for the visualization of data. However, in the present invention, numbers are assigned to the nodes along each dimension of the SOM allowing the winning SOM output to be encoded into a vector whose length is equal to the number of dimensions in the SOM. Thus, the original vectors are mapped into a lower dimensional space such that points which are nearby in the original space are also nearby in the output space.

An efficient method known in the art which is utilized for reducing redundancy in a dataset is the Karhunen-Loeve (KL) transform or eigenvector expansion via Principle Components Analysis (PCA). PCA generates a set of orthogonal axes of projections known as the principal components, or the eigenvectors, of the input data distribution in the order of decreasing variance. The KL transform is a statistical method for feature extraction and multivariate data projection and has been used widely in pattern recognition, signal processing, image processing, and data analysis. Points in an n-dimensional input space are projected into an m-dimensional space, m.ltoreq.n. The KL transform may be used as an alternative for the SOM in the dimensionality reduction of the local image samples. It should be noted that the use of the KL transform is not the same as in the eigenfaces approach because here, small local image samples are operated upon as opposed to the entire images. The KL technique is fundamentally different to the SOM method, as it assumes the images are sufficiently described by second order statistics, while the SOM is an attempt to approximate the probability density.

In principle, it should be possible to train a sufficiently large, multi-layer perceptron neural network to perform any required mapping--including that required to perfectly distinguish the classes in face recognition. In practice, however, such a system is unable to form the required features in order to generalize to unseen inputs (the class of functions which can perfectly classify the training data is too large and it is not easy to constrain the solution to the subset of this class which exhibits good generalization). A network which is large enough to classify the training data exhibits overfitting, functioning similarly to a lookup table and generalizing poorly. Additionally, there is no invariance to translation or local deformation of the images with such networks.

Convolutional networks (CN) are able to achieve a degree of shift and deformation invariance due to three characteristics, namely local receptive fields, shared weights, and spatial subsampling. The use of shared weights also reduces the number of parameters in the system, thereby aiding generalization.

Furthermore, convolutional networks have been successfully applied to character recognition as demonstrated by Y. LeCun, B. Boser, J. Denker, D. Henderson, R. Howard, W. Hubbard and L. Jackel, in an article entitled "Handwritten Digit Recognition with a Backpropagation Neural Network", which appeared in Advances in Neural Infonnation Processing Systems 2, pp. 396-404, D. Touretzky, ed., Morgan Kaufmann, San Mateo, Calif., 1990.

With reference to FIG. 5, there is shown a prior-art convolutional neural network suitable for recognizing handwritten characters. The convolutional neural network consists of a set of layers, each of which contains one or more planes. Approximately centered and normalized images enter at an input layer. Each unit in a particular plane receives input from a small neighborhood located in the planes of a previous layer. The weights forming the receptive field for a plane are forced to be equal at all points in the plane. Each plane can be considered as a feature map which has a fixed feature detector that is convolved with a local window which is scanned over the planes in the previous layer. Multiple planes are usually used in each layer so that multiple features can be detected. These layers are called convolutional layers. Once a feature has been detected, its exact location is less important. Hence, the convolutional layers are typically followed by another layer which does a local averaging and subsampling operation (e.g. for a subsampling factor of 2: y.sub.ij =(x.sub.2i,2j +x.sub.2i+1,2j +x.sub.2i,2j+1 +x.sub.2i+1,2j+1)/4 where y.sub.ij is the output of a subsampling plane at position i, j and x.sub.ij is the output of the same plane in the previous layer). The network is then trained with a backpropagation gradient-descent procedure, the specifics of which are well known in the art.

The convolutional network used contains a number of layers excluding the input layer. A confidence measure can be calculated for each classification. One possible measure of confidence is y.sub.m (y.sub.m -y.sub.2m), where y.sub.m is the maximum output, and y.sub.2m is the second maximum output. For this example, the outputs are transformed using the softmax transformation, namely: ##EQU2## where u.sub.i are the original outputs, y.sub.i are the transformed outputs, and k is the number of outputs.

While the invention has been shown and described in detail in the context of a preferred embodiment, it will be apparent to those skilled in the art that variations and modifications are possible without departing from the broad principles and spirit of the invention which should be limited solely by the scope of the claims appended hereto.