CODEWITHSUNDEEP
algorithmconditional-statementsbit-manipulationbit-shiftbranchless
alessandro ferrucci
alessandro ferrucci

Reputation: 1291

Replace branch statements by bit-shifting operations

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..

Upvotes: 5

Views: 1011

Answers (5)

AShelly
AShelly

Reputation: 35540

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.

Upvotes: 4

ChrisW
ChrisW

Reputation: 56113

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

Upvotes: 4

Jeffrey L Whitledge
Jeffrey L Whitledge

Reputation: 59463

Perhaps:

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

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

Upvotes: 0

Jessica Brown
Jessica Brown

Reputation: 8312

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)

Upvotes: 0

Mark Byers
Mark Byers

Reputation: 838296

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

Upvotes: 8

Related Questions