A quick way to find the maximum value in the rectangle area of ​​a 2d array

Question

I have a 2d array of depth values ​​and need a quick way to find the maximum value in a given rectangular area. Many rectangles will be tested against a given depth buffer, so a valid preprocess step will be acceptable.

A naive approach would be to scan each pixel in a rectangle, tracking the maximum length, requiring width iterations *.

By first creating the quadrant of the depth buffer, where each parent node contains the maximum value of its children, complexity can be reduced to approximately iterations of width and height. This method is good, but I would like to know if it can be done even faster.

I gave an example of a method for finding the average value, rather than the maximum value in constant time, using the linear time preprocess here .

Does anyone know of a similar method to find the maximum value?

Answer 1

Yes, you can generalize the trick of the average value, but only for small color depths, for example, 8 bits of depth (0-255). Suppose you have k colors (or different depths).

For your reference, here is a good explanation for the average calculation of a rectangle through the Viola / Jones CVPR 2001 integrated images , see section 2.1.

, k, /. , , . , . , ( ).

, , , , O (k) O (k * width * height) .

( , .)

Answer 2

2, . , 2 . 4 . 1/3 , mip-maps.

, , , . , , , - .

-:

 int getMax(Rect query_rect, int level, int level_x, int level_y)
 {
      int level_factor = 1 << level;
      // compute the area covered by this array element:
      Rect level_rect(level_x * level_factor, level_y * level_factor,
          (level_x + 1) * level_factor, (level_y + 1) * level_factor);

      // if the regions don't overlap then ignore:
      if(!query_rect.intersects(level_rect))
          return -1;

      // query rect entirely contains this region, return precomputed max:
      if(query_rect.contains(level_rect))
          return pyramid[level][level_x][level_y];

      if(level == 0)
          return -1;  // ran out of levels

      int max = getMax(query_rect, level - 1, level_x * 2, level_y * 2);
      max = maxValue(max, getMax(query_rect, level - 1, (level_x * 2) + 1, level_y * 2);
      max = maxValue(max, getMax(query_rect, level - 1, level_x * 2, (level_y * 2) + 1);
      max = maxValue(max, getMax(query_rect, level - 1, (level_x * 2) + 1, (level_y * 2) + 1);

      return max;
 }

( capx 1x1 ):

 int max = getMax(query_rect, 10, 0, 0);

, . , .