Replace branch instructions with bit-shift operations

Question

I am writing an image binarization algorithm that simply converts each pixel brightness value (grayscale image) to black or white. Currently, the binarization algorithm for each pixel is something like this

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

(this is actually a simplification of the ACTUAL algorithm because the bitmap image is actually a bitmap (each array index contains 8 pixels), so I actually split bit 1 into the current array index ... but I don't think that changes my question.

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

What I thought was to do something in this direction. Subtract the grayscale thresholdValue value and then do some bit manipulation to clear or shift the bit so that the result (grayscale[x]-threshold) is less than 0, I get a 0. otherwise I would get a 1 . If it’s easier to do it in another way (if grayscale[x]-threshold < 0 + bitwise trickery get a 1, else get a 0) , which will also work ... as long as I can get rid of the branch operators ... any help appreciated ..

Answer 1

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

Answer 2

If brightness is an 8-bit value, then you can have an array of 256 elements that contain 0 or 1 (the first threshold elements of the array contain 1 , and the rest of the elements contain 0 .

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

Answer 3

I just searched for similar things for a time-critical loop in my embedded application. One interesting thing I found is code like this

 bit = (a<b); 

still generating instructions on my platform (TI F2812). It seems that the compiler has no direct way to move the state flag from comparison to register, so instead something is created like

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

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

 bit = min(max((ba),0),1); 

The result max will only be nonzero if a <b. And then min converts any nonzero value to 1.

This is a very specific processor and may not be used on the X86 at all.

Answer 4

What language do you work in? Does the language have min / max functions? (For example, C ++ and Java). If this language exists, it will be one way to eliminate if ... for example, Min (shades of gray [x] <thresholdValue, 0)

Answer 5

May be:

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

Assuming your language does not equate logical and integer values ​​(like C and C ++).