Take the 2-minute tour ×

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

share|improve this question
Can you assume that bitonal[x] starts out as 0? Also, what language is this in? C? –  Laurence Gonsalves Feb 24 '10 at 21:42
Have you made sure that these calculations take place in code that is executed often enough to cause a performance impact? Or do I have to post the micro-optimization lecture again? –  David Thornley Feb 24 '10 at 21:46
@David.. where's your micro-optimization lecture it'd be nice for me to read..thank you –  alessandro ferrucci Feb 24 '10 at 22:06
After your subtraction, isn't the sign bit of the result exactly what you want? You should be able to shift that into your bitpack, right? –  Scott Smith Mar 2 '10 at 0:44
Just do bitonal[i] = (grayscale[i] >= threshold);. Check the compiler's output, it might even implement that using your CPU's vector operations (or insane bit tricks). Check out graphics.stanford.edu/~seander/bithacks.html for a catalog of bitwise manipulations. –  vonbrand Jan 20 '13 at 15:40

5 Answers 5

up vote 8 down vote accepted

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

share|improve this answer
Nice. If this was C, would it be guaranteed that the <-expression returns true as 1? –  Dirk Vollmar - 0xA3 Feb 24 '10 at 21:47
@divo, yes this is guaranteed by the standard. –  Mark Byers Feb 24 '10 at 21:50
yes this is exactly what I was looking for...thanks for the simple solution :D –  alessandro ferrucci Feb 24 '10 at 21:50
@alessandro ferrucci if it's what you're looking for, mark it as best answer. We want to appease the people who know about bits! –  Yar Feb 24 '10 at 21:53
IIRC this is only defined in the C++ standard. Older C standards did only specified false as zero, but didn't specify true. That said, I do use this form in C++ programs. –  phkahler Feb 24 '10 at 21:54

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]];
share|improve this answer

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

share|improve this answer
Nice point about the TI-F2812. I do not believe that there's any branching on an x86, but that may not be true for ARM and other embedded platforms. –  Xorlev Mar 2 '10 at 0:37
I tested this on an Intel Xeon and bitonal[x] = (grayscale[x] < thresholdValue); is 3 times faster than this method on that architecture. Thanks for your input however. –  alessandro ferrucci Mar 2 '10 at 15:12

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)

share|improve this answer
I am using C++ And Mark Byers' solution works for me. thanks! –  alessandro ferrucci Feb 24 '10 at 21:51


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

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

share|improve this answer
You're making the LSB the wrong polarity while preserving a bunch of garbage bits (unless it's unsigned math). –  phkahler Feb 24 '10 at 21:57
@phkahler - You're right, it does need to be unsigned math. This works in C#: ((uint)(grayscale - thresholdValue) >> 31) ^ 1 I was going to test it, but then the OP said he has using C++, so I just let it go. BTW-the disassembly is 3 instructions long--an eternity!--but has no jumps. :-) –  Jeffrey L Whitledge Feb 24 '10 at 22:46

Your Answer


