The Integral Image

Figure 1.10: Construction of the integral image and its use for computing areas.

Let $I$ be a generic grayscale image. The value of pixel $(x,y)$ in the integral image $\mathcal{I}$ represents the sum of the values of all pixels in the source image contained within the rectangle $(0,0)-(x,y)$:

$$\mathcal{I}(x,y) = \sum_{v=0}^{y} \sum_{u=0}^{x} I(u,v)$$ (1.140)

With this definition, it should be noted that the rectangle boundaries are included in the summation (Figure 1.10).

The computational trick of using the integral image makes it possible to optimize several algorithms presented in this book, in particular SURF (Section 6.4) and Haar feature extraction (Section 7.1).

Using the integral image, the sum over any rectangular subregion of image $I$ can be computed at a constant computational cost of four additions:

$$\begin{array}{l} \sum_{y=y_0}^{y_1} \sum_{x=x_0}^{x_1} I(x... ...- \mathcal{I}(x_1,y_0-1) - \mathcal{I}(x_0-1,y_1) \end{array}$$ (1.141)

The value obtained in this way represents the sum of the elements of the original image within the rectangle, including its boundaries.

In addition to allowing the sum over any subregion of the image to be computed quickly, the integral image also makes it easy to perform convolutions with kernels of particular shapes, with computational performance independent of filter size. Examples of convolution masks can be found in Section 7.1.