Replace branch statements by bit-shifting operations

Question

I'm writing an image binarization algorithm which simply converts each pixel's luminance value (grayscale image) to a black or white. Currently the algorithm for binarizing each pixel is roughly this

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

(this is actually a simplification of the ACTUAL algorithm because the bitonal image is actually a bitpacked image (each array index holds 8 pixels) so I actually bitpack the 1 inside the current array index...but I don't think that changes my question.

What I'm attempting to do is to remove the need for the if-statement.

What I was thinking was to do something along the lines of this. Subtract the thresholdValue by the grayscale and then perform some bit manipulation trickery to clear out or shift bits such that if the result of (grayscale[x]-threshold) is less than 0, I get a 0. otherwise I would get a 1 . If it's easier to do it the other way around (if grayscale[x]-threshold < 0 + bitwise trickery get a 1, else get a 0) that would also work... as long as I can get rid of the branch statements...any help appreciated..

Answer 1

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

Answer 2

If luminance is an 8-bit value, then you can have an array of 256 elements which contain either 0 or 1 (the first threshold elements of the array contain 1, and the remaining elements contain 0.

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

Answer 3

I've just been looking at similar stuff for a time-critical loop in my embedded app. One interesting thing I found is that code like this

bit = (a<b);

still generates a branch instruction on my platform (TI F2812). It seems the compiler has no direct way to move the status flag from a comparison into a register, so instead it generates something like

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

However, the processor does have built-in max and min operators. Since branching is quite expensive, this code actually runs faster:

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

The result of max will only be non-zero if a < b. And then the min will convert any non-zero to 1.

This is very processor specific, and may not apply at all on an X86.

Answer 4

What language are you working with? Does the language have min/max functions? (C++ and Java for example both do) If the language does, that would be one way to elminate the if...eg Min(grayscale[x] < thresholdValue, 0)

Answer 5

Perhaps:

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

Assuming your language doesn't equate boolean and integer values (as C and C++ do).