AdaBoost Face Detection Hamed Masnadi-Shirazi Department of Electrical and Computer Engineering University of California, San Diego La Jolla, California [email protected] Abstract Viola and Jones [1] introduced a new and effective face detection algorithm based on simple features trained by the AdaBoost Algorithm, Integral Images and Cascaded Feature sets. This paper attempts to replicate their results. The Feret Face data set is used as the training set. The AdaBoost Algorithm, simple feature set and Integral Images are briefly explained and implemented in our Matlab based program. A series of ten best features were identified out of a set of close to fifty thousand. These best features were used to produce probability of error plots. Finally our face detection Algorithm is implemented on a series or random Images taken from the internet. More than just ten best features are needed to have a face detector comparable to the two hundred best features of Viola and Jones [1] but the face detector still performs well and anyone can use our program included in the Appendix to implement this effective face detection algorithm and train as many best features as suited for their application.. 1. Introduction Face detection and recognition has become an increasingly researched area. The Viola and Jones [1] method for face detection is an especially successful method as it has a very low false positive rate, can detect faces in real time and yet is very flexible in the sense that it can be trained for different levels of computational complexity, speed and detection rate suitable for specific applications. What makes this algorithm even more attractive is the fact that it can be implemented with slight changes to detect many other objects as well. Using a set of two hundred best features, Viola and Jones [1] were able to produce a 95% diction rate and a 1 in 14084 false positive rate. They were also able to detect faces within a 380x280 image in less than 0.7 seconds. Such high performance makes this method one of the best face detection algorithms. As mentioned above the same algorithm can be applied to detecting other objects as well and Viola, Jones and Snow [4] have successfully used this method for detecting pedestrians. Considering the above, it is highly desirable to be able to implement this versatile method for anyone who might want to do research in this area. 1.1 Overview In This paper Section 2 will discuss the simple features and integral images. Section 3 will discuss the AdaBoost training. Section 4 will specifically discuss our program and the methods we used to implement this Algorithm. Section 5 will discuss our results. Appendix A will have a set of example runs of our program on images and Appendix B will have the complete listing of our Matlab program. 2. Features and Integral Images The first thing to keep in mind is that the Viola Jones [1] method is a feature based detection scheme. So a pool of features must be created and a scheme used to find the “good” features. “Good” features are features that best discriminate between faces and non-faces. Many different forms of feature pools can be created. A desirable feature pool would be one that is exhaustive, has feature forms that can describe the object and has features that can be applied to our images and computed efficiently. The rectangle features used have all the above conditions. An example of such features can be seen in Figure 1. Figure 1: Example rectangular features used in our program. (From left to right) feature numbers 1, 100, 1000, 15000, 25000, 49000. It should be mentioned that these features are 24x24 pixels. The image pixels that fall within this space and are under the black pixels are subtracted from the image pixels that are under the white feature pixels (or vice versa). The resulting number is considered the output of this feature applied to our image.2.1 Integral Images It might seem computationally expensive to find the output of each feature as described above, but using a clever method called the Integral Images; one can easily and effectively find the output. In this method a new image is created for each test image such that every new pixel is the sum of the pixels above and to the left of it. ii(x’,y’)= ∑<< ''),(yyxxyxi The same is done for each feature in our feature bank to the extent that each feature is represented only by a series of numbers that define how specific parts of the Integral Image should be added or subtracted to produce the feature output. This will be further explained in Section 4 when we introduce our specific program. Using this method it is no longer necessary to add or subtract individual pixels. The Image is scanned once and the Integral Image is found. After this stage to find the output of a feature applied to our image we just add and subtract a limited number of our Integral Image pixels. 3. Adaboost Training and Feature Selection Now that we have a set of features and an efficient way to compute the output of each feature, we describe how the best features are found. To realize the importance of this stage it should be mentioned that using 24x24 pixel features we produced an exhaustive set of 49,554 features. A method must be used that can reduce this feature set and give us the best features that discriminate the faces from non-faces and also complement each other. 3.1 Weak Classifiers Before we move on to explain the training algorithm the concept of a weak classifier should be explained. A training set of labeled faces and non-faces is prepared by scaling each image to a 24x24 image and normalizing it. For each feature a weak classifier is defined by applying the feature to the training set. A weighted histogram is produced and an optimal threshold that best separates the faces from non-faces is found. A parity is also found that describes weather the face outputs are above or below the threshold. So each weak classifier hj(x) has a feature fj, a threshold θj and a parity pj assigned to it. (Finding the threshold of each weak classifier is an optimization step and any optimization algorithm that minimizes the error of classification can be used.) In our implementation the output of our weak classifier is 1 if the image x is classified as a face and -1 if it is classified as a non-face. Mathematically this is equivalent to: hj(x)= ⎩⎨⎧←−Θ<←Otherwisepxfpjjjj1)(1 Figure 2: First three