I'd like to talk about face detection All right. So this is the idea or if you've got a picture with one face in it or many faces in it how do we find those faces and The standard approaches is "Ah, we'll just use deep learning" Now you can use deep learning to find faces But actually the approach that everyone uses isn't deep learning and it was developed in the early 2000s So back before deep learning did everything You kind of had to come up with these algorithms yourself right machine learning was still a thing. So people still use machine learning But they used them with handcrafted features and small neural networks and other kinds of classifiers that they tried to use to do these things Now the face detection was you know ongoing research at this time In 2002 Paul viola Michael Jones came up with this paper here called "Rapid object detection using a boosted cascade of simple features", and this is a very very good paper. It's been cited some 17,000 times And despite the fact that deep learning has kind of taken over everything. In face detection, this still performs absolutely fine, right It's incredibly quick and if you've got any kind of camera that does some kind of face detection It's going to be using something very similar to this, right? So what does it do? Let's talk about that. The problem is, right, There's a few problems with face detection one is that we don't know how big the face is going to be So it could be very big could be very small, and another is, you know, Maybe you've got a very high-resolution image. We want to be doing this lots and lots of times a second So what are we going to do to? Look over every every tiny bit of image lots and lots of times? Complicated, um, Machine learning, that says, you know, is this a face? is this not a face? There's a trade-off between speed and accuracy and false-positives and false-negatives. It's a total mess It's very difficult to find faces quickly, right? This is also considering it, you know, we have different ethnic groups young, old people, people who've got glasses on, things like this So all of this adds up to quite a difficult problem, and yet it's not a problem we worry about anymore because we can do it and we can do it because of these guys They came up with a classifier that uses very very simple features, one bit of an image subtracted from another bit of an image and On its own and that's not very good, but if you have thousands and thousands of those, all giving you a clue that maybe this is a face, you could start to come up with proper decision [offscreen] Is this looking for facial features then is it as simple as looking for a nose and an eye and etc? So no, not really, right. So deep learning kind of does that right? It takes it takes edges and other features and it combines them together into objects you know, in a hierarchy and then maybe it finds faces. What this is doing is making very quick decisions about What it is to be a face, so in for example, if we're just looking at a grayscale image Right, my eye is arguably slightly darker than my forehead, right? In terms of shadowing and the pupils darker and things like this So if you just do this bit of image minus this bit of image My eye is going to produce a different response from this blackboard, right, most of the time Now, if you do that on its own, that's not a very good classifier, right? It'll get quite a lot of the faces But it'll also find a load of other stuff as well where something happens to be darker than something else that happens all the time so the question is "can we produce a lot of these things all at once and make a decision that way?" They proposed these very very simple rectangular features Which are just one part of an image subtracted from another part of an image So there are a few types of these features. One of them is a two rectangle features So we have a block of image where we subtract one side from the other side Their approaches are machine learning-based approach Normally, what you would do in machine learning is you would extract -- You can't put the whole image in maybe there's five hundred faces in this image So we put in something we've calculated from the image some features and then we use all machine learning to try and classify bits of the image or the whole image or something like this. Their contribution was a very quick way to calculate these features and use them to make a face classification To say there is a face in this block of image or there isn't And the features they use a super simple, right? So they're just rectangular features like this So we've got two rectangles next to each other which, you know are some amount of pixels so maybe it's a It's nine pixels here and nine pixels here or just one pixel and one pixel or hundred pixels and a hundred pixels It's not really important. and we do one subtract the other right? So essentially we're looking for bits of an image where one bit is darker or brighter than another bit This is a two rectangle feature. It can also be oriented the other way so, you know like this We also have three rectangle features which are like this where you're doing sort of maybe the middle subtract the outside or vice versa And we have four rectangle feature which are going to be kind of finding diagonal sort of corner things So something like this Even if your image is small right you're going to have a lot of different possible features even of these four types So this four rectangle feature could just be one pixel each or each of these could be half the image it can scale You know or move and move around Brady : What determines that?
Mike : Um, so they do all of them, right? Or at least they look at all of them originally And they learn which ones are the most useful for finding a face this over a whole image of a face isn't hugely representative of what a face looks like right? No one's face. The corners are darker than the other two corners That doesn't make sense, right but maybe over their eye, maybe that makes more sense I don't know, that's the kind of the idea. So they have a training process at which was down Which of these features are useful, the other problem we've got is that on an image Calculating large groups of pixels and summing them up is quite a slow process So they come a really nifty idea called an integral image which makes this way way faster So let's imagine we have an image Right, and so think -- consider while we're talking about this that we want to kind of calculate these bits of image But minus some other bit of image, right? So let's imagine we have an image which is nice and small It's too small for me to write on but let's not worry about it Right and then let's draw in some pixel values. Sast forward. Look at the state of that. That's that's a total total shambles This is a rubbable-out pen, right? For goodness sake Right right okay okay so all right so Let's imagine this is our input image. We're trying to find a face in it Now I can't see one But obviously this could be a quite a lot bigger and we want to calculate let's say one of our two rectangle features So maybe we want to do these four pixels up in the top Minus the four pixels below it now that's only a few additions : 7 + 7 + 1 + 2 minus 8 + 3 + 1 + 2 But if you're doing this over large sections of image and thousands and thousands of times to try and find faces That's not gonna work So what Viola Jones came up with was this integral image where we pre-compute Some of this arithmetic for us, store it in an intermediate form, and then we can calculate rectangles minus of of rectangles really easily So we do one pass over the image, and every new pixel is the sum of all the pixels Above and to the left and it including it. right, so this will be something like this so 1 and 1 + 7 is 8 so this pixel is the sum of these two pixels and this pixel is going to be all these three So that's going to be 12... 14... 23 and now we fast forward while I do a bit of math in my head 8...17 maybe I did somebody's earlier, 24... On a computer this is much much faster The sum of all the pixels is 113. For example, the sum of this 4x4 block is 68 now The reason this is useful, bear with me here But if we want to work out what, let's say, the sum of this region is what we do is we take this one 113 we subtract this one, minus 64 Alright, and this one? minus 71 and that's taken off all of that and all of that and then we have to add this bit in because we've been Taken off twice so plus 40. All right, so that's four reads. Now funnily enough this is a 4 by 4 block So I've achieved nothing But if this was a huge huge image, I've saved a huge amount of time and the answer to this is 18 Which is 6 plus 6 plus 5 plus 1 So the assumption is that I'm not just going to be looking at these pictures one time to do this, right? There's lots of places a face could be I've got to look at lots of combinations of pixels and different regions So I'm going to be doing huge amounts of pixel addition and subtraction So let's calculate this integral image once and then use that as a base to do really quick Adding and subtracting of regions, right? and so I think for example a 4 rectangle region is going to take something like nine reads or something like that and a little bit addition. It's very simple All right. So now how do we turn this into a working face detector? Let's imagine We have a picture of a face, which is going to be one of my good drawings again Now in this particular algorithm, they look 24 by 24 pixel regions, but they can also scale up and down a little bit So let's imagine there's a face here which has, you know eyes, a nose and a mouth right and some hair Okay, good. Now as I mentioned earlier, there are probably some features that don't make a lot of sense on this So subtracting, for example, if I take my red pen Subtracting this half of image from this half. It's not going to represent most faces It may be when there's a lot of lighting on one side, but it's not very good at distinguishing Images that have faces in and images that don't have faces in So what they do, is they calculate all of the features, right for a 24 by 24 image They calculate all 180,000 possible combinations of 2, 3, and 4 rectangle features and they work out which one For a given data set of faces and not faces, which one best separates the positives from the negatives, right? So let's say you have 10,000 pictures of faces 10,000 pictures of background which one feature best says "this is a face, this is not a face"
Right, bearing in mind Nothing is going to get it completely right with just one feature So the first one it looks it turns out is something like this It's a two rectangle region, but works out a difference between the area of the eyes and the air for cheeks So it's saying if on a normal face your cheeks are generally brighter or darker than your eyes So what they do is they say, okay Well, let's start a classifier with just that feature right and see how good it is This is our first feature feature number one, and we have a pretty relaxed threshold so if there's anything plausible in this region we'll let it through right which is going to let through all of the faces and a bunch of other stuff as well that we Don't want right. So this is yes. That's okay, right? That's okay if it's a no then we immediately Fail that region of image right? So we've done one test which is as we know about four additions So we've said for this region of image if this passes will let it through to the next stage Right and we'll say okay it definitely could be a face It's not not-a-face. Does that make sense? Yeah, okay So let's do look at the next feature The next feature is this one So it's a three region feature and it measures the difference between the nose and the bridge and the eyes, right? which may or may not be darker or lighter. All right, so there's a difference there So this is feature number two, so I'm going to draw that in here number two And if that passes we go to the next feature, so this is a sort of binary, they call it "degenerate decision tree" Right, well because the decision tree is a binary tree. This is not really because you immediately stop here you don't go any further.
The argument is that Every time we calculate one of these features it takes a little bit of time The quicker we can say "no definitely not a face in there", the better. And the only time we ever need to look at all the features Or all of the good ones is when we think, "okay, that actually could be a face here" So we have less and less general, more and more specific features going forward right up to about the number I think it's about six thousand they end up using. All right, so we we say just the first one pass Yes, just a second one pass Yes, and we keep going until we get a fail and if we get all the way to the end and nothing fails that's a face, right and the beauty of this, is that For the vast majority of the image, there's no computation at all. We just take one look at it, first feature fails "Nah, not a face". They designed a really good way of adding and subtracting different regions of the image And then they trained a classifier like this to find the best features and the best order to apply those features which was a nice compromise between always detecting the faces that are there and false positives and speed right? And at the time, this was running on, I think to give you some idea of what the computational Technology was like in 2002 This was presented on a 700 megahertz Pentium 3 and ran at 15 frames a second which was totally unheard of back then. Face detection was the kind of offline, you know, it was okay at that time So this is a really, really cool algorithm and it's so effective that you still see it used in, you know, in your camera phone and in this camera and so on, when you just get a little bounding box around the face and this is still really useful because you might be doing deep learning on something like face recognition, face ID something like this But part of that process is firstly working out where the face is, and why reinvent the wheel when this technique works really really well You can't really get into the data center necessarily and take all the chips out that you've put in there So you probably will make the chips look like they're meant to be there like they're something else or hide them So the way a modern printed circuit board is constructed. It's a printed circuit board that's got several layers of fiberglass
