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