Welcome back to pattern recognition. So today we want to have the last video of our lecture

and we actually want to look into an application of Adaboost and this is going to be the Viola

Jones algorithm that was published in 2001.

So the Viola Jones algorithm is really famous because it solved the phase detection problem.

It's using integral images for the feature computation and it uses Adaboost for the

actual classification and then this is building a classifier cascade for the fast rejection of

non-phase regions. Various implementations are available for example in OpenCV the phase detector

sample is actually implementing Adaboost. So how do the features work? Well they are built

from a HAR basis functions. If you attended introduction to pattern recognition you will

know them already. Then you calculate them by subtracting essentially the sum of the

pixels in the white from the sum of the pixels in the gray rectangles and there are four different

kinds of features that are used left right top bottom then center with the sides and this kind

of checkerboard patch. Now in order to do that very quickly the set of features is really large.

So if you look at this you have more than 45,000 features for a 380 by 280 image. So the rectangle

features need to be computed very efficiently and this is done using integral images and the

integral image here indicated by I I is essentially returning the integral over the rectangle to the

top left. Now if you want to compute arbitrary integrals within the original image from the

integral image you can use the following trick. So we have four regions here A, B, C and D and we

have then values from the integral image. So the value at one is exactly the integral over A. The

value of two is the integral of A plus B the value at three is the integral over A plus C and the

value at four is the integral over A plus B plus C plus D. This essentially means that you can compute

the integral in D as four plus one minus two plus three. So you essentially subtract A here two times

this is why you need to add it back once in order to compute this integral of D very quickly. So you

can compute any rectangular integral in the original image just using the addition and

subtraction of four values from the integral image. Now they also apply boosting so the

classification functions are restricted to depend on a single feature only and then this way you

can essentially say that other boosts can be interpreted as an effective feature selection

algorithm. So the single rectangle feature is selected which best separates the observations

for each feature the weak learner then determines the optimal threshold classification function.

A weaker classifier then consists of a feature Xj and an optimal threshold theta j and a parity

Sj to indicate the direction of the inequality. So we have very simple classifiers here which is

essentially just evaluating the threshold and the parity and here X is being a sub window of an image.

So this is a very aggressive process to discard the vast majority of features and it allows you

to build such a boosting cascade and interestingly you can then have a look at the best features

selected here by other boosts and this is work by my colleague Christian Hacker and you see that

the one feature that is selected virtually always is a patch over the eyes and the nose and you just

subtract the two integral images and this is a very very good predictor already for faces and

then of course you need some additional classifications in order to really make sure

whether these are faces but this is the best feature that is selected by other boosts. So

that's very interesting that we also have this nice interpretation here. Now we built this

classifier cascade and this then means that we have to evaluate a different feature in every step

of this boosting process and as soon as we have a misclassification so it's not a face we just stop

following that particular position and this allows us to classify really really quickly. So you don't

want to evaluate the full other boost sequence on all sub windows of the image and you just abort

after you find a negative example. So this simple classifier is used to reject the majority of sub

windows and when you build this each stage is created again by other boost and the stage one

is essentially using the two features as shown before and detects 100% of the faces with a false

positive rate of around 40%. So then the procedure goes like this so you have all possible sub windows

and then you reject in the first classifier already quite a few of them then in the second

classifier you reject more sub windows and you follow this cascade over the different steps until