1 // ==========================================================
2 // Bitmap conversion routines
3 // Thresholding and halftoning functions
4 // Design and implementation by
5 // - Herv� Drolon (drolon@infonie.fr)
6 // - Dennis Lim (dlkj@users.sourceforge.net)
7 // - Thomas Chmielewski (Chmielewski.Thomas@oce.de)
8 //
9 // Main reference : Ulichney, R., Digital Halftoning, The MIT Press, Cambridge, MA, 1987
10 //
11 // This file is part of FreeImage 3
12 //
13 // COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, WITHOUT WARRANTY
14 // OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, WITHOUT LIMITATION, WARRANTIES
15 // THAT THE COVERED CODE IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE
16 // OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE COVERED
17 // CODE IS WITH YOU. SHOULD ANY COVERED CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT
18 // THE INITIAL DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY NECESSARY
19 // SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF WARRANTY CONSTITUTES AN ESSENTIAL
20 // PART OF THIS LICENSE. NO USE OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER
21 // THIS DISCLAIMER.
22 //
23 // Use at your own risk!
24 // ==========================================================
25
26 #include "FreeImage.h"
27 #include "Utilities.h"
28
29 static const int WHITE = 255;
30 static const int BLACK = 0;
31
32 // Floyd & Steinberg error diffusion dithering
33 // This algorithm use the following filter
34 // * 7
35 // 3 5 1 (1/16)
FloydSteinberg(FIBITMAP * dib)36 static FIBITMAP* FloydSteinberg(FIBITMAP *dib) {
37
38 #define RAND(RN) (((seed = 1103515245 * seed + 12345) >> 12) % (RN))
39 #define INITERR(X, Y) (((int) X) - (((int) Y) ? WHITE : BLACK) + ((WHITE/2)-((int)X)) / 2)
40
41 int seed = 0;
42 int x, y, p, pixel, threshold, error;
43 int width, height, pitch;
44 BYTE *bits, *new_bits;
45 FIBITMAP *new_dib = NULL;
46
47 // allocate a 8-bit DIB
48 width = FreeImage_GetWidth(dib);
49 height = FreeImage_GetHeight(dib);
50 pitch = FreeImage_GetPitch(dib);
51 new_dib = FreeImage_Allocate(width, height, 8);
52 if(NULL == new_dib) return NULL;
53
54 // allocate space for error arrays
55 int *lerr = (int*)malloc (width * sizeof(int));
56 int *cerr = (int*)malloc (width * sizeof(int));
57 memset(lerr, 0, width * sizeof(int));
58 memset(cerr, 0, width * sizeof(int));
59
60 // left border
61 error = 0;
62 for(y = 0; y < height; y++) {
63 bits = FreeImage_GetScanLine(dib, y);
64 new_bits = FreeImage_GetScanLine(new_dib, y);
65
66 threshold = (WHITE / 2 + RAND(129) - 64);
67 pixel = bits[0] + error;
68 p = (pixel > threshold) ? WHITE : BLACK;
69 error = pixel - p;
70 new_bits[0] = (BYTE)p;
71 }
72 // right border
73 error = 0;
74 for(y = 0; y < height; y++) {
75 bits = FreeImage_GetScanLine(dib, y);
76 new_bits = FreeImage_GetScanLine(new_dib, y);
77
78 threshold = (WHITE / 2 + RAND(129) - 64);
79 pixel = bits[width-1] + error;
80 p = (pixel > threshold) ? WHITE : BLACK;
81 error = pixel - p;
82 new_bits[width-1] = (BYTE)p;
83 }
84 // top border
85 bits = FreeImage_GetBits(dib);
86 new_bits = FreeImage_GetBits(new_dib);
87 error = 0;
88 for(x = 0; x < width; x++) {
89 threshold = (WHITE / 2 + RAND(129) - 64);
90 pixel = bits[x] + error;
91 p = (pixel > threshold) ? WHITE : BLACK;
92 error = pixel - p;
93 new_bits[x] = (BYTE)p;
94 lerr[x] = INITERR(bits[x], p);
95 }
96
97 // interior bits
98 for(y = 1; y < height; y++) {
99 // scan left to right
100 bits = FreeImage_GetScanLine(dib, y);
101 new_bits = FreeImage_GetScanLine(new_dib, y);
102
103 cerr[0] = INITERR(bits[0], new_bits[0]);
104 for(x = 1; x < width - 1; x++) {
105 error = (lerr[x-1] + 5 * lerr[x] + 3 * lerr[x+1] + 7 * cerr[x-1]) / 16;
106 pixel = bits[x] + error;
107 if(pixel > (WHITE / 2)) {
108 new_bits[x] = WHITE;
109 cerr[x] = pixel - WHITE;
110 } else {
111 new_bits[x] = BLACK;
112 cerr[x] = pixel - BLACK;
113 }
114 }
115 // set errors for ends of the row
116 cerr[0] = INITERR (bits[0], new_bits[0]);
117 cerr[width - 1] = INITERR (bits[width - 1], new_bits[width - 1]);
118
119 // swap error buffers
120 int *terr = lerr; lerr = cerr; cerr = terr;
121 }
122
123 free(lerr);
124 free(cerr);
125
126 return new_dib;
127 }
128
129 // ==========================================================
130 // Bayer ordered dispersed dot dithering
131 //
132
133 // Function taken from "Ordered Dithering, Stephen Hawley, Graphics Gems, Academic Press, 1990"
134 // This function is used to generate a Bayer dithering matrice whose dimension are 2^size by 2^size
135 //
dithervalue(int x,int y,int size)136 static int dithervalue(int x, int y, int size) {
137 int d = 0;
138 /*
139 * calculate the dither value at a particular
140 * (x, y) over the size of the matrix.
141 */
142 while (size-->0) {
143 /* Think of d as the density. At every iteration,
144 * d is shifted left one and a new bit is put in the
145 * low bit based on x and y. If x is odd and y is even,
146 * or x is even and y is odd, a bit is put in. This
147 * generates the checkerboard seen in dithering.
148 * This quantity is shifted left again and the low bit of
149 * y is added in.
150 * This whole thing interleaves a checkerboard bit pattern
151 * and y's bits, which is the value you want.
152 */
153 d = (d <<1 | (x&1 ^ y&1))<<1 | y&1;
154 x >>= 1;
155 y >>= 1;
156 }
157 return d;
158 }
159
160 // Ordered dithering with a Bayer matrix of size 2^order by 2^order
161 //
OrderedDispersedDot(FIBITMAP * dib,int order)162 static FIBITMAP* OrderedDispersedDot(FIBITMAP *dib, int order) {
163 int x, y;
164 int width, height;
165 BYTE *bits, *new_bits;
166 FIBITMAP *new_dib = NULL;
167
168 // allocate a 8-bit DIB
169 width = FreeImage_GetWidth(dib);
170 height = FreeImage_GetHeight(dib);
171 new_dib = FreeImage_Allocate(width, height, 8);
172 if(NULL == new_dib) return NULL;
173
174 // build the dithering matrix
175 int l = (1 << order); // square of dither matrix order; the dimensions of the matrix
176 BYTE *matrix = (BYTE*)malloc(l*l * sizeof(BYTE));
177 for(int i = 0; i < l*l; i++) {
178 // according to "Purdue University: Digital Image Processing Laboratory: Image Halftoning, April 30th, 2006
179 matrix[i] = (BYTE)( 255 * (((double)dithervalue(i / l, i % l, order) + 0.5) / (l*l)) );
180 }
181
182 // perform the dithering
183 for(y = 0; y < height; y++) {
184 // scan left to right
185 bits = FreeImage_GetScanLine(dib, y);
186 new_bits = FreeImage_GetScanLine(new_dib, y);
187 for(x = 0; x < width; x++) {
188 if(bits[x] > matrix[(x % l) + l * (y % l)]) {
189 new_bits[x] = WHITE;
190 } else {
191 new_bits[x] = BLACK;
192 }
193 }
194 }
195
196 free(matrix);
197
198 return new_dib;
199 }
200
201 // ==========================================================
202 // Ordered clustered dot dithering
203 //
204
205 // NB : The predefined dither matrices are the same as matrices used in
206 // the Netpbm package (http://netpbm.sourceforge.net) and are defined in Ulichney's book.
207 // See also : The newsprint web site at http://www.cl.cam.ac.uk/~and1000/newsprint/
208 // for more technical info on this dithering technique
209 //
OrderedClusteredDot(FIBITMAP * dib,int order)210 static FIBITMAP* OrderedClusteredDot(FIBITMAP *dib, int order) {
211 // Order-3 clustered dithering matrix.
212 int cluster3[] = {
213 9,11,10, 8, 6, 7,
214 12,17,16, 5, 0, 1,
215 13,14,15, 4, 3, 2,
216 8, 6, 7, 9,11,10,
217 5, 0, 1,12,17,16,
218 4, 3, 2,13,14,15
219 };
220
221 // Order-4 clustered dithering matrix.
222 int cluster4[] = {
223 18,20,19,16,13,11,12,15,
224 27,28,29,22, 4, 3, 2, 9,
225 26,31,30,21, 5, 0, 1,10,
226 23,25,24,17, 8, 6, 7,14,
227 13,11,12,15,18,20,19,16,
228 4, 3, 2, 9,27,28,29,22,
229 5, 0, 1,10,26,31,30,21,
230 8, 6, 7,14,23,25,24,17
231 };
232
233 // Order-8 clustered dithering matrix.
234 int cluster8[] = {
235 64, 69, 77, 87, 86, 76, 68, 67, 63, 58, 50, 40, 41, 51, 59, 60,
236 70, 94,100,109,108, 99, 93, 75, 57, 33, 27, 18, 19, 28, 34, 52,
237 78,101,114,116,115,112, 98, 83, 49, 26, 13, 11, 12, 15, 29, 44,
238 88,110,123,124,125,118,107, 85, 39, 17, 4, 3, 2, 9, 20, 42,
239 89,111,122,127,126,117,106, 84, 38, 16, 5, 0, 1, 10, 21, 43,
240 79,102,119,121,120,113, 97, 82, 48, 25, 8, 6, 7, 14, 30, 45,
241 71, 95,103,104,105, 96, 92, 74, 56, 32, 24, 23, 22, 31, 35, 53,
242 65, 72, 80, 90, 91, 81, 73, 66, 62, 55, 47, 37, 36, 46, 54, 61,
243 63, 58, 50, 40, 41, 51, 59, 60, 64, 69, 77, 87, 86, 76, 68, 67,
244 57, 33, 27, 18, 19, 28, 34, 52, 70, 94,100,109,108, 99, 93, 75,
245 49, 26, 13, 11, 12, 15, 29, 44, 78,101,114,116,115,112, 98, 83,
246 39, 17, 4, 3, 2, 9, 20, 42, 88,110,123,124,125,118,107, 85,
247 38, 16, 5, 0, 1, 10, 21, 43, 89,111,122,127,126,117,106, 84,
248 48, 25, 8, 6, 7, 14, 30, 45, 79,102,119,121,120,113, 97, 82,
249 56, 32, 24, 23, 22, 31, 35, 53, 71, 95,103,104,105, 96, 92, 74,
250 62, 55, 47, 37, 36, 46, 54, 61, 65, 72, 80, 90, 91, 81, 73, 66
251 };
252
253 int x, y, pixel;
254 int width, height;
255 BYTE *bits, *new_bits;
256 FIBITMAP *new_dib = NULL;
257
258 // allocate a 8-bit DIB
259 width = FreeImage_GetWidth(dib);
260 height = FreeImage_GetHeight(dib);
261 new_dib = FreeImage_Allocate(width, height, 8);
262 if(NULL == new_dib) return NULL;
263
264 // select the dithering matrix
265 int *matrix = NULL;
266 switch(order) {
267 case 3:
268 matrix = &cluster3[0];
269 break;
270 case 4:
271 matrix = &cluster4[0];
272 break;
273 case 8:
274 matrix = &cluster8[0];
275 break;
276 default:
277 return NULL;
278 }
279
280 // scale the dithering matrix
281 int l = 2 * order;
282 int scale = 256 / (l * order);
283 for(y = 0; y < l; y++) {
284 for(x = 0; x < l; x++) {
285 matrix[y*l + x] *= scale;
286 }
287 }
288
289 // perform the dithering
290 for(y = 0; y < height; y++) {
291 // scan left to right
292 bits = FreeImage_GetScanLine(dib, y);
293 new_bits = FreeImage_GetScanLine(new_dib, y);
294 for(x = 0; x < width; x++) {
295 pixel = bits[x];
296 if(pixel >= matrix[(y % l) + l * (x % l)]) {
297 new_bits[x] = WHITE;
298 } else {
299 new_bits[x] = BLACK;
300 }
301 }
302 }
303
304 return new_dib;
305 }
306
307
308 // ==========================================================
309 // Halftoning function
310 //
311 FIBITMAP * DLL_CALLCONV
FreeImage_Dither(FIBITMAP * dib,FREE_IMAGE_DITHER algorithm)312 FreeImage_Dither(FIBITMAP *dib, FREE_IMAGE_DITHER algorithm) {
313 FIBITMAP *input = NULL, *dib8 = NULL;
314
315 if(!FreeImage_HasPixels(dib)) return NULL;
316
317 const unsigned bpp = FreeImage_GetBPP(dib);
318
319 if(bpp == 1) {
320 // Just clone the dib and adjust the palette if needed
321 FIBITMAP *new_dib = FreeImage_Clone(dib);
322 if(NULL == new_dib) return NULL;
323 if(FreeImage_GetColorType(new_dib) == FIC_PALETTE) {
324 // Build a monochrome palette
325 RGBQUAD *pal = FreeImage_GetPalette(new_dib);
326 pal[0].rgbRed = pal[0].rgbGreen = pal[0].rgbBlue = 0;
327 pal[1].rgbRed = pal[1].rgbGreen = pal[1].rgbBlue = 255;
328 }
329 return new_dib;
330 }
331
332 // Convert the input dib to a 8-bit greyscale dib
333 //
334 switch(bpp) {
335 case 8:
336 if(FreeImage_GetColorType(dib) == FIC_MINISBLACK) {
337 input = dib;
338 } else {
339 input = FreeImage_ConvertToGreyscale(dib);
340 }
341 break;
342 case 4:
343 case 16:
344 case 24:
345 case 32:
346 input = FreeImage_ConvertToGreyscale(dib);
347 break;
348 }
349 if(NULL == input) return NULL;
350
351 // Apply the dithering algorithm
352 switch(algorithm) {
353 case FID_FS:
354 dib8 = FloydSteinberg(input);
355 break;
356 case FID_BAYER4x4:
357 dib8 = OrderedDispersedDot(input, 2);
358 break;
359 case FID_BAYER8x8:
360 dib8 = OrderedDispersedDot(input, 3);
361 break;
362 case FID_BAYER16x16:
363 dib8 = OrderedDispersedDot(input, 4);
364 break;
365 case FID_CLUSTER6x6:
366 dib8 = OrderedClusteredDot(input, 3);
367 break;
368 case FID_CLUSTER8x8:
369 dib8 = OrderedClusteredDot(input, 4);
370 break;
371 case FID_CLUSTER16x16:
372 dib8 = OrderedClusteredDot(input, 8);
373 break;
374 }
375 if(input != dib) {
376 FreeImage_Unload(input);
377 }
378
379 // Build a greyscale palette (needed by threshold)
380 RGBQUAD *grey_pal = FreeImage_GetPalette(dib8);
381 for(int i = 0; i < 256; i++) {
382 grey_pal[i].rgbRed = (BYTE)i;
383 grey_pal[i].rgbGreen = (BYTE)i;
384 grey_pal[i].rgbBlue = (BYTE)i;
385 }
386
387 // Convert to 1-bit
388 FIBITMAP *new_dib = FreeImage_Threshold(dib8, 128);
389 FreeImage_Unload(dib8);
390
391 // copy metadata from src to dst
392 FreeImage_CloneMetadata(new_dib, dib);
393
394 return new_dib;
395 }
396
397 // ==========================================================
398 // Thresholding function
399 //
400 FIBITMAP * DLL_CALLCONV
FreeImage_Threshold(FIBITMAP * dib,BYTE T)401 FreeImage_Threshold(FIBITMAP *dib, BYTE T) {
402 FIBITMAP *dib8 = NULL;
403
404 if(!FreeImage_HasPixels(dib)) return NULL;
405
406 const unsigned bpp = FreeImage_GetBPP(dib);
407
408 if(bpp == 1) {
409 // Just clone the dib and adjust the palette if needed
410 FIBITMAP *new_dib = FreeImage_Clone(dib);
411 if(NULL == new_dib) return NULL;
412 if(FreeImage_GetColorType(new_dib) == FIC_PALETTE) {
413 // Build a monochrome palette
414 RGBQUAD *pal = FreeImage_GetPalette(new_dib);
415 pal[0].rgbRed = pal[0].rgbGreen = pal[0].rgbBlue = 0;
416 pal[1].rgbRed = pal[1].rgbGreen = pal[1].rgbBlue = 255;
417 }
418 return new_dib;
419 }
420
421 // Convert the input dib to a 8-bit greyscale dib
422 //
423 switch(bpp) {
424 case 8:
425 if(FreeImage_GetColorType(dib) == FIC_MINISBLACK) {
426 dib8 = dib;
427 } else {
428 dib8 = FreeImage_ConvertToGreyscale(dib);
429 }
430 break;
431 case 4:
432 case 16:
433 case 24:
434 case 32:
435 dib8 = FreeImage_ConvertToGreyscale(dib);
436 break;
437 }
438 if(NULL == dib8) return NULL;
439
440 // Allocate a new 1-bit DIB
441 int width = FreeImage_GetWidth(dib);
442 int height = FreeImage_GetHeight(dib);
443 FIBITMAP *new_dib = FreeImage_Allocate(width, height, 1);
444 if(NULL == new_dib) return NULL;
445 // Build a monochrome palette
446 RGBQUAD *pal = FreeImage_GetPalette(new_dib);
447 pal[0].rgbRed = pal[0].rgbGreen = pal[0].rgbBlue = 0;
448 pal[1].rgbRed = pal[1].rgbGreen = pal[1].rgbBlue = 255;
449
450 // Perform the thresholding
451 //
452 for(int y = 0; y < height; y++) {
453 BYTE *bits8 = FreeImage_GetScanLine(dib8, y);
454 BYTE *bits1 = FreeImage_GetScanLine(new_dib, y);
455 for(int x = 0; x < width; x++) {
456 if(bits8[x] < T) {
457 // Set bit(x, y) to 0
458 bits1[x >> 3] &= (0xFF7F >> (x & 0x7));
459 } else {
460 // Set bit(x, y) to 1
461 bits1[x >> 3] |= (0x80 >> (x & 0x7));
462 }
463 }
464 }
465 if(dib8 != dib) {
466 FreeImage_Unload(dib8);
467 }
468
469 // copy metadata from src to dst
470 FreeImage_CloneMetadata(new_dib, dib);
471
472 return new_dib;
473 }
474
475