title: Summed area table (integral image) returns nonsenses on rectangle sum
body: <p>So here on wikipedia you can see an article describing <a href="http://en.wikipedia.org/wiki/Summed_area_table" rel="nofollow noreferrer">how summed area table (integral image) works</a>. It's a very important part of computer vision and image analysis.</p>
  
  <p>I'm trying to implement it. The concept is really simple:</p>
  
  <ol>
  <li>Make an <code>array[imageheight][imagewidth]</code></li>
  <li>Every array member should contain sum of all pixels before and above in the original image</li>
  <li>To get sum on any rectangle, use <code>A-B-C+D</code> formula, where ABCD is this rectangle:
  <img src="https://i.stack.imgur.com/n0O05.png" alt="summed area table sum - wikipedia"></li>
  </ol>
  
  <p>So I made this function to sum all pixels on <code>BufferedImage</code>:</p>
  
  <pre><code>  public static double[][] integralImageGrayscale(BufferedImage image) {
      //Cache width and height in variables
      int w = image.getWidth();
      int h = image.getHeight();
      //Create the 2D array as large as the image is
      //Notice that I use [Y, X] coordinates to comply with the formula
      double integral_image[][] = new double[h][w];
      //Sum to be assigned to the pixels
      double the_sum = 0;
      //Well... the loop
      for (int y = 0; y &lt; h; y++) {
        for (int x = 0; x &lt; w; x++) {
          //Get pixel. It's actually 0xAARRGGBB, so the function should be getARGB
          int pixel = image.getRGB(x, y);
          //Extrapolate color values from the integer 
          the_sum+= ((pixel&amp;0x00FF0000)&gt;&gt;16)+((pixel&amp;0x0000FF00)&gt;&gt;8)+(pixel&amp;0x000000FF);
          integral_image[y][x] = the_sum;
        }
      }
      //Return the array
      return integral_image;
    }
  </code></pre>
  
  <p>I also made a debug function and it's convincing me that it works:</p>
  
  <p><img src="https://i.stack.imgur.com/hX13U.png" alt="normal and integral image"><br>
  <sup>Notice how the white areas influence the sum of the image</sup></p>
  
  <p>But if I make this test case:</p>
  
  <pre><code>   //Summed area table (thing is BufferedImage)
     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
       //     A            B            C              D
         (+is[0][0]  -is[0][isw-1] -is[ish-1][0] +is[ish-1][isw-1])
     );
  </code></pre>
  
  <p>I get a sad result:</p>
  
  <pre><code>1.7471835E7 =? 1.7471835E7 =? 112455.0
  </code></pre>
  
  <p>Interesting thing is, that pure white image returns 0:</p>
  
  <pre><code>7650000.0 =? 7650000.0 =? 0.0  - this was 100x100 white image and 765 is 3*255 so everything seems right
  </code></pre>
  
  <p>I have no idea how to get to the bottom of this. Everything seems too clear to contain a mistake. So either there's a typo in the code above, or the logic is wrong. Any ideas?</p>