Integral table computation
The raw data:
| a | b | c | d | e |
| f | g | h | i | j |
| k | l | m | n | o |
| p | q | r | s | t |
| u | v | w | x | y |
The integral data:
| E | F | |||
| A | B | |||
| G | C | D | ||
| H | ||||
| I |
- A = a + b + f + g
- B = a + b + c + f + g + h
- C = a + b + f + g + k + l
- D = a + b + c + f + g + h + k + l + m
We can, therefore, simply archive the integral table by 4 "for loop"
for(int j = 0; j < height; j++)
{
for(int i = 0; i < width; i++)
{
integral[j][i] = 0;
for(int y = 0; y <= j; y++)
{
for(int x = 0; x <= i; x++)
{
integral[j][i] += rawdata[y][x];
}
}
}
}
but it is too inefficiency and consuming too many operations when computing in such simple way . Thus, we can examine the integral table, it can be found that D could be get from the 3 nearest upper-left element A, B, C. So D = m + B + C - A. In addition we must consider the boundary problem, when processing the first row it's just the sum of the current raw data and the left integral data, e.g, F = d + E. The same as above, when processing the first colume it's just the sum of the current raw data and the upper integral data, e.g, H = p + G. Therefore, the computation can be archieved by using only 2 "for loop"
for(int j = 0; j < height; j++)
{
for(int i = 0; i < width; i++)
{
if((j == 0) && (i == 0))// process the first col and row element
integral[j][i] = rawdata[j][i];
else if((j == 0) && (i != 0))// process the first row element
integral[j][i] = rawdata[j][i] + integral[j][i-1];
// F = d + E
else if((j != 0) && (i == 0))// process the first col elements
integral[j][i] = rawdata[j][i] + integral[j-1][i];
// H = p + G
else // process the normal element
integral[j][i] = rawdata[j][i] + integral[j-1][i] +
integral[j][i-1] - integral[j-1][i-1];
// D = m + B + C - A
}
}
[ Download ]: test file (C::B project)
