在二进制{0,255}图像中找到中值时消除分支

Question

我有一个二进制图像,二进制值是0或255.图像数据的类型是unsigned char.在这里,我需要对此图像进行中值滤波.

我认为使用直方图找到中位数应该很快.使用一些代码来解释:

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]++;
          }
     }
}

然后,我们可以非常快地得到中值.但由于这种情况,代码仍然可以改进:

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--;
          }
     }
}

但我想知道是否有其他方法可以消除if-else分支,比如使用位操作将{0,255}映射到某个东西,这样我们就可以更新一个没有分支的标志.

有人有什么建议吗？

Answer 1

所有255位都是1,因此您可以将"if"简化为:

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

如果您想使用计数器,您可以:

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

Answer 2

这种计算可以更快,更具体地说O(n)是像素数,并且与内核大小无关.

该想法首先进行计算求和区域表的"扫描转换" ,其中每个(x,y)像素的值被从(0,0)到(x,y)的所有像素的总和替换.

鉴于此,您可以在固定时间内知道在任何矩形中使用设置的像素数

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

并且假设每个像素为0或1,则总和为您提供1的计数.

总计算时间是O(n)建立总和表并O(n)进行中值滤波,无论计数区域有多大.

在中值滤波的情况下,您可以根据总和预先计算结果,内循环中的公式可以是:

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

此外,sum表不需要完全计算(因此每个像素需要一个整数)但是它可以在执行结果时"懒惰地"计算,并且您只需要与内核的高度一样多的表行计算时间,O(image_width*image_height)但只需要kernel_height*image_width内存.