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 */
161struct ColorQuantCell
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};
169typedef struct ColorQuantCell CQCELL;
170
171 /* Constants for pixOctreeColorQuant() */
172static const l_int32 CqNLevels = 5; /* only 4, 5 and 6 are allowed */
173static const l_int32 CqReservedColors = 64; /* to allow for level 2 */
174 /* remainder CTEs */
175static const l_int32 ExtraReservedColors = 25; /* to avoid running out */
176static const l_int32 TreeGenWidth = 350; /* big enough for good stats */
177static 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 * */
192struct OctcubeQuantCell
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};
199typedef 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 */
207struct L_OctcubePop
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};
215typedef 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
228static const l_int32 FIXED_DIF_CAP = 0;
229static const l_int32 POP_DIF_CAP = 40;
230
231
232 /* Static octree helper function */
233static 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 */
238static CQCELL ***octreeGenerateAndPrune(PIX *pixs, l_int32 colors,
239 l_int32 reservedcolors,
240 PIXCMAP **pcmap);
241static PIX *pixOctreeQuantizePixels(PIX *pixs, CQCELL ***cqcaa,
242 l_int32 ditherflag);
243static CQCELL ***cqcellTreeCreate(void);
244static void cqcellTreeDestroy(CQCELL ****pcqcaa);
245
246 /* Static helper octcube index functions */
247static void getRGBFromOctcube(l_int32 cubeindex, l_int32 level,
248 l_int32 *prval, l_int32 *pgval, l_int32 *pbval);
249static l_int32 getOctcubeIndices(l_int32 rgbindex, l_int32 level,
250 l_int32 *pbindex, l_int32 *psindex);
251static l_int32 octcubeGetCount(l_int32 level, l_int32 *psize);
252
253 /* Static function to perform octcube-indexed dithering */
254static 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 */
259static 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 *-------------------------------------------------------------------------*/
534PIX *
535pixOctreeColorQuant(PIX *pixs,
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
600PIX *
601pixOctreeColorQuantGeneral(PIX *pixs,
602 l_int32 colors,
603 l_int32 ditherflag,
604 l_float32 validthresh,
605 l_float32 colorthresh)
606{
607l_int32 w, h, minside, factor, index, rval, gval, bval;
608l_float32 scalefactor;
609l_float32 pixfract; /* fraction neither near white nor black */
610l_float32 colorfract; /* fraction with color of the pixfract population */
611CQCELL ***cqcaa;
612PIX *pixd, *pixsub;
613PIXCMAP *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
723static CQCELL ***
724octreeGenerateAndPrune(PIX *pixs,
725 l_int32 colors,
726 l_int32 reservedcolors,
727 PIXCMAP **pcmap)
728{
729l_int32 rval, gval, bval, cindex;
730l_int32 level, ncells, octindex;
731l_int32 w, h, wpls;
732l_int32 i, j, isub;
733l_int32 npix; /* number of remaining pixels to be assigned */
734l_int32 ncolor; /* number of remaining color cells to be used */
735l_int32 ppc; /* ave number of pixels left for each color cell */
736l_int32 rv, gv, bv;
737l_float32 thresholdFactor[] = {0.01f, 0.01f, 1.0f, 1.0f, 1.0f, 1.0f};
738l_float32 thresh; /* factor of ppc for this level */
739l_uint32 *datas, *lines;
740l_uint32 *rtab, *gtab, *btab;
741CQCELL ***cqcaa; /* one array for each octree level */
742CQCELL **cqca, **cqcasub;
743CQCELL *cqc, *cqcsub;
744PIXCMAP *cmap;
745NUMA *nat; /* accumulates levels for threshold cells */
746NUMA *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{
917l_int32 tc[] = {0, 0, 0, 0, 0, 0, 0};
918l_int32 rc[] = {0, 0, 0, 0, 0, 0, 0};
919l_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
973static PIX *
974pixOctreeQuantizePixels(PIX *pixs,
975 CQCELL ***cqcaa,
976 l_int32 ditherflag)
977{
978l_uint8 *bufu8r, *bufu8g, *bufu8b;
979l_int32 rval, gval, bval;
980l_int32 octindex, index;
981l_int32 val1, val2, val3, dif;
982l_int32 w, h, wpls, wpld, i, j, success;
983l_int32 rc, gc, bc;
984l_int32 *buf1r, *buf1g, *buf1b, *buf2r, *buf2g, *buf2b;
985l_uint32 *rtab, *gtab, *btab;
986l_uint32 *datas, *datad, *lines, *lined;
987PIX *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
1148buffer_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
1189static l_int32
1190octreeFindColorCell(l_int32 octindex,
1191 CQCELL ***cqcaa,
1192 l_int32 *pindex,
1193 l_int32 *prval,
1194 l_int32 *pgval,
1195 l_int32 *pbval)
1196{
1197l_int32 level;
1198l_int32 baseindex, subindex;
1199CQCELL *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 *------------------------------------------------------------------*/
1259static CQCELL ***
1260cqcellTreeCreate(void)
1261{
1262l_int32 level, ncells, i;
1263CQCELL ***cqcaa;
1264CQCELL **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
1288static void
1289cqcellTreeDestroy(CQCELL ****pcqcaa)
1290{
1291l_int32 level, ncells, i;
1292CQCELL ***cqcaa;
1293CQCELL **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 *------------------------------------------------------------------*/
1352l_ok
1353makeRGBToIndexTables(l_int32 cqlevels,
1354 l_uint32 **prtab,
1355 l_uint32 **pgtab,
1356 l_uint32 **pbtab)
1357{
1358l_int32 i;
1359l_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
1461void
1462getOctcubeIndexFromRGB(l_int32 rval,
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
1507static void
1508getRGBFromOctcube(l_int32 cubeindex,
1509 l_int32 level,
1510 l_int32 *prval,
1511 l_int32 *pgval,
1512 l_int32 *pbval)
1513{
1514l_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
1584static l_int32
1585getOctcubeIndices(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
1618static l_int32
1619octcubeGetCount(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 *---------------------------------------------------------------------------*/
1692PIX *
1693pixOctreeQuantByPopulation(PIX *pixs,
1694 l_int32 level,
1695 l_int32 ditherflag)
1696{
1697l_int32 w, h, wpls, wpld, i, j, depth, size, ncolors, index;
1698l_int32 rval, gval, bval;
1699l_int32 *rarray, *garray, *barray, *narray, *iarray;
1700l_uint32 octindex, octindex2;
1701l_uint32 *rtab, *gtab, *btab, *rtab2, *gtab2, *btab2;
1702l_uint32 *lines, *lined, *datas, *datad;
1703L_OCTCUBE_POP *opop;
1704L_HEAP *lh;
1705PIX *pixd;
1706PIXCMAP *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
1938array_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
1984static l_int32
1985pixDitherOctindexWithCmap(PIX *pixs,
1986 PIX *pixd,
1987 l_uint32 *rtab,
1988 l_uint32 *gtab,
1989 l_uint32 *btab,
1990 l_int32 *indexmap,
1991 l_int32 difcap)
1992{
1993l_uint8 *bufu8r, *bufu8g, *bufu8b;
1994l_int32 i, j, w, h, wpld, octindex, cmapindex, success;
1995l_int32 rval, gval, bval, rc, gc, bc;
1996l_int32 dif, val1, val2, val3;
1997l_int32 *buf1r, *buf1g, *buf1b, *buf2r, *buf2g, *buf2b;
1998l_uint32 *datad, *lined;
1999PIXCMAP *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
2148buffer_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 *---------------------------------------------------------------------------*/
2255PIX *
2256pixOctreeQuantNumColors(PIX *pixs,
2257 l_int32 maxcolors,
2258 l_int32 subsample)
2259{
2260l_int32 w, h, minside, bpp, wpls, wpld, i, j, actualcolors;
2261l_int32 rval, gval, bval, nbase, nextra, maxlevel, ncubes, val;
2262l_int32 *lut1, *lut2;
2263l_uint32 index;
2264l_uint32 *lines, *lined, *datas, *datad, *pspixel;
2265l_uint32 *rtab, *gtab, *btab;
2266OQCELL *oqc;
2267OQCELL **oqca;
2268L_HEAP *lh;
2269PIX *pixd;
2270PIXCMAP *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 *-------------------------------------------------------------------------*/
2582PIX *
2583pixOctcubeQuantMixedWithGray(PIX *pixs,
2584 l_int32 depth,
2585 l_int32 graylevels,
2586 l_int32 delta)
2587{
2588l_int32 w, h, wpls, wpld, i, j, size, octlevels;
2589l_int32 rval, gval, bval, del, val, midval;
2590l_int32 *carray, *rarray, *garray, *barray;
2591l_int32 *tabval;
2592l_uint32 octindex;
2593l_uint32 *rtab, *gtab, *btab;
2594l_uint32 *lines, *lined, *datas, *datad;
2595PIX *pixd;
2596PIXCMAP *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
2721array_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 *-------------------------------------------------------------------------*/
2801PIX *
2802pixFixedOctcubeQuant256(PIX *pixs,
2803 l_int32 ditherflag)
2804{
2805l_uint8 index;
2806l_int32 rval, gval, bval;
2807l_int32 w, h, wpls, wpld, i, j, cindex;
2808l_uint32 *rtab, *gtab, *btab;
2809l_int32 *itab;
2810l_uint32 *datas, *datad, *lines, *lined;
2811PIX *pixd;
2812PIXCMAP *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 *---------------------------------------------------------------------------*/
2935PIX *
2936pixFewColorsOctcubeQuant1(PIX *pixs,
2937 l_int32 level)
2938{
2939l_int32 w, h, wpls, wpld, i, j, depth, size, ncolors, index;
2940l_int32 rval, gval, bval;
2941l_int32 *carray, *rarray, *garray, *barray;
2942l_uint32 octindex;
2943l_uint32 *rtab, *gtab, *btab;
2944l_uint32 *lines, *lined, *datas, *datad, *pspixel;
2945PIX *pixd;
2946PIXCMAP *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
3050array_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
3105PIX *
3106pixFewColorsOctcubeQuant2(PIX *pixs,
3107 l_int32 level,
3108 NUMA *na,
3109 l_int32 ncolors,
3110 l_int32 *pnerrors)
3111{
3112l_int32 w, h, wpls, wpld, i, j, nerrors;
3113l_int32 ncubes, depth, cindex, oval;
3114l_int32 rval, gval, bval;
3115l_int32 *octarray;
3116l_uint32 octindex;
3117l_uint32 *rtab, *gtab, *btab;
3118l_uint32 *lines, *lined, *datas, *datad, *ppixel;
3119l_uint32 *colorarray;
3120PIX *pixd;
3121PIXCMAP *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
3224cleanup_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
3294PIX *
3295pixFewColorsOctcubeQuantMixed(PIX *pixs,
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{
3303l_int32 i, j, w, h, wplc, wplm, wpld, ncolors, index;
3304l_int32 rval, gval, bval, val, minval, maxval;
3305l_int32 *lut;
3306l_uint32 *datac, *datam, *datad, *linec, *linem, *lined;
3307PIX *pix1, *pixc, *pixm, *pixg, *pixd;
3308PIXCMAP *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 *---------------------------------------------------------------------------*/
3414PIX *
3415pixFixedOctcubeQuantGenRGB(PIX *pixs,
3416 l_int32 level)
3417{
3418l_int32 w, h, wpls, wpld, i, j;
3419l_int32 rval, gval, bval;
3420l_uint32 octindex;
3421l_uint32 *rtab, *gtab, *btab;
3422l_uint32 *lines, *lined, *datas, *datad;
3423PIX *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 *------------------------------------------------------------------*/
3487PIX *
3488pixQuantFromCmap(PIX *pixs,
3489 PIXCMAP *cmap,
3490 l_int32 mindepth,
3491 l_int32 level,
3492 l_int32 metric)
3493{
3494l_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
3576PIX *
3577pixOctcubeQuantFromCmap(PIX *pixs,
3578 PIXCMAP *cmap,
3579 l_int32 mindepth,
3580 l_int32 level,
3581 l_int32 metric)
3582{
3583l_int32 *cmaptab;
3584l_uint32 *rtab, *gtab, *btab;
3585PIX *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
3642static PIX *
3643pixOctcubeQuantFromCmapLUT(PIX *pixs,
3644 PIXCMAP *cmap,
3645 l_int32 mindepth,
3646 l_int32 *cmaptab,
3647 l_uint32 *rtab,
3648 l_uint32 *gtab,
3649 l_uint32 *btab)
3650{
3651l_int32 i, j, w, h, depth, wpls, wpld;
3652l_int32 rval, gval, bval, index;
3653l_uint32 octindex;
3654l_uint32 *lines, *lined, *datas, *datad;
3655PIX *pixd;
3656PIXCMAP *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 *---------------------------------------------------------------------------*/
3726NUMA *
3727pixOctcubeHistogram(PIX *pixs,
3728 l_int32 level,
3729 l_int32 *pncolors)
3730{
3731l_int32 size, i, j, w, h, wpl, ncolors, val;
3732l_int32 rval, gval, bval;
3733l_uint32 octindex;
3734l_uint32 *rtab, *gtab, *btab;
3735l_uint32 *data, *line;
3736l_float32 *array;
3737NUMA *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
3793cleanup_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 *------------------------------------------------------------------*/
3849l_int32 *
3850pixcmapToOctcubeLUT(PIXCMAP *cmap,
3851 l_int32 level,
3852 l_int32 metric)
3853{
3854l_int32 i, k, size, ncolors, mindist, dist, mincolor, index;
3855l_int32 rval, gval, bval; /* color at center of the octcube */
3856l_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 *------------------------------------------------------------------*/
3935l_ok
3936pixRemoveUnusedColors(PIX *pixs)
3937{
3938l_int32 i, j, w, h, d, nc, wpls, val, newval, index, zerofound;
3939l_int32 rval, gval, bval;
3940l_uint32 *datas, *lines;
3941l_int32 *histo, *map1, *map2;
3942PIXCMAP *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 *------------------------------------------------------------------*/
4081l_ok
4082pixNumberOccupiedOctcubes(PIX *pix,
4083 l_int32 level,
4084 l_int32 mincount,
4085 l_float32 minfract,
4086 l_int32 *pncolors)
4087{
4088l_int32 i, j, w, h, d, wpl, ncolors, size, octindex;
4089l_int32 rval, gval, bval;
4090l_int32 *carray;
4091l_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
4140cleanup_arrays:
4141 LEPT_FREE(carray);
4142 LEPT_FREE(rtab);
4143 LEPT_FREE(gtab);
4144 LEPT_FREE(btab);
4145 return 0;
4146}
GET_DATA_QBIT
#define GET_DATA_QBIT(pdata, n)
Definition: arrayaccess.h:164
SET_DATA_BIT
#define SET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:127
SET_DATA_DIBIT
#define SET_DATA_DIBIT(pdata, n, val)
Definition: arrayaccess.h:149
GET_DATA_BYTE
#define GET_DATA_BYTE(pdata, n)
Definition: arrayaccess.h:188
GET_DATA_DIBIT
#define GET_DATA_DIBIT(pdata, n)
Definition: arrayaccess.h:145
SET_DATA_BYTE
#define SET_DATA_BYTE(pdata, n, val)
Definition: arrayaccess.h:198
SET_DATA_QBIT
#define SET_DATA_QBIT(pdata, n, val)
Definition: arrayaccess.h:168
pixColorFraction
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
pixcmapDestroy
void pixcmapDestroy(PIXCMAP **pcmap)
pixcmapDestroy()
Definition: colormap.c:279
pixcmapGetCount
l_int32 pixcmapGetCount(const PIXCMAP *cmap)
pixcmapGetCount()
Definition: colormap.c:708
pixcmapCopy
PIXCMAP * pixcmapCopy(const PIXCMAP *cmaps)
pixcmapCopy()
Definition: colormap.c:248
pixcmapGetNearestIndex
l_ok pixcmapGetNearestIndex(PIXCMAP *cmap, l_int32 rval, l_int32 gval, l_int32 bval, l_int32 *pindex)
pixcmapGetNearestIndex()
Definition: colormap.c:1353
pixcmapCreate
PIXCMAP * pixcmapCreate(l_int32 depth)
pixcmapCreate()
Definition: colormap.c:125
pixcmapResetColor
l_ok pixcmapResetColor(PIXCMAP *cmap, l_int32 index, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapResetColor()
Definition: colormap.c:966
pixcmapGetColor
l_ok pixcmapGetColor(PIXCMAP *cmap, l_int32 index, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
pixcmapGetColor()
Definition: colormap.c:824
pixcmapGetMinDepth
l_ok pixcmapGetMinDepth(PIXCMAP *cmap, l_int32 *pmindepth)
pixcmapGetMinDepth()
Definition: colormap.c:765
pixcmapGetRankIntensity
l_ok pixcmapGetRankIntensity(PIXCMAP *cmap, l_float32 rankval, l_int32 *pindex)
pixcmapGetRankIntensity()
Definition: colormap.c:1302
pixcmapToArrays
l_ok pixcmapToArrays(const PIXCMAP *cmap, l_int32 **prmap, l_int32 **pgmap, l_int32 **pbmap, l_int32 **pamap)
pixcmapToArrays()
Definition: colormap.c:2068
pixcmapAddColor
l_ok pixcmapAddColor(PIXCMAP *cmap, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapAddColor()
Definition: colormap.c:414
getRGBFromOctcube
static void getRGBFromOctcube(l_int32 cubeindex, l_int32 level, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
getRGBFromOctcube()
Definition: colorquant1.c:1508
octreeFindColorCell
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
pixOctcubeHistogram
NUMA * pixOctcubeHistogram(PIX *pixs, l_int32 level, l_int32 *pncolors)
pixOctcubeHistogram()
Definition: colorquant1.c:3727
makeRGBToIndexTables
l_ok makeRGBToIndexTables(l_int32 cqlevels, l_uint32 **prtab, l_uint32 **pgtab, l_uint32 **pbtab)
makeRGBToIndexTables()
Definition: colorquant1.c:1353
pixFewColorsOctcubeQuant2
PIX * pixFewColorsOctcubeQuant2(PIX *pixs, l_int32 level, NUMA *na, l_int32 ncolors, l_int32 *pnerrors)
pixFewColorsOctcubeQuant2()
Definition: colorquant1.c:3106
pixFixedOctcubeQuantGenRGB
PIX * pixFixedOctcubeQuantGenRGB(PIX *pixs, l_int32 level)
pixFixedOctcubeQuantGenRGB()
Definition: colorquant1.c:3415
pixOctreeColorQuantGeneral
PIX * pixOctreeColorQuantGeneral(PIX *pixs, l_int32 colors, l_int32 ditherflag, l_float32 validthresh, l_float32 colorthresh)
pixOctreeColorQuantGeneral()
Definition: colorquant1.c:601
pixFewColorsOctcubeQuant1
PIX * pixFewColorsOctcubeQuant1(PIX *pixs, l_int32 level)
pixFewColorsOctcubeQuant1()
Definition: colorquant1.c:2936
cqcellTreeDestroy
static void cqcellTreeDestroy(CQCELL ****pcqcaa)
cqcellTreeDestroy()
Definition: colorquant1.c:1289
pixOctcubeQuantMixedWithGray
PIX * pixOctcubeQuantMixedWithGray(PIX *pixs, l_int32 depth, l_int32 graylevels, l_int32 delta)
pixOctcubeQuantMixedWithGray()
Definition: colorquant1.c:2583
pixRemoveUnusedColors
l_ok pixRemoveUnusedColors(PIX *pixs)
pixRemoveUnusedColors()
Definition: colorquant1.c:3936
cqcellTreeCreate
static CQCELL *** cqcellTreeCreate(void)
cqcellTreeCreate()
Definition: colorquant1.c:1260
getOctcubeIndices
static l_int32 getOctcubeIndices(l_int32 rgbindex, l_int32 level, l_int32 *pbindex, l_int32 *psindex)
getOctcubeIndices()
Definition: colorquant1.c:1585
pixQuantFromCmap
PIX * pixQuantFromCmap(PIX *pixs, PIXCMAP *cmap, l_int32 mindepth, l_int32 level, l_int32 metric)
pixQuantFromCmap()
Definition: colorquant1.c:3488
pixcmapToOctcubeLUT
l_int32 * pixcmapToOctcubeLUT(PIXCMAP *cmap, l_int32 level, l_int32 metric)
pixcmapToOctcubeLUT()
Definition: colorquant1.c:3850
octreeGenerateAndPrune
static CQCELL *** octreeGenerateAndPrune(PIX *pixs, l_int32 colors, l_int32 reservedcolors, PIXCMAP **pcmap)
octreeGenerateAndPrune()
Definition: colorquant1.c:724
pixFixedOctcubeQuant256
PIX * pixFixedOctcubeQuant256(PIX *pixs, l_int32 ditherflag)
pixFixedOctcubeQuant256()
Definition: colorquant1.c:2802
pixDitherOctindexWithCmap
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
pixOctcubeQuantFromCmapLUT
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
pixOctreeQuantByPopulation
PIX * pixOctreeQuantByPopulation(PIX *pixs, l_int32 level, l_int32 ditherflag)
pixOctreeQuantByPopulation()
Definition: colorquant1.c:1693
pixNumberOccupiedOctcubes
l_ok pixNumberOccupiedOctcubes(PIX *pix, l_int32 level, l_int32 mincount, l_float32 minfract, l_int32 *pncolors)
pixNumberOccupiedOctcubes()
Definition: colorquant1.c:4082
pixFewColorsOctcubeQuantMixed
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
octcubeGetCount
static l_int32 octcubeGetCount(l_int32 level, l_int32 *psize)
octcubeGetCount()
Definition: colorquant1.c:1619
getOctcubeIndexFromRGB
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
pixOctreeColorQuant
PIX * pixOctreeColorQuant(PIX *pixs, l_int32 colors, l_int32 ditherflag)
pixOctreeColorQuant()
Definition: colorquant1.c:535
pixOctreeQuantNumColors
PIX * pixOctreeQuantNumColors(PIX *pixs, l_int32 maxcolors, l_int32 subsample)
pixOctreeQuantNumColors()
Definition: colorquant1.c:2256
pixOctcubeQuantFromCmap
PIX * pixOctcubeQuantFromCmap(PIX *pixs, PIXCMAP *cmap, l_int32 mindepth, l_int32 level, l_int32 metric)
pixOctcubeQuantFromCmap()
Definition: colorquant1.c:3577
pixOctreeQuantizePixels
static PIX * pixOctreeQuantizePixels(PIX *pixs, CQCELL ***cqcaa, l_int32 ditherflag)
pixOctreeQuantizePixels()
Definition: colorquant1.c:974
makeGrayQuantIndexTable
l_int32 * makeGrayQuantIndexTable(l_int32 nlevels)
makeGrayQuantIndexTable()
Definition: grayquant.c:1848
pixGrayQuantFromHisto
PIX * pixGrayQuantFromHisto(PIX *pixd, PIX *pixs, PIX *pixm, l_float32 minfract, l_int32 maxsize)
pixGrayQuantFromHisto()
Definition: grayquant.c:2339
pixGrayQuantFromCmap
PIX * pixGrayQuantFromCmap(PIX *pixs, PIXCMAP *cmap, l_int32 mindepth)
pixGrayQuantFromCmap()
Definition: grayquant.c:2562
lheapDestroy
void lheapDestroy(L_HEAP **plh, l_int32 freeflag)
lheapDestroy()
Definition: heap.c:154
lheapRemove
void * lheapRemove(L_HEAP *lh)
lheapRemove()
Definition: heap.c:251
lheapCreate
L_HEAP * lheapCreate(l_int32 n, l_int32 direction)
lheapCreate()
Definition: heap.c:112
lheapAdd
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
Definition: heap.c:193
numaAddNumber
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:478
numaSetCount
l_ok numaSetCount(NUMA *na, l_int32 newcount)
numaSetCount()
Definition: numabasic.c:685
numaDestroy
void numaDestroy(NUMA **pna)
numaDestroy()
Definition: numabasic.c:366
numaGetFArray
l_float32 * numaGetFArray(NUMA *na, l_int32 copyflag)
numaGetFArray()
Definition: numabasic.c:892
numaGetCount
l_int32 numaGetCount(NUMA *na)
numaGetCount()
Definition: numabasic.c:658
numaGetIValue
l_ok numaGetIValue(NUMA *na, l_int32 index, l_int32 *pival)
numaGetIValue()
Definition: numabasic.c:754
numaCreate
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:194
pixSetColormap
l_ok pixSetColormap(PIX *pix, PIXCMAP *colormap)
pixSetColormap()
Definition: pix1.c:1699
pixDestroy
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:621
pixGetDimensions
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1113
pixClone
PIX * pixClone(PIX *pixs)
pixClone()
Definition: pix1.c:593
pixCreate
PIX * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
Definition: pix1.c:315
pixGetData
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1763
pixGetRGBLine
l_ok pixGetRGBLine(PIX *pixs, l_int32 row, l_uint8 *bufr, l_uint8 *bufg, l_uint8 *bufb)
pixGetRGBLine()
Definition: pix2.c:2897
setPixelLow
void setPixelLow(l_uint32 *line, l_int32 x, l_int32 depth, l_uint32 val)
setPixelLow()
Definition: pix2.c:679
composeRGBPixel
l_ok composeRGBPixel(l_int32 rval, l_int32 gval, l_int32 bval, l_uint32 *ppixel)
composeRGBPixel()
Definition: pix2.c:2751
extractRGBValues
void extractRGBValues(l_uint32 pixel, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
extractRGBValues()
Definition: pix2.c:2820
L_NOCOPY
@ L_NOCOPY
Definition: pix.h:710
L_SORT_DECREASING
@ L_SORT_DECREASING
Definition: pix.h:730
L_EUCLIDEAN_DISTANCE
@ L_EUCLIDEAN_DISTANCE
Definition: pix.h:947
L_MANHATTAN_DISTANCE
@ L_MANHATTAN_DISTANCE
Definition: pix.h:946
pixConvertTo8
PIX * pixConvertTo8(PIX *pixs, l_int32 cmapflag)
pixConvertTo8()
Definition: pixconv.c:3133
pixScaleBySampling
PIX * pixScaleBySampling(PIX *pixs, l_float32 scalex, l_float32 scaley)
pixScaleBySampling()
Definition: scale1.c:1338
L_Heap
Definition: heap.h:78
L_OctcubePop
Definition: colorquant1.c:208
Numa
Definition: array.h:71
PixColormap::n
l_int32 n
Definition: pix.h:164
Pix
Definition: pix.h:139
lept_stderr
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306