Leptonica  1.82.0
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 
124 /*
125  * <pre>
126  * This data structure is used for pixOctreeColorQuant(),
127  * a color octree that adjusts to the color distribution
128  * in the image that is being quantized. The best settings
129  * are with CqNLevels = 6 and DITHERING set on.
130  *
131  * Notes:
132  * (1) the CTE (color table entry) index is sequentially
133  * assigned as the tree is pruned back
134  * (2) if 'bleaf' == 1, all pixels in that cube have been
135  * assigned to one or more CTEs. But note that if
136  * all 8 subcubes have 'bleaf' == 1, it will have no
137  * pixels left for assignment and will not be a CTE.
138  * (3) 'nleaves', the number of leaves contained at the next
139  * lower level is some number between 0 and 8, inclusive.
140  * If it is zero, it means that all colors within this cube
141  * are part of a single growing cluster that has not yet
142  * been set aside as a leaf. If 'nleaves' > 0, 'bleaf'
143  * will be set to 1 and all pixels not assigned to leaves
144  * at lower levels will be assigned to a CTE here.
145  * (However, as described above, if all pixels are already
146  * assigned, we set 'bleaf' = 1 but do not create a CTE
147  * at this level.)
148  * (4) To keep the maximum color error to a minimum, we
149  * prune the tree back to level 2, and require that
150  * all 64 level 2 cells are CTEs.
151  * (5) We reserve an extra set of colors to prevent running out
152  * of colors during the assignment of the final 64 level 2 cells.
153  * This is more likely to happen with small images.
154  * (6) When we run out of colors, the dithered image can be very
155  * poor, so we additionally prevent dithering if the image
156  * is small.
157  * (7) The color content of the image is measured, and if there
158  * is very little color, it is quantized in grayscale.
159  * </pre>
160  */
162 {
163  l_int32 rc, gc, bc; /* center values */
164  l_int32 n; /* number of samples in this cell */
165  l_int32 index; /* CTE (color table entry) index */
166  l_int32 nleaves; /* # of leaves contained at next lower level */
167  l_int32 bleaf; /* boolean: 0 if not a leaf, 1 if so */
168 };
169 typedef struct ColorQuantCell CQCELL;
170 
171  /* Constants for pixOctreeColorQuant() */
172 static const l_int32 CqNLevels = 5; /* only 4, 5 and 6 are allowed */
173 static const l_int32 CqReservedColors = 64; /* to allow for level 2 */
174  /* remainder CTEs */
175 static const l_int32 ExtraReservedColors = 25; /* to avoid running out */
176 static const l_int32 TreeGenWidth = 350; /* big enough for good stats */
177 static const l_int32 MinDitherSize = 250; /* don't dither if smaller */
178 
179 /*
180  * <pre>
181  * This data structure is used for pixOctreeQuantNumColors(),
182  * a color octree that adjusts in a simple way to the to the color
183  * distribution in the image that is being quantized. It outputs
184  * colormapped images, either 4 bpp or 8 bpp, depending on the
185  * max number of colors and the compression desired.
186  *
187  * The number of samples is saved as a float in the first location,
188  * because this is required to use it as the key that orders the
189  * cells in the priority queue.
190  * </pre>
191  * */
193 {
194  l_float32 n; /* number of samples in this cell */
195  l_int32 octindex; /* octcube index */
196  l_int32 rcum, gcum, bcum; /* cumulative values */
197  l_int32 rval, gval, bval; /* average values */
198 };
199 typedef struct OctcubeQuantCell OQCELL;
200 
201 /*
202  * <pre>
203  * This data structure is using for heap sorting octcubes
204  * by population. Sort order is decreasing.
205  * </pre>
206  */
208 {
209  l_float32 npix; /* parameter on which to sort */
210  l_int32 index; /* octcube index at assigned level */
211  l_int32 rval; /* mean red value of pixels in octcube */
212  l_int32 gval; /* mean green value of pixels in octcube */
213  l_int32 bval; /* mean blue value of pixels in octcube */
214 };
215 typedef struct L_OctcubePop L_OCTCUBE_POP;
216 
217 /*
218  * <pre>
219  * In pixDitherOctindexWithCmap(), we use these default values.
220  To get the max value of 'dif' in the dithering color transfer,
221  divide these "DIF_CAP" values by 8. However, a value of
222  0 means that there is no cap (infinite cap). A very small
223  value is used for POP_DIF_CAP because dithering on the population
224  generated colormap can be unstable without a tight cap.
225  * </pre>
226  */
227 
228 static const l_int32 FIXED_DIF_CAP = 0;
229 static const l_int32 POP_DIF_CAP = 40;
230 
231 
232  /* Static octree helper function */
233 static l_int32 octreeFindColorCell(l_int32 octindex, CQCELL ***cqcaa,
234  l_int32 *pindex, l_int32 *prval,
235  l_int32 *pgval, l_int32 *pbval);
236 
237  /* Static cqcell functions */
238 static CQCELL ***octreeGenerateAndPrune(PIX *pixs, l_int32 colors,
239  l_int32 reservedcolors,
240  PIXCMAP **pcmap);
241 static PIX *pixOctreeQuantizePixels(PIX *pixs, CQCELL ***cqcaa,
242  l_int32 ditherflag);
243 static CQCELL ***cqcellTreeCreate(void);
244 static void cqcellTreeDestroy(CQCELL ****pcqcaa);
245 
246  /* Static helper octcube index functions */
247 static void getRGBFromOctcube(l_int32 cubeindex, l_int32 level,
248  l_int32 *prval, l_int32 *pgval, l_int32 *pbval);
249 static l_int32 getOctcubeIndices(l_int32 rgbindex, l_int32 level,
250  l_int32 *pbindex, l_int32 *psindex);
251 static l_int32 octcubeGetCount(l_int32 level, l_int32 *psize);
252 
253  /* Static function to perform octcube-indexed dithering */
254 static l_int32 pixDitherOctindexWithCmap(PIX *pixs, PIX *pixd, l_uint32 *rtab,
255  l_uint32 *gtab, l_uint32 *btab,
256  l_int32 *carray, l_int32 difcap);
257 
258  /* Static function to perform octcube-based quantizing from colormap */
259 static PIX *pixOctcubeQuantFromCmapLUT(PIX *pixs, PIXCMAP *cmap,
260  l_int32 mindepth, l_int32 *cmaptab,
261  l_uint32 *rtab, l_uint32 *gtab,
262  l_uint32 *btab);
263 
264 #ifndef NO_CONSOLE_IO
265 #define DEBUG_COLORQUANT 0
266 #define DEBUG_OCTINDEX 0
267 #define DEBUG_OCTCUBE_CMAP 0
268 #define DEBUG_POP 0
269 #define DEBUG_FEW_COLORS 0
270 #define PRINT_OCTCUBE_STATS 0
271 #endif /* ~NO_CONSOLE_IO */
272 
273 /*-------------------------------------------------------------------------*
274  * Two-pass adaptive octree color quantization *
275  *-------------------------------------------------------------------------*/
534 PIX *
536  l_int32 colors,
537  l_int32 ditherflag)
538 {
539  PROCNAME("pixOctreeColorQuant");
540 
541  if (!pixs)
542  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
543  if (pixGetDepth(pixs) != 32)
544  return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
545  if (colors < 128 || colors > 240) /* further restricted */
546  return (PIX *)ERROR_PTR("colors must be in [128, 240]", procName, NULL);
547 
548  return pixOctreeColorQuantGeneral(pixs, colors, ditherflag, 0.01, 0.01);
549 }
550 
551 
600 PIX *
602  l_int32 colors,
603  l_int32 ditherflag,
604  l_float32 validthresh,
605  l_float32 colorthresh)
606 {
607 l_int32 w, h, minside, factor, index, rval, gval, bval;
608 l_float32 scalefactor;
609 l_float32 pixfract; /* fraction neither near white nor black */
610 l_float32 colorfract; /* fraction with color of the pixfract population */
611 CQCELL ***cqcaa;
612 PIX *pixd, *pixsub;
613 PIXCMAP *cmap;
614 
615  PROCNAME("pixOctreeColorQuantGeneral");
616 
617  if (!pixs)
618  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
619  if (pixGetDepth(pixs) != 32)
620  return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
621  if (colors < 128 || colors > 240)
622  return (PIX *)ERROR_PTR("colors must be in [128, 240]", procName, NULL);
623 
624  /* Determine if the image has sufficient color content for
625  * octree quantization, based on the input thresholds.
626  * If pixfract << 1, most pixels are close to black or white.
627  * If colorfract << 1, the pixels that are not near
628  * black or white have very little color.
629  * If with insufficient color, quantize with a grayscale colormap. */
630  pixGetDimensions(pixs, &w, &h, NULL);
631  if (validthresh > 0.0 && colorthresh > 0.0) {
632  minside = L_MIN(w, h);
633  factor = L_MAX(1, minside / 400);
634  pixColorFraction(pixs, 20, 244, 20, factor, &pixfract, &colorfract);
635  if (pixfract * colorfract < validthresh * colorthresh) {
636  L_INFO("\n Pixel fraction neither white nor black = %6.3f"
637  "\n Color fraction of those pixels = %6.3f"
638  "\n Quantizing to 8 bpp gray\n",
639  procName, pixfract, colorfract);
640  return pixConvertTo8(pixs, 1);
641  }
642  } else {
643  L_INFO("\n Process in color by default\n", procName);
644  }
645 
646  /* Conditionally subsample to speed up the first pass */
647  if (w > TreeGenWidth) {
648  scalefactor = (l_float32)TreeGenWidth / (l_float32)w;
649  pixsub = pixScaleBySampling(pixs, scalefactor, scalefactor);
650  } else {
651  pixsub = pixClone(pixs);
652  }
653 
654  /* Drop the number of requested colors if image is very small */
655  if (w < MinDitherSize && h < MinDitherSize)
656  colors = L_MIN(colors, 220);
657 
658  /* Make the pruned octree */
659  cqcaa = octreeGenerateAndPrune(pixsub, colors, CqReservedColors, &cmap);
660  if (!cqcaa) {
661  pixDestroy(&pixsub);
662  return (PIX *)ERROR_PTR("tree not made", procName, NULL);
663  }
664 #if DEBUG_COLORQUANT
665  L_INFO(" Colors requested = %d\n", procName, colors);
666  L_INFO(" Actual colors = %d\n", procName, cmap->n);
667 #endif /* DEBUG_COLORQUANT */
668 
669  /* Do not dither if image is very small */
670  if (w < MinDitherSize && h < MinDitherSize && ditherflag == 1) {
671  L_INFO("Small image: dithering turned off\n", procName);
672  ditherflag = 0;
673  }
674 
675  /* Traverse tree from root, looking for lowest cube
676  * that is a leaf, and set dest pix value to its
677  * colortable index */
678  if ((pixd = pixOctreeQuantizePixels(pixs, cqcaa, ditherflag)) == NULL) {
679  pixDestroy(&pixsub);
680  cqcellTreeDestroy(&cqcaa);
681  return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
682  }
683 
684  /* Attach colormap and copy res */
685  pixSetColormap(pixd, cmap);
686  pixCopyResolution(pixd, pixs);
687  pixCopyInputFormat(pixd, pixs);
688 
689  /* Force darkest color to black if each component <= 4 */
690  pixcmapGetRankIntensity(cmap, 0.0, &index);
691  pixcmapGetColor(cmap, index, &rval, &gval, &bval);
692  if (rval < 5 && gval < 5 && bval < 5)
693  pixcmapResetColor(cmap, index, 0, 0, 0);
694 
695  /* Force lightest color to white if each component >= 252 */
696  pixcmapGetRankIntensity(cmap, 1.0, &index);
697  pixcmapGetColor(cmap, index, &rval, &gval, &bval);
698  if (rval > 251 && gval > 251 && bval > 251)
699  pixcmapResetColor(cmap, index, 255, 255, 255);
700 
701  cqcellTreeDestroy(&cqcaa);
702  pixDestroy(&pixsub);
703  return pixd;
704 }
705 
706 
723 static CQCELL ***
725  l_int32 colors,
726  l_int32 reservedcolors,
727  PIXCMAP **pcmap)
728 {
729 l_int32 rval, gval, bval, cindex;
730 l_int32 level, ncells, octindex;
731 l_int32 w, h, wpls;
732 l_int32 i, j, isub;
733 l_int32 npix; /* number of remaining pixels to be assigned */
734 l_int32 ncolor; /* number of remaining color cells to be used */
735 l_int32 ppc; /* ave number of pixels left for each color cell */
736 l_int32 rv, gv, bv;
737 l_float32 thresholdFactor[] = {0.01f, 0.01f, 1.0f, 1.0f, 1.0f, 1.0f};
738 l_float32 thresh; /* factor of ppc for this level */
739 l_uint32 *datas, *lines;
740 l_uint32 *rtab, *gtab, *btab;
741 CQCELL ***cqcaa; /* one array for each octree level */
742 CQCELL **cqca, **cqcasub;
743 CQCELL *cqc, *cqcsub;
744 PIXCMAP *cmap;
745 NUMA *nat; /* accumulates levels for threshold cells */
746 NUMA *nar; /* accumulates levels for residual cells */
747 
748  PROCNAME("octreeGenerateAndPrune");
749 
750  if (!pixs)
751  return (CQCELL ***)ERROR_PTR("pixs not defined", procName, NULL);
752  if (pixGetDepth(pixs) != 32)
753  return (CQCELL ***)ERROR_PTR("pixs must be 32 bpp", procName, NULL);
754  if (colors < 128 || colors > 256)
755  return (CQCELL ***)ERROR_PTR("colors not in [128,256]", procName, NULL);
756  if (!pcmap)
757  return (CQCELL ***)ERROR_PTR("&cmap not defined", procName, NULL);
758 
759  if ((cqcaa = cqcellTreeCreate()) == NULL)
760  return (CQCELL ***)ERROR_PTR("cqcaa not made", procName, NULL);
761 
762  /* Make the canonical index tables */
763  rtab = gtab = btab = NULL;
764  makeRGBToIndexTables(CqNLevels, &rtab, &gtab, &btab);
765 
766  /* Generate an 8 bpp cmap (max size 256) */
767  cmap = pixcmapCreate(8);
768  *pcmap = cmap;
769 
770  pixGetDimensions(pixs, &w, &h, NULL);
771  npix = w * h; /* initialize to all pixels */
772  ncolor = colors - reservedcolors - ExtraReservedColors;
773  ppc = npix / ncolor;
774  datas = pixGetData(pixs);
775  wpls = pixGetWpl(pixs);
776 
777  /* Accumulate the centers of each cluster at level CqNLevels */
778  ncells = 1 << (3 * CqNLevels);
779  cqca = cqcaa[CqNLevels];
780  for (i = 0; i < h; i++) {
781  lines = datas + i * wpls;
782  for (j = 0; j < w; j++) {
783  extractRGBValues(lines[j], &rval, &gval, &bval);
784  octindex = rtab[rval] | gtab[gval] | btab[bval];
785  cqc = cqca[octindex];
786  cqc->n++;
787  }
788  }
789 
790  /* Arrays for storing statistics */
791  nat = numaCreate(0);
792  nar = numaCreate(0);
793 
794  /* Prune back from the lowest level and generate the colormap */
795  for (level = CqNLevels - 1; level >= 2; level--) {
796  thresh = thresholdFactor[level];
797  cqca = cqcaa[level];
798  cqcasub = cqcaa[level + 1];
799  ncells = 1 << (3 * level);
800  for (i = 0; i < ncells; i++) { /* i is octindex at level */
801  cqc = cqca[i];
802  for (j = 0; j < 8; j++) { /* check all subnodes */
803  isub = 8 * i + j; /* isub is octindex at level+1 */
804  cqcsub = cqcasub[isub];
805  if (cqcsub->bleaf == 1) { /* already a leaf? */
806  cqc->nleaves++; /* count the subcube leaves */
807  continue;
808  }
809  if (cqcsub->n >= thresh * ppc) { /* make it a true leaf? */
810  cqcsub->bleaf = 1;
811  if (cmap->n < 256) {
812  cqcsub->index = cmap->n; /* assign the color index */
813  getRGBFromOctcube(isub, level + 1, &rv, &gv, &bv);
814  pixcmapAddColor(cmap, rv, gv, bv);
815 #if 1 /* save values */
816  cqcsub->rc = rv;
817  cqcsub->gc = gv;
818  cqcsub->bc = bv;
819 #endif
820  } else {
821  /* This doesn't seem to happen. Do something. */
822  L_ERROR("assigning pixels to wrong color\n", procName);
823  pixcmapGetNearestIndex(cmap, 128, 128, 128, &cindex);
824  cqcsub->index = cindex; /* assign to the nearest */
825  pixcmapGetColor(cmap, cindex, &rval, &gval, &bval);
826  cqcsub->rc = rval;
827  cqcsub->gc = gval;
828  cqcsub->bc = bval;
829  }
830  cqc->nleaves++;
831  npix -= cqcsub->n;
832  ncolor--;
833  if (ncolor > 0)
834  ppc = npix / ncolor;
835  else if (ncolor + reservedcolors > 0)
836  ppc = npix / (ncolor + reservedcolors);
837  else
838  ppc = 1000000; /* make it big */
839  numaAddNumber(nat, level + 1);
840 
841 #if DEBUG_OCTCUBE_CMAP
842  lept_stderr("Exceeds threshold: colors used = %d, colors remaining = %d\n",
843  cmap->n, ncolor + reservedcolors);
844  lept_stderr(" cell with %d pixels, npix = %d, ppc = %d\n",
845  cqcsub->n, npix, ppc);
846  lept_stderr(" index = %d, level = %d, subindex = %d\n",
847  i, level, j);
848  lept_stderr(" rv = %d, gv = %d, bv = %d\n", rv, gv, bv);
849 #endif /* DEBUG_OCTCUBE_CMAP */
850 
851  }
852  }
853  if (cqc->nleaves > 0 || level == 2) { /* make the cube a leaf now */
854  cqc->bleaf = 1;
855  if (cqc->nleaves < 8) { /* residual CTE cube: acquire the
856  * remaining pixels */
857  for (j = 0; j < 8; j++) { /* check all subnodes */
858  isub = 8 * i + j;
859  cqcsub = cqcasub[isub];
860  if (cqcsub->bleaf == 0) /* absorb */
861  cqc->n += cqcsub->n;
862  }
863  if (cmap->n < 256) {
864  cqc->index = cmap->n; /* assign the color index */
865  getRGBFromOctcube(i, level, &rv, &gv, &bv);
866  pixcmapAddColor(cmap, rv, gv, bv);
867 #if 1 /* save values */
868  cqc->rc = rv;
869  cqc->gc = gv;
870  cqc->bc = bv;
871 #endif
872  } else {
873  L_WARNING("possibly assigned pixels to wrong color\n",
874  procName);
875  /* This is very bad. It will only cause trouble
876  * with dithering, and we try to avoid it with
877  * ExtraReservedColors. */
878  pixcmapGetNearestIndex(cmap, rv, gv, bv, &cindex);
879  cqc->index = cindex; /* assign to the nearest */
880  pixcmapGetColor(cmap, cindex, &rval, &gval, &bval);
881  cqc->rc = rval;
882  cqc->gc = gval;
883  cqc->bc = bval;
884  }
885  npix -= cqc->n;
886  ncolor--;
887  if (ncolor > 0)
888  ppc = npix / ncolor;
889  else if (ncolor + reservedcolors > 0)
890  ppc = npix / (ncolor + reservedcolors);
891  else
892  ppc = 1000000; /* make it big */
893  numaAddNumber(nar, level);
894 
895 #if DEBUG_OCTCUBE_CMAP
896  lept_stderr("By remainder: colors used = %d, colors remaining = %d\n",
897  cmap->n, ncolor + reservedcolors);
898  lept_stderr(" cell with %d pixels, npix = %d, ppc = %d\n",
899  cqc->n, npix, ppc);
900  lept_stderr(" index = %d, level = %d\n", i, level);
901  lept_stderr(" rv = %d, gv = %d, bv = %d\n", rv, gv, bv);
902 #endif /* DEBUG_OCTCUBE_CMAP */
903 
904  }
905  } else { /* absorb all the subpixels but don't make it a leaf */
906  for (j = 0; j < 8; j++) { /* absorb from all subnodes */
907  isub = 8 * i + j;
908  cqcsub = cqcasub[isub];
909  cqc->n += cqcsub->n;
910  }
911  }
912  }
913  }
914 
915 #if PRINT_OCTCUBE_STATS
916 {
917 l_int32 tc[] = {0, 0, 0, 0, 0, 0, 0};
918 l_int32 rc[] = {0, 0, 0, 0, 0, 0, 0};
919 l_int32 nt, nr, ival;
920 
921  nt = numaGetCount(nat);
922  nr = numaGetCount(nar);
923  for (i = 0; i < nt; i++) {
924  numaGetIValue(nat, i, &ival);
925  tc[ival]++;
926  }
927  for (i = 0; i < nr; i++) {
928  numaGetIValue(nar, i, &ival);
929  rc[ival]++;
930  }
931  lept_stderr(" Threshold cells formed: %d\n", nt);
932  for (i = 1; i < CqNLevels + 1; i++)
933  lept_stderr(" level %d: %d\n", i, tc[i]);
934  lept_stderr("\n Residual cells formed: %d\n", nr);
935  for (i = 0; i < CqNLevels ; i++)
936  lept_stderr(" level %d: %d\n", i, rc[i]);
937 }
938 #endif /* PRINT_OCTCUBE_STATS */
939 
940  numaDestroy(&nat);
941  numaDestroy(&nar);
942  LEPT_FREE(rtab);
943  LEPT_FREE(gtab);
944  LEPT_FREE(btab);
945 
946  return cqcaa;
947 }
948 
949 
973 static PIX *
975  CQCELL ***cqcaa,
976  l_int32 ditherflag)
977 {
978 l_uint8 *bufu8r, *bufu8g, *bufu8b;
979 l_int32 rval, gval, bval;
980 l_int32 octindex, index;
981 l_int32 val1, val2, val3, dif;
982 l_int32 w, h, wpls, wpld, i, j, success;
983 l_int32 rc, gc, bc;
984 l_int32 *buf1r, *buf1g, *buf1b, *buf2r, *buf2g, *buf2b;
985 l_uint32 *rtab, *gtab, *btab;
986 l_uint32 *datas, *datad, *lines, *lined;
987 PIX *pixd;
988 
989  PROCNAME("pixOctreeQuantizePixels");
990 
991  if (!pixs)
992  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
993  if (pixGetDepth(pixs) != 32)
994  return (PIX *)ERROR_PTR("pixs must be 32 bpp", procName, NULL);
995  if (!cqcaa)
996  return (PIX *)ERROR_PTR("cqcaa not defined", procName, NULL);
997 
998  /* Make output 8 bpp palette image */
999  pixGetDimensions(pixs, &w, &h, NULL);
1000  datas = pixGetData(pixs);
1001  wpls = pixGetWpl(pixs);
1002  if ((pixd = pixCreate(w, h, 8)) == NULL)
1003  return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
1004  pixCopyResolution(pixd, pixs);
1005  pixCopyInputFormat(pixd, pixs);
1006  datad = pixGetData(pixd);
1007  wpld = pixGetWpl(pixd);
1008 
1009  /* Make the canonical index tables */
1010  rtab = gtab = btab = NULL;
1011  makeRGBToIndexTables(CqNLevels, &rtab, &gtab, &btab);
1012 
1013  /* Traverse tree from root, looking for lowest cube
1014  * that is a leaf, and set dest pix to its
1015  * colortable index value. The results are far
1016  * better when dithering to get a more accurate
1017  * average color. */
1018  if (ditherflag == 0) { /* no dithering */
1019  for (i = 0; i < h; i++) {
1020  lines = datas + i * wpls;
1021  lined = datad + i * wpld;
1022  for (j = 0; j < w; j++) {
1023  extractRGBValues(lines[j], &rval, &gval, &bval);
1024  octindex = rtab[rval] | gtab[gval] | btab[bval];
1025  octreeFindColorCell(octindex, cqcaa, &index, &rc, &gc, &bc);
1026  SET_DATA_BYTE(lined, j, index);
1027  }
1028  }
1029  } else { /* Dither */
1030  success = TRUE;
1031  bufu8r = bufu8g = bufu8b = NULL;
1032  buf1r = buf1g = buf1b = buf2r = buf2g = buf2b = NULL;
1033  bufu8r = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1034  bufu8g = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1035  bufu8b = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
1036  buf1r = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1037  buf1g = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1038  buf1b = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1039  buf2r = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1040  buf2g = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1041  buf2b = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
1042  if (!bufu8r || !bufu8g || !bufu8b || !buf1r || !buf1g ||
1043  !buf1b || !buf2r || !buf2g || !buf2b) {
1044  L_ERROR("buffer not made\n", procName);
1045  success = FALSE;
1046  goto buffer_cleanup;
1047  }
1048 
1049  /* Start by priming buf2; line 1 is above line 2 */
1050  pixGetRGBLine(pixs, 0, bufu8r, bufu8g, bufu8b);
1051  for (j = 0; j < w; j++) {
1052  buf2r[j] = 64 * bufu8r[j];
1053  buf2g[j] = 64 * bufu8g[j];
1054  buf2b[j] = 64 * bufu8b[j];
1055  }
1056 
1057  for (i = 0; i < h - 1; i++) {
1058  /* Swap data 2 --> 1, and read in new line 2 */
1059  memcpy(buf1r, buf2r, 4 * w);
1060  memcpy(buf1g, buf2g, 4 * w);
1061  memcpy(buf1b, buf2b, 4 * w);
1062  pixGetRGBLine(pixs, i + 1, bufu8r, bufu8g, bufu8b);
1063  for (j = 0; j < w; j++) {
1064  buf2r[j] = 64 * bufu8r[j];
1065  buf2g[j] = 64 * bufu8g[j];
1066  buf2b[j] = 64 * bufu8b[j];
1067  }
1068 
1069  /* Dither */
1070  lined = datad + i * wpld;
1071  for (j = 0; j < w - 1; j++) {
1072  rval = buf1r[j] / 64;
1073  gval = buf1g[j] / 64;
1074  bval = buf1b[j] / 64;
1075  octindex = rtab[rval] | gtab[gval] | btab[bval];
1076  octreeFindColorCell(octindex, cqcaa, &index, &rc, &gc, &bc);
1077  SET_DATA_BYTE(lined, j, index);
1078 
1079  dif = buf1r[j] / 8 - 8 * rc;
1080  if (dif != 0) {
1081  val1 = buf1r[j + 1] + 3 * dif;
1082  val2 = buf2r[j] + 3 * dif;
1083  val3 = buf2r[j + 1] + 2 * dif;
1084  if (dif > 0) {
1085  buf1r[j + 1] = L_MIN(16383, val1);
1086  buf2r[j] = L_MIN(16383, val2);
1087  buf2r[j + 1] = L_MIN(16383, val3);
1088  } else {
1089  buf1r[j + 1] = L_MAX(0, val1);
1090  buf2r[j] = L_MAX(0, val2);
1091  buf2r[j + 1] = L_MAX(0, val3);
1092  }
1093  }
1094 
1095  dif = buf1g[j] / 8 - 8 * gc;
1096  if (dif != 0) {
1097  val1 = buf1g[j + 1] + 3 * dif;
1098  val2 = buf2g[j] + 3 * dif;
1099  val3 = buf2g[j + 1] + 2 * dif;
1100  if (dif > 0) {
1101  buf1g[j + 1] = L_MIN(16383, val1);
1102  buf2g[j] = L_MIN(16383, val2);
1103  buf2g[j + 1] = L_MIN(16383, val3);
1104  } else {
1105  buf1g[j + 1] = L_MAX(0, val1);
1106  buf2g[j] = L_MAX(0, val2);
1107  buf2g[j + 1] = L_MAX(0, val3);
1108  }
1109  }
1110 
1111  dif = buf1b[j] / 8 - 8 * bc;
1112  if (dif != 0) {
1113  val1 = buf1b[j + 1] + 3 * dif;
1114  val2 = buf2b[j] + 3 * dif;
1115  val3 = buf2b[j + 1] + 2 * dif;
1116  if (dif > 0) {
1117  buf1b[j + 1] = L_MIN(16383, val1);
1118  buf2b[j] = L_MIN(16383, val2);
1119  buf2b[j + 1] = L_MIN(16383, val3);
1120  } else {
1121  buf1b[j + 1] = L_MAX(0, val1);
1122  buf2b[j] = L_MAX(0, val2);
1123  buf2b[j + 1] = L_MAX(0, val3);
1124  }
1125  }
1126  }
1127 
1128  /* Get last pixel in row; no downward propagation */
1129  rval = buf1r[w - 1] / 64;
1130  gval = buf1g[w - 1] / 64;
1131  bval = buf1b[w - 1] / 64;
1132  octindex = rtab[rval] | gtab[gval] | btab[bval];
1133  octreeFindColorCell(octindex, cqcaa, &index, &rc, &gc, &bc);
1134  SET_DATA_BYTE(lined, w - 1, index);
1135  }
1136 
1137  /* Get last row of pixels; no leftward propagation */
1138  lined = datad + (h - 1) * wpld;
1139  for (j = 0; j < w; j++) {
1140  rval = buf2r[j] / 64;
1141  gval = buf2g[j] / 64;
1142  bval = buf2b[j] / 64;
1143  octindex = rtab[rval] | gtab[gval] | btab[bval];
1144  octreeFindColorCell(octindex, cqcaa, &index, &rc, &gc, &bc);
1145  SET_DATA_BYTE(lined, j, index);
1146  }
1147 
1148 buffer_cleanup:
1149  LEPT_FREE(bufu8r);
1150  LEPT_FREE(bufu8g);
1151  LEPT_FREE(bufu8b);
1152  LEPT_FREE(buf1r);
1153  LEPT_FREE(buf1g);
1154  LEPT_FREE(buf1b);
1155  LEPT_FREE(buf2r);
1156  LEPT_FREE(buf2g);
1157  LEPT_FREE(buf2b);
1158  if (!success) pixDestroy(&pixd);
1159  }
1160 
1161  LEPT_FREE(rtab);
1162  LEPT_FREE(gtab);
1163  LEPT_FREE(btab);
1164  return pixd;
1165 }
1166 
1167 
1189 static l_int32
1190 octreeFindColorCell(l_int32 octindex,
1191  CQCELL ***cqcaa,
1192  l_int32 *pindex,
1193  l_int32 *prval,
1194  l_int32 *pgval,
1195  l_int32 *pbval)
1196 {
1197 l_int32 level;
1198 l_int32 baseindex, subindex;
1199 CQCELL *cqc, *cqcsub;
1200 
1201  /* Use rgb values stored in the cubes; a little faster */
1202  for (level = 2; level < CqNLevels; level++) {
1203  getOctcubeIndices(octindex, level, &baseindex, &subindex);
1204  cqc = cqcaa[level][baseindex];
1205  cqcsub = cqcaa[level + 1][subindex];
1206  if (cqcsub->bleaf == 0) { /* use cell at level above */
1207  *pindex = cqc->index;
1208  *prval = cqc->rc;
1209  *pgval = cqc->gc;
1210  *pbval = cqc->bc;
1211  break;
1212  } else if (level == CqNLevels - 1) { /* reached the bottom */
1213  *pindex = cqcsub->index;
1214  *prval = cqcsub->rc;
1215  *pgval = cqcsub->gc;
1216  *pbval = cqcsub->bc;
1217  break;
1218  }
1219  }
1220 
1221 #if 0
1222  /* Generate rgb values for each cube on the fly; slower */
1223  for (level = 2; level < CqNLevels; level++) {
1224  l_int32 rv, gv, bv;
1225  getOctcubeIndices(octindex, level, &baseindex, &subindex);
1226  cqc = cqcaa[level][baseindex];
1227  cqcsub = cqcaa[level + 1][subindex];
1228  if (cqcsub->bleaf == 0) { /* use cell at level above */
1229  getRGBFromOctcube(baseindex, level, &rv, &gv, &bv);
1230  *pindex = cqc->index;
1231  *prval = rv;
1232  *pgval = gv;
1233  *pbval = bv;
1234  break;
1235  } else if (level == CqNLevels - 1) { /* reached the bottom */
1236  getRGBFromOctcube(subindex, level + 1, &rv, &gv, &bv);
1237  *pindex = cqcsub->index;
1238  *prval = rv;
1239  *pgval = gv;
1240  *pbval = bv;
1241  break;
1242  }
1243  }
1244 #endif
1245 
1246  return 0;
1247 }
1248 
1249 
1250 
1251 /*------------------------------------------------------------------*
1252  * Helper cqcell functions *
1253  *------------------------------------------------------------------*/
1259 static CQCELL ***
1261 {
1262 l_int32 level, ncells, i;
1263 CQCELL ***cqcaa;
1264 CQCELL **cqca; /* one array for each octree level */
1265 
1266  PROCNAME("cqcellTreeCreate");
1267 
1268  /* Make array of accumulation cell arrays from levels 1 to 5 */
1269  cqcaa = (CQCELL ***)LEPT_CALLOC(CqNLevels + 1, sizeof(CQCELL **));
1270  for (level = 0; level <= CqNLevels; level++) {
1271  ncells = 1 << (3 * level);
1272  cqca = (CQCELL **)LEPT_CALLOC(ncells, sizeof(CQCELL *));
1273  cqcaa[level] = cqca;
1274  for (i = 0; i < ncells; i++) {
1275  cqca[i] = (CQCELL *)LEPT_CALLOC(1, sizeof(CQCELL));
1276  }
1277  }
1278 
1279  return cqcaa;
1280 }
1281 
1282 
1288 static void
1290 {
1291 l_int32 level, ncells, i;
1292 CQCELL ***cqcaa;
1293 CQCELL **cqca;
1294 
1295  PROCNAME("cqcellTreeDestroy");
1296 
1297  if (pcqcaa == NULL) {
1298  L_WARNING("ptr address is NULL\n", procName);
1299  return;
1300  }
1301 
1302  if ((cqcaa = *pcqcaa) == NULL)
1303  return;
1304 
1305  for (level = 0; level <= CqNLevels; level++) {
1306  cqca = cqcaa[level];
1307  ncells = 1 << (3 * level);
1308  for (i = 0; i < ncells; i++)
1309  LEPT_FREE(cqca[i]);
1310  LEPT_FREE(cqca);
1311  }
1312  LEPT_FREE(cqcaa);
1313  *pcqcaa = NULL;
1314 
1315  return;
1316 }
1317 
1318 
1319 
1320 /*------------------------------------------------------------------*
1321  * Helper index functions *
1322  *------------------------------------------------------------------*/
1352 l_ok
1353 makeRGBToIndexTables(l_int32 cqlevels,
1354  l_uint32 **prtab,
1355  l_uint32 **pgtab,
1356  l_uint32 **pbtab)
1357 {
1358 l_int32 i;
1359 l_uint32 *rtab, *gtab, *btab;
1360 
1361  PROCNAME("makeRGBToIndexTables");
1362 
1363  if (cqlevels < 1 || cqlevels > 6)
1364  return ERROR_INT("cqlevels must be in {1,...6}", procName, 1);
1365  if (!prtab || !pgtab || !pbtab)
1366  return ERROR_INT("not all &tabs defined", procName, 1);
1367 
1368  rtab = (l_uint32 *)LEPT_CALLOC(256, sizeof(l_uint32));
1369  gtab = (l_uint32 *)LEPT_CALLOC(256, sizeof(l_uint32));
1370  btab = (l_uint32 *)LEPT_CALLOC(256, sizeof(l_uint32));
1371  if (!rtab || !gtab || !btab)
1372  return ERROR_INT("calloc fail for tab", procName, 1);
1373  *prtab = rtab;
1374  *pgtab = gtab;
1375  *pbtab = btab;
1376 
1377  switch (cqlevels)
1378  {
1379  case 1:
1380  for (i = 0; i < 256; i++) {
1381  rtab[i] = (i >> 5) & 0x0004;
1382  gtab[i] = (i >> 6) & 0x0002;
1383  btab[i] = (i >> 7);
1384  }
1385  break;
1386  case 2:
1387  for (i = 0; i < 256; i++) {
1388  rtab[i] = ((i >> 2) & 0x0020) | ((i >> 4) & 0x0004);
1389  gtab[i] = ((i >> 3) & 0x0010) | ((i >> 5) & 0x0002);
1390  btab[i] = ((i >> 4) & 0x0008) | ((i >> 6) & 0x0001);
1391  }
1392  break;
1393  case 3:
1394  for (i = 0; i < 256; i++) {
1395  rtab[i] = ((i << 1) & 0x0100) | ((i >> 1) & 0x0020) |
1396  ((i >> 3) & 0x0004);
1397  gtab[i] = (i & 0x0080) | ((i >> 2) & 0x0010) |
1398  ((i >> 4) & 0x0002);
1399  btab[i] = ((i >> 1) & 0x0040) | ((i >> 3) & 0x0008) |
1400  ((i >> 5) & 0x0001);
1401  }
1402  break;
1403  case 4:
1404  for (i = 0; i < 256; i++) {
1405  rtab[i] = ((i << 4) & 0x0800) | ((i << 2) & 0x0100) |
1406  (i & 0x0020) | ((i >> 2) & 0x0004);
1407  gtab[i] = ((i << 3) & 0x0400) | ((i << 1) & 0x0080) |
1408  ((i >> 1) & 0x0010) | ((i >> 3) & 0x0002);
1409  btab[i] = ((i << 2) & 0x0200) | (i & 0x0040) |
1410  ((i >> 2) & 0x0008) | ((i >> 4) & 0x0001);
1411  }
1412  break;
1413  case 5:
1414  for (i = 0; i < 256; i++) {
1415  rtab[i] = ((i << 7) & 0x4000) | ((i << 5) & 0x0800) |
1416  ((i << 3) & 0x0100) | ((i << 1) & 0x0020) |
1417  ((i >> 1) & 0x0004);
1418  gtab[i] = ((i << 6) & 0x2000) | ((i << 4) & 0x0400) |
1419  ((i << 2) & 0x0080) | (i & 0x0010) |
1420  ((i >> 2) & 0x0002);
1421  btab[i] = ((i << 5) & 0x1000) | ((i << 3) & 0x0200) |
1422  ((i << 1) & 0x0040) | ((i >> 1) & 0x0008) |
1423  ((i >> 3) & 0x0001);
1424  }
1425  break;
1426  case 6:
1427  for (i = 0; i < 256; i++) {
1428  rtab[i] = ((i << 10) & 0x20000) | ((i << 8) & 0x4000) |
1429  ((i << 6) & 0x0800) | ((i << 4) & 0x0100) |
1430  ((i << 2) & 0x0020) | (i & 0x0004);
1431  gtab[i] = ((i << 9) & 0x10000) | ((i << 7) & 0x2000) |
1432  ((i << 5) & 0x0400) | ((i << 3) & 0x0080) |
1433  ((i << 1) & 0x0010) | ((i >> 1) & 0x0002);
1434  btab[i] = ((i << 8) & 0x8000) | ((i << 6) & 0x1000) |
1435  ((i << 4) & 0x0200) | ((i << 2) & 0x0040) |
1436  (i & 0x0008) | ((i >> 2) & 0x0001);
1437  }
1438  break;
1439  default:
1440  ERROR_INT("cqlevels not in [1...6]", procName, 1);
1441  break;
1442  }
1443 
1444  return 0;
1445 }
1446 
1447 
1461 void
1463  l_int32 gval,
1464  l_int32 bval,
1465  l_uint32 *rtab,
1466  l_uint32 *gtab,
1467  l_uint32 *btab,
1468  l_uint32 *pindex)
1469 {
1470  *pindex = rtab[rval] | gtab[gval] | btab[bval];
1471  return;
1472 }
1473 
1474 
1507 static void
1508 getRGBFromOctcube(l_int32 cubeindex,
1509  l_int32 level,
1510  l_int32 *prval,
1511  l_int32 *pgval,
1512  l_int32 *pbval)
1513 {
1514 l_int32 rgbindex;
1515 
1516  /* Bring to format in 21 bits: (r7 g7 b7 r6 g6 b6 ...) */
1517  /* This is valid for levels from 0 to 6 */
1518  rgbindex = cubeindex << (3 * (7 - level)); /* upper corner of cube */
1519  rgbindex |= (0x7 << (3 * (6 - level))); /* index to center of cube */
1520 
1521  /* Extract separate pieces */
1522  *prval = ((rgbindex >> 13) & 0x80) |
1523  ((rgbindex >> 11) & 0x40) |
1524  ((rgbindex >> 9) & 0x20) |
1525  ((rgbindex >> 7) & 0x10) |
1526  ((rgbindex >> 5) & 0x08) |
1527  ((rgbindex >> 3) & 0x04) |
1528  ((rgbindex >> 1) & 0x02);
1529  *pgval = ((rgbindex >> 12) & 0x80) |
1530  ((rgbindex >> 10) & 0x40) |
1531  ((rgbindex >> 8) & 0x20) |
1532  ((rgbindex >> 6) & 0x10) |
1533  ((rgbindex >> 4) & 0x08) |
1534  ((rgbindex >> 2) & 0x04) |
1535  (rgbindex & 0x02);
1536  *pbval = ((rgbindex >> 11) & 0x80) |
1537  ((rgbindex >> 9) & 0x40) |
1538  ((rgbindex >> 7) & 0x20) |
1539  ((rgbindex >> 5) & 0x10) |
1540  ((rgbindex >> 3) & 0x08) |
1541  ((rgbindex >> 1) & 0x04) |
1542  ((rgbindex << 1) & 0x02);
1543 
1544  return;
1545 }
1546 
1547 
1584 static l_int32
1585 getOctcubeIndices(l_int32 rgbindex,
1586  l_int32 level,
1587  l_int32 *pbindex,
1588  l_int32 *psindex)
1589 {
1590  PROCNAME("getOctcubeIndex");
1591 
1592  if (level < 0 || level > CqNLevels - 1)
1593  return ERROR_INT("level must be in e.g., [0 ... 5]", procName, 1);
1594  if (!pbindex)
1595  return ERROR_INT("&bindex not defined", procName, 1);
1596  if (!psindex)
1597  return ERROR_INT("&sindex not defined", procName, 1);
1598 
1599  *pbindex = rgbindex >> (3 * (CqNLevels - level));
1600  *psindex = rgbindex >> (3 * (CqNLevels - 1 - level));
1601  return 0;
1602 }
1603 
1604 
1618 static l_int32
1619 octcubeGetCount(l_int32 level,
1620  l_int32 *psize)
1621 {
1622  PROCNAME("octcubeGetCount");
1623 
1624  if (!psize)
1625  return ERROR_INT("&size not defined", procName, 1);
1626  if (level < 1 || level > 6)
1627  return ERROR_INT("invalid level", procName, 1);
1628 
1629  *psize = 1 << (3 * level);
1630  return 0;
1631 }
1632 
1633 
1634 /*---------------------------------------------------------------------------*
1635  * Adaptive octree quantization based on population at a fixed level *
1636  *---------------------------------------------------------------------------*/
1692 PIX *
1694  l_int32 level,
1695  l_int32 ditherflag)
1696 {
1697 l_int32 w, h, wpls, wpld, i, j, depth, size, ncolors, index;
1698 l_int32 rval, gval, bval;
1699 l_int32 *rarray, *garray, *barray, *narray, *iarray;
1700 l_uint32 octindex, octindex2;
1701 l_uint32 *rtab, *gtab, *btab, *rtab2, *gtab2, *btab2;
1702 l_uint32 *lines, *lined, *datas, *datad;
1703 L_OCTCUBE_POP *opop;
1704 L_HEAP *lh;
1705 PIX *pixd;
1706 PIXCMAP *cmap;
1707 
1708  PROCNAME("pixOctreeQuantByPopulation");
1709 
1710  if (!pixs)
1711  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
1712  if (pixGetDepth(pixs) != 32)
1713  return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
1714  if (level == 0) level = 4;
1715  if (level < 3 || level > 4)
1716  return (PIX *)ERROR_PTR("level not in {3,4}", procName, NULL);
1717 
1718  /* Do not dither if image is very small */
1719  pixGetDimensions(pixs, &w, &h, NULL);
1720  if (w < MinDitherSize && h < MinDitherSize && ditherflag == 1) {
1721  L_INFO("Small image: dithering turned off\n", procName);
1722  ditherflag = 0;
1723  }
1724 
1725  if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
1726  return (PIX *)ERROR_PTR("size not returned", procName, NULL);
1727  rtab = gtab = btab = NULL;
1728  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
1729 
1730  pixd = NULL;
1731  narray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
1732  rarray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
1733  garray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
1734  barray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
1735  if (!narray || !rarray || !garray || !barray)
1736  goto array_cleanup;
1737 
1738  /* Place the pixels in octcube leaves. */
1739  datas = pixGetData(pixs);
1740  wpls = pixGetWpl(pixs);
1741  for (i = 0; i < h; i++) {
1742  lines = datas + i * wpls;
1743  for (j = 0; j < w; j++) {
1744  extractRGBValues(lines[j], &rval, &gval, &bval);
1745  octindex = rtab[rval] | gtab[gval] | btab[bval];
1746  narray[octindex]++;
1747  rarray[octindex] += rval;
1748  garray[octindex] += gval;
1749  barray[octindex] += bval;
1750  }
1751  }
1752 
1753  /* Find the number of different colors */
1754  for (i = 0, ncolors = 0; i < size; i++) {
1755  if (narray[i] > 0)
1756  ncolors++;
1757  }
1758  if (ncolors <= 4)
1759  depth = 2;
1760  else if (ncolors <= 16)
1761  depth = 4;
1762  else
1763  depth = 8;
1764  pixd = pixCreate(w, h, depth);
1765  datad = pixGetData(pixd);
1766  wpld = pixGetWpl(pixd);
1767  pixCopyResolution(pixd, pixs);
1768  pixCopyInputFormat(pixd, pixs);
1769  cmap = pixcmapCreate(depth);
1770  pixSetColormap(pixd, cmap);
1771 
1772  /* Average the colors in each octcube leaf. */
1773  for (i = 0; i < size; i++) {
1774  if (narray[i] > 0) {
1775  rarray[i] /= narray[i];
1776  garray[i] /= narray[i];
1777  barray[i] /= narray[i];
1778  }
1779  }
1780 
1781  /* If ncolors <= 256, finish immediately. Do not dither.
1782  * Re-use narray to hold the colormap index + 1 */
1783  if (ncolors <= 256) {
1784  for (i = 0, index = 0; i < size; i++) {
1785  if (narray[i] > 0) {
1786  pixcmapAddColor(cmap, rarray[i], garray[i], barray[i]);
1787  narray[i] = index + 1; /* to avoid storing 0 */
1788  index++;
1789  }
1790  }
1791 
1792  /* Set the cmap indices for each pixel */
1793  for (i = 0; i < h; i++) {
1794  lines = datas + i * wpls;
1795  lined = datad + i * wpld;
1796  for (j = 0; j < w; j++) {
1797  extractRGBValues(lines[j], &rval, &gval, &bval);
1798  octindex = rtab[rval] | gtab[gval] | btab[bval];
1799  switch (depth)
1800  {
1801  case 8:
1802  SET_DATA_BYTE(lined, j, narray[octindex] - 1);
1803  break;
1804  case 4:
1805  SET_DATA_QBIT(lined, j, narray[octindex] - 1);
1806  break;
1807  case 2:
1808  SET_DATA_DIBIT(lined, j, narray[octindex] - 1);
1809  break;
1810  default:
1811  L_WARNING("shouldn't get here\n", procName);
1812  }
1813  }
1814  }
1815  goto array_cleanup;
1816  }
1817 
1818  /* More complicated. Sort by decreasing population */
1819  lh = lheapCreate(500, L_SORT_DECREASING);
1820  for (i = 0; i < size; i++) {
1821  if (narray[i] > 0) {
1822  opop = (L_OCTCUBE_POP *)LEPT_CALLOC(1, sizeof(L_OCTCUBE_POP));
1823  opop->npix = (l_float32)narray[i];
1824  opop->index = i;
1825  opop->rval = rarray[i];
1826  opop->gval = garray[i];
1827  opop->bval = barray[i];
1828  lheapAdd(lh, opop);
1829  }
1830  }
1831 
1832  /* Take the top 192. These will form the first 192 colors
1833  * in the cmap. iarray[i] holds the index into the cmap. */
1834  iarray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
1835  for (i = 0; i < 192; i++) {
1836  opop = (L_OCTCUBE_POP*)lheapRemove(lh);
1837  if (!opop) break;
1838  pixcmapAddColor(cmap, opop->rval, opop->gval, opop->bval);
1839  iarray[opop->index] = i + 1; /* +1 to avoid storing 0 */
1840 
1841 #if DEBUG_POP
1842  lept_stderr("i = %d, n = %6.0f, (r,g,b) = (%d %d %d)\n",
1843  i, opop->npix, opop->rval, opop->gval, opop->bval);
1844 #endif /* DEBUG_POP */
1845 
1846  LEPT_FREE(opop);
1847  }
1848 
1849  /* Make the octindex tables for level 2, and reuse rarray, etc. */
1850  rtab2 = gtab2 = btab2 = NULL;
1851  makeRGBToIndexTables(2, &rtab2, &gtab2, &btab2);
1852  for (i = 0; i < 64; i++) {
1853  narray[i] = 0;
1854  rarray[i] = 0;
1855  garray[i] = 0;
1856  barray[i] = 0;
1857  }
1858 
1859  /* Take the rest of the occupied octcubes, assigning the pixels
1860  * to these new colormap indices. iarray[] is addressed
1861  * by %level octcube indices, and it now holds the
1862  * colormap indices for all pixels in pixs. */
1863  for (i = 192; i < size; i++) {
1864  opop = (L_OCTCUBE_POP*)lheapRemove(lh);
1865  if (!opop) break;
1866  rval = opop->rval;
1867  gval = opop->gval;
1868  bval = opop->bval;
1869  octindex2 = rtab2[rval] | gtab2[gval] | btab2[bval];
1870  narray[octindex2] += (l_int32)opop->npix;
1871  rarray[octindex2] += (l_int32)opop->npix * rval;
1872  garray[octindex2] += (l_int32)opop->npix * gval;
1873  barray[octindex2] += (l_int32)opop->npix * bval;
1874  iarray[opop->index] = 192 + octindex2 + 1; /* +1 to avoid storing 0 */
1875  LEPT_FREE(opop);
1876  }
1877  lheapDestroy(&lh, TRUE);
1878 
1879  /* To span the full color space, which is necessary for dithering,
1880  * set each iarray element whose value is still 0 at the input
1881  * level octcube leaves (because there were no pixels in those
1882  * octcubes) to the colormap index corresponding to its level 2
1883  * octcube. */
1884  if (ditherflag) {
1885  for (i = 0; i < size; i++) {
1886  if (iarray[i] == 0) {
1887  getRGBFromOctcube(i, level, &rval, &gval, &bval);
1888  octindex2 = rtab2[rval] | gtab2[gval] | btab2[bval];
1889  iarray[i] = 192 + octindex2 + 1;
1890  }
1891  }
1892  }
1893  LEPT_FREE(rtab2);
1894  LEPT_FREE(gtab2);
1895  LEPT_FREE(btab2);
1896 
1897  /* Average the colors from the residuals in each level 2 octcube,
1898  * and add these 64 values to the colormap. */
1899  for (i = 0; i < 64; i++) {
1900  if (narray[i] > 0) {
1901  rarray[i] /= narray[i];
1902  garray[i] /= narray[i];
1903  barray[i] /= narray[i];
1904  } else { /* no pixels in this octcube; use center value */
1905  getRGBFromOctcube(i, 2, &rarray[i], &garray[i], &barray[i]);
1906  }
1907  pixcmapAddColor(cmap, rarray[i], garray[i], barray[i]);
1908  }
1909 
1910  /* Set the cmap indices for each pixel. Subtract 1 from
1911  * the value in iarray[] because we added 1 earlier. */
1912  if (ditherflag == 0) {
1913  for (i = 0; i < h; i++) {
1914  lines = datas + i * wpls;
1915  lined = datad + i * wpld;
1916  for (j = 0; j < w; j++) {
1917  extractRGBValues(lines[j], &rval, &gval, &bval);
1918  octindex = rtab[rval] | gtab[gval] | btab[bval];
1919  SET_DATA_BYTE(lined, j, iarray[octindex] - 1);
1920  }
1921  }
1922  } else { /* dither */
1923  pixDitherOctindexWithCmap(pixs, pixd, rtab, gtab, btab,
1924  iarray, POP_DIF_CAP);
1925  }
1926 
1927 #if DEBUG_POP
1928  for (i = 0; i < size / 16; i++) {
1929  l_int32 j;
1930  for (j = 0; j < 16; j++)
1931  lept_stderr("%d ", iarray[16 * i + j]);
1932  lept_stderr("\n");
1933  }
1934 #endif /* DEBUG_POP */
1935 
1936  LEPT_FREE(iarray);
1937 
1938 array_cleanup:
1939  LEPT_FREE(narray);
1940  LEPT_FREE(rarray);
1941  LEPT_FREE(garray);
1942  LEPT_FREE(barray);
1943  LEPT_FREE(rtab);
1944  LEPT_FREE(gtab);
1945  LEPT_FREE(btab);
1946 
1947  return pixd;
1948 }
1949 
1950 
1984 static l_int32
1986  PIX *pixd,
1987  l_uint32 *rtab,
1988  l_uint32 *gtab,
1989  l_uint32 *btab,
1990  l_int32 *indexmap,
1991  l_int32 difcap)
1992 {
1993 l_uint8 *bufu8r, *bufu8g, *bufu8b;
1994 l_int32 i, j, w, h, wpld, octindex, cmapindex, success;
1995 l_int32 rval, gval, bval, rc, gc, bc;
1996 l_int32 dif, val1, val2, val3;
1997 l_int32 *buf1r, *buf1g, *buf1b, *buf2r, *buf2g, *buf2b;
1998 l_uint32 *datad, *lined;
1999 PIXCMAP *cmap;
2000 
2001  PROCNAME("pixDitherOctindexWithCmap");
2002 
2003  if (!pixs || pixGetDepth(pixs) != 32)
2004  return ERROR_INT("pixs undefined or not 32 bpp", procName, 1);
2005  if (!pixd || pixGetDepth(pixd) != 8)
2006  return ERROR_INT("pixd undefined or not 8 bpp", procName, 1);
2007  if ((cmap = pixGetColormap(pixd)) == NULL)
2008  return ERROR_INT("pixd not cmapped", procName, 1);
2009  if (!rtab || !gtab || !btab || !indexmap)
2010  return ERROR_INT("not all 4 tables defined", procName, 1);
2011  pixGetDimensions(pixs, &w, &h, NULL);
2012  if (pixGetWidth(pixd) != w || pixGetHeight(pixd) != h)
2013  return ERROR_INT("pixs and pixd not same size", procName, 1);
2014 
2015  success = TRUE;
2016  bufu8r = bufu8g = bufu8b = NULL;
2017  buf1r = buf1g = buf1b = buf2r = buf2g = buf2b = NULL;
2018  bufu8r = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
2019  bufu8g = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
2020  bufu8b = (l_uint8 *)LEPT_CALLOC(w, sizeof(l_uint8));
2021  buf1r = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
2022  buf1g = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
2023  buf1b = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
2024  buf2r = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
2025  buf2g = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
2026  buf2b = (l_int32 *)LEPT_CALLOC(w, sizeof(l_int32));
2027  if (!bufu8r || !bufu8g || !bufu8b || !buf1r || !buf1g ||
2028  !buf1b || !buf2r || !buf2g || !buf2b) {
2029  L_ERROR("buffer not made\n", procName);
2030  success = FALSE;
2031  goto buffer_cleanup;
2032  }
2033 
2034  /* Start by priming buf2; line 1 is above line 2 */
2035  pixGetRGBLine(pixs, 0, bufu8r, bufu8g, bufu8b);
2036  for (j = 0; j < w; j++) {
2037  buf2r[j] = 64 * bufu8r[j];
2038  buf2g[j] = 64 * bufu8g[j];
2039  buf2b[j] = 64 * bufu8b[j];
2040  }
2041 
2042  datad = pixGetData(pixd);
2043  wpld = pixGetWpl(pixd);
2044  for (i = 0; i < h - 1; i++) {
2045  /* Swap data 2 --> 1, and read in new line 2 */
2046  memcpy(buf1r, buf2r, 4 * w);
2047  memcpy(buf1g, buf2g, 4 * w);
2048  memcpy(buf1b, buf2b, 4 * w);
2049  pixGetRGBLine(pixs, i + 1, bufu8r, bufu8g, bufu8b);
2050  for (j = 0; j < w; j++) {
2051  buf2r[j] = 64 * bufu8r[j];
2052  buf2g[j] = 64 * bufu8g[j];
2053  buf2b[j] = 64 * bufu8b[j];
2054  }
2055 
2056  /* Dither */
2057  lined = datad + i * wpld;
2058  for (j = 0; j < w - 1; j++) {
2059  rval = buf1r[j] / 64;
2060  gval = buf1g[j] / 64;
2061  bval = buf1b[j] / 64;
2062  octindex = rtab[rval] | gtab[gval] | btab[bval];
2063  cmapindex = indexmap[octindex] - 1;
2064  SET_DATA_BYTE(lined, j, cmapindex);
2065  pixcmapGetColor(cmap, cmapindex, &rc, &gc, &bc);
2066 
2067  dif = buf1r[j] / 8 - 8 * rc;
2068  if (difcap > 0) {
2069  if (dif > difcap) dif = difcap;
2070  if (dif < -difcap) dif = -difcap;
2071  }
2072  if (dif != 0) {
2073  val1 = buf1r[j + 1] + 3 * dif;
2074  val2 = buf2r[j] + 3 * dif;
2075  val3 = buf2r[j + 1] + 2 * dif;
2076  if (dif > 0) {
2077  buf1r[j + 1] = L_MIN(16383, val1);
2078  buf2r[j] = L_MIN(16383, val2);
2079  buf2r[j + 1] = L_MIN(16383, val3);
2080  } else {
2081  buf1r[j + 1] = L_MAX(0, val1);
2082  buf2r[j] = L_MAX(0, val2);
2083  buf2r[j + 1] = L_MAX(0, val3);
2084  }
2085  }
2086 
2087  dif = buf1g[j] / 8 - 8 * gc;
2088  if (difcap > 0) {
2089  if (dif > difcap) dif = difcap;
2090  if (dif < -difcap) dif = -difcap;
2091  }
2092  if (dif != 0) {
2093  val1 = buf1g[j + 1] + 3 * dif;
2094  val2 = buf2g[j] + 3 * dif;
2095  val3 = buf2g[j + 1] + 2 * dif;
2096  if (dif > 0) {
2097  buf1g[j + 1] = L_MIN(16383, val1);
2098  buf2g[j] = L_MIN(16383, val2);
2099  buf2g[j + 1] = L_MIN(16383, val3);
2100  } else {
2101  buf1g[j + 1] = L_MAX(0, val1);
2102  buf2g[j] = L_MAX(0, val2);
2103  buf2g[j + 1] = L_MAX(0, val3);
2104  }
2105  }
2106 
2107  dif = buf1b[j] / 8 - 8 * bc;
2108  if (difcap > 0) {
2109  if (dif > difcap) dif = difcap;
2110  if (dif < -difcap) dif = -difcap;
2111  }
2112  if (dif != 0) {
2113  val1 = buf1b[j + 1] + 3 * dif;
2114  val2 = buf2b[j] + 3 * dif;
2115  val3 = buf2b[j + 1] + 2 * dif;
2116  if (dif > 0) {
2117  buf1b[j + 1] = L_MIN(16383, val1);
2118  buf2b[j] = L_MIN(16383, val2);
2119  buf2b[j + 1] = L_MIN(16383, val3);
2120  } else {
2121  buf1b[j + 1] = L_MAX(0, val1);
2122  buf2b[j] = L_MAX(0, val2);
2123  buf2b[j + 1] = L_MAX(0, val3);
2124  }
2125  }
2126  }
2127 
2128  /* Get last pixel in row; no downward propagation */
2129  rval = buf1r[w - 1] / 64;
2130  gval = buf1g[w - 1] / 64;
2131  bval = buf1b[w - 1] / 64;
2132  octindex = rtab[rval] | gtab[gval] | btab[bval];
2133  cmapindex = indexmap[octindex] - 1;
2134  SET_DATA_BYTE(lined, w - 1, cmapindex);
2135  }
2136 
2137  /* Get last row of pixels; no leftward propagation */
2138  lined = datad + (h - 1) * wpld;
2139  for (j = 0; j < w; j++) {
2140  rval = buf2r[j] / 64;
2141  gval = buf2g[j] / 64;
2142  bval = buf2b[j] / 64;
2143  octindex = rtab[rval] | gtab[gval] | btab[bval];
2144  cmapindex = indexmap[octindex] - 1;
2145  SET_DATA_BYTE(lined, j, cmapindex);
2146  }
2147 
2148 buffer_cleanup:
2149  LEPT_FREE(bufu8r);
2150  LEPT_FREE(bufu8g);
2151  LEPT_FREE(bufu8b);
2152  LEPT_FREE(buf1r);
2153  LEPT_FREE(buf1g);
2154  LEPT_FREE(buf1b);
2155  LEPT_FREE(buf2r);
2156  LEPT_FREE(buf2g);
2157  LEPT_FREE(buf2b);
2158 
2159  return (success) ? 0 : 1;
2160 }
2161 
2162 
2163 /*---------------------------------------------------------------------------*
2164  * Adaptive octree quantization to 4 and 8 bpp with max colors *
2165  *---------------------------------------------------------------------------*/
2255 PIX *
2257  l_int32 maxcolors,
2258  l_int32 subsample)
2259 {
2260 l_int32 w, h, minside, bpp, wpls, wpld, i, j, actualcolors;
2261 l_int32 rval, gval, bval, nbase, nextra, maxlevel, ncubes, val;
2262 l_int32 *lut1, *lut2;
2263 l_uint32 index;
2264 l_uint32 *lines, *lined, *datas, *datad, *pspixel;
2265 l_uint32 *rtab, *gtab, *btab;
2266 OQCELL *oqc;
2267 OQCELL **oqca;
2268 L_HEAP *lh;
2269 PIX *pixd;
2270 PIXCMAP *cmap;
2271 
2272  PROCNAME("pixOctreeQuantNumColors");
2273 
2274  if (!pixs)
2275  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
2276  if (pixGetDepth(pixs) != 32)
2277  return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
2278  if (maxcolors < 8) {
2279  L_WARNING("max colors < 8; setting to 8\n", procName);
2280  maxcolors = 8;
2281  }
2282  if (maxcolors > 256) {
2283  L_WARNING("max colors > 256; setting to 256\n", procName);
2284  maxcolors = 256;
2285  }
2286 
2287  pixGetDimensions(pixs, &w, &h, NULL);
2288  datas = pixGetData(pixs);
2289  wpls = pixGetWpl(pixs);
2290  minside = L_MIN(w, h);
2291  if (subsample <= 0) {
2292  subsample = L_MAX(1, minside / 200);
2293  }
2294 
2295  if (maxcolors <= 16) {
2296  bpp = 4;
2297  pixd = pixCreate(w, h, bpp);
2298  maxlevel = 2;
2299  ncubes = 64; /* 2^6 */
2300  nbase = 8;
2301  nextra = maxcolors - nbase;
2302  } else if (maxcolors <= 64) {
2303  bpp = 8;
2304  pixd = pixCreate(w, h, bpp);
2305  maxlevel = 2;
2306  ncubes = 64; /* 2^6 */
2307  nbase = 8;
2308  nextra = maxcolors - nbase;
2309  } else { /* maxcolors <= 256 */
2310  bpp = 8;
2311  pixd = pixCreate(w, h, bpp);
2312  maxlevel = 3;
2313  ncubes = 512; /* 2^9 */
2314  nbase = 64;
2315  nextra = maxcolors - nbase;
2316  }
2317 
2318  pixCopyResolution(pixd, pixs);
2319  pixCopyInputFormat(pixd, pixs);
2320 
2321  /*----------------------------------------------------------*
2322  * If we're using the minimum number of colors, it is *
2323  * much simpler. We just use 'nbase' octcubes. *
2324  * For this case, we don't eliminate any extra colors. *
2325  *----------------------------------------------------------*/
2326  if (nextra == 0) {
2327  /* prepare the OctcubeQuantCell array */
2328  if ((oqca = (OQCELL **)LEPT_CALLOC(nbase, sizeof(OQCELL *))) == NULL) {
2329  pixDestroy(&pixd);
2330  return (PIX *)ERROR_PTR("oqca not made", procName, NULL);
2331  }
2332  for (i = 0; i < nbase; i++) {
2333  oqca[i] = (OQCELL *)LEPT_CALLOC(1, sizeof(OQCELL));
2334  oqca[i]->n = 0.0;
2335  }
2336 
2337  rtab = gtab = btab = NULL;
2338  makeRGBToIndexTables(maxlevel - 1, &rtab, &gtab, &btab);
2339 
2340  /* Go through the entire image, gathering statistics and
2341  * assigning pixels to their quantized value */
2342  datad = pixGetData(pixd);
2343  wpld = pixGetWpl(pixd);
2344  for (i = 0; i < h; i++) {
2345  lines = datas + i * wpls;
2346  lined = datad + i * wpld;
2347  for (j = 0; j < w; j++) {
2348  pspixel = lines + j;
2349  extractRGBValues(*pspixel, &rval, &gval, &bval);
2350  getOctcubeIndexFromRGB(rval, gval, bval,
2351  rtab, gtab, btab, &index);
2352 /* lept_stderr("rval = %d, gval = %d, bval = %d,"
2353  " index = %d\n", rval, gval, bval, index); */
2354  if (bpp == 4)
2355  SET_DATA_QBIT(lined, j, index);
2356  else /* bpp == 8 */
2357  SET_DATA_BYTE(lined, j, index);
2358  oqca[index]->n += 1.0;
2359  oqca[index]->rcum += rval;
2360  oqca[index]->gcum += gval;
2361  oqca[index]->bcum += bval;
2362  }
2363  }
2364 
2365  /* Compute average color values in each octcube, and
2366  * generate colormap */
2367  cmap = pixcmapCreate(bpp);
2368  pixSetColormap(pixd, cmap);
2369  for (i = 0; i < nbase; i++) {
2370  oqc = oqca[i];
2371  if (oqc->n != 0) {
2372  oqc->rval = (l_int32)(oqc->rcum / oqc->n);
2373  oqc->gval = (l_int32)(oqc->gcum / oqc->n);
2374  oqc->bval = (l_int32)(oqc->bcum / oqc->n);
2375  } else {
2376  getRGBFromOctcube(i, maxlevel - 1, &oqc->rval,
2377  &oqc->gval, &oqc->bval);
2378  }
2379  pixcmapAddColor(cmap, oqc->rval, oqc->gval, oqc->bval);
2380  }
2381 
2382  for (i = 0; i < nbase; i++)
2383  LEPT_FREE(oqca[i]);
2384  LEPT_FREE(oqca);
2385  LEPT_FREE(rtab);
2386  LEPT_FREE(gtab);
2387  LEPT_FREE(btab);
2388  return pixd;
2389  }
2390 
2391  /*------------------------------------------------------------*
2392  * General case: we will use colors in octcubes at maxlevel. *
2393  * We also remove any colors that are not populated from *
2394  * the colormap. *
2395  *------------------------------------------------------------*/
2396  /* Prepare the OctcubeQuantCell array */
2397  oqca = (OQCELL **)LEPT_CALLOC(ncubes, sizeof(OQCELL *));
2398  for (i = 0; i < ncubes; i++) {
2399  oqca[i] = (OQCELL *)LEPT_CALLOC(1, sizeof(OQCELL));
2400  oqca[i]->n = 0.0;
2401  }
2402 
2403  /* Make the tables to map color to the octindex,
2404  * of which there are 'ncubes' at 'maxlevel' */
2405  rtab = gtab = btab = NULL;
2406  makeRGBToIndexTables(maxlevel, &rtab, &gtab, &btab);
2407 
2408  /* Estimate the color distribution; we want to find the
2409  * most popular nextra colors at 'maxlevel' */
2410  for (i = 0; i < h; i += subsample) {
2411  lines = datas + i * wpls;
2412  for (j = 0; j < w; j += subsample) {
2413  pspixel = lines + j;
2414  extractRGBValues(*pspixel, &rval, &gval, &bval);
2415  getOctcubeIndexFromRGB(rval, gval, bval, rtab, gtab, btab, &index);
2416  oqca[index]->n += 1.0;
2417  oqca[index]->octindex = index;
2418  oqca[index]->rcum += rval;
2419  oqca[index]->gcum += gval;
2420  oqca[index]->bcum += bval;
2421  }
2422  }
2423 
2424  /* Transfer the OQCELL from the array, and order in a heap */
2425  lh = lheapCreate(512, L_SORT_DECREASING);
2426  for (i = 0; i < ncubes; i++)
2427  lheapAdd(lh, oqca[i]);
2428  LEPT_FREE(oqca); /* don't need this array */
2429 
2430  /* Prepare a new OctcubeQuantCell array, with maxcolors cells */
2431  oqca = (OQCELL **)LEPT_CALLOC(maxcolors, sizeof(OQCELL *));
2432  for (i = 0; i < nbase; i++) { /* make nbase cells */
2433  oqca[i] = (OQCELL *)LEPT_CALLOC(1, sizeof(OQCELL));
2434  oqca[i]->n = 0.0;
2435  }
2436 
2437  /* Remove the nextra most populated ones, and put them in the array */
2438  for (i = 0; i < nextra; i++) {
2439  oqc = (OQCELL *)lheapRemove(lh);
2440  oqc->n = 0.0; /* reinit */
2441  oqc->rcum = 0;
2442  oqc->gcum = 0;
2443  oqc->bcum = 0;
2444  oqca[nbase + i] = oqc; /* store it in the array */
2445  }
2446 
2447  /* Destroy the heap and its remaining contents */
2448  lheapDestroy(&lh, TRUE);
2449 
2450  /* Generate a lookup table from octindex at maxlevel
2451  * to color table index */
2452  lut1 = (l_int32 *)LEPT_CALLOC(ncubes, sizeof(l_int32));
2453  for (i = 0; i < nextra; i++)
2454  lut1[oqca[nbase + i]->octindex] = nbase + i;
2455  for (index = 0; index < ncubes; index++) {
2456  if (lut1[index] == 0) /* not one of the extras; need to assign */
2457  lut1[index] = index >> 3; /* remove the least significant bits */
2458 /* lept_stderr("lut1[%d] = %d\n", index, lut1[index]); */
2459  }
2460 
2461  /* Go through the entire image, gathering statistics and
2462  * assigning pixels to their quantized value */
2463  datad = pixGetData(pixd);
2464  wpld = pixGetWpl(pixd);
2465  for (i = 0; i < h; i++) {
2466  lines = datas + i * wpls;
2467  lined = datad + i * wpld;
2468  for (j = 0; j < w; j++) {
2469  pspixel = lines + j;
2470  extractRGBValues(*pspixel, &rval, &gval, &bval);
2471  getOctcubeIndexFromRGB(rval, gval, bval, rtab, gtab, btab, &index);
2472 /* lept_stderr("rval = %d, gval = %d, bval = %d, index = %d\n",
2473  rval, gval, bval, index); */
2474  val = lut1[index];
2475  switch (bpp) {
2476  case 4:
2477  SET_DATA_QBIT(lined, j, val);
2478  break;
2479  case 8:
2480  SET_DATA_BYTE(lined, j, val);
2481  break;
2482  default:
2483  LEPT_FREE(oqca);
2484  LEPT_FREE(lut1);
2485  return (PIX *)ERROR_PTR("bpp not 4 or 8!", procName, NULL);
2486  break;
2487  }
2488  oqca[val]->n += 1.0;
2489  oqca[val]->rcum += rval;
2490  oqca[val]->gcum += gval;
2491  oqca[val]->bcum += bval;
2492  }
2493  }
2494 
2495  /* Compute averages, set up a colormap, and make a second
2496  * lut that converts from the color values currently in
2497  * the image to a minimal set */
2498  lut2 = (l_int32 *)LEPT_CALLOC(ncubes, sizeof(l_int32));
2499  cmap = pixcmapCreate(bpp);
2500  pixSetColormap(pixd, cmap);
2501  for (i = 0, index = 0; i < maxcolors; i++) {
2502  oqc = oqca[i];
2503  lut2[i] = index;
2504  if (oqc->n == 0) /* no occupancy; don't bump up index */
2505  continue;
2506  oqc->rval = (l_int32)(oqc->rcum / oqc->n);
2507  oqc->gval = (l_int32)(oqc->gcum / oqc->n);
2508  oqc->bval = (l_int32)(oqc->bcum / oqc->n);
2509  pixcmapAddColor(cmap, oqc->rval, oqc->gval, oqc->bval);
2510  index++;
2511  }
2512 /* pixcmapWriteStream(stderr, cmap); */
2513  actualcolors = pixcmapGetCount(cmap);
2514 /* lept_stderr("Number of different colors = %d\n", actualcolors); */
2515 
2516  /* Last time through the image; use the lookup table to
2517  * remap the pixel value to the minimal colormap */
2518  if (actualcolors < maxcolors) {
2519  for (i = 0; i < h; i++) {
2520  lined = datad + i * wpld;
2521  for (j = 0; j < w; j++) {
2522  switch (bpp) {
2523  case 4:
2524  val = GET_DATA_QBIT(lined, j);
2525  SET_DATA_QBIT(lined, j, lut2[val]);
2526  break;
2527  case 8:
2528  val = GET_DATA_BYTE(lined, j);
2529  SET_DATA_BYTE(lined, j, lut2[val]);
2530  break;
2531  }
2532  }
2533  }
2534  }
2535 
2536  if (oqca) {
2537  for (i = 0; i < maxcolors; i++)
2538  LEPT_FREE(oqca[i]);
2539  }
2540  LEPT_FREE(oqca);
2541  LEPT_FREE(lut1);
2542  LEPT_FREE(lut2);
2543  LEPT_FREE(rtab);
2544  LEPT_FREE(gtab);
2545  LEPT_FREE(btab);
2546  return pixd;
2547 }
2548 
2549 
2550 /*-------------------------------------------------------------------------*
2551  * Mixed color/gray quantization with specified number of colors *
2552  *-------------------------------------------------------------------------*/
2582 PIX *
2584  l_int32 depth,
2585  l_int32 graylevels,
2586  l_int32 delta)
2587 {
2588 l_int32 w, h, wpls, wpld, i, j, size, octlevels;
2589 l_int32 rval, gval, bval, del, val, midval;
2590 l_int32 *carray, *rarray, *garray, *barray;
2591 l_int32 *tabval;
2592 l_uint32 octindex;
2593 l_uint32 *rtab, *gtab, *btab;
2594 l_uint32 *lines, *lined, *datas, *datad;
2595 PIX *pixd;
2596 PIXCMAP *cmap;
2597 
2598  PROCNAME("pixOctcubeQuantMixedWithGray");
2599 
2600  if (!pixs)
2601  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
2602  if (pixGetDepth(pixs) != 32)
2603  return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
2604  if (graylevels < 2)
2605  return (PIX *)ERROR_PTR("invalid graylevels", procName, NULL);
2606  if (depth == 4) {
2607  octlevels = 1;
2608  size = 8; /* 2 ** 3 */
2609  if (graylevels > 8)
2610  return (PIX *)ERROR_PTR("max 8 gray levels", procName, NULL);
2611  } else if (depth == 8) {
2612  octlevels = 2;
2613  size = 64; /* 2 ** 6 */
2614  if (graylevels > 192)
2615  return (PIX *)ERROR_PTR("max 192 gray levels", procName, NULL);
2616  } else {
2617  return (PIX *)ERROR_PTR("output depth not 4 or 8 bpp", procName, NULL);
2618  }
2619 
2620  pixd = NULL;
2621 
2622  /* Make octcube index tables */
2623  rtab = gtab = btab = NULL;
2624  makeRGBToIndexTables(octlevels, &rtab, &gtab, &btab);
2625 
2626  /* Make octcube arrays for storing points in each cube */
2627  carray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2628  rarray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2629  garray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2630  barray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2631 
2632  /* Make lookup table, using computed thresholds */
2633  tabval = makeGrayQuantIndexTable(graylevels);
2634  if (!rtab || !gtab || !btab ||
2635  !carray || !rarray || !garray || !barray || !tabval) {
2636  L_ERROR("calloc fail for an array\n", procName);
2637  goto array_cleanup;
2638  }
2639 
2640  /* Make colormapped output pixd */
2641  pixGetDimensions(pixs, &w, &h, NULL);
2642  if ((pixd = pixCreate(w, h, depth)) == NULL) {
2643  L_ERROR("pixd not made\n", procName);
2644  goto array_cleanup;
2645  }
2646  pixCopyResolution(pixd, pixs);
2647  pixCopyInputFormat(pixd, pixs);
2648  cmap = pixcmapCreate(depth);
2649  for (j = 0; j < size; j++) /* reserve octcube colors */
2650  pixcmapAddColor(cmap, 1, 1, 1); /* a color that won't be used */
2651  for (j = 0; j < graylevels; j++) { /* set grayscale colors */
2652  val = (255 * j) / (graylevels - 1);
2653  pixcmapAddColor(cmap, val, val, val);
2654  }
2655  pixSetColormap(pixd, cmap);
2656  wpld = pixGetWpl(pixd);
2657  datad = pixGetData(pixd);
2658 
2659  /* Go through src image: assign dest pixels to colormap values
2660  * and compute average colors in each occupied octcube */
2661  datas = pixGetData(pixs);
2662  wpls = pixGetWpl(pixs);
2663  for (i = 0; i < h; i++) {
2664  lines = datas + i * wpls;
2665  lined = datad + i * wpld;
2666  for (j = 0; j < w; j++) {
2667  extractRGBValues(lines[j], &rval, &gval, &bval);
2668  if (rval > gval) {
2669  if (gval > bval) { /* r > g > b */
2670  del = rval - bval;
2671  midval = gval;
2672  } else if (rval > bval) { /* r > b > g */
2673  del = rval - gval;
2674  midval = bval;
2675  } else { /* b > r > g */
2676  del = bval - gval;
2677  midval = rval;
2678  }
2679  } else { /* gval >= rval */
2680  if (rval > bval) { /* g > r > b */
2681  del = gval - bval;
2682  midval = rval;
2683  } else if (gval > bval) { /* g > b > r */
2684  del = gval - rval;
2685  midval = bval;
2686  } else { /* b > g > r */
2687  del = bval - rval;
2688  midval = gval;
2689  }
2690  }
2691  if (del > delta) { /* assign to color */
2692  octindex = rtab[rval] | gtab[gval] | btab[bval];
2693  carray[octindex]++;
2694  rarray[octindex] += rval;
2695  garray[octindex] += gval;
2696  barray[octindex] += bval;
2697  if (depth == 4)
2698  SET_DATA_QBIT(lined, j, octindex);
2699  else /* depth == 8 */
2700  SET_DATA_BYTE(lined, j, octindex);
2701  } else { /* assign to grayscale */
2702  val = size + tabval[midval];
2703  if (depth == 4)
2704  SET_DATA_QBIT(lined, j, val);
2705  else /* depth == 8 */
2706  SET_DATA_BYTE(lined, j, val);
2707  }
2708  }
2709  }
2710 
2711  /* Average the colors in each bin and reset the colormap */
2712  for (i = 0; i < size; i++) {
2713  if (carray[i] > 0) {
2714  rarray[i] /= carray[i];
2715  garray[i] /= carray[i];
2716  barray[i] /= carray[i];
2717  pixcmapResetColor(cmap, i, rarray[i], garray[i], barray[i]);
2718  }
2719  }
2720 
2721 array_cleanup:
2722  LEPT_FREE(carray);
2723  LEPT_FREE(rarray);
2724  LEPT_FREE(garray);
2725  LEPT_FREE(barray);
2726  LEPT_FREE(rtab);
2727  LEPT_FREE(gtab);
2728  LEPT_FREE(btab);
2729  LEPT_FREE(tabval);
2730 
2731  return pixd;
2732 }
2733 
2734 
2735 /*-------------------------------------------------------------------------*
2736  * Fixed partition octcube quantization with 256 cells *
2737  *-------------------------------------------------------------------------*/
2801 PIX *
2803  l_int32 ditherflag)
2804 {
2805 l_uint8 index;
2806 l_int32 rval, gval, bval;
2807 l_int32 w, h, wpls, wpld, i, j, cindex;
2808 l_uint32 *rtab, *gtab, *btab;
2809 l_int32 *itab;
2810 l_uint32 *datas, *datad, *lines, *lined;
2811 PIX *pixd;
2812 PIXCMAP *cmap;
2813 
2814  PROCNAME("pixFixedOctcubeQuant256");
2815 
2816  if (!pixs)
2817  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
2818  if (pixGetDepth(pixs) != 32)
2819  return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
2820 
2821  /* Do not dither if image is very small */
2822  pixGetDimensions(pixs, &w, &h, NULL);
2823  if (w < MinDitherSize && h < MinDitherSize && ditherflag == 1) {
2824  L_INFO("Small image: dithering turned off\n", procName);
2825  ditherflag = 0;
2826  }
2827 
2828  /* Find the centers of the 256 cells, each of which represents
2829  * the 3 MSBits of the red and green components, and the
2830  * 2 MSBits of the blue component. This gives a mapping
2831  * from a "cube index" to the rgb values. Save all 256
2832  * rgb values of these centers in a colormap.
2833  * For example, to get the red color of the cell center,
2834  * you take the 3 MSBits of to the index and add the
2835  * offset to the center of the cell, which is 0x10. */
2836  cmap = pixcmapCreate(8);
2837  for (cindex = 0; cindex < 256; cindex++) {
2838  rval = (cindex & 0xe0) | 0x10;
2839  gval = ((cindex << 3) & 0xe0) | 0x10;
2840  bval = ((cindex << 6) & 0xc0) | 0x20;
2841  pixcmapAddColor(cmap, rval, gval, bval);
2842  }
2843 
2844  /* Make output 8 bpp palette image */
2845  datas = pixGetData(pixs);
2846  wpls = pixGetWpl(pixs);
2847  if ((pixd = pixCreate(w, h, 8)) == NULL) {
2848  pixcmapDestroy(&cmap);
2849  return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
2850  }
2851  pixSetColormap(pixd, cmap);
2852  pixCopyResolution(pixd, pixs);
2853  pixCopyInputFormat(pixd, pixs);
2854  datad = pixGetData(pixd);
2855  wpld = pixGetWpl(pixd);
2856 
2857  /* Set dest pix values to colortable indices */
2858  if (ditherflag == 0) { /* no dithering */
2859  for (i = 0; i < h; i++) {
2860  lines = datas + i * wpls;
2861  lined = datad + i * wpld;
2862  for (j = 0; j < w; j++) {
2863  extractRGBValues(lines[j], &rval, &gval, &bval);
2864  index = (rval & 0xe0) | ((gval >> 3) & 0x1c) | (bval >> 6);
2865  SET_DATA_BYTE(lined, j, index);
2866  }
2867  }
2868  } else { /* ditherflag == 1 */
2869  /* Set up conversion tables from rgb directly to the colormap
2870  * index. However, the dithering function expects these tables
2871  * to generate an octcube index (+1), and the table itab[] to
2872  * convert to the colormap index. So we make a trivial
2873  * itab[], that simply compensates for the -1 in
2874  * pixDitherOctindexWithCmap(). No cap is required on
2875  * the propagated difference. */
2876  rtab = (l_uint32 *)LEPT_CALLOC(256, sizeof(l_uint32));
2877  gtab = (l_uint32 *)LEPT_CALLOC(256, sizeof(l_uint32));
2878  btab = (l_uint32 *)LEPT_CALLOC(256, sizeof(l_uint32));
2879  itab = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
2880  if (!rtab || !gtab || !btab || !itab) {
2881  pixDestroy(&pixd);
2882  return (PIX *)ERROR_PTR("calloc fail for table", procName, NULL);
2883  }
2884  for (i = 0; i < 256; i++) {
2885  rtab[i] = i & 0xe0;
2886  gtab[i] = (i >> 3) & 0x1c;
2887  btab[i] = i >> 6;
2888  itab[i] = i + 1;
2889  }
2890  pixDitherOctindexWithCmap(pixs, pixd, rtab, gtab, btab, itab,
2891  FIXED_DIF_CAP);
2892  LEPT_FREE(rtab);
2893  LEPT_FREE(gtab);
2894  LEPT_FREE(btab);
2895  LEPT_FREE(itab);
2896  }
2897 
2898  return pixd;
2899 }
2900 
2901 
2902 /*---------------------------------------------------------------------------*
2903  * Nearly exact quantization for images with few colors *
2904  *---------------------------------------------------------------------------*/
2935 PIX *
2937  l_int32 level)
2938 {
2939 l_int32 w, h, wpls, wpld, i, j, depth, size, ncolors, index;
2940 l_int32 rval, gval, bval;
2941 l_int32 *carray, *rarray, *garray, *barray;
2942 l_uint32 octindex;
2943 l_uint32 *rtab, *gtab, *btab;
2944 l_uint32 *lines, *lined, *datas, *datad, *pspixel;
2945 PIX *pixd;
2946 PIXCMAP *cmap;
2947 
2948  PROCNAME("pixFewColorsOctcubeQuant1");
2949 
2950  if (!pixs)
2951  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
2952  if (pixGetDepth(pixs) != 32)
2953  return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
2954  if (level < 1 || level > 6)
2955  return (PIX *)ERROR_PTR("invalid level", procName, NULL);
2956 
2957  pixd = NULL;
2958 
2959  if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
2960  return (PIX *)ERROR_PTR("size not returned", procName, NULL);
2961  rtab = gtab = btab = NULL;
2962  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
2963 
2964  carray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2965  rarray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2966  garray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2967  barray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32));
2968  if (!carray || !rarray || !garray || !barray) {
2969  L_ERROR("calloc fail for an array\n", procName);
2970  goto array_cleanup;
2971  }
2972 
2973  /* Place the pixels in octcube leaves. */
2974  pixGetDimensions(pixs, &w, &h, NULL);
2975  datas = pixGetData(pixs);
2976  wpls = pixGetWpl(pixs);
2977  for (i = 0; i < h; i++) {
2978  lines = datas + i * wpls;
2979  for (j = 0; j < w; j++) {
2980  pspixel = lines + j;
2981  extractRGBValues(*pspixel, &rval, &gval, &bval);
2982  octindex = rtab[rval] | gtab[gval] | btab[bval];
2983  carray[octindex]++;
2984  rarray[octindex] += rval;
2985  garray[octindex] += gval;
2986  barray[octindex] += bval;
2987  }
2988  }
2989 
2990  /* Find the number of different colors */
2991  for (i = 0, ncolors = 0; i < size; i++) {
2992  if (carray[i] > 0)
2993  ncolors++;
2994  }
2995  if (ncolors > 256) {
2996  L_WARNING("%d colors found; more than 256\n", procName, ncolors);
2997  goto array_cleanup;
2998  }
2999  if (ncolors <= 4)
3000  depth = 2;
3001  else if (ncolors <= 16)
3002  depth = 4;
3003  else
3004  depth = 8;
3005 
3006  /* Average the colors in each octcube leaf and add to colormap table;
3007  * then use carray to hold the colormap index + 1 */
3008  cmap = pixcmapCreate(depth);
3009  for (i = 0, index = 0; i < size; i++) {
3010  if (carray[i] > 0) {
3011  rarray[i] /= carray[i];
3012  garray[i] /= carray[i];
3013  barray[i] /= carray[i];
3014  pixcmapAddColor(cmap, rarray[i], garray[i], barray[i]);
3015  carray[i] = index + 1; /* to avoid storing 0 */
3016  index++;
3017  }
3018  }
3019 
3020  pixd = pixCreate(w, h, depth);
3021  pixSetColormap(pixd, cmap);
3022  pixCopyResolution(pixd, pixs);
3023  pixCopyInputFormat(pixd, pixs);
3024  datad = pixGetData(pixd);
3025  wpld = pixGetWpl(pixd);
3026  for (i = 0; i < h; i++) {
3027  lines = datas + i * wpls;
3028  lined = datad + i * wpld;
3029  for (j = 0; j < w; j++) {
3030  pspixel = lines + j;
3031  extractRGBValues(*pspixel, &rval, &gval, &bval);
3032  octindex = rtab[rval] | gtab[gval] | btab[bval];
3033  switch (depth)
3034  {
3035  case 2:
3036  SET_DATA_DIBIT(lined, j, carray[octindex] - 1);
3037  break;
3038  case 4:
3039  SET_DATA_QBIT(lined, j, carray[octindex] - 1);
3040  break;
3041  case 8:
3042  SET_DATA_BYTE(lined, j, carray[octindex] - 1);
3043  break;
3044  default:
3045  L_WARNING("shouldn't get here\n", procName);
3046  }
3047  }
3048  }
3049 
3050 array_cleanup:
3051  LEPT_FREE(carray);
3052  LEPT_FREE(rarray);
3053  LEPT_FREE(garray);
3054  LEPT_FREE(barray);
3055  LEPT_FREE(rtab);
3056  LEPT_FREE(gtab);
3057  LEPT_FREE(btab);
3058  return pixd;
3059 }
3060 
3061 
3105 PIX *
3107  l_int32 level,
3108  NUMA *na,
3109  l_int32 ncolors,
3110  l_int32 *pnerrors)
3111 {
3112 l_int32 w, h, wpls, wpld, i, j, nerrors;
3113 l_int32 ncubes, depth, cindex, oval;
3114 l_int32 rval, gval, bval;
3115 l_int32 *octarray;
3116 l_uint32 octindex;
3117 l_uint32 *rtab, *gtab, *btab;
3118 l_uint32 *lines, *lined, *datas, *datad, *ppixel;
3119 l_uint32 *colorarray;
3120 PIX *pixd;
3121 PIXCMAP *cmap;
3122 
3123  PROCNAME("pixFewColorsOctcubeQuant2");
3124 
3125  if (!pixs)
3126  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
3127  if (pixGetDepth(pixs) != 32)
3128  return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
3129  if (level < 3 || level > 6)
3130  return (PIX *)ERROR_PTR("level not in {4, 5, 6}", procName, NULL);
3131  if (ncolors > 256)
3132  return (PIX *)ERROR_PTR("ncolors > 256", procName, NULL);
3133  if (pnerrors)
3134  *pnerrors = UNDEF;
3135 
3136  pixd = NULL;
3137 
3138  /* Represent the image with a set of leaf octcubes
3139  * at 'level', one for each color. */
3140  rtab = gtab = btab = NULL;
3141  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
3142 
3143  /* The octarray will give a ptr from the octcube to the colorarray */
3144  ncubes = numaGetCount(na);
3145  octarray = (l_int32 *)LEPT_CALLOC(ncubes, sizeof(l_int32));
3146 
3147  /* The colorarray will hold the colors of the first pixel
3148  * that lands in the leaf octcube. After filling, it is
3149  * used to generate the colormap. */
3150  colorarray = (l_uint32 *)LEPT_CALLOC(ncolors + 1, sizeof(l_uint32));
3151  if (!octarray || !colorarray) {
3152  L_ERROR("octarray or colorarray not made\n", procName);
3153  goto cleanup_arrays;
3154  }
3155 
3156  /* Determine the output depth from the number of colors */
3157  pixGetDimensions(pixs, &w, &h, NULL);
3158  datas = pixGetData(pixs);
3159  wpls = pixGetWpl(pixs);
3160  if (ncolors <= 4)
3161  depth = 2;
3162  else if (ncolors <= 16)
3163  depth = 4;
3164  else /* ncolors <= 256 */
3165  depth = 8;
3166 
3167  if ((pixd = pixCreate(w, h, depth)) == NULL) {
3168  L_ERROR("pixd not made\n", procName);
3169  goto cleanup_arrays;
3170  }
3171  pixCopyResolution(pixd, pixs);
3172  pixCopyInputFormat(pixd, pixs);
3173  datad = pixGetData(pixd);
3174  wpld = pixGetWpl(pixd);
3175 
3176  /* For each pixel, get the octree index for its leaf octcube.
3177  * Check if a pixel has already been found in this octcube.
3178  * ~ If not yet found, save that color in the colorarray
3179  * and save the cindex in the octarray.
3180  * ~ If already found, compare the pixel color with the
3181  * color in the colorarray, and note if it differs.
3182  * Then set the dest pixel value to the cindex - 1, which
3183  * will be the cmap index for this color. */
3184  cindex = 1; /* start with 1 */
3185  nerrors = 0;
3186  for (i = 0; i < h; i++) {
3187  lines = datas + i * wpls;
3188  lined = datad + i * wpld;
3189  for (j = 0; j < w; j++) {
3190  ppixel = lines + j;
3191  extractRGBValues(*ppixel, &rval, &gval, &bval);
3192  octindex = rtab[rval] | gtab[gval] | btab[bval];
3193  oval = octarray[octindex];
3194  if (oval == 0) {
3195  octarray[octindex] = cindex;
3196  colorarray[cindex] = *ppixel;
3197  setPixelLow(lined, j, depth, cindex - 1);
3198  cindex++;
3199  } else { /* already have seen this color; is it unique? */
3200  setPixelLow(lined, j, depth, oval - 1);
3201  if (colorarray[oval] != *ppixel)
3202  nerrors++;
3203  }
3204  }
3205  }
3206  if (pnerrors)
3207  *pnerrors = nerrors;
3208 
3209 #if DEBUG_FEW_COLORS
3210  lept_stderr("ncubes = %d, ncolors = %d\n", ncubes, ncolors);
3211  for (i = 0; i < ncolors; i++)
3212  lept_stderr("color[%d] = %x\n", i, colorarray[i + 1]);
3213 #endif /* DEBUG_FEW_COLORS */
3214 
3215  /* Make the colormap. */
3216  cmap = pixcmapCreate(depth);
3217  for (i = 0; i < ncolors; i++) {
3218  ppixel = colorarray + i + 1;
3219  extractRGBValues(*ppixel, &rval, &gval, &bval);
3220  pixcmapAddColor(cmap, rval, gval, bval);
3221  }
3222  pixSetColormap(pixd, cmap);
3223 
3224 cleanup_arrays:
3225  LEPT_FREE(octarray);
3226  LEPT_FREE(colorarray);
3227  LEPT_FREE(rtab);
3228  LEPT_FREE(gtab);
3229  LEPT_FREE(btab);
3230 
3231  return pixd;
3232 }
3233 
3234 
3294 PIX *
3296  l_int32 level,
3297  l_int32 darkthresh,
3298  l_int32 lightthresh,
3299  l_int32 diffthresh,
3300  l_float32 minfract,
3301  l_int32 maxspan)
3302 {
3303 l_int32 i, j, w, h, wplc, wplm, wpld, ncolors, index;
3304 l_int32 rval, gval, bval, val, minval, maxval;
3305 l_int32 *lut;
3306 l_uint32 *datac, *datam, *datad, *linec, *linem, *lined;
3307 PIX *pix1, *pixc, *pixm, *pixg, *pixd;
3308 PIXCMAP *cmap, *cmapd;
3309 
3310  PROCNAME("pixFewColorsOctcubeQuantMixed");
3311 
3312  if (!pixs || pixGetDepth(pixs) != 32)
3313  return (PIX *)ERROR_PTR("pixs undefined or not 32 bpp", procName, NULL);
3314  if (level <= 0) level = 3;
3315  if (level > 6)
3316  return (PIX *)ERROR_PTR("invalid level", procName, NULL);
3317  if (darkthresh <= 0) darkthresh = 20;
3318  if (lightthresh <= 0) lightthresh = 244;
3319  if (diffthresh <= 0) diffthresh = 20;
3320  if (minfract <= 0.0) minfract = 0.05;
3321  if (maxspan <= 2) maxspan = 15;
3322 
3323  /* Start with a simple fixed octcube quantizer. */
3324  if ((pix1 = pixFewColorsOctcubeQuant1(pixs, level)) == NULL)
3325  return (PIX *)ERROR_PTR("too many colors", procName, NULL);
3326  pixc = pixConvertTo8(pix1, 1); /* must be 8 bpp */
3327  pixDestroy(&pix1);
3328 
3329  /* Identify and save color entries in the colormap. Set up a LUT
3330  * that returns -1 for any gray pixel. */
3331  cmap = pixGetColormap(pixc);
3332  ncolors = pixcmapGetCount(cmap);
3333  cmapd = pixcmapCreate(8);
3334  lut = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
3335  for (i = 0; i < 256; i++)
3336  lut[i] = -1;
3337  for (i = 0, index = 0; i < ncolors; i++) {
3338  pixcmapGetColor(cmap, i, &rval, &gval, &bval);
3339  minval = L_MIN(rval, gval);
3340  minval = L_MIN(minval, bval);
3341  if (minval > lightthresh) /* near white */
3342  continue;
3343  maxval = L_MAX(rval, gval);
3344  maxval = L_MAX(maxval, bval);
3345  if (maxval < darkthresh) /* near black */
3346  continue;
3347 
3348  /* Use the max diff between components to test for color */
3349  if (maxval - minval >= diffthresh) {
3350  pixcmapAddColor(cmapd, rval, gval, bval);
3351  lut[i] = index;
3352  index++;
3353  }
3354  }
3355 
3356  /* Generate dest pix with just the color pixels set to their
3357  * colormap indices. At the same time, make a 1 bpp mask
3358  * of the non-color pixels */
3359  pixGetDimensions(pixs, &w, &h, NULL);
3360  pixd = pixCreate(w, h, 8);
3361  pixSetColormap(pixd, cmapd);
3362  pixm = pixCreate(w, h, 1);
3363  datac = pixGetData(pixc);
3364  datam = pixGetData(pixm);
3365  datad = pixGetData(pixd);
3366  wplc = pixGetWpl(pixc);
3367  wplm = pixGetWpl(pixm);
3368  wpld = pixGetWpl(pixd);
3369  for (i = 0; i < h; i++) {
3370  linec = datac + i * wplc;
3371  linem = datam + i * wplm;
3372  lined = datad + i * wpld;
3373  for (j = 0; j < w; j++) {
3374  val = GET_DATA_BYTE(linec, j);
3375  if (lut[val] == -1)
3376  SET_DATA_BIT(linem, j);
3377  else
3378  SET_DATA_BYTE(lined, j, lut[val]);
3379  }
3380  }
3381 
3382  /* Fill in the gray values. Use a grayscale version of pixs
3383  * as input, along with the mask over the actual gray pixels. */
3384  pixg = pixConvertTo8(pixs, 0);
3385  pixGrayQuantFromHisto(pixd, pixg, pixm, minfract, maxspan);
3386 
3387  LEPT_FREE(lut);
3388  pixDestroy(&pixc);
3389  pixDestroy(&pixm);
3390  pixDestroy(&pixg);
3391  return pixd;
3392 }
3393 
3394 
3395 /*---------------------------------------------------------------------------*
3396  * Fixed partition octcube quantization with RGB output *
3397  *---------------------------------------------------------------------------*/
3414 PIX *
3416  l_int32 level)
3417 {
3418 l_int32 w, h, wpls, wpld, i, j;
3419 l_int32 rval, gval, bval;
3420 l_uint32 octindex;
3421 l_uint32 *rtab, *gtab, *btab;
3422 l_uint32 *lines, *lined, *datas, *datad;
3423 PIX *pixd;
3424 
3425  PROCNAME("pixFixedOctcubeQuantGenRGB");
3426 
3427  if (!pixs)
3428  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
3429  if (pixGetDepth(pixs) != 32)
3430  return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
3431  if (level < 1 || level > 6)
3432  return (PIX *)ERROR_PTR("level not in {1,...6}", procName, NULL);
3433 
3434  if (makeRGBToIndexTables(level, &rtab, &gtab, &btab))
3435  return (PIX *)ERROR_PTR("tables not made", procName, NULL);
3436 
3437  pixGetDimensions(pixs, &w, &h, NULL);
3438  pixd = pixCreate(w, h, 32);
3439  pixCopyResolution(pixd, pixs);
3440  pixCopyInputFormat(pixd, pixs);
3441  datad = pixGetData(pixd);
3442  wpld = pixGetWpl(pixd);
3443  datas = pixGetData(pixs);
3444  wpls = pixGetWpl(pixs);
3445  for (i = 0; i < h; i++) {
3446  lines = datas + i * wpls;
3447  lined = datad + i * wpld;
3448  for (j = 0; j < w; j++) {
3449  extractRGBValues(lines[j], &rval, &gval, &bval);
3450  octindex = rtab[rval] | gtab[gval] | btab[bval];
3451  getRGBFromOctcube(octindex, level, &rval, &gval, &bval);
3452  composeRGBPixel(rval, gval, bval, lined + j);
3453  }
3454  }
3455 
3456  LEPT_FREE(rtab);
3457  LEPT_FREE(gtab);
3458  LEPT_FREE(btab);
3459  return pixd;
3460 }
3461 
3462 
3463 /*------------------------------------------------------------------*
3464  * Color quantize RGB image using existing colormap *
3465  *------------------------------------------------------------------*/
3487 PIX *
3489  PIXCMAP *cmap,
3490  l_int32 mindepth,
3491  l_int32 level,
3492  l_int32 metric)
3493 {
3494 l_int32 d;
3495 
3496  PROCNAME("pixQuantFromCmap");
3497 
3498  if (!pixs)
3499  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
3500  if (mindepth != 2 && mindepth != 4 && mindepth != 8)
3501  return (PIX *)ERROR_PTR("invalid mindepth", procName, NULL);
3502  d = pixGetDepth(pixs);
3503  if (d == 8)
3504  return pixGrayQuantFromCmap(pixs, cmap, mindepth);
3505  else if (d == 32)
3506  return pixOctcubeQuantFromCmap(pixs, cmap, mindepth,
3507  level, metric);
3508  else
3509  return (PIX *)ERROR_PTR("d not 8 or 32 bpp", procName, NULL);
3510 }
3511 
3512 
3513 
3576 PIX *
3578  PIXCMAP *cmap,
3579  l_int32 mindepth,
3580  l_int32 level,
3581  l_int32 metric)
3582 {
3583 l_int32 *cmaptab;
3584 l_uint32 *rtab, *gtab, *btab;
3585 PIX *pixd;
3586 
3587  PROCNAME("pixOctcubeQuantFromCmap");
3588 
3589  if (!pixs)
3590  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
3591  if (pixGetDepth(pixs) != 32)
3592  return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
3593  if (!cmap)
3594  return (PIX *)ERROR_PTR("cmap not defined", procName, NULL);
3595  if (mindepth != 2 && mindepth != 4 && mindepth != 8)
3596  return (PIX *)ERROR_PTR("invalid mindepth", procName, NULL);
3597  if (level < 1 || level > 6)
3598  return (PIX *)ERROR_PTR("level not in {1...6}", procName, NULL);
3599  if (metric != L_MANHATTAN_DISTANCE && metric != L_EUCLIDEAN_DISTANCE)
3600  return (PIX *)ERROR_PTR("invalid metric", procName, NULL);
3601 
3602  /* Set up the tables to map rgb to the nearest colormap index */
3603  rtab = gtab = btab = NULL;
3604  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
3605  cmaptab = pixcmapToOctcubeLUT(cmap, level, metric);
3606 
3607  pixd = pixOctcubeQuantFromCmapLUT(pixs, cmap, mindepth,
3608  cmaptab, rtab, gtab, btab);
3609 
3610  LEPT_FREE(cmaptab);
3611  LEPT_FREE(rtab);
3612  LEPT_FREE(gtab);
3613  LEPT_FREE(btab);
3614  return pixd;
3615 }
3616 
3617 
3642 static PIX *
3644  PIXCMAP *cmap,
3645  l_int32 mindepth,
3646  l_int32 *cmaptab,
3647  l_uint32 *rtab,
3648  l_uint32 *gtab,
3649  l_uint32 *btab)
3650 {
3651 l_int32 i, j, w, h, depth, wpls, wpld;
3652 l_int32 rval, gval, bval, index;
3653 l_uint32 octindex;
3654 l_uint32 *lines, *lined, *datas, *datad;
3655 PIX *pixd;
3656 PIXCMAP *cmapc;
3657 
3658  PROCNAME("pixOctcubeQuantFromCmapLUT");
3659 
3660  if (!pixs)
3661  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
3662  if (pixGetDepth(pixs) != 32)
3663  return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
3664  if (!cmap)
3665  return (PIX *)ERROR_PTR("cmap not defined", procName, NULL);
3666  if (mindepth != 2 && mindepth != 4 && mindepth != 8)
3667  return (PIX *)ERROR_PTR("invalid mindepth", procName, NULL);
3668  if (!rtab || !gtab || !btab || !cmaptab)
3669  return (PIX *)ERROR_PTR("tables not all defined", procName, NULL);
3670 
3671  /* Init dest pix (with minimum bpp depending on cmap) */
3672  pixcmapGetMinDepth(cmap, &depth);
3673  depth = L_MAX(depth, mindepth);
3674  pixGetDimensions(pixs, &w, &h, NULL);
3675  if ((pixd = pixCreate(w, h, depth)) == NULL)
3676  return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
3677  cmapc = pixcmapCopy(cmap);
3678  pixSetColormap(pixd, cmapc);
3679  pixCopyResolution(pixd, pixs);
3680  pixCopyInputFormat(pixd, pixs);
3681 
3682  /* Insert the colormap index of the color nearest to the input pixel */
3683  datas = pixGetData(pixs);
3684  datad = pixGetData(pixd);
3685  wpls = pixGetWpl(pixs);
3686  wpld = pixGetWpl(pixd);
3687  for (i = 0; i < h; i++) {
3688  lines = datas + i * wpls;
3689  lined = datad + i * wpld;
3690  for (j = 0; j < w; j++) {
3691  extractRGBValues(lines[j], &rval, &gval, &bval);
3692  /* Map from rgb to octcube index */
3693  getOctcubeIndexFromRGB(rval, gval, bval, rtab, gtab, btab,
3694  &octindex);
3695  /* Map from octcube index to nearest colormap index */
3696  index = cmaptab[octindex];
3697  if (depth == 2)
3698  SET_DATA_DIBIT(lined, j, index);
3699  else if (depth == 4)
3700  SET_DATA_QBIT(lined, j, index);
3701  else /* depth == 8 */
3702  SET_DATA_BYTE(lined, j, index);
3703  }
3704  }
3705 
3706  return pixd;
3707 }
3708 
3709 
3710 /*---------------------------------------------------------------------------*
3711  * Generation of octcube histogram *
3712  *---------------------------------------------------------------------------*/
3726 NUMA *
3728  l_int32 level,
3729  l_int32 *pncolors)
3730 {
3731 l_int32 size, i, j, w, h, wpl, ncolors, val;
3732 l_int32 rval, gval, bval;
3733 l_uint32 octindex;
3734 l_uint32 *rtab, *gtab, *btab;
3735 l_uint32 *data, *line;
3736 l_float32 *array;
3737 NUMA *na;
3738 
3739  PROCNAME("pixOctcubeHistogram");
3740 
3741  if (pncolors) *pncolors = 0;
3742  if (!pixs)
3743  return (NUMA *)ERROR_PTR("pixs not defined", procName, NULL);
3744  if (pixGetDepth(pixs) != 32)
3745  return (NUMA *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
3746 
3747  pixGetDimensions(pixs, &w, &h, NULL);
3748  wpl = pixGetWpl(pixs);
3749  data = pixGetData(pixs);
3750 
3751  if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
3752  return (NUMA *)ERROR_PTR("size not returned", procName, NULL);
3753  rtab = gtab = btab = NULL;
3754  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
3755 
3756  if ((na = numaCreate(size)) == NULL) {
3757  L_ERROR("na not made\n", procName);
3758  goto cleanup_arrays;
3759  }
3760  numaSetCount(na, size);
3761  array = numaGetFArray(na, L_NOCOPY);
3762 
3763  for (i = 0; i < h; i++) {
3764  line = data + i * wpl;
3765  for (j = 0; j < w; j++) {
3766  extractRGBValues(line[j], &rval, &gval, &bval);
3767  octindex = rtab[rval] | gtab[gval] | btab[bval];
3768 #if DEBUG_OCTINDEX
3769  if ((level == 1 && octindex > 7) ||
3770  (level == 2 && octindex > 63) ||
3771  (level == 3 && octindex > 511) ||
3772  (level == 4 && octindex > 4097) ||
3773  (level == 5 && octindex > 32783) ||
3774  (level == 6 && octindex > 262271)) {
3775  lept_stderr("level = %d, octindex = %d, index error!\n",
3776  level, octindex);
3777  continue;
3778  }
3779 #endif /* DEBUG_OCTINDEX */
3780  array[octindex] += 1.0;
3781  }
3782  }
3783 
3784  if (pncolors) {
3785  for (i = 0, ncolors = 0; i < size; i++) {
3786  numaGetIValue(na, i, &val);
3787  if (val > 0)
3788  ncolors++;
3789  }
3790  *pncolors = ncolors;
3791  }
3792 
3793 cleanup_arrays:
3794  LEPT_FREE(rtab);
3795  LEPT_FREE(gtab);
3796  LEPT_FREE(btab);
3797  return na;
3798 }
3799 
3800 
3801 /*------------------------------------------------------------------*
3802  * Get filled octcube table from colormap *
3803  *------------------------------------------------------------------*/
3849 l_int32 *
3851  l_int32 level,
3852  l_int32 metric)
3853 {
3854 l_int32 i, k, size, ncolors, mindist, dist, mincolor, index;
3855 l_int32 rval, gval, bval; /* color at center of the octcube */
3856 l_int32 *rmap, *gmap, *bmap, *tab;
3857 
3858  PROCNAME("pixcmapToOctcubeLUT");
3859 
3860  if (!cmap)
3861  return (l_int32 *)ERROR_PTR("cmap not defined", procName, NULL);
3862  if (level < 1 || level > 6)
3863  return (l_int32 *)ERROR_PTR("level not in {1...6}", procName, NULL);
3864  if (metric != L_MANHATTAN_DISTANCE && metric != L_EUCLIDEAN_DISTANCE)
3865  return (l_int32 *)ERROR_PTR("invalid metric", procName, NULL);
3866 
3867  if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
3868  return (l_int32 *)ERROR_PTR("size not returned", procName, NULL);
3869  if ((tab = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32))) == NULL)
3870  return (l_int32 *)ERROR_PTR("tab not allocated", procName, NULL);
3871 
3872  ncolors = pixcmapGetCount(cmap);
3873  pixcmapToArrays(cmap, &rmap, &gmap, &bmap, NULL);
3874 
3875  /* Assign based on the closest octcube center to the cmap color */
3876  for (i = 0; i < size; i++) {
3877  getRGBFromOctcube(i, level, &rval, &gval, &bval);
3878  mindist = 1000000;
3879  mincolor = 0; /* irrelevant init */
3880  for (k = 0; k < ncolors; k++) {
3881  if (metric == L_MANHATTAN_DISTANCE) {
3882  dist = L_ABS(rval - rmap[k]) + L_ABS(gval - gmap[k]) +
3883  L_ABS(bval - bmap[k]);
3884  } else { /* L_EUCLIDEAN_DISTANCE */
3885  dist = (rval - rmap[k]) * (rval - rmap[k]) +
3886  (gval - gmap[k]) * (gval - gmap[k]) +
3887  (bval - bmap[k]) * (bval - bmap[k]);
3888  }
3889  if (dist < mindist) {
3890  mindist = dist;
3891  mincolor = k;
3892  }
3893  }
3894  tab[i] = mincolor;
3895  }
3896 
3897  /* Reset black and white if available in the colormap.
3898  * The darkest octcube is at octindex 0.
3899  * The lightest octcube is at the max octindex. */
3900  pixcmapGetNearestIndex(cmap, 0, 0, 0, &index);
3901  pixcmapGetColor(cmap, index, &rval, &gval, &bval);
3902  if (rval < 7 && gval < 7 && bval < 7) {
3903  tab[0] = index;
3904  }
3905  pixcmapGetNearestIndex(cmap, 255, 255, 255, &index);
3906  pixcmapGetColor(cmap, index, &rval, &gval, &bval);
3907  if (rval > 248 && gval > 248 && bval > 248) {
3908  tab[(1 << (3 * level)) - 1] = index;
3909  }
3910 
3911  LEPT_FREE(rmap);
3912  LEPT_FREE(gmap);
3913  LEPT_FREE(bmap);
3914  return tab;
3915 }
3916 
3917 
3918 /*------------------------------------------------------------------*
3919  * Strip out unused elements in colormap *
3920  *------------------------------------------------------------------*/
3935 l_ok
3937 {
3938 l_int32 i, j, w, h, d, nc, wpls, val, newval, index, zerofound;
3939 l_int32 rval, gval, bval;
3940 l_uint32 *datas, *lines;
3941 l_int32 *histo, *map1, *map2;
3942 PIXCMAP *cmap, *cmapd;
3943 
3944  PROCNAME("pixRemoveUnusedColors");
3945 
3946  if (!pixs)
3947  return ERROR_INT("pixs not defined", procName, 1);
3948  if ((cmap = pixGetColormap(pixs)) == NULL)
3949  return 0;
3950 
3951  d = pixGetDepth(pixs);
3952  if (d != 2 && d != 4 && d != 8)
3953  return ERROR_INT("d not in {2, 4, 8}", procName, 1);
3954 
3955  /* Find which indices are actually used */
3956  nc = pixcmapGetCount(cmap);
3957  if ((histo = (l_int32 *)LEPT_CALLOC(nc, sizeof(l_int32))) == NULL)
3958  return ERROR_INT("histo not made", procName, 1);
3959  pixGetDimensions(pixs, &w, &h, NULL);
3960  wpls = pixGetWpl(pixs);
3961  datas = pixGetData(pixs);
3962  for (i = 0; i < h; i++) {
3963  lines = datas + i * wpls;
3964  for (j = 0; j < w; j++) {
3965  switch (d)
3966  {
3967  case 2:
3968  val = GET_DATA_DIBIT(lines, j);
3969  break;
3970  case 4:
3971  val = GET_DATA_QBIT(lines, j);
3972  break;
3973  case 8:
3974  val = GET_DATA_BYTE(lines, j);
3975  break;
3976  default:
3977  LEPT_FREE(histo);
3978  return ERROR_INT("switch ran off end!", procName, 1);
3979  }
3980  if (val >= nc) {
3981  L_WARNING("cmap index out of bounds!\n", procName);
3982  continue;
3983  }
3984  histo[val]++;
3985  }
3986  }
3987 
3988  /* Check if there are any zeroes. If none, quit. */
3989  zerofound = FALSE;
3990  for (i = 0; i < nc; i++) {
3991  if (histo[i] == 0) {
3992  zerofound = TRUE;
3993  break;
3994  }
3995  }
3996  if (!zerofound) {
3997  LEPT_FREE(histo);
3998  return 0;
3999  }
4000 
4001  /* Generate mapping tables between indices */
4002  map1 = (l_int32 *)LEPT_CALLOC(nc, sizeof(l_int32));
4003  map2 = (l_int32 *)LEPT_CALLOC(nc, sizeof(l_int32));
4004  index = 0;
4005  for (i = 0; i < nc; i++) {
4006  if (histo[i] != 0) {
4007  map1[index] = i; /* get old index from new */
4008  map2[i] = index; /* get new index from old */
4009  index++;
4010  }
4011  }
4012 
4013  /* Generate new colormap and attach to pixs */
4014  cmapd = pixcmapCreate(d);
4015  for (i = 0; i < index; i++) {
4016  pixcmapGetColor(cmap, map1[i], &rval, &gval, &bval);
4017  pixcmapAddColor(cmapd, rval, gval, bval);
4018  }
4019  pixSetColormap(pixs, cmapd);
4020 
4021  /* Map pixel (index) values to new cmap */
4022  for (i = 0; i < h; i++) {
4023  lines = datas + i * wpls;
4024  for (j = 0; j < w; j++) {
4025  switch (d)
4026  {
4027  case 2:
4028  val = GET_DATA_DIBIT(lines, j);
4029  newval = map2[val];
4030  SET_DATA_DIBIT(lines, j, newval);
4031  break;
4032  case 4:
4033  val = GET_DATA_QBIT(lines, j);
4034  newval = map2[val];
4035  SET_DATA_QBIT(lines, j, newval);
4036  break;
4037  case 8:
4038  val = GET_DATA_BYTE(lines, j);
4039  newval = map2[val];
4040  SET_DATA_BYTE(lines, j, newval);
4041  break;
4042  default:
4043  LEPT_FREE(histo);
4044  LEPT_FREE(map1);
4045  LEPT_FREE(map2);
4046  return ERROR_INT("switch ran off end!", procName, 1);
4047  }
4048  }
4049  }
4050 
4051  LEPT_FREE(histo);
4052  LEPT_FREE(map1);
4053  LEPT_FREE(map2);
4054  return 0;
4055 }
4056 
4057 
4058 /*------------------------------------------------------------------*
4059  * Find number of occupied octcubes at the specified level *
4060  *------------------------------------------------------------------*/
4081 l_ok
4083  l_int32 level,
4084  l_int32 mincount,
4085  l_float32 minfract,
4086  l_int32 *pncolors)
4087 {
4088 l_int32 i, j, w, h, d, wpl, ncolors, size, octindex;
4089 l_int32 rval, gval, bval;
4090 l_int32 *carray;
4091 l_uint32 *data, *line, *rtab, *gtab, *btab;
4092 
4093  PROCNAME("pixNumberOccupiedOctcubes");
4094 
4095  if (!pncolors)
4096  return ERROR_INT("&ncolors not defined", procName, 1);
4097  *pncolors = 0;
4098  if (!pix)
4099  return ERROR_INT("pix not defined", procName, 1);
4100  pixGetDimensions(pix, &w, &h, &d);
4101  if (d != 32)
4102  return ERROR_INT("pix not 32 bpp", procName, 1);
4103  if (level < 1 || level > 6)
4104  return ERROR_INT("invalid level", procName, 1);
4105  if ((mincount < 0 && minfract < 0) || (mincount >= 0.0 && minfract >= 0.0))
4106  return ERROR_INT("invalid mincount/minfract", procName, 1);
4107  if (mincount == 0 || minfract == 0.0)
4108  mincount = 1;
4109  else if (minfract > 0.0)
4110  mincount = L_MIN(1, (l_int32)(minfract * w * h));
4111 
4112  if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
4113  return ERROR_INT("size not returned", procName, 1);
4114  rtab = gtab = btab = NULL;
4115  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
4116  if ((carray = (l_int32 *)LEPT_CALLOC(size, sizeof(l_int32))) == NULL) {
4117  L_ERROR("carray not made\n", procName);
4118  goto cleanup_arrays;
4119  }
4120 
4121  /* Mark the occupied octcube leaves */
4122  data = pixGetData(pix);
4123  wpl = pixGetWpl(pix);
4124  for (i = 0; i < h; i++) {
4125  line = data + i * wpl;
4126  for (j = 0; j < w; j++) {
4127  extractRGBValues(line[j], &rval, &gval, &bval);
4128  octindex = rtab[rval] | gtab[gval] | btab[bval];
4129  carray[octindex]++;
4130  }
4131  }
4132 
4133  /* Count them */
4134  for (i = 0, ncolors = 0; i < size; i++) {
4135  if (carray[i] >= mincount)
4136  ncolors++;
4137  }
4138  *pncolors = ncolors;
4139 
4140 cleanup_arrays:
4141  LEPT_FREE(carray);
4142  LEPT_FREE(rtab);
4143  LEPT_FREE(gtab);
4144  LEPT_FREE(btab);
4145  return 0;
4146 }
PIX * pixOctreeColorQuant(PIX *pixs, l_int32 colors, l_int32 ditherflag)
pixOctreeColorQuant()
Definition: colorquant1.c:535
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:3295
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:3643
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
Definition: heap.c:193
l_int32 * pixcmapToOctcubeLUT(PIXCMAP *cmap, l_int32 level, l_int32 metric)
pixcmapToOctcubeLUT()
Definition: colorquant1.c:3850
l_ok pixcmapGetMinDepth(PIXCMAP *cmap, l_int32 *pmindepth)
pixcmapGetMinDepth()
Definition: colormap.c:765
l_int32 n
Definition: pix.h:164
NUMA * pixOctcubeHistogram(PIX *pixs, l_int32 level, l_int32 *pncolors)
pixOctcubeHistogram()
Definition: colorquant1.c:3727
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:478
PIX * pixGrayQuantFromHisto(PIX *pixd, PIX *pixs, PIX *pixm, l_float32 minfract, l_int32 maxsize)
pixGrayQuantFromHisto()
Definition: grayquant.c:2339
void setPixelLow(l_uint32 *line, l_int32 x, l_int32 depth, l_uint32 val)
setPixelLow()
Definition: pix2.c:679
l_ok pixcmapGetNearestIndex(PIXCMAP *cmap, l_int32 rval, l_int32 gval, l_int32 bval, l_int32 *pindex)
pixcmapGetNearestIndex()
Definition: colormap.c:1353
static PIX * pixOctreeQuantizePixels(PIX *pixs, CQCELL ***cqcaa, l_int32 ditherflag)
pixOctreeQuantizePixels()
Definition: colorquant1.c:974
PIX * pixConvertTo8(PIX *pixs, l_int32 cmapflag)
pixConvertTo8()
Definition: pixconv.c:3133
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306
Definition: pix.h:710
PIX * pixFixedOctcubeQuant256(PIX *pixs, l_int32 ditherflag)
pixFixedOctcubeQuant256()
Definition: colorquant1.c:2802
static void cqcellTreeDestroy(CQCELL ****pcqcaa)
cqcellTreeDestroy()
Definition: colorquant1.c:1289
static l_int32 octcubeGetCount(l_int32 level, l_int32 *psize)
octcubeGetCount()
Definition: colorquant1.c:1619
PIX * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
Definition: pix1.c:315
l_ok pixNumberOccupiedOctcubes(PIX *pix, l_int32 level, l_int32 mincount, l_float32 minfract, l_int32 *pncolors)
pixNumberOccupiedOctcubes()
Definition: colorquant1.c:4082
#define SET_DATA_QBIT(pdata, n, val)
Definition: arrayaccess.h:168
void pixcmapDestroy(PIXCMAP **pcmap)
pixcmapDestroy()
Definition: colormap.c:279
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:194
l_int32 * makeGrayQuantIndexTable(l_int32 nlevels)
makeGrayQuantIndexTable()
Definition: grayquant.c:1848
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1763
l_ok numaSetCount(NUMA *na, l_int32 newcount)
numaSetCount()
Definition: numabasic.c:685
void lheapDestroy(L_HEAP **plh, l_int32 freeflag)
lheapDestroy()
Definition: heap.c:154
PIX * pixScaleBySampling(PIX *pixs, l_float32 scalex, l_float32 scaley)
pixScaleBySampling()
Definition: scale1.c:1338
PIX * pixFewColorsOctcubeQuant2(PIX *pixs, l_int32 level, NUMA *na, l_int32 ncolors, l_int32 *pnerrors)
pixFewColorsOctcubeQuant2()
Definition: colorquant1.c:3106
l_ok pixSetColormap(PIX *pix, PIXCMAP *colormap)
pixSetColormap()
Definition: pix1.c:1699
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:1985
#define SET_DATA_DIBIT(pdata, n, val)
Definition: arrayaccess.h:149
PIXCMAP * pixcmapCreate(l_int32 depth)
pixcmapCreate()
Definition: colormap.c:125
static CQCELL *** cqcellTreeCreate(void)
cqcellTreeCreate()
Definition: colorquant1.c:1260
L_HEAP * lheapCreate(l_int32 n, l_int32 direction)
lheapCreate()
Definition: heap.c:112
l_ok numaGetIValue(NUMA *na, l_int32 index, l_int32 *pival)
numaGetIValue()
Definition: numabasic.c:754
Definition: array.h:70
l_ok makeRGBToIndexTables(l_int32 cqlevels, l_uint32 **prtab, l_uint32 **pgtab, l_uint32 **pbtab)
makeRGBToIndexTables()
Definition: colorquant1.c:1353
PIX * pixOctcubeQuantFromCmap(PIX *pixs, PIXCMAP *cmap, l_int32 mindepth, l_int32 level, l_int32 metric)
pixOctcubeQuantFromCmap()
Definition: colorquant1.c:3577
l_int32 numaGetCount(NUMA *na)
numaGetCount()
Definition: numabasic.c:658
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:1462
l_ok pixcmapGetColor(PIXCMAP *cmap, l_int32 index, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
pixcmapGetColor()
Definition: colormap.c:824
#define SET_DATA_BYTE(pdata, n, val)
Definition: arrayaccess.h:198
#define GET_DATA_QBIT(pdata, n)
Definition: arrayaccess.h:164
#define GET_DATA_BYTE(pdata, n)
Definition: arrayaccess.h:188
void * lheapRemove(L_HEAP *lh)
lheapRemove()
Definition: heap.c:251
PIX * pixClone(PIX *pixs)
pixClone()
Definition: pix1.c:593
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:621
l_ok pixGetRGBLine(PIX *pixs, l_int32 row, l_uint8 *bufr, l_uint8 *bufg, l_uint8 *bufb)
pixGetRGBLine()
Definition: pix2.c:2897
Definition: heap.h:77
l_ok pixcmapResetColor(PIXCMAP *cmap, l_int32 index, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapResetColor()
Definition: colormap.c:966
PIX * pixFewColorsOctcubeQuant1(PIX *pixs, l_int32 level)
pixFewColorsOctcubeQuant1()
Definition: colorquant1.c:2936
PIX * pixGrayQuantFromCmap(PIX *pixs, PIXCMAP *cmap, l_int32 mindepth)
pixGrayQuantFromCmap()
Definition: grayquant.c:2562
void numaDestroy(NUMA **pna)
numaDestroy()
Definition: numabasic.c:366
static void getRGBFromOctcube(l_int32 cubeindex, l_int32 level, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
getRGBFromOctcube()
Definition: colorquant1.c:1508
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1113
PIX * pixFixedOctcubeQuantGenRGB(PIX *pixs, l_int32 level)
pixFixedOctcubeQuantGenRGB()
Definition: colorquant1.c:3415
PIX * pixOctreeColorQuantGeneral(PIX *pixs, l_int32 colors, l_int32 ditherflag, l_float32 validthresh, l_float32 colorthresh)
pixOctreeColorQuantGeneral()
Definition: colorquant1.c:601
PIX * pixOctreeQuantNumColors(PIX *pixs, l_int32 maxcolors, l_int32 subsample)
pixOctreeQuantNumColors()
Definition: colorquant1.c:2256
l_ok pixColorFraction(PIX *pixs, l_int32 darkthresh, l_int32 lightthresh, l_int32 diffthresh, l_int32 factor, l_float32 *ppixfract, l_float32 *pcolorfract)
pixColorFraction()
Definition: colorcontent.c:494
l_float32 * numaGetFArray(NUMA *na, l_int32 copyflag)
numaGetFArray()
Definition: numabasic.c:892
#define GET_DATA_DIBIT(pdata, n)
Definition: arrayaccess.h:145
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:1190
l_ok pixRemoveUnusedColors(PIX *pixs)
pixRemoveUnusedColors()
Definition: colorquant1.c:3936
Definition: pix.h:138
static l_int32 getOctcubeIndices(l_int32 rgbindex, l_int32 level, l_int32 *pbindex, l_int32 *psindex)
getOctcubeIndices()
Definition: colorquant1.c:1585
PIX * pixOctreeQuantByPopulation(PIX *pixs, l_int32 level, l_int32 ditherflag)
pixOctreeQuantByPopulation()
Definition: colorquant1.c:1693
l_int32 pixcmapGetCount(const PIXCMAP *cmap)
pixcmapGetCount()
Definition: colormap.c:708
PIX * pixOctcubeQuantMixedWithGray(PIX *pixs, l_int32 depth, l_int32 graylevels, l_int32 delta)
pixOctcubeQuantMixedWithGray()
Definition: colorquant1.c:2583
static CQCELL *** octreeGenerateAndPrune(PIX *pixs, l_int32 colors, l_int32 reservedcolors, PIXCMAP **pcmap)
octreeGenerateAndPrune()
Definition: colorquant1.c:724
l_ok composeRGBPixel(l_int32 rval, l_int32 gval, l_int32 bval, l_uint32 *ppixel)
composeRGBPixel()
Definition: pix2.c:2751
PIXCMAP * pixcmapCopy(const PIXCMAP *cmaps)
pixcmapCopy()
Definition: colormap.c:248
l_ok pixcmapAddColor(PIXCMAP *cmap, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapAddColor()
Definition: colormap.c:414
void extractRGBValues(l_uint32 pixel, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
extractRGBValues()
Definition: pix2.c:2820
PIX * pixQuantFromCmap(PIX *pixs, PIXCMAP *cmap, l_int32 mindepth, l_int32 level, l_int32 metric)
pixQuantFromCmap()
Definition: colorquant1.c:3488
#define SET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:127
l_ok pixcmapToArrays(const PIXCMAP *cmap, l_int32 **prmap, l_int32 **pgmap, l_int32 **pbmap, l_int32 **pamap)
pixcmapToArrays()
Definition: colormap.c:2068
l_ok pixcmapGetRankIntensity(PIXCMAP *cmap, l_float32 rankval, l_int32 *pindex)
pixcmapGetRankIntensity()
Definition: colormap.c:1302