Of all of the applications where computer vision is used, face detection presents an extremely difficult challenge. For example, in images acquired by surveillance cameras, the lighting of a scene is usually poor and uncontrollable, and the cameras are of low quality and usually distant from potentially important parts of the scene. Significant events are unpredictable. Often, a significant event is people entering a scene. People are typically identified by their faces. The location and orientation of the faces in the scene are usually not controlled. In other words, the images to be analyzed are substantially unconstrained.
In applications where a large number of images are to be analyzed, or the analysis needs to be performed in real-time, the number of images that actually include faces is usually very small. Moreover, in most images that do include a face, the amount of the image that is a face is also very small. Therefore, it is desirable to rapidly eliminate images or portions of images that do not include a face, thus more processing can be devoted to portions of images that potentially contain a face.
Face detection has a long and rich history. Some techniques use neural network systems, see Rowley et al., “Neural network-based face detection,” IEEE Patt. Anal. Mach. Intell., Vol. 20, pages 22–38, 1998. Others use Bayesian statistical models, see Schneiderman et al., “A statistical method for 3D object detection applied to faces and cars,” Computer Vision and Pattern Recognition, 2000. While neural network systems are fast and work well, Bayesian systems have better detection rates at the expense of longer processing time.
U.S. Pat. No. 5,710,833, “Detection, recognition and coding of complex objects using probabilistic eigenspace analysis” issued to Moghaddam, et al. on Jan. 20, 1998, describes a system for detecting instances of a selected object or object feature, e.g., faces, in a digitally represented scene. Their method utilizes analysis of probability densities to determine whether an input image, or portion thereof, represents such an instance.
U.S. Pat. No. 6,337,927, “Approximated invariant method for pattern detection” issued to Elad et al. on Jan. 8, 2002, describes a system and method for classifying input feature vectors into one of two classes, a target class (faces) and a non-target class (non-faces). The system utilizes iterative rejection stages to first label the input vectors that belong in the non-target class in order to identify the remaining non-labeled input vectors as belonging in the target class. The operation of their system is divided into an off-line (training) procedure and an online (actual classification) procedure.
During the off-line procedure, projection vectors and their corresponding threshold values that will be used during the on-line procedure are computed using a training set of sample non-targets and sample targets. Each projection vector facilitates identification of a large portion of the sample non-targets as belonging in the non-target class for a given set of sample targets and sample non-targets.
During the on-line procedure, an input vector is successively projected onto each computed projection vector and compared with a pair of corresponding threshold values to determine whether the input vector is a non-target. If the input vector is not determined to be a non-target during the successive projection and thresholding, the input vector is classified as a target.
As a disadvantage, the features used by their method are limited to linear projections and upper and lower thresholds. Thus, outcomes of early features do not effect the outcomes of later tests. In other words, their tests can be reordered with no effect on the final result. In addition, because the classifier is a conjunction of linear projections followed by a threshold, the resulting classification function is limited to a convex region in the input space, which is a strong limitation that makes their system a weak classifier.
A new framework for feature detection is described by Viola et al., in “Rapid Object Detection using a Boosted Cascade of Simple Features,” Proceedings IEEE Conf. on Computer Vision and Pattern Recognition, 2001. They present three new insights: a set of image features which are both extremely efficient and effective for face analysis, a feature selection process based on Adaboost, and a cascaded architecture for learning and detection. Adaboost provides an effective learning algorithm and strong bounds on generalized performance, see Freund et al., “A decision-theoretic generalization of on-line learning and an application to boosting,” Computational Learning Theory, Eurocolt '95, pages 23–37. Springer-Verlag, 1995, Schapire et al., “Boosting the margin: A new explanation for the effectiveness of voting methods,” Proceedings of the Fourteenth International Conference on Machine Learning, 1997, Tieu et al., “Boosting image retrieval,” International Conference on Computer Vision, 2000.
However, there are several problems with their cascaded approach. The simplest is that the cascade allows only for rejection thresholds, and does not have acceptance thresholds. This degrades performance when the distribution of acceptable and rejected examples are substantially equal.
Another disadvantage of their method is that later stages of the cascade ignore detailed information that was available during earlier stages of the cascade. If the early cascade stages accept features only marginally close to the threshold, then this useful information plays no role in later decisions to reject or accept the feature. For example, it is possible for multiple stages to accept a given patch because it is significantly above the rejection threshold, and then subsequently reject that patch as soon as it falls below the rejection threshold in later stages. In this case it is often better to accept the given patch.
Another disadvantage is their mechanism for setting the rejection thresholds. Their rejection thresholds are set for each cascade stage starting from the first stage. For any given task, their goal is to detect most of the objects, though it is impossible to detect all objects of a particular class. In the case of face detection, perhaps 90% to 95% of the faces are detected. The rejection threshold is set so that a very high percentage of the examples are detected. Therefore, in the early stages, one must be very conservative and not discard a potentially correct patch. For early stages in the cascade, 99% or more of the objects must be detected in order to ensure that valuable patches are not discarded.
Their process does not distinguish example patches that are easy to classify, and are eventually classified correctly, and those example patches, which are very difficult to classify and are eventually misclassified. If one could determine which example patches would eventually be misclassified, after the entire cascade, then those example patches could be eliminated early with no loss to the accuracy of the overall process. Because the rejection threshold setting process starts with the early stages of the cascade, these “difficult” examples cannot be identified so the rejection threshold is set for all positive examples. This results in rejection thresholds which are lower and less effective in reducing processing time.
Therefore, there is a need for an object detection system that improves upon the prior art.