How to dither a 256 greyscale bitmap to b/w

I need to programmatically dither a 256 grey scale bitmap to 1-bit (black and white) in a borland pascal for windows version 7.0 application.

I've seen the functions I want in Paint-Shop pro, when you do colour reduction. There you can do ordered dithering, and a number of types of error diffusion.

Does anybody know of any 16-bit graphic libraries that have functions like these?

Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
Create a monochrome bitmap (CreateBitmap(nX, nY, 1, 1, NULL)) and select it into a memory DC (destination DC). Select the color bitmap into another memory DC (source DC). BitBlt the color bitmap to the monochrome bitmap. GDI sets to white (1) all pixels that match the background color of the source DC (SetBkColor). All other bits are set to black (0).
0
Commented:
I might have misunderstood your question. If you want to dither it, the dithered monochrome bitmap will be bigger than the origianl greyscale bitmap because one pixel is represented by n x n pixels in a dithered bitmap.

Let's take n = 2 as an example. You need to analyze each pixel in the original bitmap. Divide the grayscale into 2 x 2 + 1 = 5 levels. If the gray level of the pixel is 0, use

00
00

as a pixel in the monochrome bitmap.

If the gray level is 1, use

00
01

as a pixel in the monochrome bitmap.

If the gray level is 2, use

10
01

as a pixel in the monochrome bitmap.

If the gray level is 3, use

11
01

as a pixel in the monochrome bitmap.

If the gray level is 4, use

11
11

as a pixel in the monochrome bitmap.
0
Author Commented:
Chensu:-

It is possible to dither without increasing the size of the bitmap - I know this because Paintshop pro does it.

However, thinking about it, your answer may not be bad - after all, I could use Stretchblt to stretch it back to its orriginial size....

I will hold this open to see if there are any other answers.

I'm sure there must be a graphics library that has colour reduction functions like this in it - I would prefer not to have to do it myself.

0
Commented:
>It is possible to dither without increasing the size of the bitmap - I know this because Paintshop pro does it.

If it is a monochrome bitmap, which has only two colors - black and white, and the size does not change, it is not dithering. That's the method using BitBlt I mentioned.
0
Author Commented:
Your statement is incorrect. Try printing a colour bitmap to any ordinary laser printer - it does not enlarge the bitmap, and it does not do the bitblt thing you mentioned (otherwise most photo bitmaps would come out completely black).

In fact, if you look at the graphic options under the properties of the printer driver, you have several dithering options (course, fine, error diffusion etc).

Ordinary black and white laser printers cannot natively print greyscale. They achieve the effect using dithering. The functions for doing this is what I am after.
0
Commented:
>Try printing a colour bitmap to any ordinary laser printer - it does not enlarge the bitmap, and it does not do the bitblt thing you mentioned.

Keep in mind that a pixel of a printer is much much smaller than a pixel of the screen. Although the size of the bitmap appears to be the same, one pixel is actually represented by a dozen of pixels on a printer. The size does enlarge in terms of the pixels of the printer.

>They achieve the effect using dithering.

Exactly.
0
Commented:
Oops, meant to be a comment. Sorry.
0
Author Commented:
Chensu:
Lets agree to differ on this point.
I would like to give the oppurtunity to other experts to answer.

Any other experts:
I am interested to see if there is anybody else that has an opinion.
0
Commented:
Take a look at the desciption on dither algorithm in some computer graphics programming books, you'll agree with me.
0
Author Commented:
Chensu: Look at paintshop pro. It has a dither algotithm, and it doesn't enlarge the bitmap.

This disagreement is not helping me to solve my problem.
0
Commented:
Test http://www.eleves.ens.fr:8080/docs/icon/library/fgprocs.html
This is real huge pascal library
for many actions by Graphic objects
and to dither too.
But for use it you must make some
efforts.
0
Author Commented:
AlexVirochovsky: Thanks for you comment. I checked the library out, and although it is full of useful stuff, the dither function there was more to do with shading eather than colour reduction. I could not find anything that did colour reduction.
0
Commented:
Try this:
(x,y...coordinates, c...color index)

