Deep Learning Part7: Sliding Window.
Classic Sliding Window, Convolutional Solution, Intersection over Union (IoU) and Non-Max Suppression (NMS) and beyond.
Introduction.
In the previous blog, we broke down the fundamental shift from simple image classification to advanced object localization and landmark detection, exploring how NNs are trained to understand exactly where things are in a visual scene.
We distinguished between three core concepts in computer vision Image Classification, Classification + Localization and Object Detection.
In this blog, we are going to break down exactly how machines transition from basic image guessing to precise object localization. But we aren’t just stopping at the basics. We will explore:
- The Classic Sliding Window: How it works and why its massive computational cost will break your code if left unchecked.
- The Convolutional Solution: How to smartly convert FC layers into Convolutional layers to run sliding windows across an entire image simultaneously.
- Post-Processing Superpowers: How Intersection over Union (IoU) and Non-Max Suppression (NMS) clean up messy, overlapping predictions.
- The Multi-Object Dilemma: How Anchor Boxes allow a single grid cell to detect multiple overlapping objects at the same time.
Sliding Window Algorithm.
Imagine you are looking at a crowded street photograph. In a fraction of a second, your brain doesn’t just register “cars and people” — it instantly pinpoints where every single vehicle is, tracks the pedestrians on the sidewalk, and spots the traffic light changing color.
For a computer, however, this is a massive evolutionary leap. While teaching a CNN to look at an entire image and say “this is a car” (image classification) is relatively straightforward, teaching it to draw a perfect bounding box around that car (object detection) is a completely different ballgame.
How do we bridge that gap? It all starts with a deceptively simple concept: the Sliding Window Technique.
Say, we want to build a car detection algorithm.
First, we need a labeled training set (X, Y) with examples of cars and some other pictures that doesn’t car. Then, we can train a Convnet that gets an image as an input, and outputs a car or not (binary classification).
Once we’ve trained up this Convnet, we can use it in sliding windows detection by picking a “certain window size”, and input it into a Convnet.
what we do is
- Taking this little red square, and feed it into the Convnet to make a prediction. Presumably, ConvNet will say “it does not contain a car”.
- Shifting a little bit over, and input a 2nd image (2nd region) to the Convnet, and then a 3rd image (3rd region)
- And so on across every position and it classify 0 or 1.
To summarize:
- We basically go through every region of some stride of our entire image and pass lots of little crafted images into the ConvNet.
- We’d repeat this but using a larger window size and then a more large window (as we can see in the following image).
Disadvantages of sliding window detection and how to overcome them.
There’s a huge disadvantage of sliding window which is “The Computational cost”, because of cropping out so many square regions and running each of them independently through a convnet.
Why not to use larger stride?!
If we use the very course stride, that will reduce the number of windows, right? But that coarser granularity will hurt performance.
Whereas if we use a very fine granularity (very small stride), then the huge number of these little regions we’re passing through the convnet means that there’s a “very high computational cost”.
How to avoid this problem?!
Fortunately, this problem of computational cost has a pretty good solution. In particular the sliding windows object detector can be implemented convolutional (much more efficiently).
Convolutional operation of sliding windows
It’s a method used to detect objects in an image by applying a CNN on sliding windows of the image.
Imagine you are searching for a specific object in a room with many different items. Instead of looking at the entire room at once, you divide it into smaller sections and scan each section to find the object you are looking for. This is similar to how a convolutional implementation of sliding windows object detection works, where the image is divided into smaller windows and analyzed individually.
First, we need to know “how to turn FC layers in our NN into Conv layers?!”
Suppose we run 16 of (5 by 5 by 3) filter over an (14 by 14 by 3) input (just for illustration), and we apply (2 by 2) Max pooling layer to reduce the size of a volume to (5 by 5 by 16). Then, 2 FC layers, with 400 units for each. Then a NN finally outputs Y using a softmax unit.
How to turn FC layers into convolutional layers?
The convnet is the same as before for the 1st few layers. One way of implementing the 1st FC layer, is to implement 400 of (5 by 5by 16) filters (as the filter looks across all 16 channels), then the output dimension is going to be (1 by 1 by 400). Rather than viewing these 400 as just a set of nodes (units), we’re going to view this as a (1 by 1 by 400) volume and mathematically this is the same as a FC layer. Because each of these 400 nodes has an (5 by 5 by 16) filter, so each of those 400 values is some arbitrary linear function of these (5by5by 16) activations from the previous layer.
Next, run 400 of (1 by 1) filters then the next layer will again be (1 by 1by 400), it gives us this next FC layer. And finally we’re going to have another 1 by 1 filter followed by a softmax activation so as to give a 1 by 1by 4 volume to take the place of these 4 numbers that the network was outputting.
A convolutional implementation of sliding windows object detection
Let’s say that our sliding windows convnet inputs (14 by 14 by 3). As before we’ve a NN as follows that eventually outputs a (1 by 1 by 4) volume which is the output of our softmax unit.
Our convnet inputs (14 by 14 by 3) images but our test set image is (16 by 16 by 3). So, we’ll add that yellow stripe to the border of this image.
In the original sliding window algorithm, we might input the blue region into a convnet once to generate a classification.
Then slide it down a bit (stride= 2), then slide that to the right to input this green rectangle into the convnet and return the whole convnet and get another label (0 or 1)
run it one more time, input this orange region into the convnet and to get another label and then do the 4th and final time.
It turns out a lot of this computation done by these 4 convnets is highly duplicated, so what the convolutional implementation of sliding windows does is it allows these 4 forward passes of the convnet to share a lot of computation.
We can take the convent and just run it same parameters, the same 16 of (5by 5) filters and run it to have (12 by 12 by 16) output volume, and then do the max pool same as before, now we have a (6 by 6 by 16), run through our same 400 5by5 filters to get (2 by 2 by 400) volume.
Now instead of a (1 by 1by 400), we’ve instead a (2 by 2 by 400) volume. Run it through our 1by1 filter and it gives us another 2by2by 400 instead of 1by1by400 , we will do that one more time and now we have a 2by2by4 output volume instead of 1by1by4 . It turns out that this blue 1by1by4 subset gives us the result of running in the upper left-hand corner 14by 14 image, this upper right 1by1by4 volume gives us the upper right result, the lower left gives us the results of implementing the content on the lower left 14by 14 region, and the lower right 1by1by4 volume gives us the same result as running the convnet on the lower right 14by 14 region.
Get AI & Data Science 604’s stories in your inbox
Join Medium for free to get updates from this writer.
Let’s go through a bigger example. Say, we want to run sliding windows on a (28 by 28 by 3) image. It turns out if we run for crop the same way, then we end up with an (8 by 8 by 4) output and this corresponds to running sliding windows with that (14 by 14) region, and that corresponds to running sliding windows first on that region does, giving us the output corresponding on the upper left-hand corner, then using stride of 2 to shift one window over and so on.
There’re 8 positions, so that gives us this first row. Then as we go down the image that gives us all of these (8 by 8 by 4) outputs. And because of the max pooling of 2 that this corresponds to running our NN with a stride of 2 on the original image.
To recap, to implement sliding windows, previously what we do is we drop out a region, let’s say this is on (14 by 14), and run that to our convent and do that for the next region over, then do that for the next 14by 14 region, then the next one, then the next one, the next one, the next one and so on until hopefully that one recognizes the car. But now instead of doing it sequentially, with this convolutional implementation that we saw in the previous slide, we can implement the entire image of maybe 28by28 and convolutionally make all the predictions at the same time by one for pass through this big convnet in hope it recognize the position of the car.
Intersection over Union (IOU)
How do we know if our object detection algorithm is working well?
Doing the object detection task, our expectation is to localize the object in the best possible way.
But there’re 2 bounding boxes — The ground truth (the red one) and the purple one which is the output of our algorithm.
We can see that they don’t overlap perfectly, so we need to measure “how bad/good is the actual outcome”. To do that, we’ll compute IOU.
IoU computes the size of the intersection and divides it by the size of the union to evaluate whether or not our object localization algorithm is accurate or not. This is also a way of measuring how similar the 2 boxes are to each other.
By convention the bounding box is correct if the IOU > 0.5. If the bounding box we got and the ground truth bounding boxes overlapped perfectly, the IoU would be 1 because the intersection would be equal to the union. In general as long as IoU >= 0.5 then the obtained answer is rather decent.
0.5 is used as a threshold to determine whether the predicted bounding box is correct or not.
This is just a convention used in practice. In case that we want to be more strict, we can judge an answer as correct only if the IoU >= 0.6 or some larger number.
The higher the IoU, the more accurate the bounding box is.
Non-Max Suppression
non-max suppression allows us to overcome “multiple detections” of the same object in an image.
Each of the 2 cars has one midpoint. So, it should be assigned to just one bounding box. Which actually predicts that there’s a car in the picture.
In practice, we’re running an object classification and localization algorithm for every one of these grid cells, so it’s quite possible that different cells might think that the center of a car is in many different cells.
Non-max suppression cleans up these multiple bounding boxes.
How Non-Max suppression works.
What the Non-Max suppression does, is it bends together these detections so that we end up with just one detection per car.
Since we’re running the image classification and localization algorithm on every grid cell, it is possible that many of them will be with a large probability p_c, that there is an object in that cell. When we run the algorithm we would end up with multiple detections of each object.
More specifically, this algorithm will first search for the probability associated with each of these detections (looks at p_c values), and then it takes the largest one.
In the picture above, there’s a rectangle associated with 0.9 (the right car), this means that our algorithm has detected a car there. After this, the Non-Max suppression looks at other rectangles that are close to the 1st one and the ones with the highest overlap with this one (highest IoU) will be suppressed.
To clarify, there’re 2 rectangles with the IoU 0.6 and the 0.7 are going to be suppressed.
Similarly, the same procedure can be applied for the car on the left, we go through the remaining rectangles and find the one with the highest probability (the box with the value p_{c} =0.8).
Next, a task of Non-Max suppression is to discard the remaining detections having high IoU with this cell. In this case, we’ve 2 bounding boxes with lower p_c that recognized the car on the left (2 red rectangles in the left) and because of having big IoU, both of them will be discarded.
Applying the Non-Max suppression means that we’re going to output our maximal classifications probabilities and suppress the other ones (the other detections of the same object) with lower values.
That’s why we use the name non-Max suppression.
If there’re still any remaining bounding boxes haven’t been discarded yet.
- We’re going to repeat this process with the highest p_c.
- Next, we’ll discard any remaining box with high overlap ( IoU ) with the box that we’ve just outputted in the previous step.
- Keep doing this while there’re still any no processed remaining boxes till we’ve taken each of the boxes and either output it as a prediction, or discarded it.
In case that we want to detect more objects (e.g., pedestrians, cars, & motorcycles) the output vector will have 3 p_c components. It has been shown in practice that we can run Non-Max suppression 3 times independently, one for every output class.
The Non-Max suppression obtains rather decent results. However, to complete the idea, we need to introduce one additional idea. It is the idea of anchor boxes.
Anchor Boxes
One scenario that we may encounter is that several objects of interest are present in the same grid cell. In this case, we can use the idea of anchor boxes to solve this problem.
The midpoints of both objects ( car & person) are almost in the same place within the same grid cell. If we use the previously developed ideas, our output vector (Y) will have the following structure:
note for me: write the formula here.
Obvious challenge is that with this vector we cannot detect all 3 desired classes (pedestrians, cars & motorcycles).So, we can’t have 2 detections for a single cell and we’ve to choose only one.
The main idea of anchor boxes is to predefine 2 different anchor box shapes. In general, we might use even more anchor boxes for more objects to detect.
As we can see in the above picture, we defined anchor box1 and anchor box2. Every anchor box is defined with the following values: [p_c, b_x, b_y, b_h, b_w, c_1, c_2, c_3].
Obviously, the shape of the pedestrian is more similar to anchor box1 and the shape of a car is more similar to the other.
Previously, before using anchor boxes, we defined a grid for each training image, and we assigned an object to the grid cell where the center of a grid is. So, the output was (3 by 3 by 8) dimensional because of using the (3by3) grid and in each grid cell has the values: p_c, b_x, b_y, b_h, b_w, c_1, c_2, c_3.
How do we encode the objects in the target label?
Previously, each object in the training image is assigned to a grid cell that contains that object’s midpoint. However, now with two anchor boxes, each object is assigned to grid cell that contains object’s midpoint and anchor box for the grid cell with highest Intersection over Union ( IoU).
Now, the output y is going to be (3by 3 by 16) or (3by 3 by 2 by 8) because we use now 2 anchor boxes and y is 8 dimensional.
Let’s go through a concrete example. For this grid cell let’s specify what is y.
Looking at this image, we see the pedestrian is more similar to the shape of Anchor box 1, so we will assign the anchor box 1 to the pedestrian. Also looking at the shape of the car, we would assign it to anchor box 2. If a car was actually found in the image, both output c_1 and c_3 would be 0 and c_2 would be 1.
Note that this algorithm will not work properly in 2 different cases:
- When we have 2 Anchor boxes, and 3 objects in the same grid cell.
- Also, 2 objects in the same grid cell, and both objects have the same Anchor box.
