I am working on an algorithm that performs a global threshold value of an 8-bit grayscale image into a single-bit (bit packed, for example, 1 byte contains 8 pixels) monochrome image. Each pixel in a Grayscale image can have a brightness value from 0 to 255.
My environment is Win32 in Microsoft Visual Studio C ++.
I'm interested in optimizing the algorithm as much as possible out of curiosity, a 1-bit image will be converted to TIFF. I am currently setting FillOrder as MSB2LSB (the most significant bit for the least significant bit) just because the TIFF specification offers this (it doesn't have to be MSB2LSB)
Just some kind of background for those who don’t know:
The MSB2LSB arranges the pixels from left to right in the byte in the same way that the pixels orient in the image as the X coordinate increases. If you look at the Grayscale image from left to right along the X axis, this obviously requires you to think back when you pack the bit into your current byte. Having said that, let me show you what I have (this is in C, I did not try to use ASM or Compiler Intrinsics, but only because I have very little experience with it, but that would be possible).
Since the monochrome image will have 8 pixels per byte, the width of the monochrome image will be
(grayscaleWidth + 7) / 8;
FYI, I assume that my largest image should be 6000 pixels wide:
The first thing I do (before processing any image) is
1) calculate the search table for the amounts that I need to translate into a specific byte, if you specify the X coordinate from my image in shades of gray:
int _shift_lut[6000]; for( int x = 0 ; x < 6000; x++) { _shift_lut[x] = 7-(x%8); }
Using this lookup table, I can pack the monochrome bit value into the current byte I'm working on, for example:
monochrome_pixel |= 1 << _shift_lut[ grayX ];
which ends with a huge increase in speed than
monochrome_pixel |= 1 << _shift_lut[ 7-(x%8)];
The second lookup table that I am calculating is a lookup table that tells me the X index in my monochrome pixel, taking into account the X pixel per grayscale pixels. This very simple LUT is calculated like this:
int xOffsetLut[6000]; int element_size=8; //8 bits for( int x = 0; x < 6000; x++) { xOffsetLut[x]=x/element_size; }
This LUT allows me to do something like
monochrome_image[ xOffsetLut[ GrayX ] ] = packed_byte;
My grayscale image is a simple unsigned char *, as well as my monochrome image;
This is how I initialize a monochrome image:
int bitPackedScanlineStride = (grayscaleWidth+7)/8; int bitpackedLength=bitPackedScanlineStride * grayscaleHeight; unsigned char * bitpack_image = new unsigned char[bitpackedLength]; memset(bitpack_image,0,bitpackedLength);
Then I call my binarization function as follows:
binarize( gray_image.DataPtr(), bitpack_image, globalFormThreshold, grayscaleWidth, grayscaleHeight, bitPackedScanlineStride, bitpackedLength, _shift_lut, xOffsetLut);
And here is my Binarize function (as you can see, I did a few expanding cycles, which may or may not help).
void binarize( unsigned char grayImage[], unsigned char bitPackImage[], int threshold, int grayscaleWidth, int grayscaleHeight, int bitPackedScanlineStride, int bitpackedLength, int shiftLUT[], int xOffsetLUT[] ) { int yoff; int byoff; unsigned char bitpackPel=0; unsigned char pel1=0; unsigned char pel2=0; unsigned char pel3=0; unsigned char pel4=0; unsigned char pel5=0; unsigned char pel6=0; unsigned char pel7=0; unsigned char pel8=0; int checkX=grayscaleWidth; int checkY=grayscaleHeight; for ( int by = 0 ; by < checkY; by++) { yoff=by*grayscaleWidth; byoff=by*bitPackedScanlineStride; for( int bx = 0; bx < checkX; bx+=32) { bitpackPel = 0;
I know that this algorithm could potentially skip some trailing pixels in each row, but don't worry about that.
As you can see for each monochrome byte, I process 8 gradations of gray.
Where you see pel8 <= threshold is a neat little trick that resolves to 0 or 1 and is much faster than if {} else {}
For each increment X, I pack the bits into bits of a higher order than the previous X
therefore, for the first set of 8 pixels in the image in grayscale
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
Here's what the bits in a byte look like (obviously, each numbered bit is only a threshold result of processing the corresponding numbered pixel, but you get the idea)
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
PHEW , which should be this. Feel free to have fun with some graceful tricks that squeeze more juice from this algorithm.
With compiler optimization turned on, this function takes an average of 16 milliseconds on an image of approximately 5000 x 2200 pixels in size on a dual-core kernel processor.
EDIT:
Sentence
R .. was to remove the LUT shift and just use constants that are actually perfectly logical ... I changed the OR'ing of each pixel as such:
void binarize( unsigned char grayImage[], unsigned char bitPackImage[], int threshold, int grayscaleWidth, int grayscaleHeight, int bitPackedScanlineStride, int bitpackedLength, int shiftLUT[], int xOffsetLUT[] ) { int yoff; int byoff; unsigned char bitpackPel=0; unsigned char pel1=0; unsigned char pel2=0; unsigned char pel3=0; unsigned char pel4=0; unsigned char pel5=0; unsigned char pel6=0; unsigned char pel7=0; unsigned char pel8=0; int checkX=grayscaleWidth-32; int checkY=grayscaleHeight; for ( int by = 0 ; by < checkY; by++) { yoff=by*grayscaleWidth; byoff=by*bitPackedScanlineStride; for( int bx = 0; bx < checkX; bx+=32) { bitpackPel = 0;
Now I am testing Intel Xeon 5670 using (GCC) 4.1.2. According to these specifications, a hard-coded bitshift is 4 ms slower than using my original LUT algorithm. In Xeon and GCC, the LUT algorithm takes an average of 8.61 ms, and hard-coded bit-bits take an average of 12.285 ms.