procedure MatrixDither (x,y,c: integer);
begin
if M [y mod N, x mod N] > c
then PutPixel (x,y,1)
else PutPixel (x,y,0);
end;

M is a dithering Matrix of size (N x N).
A dithering matrix contains unique numbers which mean:
M [i, j] = X ... pixel is ON in colors greater or equal to X.
For example, M (4x4) would be:
00 08 02 10
12 04 14 06
03 11 01 09
15 07 13 05

Or use this:

procedure RandomDither (x,y,c: integer);
begin
if Random (MaxGray) < c
then PutPixel (x,y,1)
else PutPixel (x,y,0);
end;

But this produces low quality image when using only 2 colors.

If you want better techniques, ask me to tell you about Floyd-Steinberg, Sierra, Jarvis-Judice-Ninke or Stucki techniques.
0
Author Commented:
maruz:

Thats brilliant - thanks.

If you can't be bothered, just repost the above answer and I'll give you the points.

Cheers.
0
Commented:
OK, if you don't enlarge it, the quality may be reduced significantly and some information may be lost.
0
Commented:
Hey.. a dithering thread.. that's one of my favorite topics..

I have 3 very nice dithering matrices which I calculated a couple of years ago.. they are 16x16 pixels large and look awsome. I use them when I dither from truecolor to highcolor (one matrix for each color-component).

static char mdm_orderedr[16][16]=
{{ 23,233,121,159, 89,149, 46, 82,157,122, 24,150, 52,226, 61,143},
{170, 49,205, 32,215, 20,248,169, 37,232, 98,245,128, 33,182,102},
{200,131, 93,176,109,183,132, 14,197, 66,190,  5,209, 79,238, 13},
{ 69,250,  7, 71,229, 53, 96,237,116,145, 87,165, 44,141,120,160},
{ 38,114,189,153, 29,139,191, 76, 31,224, 55,254,104,204, 28,223},
{138,231, 60,208, 84,253,  2,162,211,123,179, 17,152, 67,174, 97},
{ 78, 19,167,126,103, 47,203,108, 62, 10,134,218, 81,241,  1,213},
{196,148,246, 12,220,173, 73,155,243,185,100, 50,194,110,156, 56},
{119, 88, 43,112,144, 34,234, 22, 91, 36,249,140, 21,228, 40,181},
{ 26,217,127,236, 59,201,135,117,193,124,166, 63,177, 74,133,251},
{161, 51,186,  4,178, 94, 15,225, 48,214,  6,235, 95,206,  8, 86},
{ 99,199, 68,151, 80,255,164, 70,147, 85,158,107, 30,146,221,171},
{227, 16,242,115,210, 39,105,188, 27,202, 58,180,240,118, 35, 64},
{106,154, 41,175, 25,142,239, 65,230,130,252, 42,136, 72,192,129},
{ 45,212,137, 75,195,101,  0,172,113, 11, 92,168, 18,216,  3,247},
{187, 83,  9,244, 57,222,125,207, 54,219,184, 77,198,111,163, 90}};

static char mdm_orderedg[16][16]=
{{192, 11,183,125, 26,145, 44,244,  8,168,139, 38,174, 27,141, 43},
{115,211,150, 68,194, 88,177,131, 61,222, 87,238, 74,224,100,235},
{ 59, 33, 96,239, 51,232, 16,210,117, 32,187,  1,157,121, 14,165},
{248,128,217,  2,163,105,154, 81,247,149, 97,205, 52,182,209, 84},
{ 20,172, 80,140,202, 41,185, 55, 24,197, 65,129,252, 35, 70,147},
{201, 63,189, 28, 90,254,116,219,137,107,231, 17,144,119,228,109},
{ 46,245,103,229,134, 13, 67,162,  6,170, 47,178, 76,193,  4,167},
{133,  9,159, 54,175,124,225, 93,242, 79,214, 99,241, 56,221, 92},
{186,218, 78,208, 37,196, 25,188, 42,142, 29,158, 21,130,156, 40},
{102, 31,148,111,234, 85,151,120,207,113,255, 86,184,212, 69,236},
{176, 73,253,  0,138, 58,249, 71, 10,173, 62,200, 50,114, 12,123},
{ 23,204,118,191, 91,181, 19,164,216,101,233,  3,135,169,246,152},
{223, 60,143, 48,240, 34,220, 82,132, 36,146,106,227, 30, 95, 49},
{ 83,166, 18,199, 98,155,122, 53,237,179, 57,190, 77,195,127,180},
{230,108,215, 64,171,  5,206,161, 22, 94,251, 15,153, 45,243,  7},
{ 72,136, 39,250,104,226, 75,112,198,126, 66,213,110,203, 89,160}};

