Leptonica  1.83.1
Image processing and image analysis suite
colorquant1.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 
117 #ifdef HAVE_CONFIG_H
118 #include <config_auto.h>
119 #endif /* HAVE_CONFIG_H */
120 
121 #include <string.h>
122 #include "allheaders.h"
123 #include "pix_internal.h"
124 
125 /*
126  * <pre>
127  * This data structure is used for pixOctreeColorQuant(),
128  * a color octree that adjusts to the color distribution
129  * in the image that is being quantized. The best settings
130  * are with CqNLevels = 6 and DITHERING set on.
131  *
132  * Notes:
133  * (1) the CTE (color table entry) index is sequentially
134  * assigned as the tree is pruned back
135  * (2) if 'bleaf' == 1, all pixels in that cube have been
136  * assigned to one or more CTEs. But note that if
137  * all 8 subcubes have 'bleaf' == 1, it will have no
138  * pixels left for assignment and will not be a CTE.
139  * (3) 'nleaves', the number of leaves contained at the next
140  * lower level is some number between 0 and 8, inclusive.
141  * If it is zero, it means that all colors within this cube
142  * are part of a single growing cluster that has not yet
143  * been set aside as a leaf. If 'nleaves' > 0, 'bleaf'
144  * will be set to 1 and all pixels not assigned to leaves
145  * at lower levels will be assigned to a CTE here.
146  * (However, as described above, if all pixels are already
147  * assigned, we set 'bleaf' = 1 but do not create a CTE
148  * at this level.)
149  * (4) To keep the maximum color error to a minimum, we
150  * prune the tree back to level 2, and require that
151  * all 64 level 2 cells are CTEs.
152  * (5) We reserve an extra set of colors to prevent running out
153  * of colors during the assignment of the final 64 level 2 cells.
154  * This is more likely to happen with small images.
155  * (6) When we run out of colors, the dithered image can be very
156  * poor, so we additionally prevent dithering if the image
157  * is small.
158  * (7) The color content of the image is measured, and if there
159  * is very little color, it is quantized in grayscale.
160  * </pre>
161  */
163 {
164  l_int32 rc, gc, bc; /* center values */
165  l_int32 n; /* number of samples in this cell */
166  l_int32 index; /* CTE (color table entry) index */
167  l_int32 nleaves; /* # of leaves contained at next lower level */
168  l_int32 bleaf; /* boolean: 0 if not a leaf, 1 if so */
169 };
170 typedef struct ColorQuantCell CQCELL;
171 
172  /* Constants for pixOctreeColorQuant() */
173 static const l_int32 CqNLevels = 5; /* only 4, 5 and 6 are allowed */
174 static const l_int32 CqReservedColors = 64; /* to allow for level 2 */
175  /* remainder CTEs */
176 static const l_int32 ExtraReservedColors = 25; /* to avoid running out */
177 static const l_int32 TreeGenWidth = 350; /* big enough for good stats */
178 static const l_int32 MinDitherSize = 250; /* don't dither if smaller */
179 
180 /*
181  * <pre>
182  * This data structure is used for pixOctreeQuantNumColors(),
183  * a color octree that adjusts in a simple way to the to the color
184  * distribution in the image that is being quantized. It outputs
185  * colormapped images, either 4 bpp or 8 bpp, depending on the
186  * max number of colors and the compression desired.
187  *
188  * The number of samples is saved as a float in the first location,
189  * because this is required to use it as the key that orders the
190  * cells in the priority queue.
191  * </pre>
192  * */
194 {
195  l_float32 n; /* number of samples in this cell */
196  l_int32 octindex; /* octcube index */
197  l_int32 rcum, gcum, bcum; /* cumulative values */
198  l_int32 rval, gval, bval; /* average values */
199 };
200 typedef struct OctcubeQuantCell OQCELL;
201 
202 /*
203  * <pre>
204  * This data structure is using for heap sorting octcubes
205  * by population. Sort order is decreasing.
206  * </pre>
207  */
209 {
210  l_float32 npix; /* parameter on which to sort */
211  l_int32 index; /* octcube index at assigned level */
212  l_int32 rval; /* mean red value of pixels in octcube */
213  l_int32 gval; /* mean green value of pixels in octcube */
214  l_int32 bval; /* mean blue value of pixels in octcube */
215 };
216 typedef struct L_OctcubePop L_OCTCUBE_POP;
217 
218 /*
219  * <pre>
220  * In pixDitherOctindexWithCmap(), we use these default values.
221  To get the max value of 'dif' in the dithering color transfer,
222  divide these "DIF_CAP" values by 8. However, a value of
223  0 means that there is no cap (infinite cap). A very small
224  value is used for POP_DIF_CAP because dithering on the population
225  generated colormap can be unstable without a tight cap.
226  * </pre>
227  */
228 
229 static const l_int32 FIXED_DIF_CAP = 0;
230 static const l_int32 POP_DIF_CAP = 40;
231 
232 
233  /* Static octree helper function */
234 static l_int32 octreeFindColorCell(l_int32 octindex, CQCELL ***cqcaa,
235  l_int32 *pindex, l_int32 *prval,
236  l_int32 *pgval, l_int32 *pbval);
237 
238  /* Static cqcell functions */
239 static CQCELL ***octreeGenerateAndPrune(PIX *pixs, l_int32 colors,
240  l_int32 reservedcolors,
241  PIXCMAP **pcmap);
242 static PIX *pixOctreeQuantizePixels(PIX *pixs, CQCELL ***cqcaa,
243  l_int32 ditherflag);
244 static CQCELL ***cqcellTreeCreate(void);
245 static void cqcellTreeDestroy(CQCELL ****pcqcaa);
246 
247  /* Static helper octcube index functions */
248 static void getRGBFromOctcube(l_int32 cubeindex, l_int32 level,
249  l_int32 *prval, l_int32 *pgval, l_int32 *pbval);
250 static l_int32 getOctcubeIndices(l_int32 rgbindex, l_int32 level,
251  l_int32 *pbindex, l_int32 *psindex);
252 static l_int32 octcubeGetCount(l_int32 level, l_int32 *psize);
253 
254  /* Static function to perform octcube-indexed dithering */
255 static l_int32 pixDitherOctindexWithCmap(PIX *pixs, PIX *pixd, l_uint32 *rtab,
256  l_uint32 *gtab, l_uint32 *btab,
257  l_int32 *carray, l_int32 difcap);
258 
259  /* Static function to perform octcube-based quantizing from colormap */
260 static PIX *pixOctcubeQuantFromCmapLUT(PIX *pixs, PIXCMAP *cmap,
261  l_int32 mindepth, l_int32 *cmaptab,
262  l_uint32 *rtab, l_uint32 *gtab,
263  l_uint32 *btab);
264 
265 #ifndef NO_CONSOLE_IO
266 #define DEBUG_COLORQUANT 0
267 #define DEBUG_OCTINDEX 0
268 #define DEBUG_OCTCUBE_CMAP 0
269 #define DEBUG_POP 0
270 #define DEBUG_FEW_COLORS 0
271 #define PRINT_OCTCUBE_STATS 0
272 #endif /* ~NO_CONSOLE_IO */
273 
274 /*-------------------------------------------------------------------------*
275  * Two-pass adaptive octree color quantization *
276  *-------------------------------------------------------------------------*/
535 PIX *
537  l_int32 colors,
538  l_int32 ditherflag)
539 {
540  if (!pixs)
541  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
542  if (pixGetDepth(pixs) != 32)
543  return (PIX *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
544  if (colors < 128 || colors > 240) /* further restricted */
545  return (PIX *)ERROR_PTR("colors must be in [128, 240]", __func__, NULL);
546 
547  return pixOctreeColorQuantGeneral(pixs, colors, ditherflag, 0.01, 0.01);
548 }
549 
550 
599 PIX *
601  l_int32 colors,
602  l_int32 ditherflag,
603  l_float32 validthresh,
604  l_float32 colorthresh)
605 {
606 l_int32 w, h, minside, factor, index, rval, gval, bval;
607 l_float32 scalefactor;
608 l_float32 pixfract; /* fraction neither near white nor black */
609 l_float32 colorfract; /* fraction with color of the pixfract population */
610 CQCELL ***cqcaa;
611 PIX *pixd, *pixsub;
612 PIXCMAP *cmap;
613 
614  if (!pixs)
615  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
616  if (pixGetDepth(pixs) != 32)
617  return (PIX *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
618  if (colors < 128 || colors > 240)
619  return (PIX *)ERROR_PTR("colors must be in [128, 240]", __func__, NULL);
620 
621  /* Determine if the image has sufficient color content for
622  * octree quantization, based on the input thresholds.
623  * If pixfract << 1, most pixels are close to black or white.
624  * If colorfract << 1, the pixels that are not near
625  * black or white have very little color.
626  * If with insufficient color, quantize with a grayscale colormap. */
627  pixGetDimensions(pixs, &w, &h, NULL);
628  if (validthresh > 0.0 && colorthresh > 0.0) {
629  minside = L_MIN(w, h);
630  factor = L_MAX(1, minside / 400);
631  pixColorFraction(pixs, 20, 244, 20, factor, &pixfract, &colorfract);
632  if (pixfract * colorfract < validthresh * colorthresh) {
633  L_INFO("\n Pixel fraction neither white nor black = %6.3f"
634  "\n Color fraction of those pixels = %6.3f"
635  "\n Quantizing to 8 bpp gray\n",
636  __func__, pixfract, colorfract);
637  return pixConvertTo8(pixs, 1);
638  }
639  } else {
640  L_INFO("\n Process in color by default\n", __func__);
641  }
642 
643  /* Conditionally subsample to speed up the first pass */
644  if (w > TreeGenWidth) {
645  scalefactor = (l_float32)TreeGenWidth / (l_float32)w;
646  pixsub = pixScaleBySampling(pixs, scalefactor, scalefactor);
647  } else {
648  pixsub = pixClone(pixs);
649  }
650 
651  /* Drop the number of requested colors if image is very small */
652  if (w < MinDitherSize && h < MinDitherSize)
653  colors = L_MIN(colors, 220);
654 
655  /* Make the pruned octree */
656  cqcaa = octreeGenerateAndPrune(pixsub, colors, CqReservedColors, &cmap);
657  if (!cqcaa) {
658  pixDestroy(&pixsub);
659  return (PIX *)ERROR_PTR("tree not made", __func__, NULL);
660  }
661 #if DEBUG_COLORQUANT
662  L_INFO(" Colors requested = %d\n", __func__, colors);
663  L_INFO(" Actual colors = %d\n", __func__, cmap->n);
664 #endif /* DEBUG_COLORQUANT */
665 
666  /* Do not dither if image is very small */
667  if (w < MinDitherSize && h < MinDitherSize && ditherflag == 1) {
668  L_INFO("Small image: dithering turned off\n", __func__);
669  ditherflag = 0;
670  }
671 
672  /* Traverse tree from root, looking for lowest cube
673  * that is a leaf, and set dest pix value to its
674  * colortable index */
675  if ((pixd = pixOctreeQuantizePixels(pixs, cqcaa, ditherflag)) == NULL) {
676  pixDestroy(&pixsub);
677  cqcellTreeDestroy(&cqcaa);
678  return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
679  }
680 
681  /* Attach colormap and copy res */
682  pixSetColormap(pixd, cmap);
683  pixCopyResolution(pixd, pixs);
684  pixCopyInputFormat(pixd, pixs);
685 
686  /* Force darkest color to black if each component <= 4 */
687  pixcmapGetRankIntensity(cmap, 0.0, &index);
688  pixcmapGetColor(cmap, index, &rval, &gval, &bval);
689  if (rval < 5 && gval < 5 && bval < 5)
690  pixcmapResetColor(cmap, index, 0, 0, 0);
691 
692  /* Force lightest color to white if each component >= 252 */
693  pixcmapGetRankIntensity(cmap, 1.0, &index);
694  pixcmapGetColor(cmap, index, &rval, &gval, &bval);
695  if (rval > 251 && gval > 251 && bval > 251)
696  pixcmapResetColor(cmap, index, 255, 255, 255);
697 
698  cqcellTreeDestroy(&cqcaa);
699  pixDestroy(&pixsub);
700  return pixd;
701 }
702 
703 
720 static CQCELL ***
722  l_int32 colors,
723  l_int32 reservedcolors,
724  PIXCMAP **pcmap)
725 {
726 l_int32 rval, gval, bval, cindex;
727 l_int32 level, ncells, octindex;
728 l_int32 w, h, wpls;
729 l_int32 i, j, isub;
730 l_int32 npix; /* number of remaining pixels to be assigned */
731 l_int32 ncolor; /* number of remaining color cells to be used */
732 l_int32 ppc; /* ave number of pixels left for each color cell */
733 l_int32 rv, gv, bv;
734 l_float32 thresholdFactor[] = {0.01f, 0.01f, 1.0f, 1.0f, 1.0f, 1.0f};
735 l_float32 thresh; /* factor of ppc for this level */
736 l_uint32 *datas, *lines;
737 l_uint32 *rtab, *gtab, *btab;
738 CQCELL ***cqcaa; /* one array for each octree level */
739 CQCELL **cqca, **cqcasub;
740 CQCELL *cqc, *cqcsub;
741 PIXCMAP *cmap;
742 NUMA *nat; /* accumulates levels for threshold cells */
743 NUMA *nar; /* accumulates levels for residual cells */
744 
745  if (!pixs)
746  return (CQCELL ***)ERROR_PTR("pixs not defined", __func__, NULL);
747  if (pixGetDepth(pixs) != 32)
748  return (CQCELL ***)ERROR_PTR("pixs must be 32 bpp", __func__, NULL);
749  if (colors < 128 || colors > 256)
750  return (CQCELL ***)ERROR_PTR("colors not in [128,256]", __func__, NULL);
751  if (!pcmap)
752  return (CQCELL ***)ERROR_PTR("&cmap not defined", __func__, NULL);
753 
754  if ((cqcaa = cqcellTreeCreate()) == NULL)
755  return (CQCELL ***)ERROR_PTR("cqcaa not made", __func__, NULL);
756 
757  /* Make the canonical index tables */
758  rtab = gtab = btab = NULL;
759  makeRGBToIndexTables(CqNLevels, &rtab, &gtab, &btab);
760 
761  /* Generate an 8 bpp cmap (max size 256) */
762  cmap = pixcmapCreate(8);
763  *pcmap = cmap;
764 
765  pixGetDimensions(pixs, &w, &h, NULL);
766  npix = w * h; /* initialize to all pixels */
767  ncolor = colors - reservedcolors - ExtraReservedColors;
768  ppc = npix / ncolor;
769  datas = pixGetData(pixs);
770  wpls = pixGetWpl(pixs);
771 
772  /* Accumulate the centers of each cluster at level CqNLevels */
773  ncells = 1 << (3 * CqNLevels);
774  cqca = cqcaa[CqNLevels];
775  for (i = 0; i < h; i++) {
776  lines = datas + i * wpls;
777  for (j = 0; j < w; j++) {
778  extractRGBValues(lines[j], &rval, &gval, &bval);
779  octindex = rtab[rval] | gtab[gval] | btab[bval];
780  cqc = cqca[octindex];
781  cqc->n++;
782  }
783  }
784 
785  /* Arrays for storing statistics */
786  nat = numaCreate(0);
787  nar = numaCreate(0);
788 
789  /* Prune back from the lowest level and generate the colormap */
790  for (level = CqNLevels - 1; level >= 2; level--) {
791  thresh = thresholdFactor[level];
792  cqca = cqcaa[level];
793  cqcasub = cqcaa[level + 1];
794  ncells = 1 << (3 * level);
795  for (i = 0; i < ncells; i++) { /* i is octindex at level */
796  cqc = cqca[i];
797  for (j = 0; j < 8; j++) { /* check all subnodes */
798  isub = 8 * i + j; /* isub is octindex at level+1 */
799  cqcsub = cqcasub[isub];
800  if (cqcsub->bleaf == 1) { /* already a leaf? */
801  cqc->nleaves++; /* count the subcube leaves */
802  continue;
803  }
804  if (cqcsub->n >= thresh * ppc) { /* make it a true leaf? */
805  cqcsub->bleaf = 1;
806  if (cmap->n < 256) {
807  cqcsub->index = cmap->n; /* assign the color index */
808  getRGBFromOctcube(isub, level + 1, &rv, &gv, &bv);
809  pixcmapAddColor(cmap, rv, gv, bv);
810 #if 1 /* save values */
811  cqcsub->rc = rv;
812  cqcsub->gc = gv;
813  cqcsub->bc = bv;
814 #endif
815  } else {
816  /* This doesn't seem to happen. Do something. */
817  L_ERROR("assigning pixels to wrong color\n", __func__);
818  pixcmapGetNearestIndex(cmap, 128, 128, 128, &cindex);
819  cqcsub->index = cindex; /* assign to the nearest */
820  pixcmapGetColor(cmap, cindex, &rval, &gval, &bval);
821  cqcsub->rc = rval;
822  cqcsub->gc = gval;
823  cqcsub->bc = bval;
824  }
825  cqc->nleaves++;
826  npix -= cqcsub->n;
827  ncolor--;
828  if (ncolor > 0)
829  ppc = npix / ncolor;
830  else if (ncolor + reservedcolors > 0)
831  ppc = npix / (ncolor + reservedcolors);
832  else
833  ppc = 1000000; /* make it big */
834  numaAddNumber(nat, level + 1);
835 
836 #if DEBUG_OCTCUBE_CMAP
837  lept_stderr("Exceeds threshold: colors used = %d, colors remaining = %d\n",
838  cmap->n, ncolor + reservedcolors);
839  lept_stderr(" cell with %d pixels, npix = %d, ppc = %d\n",
840  cqcsub->n, npix, ppc);
841  lept_stderr(" index = %d, level = %d, subindex = %d\n",
842  i, level, j);
843  lept_stderr(" rv = %d, gv = %d, bv = %d\n", rv, gv, bv);
844 #endif /* DEBUG_OCTCUBE_CMAP */
845 
846  }
847  }
848  if (cqc->nleaves > 0 || level == 2) { /* make the cube a leaf now */
849  cqc->bleaf = 1;
850  if (cqc->nleaves < 8) { /* residual CTE cube: acquire the
851  * remaining pixels */
852  for (j = 0; j < 8; j++) { /* check all subnodes */
853  isub = 8 * i + j;
854  cqcsub = cqcasub[isub];
855  if (cqcsub->bleaf == 0) /* absorb */
856  cqc->n += cqcsub->n;
857  }
858  if (cmap->n < 256) {
859  cqc->index = cmap->n; /* assign the color index */
860  getRGBFromOctcube(i, level, &rv, &gv, &bv);
861  pixcmapAddColor(cmap, rv, gv, bv);
862 #if 1 /* save values */
863  cqc->rc = rv;
864  cqc->gc = gv;
865  cqc->bc = bv;
866 #endif
867  } else {
868  L_WARNING("possibly assigned pixels to wrong color\n",
869  __func__);
870  /* This is very bad. It will only cause trouble
871  * with dithering, and we try to avoid it with
872  * ExtraReservedColors. */
873  pixcmapGetNearestIndex(cmap, rv, gv, bv, &cindex);
874  cqc->index = cindex; /* assign to the nearest */
875  pixcmapGetColor(cmap, cindex, &rval, &gval, &bval);
876  cqc->rc = rval;
877  cqc->gc = gval;
878  cqc->bc = bval;
879  }
880  npix -= cqc->n;
881  ncolor--;
882  if (ncolor > 0)
883  ppc = npix / ncolor;
884  else if (ncolor + reservedcolors > 0)
885  ppc = npix / (ncolor + reservedcolors);
886  else
887  ppc = 1000000; /* make it big */
888  numaAddNumber(nar, level);
889 
890 #if DEBUG_OCTCUBE_CMAP
891  lept_stderr("By remainder: colors used = %d, colors remaining = %d\n",
892  cmap->n, ncolor + reservedcolors);
893  lept_stderr(" cell with %d pixels, npix = %d, ppc = %d\n",
894  cqc->n, npix, ppc);
895  lept_stderr(" index = %d, level = %d\n", i, level);
896  lept_stderr(" rv = %d, gv = %d, bv = %d\n", rv, gv, bv);
897 #endif /* DEBUG_OCTCUBE_CMAP */
898 
899  }
900  } else { /* absorb all the subpixels but don't make it a leaf */
901  for (j = 0; j < 8; j++) { /* absorb from all subnodes */
902  isub = 8 * i + j;
903  cqcsub = cqcasub[isub];
904  cqc->n += cqcsub->n;
905  }
906  }
907  }
908  }
909 
910 #if PRINT_OCTCUBE_STATS
911 {
912 l_int32 tc[] = {0, 0, 0, 0, 0, 0, 0};
913 l_int32 rc[] = {0, 0, 0, 0, 0, 0, 0};
914 l_int32 nt, nr, ival;
915 
916  nt = numaGetCount(nat);
917  nr = numaGetCount(nar);
918  for (i = 0; i < nt; i++) {
919  numaGetIValue(nat, i, &ival);
920  tc[ival]++;
921  }
922  for (i = 0; i < nr; i++) {
923  numaGetIValue(nar, i, &ival);
924  rc[ival]++;
925  }
926  lept_stderr(" Threshold cells formed: %d\n", nt);
927  for (i = 1; i < CqNLevels + 1; i++)
928  lept_stderr(" level %d: %d\n", i, tc[i]);
929  lept_stderr("\n Residual cells formed: %d\n", nr);
930  for (i = 0; i < CqNLevels ; i++)
931  lept_stderr(" level %d: %d\n", i, rc[i]);
932 }
933 #endif /* PRINT_OCTCUBE_STATS */
934 
935  numaDestroy(&nat);
936  numaDestroy(&nar);
937  LEPT_FREE(rtab);
938  LEPT_FREE(gtab);
939  LEPT_FREE(btab);
940 
941  return cqcaa;
942 }
943 
944 
968 static PIX *
970  CQCELL ***cqcaa,
971  l_int32 ditherflag)
972 {
973 l_uint8 *bufu8r, *bufu8g, *bufu8b;
974 l_int32 rval, gval, bval;
975 l_int32 octindex, index;
976 l_int32 val1, val2, val3, dif;
977 l_int32 w, h, wpls, wpld, i, j, success;
978 l_int32 rc, gc, bc;
979 l_int32 *buf1r, *buf1g, *buf1b, *buf2r, *buf2g, *buf2b;
980 l_uint32 *rtab, *gtab, *btab;
981 l_uint32 *datas, *datad, *lines, *lined;
982 PIX *pixd;
983 
984  if (!pixs)
985  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
986  if (pixGetDepth(pixs) != 32)
987  return (PIX *)ERROR_PTR("pixs must be 32 bpp", __func__, NULL);
988  if (!cqcaa)
989  return (PIX *)ERROR_PTR("cqcaa not defined", __func__, NULL);
990 
991  /* Make output 8 bpp palette image */
992  pixGetDimensions(pixs, &w, &h, NULL);
993  datas = pixGetData(pixs);
994  wpls = pixGetWpl(pixs);
995  if ((pixd = pixCreate(w, h, 8)) == NULL)
996  return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
997  pixCopyResolution(pixd, pixs);
998  pixCopyInputFormat(pixd, pixs);
999  datad = pixGetData(pixd);
1000  wpld = pixGetWpl(pixd);
1001 
1002  /* Make the canonical index tables */
1003  rtab = gtab = btab = NULL;
1004  makeRGBToIndexTables(CqNLevels, &rtab, &gtab, &btab);
1005 
1006  /* Traverse tree from root, looking for lowest cube
1007  * that is a leaf, and set dest pix to its
1008  * colortable index value. The results are far
1009  * better when dithering to get a more accurate
1010  * average color. */
1011  if (ditherflag == 0) { /* no dithering */
1012  for (i = 0; i < h; i++) {
1013  lines = datas + i * wpls;
1014  lined = datad + i * wpld;
1015  for (j = 0; j < w; j++) {
1016  extractRGBValues(lines[j], &rval, &gval, &bval);
1017  octindex = rtab[rval] | gtab[gval] | btab[bval];
1018  octreeFindColorCell(octindex, cqcaa, &index, &rc, &gc, &bc);
1019  SET_DATA_BYTE(lined, j, index);
1020  }
1021  }
1022  } else { /* Dither */
1023  success = TRUE;
1024  bufu8r = bufu8g = bufu8b = NULL;
1025  buf1r = buf1g = buf1b = buf2r = buf2g = buf2b = NULL;
1026  bufu8r = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1027  bufu8g = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1028  bufu8b = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1029  buf1r = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1030  buf1g = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1031  buf1b = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1032  buf2r = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1033  buf2g = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1034  buf2b = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1035  if (!bufu8r || !bufu8g || !bufu8b || !buf1r || !buf1g ||
1036  !buf1b || !buf2r || !buf2g || !buf2b) {
1037  L_ERROR("buffer not made\n", __func__);
1038  success = FALSE;
1039  goto buffer_cleanup;
1040  }
1041 
1042  /* Start by priming buf2; line 1 is above line 2 */
1043  pixGetRGBLine(pixs, 0, bufu8r, bufu8g, bufu8b);
1044  for (j = 0; j < w; j++) {
1045  buf2r[j] = 64 * bufu8r[j];
1046  buf2g[j] = 64 * bufu8g[j];
1047  buf2b[j] = 64 * bufu8b[j];
1048  }
1049 
1050  for (i = 0; i < h - 1; i++) {
1051  /* Swap data 2 --> 1, and read in new line 2 */
1052  memcpy(buf1r, buf2r, 4 * w);
1053  memcpy(buf1g, buf2g, 4 * w);
1054  memcpy(buf1b, buf2b, 4 * w);
1055  pixGetRGBLine(pixs, i + 1, bufu8r, bufu8g, bufu8b);
1056  for (j = 0; j < w; j++) {
1057  buf2r[j] = 64 * bufu8r[j];
1058  buf2g[j] = 64 * bufu8g[j];
1059  buf2b[j] = 64 * bufu8b[j];
1060  }
1061 
1062  /* Dither */
1063  lined = datad + i * wpld;
1064  for (j = 0; j < w - 1; j++) {
1065  rval = buf1r[j] / 64;
1066  gval = buf1g[j] / 64;
1067  bval = buf1b[j] / 64;
1068  octindex = rtab[rval] | gtab[gval] | btab[bval];
1069  octreeFindColorCell(octindex, cqcaa, &index, &rc, &gc, &bc);
1070  SET_DATA_BYTE(lined, j, index);
1071 
1072  dif = buf1r[j] / 8 - 8 * rc;
1073  if (dif != 0) {
1074  val1 = buf1r[j + 1] + 3 * dif;
1075  val2 = buf2r[j] + 3 * dif;
1076  val3 = buf2r[j + 1] + 2 * dif;
1077  if (dif > 0) {
1078  buf1r[j + 1] = L_MIN(16383, val1);
1079  buf2r[j] = L_MIN(16383, val2);
1080  buf2r[j + 1] = L_MIN(16383, val3);
1081  } else {
1082  buf1r[j + 1] = L_MAX(0, val1);
1083  buf2r[j] = L_MAX(0, val2);
1084  buf2r[j + 1] = L_MAX(0, val3);
1085  }
1086  }
1087 
1088  dif = buf1g[j] / 8 - 8 * gc;
1089  if (dif != 0) {
1090  val1 = buf1g[j + 1] + 3 * dif;
1091  val2 = buf2g[j] + 3 * dif;
1092  val3 = buf2g[j + 1] + 2 * dif;
1093  if (dif > 0) {
1094  buf1g[j + 1] = L_MIN(16383, val1);
1095  buf2g[j] = L_MIN(16383, val2);
1096  buf2g[j + 1] = L_MIN(16383, val3);
1097  } else {
1098  buf1g[j + 1] = L_MAX(0, val1);
1099  buf2g[j] = L_MAX(0, val2);
1100  buf2g[j + 1] = L_MAX(0, val3);
1101  }
1102  }
1103 
1104  dif = buf1b[j] / 8 - 8 * bc;
1105  if (dif != 0) {
1106  val1 = buf1b[j + 1] + 3 * dif;
1107  val2 = buf2b[j] + 3 * dif;
1108  val3 = buf2b[j + 1] + 2 * dif;
1109  if (dif > 0) {
1110  buf1b[j + 1] = L_MIN(16383, val1);
1111  buf2b[j] = L_MIN(16383, val2);
1112  buf2b[j + 1] = L_MIN(16383, val3);
1113  } else {
1114  buf1b[j + 1] = L_MAX(0, val1);
1115  buf2b[j] = L_MAX(0, val2);
1116  buf2b[j + 1] = L_MAX(0, val3);
1117  }
1118  }
1119  }
1120 
1121  /* Get last pixel in row; no downward propagation */
1122  rval = buf1r[w - 1] / 64;
1123  gval = buf1g[w - 1] / 64;
1124  bval = buf1b[w - 1] / 64;
1125  octindex = rtab[rval] | gtab[gval] | btab[bval];
1126  octreeFindColorCell(octindex, cqcaa, &index, &rc, &gc, &bc);
1127  SET_DATA_BYTE(lined, w - 1, index);
1128  }
1129 
1130  /* Get last row of pixels; no leftward propagation */
1131  lined = datad + (h - 1) * wpld;
1132  for (j = 0; j < w; j++) {
1133  rval = buf2r[j] / 64;
1134  gval = buf2g[j] / 64;
1135  bval = buf2b[j] / 64;
1136  octindex = rtab[rval] | gtab[gval] | btab[bval];
1137  octreeFindColorCell(octindex, cqcaa, &index, &rc, &gc, &bc);
1138  SET_DATA_BYTE(lined, j, index);
1139  }
1140 
1141 buffer_cleanup:
1142  LEPT_FREE(bufu8r);
1143  LEPT_FREE(bufu8g);
1144  LEPT_FREE(bufu8b);
1145  LEPT_FREE(buf1r);
1146  LEPT_FREE(buf1g);
1147  LEPT_FREE(buf1b);
1148  LEPT_FREE(buf2r);
1149  LEPT_FREE(buf2g);
1150  LEPT_FREE(buf2b);
1151  if (!success) pixDestroy(&pixd);
1152  }
1153 
1154  LEPT_FREE(rtab);
1155  LEPT_FREE(gtab);
1156  LEPT_FREE(btab);
1157  return pixd;
1158 }
1159 
1160 
1182 static l_int32
1183 octreeFindColorCell(l_int32 octindex,
1184  CQCELL ***cqcaa,
1185  l_int32 *pindex,
1186  l_int32 *prval,
1187  l_int32 *pgval,
1188  l_int32 *pbval)
1189 {
1190 l_int32 level;
1191 l_int32 baseindex, subindex;
1192 CQCELL *cqc, *cqcsub;
1193 
1194  /* Use rgb values stored in the cubes; a little faster */
1195  for (level = 2; level < CqNLevels; level++) {
1196  getOctcubeIndices(octindex, level, &baseindex, &subindex);
1197  cqc = cqcaa[level][baseindex];
1198  cqcsub = cqcaa[level + 1][subindex];
1199  if (cqcsub->bleaf == 0) { /* use cell at level above */
1200  *pindex = cqc->index;
1201  *prval = cqc->rc;
1202  *pgval = cqc->gc;
1203  *pbval = cqc->bc;
1204  break;
1205  } else if (level == CqNLevels - 1) { /* reached the bottom */
1206  *pindex = cqcsub->index;
1207  *prval = cqcsub->rc;
1208  *pgval = cqcsub->gc;
1209  *pbval = cqcsub->bc;
1210  break;
1211  }
1212  }
1213 
1214 #if 0
1215  /* Generate rgb values for each cube on the fly; slower */
1216  for (level = 2; level < CqNLevels; level++) {
1217  l_int32 rv, gv, bv;
1218  getOctcubeIndices(octindex, level, &baseindex, &subindex);
1219  cqc = cqcaa[level][baseindex];
1220  cqcsub = cqcaa[level + 1][subindex];
1221  if (cqcsub->bleaf == 0) { /* use cell at level above */
1222  getRGBFromOctcube(baseindex, level, &rv, &gv, &bv);
1223  *pindex = cqc->index;
1224  *prval = rv;
1225  *pgval = gv;
1226  *pbval = bv;
1227  break;
1228  } else if (level == CqNLevels - 1) { /* reached the bottom */
1229  getRGBFromOctcube(subindex, level + 1, &rv, &gv, &bv);
1230  *pindex = cqcsub->index;
1231  *prval = rv;
1232  *pgval = gv;
1233  *pbval = bv;
1234  break;
1235  }
1236  }
1237 #endif
1238 
1239  return 0;
1240 }
1241 
1242 
1243 
1244 /*------------------------------------------------------------------*
1245  * Helper cqcell functions *
1246  *------------------------------------------------------------------*/
1252 static CQCELL ***
1254 {
1255 l_int32 level, ncells, i;
1256 CQCELL ***cqcaa;
1257 CQCELL **cqca; /* one array for each octree level */
1258 
1259  /* Make array of accumulation cell arrays from levels 1 to 5 */
1260  cqcaa = (CQCELL ***)LEPT_CALLOC(CqNLevels + 1, sizeof(CQCELL **));
1261  for (level = 0; level <= CqNLevels; level++) {
1262  ncells = 1 << (3 * level);
1263  cqca = (CQCELL **)LEPT_CALLOC(ncells, sizeof(CQCELL *));
1264  cqcaa[level] = cqca;
1265  for (i = 0; i < ncells; i++) {
1266  cqca[i] = (CQCELL *)LEPT_CALLOC(1, sizeof(CQCELL));
1267  }
1268  }
1269 
1270  return cqcaa;
1271 }
1272 
1273 
1279 static void
1281 {
1282 l_int32 level, ncells, i;
1283 CQCELL ***cqcaa;
1284 CQCELL **cqca;
1285 
1286  if (pcqcaa == NULL) {
1287  L_WARNING("ptr address is NULL\n", __func__);
1288  return;
1289  }
1290 
1291  if ((cqcaa = *pcqcaa) == NULL)
1292  return;
1293 
1294  for (level = 0; level <= CqNLevels; level++) {
1295  cqca = cqcaa[level];
1296  ncells = 1 << (3 * level);
1297  for (i = 0; i < ncells; i++)
1298  LEPT_FREE(cqca[i]);
1299  LEPT_FREE(cqca);
1300  }
1301  LEPT_FREE(cqcaa);
1302  *pcqcaa = NULL;
1303 
1304  return;
1305 }
1306 
1307 
1308 
1309 /*------------------------------------------------------------------*
1310  * Helper index functions *
1311  *------------------------------------------------------------------*/
1341 l_ok
1342 makeRGBToIndexTables(l_int32 cqlevels,
1343  l_uint32 **prtab,
1344  l_uint32 **pgtab,
1345  l_uint32 **pbtab)
1346 {
1347 l_int32 i;
1348 l_uint32 *rtab, *gtab, *btab;
1349 
1350  if (cqlevels < 1 || cqlevels > 6)
1351  return ERROR_INT("cqlevels must be in {1,...6}", __func__, 1);
1352  if (!prtab || !pgtab || !pbtab)
1353  return ERROR_INT("not all &tabs defined", __func__, 1);
1354 
1355  rtab = (l_uint32 *)LEPT_CALLOC(256, sizeof(l_uint32));
1356  gtab = (l_uint32 *)LEPT_CALLOC(256, sizeof(l_uint32));
1357  btab = (l_uint32 *)LEPT_CALLOC(256, sizeof(l_uint32));
1358  if (!rtab || !gtab || !btab)
1359  return ERROR_INT("calloc fail for tab", __func__, 1);
1360  *prtab = rtab;
1361  *pgtab = gtab;
1362  *pbtab = btab;
1363 
1364  switch (cqlevels)
1365  {
1366  case 1:
1367  for (i = 0; i < 256; i++) {
1368  rtab[i] = (i >> 5) & 0x0004;
1369  gtab[i] = (i >> 6) & 0x0002;
1370  btab[i] = (i >> 7);
1371  }
1372  break;
1373  case 2:
1374  for (i = 0; i < 256; i++) {
1375  rtab[i] = ((i >> 2) & 0x0020) | ((i >> 4) & 0x0004);
1376  gtab[i] = ((i >> 3) & 0x0010) | ((i >> 5) & 0x0002);
1377  btab[i] = ((i >> 4) & 0x0008) | ((i >> 6) & 0x0001);
1378  }
1379  break;
1380  case 3:
1381  for (i = 0; i < 256; i++) {
1382  rtab[i] = ((i << 1) & 0x0100) | ((i >> 1) & 0x0020) |
1383  ((i >> 3) & 0x0004);
1384  gtab[i] = (i & 0x0080) | ((i >> 2) & 0x0010) |
1385  ((i >> 4) & 0x0002);
1386  btab[i] = ((i >> 1) & 0x0040) | ((i >> 3) & 0x0008) |
1387  ((i >> 5) & 0x0001);
1388  }
1389  break;
1390  case 4:
1391  for (i = 0; i < 256; i++) {
1392  rtab[i] = ((i << 4) & 0x0800) | ((i << 2) & 0x0100) |
1393  (i & 0x0020) | ((i >> 2) & 0x0004);
1394  gtab[i] = ((i << 3) & 0x0400) | ((i << 1) & 0x0080) |
1395  ((i >> 1) & 0x0010) | ((i >> 3) & 0x0002);
1396  btab[i] = ((i << 2) & 0x0200) | (i & 0x0040) |
1397  ((i >> 2) & 0x0008) | ((i >> 4) & 0x0001);
1398  }
1399  break;
1400  case 5:
1401  for (i = 0; i < 256; i++) {
1402  rtab[i] = ((i << 7) & 0x4000) | ((i << 5) & 0x0800) |
1403  ((i << 3) & 0x0100) | ((i << 1) & 0x0020) |
1404  ((i >> 1) & 0x0004);
1405  gtab[i] = ((i << 6) & 0x2000) | ((i << 4) & 0x0400) |
1406  ((i << 2) & 0x0080) | (i & 0x0010) |
1407  ((i >> 2) & 0x0002);
1408  btab[i] = ((i << 5) & 0x1000) | ((i << 3) & 0x0200) |
1409  ((i << 1) & 0x0040) | ((i >> 1) & 0x0008) |
1410  ((i >> 3) & 0x0001);
1411  }
1412  break;
1413  case 6:
1414  for (i = 0; i < 256; i++) {
1415  rtab[i] = ((i << 10) & 0x20000) | ((i << 8) & 0x4000) |
1416  ((i << 6) & 0x0800) | ((i << 4) & 0x0100) |
1417  ((i << 2) & 0x0020) | (i & 0x0004);
1418  gtab[i] = ((i << 9) & 0x10000) | ((i << 7) & 0x2000) |
1419  ((i << 5) & 0x0400) | ((i << 3) & 0x0080) |
1420  ((i << 1) & 0x0010) | ((i >> 1) & 0x0002);
1421  btab[i] = ((i << 8) & 0x8000) | ((i << 6) & 0x1000) |
1422  ((i << 4) & 0x0200) | ((i << 2) & 0x0040) |
1423  (i & 0x0008) | ((i >> 2) & 0x0001);
1424  }
1425  break;
1426  default:
1427  ERROR_INT("cqlevels not in [1...6]", __func__, 1);
1428  break;
1429  }
1430 
1431  return 0;
1432 }
1433 
1434 
1448 void
1450  l_int32 gval,
1451  l_int32 bval,
1452  l_uint32 *rtab,
1453  l_uint32 *gtab,
1454  l_uint32 *btab,
1455  l_uint32 *pindex)
1456 {
1457  *pindex = rtab[rval] | gtab[gval] | btab[bval];
1458  return;
1459 }
1460 
1461 
1494 static void
1495 getRGBFromOctcube(l_int32 cubeindex,
1496  l_int32 level,
1497  l_int32 *prval,
1498  l_int32 *pgval,
1499  l_int32 *pbval)
1500 {
1501 l_int32 rgbindex;
1502 
1503  /* Bring to format in 21 bits: (r7 g7 b7 r6 g6 b6 ...) */
1504  /* This is valid for levels from 0 to 6 */
1505  rgbindex = cubeindex << (3 * (7 - level)); /* upper corner of cube */
1506  rgbindex |= (0x7 << (3 * (6 - level))); /* index to center of cube */
1507 
1508  /* Extract separate pieces */
1509  *prval = ((rgbindex >> 13) & 0x80) |
1510  ((rgbindex >> 11) & 0x40) |
1511  ((rgbindex >> 9) & 0x20) |
1512  ((rgbindex >> 7) & 0x10) |
1513  ((rgbindex >> 5) & 0x08) |
1514  ((rgbindex >> 3) & 0x04) |
1515  ((rgbindex >> 1) & 0x02);
1516  *pgval = ((rgbindex >> 12) & 0x80) |
1517  ((rgbindex >> 10) & 0x40) |
1518  ((rgbindex >> 8) & 0x20) |
1519  ((rgbindex >> 6) & 0x10) |
1520  ((rgbindex >> 4) & 0x08) |
1521  ((rgbindex >> 2) & 0x04) |
1522  (rgbindex & 0x02);
1523  *pbval = ((rgbindex >> 11) & 0x80) |
1524  ((rgbindex >> 9) & 0x40) |
1525  ((rgbindex >> 7) & 0x20) |
1526  ((rgbindex >> 5) & 0x10) |
1527  ((rgbindex >> 3) & 0x08) |
1528  ((rgbindex >> 1) & 0x04) |
1529  ((rgbindex << 1) & 0x02);
1530 
1531  return;
1532 }
1533 
1534 
1571 static l_int32
1572 getOctcubeIndices(l_int32 rgbindex,
1573  l_int32 level,
1574  l_int32 *pbindex,
1575  l_int32 *psindex)
1576 {
1577  if (level < 0 || level > CqNLevels - 1)
1578  return ERROR_INT("level must be in e.g., [0 ... 5]", __func__, 1);
1579  if (!pbindex)
1580  return ERROR_INT("&bindex not defined", __func__, 1);
1581  if (!psindex)
1582  return ERROR_INT("&sindex not defined", __func__, 1);
1583 
1584  *pbindex = rgbindex >> (3 * (CqNLevels - level));
1585  *psindex = rgbindex >> (3 * (CqNLevels - 1 - level));
1586  return 0;
1587 }
1588 
1589 
1603 static l_int32
1604 octcubeGetCount(l_int32 level,
1605  l_int32 *psize)
1606 {
1607  if (!psize)
1608  return ERROR_INT("&size not defined", __func__, 1);
1609  if (level < 1 || level > 6)
1610  return ERROR_INT("invalid level", __func__, 1);
1611 
1612  *psize = 1 << (3 * level);
1613  return 0;
1614 }
1615 
1616 
1617 /*---------------------------------------------------------------------------*
1618  * Adaptive octree quantization based on population at a fixed level *
1619  *---------------------------------------------------------------------------*/
1675 PIX *
1677  l_int32 level,
1678  l_int32 ditherflag)
1679 {
1680 l_int32 w, h, wpls, wpld, i, j, depth, size, ncolors, index;
1681 l_int32 rval, gval, bval;
1682 l_int32 *rarray, *garray, *barray, *narray, *iarray;
1683 l_uint32 octindex, octindex2;
1684 l_uint32 *rtab, *gtab, *btab, *rtab2, *gtab2, *btab2;
1685 l_uint32 *lines, *lined, *datas, *datad;
1686 L_OCTCUBE_POP *opop;
1687 L_HEAP *lh;
1688 PIX *pixd;
1689 PIXCMAP *cmap;
1690 
1691  if (!pixs)
1692  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
1693  if (pixGetDepth(pixs) != 32)
1694  return (PIX *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
1695  if (level == 0) level = 4;
1696  if (level < 3 || level > 4)
1697  return (PIX *)ERROR_PTR("level not in {3,4}", __func__, NULL);
1698 
1699  /* Do not dither if image is very small */
1700  pixGetDimensions(pixs, &w, &h, NULL);
1701  if (w < MinDitherSize && h < MinDitherSize && ditherflag == 1) {
1702  L_INFO("Small image: dithering turned off\n", __func__);
1703  ditherflag = 0;
1704  }
1705 
1706  if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
1707  return (PIX *)ERROR_PTR("size not returned", __func__, NULL);
1708  rtab = gtab = btab = NULL;
1709  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
1710 
1711  pixd = NULL;
1712  narray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
1713  rarray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
1714  garray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
1715  barray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
1716  if (!narray || !rarray || !garray || !barray)
1717  goto array_cleanup;
1718 
1719  /* Place the pixels in octcube leaves. */
1720  datas = pixGetData(pixs);
1721  wpls = pixGetWpl(pixs);
1722  for (i = 0; i < h; i++) {
1723  lines = datas + i * wpls;
1724  for (j = 0; j < w; j++) {
1725  extractRGBValues(lines[j], &rval, &gval, &bval);
1726  octindex = rtab[rval] | gtab[gval] | btab[bval];
1727  narray[octindex]++;
1728  rarray[octindex] += rval;
1729  garray[octindex] += gval;
1730  barray[octindex] += bval;
1731  }
1732  }
1733 
1734  /* Find the number of different colors */
1735  for (i = 0, ncolors = 0; i < size; i++) {
1736  if (narray[i] > 0)
1737  ncolors++;
1738  }
1739  if (ncolors <= 4)
1740  depth = 2;
1741  else if (ncolors <= 16)
1742  depth = 4;
1743  else
1744  depth = 8;
1745  pixd = pixCreate(w, h, depth);
1746  datad = pixGetData(pixd);
1747  wpld = pixGetWpl(pixd);
1748  pixCopyResolution(pixd, pixs);
1749  pixCopyInputFormat(pixd, pixs);
1750  cmap = pixcmapCreate(depth);
1751  pixSetColormap(pixd, cmap);
1752 
1753  /* Average the colors in each octcube leaf. */
1754  for (i = 0; i < size; i++) {
1755  if (narray[i] > 0) {
1756  rarray[i] /= narray[i];
1757  garray[i] /= narray[i];
1758  barray[i] /= narray[i];
1759  }
1760  }
1761 
1762  /* If ncolors <= 256, finish immediately. Do not dither.
1763  * Re-use narray to hold the colormap index + 1 */
1764  if (ncolors <= 256) {
1765  for (i = 0, index = 0; i < size; i++) {
1766  if (narray[i] > 0) {
1767  pixcmapAddColor(cmap, rarray[i], garray[i], barray[i]);
1768  narray[i] = index + 1; /* to avoid storing 0 */
1769  index++;
1770  }
1771  }
1772 
1773  /* Set the cmap indices for each pixel */
1774  for (i = 0; i < h; i++) {
1775  lines = datas + i * wpls;
1776  lined = datad + i * wpld;
1777  for (j = 0; j < w; j++) {
1778  extractRGBValues(lines[j], &rval, &gval, &bval);
1779  octindex = rtab[rval] | gtab[gval] | btab[bval];
1780  switch (depth)
1781  {
1782  case 8:
1783  SET_DATA_BYTE(lined, j, narray[octindex] - 1);
1784  break;
1785  case 4:
1786  SET_DATA_QBIT(lined, j, narray[octindex] - 1);
1787  break;
1788  case 2:
1789  SET_DATA_DIBIT(lined, j, narray[octindex] - 1);
1790  break;
1791  default:
1792  L_WARNING("shouldn't get here\n", __func__);
1793  }
1794  }
1795  }
1796  goto array_cleanup;
1797  }
1798 
1799  /* More complicated. Sort by decreasing population */
1800  lh = lheapCreate(500, L_SORT_DECREASING);
1801  for (i = 0; i < size; i++) {
1802  if (narray[i] > 0) {
1803  opop = (L_OCTCUBE_POP *)LEPT_CALLOC(1, sizeof(L_OCTCUBE_POP));
1804  opop->npix = (l_float32)narray[i];
1805  opop->index = i;
1806  opop->rval = rarray[i];
1807  opop->gval = garray[i];
1808  opop->bval = barray[i];
1809  lheapAdd(lh, opop);
1810  }
1811  }
1812 
1813  /* Take the top 192. These will form the first 192 colors
1814  * in the cmap. iarray[i] holds the index into the cmap. */
1815  iarray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
1816  for (i = 0; i < 192; i++) {
1817  opop = (L_OCTCUBE_POP*)lheapRemove(lh);
1818  if (!opop) break;
1819  pixcmapAddColor(cmap, opop->rval, opop->gval, opop->bval);
1820  iarray[opop->index] = i + 1; /* +1 to avoid storing 0 */
1821 
1822 #if DEBUG_POP
1823  lept_stderr("i = %d, n = %6.0f, (r,g,b) = (%d %d %d)\n",
1824  i, opop->npix, opop->rval, opop->gval, opop->bval);
1825 #endif /* DEBUG_POP */
1826 
1827  LEPT_FREE(opop);
1828  }
1829 
1830  /* Make the octindex tables for level 2, and reuse rarray, etc. */
1831  rtab2 = gtab2 = btab2 = NULL;
1832  makeRGBToIndexTables(2, &rtab2, &gtab2, &btab2);
1833  for (i = 0; i < 64; i++) {
1834  narray[i] = 0;
1835  rarray[i] = 0;
1836  garray[i] = 0;
1837  barray[i] = 0;
1838  }
1839 
1840  /* Take the rest of the occupied octcubes, assigning the pixels
1841  * to these new colormap indices. iarray[] is addressed
1842  * by %level octcube indices, and it now holds the
1843  * colormap indices for all pixels in pixs. */
1844  for (i = 192; i < size; i++) {
1845  opop = (L_OCTCUBE_POP*)lheapRemove(lh);
1846  if (!opop) break;
1847  rval = opop->rval;
1848  gval = opop->gval;
1849  bval = opop->bval;
1850  octindex2 = rtab2[rval] | gtab2[gval] | btab2[bval];
1851  narray[octindex2] += (l_int32)opop->npix;
1852  rarray[octindex2] += (l_int32)opop->npix * rval;
1853  garray[octindex2] += (l_int32)opop->npix * gval;
1854  barray[octindex2] += (l_int32)opop->npix * bval;
1855  iarray[opop->index] = 192 + octindex2 + 1; /* +1 to avoid storing 0 */
1856  LEPT_FREE(opop);
1857  }
1858  lheapDestroy(&lh, TRUE);
1859 
1860  /* To span the full color space, which is necessary for dithering,
1861  * set each iarray element whose value is still 0 at the input
1862  * level octcube leaves (because there were no pixels in those
1863  * octcubes) to the colormap index corresponding to its level 2
1864  * octcube. */
1865  if (ditherflag) {
1866  for (i = 0; i < size; i++) {
1867  if (iarray[i] == 0) {
1868  getRGBFromOctcube(i, level, &rval, &gval, &bval);
1869  octindex2 = rtab2[rval] | gtab2[gval] | btab2[bval];
1870  iarray[i] = 192 + octindex2 + 1;
1871  }
1872  }
1873  }
1874  LEPT_FREE(rtab2);
1875  LEPT_FREE(gtab2);
1876  LEPT_FREE(btab2);
1877 
1878  /* Average the colors from the residuals in each level 2 octcube,
1879  * and add these 64 values to the colormap. */
1880  for (i = 0; i < 64; i++) {
1881  if (narray[i] > 0) {
1882  rarray[i] /= narray[i];
1883  garray[i] /= narray[i];
1884  barray[i] /= narray[i];
1885  } else { /* no pixels in this octcube; use center value */
1886  getRGBFromOctcube(i, 2, &rarray[i], &garray[i], &barray[i]);
1887  }
1888  pixcmapAddColor(cmap, rarray[i], garray[i], barray[i]);
1889  }
1890 
1891  /* Set the cmap indices for each pixel. Subtract 1 from
1892  * the value in iarray[] because we added 1 earlier. */
1893  if (ditherflag == 0) {
1894  for (i = 0; i < h; i++) {
1895  lines = datas + i * wpls;
1896  lined = datad + i * wpld;
1897  for (j = 0; j < w; j++) {
1898  extractRGBValues(lines[j], &rval, &gval, &bval);
1899  octindex = rtab[rval] | gtab[gval] | btab[bval];
1900  SET_DATA_BYTE(lined, j, iarray[octindex] - 1);
1901  }
1902  }
1903  } else { /* dither */
1904  pixDitherOctindexWithCmap(pixs, pixd, rtab, gtab, btab,
1905  iarray, POP_DIF_CAP);
1906  }
1907 
1908 #if DEBUG_POP
1909  for (i = 0; i < size / 16; i++) {
1910  l_int32 j;
1911  for (j = 0; j < 16; j++)
1912  lept_stderr("%d ", iarray[16 * i + j]);
1913  lept_stderr("\n");
1914  }
1915 #endif /* DEBUG_POP */
1916 
1917  LEPT_FREE(iarray);
1918 
1919 array_cleanup:
1920  LEPT_FREE(narray);
1921  LEPT_FREE(rarray);
1922  LEPT_FREE(garray);
1923  LEPT_FREE(barray);
1924  LEPT_FREE(rtab);
1925  LEPT_FREE(gtab);
1926  LEPT_FREE(btab);
1927 
1928  return pixd;
1929 }
1930 
1931 
1965 static l_int32
1967  PIX *pixd,
1968  l_uint32 *rtab,
1969  l_uint32 *gtab,
1970  l_uint32 *btab,
1971  l_int32 *indexmap,
1972  l_int32 difcap)
1973 {
1974 l_uint8 *bufu8r, *bufu8g, *bufu8b;
1975 l_int32 i, j, w, h, wpld, octindex, cmapindex, success;
1976 l_int32 rval, gval, bval, rc, gc, bc;
1977 l_int32 dif, val1, val2, val3;
1978 l_int32 *buf1r, *buf1g, *buf1b, *buf2r, *buf2g, *buf2b;
1979 l_uint32 *datad, *lined;
1980 PIXCMAP *cmap;
1981 
1982  if (!pixs || pixGetDepth(pixs) != 32)
1983  return ERROR_INT("pixs undefined or not 32 bpp", __func__, 1);
1984  if (!pixd || pixGetDepth(pixd) != 8)
1985  return ERROR_INT("pixd undefined or not 8 bpp", __func__, 1);
1986  if ((cmap = pixGetColormap(pixd)) == NULL)
1987  return ERROR_INT("pixd not cmapped", __func__, 1);
1988  if (!rtab || !gtab || !btab || !indexmap)
1989  return ERROR_INT("not all 4 tables defined", __func__, 1);
1990  pixGetDimensions(pixs, &w, &h, NULL);
1991  if (pixGetWidth(pixd) != w || pixGetHeight(pixd) != h)
1992  return ERROR_INT("pixs and pixd not same size", __func__, 1);
1993 
1994  success = TRUE;
1995  bufu8r = bufu8g = bufu8b = NULL;
1996  buf1r = buf1g = buf1b = buf2r = buf2g = buf2b = NULL;
1997  bufu8r = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1998  bufu8g = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1999  bufu8b = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
2000  buf1r = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
2001  buf1g = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
2002  buf1b = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
2003  buf2r = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
2004  buf2g = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
2005  buf2b = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
2006  if (!bufu8r || !bufu8g || !bufu8b || !buf1r || !buf1g ||
2007  !buf1b || !buf2r || !buf2g || !buf2b) {
2008  L_ERROR("buffer not made\n", __func__);
2009  success = FALSE;
2010  goto buffer_cleanup;
2011  }
2012 
2013  /* Start by priming buf2; line 1 is above line 2 */
2014  pixGetRGBLine(pixs, 0, bufu8r, bufu8g, bufu8b);
2015  for (j = 0; j < w; j++) {
2016  buf2r[j] = 64 * bufu8r[j];
2017  buf2g[j] = 64 * bufu8g[j];
2018  buf2b[j] = 64 * bufu8b[j];
2019  }
2020 
2021  datad = pixGetData(pixd);
2022  wpld = pixGetWpl(pixd);
2023  for (i = 0; i < h - 1; i++) {
2024  /* Swap data 2 --> 1, and read in new line 2 */
2025  memcpy(buf1r, buf2r, 4 * w);
2026  memcpy(buf1g, buf2g, 4 * w);
2027  memcpy(buf1b, buf2b, 4 * w);
2028  pixGetRGBLine(pixs, i + 1, bufu8r, bufu8g, bufu8b);
2029  for (j = 0; j < w; j++) {
2030  buf2r[j] = 64 * bufu8r[j];
2031  buf2g[j] = 64 * bufu8g[j];
2032  buf2b[j] = 64 * bufu8b[j];
2033  }
2034 
2035  /* Dither */
2036  lined = datad + i * wpld;
2037  for (j = 0; j < w - 1; j++) {
2038  rval = buf1r[j] / 64;
2039  gval = buf1g[j] / 64;
2040  bval = buf1b[j] / 64;
2041  octindex = rtab[rval] | gtab[gval] | btab[bval];
2042  cmapindex = indexmap[octindex] - 1;
2043  SET_DATA_BYTE(lined, j, cmapindex);
2044  pixcmapGetColor(cmap, cmapindex, &rc, &gc, &bc);
2045 
2046  dif = buf1r[j] / 8 - 8 * rc;
2047  if (difcap > 0) {
2048  if (dif > difcap) dif = difcap;
2049  if (dif < -difcap) dif = -difcap;
2050  }
2051  if (dif != 0) {
2052  val1 = buf1r[j + 1] + 3 * dif;
2053  val2 = buf2r[j] + 3 * dif;
2054  val3 = buf2r[j + 1] + 2 * dif;
2055  if (dif > 0) {
2056  buf1r[j + 1] = L_MIN(16383, val1);
2057  buf2r[j] = L_MIN(16383, val2);
2058  buf2r[j + 1] = L_MIN(16383, val3);
2059  } else {
2060  buf1r[j + 1] = L_MAX(0, val1);
2061  buf2r[j] = L_MAX(0, val2);
2062  buf2r[j + 1] = L_MAX(0, val3);
2063  }
2064  }
2065 
2066  dif = buf1g[j] / 8 - 8 * gc;
2067  if (difcap > 0) {
2068  if (dif > difcap) dif = difcap;
2069  if (dif < -difcap) dif = -difcap;
2070  }
2071  if (dif != 0) {
2072  val1 = buf1g[j + 1] + 3 * dif;
2073  val2 = buf2g[j] + 3 * dif;
2074  val3 = buf2g[j + 1] + 2 * dif;
2075  if (dif > 0) {
2076  buf1g[j + 1] = L_MIN(16383, val1);
2077  buf2g[j] = L_MIN(16383, val2);
2078  buf2g[j + 1] = L_MIN(16383, val3);
2079  } else {
2080  buf1g[j + 1] = L_MAX(0, val1);
2081  buf2g[j] = L_MAX(0, val2);
2082  buf2g[j + 1] = L_MAX(0, val3);
2083  }
2084  }
2085 
2086  dif = buf1b[j] / 8 - 8 * bc;
2087  if (difcap > 0) {
2088  if (dif > difcap) dif = difcap;
2089  if (dif < -difcap) dif = -difcap;
2090  }
2091  if (dif != 0) {
2092  val1 = buf1b[j + 1] + 3 * dif;
2093  val2 = buf2b[j] + 3 * dif;
2094  val3 = buf2b[j + 1] + 2 * dif;
2095  if (dif > 0) {
2096  buf1b[j + 1] = L_MIN(16383, val1);
2097  buf2b[j] = L_MIN(16383, val2);
2098  buf2b[j + 1] = L_MIN(16383, val3);
2099  } else {
2100  buf1b[j + 1] = L_MAX(0, val1);
2101  buf2b[j] = L_MAX(0, val2);
2102  buf2b[j + 1] = L_MAX(0, val3);
2103  }
2104  }
2105  }
2106 
2107  /* Get last pixel in row; no downward propagation */
2108  rval = buf1r[w - 1] / 64;
2109  gval = buf1g[w - 1] / 64;
2110  bval = buf1b[w - 1] / 64;
2111  octindex = rtab[rval] | gtab[gval] | btab[bval];
2112  cmapindex = indexmap[octindex] - 1;
2113  SET_DATA_BYTE(lined, w - 1, cmapindex);
2114  }
2115 
2116  /* Get last row of pixels; no leftward propagation */
2117  lined = datad + (h - 1) * wpld;
2118  for (j = 0; j < w; j++) {
2119  rval = buf2r[j] / 64;
2120  gval = buf2g[j] / 64;
2121  bval = buf2b[j] / 64;
2122  octindex = rtab[rval] | gtab[gval] | btab[bval];
2123  cmapindex = indexmap[octindex] - 1;
2124  SET_DATA_BYTE(lined, j, cmapindex);
2125  }
2126 
2127 buffer_cleanup:
2128  LEPT_FREE(bufu8r);
2129  LEPT_FREE(bufu8g);
2130  LEPT_FREE(bufu8b);
2131  LEPT_FREE(buf1r);
2132  LEPT_FREE(buf1g);
2133  LEPT_FREE(buf1b);
2134  LEPT_FREE(buf2r);
2135  LEPT_FREE(buf2g);
2136  LEPT_FREE(buf2b);
2137 
2138  return (success) ? 0 : 1;
2139 }
2140 
2141 
2142 /*---------------------------------------------------------------------------*
2143  * Adaptive octree quantization to 4 and 8 bpp with max colors *
2144  *---------------------------------------------------------------------------*/
2234 PIX *
2236  l_int32 maxcolors,
2237  l_int32 subsample)
2238 {
2239 l_int32 w, h, minside, bpp, wpls, wpld, i, j, actualcolors;
2240 l_int32 rval, gval, bval, nbase, nextra, maxlevel, ncubes, val;
2241 l_int32 *lut1, *lut2;
2242 l_uint32 index;
2243 l_uint32 *lines, *lined, *datas, *datad, *pspixel;
2244 l_uint32 *rtab, *gtab, *btab;
2245 OQCELL *oqc;
2246 OQCELL **oqca;
2247 L_HEAP *lh;
2248 PIX *pixd;
2249 PIXCMAP *cmap;
2250 
2251  if (!pixs)
2252  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
2253  if (pixGetDepth(pixs) != 32)
2254  return (PIX *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
2255  if (maxcolors < 8) {
2256  L_WARNING("max colors < 8; setting to 8\n", __func__);
2257  maxcolors = 8;
2258  }
2259  if (maxcolors > 256) {
2260  L_WARNING("max colors > 256; setting to 256\n", __func__);
2261  maxcolors = 256;
2262  }
2263 
2264  pixGetDimensions(pixs, &w, &h, NULL);
2265  datas = pixGetData(pixs);
2266  wpls = pixGetWpl(pixs);
2267  minside = L_MIN(w, h);
2268  if (subsample <= 0) {
2269  subsample = L_MAX(1, minside / 200);
2270  }
2271 
2272  if (maxcolors <= 16) {
2273  bpp = 4;
2274  pixd = pixCreate(w, h, bpp);
2275  maxlevel = 2;
2276  ncubes = 64; /* 2^6 */
2277  nbase = 8;
2278  nextra = maxcolors - nbase;
2279  } else if (maxcolors <= 64) {
2280  bpp = 8;
2281  pixd = pixCreate(w, h, bpp);
2282  maxlevel = 2;
2283  ncubes = 64; /* 2^6 */
2284  nbase = 8;
2285  nextra = maxcolors - nbase;
2286  } else { /* maxcolors <= 256 */
2287  bpp = 8;
2288  pixd = pixCreate(w, h, bpp);
2289  maxlevel = 3;
2290  ncubes = 512; /* 2^9 */
2291  nbase = 64;
2292  nextra = maxcolors - nbase;
2293  }
2294 
2295  pixCopyResolution(pixd, pixs);
2296  pixCopyInputFormat(pixd, pixs);
2297 
2298  /*----------------------------------------------------------*
2299  * If we're using the minimum number of colors, it is *
2300  * much simpler. We just use 'nbase' octcubes. *
2301  * For this case, we don't eliminate any extra colors. *
2302  *----------------------------------------------------------*/
2303  if (nextra == 0) {
2304  /* prepare the OctcubeQuantCell array */
2305  if ((oqca = (OQCELL **)LEPT_CALLOC(nbase, sizeof(OQCELL *))) == NULL) {
2306  pixDestroy(&pixd);
2307  return (PIX *)ERROR_PTR("oqca not made", __func__, NULL);
2308  }
2309  for (i = 0; i < nbase; i++) {
2310  oqca[i] = (OQCELL *)LEPT_CALLOC(1, sizeof(OQCELL));
2311  oqca[i]->n = 0.0;
2312  }
2313 
2314  rtab = gtab = btab = NULL;
2315  makeRGBToIndexTables(maxlevel - 1, &rtab, &gtab, &btab);
2316 
2317  /* Go through the entire image, gathering statistics and
2318  * assigning pixels to their quantized value */
2319  datad = pixGetData(pixd);
2320  wpld = pixGetWpl(pixd);
2321  for (i = 0; i < h; i++) {
2322  lines = datas + i * wpls;
2323  lined = datad + i * wpld;
2324  for (j = 0; j < w; j++) {
2325  pspixel = lines + j;
2326  extractRGBValues(*pspixel, &rval, &gval, &bval);
2327  getOctcubeIndexFromRGB(rval, gval, bval,
2328  rtab, gtab, btab, &index);
2329 /* lept_stderr("rval = %d, gval = %d, bval = %d,"
2330  " index = %d\n", rval, gval, bval, index); */
2331  if (bpp == 4)
2332  SET_DATA_QBIT(lined, j, index);
2333  else /* bpp == 8 */
2334  SET_DATA_BYTE(lined, j, index);
2335  oqca[index]->n += 1.0;
2336  oqca[index]->rcum += rval;
2337  oqca[index]->gcum += gval;
2338  oqca[index]->bcum += bval;
2339  }
2340  }
2341 
2342  /* Compute average color values in each octcube, and
2343  * generate colormap */
2344  cmap = pixcmapCreate(bpp);
2345  pixSetColormap(pixd, cmap);
2346  for (i = 0; i < nbase; i++) {
2347  oqc = oqca[i];
2348  if (oqc->n != 0) {
2349  oqc->rval = (l_int32)(oqc->rcum / oqc->n);
2350  oqc->gval = (l_int32)(oqc->gcum / oqc->n);
2351  oqc->bval = (l_int32)(oqc->bcum / oqc->n);
2352  } else {
2353  getRGBFromOctcube(i, maxlevel - 1, &oqc->rval,
2354  &oqc->gval, &oqc->bval);
2355  }
2356  pixcmapAddColor(cmap, oqc->rval, oqc->gval, oqc->bval);
2357  }
2358 
2359  for (i = 0; i < nbase; i++)
2360  LEPT_FREE(oqca[i]);
2361  LEPT_FREE(oqca);
2362  LEPT_FREE(rtab);
2363  LEPT_FREE(gtab);
2364  LEPT_FREE(btab);
2365  return pixd;
2366  }
2367 
2368  /*------------------------------------------------------------*
2369  * General case: we will use colors in octcubes at maxlevel. *
2370  * We also remove any colors that are not populated from *
2371  * the colormap. *
2372  *------------------------------------------------------------*/
2373  /* Prepare the OctcubeQuantCell array */
2374  oqca = (OQCELL **)LEPT_CALLOC(ncubes, sizeof(OQCELL *));
2375  for (i = 0; i < ncubes; i++) {
2376  oqca[i] = (OQCELL *)LEPT_CALLOC(1, sizeof(OQCELL));
2377  oqca[i]->n = 0.0;
2378  }
2379 
2380  /* Make the tables to map color to the octindex,
2381  * of which there are 'ncubes' at 'maxlevel' */
2382  rtab = gtab = btab = NULL;
2383  makeRGBToIndexTables(maxlevel, &rtab, &gtab, &btab);
2384 
2385  /* Estimate the color distribution; we want to find the
2386  * most popular nextra colors at 'maxlevel' */
2387  for (i = 0; i < h; i += subsample) {
2388  lines = datas + i * wpls;
2389  for (j = 0; j < w; j += subsample) {
2390  pspixel = lines + j;
2391  extractRGBValues(*pspixel, &rval, &gval, &bval);
2392  getOctcubeIndexFromRGB(rval, gval, bval, rtab, gtab, btab, &index);
2393  oqca[index]->n += 1.0;
2394  oqca[index]->octindex = index;
2395  oqca[index]->rcum += rval;
2396  oqca[index]->gcum += gval;
2397  oqca[index]->bcum += bval;
2398  }
2399  }
2400 
2401  /* Transfer the OQCELL from the array, and order in a heap */
2402  lh = lheapCreate(512, L_SORT_DECREASING);
2403  for (i = 0; i < ncubes; i++)
2404  lheapAdd(lh, oqca[i]);
2405  LEPT_FREE(oqca); /* don't need this array */
2406 
2407  /* Prepare a new OctcubeQuantCell array, with maxcolors cells */
2408  oqca = (OQCELL **)LEPT_CALLOC(maxcolors, sizeof(OQCELL *));
2409  for (i = 0; i < nbase; i++) { /* make nbase cells */
2410  oqca[i] = (OQCELL *)LEPT_CALLOC(1, sizeof(OQCELL));
2411  oqca[i]->n = 0.0;
2412  }
2413 
2414  /* Remove the nextra most populated ones, and put them in the array */
2415  for (i = 0; i < nextra; i++) {
2416  oqc = (OQCELL *)lheapRemove(lh);
2417  oqc->n = 0.0; /* reinit */
2418  oqc->rcum = 0;
2419  oqc->gcum = 0;
2420  oqc->bcum = 0;
2421  oqca[nbase + i] = oqc; /* store it in the array */
2422  }
2423 
2424  /* Destroy the heap and its remaining contents */
2425  lheapDestroy(&lh, TRUE);
2426 
2427  /* Generate a lookup table from octindex at maxlevel
2428  * to color table index */
2429  lut1 = (l_int32 *)LEPT_CALLOC(ncubes, sizeof(l_int32));
2430  for (i = 0; i < nextra; i++)
2431  lut1[oqca[nbase + i]->octindex] = nbase + i;
2432  for (index = 0; index < ncubes; index++) {
2433  if (lut1[index] == 0) /* not one of the extras; need to assign */
2434  lut1[index] = index >> 3; /* remove the least significant bits */
2435 /* lept_stderr("lut1[%d] = %d\n", index, lut1[index]); */
2436  }
2437 
2438  /* Go through the entire image, gathering statistics and
2439  * assigning pixels to their quantized value */
2440  datad = pixGetData(pixd);
2441  wpld = pixGetWpl(pixd);
2442  for (i = 0; i < h; i++) {
2443  lines = datas + i * wpls;
2444  lined = datad + i * wpld;
2445  for (j = 0; j < w; j++) {
2446  pspixel = lines + j;
2447  extractRGBValues(*pspixel, &rval, &gval, &bval);
2448  getOctcubeIndexFromRGB(rval, gval, bval, rtab, gtab, btab, &index);
2449 /* lept_stderr("rval = %d, gval = %d, bval = %d, index = %d\n",
2450  rval, gval, bval, index); */
2451  val = lut1[index];
2452  switch (bpp) {
2453  case 4:
2454  SET_DATA_QBIT(lined, j, val);
2455  break;
2456  case 8:
2457  SET_DATA_BYTE(lined, j, val);
2458  break;
2459  default:
2460  LEPT_FREE(oqca);
2461  LEPT_FREE(lut1);
2462  return (PIX *)ERROR_PTR("bpp not 4 or 8!", __func__, NULL);
2463  break;
2464  }
2465  oqca[val]->n += 1.0;
2466  oqca[val]->rcum += rval;
2467  oqca[val]->gcum += gval;
2468  oqca[val]->bcum += bval;
2469  }
2470  }
2471 
2472  /* Compute averages, set up a colormap, and make a second
2473  * lut that converts from the color values currently in
2474  * the image to a minimal set */
2475  lut2 = (l_int32 *)LEPT_CALLOC(ncubes, sizeof(l_int32));
2476  cmap = pixcmapCreate(bpp);
2477  pixSetColormap(pixd, cmap);
2478  for (i = 0, index = 0; i < maxcolors; i++) {
2479  oqc = oqca[i];
2480  lut2[i] = index;
2481  if (oqc->n == 0) /* no occupancy; don't bump up index */
2482  continue;
2483  oqc->rval = (l_int32)(oqc->rcum / oqc->n);
2484  oqc->gval = (l_int32)(oqc->gcum / oqc->n);
2485  oqc->bval = (l_int32)(oqc->bcum / oqc->n);
2486  pixcmapAddColor(cmap, oqc->rval, oqc->gval, oqc->bval);
2487  index++;
2488  }
2489 /* pixcmapWriteStream(stderr, cmap); */
2490  actualcolors = pixcmapGetCount(cmap);
2491 /* lept_stderr("Number of different colors = %d\n", actualcolors); */
2492 
2493  /* Last time through the image; use the lookup table to
2494  * remap the pixel value to the minimal colormap */
2495  if (actualcolors < maxcolors) {
2496  for (i = 0; i < h; i++) {
2497  lined = datad + i * wpld;
2498  for (j = 0; j < w; j++) {
2499  switch (bpp) {
2500  case 4:
2501  val = GET_DATA_QBIT(lined, j);
2502  SET_DATA_QBIT(lined, j, lut2[val]);
2503  break;
2504  case 8:
2505  val = GET_DATA_BYTE(lined, j);
2506  SET_DATA_BYTE(lined, j, lut2[val]);
2507  break;
2508  }
2509  }
2510  }
2511  }
2512 
2513  if (oqca) {
2514  for (i = 0; i < maxcolors; i++)
2515  LEPT_FREE(oqca[i]);
2516  }
2517  LEPT_FREE(oqca);
2518  LEPT_FREE(lut1);
2519  LEPT_FREE(lut2);
2520  LEPT_FREE(rtab);
2521  LEPT_FREE(gtab);
2522  LEPT_FREE(btab);
2523  return pixd;
2524 }
2525 
2526 
2527 /*-------------------------------------------------------------------------*
2528  * Mixed color/gray quantization with specified number of colors *
2529  *-------------------------------------------------------------------------*/
2559 PIX *
2561  l_int32 depth,
2562  l_int32 graylevels,
2563  l_int32 delta)
2564 {
2565 l_int32 w, h, wpls, wpld, i, j, size, octlevels;
2566 l_int32 rval, gval, bval, del, val, midval;
2567 l_int32 *carray, *rarray, *garray, *barray;
2568 l_int32 *tabval;
2569 l_uint32 octindex;
2570 l_uint32 *rtab, *gtab, *btab;
2571 l_uint32 *lines, *lined, *datas, *datad;
2572 PIX *pixd;
2573 PIXCMAP *cmap;
2574 
2575  if (!pixs)
2576  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
2577  if (pixGetDepth(pixs) != 32)
2578  return (PIX *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
2579  if (graylevels < 2)
2580  return (PIX *)ERROR_PTR("invalid graylevels", __func__, NULL);
2581  if (depth == 4) {
2582  octlevels = 1;
2583  size = 8; /* 2 ** 3 */
2584  if (graylevels > 8)
2585  return (PIX *)ERROR_PTR("max 8 gray levels", __func__, NULL);
2586  } else if (depth == 8) {
2587  octlevels = 2;
2588  size = 64; /* 2 ** 6 */
2589  if (graylevels > 192)
2590  return (PIX *)ERROR_PTR("max 192 gray levels", __func__, NULL);
2591  } else {
2592  return (PIX *)ERROR_PTR("output depth not 4 or 8 bpp", __func__, NULL);
2593  }
2594 
2595  pixd = NULL;
2596 
2597  /* Make octcube index tables */
2598  rtab = gtab = btab = NULL;
2599  makeRGBToIndexTables(octlevels, &rtab, &gtab, &btab);
2600 
2601  /* Make octcube arrays for storing points in each cube */
2602  carray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2603  rarray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2604  garray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2605  barray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2606 
2607  /* Make lookup table, using computed thresholds */
2608  tabval = makeGrayQuantIndexTable(graylevels);
2609  if (!rtab || !gtab || !btab ||
2610  !carray || !rarray || !garray || !barray || !tabval) {
2611  L_ERROR("calloc fail for an array\n", __func__);
2612  goto array_cleanup;
2613  }
2614 
2615  /* Make colormapped output pixd */
2616  pixGetDimensions(pixs, &w, &h, NULL);
2617  if ((pixd = pixCreate(w, h, depth)) == NULL) {
2618  L_ERROR("pixd not made\n", __func__);
2619  goto array_cleanup;
2620  }
2621  pixCopyResolution(pixd, pixs);
2622  pixCopyInputFormat(pixd, pixs);
2623  cmap = pixcmapCreate(depth);
2624  for (j = 0; j < size; j++) /* reserve octcube colors */
2625  pixcmapAddColor(cmap, 1, 1, 1); /* a color that won't be used */
2626  for (j = 0; j < graylevels; j++) { /* set grayscale colors */
2627  val = (255 * j) / (graylevels - 1);
2628  pixcmapAddColor(cmap, val, val, val);
2629  }
2630  pixSetColormap(pixd, cmap);
2631  wpld = pixGetWpl(pixd);
2632  datad = pixGetData(pixd);
2633 
2634  /* Go through src image: assign dest pixels to colormap values
2635  * and compute average colors in each occupied octcube */
2636  datas = pixGetData(pixs);
2637  wpls = pixGetWpl(pixs);
2638  for (i = 0; i < h; i++) {
2639  lines = datas + i * wpls;
2640  lined = datad + i * wpld;
2641  for (j = 0; j < w; j++) {
2642  extractRGBValues(lines[j], &rval, &gval, &bval);
2643  if (rval > gval) {
2644  if (gval > bval) { /* r > g > b */
2645  del = rval - bval;
2646  midval = gval;
2647  } else if (rval > bval) { /* r > b > g */
2648  del = rval - gval;
2649  midval = bval;
2650  } else { /* b > r > g */
2651  del = bval - gval;
2652  midval = rval;
2653  }
2654  } else { /* gval >= rval */
2655  if (rval > bval) { /* g > r > b */
2656  del = gval - bval;
2657  midval = rval;
2658  } else if (gval > bval) { /* g > b > r */
2659  del = gval - rval;
2660  midval = bval;
2661  } else { /* b > g > r */
2662  del = bval - rval;
2663  midval = gval;
2664  }
2665  }
2666  if (del > delta) { /* assign to color */
2667  octindex = rtab[rval] | gtab[gval] | btab[bval];
2668  carray[octindex]++;
2669  rarray[octindex] += rval;
2670  garray[octindex] += gval;
2671  barray[octindex] += bval;
2672  if (depth == 4)
2673  SET_DATA_QBIT(lined, j, octindex);
2674  else /* depth == 8 */
2675  SET_DATA_BYTE(lined, j, octindex);
2676  } else { /* assign to grayscale */
2677  val = size + tabval[midval];
2678  if (depth == 4)
2679  SET_DATA_QBIT(lined, j, val);
2680  else /* depth == 8 */
2681  SET_DATA_BYTE(lined, j, val);
2682  }
2683  }
2684  }
2685 
2686  /* Average the colors in each bin and reset the colormap */
2687  for (i = 0; i < size; i++) {
2688  if (carray[i] > 0) {
2689  rarray[i] /= carray[i];
2690  garray[i] /= carray[i];
2691  barray[i] /= carray[i];
2692  pixcmapResetColor(cmap, i, rarray[i], garray[i], barray[i]);
2693  }
2694  }
2695 
2696 array_cleanup:
2697  LEPT_FREE(carray);
2698  LEPT_FREE(rarray);
2699  LEPT_FREE(garray);
2700  LEPT_FREE(barray);
2701  LEPT_FREE(rtab);
2702  LEPT_FREE(gtab);
2703  LEPT_FREE(btab);
2704  LEPT_FREE(tabval);
2705 
2706  return pixd;
2707 }
2708 
2709 
2710 /*-------------------------------------------------------------------------*
2711  * Fixed partition octcube quantization with 256 cells *
2712  *-------------------------------------------------------------------------*/
2776 PIX *
2778  l_int32 ditherflag)
2779 {
2780 l_uint8 index;
2781 l_int32 rval, gval, bval;
2782 l_int32 w, h, wpls, wpld, i, j, cindex;
2783 l_uint32 *rtab, *gtab, *btab;
2784 l_int32 *itab;
2785 l_uint32 *datas, *datad, *lines, *lined;
2786 PIX *pixd;
2787 PIXCMAP *cmap;
2788 
2789  if (!pixs)
2790  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
2791  if (pixGetDepth(pixs) != 32)
2792  return (PIX *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
2793 
2794  /* Do not dither if image is very small */
2795  pixGetDimensions(pixs, &w, &h, NULL);
2796  if (w < MinDitherSize && h < MinDitherSize && ditherflag == 1) {
2797  L_INFO("Small image: dithering turned off\n", __func__);
2798  ditherflag = 0;
2799  }
2800 
2801  /* Find the centers of the 256 cells, each of which represents
2802  * the 3 MSBits of the red and green components, and the
2803  * 2 MSBits of the blue component. This gives a mapping
2804  * from a "cube index" to the rgb values. Save all 256
2805  * rgb values of these centers in a colormap.
2806  * For example, to get the red color of the cell center,
2807  * you take the 3 MSBits of to the index and add the
2808  * offset to the center of the cell, which is 0x10. */
2809  cmap = pixcmapCreate(8);
2810  for (cindex = 0; cindex < 256; cindex++) {
2811  rval = (cindex & 0xe0) | 0x10;
2812  gval = ((cindex << 3) & 0xe0) | 0x10;
2813  bval = ((cindex << 6) & 0xc0) | 0x20;
2814  pixcmapAddColor(cmap, rval, gval, bval);
2815  }
2816 
2817  /* Make output 8 bpp palette image */
2818  datas = pixGetData(pixs);
2819  wpls = pixGetWpl(pixs);
2820  if ((pixd = pixCreate(w, h, 8)) == NULL) {
2821  pixcmapDestroy(&cmap);
2822  return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
2823  }
2824  pixSetColormap(pixd, cmap);
2825  pixCopyResolution(pixd, pixs);
2826  pixCopyInputFormat(pixd, pixs);
2827  datad = pixGetData(pixd);
2828  wpld = pixGetWpl(pixd);
2829 
2830  /* Set dest pix values to colortable indices */
2831  if (ditherflag == 0) { /* no dithering */
2832  for (i = 0; i < h; i++) {
2833  lines = datas + i * wpls;
2834  lined = datad + i * wpld;
2835  for (j = 0; j < w; j++) {
2836  extractRGBValues(lines[j], &rval, &gval, &bval);
2837  index = (rval & 0xe0) | ((gval >> 3) & 0x1c) | (bval >> 6);
2838  SET_DATA_BYTE(lined, j, index);
2839  }
2840  }
2841  } else { /* ditherflag == 1 */
2842  /* Set up conversion tables from rgb directly to the colormap
2843  * index. However, the dithering function expects these tables
2844  * to generate an octcube index (+1), and the table itab[] to
2845  * convert to the colormap index. So we make a trivial
2846  * itab[], that simply compensates for the -1 in
2847  * pixDitherOctindexWithCmap(). No cap is required on
2848  * the propagated difference. */
2849  rtab = (l_uint32 *)LEPT_CALLOC(256, sizeof(l_uint32));
2850  gtab = (l_uint32 *)LEPT_CALLOC(256, sizeof(l_uint32));
2851  btab = (l_uint32 *)LEPT_CALLOC(256, sizeof(l_uint32));
2852  itab = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
2853  if (!rtab || !gtab || !btab || !itab) {
2854  pixDestroy(&pixd);
2855  return (PIX *)ERROR_PTR("calloc fail for table", __func__, NULL);
2856  }
2857  for (i = 0; i < 256; i++) {
2858  rtab[i] = i & 0xe0;
2859  gtab[i] = (i >> 3) & 0x1c;
2860  btab[i] = i >> 6;
2861  itab[i] = i + 1;
2862  }
2863  pixDitherOctindexWithCmap(pixs, pixd, rtab, gtab, btab, itab,
2864  FIXED_DIF_CAP);
2865  LEPT_FREE(rtab);
2866  LEPT_FREE(gtab);
2867  LEPT_FREE(btab);
2868  LEPT_FREE(itab);
2869  }
2870 
2871  return pixd;
2872 }
2873 
2874 
2875 /*---------------------------------------------------------------------------*
2876  * Nearly exact quantization for images with few colors *
2877  *---------------------------------------------------------------------------*/
2908 PIX *
2910  l_int32 level)
2911 {
2912 l_int32 w, h, wpls, wpld, i, j, depth, size, ncolors, index;
2913 l_int32 rval, gval, bval;
2914 l_int32 *carray, *rarray, *garray, *barray;
2915 l_uint32 octindex;
2916 l_uint32 *rtab, *gtab, *btab;
2917 l_uint32 *lines, *lined, *datas, *datad, *pspixel;
2918 PIX *pixd;
2919 PIXCMAP *cmap;
2920 
2921  if (!pixs)
2922  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
2923  if (pixGetDepth(pixs) != 32)
2924  return (PIX *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
2925  if (level < 1 || level > 6)
2926  return (PIX *)ERROR_PTR("invalid level", __func__, NULL);
2927 
2928  pixd = NULL;
2929 
2930  if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
2931  return (PIX *)ERROR_PTR("size not returned", __func__, NULL);
2932  rtab = gtab = btab = NULL;
2933  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
2934 
2935  carray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2936  rarray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2937  garray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2938  barray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2939  if (!carray || !rarray || !garray || !barray) {
2940  L_ERROR("calloc fail for an array\n", __func__);
2941  goto array_cleanup;
2942  }
2943 
2944  /* Place the pixels in octcube leaves. */
2945  pixGetDimensions(pixs, &w, &h, NULL);
2946  datas = pixGetData(pixs);
2947  wpls = pixGetWpl(pixs);
2948  for (i = 0; i < h; i++) {
2949  lines = datas + i * wpls;
2950  for (j = 0; j < w; j++) {
2951  pspixel = lines + j;
2952  extractRGBValues(*pspixel, &rval, &gval, &bval);
2953  octindex = rtab[rval] | gtab[gval] | btab[bval];
2954  carray[octindex]++;
2955  rarray[octindex] += rval;
2956  garray[octindex] += gval;
2957  barray[octindex] += bval;
2958  }
2959  }
2960 
2961  /* Find the number of different colors */
2962  for (i = 0, ncolors = 0; i < size; i++) {
2963  if (carray[i] > 0)
2964  ncolors++;
2965  }
2966  if (ncolors > 256) {
2967  L_WARNING("%d colors found; more than 256\n", __func__, ncolors);
2968  goto array_cleanup;
2969  }
2970  if (ncolors <= 4)
2971  depth = 2;
2972  else if (ncolors <= 16)
2973  depth = 4;
2974  else
2975  depth = 8;
2976 
2977  /* Average the colors in each octcube leaf and add to colormap table;
2978  * then use carray to hold the colormap index + 1 */
2979  cmap = pixcmapCreate(depth);
2980  for (i = 0, index = 0; i < size; i++) {
2981  if (carray[i] > 0) {
2982  rarray[i] /= carray[i];
2983  garray[i] /= carray[i];
2984  barray[i] /= carray[i];
2985  pixcmapAddColor(cmap, rarray[i], garray[i], barray[i]);
2986  carray[i] = index + 1; /* to avoid storing 0 */
2987  index++;
2988  }
2989  }
2990 
2991  pixd = pixCreate(w, h, depth);
2992  pixSetColormap(pixd, cmap);
2993  pixCopyResolution(pixd, pixs);
2994  pixCopyInputFormat(pixd, pixs);
2995  datad = pixGetData(pixd);
2996  wpld = pixGetWpl(pixd);
2997  for (i = 0; i < h; i++) {
2998  lines = datas + i * wpls;
2999  lined = datad + i * wpld;
3000  for (j = 0; j < w; j++) {
3001  pspixel = lines + j;
3002  extractRGBValues(*pspixel, &rval, &gval, &bval);
3003  octindex = rtab[rval] | gtab[gval] | btab[bval];
3004  switch (depth)
3005  {
3006  case 2:
3007  SET_DATA_DIBIT(lined, j, carray[octindex] - 1);
3008  break;
3009  case 4:
3010  SET_DATA_QBIT(lined, j, carray[octindex] - 1);
3011  break;
3012  case 8:
3013  SET_DATA_BYTE(lined, j, carray[octindex] - 1);
3014  break;
3015  default:
3016  L_WARNING("shouldn't get here\n", __func__);
3017  }
3018  }
3019  }
3020 
3021 array_cleanup:
3022  LEPT_FREE(carray);
3023  LEPT_FREE(rarray);
3024  LEPT_FREE(garray);
3025  LEPT_FREE(barray);
3026  LEPT_FREE(rtab);
3027  LEPT_FREE(gtab);
3028  LEPT_FREE(btab);
3029  return pixd;
3030 }
3031 
3032 
3076 PIX *
3078  l_int32 level,
3079  NUMA *na,
3080  l_int32 ncolors,
3081  l_int32 *pnerrors)
3082 {
3083 l_int32 w, h, wpls, wpld, i, j, nerrors;
3084 l_int32 ncubes, depth, cindex, oval;
3085 l_int32 rval, gval, bval;
3086 l_int32 *octarray;
3087 l_uint32 octindex;
3088 l_uint32 *rtab, *gtab, *btab;
3089 l_uint32 *lines, *lined, *datas, *datad, *ppixel;
3090 l_uint32 *colorarray;
3091 PIX *pixd;
3092 PIXCMAP *cmap;
3093 
3094  if (!pixs)
3095  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
3096  if (pixGetDepth(pixs) != 32)
3097  return (PIX *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
3098  if (level < 3 || level > 6)
3099  return (PIX *)ERROR_PTR("level not in {4, 5, 6}", __func__, NULL);
3100  if (ncolors > 256)
3101  return (PIX *)ERROR_PTR("ncolors > 256", __func__, NULL);
3102  if (pnerrors)
3103  *pnerrors = UNDEF;
3104 
3105  pixd = NULL;
3106 
3107  /* Represent the image with a set of leaf octcubes
3108  * at 'level', one for each color. */
3109  rtab = gtab = btab = NULL;
3110  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
3111 
3112  /* The octarray will give a ptr from the octcube to the colorarray */
3113  ncubes = numaGetCount(na);
3114  octarray = (l_int32 *)LEPT_CALLOC(ncubes, sizeof(l_int32));
3115 
3116  /* The colorarray will hold the colors of the first pixel
3117  * that lands in the leaf octcube. After filling, it is
3118  * used to generate the colormap. */
3119  colorarray = (l_uint32 *)LEPT_CALLOC(ncolors + 1, sizeof(l_uint32));
3120  if (!octarray || !colorarray) {
3121  L_ERROR("octarray or colorarray not made\n", __func__);
3122  goto cleanup_arrays;
3123  }
3124 
3125  /* Determine the output depth from the number of colors */
3126  pixGetDimensions(pixs, &w, &h, NULL);
3127  datas = pixGetData(pixs);
3128  wpls = pixGetWpl(pixs);
3129  if (ncolors <= 4)
3130  depth = 2;
3131  else if (ncolors <= 16)
3132  depth = 4;
3133  else /* ncolors <= 256 */
3134  depth = 8;
3135 
3136  if ((pixd = pixCreate(w, h, depth)) == NULL) {
3137  L_ERROR("pixd not made\n", __func__);
3138  goto cleanup_arrays;
3139  }
3140  pixCopyResolution(pixd, pixs);
3141  pixCopyInputFormat(pixd, pixs);
3142  datad = pixGetData(pixd);
3143  wpld = pixGetWpl(pixd);
3144 
3145  /* For each pixel, get the octree index for its leaf octcube.
3146  * Check if a pixel has already been found in this octcube.
3147  * ~ If not yet found, save that color in the colorarray
3148  * and save the cindex in the octarray.
3149  * ~ If already found, compare the pixel color with the
3150  * color in the colorarray, and note if it differs.
3151  * Then set the dest pixel value to the cindex - 1, which
3152  * will be the cmap index for this color. */
3153  cindex = 1; /* start with 1 */
3154  nerrors = 0;
3155  for (i = 0; i < h; i++) {
3156  lines = datas + i * wpls;
3157  lined = datad + i * wpld;
3158  for (j = 0; j < w; j++) {
3159  ppixel = lines + j;
3160  extractRGBValues(*ppixel, &rval, &gval, &bval);
3161  octindex = rtab[rval] | gtab[gval] | btab[bval];
3162  oval = octarray[octindex];
3163  if (oval == 0) {
3164  octarray[octindex] = cindex;
3165  colorarray[cindex] = *ppixel;
3166  setPixelLow(lined, j, depth, cindex - 1);
3167  cindex++;
3168  } else { /* already have seen this color; is it unique? */
3169  setPixelLow(lined, j, depth, oval - 1);
3170  if (colorarray[oval] != *ppixel)
3171  nerrors++;
3172  }
3173  }
3174  }
3175  if (pnerrors)
3176  *pnerrors = nerrors;
3177 
3178 #if DEBUG_FEW_COLORS
3179  lept_stderr("ncubes = %d, ncolors = %d\n", ncubes, ncolors);
3180  for (i = 0; i < ncolors; i++)
3181  lept_stderr("color[%d] = %x\n", i, colorarray[i + 1]);
3182 #endif /* DEBUG_FEW_COLORS */
3183 
3184  /* Make the colormap. */
3185  cmap = pixcmapCreate(depth);
3186  for (i = 0; i < ncolors; i++) {
3187  ppixel = colorarray + i + 1;
3188  extractRGBValues(*ppixel, &rval, &gval, &bval);
3189  pixcmapAddColor(cmap, rval, gval, bval);
3190  }
3191  pixSetColormap(pixd, cmap);
3192 
3193 cleanup_arrays:
3194  LEPT_FREE(octarray);
3195  LEPT_FREE(colorarray);
3196  LEPT_FREE(rtab);
3197  LEPT_FREE(gtab);
3198  LEPT_FREE(btab);
3199 
3200  return pixd;
3201 }
3202 
3203 
3263 PIX *
3265  l_int32 level,
3266  l_int32 darkthresh,
3267  l_int32 lightthresh,
3268  l_int32 diffthresh,
3269  l_float32 minfract,
3270  l_int32 maxspan)
3271 {
3272 l_int32 i, j, w, h, wplc, wplm, wpld, ncolors, index;
3273 l_int32 rval, gval, bval, val, minval, maxval;
3274 l_int32 *lut;
3275 l_uint32 *datac, *datam, *datad, *linec, *linem, *lined;
3276 PIX *pix1, *pixc, *pixm, *pixg, *pixd;
3277 PIXCMAP *cmap, *cmapd;
3278 
3279  if (!pixs || pixGetDepth(pixs) != 32)
3280  return (PIX *)ERROR_PTR("pixs undefined or not 32 bpp", __func__, NULL);
3281  if (level <= 0) level = 3;
3282  if (level > 6)
3283  return (PIX *)ERROR_PTR("invalid level", __func__, NULL);
3284  if (darkthresh <= 0) darkthresh = 20;
3285  if (lightthresh <= 0) lightthresh = 244;
3286  if (diffthresh <= 0) diffthresh = 20;
3287  if (minfract <= 0.0) minfract = 0.05;
3288  if (maxspan <= 2) maxspan = 15;
3289 
3290  /* Start with a simple fixed octcube quantizer. */
3291  if ((pix1 = pixFewColorsOctcubeQuant1(pixs, level)) == NULL)
3292  return (PIX *)ERROR_PTR("too many colors", __func__, NULL);
3293  pixc = pixConvertTo8(pix1, 1); /* must be 8 bpp */
3294  pixDestroy(&pix1);
3295 
3296  /* Identify and save color entries in the colormap. Set up a LUT
3297  * that returns -1 for any gray pixel. */
3298  cmap = pixGetColormap(pixc);
3299  ncolors = pixcmapGetCount(cmap);
3300  cmapd = pixcmapCreate(8);
3301  lut = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
3302  for (i = 0; i < 256; i++)
3303  lut[i] = -1;
3304  for (i = 0, index = 0; i < ncolors; i++) {
3305  pixcmapGetColor(cmap, i, &rval, &gval, &bval);
3306  minval = L_MIN(rval, gval);
3307  minval = L_MIN(minval, bval);
3308  if (minval > lightthresh) /* near white */
3309  continue;
3310  maxval = L_MAX(rval, gval);
3311  maxval = L_MAX(maxval, bval);
3312  if (maxval < darkthresh) /* near black */
3313  continue;
3314 
3315  /* Use the max diff between components to test for color */
3316  if (maxval - minval >= diffthresh) {
3317  pixcmapAddColor(cmapd, rval, gval, bval);
3318  lut[i] = index;
3319  index++;
3320  }
3321  }
3322 
3323  /* Generate dest pix with just the color pixels set to their
3324  * colormap indices. At the same time, make a 1 bpp mask
3325  * of the non-color pixels */
3326  pixGetDimensions(pixs, &w, &h, NULL);
3327  pixd = pixCreate(w, h, 8);
3328  pixSetColormap(pixd, cmapd);
3329  pixm = pixCreate(w, h, 1);
3330  datac = pixGetData(pixc);
3331  datam = pixGetData(pixm);
3332  datad = pixGetData(pixd);
3333  wplc = pixGetWpl(pixc);
3334  wplm = pixGetWpl(pixm);
3335  wpld = pixGetWpl(pixd);
3336  for (i = 0; i < h; i++) {
3337  linec = datac + i * wplc;
3338  linem = datam + i * wplm;
3339  lined = datad + i * wpld;
3340  for (j = 0; j < w; j++) {
3341  val = GET_DATA_BYTE(linec, j);
3342  if (lut[val] == -1)
3343  SET_DATA_BIT(linem, j);
3344  else
3345  SET_DATA_BYTE(lined, j, lut[val]);
3346  }
3347  }
3348 
3349  /* Fill in the gray values. Use a grayscale version of pixs
3350  * as input, along with the mask over the actual gray pixels. */
3351  pixg = pixConvertTo8(pixs, 0);
3352  pixGrayQuantFromHisto(pixd, pixg, pixm, minfract, maxspan);
3353 
3354  LEPT_FREE(lut);
3355  pixDestroy(&pixc);
3356  pixDestroy(&pixm);
3357  pixDestroy(&pixg);
3358  return pixd;
3359 }
3360 
3361 
3362 /*---------------------------------------------------------------------------*
3363  * Fixed partition octcube quantization with RGB output *
3364  *---------------------------------------------------------------------------*/
3381 PIX *
3383  l_int32 level)
3384 {
3385 l_int32 w, h, wpls, wpld, i, j;
3386 l_int32 rval, gval, bval;
3387 l_uint32 octindex;
3388 l_uint32 *rtab, *gtab, *btab;
3389 l_uint32 *lines, *lined, *datas, *datad;
3390 PIX *pixd;
3391 
3392  if (!pixs)
3393  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
3394  if (pixGetDepth(pixs) != 32)
3395  return (PIX *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
3396  if (level < 1 || level > 6)
3397  return (PIX *)ERROR_PTR("level not in {1,...6}", __func__, NULL);
3398 
3399  if (makeRGBToIndexTables(level, &rtab, &gtab, &btab))
3400  return (PIX *)ERROR_PTR("tables not made", __func__, NULL);
3401 
3402  pixGetDimensions(pixs, &w, &h, NULL);
3403  pixd = pixCreate(w, h, 32);
3404  pixCopyResolution(pixd, pixs);
3405  pixCopyInputFormat(pixd, pixs);
3406  datad = pixGetData(pixd);
3407  wpld = pixGetWpl(pixd);
3408  datas = pixGetData(pixs);
3409  wpls = pixGetWpl(pixs);
3410  for (i = 0; i < h; i++) {
3411  lines = datas + i * wpls;
3412  lined = datad + i * wpld;
3413  for (j = 0; j < w; j++) {
3414  extractRGBValues(lines[j], &rval, &gval, &bval);
3415  octindex = rtab[rval] | gtab[gval] | btab[bval];
3416  getRGBFromOctcube(octindex, level, &rval, &gval, &bval);
3417  composeRGBPixel(rval, gval, bval, lined + j);
3418  }
3419  }
3420 
3421  LEPT_FREE(rtab);
3422  LEPT_FREE(gtab);
3423  LEPT_FREE(btab);
3424  return pixd;
3425 }
3426 
3427 
3428 /*------------------------------------------------------------------*
3429  * Color quantize RGB image using existing colormap *
3430  *------------------------------------------------------------------*/
3452 PIX *
3454  PIXCMAP *cmap,
3455  l_int32 mindepth,
3456  l_int32 level,
3457  l_int32 metric)
3458 {
3459 l_int32 d;
3460 
3461  if (!pixs)
3462  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
3463  if (mindepth != 2 && mindepth != 4 && mindepth != 8)
3464  return (PIX *)ERROR_PTR("invalid mindepth", __func__, NULL);
3465  d = pixGetDepth(pixs);
3466  if (d == 8)
3467  return pixGrayQuantFromCmap(pixs, cmap, mindepth);
3468  else if (d == 32)
3469  return pixOctcubeQuantFromCmap(pixs, cmap, mindepth,
3470  level, metric);
3471  else
3472  return (PIX *)ERROR_PTR("d not 8 or 32 bpp", __func__, NULL);
3473 }
3474 
3475 
3476 
3539 PIX *
3541  PIXCMAP *cmap,
3542  l_int32 mindepth,
3543  l_int32 level,
3544  l_int32 metric)
3545 {
3546 l_int32 *cmaptab;
3547 l_uint32 *rtab, *gtab, *btab;
3548 PIX *pixd;
3549 
3550  if (!pixs)
3551  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
3552  if (pixGetDepth(pixs) != 32)
3553  return (PIX *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
3554  if (!cmap)
3555  return (PIX *)ERROR_PTR("cmap not defined", __func__, NULL);
3556  if (mindepth != 2 && mindepth != 4 && mindepth != 8)
3557  return (PIX *)ERROR_PTR("invalid mindepth", __func__, NULL);
3558  if (level < 1 || level > 6)
3559  return (PIX *)ERROR_PTR("level not in {1...6}", __func__, NULL);
3560  if (metric != L_MANHATTAN_DISTANCE && metric != L_EUCLIDEAN_DISTANCE)
3561  return (PIX *)ERROR_PTR("invalid metric", __func__, NULL);
3562 
3563  /* Set up the tables to map rgb to the nearest colormap index */
3564  rtab = gtab = btab = NULL;
3565  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
3566  cmaptab = pixcmapToOctcubeLUT(cmap, level, metric);
3567 
3568  pixd = pixOctcubeQuantFromCmapLUT(pixs, cmap, mindepth,
3569  cmaptab, rtab, gtab, btab);
3570 
3571  LEPT_FREE(cmaptab);
3572  LEPT_FREE(rtab);
3573  LEPT_FREE(gtab);
3574  LEPT_FREE(btab);
3575  return pixd;
3576 }
3577 
3578 
3603 static PIX *
3605  PIXCMAP *cmap,
3606  l_int32 mindepth,
3607  l_int32 *cmaptab,
3608  l_uint32 *rtab,
3609  l_uint32 *gtab,
3610  l_uint32 *btab)
3611 {
3612 l_int32 i, j, w, h, depth, wpls, wpld;
3613 l_int32 rval, gval, bval, index;
3614 l_uint32 octindex;
3615 l_uint32 *lines, *lined, *datas, *datad;
3616 PIX *pixd;
3617 PIXCMAP *cmapc;
3618 
3619  if (!pixs)
3620  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
3621  if (pixGetDepth(pixs) != 32)
3622  return (PIX *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
3623  if (!cmap)
3624  return (PIX *)ERROR_PTR("cmap not defined", __func__, NULL);
3625  if (mindepth != 2 && mindepth != 4 && mindepth != 8)
3626  return (PIX *)ERROR_PTR("invalid mindepth", __func__, NULL);
3627  if (!rtab || !gtab || !btab || !cmaptab)
3628  return (PIX *)ERROR_PTR("tables not all defined", __func__, NULL);
3629 
3630  /* Init dest pix (with minimum bpp depending on cmap) */
3631  pixcmapGetMinDepth(cmap, &depth);
3632  depth = L_MAX(depth, mindepth);
3633  pixGetDimensions(pixs, &w, &h, NULL);
3634  if ((pixd = pixCreate(w, h, depth)) == NULL)
3635  return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
3636  cmapc = pixcmapCopy(cmap);
3637  pixSetColormap(pixd, cmapc);
3638  pixCopyResolution(pixd, pixs);
3639  pixCopyInputFormat(pixd, pixs);
3640 
3641  /* Insert the colormap index of the color nearest to the input pixel */
3642  datas = pixGetData(pixs);
3643  datad = pixGetData(pixd);
3644  wpls = pixGetWpl(pixs);
3645  wpld = pixGetWpl(pixd);
3646  for (i = 0; i < h; i++) {
3647  lines = datas + i * wpls;
3648  lined = datad + i * wpld;
3649  for (j = 0; j < w; j++) {
3650  extractRGBValues(lines[j], &rval, &gval, &bval);
3651  /* Map from rgb to octcube index */
3652  getOctcubeIndexFromRGB(rval, gval, bval, rtab, gtab, btab,
3653  &octindex);
3654  /* Map from octcube index to nearest colormap index */
3655  index = cmaptab[octindex];
3656  if (depth == 2)
3657  SET_DATA_DIBIT(lined, j, index);
3658  else if (depth == 4)
3659  SET_DATA_QBIT(lined, j, index);
3660  else /* depth == 8 */
3661  SET_DATA_BYTE(lined, j, index);
3662  }
3663  }
3664 
3665  return pixd;
3666 }
3667 
3668 
3669 /*---------------------------------------------------------------------------*
3670  * Generation of octcube histogram *
3671  *---------------------------------------------------------------------------*/
3685 NUMA *
3687  l_int32 level,
3688  l_int32 *pncolors)
3689 {
3690 l_int32 size, i, j, w, h, wpl, ncolors, val;
3691 l_int32 rval, gval, bval;
3692 l_uint32 octindex;
3693 l_uint32 *rtab, *gtab, *btab;
3694 l_uint32 *data, *line;
3695 l_float32 *array;
3696 NUMA *na;
3697 
3698  if (pncolors) *pncolors = 0;
3699  if (!pixs)
3700  return (NUMA *)ERROR_PTR("pixs not defined", __func__, NULL);
3701  if (pixGetDepth(pixs) != 32)
3702  return (NUMA *)ERROR_PTR("pixs not 32 bpp", __func__, NULL);
3703 
3704  pixGetDimensions(pixs, &w, &h, NULL);
3705  wpl = pixGetWpl(pixs);
3706  data = pixGetData(pixs);
3707 
3708  if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
3709  return (NUMA *)ERROR_PTR("size not returned", __func__, NULL);
3710  rtab = gtab = btab = NULL;
3711  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
3712 
3713  if ((na = numaCreate(size)) == NULL) {
3714  L_ERROR("na not made\n", __func__);
3715  goto cleanup_arrays;
3716  }
3717  numaSetCount(na, size);
3718  array = numaGetFArray(na, L_NOCOPY);
3719 
3720  for (i = 0; i < h; i++) {
3721  line = data + i * wpl;
3722  for (j = 0; j < w; j++) {
3723  extractRGBValues(line[j], &rval, &gval, &bval);
3724  octindex = rtab[rval] | gtab[gval] | btab[bval];
3725 #if DEBUG_OCTINDEX
3726  if ((level == 1 && octindex > 7) ||
3727  (level == 2 && octindex > 63) ||
3728  (level == 3 && octindex > 511) ||
3729  (level == 4 && octindex > 4097) ||
3730  (level == 5 && octindex > 32783) ||
3731  (level == 6 && octindex > 262271)) {
3732  lept_stderr("level = %d, octindex = %d, index error!\n",
3733  level, octindex);
3734  continue;
3735  }
3736 #endif /* DEBUG_OCTINDEX */
3737  array[octindex] += 1.0;
3738  }
3739  }
3740 
3741  if (pncolors) {
3742  for (i = 0, ncolors = 0; i < size; i++) {
3743  numaGetIValue(na, i, &val);
3744  if (val > 0)
3745  ncolors++;
3746  }
3747  *pncolors = ncolors;
3748  }
3749 
3750 cleanup_arrays:
3751  LEPT_FREE(rtab);
3752  LEPT_FREE(gtab);
3753  LEPT_FREE(btab);
3754  return na;
3755 }
3756 
3757 
3758 /*------------------------------------------------------------------*
3759  * Get filled octcube table from colormap *
3760  *------------------------------------------------------------------*/
3806 l_int32 *
3808  l_int32 level,
3809  l_int32 metric)
3810 {
3811 l_int32 i, k, size, ncolors, mindist, dist, mincolor, index;
3812 l_int32 rval, gval, bval; /* color at center of the octcube */
3813 l_int32 *rmap, *gmap, *bmap, *tab;
3814 
3815  if (!cmap)
3816  return (l_int32 *)ERROR_PTR("cmap not defined", __func__, NULL);
3817  if (level < 1 || level > 6)
3818  return (l_int32 *)ERROR_PTR("level not in {1...6}", __func__, NULL);
3819  if (metric != L_MANHATTAN_DISTANCE && metric != L_EUCLIDEAN_DISTANCE)
3820  return (l_int32 *)ERROR_PTR("invalid metric", __func__, NULL);
3821 
3822  if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
3823  return (l_int32 *)ERROR_PTR("size not returned", __func__, NULL);
3824  if ((tab = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32))) == NULL)
3825  return (l_int32 *)ERROR_PTR("tab not allocated", __func__, NULL);
3826 
3827  ncolors = pixcmapGetCount(cmap);
3828  pixcmapToArrays(cmap, &rmap, &gmap, &bmap, NULL);
3829 
3830  /* Assign based on the closest octcube center to the cmap color */
3831  for (i = 0; i < size; i++) {
3832  getRGBFromOctcube(i, level, &rval, &gval, &bval);
3833  mindist = 1000000;
3834  mincolor = 0; /* irrelevant init */
3835  for (k = 0; k < ncolors; k++) {
3836  if (metric == L_MANHATTAN_DISTANCE) {
3837  dist = L_ABS(rval - rmap[k]) + L_ABS(gval - gmap[k]) +
3838  L_ABS(bval - bmap[k]);
3839  } else { /* L_EUCLIDEAN_DISTANCE */
3840  dist = (rval - rmap[k]) * (rval - rmap[k]) +
3841  (gval - gmap[k]) * (gval - gmap[k]) +
3842  (bval - bmap[k]) * (bval - bmap[k]);
3843  }
3844  if (dist < mindist) {
3845  mindist = dist;
3846  mincolor = k;
3847  }
3848  }
3849  tab[i] = mincolor;
3850  }
3851 
3852  /* Reset black and white if available in the colormap.
3853  * The darkest octcube is at octindex 0.
3854  * The lightest octcube is at the max octindex. */
3855  pixcmapGetNearestIndex(cmap, 0, 0, 0, &index);
3856  pixcmapGetColor(cmap, index, &rval, &gval, &bval);
3857  if (rval < 7 && gval < 7 && bval < 7) {
3858  tab[0] = index;
3859  }
3860  pixcmapGetNearestIndex(cmap, 255, 255, 255, &index);
3861  pixcmapGetColor(cmap, index, &rval, &gval, &bval);
3862  if (rval > 248 && gval > 248 && bval > 248) {
3863  tab[(1 << (3 * level)) - 1] = index;
3864  }
3865 
3866  LEPT_FREE(rmap);
3867  LEPT_FREE(gmap);
3868  LEPT_FREE(bmap);
3869  return tab;
3870 }
3871 
3872 
3873 /*------------------------------------------------------------------*
3874  * Strip out unused elements in colormap *
3875  *------------------------------------------------------------------*/
3890 l_ok
3892 {
3893 l_int32 i, j, w, h, d, nc, wpls, val, newval, index, zerofound;
3894 l_int32 rval, gval, bval;
3895 l_uint32 *datas, *lines;
3896 l_int32 *histo, *map1, *map2;
3897 PIXCMAP *cmap, *cmapd;
3898 
3899  if (!pixs)
3900  return ERROR_INT("pixs not defined", __func__, 1);
3901  if ((cmap = pixGetColormap(pixs)) == NULL)
3902  return 0;
3903 
3904  d = pixGetDepth(pixs);
3905  if (d != 2 && d != 4 && d != 8)
3906  return ERROR_INT("d not in {2, 4, 8}", __func__, 1);
3907 
3908  /* Find which indices are actually used */
3909  nc = pixcmapGetCount(cmap);
3910  if ((histo = (l_int32 *)LEPT_CALLOC(nc, sizeof(l_int32))) == NULL)
3911  return ERROR_INT("histo not made", __func__, 1);
3912  pixGetDimensions(pixs, &w, &h, NULL);
3913  wpls = pixGetWpl(pixs);
3914  datas = pixGetData(pixs);
3915  for (i = 0; i < h; i++) {
3916  lines = datas + i * wpls;
3917  for (j = 0; j < w; j++) {
3918  switch (d)
3919  {
3920  case 2:
3921  val = GET_DATA_DIBIT(lines, j);
3922  break;
3923  case 4:
3924  val = GET_DATA_QBIT(lines, j);
3925  break;
3926  case 8:
3927  val = GET_DATA_BYTE(lines, j);
3928  break;
3929  default:
3930  LEPT_FREE(histo);
3931  return ERROR_INT("switch ran off end!", __func__, 1);
3932  }
3933  if (val >= nc) {
3934  L_WARNING("cmap index out of bounds!\n", __func__);
3935  continue;
3936  }
3937  histo[val]++;
3938  }
3939  }
3940 
3941  /* Check if there are any zeroes. If none, quit. */
3942  zerofound = FALSE;
3943  for (i = 0; i < nc; i++) {
3944  if (histo[i] == 0) {
3945  zerofound = TRUE;
3946  break;
3947  }
3948  }
3949  if (!zerofound) {
3950  LEPT_FREE(histo);
3951  return 0;
3952  }
3953 
3954  /* Generate mapping tables between indices */
3955  map1 = (l_int32 *)LEPT_CALLOC(nc, sizeof(l_int32));
3956  map2 = (l_int32 *)LEPT_CALLOC(nc, sizeof(l_int32));
3957  index = 0;
3958  for (i = 0; i < nc; i++) {
3959  if (histo[i] != 0) {
3960  map1[index] = i; /* get old index from new */
3961  map2[i] = index; /* get new index from old */
3962  index++;
3963  }
3964  }
3965 
3966  /* Generate new colormap and attach to pixs */
3967  cmapd = pixcmapCreate(d);
3968  for (i = 0; i < index; i++) {
3969  pixcmapGetColor(cmap, map1[i], &rval, &gval, &bval);
3970  pixcmapAddColor(cmapd, rval, gval, bval);
3971  }
3972  pixSetColormap(pixs, cmapd);
3973 
3974  /* Map pixel (index) values to new cmap */
3975  for (i = 0; i < h; i++) {
3976  lines = datas + i * wpls;
3977  for (j = 0; j < w; j++) {
3978  switch (d)
3979  {
3980  case 2:
3981  val = GET_DATA_DIBIT(lines, j);
3982  newval = map2[val];
3983  SET_DATA_DIBIT(lines, j, newval);
3984  break;
3985  case 4:
3986  val = GET_DATA_QBIT(lines, j);
3987  newval = map2[val];
3988  SET_DATA_QBIT(lines, j, newval);
3989  break;
3990  case 8:
3991  val = GET_DATA_BYTE(lines, j);
3992  newval = map2[val];
3993  SET_DATA_BYTE(lines, j, newval);
3994  break;
3995  default:
3996  LEPT_FREE(histo);
3997  LEPT_FREE(map1);
3998  LEPT_FREE(map2);
3999  return ERROR_INT("switch ran off end!", __func__, 1);
4000  }
4001  }
4002  }
4003 
4004  LEPT_FREE(histo);
4005  LEPT_FREE(map1);
4006  LEPT_FREE(map2);
4007  return 0;
4008 }
4009 
4010 
4011 /*------------------------------------------------------------------*
4012  * Find number of occupied octcubes at the specified level *
4013  *------------------------------------------------------------------*/
4034 l_ok
4036  l_int32 level,
4037  l_int32 mincount,
4038  l_float32 minfract,
4039  l_int32 *pncolors)
4040 {
4041 l_int32 i, j, w, h, d, wpl, ncolors, size, octindex;
4042 l_int32 rval, gval, bval;
4043 l_int32 *carray;
4044 l_uint32 *data, *line, *rtab, *gtab, *btab;
4045 
4046  if (!pncolors)
4047  return ERROR_INT("&ncolors not defined", __func__, 1);
4048  *pncolors = 0;
4049  if (!pix)
4050  return ERROR_INT("pix not defined", __func__, 1);
4051  pixGetDimensions(pix, &w, &h, &d);
4052  if (d != 32)
4053  return ERROR_INT("pix not 32 bpp", __func__, 1);
4054  if (level < 1 || level > 6)
4055  return ERROR_INT("invalid level", __func__, 1);
4056  if ((mincount < 0 && minfract < 0) || (mincount >= 0.0 && minfract >= 0.0))
4057  return ERROR_INT("invalid mincount/minfract", __func__, 1);
4058  if (mincount == 0 || minfract == 0.0)
4059  mincount = 1;
4060  else if (minfract > 0.0)
4061  mincount = L_MIN(1, (l_int32)(minfract * w * h));
4062 
4063  if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
4064  return ERROR_INT("size not returned", __func__, 1);
4065  rtab = gtab = btab = NULL;
4066  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
4067  if ((carray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32))) == NULL) {
4068  L_ERROR("carray not made\n", __func__);
4069  goto cleanup_arrays;
4070  }
4071 
4072  /* Mark the occupied octcube leaves */
4073  data = pixGetData(pix);
4074  wpl = pixGetWpl(pix);
4075  for (i = 0; i < h; i++) {
4076  line = data + i * wpl;
4077  for (j = 0; j < w; j++) {
4078  extractRGBValues(line[j], &rval, &gval, &bval);
4079  octindex = rtab[rval] | gtab[gval] | btab[bval];
4080  carray[octindex]++;
4081  }
4082  }
4083 
4084  /* Count them */
4085  for (i = 0, ncolors = 0; i < size; i++) {
4086  if (carray[i] >= mincount)
4087  ncolors++;
4088  }
4089  *pncolors = ncolors;
4090 
4091 cleanup_arrays:
4092  LEPT_FREE(carray);
4093  LEPT_FREE(rtab);
4094  LEPT_FREE(gtab);
4095  LEPT_FREE(btab);
4096  return 0;
4097 }
#define GET_DATA_QBIT(pdata, n)
Definition: arrayaccess.h:164
#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 GET_DATA_DIBIT(pdata, n)
Definition: arrayaccess.h:145
#define SET_DATA_BYTE(pdata, n, val)
Definition: arrayaccess.h:198
#define SET_DATA_QBIT(pdata, n, val)
Definition: arrayaccess.h:168
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
void pixcmapDestroy(PIXCMAP **pcmap)
pixcmapDestroy()
Definition: colormap.c:272
l_int32 pixcmapGetCount(const PIXCMAP *cmap)
pixcmapGetCount()
Definition: colormap.c:683
PIXCMAP * pixcmapCreate(l_int32 depth)
pixcmapCreate()
Definition: colormap.c:126
l_ok pixcmapGetNearestIndex(PIXCMAP *cmap, l_int32 rval, l_int32 gval, l_int32 bval, l_int32 *pindex)
pixcmapGetNearestIndex()
Definition: colormap.c:1292
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 pixcmapGetMinDepth(PIXCMAP *cmap, l_int32 *pmindepth)
pixcmapGetMinDepth()
Definition: colormap.c:734
l_ok pixcmapGetRankIntensity(PIXCMAP *cmap, l_float32 rankval, l_int32 *pindex)
pixcmapGetRankIntensity()
Definition: colormap.c:1243
l_ok pixcmapToArrays(const PIXCMAP *cmap, l_int32 **prmap, l_int32 **pgmap, l_int32 **pbmap, l_int32 **pamap)
pixcmapToArrays()
Definition: colormap.c:1981
PIXCMAP * pixcmapCopy(const PIXCMAP *cmaps)
pixcmapCopy()
Definition: colormap.c:243
l_ok pixcmapAddColor(PIXCMAP *cmap, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapAddColor()
Definition: colormap.c:403
static void getRGBFromOctcube(l_int32 cubeindex, l_int32 level, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
getRGBFromOctcube()
Definition: colorquant1.c:1495
static l_int32 octreeFindColorCell(l_int32 octindex, CQCELL ***cqcaa, l_int32 *pindex, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
octreeFindColorCell()
Definition: colorquant1.c:1183
PIX * pixFewColorsOctcubeQuant1(PIX *pixs, l_int32 level)
pixFewColorsOctcubeQuant1()
Definition: colorquant1.c:2909
PIX * pixOctreeQuantByPopulation(PIX *pixs, l_int32 level, l_int32 ditherflag)
pixOctreeQuantByPopulation()
Definition: colorquant1.c:1676
l_ok makeRGBToIndexTables(l_int32 cqlevels, l_uint32 **prtab, l_uint32 **pgtab, l_uint32 **pbtab)
makeRGBToIndexTables()
Definition: colorquant1.c:1342
PIX * pixFixedOctcubeQuantGenRGB(PIX *pixs, l_int32 level)
pixFixedOctcubeQuantGenRGB()
Definition: colorquant1.c:3382
NUMA * pixOctcubeHistogram(PIX *pixs, l_int32 level, l_int32 *pncolors)
pixOctcubeHistogram()
Definition: colorquant1.c:3686
PIX * pixOctreeColorQuant(PIX *pixs, l_int32 colors, l_int32 ditherflag)
pixOctreeColorQuant()
Definition: colorquant1.c:536
l_int32 * pixcmapToOctcubeLUT(PIXCMAP *cmap, l_int32 level, l_int32 metric)
pixcmapToOctcubeLUT()
Definition: colorquant1.c:3807
PIX * pixFewColorsOctcubeQuant2(PIX *pixs, l_int32 level, NUMA *na, l_int32 ncolors, l_int32 *pnerrors)
pixFewColorsOctcubeQuant2()
Definition: colorquant1.c:3077
PIX * pixOctreeColorQuantGeneral(PIX *pixs, l_int32 colors, l_int32 ditherflag, l_float32 validthresh, l_float32 colorthresh)
pixOctreeColorQuantGeneral()
Definition: colorquant1.c:600
static void cqcellTreeDestroy(CQCELL ****pcqcaa)
cqcellTreeDestroy()
Definition: colorquant1.c:1280
PIX * pixQuantFromCmap(PIX *pixs, PIXCMAP *cmap, l_int32 mindepth, l_int32 level, l_int32 metric)
pixQuantFromCmap()
Definition: colorquant1.c:3453
l_ok pixRemoveUnusedColors(PIX *pixs)
pixRemoveUnusedColors()
Definition: colorquant1.c:3891
static CQCELL *** cqcellTreeCreate(void)
cqcellTreeCreate()
Definition: colorquant1.c:1253
PIX * pixOctcubeQuantFromCmap(PIX *pixs, PIXCMAP *cmap, l_int32 mindepth, l_int32 level, l_int32 metric)
pixOctcubeQuantFromCmap()
Definition: colorquant1.c:3540
static l_int32 getOctcubeIndices(l_int32 rgbindex, l_int32 level, l_int32 *pbindex, l_int32 *psindex)
getOctcubeIndices()
Definition: colorquant1.c:1572
PIX * pixFewColorsOctcubeQuantMixed(PIX *pixs, l_int32 level, l_int32 darkthresh, l_int32 lightthresh, l_int32 diffthresh, l_float32 minfract, l_int32 maxspan)
pixFewColorsOctcubeQuantMixed()
Definition: colorquant1.c:3264
PIX * pixOctcubeQuantMixedWithGray(PIX *pixs, l_int32 depth, l_int32 graylevels, l_int32 delta)
pixOctcubeQuantMixedWithGray()
Definition: colorquant1.c:2560
static CQCELL *** octreeGenerateAndPrune(PIX *pixs, l_int32 colors, l_int32 reservedcolors, PIXCMAP **pcmap)
octreeGenerateAndPrune()
Definition: colorquant1.c:721
static l_int32 pixDitherOctindexWithCmap(PIX *pixs, PIX *pixd, l_uint32 *rtab, l_uint32 *gtab, l_uint32 *btab, l_int32 *carray, l_int32 difcap)
pixDitherOctindexWithCmap()
Definition: colorquant1.c:1966
PIX * pixFixedOctcubeQuant256(PIX *pixs, l_int32 ditherflag)
pixFixedOctcubeQuant256()
Definition: colorquant1.c:2777
static PIX * pixOctcubeQuantFromCmapLUT(PIX *pixs, PIXCMAP *cmap, l_int32 mindepth, l_int32 *cmaptab, l_uint32 *rtab, l_uint32 *gtab, l_uint32 *btab)
pixOctcubeQuantFromCmapLUT()
Definition: colorquant1.c:3604
l_ok pixNumberOccupiedOctcubes(PIX *pix, l_int32 level, l_int32 mincount, l_float32 minfract, l_int32 *pncolors)
pixNumberOccupiedOctcubes()
Definition: colorquant1.c:4035
static l_int32 octcubeGetCount(l_int32 level, l_int32 *psize)
octcubeGetCount()
Definition: colorquant1.c:1604
void getOctcubeIndexFromRGB(l_int32 rval, l_int32 gval, l_int32 bval, l_uint32 *rtab, l_uint32 *gtab, l_uint32 *btab, l_uint32 *pindex)
getOctcubeIndexFromRGB()
Definition: colorquant1.c:1449
PIX * pixOctreeQuantNumColors(PIX *pixs, l_int32 maxcolors, l_int32 subsample)
pixOctreeQuantNumColors()
Definition: colorquant1.c:2235
static PIX * pixOctreeQuantizePixels(PIX *pixs, CQCELL ***cqcaa, l_int32 ditherflag)
pixOctreeQuantizePixels()
Definition: colorquant1.c:969
PIX * pixGrayQuantFromCmap(PIX *pixs, PIXCMAP *cmap, l_int32 mindepth)
pixGrayQuantFromCmap()
Definition: grayquant.c:2520
l_int32 * makeGrayQuantIndexTable(l_int32 nlevels)
makeGrayQuantIndexTable()
Definition: grayquant.c:1818
PIX * pixGrayQuantFromHisto(PIX *pixd, PIX *pixs, PIX *pixm, l_float32 minfract, l_int32 maxsize)
pixGrayQuantFromHisto()
Definition: grayquant.c:2301
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
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
Definition: heap.c:189
void * lheapRemove(L_HEAP *lh)
lheapRemove()
Definition: heap.c:243
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:460
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:193
l_ok numaSetCount(NUMA *na, l_int32 newcount)
numaSetCount()
Definition: numabasic.c:655
void numaDestroy(NUMA **pna)
numaDestroy()
Definition: numabasic.c:357
l_int32 numaGetCount(NUMA *na)
numaGetCount()
Definition: numabasic.c:630
l_ok numaGetIValue(NUMA *na, l_int32 index, l_int32 *pival)
numaGetIValue()
Definition: numabasic.c:720
l_float32 * numaGetFArray(NUMA *na, l_int32 copyflag)
numaGetFArray()
Definition: numabasic.c:850
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 * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
Definition: pix1.c:315
PIX * pixClone(PIX *pixs)
pixClone()
Definition: pix1.c:582
l_ok pixGetRGBLine(PIX *pixs, l_int32 row, l_uint8 *bufr, l_uint8 *bufg, l_uint8 *bufb)
pixGetRGBLine()
Definition: pix2.c:2870
void setPixelLow(l_uint32 *line, l_int32 x, l_int32 depth, l_uint32 val)
setPixelLow()
Definition: pix2.c:665
l_ok composeRGBPixel(l_int32 rval, l_int32 gval, l_int32 bval, l_uint32 *ppixel)
composeRGBPixel()
Definition: pix2.c:2728
void extractRGBValues(l_uint32 pixel, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
extractRGBValues()
Definition: pix2.c:2793
@ L_NOCOPY
Definition: pix.h:503
@ L_SORT_DECREASING
Definition: pix.h:523
@ L_EUCLIDEAN_DISTANCE
Definition: pix.h:740
@ L_MANHATTAN_DISTANCE
Definition: pix.h:739
PIX * pixConvertTo8(PIX *pixs, l_int32 cmapflag)
pixConvertTo8()
Definition: pixconv.c:3055
PIX * pixScaleBySampling(PIX *pixs, l_float32 scalex, l_float32 scaley)
pixScaleBySampling()
Definition: scale1.c:1306
Definition: heap.h:78
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306