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 * colorcontent.c
18 *
19 * Builds an image of the color content, on a per-pixel basis,
20 * as a measure of the amount of divergence of each color
21 * component (R,G,B) from gray.
22 * l_int32 pixColorContent()
23 *
24 * Finds the 'amount' of color in an image, on a per-pixel basis,
25 * as a measure of the difference of the pixel color from gray.
26 * PIX *pixColorMagnitude()
27 *
28 * Finds the fraction of pixels with "color" that are not close to black
29 * l_int32 pixColorFraction()
30 *
31 * Finds the number of perceptually significant gray intensities
32 * in a grayscale image.
33 * l_int32 pixNumSignificantGrayColors()
34 *
35 * Identifies images where color quantization will cause posterization
36 * due to the existence of many colors in low-gradient regions.
37 * l_int32 pixColorsForQuantization()
38 *
39 * Finds the number of unique colors in an image
40 * l_int32 pixNumColors()
41 *
42 * Color is tricky. If we consider gray (r = g = b) to have no color
43 * content, how should we define the color content in each component
44 * of an arbitrary pixel, as well as the overall color magnitude?
45 *
46 * I can think of three ways to define the color content in each component:
47 *
48 * (1) Linear. For each component, take the difference from the average
49 * of all three.
50 * (2) Linear. For each component, take the difference from the average
51 * of the other two.
52 * (3) Nonlinear. For each component, take the minimum of the differences
53 * from the other two.
54 *
55 * How might one choose from among these? Consider two different situations:
56 * (a) r = g = 0, b = 255 {255} /255/
57 * (b) r = 0, g = 127, b = 255 {191} /128/
58 * How much g is in each of these? The three methods above give:
59 * (a) 1: 85 2: 127 3: 0 [85]
60 * (b) 1: 0 2: 0 3: 127 [0]
61 * How much b is in each of these?
62 * (a) 1: 170 2: 255 3: 255 [255]
63 * (b) 1: 127 2: 191 3: 127 [191]
64 * The number I'd "like" to give is in []. (Please don't ask why, it's
65 * just a feeling.
66 *
67 * So my preferences seem to be somewhere between (1) and (2).
68 * (3) is just too "decisive!" Let's pick (2).
69 *
70 * We also allow compensation for white imbalance. For each
71 * component, we do a linear TRC (gamma = 1.0), where the black
72 * point remains at 0 and the white point is given by the input
73 * parameter. This is equivalent to doing a global remapping,
74 * as with pixGlobalNormRGB(), followed by color content (or magnitude)
75 * computation, but without the overhead of first creating the
76 * white point normalized image.
77 *
78 * Another useful property is the overall color magnitude in the pixel.
79 * For this there are again several choices, such as:
80 * (a) rms deviation from the mean
81 * (b) the average L1 deviation from the mean
82 * (c) the maximum (over components) of one of the color
83 * content measures given above.
84 *
85 * For now, we will choose two of the methods in (c):
86 * L_MAX_DIFF_FROM_AVERAGE_2
87 * Define the color magnitude as the maximum over components
88 * of the difference between the component value and the
89 * average of the other two. It is easy to show that
90 * this is equivalent to selecting the two component values
91 * that are closest to each other, averaging them, and
92 * using the distance from that average to the third component.
93 * For (a) and (b) above, this value is in {..}.
94 * L_MAX_MIN_DIFF_FROM_2
95 * Define the color magnitude as the maximum over components
96 * of the minimum difference between the component value and the
97 * other two values. It is easy to show that this is equivalent
98 * to selecting the intermediate value of the three differences
99 * between the three components. For (a) and (b) above,
100 * this value is in /../.
101 */
102
103 #include <stdio.h>
104 #include <stdlib.h>
105 #include "allheaders.h"
106
107
108 /*!
109 * pixColorContent()
110 *
111 * Input: pixs (32 bpp rgb or 8 bpp colormapped)
112 * rwhite, gwhite, bwhite (color value associated with white point)
113 * mingray (min gray value for which color is measured)
114 * &pixr (<optional return> 8 bpp red 'content')
115 * &pixg (<optional return> 8 bpp green 'content')
116 * &pixb (<optional return> 8 bpp blue 'content')
117 * Return: 0 if OK, 1 on error
118 *
119 * Notes:
120 * (1) This returns the color content in each component, which is
121 * a measure of the deviation from gray, and is defined
122 * as the difference between the component and the average of
123 * the other two components. See the discussion at the
124 * top of this file.
125 * (2) The three numbers (rwhite, gwhite and bwhite) can be thought
126 * of as the values in the image corresponding to white.
127 * They are used to compensate for an unbalanced color white point.
128 * They must either be all 0 or all non-zero. To turn this
129 * off, set them all to 0.
130 * (3) If the maximum component after white point correction,
131 * max(r,g,b), is less than mingray, all color components
132 * for that pixel are set to zero.
133 * Use mingray = 0 to turn off this filtering of dark pixels.
134 * (4) Therefore, use 0 for all four input parameters if the color
135 * magnitude is to be calculated without either white balance
136 * correction or dark filtering.
137 */
138 l_int32
pixColorContent(PIX * pixs,l_int32 rwhite,l_int32 gwhite,l_int32 bwhite,l_int32 mingray,PIX ** ppixr,PIX ** ppixg,PIX ** ppixb)139 pixColorContent(PIX *pixs,
140 l_int32 rwhite,
141 l_int32 gwhite,
142 l_int32 bwhite,
143 l_int32 mingray,
144 PIX **ppixr,
145 PIX **ppixg,
146 PIX **ppixb)
147 {
148 l_int32 w, h, d, i, j, wplc, wplr, wplg, wplb;
149 l_int32 rval, gval, bval, rgdiff, rbdiff, gbdiff, maxval, colorval;
150 l_int32 *rtab, *gtab, *btab;
151 l_uint32 pixel;
152 l_uint32 *datac, *datar, *datag, *datab, *linec, *liner, *lineg, *lineb;
153 NUMA *nar, *nag, *nab;
154 PIX *pixc; /* rgb */
155 PIX *pixr, *pixg, *pixb; /* 8 bpp grayscale */
156 PIXCMAP *cmap;
157
158 PROCNAME("pixColorContent");
159
160 if (!pixs)
161 return ERROR_INT("pixs not defined", procName, 1);
162 if (!ppixr && !ppixg && !ppixb)
163 return ERROR_INT("nothing to compute", procName, 1);
164 if (mingray < 0) mingray = 0;
165 pixGetDimensions(pixs, &w, &h, &d);
166 if (mingray > 255)
167 return ERROR_INT("mingray > 255", procName, 1);
168 if (rwhite < 0 || gwhite < 0 || bwhite < 0)
169 return ERROR_INT("some white vals are negative", procName, 1);
170 if ((rwhite || gwhite || bwhite) && (rwhite * gwhite * bwhite == 0))
171 return ERROR_INT("white vals not all zero or all nonzero", procName, 1);
172
173 cmap = pixGetColormap(pixs);
174 if (!cmap && d != 32)
175 return ERROR_INT("pixs neither cmapped nor 32 bpp", procName, 1);
176 if (cmap)
177 pixc = pixRemoveColormap(pixs, REMOVE_CMAP_TO_FULL_COLOR);
178 else
179 pixc = pixClone(pixs);
180
181 pixr = pixg = pixb = NULL;
182 w = pixGetWidth(pixc);
183 h = pixGetHeight(pixc);
184 if (ppixr) {
185 pixr = pixCreate(w, h, 8);
186 datar = pixGetData(pixr);
187 wplr = pixGetWpl(pixr);
188 *ppixr = pixr;
189 }
190 if (ppixg) {
191 pixg = pixCreate(w, h, 8);
192 datag = pixGetData(pixg);
193 wplg = pixGetWpl(pixg);
194 *ppixg = pixg;
195 }
196 if (ppixb) {
197 pixb = pixCreate(w, h, 8);
198 datab = pixGetData(pixb);
199 wplb = pixGetWpl(pixb);
200 *ppixb = pixb;
201 }
202
203 datac = pixGetData(pixc);
204 wplc = pixGetWpl(pixc);
205 if (rwhite) { /* all white pt vals are nonzero */
206 nar = numaGammaTRC(1.0, 0, rwhite);
207 rtab = numaGetIArray(nar);
208 nag = numaGammaTRC(1.0, 0, gwhite);
209 gtab = numaGetIArray(nag);
210 nab = numaGammaTRC(1.0, 0, bwhite);
211 btab = numaGetIArray(nab);
212 }
213 for (i = 0; i < h; i++) {
214 linec = datac + i * wplc;
215 if (pixr)
216 liner = datar + i * wplr;
217 if (pixg)
218 lineg = datag + i * wplg;
219 if (pixb)
220 lineb = datab + i * wplb;
221 for (j = 0; j < w; j++) {
222 pixel = linec[j];
223 extractRGBValues(pixel, &rval, &gval, &bval);
224 if (rwhite) { /* color correct for white point */
225 rval = rtab[rval];
226 gval = gtab[gval];
227 bval = btab[bval];
228 }
229 if (mingray > 0) { /* dark pixels have no color value */
230 maxval = L_MAX(rval, gval);
231 maxval = L_MAX(maxval, bval);
232 if (maxval < mingray)
233 continue; /* colorval = 0 for each component */
234 }
235 rgdiff = L_ABS(rval - gval);
236 rbdiff = L_ABS(rval - bval);
237 gbdiff = L_ABS(gval - bval);
238 if (pixr) {
239 colorval = (rgdiff + rbdiff) / 2;
240 SET_DATA_BYTE(liner, j, colorval);
241 }
242 if (pixg) {
243 colorval = (rgdiff + gbdiff) / 2;
244 SET_DATA_BYTE(lineg, j, colorval);
245 }
246 if (pixb) {
247 colorval = (rbdiff + gbdiff) / 2;
248 SET_DATA_BYTE(lineb, j, colorval);
249 }
250 }
251 }
252
253 if (rwhite) {
254 numaDestroy(&nar);
255 numaDestroy(&nag);
256 numaDestroy(&nab);
257 FREE(rtab);
258 FREE(gtab);
259 FREE(btab);
260 }
261 pixDestroy(&pixc);
262 return 0;
263 }
264
265
266 /*!
267 * pixColorMagnitude()
268 *
269 * Input: pixs (32 bpp rgb or 8 bpp colormapped)
270 * rwhite, gwhite, bwhite (color value associated with white point)
271 * type (chooses the method for calculating the color magnitude:
272 * L_MAX_DIFF_FROM_AVERAGE_2, MAX_MIN_DIFF_FROM_2)
273 * Return: pixd (8 bpp, amount of color in each source pixel),
274 * or NULL on error
275 *
276 * Notes:
277 * (1) For an RGB image, a gray pixel is one where all three components
278 * are equal. We define the amount of color in an RGB pixel by
279 * considering the absolute value of the differences between the
280 * components, of which there are three. Consider the two largest
281 * of these differences. The pixel component in common to these
282 * two differences is the color farthest from the other two.
283 * The color magnitude in an RGB pixel can be taken as:
284 * * the average of these two differences; i.e., the
285 * average distance from the two components that are
286 * nearest to each other to the third component, or
287 * * the minimum value of these two differences; i.e., the
288 * maximum over all components of the minimum distance
289 * from that component to the other two components.
290 * (2) As an example, suppose that R and G are the closest in
291 * magnitude. Then the color is determined as either:
292 * * the average distance of B from these two; namely,
293 * (|B - R| + |B - G|) / 2, which can also be found
294 * from |B - (R + G) / 2|, or
295 * * the minimum distance of B from these two; namely,
296 * min(|B - R|, |B - G|).
297 * (3) The three numbers (rwhite, gwhite and bwhite) can be thought
298 * of as the values in the image corresponding to white.
299 * They are used to compensate for an unbalanced color white point.
300 * They must either be all 0 or all non-zero. To turn this
301 * off, set them all to 0.
302 * (4) We allow the following methods for choosing the color
303 * magnitude from the three components:
304 * * L_MAX_DIFF_FROM_AVERAGE_2
305 * * L_MAX_MIN_DIFF_FROM_2
306 * These are described above in (1) and (2), as well as at
307 * the top of this file.
308 */
309 PIX *
pixColorMagnitude(PIX * pixs,l_int32 rwhite,l_int32 gwhite,l_int32 bwhite,l_int32 type)310 pixColorMagnitude(PIX *pixs,
311 l_int32 rwhite,
312 l_int32 gwhite,
313 l_int32 bwhite,
314 l_int32 type)
315 {
316 l_int32 w, h, d, i, j, wplc, wpld;
317 l_int32 rval, gval, bval, rdist, gdist, bdist, colorval;
318 l_int32 rgdist, rbdist, gbdist, mindist, maxdist;
319 l_int32 *rtab, *gtab, *btab;
320 l_uint32 pixel;
321 l_uint32 *datac, *datad, *linec, *lined;
322 NUMA *nar, *nag, *nab;
323 PIX *pixc, *pixd;
324 PIXCMAP *cmap;
325
326 PROCNAME("pixColorMagnitude");
327
328 if (!pixs)
329 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
330 pixGetDimensions(pixs, &w, &h, &d);
331 if (type != L_MAX_DIFF_FROM_AVERAGE_2 && type != L_MAX_MIN_DIFF_FROM_2)
332 return (PIX *)ERROR_PTR("invalid type", procName, NULL);
333 if (rwhite < 0 || gwhite < 0 || bwhite < 0)
334 return (PIX *)ERROR_PTR("some white vals are negative", procName, NULL);
335 if ((rwhite || gwhite || bwhite) && (rwhite * gwhite * bwhite == 0))
336 return (PIX *)ERROR_PTR("white vals not all zero or all nonzero",
337 procName, NULL);
338
339 cmap = pixGetColormap(pixs);
340 if (!cmap && d != 32)
341 return (PIX *)ERROR_PTR("pixs not cmapped or 32 bpp", procName, NULL);
342 if (cmap)
343 pixc = pixRemoveColormap(pixs, REMOVE_CMAP_TO_FULL_COLOR);
344 else
345 pixc = pixClone(pixs);
346
347 pixd = pixCreate(w, h, 8);
348 datad = pixGetData(pixd);
349 wpld = pixGetWpl(pixd);
350 datac = pixGetData(pixc);
351 wplc = pixGetWpl(pixc);
352 if (rwhite) { /* all white pt vals are nonzero */
353 nar = numaGammaTRC(1.0, 0, rwhite);
354 rtab = numaGetIArray(nar);
355 nag = numaGammaTRC(1.0, 0, gwhite);
356 gtab = numaGetIArray(nag);
357 nab = numaGammaTRC(1.0, 0, bwhite);
358 btab = numaGetIArray(nab);
359 }
360 for (i = 0; i < h; i++) {
361 linec = datac + i * wplc;
362 lined = datad + i * wpld;
363 for (j = 0; j < w; j++) {
364 pixel = linec[j];
365 extractRGBValues(pixel, &rval, &gval, &bval);
366 if (rwhite) { /* color correct for white point */
367 rval = rtab[rval];
368 gval = gtab[gval];
369 bval = btab[bval];
370 }
371 if (type == L_MAX_DIFF_FROM_AVERAGE_2) {
372 rdist = ((gval + bval ) / 2 - rval);
373 rdist = L_ABS(rdist);
374 gdist = ((rval + bval ) / 2 - gval);
375 gdist = L_ABS(gdist);
376 bdist = ((rval + gval ) / 2 - bval);
377 bdist = L_ABS(bdist);
378 colorval = L_MAX(rdist, gdist);
379 colorval = L_MAX(colorval, bdist);
380 }
381 else { /* type == L_MAX_MIN_DIFF_FROM_2; choose intermed dist */
382 rgdist = L_ABS(rval - gval);
383 rbdist = L_ABS(rval - bval);
384 gbdist = L_ABS(gval - bval);
385 maxdist = L_MAX(rgdist, rbdist);
386 if (gbdist >= maxdist)
387 colorval = maxdist;
388 else { /* gbdist is smallest or intermediate */
389 mindist = L_MIN(rgdist, rbdist);
390 colorval = L_MAX(mindist, gbdist);
391 }
392 }
393 SET_DATA_BYTE(lined, j, colorval);
394 }
395 }
396
397 if (rwhite) {
398 numaDestroy(&nar);
399 numaDestroy(&nag);
400 numaDestroy(&nab);
401 FREE(rtab);
402 FREE(gtab);
403 FREE(btab);
404 }
405 pixDestroy(&pixc);
406 return pixd;
407 }
408
409
410 /*!
411 * pixColorFraction()
412 *
413 * Input: pixs (32 bpp rgb)
414 * darkthresh (dark threshold for minimum of average value to
415 * be considered in the statistics; typ. 20)
416 * lightthresh (threshold near white, above which the pixel
417 * is not considered in the statistics; typ. 248)
418 * diffthresh (thresh for the maximum difference from
419 * the average of component values)
420 * factor (subsampling factor)
421 * &pixfract (<return> fraction of pixels in intermediate
422 * brightness range that were considered
423 * for color content)
424 * &colorfract (<return> fraction of pixels that meet the
425 * criterion for sufficient color; 0.0 on error)
426 * Return: 0 if OK, 1 on error
427 *
428 * Notes:
429 * (1) This function is asking the question: to what extent does the
430 * image appear to have color? The amount of color a pixel
431 * appears to have depends on both the deviation of the
432 * individual components from their average and on the average
433 * intensity itself. For example, the color will be much more
434 * obvious with a small deviation from white than the same
435 * deviation from black.
436 * (2) Any pixel that meets these three tests is considered a
437 * colorful pixel:
438 * (a) the average of components must equal or exceed @darkthresh
439 * (b) the average of components must not exceed @lightthresh
440 * (c) at least one component must differ from the average
441 * by at least @diffthresh
442 * (3) The dark pixels are removed from consideration because
443 * they don't appear to have color.
444 * (4) The very lightest pixels are removed because if an image
445 * has a lot of "white", the color fraction will be artificially
446 * low, even if all the other pixels are colorful.
447 * (5) If pixfract is very small, there are few pixels that are neither
448 * black nor white. If colorfract is very small, the pixels
449 * that are neither black nor white have very little color
450 * content. The product 'pixfract * colorfract' gives the
451 * fraction of pixels with significant color content.
452 * (6) One use of this function is as a preprocessing step for median
453 * cut quantization (colorquant2.c), which does a very poor job
454 * splitting the color space into rectangular volume elements when
455 * all the pixels are near the diagonal of the color cube. For
456 * octree quantization of an image with only gray values, the
457 * 2^(level) octcubes on the diagonal are the only ones
458 * that can be occupied.
459 */
460 l_int32
pixColorFraction(PIX * pixs,l_int32 darkthresh,l_int32 lightthresh,l_int32 diffthresh,l_int32 factor,l_float32 * ppixfract,l_float32 * pcolorfract)461 pixColorFraction(PIX *pixs,
462 l_int32 darkthresh,
463 l_int32 lightthresh,
464 l_int32 diffthresh,
465 l_int32 factor,
466 l_float32 *ppixfract,
467 l_float32 *pcolorfract)
468 {
469 l_int32 i, j, w, h, wpl, rval, gval, bval, ave;
470 l_int32 total, npix, ncolor, rdiff, gdiff, bdiff, maxdiff;
471 l_uint32 pixel;
472 l_uint32 *data, *line;
473
474 PROCNAME("pixColorFraction");
475
476 if (!ppixfract || !pcolorfract)
477 return ERROR_INT("&pixfract and &colorfract not both defined",
478 procName, 1);
479 *ppixfract = 0.0;
480 *pcolorfract = 0.0;
481 if (!pixs || pixGetDepth(pixs) != 32)
482 return ERROR_INT("pixs not defined or not 32 bpp", procName, 1);
483
484 pixGetDimensions(pixs, &w, &h, NULL);
485 data = pixGetData(pixs);
486 wpl = pixGetWpl(pixs);
487 npix = ncolor = total = 0;
488 for (i = 0; i < h; i += factor) {
489 line = data + i * wpl;
490 for (j = 0; j < w; j += factor) {
491 total++;
492 pixel = line[j];
493 extractRGBValues(pixel, &rval, &gval, &bval);
494 ave = (l_int32)(0.333 * (rval + gval + bval));
495 if (ave < darkthresh || ave > lightthresh)
496 continue;
497 npix++;
498 rdiff = L_ABS(rval - ave);
499 gdiff = L_ABS(gval - ave);
500 bdiff = L_ABS(bval - ave);
501 maxdiff = L_MAX(rdiff, gdiff);
502 maxdiff = L_MAX(maxdiff, bdiff);
503 if (maxdiff >= diffthresh)
504 ncolor++;
505 }
506 }
507
508 if (npix == 0) {
509 L_WARNING("No pixels found for consideration", procName);
510 return 0;
511 }
512 *ppixfract = (l_float32)npix / (l_float32)total;
513 *pcolorfract = (l_float32)ncolor / (l_float32)npix;
514 return 0;
515 }
516
517
518 /*!
519 * pixNumSignificantGrayColors()
520 *
521 * Input: pixs (8 bpp gray)
522 * darkthresh (dark threshold for minimum intensity to be
523 * considered; typ. 20)
524 * lightthresh (threshold near white, for maximum intensity
525 * to be considered; typ. 236)
526 * minfract (minimum fraction of all pixels to include a level
527 * as significant; typ. 0.0001)
528 * factor (subsample factor; integer >= 1)
529 * &ncolors (<return> number of significant colors; 0 on error)
530 * Return: 0 if OK, 1 on error
531 *
532 * Notes:
533 * (1) This function is asking the question: how many perceptually
534 * significant gray color levels is in this pix?
535 * A color level must meet 3 criteria to be significant:
536 * - it can't be too close to black
537 * - it can't be too close to white
538 * - it must have at least some minimum fractional population
539 * (2) Use -1 for default values for darkthresh, lightthresh and minfract.
540 * (3) Choose default of darkthresh = 20, because variations in very
541 * dark pixels are not visually significant.
542 * (4) Choose default of lightthresh = 236, because document images
543 * that have been jpeg'd typically have near-white pixels in the
544 * 8x8 jpeg blocks, and these should not be counted. It is desirable
545 * to obtain a clean image by quantizing this noise away.
546 */
547 l_int32
pixNumSignificantGrayColors(PIX * pixs,l_int32 darkthresh,l_int32 lightthresh,l_float32 minfract,l_int32 factor,l_int32 * pncolors)548 pixNumSignificantGrayColors(PIX *pixs,
549 l_int32 darkthresh,
550 l_int32 lightthresh,
551 l_float32 minfract,
552 l_int32 factor,
553 l_int32 *pncolors)
554 {
555 l_int32 i, w, h, count, mincount, ncolors;
556 NUMA *na;
557
558 PROCNAME("pixNumSignificantGrayColors");
559
560 if (!pncolors)
561 return ERROR_INT("&ncolors not defined", procName, 1);
562 *pncolors = 0;
563 if (!pixs || pixGetDepth(pixs) != 8)
564 return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
565 if (darkthresh < 0) darkthresh = 20; /* defaults */
566 if (lightthresh < 0) lightthresh = 236;
567 if (minfract < 0.0) minfract = 0.0001;
568 if (minfract > 1.0)
569 return ERROR_INT("minfract > 1.0", procName, 1);
570 if (lightthresh > 255 || darkthresh >= lightthresh)
571 return ERROR_INT("invalid thresholds", procName, 1);
572 if (factor < 1) factor = 1;
573
574 pixGetDimensions(pixs, &w, &h, NULL);
575 mincount = (l_int32)(minfract * w * h);
576 if ((na = pixGetGrayHistogram(pixs, factor)) == NULL)
577 return ERROR_INT("na not made", procName, 1);
578 ncolors = 2; /* add in black and white */
579 for (i = darkthresh; i <= lightthresh; i++) {
580 numaGetIValue(na, i, &count);
581 if (count >= mincount)
582 ncolors++;
583 }
584
585 *pncolors = ncolors;
586 numaDestroy(&na);
587 return 0;
588 }
589
590
591 /*!
592 * pixColorsForQuantization()
593 * Input: pixs (8 bpp gray or 32 bpp rgb; with or without colormap)
594 * thresh (binary threshold on edge gradient; 0 for default)
595 * &ncolors (<return> the number of colors found)
596 * &iscolor (<optional return> 1 if significant color is found;
597 * 0 otherwise. If pixs is 8 bpp, this is 0)
598 * debug (1 to output masked image that is tested for colors;
599 * 0 otherwise)
600 * Return: 0 if OK, 1 on error.
601 *
602 * Notes:
603 * (1) Grayscale and color quantization is often useful to achieve highly
604 * compressed images with little visible distortion. However,
605 * gray or color washes (regions of low gradient) can defeat
606 * this approach to high compression. How can one determine
607 * if an image is expected to compress well using gray or
608 * color quantization? We use the fact that
609 * - gray washes, when quantized with less than 50 intensities,
610 * have posterization (visible boundaries between regions
611 * of uniform 'color') and poor lossless compression
612 * - color washes, when quantized with level 4 octcubes,
613 * typically result in both posterization and the occupancy
614 * of many level 4 octcubes.
615 * (2) This function finds a measure of the number of colors that are
616 * found in low-gradient regions of an image. By its
617 * magnitude relative to some threshold (not specified in
618 * this function), it gives a good indication of whether
619 * quantization will generate posterization. This number
620 * is larger for images with regions of slowly varying
621 * intensity (if 8 bpp) or color (if rgb). Such images, if
622 * quantized, may require dithering to avoid posterization,
623 * and lossless compression is then expected to be poor.
624 * (3) Images can have colors either intrinsically or as jpeg
625 * compression artifacts. This function effectively ignores
626 * jpeg quantization noise in the white background of grayscale
627 * or color images.
628 * (4) The number of colors in the low-gradient regions increases
629 * monotonically with the threshold @thresh on the edge gradient.
630 * (5) If pixs has a colormap, the number of colors returned is
631 * the number in the colormap.
632 * (6) The image is tested for color. If there is very little color,
633 * it is thresholded to gray and the number of gray levels in
634 * the low gradient regions is found. If the image has color,
635 * the number of occupied level 4 octcubes is found.
636 * (7) When using the default threshold on the gradient (15),
637 * images (both gray and rgb) where ncolors is greater than
638 * about 15 will compress poorly with either lossless
639 * compression or dithered quantization, and they may be
640 * posterized with non-dithered quantization.
641 * (8) For grayscale images, or images without significant color,
642 * this returns the number of significant gray levels in
643 * the low-gradient regions. The actual number of gray levels
644 * can be large due to jpeg compression noise in the background.
645 * (9) Similarly, for color images, the actual number of different
646 * (r,g,b) colors in the low-gradient regions (rather than the
647 * number of occupied level 4 octcubes) can be quite large, e.g.,
648 * due to jpeg compression noise, even for regions that appear
649 * to be of a single color. By quantizing to level 4 octcubes,
650 * most of these superfluous colors are removed from the counting.
651 */
652 l_int32
pixColorsForQuantization(PIX * pixs,l_int32 thresh,l_int32 * pncolors,l_int32 * piscolor,l_int32 debug)653 pixColorsForQuantization(PIX *pixs,
654 l_int32 thresh,
655 l_int32 *pncolors,
656 l_int32 *piscolor,
657 l_int32 debug)
658 {
659 l_int32 w, h, d, minside, factor;
660 l_float32 pixfract, colorfract;
661 PIX *pixt, *pixsc, *pixg, *pixe, *pixb, *pixm;
662 PIXCMAP *cmap;
663
664 PROCNAME("pixColorsForQuantization");
665
666 if (!pncolors)
667 return ERROR_INT("&ncolors not defined", procName, 1);
668 *pncolors = 0;
669 if (!pixs)
670 return ERROR_INT("pixs not defined", procName, 1);
671 if ((cmap = pixGetColormap(pixs)) != NULL) {
672 *pncolors = pixcmapGetCount(cmap);
673 if (piscolor)
674 pixcmapHasColor(cmap, piscolor);
675 return 0;
676 }
677
678 pixGetDimensions(pixs, &w, &h, &d);
679 if (d != 8 && d != 32)
680 return ERROR_INT("pixs not 8 or 32 bpp", procName, 1);
681 if (thresh <= 0)
682 thresh = 15; /* default */
683 if (piscolor)
684 *piscolor = 0;
685
686 /* First test if 32 bpp has any significant color; if not,
687 * convert it to gray. Colors whose average values are within
688 * 20 of black or 8 of white are ignored because they're not
689 * very 'colorful'. If less than 1/10000 of the pixels have
690 * significant color, consider the image to be gray. */
691 minside = L_MIN(w, h);
692 if (d == 8)
693 pixt = pixClone(pixs);
694 else { /* d == 32 */
695 factor = L_MAX(1, minside / 200);
696 pixColorFraction(pixs, 20, 248, 12, factor, &pixfract, &colorfract);
697 if (pixfract * colorfract < 0.0001) {
698 pixt = pixGetRGBComponent(pixs, COLOR_RED);
699 d = 8;
700 }
701 else { /* d == 32 */
702 pixt = pixClone(pixs);
703 if (piscolor)
704 *piscolor = 1;
705 }
706 }
707
708 /* If the smallest side is less than 1000, do not downscale.
709 * If it is in [1000 ... 2000), downscale by 2x. If it is >= 2000,
710 * downscale by 4x. Factors of 2 are chosen for speed. The
711 * actual resolution at which subsequent calculations take place
712 * is not strongly dependent on downscaling. */
713 factor = L_MAX(1, minside / 500);
714 if (factor == 1)
715 pixsc = pixCopy(NULL, pixt); /* to be sure pixs is unchanged */
716 else if (factor == 2 || factor == 3)
717 pixsc = pixScaleAreaMap2(pixt);
718 else
719 pixsc = pixScaleAreaMap(pixt, 0.25, 0.25);
720
721 /* Basic edge mask generation procedure:
722 * - work on a grayscale image
723 * - get a 1 bpp edge mask by using an edge filter and
724 * thresholding to get fg pixels at the edges
725 * - dilate with a 7x7 brick Sel to get mask over all pixels
726 * within a small distance from the nearest edge pixel */
727 if (d == 8)
728 pixg = pixClone(pixsc);
729 else /* d == 32 */
730 pixg = pixConvertRGBToLuminance(pixsc);
731 pixe = pixSobelEdgeFilter(pixg, L_ALL_EDGES);
732 pixb = pixThresholdToBinary(pixe, thresh);
733 pixInvert(pixb, pixb);
734 pixm = pixMorphSequence(pixb, "d7.7", 0);
735
736 /* Mask the near-edge pixels to white, and count the colors.
737 * If grayscale, don't count colors within 20 levels of
738 * black or white, and only count colors with a fraction
739 * of at least 1/10000 of the image pixels.
740 * If color, count the number of level 4 octcubes that
741 * contain at least 20 pixels. These magic numbers are guesses
742 * as to what should work, based on a small data set. Results
743 * should not be sensitive to their actual values. */
744 if (d == 8) {
745 pixSetMasked(pixg, pixm, 0xff);
746 if (debug) pixWrite("junkpix8.png", pixg, IFF_PNG);
747 pixNumSignificantGrayColors(pixg, 20, 236, 0.0001, 1, pncolors);
748 }
749 else { /* d == 32 */
750 pixSetMasked(pixsc, pixm, 0xffffffff);
751 if (debug) pixWrite("junkpix32.png", pixsc, IFF_PNG);
752 pixNumberOccupiedOctcubes(pixsc, 4, 20, -1, pncolors);
753 }
754
755 pixDestroy(&pixt);
756 pixDestroy(&pixsc);
757 pixDestroy(&pixg);
758 pixDestroy(&pixe);
759 pixDestroy(&pixb);
760 pixDestroy(&pixm);
761 return 0;
762 }
763
764
765 /*!
766 * pixNumColors()
767 * Input: pixs (2, 4, 8, 32 bpp)
768 * factor (subsampling factor; integer)
769 * &ncolors (<return> the number of colors found, or 0 if
770 * there are more than 256)
771 * Return: 0 if OK, 1 on error.
772 *
773 * Notes:
774 * (1) This returns the actual number of colors found in the image,
775 * even if there is a colormap. If @factor == 1 and the
776 * number of colors differs from the number of entries
777 * in the colormap, a warning is issued.
778 * (2) Use @factor == 1 to find the actual number of colors.
779 * Use @factor > 1 to quickly find the approximate number of colors.
780 * (3) For d = 2, 4 or 8 bpp grayscale, this returns the number
781 * of colors found in the image in 'ncolors'.
782 * (4) For d = 32 bpp (rgb), if the number of colors is
783 * greater than 256, this returns 0 in 'ncolors'.
784 */
785 l_int32
pixNumColors(PIX * pixs,l_int32 factor,l_int32 * pncolors)786 pixNumColors(PIX *pixs,
787 l_int32 factor,
788 l_int32 *pncolors)
789 {
790 l_int32 w, h, d, i, j, wpl, hashsize, sum, count;
791 l_int32 rval, gval, bval, val;
792 l_int32 *inta;
793 l_uint32 pixel;
794 l_uint32 *data, *line;
795 PIXCMAP *cmap;
796
797 PROCNAME("pixNumColors");
798
799 if (!pncolors)
800 return ERROR_INT("&ncolors not defined", procName, 1);
801 *pncolors = 0;
802 if (!pixs)
803 return ERROR_INT("pixs not defined", procName, 1);
804 pixGetDimensions(pixs, &w, &h, &d);
805 if (d != 2 && d != 4 && d != 8 && d != 32)
806 return ERROR_INT("d not in {2, 4, 8, 32}", procName, 1);
807 if (factor < 1) factor = 1;
808
809 data = pixGetData(pixs);
810 wpl = pixGetWpl(pixs);
811 sum = 0;
812 if (d != 32) { /* grayscale */
813 inta = (l_int32 *)CALLOC(256, sizeof(l_int32));
814 for (i = 0; i < h; i += factor) {
815 line = data + i * wpl;
816 for (j = 0; j < w; j += factor) {
817 if (d == 8)
818 val = GET_DATA_BYTE(line, j);
819 else if (d == 4)
820 val = GET_DATA_QBIT(line, j);
821 else /* d == 2 */
822 val = GET_DATA_DIBIT(line, j);
823 inta[val] = 1;
824 }
825 }
826 for (i = 0; i < 256; i++)
827 if (inta[i]) sum++;
828 *pncolors = sum;
829 FREE(inta);
830
831 if (factor == 1 && ((cmap = pixGetColormap(pixs)) != NULL)) {
832 count = pixcmapGetCount(cmap);
833 if (sum != count)
834 L_WARNING_INT("colormap size %d differs from actual colors",
835 procName, count);
836 }
837 return 0;
838 }
839
840 /* 32 bpp rgb; quit if we get above 256 colors */
841 hashsize = 5507; /* big and prime; collisions are not likely */
842 inta = (l_int32 *)CALLOC(hashsize, sizeof(l_int32));
843 for (i = 0; i < h; i += factor) {
844 line = data + i * wpl;
845 for (j = 0; j < w; j += factor) {
846 pixel = line[j];
847 extractRGBValues(pixel, &rval, &gval, &bval);
848 val = (137 * rval + 269 * gval + 353 * bval) % hashsize;
849 if (inta[val] == 0) {
850 inta[val] = 1;
851 sum++;
852 if (sum > 256) {
853 FREE(inta);
854 return 0;
855 }
856 }
857 }
858 }
859
860 *pncolors = sum;
861 FREE(inta);
862 return 0;
863 }
864
865
866