1. Introduction
The integral image, or summed-area table, is a data structure and algorithm for quickly and efficiently computing the sum of values in a rectangular subset of a grid.
An integral image is created to store the integral value at every position (x, y). The value at any point (x, y) is the sum of all the pixels to the upper left of (x, y).
\[Integral(x,y)=\sum_{x^{'}<{x}, y^{'} <{y}}I(x^{'}, y^{'})\]
The integral values can be computed efficiently as follows.
\[Integral(x,y)=I(x,y) + Integral(x, y - 1) + Integral(x - 1,y) - Integral(x -1, y-1)\]
After computing the integral image, the sum over any rectangular area can be computed from its four corners.
\[sum(ABCD)=Integral(D) + Integral(A) - Integral(B) - Integral(C)\]
The integral histogram is similar to the integral image but has 256 channel values per pixel (for an 8-bit image).
Moreover, this method can be extended to quickly calculate variance or standard deviation of a block.
\[Var(ABCD)=\frac{1}{W * H}\sum_{x, y}(I(x,y) - \mu)^{2}=\frac{1}{W*H}\sum_{x,y}(I^{2}(x, y) - 2*{\mu}*{I(x,y)} + {\mu}^{2})=\frac{1}{W*H}(\sum_{x,y}I^{2}(x, y) - 2*{\mu}*\sum_{x,y}{I(x,y)} + \sum_{x,y}{\mu}^{2})=\frac{1}{W*H}(\sum_{x,y}I^{2}(x, y) - 2*{\mu}*\sum_{x,y}{I(x,y)} + (W*H)*{\mu}^{2})\]
Where \(\sum_{x,y}I^{2}(x, y)\) can be obtained by the integral of the squared pixel values
2. Experiment
3. References