Recently, I was taught about the summed area table (integral image) concept. This table represents a matrix, usually an image, so that every ${SAT}_{ij}$ (I used SAT as summed area table) equals to sum of all values before and above, including current value.
This is great if you have an image and you want to repeatedly retrieve average color values over rectangles in this image. This is then used in computer vision.
Wikipedia suggests, that sum over rectangle $ABCD$ in summed area table equals to:
$$\sum_{ABCD} = SAT(A)+ SAT(D) - SAT(C) - SAT(B)$$
I must've implemented it wrong or the equation is wrong. In order to test it, I created a test case that tries to calculate sum over whole image (rectangle from [0,0] to [width, height]:
//Summed area table
double is[][] = ScreenWatcher.integralImageGrayscale(thing);
//Sum generated by a normal for loop
double ss = ScreenWatcher.grayscaleSum(thing);
//Height of the resulting array
int ish = is.length;
//Width of resulting array. Also throws nasty error if something goes wrong
int isw = is[is.length-1].length;
//Testing whether different methods give same results
System.out.println(
ss +" =? " +
//Last "pixel" in integral image must contain the sum of the image
is[ish-1][isw-1]+" =? "+
//The "sum over rectangle" with a rectangle that contains whole image
// D A C B
(is[ish-1][isw-1]+is[0][0]-is[ish-1][0]-is[0][isw-1])
);
The output is:
431972.0 =? 431972.0 =? 0.0
The plotted summed area table seems OK (the $f(value)$ never decreases):
I posted some code, but my question is really just about the mathematic part here:
- Does the equation from wikipedia really return sum of values in (any) defined rectangle?
If your answer is yes, I will keep finding the bug.
The formula is correct. I had the integral image wrong though.