Leptonica 1.82.0
Image processing and image analysis suite
colorquant2.c
Go to the documentation of this file.
1/*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 -
4 - Redistribution and use in source and binary forms, with or without
5 - modification, are permitted provided that the following conditions
6 - are met:
7 - 1. Redistributions of source code must retain the above copyright
8 - notice, this list of conditions and the following disclaimer.
9 - 2. Redistributions in binary form must reproduce the above
10 - copyright notice, this list of conditions and the following
11 - disclaimer in the documentation and/or other materials
12 - provided with the distribution.
13 -
14 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18 - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *====================================================================*/
26
171#ifdef HAVE_CONFIG_H
172#include <config_auto.h>
173#endif /* HAVE_CONFIG_H */
174
175#include <string.h>
176#include <math.h>
177#include "allheaders.h"
178
179 /* Median cut 3-d volume element. Sort on first element, which
180 * can be the number of pixels, the volume or a combination
181 * of these. */
182struct L_Box3d
183{
184 l_float32 sortparam; /* parameter on which to sort the vbox */
185 l_int32 npix; /* number of pixels in the vbox */
186 l_int32 vol; /* quantized volume of vbox */
187 l_int32 r1; /* min r index in the vbox */
188 l_int32 r2; /* max r index in the vbox */
189 l_int32 g1; /* min g index in the vbox */
190 l_int32 g2; /* max g index in the vbox */
191 l_int32 b1; /* min b index in the vbox */
192 l_int32 b2; /* max b index in the vbox */
193};
194typedef struct L_Box3d L_BOX3D;
195
196 /* Static median cut helper functions */
197static PIXCMAP *pixcmapGenerateFromHisto(PIX *pixs, l_int32 depth,
198 l_int32 *histo, l_int32 histosize,
199 l_int32 sigbits);
200static PIX *pixQuantizeWithColormap(PIX *pixs, l_int32 ditherflag,
201 l_int32 outdepth,
202 PIXCMAP *cmap, l_int32 *indexmap,
203 l_int32 mapsize, l_int32 sigbits);
204static void getColorIndexMedianCut(l_uint32 pixel, l_int32 rshift,
205 l_uint32 mask, l_int32 sigbits,
206 l_int32 *pindex);
207static L_BOX3D *pixGetColorRegion(PIX *pixs, l_int32 sigbits,
208 l_int32 subsample);
209static l_int32 medianCutApply(l_int32 *histo, l_int32 sigbits,
210 L_BOX3D *vbox, L_BOX3D **pvbox1,
211 L_BOX3D **pvbox2);
212static PIXCMAP *pixcmapGenerateFromMedianCuts(L_HEAP *lh, l_int32 *histo,
213 l_int32 sigbits);
214static l_int32 vboxGetAverageColor(L_BOX3D *vbox, l_int32 *histo,
215 l_int32 sigbits, l_int32 index,
216 l_int32 *prval, l_int32 *pgval,
217 l_int32 *pbval);
218static l_int32 vboxGetCount(L_BOX3D *vbox, l_int32 *histo, l_int32 sigbits);
219static l_int32 vboxGetVolume(L_BOX3D *vbox);
220static L_BOX3D *box3dCreate(l_int32 r1, l_int32 r2, l_int32 g1,
221 l_int32 g2, l_int32 b1, l_int32 b2);
222static L_BOX3D *box3dCopy(L_BOX3D *vbox);
223
224
225 /* 5 significant bits for each component is generally satisfactory */
226static const l_int32 DefaultSigBits = 5;
227static const l_int32 MaxItersAllowed = 5000; /* prevents infinite looping */
228
229 /* Specify fraction of vboxes made that are sorted on population alone.
230 * The remaining vboxes are sorted on (population * vbox-volume). */
231static const l_float32 FractByPopulation = 0.85;
232
233 /* To get the max value of 'dif' in the dithering color transfer,
234 * divide DifCap by 8. */
235static const l_int32 DifCap = 100;
236
237
238#ifndef NO_CONSOLE_IO
239#define DEBUG_MC_COLORS 0
240#define DEBUG_SPLIT_AXES 0
241#endif /* ~NO_CONSOLE_IO */
242
243/*------------------------------------------------------------------------*
244 * High level *
245 *------------------------------------------------------------------------*/
259PIX *
260pixMedianCutQuant(PIX *pixs,
261 l_int32 ditherflag)
262{
263 return pixMedianCutQuantGeneral(pixs, ditherflag,
264 0, 256, DefaultSigBits, 1, 1);
265}
266
267
316PIX *
317pixMedianCutQuantGeneral(PIX *pixs,
318 l_int32 ditherflag,
319 l_int32 outdepth,
320 l_int32 maxcolors,
321 l_int32 sigbits,
322 l_int32 maxsub,
323 l_int32 checkbw)
324{
325l_int32 i, subsample, histosize, smalln, ncolors, niters, popcolors;
326l_int32 w, h, minside, factor, index, rval, gval, bval;
327l_int32 *histo;
328l_float32 maxprod, prod, norm, pixfract, colorfract;
329L_BOX3D *vbox, *vbox1, *vbox2;
330L_HEAP *lh, *lhs;
331PIX *pixd;
332PIXCMAP *cmap;
333
334 PROCNAME("pixMedianCutQuantGeneral");
335
336 if (!pixs || pixGetDepth(pixs) != 32)
337 return (PIX *)ERROR_PTR("pixs undefined or not 32 bpp", procName, NULL);
338 if (maxcolors < 2 || maxcolors > 256)
339 return (PIX *)ERROR_PTR("maxcolors not in [2...256]", procName, NULL);
340 if (outdepth != 0 && outdepth != 1 && outdepth != 2 && outdepth != 4 &&
341 outdepth != 8)
342 return (PIX *)ERROR_PTR("outdepth not in {0,1,2,4,8}", procName, NULL);
343 if (outdepth > 0 && (maxcolors > (1 << outdepth)))
344 return (PIX *)ERROR_PTR("maxcolors > 2^(outdepth)", procName, NULL);
345 if (sigbits == 0)
346 sigbits = DefaultSigBits;
347 else if (sigbits < 5 || sigbits > 6)
348 return (PIX *)ERROR_PTR("sigbits not 5 or 6", procName, NULL);
349 if (maxsub <= 0)
350 maxsub = 10; /* default will prevail for 10^7 pixels or less */
351
352 /* Determine if the image has sufficient color content.
353 * If pixfract << 1, most pixels are close to black or white.
354 * If colorfract << 1, the pixels that are not near
355 * black or white have very little color.
356 * If with little color, quantize with a grayscale colormap. */
357 pixGetDimensions(pixs, &w, &h, NULL);
358 if (checkbw) {
359 minside = L_MIN(w, h);
360 factor = L_MAX(1, minside / 400);
361 pixColorFraction(pixs, 20, 244, 20, factor, &pixfract, &colorfract);
362 if (pixfract * colorfract < 0.00025) {
363 L_INFO("\n Pixel fraction neither white nor black = %6.3f"
364 "\n Color fraction of those pixels = %6.3f"
365 "\n Quantizing in gray\n",
366 procName, pixfract, colorfract);
367 return pixConvertTo8(pixs, 1);
368 }
369 }
370
371 /* Compute the color space histogram. Default sampling
372 * is about 10^5 sampled pixels. */
373 if (maxsub == 1) {
374 subsample = 1;
375 } else {
376 subsample = (l_int32)(sqrt((l_float64)(w * h) / 100000.));
377 subsample = L_MAX(1, L_MIN(maxsub, subsample));
378 }
379 histo = pixMedianCutHisto(pixs, sigbits, subsample);
380 histosize = 1 << (3 * sigbits);
381
382 /* See if the number of quantized colors is less than maxcolors */
383 ncolors = 0;
384 smalln = TRUE;
385 for (i = 0; i < histosize; i++) {
386 if (histo[i])
387 ncolors++;
388 if (ncolors > maxcolors) {
389 smalln = FALSE;
390 break;
391 }
392 }
393 if (smalln) { /* finish up now */
394 if (outdepth == 0) {
395 if (ncolors <= 2)
396 outdepth = 1;
397 else if (ncolors <= 4)
398 outdepth = 2;
399 else if (ncolors <= 16)
400 outdepth = 4;
401 else
402 outdepth = 8;
403 }
404 cmap = pixcmapGenerateFromHisto(pixs, outdepth,
405 histo, histosize, sigbits);
406 pixd = pixQuantizeWithColormap(pixs, ditherflag, outdepth, cmap,
407 histo, histosize, sigbits);
408 LEPT_FREE(histo);
409 return pixd;
410 }
411
412 /* Initial vbox: minimum region in colorspace occupied by pixels */
413 if (ditherflag || subsample > 1) /* use full color space */
414 vbox = box3dCreate(0, (1 << sigbits) - 1,
415 0, (1 << sigbits) - 1,
416 0, (1 << sigbits) - 1);
417 else
418 vbox = pixGetColorRegion(pixs, sigbits, subsample);
419 vbox->npix = vboxGetCount(vbox, histo, sigbits);
420 vbox->vol = vboxGetVolume(vbox);
421
422 /* For a fraction 'popcolors' of the desired 'maxcolors',
423 * generate median cuts based on population, putting
424 * everything on a priority queue sorted by population. */
425 lh = lheapCreate(0, L_SORT_DECREASING);
426 lheapAdd(lh, vbox);
427 ncolors = 1;
428 niters = 0;
429 popcolors = (l_int32)(FractByPopulation * maxcolors);
430 while (1) {
431 vbox = (L_BOX3D *)lheapRemove(lh);
432 if (vboxGetCount(vbox, histo, sigbits) == 0) { /* just put it back */
433 lheapAdd(lh, vbox);
434 continue;
435 }
436 medianCutApply(histo, sigbits, vbox, &vbox1, &vbox2);
437 if (!vbox1) {
438 L_WARNING("vbox1 not defined; shouldn't happen!\n", procName);
439 break;
440 }
441 if (vbox1->vol > 1)
442 vbox1->sortparam = vbox1->npix;
443 LEPT_FREE(vbox);
444 lheapAdd(lh, vbox1);
445 if (vbox2) { /* vbox2 can be NULL */
446 if (vbox2->vol > 1)
447 vbox2->sortparam = vbox2->npix;
448 lheapAdd(lh, vbox2);
449 ncolors++;
450 }
451 if (ncolors >= popcolors)
452 break;
453 if (niters++ > MaxItersAllowed) {
454 L_WARNING("infinite loop; perhaps too few pixels!\n", procName);
455 break;
456 }
457 }
458
459 /* Re-sort by the product of pixel occupancy times the size
460 * in color space. Normalize to the largest product to avoid
461 * integer overflow. */
462 maxprod = 0.0;
463 for (i = 0; i < lh->n; i++) {
464 if ((vbox = (L_BOX3D *)lheapGetElement(lh, i)) == NULL)
465 continue;
466 prod = (l_float32)vbox->npix * (l_float32)vbox->vol;
467 if (prod > maxprod) maxprod = prod;
468 }
469 norm = (maxprod == 0) ? 1.0 : 1000000.0 / maxprod;
470 lhs = lheapCreate(0, L_SORT_DECREASING);
471 while ((vbox = (L_BOX3D *)lheapRemove(lh))) {
472 vbox->sortparam = norm * vbox->npix * vbox->vol;
473 lheapAdd(lhs, vbox);
474 }
475 lheapDestroy(&lh, TRUE);
476
477 /* For the remaining (maxcolors - popcolors), generate the
478 * median cuts using the (npix * vol) sorting. */
479 while (1) {
480 vbox = (L_BOX3D *)lheapRemove(lhs);
481 if (vboxGetCount(vbox, histo, sigbits) == 0) { /* just put it back */
482 lheapAdd(lhs, vbox);
483 continue;
484 }
485 medianCutApply(histo, sigbits, vbox, &vbox1, &vbox2);
486 if (!vbox1) {
487 L_WARNING("vbox1 not defined; shouldn't happen!\n", procName);
488 break;
489 }
490 if (vbox1->vol > 1)
491 vbox1->sortparam = norm * vbox1->npix * vbox1->vol;
492 LEPT_FREE(vbox);
493 lheapAdd(lhs, vbox1);
494 if (vbox2) { /* vbox2 can be NULL */
495 if (vbox2->vol > 1)
496 vbox2->sortparam = norm * vbox2->npix * vbox2->vol;
497 lheapAdd(lhs, vbox2);
498 ncolors++;
499 }
500 if (ncolors >= maxcolors)
501 break;
502 if (niters++ > MaxItersAllowed) {
503 L_WARNING("infinite loop; perhaps too few pixels!\n", procName);
504 break;
505 }
506 }
507
508 /* Re-sort by pixel occupancy. This is not necessary,
509 * but it makes a more useful listing. */
510 lh = lheapCreate(0, L_SORT_DECREASING);
511 while ((vbox = (L_BOX3D *)lheapRemove(lhs))) {
512 vbox->sortparam = vbox->npix;
513/* vbox->sortparam = vbox->npix * vbox->vol; */
514 lheapAdd(lh, vbox);
515 }
516 lheapDestroy(&lhs, TRUE);
517
518 /* Generate colormap from median cuts and quantize pixd */
519 cmap = pixcmapGenerateFromMedianCuts(lh, histo, sigbits);
520 if (outdepth == 0) {
521 ncolors = pixcmapGetCount(cmap);
522 if (ncolors <= 2)
523 outdepth = 1;
524 else if (ncolors <= 4)
525 outdepth = 2;
526 else if (ncolors <= 16)
527 outdepth = 4;
528 else
529 outdepth = 8;
530 }
531 pixd = pixQuantizeWithColormap(pixs, ditherflag, outdepth, cmap,
532 histo, histosize, sigbits);
533
534 /* Force darkest color to black if each component <= 4 */
535 pixcmapGetRankIntensity(cmap, 0.0, &index);
536 pixcmapGetColor(cmap, index, &rval, &gval, &bval);
537 if (rval < 5 && gval < 5 && bval < 5)
538 pixcmapResetColor(cmap, index, 0, 0, 0);
539
540 /* Force lightest color to white if each component >= 252 */
541 pixcmapGetRankIntensity(cmap, 1.0, &index);
542 pixcmapGetColor(cmap, index, &rval, &gval, &bval);
543 if (rval > 251 && gval > 251 && bval > 251)
544 pixcmapResetColor(cmap, index, 255, 255, 255);
545
546 lheapDestroy(&lh, TRUE);
547 LEPT_FREE(histo);
548 return pixd;
549}
550
551
596PIX *
597pixMedianCutQuantMixed(PIX *pixs,
598 l_int32 ncolor,
599 l_int32 ngray,
600 l_int32 darkthresh,
601 l_int32 lightthresh,
602 l_int32 diffthresh)
603{
604l_int32 i, j, w, h, wplc, wplg, wpld, nc, unused, iscolor, factor, minside;
605l_int32 rval, gval, bval, minval, maxval, val, grayval;
606l_float32 pixfract, colorfract;
607l_int32 *lut;
608l_uint32 *datac, *datag, *datad, *linec, *lineg, *lined;
609PIX *pixc, *pixg, *pixd;
610PIXCMAP *cmap;
611
612 PROCNAME("pixMedianCutQuantMixed");
613
614 if (!pixs || pixGetDepth(pixs) != 32)
615 return (PIX *)ERROR_PTR("pixs undefined or not 32 bpp", procName, NULL);
616 if (ngray < 2)
617 return (PIX *)ERROR_PTR("ngray < 2", procName, NULL);
618 if (ncolor + ngray > 255)
619 return (PIX *)ERROR_PTR("ncolor + ngray > 255", procName, NULL);
620 if (darkthresh <= 0) darkthresh = 20;
621 if (lightthresh <= 0) lightthresh = 244;
622 if (diffthresh <= 0) diffthresh = 20;
623
624 /* First check if this should be quantized in gray.
625 * Use a more sensitive parameter for detecting color than with
626 * pixMedianCutQuantGeneral(), because this function can handle
627 * gray pixels well. */
628 pixGetDimensions(pixs, &w, &h, NULL);
629 minside = L_MIN(w, h);
630 factor = L_MAX(1, minside / 400);
631 pixColorFraction(pixs, darkthresh, lightthresh, diffthresh, factor,
632 &pixfract, &colorfract);
633 if (pixfract * colorfract < 0.0001) {
634 L_INFO("\n Pixel fraction neither white nor black = %6.3f"
635 "\n Color fraction of those pixels = %6.3f"
636 "\n Quantizing in gray\n",
637 procName, pixfract, colorfract);
638 pixg = pixConvertTo8(pixs, 0);
639 pixd = pixThresholdOn8bpp(pixg, ngray, 1);
640 pixDestroy(&pixg);
641 return pixd;
642 }
643
644 /* OK, there is color in the image.
645 * Preprocess to handle the gray pixels. Set the color pixels in pixc
646 * to black, and store their (eventual) colormap indices in pixg.*/
647 pixc = pixCopy(NULL, pixs);
648 pixg = pixCreate(w, h, 8); /* color pixels will remain 0 here */
649 datac = pixGetData(pixc);
650 datag = pixGetData(pixg);
651 wplc = pixGetWpl(pixc);
652 wplg = pixGetWpl(pixg);
653 lut = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
654 for (i = 0; i < 256; i++)
655 lut[i] = ncolor + 1 + (i * (ngray - 1) + 128) / 255;
656 for (i = 0; i < h; i++) {
657 linec = datac + i * wplc;
658 lineg = datag + i * wplg;
659 for (j = 0; j < w; j++) {
660 iscolor = FALSE;
661 extractRGBValues(linec[j], &rval, &gval, &bval);
662 minval = L_MIN(rval, gval);
663 minval = L_MIN(minval, bval);
664 maxval = L_MAX(rval, gval);
665 maxval = L_MAX(maxval, bval);
666 if (maxval >= darkthresh &&
667 minval <= lightthresh &&
668 maxval - minval >= diffthresh) {
669 iscolor = TRUE;
670 }
671 if (!iscolor) {
672 linec[j] = 0x0; /* set to black */
673 grayval = (maxval + minval) / 2;
674 SET_DATA_BYTE(lineg, j, lut[grayval]);
675 }
676 }
677 }
678
679 /* Median cut on color pixels plus black */
680 pixd = pixMedianCutQuantGeneral(pixc, FALSE, 8, ncolor + 1,
681 DefaultSigBits, 1, 0);
682
683 /* Augment the colormap with gray values. The new cmap
684 * indices should agree with the values previously stored in pixg. */
685 cmap = pixGetColormap(pixd);
686 nc = pixcmapGetCount(cmap);
687 unused = ncolor + 1 - nc;
688 if (unused < 0)
689 L_ERROR("Too many colors: extra = %d\n", procName, -unused);
690 if (unused > 0) { /* fill in with black; these won't be used */
691 L_INFO("%d unused colors\n", procName, unused);
692 for (i = 0; i < unused; i++)
693 pixcmapAddColor(cmap, 0, 0, 0);
694 }
695 for (i = 0; i < ngray; i++) {
696 grayval = (255 * i) / (ngray - 1);
697 pixcmapAddColor(cmap, grayval, grayval, grayval);
698 }
699
700 /* Substitute cmap indices for the gray pixels into pixd */
701 datad = pixGetData(pixd);
702 wpld = pixGetWpl(pixd);
703 for (i = 0; i < h; i++) {
704 lined = datad + i * wpld;
705 lineg = datag + i * wplg;
706 for (j = 0; j < w; j++) {
707 val = GET_DATA_BYTE(lineg, j); /* if 0, it's a color pixel */
708 if (val)
709 SET_DATA_BYTE(lined, j, val);
710 }
711 }
712
713 pixDestroy(&pixc);
714 pixDestroy(&pixg);
715 LEPT_FREE(lut);
716 return pixd;
717}
718
719
770PIX *
771pixFewColorsMedianCutQuantMixed(PIX *pixs,
772 l_int32 ncolor,
773 l_int32 ngray,
774 l_int32 maxncolors,
775 l_int32 darkthresh,
776 l_int32 lightthresh,
777 l_int32 diffthresh)
778{
779l_int32 ncolors, iscolor;
780PIX *pixg, *pixd;
781
782 PROCNAME("pixFewColorsMedianCutQuantMixed");
783
784 if (!pixs || pixGetDepth(pixs) != 32)
785 return (PIX *)ERROR_PTR("pixs undefined or not 32 bpp", procName, NULL);
786 if (maxncolors <= 0) maxncolors = 20;
787 if (darkthresh <= 0) darkthresh = 20;
788 if (lightthresh <= 0) lightthresh = 244;
789 if (diffthresh <= 0) diffthresh = 15;
790 if (ncolor < maxncolors) {
791 L_WARNING("ncolor too small; setting to %d\n", procName, maxncolors);
792 ncolor = maxncolors;
793 }
794 if (ngray < maxncolors) {
795 L_WARNING("ngray too small; setting to %d\n", procName, maxncolors);
796 ngray = maxncolors;
797 }
798
799 /* Estimate the color content and the number of colors required */
800 pixColorsForQuantization(pixs, 15, &ncolors, &iscolor, 0);
801
802 /* Note that maxncolors applies to all colors required to quantize,
803 * both gray and colorful */
804 if (ncolors > maxncolors)
805 return (PIX *)ERROR_PTR("too many colors", procName, NULL);
806
807 /* If no color, return quantized gray pix */
808 if (!iscolor) {
809 pixg = pixConvertTo8(pixs, 0);
810 pixd = pixThresholdOn8bpp(pixg, ngray, 1);
811 pixDestroy(&pixg);
812 return pixd;
813 }
814
815 /* Use the mixed gray/color quantizer */
816 return pixMedianCutQuantMixed(pixs, ncolor, ngray, darkthresh,
817 lightthresh, diffthresh);
818}
819
820
821
822/*------------------------------------------------------------------------*
823 * Median cut indexed histogram *
824 *------------------------------------------------------------------------*/
842l_int32 *
843pixMedianCutHisto(PIX *pixs,
844 l_int32 sigbits,
845 l_int32 subsample)
846{
847l_int32 i, j, w, h, wpl, rshift, index, histosize;
848l_int32 *histo;
849l_uint32 mask, pixel;
850l_uint32 *data, *line;
851
852 PROCNAME("pixMedianCutHisto");
853
854 if (!pixs)
855 return (l_int32 *)ERROR_PTR("pixs not defined", procName, NULL);
856 if (pixGetDepth(pixs) != 32)
857 return (l_int32 *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
858 if (sigbits < 5 || sigbits > 6)
859 return (l_int32 *)ERROR_PTR("sigbits not 5 or 6", procName, NULL);
860 if (subsample <= 0)
861 return (l_int32 *)ERROR_PTR("subsample not > 0", procName, NULL);
862
863 histosize = 1 << (3 * sigbits);
864 if ((histo = (l_int32 *)LEPT_CALLOC(histosize, sizeof(l_int32))) == NULL)
865 return (l_int32 *)ERROR_PTR("histo not made", procName, NULL);
866
867 rshift = 8 - sigbits;
868 mask = 0xff >> rshift;
869 pixGetDimensions(pixs, &w, &h, NULL);
870 data = pixGetData(pixs);
871 wpl = pixGetWpl(pixs);
872 for (i = 0; i < h; i += subsample) {
873 line = data + i * wpl;
874 for (j = 0; j < w; j += subsample) {
875 pixel = line[j];
876 getColorIndexMedianCut(pixel, rshift, mask, sigbits, &index);
877 histo[index]++;
878 }
879 }
880
881 return histo;
882}
883
884
885/*------------------------------------------------------------------------*
886 * Static helpers *
887 *------------------------------------------------------------------------*/
906static PIXCMAP *
907pixcmapGenerateFromHisto(PIX *pixs,
908 l_int32 depth,
909 l_int32 *histo,
910 l_int32 histosize,
911 l_int32 sigbits)
912{
913l_int32 i, index, shift, rval, gval, bval;
914l_uint32 mask;
915PIXCMAP *cmap;
916
917 PROCNAME("pixcmapGenerateFromHisto");
918
919 if (!pixs)
920 return (PIXCMAP *)ERROR_PTR("pixs not defined", procName, NULL);
921 if (pixGetDepth(pixs) != 32)
922 return (PIXCMAP *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
923 if (!histo)
924 return (PIXCMAP *)ERROR_PTR("histo not defined", procName, NULL);
925
926 /* Capture the rgb values of each occupied cube in the histo,
927 * and re-label the histo value with the colormap index. */
928 cmap = pixcmapCreate(depth);
929 shift = 8 - sigbits;
930 mask = 0xff >> shift;
931 for (i = 0, index = 0; i < histosize; i++) {
932 if (histo[i]) {
933 rval = (i >> (2 * sigbits)) << shift;
934 gval = ((i >> sigbits) & mask) << shift;
935 bval = (i & mask) << shift;
936 pixcmapAddColor(cmap, rval, gval, bval);
937 histo[i] = index++;
938 }
939 }
940
941 return cmap;
942}
943
944
965static PIX *
966pixQuantizeWithColormap(PIX *pixs,
967 l_int32 ditherflag,
968 l_int32 outdepth,
969 PIXCMAP *cmap,
970 l_int32 *indexmap,
971 l_int32 mapsize,
972 l_int32 sigbits)
973{
974l_uint8 *bufu8r, *bufu8g, *bufu8b;
975l_int32 i, j, w, h, wpls, wpld, rshift, index, cmapindex, success;
976l_int32 rval, gval, bval, rc, gc, bc;
977l_int32 dif, val1, val2, val3;
978l_int32 *buf1r, *buf1g, *buf1b, *buf2r, *buf2g, *buf2b;
979l_uint32 *datas, *datad, *lines, *lined;
980l_uint32 mask, pixel;
981PIX *pixd;
982
983 PROCNAME("pixQuantizeWithColormap");
984
985 if (!pixs || pixGetDepth(pixs) != 32)
986 return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
987 if (!cmap)
988 return (PIX *)ERROR_PTR("cmap not defined", procName, NULL);
989 if (!indexmap)
990 return (PIX *)ERROR_PTR("indexmap not defined", procName, NULL);
991 if (ditherflag)
992 outdepth = 8;
993
994 pixGetDimensions(pixs, &w, &h, NULL);
995 pixd = pixCreate(w, h, outdepth);
996 pixSetColormap(pixd, cmap);
997 pixCopyResolution(pixd, pixs);
998 pixCopyInputFormat(pixd, pixs);
999 datas = pixGetData(pixs);
1000 datad = pixGetData(pixd);
1001 wpls = pixGetWpl(pixs);
1002 wpld = pixGetWpl(pixd);
1003
1004 rshift = 8 - sigbits;
1005 mask = 0xff >> rshift;
1006 if (ditherflag == 0) {
1007 for (i = 0; i < h; i++) {
1008 lines = datas + i * wpls;
1009 lined = datad + i * wpld;
1010 if (outdepth == 1) {
1011 for (j = 0; j < w; j++) {
1012 pixel = lines[j];
1013 getColorIndexMedianCut(pixel, rshift, mask,
1014 sigbits, &index);
1015 if (indexmap[index])
1016 SET_DATA_BIT(lined, j);
1017 }
1018 } else if (outdepth == 2) {
1019 for (j = 0; j < w; j++) {
1020 pixel = lines[j];
1021 getColorIndexMedianCut(pixel, rshift, mask,
1022 sigbits, &index);
1023 SET_DATA_DIBIT(lined, j, indexmap[index]);
1024 }
1025 } else if (outdepth == 4) {
1026 for (j = 0; j < w; j++) {
1027 pixel = lines[j];
1028 getColorIndexMedianCut(pixel, rshift, mask,
1029 sigbits, &index);
1030 SET_DATA_QBIT(lined, j, indexmap[index]);
1031 }
1032 } else { /* outdepth == 8 */
1033 for (j = 0; j < w; j++) {
1034 pixel = lines[j];
1035 getColorIndexMedianCut(pixel, rshift, mask,
1036 sigbits, &index);
1037 SET_DATA_BYTE(lined, j, indexmap[index]);
1038 }
1039 }
1040 }
1041 } else { /* ditherflag == 1 */
1042 success = TRUE;
1043 bufu8r = bufu8g = bufu8b = NULL;
1044 buf1r = buf1g = buf1b = buf2r = buf2g = buf2b = NULL;
1045 bufu8r = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1046 bufu8g = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1047 bufu8b = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1048 buf1r = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1049 buf1g = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1050 buf1b = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1051 buf2r = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1052 buf2g = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1053 buf2b = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1054 if (!bufu8r || !bufu8g || !bufu8b || !buf1r || !buf1g ||
1055 !buf1b || !buf2r || !buf2g || !buf2b) {
1056 L_ERROR("buffer not made\n", procName);
1057 success = FALSE;
1058 goto buffer_cleanup;
1059 }
1060
1061 /* Start by priming buf2; line 1 is above line 2 */
1062 pixGetRGBLine(pixs, 0, bufu8r, bufu8g, bufu8b);
1063 for (j = 0; j < w; j++) {
1064 buf2r[j] = 64 * bufu8r[j];
1065 buf2g[j] = 64 * bufu8g[j];
1066 buf2b[j] = 64 * bufu8b[j];
1067 }
1068
1069 for (i = 0; i < h - 1; i++) {
1070 /* Swap data 2 --> 1, and read in new line 2 */
1071 memcpy(buf1r, buf2r, 4 * w);
1072 memcpy(buf1g, buf2g, 4 * w);
1073 memcpy(buf1b, buf2b, 4 * w);
1074 pixGetRGBLine(pixs, i + 1, bufu8r, bufu8g, bufu8b);
1075 for (j = 0; j < w; j++) {
1076 buf2r[j] = 64 * bufu8r[j];
1077 buf2g[j] = 64 * bufu8g[j];
1078 buf2b[j] = 64 * bufu8b[j];
1079 }
1080
1081 /* Dither */
1082 lined = datad + i * wpld;
1083 for (j = 0; j < w - 1; j++) {
1084 rval = buf1r[j] / 64;
1085 gval = buf1g[j] / 64;
1086 bval = buf1b[j] / 64;
1087 index = ((rval >> rshift) << (2 * sigbits)) +
1088 ((gval >> rshift) << sigbits) + (bval >> rshift);
1089 cmapindex = indexmap[index];
1090 SET_DATA_BYTE(lined, j, cmapindex);
1091 pixcmapGetColor(cmap, cmapindex, &rc, &gc, &bc);
1092
1093 dif = buf1r[j] / 8 - 8 * rc;
1094 if (dif > DifCap) dif = DifCap;
1095 if (dif < -DifCap) dif = -DifCap;
1096 if (dif != 0) {
1097 val1 = buf1r[j + 1] + 3 * dif;
1098 val2 = buf2r[j] + 3 * dif;
1099 val3 = buf2r[j + 1] + 2 * dif;
1100 if (dif > 0) {
1101 buf1r[j + 1] = L_MIN(16383, val1);
1102 buf2r[j] = L_MIN(16383, val2);
1103 buf2r[j + 1] = L_MIN(16383, val3);
1104 } else {
1105 buf1r[j + 1] = L_MAX(0, val1);
1106 buf2r[j] = L_MAX(0, val2);
1107 buf2r[j + 1] = L_MAX(0, val3);
1108 }
1109 }
1110
1111 dif = buf1g[j] / 8 - 8 * gc;
1112 if (dif > DifCap) dif = DifCap;
1113 if (dif < -DifCap) dif = -DifCap;
1114 if (dif != 0) {
1115 val1 = buf1g[j + 1] + 3 * dif;
1116 val2 = buf2g[j] + 3 * dif;
1117 val3 = buf2g[j + 1] + 2 * dif;
1118 if (dif > 0) {
1119 buf1g[j + 1] = L_MIN(16383, val1);
1120 buf2g[j] = L_MIN(16383, val2);
1121 buf2g[j + 1] = L_MIN(16383, val3);
1122 } else {
1123 buf1g[j + 1] = L_MAX(0, val1);
1124 buf2g[j] = L_MAX(0, val2);
1125 buf2g[j + 1] = L_MAX(0, val3);
1126 }
1127 }
1128
1129 dif = buf1b[j] / 8 - 8 * bc;
1130 if (dif > DifCap) dif = DifCap;
1131 if (dif < -DifCap) dif = -DifCap;
1132 if (dif != 0) {
1133 val1 = buf1b[j + 1] + 3 * dif;
1134 val2 = buf2b[j] + 3 * dif;
1135 val3 = buf2b[j + 1] + 2 * dif;
1136 if (dif > 0) {
1137 buf1b[j + 1] = L_MIN(16383, val1);
1138 buf2b[j] = L_MIN(16383, val2);
1139 buf2b[j + 1] = L_MIN(16383, val3);
1140 } else {
1141 buf1b[j + 1] = L_MAX(0, val1);
1142 buf2b[j] = L_MAX(0, val2);
1143 buf2b[j + 1] = L_MAX(0, val3);
1144 }
1145 }
1146 }
1147
1148 /* Get last pixel in row; no downward propagation */
1149 rval = buf1r[w - 1] / 64;
1150 gval = buf1g[w - 1] / 64;
1151 bval = buf1b[w - 1] / 64;
1152 index = ((rval >> rshift) << (2 * sigbits)) +
1153 ((gval >> rshift) << sigbits) + (bval >> rshift);
1154 SET_DATA_BYTE(lined, w - 1, indexmap[index]);
1155 }
1156
1157 /* Get last row of pixels; no leftward propagation */
1158 lined = datad + (h - 1) * wpld;
1159 for (j = 0; j < w; j++) {
1160 rval = buf2r[j] / 64;
1161 gval = buf2g[j] / 64;
1162 bval = buf2b[j] / 64;
1163 index = ((rval >> rshift) << (2 * sigbits)) +
1164 ((gval >> rshift) << sigbits) + (bval >> rshift);
1165 SET_DATA_BYTE(lined, j, indexmap[index]);
1166 }
1167
1168buffer_cleanup:
1169 LEPT_FREE(bufu8r);
1170 LEPT_FREE(bufu8g);
1171 LEPT_FREE(bufu8b);
1172 LEPT_FREE(buf1r);
1173 LEPT_FREE(buf1g);
1174 LEPT_FREE(buf1b);
1175 LEPT_FREE(buf2r);
1176 LEPT_FREE(buf2g);
1177 LEPT_FREE(buf2b);
1178 if (!success) pixDestroy(&pixd);
1179 }
1180
1181 return pixd;
1182}
1183
1184
1201static void
1202getColorIndexMedianCut(l_uint32 pixel,
1203 l_int32 rshift,
1204 l_uint32 mask,
1205 l_int32 sigbits,
1206 l_int32 *pindex)
1207{
1208l_int32 rval, gval, bval;
1209
1210 rval = pixel >> (24 + rshift);
1211 gval = (pixel >> (16 + rshift)) & mask;
1212 bval = (pixel >> (8 + rshift)) & mask;
1213 *pindex = (rval << (2 * sigbits)) + (gval << sigbits) + bval;
1214 return;
1215}
1216
1217
1233static L_BOX3D *
1234pixGetColorRegion(PIX *pixs,
1235 l_int32 sigbits,
1236 l_int32 subsample)
1237{
1238l_int32 rmin, rmax, gmin, gmax, bmin, bmax, rval, gval, bval;
1239l_int32 w, h, wpl, i, j, rshift;
1240l_uint32 mask, pixel;
1241l_uint32 *data, *line;
1242
1243 PROCNAME("pixGetColorRegion");
1244
1245 if (!pixs)
1246 return (L_BOX3D *)ERROR_PTR("pixs not defined", procName, NULL);
1247
1248 rmin = gmin = bmin = 1000000;
1249 rmax = gmax = bmax = 0;
1250 rshift = 8 - sigbits;
1251 mask = 0xff >> rshift;
1252 pixGetDimensions(pixs, &w, &h, NULL);
1253 data = pixGetData(pixs);
1254 wpl = pixGetWpl(pixs);
1255 for (i = 0; i < h; i += subsample) {
1256 line = data + i * wpl;
1257 for (j = 0; j < w; j += subsample) {
1258 pixel = line[j];
1259 rval = pixel >> (24 + rshift);
1260 gval = (pixel >> (16 + rshift)) & mask;
1261 bval = (pixel >> (8 + rshift)) & mask;
1262 if (rval < rmin)
1263 rmin = rval;
1264 else if (rval > rmax)
1265 rmax = rval;
1266 if (gval < gmin)
1267 gmin = gval;
1268 else if (gval > gmax)
1269 gmax = gval;
1270 if (bval < bmin)
1271 bmin = bval;
1272 else if (bval > bmax)
1273 bmax = bval;
1274 }
1275 }
1276
1277 return box3dCreate(rmin, rmax, gmin, gmax, bmin, bmax);
1278}
1279
1280
1290static l_int32
1291medianCutApply(l_int32 *histo,
1292 l_int32 sigbits,
1293 L_BOX3D *vbox,
1294 L_BOX3D **pvbox1,
1295 L_BOX3D **pvbox2)
1296{
1297l_int32 i, j, k, sum, rw, gw, bw, maxw, index;
1298l_int32 total, left, right;
1299l_int32 partialsum[128];
1300L_BOX3D *vbox1, *vbox2;
1301
1302 PROCNAME("medianCutApply");
1303
1304 if (pvbox1) *pvbox1 = NULL;
1305 if (pvbox2) *pvbox2 = NULL;
1306 if (!histo)
1307 return ERROR_INT("histo not defined", procName, 1);
1308 if (!vbox)
1309 return ERROR_INT("vbox not defined", procName, 1);
1310 if (!pvbox1 || !pvbox2)
1311 return ERROR_INT("&vbox1 and &vbox2 not both defined", procName, 1);
1312
1313 if (vboxGetCount(vbox, histo, sigbits) == 0)
1314 return ERROR_INT("no pixels in vbox", procName, 1);
1315
1316 /* If the vbox occupies just one element in color space, it can't
1317 * be split. Leave the 'sortparam' field at 0, so that it goes to
1318 * the tail of the priority queue and stays there, thereby avoiding
1319 * an infinite loop (take off, put back on the head) if it
1320 * happens to be the most populous box! */
1321 rw = vbox->r2 - vbox->r1 + 1;
1322 gw = vbox->g2 - vbox->g1 + 1;
1323 bw = vbox->b2 - vbox->b1 + 1;
1324 if (rw == 1 && gw == 1 && bw == 1) {
1325 *pvbox1 = box3dCopy(vbox);
1326 return 0;
1327 }
1328
1329 /* Select the longest axis for splitting */
1330 maxw = L_MAX(rw, gw);
1331 maxw = L_MAX(maxw, bw);
1332#if DEBUG_SPLIT_AXES
1333 if (rw == maxw)
1334 lept_stderr("red split\n");
1335 else if (gw == maxw)
1336 lept_stderr("green split\n");
1337 else
1338 lept_stderr("blue split\n");
1339#endif /* DEBUG_SPLIT_AXES */
1340
1341 /* Find the partial sum arrays along the selected axis. */
1342 total = 0;
1343 if (maxw == rw) {
1344 for (i = vbox->r1; i <= vbox->r2; i++) {
1345 sum = 0;
1346 for (j = vbox->g1; j <= vbox->g2; j++) {
1347 for (k = vbox->b1; k <= vbox->b2; k++) {
1348 index = (i << (2 * sigbits)) + (j << sigbits) + k;
1349 sum += histo[index];
1350 }
1351 }
1352 total += sum;
1353 partialsum[i] = total;
1354 }
1355 } else if (maxw == gw) {
1356 for (i = vbox->g1; i <= vbox->g2; i++) {
1357 sum = 0;
1358 for (j = vbox->r1; j <= vbox->r2; j++) {
1359 for (k = vbox->b1; k <= vbox->b2; k++) {
1360 index = (i << sigbits) + (j << (2 * sigbits)) + k;
1361 sum += histo[index];
1362 }
1363 }
1364 total += sum;
1365 partialsum[i] = total;
1366 }
1367 } else { /* maxw == bw */
1368 for (i = vbox->b1; i <= vbox->b2; i++) {
1369 sum = 0;
1370 for (j = vbox->r1; j <= vbox->r2; j++) {
1371 for (k = vbox->g1; k <= vbox->g2; k++) {
1372 index = i + (j << (2 * sigbits)) + (k << sigbits);
1373 sum += histo[index];
1374 }
1375 }
1376 total += sum;
1377 partialsum[i] = total;
1378 }
1379 }
1380
1381 /* Determine the cut planes, making sure that two vboxes
1382 * are always produced. Generate the two vboxes and compute
1383 * the sum in each of them. Choose the cut plane within
1384 * the greater of the (left, right) sides of the bin in which
1385 * the median pixel resides. Here's the surprise: go halfway
1386 * into that side. By doing that, you technically move away
1387 * from "median cut," but in the process a significant number
1388 * of low-count vboxes are produced, allowing much better
1389 * reproduction of low-count spot colors. */
1390 vbox1 = vbox2 = NULL;
1391 if (maxw == rw) {
1392 for (i = vbox->r1; i <= vbox->r2; i++) {
1393 if (partialsum[i] > total / 2) {
1394 vbox1 = box3dCopy(vbox);
1395 vbox2 = box3dCopy(vbox);
1396 left = i - vbox->r1;
1397 right = vbox->r2 - i;
1398 if (left <= right)
1399 vbox1->r2 = L_MIN(vbox->r2 - 1, i + right / 2);
1400 else /* left > right */
1401 vbox1->r2 = L_MAX(vbox->r1, i - 1 - left / 2);
1402 vbox2->r1 = vbox1->r2 + 1;
1403 break;
1404 }
1405 }
1406 } else if (maxw == gw) {
1407 for (i = vbox->g1; i <= vbox->g2; i++) {
1408 if (partialsum[i] > total / 2) {
1409 vbox1 = box3dCopy(vbox);
1410 vbox2 = box3dCopy(vbox);
1411 left = i - vbox->g1;
1412 right = vbox->g2 - i;
1413 if (left <= right)
1414 vbox1->g2 = L_MIN(vbox->g2 - 1, i + right / 2);
1415 else /* left > right */
1416 vbox1->g2 = L_MAX(vbox->g1, i - 1 - left / 2);
1417 vbox2->g1 = vbox1->g2 + 1;
1418 break;
1419 }
1420 }
1421 } else { /* maxw == bw */
1422 for (i = vbox->b1; i <= vbox->b2; i++) {
1423 if (partialsum[i] > total / 2) {
1424 vbox1 = box3dCopy(vbox);
1425 vbox2 = box3dCopy(vbox);
1426 left = i - vbox->b1;
1427 right = vbox->b2 - i;
1428 if (left <= right)
1429 vbox1->b2 = L_MIN(vbox->b2 - 1, i + right / 2);
1430 else /* left > right */
1431 vbox1->b2 = L_MAX(vbox->b1, i - 1 - left / 2);
1432 vbox2->b1 = vbox1->b2 + 1;
1433 break;
1434 }
1435 }
1436 }
1437 *pvbox1 = vbox1;
1438 *pvbox2 = vbox2;
1439 if (!vbox1)
1440 return ERROR_INT("vbox1 not made; shouldn't happen", procName, 1);
1441 if (!vbox2)
1442 return ERROR_INT("vbox2 not made; shouldn't happen", procName, 1);
1443 vbox1->npix = vboxGetCount(vbox1, histo, sigbits);
1444 vbox2->npix = vboxGetCount(vbox2, histo, sigbits);
1445 vbox1->vol = vboxGetVolume(vbox1);
1446 vbox2->vol = vboxGetVolume(vbox2);
1447
1448 return 0;
1449}
1450
1451
1470static PIXCMAP *
1471pixcmapGenerateFromMedianCuts(L_HEAP *lh,
1472 l_int32 *histo,
1473 l_int32 sigbits)
1474{
1475l_int32 index, rval, gval, bval;
1476L_BOX3D *vbox;
1477PIXCMAP *cmap;
1478
1479 PROCNAME("pixcmapGenerateFromMedianCuts");
1480
1481 if (!lh)
1482 return (PIXCMAP *)ERROR_PTR("lh not defined", procName, NULL);
1483 if (!histo)
1484 return (PIXCMAP *)ERROR_PTR("histo not defined", procName, NULL);
1485
1486 rval = gval = bval = 0; /* make compiler happy */
1487 cmap = pixcmapCreate(8);
1488 index = 0;
1489 while (lheapGetCount(lh) > 0) {
1490 vbox = (L_BOX3D *)lheapRemove(lh);
1491 vboxGetAverageColor(vbox, histo, sigbits, index, &rval, &gval, &bval);
1492 pixcmapAddColor(cmap, rval, gval, bval);
1493 LEPT_FREE(vbox);
1494 index++;
1495 }
1496
1497 return cmap;
1498}
1499
1500
1526static l_int32
1527vboxGetAverageColor(L_BOX3D *vbox,
1528 l_int32 *histo,
1529 l_int32 sigbits,
1530 l_int32 index,
1531 l_int32 *prval,
1532 l_int32 *pgval,
1533 l_int32 *pbval)
1534{
1535l_int32 i, j, k, ntot, mult, histoindex, rsum, gsum, bsum;
1536
1537 PROCNAME("vboxGetAverageColor");
1538
1539 if (!vbox)
1540 return ERROR_INT("vbox not defined", procName, 1);
1541 if (!histo)
1542 return ERROR_INT("histo not defined", procName, 1);
1543 if (!prval || !pgval || !pbval)
1544 return ERROR_INT("&p*val not all defined", procName, 1);
1545
1546 *prval = *pgval = *pbval = 0;
1547 ntot = 0;
1548 mult = 1 << (8 - sigbits);
1549 rsum = gsum = bsum = 0;
1550 for (i = vbox->r1; i <= vbox->r2; i++) {
1551 for (j = vbox->g1; j <= vbox->g2; j++) {
1552 for (k = vbox->b1; k <= vbox->b2; k++) {
1553 histoindex = (i << (2 * sigbits)) + (j << sigbits) + k;
1554 ntot += histo[histoindex];
1555 rsum += (l_int32)(histo[histoindex] * (i + 0.5) * mult);
1556 gsum += (l_int32)(histo[histoindex] * (j + 0.5) * mult);
1557 bsum += (l_int32)(histo[histoindex] * (k + 0.5) * mult);
1558 if (index >= 0)
1559 histo[histoindex] = index;
1560 }
1561 }
1562 }
1563
1564 if (ntot == 0) {
1565 *prval = mult * (vbox->r1 + vbox->r2 + 1) / 2;
1566 *pgval = mult * (vbox->g1 + vbox->g2 + 1) / 2;
1567 *pbval = mult * (vbox->b1 + vbox->b2 + 1) / 2;
1568 } else {
1569 *prval = rsum / ntot;
1570 *pgval = gsum / ntot;
1571 *pbval = bsum / ntot;
1572 }
1573
1574#if DEBUG_MC_COLORS
1575 lept_stderr("ntot[%d] = %d: [%d, %d, %d], (%d, %d, %d)\n",
1576 index, ntot, vbox->r2 - vbox->r1 + 1,
1577 vbox->g2 - vbox->g1 + 1, vbox->b2 - vbox->b1 + 1,
1578 *prval, *pgval, *pbval);
1579#endif /* DEBUG_MC_COLORS */
1580
1581 return 0;
1582}
1583
1584
1593static l_int32
1594vboxGetCount(L_BOX3D *vbox,
1595 l_int32 *histo,
1596 l_int32 sigbits)
1597{
1598l_int32 i, j, k, npix, index;
1599
1600 PROCNAME("vboxGetCount");
1601
1602 if (!vbox)
1603 return ERROR_INT("vbox not defined", procName, 0);
1604 if (!histo)
1605 return ERROR_INT("histo not defined", procName, 0);
1606
1607 npix = 0;
1608 for (i = vbox->r1; i <= vbox->r2; i++) {
1609 for (j = vbox->g1; j <= vbox->g2; j++) {
1610 for (k = vbox->b1; k <= vbox->b2; k++) {
1611 index = (i << (2 * sigbits)) + (j << sigbits) + k;
1612 npix += histo[index];
1613 }
1614 }
1615 }
1616
1617 return npix;
1618}
1619
1620
1627static l_int32
1628vboxGetVolume(L_BOX3D *vbox)
1629{
1630 PROCNAME("vboxGetVolume");
1631
1632 if (!vbox)
1633 return ERROR_INT("vbox not defined", procName, 0);
1634
1635 return ((vbox->r2 - vbox->r1 + 1) * (vbox->g2 - vbox->g1 + 1) *
1636 (vbox->b2 - vbox->b1 + 1));
1637}
1638
1645static L_BOX3D *
1646box3dCreate(l_int32 r1,
1647 l_int32 r2,
1648 l_int32 g1,
1649 l_int32 g2,
1650 l_int32 b1,
1651 l_int32 b2)
1652{
1653L_BOX3D *vbox;
1654
1655 vbox = (L_BOX3D *)LEPT_CALLOC(1, sizeof(L_BOX3D));
1656 vbox->r1 = r1;
1657 vbox->r2 = r2;
1658 vbox->g1 = g1;
1659 vbox->g2 = g2;
1660 vbox->b1 = b1;
1661 vbox->b2 = b2;
1662 return vbox;
1663}
1664
1665
1677static L_BOX3D *
1678box3dCopy(L_BOX3D *vbox)
1679{
1680L_BOX3D *vboxc;
1681
1682 PROCNAME("box3dCopy");
1683
1684 if (!vbox)
1685 return (L_BOX3D *)ERROR_PTR("vbox not defined", procName, NULL);
1686
1687 vboxc = box3dCreate(vbox->r1, vbox->r2, vbox->g1, vbox->g2,
1688 vbox->b1, vbox->b2);
1689 vboxc->npix = vbox->npix;
1690 vboxc->vol = vbox->vol;
1691 return vboxc;
1692}
SET_DATA_BIT
#define SET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:127
SET_DATA_DIBIT
#define SET_DATA_DIBIT(pdata, n, val)
Definition: arrayaccess.h:149
GET_DATA_BYTE
#define GET_DATA_BYTE(pdata, n)
Definition: arrayaccess.h:188
SET_DATA_BYTE
#define SET_DATA_BYTE(pdata, n, val)
Definition: arrayaccess.h:198
SET_DATA_QBIT
#define SET_DATA_QBIT(pdata, n, val)
Definition: arrayaccess.h:168
pixColorsForQuantization
l_ok pixColorsForQuantization(PIX *pixs, l_int32 thresh, l_int32 *pncolors, l_int32 *piscolor, l_int32 debug)
pixColorsForQuantization()
Definition: colorcontent.c:1286
pixColorFraction
l_ok pixColorFraction(PIX *pixs, l_int32 darkthresh, l_int32 lightthresh, l_int32 diffthresh, l_int32 factor, l_float32 *ppixfract, l_float32 *pcolorfract)
pixColorFraction()
Definition: colorcontent.c:494
pixcmapGetCount
l_int32 pixcmapGetCount(const PIXCMAP *cmap)
pixcmapGetCount()
Definition: colormap.c:708
pixcmapCreate
PIXCMAP * pixcmapCreate(l_int32 depth)
pixcmapCreate()
Definition: colormap.c:125
pixcmapResetColor
l_ok pixcmapResetColor(PIXCMAP *cmap, l_int32 index, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapResetColor()
Definition: colormap.c:966
pixcmapGetColor
l_ok pixcmapGetColor(PIXCMAP *cmap, l_int32 index, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
pixcmapGetColor()
Definition: colormap.c:824
pixcmapGetRankIntensity
l_ok pixcmapGetRankIntensity(PIXCMAP *cmap, l_float32 rankval, l_int32 *pindex)
pixcmapGetRankIntensity()
Definition: colormap.c:1302
pixcmapAddColor
l_ok pixcmapAddColor(PIXCMAP *cmap, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapAddColor()
Definition: colormap.c:414
box3dCopy
static L_BOX3D * box3dCopy(L_BOX3D *vbox)
box3dCopy()
Definition: colorquant2.c:1678
vboxGetAverageColor
static l_int32 vboxGetAverageColor(L_BOX3D *vbox, l_int32 *histo, l_int32 sigbits, l_int32 index, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
vboxGetAverageColor()
Definition: colorquant2.c:1527
pixMedianCutQuant
PIX * pixMedianCutQuant(PIX *pixs, l_int32 ditherflag)
pixMedianCutQuant()
Definition: colorquant2.c:260
pixMedianCutQuantMixed
PIX * pixMedianCutQuantMixed(PIX *pixs, l_int32 ncolor, l_int32 ngray, l_int32 darkthresh, l_int32 lightthresh, l_int32 diffthresh)
pixMedianCutQuantMixed()
Definition: colorquant2.c:597
vboxGetCount
static l_int32 vboxGetCount(L_BOX3D *vbox, l_int32 *histo, l_int32 sigbits)
vboxGetCount()
Definition: colorquant2.c:1594
pixMedianCutHisto
l_int32 * pixMedianCutHisto(PIX *pixs, l_int32 sigbits, l_int32 subsample)
pixMedianCutHisto()
Definition: colorquant2.c:843
pixFewColorsMedianCutQuantMixed
PIX * pixFewColorsMedianCutQuantMixed(PIX *pixs, l_int32 ncolor, l_int32 ngray, l_int32 maxncolors, l_int32 darkthresh, l_int32 lightthresh, l_int32 diffthresh)
pixFewColorsMedianCutQuantMixed()
Definition: colorquant2.c:771
pixcmapGenerateFromHisto
static PIXCMAP * pixcmapGenerateFromHisto(PIX *pixs, l_int32 depth, l_int32 *histo, l_int32 histosize, l_int32 sigbits)
pixcmapGenerateFromHisto()
Definition: colorquant2.c:907
getColorIndexMedianCut
static void getColorIndexMedianCut(l_uint32 pixel, l_int32 rshift, l_uint32 mask, l_int32 sigbits, l_int32 *pindex)
getColorIndexMedianCut()
Definition: colorquant2.c:1202
pixMedianCutQuantGeneral
PIX * pixMedianCutQuantGeneral(PIX *pixs, l_int32 ditherflag, l_int32 outdepth, l_int32 maxcolors, l_int32 sigbits, l_int32 maxsub, l_int32 checkbw)
pixMedianCutQuantGeneral()
Definition: colorquant2.c:317
pixcmapGenerateFromMedianCuts
static PIXCMAP * pixcmapGenerateFromMedianCuts(L_HEAP *lh, l_int32 *histo, l_int32 sigbits)
pixcmapGenerateFromMedianCuts()
Definition: colorquant2.c:1471
medianCutApply
static l_int32 medianCutApply(l_int32 *histo, l_int32 sigbits, L_BOX3D *vbox, L_BOX3D **pvbox1, L_BOX3D **pvbox2)
medianCutApply()
Definition: colorquant2.c:1291
box3dCreate
static L_BOX3D * box3dCreate(l_int32 r1, l_int32 r2, l_int32 g1, l_int32 g2, l_int32 b1, l_int32 b2)
box3dCreate()
Definition: colorquant2.c:1646
vboxGetVolume
static l_int32 vboxGetVolume(L_BOX3D *vbox)
vboxGetVolume()
Definition: colorquant2.c:1628
pixGetColorRegion
static L_BOX3D * pixGetColorRegion(PIX *pixs, l_int32 sigbits, l_int32 subsample)
pixGetColorRegion()
Definition: colorquant2.c:1234
pixQuantizeWithColormap
static PIX * pixQuantizeWithColormap(PIX *pixs, l_int32 ditherflag, l_int32 outdepth, PIXCMAP *cmap, l_int32 *indexmap, l_int32 mapsize, l_int32 sigbits)
pixQuantizeWithColormap()
Definition: colorquant2.c:966
pixThresholdOn8bpp
PIX * pixThresholdOn8bpp(PIX *pixs, l_int32 nlevels, l_int32 cmapflag)
pixThresholdOn8bpp()
Definition: grayquant.c:1637
lheapDestroy
void lheapDestroy(L_HEAP **plh, l_int32 freeflag)
lheapDestroy()
Definition: heap.c:154
lheapRemove
void * lheapRemove(L_HEAP *lh)
lheapRemove()
Definition: heap.c:251
lheapGetElement
void * lheapGetElement(L_HEAP *lh, l_int32 index)
lheapGetElement()
Definition: heap.c:311
lheapCreate
L_HEAP * lheapCreate(l_int32 n, l_int32 direction)
lheapCreate()
Definition: heap.c:112
lheapGetCount
l_int32 lheapGetCount(L_HEAP *lh)
lheapGetCount()
Definition: heap.c:283
lheapAdd
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
Definition: heap.c:193
pixSetColormap
l_ok pixSetColormap(PIX *pix, PIXCMAP *colormap)
pixSetColormap()
Definition: pix1.c:1699
pixDestroy
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:621
pixGetDimensions
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1113
pixCreate
PIX * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
Definition: pix1.c:315
pixCopy
PIX * pixCopy(PIX *pixd, const PIX *pixs)
pixCopy()
Definition: pix1.c:705
pixGetData
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1763
pixGetRGBLine
l_ok pixGetRGBLine(PIX *pixs, l_int32 row, l_uint8 *bufr, l_uint8 *bufg, l_uint8 *bufb)
pixGetRGBLine()
Definition: pix2.c:2897
extractRGBValues
void extractRGBValues(l_uint32 pixel, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
extractRGBValues()
Definition: pix2.c:2820
L_SORT_DECREASING
@ L_SORT_DECREASING
Definition: pix.h:730
pixConvertTo8
PIX * pixConvertTo8(PIX *pixs, l_int32 cmapflag)
pixConvertTo8()
Definition: pixconv.c:3133
L_Box3d
Definition: colorquant2.c:183
L_Heap
Definition: heap.h:78
L_Heap::n
l_int32 n
Definition: heap.h:80
Pix
Definition: pix.h:139
lept_stderr
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306