Image analysis – Learning systems – Trainable classifiers or pattern recognizers
Reexamination Certificate
2000-11-22
2004-10-12
Ahmed, Samir (Department: 2623)
Image analysis
Learning systems
Trainable classifiers or pattern recognizers
C706S045000
Reexamination Certificate
active
06804391
ABSTRACT:
TECHNICAL FIELD
This invention relates to pattern detection methods and systems, and, more particularly, to face detection methods and systems.
BACKGROUND
In recent years, problems associated with general visual pattern recognition or object recognition/classification have received an increasing amount of attention in the computer vision community. In many cases the only feasible approach is to represent a class of patterns/objects (e.g. faces) by a set of learned examples. The complexity of some of the class of objects/patterns is often such that an extremely large set of examples is needed in order to learn all the potential variations (facial expression/pose etc). Additionally, typically the data points associated with the examples belong to some high-dimensional space. Thus, there has been and continues to be a need for pattern recognition techniques that can handle large data sets in high dimensional spaces.
One particular type of visual pattern is a face. Typically, face detection represents a very computationally intensive task that involves testing a digitized image for the location of a face by placing an observation window at all scales, in all positions, and at all orientations on the image, and ascertaining whether a face is present within the observation window. This process, however, can be quite slow. Exemplary face detection techniques are described in the following references, to which the reader is referred for additional material: Osuna et al.,
Training support vector machines: An application to face detection
, Proc. Computer Vision and Pattern Recognition '97, pages 130-136, 1997; and Rowley et al.,
Neural network
-
based face detection
, Proc. IEEE Conf. On Computer Vision and Pattern Recognition, pages 203-207, IEEE, 1996.
Nonlinear Support Vector Machines (SVMs) are known to lead to excellent classification accuracies on a wide range of tasks, including face detection. The following references describe non-linear SVMs and their various characteristics: Schölkopf et al.,
Advances in Kernel Methods—Support Vector Learning
, MIT Press, Cambridge, Mass., 1999; and Vapnik,
The Nature of Statistical Learning Theory Statistical Learning Theory
, Springer, N.Y. 1995.
Nonlinear SVMs are, however, usually slower classifiers than neural networks. The reason for this is that their run-time complexity is proportional to the number of support vectors (SVs), i.e. to the number of training examples that the SVM algorithm utilizes in the expansion of the decision function. While it is possible to construct classification problems, even in high-dimensional spaces, where the decision surface can be described by two SVs only, it is normally the case that the set of SVs forms a substantial subset of the whole training set.
There has been a fair amount of research on methods for reducing the run-time complexity of SVMs. Exemplary articles includes the following: Burges, Simplified support vector decision rules, Proceedings, 13
th
Intl. Conf. On Machine Learning, pages 71-77, San Mateo, Calif., 1996; and Schölkopf et al.,
Input space vs. feature space in kernel-based methods
, IEEE Transactions on Neural Networks, 10(5):1000-1017, 1999. Yet, the run time complexity of SVMs continues to be an issue in their efficient employment for pattern recognition or classification.
Accordingly, this invention arose out of concerns associated with improving the systems and methods that are utilized for pattern recognition or classification. Particular concerns giving rise to the invention were those associated with improving the efficiencies with which the evaluation of support vector expansions is utilized for pattern classification, particularly where the patterns comprise faces.
SUMMARY
Systems and methods for object or pattern detection that use a nonlinear support vector (SV) machine are described. In the illustrated and described embodiment, objects or patterns comprising faces are detected. The decision surface (in the high dimensional data space) is approximated in terms of a reduced set of expansion vectors. In order to determine the presence of a face, the kernelized inner products of the reduced set vectors with the input pattern are sequentially evaluated and summed, such that if at any point the pattern can be rejected as not comprising a face, no more reduced set vectors are used. The sequential application of the reduced set vectors produces a substantial saving in computational time.
REFERENCES:
patent: 5649068 (1997-07-01), Boser et al.
patent: 5950146 (1999-09-01), Vapnik
patent: 6134344 (2000-10-01), Burges
patent: 6662170 (2003-12-01), Dom et al.
Osuna et al., “Training Support Vector Machines: an Application to Face Detection”, Proceedings of CVPR '97, Jun. 17-19, 1997, 8 pages.
Scholkopf et al., “Input Space Versus Feature Space in Kernel-Based Methods”, IEEE Transactions on Neural Networks, vol. 10, No. 5, Sep. 1999, pp. 1000-1017.
Burges, “Simplified Support Vector Decision Rules”, Bell Laboratories, Lucent Technologies, 7 pages.
Platt, “Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines”, Microsoft Research Technical Report, Apr. 21, 1998, 21 pages.
Rowley et al., “Neural Network-Based Face Detection”, IEEE 1996, pp. 203-208.
Rowley et al., “Neural Network-Based Face Detection”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, No. 1, Jan. 1998, pp. 23-38.
Sung, “Example-Based Learning for View-Based Human Face Detection”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, No. 1, Jan. 1998, pp. 39-51.
Blake Andrew
Romdhani Sami
Schoelkopf Bernhard
Torr Philip H. S.
Ahmed Samir
Lee & Hayes PLLC
Microsoft Corporation
LandOfFree
Pattern detection methods and systems, and face detection... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pattern detection methods and systems, and face detection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern detection methods and systems, and face detection... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3327552