Counting pixels with integral images

In the previous recipes, we learned that a histogram is computed by going through all the pixels of an image and cumulating a count of how often each intensity value occurs in this image. We have also seen that, sometimes, we are only interested in computing our histogram in a certain area of the image. In fact, having to accumulate a sum of pixels inside an image's subregion is a common task in many computer vision algorithms. Now, suppose you have to compute several such histograms over multiple regions of interest inside your image. All these computations could rapidly become very costly. In such a situation, there is a tool that can drastically improve the efficiency of counting pixels over image subregions: the integral image.

Integral images have been introduced as an efficient way of summing pixels in image regions of interest. They are widely used in applications that involve, for example, computations over sliding windows at multiple scales.

This...