1 /////////////////////////////////////////////////////////////////////////////
3 // Purpose: wxQuantize implementation
4 // Author: Julian Smart
8 // Copyright: (c) Thomas G. Lane, Vaclav Slavik, Julian Smart
9 // Licence: wxWindows licence + JPEG library licence
10 /////////////////////////////////////////////////////////////////////////////
15 * Copyright (C) 1991-1996, Thomas G. Lane.
16 * This file is part of the Independent JPEG Group's software.
17 * For conditions of distribution and use, see the accompanying README file.
19 * This file contains 2-pass color quantization (color mapping) routines.
20 * These routines provide selection of a custom color map for an image,
21 * followed by mapping of the image to that color map, with optional
22 * Floyd-Steinberg dithering.
23 * It is also possible to use just the second pass to map to an arbitrary
24 * externally-given color map.
26 * Note: ordered dithering is not supported, since there isn't any fast
27 * way to compute intercolor distances; it's unclear that ordered dither's
28 * fundamental assumptions even hold with an irregularly spaced color map.
31 /* modified by Vaclav Slavik for use as jpeglib-independent module */
34 #pragma implementation "quantize.h"
37 // For compilers that support precompilation, includes "wx/wx.h".
38 #include "wx/wxprec.h"
49 #include "wx/quantize.h"
61 #define RGB_PIXELSIZE 3
63 #define MAXJSAMPLE 255
64 #define CENTERJSAMPLE 128
65 #define BITS_IN_JSAMPLE 8
66 #define GETJSAMPLE(value) ((int) (value))
68 #define RIGHT_SHIFT(x,shft) ((x) >> (shft))
70 typedef unsigned short UINT16
;
71 typedef signed short INT16
;
72 typedef signed int INT32
;
74 typedef unsigned char JSAMPLE
;
75 typedef JSAMPLE
*JSAMPROW
;
76 typedef JSAMPROW
*JSAMPARRAY
;
77 typedef unsigned int JDIMENSION
;
81 JDIMENSION output_width
;
83 int actual_number_of_colors
;
84 int desired_number_of_colors
;
85 JSAMPLE
*sample_range_limit
, *srl_orig
;
88 typedef j_decompress
*j_decompress_ptr
;
92 * This module implements the well-known Heckbert paradigm for color
93 * quantization. Most of the ideas used here can be traced back to
94 * Heckbert's seminal paper
95 * Heckbert, Paul. "Color Image Quantization for Frame Buffer Display",
96 * Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304.
98 * In the first pass over the image, we accumulate a histogram showing the
99 * usage count of each possible color. To keep the histogram to a reasonable
100 * size, we reduce the precision of the input; typical practice is to retain
101 * 5 or 6 bits per color, so that 8 or 4 different input values are counted
102 * in the same histogram cell.
104 * Next, the color-selection step begins with a box representing the whole
105 * color space, and repeatedly splits the "largest" remaining box until we
106 * have as many boxes as desired colors. Then the mean color in each
107 * remaining box becomes one of the possible output colors.
109 * The second pass over the image maps each input pixel to the closest output
110 * color (optionally after applying a Floyd-Steinberg dithering correction).
111 * This mapping is logically trivial, but making it go fast enough requires
114 * Heckbert-style quantizers vary a good deal in their policies for choosing
115 * the "largest" box and deciding where to cut it. The particular policies
116 * used here have proved out well in experimental comparisons, but better ones
119 * In earlier versions of the IJG code, this module quantized in YCbCr color
120 * space, processing the raw upsampled data without a color conversion step.
121 * This allowed the color conversion math to be done only once per colormap
122 * entry, not once per pixel. However, that optimization precluded other
123 * useful optimizations (such as merging color conversion with upsampling)
124 * and it also interfered with desired capabilities such as quantizing to an
125 * externally-supplied colormap. We have therefore abandoned that approach.
126 * The present code works in the post-conversion color space, typically RGB.
128 * To improve the visual quality of the results, we actually work in scaled
129 * RGB space, giving G distances more weight than R, and R in turn more than
130 * B. To do everything in integer math, we must use integer scale factors.
131 * The 2/3/1 scale factors used here correspond loosely to the relative
132 * weights of the colors in the NTSC grayscale equation.
133 * If you want to use this code to quantize a non-RGB color space, you'll
134 * probably need to change these scale factors.
137 #define R_SCALE 2 /* scale R distances by this much */
138 #define G_SCALE 3 /* scale G distances by this much */
139 #define B_SCALE 1 /* and B by this much */
141 /* Relabel R/G/B as components 0/1/2, respecting the RGB ordering defined
142 * in jmorecfg.h. As the code stands, it will do the right thing for R,G,B
143 * and B,G,R orders. If you define some other weird order in jmorecfg.h,
144 * you'll get compile errors until you extend this logic. In that case
145 * you'll probably want to tweak the histogram sizes too.
149 #define C0_SCALE R_SCALE
152 #define C0_SCALE B_SCALE
155 #define C1_SCALE G_SCALE
158 #define C2_SCALE R_SCALE
161 #define C2_SCALE B_SCALE
166 * First we have the histogram data structure and routines for creating it.
168 * The number of bits of precision can be adjusted by changing these symbols.
169 * We recommend keeping 6 bits for G and 5 each for R and B.
170 * If you have plenty of memory and cycles, 6 bits all around gives marginally
171 * better results; if you are short of memory, 5 bits all around will save
172 * some space but degrade the results.
173 * To maintain a fully accurate histogram, we'd need to allocate a "long"
174 * (preferably unsigned long) for each cell. In practice this is overkill;
175 * we can get by with 16 bits per cell. Few of the cell counts will overflow,
176 * and clamping those that do overflow to the maximum value will give close-
177 * enough results. This reduces the recommended histogram size from 256Kb
178 * to 128Kb, which is a useful savings on PC-class machines.
179 * (In the second pass the histogram space is re-used for pixel mapping data;
180 * in that capacity, each cell must be able to store zero to the number of
181 * desired colors. 16 bits/cell is plenty for that too.)
182 * Since the JPEG code is intended to run in small memory model on 80x86
183 * machines, we can't just allocate the histogram in one chunk. Instead
184 * of a true 3-D array, we use a row of pointers to 2-D arrays. Each
185 * pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and
186 * each 2-D array has 2^6*2^5 = 2048 or 2^6*2^6 = 4096 entries. Note that
187 * on 80x86 machines, the pointer row is in near memory but the actual
188 * arrays are in far memory (same arrangement as we use for image arrays).
191 #define MAXNUMCOLORS (MAXJSAMPLE+1) /* maximum size of colormap */
193 /* These will do the right thing for either R,G,B or B,G,R color order,
194 * but you may not like the results for other color orders.
196 #define HIST_C0_BITS 5 /* bits of precision in R/B histogram */
197 #define HIST_C1_BITS 6 /* bits of precision in G histogram */
198 #define HIST_C2_BITS 5 /* bits of precision in B/R histogram */
200 /* Number of elements along histogram axes. */
201 #define HIST_C0_ELEMS (1<<HIST_C0_BITS)
202 #define HIST_C1_ELEMS (1<<HIST_C1_BITS)
203 #define HIST_C2_ELEMS (1<<HIST_C2_BITS)
205 /* These are the amounts to shift an input value to get a histogram index. */
206 #define C0_SHIFT (BITS_IN_JSAMPLE-HIST_C0_BITS)
207 #define C1_SHIFT (BITS_IN_JSAMPLE-HIST_C1_BITS)
208 #define C2_SHIFT (BITS_IN_JSAMPLE-HIST_C2_BITS)
211 typedef UINT16 histcell
; /* histogram cell; prefer an unsigned type */
213 typedef histcell
* histptr
; /* for pointers to histogram cells */
215 typedef histcell hist1d
[HIST_C2_ELEMS
]; /* typedefs for the array */
216 typedef hist1d
* hist2d
; /* type for the 2nd-level pointers */
217 typedef hist2d
* hist3d
; /* type for top-level pointer */
220 /* Declarations for Floyd-Steinberg dithering.
222 * Errors are accumulated into the array fserrors[], at a resolution of
223 * 1/16th of a pixel count. The error at a given pixel is propagated
224 * to its not-yet-processed neighbors using the standard F-S fractions,
227 * We work left-to-right on even rows, right-to-left on odd rows.
229 * We can get away with a single array (holding one row's worth of errors)
230 * by using it to store the current row's errors at pixel columns not yet
231 * processed, but the next row's errors at columns already processed. We
232 * need only a few extra variables to hold the errors immediately around the
233 * current column. (If we are lucky, those variables are in registers, but
234 * even if not, they're probably cheaper to access than array elements are.)
236 * The fserrors[] array has (#columns + 2) entries; the extra entry at
237 * each end saves us from special-casing the first and last pixels.
238 * Each entry is three values long, one value for each color component.
240 * Note: on a wide image, we might not have enough room in a PC's near data
241 * segment to hold the error array; so it is allocated with alloc_large.
244 #if BITS_IN_JSAMPLE == 8
245 typedef INT16 FSERROR
; /* 16 bits should be enough */
246 typedef int LOCFSERROR
; /* use 'int' for calculation temps */
248 typedef INT32 FSERROR
; /* may need more than 16 bits */
249 typedef INT32 LOCFSERROR
; /* be sure calculation temps are big enough */
252 typedef FSERROR
*FSERRPTR
; /* pointer to error array (in storage!) */
255 /* Private subobject */
260 void (*finish_pass
)(j_decompress_ptr
);
261 void (*color_quantize
)(j_decompress_ptr
, JSAMPARRAY
, JSAMPARRAY
, int);
262 void (*start_pass
)(j_decompress_ptr
, bool);
263 void (*new_color_map
)(j_decompress_ptr
);
266 /* Space for the eventually created colormap is stashed here */
267 JSAMPARRAY sv_colormap
; /* colormap allocated at init time */
268 int desired
; /* desired # of colors = size of colormap */
270 /* Variables for accumulating image statistics */
271 hist3d histogram
; /* pointer to the histogram */
273 bool needs_zeroed
; /* true if next pass must zero histogram */
275 /* Variables for Floyd-Steinberg dithering */
276 FSERRPTR fserrors
; /* accumulated errors */
277 bool on_odd_row
; /* flag to remember which row we are on */
278 int * error_limiter
; /* table for clamping the applied error */
281 typedef my_cquantizer
* my_cquantize_ptr
;
285 * Prescan some rows of pixels.
286 * In this module the prescan simply updates the histogram, which has been
287 * initialized to zeroes by start_pass.
288 * An output_buf parameter is required by the method signature, but no data
289 * is actually output (in fact the buffer controller is probably passing a
294 prescan_quantize (j_decompress_ptr cinfo
, JSAMPARRAY input_buf
,
295 JSAMPARRAY output_buf
, int num_rows
)
297 my_cquantize_ptr cquantize
= (my_cquantize_ptr
) cinfo
->cquantize
;
298 register JSAMPROW ptr
;
299 register histptr histp
;
300 register hist3d histogram
= cquantize
->histogram
;
303 JDIMENSION width
= cinfo
->output_width
;
305 for (row
= 0; row
< num_rows
; row
++) {
306 ptr
= input_buf
[row
];
307 for (col
= width
; col
> 0; col
--) {
311 /* get pixel value and index into the histogram */
312 histp
= & histogram
[GETJSAMPLE(ptr
[0]) >> C0_SHIFT
]
313 [GETJSAMPLE(ptr
[1]) >> C1_SHIFT
]
314 [GETJSAMPLE(ptr
[2]) >> C2_SHIFT
];
315 /* increment, check for overflow and undo increment if so. */
326 * Next we have the really interesting routines: selection of a colormap
327 * given the completed histogram.
328 * These routines work with a list of "boxes", each representing a rectangular
329 * subset of the input color space (to histogram precision).
333 /* The bounds of the box (inclusive); expressed as histogram indexes */
337 /* The volume (actually 2-norm) of the box */
339 /* The number of nonzero histogram cells within this box */
343 typedef box
* boxptr
;
347 find_biggest_color_pop (boxptr boxlist
, int numboxes
)
348 /* Find the splittable box with the largest color population */
349 /* Returns NULL if no splittable boxes remain */
351 register boxptr boxp
;
353 register long maxc
= 0;
356 for (i
= 0, boxp
= boxlist
; i
< numboxes
; i
++, boxp
++) {
357 if (boxp
->colorcount
> maxc
&& boxp
->volume
> 0) {
359 maxc
= boxp
->colorcount
;
367 find_biggest_volume (boxptr boxlist
, int numboxes
)
368 /* Find the splittable box with the largest (scaled) volume */
369 /* Returns NULL if no splittable boxes remain */
371 register boxptr boxp
;
373 register INT32 maxv
= 0;
376 for (i
= 0, boxp
= boxlist
; i
< numboxes
; i
++, boxp
++) {
377 if (boxp
->volume
> maxv
) {
387 update_box (j_decompress_ptr cinfo
, boxptr boxp
)
388 /* Shrink the min/max bounds of a box to enclose only nonzero elements, */
389 /* and recompute its volume and population */
391 my_cquantize_ptr cquantize
= (my_cquantize_ptr
) cinfo
->cquantize
;
392 hist3d histogram
= cquantize
->histogram
;
395 int c0min
,c0max
,c1min
,c1max
,c2min
,c2max
;
396 INT32 dist0
,dist1
,dist2
;
399 c0min
= boxp
->c0min
; c0max
= boxp
->c0max
;
400 c1min
= boxp
->c1min
; c1max
= boxp
->c1max
;
401 c2min
= boxp
->c2min
; c2max
= boxp
->c2max
;
404 for (c0
= c0min
; c0
<= c0max
; c0
++)
405 for (c1
= c1min
; c1
<= c1max
; c1
++) {
406 histp
= & histogram
[c0
][c1
][c2min
];
407 for (c2
= c2min
; c2
<= c2max
; c2
++)
409 boxp
->c0min
= c0min
= c0
;
415 for (c0
= c0max
; c0
>= c0min
; c0
--)
416 for (c1
= c1min
; c1
<= c1max
; c1
++) {
417 histp
= & histogram
[c0
][c1
][c2min
];
418 for (c2
= c2min
; c2
<= c2max
; c2
++)
420 boxp
->c0max
= c0max
= c0
;
426 for (c1
= c1min
; c1
<= c1max
; c1
++)
427 for (c0
= c0min
; c0
<= c0max
; c0
++) {
428 histp
= & histogram
[c0
][c1
][c2min
];
429 for (c2
= c2min
; c2
<= c2max
; c2
++)
431 boxp
->c1min
= c1min
= c1
;
437 for (c1
= c1max
; c1
>= c1min
; c1
--)
438 for (c0
= c0min
; c0
<= c0max
; c0
++) {
439 histp
= & histogram
[c0
][c1
][c2min
];
440 for (c2
= c2min
; c2
<= c2max
; c2
++)
442 boxp
->c1max
= c1max
= c1
;
448 for (c2
= c2min
; c2
<= c2max
; c2
++)
449 for (c0
= c0min
; c0
<= c0max
; c0
++) {
450 histp
= & histogram
[c0
][c1min
][c2
];
451 for (c1
= c1min
; c1
<= c1max
; c1
++, histp
+= HIST_C2_ELEMS
)
453 boxp
->c2min
= c2min
= c2
;
459 for (c2
= c2max
; c2
>= c2min
; c2
--)
460 for (c0
= c0min
; c0
<= c0max
; c0
++) {
461 histp
= & histogram
[c0
][c1min
][c2
];
462 for (c1
= c1min
; c1
<= c1max
; c1
++, histp
+= HIST_C2_ELEMS
)
464 boxp
->c2max
= c2max
= c2
;
470 /* Update box volume.
471 * We use 2-norm rather than real volume here; this biases the method
472 * against making long narrow boxes, and it has the side benefit that
473 * a box is splittable iff norm > 0.
474 * Since the differences are expressed in histogram-cell units,
475 * we have to shift back to JSAMPLE units to get consistent distances;
476 * after which, we scale according to the selected distance scale factors.
478 dist0
= ((c0max
- c0min
) << C0_SHIFT
) * C0_SCALE
;
479 dist1
= ((c1max
- c1min
) << C1_SHIFT
) * C1_SCALE
;
480 dist2
= ((c2max
- c2min
) << C2_SHIFT
) * C2_SCALE
;
481 boxp
->volume
= dist0
*dist0
+ dist1
*dist1
+ dist2
*dist2
;
483 /* Now scan remaining volume of box and compute population */
485 for (c0
= c0min
; c0
<= c0max
; c0
++)
486 for (c1
= c1min
; c1
<= c1max
; c1
++) {
487 histp
= & histogram
[c0
][c1
][c2min
];
488 for (c2
= c2min
; c2
<= c2max
; c2
++, histp
++)
493 boxp
->colorcount
= ccount
;
498 median_cut (j_decompress_ptr cinfo
, boxptr boxlist
, int numboxes
,
500 /* Repeatedly select and split the largest box until we have enough boxes */
504 register boxptr b1
,b2
;
506 while (numboxes
< desired_colors
) {
507 /* Select box to split.
508 * Current algorithm: by population for first half, then by volume.
510 if (numboxes
*2 <= desired_colors
) {
511 b1
= find_biggest_color_pop(boxlist
, numboxes
);
513 b1
= find_biggest_volume(boxlist
, numboxes
);
515 if (b1
== NULL
) /* no splittable boxes left! */
517 b2
= &boxlist
[numboxes
]; /* where new box will go */
518 /* Copy the color bounds to the new box. */
519 b2
->c0max
= b1
->c0max
; b2
->c1max
= b1
->c1max
; b2
->c2max
= b1
->c2max
;
520 b2
->c0min
= b1
->c0min
; b2
->c1min
= b1
->c1min
; b2
->c2min
= b1
->c2min
;
521 /* Choose which axis to split the box on.
522 * Current algorithm: longest scaled axis.
523 * See notes in update_box about scaling distances.
525 c0
= ((b1
->c0max
- b1
->c0min
) << C0_SHIFT
) * C0_SCALE
;
526 c1
= ((b1
->c1max
- b1
->c1min
) << C1_SHIFT
) * C1_SCALE
;
527 c2
= ((b1
->c2max
- b1
->c2min
) << C2_SHIFT
) * C2_SCALE
;
528 /* We want to break any ties in favor of green, then red, blue last.
529 * This code does the right thing for R,G,B or B,G,R color orders only.
533 if (c0
> cmax
) { cmax
= c0
; n
= 0; }
534 if (c2
> cmax
) { n
= 2; }
537 if (c2
> cmax
) { cmax
= c2
; n
= 2; }
538 if (c0
> cmax
) { n
= 0; }
540 /* Choose split point along selected axis, and update box bounds.
541 * Current algorithm: split at halfway point.
542 * (Since the box has been shrunk to minimum volume,
543 * any split will produce two nonempty subboxes.)
544 * Note that lb value is max for lower box, so must be < old max.
548 lb
= (b1
->c0max
+ b1
->c0min
) / 2;
553 lb
= (b1
->c1max
+ b1
->c1min
) / 2;
558 lb
= (b1
->c2max
+ b1
->c2min
) / 2;
563 /* Update stats for boxes */
564 update_box(cinfo
, b1
);
565 update_box(cinfo
, b2
);
573 compute_color (j_decompress_ptr cinfo
, boxptr boxp
, int icolor
)
574 /* Compute representative color for a box, put it in colormap[icolor] */
576 /* Current algorithm: mean weighted by pixels (not colors) */
577 /* Note it is important to get the rounding correct! */
578 my_cquantize_ptr cquantize
= (my_cquantize_ptr
) cinfo
->cquantize
;
579 hist3d histogram
= cquantize
->histogram
;
582 int c0min
,c0max
,c1min
,c1max
,c2min
,c2max
;
589 c0min
= boxp
->c0min
; c0max
= boxp
->c0max
;
590 c1min
= boxp
->c1min
; c1max
= boxp
->c1max
;
591 c2min
= boxp
->c2min
; c2max
= boxp
->c2max
;
593 for (c0
= c0min
; c0
<= c0max
; c0
++)
594 for (c1
= c1min
; c1
<= c1max
; c1
++) {
595 histp
= & histogram
[c0
][c1
][c2min
];
596 for (c2
= c2min
; c2
<= c2max
; c2
++) {
597 if ((count
= *histp
++) != 0) {
599 c0total
+= ((c0
<< C0_SHIFT
) + ((1<<C0_SHIFT
)>>1)) * count
;
600 c1total
+= ((c1
<< C1_SHIFT
) + ((1<<C1_SHIFT
)>>1)) * count
;
601 c2total
+= ((c2
<< C2_SHIFT
) + ((1<<C2_SHIFT
)>>1)) * count
;
606 cinfo
->colormap
[0][icolor
] = (JSAMPLE
) ((c0total
+ (total
>>1)) / total
);
607 cinfo
->colormap
[1][icolor
] = (JSAMPLE
) ((c1total
+ (total
>>1)) / total
);
608 cinfo
->colormap
[2][icolor
] = (JSAMPLE
) ((c2total
+ (total
>>1)) / total
);
613 select_colors (j_decompress_ptr cinfo
, int desired_colors
)
614 /* Master routine for color selection */
620 /* Allocate workspace for box list */
621 boxlist
= (boxptr
) malloc(desired_colors
* sizeof(box
));
622 /* Initialize one box containing whole space */
624 boxlist
[0].c0min
= 0;
625 boxlist
[0].c0max
= MAXJSAMPLE
>> C0_SHIFT
;
626 boxlist
[0].c1min
= 0;
627 boxlist
[0].c1max
= MAXJSAMPLE
>> C1_SHIFT
;
628 boxlist
[0].c2min
= 0;
629 boxlist
[0].c2max
= MAXJSAMPLE
>> C2_SHIFT
;
630 /* Shrink it to actually-used volume and set its statistics */
631 update_box(cinfo
, & boxlist
[0]);
632 /* Perform median-cut to produce final box list */
633 numboxes
= median_cut(cinfo
, boxlist
, numboxes
, desired_colors
);
634 /* Compute the representative color for each box, fill colormap */
635 for (i
= 0; i
< numboxes
; i
++)
636 compute_color(cinfo
, & boxlist
[i
], i
);
637 cinfo
->actual_number_of_colors
= numboxes
;
639 free(boxlist
); //FIXME?? I don't know if this is correct - VS
644 * These routines are concerned with the time-critical task of mapping input
645 * colors to the nearest color in the selected colormap.
647 * We re-use the histogram space as an "inverse color map", essentially a
648 * cache for the results of nearest-color searches. All colors within a
649 * histogram cell will be mapped to the same colormap entry, namely the one
650 * closest to the cell's center. This may not be quite the closest entry to
651 * the actual input color, but it's almost as good. A zero in the cache
652 * indicates we haven't found the nearest color for that cell yet; the array
653 * is cleared to zeroes before starting the mapping pass. When we find the
654 * nearest color for a cell, its colormap index plus one is recorded in the
655 * cache for future use. The pass2 scanning routines call fill_inverse_cmap
656 * when they need to use an unfilled entry in the cache.
658 * Our method of efficiently finding nearest colors is based on the "locally
659 * sorted search" idea described by Heckbert and on the incremental distance
660 * calculation described by Spencer W. Thomas in chapter III.1 of Graphics
661 * Gems II (James Arvo, ed. Academic Press, 1991). Thomas points out that
662 * the distances from a given colormap entry to each cell of the histogram can
663 * be computed quickly using an incremental method: the differences between
664 * distances to adjacent cells themselves differ by a constant. This allows a
665 * fairly fast implementation of the "brute force" approach of computing the
666 * distance from every colormap entry to every histogram cell. Unfortunately,
667 * it needs a work array to hold the best-distance-so-far for each histogram
668 * cell (because the inner loop has to be over cells, not colormap entries).
669 * The work array elements have to be INT32s, so the work array would need
670 * 256Kb at our recommended precision. This is not feasible in DOS machines.
672 * To get around these problems, we apply Thomas' method to compute the
673 * nearest colors for only the cells within a small subbox of the histogram.
674 * The work array need be only as big as the subbox, so the memory usage
675 * problem is solved. Furthermore, we need not fill subboxes that are never
676 * referenced in pass2; many images use only part of the color gamut, so a
677 * fair amount of work is saved. An additional advantage of this
678 * approach is that we can apply Heckbert's locality criterion to quickly
679 * eliminate colormap entries that are far away from the subbox; typically
680 * three-fourths of the colormap entries are rejected by Heckbert's criterion,
681 * and we need not compute their distances to individual cells in the subbox.
682 * The speed of this approach is heavily influenced by the subbox size: too
683 * small means too much overhead, too big loses because Heckbert's criterion
684 * can't eliminate as many colormap entries. Empirically the best subbox
685 * size seems to be about 1/512th of the histogram (1/8th in each direction).
687 * Thomas' article also describes a refined method which is asymptotically
688 * faster than the brute-force method, but it is also far more complex and
689 * cannot efficiently be applied to small subboxes. It is therefore not
690 * useful for programs intended to be portable to DOS machines. On machines
691 * with plenty of memory, filling the whole histogram in one shot with Thomas'
692 * refined method might be faster than the present code --- but then again,
693 * it might not be any faster, and it's certainly more complicated.
697 /* log2(histogram cells in update box) for each axis; this can be adjusted */
698 #define BOX_C0_LOG (HIST_C0_BITS-3)
699 #define BOX_C1_LOG (HIST_C1_BITS-3)
700 #define BOX_C2_LOG (HIST_C2_BITS-3)
702 #define BOX_C0_ELEMS (1<<BOX_C0_LOG) /* # of hist cells in update box */
703 #define BOX_C1_ELEMS (1<<BOX_C1_LOG)
704 #define BOX_C2_ELEMS (1<<BOX_C2_LOG)
706 #define BOX_C0_SHIFT (C0_SHIFT + BOX_C0_LOG)
707 #define BOX_C1_SHIFT (C1_SHIFT + BOX_C1_LOG)
708 #define BOX_C2_SHIFT (C2_SHIFT + BOX_C2_LOG)
712 * The next three routines implement inverse colormap filling. They could
713 * all be folded into one big routine, but splitting them up this way saves
714 * some stack space (the mindist[] and bestdist[] arrays need not coexist)
715 * and may allow some compilers to produce better code by registerizing more
716 * inner-loop variables.
720 find_nearby_colors (j_decompress_ptr cinfo
, int minc0
, int minc1
, int minc2
,
722 /* Locate the colormap entries close enough to an update box to be candidates
723 * for the nearest entry to some cell(s) in the update box. The update box
724 * is specified by the center coordinates of its first cell. The number of
725 * candidate colormap entries is returned, and their colormap indexes are
726 * placed in colorlist[].
727 * This routine uses Heckbert's "locally sorted search" criterion to select
728 * the colors that need further consideration.
731 int numcolors
= cinfo
->actual_number_of_colors
;
732 int maxc0
, maxc1
, maxc2
;
733 int centerc0
, centerc1
, centerc2
;
735 INT32 minmaxdist
, min_dist
, max_dist
, tdist
;
736 INT32 mindist
[MAXNUMCOLORS
]; /* min distance to colormap entry i */
738 /* Compute true coordinates of update box's upper corner and center.
739 * Actually we compute the coordinates of the center of the upper-corner
740 * histogram cell, which are the upper bounds of the volume we care about.
741 * Note that since ">>" rounds down, the "center" values may be closer to
742 * min than to max; hence comparisons to them must be "<=", not "<".
744 maxc0
= minc0
+ ((1 << BOX_C0_SHIFT
) - (1 << C0_SHIFT
));
745 centerc0
= (minc0
+ maxc0
) >> 1;
746 maxc1
= minc1
+ ((1 << BOX_C1_SHIFT
) - (1 << C1_SHIFT
));
747 centerc1
= (minc1
+ maxc1
) >> 1;
748 maxc2
= minc2
+ ((1 << BOX_C2_SHIFT
) - (1 << C2_SHIFT
));
749 centerc2
= (minc2
+ maxc2
) >> 1;
751 /* For each color in colormap, find:
752 * 1. its minimum squared-distance to any point in the update box
753 * (zero if color is within update box);
754 * 2. its maximum squared-distance to any point in the update box.
755 * Both of these can be found by considering only the corners of the box.
756 * We save the minimum distance for each color in mindist[];
757 * only the smallest maximum distance is of interest.
759 minmaxdist
= 0x7FFFFFFFL
;
761 for (i
= 0; i
< numcolors
; i
++) {
762 /* We compute the squared-c0-distance term, then add in the other two. */
763 x
= GETJSAMPLE(cinfo
->colormap
[0][i
]);
765 tdist
= (x
- minc0
) * C0_SCALE
;
766 min_dist
= tdist
*tdist
;
767 tdist
= (x
- maxc0
) * C0_SCALE
;
768 max_dist
= tdist
*tdist
;
769 } else if (x
> maxc0
) {
770 tdist
= (x
- maxc0
) * C0_SCALE
;
771 min_dist
= tdist
*tdist
;
772 tdist
= (x
- minc0
) * C0_SCALE
;
773 max_dist
= tdist
*tdist
;
775 /* within cell range so no contribution to min_dist */
778 tdist
= (x
- maxc0
) * C0_SCALE
;
779 max_dist
= tdist
*tdist
;
781 tdist
= (x
- minc0
) * C0_SCALE
;
782 max_dist
= tdist
*tdist
;
786 x
= GETJSAMPLE(cinfo
->colormap
[1][i
]);
788 tdist
= (x
- minc1
) * C1_SCALE
;
789 min_dist
+= tdist
*tdist
;
790 tdist
= (x
- maxc1
) * C1_SCALE
;
791 max_dist
+= tdist
*tdist
;
792 } else if (x
> maxc1
) {
793 tdist
= (x
- maxc1
) * C1_SCALE
;
794 min_dist
+= tdist
*tdist
;
795 tdist
= (x
- minc1
) * C1_SCALE
;
796 max_dist
+= tdist
*tdist
;
798 /* within cell range so no contribution to min_dist */
800 tdist
= (x
- maxc1
) * C1_SCALE
;
801 max_dist
+= tdist
*tdist
;
803 tdist
= (x
- minc1
) * C1_SCALE
;
804 max_dist
+= tdist
*tdist
;
808 x
= GETJSAMPLE(cinfo
->colormap
[2][i
]);
810 tdist
= (x
- minc2
) * C2_SCALE
;
811 min_dist
+= tdist
*tdist
;
812 tdist
= (x
- maxc2
) * C2_SCALE
;
813 max_dist
+= tdist
*tdist
;
814 } else if (x
> maxc2
) {
815 tdist
= (x
- maxc2
) * C2_SCALE
;
816 min_dist
+= tdist
*tdist
;
817 tdist
= (x
- minc2
) * C2_SCALE
;
818 max_dist
+= tdist
*tdist
;
820 /* within cell range so no contribution to min_dist */
822 tdist
= (x
- maxc2
) * C2_SCALE
;
823 max_dist
+= tdist
*tdist
;
825 tdist
= (x
- minc2
) * C2_SCALE
;
826 max_dist
+= tdist
*tdist
;
830 mindist
[i
] = min_dist
; /* save away the results */
831 if (max_dist
< minmaxdist
)
832 minmaxdist
= max_dist
;
835 /* Now we know that no cell in the update box is more than minmaxdist
836 * away from some colormap entry. Therefore, only colors that are
837 * within minmaxdist of some part of the box need be considered.
840 for (i
= 0; i
< numcolors
; i
++) {
841 if (mindist
[i
] <= minmaxdist
)
842 colorlist
[ncolors
++] = (JSAMPLE
) i
;
849 find_best_colors (j_decompress_ptr cinfo
, int minc0
, int minc1
, int minc2
,
850 int numcolors
, JSAMPLE colorlist
[], JSAMPLE bestcolor
[])
851 /* Find the closest colormap entry for each cell in the update box,
852 * given the list of candidate colors prepared by find_nearby_colors.
853 * Return the indexes of the closest entries in the bestcolor[] array.
854 * This routine uses Thomas' incremental distance calculation method to
855 * find the distance from a colormap entry to successive cells in the box.
860 register INT32
* bptr
; /* pointer into bestdist[] array */
861 JSAMPLE
* cptr
; /* pointer into bestcolor[] array */
862 INT32 dist0
, dist1
; /* initial distance values */
863 register INT32 dist2
; /* current distance in inner loop */
864 INT32 xx0
, xx1
; /* distance increments */
866 INT32 inc0
, inc1
, inc2
; /* initial values for increments */
867 /* This array holds the distance to the nearest-so-far color for each cell */
868 INT32 bestdist
[BOX_C0_ELEMS
* BOX_C1_ELEMS
* BOX_C2_ELEMS
];
870 /* Initialize best-distance for each cell of the update box */
872 for (i
= BOX_C0_ELEMS
*BOX_C1_ELEMS
*BOX_C2_ELEMS
-1; i
>= 0; i
--)
873 *bptr
++ = 0x7FFFFFFFL
;
875 /* For each color selected by find_nearby_colors,
876 * compute its distance to the center of each cell in the box.
877 * If that's less than best-so-far, update best distance and color number.
880 /* Nominal steps between cell centers ("x" in Thomas article) */
881 #define STEP_C0 ((1 << C0_SHIFT) * C0_SCALE)
882 #define STEP_C1 ((1 << C1_SHIFT) * C1_SCALE)
883 #define STEP_C2 ((1 << C2_SHIFT) * C2_SCALE)
885 for (i
= 0; i
< numcolors
; i
++) {
886 icolor
= GETJSAMPLE(colorlist
[i
]);
887 /* Compute (square of) distance from minc0/c1/c2 to this color */
888 inc0
= (minc0
- GETJSAMPLE(cinfo
->colormap
[0][icolor
])) * C0_SCALE
;
890 inc1
= (minc1
- GETJSAMPLE(cinfo
->colormap
[1][icolor
])) * C1_SCALE
;
892 inc2
= (minc2
- GETJSAMPLE(cinfo
->colormap
[2][icolor
])) * C2_SCALE
;
894 /* Form the initial difference increments */
895 inc0
= inc0
* (2 * STEP_C0
) + STEP_C0
* STEP_C0
;
896 inc1
= inc1
* (2 * STEP_C1
) + STEP_C1
* STEP_C1
;
897 inc2
= inc2
* (2 * STEP_C2
) + STEP_C2
* STEP_C2
;
898 /* Now loop over all cells in box, updating distance per Thomas method */
902 for (ic0
= BOX_C0_ELEMS
-1; ic0
>= 0; ic0
--) {
905 for (ic1
= BOX_C1_ELEMS
-1; ic1
>= 0; ic1
--) {
908 for (ic2
= BOX_C2_ELEMS
-1; ic2
>= 0; ic2
--) {
911 *cptr
= (JSAMPLE
) icolor
;
914 xx2
+= 2 * STEP_C2
* STEP_C2
;
919 xx1
+= 2 * STEP_C1
* STEP_C1
;
922 xx0
+= 2 * STEP_C0
* STEP_C0
;
929 fill_inverse_cmap (j_decompress_ptr cinfo
, int c0
, int c1
, int c2
)
930 /* Fill the inverse-colormap entries in the update box that contains */
931 /* histogram cell c0/c1/c2. (Only that one cell MUST be filled, but */
932 /* we can fill as many others as we wish.) */
934 my_cquantize_ptr cquantize
= (my_cquantize_ptr
) cinfo
->cquantize
;
935 hist3d histogram
= cquantize
->histogram
;
936 int minc0
, minc1
, minc2
; /* lower left corner of update box */
938 register JSAMPLE
* cptr
; /* pointer into bestcolor[] array */
939 register histptr cachep
; /* pointer into main cache array */
940 /* This array lists the candidate colormap indexes. */
941 JSAMPLE colorlist
[MAXNUMCOLORS
];
942 int numcolors
; /* number of candidate colors */
943 /* This array holds the actually closest colormap index for each cell. */
944 JSAMPLE bestcolor
[BOX_C0_ELEMS
* BOX_C1_ELEMS
* BOX_C2_ELEMS
];
946 /* Convert cell coordinates to update box ID */
951 /* Compute true coordinates of update box's origin corner.
952 * Actually we compute the coordinates of the center of the corner
953 * histogram cell, which are the lower bounds of the volume we care about.
955 minc0
= (c0
<< BOX_C0_SHIFT
) + ((1 << C0_SHIFT
) >> 1);
956 minc1
= (c1
<< BOX_C1_SHIFT
) + ((1 << C1_SHIFT
) >> 1);
957 minc2
= (c2
<< BOX_C2_SHIFT
) + ((1 << C2_SHIFT
) >> 1);
959 /* Determine which colormap entries are close enough to be candidates
960 * for the nearest entry to some cell in the update box.
962 numcolors
= find_nearby_colors(cinfo
, minc0
, minc1
, minc2
, colorlist
);
964 /* Determine the actually nearest colors. */
965 find_best_colors(cinfo
, minc0
, minc1
, minc2
, numcolors
, colorlist
,
968 /* Save the best color numbers (plus 1) in the main cache array */
969 c0
<<= BOX_C0_LOG
; /* convert ID back to base cell indexes */
973 for (ic0
= 0; ic0
< BOX_C0_ELEMS
; ic0
++) {
974 for (ic1
= 0; ic1
< BOX_C1_ELEMS
; ic1
++) {
975 cachep
= & histogram
[c0
+ic0
][c1
+ic1
][c2
];
976 for (ic2
= 0; ic2
< BOX_C2_ELEMS
; ic2
++) {
977 *cachep
++ = (histcell
) (GETJSAMPLE(*cptr
++) + 1);
985 * Map some rows of pixels to the output colormapped representation.
989 pass2_no_dither (j_decompress_ptr cinfo
,
990 JSAMPARRAY input_buf
, JSAMPARRAY output_buf
, int num_rows
)
991 /* This version performs no dithering */
993 my_cquantize_ptr cquantize
= (my_cquantize_ptr
) cinfo
->cquantize
;
994 hist3d histogram
= cquantize
->histogram
;
995 register JSAMPROW inptr
, outptr
;
996 register histptr cachep
;
997 register int c0
, c1
, c2
;
1000 JDIMENSION width
= cinfo
->output_width
;
1002 for (row
= 0; row
< num_rows
; row
++) {
1003 inptr
= input_buf
[row
];
1004 outptr
= output_buf
[row
];
1005 for (col
= width
; col
> 0; col
--) {
1006 /* get pixel value and index into the cache */
1007 c0
= GETJSAMPLE(*inptr
++) >> C0_SHIFT
;
1008 c1
= GETJSAMPLE(*inptr
++) >> C1_SHIFT
;
1009 c2
= GETJSAMPLE(*inptr
++) >> C2_SHIFT
;
1010 cachep
= & histogram
[c0
][c1
][c2
];
1011 /* If we have not seen this color before, find nearest colormap entry */
1012 /* and update the cache */
1014 fill_inverse_cmap(cinfo
, c0
,c1
,c2
);
1015 /* Now emit the colormap index for this cell */
1016 *outptr
++ = (JSAMPLE
) (*cachep
- 1);
1023 pass2_fs_dither (j_decompress_ptr cinfo
,
1024 JSAMPARRAY input_buf
, JSAMPARRAY output_buf
, int num_rows
)
1025 /* This version performs Floyd-Steinberg dithering */
1027 my_cquantize_ptr cquantize
= (my_cquantize_ptr
) cinfo
->cquantize
;
1028 hist3d histogram
= cquantize
->histogram
;
1029 register LOCFSERROR cur0
, cur1
, cur2
; /* current error or pixel value */
1030 LOCFSERROR belowerr0
, belowerr1
, belowerr2
; /* error for pixel below cur */
1031 LOCFSERROR bpreverr0
, bpreverr1
, bpreverr2
; /* error for below/prev col */
1032 register FSERRPTR errorptr
; /* => fserrors[] at column before current */
1033 JSAMPROW inptr
; /* => current input pixel */
1034 JSAMPROW outptr
; /* => current output pixel */
1036 int dir
; /* +1 or -1 depending on direction */
1037 int dir3
; /* 3*dir, for advancing inptr & errorptr */
1040 JDIMENSION width
= cinfo
->output_width
;
1041 JSAMPLE
*range_limit
= cinfo
->sample_range_limit
;
1042 int *error_limit
= cquantize
->error_limiter
;
1043 JSAMPROW colormap0
= cinfo
->colormap
[0];
1044 JSAMPROW colormap1
= cinfo
->colormap
[1];
1045 JSAMPROW colormap2
= cinfo
->colormap
[2];
1048 for (row
= 0; row
< num_rows
; row
++) {
1049 inptr
= input_buf
[row
];
1050 outptr
= output_buf
[row
];
1051 if (cquantize
->on_odd_row
) {
1052 /* work right to left in this row */
1053 inptr
+= (width
-1) * 3; /* so point to rightmost pixel */
1057 errorptr
= cquantize
->fserrors
+ (width
+1)*3; /* => entry after last column */
1058 cquantize
->on_odd_row
= false; /* flip for next time */
1060 /* work left to right in this row */
1063 errorptr
= cquantize
->fserrors
; /* => entry before first real column */
1064 cquantize
->on_odd_row
= true; /* flip for next time */
1066 /* Preset error values: no error propagated to first pixel from left */
1067 cur0
= cur1
= cur2
= 0;
1068 /* and no error propagated to row below yet */
1069 belowerr0
= belowerr1
= belowerr2
= 0;
1070 bpreverr0
= bpreverr1
= bpreverr2
= 0;
1072 for (col
= width
; col
> 0; col
--) {
1073 /* curN holds the error propagated from the previous pixel on the
1074 * current line. Add the error propagated from the previous line
1075 * to form the complete error correction term for this pixel, and
1076 * round the error term (which is expressed * 16) to an integer.
1077 * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct
1078 * for either sign of the error value.
1079 * Note: errorptr points to *previous* column's array entry.
1081 cur0
= RIGHT_SHIFT(cur0
+ errorptr
[dir3
+0] + 8, 4);
1082 cur1
= RIGHT_SHIFT(cur1
+ errorptr
[dir3
+1] + 8, 4);
1083 cur2
= RIGHT_SHIFT(cur2
+ errorptr
[dir3
+2] + 8, 4);
1084 /* Limit the error using transfer function set by init_error_limit.
1085 * See comments with init_error_limit for rationale.
1087 cur0
= error_limit
[cur0
];
1088 cur1
= error_limit
[cur1
];
1089 cur2
= error_limit
[cur2
];
1090 /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE.
1091 * The maximum error is +- MAXJSAMPLE (or less with error limiting);
1092 * this sets the required size of the range_limit array.
1094 cur0
+= GETJSAMPLE(inptr
[0]);
1095 cur1
+= GETJSAMPLE(inptr
[1]);
1096 cur2
+= GETJSAMPLE(inptr
[2]);
1097 cur0
= GETJSAMPLE(range_limit
[cur0
]);
1098 cur1
= GETJSAMPLE(range_limit
[cur1
]);
1099 cur2
= GETJSAMPLE(range_limit
[cur2
]);
1100 /* Index into the cache with adjusted pixel value */
1101 cachep
= & histogram
[cur0
>>C0_SHIFT
][cur1
>>C1_SHIFT
][cur2
>>C2_SHIFT
];
1102 /* If we have not seen this color before, find nearest colormap */
1103 /* entry and update the cache */
1105 fill_inverse_cmap(cinfo
, cur0
>>C0_SHIFT
,cur1
>>C1_SHIFT
,cur2
>>C2_SHIFT
);
1106 /* Now emit the colormap index for this cell */
1107 { register int pixcode
= *cachep
- 1;
1108 *outptr
= (JSAMPLE
) pixcode
;
1109 /* Compute representation error for this pixel */
1110 cur0
-= GETJSAMPLE(colormap0
[pixcode
]);
1111 cur1
-= GETJSAMPLE(colormap1
[pixcode
]);
1112 cur2
-= GETJSAMPLE(colormap2
[pixcode
]);
1114 /* Compute error fractions to be propagated to adjacent pixels.
1115 * Add these into the running sums, and simultaneously shift the
1116 * next-line error sums left by 1 column.
1118 { register LOCFSERROR bnexterr
, delta
;
1120 bnexterr
= cur0
; /* Process component 0 */
1122 cur0
+= delta
; /* form error * 3 */
1123 errorptr
[0] = (FSERROR
) (bpreverr0
+ cur0
);
1124 cur0
+= delta
; /* form error * 5 */
1125 bpreverr0
= belowerr0
+ cur0
;
1126 belowerr0
= bnexterr
;
1127 cur0
+= delta
; /* form error * 7 */
1128 bnexterr
= cur1
; /* Process component 1 */
1130 cur1
+= delta
; /* form error * 3 */
1131 errorptr
[1] = (FSERROR
) (bpreverr1
+ cur1
);
1132 cur1
+= delta
; /* form error * 5 */
1133 bpreverr1
= belowerr1
+ cur1
;
1134 belowerr1
= bnexterr
;
1135 cur1
+= delta
; /* form error * 7 */
1136 bnexterr
= cur2
; /* Process component 2 */
1138 cur2
+= delta
; /* form error * 3 */
1139 errorptr
[2] = (FSERROR
) (bpreverr2
+ cur2
);
1140 cur2
+= delta
; /* form error * 5 */
1141 bpreverr2
= belowerr2
+ cur2
;
1142 belowerr2
= bnexterr
;
1143 cur2
+= delta
; /* form error * 7 */
1145 /* At this point curN contains the 7/16 error value to be propagated
1146 * to the next pixel on the current line, and all the errors for the
1147 * next line have been shifted over. We are therefore ready to move on.
1149 inptr
+= dir3
; /* Advance pixel pointers to next column */
1151 errorptr
+= dir3
; /* advance errorptr to current column */
1153 /* Post-loop cleanup: we must unload the final error values into the
1154 * final fserrors[] entry. Note we need not unload belowerrN because
1155 * it is for the dummy column before or after the actual array.
1157 errorptr
[0] = (FSERROR
) bpreverr0
; /* unload prev errs into array */
1158 errorptr
[1] = (FSERROR
) bpreverr1
;
1159 errorptr
[2] = (FSERROR
) bpreverr2
;
1165 * Initialize the error-limiting transfer function (lookup table).
1166 * The raw F-S error computation can potentially compute error values of up to
1167 * +- MAXJSAMPLE. But we want the maximum correction applied to a pixel to be
1168 * much less, otherwise obviously wrong pixels will be created. (Typical
1169 * effects include weird fringes at color-area boundaries, isolated bright
1170 * pixels in a dark area, etc.) The standard advice for avoiding this problem
1171 * is to ensure that the "corners" of the color cube are allocated as output
1172 * colors; then repeated errors in the same direction cannot cause cascading
1173 * error buildup. However, that only prevents the error from getting
1174 * completely out of hand; Aaron Giles reports that error limiting improves
1175 * the results even with corner colors allocated.
1176 * A simple clamping of the error values to about +- MAXJSAMPLE/8 works pretty
1177 * well, but the smoother transfer function used below is even better. Thanks
1178 * to Aaron Giles for this idea.
1182 init_error_limit (j_decompress_ptr cinfo
)
1183 /* Allocate and fill in the error_limiter table */
1185 my_cquantize_ptr cquantize
= (my_cquantize_ptr
) cinfo
->cquantize
;
1189 table
= (int *) malloc((MAXJSAMPLE
*2+1) * sizeof(int));
1190 table
+= MAXJSAMPLE
; /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */
1191 cquantize
->error_limiter
= table
;
1193 #define STEPSIZE ((MAXJSAMPLE+1)/16)
1194 /* Map errors 1:1 up to +- MAXJSAMPLE/16 */
1196 for (in
= 0; in
< STEPSIZE
; in
++, out
++) {
1197 table
[in
] = out
; table
[-in
] = -out
;
1199 /* Map errors 1:2 up to +- 3*MAXJSAMPLE/16 */
1200 for (; in
< STEPSIZE
*3; in
++, out
+= (in
&1) ? 0 : 1) {
1201 table
[in
] = out
; table
[-in
] = -out
;
1203 /* Clamp the rest to final out value (which is (MAXJSAMPLE+1)/8) */
1204 for (; in
<= MAXJSAMPLE
; in
++) {
1205 table
[in
] = out
; table
[-in
] = -out
;
1212 * Finish up at the end of each pass.
1216 finish_pass1 (j_decompress_ptr cinfo
)
1218 my_cquantize_ptr cquantize
= (my_cquantize_ptr
) cinfo
->cquantize
;
1220 /* Select the representative colors and fill in cinfo->colormap */
1221 cinfo
->colormap
= cquantize
->sv_colormap
;
1222 select_colors(cinfo
, cquantize
->desired
);
1223 /* Force next pass to zero the color index table */
1224 cquantize
->needs_zeroed
= true;
1229 finish_pass2 (j_decompress_ptr cinfo
)
1236 * Initialize for each processing pass.
1240 start_pass_2_quant (j_decompress_ptr cinfo
, bool is_pre_scan
)
1242 my_cquantize_ptr cquantize
= (my_cquantize_ptr
) cinfo
->cquantize
;
1243 hist3d histogram
= cquantize
->histogram
;
1247 /* Set up method pointers */
1248 cquantize
->pub
.color_quantize
= prescan_quantize
;
1249 cquantize
->pub
.finish_pass
= finish_pass1
;
1250 cquantize
->needs_zeroed
= true; /* Always zero histogram */
1252 /* Set up method pointers */
1253 cquantize
->pub
.color_quantize
= pass2_fs_dither
;
1254 cquantize
->pub
.finish_pass
= finish_pass2
;
1256 /* Make sure color count is acceptable */
1257 i
= cinfo
->actual_number_of_colors
;
1260 size_t arraysize
= (size_t) ((cinfo
->output_width
+ 2) *
1261 (3 * sizeof(FSERROR
)));
1262 /* Allocate Floyd-Steinberg workspace if we didn't already. */
1263 if (cquantize
->fserrors
== NULL
)
1264 cquantize
->fserrors
= (INT16
*) malloc(arraysize
);
1265 /* Initialize the propagated errors to zero. */
1266 memset((void *) cquantize
->fserrors
, 0, arraysize
);
1267 /* Make the error-limit table if we didn't already. */
1268 if (cquantize
->error_limiter
== NULL
)
1269 init_error_limit(cinfo
);
1270 cquantize
->on_odd_row
= false;
1274 /* Zero the histogram or inverse color map, if necessary */
1275 if (cquantize
->needs_zeroed
) {
1276 for (i
= 0; i
< HIST_C0_ELEMS
; i
++) {
1277 memset((void *) histogram
[i
], 0,
1278 HIST_C1_ELEMS
*HIST_C2_ELEMS
* sizeof(histcell
));
1280 cquantize
->needs_zeroed
= false;
1286 * Switch to a new external colormap between output passes.
1290 new_color_map_2_quant (j_decompress_ptr cinfo
)
1292 my_cquantize_ptr cquantize
= (my_cquantize_ptr
) cinfo
->cquantize
;
1294 /* Reset the inverse color map */
1295 cquantize
->needs_zeroed
= true;
1300 * Module initialization routine for 2-pass color quantization.
1304 jinit_2pass_quantizer (j_decompress_ptr cinfo
)
1306 my_cquantize_ptr cquantize
;
1309 cquantize
= (my_cquantize_ptr
) malloc(sizeof(my_cquantizer
));
1310 cinfo
->cquantize
= (struct jpeg_color_quantizer
*) cquantize
;
1311 cquantize
->pub
.start_pass
= start_pass_2_quant
;
1312 cquantize
->pub
.new_color_map
= new_color_map_2_quant
;
1313 cquantize
->fserrors
= NULL
; /* flag optional arrays not allocated */
1314 cquantize
->error_limiter
= NULL
;
1317 /* Allocate the histogram/inverse colormap storage */
1318 cquantize
->histogram
= (hist3d
) malloc(HIST_C0_ELEMS
* sizeof(hist2d
));
1319 for (i
= 0; i
< HIST_C0_ELEMS
; i
++) {
1320 cquantize
->histogram
[i
] = (hist2d
) malloc(HIST_C1_ELEMS
*HIST_C2_ELEMS
* sizeof(histcell
));
1322 cquantize
->needs_zeroed
= true; /* histogram is garbage now */
1324 /* Allocate storage for the completed colormap, if required.
1325 * We do this now since it is storage and may affect
1326 * the memory manager's space calculations.
1329 /* Make sure color count is acceptable */
1330 int desired
= cinfo
->desired_number_of_colors
;
1332 cquantize
->sv_colormap
= (JSAMPARRAY
) malloc(sizeof(JSAMPROW
) * 3);
1333 cquantize
->sv_colormap
[0] = (JSAMPROW
) malloc(sizeof(JSAMPLE
) * desired
);
1334 cquantize
->sv_colormap
[1] = (JSAMPROW
) malloc(sizeof(JSAMPLE
) * desired
);
1335 cquantize
->sv_colormap
[2] = (JSAMPROW
) malloc(sizeof(JSAMPLE
) * desired
);
1337 cquantize
->desired
= desired
;
1340 /* Allocate Floyd-Steinberg workspace if necessary.
1341 * This isn't really needed until pass 2, but again it is storage.
1342 * Although we will cope with a later change in dither_mode,
1343 * we do not promise to honor max_memory_to_use if dither_mode changes.
1346 cquantize
->fserrors
= (FSERRPTR
) malloc(
1347 (size_t) ((cinfo
->output_width
+ 2) * (3 * sizeof(FSERROR
))));
1348 /* Might as well create the error-limiting table too. */
1349 init_error_limit(cinfo
);
1363 prepare_range_limit_table (j_decompress_ptr cinfo
)
1364 /* Allocate and fill in the sample_range_limit table */
1369 table
= (JSAMPLE
*) malloc((5 * (MAXJSAMPLE
+1) + CENTERJSAMPLE
) * sizeof(JSAMPLE
));
1370 cinfo
->srl_orig
= table
;
1371 table
+= (MAXJSAMPLE
+1); /* allow negative subscripts of simple table */
1372 cinfo
->sample_range_limit
= table
;
1373 /* First segment of "simple" table: limit[x] = 0 for x < 0 */
1374 memset(table
- (MAXJSAMPLE
+1), 0, (MAXJSAMPLE
+1) * sizeof(JSAMPLE
));
1375 /* Main part of "simple" table: limit[x] = x */
1376 for (i
= 0; i
<= MAXJSAMPLE
; i
++)
1377 table
[i
] = (JSAMPLE
) i
;
1378 table
+= CENTERJSAMPLE
; /* Point to where post-IDCT table starts */
1379 /* End of simple table, rest of first half of post-IDCT table */
1380 for (i
= CENTERJSAMPLE
; i
< 2*(MAXJSAMPLE
+1); i
++)
1381 table
[i
] = MAXJSAMPLE
;
1382 /* Second half of post-IDCT table */
1383 memset(table
+ (2 * (MAXJSAMPLE
+1)), 0,
1384 (2 * (MAXJSAMPLE
+1) - CENTERJSAMPLE
) * sizeof(JSAMPLE
));
1385 memcpy(table
+ (4 * (MAXJSAMPLE
+1) - CENTERJSAMPLE
),
1386 cinfo
->sample_range_limit
, CENTERJSAMPLE
* sizeof(JSAMPLE
));
1396 IMPLEMENT_DYNAMIC_CLASS(wxQuantize
, wxObject
)
1398 void wxQuantize::DoQuantize(unsigned w
, unsigned h
, unsigned char **in_rows
, unsigned char **out_rows
,
1399 unsigned char *palette
, int desiredNoColours
)
1402 my_cquantize_ptr cquantize
;
1404 dec
.output_width
= w
;
1405 dec
.desired_number_of_colors
= desiredNoColours
;
1406 prepare_range_limit_table(&dec
);
1407 jinit_2pass_quantizer(&dec
);
1408 cquantize
= (my_cquantize_ptr
) dec
.cquantize
;
1411 cquantize
->pub
.start_pass(&dec
, true);
1412 cquantize
->pub
.color_quantize(&dec
, in_rows
, out_rows
, h
);
1413 cquantize
->pub
.finish_pass(&dec
);
1415 cquantize
->pub
.start_pass(&dec
, false);
1416 cquantize
->pub
.color_quantize(&dec
, in_rows
, out_rows
, h
);
1417 cquantize
->pub
.finish_pass(&dec
);
1420 for (int i
= 0; i
< dec
.desired_number_of_colors
; i
++) {
1421 palette
[3 * i
+ 0] = dec
.colormap
[0][i
];
1422 palette
[3 * i
+ 1] = dec
.colormap
[1][i
];
1423 palette
[3 * i
+ 2] = dec
.colormap
[2][i
];
1426 for (int ii
= 0; ii
< HIST_C0_ELEMS
; ii
++) free(cquantize
->histogram
[ii
]);
1427 free(cquantize
->histogram
);
1428 free(dec
.colormap
[0]);
1429 free(dec
.colormap
[1]);
1430 free(dec
.colormap
[2]);
1434 //free(cquantize->error_limiter);
1435 free((void*)(cquantize
->error_limiter
- MAXJSAMPLE
)); // To reverse what was done to it
1437 free(cquantize
->fserrors
);
1441 // TODO: somehow make use of the Windows system colours, rather than ignoring them for the
1442 // purposes of quantization.
1444 bool wxQuantize::Quantize(const wxImage
& src
, wxImage
& dest
, wxPalette
** pPalette
, int desiredNoColours
,
1445 unsigned char** eightBitData
, int flags
)
1449 int w
= src
.GetWidth();
1450 int h
= src
.GetHeight();
1452 int windowsSystemColourCount
= 20;
1453 int paletteShift
= 0;
1455 // Shift the palette up by the number of Windows system colours,
1457 if (flags
& wxQUANTIZE_INCLUDE_WINDOWS_COLOURS
)
1458 paletteShift
= windowsSystemColourCount
;
1460 // Make room for the Windows system colours
1462 if ((flags
& wxQUANTIZE_INCLUDE_WINDOWS_COLOURS
) && (desiredNoColours
> (256 - windowsSystemColourCount
)))
1463 desiredNoColours
= 256 - windowsSystemColourCount
;
1466 // create rows info:
1467 unsigned char **rows
= new unsigned char *[h
];
1468 h
= src
.GetHeight(), w
= src
.GetWidth();
1469 unsigned char *imgdt
= src
.GetData();
1470 for (i
= 0; i
< h
; i
++)
1471 rows
[i
] = imgdt
+ 3/*RGB*/ * w
* i
;
1473 unsigned char palette
[3*256];
1475 // This is the image as represented by palette indexes.
1476 unsigned char *data8bit
= new unsigned char[w
* h
];
1477 unsigned char **outrows
= new unsigned char *[h
];
1478 for (i
= 0; i
< h
; i
++)
1479 outrows
[i
] = data8bit
+ w
* i
;
1482 DoQuantize(w
, h
, rows
, outrows
, palette
, desiredNoColours
);
1487 // palette->RGB(max.256)
1489 if (flags
& wxQUANTIZE_FILL_DESTINATION_IMAGE
)
1494 imgdt
= dest
.GetData();
1495 for (i
= 0; i
< w
* h
; i
++)
1497 unsigned char c
= data8bit
[i
];
1498 imgdt
[3 * i
+ 0/*R*/] = palette
[3 * c
+ 0];
1499 imgdt
[3 * i
+ 1/*G*/] = palette
[3 * c
+ 1];
1500 imgdt
[3 * i
+ 2/*B*/] = palette
[3 * c
+ 2];
1504 if (eightBitData
&& (flags
& wxQUANTIZE_RETURN_8BIT_DATA
))
1507 if (flags
& wxQUANTIZE_INCLUDE_WINDOWS_COLOURS
)
1509 // We need to shift the palette entries up
1510 // to make room for the Windows system colours.
1511 for (i
= 0; i
< w
* h
; i
++)
1512 data8bit
[i
] = data8bit
[i
] + paletteShift
;
1515 *eightBitData
= data8bit
;
1520 // Make a wxWindows palette
1523 unsigned char* r
= new unsigned char[256];
1524 unsigned char* g
= new unsigned char[256];
1525 unsigned char* b
= new unsigned char[256];
1528 // Fill the first 20 entries with Windows system colours
1529 if (flags
& wxQUANTIZE_INCLUDE_WINDOWS_COLOURS
)
1531 HDC hDC
= ::GetDC(NULL
);
1532 PALETTEENTRY
* entries
= new PALETTEENTRY
[windowsSystemColourCount
];
1533 ::GetSystemPaletteEntries(hDC
, 0, windowsSystemColourCount
, entries
);
1534 ::ReleaseDC(NULL
, hDC
);
1536 for (i
= 0; i
< windowsSystemColourCount
; i
++)
1538 r
[i
] = entries
[i
].peRed
;
1539 g
[i
] = entries
[i
].peGreen
;
1540 b
[i
] = entries
[i
].peBlue
;
1546 for (i
= 0; i
< desiredNoColours
; i
++)
1548 r
[i
+paletteShift
] = palette
[i
*3 + 0];
1549 g
[i
+paletteShift
] = palette
[i
*3 + 1];
1550 b
[i
+paletteShift
] = palette
[i
*3 + 2];
1553 // Blank out any remaining palette entries
1554 for (i
= desiredNoColours
+paletteShift
; i
< 256; i
++)
1560 *pPalette
= new wxPalette(256, r
, g
, b
);
1569 // This version sets a palette in the destination image so you don't
1570 // have to manage it yourself.
1572 bool wxQuantize::Quantize(const wxImage
& src
, wxImage
& dest
, int desiredNoColours
,
1573 unsigned char** eightBitData
, int flags
)
1575 wxPalette
* palette
= NULL
;
1576 if (Quantize(src
, dest
, & palette
, desiredNoColours
, eightBitData
, flags
))
1580 dest
.SetPalette(* palette
);