用位移操作代替分支语句

Question

我正在编写一个图像二值化算法，它只需将每个像素的亮度值（灰度图像）转换为黑色或白色。目前每个像素二值化的算法大致是这样的

if( grayscale[x] < thresholdValue)
{
bitonal[x] = 1;
}

（这实际上是 ACTUAL 算法的简化，因为双色图像实际上是位打包图像（每个数组索引保存 8 个像素），所以我实际上将 1 位打包到当前数组索引中......但我不认为这会改变我的问题。

我试图做的是消除对 if 语句的需要。

我的想法是按照这个思路做一些事情。用灰度减去阈值，然后执行一些位操作技巧来清除或移动位，这样，如果

(grayscale[x]-threshold) is less than 0, I get a 0. otherwise I would get a 1

的结果。如果以相反的方式做更容易

(if grayscale[x]-threshold < 0 + bitwise trickery get a 1, else get a 0)

，那也可以...只要我可以摆脱分支语句...任何帮助表示赞赏..

Answer 1

bitonal[x] = (grayscale[x] < thresholdValue);

Answer 2

如果亮度是 8 位值，则可以拥有一个包含 0 或 1 的 256 个元素的数组（数组的第一个 threshold 元素包含

1

，其余元素包含

0

。

bitonal[x] = array[grayscale[x]];

Answer 3

我刚刚在我的嵌入式应用程序中寻找类似的时间关键循环的东西。 我发现的一件有趣的事情是这样的代码

bit = (a<b);

仍然在我的平台（TI F2812）上生成分支指令。编译器似乎没有直接的方法将状态标志从比较移动到寄存器中，因此它会生成类似的内容

 temp_register =  0
 cmp a,b
 branch to label if LT
 temp_register = 1
label:
 bit = temp_register

但是，处理器确实有内置的最大和最小运算符。由于分支相当昂贵，因此这段代码实际上运行得更快：

bit = min(max((b-a),0),1);

仅当

max

将任何非零值转换为 1 时，< b. And then the

min

的结果才会非零。

这是特定于处理器的，可能根本不适用于 X86。

Answer 4

您使用什么语言？该语言有最小/最大函数吗？ （例如 C++ 和 Java 都这样做）如果语言这样做，这将是消除 if...eg Min(grayscale[x] < thresholdValue, 0)

Answer 5

也许：

bitonal[x] = ((grayscale[x] - thresholdValue) >> 31) xor 1;

假设您的语言不将布尔值和整数值等同（如 C 和 C++ 那样）。