Leptonica  1.83.1
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. */
182 struct 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 };
194 typedef struct L_Box3d L_BOX3D;
195 
196  /* Static median cut helper functions */
197 static PIXCMAP *pixcmapGenerateFromHisto(PIX *pixs, l_int32 depth,
198  l_int32 *histo, l_int32 histosize,
199  l_int32 sigbits);
200 static PIX *pixQuantizeWithColormap(PIX *pixs, l_int32 ditherflag,
201  l_int32 outdepth,
202  PIXCMAP *cmap, l_int32 *indexmap,
203  l_int32 mapsize, l_int32 sigbits);
204 static void getColorIndexMedianCut(l_uint32 pixel, l_int32 rshift,
205  l_uint32 mask, l_int32 sigbits,
206  l_int32 *pindex);
207 static L_BOX3D *pixGetColorRegion(PIX *pixs, l_int32 sigbits,
208  l_int32 subsample);
209 static l_int32 medianCutApply(l_int32 *histo, l_int32 sigbits,
210  L_BOX3D *vbox, L_BOX3D **pvbox1,
211  L_BOX3D **pvbox2);
212 static PIXCMAP *pixcmapGenerateFromMedianCuts(L_HEAP *lh, l_int32 *histo,
213  l_int32 sigbits);
214 static 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);
218 static l_int32 vboxGetCount(L_BOX3D *vbox, l_int32 *histo, l_int32 sigbits);
219 static l_int32 vboxGetVolume(L_BOX3D *vbox);
220 static L_BOX3D *box3dCreate(l_int32 r1, l_int32 r2, l_int32 g1,
221  l_int32 g2, l_int32 b1, l_int32 b2);
222 static L_BOX3D *box3dCopy(L_BOX3D *vbox);
223 
224 
225  /* 5 significant bits for each component is generally satisfactory */
226 static const l_int32 DefaultSigBits = 5;
227 static 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). */
231 static 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. */
235 static 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  *------------------------------------------------------------------------*/
259 PIX *
261  l_int32 ditherflag)
262 {
263  return pixMedianCutQuantGeneral(pixs, ditherflag,
264  0, 256, DefaultSigBits, 1, 1);
265 }
266 
267 
316 PIX *
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 {
325 l_int32 i, subsample, histosize, smalln, ncolors, niters, popcolors;
326 l_int32 w, h, minside, factor, index, rval, gval, bval;
327 l_int32 *histo;
328 l_float32 maxprod, prod, norm, pixfract, colorfract;
329 L_BOX3D *vbox, *vbox1, *vbox2;
330 L_HEAP *lh, *lhs;
331 PIX *pixd;
332 PIXCMAP *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. */
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. */
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 
594 PIX *
596  l_int32 ncolor,
597  l_int32 ngray,
598  l_int32 darkthresh,
599  l_int32 lightthresh,
600  l_int32 diffthresh)
601 {
602 l_int32 i, j, w, h, wplc, wplg, wpld, nc, unused, iscolor, factor, minside;
603 l_int32 rval, gval, bval, minval, maxval, val, grayval;
604 l_float32 pixfract, colorfract;
605 l_int32 *lut;
606 l_uint32 *datac, *datag, *datad, *linec, *lineg, *lined;
607 PIX *pixc, *pixg, *pixd;
608 PIXCMAP *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 
766 PIX *
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 {
775 l_int32 ncolors, iscolor;
776 PIX *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  *------------------------------------------------------------------------*/
836 l_int32 *
838  l_int32 sigbits,
839  l_int32 subsample)
840 {
841 l_int32 i, j, w, h, wpl, rshift, index, histosize;
842 l_int32 *histo;
843 l_uint32 mask, pixel;
844 l_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  *------------------------------------------------------------------------*/
898 static PIXCMAP *
900  l_int32 depth,
901  l_int32 *histo,
902  l_int32 histosize,
903  l_int32 sigbits)
904 {
905 l_int32 i, index, shift, rval, gval, bval;
906 l_uint32 mask;
907 PIXCMAP *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 
955 static PIX *
957  l_int32 ditherflag,
958  l_int32 outdepth,
959  PIXCMAP *cmap,
960  l_int32 *indexmap,
961  l_int32 mapsize,
962  l_int32 sigbits)
963 {
964 l_uint8 *bufu8r, *bufu8g, *bufu8b;
965 l_int32 i, j, w, h, wpls, wpld, rshift, index, cmapindex, success;
966 l_int32 rval, gval, bval, rc, gc, bc;
967 l_int32 dif, val1, val2, val3;
968 l_int32 *buf1r, *buf1g, *buf1b, *buf2r, *buf2g, *buf2b;
969 l_uint32 *datas, *datad, *lines, *lined;
970 l_uint32 mask, pixel;
971 PIX *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 
1156 buffer_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 
1189 static void
1190 getColorIndexMedianCut(l_uint32 pixel,
1191  l_int32 rshift,
1192  l_uint32 mask,
1193  l_int32 sigbits,
1194  l_int32 *pindex)
1195 {
1196 l_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 
1221 static L_BOX3D *
1223  l_int32 sigbits,
1224  l_int32 subsample)
1225 {
1226 l_int32 rmin, rmax, gmin, gmax, bmin, bmax, rval, gval, bval;
1227 l_int32 w, h, wpl, i, j, rshift;
1228 l_uint32 mask, pixel;
1229 l_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 
1276 static l_int32
1277 medianCutApply(l_int32 *histo,
1278  l_int32 sigbits,
1279  L_BOX3D *vbox,
1280  L_BOX3D **pvbox1,
1281  L_BOX3D **pvbox2)
1282 {
1283 l_int32 i, j, k, sum, rw, gw, bw, maxw, index;
1284 l_int32 total, left, right;
1285 l_int32 partialsum[128];
1286 L_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 
1454 static PIXCMAP *
1456  l_int32 *histo,
1457  l_int32 sigbits)
1458 {
1459 l_int32 index, rval, gval, bval;
1460 L_BOX3D *vbox;
1461 PIXCMAP *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 
1508 static l_int32
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 {
1517 l_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 
1573 static l_int32
1575  l_int32 *histo,
1576  l_int32 sigbits)
1577 {
1578 l_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 
1605 static l_int32
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 
1621 static L_BOX3D *
1622 box3dCreate(l_int32 r1,
1623  l_int32 r2,
1624  l_int32 g1,
1625  l_int32 g2,
1626  l_int32 b1,
1627  l_int32 b2)
1628 {
1629 L_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 
1653 static L_BOX3D *
1655 {
1656 L_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 }
#define SET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:127
#define SET_DATA_DIBIT(pdata, n, val)
Definition: arrayaccess.h:149
#define GET_DATA_BYTE(pdata, n)
Definition: arrayaccess.h:188
#define SET_DATA_BYTE(pdata, n, val)
Definition: arrayaccess.h:198
#define SET_DATA_QBIT(pdata, n, val)
Definition: arrayaccess.h:168
l_ok pixColorsForQuantization(PIX *pixs, l_int32 thresh, l_int32 *pncolors, l_int32 *piscolor, l_int32 debug)
pixColorsForQuantization()
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:490
l_int32 pixcmapGetCount(const PIXCMAP *cmap)
pixcmapGetCount()
Definition: colormap.c:683
PIXCMAP * pixcmapCreate(l_int32 depth)
pixcmapCreate()
Definition: colormap.c:126
l_ok pixcmapResetColor(PIXCMAP *cmap, l_int32 index, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapResetColor()
Definition: colormap.c:923
l_ok pixcmapGetColor(PIXCMAP *cmap, l_int32 index, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
pixcmapGetColor()
Definition: colormap.c:789
l_ok pixcmapGetRankIntensity(PIXCMAP *cmap, l_float32 rankval, l_int32 *pindex)
pixcmapGetRankIntensity()
Definition: colormap.c:1243
l_ok pixcmapAddColor(PIXCMAP *cmap, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapAddColor()
Definition: colormap.c:403
PIX * pixMedianCutQuant(PIX *pixs, l_int32 ditherflag)
pixMedianCutQuant()
Definition: colorquant2.c:260
static L_BOX3D * box3dCopy(L_BOX3D *vbox)
box3dCopy()
Definition: colorquant2.c:1654
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
static l_int32 vboxGetCount(L_BOX3D *vbox, l_int32 *histo, l_int32 sigbits)
vboxGetCount()
Definition: colorquant2.c:1574
l_int32 * pixMedianCutHisto(PIX *pixs, l_int32 sigbits, l_int32 subsample)
pixMedianCutHisto()
Definition: colorquant2.c:837
PIX * pixMedianCutQuantMixed(PIX *pixs, l_int32 ncolor, l_int32 ngray, l_int32 darkthresh, l_int32 lightthresh, l_int32 diffthresh)
pixMedianCutQuantMixed()
Definition: colorquant2.c:595
static PIXCMAP * pixcmapGenerateFromHisto(PIX *pixs, l_int32 depth, l_int32 *histo, l_int32 histosize, l_int32 sigbits)
pixcmapGenerateFromHisto()
Definition: colorquant2.c:899
static void getColorIndexMedianCut(l_uint32 pixel, l_int32 rshift, l_uint32 mask, l_int32 sigbits, l_int32 *pindex)
getColorIndexMedianCut()
Definition: colorquant2.c:1190
static PIXCMAP * pixcmapGenerateFromMedianCuts(L_HEAP *lh, l_int32 *histo, l_int32 sigbits)
pixcmapGenerateFromMedianCuts()
Definition: colorquant2.c:1455
static l_int32 medianCutApply(l_int32 *histo, l_int32 sigbits, L_BOX3D *vbox, L_BOX3D **pvbox1, L_BOX3D **pvbox2)
medianCutApply()
Definition: colorquant2.c:1277
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
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
static l_int32 vboxGetVolume(L_BOX3D *vbox)
vboxGetVolume()
Definition: colorquant2.c:1606
static L_BOX3D * pixGetColorRegion(PIX *pixs, l_int32 sigbits, l_int32 subsample)
pixGetColorRegion()
Definition: colorquant2.c:1222
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
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
PIX * pixThresholdOn8bpp(PIX *pixs, l_int32 nlevels, l_int32 cmapflag)
pixThresholdOn8bpp()
Definition: grayquant.c:1611
void lheapDestroy(L_HEAP **plh, l_int32 freeflag)
lheapDestroy()
Definition: heap.c:152
L_HEAP * lheapCreate(l_int32 n, l_int32 direction)
lheapCreate()
Definition: heap.c:112
void * lheapGetElement(L_HEAP *lh, l_int32 index)
lheapGetElement()
Definition: heap.c:299
l_int32 lheapGetCount(L_HEAP *lh)
lheapGetCount()
Definition: heap.c:273
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
Definition: heap.c:189
void * lheapRemove(L_HEAP *lh)
lheapRemove()
Definition: heap.c:243
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1642
l_ok pixSetColormap(PIX *pix, PIXCMAP *colormap)
pixSetColormap()
Definition: pix1.c:1582
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:608
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1074
PIX * pixCopy(PIX *pixd, const PIX *pixs)
pixCopy()
Definition: pix1.c:689
PIX * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
Definition: pix1.c:315
l_ok pixGetRGBLine(PIX *pixs, l_int32 row, l_uint8 *bufr, l_uint8 *bufg, l_uint8 *bufb)
pixGetRGBLine()
Definition: pix2.c:2870
void extractRGBValues(l_uint32 pixel, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
extractRGBValues()
Definition: pix2.c:2793
@ L_SORT_DECREASING
Definition: pix.h:523
PIX * pixConvertTo8(PIX *pixs, l_int32 cmapflag)
pixConvertTo8()
Definition: pixconv.c:3055
Definition: heap.h:78
l_int32 n
Definition: heap.h:80
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306