3D variant for summed area table (SAT)

user_1813971 0
Viewed 1343

As per Wikipedia:

A summed area table is a data structure and algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid.

For a 2D space a summed area table can be generated by iterating x,y over the desired range, 

I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1)

And the query function for a rectangle corners A(top-left), B(top-right), C(bottom-right), D can be given by:-

I(C) + I(A) - I(B) - I(D)

I want to convert the above to 3D. Also please tell if any other method/data structure available for calculating partial sums in 3D space.

cumulative-sum data-structures 3d algorithm
2 Answers

A bit late to the party, but anyway. There is a general formula for n-dimensional space in Wikipedia, presented in this paper. Following that notation, we assume that you are interested in the volume specified by a rectangular box with corners (x0,y0,z0) and (x1,y1,z1). Then, having an integral image (volume), the coefficients would be: S((x0,y0,z0) to(x1,y1,z1)) = S(x1,y1,z1) - S(x1,y1,z0) - S(x1,y0,z1) + S(x1,y0,z0) - S(x0,y1,z1) + S(x0,y1,z0) + S(x0,y0,z1) - S(x0,y0,z0)

Here is matlab code I used to calculate them (can specify dimensionality)

%number of dimensions
nDim = 3;
for i=1:2^nDim
        str=dec2bin(i-1,nDim);
        strout='index combo (';
        sum=0;
        for n=1:nDim
            strout = strcat(strout,str(n));
            sum=sum + str2num(str(n));
        end
        strout = strcat(strout,') sign: ',num2str((-1)^(nDim-sum)));
        disp(strout);
end

which outputs:

(000) sign:-1
(001) sign:1
(010) sign:1
(011) sign:-1
(100) sign:1
(101) sign:-1
(110) sign:-1
(111) sign:1
user_69965070
Related