Leptonica 1.85.0
Image processing and image analysis suite
Loading...
Searching...
No Matches
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.85f;
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 if (!pixs || pixGetDepth(pixs) != 32)
335 return (PIX *)ERROR_PTR("pixs undefined or not 32 bpp", __func__, NULL);
336 if (maxcolors < 2 || maxcolors > 256)
337 return (PIX *)ERROR_PTR("maxcolors not in [2...256]", __func__, NULL);
338 if (outdepth != 0 && outdepth != 1 && outdepth != 2 && outdepth != 4 &&
339 outdepth != 8)
340 return (PIX *)ERROR_PTR("outdepth not in {0,1,2,4,8}", __func__, NULL);
341 if (outdepth > 0 && (maxcolors > (1 << outdepth)))
342 return (PIX *)ERROR_PTR("maxcolors > 2^(outdepth)", __func__, NULL);
343 if (sigbits == 0)
344 sigbits = DefaultSigBits;
345 else if (sigbits < 5 || sigbits > 6)
346 return (PIX *)ERROR_PTR("sigbits not 5 or 6", __func__, NULL);
347 if (maxsub <= 0)
348 maxsub = 10; /* default will prevail for 10^7 pixels or less */
349
350 /* Determine if the image has sufficient color content.
351 * If pixfract << 1, most pixels are close to black or white.
352 * If colorfract << 1, the pixels that are not near
353 * black or white have very little color.
354 * If with little color, quantize with a grayscale colormap. */
355 pixGetDimensions(pixs, &w, &h, NULL);
356 if (checkbw) {
357 minside = L_MIN(w, h);
358 factor = L_MAX(1, minside / 400);
359 pixColorFraction(pixs, 20, 244, 20, factor, &pixfract, &colorfract);
360 if (pixfract * colorfract < 0.00025) {
361 L_INFO("\n Pixel fraction neither white nor black = %6.3f"
362 "\n Color fraction of those pixels = %6.3f"
363 "\n Quantizing in gray\n",
364 __func__, pixfract, colorfract);
365 return pixConvertTo8(pixs, 1);
366 }
367 }
368
369 /* Compute the color space histogram. Default sampling
370 * is about 10^5 sampled pixels. */
371 if (maxsub == 1) {
372 subsample = 1;
373 } else {
374 subsample = (l_int32)(sqrt((l_float64)(w * h) / 100000.));
375 subsample = L_MAX(1, L_MIN(maxsub, subsample));
376 }
377 histo = pixMedianCutHisto(pixs, sigbits, subsample);
378 histosize = 1 << (3 * sigbits);
379
380 /* See if the number of quantized colors is less than maxcolors */
381 ncolors = 0;
382 smalln = TRUE;
383 for (i = 0; i < histosize; i++) {
384 if (histo[i])
385 ncolors++;
386 if (ncolors > maxcolors) {
387 smalln = FALSE;
388 break;
389 }
390 }
391 if (smalln) { /* finish up now */
392 if (outdepth == 0) {
393 if (ncolors <= 2)
394 outdepth = 1;
395 else if (ncolors <= 4)
396 outdepth = 2;
397 else if (ncolors <= 16)
398 outdepth = 4;
399 else
400 outdepth = 8;
401 }
402 cmap = pixcmapGenerateFromHisto(pixs, outdepth,
403 histo, histosize, sigbits);
404 pixd = pixQuantizeWithColormap(pixs, ditherflag, outdepth, cmap,
405 histo, histosize, sigbits);
406 LEPT_FREE(histo);
407 return pixd;
408 }
409
410 /* Initial vbox: minimum region in colorspace occupied by pixels */
411 if (ditherflag || subsample > 1) /* use full color space */
412 vbox = box3dCreate(0, (1 << sigbits) - 1,
413 0, (1 << sigbits) - 1,
414 0, (1 << sigbits) - 1);
415 else
416 vbox = pixGetColorRegion(pixs, sigbits, subsample);
417 vbox->npix = vboxGetCount(vbox, histo, sigbits);
418 vbox->vol = vboxGetVolume(vbox);
419
420 /* For a fraction 'popcolors' of the desired 'maxcolors',
421 * generate median cuts based on population, putting
422 * everything on a priority queue sorted by population. */
423 lh = lheapCreate(0, L_SORT_DECREASING);
424 lheapAdd(lh, vbox);
425 ncolors = 1;
426 niters = 0;
427 popcolors = (l_int32)(FractByPopulation * maxcolors);
428 while (1) {
429 vbox = (L_BOX3D *)lheapRemove(lh);
430 if (vboxGetCount(vbox, histo, sigbits) == 0) { /* just put it back */
431 lheapAdd(lh, vbox);
432 continue;
433 }
434 medianCutApply(histo, sigbits, vbox, &vbox1, &vbox2);
435 if (!vbox1) {
436 L_WARNING("vbox1 not defined; shouldn't happen!\n", __func__);
437 break;
438 }
439 if (vbox1->vol > 1)
440 vbox1->sortparam = vbox1->npix;
441 LEPT_FREE(vbox);
442 lheapAdd(lh, vbox1);
443 if (vbox2) { /* vbox2 can be NULL */
444 if (vbox2->vol > 1)
445 vbox2->sortparam = vbox2->npix;
446 lheapAdd(lh, vbox2);
447 ncolors++;
448 }
449 if (ncolors >= popcolors)
450 break;
451 if (niters++ > MaxItersAllowed) {
452 L_WARNING("infinite loop; perhaps too few pixels!\n", __func__);
453 break;
454 }
455 }
456
457 /* Re-sort by the product of pixel occupancy times the size
458 * in color space. Normalize to the largest product to avoid
459 * integer overflow. */
460 maxprod = 0.0;
461 for (i = 0; i < lh->n; i++) {
462 if ((vbox = (L_BOX3D *)lheapGetElement(lh, i)) == NULL)
463 continue;
464 prod = (l_float32)vbox->npix * (l_float32)vbox->vol;
465 if (prod > maxprod) maxprod = prod;
466 }
467 norm = (maxprod == 0) ? 1.0 : 1000000.0 / maxprod;
468 lhs = lheapCreate(0, L_SORT_DECREASING);
469 while ((vbox = (L_BOX3D *)lheapRemove(lh))) {
470 vbox->sortparam = norm * vbox->npix * vbox->vol;
471 lheapAdd(lhs, vbox);
472 }
473 lheapDestroy(&lh, TRUE);
474
475 /* For the remaining (maxcolors - popcolors), generate the
476 * median cuts using the (npix * vol) sorting. */
477 while (1) {
478 vbox = (L_BOX3D *)lheapRemove(lhs);
479 if (vboxGetCount(vbox, histo, sigbits) == 0) { /* just put it back */
480 lheapAdd(lhs, vbox);
481 continue;
482 }
483 medianCutApply(histo, sigbits, vbox, &vbox1, &vbox2);
484 if (!vbox1) {
485 L_WARNING("vbox1 not defined; shouldn't happen!\n", __func__);
486 break;
487 }
488 if (vbox1->vol > 1)
489 vbox1->sortparam = norm * vbox1->npix * vbox1->vol;
490 LEPT_FREE(vbox);
491 lheapAdd(lhs, vbox1);
492 if (vbox2) { /* vbox2 can be NULL */
493 if (vbox2->vol > 1)
494 vbox2->sortparam = norm * vbox2->npix * vbox2->vol;
495 lheapAdd(lhs, vbox2);
496 ncolors++;
497 }
498 if (ncolors >= maxcolors)
499 break;
500 if (niters++ > MaxItersAllowed) {
501 L_WARNING("infinite loop; perhaps too few pixels!\n", __func__);
502 break;
503 }
504 }
505
506 /* Re-sort by pixel occupancy. This is not necessary,
507 * but it makes a more useful listing. */
508 lh = lheapCreate(0, L_SORT_DECREASING);
509 while ((vbox = (L_BOX3D *)lheapRemove(lhs))) {
510 vbox->sortparam = vbox->npix;
511/* vbox->sortparam = vbox->npix * vbox->vol; */
512 lheapAdd(lh, vbox);
513 }
514 lheapDestroy(&lhs, TRUE);
515
516 /* Generate colormap from median cuts and quantize pixd */
517 cmap = pixcmapGenerateFromMedianCuts(lh, histo, sigbits);
518 if (outdepth == 0) {
519 ncolors = pixcmapGetCount(cmap);
520 if (ncolors <= 2)
521 outdepth = 1;
522 else if (ncolors <= 4)
523 outdepth = 2;
524 else if (ncolors <= 16)
525 outdepth = 4;
526 else
527 outdepth = 8;
528 }
529 pixd = pixQuantizeWithColormap(pixs, ditherflag, outdepth, cmap,
530 histo, histosize, sigbits);
531
532 /* Force darkest color to black if each component <= 4 */
533 pixcmapGetRankIntensity(cmap, 0.0, &index);
534 pixcmapGetColor(cmap, index, &rval, &gval, &bval);
535 if (rval < 5 && gval < 5 && bval < 5)
536 pixcmapResetColor(cmap, index, 0, 0, 0);
537
538 /* Force lightest color to white if each component >= 252 */
539 pixcmapGetRankIntensity(cmap, 1.0, &index);
540 pixcmapGetColor(cmap, index, &rval, &gval, &bval);
541 if (rval > 251 && gval > 251 && bval > 251)
542 pixcmapResetColor(cmap, index, 255, 255, 255);
543
544 lheapDestroy(&lh, TRUE);
545 LEPT_FREE(histo);
546 return pixd;
547}
548
549
594PIX *
595pixMedianCutQuantMixed(PIX *pixs,
596 l_int32 ncolor,
597 l_int32 ngray,
598 l_int32 darkthresh,
599 l_int32 lightthresh,
600 l_int32 diffthresh)
601{
602l_int32 i, j, w, h, wplc, wplg, wpld, nc, unused, iscolor, factor, minside;
603l_int32 rval, gval, bval, minval, maxval, val, grayval;
604l_float32 pixfract, colorfract;
605l_int32 *lut;
606l_uint32 *datac, *datag, *datad, *linec, *lineg, *lined;
607PIX *pixc, *pixg, *pixd;
608PIXCMAP *cmap;
609
610 if (!pixs || pixGetDepth(pixs) != 32)
611 return (PIX *)ERROR_PTR("pixs undefined or not 32 bpp", __func__, NULL);
612 if (ngray < 2)
613 return (PIX *)ERROR_PTR("ngray < 2", __func__, NULL);
614 if (ncolor + ngray > 255)
615 return (PIX *)ERROR_PTR("ncolor + ngray > 255", __func__, NULL);
616 if (darkthresh <= 0) darkthresh = 20;
617 if (lightthresh <= 0) lightthresh = 244;
618 if (diffthresh <= 0) diffthresh = 20;
619
620 /* First check if this should be quantized in gray.
621 * Use a more sensitive parameter for detecting color than with
622 * pixMedianCutQuantGeneral(), because this function can handle
623 * gray pixels well. */
624 pixGetDimensions(pixs, &w, &h, NULL);
625 minside = L_MIN(w, h);
626 factor = L_MAX(1, minside / 400);
627 pixColorFraction(pixs, darkthresh, lightthresh, diffthresh, factor,
628 &pixfract, &colorfract);
629 if (pixfract * colorfract < 0.0001) {
630 L_INFO("\n Pixel fraction neither white nor black = %6.3f"
631 "\n Color fraction of those pixels = %6.3f"
632 "\n Quantizing in gray\n",
633 __func__, pixfract, colorfract);
634 pixg = pixConvertTo8(pixs, 0);
635 pixd = pixThresholdOn8bpp(pixg, ngray, 1);
636 pixDestroy(&pixg);
637 return pixd;
638 }
639
640 /* OK, there is color in the image.
641 * Preprocess to handle the gray pixels. Set the color pixels in pixc
642 * to black, and store their (eventual) colormap indices in pixg.*/
643 pixc = pixCopy(NULL, pixs);
644 pixg = pixCreate(w, h, 8); /* color pixels will remain 0 here */
645 datac = pixGetData(pixc);
646 datag = pixGetData(pixg);
647 wplc = pixGetWpl(pixc);
648 wplg = pixGetWpl(pixg);
649 lut = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
650 for (i = 0; i < 256; i++)
651 lut[i] = ncolor + 1 + (i * (ngray - 1) + 128) / 255;
652 for (i = 0; i < h; i++) {
653 linec = datac + i * wplc;
654 lineg = datag + i * wplg;
655 for (j = 0; j < w; j++) {
656 iscolor = FALSE;
657 extractRGBValues(linec[j], &rval, &gval, &bval);
658 minval = L_MIN(rval, gval);
659 minval = L_MIN(minval, bval);
660 maxval = L_MAX(rval, gval);
661 maxval = L_MAX(maxval, bval);
662 if (maxval >= darkthresh &&
663 minval <= lightthresh &&
664 maxval - minval >= diffthresh) {
665 iscolor = TRUE;
666 }
667 if (!iscolor) {
668 linec[j] = 0x0; /* set to black */
669 grayval = (maxval + minval) / 2;
670 SET_DATA_BYTE(lineg, j, lut[grayval]);
671 }
672 }
673 }
674
675 /* Median cut on color pixels plus black */
676 pixd = pixMedianCutQuantGeneral(pixc, FALSE, 8, ncolor + 1,
677 DefaultSigBits, 1, 0);
678
679 /* Augment the colormap with gray values. The new cmap
680 * indices should agree with the values previously stored in pixg. */
681 cmap = pixGetColormap(pixd);
682 nc = pixcmapGetCount(cmap);
683 unused = ncolor + 1 - nc;
684 if (unused < 0)
685 L_ERROR("Too many colors: extra = %d\n", __func__, -unused);
686 if (unused > 0) { /* fill in with black; these won't be used */
687 L_INFO("%d unused colors\n", __func__, unused);
688 for (i = 0; i < unused; i++)
689 pixcmapAddColor(cmap, 0, 0, 0);
690 }
691 for (i = 0; i < ngray; i++) {
692 grayval = (255 * i) / (ngray - 1);
693 pixcmapAddColor(cmap, grayval, grayval, grayval);
694 }
695
696 /* Substitute cmap indices for the gray pixels into pixd */
697 datad = pixGetData(pixd);
698 wpld = pixGetWpl(pixd);
699 for (i = 0; i < h; i++) {
700 lined = datad + i * wpld;
701 lineg = datag + i * wplg;
702 for (j = 0; j < w; j++) {
703 val = GET_DATA_BYTE(lineg, j); /* if 0, it's a color pixel */
704 if (val)
705 SET_DATA_BYTE(lined, j, val);
706 }
707 }
708
709 pixDestroy(&pixc);
710 pixDestroy(&pixg);
711 LEPT_FREE(lut);
712 return pixd;
713}
714
715
766PIX *
767pixFewColorsMedianCutQuantMixed(PIX *pixs,
768 l_int32 ncolor,
769 l_int32 ngray,
770 l_int32 maxncolors,
771 l_int32 darkthresh,
772 l_int32 lightthresh,
773 l_int32 diffthresh)
774{
775l_int32 ncolors, iscolor;
776PIX *pixg, *pixd;
777
778 if (!pixs || pixGetDepth(pixs) != 32)
779 return (PIX *)ERROR_PTR("pixs undefined or not 32 bpp", __func__, NULL);
780 if (maxncolors <= 0) maxncolors = 20;
781 if (darkthresh <= 0) darkthresh = 20;
782 if (lightthresh <= 0) lightthresh = 244;
783 if (diffthresh <= 0) diffthresh = 15;
784 if (ncolor < maxncolors) {
785 L_WARNING("ncolor too small; setting to %d\n", __func__, maxncolors);
786 ncolor = maxncolors;
787 }
788 if (ngray < maxncolors) {
789 L_WARNING("ngray too small; setting to %d\n", __func__, maxncolors);
790 ngray = maxncolors;
791 }
792
793 /* Estimate the color content and the number of colors required */
794 pixColorsForQuantization(pixs, 15, &ncolors, &iscolor, 0);
795
796 /* Note that maxncolors applies to all colors required to quantize,
797 * both gray and colorful */
798 if (ncolors > maxncolors)
799 return (PIX *)ERROR_PTR("too many colors", __func__, NULL);
800
801 /* If no color, return quantized gray pix */
802 if (!iscolor) {
803 pixg = pixConvertTo8(pixs, 0);
804 pixd = pixThresholdOn8bpp(pixg, ngray, 1);
805 pixDestroy(&pixg);
806 return pixd;
807 }
808
809 /* Use the mixed gray/color quantizer */
810 return pixMedianCutQuantMixed(pixs, ncolor, ngray, darkthresh,
811 lightthresh, diffthresh);
812}
813
814
815
816/*------------------------------------------------------------------------*
817 * Median cut indexed histogram *
818 *------------------------------------------------------------------------*/
836l_int32 *
837pixMedianCutHisto(PIX *pixs,
838 l_int32 sigbits,
839 l_int32 subsample)
840{
841l_int32 i, j, w, h, wpl, rshift, index, histosize;
842l_int32 *histo;
843l_uint32 mask, pixel;
844l_uint32 *data, *line;
845
846 if (!pixs)
847 return (l_int32 *)ERROR_PTR("pixs not defined", __func__, NULL);
848 if (pixGetDepth(pixs) != 32)
849 return (l_int32 *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
850 if (sigbits < 5 || sigbits > 6)
851 return (l_int32 *)ERROR_PTR("sigbits not 5 or 6", __func__, NULL);
852 if (subsample <= 0)
853 return (l_int32 *)ERROR_PTR("subsample not > 0", __func__, NULL);
854
855 histosize = 1 << (3 * sigbits);
856 if ((histo = (l_int32 *)LEPT_CALLOC(histosize, sizeof(l_int32))) == NULL)
857 return (l_int32 *)ERROR_PTR("histo not made", __func__, NULL);
858
859 rshift = 8 - sigbits;
860 mask = 0xff >> rshift;
861 pixGetDimensions(pixs, &w, &h, NULL);
862 data = pixGetData(pixs);
863 wpl = pixGetWpl(pixs);
864 for (i = 0; i < h; i += subsample) {
865 line = data + i * wpl;
866 for (j = 0; j < w; j += subsample) {
867 pixel = line[j];
868 getColorIndexMedianCut(pixel, rshift, mask, sigbits, &index);
869 histo[index]++;
870 }
871 }
872
873 return histo;
874}
875
876
877/*------------------------------------------------------------------------*
878 * Static helpers *
879 *------------------------------------------------------------------------*/
898static PIXCMAP *
899pixcmapGenerateFromHisto(PIX *pixs,
900 l_int32 depth,
901 l_int32 *histo,
902 l_int32 histosize,
903 l_int32 sigbits)
904{
905l_int32 i, index, shift, rval, gval, bval;
906l_uint32 mask;
907PIXCMAP *cmap;
908
909 if (!pixs)
910 return (PIXCMAP *)ERROR_PTR("pixs not defined", __func__, NULL);
911 if (pixGetDepth(pixs) != 32)
912 return (PIXCMAP *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
913 if (!histo)
914 return (PIXCMAP *)ERROR_PTR("histo not defined", __func__, NULL);
915
916 /* Capture the rgb values of each occupied cube in the histo,
917 * and re-label the histo value with the colormap index. */
918 cmap = pixcmapCreate(depth);
919 shift = 8 - sigbits;
920 mask = 0xff >> shift;
921 for (i = 0, index = 0; i < histosize; i++) {
922 if (histo[i]) {
923 rval = (i >> (2 * sigbits)) << shift;
924 gval = ((i >> sigbits) & mask) << shift;
925 bval = (i & mask) << shift;
926 pixcmapAddColor(cmap, rval, gval, bval);
927 histo[i] = index++;
928 }
929 }
930
931 return cmap;
932}
933
934
955static PIX *
956pixQuantizeWithColormap(PIX *pixs,
957 l_int32 ditherflag,
958 l_int32 outdepth,
959 PIXCMAP *cmap,
960 l_int32 *indexmap,
961 l_int32 mapsize,
962 l_int32 sigbits)
963{
964l_uint8 *bufu8r, *bufu8g, *bufu8b;
965l_int32 i, j, w, h, wpls, wpld, rshift, index, cmapindex, success;
966l_int32 rval, gval, bval, rc, gc, bc;
967l_int32 dif, val1, val2, val3;
968l_int32 *buf1r, *buf1g, *buf1b, *buf2r, *buf2g, *buf2b;
969l_uint32 *datas, *datad, *lines, *lined;
970l_uint32 mask, pixel;
971PIX *pixd;
972
973 if (!pixs || pixGetDepth(pixs) != 32)
974 return (PIX *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
975 if (!cmap)
976 return (PIX *)ERROR_PTR("cmap not defined", __func__, NULL);
977 if (!indexmap)
978 return (PIX *)ERROR_PTR("indexmap not defined", __func__, NULL);
979 if (ditherflag)
980 outdepth = 8;
981
982 pixGetDimensions(pixs, &w, &h, NULL);
983 pixd = pixCreate(w, h, outdepth);
984 pixSetColormap(pixd, cmap);
985 pixCopyResolution(pixd, pixs);
986 pixCopyInputFormat(pixd, pixs);
987 datas = pixGetData(pixs);
988 datad = pixGetData(pixd);
989 wpls = pixGetWpl(pixs);
990 wpld = pixGetWpl(pixd);
991
992 rshift = 8 - sigbits;
993 mask = 0xff >> rshift;
994 if (ditherflag == 0) {
995 for (i = 0; i < h; i++) {
996 lines = datas + i * wpls;
997 lined = datad + i * wpld;
998 if (outdepth == 1) {
999 for (j = 0; j < w; j++) {
1000 pixel = lines[j];
1001 getColorIndexMedianCut(pixel, rshift, mask,
1002 sigbits, &index);
1003 if (indexmap[index])
1004 SET_DATA_BIT(lined, j);
1005 }
1006 } else if (outdepth == 2) {
1007 for (j = 0; j < w; j++) {
1008 pixel = lines[j];
1009 getColorIndexMedianCut(pixel, rshift, mask,
1010 sigbits, &index);
1011 SET_DATA_DIBIT(lined, j, indexmap[index]);
1012 }
1013 } else if (outdepth == 4) {
1014 for (j = 0; j < w; j++) {
1015 pixel = lines[j];
1016 getColorIndexMedianCut(pixel, rshift, mask,
1017 sigbits, &index);
1018 SET_DATA_QBIT(lined, j, indexmap[index]);
1019 }
1020 } else { /* outdepth == 8 */
1021 for (j = 0; j < w; j++) {
1022 pixel = lines[j];
1023 getColorIndexMedianCut(pixel, rshift, mask,
1024 sigbits, &index);
1025 SET_DATA_BYTE(lined, j, indexmap[index]);
1026 }
1027 }
1028 }
1029 } else { /* ditherflag == 1 */
1030 success = TRUE;
1031 bufu8r = bufu8g = bufu8b = NULL;
1032 buf1r = buf1g = buf1b = buf2r = buf2g = buf2b = NULL;
1033 bufu8r = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1034 bufu8g = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1035 bufu8b = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1036 buf1r = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1037 buf1g = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1038 buf1b = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1039 buf2r = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1040 buf2g = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1041 buf2b = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1042 if (!bufu8r || !bufu8g || !bufu8b || !buf1r || !buf1g ||
1043 !buf1b || !buf2r || !buf2g || !buf2b) {
1044 L_ERROR("buffer not made\n", __func__);
1045 success = FALSE;
1046 goto buffer_cleanup;
1047 }
1048
1049 /* Start by priming buf2; line 1 is above line 2 */
1050 pixGetRGBLine(pixs, 0, bufu8r, bufu8g, bufu8b);
1051 for (j = 0; j < w; j++) {
1052 buf2r[j] = 64 * bufu8r[j];
1053 buf2g[j] = 64 * bufu8g[j];
1054 buf2b[j] = 64 * bufu8b[j];
1055 }
1056
1057 for (i = 0; i < h - 1; i++) {
1058 /* Swap data 2 --> 1, and read in new line 2 */
1059 memcpy(buf1r, buf2r, 4 * w);
1060 memcpy(buf1g, buf2g, 4 * w);
1061 memcpy(buf1b, buf2b, 4 * w);
1062 pixGetRGBLine(pixs, i + 1, 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 /* Dither */
1070 lined = datad + i * wpld;
1071 for (j = 0; j < w - 1; j++) {
1072 rval = buf1r[j] / 64;
1073 gval = buf1g[j] / 64;
1074 bval = buf1b[j] / 64;
1075 index = ((rval >> rshift) << (2 * sigbits)) +
1076 ((gval >> rshift) << sigbits) + (bval >> rshift);
1077 cmapindex = indexmap[index];
1078 SET_DATA_BYTE(lined, j, cmapindex);
1079 pixcmapGetColor(cmap, cmapindex, &rc, &gc, &bc);
1080
1081 dif = buf1r[j] / 8 - 8 * rc;
1082 if (dif > DifCap) dif = DifCap;
1083 if (dif < -DifCap) dif = -DifCap;
1084 if (dif != 0) {
1085 val1 = buf1r[j + 1] + 3 * dif;
1086 val2 = buf2r[j] + 3 * dif;
1087 val3 = buf2r[j + 1] + 2 * dif;
1088 if (dif > 0) {
1089 buf1r[j + 1] = L_MIN(16383, val1);
1090 buf2r[j] = L_MIN(16383, val2);
1091 buf2r[j + 1] = L_MIN(16383, val3);
1092 } else {
1093 buf1r[j + 1] = L_MAX(0, val1);
1094 buf2r[j] = L_MAX(0, val2);
1095 buf2r[j + 1] = L_MAX(0, val3);
1096 }
1097 }
1098
1099 dif = buf1g[j] / 8 - 8 * gc;
1100 if (dif > DifCap) dif = DifCap;
1101 if (dif < -DifCap) dif = -DifCap;
1102 if (dif != 0) {
1103 val1 = buf1g[j + 1] + 3 * dif;
1104 val2 = buf2g[j] + 3 * dif;
1105 val3 = buf2g[j + 1] + 2 * dif;
1106 if (dif > 0) {
1107 buf1g[j + 1] = L_MIN(16383, val1);
1108 buf2g[j] = L_MIN(16383, val2);
1109 buf2g[j + 1] = L_MIN(16383, val3);
1110 } else {
1111 buf1g[j + 1] = L_MAX(0, val1);
1112 buf2g[j] = L_MAX(0, val2);
1113 buf2g[j + 1] = L_MAX(0, val3);
1114 }
1115 }
1116
1117 dif = buf1b[j] / 8 - 8 * bc;
1118 if (dif > DifCap) dif = DifCap;
1119 if (dif < -DifCap) dif = -DifCap;
1120 if (dif != 0) {
1121 val1 = buf1b[j + 1] + 3 * dif;
1122 val2 = buf2b[j] + 3 * dif;
1123 val3 = buf2b[j + 1] + 2 * dif;
1124 if (dif > 0) {
1125 buf1b[j + 1] = L_MIN(16383, val1);
1126 buf2b[j] = L_MIN(16383, val2);
1127 buf2b[j + 1] = L_MIN(16383, val3);
1128 } else {
1129 buf1b[j + 1] = L_MAX(0, val1);
1130 buf2b[j] = L_MAX(0, val2);
1131 buf2b[j + 1] = L_MAX(0, val3);
1132 }
1133 }
1134 }
1135
1136 /* Get last pixel in row; no downward propagation */
1137 rval = buf1r[w - 1] / 64;
1138 gval = buf1g[w - 1] / 64;
1139 bval = buf1b[w - 1] / 64;
1140 index = ((rval >> rshift) << (2 * sigbits)) +
1141 ((gval >> rshift) << sigbits) + (bval >> rshift);
1142 SET_DATA_BYTE(lined, w - 1, indexmap[index]);
1143 }
1144
1145 /* Get last row of pixels; no leftward propagation */
1146 lined = datad + (h - 1) * wpld;
1147 for (j = 0; j < w; j++) {
1148 rval = buf2r[j] / 64;
1149 gval = buf2g[j] / 64;
1150 bval = buf2b[j] / 64;
1151 index = ((rval >> rshift) << (2 * sigbits)) +
1152 ((gval >> rshift) << sigbits) + (bval >> rshift);
1153 SET_DATA_BYTE(lined, j, indexmap[index]);
1154 }
1155
1156buffer_cleanup:
1157 LEPT_FREE(bufu8r);
1158 LEPT_FREE(bufu8g);
1159 LEPT_FREE(bufu8b);
1160 LEPT_FREE(buf1r);
1161 LEPT_FREE(buf1g);
1162 LEPT_FREE(buf1b);
1163 LEPT_FREE(buf2r);
1164 LEPT_FREE(buf2g);
1165 LEPT_FREE(buf2b);
1166 if (!success) pixDestroy(&pixd);
1167 }
1168
1169 return pixd;
1170}
1171
1172
1189static void
1190getColorIndexMedianCut(l_uint32 pixel,
1191 l_int32 rshift,
1192 l_uint32 mask,
1193 l_int32 sigbits,
1194 l_int32 *pindex)
1195{
1196l_int32 rval, gval, bval;
1197
1198 rval = pixel >> (24 + rshift);
1199 gval = (pixel >> (16 + rshift)) & mask;
1200 bval = (pixel >> (8 + rshift)) & mask;
1201 *pindex = (rval << (2 * sigbits)) + (gval << sigbits) + bval;
1202 return;
1203}
1204
1205
1221static L_BOX3D *
1222pixGetColorRegion(PIX *pixs,
1223 l_int32 sigbits,
1224 l_int32 subsample)
1225{
1226l_int32 rmin, rmax, gmin, gmax, bmin, bmax, rval, gval, bval;
1227l_int32 w, h, wpl, i, j, rshift;
1228l_uint32 mask, pixel;
1229l_uint32 *data, *line;
1230
1231 if (!pixs)
1232 return (L_BOX3D *)ERROR_PTR("pixs not defined", __func__, NULL);
1233
1234 rmin = gmin = bmin = 1000000;
1235 rmax = gmax = bmax = 0;
1236 rshift = 8 - sigbits;
1237 mask = 0xff >> rshift;
1238 pixGetDimensions(pixs, &w, &h, NULL);
1239 data = pixGetData(pixs);
1240 wpl = pixGetWpl(pixs);
1241 for (i = 0; i < h; i += subsample) {
1242 line = data + i * wpl;
1243 for (j = 0; j < w; j += subsample) {
1244 pixel = line[j];
1245 rval = pixel >> (24 + rshift);
1246 gval = (pixel >> (16 + rshift)) & mask;
1247 bval = (pixel >> (8 + rshift)) & mask;
1248 if (rval < rmin)
1249 rmin = rval;
1250 else if (rval > rmax)
1251 rmax = rval;
1252 if (gval < gmin)
1253 gmin = gval;
1254 else if (gval > gmax)
1255 gmax = gval;
1256 if (bval < bmin)
1257 bmin = bval;
1258 else if (bval > bmax)
1259 bmax = bval;
1260 }
1261 }
1262
1263 return box3dCreate(rmin, rmax, gmin, gmax, bmin, bmax);
1264}
1265
1266
1276static l_int32
1277medianCutApply(l_int32 *histo,
1278 l_int32 sigbits,
1279 L_BOX3D *vbox,
1280 L_BOX3D **pvbox1,
1281 L_BOX3D **pvbox2)
1282{
1283l_int32 i, j, k, sum, rw, gw, bw, maxw, index;
1284l_int32 total, left, right;
1285l_int32 partialsum[128];
1286L_BOX3D *vbox1, *vbox2;
1287
1288 if (pvbox1) *pvbox1 = NULL;
1289 if (pvbox2) *pvbox2 = NULL;
1290 if (!histo)
1291 return ERROR_INT("histo not defined", __func__, 1);
1292 if (!vbox)
1293 return ERROR_INT("vbox not defined", __func__, 1);
1294 if (!pvbox1 || !pvbox2)
1295 return ERROR_INT("&vbox1 and &vbox2 not both defined", __func__, 1);
1296
1297 if (vboxGetCount(vbox, histo, sigbits) == 0)
1298 return ERROR_INT("no pixels in vbox", __func__, 1);
1299
1300 /* If the vbox occupies just one element in color space, it can't
1301 * be split. Leave the 'sortparam' field at 0, so that it goes to
1302 * the tail of the priority queue and stays there, thereby avoiding
1303 * an infinite loop (take off, put back on the head) if it
1304 * happens to be the most populous box! */
1305 rw = vbox->r2 - vbox->r1 + 1;
1306 gw = vbox->g2 - vbox->g1 + 1;
1307 bw = vbox->b2 - vbox->b1 + 1;
1308 if (rw == 1 && gw == 1 && bw == 1) {
1309 *pvbox1 = box3dCopy(vbox);
1310 return 0;
1311 }
1312
1313 /* Select the longest axis for splitting */
1314 maxw = L_MAX(rw, gw);
1315 maxw = L_MAX(maxw, bw);
1316#if DEBUG_SPLIT_AXES
1317 if (rw == maxw)
1318 lept_stderr("red split\n");
1319 else if (gw == maxw)
1320 lept_stderr("green split\n");
1321 else
1322 lept_stderr("blue split\n");
1323#endif /* DEBUG_SPLIT_AXES */
1324
1325 /* Find the partial sum arrays along the selected axis. */
1326 total = 0;
1327 if (maxw == rw) {
1328 for (i = vbox->r1; i <= vbox->r2; i++) {
1329 sum = 0;
1330 for (j = vbox->g1; j <= vbox->g2; j++) {
1331 for (k = vbox->b1; k <= vbox->b2; k++) {
1332 index = (i << (2 * sigbits)) + (j << sigbits) + k;
1333 sum += histo[index];
1334 }
1335 }
1336 total += sum;
1337 partialsum[i] = total;
1338 }
1339 } else if (maxw == gw) {
1340 for (i = vbox->g1; i <= vbox->g2; i++) {
1341 sum = 0;
1342 for (j = vbox->r1; j <= vbox->r2; j++) {
1343 for (k = vbox->b1; k <= vbox->b2; k++) {
1344 index = (i << sigbits) + (j << (2 * sigbits)) + k;
1345 sum += histo[index];
1346 }
1347 }
1348 total += sum;
1349 partialsum[i] = total;
1350 }
1351 } else { /* maxw == bw */
1352 for (i = vbox->b1; i <= vbox->b2; i++) {
1353 sum = 0;
1354 for (j = vbox->r1; j <= vbox->r2; j++) {
1355 for (k = vbox->g1; k <= vbox->g2; k++) {
1356 index = i + (j << (2 * sigbits)) + (k << sigbits);
1357 sum += histo[index];
1358 }
1359 }
1360 total += sum;
1361 partialsum[i] = total;
1362 }
1363 }
1364
1365 /* Determine the cut planes, making sure that two vboxes
1366 * are always produced. Generate the two vboxes and compute
1367 * the sum in each of them. Choose the cut plane within
1368 * the greater of the (left, right) sides of the bin in which
1369 * the median pixel resides. Here's the surprise: go halfway
1370 * into that side. By doing that, you technically move away
1371 * from "median cut," but in the process a significant number
1372 * of low-count vboxes are produced, allowing much better
1373 * reproduction of low-count spot colors. */
1374 vbox1 = vbox2 = NULL;
1375 if (maxw == rw) {
1376 for (i = vbox->r1; i <= vbox->r2; i++) {
1377 if (partialsum[i] > total / 2) {
1378 vbox1 = box3dCopy(vbox);
1379 vbox2 = box3dCopy(vbox);
1380 left = i - vbox->r1;
1381 right = vbox->r2 - i;
1382 if (left <= right)
1383 vbox1->r2 = L_MIN(vbox->r2 - 1, i + right / 2);
1384 else /* left > right */
1385 vbox1->r2 = L_MAX(vbox->r1, i - 1 - left / 2);
1386 vbox2->r1 = vbox1->r2 + 1;
1387 break;
1388 }
1389 }
1390 } else if (maxw == gw) {
1391 for (i = vbox->g1; i <= vbox->g2; i++) {
1392 if (partialsum[i] > total / 2) {
1393 vbox1 = box3dCopy(vbox);
1394 vbox2 = box3dCopy(vbox);
1395 left = i - vbox->g1;
1396 right = vbox->g2 - i;
1397 if (left <= right)
1398 vbox1->g2 = L_MIN(vbox->g2 - 1, i + right / 2);
1399 else /* left > right */
1400 vbox1->g2 = L_MAX(vbox->g1, i - 1 - left / 2);
1401 vbox2->g1 = vbox1->g2 + 1;
1402 break;
1403 }
1404 }
1405 } else { /* maxw == bw */
1406 for (i = vbox->b1; i <= vbox->b2; i++) {
1407 if (partialsum[i] > total / 2) {
1408 vbox1 = box3dCopy(vbox);
1409 vbox2 = box3dCopy(vbox);
1410 left = i - vbox->b1;
1411 right = vbox->b2 - i;
1412 if (left <= right)
1413 vbox1->b2 = L_MIN(vbox->b2 - 1, i + right / 2);
1414 else /* left > right */
1415 vbox1->b2 = L_MAX(vbox->b1, i - 1 - left / 2);
1416 vbox2->b1 = vbox1->b2 + 1;
1417 break;
1418 }
1419 }
1420 }
1421 *pvbox1 = vbox1;
1422 *pvbox2 = vbox2;
1423 if (!vbox1)
1424 return ERROR_INT("vbox1 not made; shouldn't happen", __func__, 1);
1425 if (!vbox2)
1426 return ERROR_INT("vbox2 not made; shouldn't happen", __func__, 1);
1427 vbox1->npix = vboxGetCount(vbox1, histo, sigbits);
1428 vbox2->npix = vboxGetCount(vbox2, histo, sigbits);
1429 vbox1->vol = vboxGetVolume(vbox1);
1430 vbox2->vol = vboxGetVolume(vbox2);
1431
1432 return 0;
1433}
1434
1435
1454static PIXCMAP *
1455pixcmapGenerateFromMedianCuts(L_HEAP *lh,
1456 l_int32 *histo,
1457 l_int32 sigbits)
1458{
1459l_int32 index, rval, gval, bval;
1460L_BOX3D *vbox;
1461PIXCMAP *cmap;
1462
1463 if (!lh)
1464 return (PIXCMAP *)ERROR_PTR("lh not defined", __func__, NULL);
1465 if (!histo)
1466 return (PIXCMAP *)ERROR_PTR("histo not defined", __func__, NULL);
1467
1468 rval = gval = bval = 0; /* make compiler happy */
1469 cmap = pixcmapCreate(8);
1470 index = 0;
1471 while (lheapGetCount(lh) > 0) {
1472 vbox = (L_BOX3D *)lheapRemove(lh);
1473 vboxGetAverageColor(vbox, histo, sigbits, index, &rval, &gval, &bval);
1474 pixcmapAddColor(cmap, rval, gval, bval);
1475 LEPT_FREE(vbox);
1476 index++;
1477 }
1478
1479 return cmap;
1480}
1481
1482
1508static l_int32
1509vboxGetAverageColor(L_BOX3D *vbox,
1510 l_int32 *histo,
1511 l_int32 sigbits,
1512 l_int32 index,
1513 l_int32 *prval,
1514 l_int32 *pgval,
1515 l_int32 *pbval)
1516{
1517l_int32 i, j, k, ntot, mult, histoindex, rsum, gsum, bsum;
1518
1519 if (!vbox)
1520 return ERROR_INT("vbox not defined", __func__, 1);
1521 if (!histo)
1522 return ERROR_INT("histo not defined", __func__, 1);
1523 if (!prval || !pgval || !pbval)
1524 return ERROR_INT("&p*val not all defined", __func__, 1);
1525
1526 *prval = *pgval = *pbval = 0;
1527 ntot = 0;
1528 mult = 1 << (8 - sigbits);
1529 rsum = gsum = bsum = 0;
1530 for (i = vbox->r1; i <= vbox->r2; i++) {
1531 for (j = vbox->g1; j <= vbox->g2; j++) {
1532 for (k = vbox->b1; k <= vbox->b2; k++) {
1533 histoindex = (i << (2 * sigbits)) + (j << sigbits) + k;
1534 ntot += histo[histoindex];
1535 rsum += (l_int32)(histo[histoindex] * (i + 0.5) * mult);
1536 gsum += (l_int32)(histo[histoindex] * (j + 0.5) * mult);
1537 bsum += (l_int32)(histo[histoindex] * (k + 0.5) * mult);
1538 if (index >= 0)
1539 histo[histoindex] = index;
1540 }
1541 }
1542 }
1543
1544 if (ntot == 0) {
1545 *prval = mult * (vbox->r1 + vbox->r2 + 1) / 2;
1546 *pgval = mult * (vbox->g1 + vbox->g2 + 1) / 2;
1547 *pbval = mult * (vbox->b1 + vbox->b2 + 1) / 2;
1548 } else {
1549 *prval = rsum / ntot;
1550 *pgval = gsum / ntot;
1551 *pbval = bsum / ntot;
1552 }
1553
1554#if DEBUG_MC_COLORS
1555 lept_stderr("ntot[%d] = %d: [%d, %d, %d], (%d, %d, %d)\n",
1556 index, ntot, vbox->r2 - vbox->r1 + 1,
1557 vbox->g2 - vbox->g1 + 1, vbox->b2 - vbox->b1 + 1,
1558 *prval, *pgval, *pbval);
1559#endif /* DEBUG_MC_COLORS */
1560
1561 return 0;
1562}
1563
1564
1573static l_int32
1574vboxGetCount(L_BOX3D *vbox,
1575 l_int32 *histo,
1576 l_int32 sigbits)
1577{
1578l_int32 i, j, k, npix, index;
1579
1580 if (!vbox)
1581 return ERROR_INT("vbox not defined", __func__, 0);
1582 if (!histo)
1583 return ERROR_INT("histo not defined", __func__, 0);
1584
1585 npix = 0;
1586 for (i = vbox->r1; i <= vbox->r2; i++) {
1587 for (j = vbox->g1; j <= vbox->g2; j++) {
1588 for (k = vbox->b1; k <= vbox->b2; k++) {
1589 index = (i << (2 * sigbits)) + (j << sigbits) + k;
1590 npix += histo[index];
1591 }
1592 }
1593 }
1594
1595 return npix;
1596}
1597
1598
1605static l_int32
1606vboxGetVolume(L_BOX3D *vbox)
1607{
1608 if (!vbox)
1609 return ERROR_INT("vbox not defined", __func__, 0);
1610
1611 return ((vbox->r2 - vbox->r1 + 1) * (vbox->g2 - vbox->g1 + 1) *
1612 (vbox->b2 - vbox->b1 + 1));
1613}
1614
1621static L_BOX3D *
1622box3dCreate(l_int32 r1,
1623 l_int32 r2,
1624 l_int32 g1,
1625 l_int32 g2,
1626 l_int32 b1,
1627 l_int32 b2)
1628{
1629L_BOX3D *vbox;
1630
1631 vbox = (L_BOX3D *)LEPT_CALLOC(1, sizeof(L_BOX3D));
1632 vbox->r1 = r1;
1633 vbox->r2 = r2;
1634 vbox->g1 = g1;
1635 vbox->g2 = g2;
1636 vbox->b1 = b1;
1637 vbox->b2 = b2;
1638 return vbox;
1639}
1640
1641
1653static L_BOX3D *
1654box3dCopy(L_BOX3D *vbox)
1655{
1656L_BOX3D *vboxc;
1657
1658 if (!vbox)
1659 return (L_BOX3D *)ERROR_PTR("vbox not defined", __func__, NULL);
1660
1661 vboxc = box3dCreate(vbox->r1, vbox->r2, vbox->g1, vbox->g2,
1662 vbox->b1, vbox->b2);
1663 vboxc->npix = vbox->npix;
1664 vboxc->vol = vbox->vol;
1665 return vboxc;
1666}
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
box3dCopy
static L_BOX3D * box3dCopy(L_BOX3D *vbox)
box3dCopy()
Definition colorquant2.c:1654
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:1509
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:595
vboxGetCount
static l_int32 vboxGetCount(L_BOX3D *vbox, l_int32 *histo, l_int32 sigbits)
vboxGetCount()
Definition colorquant2.c:1574
pixMedianCutHisto
l_int32 * pixMedianCutHisto(PIX *pixs, l_int32 sigbits, l_int32 subsample)
pixMedianCutHisto()
Definition colorquant2.c:837
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:767
pixcmapGenerateFromHisto
static PIXCMAP * pixcmapGenerateFromHisto(PIX *pixs, l_int32 depth, l_int32 *histo, l_int32 histosize, l_int32 sigbits)
pixcmapGenerateFromHisto()
Definition colorquant2.c:899
getColorIndexMedianCut
static void getColorIndexMedianCut(l_uint32 pixel, l_int32 rshift, l_uint32 mask, l_int32 sigbits, l_int32 *pindex)
getColorIndexMedianCut()
Definition colorquant2.c:1190
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:1455
medianCutApply
static l_int32 medianCutApply(l_int32 *histo, l_int32 sigbits, L_BOX3D *vbox, L_BOX3D **pvbox1, L_BOX3D **pvbox2)
medianCutApply()
Definition colorquant2.c:1277
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:1622
vboxGetVolume
static l_int32 vboxGetVolume(L_BOX3D *vbox)
vboxGetVolume()
Definition colorquant2.c:1606
pixGetColorRegion
static L_BOX3D * pixGetColorRegion(PIX *pixs, l_int32 sigbits, l_int32 subsample)
pixGetColorRegion()
Definition colorquant2.c:1222
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:956
L_SORT_DECREASING
@ L_SORT_DECREASING
Definition pix.h:523
L_Box3d
Definition colorquant2.c:183
L_Heap
Definition heap.h:78
L_Heap::n
l_int32 n
Definition heap.h:80