1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 -
4 - Redistribution and use in source and binary forms, with or without
5 - modification, are permitted provided that the following conditions
6 - are met:
7 - 1. Redistributions of source code must retain the above copyright
8 - notice, this list of conditions and the following disclaimer.
9 - 2. Redistributions in binary form must reproduce the above
10 - copyright notice, this list of conditions and the following
11 - disclaimer in the documentation and/or other materials
12 - provided with the distribution.
13 -
14 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18 - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *====================================================================*/
26
27 /*!
28 * \file grayquant.c
29 * <pre>
30 *
31 * Thresholding from 8 bpp to 1 bpp
32 *
33 * Floyd-Steinberg dithering to binary
34 * PIX *pixDitherToBinary()
35 * PIX *pixDitherToBinarySpec()
36 * static void ditherToBinaryLow()
37 * void ditherToBinaryLineLow()
38 *
39 * Simple (pixelwise) binarization with fixed threshold
40 * PIX *pixThresholdToBinary()
41 * static void thresholdToBinaryLow()
42 * void thresholdToBinaryLineLow()
43 *
44 * Binarization with variable threshold
45 * PIX *pixVarThresholdToBinary()
46 *
47 * Binarization by adaptive mapping
48 * PIX *pixAdaptThresholdToBinary()
49 * PIX *pixAdaptThresholdToBinaryGen()
50 *
51 * Generate a binary mask from pixels of particular values
52 * PIX *pixGenerateMaskByValue()
53 * PIX *pixGenerateMaskByBand()
54 *
55 * Thresholding from 8 bpp to 2 bpp
56 *
57 * Floyd-Steinberg-like dithering to 2 bpp
58 * PIX *pixDitherTo2bpp()
59 * PIX *pixDitherTo2bppSpec()
60 * static void ditherTo2bppLow()
61 * static void ditherTo2bppLineLow()
62 * static l_int32 make8To2DitherTables()
63 *
64 * Simple (pixelwise) thresholding to 2 bpp with optional cmap
65 * PIX *pixThresholdTo2bpp()
66 * static void thresholdTo2bppLow()
67 *
68 * Simple (pixelwise) thresholding from 8 bpp to 4 bpp
69 * PIX *pixThresholdTo4bpp()
70 * static void thresholdTo4bppLow()
71 *
72 * Simple (pixelwise) quantization on 8 bpp grayscale
73 * PIX *pixThresholdOn8bpp()
74 *
75 * Arbitrary (pixelwise) thresholding from 8 bpp to 2, 4 or 8 bpp
76 * PIX *pixThresholdGrayArb()
77 *
78 * Quantization tables for linear thresholds of grayscale images
79 * l_int32 *makeGrayQuantIndexTable()
80 * static l_int32 *makeGrayQuantTargetTable()
81 *
82 * Quantization table for arbitrary thresholding of grayscale images
83 * l_int32 makeGrayQuantTableArb()
84 * static l_int32 makeGrayQuantColormapArb()
85 *
86 * Thresholding from 32 bpp rgb to 1 bpp
87 * (really color quantization, but it's better placed in this file)
88 * PIX *pixGenerateMaskByBand32()
89 * PIX *pixGenerateMaskByDiscr32()
90 *
91 * Histogram-based grayscale quantization
92 * PIX *pixGrayQuantFromHisto()
93 * static l_int32 numaFillCmapFromHisto()
94 *
95 * Color quantize grayscale image using existing colormap
96 * PIX *pixGrayQuantFromCmap()
97 * </pre>
98 */
99
100 #include <string.h>
101 #include <math.h>
102 #include "allheaders.h"
103
104 static void ditherToBinaryLow(l_uint32 *datad, l_int32 w, l_int32 h,
105 l_int32 wpld, l_uint32 *datas, l_int32 wpls,
106 l_uint32 *bufs1, l_uint32 *bufs2,
107 l_int32 lowerclip, l_int32 upperclip);
108 static void thresholdToBinaryLow(l_uint32 *datad, l_int32 w, l_int32 h,
109 l_int32 wpld, l_uint32 *datas, l_int32 d,
110 l_int32 wpls, l_int32 thresh);
111 static void ditherTo2bppLow(l_uint32 *datad, l_int32 w, l_int32 h, l_int32 wpld,
112 l_uint32 *datas, l_int32 wpls, l_uint32 *bufs1,
113 l_uint32 *bufs2, l_int32 *tabval, l_int32 *tab38,
114 l_int32 *tab14);
115 static void ditherTo2bppLineLow(l_uint32 *lined, l_int32 w, l_uint32 *bufs1,
116 l_uint32 *bufs2, l_int32 *tabval,
117 l_int32 *tab38, l_int32 *tab14,
118 l_int32 lastlineflag);
119 static l_int32 make8To2DitherTables(l_int32 **ptabval, l_int32 **ptab38,
120 l_int32 **ptab14, l_int32 cliptoblack,
121 l_int32 cliptowhite);
122 static void thresholdTo2bppLow(l_uint32 *datad, l_int32 h, l_int32 wpld,
123 l_uint32 *datas, l_int32 wpls, l_int32 *tab);
124 static void thresholdTo4bppLow(l_uint32 *datad, l_int32 h, l_int32 wpld,
125 l_uint32 *datas, l_int32 wpls, l_int32 *tab);
126 static l_int32 *makeGrayQuantTargetTable(l_int32 nlevels, l_int32 depth);
127 static l_int32 makeGrayQuantColormapArb(PIX *pixs, l_int32 *tab,
128 l_int32 outdepth, PIXCMAP **pcmap);
129 static l_int32 numaFillCmapFromHisto(NUMA *na, PIXCMAP *cmap,
130 l_float32 minfract, l_int32 maxsize,
131 l_int32 **plut);
132
133 #ifndef NO_CONSOLE_IO
134 #define DEBUG_UNROLLING 0
135 #endif /* ~NO_CONSOLE_IO */
136
137 /*------------------------------------------------------------------*
138 * Binarization by Floyd-Steinberg dithering *
139 *------------------------------------------------------------------*/
140 /*!
141 * \brief pixDitherToBinary()
142 *
143 * \param[in] pixs
144 * \return pixd dithered binary, or NULL on error
145 *
146 * The Floyd-Steinberg error diffusion dithering algorithm
147 * binarizes an 8 bpp grayscale image to a threshold of 128.
148 * If a pixel has a value above 127, it is binarized to white
149 * and the excess below 255 is subtracted from three
150 * neighboring pixels in the fractions 3/8 to i, j+1,
151 * 3/8 to i+1, j) and 1/4 to (i+1,j+1, truncating to 0
152 * if necessary. Likewise, if it the pixel has a value
153 * below 128, it is binarized to black and the excess above 0
154 * is added to the neighboring pixels, truncating to 255 if necessary.
155 *
156 * This function differs from straight dithering in that it allows
157 * clipping of grayscale to 0 or 255 if the values are
158 * sufficiently close, without distribution of the excess.
159 * This uses default values to specify the range of lower
160 * and upper values near 0 and 255, rsp that are clipped
161 * to black and white without propagating the excess.
162 * Not propagating the excess has the effect of reducing the
163 * snake patterns in parts of the image that are nearly black or white;
164 * however, it also prevents the attempt to reproduce gray for those values.
165 *
166 * The implementation is straightforward. It uses a pair of
167 * line buffers to avoid changing pixs. It is about the same speed
168 * as pixDitherToBinaryLUT(), which uses three LUTs.
169 */
170 PIX *
pixDitherToBinary(PIX * pixs)171 pixDitherToBinary(PIX *pixs)
172 {
173 PROCNAME("pixDitherToBinary");
174
175 if (!pixs)
176 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
177 if (pixGetDepth(pixs) != 8)
178 return (PIX *)ERROR_PTR("must be 8 bpp for dithering", procName, NULL);
179
180 return pixDitherToBinarySpec(pixs, DEFAULT_CLIP_LOWER_1,
181 DEFAULT_CLIP_UPPER_1);
182 }
183
184
185 /*!
186 * \brief pixDitherToBinarySpec()
187 *
188 * \param[in] pixs
189 * \param[in] lowerclip lower clip distance to black; use 0 for default
190 * \param[in] upperclip upper clip distance to white; use 0 for default
191 * \return pixd dithered binary, or NULL on error
192 *
193 * <pre>
194 * Notes:
195 * (1) See comments above in pixDitherToBinary() for details.
196 * (2) The input parameters lowerclip and upperclip specify the range
197 * of lower and upper values (near 0 and 255, rsp) that are
198 * clipped to black and white without propagating the excess.
199 * For that reason, lowerclip and upperclip should be small numbers.
200 * </pre>
201 */
202 PIX *
pixDitherToBinarySpec(PIX * pixs,l_int32 lowerclip,l_int32 upperclip)203 pixDitherToBinarySpec(PIX *pixs,
204 l_int32 lowerclip,
205 l_int32 upperclip)
206 {
207 l_int32 w, h, d, wplt, wpld;
208 l_uint32 *datat, *datad;
209 l_uint32 *bufs1, *bufs2;
210 PIX *pixt, *pixd;
211
212 PROCNAME("pixDitherToBinarySpec");
213
214 if (!pixs)
215 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
216 pixGetDimensions(pixs, &w, &h, &d);
217 if (d != 8)
218 return (PIX *)ERROR_PTR("must be 8 bpp for dithering", procName, NULL);
219 if (lowerclip < 0 || lowerclip > 255)
220 return (PIX *)ERROR_PTR("invalid value for lowerclip", procName, NULL);
221 if (upperclip < 0 || upperclip > 255)
222 return (PIX *)ERROR_PTR("invalid value for upperclip", procName, NULL);
223
224 if ((pixd = pixCreate(w, h, 1)) == NULL)
225 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
226 pixCopyResolution(pixd, pixs);
227 pixCopyInputFormat(pixd, pixs);
228 datad = pixGetData(pixd);
229 wpld = pixGetWpl(pixd);
230
231 /* Remove colormap if it exists */
232 if ((pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE)) == NULL) {
233 pixDestroy(&pixd);
234 return (PIX *)ERROR_PTR("pixt not made", procName, NULL);
235 }
236 datat = pixGetData(pixt);
237 wplt = pixGetWpl(pixt);
238
239 /* Two line buffers, 1 for current line and 2 for next line */
240 bufs1 = (l_uint32 *)LEPT_CALLOC(wplt, sizeof(l_uint32));
241 bufs2 = (l_uint32 *)LEPT_CALLOC(wplt, sizeof(l_uint32));
242 if (!bufs1 || !bufs2) {
243 LEPT_FREE(bufs1);
244 LEPT_FREE(bufs2);
245 pixDestroy(&pixd);
246 pixDestroy(&pixt);
247 return (PIX *)ERROR_PTR("bufs1, bufs2 not both made", procName, NULL);
248 }
249
250 ditherToBinaryLow(datad, w, h, wpld, datat, wplt, bufs1, bufs2,
251 lowerclip, upperclip);
252
253 LEPT_FREE(bufs1);
254 LEPT_FREE(bufs2);
255 pixDestroy(&pixt);
256 return pixd;
257 }
258
259
260 /*!
261 * \brief ditherToBinaryLow()
262 *
263 * See comments in pixDitherToBinary() in binarize.c
264 */
265 static void
ditherToBinaryLow(l_uint32 * datad,l_int32 w,l_int32 h,l_int32 wpld,l_uint32 * datas,l_int32 wpls,l_uint32 * bufs1,l_uint32 * bufs2,l_int32 lowerclip,l_int32 upperclip)266 ditherToBinaryLow(l_uint32 *datad,
267 l_int32 w,
268 l_int32 h,
269 l_int32 wpld,
270 l_uint32 *datas,
271 l_int32 wpls,
272 l_uint32 *bufs1,
273 l_uint32 *bufs2,
274 l_int32 lowerclip,
275 l_int32 upperclip)
276 {
277 l_int32 i;
278 l_uint32 *lined;
279
280 /* do all lines except last line */
281 memcpy(bufs2, datas, 4 * wpls); /* prime the buffer */
282 for (i = 0; i < h - 1; i++) {
283 memcpy(bufs1, bufs2, 4 * wpls);
284 memcpy(bufs2, datas + (i + 1) * wpls, 4 * wpls);
285 lined = datad + i * wpld;
286 ditherToBinaryLineLow(lined, w, bufs1, bufs2, lowerclip, upperclip, 0);
287 }
288
289 /* do last line */
290 memcpy(bufs1, bufs2, 4 * wpls);
291 lined = datad + (h - 1) * wpld;
292 ditherToBinaryLineLow(lined, w, bufs1, bufs2, lowerclip, upperclip, 1);
293 }
294
295
296 /*!
297 * \brief ditherToBinaryLineLow()
298 *
299 * \param[in] lined ptr to beginning of dest line
300 * w (width of image in pixels
301 * \param[in] bufs1 buffer of current source line
302 * \param[in] bufs2 buffer of next source line
303 * \param[in] lowerclip lower clip distance to black
304 * \param[in] upperclip upper clip distance to white
305 * \param[in] lastlineflag 0 if not last dest line, 1 if last dest line
306 * \return void
307 *
308 * Dispatches FS error diffusion dithering for
309 * a single line of the image. If lastlineflag == 0,
310 * both source buffers are used; otherwise, only bufs1
311 * is used. We use source buffers because the error
312 * is propagated into them, and we don't want to change
313 * the input src image.
314 *
315 * We break dithering out line by line to make it
316 * easier to combine functions like interpolative
317 * scaling and error diffusion dithering, as such a
318 * combination of operations obviates the need to
319 * generate a 2x grayscale image as an intermediary.
320 */
321 void
ditherToBinaryLineLow(l_uint32 * lined,l_int32 w,l_uint32 * bufs1,l_uint32 * bufs2,l_int32 lowerclip,l_int32 upperclip,l_int32 lastlineflag)322 ditherToBinaryLineLow(l_uint32 *lined,
323 l_int32 w,
324 l_uint32 *bufs1,
325 l_uint32 *bufs2,
326 l_int32 lowerclip,
327 l_int32 upperclip,
328 l_int32 lastlineflag)
329 {
330 l_int32 j;
331 l_int32 oval, eval;
332 l_uint8 fval1, fval2, rval, bval, dval;
333
334 if (lastlineflag == 0) {
335 for (j = 0; j < w - 1; j++) {
336 oval = GET_DATA_BYTE(bufs1, j);
337 if (oval > 127) { /* binarize to OFF */
338 if ((eval = 255 - oval) > upperclip) {
339 /* subtract from neighbors */
340 fval1 = (3 * eval) / 8;
341 fval2 = eval / 4;
342 rval = GET_DATA_BYTE(bufs1, j + 1);
343 rval = L_MAX(0, rval - fval1);
344 SET_DATA_BYTE(bufs1, j + 1, rval);
345 bval = GET_DATA_BYTE(bufs2, j);
346 bval = L_MAX(0, bval - fval1);
347 SET_DATA_BYTE(bufs2, j, bval);
348 dval = GET_DATA_BYTE(bufs2, j + 1);
349 dval = L_MAX(0, dval - fval2);
350 SET_DATA_BYTE(bufs2, j + 1, dval);
351 }
352 } else { /* oval <= 127; binarize to ON */
353 SET_DATA_BIT(lined, j); /* ON pixel */
354 if (oval > lowerclip) {
355 /* add to neighbors */
356 fval1 = (3 * oval) / 8;
357 fval2 = oval / 4;
358 rval = GET_DATA_BYTE(bufs1, j + 1);
359 rval = L_MIN(255, rval + fval1);
360 SET_DATA_BYTE(bufs1, j + 1, rval);
361 bval = GET_DATA_BYTE(bufs2, j);
362 bval = L_MIN(255, bval + fval1);
363 SET_DATA_BYTE(bufs2, j, bval);
364 dval = GET_DATA_BYTE(bufs2, j + 1);
365 dval = L_MIN(255, dval + fval2);
366 SET_DATA_BYTE(bufs2, j + 1, dval);
367 }
368 }
369 }
370
371 /* do last column: j = w - 1 */
372 oval = GET_DATA_BYTE(bufs1, j);
373 if (oval > 127) { /* binarize to OFF */
374 if ((eval = 255 - oval) > upperclip) {
375 /* subtract from neighbors */
376 fval1 = (3 * eval) / 8;
377 bval = GET_DATA_BYTE(bufs2, j);
378 bval = L_MAX(0, bval - fval1);
379 SET_DATA_BYTE(bufs2, j, bval);
380 }
381 } else { /*oval <= 127; binarize to ON */
382 SET_DATA_BIT(lined, j); /* ON pixel */
383 if (oval > lowerclip) {
384 /* add to neighbors */
385 fval1 = (3 * oval) / 8;
386 bval = GET_DATA_BYTE(bufs2, j);
387 bval = L_MIN(255, bval + fval1);
388 SET_DATA_BYTE(bufs2, j, bval);
389 }
390 }
391 } else { /* lastlineflag == 1 */
392 for (j = 0; j < w - 1; j++) {
393 oval = GET_DATA_BYTE(bufs1, j);
394 if (oval > 127) { /* binarize to OFF */
395 if ((eval = 255 - oval) > upperclip) {
396 /* subtract from neighbors */
397 fval1 = (3 * eval) / 8;
398 rval = GET_DATA_BYTE(bufs1, j + 1);
399 rval = L_MAX(0, rval - fval1);
400 SET_DATA_BYTE(bufs1, j + 1, rval);
401 }
402 } else { /* oval <= 127; binarize to ON */
403 SET_DATA_BIT(lined, j); /* ON pixel */
404 if (oval > lowerclip) {
405 /* add to neighbors */
406 fval1 = (3 * oval) / 8;
407 rval = GET_DATA_BYTE(bufs1, j + 1);
408 rval = L_MIN(255, rval + fval1);
409 SET_DATA_BYTE(bufs1, j + 1, rval);
410 }
411 }
412 }
413
414 /* do last pixel: (i, j) = (h - 1, w - 1) */
415 oval = GET_DATA_BYTE(bufs1, j);
416 if (oval < 128)
417 SET_DATA_BIT(lined, j); /* ON pixel */
418 }
419 }
420
421
422 /*------------------------------------------------------------------*
423 * Simple (pixelwise) binarization with fixed threshold *
424 *------------------------------------------------------------------*/
425 /*!
426 * \brief pixThresholdToBinary()
427 *
428 * \param[in] pixs 4 or 8 bpp
429 * \param[in] thresh threshold value
430 * \return pixd 1 bpp, or NULL on error
431 *
432 * <pre>
433 * Notes:
434 * (1) If the source pixel is less than the threshold value,
435 * the dest will be 1; otherwise, it will be 0.
436 * (2) For example, for 8 bpp src pix, if %thresh == 256, the dest
437 * 1 bpp pix is all ones (fg), and if %thresh == 0, the dest
438 * pix is all zeros (bg).
439 *
440 * </pre>
441 */
442 PIX *
pixThresholdToBinary(PIX * pixs,l_int32 thresh)443 pixThresholdToBinary(PIX *pixs,
444 l_int32 thresh)
445 {
446 l_int32 d, w, h, wplt, wpld;
447 l_uint32 *datat, *datad;
448 PIX *pixt, *pixd;
449
450 PROCNAME("pixThresholdToBinary");
451
452 if (!pixs)
453 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
454 pixGetDimensions(pixs, &w, &h, &d);
455 if (d != 4 && d != 8)
456 return (PIX *)ERROR_PTR("pixs must be 4 or 8 bpp", procName, NULL);
457 if (thresh < 0)
458 return (PIX *)ERROR_PTR("thresh must be non-negative", procName, NULL);
459 if (d == 4 && thresh > 16)
460 return (PIX *)ERROR_PTR("4 bpp thresh not in {0-16}", procName, NULL);
461 if (d == 8 && thresh > 256)
462 return (PIX *)ERROR_PTR("8 bpp thresh not in {0-256}", procName, NULL);
463
464 if ((pixd = pixCreate(w, h, 1)) == NULL)
465 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
466 pixCopyResolution(pixd, pixs);
467 pixCopyInputFormat(pixd, pixs);
468 datad = pixGetData(pixd);
469 wpld = pixGetWpl(pixd);
470
471 /* Remove colormap if it exists. If there is a colormap,
472 * pixt will be 8 bpp regardless of the depth of pixs. */
473 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
474 datat = pixGetData(pixt);
475 wplt = pixGetWpl(pixt);
476 if (pixGetColormap(pixs) && d == 4) { /* promoted to 8 bpp */
477 d = 8;
478 thresh *= 16;
479 }
480
481 thresholdToBinaryLow(datad, w, h, wpld, datat, d, wplt, thresh);
482 pixDestroy(&pixt);
483 return pixd;
484 }
485
486
487 /*!
488 * \brief thresholdToBinaryLow()
489 *
490 * If the source pixel is less than thresh,
491 * the dest will be 1; otherwise, it will be 0
492 */
493 static void
thresholdToBinaryLow(l_uint32 * datad,l_int32 w,l_int32 h,l_int32 wpld,l_uint32 * datas,l_int32 d,l_int32 wpls,l_int32 thresh)494 thresholdToBinaryLow(l_uint32 *datad,
495 l_int32 w,
496 l_int32 h,
497 l_int32 wpld,
498 l_uint32 *datas,
499 l_int32 d,
500 l_int32 wpls,
501 l_int32 thresh)
502 {
503 l_int32 i;
504 l_uint32 *lines, *lined;
505
506 for (i = 0; i < h; i++) {
507 lines = datas + i * wpls;
508 lined = datad + i * wpld;
509 thresholdToBinaryLineLow(lined, w, lines, d, thresh);
510 }
511 }
512
513
514 /*
515 * thresholdToBinaryLineLow()
516 *
517 */
518 void
thresholdToBinaryLineLow(l_uint32 * lined,l_int32 w,l_uint32 * lines,l_int32 d,l_int32 thresh)519 thresholdToBinaryLineLow(l_uint32 *lined,
520 l_int32 w,
521 l_uint32 *lines,
522 l_int32 d,
523 l_int32 thresh)
524 {
525 l_int32 j, k, gval, scount, dcount;
526 l_uint32 sword, dword;
527
528 PROCNAME("thresholdToBinaryLineLow");
529
530 switch (d)
531 {
532 case 4:
533 /* Unrolled as 4 source words, 1 dest word */
534 for (j = 0, scount = 0, dcount = 0; j + 31 < w; j += 32) {
535 dword = 0;
536 for (k = 0; k < 4; k++) {
537 sword = lines[scount++];
538 dword <<= 8;
539 gval = (sword >> 28) & 0xf;
540 /* Trick used here and below: if gval < thresh then
541 * gval - thresh < 0, so its high-order bit is 1, and
542 * ((gval - thresh) >> 31) & 1 == 1; likewise, if
543 * gval >= thresh, then ((gval - thresh) >> 31) & 1 == 0
544 * Doing it this way avoids a random (and thus easily
545 * mispredicted) branch on each pixel. */
546 dword |= ((gval - thresh) >> 24) & 128;
547 gval = (sword >> 24) & 0xf;
548 dword |= ((gval - thresh) >> 25) & 64;
549 gval = (sword >> 20) & 0xf;
550 dword |= ((gval - thresh) >> 26) & 32;
551 gval = (sword >> 16) & 0xf;
552 dword |= ((gval - thresh) >> 27) & 16;
553 gval = (sword >> 12) & 0xf;
554 dword |= ((gval - thresh) >> 28) & 8;
555 gval = (sword >> 8) & 0xf;
556 dword |= ((gval - thresh) >> 29) & 4;
557 gval = (sword >> 4) & 0xf;
558 dword |= ((gval - thresh) >> 30) & 2;
559 gval = sword & 0xf;
560 dword |= ((gval - thresh) >> 31) & 1;
561 }
562 lined[dcount++] = dword;
563 }
564
565 if (j < w) {
566 dword = 0;
567 for (; j < w; j++) {
568 if ((j & 7) == 0) {
569 sword = lines[scount++];
570 }
571 gval = (sword >> 28) & 0xf;
572 sword <<= 4;
573 dword |= (((gval - thresh) >> 31) & 1) << (31 - (j & 31));
574 }
575 lined[dcount] = dword;
576 }
577 #if DEBUG_UNROLLING
578 #define CHECK_BIT(a, b, c) if (GET_DATA_BIT(a, b) != c) { \
579 fprintf(stderr, "Error: mismatch at %d/%d(%d), %d vs %d\n", \
580 j, w, d, GET_DATA_BIT(a, b), c); }
581 for (j = 0; j < w; j++) {
582 gval = GET_DATA_QBIT(lines, j);
583 CHECK_BIT(lined, j, gval < thresh ? 1 : 0);
584 }
585 #endif
586 break;
587 case 8:
588 /* Unrolled as 8 source words, 1 dest word */
589 for (j = 0, scount = 0, dcount = 0; j + 31 < w; j += 32) {
590 dword = 0;
591 for (k = 0; k < 8; k++) {
592 sword = lines[scount++];
593 dword <<= 4;
594 gval = (sword >> 24) & 0xff;
595 dword |= ((gval - thresh) >> 28) & 8;
596 gval = (sword >> 16) & 0xff;
597 dword |= ((gval - thresh) >> 29) & 4;
598 gval = (sword >> 8) & 0xff;
599 dword |= ((gval - thresh) >> 30) & 2;
600 gval = sword & 0xff;
601 dword |= ((gval - thresh) >> 31) & 1;
602 }
603 lined[dcount++] = dword;
604 }
605
606 if (j < w) {
607 dword = 0;
608 for (; j < w; j++) {
609 if ((j & 3) == 0) {
610 sword = lines[scount++];
611 }
612 gval = (sword >> 24) & 0xff;
613 sword <<= 8;
614 dword |= (((gval - thresh) >> 31) & 1) << (31 - (j & 31));
615 }
616 lined[dcount] = dword;
617 }
618 #if DEBUG_UNROLLING
619 for (j = 0; j < w; j++) {
620 gval = GET_DATA_BYTE(lines, j);
621 CHECK_BIT(lined, j, gval < thresh ? 1 : 0);
622 }
623 #undef CHECK_BIT
624 #endif
625 break;
626 default:
627 L_ERROR("src depth not 4 or 8 bpp\n", procName);
628 break;
629 }
630 }
631
632
633 /*------------------------------------------------------------------*
634 * Binarization with variable threshold *
635 *------------------------------------------------------------------*/
636 /*!
637 * \brief pixVarThresholdToBinary()
638 *
639 * \param[in] pixs 8 bpp
640 * \param[in] pixg 8 bpp; contains threshold values for each pixel
641 * \return pixd 1 bpp, or NULL on error
642 *
643 * <pre>
644 * Notes:
645 * (1) If the pixel in pixs is less than the corresponding pixel
646 * in pixg, the dest will be 1; otherwise it will be 0.
647 * </pre>
648 */
649 PIX *
pixVarThresholdToBinary(PIX * pixs,PIX * pixg)650 pixVarThresholdToBinary(PIX *pixs,
651 PIX *pixg)
652 {
653 l_int32 i, j, vals, valg, w, h, d, wpls, wplg, wpld;
654 l_uint32 *datas, *datag, *datad, *lines, *lineg, *lined;
655 PIX *pixd;
656
657 PROCNAME("pixVarThresholdToBinary");
658
659 if (!pixs)
660 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
661 if (!pixg)
662 return (PIX *)ERROR_PTR("pixg not defined", procName, NULL);
663 if (!pixSizesEqual(pixs, pixg))
664 return (PIX *)ERROR_PTR("pix sizes not equal", procName, NULL);
665 pixGetDimensions(pixs, &w, &h, &d);
666 if (d != 8)
667 return (PIX *)ERROR_PTR("pixs must be 8 bpp", procName, NULL);
668
669 pixd = pixCreate(w, h, 1);
670 pixCopyResolution(pixd, pixs);
671 pixCopyInputFormat(pixd, pixs);
672 datad = pixGetData(pixd);
673 wpld = pixGetWpl(pixd);
674 datas = pixGetData(pixs);
675 wpls = pixGetWpl(pixs);
676 datag = pixGetData(pixg);
677 wplg = pixGetWpl(pixg);
678 for (i = 0; i < h; i++) {
679 lines = datas + i * wpls;
680 lineg = datag + i * wplg;
681 lined = datad + i * wpld;
682 for (j = 0; j < w; j++) {
683 vals = GET_DATA_BYTE(lines, j);
684 valg = GET_DATA_BYTE(lineg, j);
685 if (vals < valg)
686 SET_DATA_BIT(lined, j);
687 }
688 }
689
690 return pixd;
691 }
692
693
694 /*------------------------------------------------------------------*
695 * Binarization by adaptive mapping *
696 *------------------------------------------------------------------*/
697 /*!
698 * \brief pixAdaptThresholdToBinary()
699 *
700 * \param[in] pixs 8 bpp
701 * \param[in] pixm [optional] 1 bpp image mask; can be null
702 * \param[in] gamma gamma correction; must be > 0.0; typically ~1.0
703 * \return pixd 1 bpp, or NULL on error
704 *
705 * <pre>
706 * Notes:
707 * (1) This is a simple convenience function for doing adaptive
708 * thresholding on a grayscale image with variable background.
709 * It uses default parameters appropriate for typical text images.
710 * (2) %pixm is a 1 bpp mask over "image" regions, which are not
711 * expected to have a white background. The mask inhibits
712 * background finding under the fg pixels of the mask. For
713 * images with both text and image, the image regions would
714 * be binarized (or quantized) by a different set of operations.
715 * (3) As %gamma is increased, the foreground pixels are reduced.
716 * (4) Under the covers: The default background value for normalization
717 * is 200, so we choose 170 for 'maxval' in pixGammaTRC. Likewise,
718 * the default foreground threshold for normalization is 60,
719 * so we choose 50 for 'minval' in pixGammaTRC. Because
720 * 170 was mapped to 255, choosing 200 for the threshold is
721 * quite safe for avoiding speckle noise from the background.
722 * </pre>
723 */
724 PIX *
pixAdaptThresholdToBinary(PIX * pixs,PIX * pixm,l_float32 gamma)725 pixAdaptThresholdToBinary(PIX *pixs,
726 PIX *pixm,
727 l_float32 gamma)
728 {
729 PROCNAME("pixAdaptThresholdToBinary");
730
731 if (!pixs || pixGetDepth(pixs) != 8)
732 return (PIX *)ERROR_PTR("pixs undefined or not 8 bpp", procName, NULL);
733
734 return pixAdaptThresholdToBinaryGen(pixs, pixm, gamma, 50, 170, 200);
735 }
736
737
738 /*!
739 * \brief pixAdaptThresholdToBinaryGen()
740 *
741 * \param[in] pixs 8 bpp
742 * \param[in] pixm [optional] 1 bpp image mask; can be null
743 * \param[in] gamma gamma correction; must be > 0.0; typically ~1.0
744 * \param[in] blackval dark value to set to black (0)
745 * \param[in] whiteval light value to set to white (255)
746 * \param[in] thresh final threshold for binarization
747 * \return pixd 1 bpp, or NULL on error
748 *
749 * <pre>
750 * Notes:
751 * (1) This is a convenience function for doing adaptive thresholding
752 * on a grayscale image with variable background. Also see notes
753 * in pixAdaptThresholdToBinary().
754 * (2) Reducing %gamma increases the foreground (text) pixels.
755 * Use a low value (e.g., 0.5) for images with light text.
756 * (3) For normal images, see default args in pixAdaptThresholdToBinary().
757 * For images with very light text, these values are appropriate:
758 * gamma ~0.5
759 * blackval ~70
760 * whiteval ~190
761 * thresh ~200
762 * </pre>
763 */
764 PIX *
pixAdaptThresholdToBinaryGen(PIX * pixs,PIX * pixm,l_float32 gamma,l_int32 blackval,l_int32 whiteval,l_int32 thresh)765 pixAdaptThresholdToBinaryGen(PIX *pixs,
766 PIX *pixm,
767 l_float32 gamma,
768 l_int32 blackval,
769 l_int32 whiteval,
770 l_int32 thresh)
771 {
772 PIX *pix1, *pixd;
773
774 PROCNAME("pixAdaptThresholdToBinaryGen");
775
776 if (!pixs || pixGetDepth(pixs) != 8)
777 return (PIX *)ERROR_PTR("pixs undefined or not 8 bpp", procName, NULL);
778
779 pix1 = pixBackgroundNormSimple(pixs, pixm, NULL);
780 pixGammaTRC(pix1, pix1, gamma, blackval, whiteval);
781 pixd = pixThresholdToBinary(pix1, thresh);
782 pixDestroy(&pix1);
783 return pixd;
784 }
785
786
787 /*--------------------------------------------------------------------*
788 * Generate a binary mask from pixels of particular value(s) *
789 *--------------------------------------------------------------------*/
790 /*!
791 * \brief pixGenerateMaskByValue()
792 *
793 * \param[in] pixs 2, 4 or 8 bpp, or colormapped
794 * \param[in] val of pixels for which we set 1 in dest
795 * \param[in] usecmap 1 to retain cmap values; 0 to convert to gray
796 * \return pixd 1 bpp, or NULL on error
797 *
798 * <pre>
799 * Notes:
800 * (1) %val is the pixel value that we are selecting. It can be
801 * either a gray value or a colormap index.
802 * (2) If pixs is colormapped, %usecmap determines if the colormap
803 * index values are used, or if the colormap is removed to gray and
804 * the gray values are used. For the latter, it generates
805 * an approximate grayscale value for each pixel, and then looks
806 * for gray pixels with the value %val.
807 * </pre>
808 */
809 PIX *
pixGenerateMaskByValue(PIX * pixs,l_int32 val,l_int32 usecmap)810 pixGenerateMaskByValue(PIX *pixs,
811 l_int32 val,
812 l_int32 usecmap)
813 {
814 l_int32 i, j, w, h, d, wplg, wpld;
815 l_uint32 *datag, *datad, *lineg, *lined;
816 PIX *pixg, *pixd;
817
818 PROCNAME("pixGenerateMaskByValue");
819
820 if (!pixs)
821 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
822 d = pixGetDepth(pixs);
823 if (d != 2 && d != 4 && d != 8)
824 return (PIX *)ERROR_PTR("not 2, 4 or 8 bpp", procName, NULL);
825
826 if (!usecmap && pixGetColormap(pixs))
827 pixg = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
828 else
829 pixg = pixClone(pixs);
830 pixGetDimensions(pixg, &w, &h, &d);
831 if (d == 8 && (val < 0 || val > 255)) {
832 pixDestroy(&pixg);
833 return (PIX *)ERROR_PTR("val out of 8 bpp range", procName, NULL);
834 }
835 if (d == 4 && (val < 0 || val > 15)) {
836 pixDestroy(&pixg);
837 return (PIX *)ERROR_PTR("val out of 4 bpp range", procName, NULL);
838 }
839 if (d == 2 && (val < 0 || val > 3)) {
840 pixDestroy(&pixg);
841 return (PIX *)ERROR_PTR("val out of 2 bpp range", procName, NULL);
842 }
843
844 pixd = pixCreate(w, h, 1);
845 pixCopyResolution(pixd, pixg);
846 pixCopyInputFormat(pixd, pixs);
847 datag = pixGetData(pixg);
848 wplg = pixGetWpl(pixg);
849 datad = pixGetData(pixd);
850 wpld = pixGetWpl(pixd);
851 for (i = 0; i < h; i++) {
852 lineg = datag + i * wplg;
853 lined = datad + i * wpld;
854 for (j = 0; j < w; j++) {
855 if (d == 8) {
856 if (GET_DATA_BYTE(lineg, j) == val)
857 SET_DATA_BIT(lined, j);
858 } else if (d == 4) {
859 if (GET_DATA_QBIT(lineg, j) == val)
860 SET_DATA_BIT(lined, j);
861 } else { /* d == 2 */
862 if (GET_DATA_DIBIT(lineg, j) == val)
863 SET_DATA_BIT(lined, j);
864 }
865 }
866 }
867
868 pixDestroy(&pixg);
869 return pixd;
870 }
871
872
873 /*!
874 * \brief pixGenerateMaskByBand()
875 *
876 * \param[in] pixs 2, 4 or 8 bpp, or colormapped
877 * \param[in] lower, upper two pixel values from which a range, either
878 * between (inband) or outside of (!inband),
879 * determines which pixels in pixs cause us to
880 * set a 1 in the dest mask
881 * \param[in] inband 1 for finding pixels in [lower, upper];
882 * 0 for finding pixels in [0, lower) union (upper, 255]
883 * \param[in] usecmap 1 to retain cmap values; 0 to convert to gray
884 * \return pixd 1 bpp, or NULL on error
885 *
886 * <pre>
887 * Notes:
888 * (1) Generates a 1 bpp mask pixd, the same size as pixs, where
889 * the fg pixels in the mask are those either within the specified
890 * band (for inband == 1) or outside the specified band
891 * (for inband == 0).
892 * (2) If pixs is colormapped, %usecmap determines if the colormap
893 * values are used, or if the colormap is removed to gray and
894 * the gray values are used. For the latter, it generates
895 * an approximate grayscale value for each pixel, and then looks
896 * for gray pixels with the value %val.
897 * </pre>
898 */
899 PIX *
pixGenerateMaskByBand(PIX * pixs,l_int32 lower,l_int32 upper,l_int32 inband,l_int32 usecmap)900 pixGenerateMaskByBand(PIX *pixs,
901 l_int32 lower,
902 l_int32 upper,
903 l_int32 inband,
904 l_int32 usecmap)
905 {
906 l_int32 i, j, w, h, d, wplg, wpld, val;
907 l_uint32 *datag, *datad, *lineg, *lined;
908 PIX *pixg, *pixd;
909
910 PROCNAME("pixGenerateMaskByBand");
911
912 if (!pixs)
913 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
914 d = pixGetDepth(pixs);
915 if (d != 2 && d != 4 && d != 8)
916 return (PIX *)ERROR_PTR("not 2, 4 or 8 bpp", procName, NULL);
917 if (lower < 0 || lower > upper)
918 return (PIX *)ERROR_PTR("lower < 0 or lower > upper!", procName, NULL);
919
920 if (!usecmap && pixGetColormap(pixs))
921 pixg = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
922 else
923 pixg = pixClone(pixs);
924 pixGetDimensions(pixg, &w, &h, &d);
925 if (d == 8 && upper > 255) {
926 pixDestroy(&pixg);
927 return (PIX *)ERROR_PTR("d == 8 and upper > 255", procName, NULL);
928 }
929 if (d == 4 && upper > 15) {
930 pixDestroy(&pixg);
931 return (PIX *)ERROR_PTR("d == 4 and upper > 15", procName, NULL);
932 }
933 if (d == 2 && upper > 3) {
934 pixDestroy(&pixg);
935 return (PIX *)ERROR_PTR("d == 2 and upper > 3", procName, NULL);
936 }
937
938 pixd = pixCreate(w, h, 1);
939 pixCopyResolution(pixd, pixg);
940 pixCopyInputFormat(pixd, pixs);
941 datag = pixGetData(pixg);
942 wplg = pixGetWpl(pixg);
943 datad = pixGetData(pixd);
944 wpld = pixGetWpl(pixd);
945 for (i = 0; i < h; i++) {
946 lineg = datag + i * wplg;
947 lined = datad + i * wpld;
948 for (j = 0; j < w; j++) {
949 if (d == 8)
950 val = GET_DATA_BYTE(lineg, j);
951 else if (d == 4)
952 val = GET_DATA_QBIT(lineg, j);
953 else /* d == 2 */
954 val = GET_DATA_DIBIT(lineg, j);
955 if (inband) {
956 if (val >= lower && val <= upper)
957 SET_DATA_BIT(lined, j);
958 } else { /* out of band */
959 if (val < lower || val > upper)
960 SET_DATA_BIT(lined, j);
961 }
962 }
963 }
964
965 pixDestroy(&pixg);
966 return pixd;
967 }
968
969
970 /*------------------------------------------------------------------*
971 * Thresholding to 2 bpp by dithering *
972 *------------------------------------------------------------------*/
973 /*!
974 * \brief pixDitherTo2bpp()
975 *
976 * \param[in] pixs 8 bpp
977 * \param[in] cmapflag 1 to generate a colormap
978 * \return pixd dithered 2 bpp, or NULL on error
979 *
980 * An analog of the Floyd-Steinberg error diffusion dithering
981 * algorithm is used to "dibitize" an 8 bpp grayscale image
982 * to 2 bpp, using equally spaced gray values of 0, 85, 170, and 255,
983 * which are served by thresholds of 43, 128 and 213.
984 * If cmapflag == 1, the colormap values are set to 0, 85, 170 and 255.
985 * If a pixel has a value between 0 and 42, it is dibitized
986 * to 0, and the excess above 0 is added to the
987 * three neighboring pixels, in the fractions 3/8 to i, j+1,
988 * 3/8 to i+1, j) and 1/4 to (i+1, j+1, truncating to 255 if
989 * necessary. If a pixel has a value between 43 and 127, it is
990 * dibitized to 1, and the excess above 85 is added to the three
991 * neighboring pixels as before. If the value is below 85, the
992 * excess is subtracted. With a value between 128
993 * and 212, it is dibitized to 2, with the excess on either side
994 * of 170 distributed as before. Finally, with a value between
995 * 213 and 255, it is dibitized to 3, with the excess below 255
996 * subtracted from the neighbors. We always truncate to 0 or 255.
997 * The details can be seen in the lookup table generation.
998 *
999 * This function differs from straight dithering in that it allows
1000 * clipping of grayscale to 0 or 255 if the values are
1001 * sufficiently close, without distribution of the excess.
1002 * This uses default values from pix.h to specify the range of lower
1003 * and upper values near 0 and 255, rsp that are clipped to black
1004 * and white without propagating the excess.
1005 * Not propagating the excess has the effect of reducing the snake
1006 * patterns in parts of the image that are nearly black or white;
1007 * however, it also prevents any attempt to reproduce gray for those values.
1008 *
1009 * The implementation uses 3 lookup tables for simplicity, and
1010 * a pair of line buffers to avoid modifying pixs.
1011 */
1012 PIX *
pixDitherTo2bpp(PIX * pixs,l_int32 cmapflag)1013 pixDitherTo2bpp(PIX *pixs,
1014 l_int32 cmapflag)
1015 {
1016 PROCNAME("pixDitherTo2bpp");
1017
1018 if (!pixs)
1019 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
1020 if (pixGetDepth(pixs) != 8)
1021 return (PIX *)ERROR_PTR("must be 8 bpp for dithering", procName, NULL);
1022
1023 return pixDitherTo2bppSpec(pixs, DEFAULT_CLIP_LOWER_2,
1024 DEFAULT_CLIP_UPPER_2, cmapflag);
1025 }
1026
1027
1028 /*!
1029 * \brief pixDitherTo2bppSpec()
1030 *
1031 * \param[in] pixs 8 bpp
1032 * \param[in] lowerclip lower clip distance to black; use 0 for default
1033 * \param[in] upperclip upper clip distance to white; use 0 for default
1034 * \param[in] cmapflag 1 to generate a colormap
1035 * \return pixd dithered 2 bpp, or NULL on error
1036 *
1037 * <pre>
1038 * Notes:
1039 * (1) See comments above in pixDitherTo2bpp() for details.
1040 * (2) The input parameters lowerclip and upperclip specify the range
1041 * of lower and upper values (near 0 and 255, rsp) that are
1042 * clipped to black and white without propagating the excess.
1043 * For that reason, lowerclip and upperclip should be small numbers.
1044 * </pre>
1045 */
1046 PIX *
pixDitherTo2bppSpec(PIX * pixs,l_int32 lowerclip,l_int32 upperclip,l_int32 cmapflag)1047 pixDitherTo2bppSpec(PIX *pixs,
1048 l_int32 lowerclip,
1049 l_int32 upperclip,
1050 l_int32 cmapflag)
1051 {
1052 l_int32 w, h, d, wplt, wpld;
1053 l_int32 *tabval, *tab38, *tab14;
1054 l_uint32 *datat, *datad;
1055 l_uint32 *bufs1, *bufs2;
1056 PIX *pixt, *pixd;
1057 PIXCMAP *cmap;
1058
1059 PROCNAME("pixDitherTo2bppSpec");
1060
1061 if (!pixs)
1062 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
1063 pixGetDimensions(pixs, &w, &h, &d);
1064 if (d != 8)
1065 return (PIX *)ERROR_PTR("must be 8 bpp for dithering", procName, NULL);
1066 if (lowerclip < 0 || lowerclip > 255)
1067 return (PIX *)ERROR_PTR("invalid value for lowerclip", procName, NULL);
1068 if (upperclip < 0 || upperclip > 255)
1069 return (PIX *)ERROR_PTR("invalid value for upperclip", procName, NULL);
1070
1071 if ((pixd = pixCreate(w, h, 2)) == NULL)
1072 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
1073 pixCopyResolution(pixd, pixs);
1074 pixCopyInputFormat(pixd, pixs);
1075 datad = pixGetData(pixd);
1076 wpld = pixGetWpl(pixd);
1077
1078 /* If there is a colormap, remove it */
1079 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
1080 datat = pixGetData(pixt);
1081 wplt = pixGetWpl(pixt);
1082
1083 /* Two line buffers, 1 for current line and 2 for next line */
1084 bufs1 = (l_uint32 *)LEPT_CALLOC(wplt, sizeof(l_uint32));
1085 bufs2 = (l_uint32 *)LEPT_CALLOC(wplt, sizeof(l_uint32));
1086 if (!bufs1 || !bufs2) {
1087 LEPT_FREE(bufs1);
1088 LEPT_FREE(bufs2);
1089 pixDestroy(&pixd);
1090 pixDestroy(&pixt);
1091 return (PIX *)ERROR_PTR("bufs1, bufs2 not both made", procName, NULL);
1092 }
1093
1094 /* 3 lookup tables: 2-bit value, (3/8)excess, and (1/4)excess */
1095 make8To2DitherTables(&tabval, &tab38, &tab14, lowerclip, upperclip);
1096
1097 ditherTo2bppLow(datad, w, h, wpld, datat, wplt, bufs1, bufs2,
1098 tabval, tab38, tab14);
1099
1100 if (cmapflag) {
1101 cmap = pixcmapCreateLinear(2, 4);
1102 pixSetColormap(pixd, cmap);
1103 }
1104
1105 LEPT_FREE(bufs1);
1106 LEPT_FREE(bufs2);
1107 LEPT_FREE(tabval);
1108 LEPT_FREE(tab38);
1109 LEPT_FREE(tab14);
1110 pixDestroy(&pixt);
1111 return pixd;
1112 }
1113
1114
1115 /*!
1116 * \brief ditherTo2bppLow()
1117 *
1118 * Low-level function for doing Floyd-Steinberg error diffusion
1119 * dithering from 8 bpp (datas) to 2 bpp (datad). Two source
1120 * line buffers, bufs1 and bufs2, are provided, along with three
1121 * 256-entry lookup tables: tabval gives the output pixel value,
1122 * tab38 gives the extra (plus or minus) transferred to the pixels
1123 * directly to the left and below, and tab14 gives the extra
1124 * transferred to the diagonal below. The choice of 3/8 and 1/4
1125 * is traditional but arbitrary when you use a lookup table; the
1126 * only constraint is that the sum is 1. See other comments
1127 * below and in grayquant.c.
1128 */
1129 static void
ditherTo2bppLow(l_uint32 * datad,l_int32 w,l_int32 h,l_int32 wpld,l_uint32 * datas,l_int32 wpls,l_uint32 * bufs1,l_uint32 * bufs2,l_int32 * tabval,l_int32 * tab38,l_int32 * tab14)1130 ditherTo2bppLow(l_uint32 *datad,
1131 l_int32 w,
1132 l_int32 h,
1133 l_int32 wpld,
1134 l_uint32 *datas,
1135 l_int32 wpls,
1136 l_uint32 *bufs1,
1137 l_uint32 *bufs2,
1138 l_int32 *tabval,
1139 l_int32 *tab38,
1140 l_int32 *tab14)
1141 {
1142 l_int32 i;
1143 l_uint32 *lined;
1144
1145 /* do all lines except last line */
1146 memcpy(bufs2, datas, 4 * wpls); /* prime the buffer */
1147 for (i = 0; i < h - 1; i++) {
1148 memcpy(bufs1, bufs2, 4 * wpls);
1149 memcpy(bufs2, datas + (i + 1) * wpls, 4 * wpls);
1150 lined = datad + i * wpld;
1151 ditherTo2bppLineLow(lined, w, bufs1, bufs2, tabval, tab38, tab14, 0);
1152 }
1153
1154 /* do last line */
1155 memcpy(bufs1, bufs2, 4 * wpls);
1156 lined = datad + (h - 1) * wpld;
1157 ditherTo2bppLineLow(lined, w, bufs1, bufs2, tabval, tab38, tab14, 1);
1158 }
1159
1160
1161 /*!
1162 * \brief ditherTo2bppLineLow()
1163 *
1164 * \param[in] lined ptr to beginning of dest line
1165 * w (width of image in pixels
1166 * \param[in] bufs1 buffer of current source line
1167 * \param[in] bufs2 buffer of next source line
1168 * \param[in] tabval value to assign for current pixel
1169 * \param[in] tab38 excess value to give to neighboring 3/8 pixels
1170 * \param[in] tab14 excess value to give to neighboring 1/4 pixel
1171 * \param[in] lastlineflag 0 if not last dest line, 1 if last dest line
1172 * \return void
1173 *
1174 * Dispatches error diffusion dithering for
1175 * a single line of the image. If lastlineflag == 0,
1176 * both source buffers are used; otherwise, only bufs1
1177 * is used. We use source buffers because the error
1178 * is propagated into them, and we don't want to change
1179 * the input src image.
1180 *
1181 * We break dithering out line by line to make it
1182 * easier to combine functions like interpolative
1183 * scaling and error diffusion dithering, as such a
1184 * combination of operations obviates the need to
1185 * generate a 2x grayscale image as an intermediary.
1186 */
1187 static void
ditherTo2bppLineLow(l_uint32 * lined,l_int32 w,l_uint32 * bufs1,l_uint32 * bufs2,l_int32 * tabval,l_int32 * tab38,l_int32 * tab14,l_int32 lastlineflag)1188 ditherTo2bppLineLow(l_uint32 *lined,
1189 l_int32 w,
1190 l_uint32 *bufs1,
1191 l_uint32 *bufs2,
1192 l_int32 *tabval,
1193 l_int32 *tab38,
1194 l_int32 *tab14,
1195 l_int32 lastlineflag)
1196 {
1197 l_int32 j;
1198 l_int32 oval, tab38val, tab14val;
1199 l_uint8 rval, bval, dval;
1200
1201 if (lastlineflag == 0) {
1202 for (j = 0; j < w - 1; j++) {
1203 oval = GET_DATA_BYTE(bufs1, j);
1204 SET_DATA_DIBIT(lined, j, tabval[oval]);
1205 rval = GET_DATA_BYTE(bufs1, j + 1);
1206 bval = GET_DATA_BYTE(bufs2, j);
1207 dval = GET_DATA_BYTE(bufs2, j + 1);
1208 tab38val = tab38[oval];
1209 tab14val = tab14[oval];
1210 if (tab38val < 0) {
1211 rval = L_MAX(0, rval + tab38val);
1212 bval = L_MAX(0, bval + tab38val);
1213 dval = L_MAX(0, dval + tab14val);
1214 } else {
1215 rval = L_MIN(255, rval + tab38val);
1216 bval = L_MIN(255, bval + tab38val);
1217 dval = L_MIN(255, dval + tab14val);
1218 }
1219 SET_DATA_BYTE(bufs1, j + 1, rval);
1220 SET_DATA_BYTE(bufs2, j, bval);
1221 SET_DATA_BYTE(bufs2, j + 1, dval);
1222 }
1223
1224 /* do last column: j = w - 1 */
1225 oval = GET_DATA_BYTE(bufs1, j);
1226 SET_DATA_DIBIT(lined, j, tabval[oval]);
1227 bval = GET_DATA_BYTE(bufs2, j);
1228 tab38val = tab38[oval];
1229 if (tab38val < 0)
1230 bval = L_MAX(0, bval + tab38val);
1231 else
1232 bval = L_MIN(255, bval + tab38val);
1233 SET_DATA_BYTE(bufs2, j, bval);
1234 } else { /* lastlineflag == 1 */
1235 for (j = 0; j < w - 1; j++) {
1236 oval = GET_DATA_BYTE(bufs1, j);
1237 SET_DATA_DIBIT(lined, j, tabval[oval]);
1238 rval = GET_DATA_BYTE(bufs1, j + 1);
1239 tab38val = tab38[oval];
1240 if (tab38val < 0)
1241 rval = L_MAX(0, rval + tab38val);
1242 else
1243 rval = L_MIN(255, rval + tab38val);
1244 SET_DATA_BYTE(bufs1, j + 1, rval);
1245 }
1246
1247 /* do last pixel: (i, j) = (h - 1, w - 1) */
1248 oval = GET_DATA_BYTE(bufs1, j);
1249 SET_DATA_DIBIT(lined, j, tabval[oval]);
1250 }
1251 }
1252
1253
1254 /*!
1255 * \brief make8To2DitherTables()
1256 *
1257 * \param[out] ptabval value assigned to output pixel; 0, 1, 2 or 3
1258 * \param[out] ptab38 amount propagated to pixels left and below
1259 * \param[out] ptab14 amount propagated to pixel to left and down
1260 * \param[in] cliptoblack values near 0 where the excess is not propagated
1261 * \param[in] cliptowhite values near 255 where the deficit is not propagated
1262 *
1263 * \return 0 if OK, 1 on error
1264 */
1265 static l_int32
make8To2DitherTables(l_int32 ** ptabval,l_int32 ** ptab38,l_int32 ** ptab14,l_int32 cliptoblack,l_int32 cliptowhite)1266 make8To2DitherTables(l_int32 **ptabval,
1267 l_int32 **ptab38,
1268 l_int32 **ptab14,
1269 l_int32 cliptoblack,
1270 l_int32 cliptowhite)
1271 {
1272 l_int32 i;
1273 l_int32 *tabval, *tab38, *tab14;
1274
1275 PROCNAME("make8To2DitherTables");
1276
1277 /* 3 lookup tables: 2-bit value, (3/8)excess, and (1/4)excess */
1278 tabval = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
1279 tab38 = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
1280 tab14 = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
1281 *ptabval = tabval;
1282 *ptab38 = tab38;
1283 *ptab14 = tab14;
1284
1285 for (i = 0; i < 256; i++) {
1286 if (i <= cliptoblack) {
1287 tabval[i] = 0;
1288 tab38[i] = 0;
1289 tab14[i] = 0;
1290 } else if (i < 43) {
1291 tabval[i] = 0;
1292 tab38[i] = (3 * i + 4) / 8;
1293 tab14[i] = (i + 2) / 4;
1294 } else if (i < 85) {
1295 tabval[i] = 1;
1296 tab38[i] = (3 * (i - 85) - 4) / 8;
1297 tab14[i] = ((i - 85) - 2) / 4;
1298 } else if (i < 128) {
1299 tabval[i] = 1;
1300 tab38[i] = (3 * (i - 85) + 4) / 8;
1301 tab14[i] = ((i - 85) + 2) / 4;
1302 } else if (i < 170) {
1303 tabval[i] = 2;
1304 tab38[i] = (3 * (i - 170) - 4) / 8;
1305 tab14[i] = ((i - 170) - 2) / 4;
1306 } else if (i < 213) {
1307 tabval[i] = 2;
1308 tab38[i] = (3 * (i - 170) + 4) / 8;
1309 tab14[i] = ((i - 170) + 2) / 4;
1310 } else if (i < 255 - cliptowhite) {
1311 tabval[i] = 3;
1312 tab38[i] = (3 * (i - 255) - 4) / 8;
1313 tab14[i] = ((i - 255) - 2) / 4;
1314 } else { /* i >= 255 - cliptowhite */
1315 tabval[i] = 3;
1316 tab38[i] = 0;
1317 tab14[i] = 0;
1318 }
1319 }
1320
1321 return 0;
1322 }
1323
1324
1325 /*--------------------------------------------------------------------*
1326 * Simple (pixelwise) thresholding to 2 bpp with optional colormap *
1327 *--------------------------------------------------------------------*/
1328 /*!
1329 * \brief pixThresholdTo2bpp()
1330 *
1331 * \param[in] pixs 8 bpp
1332 * \param[in] nlevels equally spaced; must be between 2 and 4
1333 * \param[in] cmapflag 1 to build colormap; 0 otherwise
1334 * \return pixd 2 bpp, optionally with colormap, or NULL on error
1335 *
1336 * <pre>
1337 * Notes:
1338 * (1) Valid values for nlevels is the set {2, 3, 4}.
1339 * (2) Any colormap on the input pixs is removed to 8 bpp grayscale.
1340 * (3) This function is typically invoked with cmapflag == 1.
1341 * In the situation where no colormap is desired, nlevels is
1342 * ignored and pixs is thresholded to 4 levels.
1343 * (4) The target output colors are equally spaced, with the
1344 * darkest at 0 and the lightest at 255. The thresholds are
1345 * chosen halfway between adjacent output values. A table
1346 * is built that specifies the mapping from src to dest.
1347 * (5) If cmapflag == 1, a colormap of size 'nlevels' is made,
1348 * and the pixel values in pixs are replaced by their
1349 * appropriate color indices. The number of holdouts,
1350 * 4 - nlevels, will be between 0 and 2.
1351 * (6) If you don't want the thresholding to be equally spaced,
1352 * either first transform the 8 bpp src using pixGammaTRC().
1353 * or, if cmapflag == 1, after calling this function you can use
1354 * pixcmapResetColor() to change any individual colors.
1355 * (7) If a colormap is generated, it will specify (to display
1356 * programs) exactly how each level is to be represented in RGB
1357 * space. When representing text, 3 levels is far better than
1358 * 2 because of the antialiasing of the single gray level,
1359 * and 4 levels (black, white and 2 gray levels) is getting
1360 * close to the perceptual quality of a (nearly continuous)
1361 * grayscale image. With 2 bpp, you can set up a colormap
1362 * and allocate from 2 to 4 levels to represent antialiased text.
1363 * Any left over colormap entries can be used for coloring regions.
1364 * For the same number of levels, the file size of a 2 bpp image
1365 * is about 10% smaller than that of a 4 bpp result for the same
1366 * number of levels. For both 2 bpp and 4 bpp, using 4 levels you
1367 * get compression far better than that of jpeg, because the
1368 * quantization to 4 levels will remove the jpeg ringing in the
1369 * background near character edges.
1370 * </pre>
1371 */
1372 PIX *
pixThresholdTo2bpp(PIX * pixs,l_int32 nlevels,l_int32 cmapflag)1373 pixThresholdTo2bpp(PIX *pixs,
1374 l_int32 nlevels,
1375 l_int32 cmapflag)
1376 {
1377 l_int32 *qtab;
1378 l_int32 w, h, d, wplt, wpld;
1379 l_uint32 *datat, *datad;
1380 PIX *pixt, *pixd;
1381 PIXCMAP *cmap;
1382
1383 PROCNAME("pixThresholdTo2bpp");
1384
1385 if (!pixs)
1386 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
1387 pixGetDimensions(pixs, &w, &h, &d);
1388 if (d != 8)
1389 return (PIX *)ERROR_PTR("pixs not 8 bpp", procName, NULL);
1390 if (nlevels < 2 || nlevels > 4)
1391 return (PIX *)ERROR_PTR("nlevels not in {2, 3, 4}", procName, NULL);
1392
1393 if ((pixd = pixCreate(w, h, 2)) == NULL)
1394 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
1395 pixCopyResolution(pixd, pixs);
1396 pixCopyInputFormat(pixd, pixs);
1397 datad = pixGetData(pixd);
1398 wpld = pixGetWpl(pixd);
1399
1400 if (cmapflag) { /* hold out (4 - nlevels) cmap entries */
1401 cmap = pixcmapCreateLinear(2, nlevels);
1402 pixSetColormap(pixd, cmap);
1403 }
1404
1405 /* If there is a colormap in the src, remove it */
1406 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
1407 datat = pixGetData(pixt);
1408 wplt = pixGetWpl(pixt);
1409
1410 /* Make the appropriate table */
1411 if (cmapflag)
1412 qtab = makeGrayQuantIndexTable(nlevels);
1413 else
1414 qtab = makeGrayQuantTargetTable(4, 2);
1415
1416 thresholdTo2bppLow(datad, h, wpld, datat, wplt, qtab);
1417
1418 LEPT_FREE(qtab);
1419 pixDestroy(&pixt);
1420 return pixd;
1421 }
1422
1423
1424 /*!
1425 * \brief thresholdTo2bppLow()
1426 *
1427 * Low-level function for thresholding from 8 bpp (datas) to
1428 * 2 bpp (datad), using thresholds implicitly defined through %tab,
1429 * a 256-entry lookup table that gives a 2-bit output value
1430 * for each possible input.
1431 *
1432 * For each line, unroll the loop so that for each 32 bit src word,
1433 * representing four consecutive 8-bit pixels, we compose one byte
1434 * of output consisiting of four 2-bit pixels.
1435 */
1436 static void
thresholdTo2bppLow(l_uint32 * datad,l_int32 h,l_int32 wpld,l_uint32 * datas,l_int32 wpls,l_int32 * tab)1437 thresholdTo2bppLow(l_uint32 *datad,
1438 l_int32 h,
1439 l_int32 wpld,
1440 l_uint32 *datas,
1441 l_int32 wpls,
1442 l_int32 *tab)
1443 {
1444 l_uint8 sval1, sval2, sval3, sval4, dval;
1445 l_int32 i, j, k;
1446 l_uint32 *lines, *lined;
1447
1448 for (i = 0; i < h; i++) {
1449 lines = datas + i * wpls;
1450 lined = datad + i * wpld;
1451 for (j = 0; j < wpls; j++) {
1452 k = 4 * j;
1453 sval1 = GET_DATA_BYTE(lines, k);
1454 sval2 = GET_DATA_BYTE(lines, k + 1);
1455 sval3 = GET_DATA_BYTE(lines, k + 2);
1456 sval4 = GET_DATA_BYTE(lines, k + 3);
1457 dval = (tab[sval1] << 6) | (tab[sval2] << 4) |
1458 (tab[sval3] << 2) | tab[sval4];
1459 SET_DATA_BYTE(lined, j, dval);
1460 }
1461 }
1462 }
1463
1464
1465 /*----------------------------------------------------------------------*
1466 * Simple (pixelwise) thresholding to 4 bpp *
1467 *----------------------------------------------------------------------*/
1468 /*!
1469 * \brief pixThresholdTo4bpp()
1470 *
1471 * \param[in] pixs 8 bpp, can have colormap
1472 * \param[in] nlevels equally spaced; must be between 2 and 16
1473 * \param[in] cmapflag 1 to build colormap; 0 otherwise
1474 * \return pixd 4 bpp, optionally with colormap, or NULL on error
1475 *
1476 * <pre>
1477 * Notes:
1478 * (1) Valid values for nlevels is the set {2, ... 16}.
1479 * (2) Any colormap on the input pixs is removed to 8 bpp grayscale.
1480 * (3) This function is typically invoked with cmapflag == 1.
1481 * In the situation where no colormap is desired, nlevels is
1482 * ignored and pixs is thresholded to 16 levels.
1483 * (4) The target output colors are equally spaced, with the
1484 * darkest at 0 and the lightest at 255. The thresholds are
1485 * chosen halfway between adjacent output values. A table
1486 * is built that specifies the mapping from src to dest.
1487 * (5) If cmapflag == 1, a colormap of size 'nlevels' is made,
1488 * and the pixel values in pixs are replaced by their
1489 * appropriate color indices. The number of holdouts,
1490 * 16 - nlevels, will be between 0 and 14.
1491 * (6) If you don't want the thresholding to be equally spaced,
1492 * either first transform the 8 bpp src using pixGammaTRC().
1493 * or, if cmapflag == 1, after calling this function you can use
1494 * pixcmapResetColor() to change any individual colors.
1495 * (7) If a colormap is generated, it will specify, to display
1496 * programs, exactly how each level is to be represented in RGB
1497 * space. When representing text, 3 levels is far better than
1498 * 2 because of the antialiasing of the single gray level,
1499 * and 4 levels (black, white and 2 gray levels) is getting
1500 * close to the perceptual quality of a (nearly continuous)
1501 * grayscale image. Therefore, with 4 bpp, you can set up a
1502 * colormap, allocate a relatively small fraction of the 16
1503 * possible values to represent antialiased text, and use the
1504 * other colormap entries for other things, such as coloring
1505 * text or background. Two other reasons for using a small number
1506 * of gray values for antialiased text are (1) PNG compression
1507 * gets worse as the number of levels that are used is increased,
1508 * and (2) using a small number of levels will filter out most of
1509 * the jpeg ringing that is typically introduced near sharp edges
1510 * of text. This filtering is partly responsible for the improved
1511 * compression.
1512 * </pre>
1513 */
1514 PIX *
pixThresholdTo4bpp(PIX * pixs,l_int32 nlevels,l_int32 cmapflag)1515 pixThresholdTo4bpp(PIX *pixs,
1516 l_int32 nlevels,
1517 l_int32 cmapflag)
1518 {
1519 l_int32 *qtab;
1520 l_int32 w, h, d, wplt, wpld;
1521 l_uint32 *datat, *datad;
1522 PIX *pixt, *pixd;
1523 PIXCMAP *cmap;
1524
1525 PROCNAME("pixThresholdTo4bpp");
1526
1527 if (!pixs)
1528 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
1529 pixGetDimensions(pixs, &w, &h, &d);
1530 if (d != 8)
1531 return (PIX *)ERROR_PTR("pixs not 8 bpp", procName, NULL);
1532 if (nlevels < 2 || nlevels > 16)
1533 return (PIX *)ERROR_PTR("nlevels not in [2,...,16]", procName, NULL);
1534
1535 if ((pixd = pixCreate(w, h, 4)) == NULL)
1536 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
1537 pixCopyResolution(pixd, pixs);
1538 pixCopyInputFormat(pixd, pixs);
1539 datad = pixGetData(pixd);
1540 wpld = pixGetWpl(pixd);
1541
1542 if (cmapflag) { /* hold out (16 - nlevels) cmap entries */
1543 cmap = pixcmapCreateLinear(4, nlevels);
1544 pixSetColormap(pixd, cmap);
1545 }
1546
1547 /* If there is a colormap in the src, remove it */
1548 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
1549 datat = pixGetData(pixt);
1550 wplt = pixGetWpl(pixt);
1551
1552 /* Make the appropriate table */
1553 if (cmapflag)
1554 qtab = makeGrayQuantIndexTable(nlevels);
1555 else
1556 qtab = makeGrayQuantTargetTable(16, 4);
1557
1558 thresholdTo4bppLow(datad, h, wpld, datat, wplt, qtab);
1559
1560 LEPT_FREE(qtab);
1561 pixDestroy(&pixt);
1562 return pixd;
1563 }
1564
1565
1566 /*!
1567 * \brief thresholdTo4bppLow()
1568 *
1569 * Low-level function for thresholding from 8 bpp (datas) to
1570 * 4 bpp (datad), using thresholds implicitly defined through %tab,
1571 * a 256-entry lookup table that gives a 4-bit output value
1572 * for each possible input.
1573 *
1574 * For each line, unroll the loop so that for each 32 bit src word,
1575 * representing four consecutive 8-bit pixels, we compose two bytes
1576 * of output consisiting of four 4-bit pixels.
1577 */
1578 static void
thresholdTo4bppLow(l_uint32 * datad,l_int32 h,l_int32 wpld,l_uint32 * datas,l_int32 wpls,l_int32 * tab)1579 thresholdTo4bppLow(l_uint32 *datad,
1580 l_int32 h,
1581 l_int32 wpld,
1582 l_uint32 *datas,
1583 l_int32 wpls,
1584 l_int32 *tab)
1585 {
1586 l_uint8 sval1, sval2, sval3, sval4;
1587 l_uint16 dval;
1588 l_int32 i, j, k;
1589 l_uint32 *lines, *lined;
1590
1591 for (i = 0; i < h; i++) {
1592 lines = datas + i * wpls;
1593 lined = datad + i * wpld;
1594 for (j = 0; j < wpls; j++) {
1595 k = 4 * j;
1596 sval1 = GET_DATA_BYTE(lines, k);
1597 sval2 = GET_DATA_BYTE(lines, k + 1);
1598 sval3 = GET_DATA_BYTE(lines, k + 2);
1599 sval4 = GET_DATA_BYTE(lines, k + 3);
1600 dval = (tab[sval1] << 12) | (tab[sval2] << 8) |
1601 (tab[sval3] << 4) | tab[sval4];
1602 SET_DATA_TWO_BYTES(lined, j, dval);
1603 }
1604 }
1605 }
1606
1607
1608 /*----------------------------------------------------------------------*
1609 * Simple (pixelwise) thresholding on 8 bpp with optional colormap *
1610 *----------------------------------------------------------------------*/
1611 /*!
1612 * \brief pixThresholdOn8bpp()
1613 *
1614 * \param[in] pixs 8 bpp, can have colormap
1615 * \param[in] nlevels equally spaced; must be between 2 and 256
1616 * \param[in] cmapflag 1 to build colormap; 0 otherwise
1617 * \return pixd 8 bpp, optionally with colormap, or NULL on error
1618 *
1619 * <pre>
1620 * Notes:
1621 * (1) Valid values for nlevels is the set {2,...,256}.
1622 * (2) Any colormap on the input pixs is removed to 8 bpp grayscale.
1623 * (3) If cmapflag == 1, a colormap of size 'nlevels' is made,
1624 * and the pixel values in pixs are replaced by their
1625 * appropriate color indices. Otherwise, the pixel values
1626 * are the actual thresholded (i.e., quantized) grayscale values.
1627 * (4) If you don't want the thresholding to be equally spaced,
1628 * first transform the input 8 bpp src using pixGammaTRC().
1629 * </pre>
1630 */
1631 PIX *
pixThresholdOn8bpp(PIX * pixs,l_int32 nlevels,l_int32 cmapflag)1632 pixThresholdOn8bpp(PIX *pixs,
1633 l_int32 nlevels,
1634 l_int32 cmapflag)
1635 {
1636 l_int32 *qtab; /* quantization table */
1637 l_int32 i, j, w, h, wpld, val, newval;
1638 l_uint32 *datad, *lined;
1639 PIX *pixd;
1640 PIXCMAP *cmap;
1641
1642 PROCNAME("pixThresholdOn8bpp");
1643
1644 if (!pixs)
1645 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
1646 if (pixGetDepth(pixs) != 8)
1647 return (PIX *)ERROR_PTR("pixs not 8 bpp", procName, NULL);
1648 if (nlevels < 2 || nlevels > 256)
1649 return (PIX *)ERROR_PTR("nlevels not in [2,...,256]", procName, NULL);
1650
1651 /* Get a new pixd; if there is a colormap in the src, remove it */
1652 if (pixGetColormap(pixs))
1653 pixd = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
1654 else
1655 pixd = pixCopy(NULL, pixs);
1656
1657 if (cmapflag) { /* hold out (256 - nlevels) cmap entries */
1658 cmap = pixcmapCreateLinear(8, nlevels);
1659 pixSetColormap(pixd, cmap);
1660 }
1661
1662 if (cmapflag)
1663 qtab = makeGrayQuantIndexTable(nlevels);
1664 else
1665 qtab = makeGrayQuantTargetTable(nlevels, 8);
1666
1667 pixGetDimensions(pixd, &w, &h, NULL);
1668 pixCopyResolution(pixd, pixs);
1669 pixCopyInputFormat(pixd, pixs);
1670 datad = pixGetData(pixd);
1671 wpld = pixGetWpl(pixd);
1672 for (i = 0; i < h; i++) {
1673 lined = datad + i * wpld;
1674 for (j = 0; j < w; j++) {
1675 val = GET_DATA_BYTE(lined, j);
1676 newval = qtab[val];
1677 SET_DATA_BYTE(lined, j, newval);
1678 }
1679 }
1680
1681 LEPT_FREE(qtab);
1682 return pixd;
1683 }
1684
1685
1686 /*----------------------------------------------------------------------*
1687 * Arbitrary (pixelwise) thresholding from 8 bpp to 2, 4 or 8 bpp *
1688 *----------------------------------------------------------------------*/
1689 /*!
1690 * \brief pixThresholdGrayArb()
1691 *
1692 * \param[in] pixs 8 bpp grayscale; can have colormap
1693 * \param[in] edgevals string giving edge value of each bin
1694 * \param[in] outdepth 0, 2, 4 or 8 bpp; 0 is default for min depth
1695 * \param[in] use_average 1 if use the average pixel value in colormap
1696 * \param[in] setblack 1 if darkest color is set to black
1697 * \param[in] setwhite 1 if lightest color is set to white
1698 * \return pixd 2, 4 or 8 bpp quantized image with colormap,
1699 * or NULL on error
1700 *
1701 * <pre>
1702 * Notes:
1703 * (1) This function allows exact specification of the quantization bins.
1704 * The string %edgevals is a space-separated set of values
1705 * specifying the dividing points between output quantization bins.
1706 * These threshold values are assigned to the bin with higher
1707 * values, so that each of them is the smallest value in their bin.
1708 * (2) The output image (pixd) depth is specified by %outdepth. The
1709 * number of bins is the number of edgevals + 1. The
1710 * relation between outdepth and the number of bins is:
1711 * outdepth = 2 nbins <= 4
1712 * outdepth = 4 nbins <= 16
1713 * outdepth = 8 nbins <= 256
1714 * With %outdepth == 0, the minimum required depth for the
1715 * given number of bins is used.
1716 * The output pixd has a colormap.
1717 * (3) The last 3 args determine the specific values that go into
1718 * the colormap.
1719 * (4) For %use_average:
1720 * ~ if TRUE, the average value of pixels falling in the bin is
1721 * chosen as the representative gray value. Otherwise,
1722 * ~ if FALSE, the central value of each bin is chosen as
1723 * the representative value.
1724 * The colormap holds the representative value.
1725 * (5) For %setblack, if TRUE the darkest color is set to (0,0,0).
1726 * (6) For %setwhite, if TRUE the lightest color is set to (255,255,255).
1727 * (7) An alternative to using this function to quantize to
1728 * unequally-spaced bins is to first transform the 8 bpp pixs
1729 * using pixGammaTRC(), and follow this with pixThresholdTo4bpp().
1730 * </pre>
1731 */
1732 PIX *
pixThresholdGrayArb(PIX * pixs,const char * edgevals,l_int32 outdepth,l_int32 use_average,l_int32 setblack,l_int32 setwhite)1733 pixThresholdGrayArb(PIX *pixs,
1734 const char *edgevals,
1735 l_int32 outdepth,
1736 l_int32 use_average,
1737 l_int32 setblack,
1738 l_int32 setwhite)
1739 {
1740 l_int32 *qtab;
1741 l_int32 w, h, d, i, j, n, wplt, wpld, val, newval;
1742 l_uint32 *datat, *datad, *linet, *lined;
1743 NUMA *na;
1744 PIX *pixt, *pixd;
1745 PIXCMAP *cmap;
1746
1747 PROCNAME("pixThresholdGrayArb");
1748
1749 if (!pixs)
1750 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
1751 pixGetDimensions(pixs, &w, &h, &d);
1752 if (d != 8)
1753 return (PIX *)ERROR_PTR("pixs not 8 bpp", procName, NULL);
1754 if (!edgevals)
1755 return (PIX *)ERROR_PTR("edgevals not defined", procName, NULL);
1756 if (outdepth != 0 && outdepth != 2 && outdepth != 4 && outdepth != 8)
1757 return (PIX *)ERROR_PTR("invalid outdepth", procName, NULL);
1758
1759 /* Parse and sort (if required) the bin edge values */
1760 na = parseStringForNumbers(edgevals, " \t\n,");
1761 n = numaGetCount(na);
1762 if (n > 255) {
1763 numaDestroy(&na);
1764 return (PIX *)ERROR_PTR("more than 256 levels", procName, NULL);
1765 }
1766 if (outdepth == 0) {
1767 if (n <= 3)
1768 outdepth = 2;
1769 else if (n <= 15)
1770 outdepth = 4;
1771 else
1772 outdepth = 8;
1773 } else if (n + 1 > (1 << outdepth)) {
1774 L_WARNING("outdepth too small; setting to 8 bpp\n", procName);
1775 outdepth = 8;
1776 }
1777 numaSort(na, na, L_SORT_INCREASING);
1778
1779 /* Make the quantization LUT and the colormap */
1780 makeGrayQuantTableArb(na, outdepth, &qtab, &cmap);
1781 if (use_average) { /* use the average value in each bin */
1782 pixcmapDestroy(&cmap);
1783 makeGrayQuantColormapArb(pixs, qtab, outdepth, &cmap);
1784 }
1785 pixcmapSetBlackAndWhite(cmap, setblack, setwhite);
1786 numaDestroy(&na);
1787
1788 if ((pixd = pixCreate(w, h, outdepth)) == NULL) {
1789 LEPT_FREE(qtab);
1790 pixcmapDestroy(&cmap);
1791 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
1792 }
1793 pixCopyResolution(pixd, pixs);
1794 pixCopyInputFormat(pixd, pixs);
1795 pixSetColormap(pixd, cmap);
1796 datad = pixGetData(pixd);
1797 wpld = pixGetWpl(pixd);
1798
1799 /* If there is a colormap in the src, remove it */
1800 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
1801 datat = pixGetData(pixt);
1802 wplt = pixGetWpl(pixt);
1803
1804 if (outdepth == 2) {
1805 thresholdTo2bppLow(datad, h, wpld, datat, wplt, qtab);
1806 } else if (outdepth == 4) {
1807 thresholdTo4bppLow(datad, h, wpld, datat, wplt, qtab);
1808 } else {
1809 for (i = 0; i < h; i++) {
1810 lined = datad + i * wpld;
1811 linet = datat + i * wplt;
1812 for (j = 0; j < w; j++) {
1813 val = GET_DATA_BYTE(linet, j);
1814 newval = qtab[val];
1815 SET_DATA_BYTE(lined, j, newval);
1816 }
1817 }
1818 }
1819
1820 LEPT_FREE(qtab);
1821 pixDestroy(&pixt);
1822 return pixd;
1823 }
1824
1825
1826 /*----------------------------------------------------------------------*
1827 * Quantization tables for linear thresholds of grayscale images *
1828 *----------------------------------------------------------------------*/
1829 /*!
1830 * \brief makeGrayQuantIndexTable()
1831 *
1832 * \param[in] nlevels number of output levels
1833 * \return table maps input gray level to colormap index,
1834 * or NULL on error
1835 * <pre>
1836 * Notes:
1837 * (1) 'nlevels' is some number between 2 and 256 (typically 8 or less).
1838 * (2) The table is typically used for quantizing 2, 4 and 8 bpp
1839 * grayscale src pix, and generating a colormapped dest pix.
1840 * </pre>
1841 */
1842 l_int32 *
makeGrayQuantIndexTable(l_int32 nlevels)1843 makeGrayQuantIndexTable(l_int32 nlevels)
1844 {
1845 l_int32 *tab;
1846 l_int32 i, j, thresh;
1847
1848 PROCNAME("makeGrayQuantIndexTable");
1849
1850 if ((tab = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32))) == NULL)
1851 return (l_int32 *)ERROR_PTR("calloc fail for tab", procName, NULL);
1852 for (i = 0; i < 256; i++) {
1853 for (j = 0; j < nlevels; j++) {
1854 thresh = 255 * (2 * j + 1) / (2 * nlevels - 2);
1855 if (i <= thresh) {
1856 tab[i] = j;
1857 /* fprintf(stderr, "tab[%d] = %d\n", i, j); */
1858 break;
1859 }
1860 }
1861 }
1862 return tab;
1863 }
1864
1865
1866 /*!
1867 * \brief makeGrayQuantTargetTable()
1868 *
1869 * \param[in] nlevels number of output levels
1870 * \param[in] depth of dest pix, in bpp; 2, 4 or 8 bpp
1871 * \return table maps input gray level to thresholded gray level,
1872 * or NULL on error
1873 *
1874 * <pre>
1875 * Notes:
1876 * (1) nlevels is some number between 2 and 2^(depth)
1877 * (2) The table is used in two similar ways:
1878 * ~ for 8 bpp, it quantizes to a given number of target levels
1879 * ~ for 2 and 4 bpp, it thresholds to appropriate target values
1880 * that will use the full dynamic range of the dest pix.
1881 * (3) For depth = 8, the number of thresholds chosen is
1882 * ('nlevels' - 1), and the 'nlevels' values stored in the
1883 * table are at the two at the extreme ends, (0, 255), plus
1884 * plus ('nlevels' - 2) values chosen at equal intervals between.
1885 * For example, for depth = 8 and 'nlevels' = 3, the two
1886 * threshold values are 3f and bf, and the three target pixel
1887 * values are 0, 7f and ff.
1888 * (4) For depth < 8, we ignore nlevels, and always use the maximum
1889 * number of levels, which is 2^(depth).
1890 * If you want nlevels < the maximum number, you should always
1891 * use a colormap.
1892 * </pre>
1893 */
1894 static l_int32 *
makeGrayQuantTargetTable(l_int32 nlevels,l_int32 depth)1895 makeGrayQuantTargetTable(l_int32 nlevels,
1896 l_int32 depth)
1897 {
1898 l_int32 *tab;
1899 l_int32 i, j, thresh, maxval, quantval;
1900
1901 PROCNAME("makeGrayQuantTargetTable");
1902
1903 if ((tab = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32))) == NULL)
1904 return (l_int32 *)ERROR_PTR("calloc fail for tab", procName, NULL);
1905
1906 maxval = (1 << depth) - 1;
1907 if (depth < 8)
1908 nlevels = 1 << depth;
1909 for (i = 0; i < 256; i++) {
1910 for (j = 0; j < nlevels; j++) {
1911 thresh = 255 * (2 * j + 1) / (2 * nlevels - 2);
1912 if (i <= thresh) {
1913 quantval = maxval * j / (nlevels - 1);
1914 tab[i] = quantval;
1915 /* fprintf(stderr, "tab[%d] = %d\n", i, tab[i]); */
1916 break;
1917 }
1918 }
1919 }
1920 return tab;
1921 }
1922
1923
1924 /*----------------------------------------------------------------------*
1925 * Quantization table for arbitrary thresholding of grayscale images *
1926 *----------------------------------------------------------------------*/
1927 /*!
1928 * \brief makeGrayQuantTableArb()
1929 *
1930 * \param[in] na numa of bin boundaries
1931 * \param[in] outdepth of colormap: 1, 2, 4 or 8
1932 * \param[out] ptab table mapping input gray level to cmap index
1933 * \param[out] pcmap colormap
1934 * \return 0 if OK, 1 on error
1935 *
1936 * <pre>
1937 * Notes:
1938 * (1) The number of bins is the count of %na + 1.
1939 * (2) The bin boundaries in na must be sorted in increasing order.
1940 * (3) The table is an inverse colormap: it maps input gray level
1941 * to colormap index (the bin number).
1942 * (4) The colormap generated here has quantized values at the
1943 * center of each bin. If you want to use the average gray
1944 * value of pixels within the bin, discard the colormap and
1945 * compute it using makeGrayQuantColormapArb().
1946 * (5) Returns an error if there are not enough levels in the
1947 * output colormap for the number of bins. The number
1948 * of bins must not exceed 2^outdepth.
1949 * </pre>
1950 */
1951 l_int32
makeGrayQuantTableArb(NUMA * na,l_int32 outdepth,l_int32 ** ptab,PIXCMAP ** pcmap)1952 makeGrayQuantTableArb(NUMA *na,
1953 l_int32 outdepth,
1954 l_int32 **ptab,
1955 PIXCMAP **pcmap)
1956 {
1957 l_int32 i, j, n, jstart, ave, val;
1958 l_int32 *tab;
1959 PIXCMAP *cmap;
1960
1961 PROCNAME("makeGrayQuantTableArb");
1962
1963 if (!ptab)
1964 return ERROR_INT("&tab not defined", procName, 1);
1965 *ptab = NULL;
1966 if (!pcmap)
1967 return ERROR_INT("&cmap not defined", procName, 1);
1968 *pcmap = NULL;
1969 if (!na)
1970 return ERROR_INT("na not defined", procName, 1);
1971 n = numaGetCount(na);
1972 if (n + 1 > (1 << outdepth))
1973 return ERROR_INT("more bins than cmap levels", procName, 1);
1974
1975 if ((cmap = pixcmapCreate(outdepth)) == NULL)
1976 return ERROR_INT("cmap not made", procName, 1);
1977 tab = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
1978 *ptab = tab;
1979 *pcmap = cmap;
1980
1981 /* First n bins */
1982 jstart = 0;
1983 for (i = 0; i < n; i++) {
1984 numaGetIValue(na, i, &val);
1985 ave = (jstart + val) / 2;
1986 pixcmapAddColor(cmap, ave, ave, ave);
1987 for (j = jstart; j < val; j++)
1988 tab[j] = i;
1989 jstart = val;
1990 }
1991
1992 /* Last bin */
1993 ave = (jstart + 255) / 2;
1994 pixcmapAddColor(cmap, ave, ave, ave);
1995 for (j = jstart; j < 256; j++)
1996 tab[j] = n;
1997
1998 return 0;
1999 }
2000
2001
2002 /*!
2003 * \brief makeGrayQuantColormapArb()
2004 *
2005 * \param[in] pixs 8 bpp
2006 * \param[in] tab table mapping input gray level to cmap index
2007 * \param[in] outdepth of colormap: 1, 2, 4 or 8
2008 * \param[out] pcmap colormap
2009 * \return 0 if OK, 1 on error
2010 *
2011 * <pre>
2012 * Notes:
2013 * (1) The table is a 256-entry inverse colormap: it maps input gray
2014 * level to colormap index (the bin number). It is computed
2015 * using makeGrayQuantTableArb().
2016 * (2) The colormap generated here has quantized values at the
2017 * average gray value of the pixels that are in each bin.
2018 * (3) Returns an error if there are not enough levels in the
2019 * output colormap for the number of bins. The number
2020 * of bins must not exceed 2^outdepth.
2021 * </pre>
2022 */
2023 static l_int32
makeGrayQuantColormapArb(PIX * pixs,l_int32 * tab,l_int32 outdepth,PIXCMAP ** pcmap)2024 makeGrayQuantColormapArb(PIX *pixs,
2025 l_int32 *tab,
2026 l_int32 outdepth,
2027 PIXCMAP **pcmap)
2028 {
2029 l_int32 i, j, index, w, h, d, nbins, wpl, factor, val;
2030 l_int32 *bincount, *binave, *binstart;
2031 l_uint32 *line, *data;
2032
2033 PROCNAME("makeGrayQuantColormapArb");
2034
2035 if (!pcmap)
2036 return ERROR_INT("&cmap not defined", procName, 1);
2037 *pcmap = NULL;
2038 if (!pixs)
2039 return ERROR_INT("pixs not defined", procName, 1);
2040 pixGetDimensions(pixs, &w, &h, &d);
2041 if (d != 8)
2042 return ERROR_INT("pixs not 8 bpp", procName, 1);
2043 if (!tab)
2044 return ERROR_INT("tab not defined", procName, 1);
2045 nbins = tab[255] + 1;
2046 if (nbins > (1 << outdepth))
2047 return ERROR_INT("more bins than cmap levels", procName, 1);
2048
2049 /* Find the count and weighted count for each bin */
2050 if ((bincount = (l_int32 *)LEPT_CALLOC(nbins, sizeof(l_int32))) == NULL)
2051 return ERROR_INT("calloc fail for bincount", procName, 1);
2052 if ((binave = (l_int32 *)LEPT_CALLOC(nbins, sizeof(l_int32))) == NULL) {
2053 LEPT_FREE(bincount);
2054 return ERROR_INT("calloc fail for binave", procName, 1);
2055 }
2056 factor = (l_int32)(sqrt((l_float64)(w * h) / 30000.) + 0.5);
2057 factor = L_MAX(1, factor);
2058 data = pixGetData(pixs);
2059 wpl = pixGetWpl(pixs);
2060 for (i = 0; i < h; i += factor) {
2061 line = data + i * wpl;
2062 for (j = 0; j < w; j += factor) {
2063 val = GET_DATA_BYTE(line, j);
2064 bincount[tab[val]]++;
2065 binave[tab[val]] += val;
2066 }
2067 }
2068
2069 /* Find the smallest gray values in each bin */
2070 binstart = (l_int32 *)LEPT_CALLOC(nbins, sizeof(l_int32));
2071 for (i = 1, index = 1; i < 256; i++) {
2072 if (tab[i] < index) continue;
2073 if (tab[i] == index)
2074 binstart[index++] = i;
2075 }
2076
2077 /* Get the averages. If there are no samples in a bin, use
2078 * the center value of the bin. */
2079 *pcmap = pixcmapCreate(outdepth);
2080 for (i = 0; i < nbins; i++) {
2081 if (bincount[i]) {
2082 val = binave[i] / bincount[i];
2083 } else { /* no samples in the bin */
2084 if (i < nbins - 1)
2085 val = (binstart[i] + binstart[i + 1]) / 2;
2086 else /* last bin */
2087 val = (binstart[i] + 255) / 2;
2088 }
2089 pixcmapAddColor(*pcmap, val, val, val);
2090 }
2091
2092 LEPT_FREE(bincount);
2093 LEPT_FREE(binave);
2094 LEPT_FREE(binstart);
2095 return 0;
2096 }
2097
2098
2099 /*--------------------------------------------------------------------*
2100 * Thresholding from 32 bpp rgb to 1 bpp *
2101 *--------------------------------------------------------------------*/
2102 /*!
2103 * \brief pixGenerateMaskByBand32()
2104 *
2105 * \param[in] pixs 32 bpp
2106 * \param[in] refval reference rgb value
2107 * \param[in] delm max amount below the ref value for any component
2108 * \param[in] delp max amount above the ref value for any component
2109 * \param[in] fractm fractional amount below ref value for all components
2110 * \param[in] fractp fractional amount above ref value for all components
2111 * \return pixd 1 bpp, or NULL on error
2112 *
2113 * <pre>
2114 * Notes:
2115 * (1) Generates a 1 bpp mask pixd, the same size as pixs, where
2116 * the fg pixels in the mask within a band of rgb values
2117 * surrounding %refval. The band can be chosen in two ways
2118 * for each component:
2119 * (a) Use (%delm, %delp) to specify how many levels down and up
2120 * (b) Use (%fractm, %fractp) to specify the fractional
2121 * distance toward 0 and 255, respectively.
2122 * Note that %delm and %delp must be in [0 ... 255], whereas
2123 * %fractm and %fractp must be in [0.0 - 1.0].
2124 * (2) Either (%delm, %delp) or (%fractm, %fractp) can be used.
2125 * Set each value in the other pair to 0.
2126 * </pre>
2127 */
2128 PIX *
pixGenerateMaskByBand32(PIX * pixs,l_uint32 refval,l_int32 delm,l_int32 delp,l_float32 fractm,l_float32 fractp)2129 pixGenerateMaskByBand32(PIX *pixs,
2130 l_uint32 refval,
2131 l_int32 delm,
2132 l_int32 delp,
2133 l_float32 fractm,
2134 l_float32 fractp)
2135 {
2136 l_int32 i, j, w, h, d, wpls, wpld;
2137 l_int32 rref, gref, bref, rval, gval, bval;
2138 l_int32 rmin, gmin, bmin, rmax, gmax, bmax;
2139 l_uint32 pixel;
2140 l_uint32 *datas, *datad, *lines, *lined;
2141 PIX *pixd;
2142
2143 PROCNAME("pixGenerateMaskByBand32");
2144
2145 if (!pixs)
2146 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
2147 pixGetDimensions(pixs, &w, &h, &d);
2148 if (d != 32)
2149 return (PIX *)ERROR_PTR("not 32 bpp", procName, NULL);
2150 if (delm < 0 || delp < 0)
2151 return (PIX *)ERROR_PTR("delm and delp must be >= 0", procName, NULL);
2152 if (fractm < 0.0 || fractm > 1.0 || fractp < 0.0 || fractp > 1.0)
2153 return (PIX *)ERROR_PTR("fractm and/or fractp invalid", procName, NULL);
2154
2155 extractRGBValues(refval, &rref, &gref, &bref);
2156 if (fractm == 0.0 && fractp == 0.0) {
2157 rmin = rref - delm;
2158 gmin = gref - delm;
2159 bmin = bref - delm;
2160 rmax = rref + delm;
2161 gmax = gref + delm;
2162 bmax = bref + delm;
2163 } else if (delm == 0 && delp == 0) {
2164 rmin = (l_int32)((1.0 - fractm) * rref);
2165 gmin = (l_int32)((1.0 - fractm) * gref);
2166 bmin = (l_int32)((1.0 - fractm) * bref);
2167 rmax = rref + (l_int32)(fractp * (255 - rref));
2168 gmax = gref + (l_int32)(fractp * (255 - gref));
2169 bmax = bref + (l_int32)(fractp * (255 - bref));
2170 } else {
2171 L_ERROR("bad input: either (delm, delp) or (fractm, fractp) "
2172 "must be 0\n", procName);
2173 return NULL;
2174 }
2175
2176 pixd = pixCreate(w, h, 1);
2177 pixCopyResolution(pixd, pixs);
2178 pixCopyInputFormat(pixd, pixs);
2179 datas = pixGetData(pixs);
2180 wpls = pixGetWpl(pixs);
2181 datad = pixGetData(pixd);
2182 wpld = pixGetWpl(pixd);
2183 for (i = 0; i < h; i++) {
2184 lines = datas + i * wpls;
2185 lined = datad + i * wpld;
2186 for (j = 0; j < w; j++) {
2187 pixel = lines[j];
2188 rval = (pixel >> L_RED_SHIFT) & 0xff;
2189 if (rval < rmin || rval > rmax)
2190 continue;
2191 gval = (pixel >> L_GREEN_SHIFT) & 0xff;
2192 if (gval < gmin || gval > gmax)
2193 continue;
2194 bval = (pixel >> L_BLUE_SHIFT) & 0xff;
2195 if (bval < bmin || bval > bmax)
2196 continue;
2197 SET_DATA_BIT(lined, j);
2198 }
2199 }
2200
2201 return pixd;
2202 }
2203
2204
2205 /*!
2206 * \brief pixGenerateMaskByDiscr32()
2207 *
2208 * \param[in] pixs 32 bpp
2209 * \param[in] refval1 reference rgb value
2210 * \param[in] refval2 reference rgb value
2211 * \param[in] distflag L_MANHATTAN_DISTANCE, L_EUCLIDEAN_DISTANCE
2212 * \return pixd 1 bpp, or NULL on error
2213 *
2214 * <pre>
2215 * Notes:
2216 * (1) Generates a 1 bpp mask pixd, the same size as pixs, where
2217 * the fg pixels in the mask are those where the pixel in pixs
2218 * is "closer" to refval1 than to refval2.
2219 * (2) "Closer" can be defined in several ways, such as:
2220 * ~ manhattan distance (L1)
2221 * ~ euclidean distance (L2)
2222 * ~ majority vote of the individual components
2223 * Here, we have a choice of L1 or L2.
2224 * </pre>
2225 */
2226 PIX *
pixGenerateMaskByDiscr32(PIX * pixs,l_uint32 refval1,l_uint32 refval2,l_int32 distflag)2227 pixGenerateMaskByDiscr32(PIX *pixs,
2228 l_uint32 refval1,
2229 l_uint32 refval2,
2230 l_int32 distflag)
2231 {
2232 l_int32 i, j, w, h, d, wpls, wpld;
2233 l_int32 rref1, gref1, bref1, rref2, gref2, bref2, rval, gval, bval;
2234 l_uint32 pixel, dist1, dist2;
2235 l_uint32 *datas, *datad, *lines, *lined;
2236 PIX *pixd;
2237
2238 PROCNAME("pixGenerateMaskByDiscr32");
2239
2240 if (!pixs)
2241 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
2242 pixGetDimensions(pixs, &w, &h, &d);
2243 if (d != 32)
2244 return (PIX *)ERROR_PTR("not 32 bpp", procName, NULL);
2245 if (distflag != L_MANHATTAN_DISTANCE && distflag != L_EUCLIDEAN_DISTANCE)
2246 return (PIX *)ERROR_PTR("invalid distflag", procName, NULL);
2247
2248 extractRGBValues(refval1, &rref1, &gref1, &bref1);
2249 extractRGBValues(refval2, &rref2, &gref2, &bref2);
2250 pixd = pixCreate(w, h, 1);
2251 pixCopyResolution(pixd, pixs);
2252 pixCopyInputFormat(pixd, pixs);
2253 datas = pixGetData(pixs);
2254 wpls = pixGetWpl(pixs);
2255 datad = pixGetData(pixd);
2256 wpld = pixGetWpl(pixd);
2257 for (i = 0; i < h; i++) {
2258 lines = datas + i * wpls;
2259 lined = datad + i * wpld;
2260 for (j = 0; j < w; j++) {
2261 pixel = lines[j];
2262 extractRGBValues(pixel, &rval, &gval, &bval);
2263 if (distflag == L_MANHATTAN_DISTANCE) {
2264 dist1 = L_ABS(rref1 - rval);
2265 dist2 = L_ABS(rref2 - rval);
2266 dist1 += L_ABS(gref1 - gval);
2267 dist2 += L_ABS(gref2 - gval);
2268 dist1 += L_ABS(bref1 - bval);
2269 dist2 += L_ABS(bref2 - bval);
2270 } else {
2271 dist1 = (rref1 - rval) * (rref1 - rval);
2272 dist2 = (rref2 - rval) * (rref2 - rval);
2273 dist1 += (gref1 - gval) * (gref1 - gval);
2274 dist2 += (gref2 - gval) * (gref2 - gval);
2275 dist1 += (bref1 - bval) * (bref1 - bval);
2276 dist2 += (bref2 - bval) * (bref2 - bval);
2277 }
2278 if (dist1 < dist2)
2279 SET_DATA_BIT(lined, j);
2280 }
2281 }
2282
2283 return pixd;
2284 }
2285
2286
2287 /*----------------------------------------------------------------------*
2288 * Histogram-based grayscale quantization *
2289 *----------------------------------------------------------------------*/
2290 /*!
2291 * \brief pixGrayQuantFromHisto()
2292 *
2293 * \param[in] pixd [optional] quantized pix with cmap; can be null
2294 * \param[in] pixs 8 bpp gray input pix; not cmapped
2295 * \param[in] pixm [optional] mask over pixels in pixs to quantize
2296 * \param[in] minfract minimum fraction of pixels in a set of adjacent
2297 * histo bins that causes the set to be automatically
2298 * set aside as a color in the colormap; must be
2299 * at least 0.01
2300 * \param[in] maxsize maximum number of adjacent bins allowed to represent
2301 * a color, regardless of the population of pixels
2302 * in the bins; must be at least 2
2303 * \return pixd 8 bpp, cmapped, or NULL on error
2304 *
2305 * <pre>
2306 * Notes:
2307 * (1) This is useful for quantizing images with relatively few
2308 * colors, but which may have both color and gray pixels.
2309 * If there are color pixels, it is assumed that an input
2310 * rgb image has been color quantized first so that:
2311 * ~ pixd has a colormap describing the color pixels
2312 * ~ pixm is a mask over the non-color pixels in pixd
2313 * ~ the colormap in pixd, and the color pixels in pixd,
2314 * have been repacked to go from 0 to n-1 (n colors)
2315 * If there are no color pixels, pixd and pixm are both null,
2316 * and all pixels in pixs are quantized to gray.
2317 * (2) A 256-entry histogram is built of the gray values in pixs.
2318 * If pixm exists, the pixels contributing to the histogram are
2319 * restricted to the fg of pixm. A colormap and LUT are generated
2320 * from this histogram. We break up the array into a set
2321 * of intervals, each one constituting a color in the colormap:
2322 * An interval is identified by summing histogram bins until
2323 * either the sum equals or exceeds the %minfract of the total
2324 * number of pixels, or the span itself equals or exceeds %maxsize.
2325 * The color of each bin is always an average of the pixels
2326 * that constitute it.
2327 * (3) Note that we do not specify the number of gray colors in
2328 * the colormap. Instead, we specify two parameters that
2329 * describe the accuracy of the color assignments; this and
2330 * the actual image determine the number of resulting colors.
2331 * (4) If a mask exists and it is not the same size as pixs, make
2332 * a new mask the same size as pixs, with the original mask
2333 * aligned at the UL corners. Set all additional pixels
2334 * in the (larger) new mask set to 1, causing those pixels
2335 * in pixd to be set as gray.
2336 * (5) We estimate the total number of colors (color plus gray);
2337 * if it exceeds 255, return null.
2338 * </pre>
2339 */
2340 PIX *
pixGrayQuantFromHisto(PIX * pixd,PIX * pixs,PIX * pixm,l_float32 minfract,l_int32 maxsize)2341 pixGrayQuantFromHisto(PIX *pixd,
2342 PIX *pixs,
2343 PIX *pixm,
2344 l_float32 minfract,
2345 l_int32 maxsize)
2346 {
2347 l_int32 w, h, wd, hd, wm, hm, wpls, wplm, wpld;
2348 l_int32 nc, nestim, i, j, vals, vald;
2349 l_int32 *lut;
2350 l_uint32 *datas, *datam, *datad, *lines, *linem, *lined;
2351 NUMA *na;
2352 PIX *pixmr; /* resized mask */
2353 PIXCMAP *cmap;
2354
2355 PROCNAME("pixGrayQuantFromHisto");
2356
2357 if (!pixs || pixGetDepth(pixs) != 8)
2358 return (PIX *)ERROR_PTR("pixs undefined or not 8 bpp", procName, NULL);
2359 if (minfract < 0.01) {
2360 L_WARNING("minfract < 0.01; setting to 0.05\n", procName);
2361 minfract = 0.05;
2362 }
2363 if (maxsize < 2) {
2364 L_WARNING("maxsize < 2; setting to 10\n", procName);
2365 maxsize = 10;
2366 }
2367 if ((pixd && !pixm) || (!pixd && pixm))
2368 return (PIX *)ERROR_PTR("(pixd,pixm) not defined together",
2369 procName, NULL);
2370 pixGetDimensions(pixs, &w, &h, NULL);
2371 if (pixd) {
2372 if (pixGetDepth(pixm) != 1)
2373 return (PIX *)ERROR_PTR("pixm not 1 bpp", procName, NULL);
2374 if ((cmap = pixGetColormap(pixd)) == NULL)
2375 return (PIX *)ERROR_PTR("pixd not cmapped", procName, NULL);
2376 pixGetDimensions(pixd, &wd, &hd, NULL);
2377 if (w != wd || h != hd)
2378 return (PIX *)ERROR_PTR("pixs, pixd sizes differ", procName, NULL);
2379 nc = pixcmapGetCount(cmap);
2380 nestim = nc + (l_int32)(1.5 * 255 / maxsize);
2381 fprintf(stderr, "nestim = %d\n", nestim);
2382 if (nestim > 255) {
2383 L_ERROR("Estimate %d colors!\n", procName, nestim);
2384 return (PIX *)ERROR_PTR("probably too many colors", procName, NULL);
2385 }
2386 pixGetDimensions(pixm, &wm, &hm, NULL);
2387 if (w != wm || h != hm) { /* resize the mask */
2388 L_WARNING("mask and dest sizes not equal\n", procName);
2389 pixmr = pixCreateNoInit(w, h, 1);
2390 pixRasterop(pixmr, 0, 0, wm, hm, PIX_SRC, pixm, 0, 0);
2391 pixRasterop(pixmr, wm, 0, w - wm, h, PIX_SET, NULL, 0, 0);
2392 pixRasterop(pixmr, 0, hm, wm, h - hm, PIX_SET, NULL, 0, 0);
2393 } else {
2394 pixmr = pixClone(pixm);
2395 }
2396 } else {
2397 pixd = pixCreateTemplate(pixs);
2398 cmap = pixcmapCreate(8);
2399 pixSetColormap(pixd, cmap);
2400 }
2401 pixCopyResolution(pixd, pixs);
2402 pixCopyInputFormat(pixd, pixs);
2403
2404 /* Use original mask, if it exists, to select gray pixels */
2405 na = pixGetGrayHistogramMasked(pixs, pixm, 0, 0, 1);
2406
2407 /* Fill out the cmap with gray colors, and generate the lut
2408 * for pixel assignment. Issue a warning on failure. */
2409 if (numaFillCmapFromHisto(na, cmap, minfract, maxsize, &lut))
2410 L_ERROR("ran out of colors in cmap!\n", procName);
2411 numaDestroy(&na);
2412
2413 /* Assign the gray pixels to their cmap indices */
2414 datas = pixGetData(pixs);
2415 datad = pixGetData(pixd);
2416 wpls = pixGetWpl(pixs);
2417 wpld = pixGetWpl(pixd);
2418 if (!pixm) {
2419 for (i = 0; i < h; i++) {
2420 lines = datas + i * wpls;
2421 lined = datad + i * wpld;
2422 for (j = 0; j < w; j++) {
2423 vals = GET_DATA_BYTE(lines, j);
2424 vald = lut[vals];
2425 SET_DATA_BYTE(lined, j, vald);
2426 }
2427 }
2428 LEPT_FREE(lut);
2429 return pixd;
2430 }
2431
2432 datam = pixGetData(pixmr);
2433 wplm = pixGetWpl(pixmr);
2434 for (i = 0; i < h; i++) {
2435 lines = datas + i * wpls;
2436 linem = datam + i * wplm;
2437 lined = datad + i * wpld;
2438 for (j = 0; j < w; j++) {
2439 if (!GET_DATA_BIT(linem, j))
2440 continue;
2441 vals = GET_DATA_BYTE(lines, j);
2442 vald = lut[vals];
2443 SET_DATA_BYTE(lined, j, vald);
2444 }
2445 }
2446 pixDestroy(&pixmr);
2447 LEPT_FREE(lut);
2448 return pixd;
2449 }
2450
2451
2452 /*!
2453 * \brief numaFillCmapFromHisto()
2454 *
2455 * \param[in] na histogram of gray values
2456 * \param[in] cmap 8 bpp cmap, possibly initialized with color value
2457 * \param[in] minfract minimum fraction of pixels in a set of adjacent
2458 * histo bins that causes the set to be automatically
2459 * set aside as a color in the colormap; must be
2460 * at least 0.01
2461 * \param[in] maxsize maximum number of adjacent bins allowed to represent
2462 * a color, regardless of the population of pixels
2463 * in the bins; must be at least 2
2464 * \param[out] plut lookup table from gray value to colormap index
2465 * \return 0 if OK, 1 on error
2466 *
2467 * <pre>
2468 * Notes:
2469 * (1) This static function must be called from pixGrayQuantFromHisto()
2470 * </pre>
2471 */
2472 static l_int32
numaFillCmapFromHisto(NUMA * na,PIXCMAP * cmap,l_float32 minfract,l_int32 maxsize,l_int32 ** plut)2473 numaFillCmapFromHisto(NUMA *na,
2474 PIXCMAP *cmap,
2475 l_float32 minfract,
2476 l_int32 maxsize,
2477 l_int32 **plut)
2478 {
2479 l_int32 mincount, index, sum, wtsum, span, istart, i, val, ret;
2480 l_int32 *iahisto, *lut;
2481 l_float32 total;
2482
2483 PROCNAME("numaFillCmapFromHisto");
2484
2485 if (!plut)
2486 return ERROR_INT("&lut not defined", procName, 1);
2487 *plut = NULL;
2488 if (!na)
2489 return ERROR_INT("na not defined", procName, 1);
2490 if (!cmap)
2491 return ERROR_INT("cmap not defined", procName, 1);
2492
2493 numaGetSum(na, &total);
2494 mincount = (l_int32)(minfract * total);
2495 iahisto = numaGetIArray(na);
2496 lut = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
2497 *plut = lut;
2498 index = pixcmapGetCount(cmap); /* start with number of colors
2499 * already reserved */
2500
2501 /* March through, associating colors with sets of adjacent
2502 * gray levels. During the process, the LUT that gives
2503 * the colormap index for each gray level is computed.
2504 * To complete a color, either the total count must equal
2505 * or exceed %mincount, or the current span of colors must
2506 * equal or exceed %maxsize. An empty span is not converted
2507 * into a color; it is simply ignored. When a span is completed for a
2508 * color, the weighted color in the span is added to the colormap. */
2509 sum = 0;
2510 wtsum = 0;
2511 istart = 0;
2512 ret = 0;
2513 for (i = 0; i < 256; i++) {
2514 lut[i] = index;
2515 sum += iahisto[i];
2516 wtsum += i * iahisto[i];
2517 span = i - istart + 1;
2518 if (sum < mincount && span < maxsize)
2519 continue;
2520
2521 if (sum == 0) { /* empty span; don't save */
2522 istart = i + 1;
2523 continue;
2524 }
2525
2526 /* Found new color; sum > 0 */
2527 val = (l_int32)((l_float32)wtsum / (l_float32)sum + 0.5);
2528 ret = pixcmapAddColor(cmap, val, val, val);
2529 istart = i + 1;
2530 sum = 0;
2531 wtsum = 0;
2532 index++;
2533 }
2534 if (istart < 256 && sum > 0) { /* last one */
2535 span = 256 - istart;
2536 val = (l_int32)((l_float32)wtsum / (l_float32)sum + 0.5);
2537 ret = pixcmapAddColor(cmap, val, val, val);
2538 }
2539
2540 LEPT_FREE(iahisto);
2541 return ret;
2542 }
2543
2544
2545 /*----------------------------------------------------------------------*
2546 * Color quantize grayscale image using existing colormap *
2547 *----------------------------------------------------------------------*/
2548 /*!
2549 * \brief pixGrayQuantFromCmap()
2550 *
2551 * \param[in] pixs 8 bpp grayscale without cmap
2552 * \param[in] cmap to quantize to; of dest pix
2553 * \param[in] mindepth minimum depth of pixd: can be 2, 4 or 8 bpp
2554 * \return pixd 2, 4 or 8 bpp, colormapped, or NULL on error
2555 *
2556 * <pre>
2557 * Notes:
2558 * (1) In use, pixs is an 8 bpp grayscale image without a colormap.
2559 * If there is an existing colormap, a warning is issued and
2560 * a copy of the input pixs is returned.
2561 * </pre>
2562 */
2563 PIX *
pixGrayQuantFromCmap(PIX * pixs,PIXCMAP * cmap,l_int32 mindepth)2564 pixGrayQuantFromCmap(PIX *pixs,
2565 PIXCMAP *cmap,
2566 l_int32 mindepth)
2567 {
2568 l_int32 i, j, index, w, h, d, depth, wpls, wpld;
2569 l_int32 hascolor, vals, vald;
2570 l_int32 *tab;
2571 l_uint32 *datas, *datad, *lines, *lined;
2572 PIXCMAP *cmapd;
2573 PIX *pixd;
2574
2575 PROCNAME("pixGrayQuantFromCmap");
2576
2577 if (!pixs)
2578 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
2579 if (pixGetColormap(pixs) != NULL) {
2580 L_WARNING("pixs already has a colormap; returning a copy\n", procName);
2581 return pixCopy(NULL, pixs);
2582 }
2583 pixGetDimensions(pixs, &w, &h, &d);
2584 if (d != 8)
2585 return (PIX *)ERROR_PTR("pixs not 8 bpp", procName, NULL);
2586 if (!cmap)
2587 return (PIX *)ERROR_PTR("cmap not defined", procName, NULL);
2588 if (mindepth != 2 && mindepth != 4 && mindepth != 8)
2589 return (PIX *)ERROR_PTR("invalid mindepth", procName, NULL);
2590
2591 /* Make sure the colormap is gray */
2592 pixcmapHasColor(cmap, &hascolor);
2593 if (hascolor) {
2594 L_WARNING("Converting colormap colors to gray\n", procName);
2595 cmapd = pixcmapColorToGray(cmap, 0.3, 0.5, 0.2);
2596 } else {
2597 cmapd = pixcmapCopy(cmap);
2598 }
2599
2600 /* Make LUT into colormap */
2601 tab = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
2602 for (i = 0; i < 256; i++) {
2603 pixcmapGetNearestGrayIndex(cmapd, i, &index);
2604 tab[i] = index;
2605 }
2606
2607 pixcmapGetMinDepth(cmap, &depth);
2608 depth = L_MAX(depth, mindepth);
2609 pixd = pixCreate(w, h, depth);
2610 pixSetColormap(pixd, cmapd);
2611 pixCopyResolution(pixd, pixs);
2612 pixCopyInputFormat(pixd, pixs);
2613 datas = pixGetData(pixs);
2614 datad = pixGetData(pixd);
2615 wpls = pixGetWpl(pixs);
2616 wpld = pixGetWpl(pixd);
2617 for (i = 0; i < h; i++) {
2618 lines = datas + i * wpls;
2619 lined = datad + i * wpld;
2620 for (j = 0; j < w; j++) {
2621 vals = GET_DATA_BYTE(lines, j);
2622 vald = tab[vals];
2623 if (depth == 2)
2624 SET_DATA_DIBIT(lined, j, vald);
2625 else if (depth == 4)
2626 SET_DATA_QBIT(lined, j, vald);
2627 else /* depth == 8 */
2628 SET_DATA_BYTE(lined, j, vald);
2629 }
2630 }
2631
2632 LEPT_FREE(tab);
2633 return pixd;
2634 }
2635
2636
2637 #if 0 /* Documentation */
2638 /*--------------------------------------------------------------------*
2639 * Implementation of binarization by dithering using LUTs *
2640 * It is archived here. *
2641 *--------------------------------------------------------------------*/
2642 /*!
2643 * \brief pixDitherToBinaryLUT()
2644 *
2645 * \param[in] pixs
2646 * \param[in] lowerclip lower clip distance to black; use -1 for default
2647 * \param[in] upperclip upper clip distance to white; use -1 for default
2648 * \return pixd dithered binary, or NULL on error
2649 *
2650 * We don't need two implementations of Floyd-Steinberg dithering,
2651 * and this one with LUTs is a little more complicated than
2652 * pixDitherToBinary(). It uses three lookup tables to generate the
2653 * output pixel value and the excess or deficit carried over to the
2654 * neighboring pixels. It's here for pedagogical reasons only.
2655 */
2656 PIX *
2657 pixDitherToBinaryLUT(PIX *pixs,
2658 l_int32 lowerclip,
2659 l_int32 upperclip)
2660 {
2661 l_int32 w, h, d, wplt, wpld;
2662 l_int32 *tabval, *tab38, *tab14;
2663 l_uint32 *datat, *datad;
2664 l_uint32 *bufs1, *bufs2;
2665 PIX *pixt, *pixd;
2666
2667 PROCNAME("pixDitherToBinaryLUT");
2668
2669 if (!pixs)
2670 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
2671 pixGetDimensions(pixs, &w, &h, &d);
2672 if (d != 8)
2673 return (PIX *)ERROR_PTR("must be 8 bpp for dithering", procName, NULL);
2674 if (lowerclip < 0)
2675 lowerclip = DEFAULT_CLIP_LOWER_1;
2676 if (upperclip < 0)
2677 upperclip = DEFAULT_CLIP_UPPER_1;
2678
2679 if ((pixd = pixCreate(w, h, 1)) == NULL)
2680 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
2681 pixCopyResolution(pixd, pixs);
2682 pixCopyInputFormat(pixd, pixs);
2683 datad = pixGetData(pixd);
2684 wpld = pixGetWpl(pixd);
2685
2686 /* Remove colormap if it exists */
2687 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
2688 datat = pixGetData(pixt);
2689 wplt = pixGetWpl(pixt);
2690
2691 /* Two line buffers, 1 for current line and 2 for next line */
2692 bufs1 = (l_uint32 *)LEPT_CALLOC(wplt, sizeof(l_uint32));
2693 bufs2 = (l_uint32 *)LEPT_CALLOC(wplt, sizeof(l_uint32));
2694 if (!bufs1 || !bufs2) {
2695 LEPT_FREE(bufs1);
2696 LEPT_FREE(bufs2);
2697 pixDestroy(&pixd);
2698 pixDestroy(&pixt);
2699 return (PIX *)ERROR_PTR("bufs1, bufs2 not both made", procName, NULL);
2700 }
2701
2702 /* 3 lookup tables: 1-bit value, (3/8)excess, and (1/4)excess */
2703 make8To1DitherTables(&tabval, &tab38, &tab14, lowerclip, upperclip);
2704
2705 ditherToBinaryLUTLow(datad, w, h, wpld, datat, wplt, bufs1, bufs2,
2706 tabval, tab38, tab14);
2707
2708 LEPT_FREE(bufs1);
2709 LEPT_FREE(bufs2);
2710 LEPT_FREE(tabval);
2711 LEPT_FREE(tab38);
2712 LEPT_FREE(tab14);
2713 pixDestroy(&pixt);
2714 return pixd;
2715 }
2716
2717 /*!
2718 * \brief ditherToBinaryLUTLow()
2719 *
2720 * Low-level function for doing Floyd-Steinberg error diffusion
2721 * dithering from 8 bpp (datas) to 1 bpp (datad). Two source
2722 * line buffers, bufs1 and bufs2, are provided, along with three
2723 * 256-entry lookup tables: tabval gives the output pixel value,
2724 * tab38 gives the extra (plus or minus) transferred to the pixels
2725 * directly to the left and below, and tab14 gives the extra
2726 * transferred to the diagonal below. The choice of 3/8 and 1/4
2727 * is traditional but arbitrary when you use a lookup table; the
2728 * only constraint is that the sum is 1. See other comments below.
2729 */
2730 void
2731 ditherToBinaryLUTLow(l_uint32 *datad,
2732 l_int32 w,
2733 l_int32 h,
2734 l_int32 wpld,
2735 l_uint32 *datas,
2736 l_int32 wpls,
2737 l_uint32 *bufs1,
2738 l_uint32 *bufs2,
2739 l_int32 *tabval,
2740 l_int32 *tab38,
2741 l_int32 *tab14)
2742 {
2743 l_int32 i;
2744 l_uint32 *lined;
2745
2746 /* do all lines except last line */
2747 memcpy(bufs2, datas, 4 * wpls); /* prime the buffer */
2748 for (i = 0; i < h - 1; i++) {
2749 memcpy(bufs1, bufs2, 4 * wpls);
2750 memcpy(bufs2, datas + (i + 1) * wpls, 4 * wpls);
2751 lined = datad + i * wpld;
2752 ditherToBinaryLineLUTLow(lined, w, bufs1, bufs2,
2753 tabval, tab38, tab14, 0);
2754 }
2755
2756 /* do last line */
2757 memcpy(bufs1, bufs2, 4 * wpls);
2758 lined = datad + (h - 1) * wpld;
2759 ditherToBinaryLineLUTLow(lined, w, bufs1, bufs2, tabval, tab38, tab14, 1);
2760 return;
2761 }
2762
2763 /*!
2764 * \brief ditherToBinaryLineLUTLow()
2765 *
2766 * \param[in] lined ptr to beginning of dest line
2767 * w (width of image in pixels
2768 * \param[in] bufs1 buffer of current source line
2769 * \param[in] bufs2 buffer of next source line
2770 * \param[in] tabval value to assign for current pixel
2771 * \param[in] tab38 excess value to give to neighboring 3/8 pixels
2772 * \param[in] tab14 excess value to give to neighboring 1/4 pixel
2773 * \param[in] lastlineflag 0 if not last dest line, 1 if last dest line
2774 * \return void
2775 */
2776 void
2777 ditherToBinaryLineLUTLow(l_uint32 *lined,
2778 l_int32 w,
2779 l_uint32 *bufs1,
2780 l_uint32 *bufs2,
2781 l_int32 *tabval,
2782 l_int32 *tab38,
2783 l_int32 *tab14,
2784 l_int32 lastlineflag)
2785 {
2786 l_int32 j;
2787 l_int32 oval, tab38val, tab14val;
2788 l_uint8 rval, bval, dval;
2789
2790 if (lastlineflag == 0) {
2791 for (j = 0; j < w - 1; j++) {
2792 oval = GET_DATA_BYTE(bufs1, j);
2793 if (tabval[oval])
2794 SET_DATA_BIT(lined, j);
2795 rval = GET_DATA_BYTE(bufs1, j + 1);
2796 bval = GET_DATA_BYTE(bufs2, j);
2797 dval = GET_DATA_BYTE(bufs2, j + 1);
2798 tab38val = tab38[oval];
2799 if (tab38val == 0)
2800 continue;
2801 tab14val = tab14[oval];
2802 if (tab38val < 0) {
2803 rval = L_MAX(0, rval + tab38val);
2804 bval = L_MAX(0, bval + tab38val);
2805 dval = L_MAX(0, dval + tab14val);
2806 } else {
2807 rval = L_MIN(255, rval + tab38val);
2808 bval = L_MIN(255, bval + tab38val);
2809 dval = L_MIN(255, dval + tab14val);
2810 }
2811 SET_DATA_BYTE(bufs1, j + 1, rval);
2812 SET_DATA_BYTE(bufs2, j, bval);
2813 SET_DATA_BYTE(bufs2, j + 1, dval);
2814 }
2815
2816 /* do last column: j = w - 1 */
2817 oval = GET_DATA_BYTE(bufs1, j);
2818 if (tabval[oval])
2819 SET_DATA_BIT(lined, j);
2820 bval = GET_DATA_BYTE(bufs2, j);
2821 tab38val = tab38[oval];
2822 if (tab38val < 0) {
2823 bval = L_MAX(0, bval + tab38val);
2824 SET_DATA_BYTE(bufs2, j, bval);
2825 } else if (tab38val > 0 ) {
2826 bval = L_MIN(255, bval + tab38val);
2827 SET_DATA_BYTE(bufs2, j, bval);
2828 }
2829 } else { /* lastlineflag == 1 */
2830 for (j = 0; j < w - 1; j++) {
2831 oval = GET_DATA_BYTE(bufs1, j);
2832 if (tabval[oval])
2833 SET_DATA_BIT(lined, j);
2834 rval = GET_DATA_BYTE(bufs1, j + 1);
2835 tab38val = tab38[oval];
2836 if (tab38val == 0)
2837 continue;
2838 if (tab38val < 0)
2839 rval = L_MAX(0, rval + tab38val);
2840 else
2841 rval = L_MIN(255, rval + tab38val);
2842 SET_DATA_BYTE(bufs1, j + 1, rval);
2843 }
2844
2845 /* do last pixel: (i, j) = (h - 1, w - 1) */
2846 oval = GET_DATA_BYTE(bufs1, j);
2847 if (tabval[oval])
2848 SET_DATA_BIT(lined, j);
2849 }
2850
2851 return;
2852 }
2853
2854 /*!
2855 * \brief make8To1DitherTables()
2856 *
2857 * \param[out] ptabval value assigned to output pixel; 0 or 1
2858 * \param[out] ptab38 amount propagated to pixels left and below
2859 * \param[out] ptab14 amount propagated to pixel to left and down
2860 * \param[in] lowerclip values near 0 where the excess is not propagated
2861 * \param[in] upperclip values near 255 where the deficit is not propagated
2862 *
2863 * \return 0 if OK, 1 on error
2864 */
2865 l_int32
2866 make8To1DitherTables(l_int32 **ptabval,
2867 l_int32 **ptab38,
2868 l_int32 **ptab14,
2869 l_int32 lowerclip,
2870 l_int32 upperclip)
2871 {
2872 l_int32 i;
2873 l_int32 *tabval, *tab38, *tab14;
2874
2875 PROCNAME("make8To1DitherTables");
2876
2877 if (ptabval) *ptabval = NULL;
2878 if (ptab38) *ptab38 = NULL;
2879 if (ptab14) *ptab14 = NULL;
2880 if (!ptabval || !ptab38 || !ptab14)
2881 return ERROR_INT("table ptrs not all defined", procName, 1);
2882
2883 /* 3 lookup tables: 1-bit value, (3/8)excess, and (1/4)excess */
2884 tabval = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
2885 tab38 = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
2886 tab14 = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
2887 if (!tabval || !tab38 || !tab14)
2888 return ERROR_INT("calloc failure to make small table", procName, 1);
2889 *ptabval = tabval;
2890 *ptab38 = tab38;
2891 *ptab14 = tab14;
2892
2893 for (i = 0; i < 256; i++) {
2894 if (i <= lowerclip) {
2895 tabval[i] = 1;
2896 tab38[i] = 0;
2897 tab14[i] = 0;
2898 } else if (i < 128) {
2899 tabval[i] = 1;
2900 tab38[i] = (3 * i + 4) / 8;
2901 tab14[i] = (i + 2) / 4;
2902 } else if (i < 255 - upperclip) {
2903 tabval[i] = 0;
2904 tab38[i] = (3 * (i - 255) + 4) / 8;
2905 tab14[i] = ((i - 255) + 2) / 4;
2906 } else { /* i >= 255 - upperclip */
2907 tabval[i] = 0;
2908 tab38[i] = 0;
2909 tab14[i] = 0;
2910 }
2911 }
2912
2913 return 0;
2914 }
2915 #endif /* Documentation */
2916