1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 - This software is distributed in the hope that it will be
4 - useful, but with NO WARRANTY OF ANY KIND.
5 - No author or distributor accepts responsibility to anyone for the
6 - consequences of using this software, or for whether it serves any
7 - particular purpose or works at all, unless he or she says so in
8 - writing. Everyone is granted permission to copy, modify and
9 - redistribute this source code, for commercial or non-commercial
10 - purposes, with the following restrictions: (1) the origin of this
11 - source code must not be misrepresented; (2) modified versions must
12 - be plainly marked as such; and (3) this notice may not be removed
13 - or altered from any source or modified source distribution.
14 *====================================================================*/
15
16 /*
17 * grayquant.c
18 *
19 * Thresholding from 8 bpp to 1 bpp
20 *
21 * Floyd-Steinberg dithering to binary
22 * PIX *pixDitherToBinary()
23 * PIX *pixDitherToBinarySpec()
24 *
25 * Simple (pixelwise) binarization with fixed threshold
26 * PIX *pixThresholdToBinary()
27 *
28 * Binarization with variable threshold
29 * PIX *pixVarThresholdToBinary()
30 *
31 * Slower implementation of Floyd-Steinberg dithering, using LUTs
32 * PIX *pixDitherToBinaryLUT()
33 *
34 * Generate a binary mask from pixels of particular values
35 * PIX *pixGenerateMaskByValue()
36 * PIX *pixGenerateMaskByBand()
37 *
38 * Thresholding from 8 bpp to 2 bpp
39 *
40 * Dithering to 2 bpp
41 * PIX *pixDitherTo2bpp()
42 * PIX *pixDitherTo2bppSpec()
43 *
44 * Simple (pixelwise) thresholding to 2 bpp with optional cmap
45 * PIX *pixThresholdTo2bpp()
46 *
47 * Simple (pixelwise) thresholding from 8 bpp to 4 bpp
48 * PIX *pixThresholdTo4bpp()
49 *
50 * Simple (pixelwise) quantization on 8 bpp grayscale
51 * PIX *pixThresholdOn8bpp()
52 *
53 * Arbitrary (pixelwise) thresholding from 8 bpp to 2, 4 or 8 bpp
54 * PIX *pixThresholdGrayArb()
55 *
56 * Quantization tables for linear thresholds of grayscale images
57 * l_int32 *makeGrayQuantIndexTable()
58 * l_int32 *makeGrayQuantTargetTable()
59 *
60 * Quantization table for arbitrary thresholding of grayscale images
61 * l_int32 makeGrayQuantTableArb()
62 * l_int32 makeGrayQuantColormapArb()
63 *
64 * Thresholding from 32 bpp rgb to 1 bpp
65 * (really color quantization, but it's better placed in this file)
66 * PIX *pixGenerateMaskByBand32()
67 * PIX *pixGenerateMaskByDiscr32()
68 *
69 * Histogram-based grayscale quantization
70 * PIX *pixGrayQuantFromHisto()
71 * static l_int32 numaFillCmapFromHisto()
72 *
73 * Color quantize grayscale image using existing colormap
74 * PIX *pixGrayQuantFromCmap()
75 */
76
77 #include <stdio.h>
78 #include <stdlib.h>
79 #include <string.h>
80 #include <math.h>
81 #include "allheaders.h"
82
83
84 static l_int32 numaFillCmapFromHisto(NUMA *na, PIXCMAP *cmap,
85 l_float32 minfract, l_int32 maxsize,
86 l_int32 **plut);
87
88
89 /*------------------------------------------------------------------*
90 * Binarization by Floyd-Steinberg dithering *
91 *------------------------------------------------------------------*/
92 /*!
93 * pixDitherToBinary()
94 *
95 * Input: pixs
96 * Return: pixd (dithered binary), or null on error
97 *
98 * The Floyd-Steinberg error diffusion dithering algorithm
99 * binarizes an 8 bpp grayscale image to a threshold of 128.
100 * If a pixel has a value above 127, it is binarized to white
101 * and the excess (below 255) is subtracted from three
102 * neighboring pixels in the fractions 3/8 to (i, j+1),
103 * 3/8 to (i+1, j) and 1/4 to (i+1,j+1), truncating to 0
104 * if necessary. Likewise, if it the pixel has a value
105 * below 128, it is binarized to black and the excess above 0
106 * is added to the neighboring pixels, truncating to 255 if necessary.
107 *
108 * This function differs from straight dithering in that it allows
109 * clipping of grayscale to 0 or 255 if the values are
110 * sufficiently close, without distribution of the excess.
111 * This uses default values to specify the range of lower
112 * and upper values (near 0 and 255, rsp) that are clipped
113 * to black and white without propagating the excess.
114 * Not propagating the excess has the effect of reducing the
115 * snake patterns in parts of the image that are nearly black or white;
116 * however, it also prevents the attempt to reproduce gray for those values.
117 *
118 * The implementation is straightforward. It uses a pair of
119 * line buffers to avoid changing pixs. It is about 2x faster
120 * than the implementation using LUTs.
121 */
122 PIX *
pixDitherToBinary(PIX * pixs)123 pixDitherToBinary(PIX *pixs)
124 {
125 PROCNAME("pixDitherToBinary");
126
127 if (!pixs)
128 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
129 if (pixGetDepth(pixs) != 8)
130 return (PIX *)ERROR_PTR("must be 8 bpp for dithering", procName, NULL);
131
132 return pixDitherToBinarySpec(pixs, DEFAULT_CLIP_LOWER_1,
133 DEFAULT_CLIP_UPPER_1);
134 }
135
136
137 /*!
138 * pixDitherToBinarySpec()
139 *
140 * Input: pixs
141 * lowerclip (lower clip distance to black; use 0 for default)
142 * upperclip (upper clip distance to white; use 0 for default)
143 * Return: pixd (dithered binary), or null on error
144 *
145 * Notes:
146 * (1) See comments above in pixDitherToBinary() for details.
147 * (2) The input parameters lowerclip and upperclip specify the range
148 * of lower and upper values (near 0 and 255, rsp) that are
149 * clipped to black and white without propagating the excess.
150 * For that reason, lowerclip and upperclip should be small numbers.
151 */
152 PIX *
pixDitherToBinarySpec(PIX * pixs,l_int32 lowerclip,l_int32 upperclip)153 pixDitherToBinarySpec(PIX *pixs,
154 l_int32 lowerclip,
155 l_int32 upperclip)
156 {
157 l_int32 w, h, d, wplt, wpld;
158 l_uint32 *datat, *datad;
159 l_uint32 *bufs1, *bufs2;
160 PIX *pixt, *pixd;
161
162 PROCNAME("pixDitherToBinarySpec");
163
164 if (!pixs)
165 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
166 pixGetDimensions(pixs, &w, &h, &d);
167 if (d != 8)
168 return (PIX *)ERROR_PTR("must be 8 bpp for dithering", procName, NULL);
169 if (lowerclip < 0 || lowerclip > 255)
170 return (PIX *)ERROR_PTR("invalid value for lowerclip", procName, NULL);
171 if (upperclip < 0 || upperclip > 255)
172 return (PIX *)ERROR_PTR("invalid value for upperclip", procName, NULL);
173
174 if ((pixd = pixCreate(w, h, 1)) == NULL)
175 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
176 pixCopyResolution(pixd, pixs);
177 datad = pixGetData(pixd);
178 wpld = pixGetWpl(pixd);
179
180 /* Remove colormap if it exists */
181 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
182 datat = pixGetData(pixt);
183 wplt = pixGetWpl(pixt);
184
185 /* Two line buffers, 1 for current line and 2 for next line */
186 if ((bufs1 = (l_uint32 *)CALLOC(wplt, sizeof(l_uint32))) == NULL)
187 return (PIX *)ERROR_PTR("bufs1 not made", procName, NULL);
188 if ((bufs2 = (l_uint32 *)CALLOC(wplt, sizeof(l_uint32))) == NULL)
189 return (PIX *)ERROR_PTR("bufs2 not made", procName, NULL);
190
191 ditherToBinaryLow(datad, w, h, wpld, datat, wplt, bufs1, bufs2,
192 lowerclip, upperclip);
193
194 FREE(bufs1);
195 FREE(bufs2);
196 pixDestroy(&pixt);
197
198 return pixd;
199 }
200
201
202 /*------------------------------------------------------------------*
203 * Simple (pixelwise) binarization with fixed threshold *
204 *------------------------------------------------------------------*/
205 /*!
206 * pixThresholdToBinary()
207 *
208 * Input: pixs (4 or 8 bpp)
209 * threshold value
210 * Return: pixd (1 bpp), or null on error
211 *
212 * Notes:
213 * (1) If the source pixel is less than the threshold value,
214 * the dest will be 1; otherwise, it will be 0
215 */
216 PIX *
pixThresholdToBinary(PIX * pixs,l_int32 thresh)217 pixThresholdToBinary(PIX *pixs,
218 l_int32 thresh)
219 {
220 l_int32 d, w, h, wplt, wpld;
221 l_uint32 *datat, *datad;
222 PIX *pixt, *pixd;
223
224 PROCNAME("pixThresholdToBinary");
225
226 if (!pixs)
227 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
228 pixGetDimensions(pixs, &w, &h, &d);
229 if (d != 4 && d != 8)
230 return (PIX *)ERROR_PTR("pixs must be 4 or 8 bpp", procName, NULL);
231 if (thresh < 0)
232 return (PIX *)ERROR_PTR("thresh must be non-negative", procName, NULL);
233 if (d == 4 && thresh > 16)
234 return (PIX *)ERROR_PTR("4 bpp thresh not in {0-16}", procName, NULL);
235 if (d == 8 && thresh > 256)
236 return (PIX *)ERROR_PTR("8 bpp thresh not in {0-256}", procName, NULL);
237
238 if ((pixd = pixCreate(w, h, 1)) == NULL)
239 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
240 pixCopyResolution(pixd, pixs);
241 datad = pixGetData(pixd);
242 wpld = pixGetWpl(pixd);
243
244 /* Remove colormap if it exists. If there is a colormap,
245 * pixt will be 8 bpp regardless of the depth of pixs. */
246 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
247 datat = pixGetData(pixt);
248 wplt = pixGetWpl(pixt);
249 if (pixGetColormap(pixs) && d == 4) { /* promoted to 8 bpp */
250 d = 8;
251 thresh *= 16;
252 }
253
254 thresholdToBinaryLow(datad, w, h, wpld, datat, d, wplt, thresh);
255 pixDestroy(&pixt);
256 return pixd;
257 }
258
259
260 /*------------------------------------------------------------------*
261 * Binarization with variable threshold *
262 *------------------------------------------------------------------*/
263 /*!
264 * pixVarThresholdToBinary()
265 *
266 * Input: pixs (8 bpp)
267 * pixg (8 bpp; contains threshold values for each pixel)
268 * Return: pixd (1 bpp), or null on error
269 *
270 * Notes:
271 * (1) If the pixel in pixs is less than the corresponding pixel
272 * in pixg, the dest will be 1; otherwise it will be 0.
273 */
274 PIX *
pixVarThresholdToBinary(PIX * pixs,PIX * pixg)275 pixVarThresholdToBinary(PIX *pixs,
276 PIX *pixg)
277 {
278 l_int32 i, j, vals, valg, w, h, d, wpls, wplg, wpld;
279 l_uint32 *datas, *datag, *datad, *lines, *lineg, *lined;
280 PIX *pixd;
281
282 PROCNAME("pixVarThresholdToBinary");
283
284 if (!pixs)
285 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
286 if (!pixg)
287 return (PIX *)ERROR_PTR("pixg not defined", procName, NULL);
288 if (!pixSizesEqual(pixs, pixg))
289 return (PIX *)ERROR_PTR("pix sizes not equal", procName, NULL);
290 pixGetDimensions(pixs, &w, &h, &d);
291 if (d != 8)
292 return (PIX *)ERROR_PTR("pixs must be 8 bpp", procName, NULL);
293
294 pixd = pixCreate(w, h, 1);
295 datad = pixGetData(pixd);
296 wpld = pixGetWpl(pixd);
297 datas = pixGetData(pixs);
298 wpls = pixGetWpl(pixs);
299 datag = pixGetData(pixg);
300 wplg = pixGetWpl(pixg);
301 for (i = 0; i < h; i++) {
302 lines = datas + i * wpls;
303 lineg = datag + i * wplg;
304 lined = datad + i * wpld;
305 for (j = 0; j < w; j++) {
306 vals = GET_DATA_BYTE(lines, j);
307 valg = GET_DATA_BYTE(lineg, j);
308 if (vals < valg)
309 SET_DATA_BIT(lined, j);
310 }
311 }
312
313 return pixd;
314 }
315
316
317 /*--------------------------------------------------------------------*
318 * Slower implementation of binarization by dithering using LUTs *
319 *--------------------------------------------------------------------*/
320 /*!
321 * pixDitherToBinaryLUT()
322 *
323 * Input: pixs
324 * lowerclip (lower clip distance to black; use -1 for default)
325 * upperclip (upper clip distance to white; use -1 for default)
326 * Return: pixd (dithered binary), or null on error
327 *
328 * This implementation is deprecated. You should use pixDitherToBinary().
329 *
330 * See comments in pixDitherToBinary()
331 *
332 * This implementation additionally uses three lookup tables to
333 * generate the output pixel value and the excess or deficit
334 * carried over to the neighboring pixels.
335 */
336 PIX *
pixDitherToBinaryLUT(PIX * pixs,l_int32 lowerclip,l_int32 upperclip)337 pixDitherToBinaryLUT(PIX *pixs,
338 l_int32 lowerclip,
339 l_int32 upperclip)
340 {
341 l_int32 w, h, d, wplt, wpld;
342 l_int32 *tabval, *tab38, *tab14;
343 l_uint32 *datat, *datad;
344 l_uint32 *bufs1, *bufs2;
345 PIX *pixt, *pixd;
346
347 PROCNAME("pixDitherToBinaryLUT");
348
349 if (!pixs)
350 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
351 pixGetDimensions(pixs, &w, &h, &d);
352 if (d != 8)
353 return (PIX *)ERROR_PTR("must be 8 bpp for dithering", procName, NULL);
354 if (lowerclip < 0)
355 lowerclip = DEFAULT_CLIP_LOWER_1;
356 if (upperclip < 0)
357 upperclip = DEFAULT_CLIP_UPPER_1;
358
359 if ((pixd = pixCreate(w, h, 1)) == NULL)
360 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
361 pixCopyResolution(pixd, pixs);
362 datad = pixGetData(pixd);
363 wpld = pixGetWpl(pixd);
364
365 /* Remove colormap if it exists */
366 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
367 datat = pixGetData(pixt);
368 wplt = pixGetWpl(pixt);
369
370 /* Two line buffers, 1 for current line and 2 for next line */
371 if ((bufs1 = (l_uint32 *)CALLOC(wplt, sizeof(l_uint32))) == NULL)
372 return (PIX *)ERROR_PTR("bufs1 not made", procName, NULL);
373 if ((bufs2 = (l_uint32 *)CALLOC(wplt, sizeof(l_uint32))) == NULL)
374 return (PIX *)ERROR_PTR("bufs2 not made", procName, NULL);
375
376 /* 3 lookup tables: 1-bit value, (3/8)excess, and (1/4)excess */
377 make8To1DitherTables(&tabval, &tab38, &tab14, lowerclip, upperclip);
378
379 ditherToBinaryLUTLow(datad, w, h, wpld, datat, wplt, bufs1, bufs2,
380 tabval, tab38, tab14);
381
382 FREE(bufs1);
383 FREE(bufs2);
384 FREE(tabval);
385 FREE(tab38);
386 FREE(tab14);
387 pixDestroy(&pixt);
388
389 return pixd;
390 }
391
392
393 /*--------------------------------------------------------------------*
394 * Generate a binary mask from pixels of particular value(s) *
395 *--------------------------------------------------------------------*/
396 /*!
397 * pixGenerateMaskByValue()
398 *
399 * Input: pixs (8 bpp, or colormapped)
400 * val (of pixels for which we set 1 in dest)
401 * Return: pixd (1 bpp), or null on error
402 *
403 * Notes:
404 * (1) @val is the gray value of the pixels that we are selecting.
405 * (2) If pixs is colormapped, this first removes the colormap to
406 * generate an approximate grayscale value for each pixel, and
407 * then looks for gray pixels with the value @val.
408 * (3) If pixs is colormapped and you want to use @val to select
409 * the colormap index, you must first call pixDestroyColormap(pixs)
410 * to remove the colormap from pixs.
411 */
412 PIX *
pixGenerateMaskByValue(PIX * pixs,l_int32 val)413 pixGenerateMaskByValue(PIX *pixs,
414 l_int32 val)
415 {
416 l_int32 i, j, w, h, wplg, wpld;
417 l_uint32 *datag, *datad, *lineg, *lined;
418 PIX *pixg, *pixd;
419
420 PROCNAME("pixGenerateMaskByValue");
421
422 if (!pixs)
423 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
424 if (pixGetDepth(pixs) != 8)
425 return (PIX *)ERROR_PTR("not 8 bpp", procName, NULL);
426 if (val < 0 || val > 255)
427 return (PIX *)ERROR_PTR("val out of 8 bpp range", procName, NULL);
428
429 if (pixGetColormap(pixs))
430 pixg = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
431 else
432 pixg = pixClone(pixs);
433
434 pixGetDimensions(pixg, &w, &h, NULL);
435 pixd = pixCreate(w, h, 1);
436 pixCopyResolution(pixd, pixg);
437 datag = pixGetData(pixg);
438 wplg = pixGetWpl(pixg);
439 datad = pixGetData(pixd);
440 wpld = pixGetWpl(pixd);
441 for (i = 0; i < h; i++) {
442 lineg = datag + i * wplg;
443 lined = datad + i * wpld;
444 for (j = 0; j < w; j++) {
445 if (GET_DATA_BYTE(lineg, j) == val)
446 SET_DATA_BIT(lined, j);
447 }
448 }
449
450 pixDestroy(&pixg);
451 return pixd;
452 }
453
454
455 /*!
456 * pixGenerateMaskByBand()
457 *
458 * Input: pixs (8 bpp, or colormapped)
459 * lower, upper (two pixel values from which a range, either
460 * between (inband) or outside of (!inband),
461 * determines which pixels in pixs cause us to
462 * set a 1 in the dest mask)
463 * inband (1 for finding pixels in [lower, upper];
464 * 0 for finding pixels in [0, lower) union (upper, 255])
465 * Return: pixd (1 bpp), or null on error
466 *
467 * Notes:
468 * (1) Generates a 1 bpp mask pixd, the same size as pixs, where
469 * the fg pixels in the mask are those either within the specified
470 * band (for inband == 1) or outside the specified band
471 * (for inband == 0).
472 * (2) If pixs is colormapped, this first removes the colormap to
473 * generate an approximate grayscale value for each pixel, and
474 * then looks for gray pixels in or out of the given band.
475 * (3) If pixs is colormapped and you want to the band of values to
476 * select the colormap indices directly, you must first call
477 * pixDestroyColormap(pixs) to remove the colormap from pixs.
478 */
479 PIX *
pixGenerateMaskByBand(PIX * pixs,l_int32 lower,l_int32 upper,l_int32 inband)480 pixGenerateMaskByBand(PIX *pixs,
481 l_int32 lower,
482 l_int32 upper,
483 l_int32 inband)
484 {
485 l_int32 i, j, w, h, wplg, wpld, val;
486 l_uint32 *datag, *datad, *lineg, *lined;
487 PIX *pixg, *pixd;
488
489 PROCNAME("pixGenerateMaskByBand");
490
491 if (!pixs)
492 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
493 if (pixGetDepth(pixs) != 8)
494 return (PIX *)ERROR_PTR("not 8 bpp", procName, NULL);
495 if (lower < 0 || upper > 255)
496 return (PIX *)ERROR_PTR("invalid lower and/or upper", procName, NULL);
497 if (lower > upper)
498 return (PIX *)ERROR_PTR("lower > upper!", procName, NULL);
499
500 if (pixGetColormap(pixs))
501 pixg = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
502 else
503 pixg = pixClone(pixs);
504
505 pixGetDimensions(pixg, &w, &h, NULL);
506 pixd = pixCreate(w, h, 1);
507 pixCopyResolution(pixd, pixg);
508 datag = pixGetData(pixg);
509 wplg = pixGetWpl(pixg);
510 datad = pixGetData(pixd);
511 wpld = pixGetWpl(pixd);
512 for (i = 0; i < h; i++) {
513 lineg = datag + i * wplg;
514 lined = datad + i * wpld;
515 for (j = 0; j < w; j++) {
516 val = GET_DATA_BYTE(lineg, j);
517 if (inband) {
518 if (val >= lower && val <= upper)
519 SET_DATA_BIT(lined, j);
520 }
521 else { /* out of band */
522 if (val < lower || val > upper)
523 SET_DATA_BIT(lined, j);
524 }
525 }
526 }
527
528 pixDestroy(&pixg);
529 return pixd;
530 }
531
532
533 /*------------------------------------------------------------------*
534 * Thresholding to 2 bpp by dithering *
535 *------------------------------------------------------------------*/
536 /*!
537 * pixDitherTo2bpp()
538 *
539 * Input: pixs (8 bpp)
540 * cmapflag (1 to generate a colormap)
541 * Return: pixd (dithered 2 bpp), or null on error
542 *
543 * An analog of the Floyd-Steinberg error diffusion dithering
544 * algorithm is used to "dibitize" an 8 bpp grayscale image
545 * to 2 bpp, using equally spaced gray values of 0, 85, 170, and 255,
546 * which are served by thresholds of 43, 128 and 213.
547 * If cmapflag == 1, the colormap values are set to 0, 85, 170 and 255.
548 * If a pixel has a value between 0 and 42, it is dibitized
549 * to 0, and the excess (above 0) is added to the
550 * three neighboring pixels, in the fractions 3/8 to (i, j+1),
551 * 3/8 to (i+1, j) and 1/4 to (i+1, j+1), truncating to 255 if
552 * necessary. If a pixel has a value between 43 and 127, it is
553 * dibitized to 1, and the excess (above 85) is added to the three
554 * neighboring pixels as before. If the value is below 85, the
555 * excess is subtracted. With a value between 128
556 * and 212, it is dibitized to 2, with the excess on either side
557 * of 170 distributed as before. Finally, with a value between
558 * 213 and 255, it is dibitized to 3, with the excess (below 255)
559 * subtracted from the neighbors. We always truncate to 0 or 255.
560 * The details can be seen in the lookup table generation.
561 *
562 * This function differs from straight dithering in that it allows
563 * clipping of grayscale to 0 or 255 if the values are
564 * sufficiently close, without distribution of the excess.
565 * This uses default values (from pix.h) to specify the range of lower
566 * and upper values (near 0 and 255, rsp) that are clipped to black
567 * and white without propagating the excess.
568 * Not propagating the excess has the effect of reducing the snake
569 * patterns in parts of the image that are nearly black or white;
570 * however, it also prevents any attempt to reproduce gray for those values.
571 *
572 * The implementation uses 3 lookup tables for simplicity, and
573 * a pair of line buffers to avoid modifying pixs.
574 */
575 PIX *
pixDitherTo2bpp(PIX * pixs,l_int32 cmapflag)576 pixDitherTo2bpp(PIX *pixs,
577 l_int32 cmapflag)
578 {
579 PROCNAME("pixDitherTo2bpp");
580
581 if (!pixs)
582 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
583 if (pixGetDepth(pixs) != 8)
584 return (PIX *)ERROR_PTR("must be 8 bpp for dithering", procName, NULL);
585
586 return pixDitherTo2bppSpec(pixs, DEFAULT_CLIP_LOWER_2,
587 DEFAULT_CLIP_UPPER_2, cmapflag);
588 }
589
590
591 /*!
592 * pixDitherTo2bppSpec()
593 *
594 * Input: pixs (8 bpp)
595 * lowerclip (lower clip distance to black; use 0 for default)
596 * upperclip (upper clip distance to white; use 0 for default)
597 * cmapflag (1 to generate a colormap)
598 * Return: pixd (dithered 2 bpp), or null on error
599 *
600 * Notes:
601 * (1) See comments above in pixDitherTo2bpp() for details.
602 * (2) The input parameters lowerclip and upperclip specify the range
603 * of lower and upper values (near 0 and 255, rsp) that are
604 * clipped to black and white without propagating the excess.
605 * For that reason, lowerclip and upperclip should be small numbers.
606 */
607 PIX *
pixDitherTo2bppSpec(PIX * pixs,l_int32 lowerclip,l_int32 upperclip,l_int32 cmapflag)608 pixDitherTo2bppSpec(PIX *pixs,
609 l_int32 lowerclip,
610 l_int32 upperclip,
611 l_int32 cmapflag)
612 {
613 l_int32 w, h, d, wplt, wpld;
614 l_int32 *tabval, *tab38, *tab14;
615 l_uint32 *datat, *datad;
616 l_uint32 *bufs1, *bufs2;
617 PIX *pixt, *pixd;
618 PIXCMAP *cmap;
619
620 PROCNAME("pixDitherTo2bppSpec");
621
622 if (!pixs)
623 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
624 pixGetDimensions(pixs, &w, &h, &d);
625 if (d != 8)
626 return (PIX *)ERROR_PTR("must be 8 bpp for dithering", procName, NULL);
627 if (lowerclip < 0 || lowerclip > 255)
628 return (PIX *)ERROR_PTR("invalid value for lowerclip", procName, NULL);
629 if (upperclip < 0 || upperclip > 255)
630 return (PIX *)ERROR_PTR("invalid value for upperclip", procName, NULL);
631
632 if ((pixd = pixCreate(w, h, 2)) == NULL)
633 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
634 pixCopyResolution(pixd, pixs);
635 datad = pixGetData(pixd);
636 wpld = pixGetWpl(pixd);
637
638 /* If there is a colormap, remove it */
639 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
640 datat = pixGetData(pixt);
641 wplt = pixGetWpl(pixt);
642
643 /* Two line buffers, 1 for current line and 2 for next line */
644 if ((bufs1 = (l_uint32 *)CALLOC(wplt, sizeof(l_uint32))) == NULL)
645 return (PIX *)ERROR_PTR("bufs1 not made", procName, NULL);
646 if ((bufs2 = (l_uint32 *)CALLOC(wplt, sizeof(l_uint32))) == NULL)
647 return (PIX *)ERROR_PTR("bufs2 not made", procName, NULL);
648
649 /* 3 lookup tables: 2-bit value, (3/8)excess, and (1/4)excess */
650 make8To2DitherTables(&tabval, &tab38, &tab14, lowerclip, upperclip);
651
652 ditherTo2bppLow(datad, w, h, wpld, datat, wplt, bufs1, bufs2,
653 tabval, tab38, tab14);
654
655 if (cmapflag) {
656 cmap = pixcmapCreateLinear(2, 4);
657 pixSetColormap(pixd, cmap);
658 }
659
660 FREE(bufs1);
661 FREE(bufs2);
662 FREE(tabval);
663 FREE(tab38);
664 FREE(tab14);
665 pixDestroy(&pixt);
666
667 return pixd;
668 }
669
670
671 /*--------------------------------------------------------------------*
672 * Simple (pixelwise) thresholding to 2 bpp with optional colormap *
673 *--------------------------------------------------------------------*/
674 /*!
675 * pixThresholdTo2bpp()
676 *
677 * Input: pixs (8 bpp)
678 * nlevels (equally spaced; must be between 2 and 4)
679 * cmapflag (1 to build colormap; 0 otherwise)
680 * Return: pixd (2 bpp, optionally with colormap), or null on error
681 *
682 * Notes:
683 * (1) Valid values for nlevels is the set {2, 3, 4}.
684 * (2) Any colormap on the input pixs is removed to 8 bpp grayscale.
685 * (3) This function is typically invoked with cmapflag == 1.
686 * In the situation where no colormap is desired, nlevels is
687 * ignored and pixs is thresholded to 4 levels.
688 * (4) The target output colors are equally spaced, with the
689 * darkest at 0 and the lightest at 255. The thresholds are
690 * chosen halfway between adjacent output values. A table
691 * is built that specifies the mapping from src to dest.
692 * (5) If cmapflag == 1, a colormap of size 'nlevels' is made,
693 * and the pixel values in pixs are replaced by their
694 * appropriate color indices. The number of holdouts,
695 * 4 - nlevels, will be between 0 and 2.
696 * (6) If you don't want the thresholding to be equally spaced,
697 * either first transform the 8 bpp src using pixGammaTRC().
698 * or, if cmapflag == 1, after calling this function you can use
699 * pixcmapResetColor() to change any individual colors.
700 * (7) If a colormap is generated, it will specify (to display
701 * programs) exactly how each level is to be represented in RGB
702 * space. When representing text, 3 levels is far better than
703 * 2 because of the antialiasing of the single gray level,
704 * and 4 levels (black, white and 2 gray levels) is getting
705 * close to the perceptual quality of a (nearly continuous)
706 * grayscale image. With 2 bpp, you can set up a colormap
707 * and allocate from 2 to 4 levels to represent antialiased text.
708 * Any left over colormap entries can be used for coloring regions.
709 * For the same number of levels, the file size of a 2 bpp image
710 * is about 10% smaller than that of a 4 bpp result for the same
711 * number of levels. For both 2 bpp and 4 bpp, using 4 levels you
712 * get compression far better than that of jpeg, because the
713 * quantization to 4 levels will remove the jpeg ringing in the
714 * background near character edges.
715 */
716 PIX *
pixThresholdTo2bpp(PIX * pixs,l_int32 nlevels,l_int32 cmapflag)717 pixThresholdTo2bpp(PIX *pixs,
718 l_int32 nlevels,
719 l_int32 cmapflag)
720 {
721 l_int32 *qtab;
722 l_int32 w, h, d, wplt, wpld;
723 l_uint32 *datat, *datad;
724 PIX *pixt, *pixd;
725 PIXCMAP *cmap;
726
727 PROCNAME("pixThresholdTo2bpp");
728
729 if (!pixs)
730 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
731 pixGetDimensions(pixs, &w, &h, &d);
732 if (d != 8)
733 return (PIX *)ERROR_PTR("pixs not 8 bpp", procName, NULL);
734 if (nlevels < 2 || nlevels > 4)
735 return (PIX *)ERROR_PTR("nlevels not in {2, 3, 4}", procName, NULL);
736
737 /* Make the appropriate table */
738 if (cmapflag)
739 qtab = makeGrayQuantIndexTable(nlevels);
740 else
741 qtab = makeGrayQuantTargetTable(4, 2);
742
743 if ((pixd = pixCreate(w, h, 2)) == NULL)
744 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
745 pixCopyResolution(pixd, pixs);
746 datad = pixGetData(pixd);
747 wpld = pixGetWpl(pixd);
748
749 if (cmapflag) { /* hold out (4 - nlevels) cmap entries */
750 cmap = pixcmapCreateLinear(2, nlevels);
751 pixSetColormap(pixd, cmap);
752 }
753
754 /* If there is a colormap in the src, remove it */
755 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
756 datat = pixGetData(pixt);
757 wplt = pixGetWpl(pixt);
758
759 thresholdTo2bppLow(datad, h, wpld, datat, wplt, qtab);
760
761 if (qtab) FREE(qtab);
762 pixDestroy(&pixt);
763 return pixd;
764 }
765
766
767 /*----------------------------------------------------------------------*
768 * Simple (pixelwise) thresholding to 4 bpp *
769 *----------------------------------------------------------------------*/
770 /*!
771 * pixThresholdTo4bpp()
772 *
773 * Input: pixs (8 bpp, can have colormap)
774 * nlevels (equally spaced; must be between 2 and 16)
775 * cmapflag (1 to build colormap; 0 otherwise)
776 * Return: pixd (4 bpp, optionally with colormap), or null on error
777 *
778 * Notes:
779 * (1) Valid values for nlevels is the set {2, ... 16}.
780 * (2) Any colormap on the input pixs is removed to 8 bpp grayscale.
781 * (3) This function is typically invoked with cmapflag == 1.
782 * In the situation where no colormap is desired, nlevels is
783 * ignored and pixs is thresholded to 16 levels.
784 * (4) The target output colors are equally spaced, with the
785 * darkest at 0 and the lightest at 255. The thresholds are
786 * chosen halfway between adjacent output values. A table
787 * is built that specifies the mapping from src to dest.
788 * (5) If cmapflag == 1, a colormap of size 'nlevels' is made,
789 * and the pixel values in pixs are replaced by their
790 * appropriate color indices. The number of holdouts,
791 * 16 - nlevels, will be between 0 and 14.
792 * (6) If you don't want the thresholding to be equally spaced,
793 * either first transform the 8 bpp src using pixGammaTRC().
794 * or, if cmapflag == 1, after calling this function you can use
795 * pixcmapResetColor() to change any individual colors.
796 * (7) If a colormap is generated, it will specify, to display
797 * programs, exactly how each level is to be represented in RGB
798 * space. When representing text, 3 levels is far better than
799 * 2 because of the antialiasing of the single gray level,
800 * and 4 levels (black, white and 2 gray levels) is getting
801 * close to the perceptual quality of a (nearly continuous)
802 * grayscale image. Therefore, with 4 bpp, you can set up a
803 * colormap, allocate a relatively small fraction of the 16
804 * possible values to represent antialiased text, and use the
805 * other colormap entries for other things, such as coloring
806 * text or background. Two other reasons for using a small number
807 * of gray values for antialiased text are (1) PNG compression
808 * gets worse as the number of levels that are used is increased,
809 * and (2) using a small number of levels will filter out most of
810 * the jpeg ringing that is typically introduced near sharp edges
811 * of text. This filtering is partly responsible for the improved
812 * compression.
813 */
814 PIX *
pixThresholdTo4bpp(PIX * pixs,l_int32 nlevels,l_int32 cmapflag)815 pixThresholdTo4bpp(PIX *pixs,
816 l_int32 nlevels,
817 l_int32 cmapflag)
818 {
819 l_int32 *qtab;
820 l_int32 w, h, d, wplt, wpld;
821 l_uint32 *datat, *datad;
822 PIX *pixt, *pixd;
823 PIXCMAP *cmap;
824
825 PROCNAME("pixThresholdTo4bpp");
826
827 if (!pixs)
828 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
829 pixGetDimensions(pixs, &w, &h, &d);
830 if (d != 8)
831 return (PIX *)ERROR_PTR("pixs not 8 bpp", procName, NULL);
832 if (nlevels < 2 || nlevels > 16)
833 return (PIX *)ERROR_PTR("nlevels not in [2,...,16]", procName, NULL);
834
835 /* Make the appropriate table */
836 if (cmapflag)
837 qtab = makeGrayQuantIndexTable(nlevels);
838 else
839 qtab = makeGrayQuantTargetTable(16, 4);
840
841 if ((pixd = pixCreate(w, h, 4)) == NULL)
842 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
843 pixCopyResolution(pixd, pixs);
844 datad = pixGetData(pixd);
845 wpld = pixGetWpl(pixd);
846
847 if (cmapflag) { /* hold out (16 - nlevels) cmap entries */
848 cmap = pixcmapCreateLinear(4, nlevels);
849 pixSetColormap(pixd, cmap);
850 }
851
852 /* If there is a colormap in the src, remove it */
853 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
854 datat = pixGetData(pixt);
855 wplt = pixGetWpl(pixt);
856
857 thresholdTo4bppLow(datad, h, wpld, datat, wplt, qtab);
858
859 if (qtab) FREE(qtab);
860 pixDestroy(&pixt);
861 return pixd;
862 }
863
864
865 /*----------------------------------------------------------------------*
866 * Simple (pixelwise) thresholding on 8 bpp with optional colormap *
867 *----------------------------------------------------------------------*/
868 /*!
869 * pixThresholdOn8bpp()
870 *
871 * Input: pixs (8 bpp, can have colormap)
872 * nlevels (equally spaced; must be between 2 and 256)
873 * cmapflag (1 to build colormap; 0 otherwise)
874 * Return: pixd (8 bpp, optionally with colormap), or null on error
875 *
876 * Notes:
877 * (1) Valid values for nlevels is the set {2,...,256}.
878 * (2) Any colormap on the input pixs is removed to 8 bpp grayscale.
879 * (3) If cmapflag == 1, a colormap of size 'nlevels' is made,
880 * and the pixel values in pixs are replaced by their
881 * appropriate color indices. Otherwise, the pixel values
882 * are the actual thresholded (i.e., quantized) grayscale values.
883 * (4) If you don't want the thresholding to be equally spaced,
884 * first transform the input 8 bpp src using pixGammaTRC().
885 */
886 PIX *
pixThresholdOn8bpp(PIX * pixs,l_int32 nlevels,l_int32 cmapflag)887 pixThresholdOn8bpp(PIX *pixs,
888 l_int32 nlevels,
889 l_int32 cmapflag)
890 {
891 l_int32 *qtab; /* quantization table */
892 l_int32 i, j, w, h, wpld, val, newval;
893 l_uint32 *datad, *lined;
894 PIX *pixd;
895 PIXCMAP *cmap;
896
897 PROCNAME("pixThresholdOn8bpp");
898
899 if (!pixs)
900 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
901 if (pixGetDepth(pixs) != 8)
902 return (PIX *)ERROR_PTR("pixs not 8 bpp", procName, NULL);
903 if (nlevels < 2 || nlevels > 256)
904 return (PIX *)ERROR_PTR("nlevels not in [2,...,256]", procName, NULL);
905
906 if (cmapflag)
907 qtab = makeGrayQuantIndexTable(nlevels);
908 else
909 qtab = makeGrayQuantTargetTable(nlevels, 8);
910
911 /* Get a new pixd; if there is a colormap in the src, remove it */
912 if (pixGetColormap(pixs))
913 pixd = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
914 else
915 pixd = pixCopy(NULL, pixs);
916
917 if (cmapflag) { /* hold out (256 - nlevels) cmap entries */
918 cmap = pixcmapCreateLinear(8, nlevels);
919 pixSetColormap(pixd, cmap);
920 }
921
922 pixGetDimensions(pixd, &w, &h, NULL);
923 datad = pixGetData(pixd);
924 wpld = pixGetWpl(pixd);
925 for (i = 0; i < h; i++) {
926 lined = datad + i * wpld;
927 for (j = 0; j < w; j++) {
928 val = GET_DATA_BYTE(lined, j);
929 newval = qtab[val];
930 SET_DATA_BYTE(lined, j, newval);
931 }
932 }
933
934 if (qtab) FREE(qtab);
935 return pixd;
936 }
937
938
939 /*----------------------------------------------------------------------*
940 * Arbitrary (pixelwise) thresholding from 8 bpp to 2, 4 or 8 bpp *
941 *----------------------------------------------------------------------*/
942 /*!
943 * pixThresholdGrayArb()
944 *
945 * Input: pixs (8 bpp grayscale; can have colormap)
946 * edgevals (string giving edge value of each bin)
947 * outdepth (0, 2, 4 or 8 bpp; 0 is default for min depth)
948 * use_average (1 if use the average pixel value in colormap)
949 * setblack (1 if darkest color is set to black)
950 * setwhite (1 if lightest color is set to white)
951 * Return: pixd (2, 4 or 8 bpp quantized image with colormap),
952 * or null on error
953 *
954 * Notes:
955 * (1) This function allows exact specification of the quantization bins.
956 * The string @edgevals is a space-separated set of values
957 * specifying the dividing points between output quantization bins.
958 * These threshold values are assigned to the bin with higher
959 * values, so that each of them is the smallest value in their bin.
960 * (2) The output image (pixd) depth is specified by @outdepth. The
961 * number of bins is the number of edgevals + 1. The
962 * relation between outdepth and the number of bins is:
963 * outdepth = 2 nbins <= 4
964 * outdepth = 4 nbins <= 16
965 * outdepth = 8 nbins <= 256
966 * With @outdepth == 0, the minimum required depth for the
967 * given number of bins is used.
968 * The output pixd has a colormap.
969 * (3) The last 3 args determine the specific values that go into
970 * the colormap.
971 * (4) For @use_average:
972 * - if TRUE, the average value of pixels falling in the bin is
973 * chosen as the representative gray value. Otherwise,
974 * - if FALSE, the central value of each bin is chosen as
975 * the representative value.
976 * The colormap holds the representative value.
977 * (5) For @setblack, if TRUE the darkest color is set to (0,0,0).
978 * (6) For @setwhite, if TRUE the lightest color is set to (255,255,255).
979 * (7) An alternative to using this function to quantize to
980 * unequally-spaced bins is to first transform the 8 bpp pixs
981 * using pixGammaTRC(), and follow this with pixThresholdTo4bpp().
982 */
983 PIX *
pixThresholdGrayArb(PIX * pixs,const char * edgevals,l_int32 outdepth,l_int32 use_average,l_int32 setblack,l_int32 setwhite)984 pixThresholdGrayArb(PIX *pixs,
985 const char *edgevals,
986 l_int32 outdepth,
987 l_int32 use_average,
988 l_int32 setblack,
989 l_int32 setwhite)
990 {
991 l_int32 *qtab;
992 l_int32 w, h, d, i, j, n, wplt, wpld, val, newval;
993 l_uint32 *datat, *datad, *linet, *lined;
994 NUMA *na;
995 PIX *pixt, *pixd;
996 PIXCMAP *cmap;
997
998 PROCNAME("pixThresholdGrayArb");
999
1000 if (!pixs)
1001 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
1002 pixGetDimensions(pixs, &w, &h, &d);
1003 if (d != 8)
1004 return (PIX *)ERROR_PTR("pixs not 8 bpp", procName, NULL);
1005 if (!edgevals)
1006 return (PIX *)ERROR_PTR("edgevals not defined", procName, NULL);
1007 if (outdepth != 0 && outdepth != 2 && outdepth != 4 && outdepth != 8)
1008 return (PIX *)ERROR_PTR("invalid outdepth", procName, NULL);
1009
1010 /* Parse and sort (if required) the bin edge values */
1011 na = parseStringForNumbers(edgevals, " \t\n,");
1012 n = numaGetCount(na);
1013 if (n > 255)
1014 return (PIX *)ERROR_PTR("more than 256 levels", procName, NULL);
1015 if (outdepth == 0) {
1016 if (n <= 3)
1017 outdepth = 2;
1018 else if (n <= 15)
1019 outdepth = 4;
1020 else
1021 outdepth = 8;
1022 }
1023 else if (n + 1 > (1 << outdepth)) {
1024 L_WARNING("outdepth too small; setting to 8 bpp", procName);
1025 outdepth = 8;
1026 }
1027 numaSort(na, na, L_SORT_INCREASING);
1028
1029 /* Make the quantization LUT and the colormap */
1030 makeGrayQuantTableArb(na, outdepth, &qtab, &cmap);
1031 if (use_average) { /* use the average value in each bin */
1032 pixcmapDestroy(&cmap);
1033 makeGrayQuantColormapArb(pixs, qtab, outdepth, &cmap);
1034 }
1035 pixcmapSetBlackAndWhite(cmap, setblack, setwhite);
1036 numaDestroy(&na);
1037
1038 if ((pixd = pixCreate(w, h, outdepth)) == NULL)
1039 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
1040 pixCopyResolution(pixd, pixs);
1041 pixSetColormap(pixd, cmap);
1042 datad = pixGetData(pixd);
1043 wpld = pixGetWpl(pixd);
1044
1045 /* If there is a colormap in the src, remove it */
1046 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_TO_GRAYSCALE);
1047 datat = pixGetData(pixt);
1048 wplt = pixGetWpl(pixt);
1049
1050 if (outdepth == 2)
1051 thresholdTo2bppLow(datad, h, wpld, datat, wplt, qtab);
1052 else if (outdepth == 4)
1053 thresholdTo4bppLow(datad, h, wpld, datat, wplt, qtab);
1054 else {
1055 for (i = 0; i < h; i++) {
1056 lined = datad + i * wpld;
1057 linet = datat + i * wplt;
1058 for (j = 0; j < w; j++) {
1059 val = GET_DATA_BYTE(linet, j);
1060 newval = qtab[val];
1061 SET_DATA_BYTE(lined, j, newval);
1062 }
1063 }
1064 }
1065
1066 FREE(qtab);
1067 pixDestroy(&pixt);
1068 return pixd;
1069 }
1070
1071
1072 /*----------------------------------------------------------------------*
1073 * Quantization tables for linear thresholds of grayscale images *
1074 *----------------------------------------------------------------------*/
1075 /*!
1076 * makeGrayQuantIndexTable()
1077 *
1078 * Input: nlevels (number of output levels)
1079 * Return: table (maps input gray level to colormap index,
1080 * or null on error)
1081 * Notes:
1082 * (1) 'nlevels' is some number between 2 and 256 (typically 8 or less).
1083 * (2) The table is typically used for quantizing 2, 4 and 8 bpp
1084 * grayscale src pix, and generating a colormapped dest pix.
1085 */
1086 l_int32 *
makeGrayQuantIndexTable(l_int32 nlevels)1087 makeGrayQuantIndexTable(l_int32 nlevels)
1088 {
1089 l_int32 *tab;
1090 l_int32 i, j, thresh;
1091
1092 PROCNAME("makeGrayQuantIndexTable");
1093
1094 if ((tab = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL)
1095 return (l_int32 *)ERROR_PTR("calloc fail for tab", procName, NULL);
1096 for (i = 0; i < 256; i++) {
1097 for (j = 0; j < nlevels; j++) {
1098 thresh = 255 * (2 * j + 1) / (2 * nlevels - 2);
1099 if (i <= thresh) {
1100 tab[i] = j;
1101 /* fprintf(stderr, "tab[%d] = %d\n", i, j); */
1102 break;
1103 }
1104 }
1105 }
1106 return tab;
1107 }
1108
1109
1110 /*!
1111 * makeGrayQuantTargetTable()
1112 *
1113 * Input: nlevels (number of output levels)
1114 * depth (of dest pix, in bpp; 2, 4 or 8 bpp)
1115 * Return: table (maps input gray level to thresholded gray level,
1116 * or null on error)
1117 *
1118 * Notes:
1119 * (1) nlevels is some number between 2 and 2^(depth)
1120 * (2) The table is used in two similar ways:
1121 * - for 8 bpp, it quantizes to a given number of target levels
1122 * - for 2 and 4 bpp, it thresholds to appropriate target values
1123 * that will use the full dynamic range of the dest pix.
1124 * (3) For depth = 8, the number of thresholds chosen is
1125 * ('nlevels' - 1), and the 'nlevels' values stored in the
1126 * table are at the two at the extreme ends, (0, 255), plus
1127 * plus ('nlevels' - 2) values chosen at equal intervals between.
1128 * For example, for depth = 8 and 'nlevels' = 3, the two
1129 * threshold values are 3f and bf, and the three target pixel
1130 * values are 0, 7f and ff.
1131 * (4) For depth < 8, we ignore nlevels, and always use the maximum
1132 * number of levels, which is 2^(depth).
1133 * If you want nlevels < the maximum number, you should always
1134 * use a colormap.
1135 */
1136 l_int32 *
makeGrayQuantTargetTable(l_int32 nlevels,l_int32 depth)1137 makeGrayQuantTargetTable(l_int32 nlevels,
1138 l_int32 depth)
1139 {
1140 l_int32 *tab;
1141 l_int32 i, j, thresh, maxval, quantval;
1142
1143 PROCNAME("makeGrayQuantTargetTable");
1144
1145 if ((tab = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL)
1146 return (l_int32 *)ERROR_PTR("calloc fail for tab", procName, NULL);
1147 maxval = (1 << depth) - 1;
1148 if (depth < 8)
1149 nlevels = 1 << depth;
1150 for (i = 0; i < 256; i++) {
1151 for (j = 0; j < nlevels; j++) {
1152 thresh = 255 * (2 * j + 1) / (2 * nlevels - 2);
1153 if (i <= thresh) {
1154 quantval = maxval * j / (nlevels - 1);
1155 tab[i] = quantval;
1156 /* fprintf(stderr, "tab[%d] = %d\n", i, tab[i]); */
1157 break;
1158 }
1159 }
1160 }
1161 return tab;
1162 }
1163
1164
1165 /*----------------------------------------------------------------------*
1166 * Quantization table for arbitrary thresholding of grayscale images *
1167 *----------------------------------------------------------------------*/
1168 /*!
1169 * makeGrayQuantTableArb()
1170 *
1171 * Input: na (numa of bin boundaries)
1172 * outdepth (of colormap: 1, 2, 4 or 8)
1173 * &tab (<return> table mapping input gray level to cmap index)
1174 * &cmap (<return> colormap)
1175 * Return: 0 if OK, 1 on error
1176 *
1177 * Notes:
1178 * (1) The number of bins is the count of @na + 1.
1179 * (2) The bin boundaries in na must be sorted in increasing order.
1180 * (3) The table is an inverse colormap: it maps input gray level
1181 * to colormap index (the bin number).
1182 * (4) The colormap generated here has quantized values at the
1183 * center of each bin. If you want to use the average gray
1184 * value of pixels within the bin, discard the colormap and
1185 * compute it using makeGrayQuantColormapArb().
1186 * (5) Returns an error if there are not enough levels in the
1187 * output colormap for the number of bins. The number
1188 * of bins must not exceed 2^outdepth.
1189 */
1190 l_int32
makeGrayQuantTableArb(NUMA * na,l_int32 outdepth,l_int32 ** ptab,PIXCMAP ** pcmap)1191 makeGrayQuantTableArb(NUMA *na,
1192 l_int32 outdepth,
1193 l_int32 **ptab,
1194 PIXCMAP **pcmap)
1195 {
1196 l_int32 i, j, n, jstart, ave, val;
1197 l_int32 *tab;
1198 PIXCMAP *cmap;
1199
1200 PROCNAME("makeGrayQuantTableArb");
1201
1202 if (!ptab)
1203 return ERROR_INT("&tab not defined", procName, 1);
1204 *ptab = NULL;
1205 if (!pcmap)
1206 return ERROR_INT("&cmap not defined", procName, 1);
1207 *pcmap = NULL;
1208 if (!na)
1209 return ERROR_INT("na not defined", procName, 1);
1210 n = numaGetCount(na);
1211 if (n + 1 > (1 << outdepth))
1212 return ERROR_INT("more bins than cmap levels", procName, 1);
1213
1214 if ((tab = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL)
1215 return ERROR_INT("calloc fail for tab", procName, 1);
1216 if ((cmap = pixcmapCreate(outdepth)) == NULL)
1217 return ERROR_INT("cmap not made", procName, 1);
1218 *ptab = tab;
1219 *pcmap = cmap;
1220
1221 /* First n bins */
1222 jstart = 0;
1223 for (i = 0; i < n; i++) {
1224 numaGetIValue(na, i, &val);
1225 ave = (jstart + val) / 2;
1226 pixcmapAddColor(cmap, ave, ave, ave);
1227 for (j = jstart; j < val; j++)
1228 tab[j] = i;
1229 jstart = val;
1230 }
1231
1232 /* Last bin */
1233 ave = (jstart + 255) / 2;
1234 pixcmapAddColor(cmap, ave, ave, ave);
1235 for (j = jstart; j < 256; j++)
1236 tab[j] = n;
1237
1238 return 0;
1239 }
1240
1241
1242 /*!
1243 * makeGrayQuantColormapArb()
1244 *
1245 * Input: pixs (8 bpp)
1246 * tab (table mapping input gray level to cmap index)
1247 * outdepth (of colormap: 1, 2, 4 or 8)
1248 * &cmap (<return> colormap)
1249 * Return: 0 if OK, 1 on error
1250 *
1251 * Notes:
1252 * (1) The table is a 256-entry inverse colormap: it maps input gray
1253 * level to colormap index (the bin number). It is computed
1254 * using makeGrayQuantTableArb().
1255 * (2) The colormap generated here has quantized values at the
1256 * average gray value of the pixels that are in each bin.
1257 * (3) Returns an error if there are not enough levels in the
1258 * output colormap for the number of bins. The number
1259 * of bins must not exceed 2^outdepth.
1260 */
1261 l_int32
makeGrayQuantColormapArb(PIX * pixs,l_int32 * tab,l_int32 outdepth,PIXCMAP ** pcmap)1262 makeGrayQuantColormapArb(PIX *pixs,
1263 l_int32 *tab,
1264 l_int32 outdepth,
1265 PIXCMAP **pcmap)
1266 {
1267 l_int32 i, j, index, w, h, d, nbins, wpl, factor, val;
1268 l_int32 *bincount, *binave, *binstart;
1269 l_uint32 *line, *data;
1270
1271 PROCNAME("makeGrayQuantColormapArb");
1272
1273 if (!pcmap)
1274 return ERROR_INT("&cmap not defined", procName, 1);
1275 *pcmap = NULL;
1276 if (!pixs)
1277 return ERROR_INT("pixs not defined", procName, 1);
1278 pixGetDimensions(pixs, &w, &h, &d);
1279 if (d != 8)
1280 return ERROR_INT("pixs not 8 bpp", procName, 1);
1281 if (!tab)
1282 return ERROR_INT("tab not defined", procName, 1);
1283 nbins = tab[255] + 1;
1284 if (nbins > (1 << outdepth))
1285 return ERROR_INT("more bins than cmap levels", procName, 1);
1286
1287 /* Find the count and weighted count for each bin */
1288 if ((bincount = (l_int32 *)CALLOC(nbins, sizeof(l_int32))) == NULL)
1289 return ERROR_INT("calloc fail for bincount", procName, 1);
1290 if ((binave = (l_int32 *)CALLOC(nbins, sizeof(l_int32))) == NULL)
1291 return ERROR_INT("calloc fail for binave", procName, 1);
1292 factor = (l_int32)(sqrt((l_float64)(w * h) / 30000.) + 0.5);
1293 factor = L_MAX(1, factor);
1294 data = pixGetData(pixs);
1295 wpl = pixGetWpl(pixs);
1296 for (i = 0; i < h; i += factor) {
1297 line = data + i * wpl;
1298 for (j = 0; j < w; j += factor) {
1299 val = GET_DATA_BYTE(line, j);
1300 bincount[tab[val]]++;
1301 binave[tab[val]] += val;
1302 }
1303 }
1304
1305 /* Find the smallest gray values in each bin */
1306 if ((binstart = (l_int32 *)CALLOC(nbins, sizeof(l_int32))) == NULL)
1307 return ERROR_INT("calloc fail for binstart", procName, 1);
1308 for (i = 1, index = 1; i < 256; i++) {
1309 if (tab[i] < index) continue;
1310 if (tab[i] == index)
1311 binstart[index++] = i;
1312 }
1313
1314 /* Get the averages. If there are no samples in a bin, use
1315 * the center value of the bin. */
1316 *pcmap = pixcmapCreate(outdepth);
1317 for (i = 0; i < nbins; i++) {
1318 if (bincount[i])
1319 val = binave[i] / bincount[i];
1320 else { /* no samples in the bin */
1321 if (i < nbins - 1)
1322 val = (binstart[i] + binstart[i + 1]) / 2;
1323 else /* last bin */
1324 val = (binstart[i] + 255) / 2;
1325 }
1326 pixcmapAddColor(*pcmap, val, val, val);
1327 }
1328
1329 FREE(bincount);
1330 FREE(binave);
1331 FREE(binstart);
1332 return 0;
1333 }
1334
1335
1336 /*--------------------------------------------------------------------*
1337 * Thresholding from 32 bpp rgb to 1 bpp *
1338 *--------------------------------------------------------------------*/
1339 /*!
1340 * pixGenerateMaskByBand32()
1341 *
1342 * Input: pixs (32 bpp)
1343 * refval (reference rgb value)
1344 * delm (max amount below the ref value for any component)
1345 * delp (max amount above the ref value for any component)
1346 * Return: pixd (1 bpp), or null on error
1347 *
1348 * Notes:
1349 * (1) Generates a 1 bpp mask pixd, the same size as pixs, where
1350 * the fg pixels in the mask are those where each component
1351 * is within -delm to +delp of the reference value.
1352 */
1353 PIX *
pixGenerateMaskByBand32(PIX * pixs,l_uint32 refval,l_int32 delm,l_int32 delp)1354 pixGenerateMaskByBand32(PIX *pixs,
1355 l_uint32 refval,
1356 l_int32 delm,
1357 l_int32 delp)
1358 {
1359 l_int32 i, j, w, h, d, wpls, wpld;
1360 l_int32 rref, gref, bref, rval, gval, bval;
1361 l_uint32 pixel;
1362 l_uint32 *datas, *datad, *lines, *lined;
1363 PIX *pixd;
1364
1365 PROCNAME("pixGenerateMaskByBand32");
1366
1367 if (!pixs)
1368 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
1369 pixGetDimensions(pixs, &w, &h, &d);
1370 if (d != 32)
1371 return (PIX *)ERROR_PTR("not 32 bpp", procName, NULL);
1372 if (delm < 0 || delp < 0)
1373 return (PIX *)ERROR_PTR("delm and delp must be >= 0", procName, NULL);
1374
1375 extractRGBValues(refval, &rref, &gref, &bref);
1376 pixd = pixCreate(w, h, 1);
1377 pixCopyResolution(pixd, pixs);
1378 datas = pixGetData(pixs);
1379 wpls = pixGetWpl(pixs);
1380 datad = pixGetData(pixd);
1381 wpld = pixGetWpl(pixd);
1382 for (i = 0; i < h; i++) {
1383 lines = datas + i * wpls;
1384 lined = datad + i * wpld;
1385 for (j = 0; j < w; j++) {
1386 pixel = lines[j];
1387 rval = (pixel >> L_RED_SHIFT) & 0xff;
1388 if (rval < rref - delm || rval > rref + delp)
1389 continue;
1390 gval = (pixel >> L_GREEN_SHIFT) & 0xff;
1391 if (gval < gref - delm || gval > gref + delp)
1392 continue;
1393 bval = (pixel >> L_BLUE_SHIFT) & 0xff;
1394 if (bval < bref - delm || bval > bref + delp)
1395 continue;
1396 SET_DATA_BIT(lined, j);
1397 }
1398 }
1399
1400 return pixd;
1401 }
1402
1403
1404 /*!
1405 * pixGenerateMaskByDiscr32()
1406 *
1407 * Input: pixs (32 bpp)
1408 * refval1 (reference rgb value)
1409 * refval2 (reference rgb value)
1410 * distflag (L_MANHATTAN_DISTANCE, L_EUCLIDEAN_DISTANCE)
1411 * Return: pixd (1 bpp), or null on error
1412 *
1413 * Notes:
1414 * (1) Generates a 1 bpp mask pixd, the same size as pixs, where
1415 * the fg pixels in the mask are those where the pixel in pixs
1416 * is "closer" to refval1 than to refval2.
1417 * (2) "Closer" can be defined in several ways, such as:
1418 * - manhattan distance (L1)
1419 * - euclidean distance (L2)
1420 * - majority vote of the individual components
1421 * Here, we have a choice of L1 or L2.
1422 */
1423 PIX *
pixGenerateMaskByDiscr32(PIX * pixs,l_uint32 refval1,l_uint32 refval2,l_int32 distflag)1424 pixGenerateMaskByDiscr32(PIX *pixs,
1425 l_uint32 refval1,
1426 l_uint32 refval2,
1427 l_int32 distflag)
1428 {
1429 l_int32 i, j, w, h, d, wpls, wpld;
1430 l_int32 rref1, gref1, bref1, rref2, gref2, bref2, rval, gval, bval;
1431 l_uint32 pixel, dist1, dist2;
1432 l_uint32 *datas, *datad, *lines, *lined;
1433 PIX *pixd;
1434
1435 PROCNAME("pixGenerateMaskByDiscr32");
1436
1437 if (!pixs)
1438 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
1439 pixGetDimensions(pixs, &w, &h, &d);
1440 if (d != 32)
1441 return (PIX *)ERROR_PTR("not 32 bpp", procName, NULL);
1442 if (distflag != L_MANHATTAN_DISTANCE && distflag != L_EUCLIDEAN_DISTANCE)
1443 return (PIX *)ERROR_PTR("invalid distflag", procName, NULL);
1444
1445 extractRGBValues(refval1, &rref1, &gref1, &bref1);
1446 extractRGBValues(refval2, &rref2, &gref2, &bref2);
1447 pixd = pixCreate(w, h, 1);
1448 pixCopyResolution(pixd, pixs);
1449 datas = pixGetData(pixs);
1450 wpls = pixGetWpl(pixs);
1451 datad = pixGetData(pixd);
1452 wpld = pixGetWpl(pixd);
1453 for (i = 0; i < h; i++) {
1454 lines = datas + i * wpls;
1455 lined = datad + i * wpld;
1456 for (j = 0; j < w; j++) {
1457 pixel = lines[j];
1458 extractRGBValues(pixel, &rval, &gval, &bval);
1459 if (distflag == L_MANHATTAN_DISTANCE) {
1460 dist1 = L_ABS(rref1 - rval);
1461 dist2 = L_ABS(rref2 - rval);
1462 dist1 += L_ABS(gref1 - gval);
1463 dist2 += L_ABS(gref2 - gval);
1464 dist1 += L_ABS(bref1 - bval);
1465 dist2 += L_ABS(bref2 - bval);
1466 }
1467 else {
1468 dist1 = (rref1 - rval) * (rref1 - rval);
1469 dist2 = (rref2 - rval) * (rref2 - rval);
1470 dist1 += (gref1 - gval) * (gref1 - gval);
1471 dist2 += (gref2 - gval) * (gref2 - gval);
1472 dist1 += (bref1 - bval) * (bref1 - bval);
1473 dist2 += (bref2 - bval) * (bref2 - bval);
1474 }
1475 if (dist1 < dist2)
1476 SET_DATA_BIT(lined, j);
1477 }
1478 }
1479
1480 return pixd;
1481 }
1482
1483
1484 /*----------------------------------------------------------------------*
1485 * Histogram-based grayscale quantization *
1486 *----------------------------------------------------------------------*/
1487 /*!
1488 * pixGrayQuantFromHisto()
1489 *
1490 * Input: pixd (<optional> quantized pix with cmap; can be null)
1491 * pixs (8 bpp gray input pix; not cmapped)
1492 * pixm (<optional> mask over pixels in pixs to quantize)
1493 * minfract (minimum fraction of pixels in a set of adjacent
1494 * histo bins that causes the set to be automatically
1495 * set aside as a color in the colormap; must be
1496 * at least 0.01)
1497 * maxsize (maximum number of adjacent bins allowed to represent
1498 * a color, regardless of the population of pixels
1499 * in the bins; must be at least 2)
1500 * Return: pixd (8 bpp, cmapped), or null on error
1501 *
1502 * Notes:
1503 * (1) This is useful for quantizing images with relatively few
1504 * colors, but which may have both color and gray pixels.
1505 * If there are color pixels, it is assumed that an input
1506 * rgb image has been color quantized first so that:
1507 * - pixd has a colormap describing the color pixels
1508 * - pixm is a mask over the non-color pixels in pixd
1509 * - the colormap in pixd, and the color pixels in pixd,
1510 * have been repacked to go from 0 to n-1 (n colors)
1511 * If there are no color pixels, pixd and pixm are both null,
1512 * and all pixels in pixs are quantized to gray.
1513 * (2) A 256-entry histogram is built of the gray values in pixs.
1514 * If pixm exists, the pixels contributing to the histogram are
1515 * restricted to the fg of pixm. A colormap and LUT are generated
1516 * from this histogram. We break up the array into a set
1517 * of intervals, each one constituting a color in the colormap:
1518 * An interval is identified by summing histogram bins until
1519 * either the sum equals or exceeds the @minfract of the total
1520 * number of pixels, or the span itself equals or exceeds @maxsize.
1521 * The color of each bin is always an average of the pixels
1522 * that constitute it.
1523 * (3) Note that we do not specify the number of gray colors in
1524 * the colormap. Instead, we specify two parameters that
1525 * describe the accuracy of the color assignments; this and
1526 * the actual image determine the number of resulting colors.
1527 * (4) If a mask exists and it is not the same size as pixs, make
1528 * a new mask the same size as pixs, with the original mask
1529 * aligned at the UL corners. Set all additional pixels
1530 * in the (larger) new mask set to 1, causing those pixels
1531 * in pixd to be set as gray.
1532 * (5) We estimate the total number of colors (color plus gray);
1533 * if it exceeds 255, return null.
1534 */
1535 PIX *
pixGrayQuantFromHisto(PIX * pixd,PIX * pixs,PIX * pixm,l_float32 minfract,l_int32 maxsize)1536 pixGrayQuantFromHisto(PIX *pixd,
1537 PIX *pixs,
1538 PIX *pixm,
1539 l_float32 minfract,
1540 l_int32 maxsize)
1541 {
1542 l_int32 w, h, wd, hd, wm, hm, wpls, wplm, wpld;
1543 l_int32 nc, nestim, i, j, vals, vald;
1544 l_int32 *lut;
1545 l_uint32 *datas, *datam, *datad, *lines, *linem, *lined;
1546 NUMA *na;
1547 PIX *pixmr; /* resized mask */
1548 PIXCMAP *cmap;
1549
1550 PROCNAME("pixGrayQuantFromHisto");
1551
1552 if (!pixs || pixGetDepth(pixs) != 8)
1553 return (PIX *)ERROR_PTR("pixs undefined or not 8 bpp", procName, NULL);
1554 if (minfract < 0.01) {
1555 L_WARNING("minfract < 0.01; setting to 0.05", procName);
1556 minfract = 0.05;
1557 }
1558 if (maxsize < 2) {
1559 L_WARNING("maxsize < 2; setting to 10", procName);
1560 maxsize = 10;
1561 }
1562 if ((pixd && !pixm) || (!pixd && pixm))
1563 return (PIX *)ERROR_PTR("(pixd,pixm) not defined together",
1564 procName, NULL);
1565 pixGetDimensions(pixs, &w, &h, NULL);
1566 if (pixd) {
1567 if (pixGetDepth(pixm) != 1)
1568 return (PIX *)ERROR_PTR("pixm not 1 bpp", procName, NULL);
1569 if ((cmap = pixGetColormap(pixd)) == NULL)
1570 return (PIX *)ERROR_PTR("pixd not cmapped", procName, NULL);
1571 pixGetDimensions(pixd, &wd, &hd, NULL);
1572 if (w != wd || h != hd)
1573 return (PIX *)ERROR_PTR("pixs, pixd sizes differ", procName, NULL);
1574 nc = pixcmapGetCount(cmap);
1575 nestim = nc + (l_int32)(1.5 * 255 / maxsize);
1576 fprintf(stderr, "nestim = %d\n", nestim);
1577 if (nestim > 255) {
1578 L_ERROR_INT("Estimate %d colors!", procName, nestim);
1579 return (PIX *)ERROR_PTR("probably too many colors", procName, NULL);
1580 }
1581 pixGetDimensions(pixm, &wm, &hm, NULL);
1582 if (w != wm || h != hm) { /* resize the mask */
1583 L_WARNING("mask and dest sizes not equal", procName);
1584 pixmr = pixCreateNoInit(w, h, 1);
1585 pixRasterop(pixmr, 0, 0, wm, hm, PIX_SRC, pixm, 0, 0);
1586 pixRasterop(pixmr, wm, 0, w - wm, h, PIX_SET, NULL, 0, 0);
1587 pixRasterop(pixmr, 0, hm, wm, h - hm, PIX_SET, NULL, 0, 0);
1588 }
1589 else
1590 pixmr = pixClone(pixm);
1591 }
1592 else {
1593 pixd = pixCreateTemplate(pixs);
1594 cmap = pixcmapCreate(8);
1595 pixSetColormap(pixd, cmap);
1596 }
1597
1598 /* Use original mask, if it exists, to select gray pixels */
1599 na = pixGetGrayHistogramMasked(pixs, pixm, 0, 0, 1);
1600
1601 /* Fill out the cmap with gray colors, and generate the lut
1602 * for pixel assignment. Issue a warning on failure. */
1603 if (numaFillCmapFromHisto(na, cmap, minfract, maxsize, &lut))
1604 L_ERROR("ran out of colors in cmap!", procName);
1605 numaDestroy(&na);
1606
1607 /* Assign the gray pixels to their cmap indices */
1608 datas = pixGetData(pixs);
1609 datad = pixGetData(pixd);
1610 wpls = pixGetWpl(pixs);
1611 wpld = pixGetWpl(pixd);
1612 if (!pixm) {
1613 for (i = 0; i < h; i++) {
1614 lines = datas + i * wpls;
1615 lined = datad + i * wpld;
1616 for (j = 0; j < w; j++) {
1617 vals = GET_DATA_BYTE(lines, j);
1618 vald = lut[vals];
1619 SET_DATA_BYTE(lined, j, vald);
1620 }
1621 }
1622 FREE(lut);
1623 return pixd;
1624 }
1625
1626 datam = pixGetData(pixmr);
1627 wplm = pixGetWpl(pixmr);
1628 for (i = 0; i < h; i++) {
1629 lines = datas + i * wpls;
1630 linem = datam + i * wplm;
1631 lined = datad + i * wpld;
1632 for (j = 0; j < w; j++) {
1633 if (!GET_DATA_BIT(linem, j))
1634 continue;
1635 vals = GET_DATA_BYTE(lines, j);
1636 vald = lut[vals];
1637 SET_DATA_BYTE(lined, j, vald);
1638 }
1639 }
1640 pixDestroy(&pixmr);
1641 FREE(lut);
1642 return pixd;
1643 }
1644
1645
1646 /*!
1647 * numaFillCmapFromHisto()
1648 *
1649 * Input: na (histogram of gray values)
1650 * cmap (8 bpp cmap, possibly initialized with color value)
1651 * minfract (minimum fraction of pixels in a set of adjacent
1652 * histo bins that causes the set to be automatically
1653 * set aside as a color in the colormap; must be
1654 * at least 0.01)
1655 * maxsize (maximum number of adjacent bins allowed to represent
1656 * a color, regardless of the population of pixels
1657 * in the bins; must be at least 2)
1658 * &lut (<return> lookup table from gray value to colormap index)
1659 * Return: 0 if OK, 1 on error
1660 *
1661 * Notes:
1662 * (1) This static function must be called from pixGrayQuantFromHisto()
1663 */
1664 static l_int32
numaFillCmapFromHisto(NUMA * na,PIXCMAP * cmap,l_float32 minfract,l_int32 maxsize,l_int32 ** plut)1665 numaFillCmapFromHisto(NUMA *na,
1666 PIXCMAP *cmap,
1667 l_float32 minfract,
1668 l_int32 maxsize,
1669 l_int32 **plut)
1670 {
1671 l_int32 mincount, index, sum, wtsum, span, istart, i, val, ret;
1672 l_int32 *iahisto, *lut;
1673 l_float32 total;
1674
1675 PROCNAME("numaFillCmapFromHisto");
1676
1677 if (!plut)
1678 return ERROR_INT("&lut not defined", procName, 1);
1679 *plut = NULL;
1680 if (!na)
1681 return ERROR_INT("na not defined", procName, 1);
1682 if (!cmap)
1683 return ERROR_INT("cmap not defined", procName, 1);
1684
1685 numaGetSum(na, &total);
1686 mincount = (l_int32)(minfract * total);
1687 iahisto = numaGetIArray(na);
1688 if ((lut = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL)
1689 return ERROR_INT("lut not made", procName, 1);
1690 *plut = lut;
1691 index = pixcmapGetCount(cmap); /* start with number of colors
1692 * already reserved */
1693
1694 /* March through, associating colors with sets of adjacent
1695 * gray levels. During the process, the LUT that gives
1696 * the colormap index for each gray level is computed.
1697 * To complete a color, either the total count must equal
1698 * or exceed @mincount, or the current span of colors must
1699 * equal or exceed @maxsize. An empty span is not converted
1700 * into a color; it is simply ignored. When a span is completed for a
1701 * color, the weighted color in the span is added to the colormap. */
1702 sum = 0;
1703 wtsum = 0;
1704 istart = 0;
1705 ret = 0;
1706 for (i = 0; i < 256; i++) {
1707 lut[i] = index;
1708 sum += iahisto[i];
1709 wtsum += i * iahisto[i];
1710 span = i - istart + 1;
1711 if (sum < mincount && span < maxsize)
1712 continue;
1713
1714 if (sum == 0) { /* empty span; don't save */
1715 istart = i + 1;
1716 continue;
1717 }
1718
1719 /* Found new color; sum > 0 */
1720 val = (l_int32)((l_float32)wtsum / (l_float32)sum + 0.5);
1721 ret = pixcmapAddColor(cmap, val, val, val);
1722 istart = i + 1;
1723 sum = 0;
1724 wtsum = 0;
1725 index++;
1726 }
1727 if (istart < 256 && sum > 0) { /* last one */
1728 span = 256 - istart;
1729 val = (l_int32)((l_float32)wtsum / (l_float32)sum + 0.5);
1730 ret = pixcmapAddColor(cmap, val, val, val);
1731 }
1732
1733 FREE(iahisto);
1734 return ret;
1735 }
1736
1737
1738 /*----------------------------------------------------------------------*
1739 * Color quantize grayscale image using existing colormap *
1740 *----------------------------------------------------------------------*/
1741 /*!
1742 * pixGrayQuantFromCmap()
1743 *
1744 * Input: pixs (8 bpp grayscale without cmap)
1745 * cmap (to quantize to; of dest pix)
1746 * mindepth (minimum depth of pixd: can be 2, 4 or 8 bpp)
1747 * Return: pixd (2, 4 or 8 bpp, colormapped), or null on error
1748 *
1749 * Notes:
1750 * (1) In use, pixs is an 8 bpp grayscale image without a colormap.
1751 * If there is an existing colormap, a warning is issued and
1752 * a copy of the input pixs is returned.
1753 */
1754 PIX *
pixGrayQuantFromCmap(PIX * pixs,PIXCMAP * cmap,l_int32 mindepth)1755 pixGrayQuantFromCmap(PIX *pixs,
1756 PIXCMAP *cmap,
1757 l_int32 mindepth)
1758 {
1759 l_int32 i, j, index, w, h, d, depth, wpls, wpld;
1760 l_int32 hascolor, vals, vald;
1761 l_int32 *tab;
1762 l_uint32 *datas, *datad, *lines, *lined;
1763 PIXCMAP *cmapd;
1764 PIX *pixd;
1765
1766 PROCNAME("pixGrayQuantFromCmap");
1767
1768 if (!pixs)
1769 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
1770 if (pixGetColormap(pixs) != NULL) {
1771 L_WARNING("pixs already has a colormap; returning a copy", procName);
1772 return pixCopy(NULL, pixs);
1773 }
1774 pixGetDimensions(pixs, &w, &h, &d);
1775 if (d != 8)
1776 return (PIX *)ERROR_PTR("pixs not 8 bpp", procName, NULL);
1777 if (!cmap)
1778 return (PIX *)ERROR_PTR("cmap not defined", procName, NULL);
1779 if (mindepth != 2 && mindepth != 4 && mindepth != 8)
1780 return (PIX *)ERROR_PTR("invalid mindepth", procName, NULL);
1781
1782 /* Make sure the colormap is gray */
1783 pixcmapHasColor(cmap, &hascolor);
1784 if (hascolor) {
1785 L_WARNING("Converting colormap colors to gray", procName);
1786 cmapd = pixcmapColorToGray(cmap, 0.3, 0.5, 0.2);
1787 }
1788 else
1789 cmapd = pixcmapCopy(cmap);
1790
1791 /* Make LUT into colormap */
1792 if ((tab = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL)
1793 return (PIX *)ERROR_PTR("tab not made", procName, NULL);
1794 for (i = 0; i < 256; i++) {
1795 pixcmapGetNearestGrayIndex(cmapd, i, &index);
1796 tab[i] = index;
1797 }
1798
1799 pixcmapGetMinDepth(cmap, &depth);
1800 depth = L_MAX(depth, mindepth);
1801 pixd = pixCreate(w, h, depth);
1802 pixSetColormap(pixd, cmapd);
1803 pixCopyResolution(pixd, pixs);
1804 pixCopyInputFormat(pixd, pixs);
1805 datas = pixGetData(pixs);
1806 datad = pixGetData(pixd);
1807 wpls = pixGetWpl(pixs);
1808 wpld = pixGetWpl(pixd);
1809 for (i = 0; i < h; i++) {
1810 lines = datas + i * wpls;
1811 lined = datad + i * wpld;
1812 for (j = 0; j < w; j++) {
1813 vals = GET_DATA_BYTE(lines, j);
1814 vald = tab[vals];
1815 if (depth == 2)
1816 SET_DATA_DIBIT(lined, j, vald);
1817 else if (depth == 4)
1818 SET_DATA_QBIT(lined, j, vald);
1819 else /* depth == 8 */
1820 SET_DATA_BYTE(lined, j, vald);
1821 }
1822 }
1823
1824 FREE(tab);
1825 return pixd;
1826 }
1827
1828
1829