static char mdm_orderedb[16][16]=
{{ 23,233,121,159, 89,149, 46, 82,157,122, 24,150, 52,226, 61,143},
{170, 49,205, 32,215, 20,248,169, 37,232, 98,245,128, 33,182,102},
{200,131, 93,176,109,183,132, 14,197, 66,190,  5,209, 79,238, 13},
{ 69,250,  7, 71,229, 53, 96,237,116,145, 87,165, 44,141,120,160},
{ 38,114,189,153, 29,139,191, 76, 31,224, 55,254,104,204, 28,223},
{138,231, 60,208, 84,253,  2,162,211,123,179, 17,152, 67,174, 97},
{ 78, 19,167,126,103, 47,203,108, 62, 10,134,218, 81,241,  1,213},
{196,148,246, 12,220,173, 73,155,243,185,100, 50,194,110,156, 56},
{119, 88, 43,112,144, 34,234, 22, 91, 36,249,140, 21,228, 40,181},
{ 26,217,127,236, 59,201,135,117,193,124,166, 63,177, 74,133,251},
{161, 51,186,  4,178, 94, 15,225, 48,214,  6,235, 95,206,  8, 86},
{ 99,199, 68,151, 80,255,164, 70,147, 85,158,107, 30,146,221,171},
{227, 16,242,115,210, 39,105,188, 27,202, 58,180,240,118, 35, 64},
{106,154, 41,175, 25,142,239, 65,230,130,252, 42,136, 72,192,129},
{ 45,212,137, 75,195,101,  0,172,113, 11, 92,168, 18,216,  3,247},
{187, 83,  9,244, 57,222,125,207, 54,219,184, 77,198,111,163, 90}};

jonwcroft, I can give you an explanation how the error diffusion dithering works (it's pretty easy btw..) I also have a collection of all the classic error diffusion schemes here (floyed steinberg, stucki and so on). I'm a weak pascal coder, but I could give you pseudo code and c code that can be understood by pascal programmers... you wanna have it?

Nils Pipenbrinck

0
Commented:
The other techniques I mentioned last time are called difference distribution (I don't know whether I've translated this right).
You can use any of the methods and then distribute the difference between original value and the new one among the closest pixels.
For example, if the intensity value of the original pixel was 5/16 and you convert it to 0, you can add 2/16 to the pixel to the "east" and 1/16 to each pixel on the next line, from "south-west" to "south-east".
There are many methods how to divide the difference among the neighbors. The best of them seems to be Floyd-Steinberg.

Floyd-Steinberg:
7/16 to the east
3/16 to the south-west
5/16 to the south
1/16 to the south-east

F.Sierra:
1/2 to the east
1/4 to the south-west
1/4 to the south
(this is easier to compute)

Jarvis-Judice-Ninke:
X 7 5
3 5 7 5 3     /48
1 3 5 3 1

Stucki:
X 8 4
2 4 8 4 2     /42
1 2 4 2 1

Of course, you have to draw the image line by line, north to south (from up to down), west to east (from left to right).
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
chensu: Converting a picture with enlarging it is called halftoning, not dithering.
0
Author Commented:
Maruz: Thanks mate!

nils pipenbrinck: