1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 - This software is distributed in the hope that it will be
4 - useful, but with NO WARRANTY OF ANY KIND.
5 - No author or distributor accepts responsibility to anyone for the
6 - consequences of using this software, or for whether it serves any
7 - particular purpose or works at all, unless he or she says so in
8 - writing. Everyone is granted permission to copy, modify and
9 - redistribute this source code, for commercial or non-commercial
10 - purposes, with the following restrictions: (1) the origin of this
11 - source code must not be misrepresented; (2) modified versions must
12 - be plainly marked as such; and (3) this notice may not be removed
13 - or altered from any source or modified source distribution.
14 *====================================================================*/
15
16 /*
17 * colorquant1.c
18 *
19 * Octcube color quantization
20 *
21 * There are several different octcube/octree based quantizations.
22 * These can be classified, in the order in which they appear in this
23 * file, as follows:
24 *
25 * -----------------------------------------------------------------
26 * (1) General adaptive octree
27 * (2) Adaptive octree by population at fixed level
28 * (3) Adaptive octree using population and with specified number
29 * of output colors
30 * (4) Octcube with colormap representation of mixed color/gray
31 * (5) 256 fixed octcubes covering color space
32 * (6) Octcubes at fixed level for ncolors <= 256
33 * (7) Octcubes at fixed level with RGB output
34 * (8) Quantizing an rgb image using a specified colormap
35 * -----------------------------------------------------------------
36 *
37 * (1) Two-pass adaptive octree color quantization
38 * PIX *pixOctreeColorQuant()
39 * PIX *pixOctreeColorQuantGeneral()
40 *
41 * which calls
42 * static CQCELL ***octreeGenerateAndPrune()
43 * static PIX *pixOctreeQuantizePixels()
44 *
45 * which calls
46 * static l_int32 octreeFindColorCell()
47 *
48 * Helper cqcell functions
49 * static CQCELL ***cqcellTreeCreate()
50 * static void cqcellTreeDestroy()
51 *
52 * Helper index functions
53 * l_int32 makeRGBToIndexTables()
54 * void getOctcubeIndexFromRGB()
55 * static void getRGBFromOctcube()
56 * static l_int32 getOctcubeIndices()
57 * static l_int32 octcubeGetCount()
58 *
59 * (2) Adaptive octree quantization based on population at a fixed level
60 * PIX *pixOctreeQuantByPopulation()
61 * static l_int32 pixDitherOctindexWithCmap()
62 *
63 * (3) Adaptive octree quantization to 4 and 8 bpp with specified
64 * number of output colors in colormap
65 * PIX *pixOctreeQuantNumColors()
66 *
67 * (4) Mixed color/gray quantization with specified number of colors
68 * PIX *pixOctcubeQuantMixedWithGray()
69 *
70 * (5) Fixed partition octcube quantization with 256 cells
71 * PIX *pixFixedOctcubeQuant256()
72 *
73 * (6) Fixed partition quantization for images with few colors
74 * PIX *pixFewColorsOctcubeQuant1()
75 * PIX *pixFewColorsOctcubeQuant2()
76 * PIX *pixFewColorsOctcubeQuantMixed()
77 *
78 * (7) Fixed partition octcube quantization at specified level
79 * with quantized output to RGB
80 * PIX *pixFixedOctcubeQuantGenRGB()
81 *
82 * (8) Color quantize RGB image using existing colormap
83 * PIX *pixQuantFromCmap() [high-level wrapper]
84 * PIX *pixOctcubeQuantFromCmap()
85 * PIX *pixOctcubeQuantFromCmapLUT()
86 *
87 * Generation of octcube histogram
88 * NUMA *pixOctcubeHistogram()
89 *
90 * Get filled octcube table from colormap
91 * l_int32 *pixcmapToOctcubeLUT()
92 *
93 * Strip out unused elements in colormap
94 * l_int32 pixRemoveUnusedColors()
95 *
96 * Find number of occupied octcubes at the specified level
97 * l_int32 pixNumberOccupiedOctcubes()
98 *
99 * Note: leptonica also provides color quantization using a modified
100 * form of median cut. See colorquant2.c for details.
101 */
102
103 #include <stdio.h>
104 #include <stdlib.h>
105 #include <string.h>
106 #include "allheaders.h"
107
108
109 /* This data structure is used for pixOctreeColorQuant(),
110 * a color octree that adjusts to the color distribution
111 * in the image that is being quantized. The best settings
112 * are with CQ_NLEVELS = 6 and DITHERING set on.
113 *
114 * Notes: (1) the CTE (color table entry) index is sequentially
115 * assigned as the tree is pruned back
116 * (2) if 'bleaf' == 1, all pixels in that cube have been
117 * assigned to one or more CTEs. But note that if
118 * all 8 subcubes have 'bleaf' == 1, it will have no
119 * pixels left for assignment and will not be a CTE.
120 * (3) 'nleaves', the number of leaves contained at the next
121 * lower level is some number between 0 and 8, inclusive.
122 * If it is zero, it means that all colors within this cube
123 * are part of a single growing cluster that has not yet
124 * been set aside as a leaf. If 'nleaves' > 0, 'bleaf'
125 * will be set to 1 and all pixels not assigned to leaves
126 * at lower levels will be assigned to a CTE here.
127 * (However, as described above, if all pixels are already
128 * assigned, we set 'bleaf' = 1 but do not create a CTE
129 * at this level.)
130 * (4) To keep the maximum color error to a minimum, we
131 * prune the tree back to level 2, and require that
132 * all 64 level 2 cells are CTEs.
133 * (5) We reserve an extra set of colors to prevent running out
134 * of colors during the assignment of the final 64 level 2 cells.
135 * This is more likely to happen with small images.
136 * (6) When we run out of colors, the dithered image can be very
137 * poor, so we additionally prevent dithering if the image
138 * is small.
139 * (7) The color content of the image is measured, and if there
140 * is very little color, it is quantized in grayscale.
141 */
142 struct ColorQuantCell
143 {
144 l_int32 rc, gc, bc; /* center values */
145 l_int32 n; /* number of samples in this cell */
146 l_int32 index; /* CTE (color table entry) index */
147 l_int32 nleaves; /* # of leaves contained at next lower level */
148 l_int32 bleaf; /* boolean: 0 if not a leaf, 1 if so */
149 };
150 typedef struct ColorQuantCell CQCELL;
151
152 /* Constants for pixOctreeColorQuant() */
153 static const l_int32 CQ_NLEVELS = 5; /* only 4, 5 and 6 are allowed */
154 static const l_int32 CQ_RESERVED_COLORS = 64; /* to allow for level 2 */
155 /* remainder CTEs */
156 static const l_int32 EXTRA_RESERVED_COLORS = 25; /* to avoid running out */
157 static const l_int32 TREE_GEN_WIDTH = 350; /* big enough for good stats */
158 static const l_int32 MIN_DITHER_SIZE = 250; /* don't dither if smaller */
159
160
161 /* This data structure is used for pixOctreeQuantNumColors(),
162 * a color octree that adjusts in a simple way to the to the color
163 * distribution in the image that is being quantized. It outputs
164 * colormapped images, either 4 bpp or 8 bpp, depending on the
165 * max number of colors and the compression desired.
166 *
167 * The number of samples is saved as a float in the first location,
168 * because this is required to use it as the key that orders the
169 * cells in the priority queue. */
170 struct OctcubeQuantCell
171 {
172 l_float32 n; /* number of samples in this cell */
173 l_int32 octindex; /* octcube index */
174 l_int32 rcum, gcum, bcum; /* cumulative values */
175 l_int32 rval, gval, bval; /* average values */
176 };
177 typedef struct OctcubeQuantCell OQCELL;
178
179
180 /* This data structure is using for heap sorting octcubes
181 * by population. Sort order is decreasing. */
182 struct L_OctcubePop
183 {
184 l_float32 npix; /* parameter on which to sort */
185 l_int32 index; /* octcube index at assigned level */
186 l_int32 rval; /* mean red value of pixels in octcube */
187 l_int32 gval; /* mean green value of pixels in octcube */
188 l_int32 bval; /* mean blue value of pixels in octcube */
189 };
190 typedef struct L_OctcubePop L_OCTCUBE_POP;
191
192 /* In pixDitherOctindexWithCmap(), we use these default values.
193 * To get the max value of 'dif' in the dithering color transfer,
194 * divide these "DIF_CAP" values by 8. However, a value of
195 * 0 means that there is no cap (infinite cap). A very small
196 * value is used for POP_DIF_CAP because dithering on the population
197 * generated colormap can be unstable without a tight cap. */
198 static const l_int32 FIXED_DIF_CAP = 0;
199 static const l_int32 POP_DIF_CAP = 40;
200
201
202 /* Static octree helper function */
203 static l_int32 octreeFindColorCell(l_int32 octindex, CQCELL ***cqcaa,
204 l_int32 *pindex, l_int32 *prval,
205 l_int32 *pgval, l_int32 *pbval);
206
207 /* Static cqcell functions */
208 static CQCELL ***octreeGenerateAndPrune(PIX *pixs, l_int32 colors,
209 l_int32 reservedcolors,
210 PIXCMAP **pcmap);
211 static PIX *pixOctreeQuantizePixels(PIX *pixs, CQCELL ***cqcaa,
212 l_int32 ditherflag);
213 static CQCELL ***cqcellTreeCreate(void);
214 static void cqcellTreeDestroy(CQCELL ****pcqcaa);
215
216 /* Static helper octcube index functions */
217 static void getRGBFromOctcube(l_int32 cubeindex, l_int32 level,
218 l_int32 *prval, l_int32 *pgval, l_int32 *pbval);
219 static l_int32 getOctcubeIndices(l_int32 rgbindex, l_int32 level,
220 l_int32 *pbindex, l_int32 *psindex);
221 static l_int32 octcubeGetCount(l_int32 level, l_int32 *psize);
222
223 /* Static function to perform octcube-indexed dithering */
224 static l_int32 pixDitherOctindexWithCmap(PIX *pixs, PIX *pixd, l_uint32 *rtab,
225 l_uint32 *gtab, l_uint32 *btab,
226 l_int32 *carray, l_int32 difcap);
227
228
229 #ifndef NO_CONSOLE_IO
230 #define DEBUG_OCTINDEX 0
231 #define DEBUG_OCTCUBE_CMAP 0
232 #define DEBUG_POP 0
233 #define DEBUG_FEW_COLORS 0
234 #define PRINT_OCTCUBE_STATS 0
235 #endif /* ~NO_CONSOLE_IO */
236
237
238 /*-------------------------------------------------------------------------*
239 * Two-pass adaptive octree color quantization *
240 *-------------------------------------------------------------------------*/
241 /*!
242 * pixOctreeColorQuant()
243 *
244 * Input: pixs (32 bpp; 24-bit color)
245 * colors (in colormap; some number in range [32 ... 256];
246 * the actual number of colors used will be smaller)
247 * ditherflag (1 to dither, 0 otherwise)
248 * Return: pixd (8 bpp with colormap), or null on error
249 *
250 * I found one description in the literature of octree color
251 * quantization, using progressive truncation of the octree,
252 * by M. Gervautz and W. Purgathofer in Graphics Gems, pp.
253 * 287-293, ed. A. Glassner, Academic Press, 1990.
254 * Rather than setting up a fixed partitioning of the color
255 * space ab initio, as we do here, they allow the octree to be
256 * progressively truncated as new pixels are added. They
257 * need to set up some data structures that are traversed
258 * with the addition of each 24 bit pixel, in order to decide
259 * either (1) in which cluster (sub-branch of the octree) to put
260 * the pixel, or (2) whether to truncate the octree further
261 * to place the pixel in an existing cluster, or (3) which
262 * two existing clusters should be merged so that the pixel
263 * can be left to start a truncated leaf of the octree. Such dynamic
264 * truncation is considerably more complicated, and Gervautz et
265 * al. did not explain how they did it in anywhere near the
266 * detail required to check their implementation.
267 *
268 * The simple method in pixFixedOctcubeQuant256() is very
269 * fast, and with dithering the results are good, but you
270 * can do better if the color clusters are selected adaptively
271 * from the image. We want a method that makes much better
272 * use of color samples in regions of color space with high
273 * pixel density, while also fairly representing small numbers
274 * of color pixels in low density regions. Such adaptation
275 * requires two passes through the image: the first for generating
276 * the pruned tree of color cubes and the second for computing the index
277 * into the color table for each pixel.
278 *
279 * A relatively simple adaptive method is pixOctreeQuantByPopulation().
280 * That function first determines if the image has very few colors,
281 * and, if so, quantizes to those colors. If there are more than
282 * 256 colors, it generates a histogram of octcube leaf occupancy
283 * at level 4, chooses the 192 most populated such leaves as
284 * the first 192 colors, and sets the remaining 64 colors to the
285 * residual average pixel values in each of the 64 level 2 octcubes.
286 * This is a bit faster than pixOctreeColorQuant(), and does very
287 * well without dithering, but for most images with dithering it
288 * is clearly inferior.
289 *
290 * We now describe pixOctreeColorQuant(). The first pass is done
291 * on a subsampled image, because we do not need to use all the
292 * pixels in the image to generate the tree. Subsampling
293 * down to 0.25 (1/16 of the pixels) makes the program run
294 * about 1.3 times faster.
295 *
296 * Instead of dividing the color space into 256 equal-sized
297 * regions, we initially divide it into 2^12 or 2^15 or 2^18
298 * equal-sized octcubes. Suppose we choose to use 2^18 octcubes.
299 * This gives us 6 octree levels. We then prune back,
300 * starting from level 6. For every cube at level 6, there
301 * are 8 cubes at level 5. Call the operation of putting a
302 * cube aside as a color table entry (CTE) a "saving."
303 * We use a (in general) level-dependent threshold, and save
304 * those level 6 cubes that are above threshold.
305 * The rest are combined into the containing level 5 cube.
306 * If between 1 and 7 level 6 cubes within a level 5
307 * cube have been saved by thresholding, then the remaining
308 * level 6 cubes in that level 5 cube are automatically
309 * saved as well, without applying a threshold. This greatly
310 * simplifies both the description of the CTEs and the later
311 * classification of each pixel as belonging to a CTE.
312 * This procedure is iterated through every cube, starting at
313 * level 5, and then 4, 3, and 2, successively. The result is that
314 * each CTE contains the entirety of a set of from 1 to 7 cubes
315 * from a given level that all belong to a single cube at the
316 * level above. We classify the CTEs in terms of the
317 * condition in which they are made as either being "threshold"
318 * or "residual." They are "threshold" CTEs if no subcubes
319 * are CTEs (that is, they contain every pixel within the cube)
320 * and the number of pixels exceeds the threshold for making
321 * a CTE. They are "residual" CTEs if at least one but not more
322 * than 7 of the subcubes have already been determined to be CTEs;
323 * this happens automatically -- no threshold is applied.
324 * If all 8 subcubes are determined to be CTEs, the cube is
325 * marked as having all pixels accounted for ('bleaf' = 1) but
326 * is not saved as a CTE.
327 *
328 * We stop the pruning at level 2, at which there are 64
329 * sub-cubes. Any pixels not already claimed in a CTE are
330 * put in these cubes.
331 *
332 * As the cubes are saved as color samples in the color table,
333 * the number of remaining pixels P and the number of
334 * remaining colors in the color table N are recomputed,
335 * along with the average number of pixels P/N (ppc) to go in
336 * each of the remaining colors. This running average number is
337 * used to set the threshold at the current level.
338 *
339 * Because we are going to very small cubes at levels 6 or 5,
340 * and will dither the colors for errors, it is not necessary
341 * to compute the color center of each cluster; we can simply
342 * use the center of the cube. This gives us a minimax error
343 * condition: the maximum error is half the width of the
344 * level 2 cubes -- 32 color values out of 256 -- for each color
345 * sample. In practice, most of the pixels will be very much
346 * closer to the center of their cells. And with dithering,
347 * the average pixel color in a small region will be closer still.
348 * Thus with the octree quantizer, we are able to capture
349 * regions of high color pdf (probability density function) in small
350 * but accurate CTEs, and to have only a small number of pixels
351 * that end up a significant distance (with a guaranteed maximum)
352 * from their true color.
353 *
354 * How should the threshold factor vary? Threshold factors
355 * are required for levels 2, 3, 4 and 5 in the pruning stage.
356 * The threshold for level 5 is actually applied to cubes at
357 * level 6, etc. From various experiments, it appears that
358 * the results do not vary appreciably for threshold values near 1.0.
359 * If you want more colors in smaller cubes, the threshold
360 * factors can be set lower than 1.0 for cubes at levels 4 and 5.
361 * However, if the factor is set much lower than 1.0 for
362 * levels 2 and 3, we can easily run out of colors.
363 * We put aside 64 colors in the calculation of the threshold
364 * values, because we must have 64 color centers at level 2,
365 * that will have very few pixels in most of them.
366 * If we reduce the factor for level 5 to 0.4, this will
367 * generate many level 6 CTEs, and consequently
368 * many residual cells will be formed up from those leaves,
369 * resulting in the possibility of running out of colors.
370 * Remember, the residual CTEs are mandatory, and are formed
371 * without using the threshold, regardless of the number of
372 * pixels that are absorbed.
373 *
374 * The implementation logically has four parts:
375 *
376 * (1) accumulation into small, fixed cells
377 * (2) pruning back into selected CTE cubes
378 * (3) organizing the CTEs for fast search to find
379 * the CTE to which any image pixel belongs
380 * (4) doing a second scan to code the image pixels by CTE
381 *
382 * Step (1) is straightforward; we use 2^15 cells.
383 *
384 * We've already discussed how the pruning step (2) will be performed.
385 *
386 * Steps (3) and (4) are related, in that the organization
387 * used by step (3) determines how the search actually
388 * takes place for each pixel in step (4).
389 *
390 * There are many ways to do step (3). Let's explore a few.
391 *
392 * (a) The simplest is to order the cubes from highest occupancy
393 * to lowest, and traverse the list looking for the deepest
394 * match. To make this more efficient, so that we know when
395 * to stop looking, any cube that has separate CTE subcubes
396 * would be marked as such, so that we know when we hit a
397 * true leaf.
398 *
399 * (b) Alternatively, we can order the cubes by highest
400 * occupancy separately each level, and work upward,
401 * starting at level 5, so that when we find a match we
402 * know that it will be correct.
403 *
404 * (c) Another approach would be to order the cubes by
405 * "address" and use a hash table to find the cube
406 * corresponding to a pixel color. I don't know how to
407 * do this with a variable length address, as each CTE
408 * will have 3*n bits, where n is the level.
409 *
410 * (d) Another approach entirely is to put the CTE cubes into
411 * a tree, in such a way that starting from the root, and
412 * using 3 bits of address at a time, the correct branch of
413 * each octree can be taken until a leaf is found. Because
414 * a given cube can be both a leaf and also have branches
415 * going to sub-cubes, the search stops only when no
416 * marked subcubes have addresses that match the given pixel.
417 *
418 * In the tree method, we can start with a dense infrastructure,
419 * and place the leaves corresponding to the N colors
420 * in the tree, or we can grow from the root only those
421 * branches that end directly on leaves.
422 *
423 * What we do here is to take approach (d), and implement the tree
424 * "virtually", as a set of arrays, one array for each level
425 * of the tree. Initially we start at level 5, an array with
426 * 2^15 cubes, each with 8 subcubes. We then build nodes at
427 * levels closer to the root; at level 4 there are 2^12 nodes
428 * each with 8 subcubes; etc. Using these arrays has
429 * several advantages:
430 *
431 * - We don't need to keep track of links between cubes
432 * and subcubes, because we can use the canonical
433 * addressing on the cell arrays directly to determine
434 * which nodes are parent cubes and which are sub-cubes.
435 *
436 * - We can prune directly on this tree
437 *
438 * - We can navigate the pruned tree quickly to classify
439 * each pixel in the image.
440 *
441 * Canonical addressing guarantees that the i-th node at level k
442 * has 8 subnodes given by the 8*i ... 8*i+7 nodes at level k+1.
443 *
444 * The pruning step works as follows. We go from the lowest
445 * level up. At each level, the threshold is found from the
446 * product of a factor near 1.0 and the ratio of unmarked pixels
447 * to remaining colors (minus the 64). We march through
448 * the space, sequentially considering a cube and its 8 subcubes.
449 * We first check those subcubes that are not already
450 * marked as CTE to see if any are above threshold, and if so,
451 * generate a CTE and mark them as such.
452 * We then determine if any of the subcubes have been marked.
453 * If so, and there are subcubes that are not marked,
454 * we generate a CTE for the cube from the remaining unmarked
455 * subcubes; this is mandatory and does not depend on how many
456 * pixels are in the set of subcubes. If none of the subcubes
457 * are marked, we aggregate their pixels into the cube
458 * containing them, but do not mark it as a CTE; that
459 * will be determined when iterating through the next level up.
460 *
461 * When all the pixels in a cube are accounted for in one or more
462 * colors, we set the boolean 'bleaf' to true. This is the
463 * flag used to mark the cubes in the pruning step. If a cube
464 * is marked, and all 8 subcubes are marked, then it is not
465 * itself given a CTE because all pixels have already been
466 * accounted for.
467 *
468 * Note that the pruning of the tree and labelling of the CTEs
469 * (step 2) accomplishes step 3 implicitly, because the marked
470 * and pruned tree is ready for use in labelling each pixel
471 * in step 4. We now, for every pixel in the image, traverse
472 * the tree from the root, looking for the lowest cube that is a leaf.
473 * At each level we have a cube and subcube. If we reach a subcube
474 * leaf that is marked 0, we know that the color is stored in the
475 * cube above, and we've found the CTE. Otherwise, the subcube
476 * leaf is marked 1. If we're at the last level, we've reached
477 * the final leaf and must use it. Otherwise, continue the
478 * process at the next level down.
479 *
480 * For robustness, efficiency and high quality output, we do the following:
481 *
482 * (1) Measure the color content of the image. If there is very little
483 * color, quantize in grayscale.
484 * (2) For efficiency, build the octree with a subsampled image if the
485 * image is larger than some threshold size.
486 * (3) Reserve an extra set of colors to prevent running out of colors
487 * when pruning the octree; specifically, during the assignment
488 * of those level 2 cells (out of the 64) that have unassigned
489 * pixels. The problem of running out is more likely to happen
490 * with small images, because the estimation we use for the
491 * number of pixels available is not accurate.
492 * (4) In the unlikely event that we run out of colors, the dithered
493 * image can be very poor. As this would only happen with very
494 * small images, and dithering is not particularly noticeable with
495 * such images, turn it off.
496 */
497 PIX *
pixOctreeColorQuant(PIX * pixs,l_int32 colors,l_int32 ditherflag)498 pixOctreeColorQuant(PIX *pixs,
499 l_int32 colors,
500 l_int32 ditherflag)
501 {
502 PROCNAME("pixOctreeColorQuant");
503
504 if (!pixs)
505 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
506 if (pixGetDepth(pixs) != 32)
507 return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
508 if (colors < 128 || colors > 240) /* further restricted */
509 return (PIX *)ERROR_PTR("colors must be in [128, 240]", procName, NULL);
510
511 return pixOctreeColorQuantGeneral(pixs, colors, ditherflag, 0.01, 0.01);
512 }
513
514
515 /*!
516 * pixOctreeColorQuantGeneral()
517 *
518 * Input: pixs (32 bpp; 24-bit color)
519 * colors (in colormap; some number in range [32 ... 256];
520 * the actual number of colors used will be smaller)
521 * ditherflag (1 to dither, 0 otherwise)
522 * validthresh (minimum fraction of pixels neither near white
523 * nor black, required for color quantization;
524 * typically ~0.01, but smaller for images that have
525 * color but are nearly all white)
526 * colorthresh (minimum fraction of pixels with color that are
527 * not near white or black, that are required
528 * for color quantization; typ. ~0.01)
529 * Return: pixd (8 bit with colormap), or null on error
530 *
531 * Notes:
532 * (1) The parameters @validthresh and @colorthresh are used to
533 * determine if color quantization should be used on an image,
534 * or whether, instead, it should be quantized in grayscale.
535 * If the image has very few non-white and non-black pixels, or
536 * if those pixels that are non-white and non-black are all
537 * very close to either white or black, it is usually better
538 * to treat the color as accidental and to quantize the image
539 * to gray only. These parameters are useful if you know
540 * something a priori about the image. Perhaps you know that
541 * there is only a very small fraction of color pixels, but they're
542 * important to preserve; then you want to use a smaller value for
543 * these parameters. To disable conversion to gray and force
544 * color quantization, use @validthresh = 0.0 and @colorthresh = 0.0.
545 * (2) See pixOctreeColorQuant() for algorithmic and implementation
546 * details. This function has a more general interface.
547 * (3) See pixColorFraction() for computing the fraction of pixels
548 * that are neither white nor black, and the fraction of those
549 * pixels that have little color. From the documentation there:
550 * If pixfract is very small, there are few pixels that are
551 * neither black nor white. If colorfract is very small,
552 * the pixels that are neither black nor white have very
553 * little color content. The product 'pixfract * colorfract'
554 * gives the fraction of pixels with significant color content.
555 */
556 PIX *
pixOctreeColorQuantGeneral(PIX * pixs,l_int32 colors,l_int32 ditherflag,l_float32 validthresh,l_float32 colorthresh)557 pixOctreeColorQuantGeneral(PIX *pixs,
558 l_int32 colors,
559 l_int32 ditherflag,
560 l_float32 validthresh,
561 l_float32 colorthresh)
562 {
563 l_int32 w, h, minside, factor;
564 l_float32 scalefactor;
565 l_float32 pixfract; /* fraction neither near white nor black */
566 l_float32 colorfract; /* fraction with color of the pixfract population */
567 CQCELL ***cqcaa;
568 PIX *pixd, *pixsub;
569 PIXCMAP *cmap;
570
571 PROCNAME("pixOctreeColorQuantGeneral");
572
573 if (!pixs)
574 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
575 if (pixGetDepth(pixs) != 32)
576 return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
577 if (colors < 128 || colors > 256)
578 return (PIX *)ERROR_PTR("colors must be in [128, 256]", procName, NULL);
579
580 /* Determine if the image has sufficient color content.
581 * If pixfract << 1, most pixels are close to black or white.
582 * If colorfract << 1, the pixels that are not near
583 * black or white have very little color.
584 * If without color, quantize with a grayscale colormap. */
585 pixGetDimensions(pixs, &w, &h, NULL);
586 minside = L_MIN(w, h);
587 factor = L_MAX(1, minside / 200);
588 pixColorFraction(pixs, 20, 248, 12, factor, &pixfract, &colorfract);
589 if (pixfract < validthresh || colorfract < colorthresh) {
590 L_INFO_FLOAT2("\n Pixel fraction neither white nor black = %6.3f"
591 "\n Color fraction of those pixels = %6.3f"
592 "\n Quantizing in gray",
593 procName, pixfract, colorfract);
594 return pixConvertTo8(pixs, 1);
595 }
596
597 /* Conditionally subsample to speed up the first pass */
598 if (w > TREE_GEN_WIDTH) {
599 scalefactor = (l_float32)TREE_GEN_WIDTH / (l_float32)w;
600 pixsub = pixScaleBySampling(pixs, scalefactor, scalefactor);
601 }
602 else
603 pixsub = pixClone(pixs);
604
605 /* Drop the number of requested colors if image is very small */
606 if (w < MIN_DITHER_SIZE && h < MIN_DITHER_SIZE)
607 colors = L_MIN(colors, 220);
608
609 /* Make the pruned octree */
610 cqcaa = octreeGenerateAndPrune(pixsub, colors, CQ_RESERVED_COLORS, &cmap);
611 if (!cqcaa)
612 return (PIX *)ERROR_PTR("tree not made", procName, NULL);
613 #if 0
614 L_INFO_INT(" Colors requested = %d", procName, colors);
615 L_INFO_INT(" Actual colors = %d", procName, cmap->n);
616 #endif
617
618 /* Do not dither if image is very small */
619 if (w < MIN_DITHER_SIZE && h < MIN_DITHER_SIZE && ditherflag == 1) {
620 L_INFO("Small image: dithering turned off", procName);
621 ditherflag = 0;
622 }
623
624 /* Traverse tree from root, looking for lowest cube
625 * that is a leaf, and set dest pix value to its
626 * colortable index */
627 if ((pixd = pixOctreeQuantizePixels(pixs, cqcaa, ditherflag)) == NULL)
628 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
629
630 /* Attach colormap and copy res */
631 pixSetColormap(pixd, cmap);
632 pixCopyResolution(pixd, pixs);
633 pixCopyInputFormat(pixd, pixs);
634
635 cqcellTreeDestroy(&cqcaa);
636 pixDestroy(&pixsub);
637 return pixd;
638 }
639
640
641 /*!
642 * octreeGenerateAndPrune()
643 *
644 * Input: pixs
645 * number of colors to use (between 128 and 256)
646 * number of reserved colors
647 * &cmap (made and returned)
648 * Return: octree, colormap and number of colors used, or null
649 * on error
650 *
651 * Notes:
652 * (1) The number of colors in the cmap may differ from the number
653 * of colors requested, but it will not be larger than 256
654 */
655 static CQCELL ***
octreeGenerateAndPrune(PIX * pixs,l_int32 colors,l_int32 reservedcolors,PIXCMAP ** pcmap)656 octreeGenerateAndPrune(PIX *pixs,
657 l_int32 colors,
658 l_int32 reservedcolors,
659 PIXCMAP **pcmap)
660 {
661 l_int32 rval, gval, bval, cindex;
662 l_int32 level, ncells, octindex;
663 l_int32 w, h, wpls;
664 l_int32 i, j, isub;
665 l_int32 npix; /* number of remaining pixels to be assigned */
666 l_int32 ncolor; /* number of remaining color cells to be used */
667 l_int32 ppc; /* ave number of pixels left for each color cell */
668 l_int32 rv, gv, bv;
669 l_float32 thresholdFactor[] = {0.01, 0.01, 1.0, 1.0, 1.0, 1.0};
670 l_float32 thresh; /* factor of ppc for this level */
671 l_uint32 *datas, *lines;
672 l_uint32 *rtab, *gtab, *btab;
673 CQCELL ***cqcaa; /* one array for each octree level */
674 CQCELL **cqca, **cqcasub;
675 CQCELL *cqc, *cqcsub;
676 PIXCMAP *cmap;
677 NUMA *nat; /* accumulates levels for threshold cells */
678 NUMA *nar; /* accumulates levels for residual cells */
679
680 PROCNAME("octreeGenerateAndPrune");
681
682 if (!pixs)
683 return (CQCELL ***)ERROR_PTR("pixs not defined", procName, NULL);
684 if (pixGetDepth(pixs) != 32)
685 return (CQCELL ***)ERROR_PTR("pixs must be 32 bpp", procName, NULL);
686 if (colors < 128 || colors > 256)
687 return (CQCELL ***)ERROR_PTR("colors not in [128,256]", procName, NULL);
688 if (!pcmap)
689 return (CQCELL ***)ERROR_PTR("&cmap not defined", procName, NULL);
690
691 /* Make the canonical index tables */
692 if (makeRGBToIndexTables(&rtab, >ab, &btab, CQ_NLEVELS))
693 return (CQCELL ***)ERROR_PTR("tables not made", procName, NULL);
694
695 if ((cqcaa = cqcellTreeCreate()) == NULL)
696 return (CQCELL ***)ERROR_PTR("cqcaa not made", procName, NULL);
697
698 /* Generate an 8 bpp cmap (max size 256) */
699 cmap = pixcmapCreate(8);
700 *pcmap = cmap;
701
702 pixGetDimensions(pixs, &w, &h, NULL);
703 npix = w * h; /* initialize to all pixels */
704 ncolor = colors - reservedcolors - EXTRA_RESERVED_COLORS;
705 ppc = npix / ncolor;
706 datas = pixGetData(pixs);
707 wpls = pixGetWpl(pixs);
708
709 /* Accumulate the centers of each cluster at level CQ_NLEVELS */
710 ncells = 1 << (3 * CQ_NLEVELS);
711 cqca = cqcaa[CQ_NLEVELS];
712 for (i = 0; i < h; i++) {
713 lines = datas + i * wpls;
714 for (j = 0; j < w; j++) {
715 extractRGBValues(lines[j], &rval, &gval, &bval);
716 octindex = rtab[rval] | gtab[gval] | btab[bval];
717 cqc = cqca[octindex];
718 cqc->n++;
719 }
720 }
721
722 /* Arrays for storing statistics */
723 if ((nat = numaCreate(0)) == NULL)
724 return (CQCELL ***)ERROR_PTR("nat not made", procName, NULL);
725 if ((nar = numaCreate(0)) == NULL)
726 return (CQCELL ***)ERROR_PTR("nar not made", procName, NULL);
727
728 /* Prune back from the lowest level and generate the colormap */
729 for (level = CQ_NLEVELS - 1; level >= 2; level--) {
730 thresh = thresholdFactor[level];
731 cqca = cqcaa[level];
732 cqcasub = cqcaa[level + 1];
733 ncells = 1 << (3 * level);
734 for (i = 0; i < ncells; i++) { /* i is octindex at level */
735 cqc = cqca[i];
736 for (j = 0; j < 8; j++) { /* check all subnodes */
737 isub = 8 * i + j; /* isub is octindex at level+1 */
738 cqcsub = cqcasub[isub];
739 if (cqcsub->bleaf == 1) { /* already a leaf? */
740 cqc->nleaves++; /* count the subcube leaves */
741 continue;
742 }
743 if (cqcsub->n >= thresh * ppc) { /* make it a true leaf? */
744 cqcsub->bleaf = 1;
745 if (cmap->n < 256) {
746 cqcsub->index = cmap->n; /* assign the color index */
747 getRGBFromOctcube(isub, level + 1, &rv, &gv, &bv);
748 pixcmapAddColor(cmap, rv, gv, bv);
749 #if 1 /* save values */
750 cqcsub->rc = rv;
751 cqcsub->gc = gv;
752 cqcsub->bc = bv;
753 #endif
754 }
755 else {
756 /* This doesn't seem to happen. */
757 L_WARNING("possibly assigned pixels to wrong color",
758 procName);
759 pixcmapGetNearestIndex(cmap, rv, gv, bv, &cindex);
760 cqcsub->index = cindex; /* assign to the nearest */
761 pixcmapGetColor(cmap, cindex, &rval, &gval, &bval);
762 cqcsub->rc = rval;
763 cqcsub->gc = gval;
764 cqcsub->bc = bval;
765 }
766 cqc->nleaves++;
767 npix -= cqcsub->n;
768 ncolor--;
769 if (ncolor > 0)
770 ppc = npix / ncolor;
771 else if (ncolor + reservedcolors > 0)
772 ppc = npix / (ncolor + reservedcolors);
773 else
774 ppc = 1000000; /* make it big */
775 numaAddNumber(nat, level + 1);
776
777 #if DEBUG_OCTCUBE_CMAP
778 fprintf(stderr, "Exceeds threshold: colors used = %d, colors remaining = %d\n",
779 cmap->n, ncolor + reservedcolors);
780 fprintf(stderr, " cell with %d pixels, npix = %d, ppc = %d\n",
781 cqcsub->n, npix, ppc);
782 fprintf(stderr, " index = %d, level = %d, subindex = %d\n",
783 i, level, j);
784 fprintf(stderr, " rv = %d, gv = %d, bv = %d\n", rv, gv, bv);
785 #endif /* DEBUG_OCTCUBE_CMAP */
786
787 }
788 }
789 if (cqc->nleaves > 0 || level == 2) { /* make the cube a leaf now */
790 cqc->bleaf = 1;
791 if (cqc->nleaves < 8) { /* residual CTE cube: acquire the
792 * remaining pixels */
793 for (j = 0; j < 8; j++) { /* check all subnodes */
794 isub = 8 * i + j;
795 cqcsub = cqcasub[isub];
796 if (cqcsub->bleaf == 0) /* absorb */
797 cqc->n += cqcsub->n;
798 }
799 if (cmap->n < 256) {
800 cqc->index = cmap->n; /* assign the color index */
801 getRGBFromOctcube(i, level, &rv, &gv, &bv);
802 pixcmapAddColor(cmap, rv, gv, bv);
803 #if 1 /* save values */
804 cqc->rc = rv;
805 cqc->gc = gv;
806 cqc->bc = bv;
807 #endif
808 }
809 else {
810 L_WARNING("possibly assigned pixels to wrong color",
811 procName);
812 /* This is very bad. It will only cause trouble
813 * with dithering, and we try to avoid it with
814 * EXTRA_RESERVED_PIXELS. */
815 pixcmapGetNearestIndex(cmap, rv, gv, bv, &cindex);
816 cqc->index = cindex; /* assign to the nearest */
817 pixcmapGetColor(cmap, cindex, &rval, &gval, &bval);
818 cqc->rc = rval;
819 cqc->gc = gval;
820 cqc->bc = bval;
821 }
822 npix -= cqc->n;
823 ncolor--;
824 if (ncolor > 0)
825 ppc = npix / ncolor;
826 else if (ncolor + reservedcolors > 0)
827 ppc = npix / (ncolor + reservedcolors);
828 else
829 ppc = 1000000; /* make it big */
830 numaAddNumber(nar, level);
831
832 #if DEBUG_OCTCUBE_CMAP
833 fprintf(stderr, "By remainder: colors used = %d, colors remaining = %d\n",
834 cmap->n, ncolor + reservedcolors);
835 fprintf(stderr, " cell with %d pixels, npix = %d, ppc = %d\n",
836 cqc->n, npix, ppc);
837 fprintf(stderr, " index = %d, level = %d\n", i, level);
838 fprintf(stderr, " rv = %d, gv = %d, bv = %d\n", rv, gv, bv);
839 #endif /* DEBUG_OCTCUBE_CMAP */
840
841 }
842 }
843 else { /* absorb all the subpixels but don't make it a leaf */
844 for (j = 0; j < 8; j++) { /* absorb from all subnodes */
845 isub = 8 * i + j;
846 cqcsub = cqcasub[isub];
847 cqc->n += cqcsub->n;
848 }
849 }
850 }
851 }
852
853 #if PRINT_OCTCUBE_STATS
854 {
855 l_int32 tc[] = {0, 0, 0, 0, 0, 0, 0};
856 l_int32 rc[] = {0, 0, 0, 0, 0, 0, 0};
857 l_int32 nt, nr, ival;
858
859 nt = numaGetCount(nat);
860 nr = numaGetCount(nar);
861 for (i = 0; i < nt; i++) {
862 numaGetIValue(nat, i, &ival);
863 tc[ival]++;
864 }
865 for (i = 0; i < nr; i++) {
866 numaGetIValue(nar, i, &ival);
867 rc[ival]++;
868 }
869 fprintf(stderr, " Threshold cells formed: %d\n", nt);
870 for (i = 1; i < CQ_NLEVELS + 1; i++)
871 fprintf(stderr, " level %d: %d\n", i, tc[i]);
872 fprintf(stderr, "\n Residual cells formed: %d\n", nr);
873 for (i = 0; i < CQ_NLEVELS ; i++)
874 fprintf(stderr, " level %d: %d\n", i, rc[i]);
875 }
876 #endif /* PRINT_OCTCUBE_STATS */
877
878 numaDestroy(&nat);
879 numaDestroy(&nar);
880 FREE(rtab);
881 FREE(gtab);
882 FREE(btab);
883
884 return cqcaa;
885 }
886
887
888 /*!
889 * pixOctreeQuantizePixels()
890 *
891 * Input: pixs (32 bpp)
892 * octree in array format
893 * ditherflag (1 for dithering, 0 for no dithering)
894 * Return: pixd or null on error
895 *
896 * Notes:
897 * (1) This routine doesn't need to use the CTEs (colormap
898 * table entries) because the color indices are embedded
899 * in the octree. Thus, the calling program must make
900 * and attach the colormap to pixd after it is returned.
901 * (2) Dithering is performed in integers, effectively rounding
902 * to 1/8 sample increment. The data in the integer buffers is
903 * 64 times the sample values. The 'dif' is 8 times the
904 * sample values, and this spread, multiplied by 8, to the
905 * integer buffers. Because the dif is truncated to an
906 * integer, the dither is accurate to 1/8 of a sample increment,
907 * or 1/2048 of the color range.
908 */
909 static PIX *
pixOctreeQuantizePixels(PIX * pixs,CQCELL *** cqcaa,l_int32 ditherflag)910 pixOctreeQuantizePixels(PIX *pixs,
911 CQCELL ***cqcaa,
912 l_int32 ditherflag)
913 {
914 l_uint8 *bufu8r, *bufu8g, *bufu8b;
915 l_int32 rval, gval, bval;
916 l_int32 octindex, index;
917 l_int32 val1, val2, val3, dif;
918 l_int32 w, h, wpls, wpld, i, j;
919 l_int32 rc, gc, bc;
920 l_int32 *buf1r, *buf1g, *buf1b, *buf2r, *buf2g, *buf2b;
921 l_uint32 *rtab, *gtab, *btab;
922 l_uint32 *datas, *datad, *lines, *lined;
923 PIX *pixd;
924
925 PROCNAME("pixOctreeQuantizePixels");
926
927 if (!pixs)
928 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
929 if (pixGetDepth(pixs) != 32)
930 return (PIX *)ERROR_PTR("pixs must be 32 bpp", procName, NULL);
931 if (!cqcaa)
932 return (PIX *)ERROR_PTR("cqcaa not defined", procName, NULL);
933
934 /* Make the canonical index tables */
935 if (makeRGBToIndexTables(&rtab, >ab, &btab, CQ_NLEVELS))
936 return (PIX *)ERROR_PTR("tables not made", procName, NULL);
937
938 /* Make output 8 bpp palette image */
939 pixGetDimensions(pixs, &w, &h, NULL);
940 datas = pixGetData(pixs);
941 wpls = pixGetWpl(pixs);
942 if ((pixd = pixCreate(w, h, 8)) == NULL)
943 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
944 pixCopyResolution(pixd, pixs);
945 pixCopyInputFormat(pixd, pixs);
946 datad = pixGetData(pixd);
947 wpld = pixGetWpl(pixd);
948
949 /* Traverse tree from root, looking for lowest cube
950 * that is a leaf, and set dest pix to its
951 * colortable index value. The results are far
952 * better when dithering to get a more accurate
953 * average color. */
954 if (ditherflag == 0) { /* no dithering */
955 for (i = 0; i < h; i++) {
956 lines = datas + i * wpls;
957 lined = datad + i * wpld;
958 for (j = 0; j < w; j++) {
959 extractRGBValues(lines[j], &rval, &gval, &bval);
960 octindex = rtab[rval] | gtab[gval] | btab[bval];
961 octreeFindColorCell(octindex, cqcaa, &index, &rc, &gc, &bc);
962 SET_DATA_BYTE(lined, j, index);
963 }
964 }
965 }
966 else { /* Dither */
967 bufu8r = (l_uint8 *)CALLOC(w, sizeof(l_uint8));
968 bufu8g = (l_uint8 *)CALLOC(w, sizeof(l_uint8));
969 bufu8b = (l_uint8 *)CALLOC(w, sizeof(l_uint8));
970 buf1r = (l_int32 *)CALLOC(w, sizeof(l_int32));
971 buf1g = (l_int32 *)CALLOC(w, sizeof(l_int32));
972 buf1b = (l_int32 *)CALLOC(w, sizeof(l_int32));
973 buf2r = (l_int32 *)CALLOC(w, sizeof(l_int32));
974 buf2g = (l_int32 *)CALLOC(w, sizeof(l_int32));
975 buf2b = (l_int32 *)CALLOC(w, sizeof(l_int32));
976 if (!bufu8r || !bufu8g || !bufu8b)
977 return (PIX *)ERROR_PTR("uint8 mono line buf not made",
978 procName, NULL);
979 if (!buf1r || !buf1g || !buf1b || !buf2r || !buf2g || !buf2b)
980 return (PIX *)ERROR_PTR("mono line buf not made", procName, NULL);
981
982 /* Start by priming buf2; line 1 is above line 2 */
983 pixGetRGBLine(pixs, 0, bufu8r, bufu8g, bufu8b);
984 for (j = 0; j < w; j++) {
985 buf2r[j] = 64 * bufu8r[j];
986 buf2g[j] = 64 * bufu8g[j];
987 buf2b[j] = 64 * bufu8b[j];
988 }
989
990 for (i = 0; i < h - 1; i++) {
991 /* Swap data 2 --> 1, and read in new line 2 */
992 memcpy(buf1r, buf2r, 4 * w);
993 memcpy(buf1g, buf2g, 4 * w);
994 memcpy(buf1b, buf2b, 4 * w);
995 pixGetRGBLine(pixs, i + 1, bufu8r, bufu8g, bufu8b);
996 for (j = 0; j < w; j++) {
997 buf2r[j] = 64 * bufu8r[j];
998 buf2g[j] = 64 * bufu8g[j];
999 buf2b[j] = 64 * bufu8b[j];
1000 }
1001
1002 /* Dither */
1003 lined = datad + i * wpld;
1004 for (j = 0; j < w - 1; j++) {
1005 rval = buf1r[j] / 64;
1006 gval = buf1g[j] / 64;
1007 bval = buf1b[j] / 64;
1008 octindex = rtab[rval] | gtab[gval] | btab[bval];
1009 octreeFindColorCell(octindex, cqcaa, &index, &rc, &gc, &bc);
1010 SET_DATA_BYTE(lined, j, index);
1011
1012 dif = buf1r[j] / 8 - 8 * rc;
1013 if (dif != 0) {
1014 val1 = buf1r[j + 1] + 3 * dif;
1015 val2 = buf2r[j] + 3 * dif;
1016 val3 = buf2r[j + 1] + 2 * dif;
1017 if (dif > 0) {
1018 buf1r[j + 1] = L_MIN(16383, val1);
1019 buf2r[j] = L_MIN(16383, val2);
1020 buf2r[j + 1] = L_MIN(16383, val3);
1021 }
1022 else if (dif < 0) {
1023 buf1r[j + 1] = L_MAX(0, val1);
1024 buf2r[j] = L_MAX(0, val2);
1025 buf2r[j + 1] = L_MAX(0, val3);
1026 }
1027 }
1028
1029 dif = buf1g[j] / 8 - 8 * gc;
1030 if (dif != 0) {
1031 val1 = buf1g[j + 1] + 3 * dif;
1032 val2 = buf2g[j] + 3 * dif;
1033 val3 = buf2g[j + 1] + 2 * dif;
1034 if (dif > 0) {
1035 buf1g[j + 1] = L_MIN(16383, val1);
1036 buf2g[j] = L_MIN(16383, val2);
1037 buf2g[j + 1] = L_MIN(16383, val3);
1038 }
1039 else if (dif < 0) {
1040 buf1g[j + 1] = L_MAX(0, val1);
1041 buf2g[j] = L_MAX(0, val2);
1042 buf2g[j + 1] = L_MAX(0, val3);
1043 }
1044 }
1045
1046 dif = buf1b[j] / 8 - 8 * bc;
1047 if (dif != 0) {
1048 val1 = buf1b[j + 1] + 3 * dif;
1049 val2 = buf2b[j] + 3 * dif;
1050 val3 = buf2b[j + 1] + 2 * dif;
1051 if (dif > 0) {
1052 buf1b[j + 1] = L_MIN(16383, val1);
1053 buf2b[j] = L_MIN(16383, val2);
1054 buf2b[j + 1] = L_MIN(16383, val3);
1055 }
1056 else if (dif < 0) {
1057 buf1b[j + 1] = L_MAX(0, val1);
1058 buf2b[j] = L_MAX(0, val2);
1059 buf2b[j + 1] = L_MAX(0, val3);
1060 }
1061 }
1062 }
1063
1064 /* Get last pixel in row; no downward propagation */
1065 rval = buf1r[w - 1] / 64;
1066 gval = buf1g[w - 1] / 64;
1067 bval = buf1b[w - 1] / 64;
1068 octindex = rtab[rval] | gtab[gval] | btab[bval];
1069 octreeFindColorCell(octindex, cqcaa, &index, &rc, &gc, &bc);
1070 SET_DATA_BYTE(lined, w - 1, index);
1071 }
1072
1073 /* Get last row of pixels; no leftward propagation */
1074 lined = datad + (h - 1) * wpld;
1075 for (j = 0; j < w; j++) {
1076 rval = buf2r[j] / 64;
1077 gval = buf2g[j] / 64;
1078 bval = buf2b[j] / 64;
1079 octindex = rtab[rval] | gtab[gval] | btab[bval];
1080 octreeFindColorCell(octindex, cqcaa, &index, &rc, &gc, &bc);
1081 SET_DATA_BYTE(lined, j, index);
1082 }
1083
1084 FREE(bufu8r);
1085 FREE(bufu8g);
1086 FREE(bufu8b);
1087 FREE(buf1r);
1088 FREE(buf1g);
1089 FREE(buf1b);
1090 FREE(buf2r);
1091 FREE(buf2g);
1092 FREE(buf2b);
1093 }
1094
1095 FREE(rtab);
1096 FREE(gtab);
1097 FREE(btab);
1098 return pixd;
1099 }
1100
1101
1102 /*!
1103 * octreeFindColorCell()
1104 *
1105 * Input: octindex
1106 * cqcaa
1107 * &index (<return> index of CTE; returned to set pixel value)
1108 * &rval (<return> of CTE)
1109 * &gval (<return> of CTE)
1110 * &bval (<return> of CTE)
1111 * Return: 0 if OK; 1 on error
1112 *
1113 * Notes:
1114 * (1) As this is in inner loop, we don't check input pointers!
1115 * (2) This traverses from the root (well, actually from level 2,
1116 * because the level 2 cubes are the largest CTE cubes),
1117 * and finds the index number of the cell and the color values,
1118 * which can be used either directly or in a (Floyd-Steinberg)
1119 * error-diffusion dithering algorithm.
1120 */
1121 static l_int32
octreeFindColorCell(l_int32 octindex,CQCELL *** cqcaa,l_int32 * pindex,l_int32 * prval,l_int32 * pgval,l_int32 * pbval)1122 octreeFindColorCell(l_int32 octindex,
1123 CQCELL ***cqcaa,
1124 l_int32 *pindex,
1125 l_int32 *prval,
1126 l_int32 *pgval,
1127 l_int32 *pbval)
1128 {
1129 l_int32 level;
1130 l_int32 baseindex, subindex;
1131 CQCELL *cqc, *cqcsub;
1132
1133 /* Use rgb values stored in the cubes; a little faster */
1134 for (level = 2; level < CQ_NLEVELS; level++) {
1135 getOctcubeIndices(octindex, level, &baseindex, &subindex);
1136 cqc = cqcaa[level][baseindex];
1137 cqcsub = cqcaa[level + 1][subindex];
1138 if (cqcsub->bleaf == 0) { /* use cell at level above */
1139 *pindex = cqc->index;
1140 *prval = cqc->rc;
1141 *pgval = cqc->gc;
1142 *pbval = cqc->bc;
1143 break;
1144 }
1145 else if (level == CQ_NLEVELS - 1) { /* reached the bottom */
1146 *pindex = cqcsub->index;
1147 *prval = cqcsub->rc;
1148 *pgval = cqcsub->gc;
1149 *pbval = cqcsub->bc;
1150 break;
1151 }
1152 }
1153
1154 #if 0
1155 /* Generate rgb values for each cube on the fly; slower */
1156 for (level = 2; level < CQ_NLEVELS; level++) {
1157 l_int32 rv, gv, bv;
1158 getOctcubeIndices(octindex, level, &baseindex, &subindex);
1159 cqc = cqcaa[level][baseindex];
1160 cqcsub = cqcaa[level + 1][subindex];
1161 if (cqcsub->bleaf == 0) { /* use cell at level above */
1162 getRGBFromOctcube(baseindex, level, &rv, &gv, &bv);
1163 *pindex = cqc->index;
1164 *prval = rv;
1165 *pgval = gv;
1166 *pbval = bv;
1167 break;
1168 }
1169 else if (level == CQ_NLEVELS - 1) { /* reached the bottom */
1170 getRGBFromOctcube(subindex, level + 1, &rv, &gv, &bv);
1171 *pindex = cqcsub->index;
1172 *prval = rv;
1173 *pgval = gv;
1174 *pbval = bv;
1175 break;
1176 }
1177 }
1178 #endif
1179
1180 return 0;
1181 }
1182
1183
1184
1185 /*------------------------------------------------------------------*
1186 * Helper cqcell functions *
1187 *------------------------------------------------------------------*/
1188 /*!
1189 * cqcellTreeCreate()
1190 *
1191 * Input: none
1192 * Return: cqcell array tree
1193 */
1194 static CQCELL ***
cqcellTreeCreate(void)1195 cqcellTreeCreate(void)
1196 {
1197 l_int32 level, ncells, i;
1198 CQCELL ***cqcaa;
1199 CQCELL **cqca; /* one array for each octree level */
1200
1201 PROCNAME("cqcellTreeCreate");
1202
1203 /* Make array of accumulation cell arrays from levels 1 to 5 */
1204 if ((cqcaa = (CQCELL ***)CALLOC(CQ_NLEVELS + 1, sizeof(CQCELL **))) == NULL)
1205 return (CQCELL ***)ERROR_PTR("cqcaa not made", procName, NULL);
1206 for (level = 0; level <= CQ_NLEVELS; level++) {
1207 ncells = 1 << (3 * level);
1208 if ((cqca = (CQCELL **)CALLOC(ncells, sizeof(CQCELL *))) == NULL)
1209 return (CQCELL ***)ERROR_PTR("cqca not made", procName, NULL);
1210 cqcaa[level] = cqca;
1211 for (i = 0; i < ncells; i++) {
1212 if ((cqca[i] = (CQCELL *)CALLOC(1, sizeof(CQCELL))) == NULL)
1213 return (CQCELL ***)ERROR_PTR("cqc not made", procName, NULL);
1214 }
1215 }
1216
1217 return cqcaa;
1218 }
1219
1220
1221 /*!
1222 * cqcellTreeDestroy()
1223 *
1224 * Input: &cqcaa (<to be nulled>
1225 * Return: void
1226 */
1227 static void
cqcellTreeDestroy(CQCELL **** pcqcaa)1228 cqcellTreeDestroy(CQCELL ****pcqcaa)
1229 {
1230 l_int32 level, ncells, i;
1231 CQCELL ***cqcaa;
1232 CQCELL **cqca;
1233
1234 PROCNAME("cqcellTreeDestroy");
1235
1236 if (pcqcaa == NULL) {
1237 L_WARNING("ptr address is NULL", procName);
1238 return;
1239 }
1240
1241 if ((cqcaa = *pcqcaa) == NULL)
1242 return;
1243
1244 for (level = 0; level <= CQ_NLEVELS; level++) {
1245 cqca = cqcaa[level];
1246 ncells = 1 << (3 * level);
1247 for (i = 0; i < ncells; i++)
1248 FREE(cqca[i]);
1249 FREE(cqca);
1250 }
1251 FREE(cqcaa);
1252 *pcqcaa = NULL;
1253
1254 return;
1255 }
1256
1257
1258
1259 /*------------------------------------------------------------------*
1260 * Helper index functions *
1261 *------------------------------------------------------------------*/
1262 /*!
1263 * makeRGBToIndexTables()
1264 *
1265 * Input: &rtab, >ab, &btab (<return> tables)
1266 * cqlevels (can be 1, 2, 3, 4, 5 or 6)
1267 * Return: 0 if OK; 1 on error
1268 *
1269 * Set up tables. e.g., for cqlevels = 5, we need an integer 0 < i < 2^15:
1270 * rtab = (0 i7 0 0 i6 0 0 i5 0 0 i4 0 0 i3 0 0)
1271 * gtab = (0 0 i7 0 0 i6 0 0 i5 0 0 i4 0 0 i3 0)
1272 * btab = (0 0 0 i7 0 0 i6 0 0 i5 0 0 i4 0 0 i3)
1273 *
1274 * The tables are then used to map from rbg --> index as follows:
1275 * index = (0 r7 g7 b7 r6 g6 b6 r5 g5 b5 r4 g4 b4 r3 g3 b3)
1276 *
1277 * e.g., for cqlevels = 4, we map to
1278 * index = (0 0 0 0 r7 g7 b7 r6 g6 b6 r5 g5 b5 r4 g4 b4)
1279 *
1280 * This may look a bit strange. The notation 'r7' means the MSBit of
1281 * the r value (which has 8 bits, going down from r7 to r0).
1282 * Keep in mind that r7 is actually the r component bit for level 1 of
1283 * the octtree. Level 1 is composed of 8 octcubes, represented by
1284 * the bits (r7 g7 b7), which divide the entire color space into
1285 * 8 cubes. At level 2, each of these 8 octcubes is further divided into
1286 * 8 cubes, each labeled by the second most significant bits (r6 g6 b6)
1287 * of the rgb color.
1288 */
1289 l_int32
makeRGBToIndexTables(l_uint32 ** prtab,l_uint32 ** pgtab,l_uint32 ** pbtab,l_int32 cqlevels)1290 makeRGBToIndexTables(l_uint32 **prtab,
1291 l_uint32 **pgtab,
1292 l_uint32 **pbtab,
1293 l_int32 cqlevels)
1294 {
1295 l_int32 i;
1296 l_uint32 *rtab, *gtab, *btab;
1297
1298 PROCNAME("makeRGBToIndexTables");
1299
1300 if (cqlevels < 1 || cqlevels > 6)
1301 return ERROR_INT("cqlevels must be in {1,...6}", procName, 1);
1302
1303 if (!prtab || !pgtab || !pbtab)
1304 return ERROR_INT("&*tab not defined", procName, 1);
1305 if ((rtab = (l_uint32 *)CALLOC(256, sizeof(l_uint32))) == NULL)
1306 return ERROR_INT("rtab not made", procName, 1);
1307 if ((gtab = (l_uint32 *)CALLOC(256, sizeof(l_uint32))) == NULL)
1308 return ERROR_INT("gtab not made", procName, 1);
1309 if ((btab = (l_uint32 *)CALLOC(256, sizeof(l_uint32))) == NULL)
1310 return ERROR_INT("btab not made", procName, 1);
1311 *prtab = rtab;
1312 *pgtab = gtab;
1313 *pbtab = btab;
1314
1315 switch (cqlevels)
1316 {
1317 case 1:
1318 for (i = 0; i < 256; i++) {
1319 rtab[i] = (i >> 5) & 0x0004;
1320 gtab[i] = (i >> 6) & 0x0002;
1321 btab[i] = (i >> 7);
1322 }
1323 break;
1324 case 2:
1325 for (i = 0; i < 256; i++) {
1326 rtab[i] = ((i >> 2) & 0x0020) | ((i >> 4) & 0x0004);
1327 gtab[i] = ((i >> 3) & 0x0010) | ((i >> 5) & 0x0002);
1328 btab[i] = ((i >> 4) & 0x0008) | ((i >> 6) & 0x0001);
1329 }
1330 break;
1331 case 3:
1332 for (i = 0; i < 256; i++) {
1333 rtab[i] = ((i << 1) & 0x0100) | ((i >> 1) & 0x0020) |
1334 ((i >> 3) & 0x0004);
1335 gtab[i] = (i & 0x0080) | ((i >> 2) & 0x0010) |
1336 ((i >> 4) & 0x0002);
1337 btab[i] = ((i >> 1) & 0x0040) | ((i >> 3) & 0x0008) |
1338 ((i >> 5) & 0x0001);
1339 }
1340 break;
1341 case 4:
1342 for (i = 0; i < 256; i++) {
1343 rtab[i] = ((i << 4) & 0x0800) | ((i << 2) & 0x0100) |
1344 (i & 0x0020) | ((i >> 2) & 0x0004);
1345 gtab[i] = ((i << 3) & 0x0400) | ((i << 1) & 0x0080) |
1346 ((i >> 1) & 0x0010) | ((i >> 3) & 0x0002);
1347 btab[i] = ((i << 2) & 0x0200) | (i & 0x0040) |
1348 ((i >> 2) & 0x0008) | ((i >> 4) & 0x0001);
1349 }
1350 break;
1351 case 5:
1352 for (i = 0; i < 256; i++) {
1353 rtab[i] = ((i << 7) & 0x4000) | ((i << 5) & 0x0800) |
1354 ((i << 3) & 0x0100) | ((i << 1) & 0x0020) |
1355 ((i >> 1) & 0x0004);
1356 gtab[i] = ((i << 6) & 0x2000) | ((i << 4) & 0x0400) |
1357 ((i << 2) & 0x0080) | (i & 0x0010) |
1358 ((i >> 2) & 0x0002);
1359 btab[i] = ((i << 5) & 0x1000) | ((i << 3) & 0x0200) |
1360 ((i << 1) & 0x0040) | ((i >> 1) & 0x0008) |
1361 ((i >> 3) & 0x0001);
1362 }
1363 break;
1364 case 6:
1365 for (i = 0; i < 256; i++) {
1366 rtab[i] = ((i << 10) & 0x20000) | ((i << 8) & 0x4000) |
1367 ((i << 6) & 0x0800) | ((i << 4) & 0x0100) |
1368 ((i << 2) & 0x0020) | (i & 0x0004);
1369 gtab[i] = ((i << 9) & 0x10000) | ((i << 7) & 0x2000) |
1370 ((i << 5) & 0x0400) | ((i << 3) & 0x0080) |
1371 ((i << 1) & 0x0010) | ((i >> 1) & 0x0002);
1372 btab[i] = ((i << 8) & 0x8000) | ((i << 6) & 0x1000) |
1373 ((i << 4) & 0x0200) | ((i << 2) & 0x0040) |
1374 (i & 0x0008) | ((i >> 2) & 0x0001);
1375 }
1376 break;
1377 default:
1378 ERROR_INT("cqlevels not in [1...6]", procName, 1);
1379 break;
1380 }
1381
1382 return 0;
1383 }
1384
1385
1386 /*!
1387 * getOctcubeIndexFromRGB()
1388 *
1389 * Input: rval, gval, bval
1390 * rtab, gtab, btab (generated with makeRGBToIndexTables())
1391 * &index (<return>)
1392 * Return: void
1393 *
1394 * Note: no error checking!
1395 */
1396 void
getOctcubeIndexFromRGB(l_int32 rval,l_int32 gval,l_int32 bval,l_uint32 * rtab,l_uint32 * gtab,l_uint32 * btab,l_uint32 * pindex)1397 getOctcubeIndexFromRGB(l_int32 rval,
1398 l_int32 gval,
1399 l_int32 bval,
1400 l_uint32 *rtab,
1401 l_uint32 *gtab,
1402 l_uint32 *btab,
1403 l_uint32 *pindex)
1404 {
1405 *pindex = rtab[rval] | gtab[gval] | btab[bval];
1406 return;
1407 }
1408
1409
1410 /*!
1411 * getRGBFromOctcube()
1412 *
1413 * Input: octcube index
1414 * level (at which index is expressed)
1415 * &rval (<return> r val of this cube)
1416 * &gval (<return> g val of this cube)
1417 * &bval (<return> b val of this cube)
1418 * Return: void
1419 *
1420 * Notes:
1421 * (1) We can consider all octcube indices to represent a
1422 * specific point in color space: namely, the location
1423 * of the 'upper-left' corner of the cube, where indices
1424 * increase down and to the right. The upper left corner
1425 * of the color space is then 00000....
1426 * (2) The 'rgbindex' is a 24-bit representation of the location,
1427 * in octcube notation, at the center of the octcube.
1428 * To get to the center of an octcube, you choose the 111
1429 * octcube at the next lower level.
1430 * (3) For example, if the octcube index = 110101 (binary),
1431 * which is a level 2 expression, then the rgbindex
1432 * is the 24-bit representation of 110101111 (at level 3);
1433 * namely, 000110101111000000000000. The number is padded
1434 * with 3 leading 0s (because the representation uses
1435 * only 21 bits) and 12 trailing 0s (the default for
1436 * levels 4-7, which are contained within each of the level3
1437 * octcubes. Then the rgb values for the center of the
1438 * octcube are: rval = 11100000, gval = 10100000, bval = 01100000
1439 */
1440 static void
getRGBFromOctcube(l_int32 cubeindex,l_int32 level,l_int32 * prval,l_int32 * pgval,l_int32 * pbval)1441 getRGBFromOctcube(l_int32 cubeindex,
1442 l_int32 level,
1443 l_int32 *prval,
1444 l_int32 *pgval,
1445 l_int32 *pbval)
1446 {
1447 l_int32 rgbindex;
1448
1449 /* Bring to format in 21 bits: (r7 g7 b7 r6 g6 b6 ...) */
1450 /* This is valid for levels from 0 to 6 */
1451 rgbindex = cubeindex << (3 * (7 - level)); /* upper corner of cube */
1452 rgbindex |= (0x7 << (3 * (6 - level))); /* index to center of cube */
1453
1454 /* Extract separate pieces */
1455 *prval = ((rgbindex >> 13) & 0x80) |
1456 ((rgbindex >> 11) & 0x40) |
1457 ((rgbindex >> 9) & 0x20) |
1458 ((rgbindex >> 7) & 0x10) |
1459 ((rgbindex >> 5) & 0x08) |
1460 ((rgbindex >> 3) & 0x04) |
1461 ((rgbindex >> 1) & 0x02);
1462 *pgval = ((rgbindex >> 12) & 0x80) |
1463 ((rgbindex >> 10) & 0x40) |
1464 ((rgbindex >> 8) & 0x20) |
1465 ((rgbindex >> 6) & 0x10) |
1466 ((rgbindex >> 4) & 0x08) |
1467 ((rgbindex >> 2) & 0x04) |
1468 (rgbindex & 0x02);
1469 *pbval = ((rgbindex >> 11) & 0x80) |
1470 ((rgbindex >> 9) & 0x40) |
1471 ((rgbindex >> 7) & 0x20) |
1472 ((rgbindex >> 5) & 0x10) |
1473 ((rgbindex >> 3) & 0x08) |
1474 ((rgbindex >> 1) & 0x04) |
1475 ((rgbindex << 1) & 0x02);
1476
1477 return;
1478 }
1479
1480
1481 /*!
1482 * getOctcubeIndices()
1483 *
1484 * Input: rgbindex
1485 * octree level (0, 1, 2, 3, 4, 5)
1486 * &octcube base index (<return> index at the octree level)
1487 * &octcube sub index (<return> index at the next lower level)
1488 * Return: 0 if OK, 1 on error
1489 *
1490 * for CQ_NLEVELS = 6, the full RGB index is in the form:
1491 * index = (0[13] 0 r7 g7 b7 r6 g6 b6 r5 g5 b5 r4 g4 b4 r3 g3 b3 r2 g2 b2)
1492 * for CQ_NLEVELS = 5, the full RGB index is in the form:
1493 * index = (0[16] 0 r7 g7 b7 r6 g6 b6 r5 g5 b5 r4 g4 b4 r3 g3 b3)
1494 * for CQ_NLEVELS = 4, the full RGB index is in the form:
1495 * index = (0[19] 0 r7 g7 b7 r6 g6 b6 r5 g5 b5 r4 g4 b4)
1496 *
1497 * The base index is the index of the octcube at the level given,
1498 * whereas the sub index is the index at the next level down.
1499 *
1500 * For level 0: base index = 0
1501 * sub index is the 3 bit number (r7 g7 b7)
1502 * For level 1: base index = (r7 g7 b7)
1503 * sub index = (r7 g7 b7 r6 g6 b6)
1504 * For level 2: base index = (r7 g7 b7 r6 g6 b6)
1505 * sub index = (r7 g7 b7 r6 g6 b6 r5 g5 b5)
1506 * For level 3: base index = (r7 g7 b7 r6 g6 b6 r5 g5 b5)
1507 * sub index = (r7 g7 b7 r6 g6 b6 r5 g5 b5 r4 g4 b4)
1508 * For level 4: base index = (r7 g7 b7 r6 g6 b6 r5 g5 b5 r4 g4 b4)
1509 * sub index = (r7 g7 b7 r6 g6 b6 r5 g5 b5 r4 g4 b4 r3 g3 b3)
1510 * For level 5: base index = (r7 g7 b7 r6 g6 b6 r5 g5 b5 r4 g4 b4 r3 g3 b3)
1511 * sub index = (r7 g7 b7 r6 g6 b6 r5 g5 b5 r4 g4 b4 r3 g3 b3
1512 * r2 g2 b2)
1513 */
1514 static l_int32
getOctcubeIndices(l_int32 rgbindex,l_int32 level,l_int32 * pbindex,l_int32 * psindex)1515 getOctcubeIndices(l_int32 rgbindex,
1516 l_int32 level,
1517 l_int32 *pbindex,
1518 l_int32 *psindex)
1519 {
1520 PROCNAME("getOctcubeIndex");
1521
1522 if (level < 0 || level > CQ_NLEVELS - 1)
1523 return ERROR_INT("level must be in e.g., [0 ... 5]", procName, 1);
1524 if (!pbindex)
1525 return ERROR_INT("&bindex not defined", procName, 1);
1526 if (!psindex)
1527 return ERROR_INT("&sindex not defined", procName, 1);
1528
1529 *pbindex = rgbindex >> (3 * (CQ_NLEVELS - level));
1530 *psindex = rgbindex >> (3 * (CQ_NLEVELS - 1 - level));
1531 return 0;
1532 }
1533
1534
1535 /*!
1536 * octcubeGetCount()
1537 *
1538 * Input: level (valid values are in [1,...6]; there are 2^level
1539 * cubes along each side of the rgb cube)
1540 * &size (<return> 2^(3 * level) cubes in the entire rgb cube)
1541 * Return: 0 if OK, 1 on error. Caller must check!
1542 *
1543 * level: 1 2 3 4 5 6
1544 * size: 8 64 512 4098 32784 262272
1545 */
1546 static l_int32
octcubeGetCount(l_int32 level,l_int32 * psize)1547 octcubeGetCount(l_int32 level,
1548 l_int32 *psize)
1549 {
1550 PROCNAME("octcubeGetCount");
1551
1552 if (!psize)
1553 return ERROR_INT("&size not defined", procName, 1);
1554 if (level < 1 || level > 6)
1555 return ERROR_INT("invalid level", procName, 1);
1556
1557 *psize = 1 << (3 * level);
1558 return 0;
1559 }
1560
1561
1562 /*---------------------------------------------------------------------------*
1563 * Adaptive octree quantization based on population at a fixed level *
1564 *---------------------------------------------------------------------------*/
1565 /*!
1566 * pixOctreeQuantByPopulation()
1567 *
1568 * Input: pixs (32 bpp rgb)
1569 * level (significant bits for each of RGB; valid for {3,4},
1570 * Use 0 for default (level 4; recommended)
1571 * ditherflag (1 to dither, 0 otherwise)
1572 * Return: pixd (quantized to octcubes) or null on error
1573 *
1574 * Notes:
1575 * (1) This color quantization method works very well without
1576 * dithering, using octcubes at two different levels:
1577 * (a) the input @level, which is either 3 or 4
1578 * (b) level 2 (64 octcubes to cover the entire color space)
1579 * (2) For best results, using @level = 4 is recommended.
1580 * Why do we provide an option for using level 3? Because
1581 * there are 512 octcubes at level 3, and for many images
1582 * not more than 256 are filled. As a result, on some images
1583 * a very accurate quantized representation is possible using
1584 * @level = 3.
1585 * (3) This first breaks up the color space into octcubes at the
1586 * input @level, and computes, for each octcube, the average
1587 * value of the pixels that are in it.
1588 * (4) Then there are two possible situations:
1589 * (a) If there are not more than 256 populated octcubes,
1590 * it returns a cmapped pix with those values assigned.
1591 * (b) Otherwise, it selects 192 octcubes containing the largest
1592 * number of pixels and quantizes pixels within those octcubes
1593 * to their average. Then, to handle the residual pixels
1594 * that are not in those 192 octcubes, it generates a
1595 * level 2 octree consisting of 64 octcubes, and within
1596 * each octcube it quantizes the residual pixels to their
1597 * average within each of those level 2 octcubes.
1598 * (5) Unpopulated level 2 octcubes are represented in the colormap
1599 * by their centers. This, of course, has no effect unless
1600 * dithering is used for the output image.
1601 * (6) The depth of pixd is the minumum required to suppport the
1602 * number of colors found at @level; namely, 2, 4 or 8.
1603 * (7) This function works particularly well on images such as maps,
1604 * where there are a relatively small number of well-populated
1605 * colors, but due to antialiasing and compression artifacts
1606 * there may be a large number of different colors. This will
1607 * pull out and represent accurately the highly populated colors,
1608 * while still making a reasonable approximation for the others.
1609 * (8) The highest level of octcubes allowed is 4. Use of higher
1610 * levels typically results in having a small fraction of
1611 * pixels in the most populated 192 octcubes. As a result,
1612 * most of the pixels are represented at level 2, which is
1613 * not sufficiently accurate.
1614 * (9) Dithering shows artifacts on some images. If you plan to
1615 * dither, pixOctreeColorQuant() and pixFixedOctcubeQuant256()
1616 * usually give better results.
1617 */
1618 PIX *
pixOctreeQuantByPopulation(PIX * pixs,l_int32 level,l_int32 ditherflag)1619 pixOctreeQuantByPopulation(PIX *pixs,
1620 l_int32 level,
1621 l_int32 ditherflag)
1622 {
1623 l_int32 w, h, wpls, wpld, i, j, depth, size, ncolors, index;
1624 l_int32 rval, gval, bval;
1625 l_int32 *rarray, *garray, *barray, *narray, *iarray;
1626 l_uint32 octindex, octindex2;
1627 l_uint32 *rtab, *gtab, *btab, *rtab2, *gtab2, *btab2;
1628 l_uint32 *lines, *lined, *datas, *datad;
1629 L_OCTCUBE_POP *opop;
1630 L_HEAP *lh;
1631 PIX *pixd;
1632 PIXCMAP *cmap;
1633
1634 PROCNAME("pixOctreeQuantByPopulation");
1635
1636 if (!pixs)
1637 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
1638 if (pixGetDepth(pixs) != 32)
1639 return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
1640 if (level == 0) level = 4;
1641 if (level < 3 || level > 4)
1642 return (PIX *)ERROR_PTR("level not in {3,4}", procName, NULL);
1643
1644 /* Do not dither if image is very small */
1645 pixGetDimensions(pixs, &w, &h, NULL);
1646 if (w < MIN_DITHER_SIZE && h < MIN_DITHER_SIZE && ditherflag == 1) {
1647 L_INFO("Small image: dithering turned off", procName);
1648 ditherflag = 0;
1649 }
1650
1651 if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
1652 return (PIX *)ERROR_PTR("size not returned", procName, NULL);
1653 if (makeRGBToIndexTables(&rtab, >ab, &btab, level))
1654 return (PIX *)ERROR_PTR("tables not made", procName, NULL);
1655
1656 if ((narray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
1657 return (PIX *)ERROR_PTR("narray not made", procName, NULL);
1658 if ((rarray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
1659 return (PIX *)ERROR_PTR("rarray not made", procName, NULL);
1660 if ((garray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
1661 return (PIX *)ERROR_PTR("garray not made", procName, NULL);
1662 if ((barray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
1663 return (PIX *)ERROR_PTR("barray not made", procName, NULL);
1664
1665 /* Place the pixels in octcube leaves. */
1666 datas = pixGetData(pixs);
1667 wpls = pixGetWpl(pixs);
1668 pixd = NULL;
1669 for (i = 0; i < h; i++) {
1670 lines = datas + i * wpls;
1671 for (j = 0; j < w; j++) {
1672 extractRGBValues(lines[j], &rval, &gval, &bval);
1673 octindex = rtab[rval] | gtab[gval] | btab[bval];
1674 narray[octindex]++;
1675 rarray[octindex] += rval;
1676 garray[octindex] += gval;
1677 barray[octindex] += bval;
1678 }
1679 }
1680
1681 /* Find the number of different colors */
1682 for (i = 0, ncolors = 0; i < size; i++) {
1683 if (narray[i] > 0)
1684 ncolors++;
1685 }
1686 if (ncolors <= 4)
1687 depth = 2;
1688 else if (ncolors <= 16)
1689 depth = 4;
1690 else
1691 depth = 8;
1692 pixd = pixCreate(w, h, depth);
1693 datad = pixGetData(pixd);
1694 wpld = pixGetWpl(pixd);
1695 pixCopyResolution(pixd, pixs);
1696 pixCopyInputFormat(pixd, pixs);
1697 cmap = pixcmapCreate(depth);
1698 pixSetColormap(pixd, cmap);
1699
1700 /* Average the colors in each octcube leaf. */
1701 for (i = 0; i < size; i++) {
1702 if (narray[i] > 0) {
1703 rarray[i] /= narray[i];
1704 garray[i] /= narray[i];
1705 barray[i] /= narray[i];
1706 }
1707 }
1708
1709 /* If ncolors <= 256, finish immediately. Do not dither.
1710 * Re-use narray to hold the colormap index + 1 */
1711 if (ncolors <= 256) {
1712 for (i = 0, index = 0; i < size; i++) {
1713 if (narray[i] > 0) {
1714 pixcmapAddColor(cmap, rarray[i], garray[i], barray[i]);
1715 narray[i] = index + 1; /* to avoid storing 0 */
1716 index++;
1717 }
1718 }
1719
1720 /* Set the cmap indices for each pixel */
1721 for (i = 0; i < h; i++) {
1722 lines = datas + i * wpls;
1723 lined = datad + i * wpld;
1724 for (j = 0; j < w; j++) {
1725 extractRGBValues(lines[j], &rval, &gval, &bval);
1726 octindex = rtab[rval] | gtab[gval] | btab[bval];
1727 switch (depth)
1728 {
1729 case 8:
1730 SET_DATA_BYTE(lined, j, narray[octindex] - 1);
1731 break;
1732 case 4:
1733 SET_DATA_QBIT(lined, j, narray[octindex] - 1);
1734 break;
1735 case 2:
1736 SET_DATA_DIBIT(lined, j, narray[octindex] - 1);
1737 break;
1738 default:
1739 L_WARNING("shouldn't get here", procName);
1740 }
1741 }
1742 }
1743 goto array_cleanup;
1744 }
1745
1746 /* More complicated. Sort by decreasing population */
1747 lh = lheapCreate(500, L_SORT_DECREASING);
1748 for (i = 0; i < size; i++) {
1749 if (narray[i] > 0) {
1750 opop = (L_OCTCUBE_POP *)CALLOC(1, sizeof(L_OCTCUBE_POP));
1751 opop->npix = (l_float32)narray[i];
1752 opop->index = i;
1753 opop->rval = rarray[i];
1754 opop->gval = garray[i];
1755 opop->bval = barray[i];
1756 lheapAdd(lh, opop);
1757 }
1758 }
1759
1760 /* Take the top 192. These will form the first 192 colors
1761 * in the cmap. iarray[i] holds the index into the cmap. */
1762 if ((iarray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
1763 return (PIX *)ERROR_PTR("iarray not made", procName, NULL);
1764 for (i = 0; i < 192; i++) {
1765 opop = (L_OCTCUBE_POP*)lheapRemove(lh);
1766 if (!opop) break;
1767 pixcmapAddColor(cmap, opop->rval, opop->gval, opop->bval);
1768 iarray[opop->index] = i + 1; /* +1 to avoid storing 0 */
1769
1770 #if DEBUG_POP
1771 fprintf(stderr, "i = %d, n = %6.0f, (r,g,b) = (%d %d %d)\n",
1772 i, opop->npix, opop->rval, opop->gval, opop->bval);
1773 #endif /* DEBUG_POP */
1774
1775 FREE(opop);
1776 }
1777
1778 /* Make the octindex tables for level 2, and reuse rarray, etc. */
1779 if (makeRGBToIndexTables(&rtab2, >ab2, &btab2, 2))
1780 return (PIX *)ERROR_PTR("level 2 tables not made", procName, NULL);
1781 for (i = 0; i < 64; i++) {
1782 narray[i] = 0;
1783 rarray[i] = 0;
1784 garray[i] = 0;
1785 barray[i] = 0;
1786 }
1787
1788 /* Take the rest of the occupied octcubes, assigning the pixels
1789 * to these new colormap indices. iarray[] is addressed
1790 * by @level octcube indices, and it now holds the
1791 * colormap indices for all pixels in pixs. */
1792 for (i = 192; i < size; i++) {
1793 opop = (L_OCTCUBE_POP*)lheapRemove(lh);
1794 if (!opop) break;
1795 rval = opop->rval;
1796 gval = opop->gval;
1797 bval = opop->bval;
1798 octindex2 = rtab2[rval] | gtab2[gval] | btab2[bval];
1799 narray[octindex2] += (l_int32)opop->npix;
1800 rarray[octindex2] += (l_int32)opop->npix * rval;
1801 garray[octindex2] += (l_int32)opop->npix * gval;
1802 barray[octindex2] += (l_int32)opop->npix * bval;
1803 iarray[opop->index] = 192 + octindex2 + 1; /* +1 to avoid storing 0 */
1804 FREE(opop);
1805 }
1806 lheapDestroy(&lh, TRUE);
1807
1808 /* To span the full color space, which is necessary for dithering,
1809 * set each iarray element whose value is still 0 at the input
1810 * level octcube leaves (because there were no pixels in those
1811 * octcubes) to the colormap index corresponding to its level 2
1812 * octcube. */
1813 if (ditherflag) {
1814 for (i = 0; i < size; i++) {
1815 if (iarray[i] == 0) {
1816 getRGBFromOctcube(i, level, &rval, &gval, &bval);
1817 octindex2 = rtab2[rval] | gtab2[gval] | btab2[bval];
1818 iarray[i] = 192 + octindex2 + 1;
1819 }
1820 }
1821 }
1822 FREE(rtab2);
1823 FREE(gtab2);
1824 FREE(btab2);
1825
1826 /* Average the colors from the residuals in each level 2 octcube,
1827 * and add these 64 values to the colormap. */
1828 for (i = 0; i < 64; i++) {
1829 if (narray[i] > 0) {
1830 rarray[i] /= narray[i];
1831 garray[i] /= narray[i];
1832 barray[i] /= narray[i];
1833 }
1834 else /* no pixels in this octcube; use center value */
1835 getRGBFromOctcube(i, 2, &rarray[i], &garray[i], &barray[i]);
1836 pixcmapAddColor(cmap, rarray[i], garray[i], barray[i]);
1837 }
1838
1839 /* Set the cmap indices for each pixel. Subtract 1 from
1840 * the value in iarray[] because we added 1 earlier. */
1841 if (ditherflag == 0) {
1842 for (i = 0; i < h; i++) {
1843 lines = datas + i * wpls;
1844 lined = datad + i * wpld;
1845 for (j = 0; j < w; j++) {
1846 extractRGBValues(lines[j], &rval, &gval, &bval);
1847 octindex = rtab[rval] | gtab[gval] | btab[bval];
1848 SET_DATA_BYTE(lined, j, iarray[octindex] - 1);
1849 }
1850 }
1851 }
1852 else /* dither */
1853 pixDitherOctindexWithCmap(pixs, pixd, rtab, gtab, btab,
1854 iarray, POP_DIF_CAP);
1855
1856 #if DEBUG_POP
1857 for (i = 0; i < size / 16; i++) {
1858 l_int32 j;
1859 for (j = 0; j < 16; j++)
1860 fprintf(stderr, "%d ", iarray[16 * i + j]);
1861 fprintf(stderr, "\n");
1862 }
1863 #endif /* DEBUG_POP */
1864
1865 FREE(iarray);
1866
1867 array_cleanup:
1868 FREE(narray);
1869 FREE(rarray);
1870 FREE(garray);
1871 FREE(barray);
1872 FREE(rtab);
1873 FREE(gtab);
1874 FREE(btab);
1875
1876 return pixd;
1877 }
1878
1879
1880 /*!
1881 * pixDitherOctindexWithCmap()
1882 *
1883 * Input: pixs (32 bpp rgb)
1884 * pixd (8 bpp cmapped)
1885 * rtab, gtab, btab (tables from rval to octindex)
1886 * indexmap (array mapping octindex to cmap index)
1887 * difcap (max allowed dither transfer; use 0 for infinite cap)
1888 * Return: 0 if OK, 1 on error
1889 *
1890 * Notes:
1891 * (1) This performs dithering to generate the colormap indices
1892 * in pixd. The colormap has been calculated, along with
1893 * four input LUTs that together give the inverse colormapping
1894 * from RGB to colormap index.
1895 * (2) For pixOctreeQuantByPopulation(), @indexmap maps from the
1896 * standard octindex to colormap index (after subtracting 1).
1897 * The basic pixel-level function, without dithering, is:
1898 * extractRGBValues(lines[j], &rval, &gval, &bval);
1899 * octindex = rtab[rval] | gtab[gval] | btab[bval];
1900 * SET_DATA_BYTE(lined, j, indexmap[octindex] - 1);
1901 * (3) This can be used in any situation where the general
1902 * prescription for finding the colormap index from the rgb
1903 * value is precisely this:
1904 * cmapindex = indexmap[rtab[rval] | gtab[gval] | btab[bval]] - 1
1905 * For example, in pixFixedOctcubeQuant256(), we don't use
1906 * standard octcube indexing, the rtab (etc) LUTs map directly
1907 * to the colormap index, and @indexmap just compensates for
1908 * the 1-off indexing assumed to be in that table.
1909 */
1910 static l_int32
pixDitherOctindexWithCmap(PIX * pixs,PIX * pixd,l_uint32 * rtab,l_uint32 * gtab,l_uint32 * btab,l_int32 * indexmap,l_int32 difcap)1911 pixDitherOctindexWithCmap(PIX *pixs,
1912 PIX *pixd,
1913 l_uint32 *rtab,
1914 l_uint32 *gtab,
1915 l_uint32 *btab,
1916 l_int32 *indexmap,
1917 l_int32 difcap)
1918 {
1919 l_uint8 *bufu8r, *bufu8g, *bufu8b;
1920 l_int32 i, j, w, h, wpld, octindex, cmapindex;
1921 l_int32 rval, gval, bval, rc, gc, bc;
1922 l_int32 dif, val1, val2, val3;
1923 l_int32 *buf1r, *buf1g, *buf1b, *buf2r, *buf2g, *buf2b;
1924 l_uint32 *datad, *lined;
1925 PIXCMAP *cmap;
1926
1927 PROCNAME("pixDitherOctindexWithCmap");
1928
1929 if (!pixs || pixGetDepth(pixs) != 32)
1930 return ERROR_INT("pixs undefined or not 32 bpp", procName, 1);
1931 if (!pixd || pixGetDepth(pixd) != 8)
1932 return ERROR_INT("pixd undefined or not 8 bpp", procName, 1);
1933 if ((cmap = pixGetColormap(pixd)) == NULL)
1934 return ERROR_INT("pixd not cmapped", procName, 1);
1935 if (!rtab || !gtab || !btab || !indexmap)
1936 return ERROR_INT("not all 4 tables defined", procName, 1);
1937 pixGetDimensions(pixs, &w, &h, NULL);
1938 if (pixGetWidth(pixd) != w || pixGetHeight(pixd) != h)
1939 return ERROR_INT("pixs and pixd not same size", procName, 1);
1940
1941 bufu8r = (l_uint8 *)CALLOC(w, sizeof(l_uint8));
1942 bufu8g = (l_uint8 *)CALLOC(w, sizeof(l_uint8));
1943 bufu8b = (l_uint8 *)CALLOC(w, sizeof(l_uint8));
1944 buf1r = (l_int32 *)CALLOC(w, sizeof(l_int32));
1945 buf1g = (l_int32 *)CALLOC(w, sizeof(l_int32));
1946 buf1b = (l_int32 *)CALLOC(w, sizeof(l_int32));
1947 buf2r = (l_int32 *)CALLOC(w, sizeof(l_int32));
1948 buf2g = (l_int32 *)CALLOC(w, sizeof(l_int32));
1949 buf2b = (l_int32 *)CALLOC(w, sizeof(l_int32));
1950 if (!bufu8r || !bufu8g || !bufu8b)
1951 return ERROR_INT("uint8 line buf not made", procName, 1);
1952 if (!buf1r || !buf1g || !buf1b || !buf2r || !buf2g || !buf2b)
1953 return ERROR_INT("mono line buf not made", procName, 1);
1954
1955 /* Start by priming buf2; line 1 is above line 2 */
1956 pixGetRGBLine(pixs, 0, bufu8r, bufu8g, bufu8b);
1957 for (j = 0; j < w; j++) {
1958 buf2r[j] = 64 * bufu8r[j];
1959 buf2g[j] = 64 * bufu8g[j];
1960 buf2b[j] = 64 * bufu8b[j];
1961 }
1962
1963 datad = pixGetData(pixd);
1964 wpld = pixGetWpl(pixd);
1965 for (i = 0; i < h - 1; i++) {
1966 /* Swap data 2 --> 1, and read in new line 2 */
1967 memcpy(buf1r, buf2r, 4 * w);
1968 memcpy(buf1g, buf2g, 4 * w);
1969 memcpy(buf1b, buf2b, 4 * w);
1970 pixGetRGBLine(pixs, i + 1, bufu8r, bufu8g, bufu8b);
1971 for (j = 0; j < w; j++) {
1972 buf2r[j] = 64 * bufu8r[j];
1973 buf2g[j] = 64 * bufu8g[j];
1974 buf2b[j] = 64 * bufu8b[j];
1975 }
1976
1977 /* Dither */
1978 lined = datad + i * wpld;
1979 for (j = 0; j < w - 1; j++) {
1980 rval = buf1r[j] / 64;
1981 gval = buf1g[j] / 64;
1982 bval = buf1b[j] / 64;
1983 octindex = rtab[rval] | gtab[gval] | btab[bval];
1984 cmapindex = indexmap[octindex] - 1;
1985 SET_DATA_BYTE(lined, j, cmapindex);
1986 pixcmapGetColor(cmap, cmapindex, &rc, &gc, &bc);
1987
1988 dif = buf1r[j] / 8 - 8 * rc;
1989 if (difcap > 0) {
1990 if (dif > difcap) dif = difcap;
1991 if (dif < -difcap) dif = -difcap;
1992 }
1993 if (dif != 0) {
1994 val1 = buf1r[j + 1] + 3 * dif;
1995 val2 = buf2r[j] + 3 * dif;
1996 val3 = buf2r[j + 1] + 2 * dif;
1997 if (dif > 0) {
1998 buf1r[j + 1] = L_MIN(16383, val1);
1999 buf2r[j] = L_MIN(16383, val2);
2000 buf2r[j + 1] = L_MIN(16383, val3);
2001 }
2002 else if (dif < 0) {
2003 buf1r[j + 1] = L_MAX(0, val1);
2004 buf2r[j] = L_MAX(0, val2);
2005 buf2r[j + 1] = L_MAX(0, val3);
2006 }
2007 }
2008
2009 dif = buf1g[j] / 8 - 8 * gc;
2010 if (difcap > 0) {
2011 if (dif > difcap) dif = difcap;
2012 if (dif < -difcap) dif = -difcap;
2013 }
2014 if (dif != 0) {
2015 val1 = buf1g[j + 1] + 3 * dif;
2016 val2 = buf2g[j] + 3 * dif;
2017 val3 = buf2g[j + 1] + 2 * dif;
2018 if (dif > 0) {
2019 buf1g[j + 1] = L_MIN(16383, val1);
2020 buf2g[j] = L_MIN(16383, val2);
2021 buf2g[j + 1] = L_MIN(16383, val3);
2022 }
2023 else if (dif < 0) {
2024 buf1g[j + 1] = L_MAX(0, val1);
2025 buf2g[j] = L_MAX(0, val2);
2026 buf2g[j + 1] = L_MAX(0, val3);
2027 }
2028 }
2029
2030 dif = buf1b[j] / 8 - 8 * bc;
2031 if (difcap > 0) {
2032 if (dif > difcap) dif = difcap;
2033 if (dif < -difcap) dif = -difcap;
2034 }
2035 if (dif != 0) {
2036 val1 = buf1b[j + 1] + 3 * dif;
2037 val2 = buf2b[j] + 3 * dif;
2038 val3 = buf2b[j + 1] + 2 * dif;
2039 if (dif > 0) {
2040 buf1b[j + 1] = L_MIN(16383, val1);
2041 buf2b[j] = L_MIN(16383, val2);
2042 buf2b[j + 1] = L_MIN(16383, val3);
2043 }
2044 else if (dif < 0) {
2045 buf1b[j + 1] = L_MAX(0, val1);
2046 buf2b[j] = L_MAX(0, val2);
2047 buf2b[j + 1] = L_MAX(0, val3);
2048 }
2049 }
2050 }
2051
2052 /* Get last pixel in row; no downward propagation */
2053 rval = buf1r[w - 1] / 64;
2054 gval = buf1g[w - 1] / 64;
2055 bval = buf1b[w - 1] / 64;
2056 octindex = rtab[rval] | gtab[gval] | btab[bval];
2057 cmapindex = indexmap[octindex] - 1;
2058 SET_DATA_BYTE(lined, w - 1, cmapindex);
2059 }
2060
2061 /* Get last row of pixels; no leftward propagation */
2062 lined = datad + (h - 1) * wpld;
2063 for (j = 0; j < w; j++) {
2064 rval = buf2r[j] / 64;
2065 gval = buf2g[j] / 64;
2066 bval = buf2b[j] / 64;
2067 octindex = rtab[rval] | gtab[gval] | btab[bval];
2068 cmapindex = indexmap[octindex] - 1;
2069 SET_DATA_BYTE(lined, j, cmapindex);
2070 }
2071
2072 FREE(bufu8r);
2073 FREE(bufu8g);
2074 FREE(bufu8b);
2075 FREE(buf1r);
2076 FREE(buf1g);
2077 FREE(buf1b);
2078 FREE(buf2r);
2079 FREE(buf2g);
2080 FREE(buf2b);
2081
2082 return 0;
2083 }
2084
2085
2086 /*---------------------------------------------------------------------------*
2087 * Adaptive octree quantization to 4 and 8 bpp with max colors *
2088 *---------------------------------------------------------------------------*/
2089 /*!
2090 * pixOctreeQuantNumColors()
2091 *
2092 * Input: pixs (32 bpp rgb)
2093 * maxcolors (8 to 256; the actual number of colors used
2094 * may be less than this)
2095 * subsample (factor for computing color distribution;
2096 * use 0 for default)
2097 * Return: pixd (4 or 8 bpp, colormapped), or null on error
2098 *
2099 * pixOctreeColorQuant() is very flexible in terms of the relative
2100 * depth of different cubes of the octree. By contrast, this function,
2101 * pixOctreeQuantNumColors() is also adaptive, but it supports octcube
2102 * leaves at only two depths: a smaller depth that guarantees
2103 * full coverage of the color space and octcubes at one level
2104 * deeper for more accurate colors. Its main virutes are simplicity
2105 * and speed, which are both derived from the natural indexing of
2106 * the octcubes from the RGB values.
2107 *
2108 * Before describing pixOctreeQuantNumColors(), consider an even simpler
2109 * approach for 4 bpp with either 8 or 16 colors. With 8 colors,
2110 * you simply go to level 1 octcubes and use the average color
2111 * found in each cube. For 16 colors, you find which of the three
2112 * colors has the largest variance at the second level, and use two
2113 * indices for that color. The result is quite poor, because (1) some
2114 * of the cubes are nearly empty and (2) you don't get much color
2115 * differentiation for the extra 8 colors. Trust me, this method may
2116 * be simple, but it isn't worth anything.
2117 *
2118 * In pixOctreeQuantNumColors(), we generate colormapped images at
2119 * either 4 bpp or 8 bpp. For 4 bpp, we have a minimum of 8 colors
2120 * for the level 1 octcubes, plus up to 8 additional colors that
2121 * are determined from the level 2 popularity. If the number of colors
2122 * is between 8 and 16, the output is a 4 bpp image. If the number of
2123 * colors is greater than 16, the output is a 8 bpp image.
2124 *
2125 * We use a priority queue, implemented with a heap, to select the
2126 * requisite number of most populated octcubes at the deepest level
2127 * (level 2 for 64 or fewer colors; level 3 for more than 64 colors).
2128 * These are combined with one color for each octcube one level above,
2129 * which is used to span the color space of octcubes that were not
2130 * included at the deeper level.
2131 *
2132 * If the deepest level is 2, we combine the popular level 2 octcubes
2133 * (out of a total of 64) with the 8 level 1 octcubes. If the deepest
2134 * level is 3, we combine the popular level 3 octcubes (out of a
2135 * total 512) with the 64 level 2 octcubes that span the color space.
2136 * In the latter case, we require a minimum of 64 colors for the level 2
2137 * octcubes, plus up to 192 additional colors determined from level 3
2138 * popularity.
2139 *
2140 * The parameter 'maxlevel' is the deepest octcube level that is used.
2141 * The implementation also uses two LUTs, which are employed in
2142 * two successive traversals of the dest image. The first maps
2143 * from the src octindex at 'maxlevel' to the color table index,
2144 * which is the value that is stored in the 4 or 8 bpp dest pixel.
2145 * The second LUT maps from that colormap value in the dest to a
2146 * new colormap value for a minimum sized colormap, stored back in
2147 * the dest. It is used to remove any color map entries that
2148 * correspond to color space regions that have no pixels in the
2149 * source image. These regions can be either from the higher level
2150 * (e.g., level 1 for 4 bpp), or from octcubes at 'maxlevel' that
2151 * are unoccupied. This remapping results in the minimum number
2152 * of colors used according to the constraints induced by the
2153 * input 'maxcolors'. We also compute the average R, G and B color
2154 * values in each region of the color space represented by a
2155 * colormap entry, and store them in the colormap.
2156 *
2157 * The maximum number of colors is input, which determines the
2158 * following properties of the dest image and octcube regions used:
2159 *
2160 * Number of colors dest image depth maxlevel
2161 * ---------------- ---------------- --------
2162 * 8 to 16 4 bpp 2
2163 * 17 to 64 8 bpp 2
2164 * 65 to 256 8 bpp 3
2165 *
2166 * It may turn out that the number of extra colors, beyond the
2167 * minimum (8 and 64 for maxlevel 2 and 3, respectively), is larger
2168 * than the actual number of occupied cubes at these levels
2169 * In that case, all the pixels are contained in this
2170 * subset of cubes at maxlevel, and no colormap colors are needed
2171 * to represent the remainder pixels one level above. Thus, for
2172 * example, in use one often finds that the pixels in an image
2173 * occupy less than 192 octcubes at level 3, so they can be represented
2174 * by a colormap for octcubes at level 3 only.
2175 */
2176 PIX *
pixOctreeQuantNumColors(PIX * pixs,l_int32 maxcolors,l_int32 subsample)2177 pixOctreeQuantNumColors(PIX *pixs,
2178 l_int32 maxcolors,
2179 l_int32 subsample)
2180 {
2181 l_int32 w, h, minside, bpp, wpls, wpld, i, j, actualcolors;
2182 l_int32 rval, gval, bval, nbase, nextra, maxlevel, ncubes, val;
2183 l_int32 *lut1, *lut2;
2184 l_uint32 index;
2185 l_uint32 *lines, *lined, *datas, *datad, *pspixel;
2186 l_uint32 *rtab, *gtab, *btab;
2187 OQCELL *oqc;
2188 OQCELL **oqca;
2189 L_HEAP *lh;
2190 PIX *pixd;
2191 PIXCMAP *cmap;
2192
2193 PROCNAME("pixOctreeQuantNumColors");
2194
2195 if (!pixs)
2196 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
2197 if (pixGetDepth(pixs) != 32)
2198 return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
2199
2200 pixGetDimensions(pixs, &w, &h, NULL);
2201 datas = pixGetData(pixs);
2202 wpls = pixGetWpl(pixs);
2203 minside = L_MIN(w, h);
2204 if (subsample <= 0) {
2205 subsample = L_MAX(1, minside / 200);
2206 }
2207
2208 if (maxcolors >= 8 && maxcolors <= 16) {
2209 bpp = 4;
2210 pixd = pixCreate(w, h, bpp);
2211 maxlevel = 2;
2212 ncubes = 64; /* 2^6 */
2213 nbase = 8;
2214 nextra = maxcolors - nbase;
2215 }
2216 else if (maxcolors < 64) {
2217 bpp = 8;
2218 pixd = pixCreate(w, h, bpp);
2219 maxlevel = 2;
2220 ncubes = 64; /* 2^6 */
2221 nbase = 8;
2222 nextra = maxcolors - nbase;
2223 }
2224 else if (maxcolors >= 64 && maxcolors <= 256) {
2225 bpp = 8;
2226 pixd = pixCreate(w, h, bpp);
2227 maxlevel = 3;
2228 ncubes = 512; /* 2^9 */
2229 nbase = 64;
2230 nextra = maxcolors - nbase;
2231 }
2232 else
2233 return (PIX *)ERROR_PTR("maxcolors not in {8...256}", procName, NULL);
2234
2235 pixCopyResolution(pixd, pixs);
2236 pixCopyInputFormat(pixd, pixs);
2237
2238 /*----------------------------------------------------------*
2239 * If we're using the minimum number of colors, it is *
2240 * much simpler. We just use 'nbase' octcubes. *
2241 * For this case, we don't eliminate any extra colors. *
2242 *----------------------------------------------------------*/
2243 if (nextra == 0) {
2244 /* prepare the OctcubeQuantCell array */
2245 if ((oqca = (OQCELL **)CALLOC(nbase, sizeof(OQCELL *))) == NULL)
2246 return (PIX *)ERROR_PTR("oqca not made", procName, NULL);
2247 for (i = 0; i < nbase; i++) {
2248 oqca[i] = (OQCELL *)CALLOC(1, sizeof(OQCELL));
2249 oqca[i]->n = 0.0;
2250 }
2251
2252 makeRGBToIndexTables(&rtab, >ab, &btab, maxlevel - 1);
2253
2254 /* Go through the entire image, gathering statistics and
2255 * assigning pixels to their quantized value */
2256 datad = pixGetData(pixd);
2257 wpld = pixGetWpl(pixd);
2258 for (i = 0; i < h; i++) {
2259 lines = datas + i * wpls;
2260 lined = datad + i * wpld;
2261 for (j = 0; j < w; j++) {
2262 pspixel = lines + j;
2263 extractRGBValues(*pspixel, &rval, &gval, &bval);
2264 getOctcubeIndexFromRGB(rval, gval, bval,
2265 rtab, gtab, btab, &index);
2266 /* fprintf(stderr, "rval = %d, gval = %d, bval = %d, index = %d\n",
2267 rval, gval, bval, index); */
2268 switch (bpp) {
2269 case 4:
2270 SET_DATA_QBIT(lined, j, index);
2271 break;
2272 case 8:
2273 SET_DATA_BYTE(lined, j, index);
2274 break;
2275 default:
2276 return (PIX *)ERROR_PTR("bpp not 4 or 8!", procName, NULL);
2277 break;
2278 }
2279 oqca[index]->n += 1.0;
2280 oqca[index]->rcum += rval;
2281 oqca[index]->gcum += gval;
2282 oqca[index]->bcum += bval;
2283 }
2284 }
2285
2286 /* Compute average color values in each octcube, and
2287 * generate colormap */
2288 cmap = pixcmapCreate(bpp);
2289 pixSetColormap(pixd, cmap);
2290 for (i = 0; i < nbase; i++) {
2291 oqc = oqca[i];
2292 if (oqc->n != 0) {
2293 oqc->rval = (l_int32)(oqc->rcum / oqc->n);
2294 oqc->gval = (l_int32)(oqc->gcum / oqc->n);
2295 oqc->bval = (l_int32)(oqc->bcum / oqc->n);
2296 }
2297 else
2298 getRGBFromOctcube(i, maxlevel - 1, &oqc->rval,
2299 &oqc->gval, &oqc->bval);
2300 pixcmapAddColor(cmap, oqc->rval, oqc->gval, oqc->bval);
2301 }
2302 /* pixcmapWriteStream(stderr, cmap); */
2303
2304 for (i = 0; i < nbase; i++)
2305 FREE(oqca[i]);
2306 FREE(oqca);
2307 FREE(rtab);
2308 FREE(gtab);
2309 FREE(btab);
2310 return pixd;
2311 }
2312
2313 /*------------------------------------------------------------*
2314 * General case: we will use colors in octcubes at maxlevel. *
2315 * We also remove any colors that are not populated from *
2316 * the colormap. *
2317 *------------------------------------------------------------*/
2318 /* Prepare the OctcubeQuantCell array */
2319 if ((oqca = (OQCELL **)CALLOC(ncubes, sizeof(OQCELL *))) == NULL)
2320 return (PIX *)ERROR_PTR("oqca not made", procName, NULL);
2321 for (i = 0; i < ncubes; i++) {
2322 oqca[i] = (OQCELL *)CALLOC(1, sizeof(OQCELL));
2323 oqca[i]->n = 0.0;
2324 }
2325
2326 /* Make the tables to map color to the octindex,
2327 * of which there are 'ncubes' at 'maxlevel' */
2328 makeRGBToIndexTables(&rtab, >ab, &btab, maxlevel);
2329
2330 /* Estimate the color distribution; we want to find the
2331 * most popular nextra colors at 'maxlevel' */
2332 for (i = 0; i < h; i += subsample) {
2333 lines = datas + i * wpls;
2334 for (j = 0; j < w; j += subsample) {
2335 pspixel = lines + j;
2336 extractRGBValues(*pspixel, &rval, &gval, &bval);
2337 getOctcubeIndexFromRGB(rval, gval, bval, rtab, gtab, btab, &index);
2338 oqca[index]->n += 1.0;
2339 oqca[index]->octindex = index;
2340 oqca[index]->rcum += rval;
2341 oqca[index]->gcum += gval;
2342 oqca[index]->bcum += bval;
2343 }
2344 }
2345
2346 /* Transfer the OQCELL from the array, and order in a heap */
2347 lh = lheapCreate(512, L_SORT_DECREASING);
2348 for (i = 0; i < ncubes; i++)
2349 lheapAdd(lh, oqca[i]);
2350 FREE(oqca); /* don't need this array */
2351
2352 /* Prepare a new OctcubeQuantCell array, with maxcolors cells */
2353 if ((oqca = (OQCELL **)CALLOC(maxcolors, sizeof(OQCELL *))) == NULL)
2354 return (PIX *)ERROR_PTR("oqca not made", procName, NULL);
2355 for (i = 0; i < nbase; i++) { /* make nbase cells */
2356 oqca[i] = (OQCELL *)CALLOC(1, sizeof(OQCELL));
2357 oqca[i]->n = 0.0;
2358 }
2359
2360 /* Remove the nextra most populated ones, and put them in the array */
2361 for (i = 0; i < nextra; i++) {
2362 oqc = (OQCELL *)lheapRemove(lh);
2363 oqc->n = 0.0; /* reinit */
2364 oqc->rcum = 0;
2365 oqc->gcum = 0;
2366 oqc->bcum = 0;
2367 oqca[nbase + i] = oqc; /* store it in the array */
2368 }
2369
2370 /* Destroy the heap and its remaining contents */
2371 lheapDestroy(&lh, TRUE);
2372
2373 /* Generate a lookup table from octindex at maxlevel
2374 * to color table index */
2375 if ((lut1 = (l_int32 *)CALLOC(ncubes, sizeof(l_int32))) == NULL)
2376 return (PIX *)ERROR_PTR("lut1 not made", procName, NULL);
2377 for (i = 0; i < nextra; i++)
2378 lut1[oqca[nbase + i]->octindex] = nbase + i;
2379 for (index = 0; index < ncubes; index++) {
2380 if (lut1[index] == 0) /* not one of the extras; need to assign */
2381 lut1[index] = index >> 3; /* remove the least significant bits */
2382 /* fprintf(stderr, "lut1[%d] = %d\n", index, lut1[index]); */
2383 }
2384
2385 /* Go through the entire image, gathering statistics and
2386 * assigning pixels to their quantized value */
2387 datad = pixGetData(pixd);
2388 wpld = pixGetWpl(pixd);
2389 for (i = 0; i < h; i++) {
2390 lines = datas + i * wpls;
2391 lined = datad + i * wpld;
2392 for (j = 0; j < w; j++) {
2393 pspixel = lines + j;
2394 extractRGBValues(*pspixel, &rval, &gval, &bval);
2395 getOctcubeIndexFromRGB(rval, gval, bval, rtab, gtab, btab, &index);
2396 /* fprintf(stderr, "rval = %d, gval = %d, bval = %d, index = %d\n",
2397 rval, gval, bval, index); */
2398 val = lut1[index];
2399 switch (bpp) {
2400 case 4:
2401 SET_DATA_QBIT(lined, j, val);
2402 break;
2403 case 8:
2404 SET_DATA_BYTE(lined, j, val);
2405 break;
2406 default:
2407 return (PIX *)ERROR_PTR("bpp not 4 or 8!", procName, NULL);
2408 break;
2409 }
2410 oqca[val]->n += 1.0;
2411 oqca[val]->rcum += rval;
2412 oqca[val]->gcum += gval;
2413 oqca[val]->bcum += bval;
2414 }
2415 }
2416
2417 /* Compute averages, set up a colormap, and make a second
2418 * lut that converts from the color values currently in
2419 * the image to a minimal set */
2420 if ((lut2 = (l_int32 *)CALLOC(ncubes, sizeof(l_int32))) == NULL)
2421 return (PIX *)ERROR_PTR("lut2 not made", procName, NULL);
2422 cmap = pixcmapCreate(bpp);
2423 pixSetColormap(pixd, cmap);
2424 for (i = 0, index = 0; i < maxcolors; i++) {
2425 oqc = oqca[i];
2426 lut2[i] = index;
2427 if (oqc->n == 0) /* no occupancy; don't bump up index */
2428 continue;
2429 oqc->rval = (l_int32)(oqc->rcum / oqc->n);
2430 oqc->gval = (l_int32)(oqc->gcum / oqc->n);
2431 oqc->bval = (l_int32)(oqc->bcum / oqc->n);
2432 pixcmapAddColor(cmap, oqc->rval, oqc->gval, oqc->bval);
2433 index++;
2434 }
2435 /* pixcmapWriteStream(stderr, cmap); */
2436 actualcolors = pixcmapGetCount(cmap);
2437 /* fprintf(stderr, "Number of different colors = %d\n", actualcolors); */
2438
2439 /* Last time through the image; use the lookup table to
2440 * remap the pixel value to the minimal colormap */
2441 if (actualcolors < maxcolors) {
2442 for (i = 0; i < h; i++) {
2443 lined = datad + i * wpld;
2444 for (j = 0; j < w; j++) {
2445 switch (bpp) {
2446 case 4:
2447 val = GET_DATA_QBIT(lined, j);
2448 SET_DATA_QBIT(lined, j, lut2[val]);
2449 break;
2450 case 8:
2451 val = GET_DATA_BYTE(lined, j);
2452 SET_DATA_BYTE(lined, j, lut2[val]);
2453 break;
2454 }
2455 }
2456 }
2457 }
2458
2459 for (i = 0; i < maxcolors; i++)
2460 FREE(oqca[i]);
2461 FREE(oqca);
2462 FREE(lut1);
2463 FREE(lut2);
2464 FREE(rtab);
2465 FREE(gtab);
2466 FREE(btab);
2467 return pixd;
2468 }
2469
2470
2471 /*-------------------------------------------------------------------------*
2472 * Mixed color/gray quantization with specified number of colors *
2473 *-------------------------------------------------------------------------*/
2474 /*!
2475 * pixOctcubeQuantMixedWithGray()
2476 *
2477 * Input: pixs (32 bpp rgb)
2478 * depth (of output pix)
2479 * graylevels (grayscale)
2480 * delta (threshold for deciding if a pix is color or grayscale)
2481 * Return: pixd (quantized to octcube and gray levels) or null on error
2482 *
2483 * Notes:
2484 * (1) Generates a colormapped image, where the colormap table values
2485 * have two components: octcube values representing pixels with
2486 * color content, and grayscale values for the rest.
2487 * (2) The threshold (delta) is the maximum allowable difference of
2488 * the max abs value of | r - g |, | r - b | and | g - b |.
2489 * (3) The octcube values are the averages of all pixels that are
2490 * found in the octcube, and that are far enough from gray to
2491 * be considered color. This can roughly be visualized as all
2492 * the points in the rgb color cube that are not within a "cylinder"
2493 * of diameter approximately 'delta' along the main diagonal.
2494 * (4) We want to guarantee full coverage of the rgb color space; thus,
2495 * if the output depth is 4, the octlevel is 1 (2 x 2 x 2 = 8 cubes)
2496 * and if the output depth is 8, the octlevel is 2 (4 x 4 x 4
2497 * = 64 cubes).
2498 * (5) Consequently, we have the following constraint on the number
2499 * of allowed gray levels: for 4 bpp, 8; for 8 bpp, 192.
2500 */
2501 PIX *
pixOctcubeQuantMixedWithGray(PIX * pixs,l_int32 depth,l_int32 graylevels,l_int32 delta)2502 pixOctcubeQuantMixedWithGray(PIX *pixs,
2503 l_int32 depth,
2504 l_int32 graylevels,
2505 l_int32 delta)
2506 {
2507 l_int32 w, h, wpls, wpld, i, j, size, octlevels;
2508 l_int32 rval, gval, bval, del, val, midval;
2509 l_int32 *carray, *rarray, *garray, *barray;
2510 l_int32 *tabval;
2511 l_uint32 octindex;
2512 l_uint32 *rtab, *gtab, *btab;
2513 l_uint32 *lines, *lined, *datas, *datad;
2514 PIX *pixd;
2515 PIXCMAP *cmap;
2516
2517 PROCNAME("pixOctcubeQuantMixedWithGray");
2518
2519 if (!pixs)
2520 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
2521 if (pixGetDepth(pixs) != 32)
2522 return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
2523 if (depth == 4) {
2524 octlevels = 1;
2525 size = 8; /* 2 ** 3 */
2526 if (graylevels > 8)
2527 return (PIX *)ERROR_PTR("max 8 gray levels", procName, NULL);
2528 }
2529 else if (depth == 8) {
2530 octlevels = 2;
2531 size = 64; /* 2 ** 6 */
2532 if (graylevels > 192)
2533 return (PIX *)ERROR_PTR("max 192 gray levels", procName, NULL);
2534 }
2535 else
2536 return (PIX *)ERROR_PTR("output depth not 4 or 8 bpp", procName, NULL);
2537
2538 /* Make octcube index tables */
2539 if (makeRGBToIndexTables(&rtab, >ab, &btab, octlevels))
2540 return (PIX *)ERROR_PTR("tables not made", procName, NULL);
2541
2542 /* Make octcube arrays for storing points in each cube */
2543 if ((carray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
2544 return (PIX *)ERROR_PTR("carray not made", procName, NULL);
2545 if ((rarray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
2546 return (PIX *)ERROR_PTR("rarray not made", procName, NULL);
2547 if ((garray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
2548 return (PIX *)ERROR_PTR("garray not made", procName, NULL);
2549 if ((barray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
2550 return (PIX *)ERROR_PTR("barray not made", procName, NULL);
2551
2552 /* Make lookup table, using computed thresholds */
2553 if ((tabval = makeGrayQuantIndexTable(graylevels)) == NULL)
2554 return (PIX *)ERROR_PTR("tabval not made", procName, NULL);
2555
2556 /* Make colormapped output pixd */
2557 pixGetDimensions(pixs, &w, &h, NULL);
2558 if ((pixd = pixCreate(w, h, depth)) == NULL)
2559 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
2560 pixCopyResolution(pixd, pixs);
2561 pixCopyInputFormat(pixd, pixs);
2562 cmap = pixcmapCreate(depth);
2563 for (j = 0; j < size; j++) /* reserve octcube colors */
2564 pixcmapAddColor(cmap, 1, 1, 1); /* a color that won't be used */
2565 for (j = 0; j < graylevels; j++) { /* set grayscale colors */
2566 val = (255 * j) / (graylevels - 1);
2567 pixcmapAddColor(cmap, val, val, val);
2568 }
2569 pixSetColormap(pixd, cmap);
2570 wpld = pixGetWpl(pixd);
2571 datad = pixGetData(pixd);
2572
2573 /* Go through src image: assign dest pixels to colormap values
2574 * and compute average colors in each occupied octcube */
2575 datas = pixGetData(pixs);
2576 wpls = pixGetWpl(pixs);
2577 for (i = 0; i < h; i++) {
2578 lines = datas + i * wpls;
2579 lined = datad + i * wpld;
2580 for (j = 0; j < w; j++) {
2581 extractRGBValues(lines[j], &rval, &gval, &bval);
2582 if (rval > gval) {
2583 if (gval > bval) { /* r > g > b */
2584 del = rval - bval;
2585 midval = gval;
2586 }
2587 else {
2588 if (rval > bval) { /* r > b > g */
2589 del = rval - gval;
2590 midval = bval;
2591 }
2592 else { /* b > r > g */
2593 del = bval - gval;
2594 midval = rval;
2595 }
2596 }
2597 }
2598 else { /* gval >= rval */
2599 if (rval > bval) { /* g > r > b */
2600 del = gval - bval;
2601 midval = rval;
2602 }
2603 else {
2604 if (gval > bval) { /* g > b > r */
2605 del = gval - rval;
2606 midval = bval;
2607 }
2608 else { /* b > g > r */
2609 del = bval - rval;
2610 midval = gval;
2611 }
2612 }
2613 }
2614 if (del > delta) { /* assign to color */
2615 octindex = rtab[rval] | gtab[gval] | btab[bval];
2616 carray[octindex]++;
2617 rarray[octindex] += rval;
2618 garray[octindex] += gval;
2619 barray[octindex] += bval;
2620 if (depth == 4)
2621 SET_DATA_QBIT(lined, j, octindex);
2622 else /* depth == 8 */
2623 SET_DATA_BYTE(lined, j, octindex);
2624 }
2625 else { /* assign to grayscale */
2626 val = size + tabval[midval];
2627 if (depth == 4)
2628 SET_DATA_QBIT(lined, j, val);
2629 else /* depth == 8 */
2630 SET_DATA_BYTE(lined, j, val);
2631 }
2632 }
2633 }
2634
2635 /* Average the colors in each bin and reset the colormap */
2636 for (i = 0; i < size; i++) {
2637 if (carray[i] > 0) {
2638 rarray[i] /= carray[i];
2639 garray[i] /= carray[i];
2640 barray[i] /= carray[i];
2641 pixcmapResetColor(cmap, i, rarray[i], garray[i], barray[i]);
2642 }
2643 }
2644
2645 FREE(carray);
2646 FREE(rarray);
2647 FREE(garray);
2648 FREE(barray);
2649 FREE(rtab);
2650 FREE(gtab);
2651 FREE(btab);
2652 FREE(tabval);
2653 return pixd;
2654 }
2655
2656
2657 /*-------------------------------------------------------------------------*
2658 * Fixed partition octcube quantization with 256 cells *
2659 *-------------------------------------------------------------------------*/
2660 /*!
2661 * pixFixedOctcubeQuant256()
2662 *
2663 * Input: pixs (32 bpp; 24-bit color)
2664 * ditherflag (1 for dithering; 0 for no dithering)
2665 * Return: pixd (8 bit with colormap), or null on error
2666 *
2667 * This simple 1-pass color quantization works by breaking the
2668 * color space into 256 pieces, with 3 bits quantized for each of
2669 * red and green, and 2 bits quantized for blue. We shortchange
2670 * blue because the eye is least sensitive to blue. This
2671 * division of the color space is into two levels of octrees,
2672 * followed by a further division by 4 (not 8), where both
2673 * blue octrees have been combined in the third level.
2674 *
2675 * The color map is generated from the 256 color centers by
2676 * taking the representative color to be the center of the
2677 * cell volume. This gives a maximum error in the red and
2678 * green values of 16 levels, and a maximum error in the
2679 * blue sample of 32 levels.
2680 *
2681 * Each pixel in the 24-bit color image is placed in its containing
2682 * cell, given by the relevant MSbits of the red, green and blue
2683 * samples. An error-diffusion dithering is performed on each
2684 * color sample to give the appearance of good average local color.
2685 * Dithering is required; without it, the contouring and visible
2686 * color errors are very bad.
2687 *
2688 * I originally implemented this algorithm in two passes,
2689 * where the first pass was used to compute the weighted average
2690 * of each sample in each pre-allocated region of color space.
2691 * The idea was to use these centroids in the dithering algorithm
2692 * of the second pass, to reduce the average error that was
2693 * being dithered. However, with dithering, there is
2694 * virtually no difference, so there is no reason to make the
2695 * first pass. Consequently, this 1-pass version just assigns
2696 * the pixels to the centers of the pre-allocated cells.
2697 * We use dithering to spread the difference between the sample
2698 * value and the location of the center of the cell. For speed
2699 * and simplicity, we use integer dithering and propagate only
2700 * to the right, down, and diagonally down-right, with ratios
2701 * 3/8, 3/8 and 1/4, respectively. The results should be nearly
2702 * as good, and a bit faster, with propagation only to the right
2703 * and down.
2704 *
2705 * The algorithm is very fast, because there is no search,
2706 * only fast generation of the cell index for each pixel.
2707 * We use a simple mapping from the three 8 bit rgb samples
2708 * to the 8 bit cell index; namely, (r7 r6 r5 g7 g6 g5 b7 b6).
2709 * This is not in an octcube format, but it doesn't matter.
2710 * There are no storage requirements. We could keep a
2711 * running average of the center of each sample in each
2712 * cluster, rather than using the center of the cell, but
2713 * this is just extra work, esp. with dithering.
2714 *
2715 * This method gives surprisingly good results with dithering.
2716 * However, without dithering, the loss of color accuracy is
2717 * evident in regions that are very light or that have subtle
2718 * blending of colors.
2719 */
2720 PIX *
pixFixedOctcubeQuant256(PIX * pixs,l_int32 ditherflag)2721 pixFixedOctcubeQuant256(PIX *pixs,
2722 l_int32 ditherflag)
2723 {
2724 l_uint8 index;
2725 l_int32 rval, gval, bval;
2726 l_int32 w, h, wpls, wpld, i, j, cindex;
2727 l_uint32 *rtab, *gtab, *btab;
2728 l_int32 *itab;
2729 l_uint32 *datas, *datad, *lines, *lined;
2730 PIX *pixd;
2731 PIXCMAP *cmap;
2732
2733 PROCNAME("pixFixedOctcubeQuant256");
2734
2735 if (!pixs)
2736 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
2737 if (pixGetDepth(pixs) != 32)
2738 return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
2739
2740 /* Do not dither if image is very small */
2741 pixGetDimensions(pixs, &w, &h, NULL);
2742 if (w < MIN_DITHER_SIZE && h < MIN_DITHER_SIZE && ditherflag == 1) {
2743 L_INFO("Small image: dithering turned off", procName);
2744 ditherflag = 0;
2745 }
2746
2747 /* Find the centers of the 256 cells, each of which represents
2748 * the 3 MSBits of the red and green components, and the
2749 * 2 MSBits of the blue component. This gives a mapping
2750 * from a "cube index" to the rgb values. Save all 256
2751 * rgb values of these centers in a colormap.
2752 * For example, to get the red color of the cell center,
2753 * you take the 3 MSBits of to the index and add the
2754 * offset to the center of the cell, which is 0x10. */
2755 cmap = pixcmapCreate(8);
2756 for (cindex = 0; cindex < 256; cindex++) {
2757 rval = (cindex & 0xe0) | 0x10;
2758 gval = ((cindex << 3) & 0xe0) | 0x10;
2759 bval = ((cindex << 6) & 0xc0) | 0x20;
2760 pixcmapAddColor(cmap, rval, gval, bval);
2761 }
2762
2763 /* Make output 8 bpp palette image */
2764 datas = pixGetData(pixs);
2765 wpls = pixGetWpl(pixs);
2766 if ((pixd = pixCreate(w, h, 8)) == NULL)
2767 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
2768 pixSetColormap(pixd, cmap);
2769 pixCopyResolution(pixd, pixs);
2770 pixCopyInputFormat(pixd, pixs);
2771 datad = pixGetData(pixd);
2772 wpld = pixGetWpl(pixd);
2773
2774 /* Set dest pix values to colortable indices */
2775 if (ditherflag == 0) { /* no dithering */
2776 for (i = 0; i < h; i++) {
2777 lines = datas + i * wpls;
2778 lined = datad + i * wpld;
2779 for (j = 0; j < w; j++) {
2780 extractRGBValues(lines[j], &rval, &gval, &bval);
2781 index = (rval & 0xe0) | ((gval >> 3) & 0x1c) | (bval >> 6);
2782 SET_DATA_BYTE(lined, j, index);
2783 }
2784 }
2785 }
2786 else { /* ditherflag == 1 */
2787 /* Set up conversion tables from rgb directly to the colormap
2788 * index. However, the dithering function expects these tables
2789 * to generate an octcube index (+1), and the table itab[] to
2790 * convert to the colormap index. So we make a trivial
2791 * itab[], that simply compensates for the -1 in
2792 * pixDitherOctindexWithCmap(). No cap is required on
2793 * the propagated difference. */
2794 rtab = (l_uint32 *)CALLOC(256, sizeof(l_uint32));
2795 gtab = (l_uint32 *)CALLOC(256, sizeof(l_uint32));
2796 btab = (l_uint32 *)CALLOC(256, sizeof(l_uint32));
2797 itab = (l_int32 *)CALLOC(256, sizeof(l_int32));
2798 for (i = 0; i < 256; i++) {
2799 rtab[i] = i & 0xe0;
2800 gtab[i] = (i >> 3) & 0x1c;
2801 btab[i] = i >> 6;
2802 itab[i] = i + 1;
2803 }
2804 pixDitherOctindexWithCmap(pixs, pixd, rtab, gtab, btab, itab,
2805 FIXED_DIF_CAP);
2806 FREE(rtab);
2807 FREE(gtab);
2808 FREE(btab);
2809 FREE(itab);
2810 }
2811
2812 return pixd;
2813 }
2814
2815
2816 /*---------------------------------------------------------------------------*
2817 * Nearly exact quantization for images with few colors *
2818 *---------------------------------------------------------------------------*/
2819 /*!
2820 * pixFewColorsOctcubeQuant1()
2821 *
2822 * Input: pixs (32 bpp rgb)
2823 * level (significant bits for each of RGB; valid in [1...6])
2824 * Return: pixd (quantized to octcube) or null on error
2825 *
2826 * Notes:
2827 * (1) Generates a colormapped image, where the colormap table values
2828 * are the averages of all pixels that are found in the octcube.
2829 * (2) This fails if there are more than 256 colors (i.e., more
2830 * than 256 occupied octcubes).
2831 * (3) Often level 3 (512 octcubes) will succeed because not more
2832 * than half of them are occupied with 1 or more pixels.
2833 * (4) The depth of the result, which is either 2, 4 or 8 bpp,
2834 * is the minimum required to hold the number of colors that
2835 * are found.
2836 * (5) This can be useful for quantizing orthographically generated
2837 * images such as color maps, where there may be more than 256 colors
2838 * because of aliasing or jpeg artifacts on text or lines, but
2839 * there are a relatively small number of solid colors. Then,
2840 * use with level = 3 can often generate a compact and accurate
2841 * representation of the original RGB image. For this purpose,
2842 * it is better than pixFewColorsOctcubeQuant2(), because it
2843 * uses the average value of pixels in the octcube rather
2844 * than the first found pixel. It is also simpler to use,
2845 * because it generates the histogram internally.
2846 */
2847 PIX *
pixFewColorsOctcubeQuant1(PIX * pixs,l_int32 level)2848 pixFewColorsOctcubeQuant1(PIX *pixs,
2849 l_int32 level)
2850 {
2851 l_int32 w, h, wpls, wpld, i, j, depth, size, ncolors, index;
2852 l_int32 rval, gval, bval;
2853 l_int32 *carray, *rarray, *garray, *barray;
2854 l_uint32 octindex;
2855 l_uint32 *rtab, *gtab, *btab;
2856 l_uint32 *lines, *lined, *datas, *datad, *pspixel;
2857 PIX *pixd;
2858 PIXCMAP *cmap;
2859
2860 PROCNAME("pixFewColorsOctcubeQuant1");
2861
2862 if (!pixs)
2863 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
2864 if (pixGetDepth(pixs) != 32)
2865 return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
2866 if (level < 1 || level > 6)
2867 return (PIX *)ERROR_PTR("invalid level", procName, NULL);
2868
2869 if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
2870 return (PIX *)ERROR_PTR("size not returned", procName, NULL);
2871 if (makeRGBToIndexTables(&rtab, >ab, &btab, level))
2872 return (PIX *)ERROR_PTR("tables not made", procName, NULL);
2873
2874 if ((carray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
2875 return (PIX *)ERROR_PTR("carray not made", procName, NULL);
2876 if ((rarray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
2877 return (PIX *)ERROR_PTR("rarray not made", procName, NULL);
2878 if ((garray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
2879 return (PIX *)ERROR_PTR("garray not made", procName, NULL);
2880 if ((barray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
2881 return (PIX *)ERROR_PTR("barray not made", procName, NULL);
2882
2883 /* Place the pixels in octcube leaves. */
2884 pixGetDimensions(pixs, &w, &h, NULL);
2885 datas = pixGetData(pixs);
2886 wpls = pixGetWpl(pixs);
2887 pixd = NULL;
2888 for (i = 0; i < h; i++) {
2889 lines = datas + i * wpls;
2890 for (j = 0; j < w; j++) {
2891 pspixel = lines + j;
2892 extractRGBValues(*pspixel, &rval, &gval, &bval);
2893 octindex = rtab[rval] | gtab[gval] | btab[bval];
2894 carray[octindex]++;
2895 rarray[octindex] += rval;
2896 garray[octindex] += gval;
2897 barray[octindex] += bval;
2898 }
2899 }
2900
2901 /* Find the number of different colors */
2902 for (i = 0, ncolors = 0; i < size; i++) {
2903 if (carray[i] > 0)
2904 ncolors++;
2905 }
2906 if (ncolors > 256) {
2907 L_WARNING_INT("%d colors found; more than 256", procName, ncolors);
2908 goto array_cleanup;
2909 }
2910 if (ncolors <= 4)
2911 depth = 2;
2912 else if (ncolors <= 16)
2913 depth = 4;
2914 else
2915 depth = 8;
2916
2917 /* Average the colors in each octcube leaf and add to colormap table;
2918 * then use carray to hold the colormap index + 1 */
2919 cmap = pixcmapCreate(depth);
2920 for (i = 0, index = 0; i < size; i++) {
2921 if (carray[i] > 0) {
2922 rarray[i] /= carray[i];
2923 garray[i] /= carray[i];
2924 barray[i] /= carray[i];
2925 pixcmapAddColor(cmap, rarray[i], garray[i], barray[i]);
2926 carray[i] = index + 1; /* to avoid storing 0 */
2927 index++;
2928 }
2929 }
2930
2931 pixd = pixCreate(w, h, depth);
2932 pixSetColormap(pixd, cmap);
2933 pixCopyResolution(pixd, pixs);
2934 pixCopyInputFormat(pixd, pixs);
2935 datad = pixGetData(pixd);
2936 wpld = pixGetWpl(pixd);
2937 for (i = 0; i < h; i++) {
2938 lines = datas + i * wpls;
2939 lined = datad + i * wpld;
2940 for (j = 0; j < w; j++) {
2941 pspixel = lines + j;
2942 extractRGBValues(*pspixel, &rval, &gval, &bval);
2943 octindex = rtab[rval] | gtab[gval] | btab[bval];
2944 switch (depth)
2945 {
2946 case 2:
2947 SET_DATA_DIBIT(lined, j, carray[octindex] - 1);
2948 break;
2949 case 4:
2950 SET_DATA_QBIT(lined, j, carray[octindex] - 1);
2951 break;
2952 case 8:
2953 SET_DATA_BYTE(lined, j, carray[octindex] - 1);
2954 break;
2955 default:
2956 L_WARNING("shouldn't get here", procName);
2957 }
2958 }
2959 }
2960
2961 array_cleanup:
2962 FREE(carray);
2963 FREE(rarray);
2964 FREE(garray);
2965 FREE(barray);
2966 FREE(rtab);
2967 FREE(gtab);
2968 FREE(btab);
2969 return pixd;
2970 }
2971
2972
2973 /*!
2974 * pixFewColorsOctcubeQuant2()
2975 *
2976 * Input: pixs (32 bpp rgb)
2977 * level (of octcube indexing, for histogram: 3, 4, 5, 6)
2978 * na (histogram of pixel occupation in octree leaves at
2979 * given level)
2980 * ncolors (number of occupied octree leaves at given level)
2981 * &nerrors (<optional return> num of pixels not exactly
2982 * represented in the colormap)
2983 * Return: pixd (2, 4 or 8 bpp with colormap), or null on error
2984 *
2985 * Notes:
2986 * (1) Generates a colormapped image, where the colormap table values
2987 * are the averages of all pixels that are found in the octcube.
2988 * (2) This fails if there are more than 256 colors (i.e., more
2989 * than 256 occupied octcubes).
2990 * (3) Often level 3 (512 octcubes) will succeed because not more
2991 * than half of them are occupied with 1 or more pixels.
2992 * (4) For an image with not more than 256 colors, it is unlikely
2993 * that two pixels of different color will fall in the same
2994 * octcube at level = 4. However it is possible, and this
2995 * function optionally returns @nerrors, the number of pixels
2996 * where, because more than one color is in the same octcube,
2997 * the pixel color is not exactly reproduced in the colormap.
2998 * The colormap for an occupied leaf of the octree contains
2999 * the color of the first pixel encountered in that octcube.
3000 * (5) This differs from pixFewColorsOctcubeQuant1(), which also
3001 * requires not more than 256 occupied leaves, but represents
3002 * the color of each leaf by an average over the pixels in
3003 * that leaf. This also requires precomputing the histogram
3004 * of occupied octree leaves, which is generated using
3005 * pixOctcubeHistogram().
3006 * (6) This is used in pixConvertRGBToColormap() for images that
3007 * are determined, by their histogram, to have relatively few
3008 * colors. This typically happens with orthographically
3009 * produced images (as oppopsed to natural images), where
3010 * it is expected that most of the pixels within a leaf
3011 * octcube have exactly the same color, and quantization to
3012 * that color is lossless.
3013 */
3014 PIX *
pixFewColorsOctcubeQuant2(PIX * pixs,l_int32 level,NUMA * na,l_int32 ncolors,l_int32 * pnerrors)3015 pixFewColorsOctcubeQuant2(PIX *pixs,
3016 l_int32 level,
3017 NUMA *na,
3018 l_int32 ncolors,
3019 l_int32 *pnerrors)
3020 {
3021 l_int32 w, h, wpls, wpld, i, j, nerrors;
3022 l_int32 ncubes, depth, cindex, oval;
3023 l_int32 rval, gval, bval;
3024 l_int32 *octarray;
3025 l_uint32 octindex;
3026 l_uint32 *rtab, *gtab, *btab;
3027 l_uint32 *lines, *lined, *datas, *datad, *ppixel;
3028 l_uint32 *colorarray;
3029 PIX *pixd;
3030 PIXCMAP *cmap;
3031
3032 PROCNAME("pixFewColorsOctcubeQuant2");
3033
3034 if (!pixs)
3035 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
3036 if (pixGetDepth(pixs) != 32)
3037 return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
3038 if (level < 3 || level > 6)
3039 return (PIX *)ERROR_PTR("level not in {4, 5, 6}", procName, NULL);
3040 if (ncolors > 256)
3041 return (PIX *)ERROR_PTR("ncolors > 256", procName, NULL);
3042 if (pnerrors)
3043 *pnerrors = UNDEF;
3044
3045 /* Represent the image with a set of leaf octcubes
3046 * at 'level', one for each color. */
3047 if (makeRGBToIndexTables(&rtab, >ab, &btab, level))
3048 return (PIX *)ERROR_PTR("tables not made", procName, NULL);
3049
3050 /* Determine the output depth from the number of colors */
3051 pixGetDimensions(pixs, &w, &h, NULL);
3052 datas = pixGetData(pixs);
3053 wpls = pixGetWpl(pixs);
3054 if (ncolors <= 4)
3055 depth = 2;
3056 else if (ncolors <= 16)
3057 depth = 4;
3058 else /* ncolors <= 256 */
3059 depth = 8;
3060
3061 if ((pixd = pixCreate(w, h, depth)) == NULL)
3062 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
3063 pixCopyResolution(pixd, pixs);
3064 pixCopyInputFormat(pixd, pixs);
3065 datad = pixGetData(pixd);
3066 wpld = pixGetWpl(pixd);
3067
3068 /* The octarray will give a ptr from the octcube to the colorarray */
3069 ncubes = numaGetCount(na);
3070 if ((octarray = (l_int32 *)CALLOC(ncubes, sizeof(l_int32))) == NULL)
3071 return (PIX *)ERROR_PTR("octarray not made", procName, NULL);
3072
3073 /* The colorarray will hold the colors of the first pixel
3074 * that lands in the leaf octcube. After filling, it is
3075 * used to generate the colormap. */
3076 if ((colorarray = (l_uint32 *)CALLOC(ncolors + 1, sizeof(l_uint32)))
3077 == NULL)
3078 return (PIX *)ERROR_PTR("colorarray not made", procName, NULL);
3079
3080 /* For each pixel, get the octree index for its leaf octcube.
3081 * Check if a pixel has already been found in this octcube.
3082 * - If not yet found, save that color in the colorarray
3083 * and save the cindex in the octarray.
3084 * - If already found, compare the pixel color with the
3085 * color in the colorarray, and note if it differs.
3086 * Then set the dest pixel value to the cindex - 1, which
3087 * will be the cmap index for this color. */
3088 cindex = 1; /* start with 1 */
3089 nerrors = 0;
3090 for (i = 0; i < h; i++) {
3091 lines = datas + i * wpls;
3092 lined = datad + i * wpld;
3093 for (j = 0; j < w; j++) {
3094 ppixel = lines + j;
3095 extractRGBValues(*ppixel, &rval, &gval, &bval);
3096 octindex = rtab[rval] | gtab[gval] | btab[bval];
3097 oval = octarray[octindex];
3098 if (oval == 0) {
3099 octarray[octindex] = cindex;
3100 colorarray[cindex] = *ppixel;
3101 setPixelLow(lined, j, depth, cindex - 1);
3102 cindex++;
3103 }
3104 else { /* already have seen this color; is it unique? */
3105 setPixelLow(lined, j, depth, oval - 1);
3106 if (colorarray[oval] != *ppixel)
3107 nerrors++;
3108 }
3109 }
3110 }
3111 if (pnerrors)
3112 *pnerrors = nerrors;
3113
3114 #if DEBUG_FEW_COLORS
3115 fprintf(stderr, "ncubes = %d, ncolors = %d\n", ncubes, ncolors);
3116 for (i = 0; i < ncolors; i++)
3117 fprintf(stderr, "color[%d] = %x\n", i, colorarray[i + 1]);
3118 #endif /* DEBUG_FEW_COLORS */
3119
3120 /* Make the colormap. */
3121 cmap = pixcmapCreate(depth);
3122 for (i = 0; i < ncolors; i++) {
3123 ppixel = colorarray + i + 1;
3124 extractRGBValues(*ppixel, &rval, &gval, &bval);
3125 pixcmapAddColor(cmap, rval, gval, bval);
3126 }
3127 pixSetColormap(pixd, cmap);
3128
3129 FREE(octarray);
3130 FREE(colorarray);
3131 FREE(rtab);
3132 FREE(gtab);
3133 FREE(btab);
3134 return pixd;
3135 }
3136
3137
3138 /*!
3139 * pixFewColorsOctcubeQuantMixed()
3140 *
3141 * Input: pixs (32 bpp rgb)
3142 * level (significant octcube bits for each of RGB;
3143 * valid in [1...6]; use 0 for default)
3144 * darkthresh (darkest average value not automatically
3145 * considered gray; use 0 for default)
3146 * lightthresh (lightest average value not automatically
3147 * considered gray; use 0 for default)
3148 * diffthresh (thresh for max difference from the average of
3149 * component values to consider pixel gray;
3150 * use 0 for default)
3151 * considered gray; use 0 for default)
3152 * minfract (min fraction of pixels for gray histo bin;
3153 * use 0.0 for default)
3154 * maxspan (max size of gray histo bin; use 0 for default)
3155 * Return: pixd (8 bpp, quantized to octcube for pixels that are
3156 * not gray; gray pixels are quantized separately
3157 * over the full gray range), or null on error
3158 *
3159 * Notes:
3160 * (1) First runs pixFewColorsOctcubeQuant1(). If this succeeds,
3161 * it separates the color from gray(ish) entries in the cmap,
3162 * and re-quantizes the gray pixels. The result has some pixels
3163 * in color and others in gray.
3164 * (2) This fails if there are more than 256 colors (i.e., more
3165 * than 256 occupied octcubes in the color quantization).
3166 * (3) Level 3 (512 octcubes) will usually succeed because not more
3167 * than half of them are occupied with 1 or more pixels.
3168 * (4) This uses the criterion from pixColorFraction() for deciding
3169 * if a colormap entry is color; namely, if the average is
3170 * not too close to either black or white, and the maximum
3171 * deviation of a component from the average exceeds a threshold.
3172 * (5) For quantizing the gray pixels, it uses a histogram-based
3173 * method where input parameters determining the buckets are
3174 * the minimum population fraction and the maximum allowed size.
3175 * (6) Recommended input parameters are:
3176 * @level: 3 or 4 (3 is default)
3177 * @darkthresh: 20
3178 * @lightthresh: 248
3179 * @diffthresh: 12
3180 * @minfract: 0.05
3181 * @maxspan: 15
3182 * Input 0 on any of these to get the default.
3183 * (7) This can be useful for quantizing orthographically generated
3184 * images such as color maps, where there may be more than 256 colors
3185 * because of aliasing or jpeg artifacts on text or lines, but
3186 * there are a relatively small number of solid colors. It usually
3187 * gives results that are better than pixOctcubeQuantMixedWithGray(),
3188 * both in size and appearance. But it is a bit slower.
3189 */
3190 PIX *
pixFewColorsOctcubeQuantMixed(PIX * pixs,l_int32 level,l_int32 darkthresh,l_int32 lightthresh,l_int32 diffthresh,l_float32 minfract,l_int32 maxspan)3191 pixFewColorsOctcubeQuantMixed(PIX *pixs,
3192 l_int32 level,
3193 l_int32 darkthresh,
3194 l_int32 lightthresh,
3195 l_int32 diffthresh,
3196 l_float32 minfract,
3197 l_int32 maxspan)
3198 {
3199 l_int32 i, j, w, h, wplc, wplm, wpld, ncolors, index;
3200 l_int32 rval, gval, bval, val, rdiff, gdiff, bdiff, maxdiff, ave;
3201 l_int32 *lut;
3202 l_uint32 *datac, *datam, *datad, *linec, *linem, *lined;
3203 PIX *pixc, *pixm, *pixg, *pixd;
3204 PIXCMAP *cmap, *cmapd;
3205
3206 PROCNAME("pixFewColorsOctcubeQuantMixed");
3207
3208 if (!pixs || pixGetDepth(pixs) != 32)
3209 return (PIX *)ERROR_PTR("pixs undefined or not 32 bpp", procName, NULL);
3210 if (level <= 0) level = 3;
3211 if (level > 6)
3212 return (PIX *)ERROR_PTR("invalid level", procName, NULL);
3213 if (darkthresh <= 0) darkthresh = 20;
3214 if (lightthresh <= 0) lightthresh = 248;
3215 if (diffthresh <= 0) diffthresh = 12;
3216 if (minfract <= 0.0) minfract = 0.05;
3217 if (maxspan <= 2) maxspan = 15;
3218
3219 /* Start with a simple fixed octcube quantizer. */
3220 if ((pixc = pixFewColorsOctcubeQuant1(pixs, level)) == NULL)
3221 return (PIX *)ERROR_PTR("too many colors", procName, NULL);
3222
3223 /* Identify and save color entries in the colormap. Set up a LUT
3224 * that returns -1 for any gray pixel. */
3225 cmap = pixGetColormap(pixc);
3226 ncolors = pixcmapGetCount(cmap);
3227 cmapd = pixcmapCreate(8);
3228 lut = (l_int32 *)CALLOC(256, sizeof(l_int32));
3229 for (i = 0; i < 256; i++)
3230 lut[i] = -1;
3231 for (i = 0, index = 0; i < ncolors; i++) {
3232 pixcmapGetColor(cmap, i, &rval, &gval, &bval);
3233 ave = (l_int32)(0.333 * (rval + gval + bval));
3234 if (ave < darkthresh || ave > lightthresh)
3235 continue;
3236 rdiff = L_ABS(rval - ave);
3237 gdiff = L_ABS(gval - ave);
3238 bdiff = L_ABS(bval - ave);
3239 maxdiff = L_MAX(rdiff, gdiff);
3240 maxdiff = L_MAX(maxdiff, bdiff);
3241 if (maxdiff >= diffthresh) {
3242 pixcmapAddColor(cmapd, rval, gval, bval);
3243 lut[i] = index;
3244 index++;
3245 }
3246 }
3247
3248 /* Generate dest pix with just the color pixels set to their
3249 * colormap indices. At the same time, make a 1 bpp mask
3250 * of the non-color pixels */
3251 pixGetDimensions(pixs, &w, &h, NULL);
3252 pixd = pixCreate(w, h, 8);
3253 pixSetColormap(pixd, cmapd);
3254 pixm = pixCreate(w, h, 1);
3255 datac = pixGetData(pixc);
3256 datam = pixGetData(pixm);
3257 datad = pixGetData(pixd);
3258 wplc = pixGetWpl(pixc);
3259 wplm = pixGetWpl(pixm);
3260 wpld = pixGetWpl(pixd);
3261 for (i = 0; i < h; i++) {
3262 linec = datac + i * wplc;
3263 linem = datam + i * wplm;
3264 lined = datad + i * wpld;
3265 for (j = 0; j < w; j++) {
3266 val = GET_DATA_BYTE(linec, j);
3267 if (lut[val] == -1)
3268 SET_DATA_BIT(linem, j);
3269 else
3270 SET_DATA_BYTE(lined, j, lut[val]);
3271 }
3272 }
3273
3274 /* Fill in the gray values. Use a grayscale version of pixs
3275 * as input, along with the mask over the actual gray pixels. */
3276 pixg = pixConvertTo8(pixs, 0);
3277 pixGrayQuantFromHisto(pixd, pixg, pixm, minfract, maxspan);
3278
3279 FREE(lut);
3280 pixDestroy(&pixc);
3281 pixDestroy(&pixm);
3282 pixDestroy(&pixg);
3283 return pixd;
3284 }
3285
3286
3287 /*---------------------------------------------------------------------------*
3288 * Fixed partition octcube quantization with RGB output *
3289 *---------------------------------------------------------------------------*/
3290 /*!
3291 * pixFixedOctcubeQuantGenRGB()
3292 *
3293 * Input: pixs (32 bpp rgb)
3294 * level (significant bits for each of r,g,b)
3295 * Return: pixd (rgb; quantized to octcube centers), or null on error
3296 *
3297 * Notes:
3298 * (1) Unlike the other color quantization functions, this one
3299 * generates an rgb image.
3300 * (2) The pixel values are quantized to the center of each octcube
3301 * (at the specified level) containing the pixel. They are
3302 * not quantized to the average of the pixels in that octcube.
3303 */
3304 PIX *
pixFixedOctcubeQuantGenRGB(PIX * pixs,l_int32 level)3305 pixFixedOctcubeQuantGenRGB(PIX *pixs,
3306 l_int32 level)
3307 {
3308 l_int32 w, h, wpls, wpld, i, j;
3309 l_int32 rval, gval, bval;
3310 l_uint32 octindex;
3311 l_uint32 *rtab, *gtab, *btab;
3312 l_uint32 *lines, *lined, *datas, *datad;
3313 PIX *pixd;
3314
3315 PROCNAME("pixFixedOctcubeQuantGenRGB");
3316
3317 if (!pixs)
3318 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
3319 if (pixGetDepth(pixs) != 32)
3320 return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
3321 if (level < 1 || level > 6)
3322 return (PIX *)ERROR_PTR("level not in {1,...6}", procName, NULL);
3323
3324 if (makeRGBToIndexTables(&rtab, >ab, &btab, level))
3325 return (PIX *)ERROR_PTR("tables not made", procName, NULL);
3326
3327 pixGetDimensions(pixs, &w, &h, NULL);
3328 pixd = pixCreate(w, h, 32);
3329 pixCopyResolution(pixd, pixs);
3330 pixCopyInputFormat(pixd, pixs);
3331 datad = pixGetData(pixd);
3332 wpld = pixGetWpl(pixd);
3333 datas = pixGetData(pixs);
3334 wpls = pixGetWpl(pixs);
3335 for (i = 0; i < h; i++) {
3336 lines = datas + i * wpls;
3337 lined = datad + i * wpld;
3338 for (j = 0; j < w; j++) {
3339 extractRGBValues(lines[j], &rval, &gval, &bval);
3340 octindex = rtab[rval] | gtab[gval] | btab[bval];
3341 getRGBFromOctcube(octindex, level, &rval, &gval, &bval);
3342 composeRGBPixel(rval, gval, bval, lined + j);
3343 }
3344 }
3345
3346 FREE(rtab);
3347 FREE(gtab);
3348 FREE(btab);
3349 return pixd;
3350 }
3351
3352
3353 /*------------------------------------------------------------------*
3354 * Color quantize RGB image using existing colormap *
3355 *------------------------------------------------------------------*/
3356 /*!
3357 * pixQuantFromCmap()
3358 *
3359 * Input: pixs (8 bpp grayscale without cmap, or 32 bpp rgb)
3360 * cmap (to quantize to; insert copy into dest pix)
3361 * mindepth (minimum depth of pixd: can be 2, 4 or 8 bpp)
3362 * level (of octcube used for finding nearest color in cmap)
3363 * metric (L_MANHATTAN_DISTANCE, L_EUCLIDEAN_DISTANCE)
3364 * Return: pixd (2, 4 or 8 bpp, colormapped), or null on error
3365 *
3366 * Notes:
3367 * (1) This is a top-level wrapper for quantizing either grayscale
3368 * or rgb images to a specified colormap.
3369 * (2) The actual output depth is constrained by @mindepth and
3370 * by the number of colors in @cmap.
3371 * (3) For grayscale, @level and @metric are ignored.
3372 * (4) If the cmap has color and pixs is grayscale, the color is
3373 * removed from the cmap before quantizing pixs.
3374 */
3375 PIX *
pixQuantFromCmap(PIX * pixs,PIXCMAP * cmap,l_int32 mindepth,l_int32 level,l_int32 metric)3376 pixQuantFromCmap(PIX *pixs,
3377 PIXCMAP *cmap,
3378 l_int32 mindepth,
3379 l_int32 level,
3380 l_int32 metric)
3381 {
3382 l_int32 d;
3383
3384 PROCNAME("pixQuantFromCmap");
3385
3386 if (!pixs)
3387 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
3388 if (mindepth != 2 && mindepth != 4 && mindepth != 8)
3389 return (PIX *)ERROR_PTR("invalid mindepth", procName, NULL);
3390 d = pixGetDepth(pixs);
3391 if (d == 8)
3392 return pixGrayQuantFromCmap(pixs, cmap, mindepth);
3393 else if (d == 32)
3394 return pixOctcubeQuantFromCmap(pixs, cmap, mindepth,
3395 level, metric);
3396 else
3397 return (PIX *)ERROR_PTR("d not 8 or 32 bpp", procName, NULL);
3398 }
3399
3400
3401
3402 /*!
3403 * pixOctcubeQuantFromCmap()
3404 *
3405 * Input: pixs (32 bpp rgb)
3406 * cmap (to quantize to; insert copy into dest pix)
3407 * mindepth (minimum depth of pixd: can be 2, 4 or 8 bpp)
3408 * level (of octcube used for finding nearest color in cmap)
3409 * metric (L_MANHATTAN_DISTANCE, L_EUCLIDEAN_DISTANCE)
3410 * Return: pixd (2, 4 or 8 bpp, colormapped), or null on error
3411 *
3412 * Notes:
3413 * (1) In typical use, we are doing an operation, such as
3414 * interpolative scaling, on a colormapped pix, where it is
3415 * necessary to remove the colormap before the operation.
3416 * We then want to re-quantize the RGB result using the same
3417 * colormap.
3418 * (2) The level is used to divide the color space into octcubes.
3419 * Each input pixel is, in effect, placed at the center of an
3420 * octcube at the given level, and it is mapped into the
3421 * exact color (given in the colormap) that is the closest
3422 * to that location. We need to know that distance, for each color
3423 * in the colormap. The higher the level of the octtree, the smaller
3424 * the octcubes in the color space, and hence the more accurately
3425 * we can determine the closest color in the colormap; however,
3426 * the size of the LUT, which is the total number of octcubes,
3427 * increases by a factor of 8 for each increase of 1 level.
3428 * The time required to acquire a level 4 mapping table, which has
3429 * about 4K entries, is less than 1 msec, so that is the
3430 * recommended minimum size to be used. At that size, the
3431 * octcubes have their centers 16 units apart in each (r,g,b)
3432 * direction. If two colors are in the same octcube, the one
3433 * closest to the center will always be chosen. The maximum
3434 * error for any component occurs when the correct color is
3435 * at a cube corner and there is an incorrect color just inside
3436 * the cube next to the opposite corner, giving an error of
3437 * 14 units (out of 256) for each component. Using a level 5
3438 * mapping table reduces the maximum error to 6 units.
3439 * (3) Typically you should use the Euclidean metric, because the
3440 * resulting voronoi cells (which are generated using the actual
3441 * colormap values as seeds) are convex for Euclidean distance
3442 * but not for Manhattan distance. In terms of the octcubes,
3443 * convexity of the voronoi cells means that if the 8 corners
3444 * of any cube (of which the octcubes are special cases)
3445 * are all within a cell, then every point in the cube will
3446 * lie within the cell.
3447 * (4) The depth of the output pixd is equal to the maximum of
3448 * (a) @mindepth and (b) the minimum (2, 4 or 8 bpp) necessary
3449 * to hold the indices in the colormap.
3450 * (5) We build a mapping table from octcube to colormap index so
3451 * that this function can run in a time (otherwise) independent
3452 * of the number of colors in the colormap. This avoids a
3453 * brute-force search for the closest colormap color to each
3454 * pixel in the image.
3455 * (6) This is similar to the function pixAssignToNearestColor()
3456 * used for color segmentation.
3457 * (7) Except for very small images or when using level > 4,
3458 * it takes very little time to generate the tables,
3459 * compared to the generation of the colormapped dest pix,
3460 * so one would not typically use the low-level version.
3461 */
3462 PIX *
pixOctcubeQuantFromCmap(PIX * pixs,PIXCMAP * cmap,l_int32 mindepth,l_int32 level,l_int32 metric)3463 pixOctcubeQuantFromCmap(PIX *pixs,
3464 PIXCMAP *cmap,
3465 l_int32 mindepth,
3466 l_int32 level,
3467 l_int32 metric)
3468 {
3469 l_int32 *cmaptab;
3470 l_uint32 *rtab, *gtab, *btab;
3471 PIX *pixd;
3472
3473 PROCNAME("pixOctcubeQuantFromCmap");
3474
3475 if (!pixs)
3476 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
3477 if (pixGetDepth(pixs) != 32)
3478 return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
3479 if (!cmap)
3480 return (PIX *)ERROR_PTR("cmap not defined", procName, NULL);
3481 if (mindepth != 2 && mindepth != 4 && mindepth != 8)
3482 return (PIX *)ERROR_PTR("invalid mindepth", procName, NULL);
3483 if (level < 1 || level > 6)
3484 return (PIX *)ERROR_PTR("level not in {1...6}", procName, NULL);
3485 if (metric != L_MANHATTAN_DISTANCE && metric != L_EUCLIDEAN_DISTANCE)
3486 return (PIX *)ERROR_PTR("invalid metric", procName, NULL);
3487
3488 /* Set up the tables to map rgb to the nearest colormap index */
3489 if (makeRGBToIndexTables(&rtab, >ab, &btab, level))
3490 return (PIX *)ERROR_PTR("index tables not made", procName, NULL);
3491 if ((cmaptab = pixcmapToOctcubeLUT(cmap, level, metric)) == NULL)
3492 return (PIX *)ERROR_PTR("cmaptab not made", procName, NULL);
3493
3494 pixd = pixOctcubeQuantFromCmapLUT(pixs, cmap, mindepth,
3495 cmaptab, rtab, gtab, btab);
3496
3497 FREE(cmaptab);
3498 FREE(rtab);
3499 FREE(gtab);
3500 FREE(btab);
3501 return pixd;
3502 }
3503
3504
3505 /*!
3506 * pixOctcubeQuantFromCmapLUT()
3507 *
3508 * Input: pixs (32 bpp rgb)
3509 * cmap (to quantize to; insert copy into dest pix)
3510 * mindepth (minimum depth of pixd: can be 2, 4 or 8 bpp)
3511 * cmaptab (table mapping from octindex to colormap index)
3512 * rtab, gtab, btab (tables mapping from RGB to octindex)
3513 * Return: pixd (2, 4 or 8 bpp, colormapped), or null on error
3514 *
3515 * Notes:
3516 * (1) See the notes in the higher-level function
3517 * pixOctcubeQuantFromCmap(). The octcube level for
3518 * the generated octree is specified there, along with
3519 * the distance metric for determining the closest
3520 * color in the colormap to each octcube.
3521 * (2) If the colormap, level and metric information have already
3522 * been used to construct the set of mapping tables,
3523 * this low-level function can be used directly (i.e.,
3524 * independently of pixOctcubeQuantFromCmap()) to build
3525 * a colormapped pix that uses the specified colormap.
3526 */
3527 PIX *
pixOctcubeQuantFromCmapLUT(PIX * pixs,PIXCMAP * cmap,l_int32 mindepth,l_int32 * cmaptab,l_uint32 * rtab,l_uint32 * gtab,l_uint32 * btab)3528 pixOctcubeQuantFromCmapLUT(PIX *pixs,
3529 PIXCMAP *cmap,
3530 l_int32 mindepth,
3531 l_int32 *cmaptab,
3532 l_uint32 *rtab,
3533 l_uint32 *gtab,
3534 l_uint32 *btab)
3535 {
3536 l_int32 i, j, w, h, depth, wpls, wpld;
3537 l_int32 rval, gval, bval, index;
3538 l_uint32 octindex;
3539 l_uint32 *lines, *lined, *datas, *datad;
3540 PIX *pixd;
3541 PIXCMAP *cmapc;
3542
3543 PROCNAME("pixOctcubeQuantFromCmapLUT");
3544
3545 if (!pixs)
3546 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
3547 if (pixGetDepth(pixs) != 32)
3548 return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
3549 if (!cmap)
3550 return (PIX *)ERROR_PTR("cmap not defined", procName, NULL);
3551 if (mindepth != 2 && mindepth != 4 && mindepth != 8)
3552 return (PIX *)ERROR_PTR("invalid mindepth", procName, NULL);
3553 if (!rtab || !gtab || !btab || !cmaptab)
3554 return (PIX *)ERROR_PTR("tables not all defined", procName, NULL);
3555
3556 /* Init dest pix (with minimum bpp depending on cmap) */
3557 pixcmapGetMinDepth(cmap, &depth);
3558 depth = L_MAX(depth, mindepth);
3559 pixGetDimensions(pixs, &w, &h, NULL);
3560 if ((pixd = pixCreate(w, h, depth)) == NULL)
3561 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
3562 cmapc = pixcmapCopy(cmap);
3563 pixSetColormap(pixd, cmapc);
3564 pixCopyResolution(pixd, pixs);
3565 pixCopyInputFormat(pixd, pixs);
3566
3567 /* Insert the colormap index of the color nearest to the input pixel */
3568 datas = pixGetData(pixs);
3569 datad = pixGetData(pixd);
3570 wpls = pixGetWpl(pixs);
3571 wpld = pixGetWpl(pixd);
3572 for (i = 0; i < h; i++) {
3573 lines = datas + i * wpls;
3574 lined = datad + i * wpld;
3575 for (j = 0; j < w; j++) {
3576 extractRGBValues(lines[j], &rval, &gval, &bval);
3577 /* Map from rgb to octcube index */
3578 getOctcubeIndexFromRGB(rval, gval, bval, rtab, gtab, btab,
3579 &octindex);
3580 /* Map from octcube index to nearest colormap index */
3581 index = cmaptab[octindex];
3582 if (depth == 2)
3583 SET_DATA_DIBIT(lined, j, index);
3584 else if (depth == 4)
3585 SET_DATA_QBIT(lined, j, index);
3586 else /* depth == 8 */
3587 SET_DATA_BYTE(lined, j, index);
3588 }
3589 }
3590
3591 return pixd;
3592 }
3593
3594
3595 /*---------------------------------------------------------------------------*
3596 * Generation of octcube histogram *
3597 *---------------------------------------------------------------------------*/
3598 /*!
3599 * pixOctcubeHistogram()
3600 *
3601 * Input: pixs (32 bpp rgb)
3602 * level (significant bits for each of RGB; valid in [1...6])
3603 * &ncolors (<optional return> number of occupied cubes)
3604 * Return: numa (histogram of color pixels, or null on error)
3605 *
3606 * Notes:
3607 * (1) Input NULL for &ncolors to prevent computation and return value.
3608 */
3609 NUMA *
pixOctcubeHistogram(PIX * pixs,l_int32 level,l_int32 * pncolors)3610 pixOctcubeHistogram(PIX *pixs,
3611 l_int32 level,
3612 l_int32 *pncolors)
3613 {
3614 l_int32 size, i, j, w, h, wpl, ncolors, val;
3615 l_int32 rval, gval, bval;
3616 l_uint32 octindex;
3617 l_uint32 *rtab, *gtab, *btab;
3618 l_uint32 *data, *line;
3619 l_float32 *array;
3620 NUMA *na;
3621
3622 PROCNAME("pixOctcubeHistogram");
3623
3624 if (pncolors) *pncolors = 0;
3625 if (!pixs)
3626 return (NUMA *)ERROR_PTR("pixs not defined", procName, NULL);
3627 if (pixGetDepth(pixs) != 32)
3628 return (NUMA *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
3629
3630 pixGetDimensions(pixs, &w, &h, NULL);
3631 wpl = pixGetWpl(pixs);
3632 data = pixGetData(pixs);
3633
3634 if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
3635 return (NUMA *)ERROR_PTR("size not returned", procName, NULL);
3636 if (makeRGBToIndexTables(&rtab, >ab, &btab, level))
3637 return (NUMA *)ERROR_PTR("tables not made", procName, NULL);
3638
3639 if ((na = numaCreate(size)) == NULL)
3640 return (NUMA *)ERROR_PTR("na not made", procName, NULL);
3641 numaSetCount(na, size);
3642 array = numaGetFArray(na, L_NOCOPY);
3643
3644 for (i = 0; i < h; i++) {
3645 line = data + i * wpl;
3646 for (j = 0; j < w; j++) {
3647 extractRGBValues(line[j], &rval, &gval, &bval);
3648 octindex = rtab[rval] | gtab[gval] | btab[bval];
3649 #if DEBUG_OCTINDEX
3650 if ((level == 1 && octindex > 7) ||
3651 (level == 2 && octindex > 63) ||
3652 (level == 3 && octindex > 511) ||
3653 (level == 4 && octindex > 4097) ||
3654 (level == 5 && octindex > 32783) ||
3655 (level == 6 && octindex > 262271)) {
3656 fprintf(stderr, "level = %d, octindex = %d, index error!\n",
3657 level, octindex);
3658 continue;
3659 }
3660 #endif /* DEBUG_OCTINDEX */
3661 array[octindex] += 1.0;
3662 }
3663 }
3664
3665 if (pncolors) {
3666 for (i = 0, ncolors = 0; i < size; i++) {
3667 numaGetIValue(na, i, &val);
3668 if (val > 0)
3669 ncolors++;
3670 }
3671 *pncolors = ncolors;
3672 }
3673
3674 FREE(rtab);
3675 FREE(gtab);
3676 FREE(btab);
3677 return na;
3678 }
3679
3680
3681 /*------------------------------------------------------------------*
3682 * Get filled octcube table from colormap *
3683 *------------------------------------------------------------------*/
3684 /*!
3685 * pixcmapToOctcubeLUT()
3686 *
3687 * Input: cmap
3688 * level (significant bits for each of RGB; valid in [1...6])
3689 * metric (L_MANHATTAN_DISTANCE, L_EUCLIDEAN_DISTANCE)
3690 * Return: tab[2**(3 * level)]
3691 *
3692 * Notes:
3693 * (1) This function is used to quickly find the colormap color
3694 * that is closest to any rgb color. It is used to assign
3695 * rgb colors to an existing colormap. It can be very expensive
3696 * to search through the entire colormap for the closest color
3697 * to each pixel. Instead, we first set up this table, which is
3698 * populated by the colormap index nearest to each octcube
3699 * color. Then we go through the image; for each pixel,
3700 * do two table lookups: first to generate the octcube index
3701 * from rgb and second to use this table to read out the
3702 * colormap index.
3703 * (2) Do a slight modification for white and black. For level = 4,
3704 * each octcube size is 16. The center of the whitest octcube
3705 * is at (248, 248, 248), which is closer to 242 than 255.
3706 * Consequently, any gray color between 242 and 254 will
3707 * be selected, even if white (255, 255, 255) exists. This is
3708 * typically not optimal, because the original color was
3709 * likely white. Therefore, if white exists in the colormap,
3710 * use it for any rgb color that falls into the most white octcube.
3711 * Do the similar thing for black.
3712 * (3) Here are the actual function calls for quantizing to a
3713 * specified colormap:
3714 * - first make the tables that map from rgb --> octcube index
3715 * makeRGBToIndexTables()
3716 * - then for each pixel:
3717 * * use the tables to get the octcube index
3718 * getOctcubeIndexFromRGB()
3719 * * use this table to get the nearest color in the colormap
3720 * cmap_index = tab[index]
3721 * (4) Distance can be either manhattan or euclidean.
3722 * (5) In typical use, level = 4 gives reasonable results, and
3723 * level = 5 is slightly better. When this function is used
3724 * for color segmentation, there are typically a small number
3725 * of colors and the number of levels can be small (e.g., level = 3).
3726 */
3727 l_int32 *
pixcmapToOctcubeLUT(PIXCMAP * cmap,l_int32 level,l_int32 metric)3728 pixcmapToOctcubeLUT(PIXCMAP *cmap,
3729 l_int32 level,
3730 l_int32 metric)
3731 {
3732 l_int32 i, k, size, ncolors, mindist, dist, mincolor, index;
3733 l_int32 rval, gval, bval; /* color at center of the octcube */
3734 l_int32 *rmap, *gmap, *bmap, *tab;
3735
3736 PROCNAME("pixcmapToOctcubeLUT");
3737
3738 if (!cmap)
3739 return (l_int32 *)ERROR_PTR("cmap not defined", procName, NULL);
3740 if (level < 1 || level > 6)
3741 return (l_int32 *)ERROR_PTR("level not in {1...6}", procName, NULL);
3742 if (metric != L_MANHATTAN_DISTANCE && metric != L_EUCLIDEAN_DISTANCE)
3743 return (l_int32 *)ERROR_PTR("invalid metric", procName, NULL);
3744
3745 if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
3746 return (l_int32 *)ERROR_PTR("size not returned", procName, NULL);
3747 if ((tab = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
3748 return (l_int32 *)ERROR_PTR("tab not allocated", procName, NULL);
3749
3750 ncolors = pixcmapGetCount(cmap);
3751 pixcmapToArrays(cmap, &rmap, &gmap, &bmap);
3752
3753 /* Assign based on the closest octcube center to the cmap color */
3754 for (i = 0; i < size; i++) {
3755 getRGBFromOctcube(i, level, &rval, &gval, &bval);
3756 mindist = 1000000;
3757 mincolor = 0; /* irrelevant init */
3758 for (k = 0; k < ncolors; k++) {
3759 if (metric == L_MANHATTAN_DISTANCE) {
3760 dist = L_ABS(rval - rmap[k]) + L_ABS(gval - gmap[k]) +
3761 L_ABS(bval - bmap[k]);
3762 }
3763 else { /* L_EUCLIDEAN_DISTANCE */
3764 dist = (rval - rmap[k]) * (rval - rmap[k]) +
3765 (gval - gmap[k]) * (gval - gmap[k]) +
3766 (bval - bmap[k]) * (bval - bmap[k]);
3767 }
3768 if (dist < mindist) {
3769 mindist = dist;
3770 mincolor = k;
3771 }
3772 }
3773 tab[i] = mincolor;
3774 }
3775
3776 /* Reset black and white if available in the colormap.
3777 * The darkest octcube is at octindex 0.
3778 * The lightest octcube is at the max octindex. */
3779 pixcmapGetNearestIndex(cmap, 0, 0, 0, &index);
3780 pixcmapGetColor(cmap, index, &rval, &gval, &bval);
3781 if (rval < 7 && gval < 7 && bval < 7) {
3782 tab[0] = index;
3783 }
3784 pixcmapGetNearestIndex(cmap, 255, 255, 255, &index);
3785 pixcmapGetColor(cmap, index, &rval, &gval, &bval);
3786 if (rval > 248 && gval > 248 && bval > 248) {
3787 tab[(1 << (3 * level)) - 1] = index;
3788 }
3789
3790 FREE(rmap);
3791 FREE(gmap);
3792 FREE(bmap);
3793 return tab;
3794 }
3795
3796
3797 /*------------------------------------------------------------------*
3798 * Strip out unused elements in colormap *
3799 *------------------------------------------------------------------*/
3800 /*!
3801 * pixRemoveUnusedColors()
3802 *
3803 * Input: pixs (colormapped)
3804 * Return: 0 if OK, 1 on error
3805 *
3806 * Notes:
3807 * (1) This is an in-place operation.
3808 * (2) If the image doesn't have a colormap, returns without error.
3809 * (3) Unusued colors are removed from the colormap, and the
3810 * image pixels are re-numbered.
3811 */
3812 l_int32
pixRemoveUnusedColors(PIX * pixs)3813 pixRemoveUnusedColors(PIX *pixs)
3814 {
3815 l_int32 i, j, w, h, d, nc, wpls, val, newval, index, zerofound;
3816 l_int32 rval, gval, bval;
3817 l_uint32 *datas, *lines;
3818 l_int32 *histo, *map1, *map2;
3819 PIXCMAP *cmap, *cmapd;
3820
3821 PROCNAME("pixRemoveUnusedColors");
3822
3823 if (!pixs)
3824 return ERROR_INT("pixs not defined", procName, 1);
3825 if ((cmap = pixGetColormap(pixs)) == NULL)
3826 return 0;
3827
3828 d = pixGetDepth(pixs);
3829 if (d != 2 && d != 4 && d != 8)
3830 return ERROR_INT("d not in {2, 4, 8}", procName, 1);
3831
3832 /* Find which indices are actually used */
3833 nc = pixcmapGetCount(cmap);
3834 if ((histo = (l_int32 *)CALLOC(nc, sizeof(l_int32))) == NULL)
3835 return ERROR_INT("histo not made", procName, 1);
3836 pixGetDimensions(pixs, &w, &h, NULL);
3837 wpls = pixGetWpl(pixs);
3838 datas = pixGetData(pixs);
3839 for (i = 0; i < h; i++) {
3840 lines = datas + i * wpls;
3841 for (j = 0; j < w; j++) {
3842 switch (d)
3843 {
3844 case 2:
3845 val = GET_DATA_DIBIT(lines, j);
3846 break;
3847 case 4:
3848 val = GET_DATA_QBIT(lines, j);
3849 break;
3850 case 8:
3851 val = GET_DATA_BYTE(lines, j);
3852 break;
3853 default:
3854 return ERROR_INT("switch ran off end!", procName, 1);
3855 }
3856 if (val >= nc) {
3857 L_WARNING("cmap index out of bounds!", procName);
3858 continue;
3859 }
3860 histo[val]++;
3861 }
3862 }
3863
3864 /* Check if there are any zeroes. If none, quit. */
3865 zerofound = FALSE;
3866 for (i = 0; i < nc; i++) {
3867 if (histo[i] == 0) {
3868 zerofound = TRUE;
3869 break;
3870 }
3871 }
3872 if (!zerofound) {
3873 FREE(histo);
3874 return 0;
3875 }
3876
3877 /* Generate mapping tables between indices */
3878 if ((map1 = (l_int32 *)CALLOC(nc, sizeof(l_int32))) == NULL)
3879 return ERROR_INT("map1 not made", procName, 1);
3880 if ((map2 = (l_int32 *)CALLOC(nc, sizeof(l_int32))) == NULL)
3881 return ERROR_INT("map2 not made", procName, 1);
3882 index = 0;
3883 for (i = 0; i < nc; i++) {
3884 if (histo[i] != 0) {
3885 map1[index] = i; /* get old index from new */
3886 map2[i] = index; /* get new index from old */
3887 index++;
3888 }
3889 }
3890
3891 /* Generate new colormap and attach to pixs */
3892 cmapd = pixcmapCreate(d);
3893 for (i = 0; i < index; i++) {
3894 pixcmapGetColor(cmap, map1[i], &rval, &gval, &bval);
3895 pixcmapAddColor(cmapd, rval, gval, bval);
3896 }
3897 pixSetColormap(pixs, cmapd);
3898
3899 /* Map pixel (index) values to new cmap */
3900 for (i = 0; i < h; i++) {
3901 lines = datas + i * wpls;
3902 for (j = 0; j < w; j++) {
3903 switch (d)
3904 {
3905 case 2:
3906 val = GET_DATA_DIBIT(lines, j);
3907 newval = map2[val];
3908 SET_DATA_DIBIT(lines, j, newval);
3909 break;
3910 case 4:
3911 val = GET_DATA_QBIT(lines, j);
3912 newval = map2[val];
3913 SET_DATA_QBIT(lines, j, newval);
3914 break;
3915 case 8:
3916 val = GET_DATA_BYTE(lines, j);
3917 newval = map2[val];
3918 SET_DATA_BYTE(lines, j, newval);
3919 break;
3920 default:
3921 return ERROR_INT("switch ran off end!", procName, 1);
3922 }
3923 }
3924 }
3925
3926 FREE(histo);
3927 FREE(map1);
3928 FREE(map2);
3929 return 0;
3930 }
3931
3932
3933 /*------------------------------------------------------------------*
3934 * Find number of occupied octcubes at the specified level *
3935 *------------------------------------------------------------------*/
3936 /*!
3937 * pixNumberOccupiedOctcubes()
3938 *
3939 * Input: pix (32 bpp)
3940 * level (of octcube)
3941 * mincount (minimum num pixels in an octcube to be counted;
3942 * -1 to not use)
3943 * minfract (minimum fract of pixels in an octcube to be
3944 * counted; -1 to not use)
3945 * &ncolors (<return> number of occupied octcubes)
3946 * Return: 0 if OK, 1 on error
3947 *
3948 * Notes:
3949 * (1) Exactly one of (@mincount, @minfract) must be -1, so, e.g.,
3950 * if @mincount == -1, then we use @minfract.
3951 * (2) If all occupied octcubes are to count, set @mincount == 1.
3952 * Setting @minfract == 0.0 is taken to mean the same thing.
3953 */
3954 l_int32
pixNumberOccupiedOctcubes(PIX * pix,l_int32 level,l_int32 mincount,l_float32 minfract,l_int32 * pncolors)3955 pixNumberOccupiedOctcubes(PIX *pix,
3956 l_int32 level,
3957 l_int32 mincount,
3958 l_float32 minfract,
3959 l_int32 *pncolors)
3960 {
3961 l_int32 i, j, w, h, d, wpl, ncolors, size, octindex;
3962 l_int32 rval, gval, bval;
3963 l_int32 *carray;
3964 l_uint32 *data, *line, *rtab, *gtab, *btab;
3965
3966 PROCNAME("pixNumberOccupiedOctcubes");
3967
3968 if (!pncolors)
3969 return ERROR_INT("&ncolors not defined", procName, 1);
3970 *pncolors = 0;
3971 if (!pix)
3972 return ERROR_INT("pix not defined", procName, 1);
3973 pixGetDimensions(pix, &w, &h, &d);
3974 if (d != 32)
3975 return ERROR_INT("pix not 32 bpp", procName, 1);
3976 if (level < 1 || level > 6)
3977 return ERROR_INT("invalid level", procName, 1);
3978 if ((mincount < 0 && minfract < 0) || (mincount >= 0.0 && minfract >= 0.0))
3979 return ERROR_INT("invalid mincount/minfract", procName, 1);
3980 if (mincount == 0 || minfract == 0.0)
3981 mincount = 1;
3982 else if (minfract > 0.0)
3983 mincount = L_MIN(1, (l_int32)(minfract * w * h));
3984
3985 if (octcubeGetCount(level, &size)) /* array size = 2 ** (3 * level) */
3986 return ERROR_INT("size not returned", procName, 1);
3987 if (makeRGBToIndexTables(&rtab, >ab, &btab, level))
3988 return ERROR_INT("tables not made", procName, 1);
3989 if ((carray = (l_int32 *)CALLOC(size, sizeof(l_int32))) == NULL)
3990 return ERROR_INT("carray not made", procName, 1);
3991
3992 /* Mark the occupied octcube leaves */
3993 data = pixGetData(pix);
3994 wpl = pixGetWpl(pix);
3995 for (i = 0; i < h; i++) {
3996 line = data + i * wpl;
3997 for (j = 0; j < w; j++) {
3998 extractRGBValues(line[j], &rval, &gval, &bval);
3999 octindex = rtab[rval] | gtab[gval] | btab[bval];
4000 carray[octindex]++;
4001 }
4002 }
4003
4004 /* Count them */
4005 for (i = 0, ncolors = 0; i < size; i++) {
4006 if (carray[i] >= mincount)
4007 ncolors++;
4008 }
4009 *pncolors = ncolors;
4010
4011 FREE(carray);
4012 FREE(rtab);
4013 FREE(gtab);
4014 FREE(btab);
4015 return 0;
4016 }
4017
4018