Eliminate branching when find median in a binary {0, 255} image

Question

I have a binary image, the binary value is either 0 or 255. the type of the image data is unsigned char. Here I need to do a median filtering on this image.

I think using a histogram to find the median should be fast. Using some codes to explain:

unsigned int hist[2] = {0, 0};

for (int i = 0; i < kernel_h; ++i) {
     for (int j = 0; j < kernel_w; ++j) {
          if (image(i,j) == 0) {
              hist[0]++;
          }
          else {
              hist[1]++;
          }
     }
}

Then, we could get the median value very fast. But due to this case, the codes still could be improved：

int counter = 0;

for (int i = 0; i < kernel_h; ++i) {
     for (int j = 0; j < kernel_w; ++j) {
          if (image(i,j) == 0) {
              counter++
          }
          else {
              counter--;
          }
     }
}

But I wonder is there some other way to eliminate the if-else branch, like using bit operations to map {0, 255} to something so that we could just update a flag without branching.

Anybody any suggestion ?

Answer 1

All bits of 255 are 1 so you can simplify that "if" to:

hist[image(i,j) & 1]++;

If you want to use the counter you can do:

counter += (image(i,j) & 2)-1;

Answer 2

This computation can be made MUCH faster and more specifically O(n) in the number of pixels and independent on the kernel size.

The idea is to do first a "scan conversion" computing a summed area table in which the value of each (x, y) pixel is replaced by the sum of all pixels from (0, 0) to (x, y).

Given this you can know in fixed time how many pixels are set in any rect using

st(x0, y0) + st(x1, y1) - st(x0, y1) - st(x1, y0)

and given that each pixel was 0 or 1 the sum gives you the count of ones.

The total computation time is O(n) to build the sum table and O(n) to do the median filtering, no matter how big is the area where to do the counting.

In the case of median filtering you could precompute the result depending on the sum and the formula in the inner loop could be:

result[x] = res[p0[x] + p1[x+box] - p0[x+box] - p1[x]];

Moreover the sum table doesn't need to be computed completely (thus requiring one integer per pixel) but it could be computed "lazily" while doing the result and you need only as many lines of the table as the height of the kernel still keeping computing time O(image_width*image_height) but requiring only kernel_height*image_width memory.