Original subtitles

1

Hello welcome back to the course on computer vision in today's tutorial we're going to talk about adaptive

2

boosting or other boost.

3

So previously we left off when we discussed how the algorithm uses input data or images to find which

4

features are important to recognizing faces.

5

So it uses the face images to understand which features are common among faces and it keeps those.

6

And then it uses the nonfatal images to understand out of the ones that are the features that it's kept

7

which features give it high rates of false positives.

8

And then it discards those features and makes them less important and focus on the features that are

9

present and faces and faces only that do not come up very commonly in other types of objects or the

10

pictures.

11

And so that's basically how the algorithm is trained.

12

And then we have these different features and there are thresholds at which they are considered to be

13

present in an image and so that sounds like the end of the story sounds like.

14

Ok cool.

15

We've identified the features we've identified thresholds all we have to do when a new image which is

16

going to watch is going to look at the features that we've identified check if their present check the

17

thresholds are met.

18

And we're going to know if it's a face while everything is not that simple.

19

The reason for this hurdle is that even in a 24 by 24 pixel image the number of features is huge the

20

number of features actually is over a hundred and eighty thousand possible features that can fit into

21

this image.

22

Sounds it sounds unbelievable because the image is so small it's only 24 pixels but it is true.

23

So the the reason for that is that these features as we discussed there are scalable.

24

So not only are we looking at these features on all their different positions in this image.

25

We're actually looking at all of the variations of each one of these features.

26

For instance this feature looks like for example it looks like there's one 2 pixels here and 1 2 pixels

27

here.

28

So you need to look through this image and try all all possible positions of this feature or very likely

29

like that and then all possible positions here here all different positions here.

30

And that's that's the start.

31

But now you need to also extend that as to be like one to three pixels three pixels here and three pixels

32

here and again you have to try out all possible positions for that feature.

33

Next you might make it like four pixels high.

34

Again you have to try it out all the positions the next you might make it for pixels high and then two

35

pixels wide so that one.

36

One two three four one two three four here and one two three four one two three four here and you need

37

to try that out as well.

38

And then once and then you keep doing that you keep expanding making it wider and so on and all the

39

possible widths and heights of this feature.

40

And then once you've run out of options for that you need to move on to the next one and the next or

41

next on THE NEXT ONE.

42

And so in a 24 by 24 pixel image these base features they all possible variations of them and their

43

different positions.

44

They add up to over a hundred and eighty thousand possible options that we would have to explore.

45

And that is a huge number.

46

So and it poses two concerns.

47

First of all during the training that would be very hard because you know not only have to check 180000

48

features for one image you need to check hundred eighty thousand features for all the images in the

49

training data which is nine thousand eight hundred thirty two faces in the original Old Jones paper

50

plus the huge number you know thousands and tens of thousands of images of known faces so you'd have

51

to check that across all those images so training becomes quite long becomes like a nightmare.

52

And the second thing is that even during your application so when you're detecting you're in if you've

53

somehow managed to train those all those features now when you're detecting the faces you have to check

54

180000 every single time.

55

And that is practically impossible to do in real time.

56

Take a lot of computation to do that for every single frame or every single image.

57

So this is where adaptive boosting comes in to help solve this problem.

58

So we've got we're going to take our features and we're going to put them together into a classifier

59

which will look like this so here on the left we've got the classifier f f of x and then here f one

60

of two and three are the features and Alpha 1 2 and 3 are the way to those features so we'll just add

61

some features here.

62

For instance there's a feature so that feature could be that's one that's commonly talked about the

63

bridge of the nose of the nose is usually lighter than on the left on the right.

64

So it's it's a feature that can help detect faces and this is the feature that the eyes are commonly

65

darker than the area under the eyes.

66

And so just even these two features will get as I say.

67

So that's those two features and then maybe there's another feature and so on.

68

So we've got our features aligned and that and it keeps going like that.

69

And each one of these features is called a weak classifier on its own.

70

He doesn't get a very high rate of success so as long as it gets over 50 percent that's already good.

71

So for instance maybe this bridge of the nose if you just used that feature on its own maybe gets a

72

60 percent success rate or a road or 65 percent success rate out of the images.

73

And then this image that or this classifier or this part on the left the effort the F couple of X that's

74

called a strong cost classified.

75

And the way it works is that when you have one classifier by itself it's not as good.

76

It maybe has a 60 percent success rate.

77

When you have two week classifiers together even though this one might also be only like 60 or something

78

percent or 55 percent.

79

But together all of a sudden they're much stronger.

80

And then as you keep adding they get stronger and stronger and stronger so you don't actually need.

81

You don't need all hundred and eighty thousand of them.

82

You might just need a couple of thousand to get a really really good result very strong classified.

83

And this is called an ensemble method this is called ensemble because you are leveraging the power of

84

the crowd as they call it.

85

So it's like the power of one is not as strong.

86

But when you put lots of we classifiers together they become a strong classifier and that is what I

87

was going to say that even just these two features the bridge of the nose and the eyes and the area

88

under the eyes.

89

It's the exact numbers in the village on paper but I think they said something like it gave them an

90

80 percent accuracy just those two features together or really made it so much more powerful.

91

Not it wasn't close to 90 or a hundred but it was already much better than each one of those on their

92

own.

93

And so as you can imagine by adding more and more and more you can get better and better better results.

94

So the question is now how do we find these right features how do we add the right ones.

95

So the most important ones are want to have the most important ones at the front.

96

And then.

97

So then because our of the 180 thousand then the ones at the end you don't even need to worry about

98

them after a certain point.

99

So how do we find the best ones and this is where adaptive boosting comes into play.

