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. */
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  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. */
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. */
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 
596 PIX *
598  l_int32 ncolor,
599  l_int32 ngray,
600  l_int32 darkthresh,
601  l_int32 lightthresh,
602  l_int32 diffthresh)
603 {
604 l_int32 i, j, w, h, wplc, wplg, wpld, nc, unused, iscolor, factor, minside;
605 l_int32 rval, gval, bval, minval, maxval, val, grayval;
606 l_float32 pixfract, colorfract;
607 l_int32 *lut;
608 l_uint32 *datac, *datag, *datad, *linec, *lineg, *lined;
609 PIX *pixc, *pixg, *pixd;
610 PIXCMAP *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 
770 PIX *
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 {
779 l_int32 ncolors, iscolor;
780 PIX *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  *------------------------------------------------------------------------*/
842 l_int32 *
844  l_int32 sigbits,
845  l_int32 subsample)
846 {
847 l_int32 i, j, w, h, wpl, rshift, index, histosize;
848 l_int32 *histo;
849 l_uint32 mask, pixel;
850 l_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  *------------------------------------------------------------------------*/
906 static PIXCMAP *
908  l_int32 depth,
909  l_int32 *histo,
910  l_int32 histosize,
911  l_int32 sigbits)
912 {
913 l_int32 i, index, shift, rval, gval, bval;
914 l_uint32 mask;
915 PIXCMAP *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 
965 static PIX *
967  l_int32 ditherflag,
968  l_int32 outdepth,
969  PIXCMAP *cmap,
970  l_int32 *indexmap,
971  l_int32 mapsize,
972  l_int32 sigbits)
973 {
974 l_uint8 *bufu8r, *bufu8g, *bufu8b;
975 l_int32 i, j, w, h, wpls, wpld, rshift, index, cmapindex, success;
976 l_int32 rval, gval, bval, rc, gc, bc;
977 l_int32 dif, val1, val2, val3;
978 l_int32 *buf1r, *buf1g, *buf1b, *buf2r, *buf2g, *buf2b;
979 l_uint32 *datas, *datad, *lines, *lined;
980 l_uint32 mask, pixel;
981 PIX *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 
1168 buffer_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 
1201 static void
1202 getColorIndexMedianCut(l_uint32 pixel,
1203  l_int32 rshift,
1204  l_uint32 mask,
1205  l_int32 sigbits,
1206  l_int32 *pindex)
1207 {
1208 l_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 
1233 static L_BOX3D *
1235  l_int32 sigbits,
1236  l_int32 subsample)
1237 {
1238 l_int32 rmin, rmax, gmin, gmax, bmin, bmax, rval, gval, bval;
1239 l_int32 w, h, wpl, i, j, rshift;
1240 l_uint32 mask, pixel;
1241 l_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 
1290 static l_int32
1291 medianCutApply(l_int32 *histo,
1292  l_int32 sigbits,
1293  L_BOX3D *vbox,
1294  L_BOX3D **pvbox1,
1295  L_BOX3D **pvbox2)
1296 {
1297 l_int32 i, j, k, sum, rw, gw, bw, maxw, index;
1298 l_int32 total, left, right;
1299 l_int32 partialsum[128];
1300 L_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 
1470 static PIXCMAP *
1472  l_int32 *histo,
1473  l_int32 sigbits)
1474 {
1475 l_int32 index, rval, gval, bval;
1476 L_BOX3D *vbox;
1477 PIXCMAP *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 
1526 static l_int32
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 {
1535 l_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 
1593 static l_int32
1595  l_int32 *histo,
1596  l_int32 sigbits)
1597 {
1598 l_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 
1627 static l_int32
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 
1645 static L_BOX3D *
1646 box3dCreate(l_int32 r1,
1647  l_int32 r2,
1648  l_int32 g1,
1649  l_int32 g2,
1650  l_int32 b1,
1651  l_int32 b2)
1652 {
1653 L_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 
1677 static L_BOX3D *
1679 {
1680 L_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 }
#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:494
l_int32 pixcmapGetCount(const PIXCMAP *cmap)
pixcmapGetCount()
Definition: colormap.c:708
PIXCMAP * pixcmapCreate(l_int32 depth)
pixcmapCreate()
Definition: colormap.c:125
l_ok pixcmapResetColor(PIXCMAP *cmap, l_int32 index, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapResetColor()
Definition: colormap.c:966
l_ok pixcmapGetColor(PIXCMAP *cmap, l_int32 index, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
pixcmapGetColor()
Definition: colormap.c:824
l_ok pixcmapGetRankIntensity(PIXCMAP *cmap, l_float32 rankval, l_int32 *pindex)
pixcmapGetRankIntensity()
Definition: colormap.c:1302
l_ok pixcmapAddColor(PIXCMAP *cmap, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapAddColor()
Definition: colormap.c:414
PIX * pixMedianCutQuant(PIX *pixs, l_int32 ditherflag)
pixMedianCutQuant()
Definition: colorquant2.c:260
static L_BOX3D * box3dCopy(L_BOX3D *vbox)
box3dCopy()
Definition: colorquant2.c:1678
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
static l_int32 vboxGetCount(L_BOX3D *vbox, l_int32 *histo, l_int32 sigbits)
vboxGetCount()
Definition: colorquant2.c:1594
l_int32 * pixMedianCutHisto(PIX *pixs, l_int32 sigbits, l_int32 subsample)
pixMedianCutHisto()
Definition: colorquant2.c:843
PIX * pixMedianCutQuantMixed(PIX *pixs, l_int32 ncolor, l_int32 ngray, l_int32 darkthresh, l_int32 lightthresh, l_int32 diffthresh)
pixMedianCutQuantMixed()
Definition: colorquant2.c:597
static PIXCMAP * pixcmapGenerateFromHisto(PIX *pixs, l_int32 depth, l_int32 *histo, l_int32 histosize, l_int32 sigbits)
pixcmapGenerateFromHisto()
Definition: colorquant2.c:907
static void getColorIndexMedianCut(l_uint32 pixel, l_int32 rshift, l_uint32 mask, l_int32 sigbits, l_int32 *pindex)
getColorIndexMedianCut()
Definition: colorquant2.c:1202
static PIXCMAP * pixcmapGenerateFromMedianCuts(L_HEAP *lh, l_int32 *histo, l_int32 sigbits)
pixcmapGenerateFromMedianCuts()
Definition: colorquant2.c:1471
static l_int32 medianCutApply(l_int32 *histo, l_int32 sigbits, L_BOX3D *vbox, L_BOX3D **pvbox1, L_BOX3D **pvbox2)
medianCutApply()
Definition: colorquant2.c:1291
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
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:1628
static L_BOX3D * pixGetColorRegion(PIX *pixs, l_int32 sigbits, l_int32 subsample)
pixGetColorRegion()
Definition: colorquant2.c:1234
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
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
PIX * pixThresholdOn8bpp(PIX *pixs, l_int32 nlevels, l_int32 cmapflag)
pixThresholdOn8bpp()
Definition: grayquant.c:1637
void lheapDestroy(L_HEAP **plh, l_int32 freeflag)
lheapDestroy()
Definition: heap.c:154
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:311
l_int32 lheapGetCount(L_HEAP *lh)
lheapGetCount()
Definition: heap.c:283
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
Definition: heap.c:193
void * lheapRemove(L_HEAP *lh)
lheapRemove()
Definition: heap.c:251
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1763
l_ok pixSetColormap(PIX *pix, PIXCMAP *colormap)
pixSetColormap()
Definition: pix1.c:1699
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:621
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1113
PIX * pixCopy(PIX *pixd, const PIX *pixs)
pixCopy()
Definition: pix1.c:705
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:2897
void extractRGBValues(l_uint32 pixel, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
extractRGBValues()
Definition: pix2.c:2820
@ L_SORT_DECREASING
Definition: pix.h:730
PIX * pixConvertTo8(PIX *pixs, l_int32 cmapflag)
pixConvertTo8()
Definition: pixconv.c:3133
Definition: heap.h:78
l_int32 n
Definition: heap.h:80
Definition: pix.h:139
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306