java - 求和面积表(积分图像)在矩形和上返回无意义的内容

Question

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

我正在努力实现它。这个概念非常简单:

1. 创建一个数组[imageheight][imagewidth]
2. 每个数组成员应包含原始图像中前后所有像素的总和
3. 要计算任意矩形的总和，请使用 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

有趣的是，纯白色图像返回 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。