面积求和table（积分图）returns 矩形求和的废话

Question

所以在维基百科上，您可以看到一篇描述 how summed area table (integral image) works 的文章。它是计算机视觉和图像分析中非常重要的一部分。

我正在努力实现它。这个概念真的很简单：

做一个array[imageheight][imagewidth]
每个数组成员应包含原始图像中前后所有像素的总和
要计算任何矩形的总和，请使用 A-B-C+D 公式，其中 ABCD 是该矩形：

所以我做了这个函数来对BufferedImage上的所有像素求和：

  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 < h; y++) {
      for (int x = 0; x < 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&0x00FF0000)>>16)+((pixel&0x0000FF00)>>8)+(pixel&0x000000FF);
        integral_image[y][x] = the_sum;
      }
    }
    //Return the array
    return integral_image;
  }

我还制作了一个调试功能，它让我相信它可以工作：

^{注意白色区域如何影响图像的总和}

但是如果我做这个测试用例：

   //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])
   );

我得到一个悲伤的结果：

1.7471835E7 =? 1.7471835E7 =? 112455.0

有趣的是，那个纯白色的图像returns 0:

7650000.0 =? 7650000.0 =? 0.0  - this was 100x100 white image and 765 is 3*255 so everything seems right

我不知道如何弄清楚这个问题。一切似乎都太清楚了，不会有错误。所以要么上面的代码有错别字，要么逻辑有误。有什么想法吗？

Answer 1

你的问题在这里：

//Extrapolate color values from the integer 
the_sum+= ((pixel&0x00FF0000)>>16)+((pixel&0x0000FF00)>>8)+(pixel&0x000000FF);
integral_image[y][x] = the_sum;

你应该做的是：

int A = (x > 0 && y > 0) ? integral_image[y-1][x-1] : 0;
int B = (x > 0) ? integral_image[y][x-1] : 0;
int C = (y > 0) ? integral_image[y-1][x] : 0;
integral_image[y][x] = - A + B + C
    + ((pixel&0x00FF0000)>>16)+((pixel&0x0000FF00)>>8)+(pixel&0x000000FF);

（没有 the_sum 变量）。

现在可以使用 integral_image:

中的值在常数时间内计算图像部分 (minx, miny) -> (maxx, maxy) 的总和

double A = (minx > 0 && miny > 0) ? integral_image[miny-1][minx-1] : 0;
double B = (minx > 0) ? integral_image[maxy][minx-1] : 0;
double C = (miny > 0) ? integral_image[miny-1][maxx] : 0;
double D = integral_image[maxy][maxx];

double sum = A - B - C + D;

请注意，使用 minx-1 和 miny-1 是因为最小坐标具有包容性。

面积求和table（积分图）returns 矩形求和的废话

Summed area table (integral image) returns nonsenses on rectangle sum

java

image-processing

computer-vision