100

We won't go into the mathematics behind the algorithm we'll just go into the intuition.

101

So let's say you have 10 pictures you have five faces and five known faces.

102

And during the training process you apply.

103

You want to identify the like the best feature.

104

See I don't you want to identify how to build that strong classifier So you identify a feature that

105

is important.

106

And for instance the bridge of the nose feature and there you you apply it to your images.

107

And so you get a result for for instance it says identify that these three are indeed faces.

108

That's great.

109

And then it's identified out of the ones on the right.

110

It's identified that these three are not.

111

And hasn't found that feature in those images.

112

So for the for the algorithm those are not faces that's also good but then it does have some error.

113

So it's got some these false negatives.

114

Right so it's it's a Negat saying it's a negative but it's actually false.

115

It's not so correct.

116

These got two false negatives that says these are not faces when they are actually faces so didn't find

117

the feature on these on these two pictures.

118

But these are actually faces.

119

And then it's got two false positives.

120

It's identified these as faces even though they're not faces so what adaptive boosting does is it says

121

ok cool.

122

So we we like this feature because and the way we found it was perhaps that it is present on a huge

123

number of images it's the one that comes up most commonly and through our like empirical training we've

124

identified that yes this is a good picture but now what adaptive boosting will do is.

125

OK I need to compliment like I might have a lot of very good features I might have this feature is good

126

then another feature is good and so on.

127

So but our idea is to go back here so the point of adaptive boosting is that we don't want to just combine

128

the strongest features or because they might they might actually be leveraging off very similar things

129

or that might not be the best approach the best approach that we want to take this is the important

130

part is we want to take a strong feature but then we want to complement it with something that will

131

help you know help fix where this feature is strong.

132

That's good but where it's weak where it's making mistakes.

133

This will help complement that area and will help improve the performance in those areas which are falling

134

behind in this feature by itself.

135

And then this feature will be used to complement these two.

136

And we're they're falling behind.

137

And so each next one we're not just taking the strongest features we can find we're staying a strong

138

feature or the strongest and then we take in the one that best complements this one and then we're taking

139

the next one which best complements these two and the next on and so on.

140

So basically instead of just taking the strongest all the time we're constructing the strongest classifier

141

to resulting classify that we can rather than.

142

And so basically by leveraging the strengths of this one and then fixing up its weaknesses with this

143

one and then fixing up their weaknesses with this and so on so we covered.

144

That's very kind of like a strategic approach.

145

And so here again we've got these are this is all good but then we've got these two false negative false

146

negatives and false positives.

147

And so what adaptive boosting our will do is in the next round it will now look for something that complements

148

this feature that we found and how we'll do it.

149

What I'll say is it will give more weight to where the errors were made.

150

Ill say Okay so now I'm going to let's go let's go back.

151

Although explain this or so it's decreased the sizes.

152

This is just to just to symbolize what is going on so we've decreased the size of these images increase

153

the sizes of these zones highlighted in blue and decreased the size of these on increase the size of

154

these ones so you can see again if I go back.

155

So there you go.

156

So it's increased the sizes of these ones saying that it's not actually increasing the size of the image

157

which is doing it here on the PowerPoint just so that it is clear.

158

It's like it's easier to follow along but what it's doing is just increasing the weight the importance

159

of these images for the next for the next horror like feature one is going to be looking at this whole

160

system is going to now is going to know that the importance of these images is higher and it's going

161

to find a feature that treats them the best that helps I classify them properly.

162

And that's what we do.

163

That's how it accounts for that is how it implements that notion where we want to fix the problems of

164

the first class fire the first feature that we had so.

165

So now if we add a new one it finds the next one that best works with these images that predominantly

166

classify these images properly and find this one.

167

And so as you can see this now it applies to classify these five images correctly.

168

Unfortunately classify that or an incorrectly so that's a false negative.

169

And then it's classified these images correctly and then it's classified.

170

This one still incorrectly it's a false positive.

171

So maybe it was not possible to find a classifier that would classify these two very well so what the

172

algorithm did is it found one that classifies these four including this one very well.

173

And now we're going to have to fix find a new classifier that fixes these errors.

174

And that's what will happen next.

175

Next we would focus on these two.

176

So everything will become smaller and would focus on these two as predominantly the ones that we need

177

to fix in order to create that very strong overall classifier.

178

And and this would keep going.

179

And in the end the goal is to create a classifier that classifies all of these correctly and classifies

180

all of these correctly as well.

181

These faces spaces these are known faces.

182

So of course it's not never going to be ideal.

183

But the point is to keep building this strong classifier through these weak classifiers just keep building

184

it and minimizing the error rate until you get to a satisfactory level until you get to a very high

185

percentage of correct classifications like 99 point something percent.

186

And at that point you don't need the hundred and eighty thousand You just need that first couple of

187

thousand that or hundreds however many you can get to.

188

You mean you'll need to get to that good satisfactory conversion rate and then that's it.

189

And that's all you need.

190

And then you don't classify as really.

191

And that's a first step to reducing the number of the computation expense of finding find these images.

192

That's the first step is the added boost in what we discussed today.

193

And then the next step is going to be the cascading.

194

And once you combine them together you'll see that it actually improves the efficiency substantially.

195

So there you go that's how the Arab Boosler adaptive boosting algorithm works.

196

If you'd like to read a bit more about it there is a paper by Gene you and Paul Viola.

197

It's called boosting image retrieval.

198

And this paper inspired some of the work in the violin Jones paper which we were talking about at the

199

start.

200

So hope you enjoyed Sterle 40 next 14.

201

And until then enjoy computer vision.