An Explanation of Integral Images
Of Card Tricks
I love card tricks. They’re fun to learn, and fun to show. It’s interesting to see the creativity in the execution. Whether it’s sleight-of-hand or manipulating the audience’s attention, performers have to come up with a creative way to deceive the audience.
That being said, there are quite a few card tricks that don’t require misdirection, sleight-of-hand, or any kind of deception. They are built entirely on math. Whether it’s The Count or the Twenty-One Card trick, these self-working card tricks operate on mathematics and require no more skill than following a pattern.
If we were to try to make this analogous to data science and program engineering, this is both an optimization and a hack. It’s a way of performing a task (a card trick) while minimizing the resources taken up (time and practice).
It was this similarity that had me randomly associate card tricks with Integral Images, a work-around that allows for much faster processing of image recognition algorithms.
Of Integral Images
Let’s look at this matrix below.
Let’s pretend that this matrix that represents a 10 x 8 pixel image (really small, I know, but let’s just go with it). The numbers represent how bright the pixel is. Normally, this would not only be on a different scale, but we also would see a pattern instead of random numbers, but this is all for demonstration.
Now let’s say you wanted to find the sum of the values within the highlighted area. That’s 15 pixels to add up. While that’s not a lot, what if we found a way in which we only need to calculate the sum of 4 numbers no matter how many pixels are in the highlighted area? Enter the Integral Image!
Integral images are a matrixes whose values are the sums of corresponding areas of an original image. That’s a really confusing way to put it, so let’s make an integral image to gain some better understanding.
This table will become the integral image for our original image. We want to calculate the value for the blue cell. How do we do that? The value would be a sum, but the sum of what? Well, check out the image below:
We start by finding the corresponding pixel in the original image. Then, starting from the bottom right corner, we draw a vertical line upward and a horizontal line going to the left. The value for the cell in our integral image is the sum of all the numbers are above the horizontal line and to the left of the vertical line. Let’s go a head put this into our integral image.
This cell, then, represents the sum of all of the values within the blue shaded area above. Let’s try one more.
Now we want to find the value for this cell. So we find the corresponding pixel in the original image, draw a vertical line starting from the bottom right hand corner of the pixel and up to the top. Then draw the horizontal line, starting from the same place and go straight to the left. Shade in everything that is up and to the left of these borders and you get:
Nice! Now just calculate the sum of these values.
Awesome! Again, the values in that cell represents the sum of the values within their corresponding areas in the original image.
Now let’s look at the completed integral image.
The highlighted area represents the portion on the ORIGINAL image that we wanted to calculate the sum of. It’s only here as a guide to help us find the 4 magic numbers we need to make our trick work (Remember, we want to find the sum of the values inside the red box in the original image)
Let’s get started! First let’s select the bottom right cell that’s inside the highlighted area: 215.
Now, again, this number is the sum of values located in a specific area of the original image. What area of the original image does this cell correspond to?
That blue cell represents the sum of all of the numbers in the blue shaded area.
Take a second to look at it. Does the shaded region contain all of the numbers that we want to calculate the sum of?
Yes! But it also captures a lot of other numbers. So this area is too big! Sadly, the Integral Image can only “select” areas that are above and to the left of the bottom righthand corner. In order to isolate the values in the red box, we’re going to need to subtract the sum of the shaded area outside of it.
Let’s trim some of the excess. Look at the original image. To target the top two rows of the shaded area, what cell on the Integral Image represents this area?
If you guessed 80, you’re right! Let’s double check! Shade in the area of the original image that is above and to the left of the bottom-right corner of the corresponding pixel.
There we go! Those are the two rows that we want to remove! So our second number for our magical equation is 80!
Let’s look at what happens to the highlighted area when we subtract 80 from 215.
Nice! We trimmed a lot of the fat!
We still have some left and this is where it gets a little tricky. If we go to the Integral Image and find the cell that is directly left of the bottom left corner of our box, we’ll find the number 72. What area of the original image does this represent?
Do you see the problem? We’ve already subtracted the six values highlighted below!
Luckily, this isn’t much of a problem. We just need to add the sum of these values back! And what cell represents this area?
That’s right! 20 (or, the value in the cell that is up and to the left of the top left corner)! If we add this back, then the current total is the sum of the highlighted values below.
Perfect! Now the shaded area outside of the red box is the same as the one whose sum was 72. Where was that on the Integral Image, again?
Just to the left of the bottom left corner! Once we’ve subtracted this number, we’ll have cut all of the excess area and should only be left with the area in the red box in our original image. Let’s check!
Perfect! Let’s recap!
- To calculate the sum of this highlighted area we first looked at the Integral Image and found the cell that corresponded to the bottom left pixel of the original image. That number was 215, which was the sum of more than just the highlighted pixels.
- To fix this, we found the cell in the Integral Image that was just above the top-right corner of the red box and subtracted its value; 80.
- In order to avoid subtracting too much, we had to add the sum of an overlapping portion back. This value was found in the Integral Image, located in the cell above and to the left of the top-left corner of the box; 20.
- With that done, we were free to remove the final section. We found the cell that was directly left of the bottom-left corner of the box in our Integral Image and subtracted its value; 72.
Thus, the sum of the values in the red box of the original image is:
215 - 80 + 20 - 72 = 83
Summary
So how is the Integral Image like a self-working card trick? I mentioned at the beginning that many self-working card tricks use mathematics to perform a task (a card trick) while minimizing resources used (practice time). As we just witnessed, if we our task is to find the sum of values in a specified area of an image, we only need 4 numbers. Ever! The area could contain over 20,000 pixels and, thanks to the Integral Image (a clever use of mathematics), you would only need 4 numbers to calculate the sum! The results of reducing the computational cost is that we can run facial recognition algorithms in real-time on hardware like smart phones and even mid-ranged digital cameras. Quite simply, the results are magical.
