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

The output is:

431972.0 =? 431972.0 =? 0.0

The plotted summed area table seems OK (the $f(value)$ never decreases):

image description

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.