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

 

     The integral rule is that each element in the integral table is sum of upper-left elements( including itself ). e.g,

• 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)