1 | /* |
---|
2 | * jquant2.c |
---|
3 | * |
---|
4 | * Copyright (C) 1991-1996, Thomas G. Lane. |
---|
5 | * This file is part of the Independent JPEG Group's software. |
---|
6 | * For conditions of distribution and use, see the accompanying README file. |
---|
7 | * |
---|
8 | * This file contains 2-pass color quantization (color mapping) routines. |
---|
9 | * These routines provide selection of a custom color map for an image, |
---|
10 | * followed by mapping of the image to that color map, with optional |
---|
11 | * Floyd-Steinberg dithering. |
---|
12 | * It is also possible to use just the second pass to map to an arbitrary |
---|
13 | * externally-given color map. |
---|
14 | * |
---|
15 | * Note: ordered dithering is not supported, since there isn't any fast |
---|
16 | * way to compute intercolor distances; it's unclear that ordered dither's |
---|
17 | * fundamental assumptions even hold with an irregularly spaced color map. |
---|
18 | */ |
---|
19 | |
---|
20 | #define JPEG_INTERNALS |
---|
21 | #include "jinclude.h" |
---|
22 | #include "jpeglib.h" |
---|
23 | |
---|
24 | #ifdef QUANT_2PASS_SUPPORTED |
---|
25 | |
---|
26 | |
---|
27 | /* |
---|
28 | * This module implements the well-known Heckbert paradigm for color |
---|
29 | * quantization. Most of the ideas used here can be traced back to |
---|
30 | * Heckbert's seminal paper |
---|
31 | * Heckbert, Paul. "Color Image Quantization for Frame Buffer Display", |
---|
32 | * Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304. |
---|
33 | * |
---|
34 | * In the first pass over the image, we accumulate a histogram showing the |
---|
35 | * usage count of each possible color. To keep the histogram to a reasonable |
---|
36 | * size, we reduce the precision of the input; typical practice is to retain |
---|
37 | * 5 or 6 bits per color, so that 8 or 4 different input values are counted |
---|
38 | * in the same histogram cell. |
---|
39 | * |
---|
40 | * Next, the color-selection step begins with a box representing the whole |
---|
41 | * color space, and repeatedly splits the "largest" remaining box until we |
---|
42 | * have as many boxes as desired colors. Then the mean color in each |
---|
43 | * remaining box becomes one of the possible output colors. |
---|
44 | * |
---|
45 | * The second pass over the image maps each input pixel to the closest output |
---|
46 | * color (optionally after applying a Floyd-Steinberg dithering correction). |
---|
47 | * This mapping is logically trivial, but making it go fast enough requires |
---|
48 | * considerable care. |
---|
49 | * |
---|
50 | * Heckbert-style quantizers vary a good deal in their policies for choosing |
---|
51 | * the "largest" box and deciding where to cut it. The particular policies |
---|
52 | * used here have proved out well in experimental comparisons, but better ones |
---|
53 | * may yet be found. |
---|
54 | * |
---|
55 | * In earlier versions of the IJG code, this module quantized in YCbCr color |
---|
56 | * space, processing the raw upsampled data without a color conversion step. |
---|
57 | * This allowed the color conversion math to be done only once per colormap |
---|
58 | * entry, not once per pixel. However, that optimization precluded other |
---|
59 | * useful optimizations (such as merging color conversion with upsampling) |
---|
60 | * and it also interfered with desired capabilities such as quantizing to an |
---|
61 | * externally-supplied colormap. We have therefore abandoned that approach. |
---|
62 | * The present code works in the post-conversion color space, typically RGB. |
---|
63 | * |
---|
64 | * To improve the visual quality of the results, we actually work in scaled |
---|
65 | * RGB space, giving G distances more weight than R, and R in turn more than |
---|
66 | * B. To do everything in integer math, we must use integer scale factors. |
---|
67 | * The 2/3/1 scale factors used here correspond loosely to the relative |
---|
68 | * weights of the colors in the NTSC grayscale equation. |
---|
69 | * If you want to use this code to quantize a non-RGB color space, you'll |
---|
70 | * probably need to change these scale factors. |
---|
71 | */ |
---|
72 | |
---|
73 | #define R_SCALE 2 /* scale R distances by this much */ |
---|
74 | #define G_SCALE 3 /* scale G distances by this much */ |
---|
75 | #define B_SCALE 1 /* and B by this much */ |
---|
76 | |
---|
77 | /* Relabel R/G/B as components 0/1/2, respecting the RGB ordering defined |
---|
78 | * in jmorecfg.h. As the code stands, it will do the right thing for R,G,B |
---|
79 | * and B,G,R orders. If you define some other weird order in jmorecfg.h, |
---|
80 | * you'll get compile errors until you extend this logic. In that case |
---|
81 | * you'll probably want to tweak the histogram sizes too. |
---|
82 | */ |
---|
83 | |
---|
84 | #if RGB_RED == 0 |
---|
85 | #define C0_SCALE R_SCALE |
---|
86 | #endif |
---|
87 | #if RGB_BLUE == 0 |
---|
88 | #define C0_SCALE B_SCALE |
---|
89 | #endif |
---|
90 | #if RGB_GREEN == 1 |
---|
91 | #define C1_SCALE G_SCALE |
---|
92 | #endif |
---|
93 | #if RGB_RED == 2 |
---|
94 | #define C2_SCALE R_SCALE |
---|
95 | #endif |
---|
96 | #if RGB_BLUE == 2 |
---|
97 | #define C2_SCALE B_SCALE |
---|
98 | #endif |
---|
99 | |
---|
100 | |
---|
101 | /* |
---|
102 | * First we have the histogram data structure and routines for creating it. |
---|
103 | * |
---|
104 | * The number of bits of precision can be adjusted by changing these symbols. |
---|
105 | * We recommend keeping 6 bits for G and 5 each for R and B. |
---|
106 | * If you have plenty of memory and cycles, 6 bits all around gives marginally |
---|
107 | * better results; if you are short of memory, 5 bits all around will save |
---|
108 | * some space but degrade the results. |
---|
109 | * To maintain a fully accurate histogram, we'd need to allocate a "long" |
---|
110 | * (preferably unsigned long) for each cell. In practice this is overkill; |
---|
111 | * we can get by with 16 bits per cell. Few of the cell counts will overflow, |
---|
112 | * and clamping those that do overflow to the maximum value will give close- |
---|
113 | * enough results. This reduces the recommended histogram size from 256Kb |
---|
114 | * to 128Kb, which is a useful savings on PC-class machines. |
---|
115 | * (In the second pass the histogram space is re-used for pixel mapping data; |
---|
116 | * in that capacity, each cell must be able to store zero to the number of |
---|
117 | * desired colors. 16 bits/cell is plenty for that too.) |
---|
118 | * Since the JPEG code is intended to run in small memory model on 80x86 |
---|
119 | * machines, we can't just allocate the histogram in one chunk. Instead |
---|
120 | * of a true 3-D array, we use a row of pointers to 2-D arrays. Each |
---|
121 | * pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and |
---|
122 | * each 2-D array has 2^6*2^5 = 2048 or 2^6*2^6 = 4096 entries. Note that |
---|
123 | * on 80x86 machines, the pointer row is in near memory but the actual |
---|
124 | * arrays are in far memory (same arrangement as we use for image arrays). |
---|
125 | */ |
---|
126 | |
---|
127 | #define MAXNUMCOLORS (MAXJSAMPLE+1) /* maximum size of colormap */ |
---|
128 | |
---|
129 | /* These will do the right thing for either R,G,B or B,G,R color order, |
---|
130 | * but you may not like the results for other color orders. |
---|
131 | */ |
---|
132 | #define HIST_C0_BITS 5 /* bits of precision in R/B histogram */ |
---|
133 | #define HIST_C1_BITS 6 /* bits of precision in G histogram */ |
---|
134 | #define HIST_C2_BITS 5 /* bits of precision in B/R histogram */ |
---|
135 | |
---|
136 | /* Number of elements along histogram axes. */ |
---|
137 | #define HIST_C0_ELEMS (1<<HIST_C0_BITS) |
---|
138 | #define HIST_C1_ELEMS (1<<HIST_C1_BITS) |
---|
139 | #define HIST_C2_ELEMS (1<<HIST_C2_BITS) |
---|
140 | |
---|
141 | /* These are the amounts to shift an input value to get a histogram index. */ |
---|
142 | #define C0_SHIFT (BITS_IN_JSAMPLE-HIST_C0_BITS) |
---|
143 | #define C1_SHIFT (BITS_IN_JSAMPLE-HIST_C1_BITS) |
---|
144 | #define C2_SHIFT (BITS_IN_JSAMPLE-HIST_C2_BITS) |
---|
145 | |
---|
146 | |
---|
147 | typedef UINT16 histcell; /* histogram cell; prefer an unsigned type */ |
---|
148 | |
---|
149 | typedef histcell FAR * histptr; /* for pointers to histogram cells */ |
---|
150 | |
---|
151 | typedef histcell hist1d[HIST_C2_ELEMS]; /* typedefs for the array */ |
---|
152 | typedef hist1d FAR * hist2d; /* type for the 2nd-level pointers */ |
---|
153 | typedef hist2d * hist3d; /* type for top-level pointer */ |
---|
154 | |
---|
155 | |
---|
156 | /* Declarations for Floyd-Steinberg dithering. |
---|
157 | * |
---|
158 | * Errors are accumulated into the array fserrors[], at a resolution of |
---|
159 | * 1/16th of a pixel count. The error at a given pixel is propagated |
---|
160 | * to its not-yet-processed neighbors using the standard F-S fractions, |
---|
161 | * ... (here) 7/16 |
---|
162 | * 3/16 5/16 1/16 |
---|
163 | * We work left-to-right on even rows, right-to-left on odd rows. |
---|
164 | * |
---|
165 | * We can get away with a single array (holding one row's worth of errors) |
---|
166 | * by using it to store the current row's errors at pixel columns not yet |
---|
167 | * processed, but the next row's errors at columns already processed. We |
---|
168 | * need only a few extra variables to hold the errors immediately around the |
---|
169 | * current column. (If we are lucky, those variables are in registers, but |
---|
170 | * even if not, they're probably cheaper to access than array elements are.) |
---|
171 | * |
---|
172 | * The fserrors[] array has (#columns + 2) entries; the extra entry at |
---|
173 | * each end saves us from special-casing the first and last pixels. |
---|
174 | * Each entry is three values long, one value for each color component. |
---|
175 | * |
---|
176 | * Note: on a wide image, we might not have enough room in a PC's near data |
---|
177 | * segment to hold the error array; so it is allocated with alloc_large. |
---|
178 | */ |
---|
179 | |
---|
180 | #if BITS_IN_JSAMPLE == 8 |
---|
181 | typedef INT16 FSERROR; /* 16 bits should be enough */ |
---|
182 | typedef int LOCFSERROR; /* use 'int' for calculation temps */ |
---|
183 | #else |
---|
184 | typedef INT32 FSERROR; /* may need more than 16 bits */ |
---|
185 | typedef INT32 LOCFSERROR; /* be sure calculation temps are big enough */ |
---|
186 | #endif |
---|
187 | |
---|
188 | typedef FSERROR FAR *FSERRPTR; /* pointer to error array (in FAR storage!) */ |
---|
189 | |
---|
190 | |
---|
191 | /* Private subobject */ |
---|
192 | |
---|
193 | typedef struct { |
---|
194 | struct jpeg_color_quantizer pub; /* public fields */ |
---|
195 | |
---|
196 | /* Space for the eventually created colormap is stashed here */ |
---|
197 | JSAMPARRAY sv_colormap; /* colormap allocated at init time */ |
---|
198 | int desired; /* desired # of colors = size of colormap */ |
---|
199 | |
---|
200 | /* Variables for accumulating image statistics */ |
---|
201 | hist3d histogram; /* pointer to the histogram */ |
---|
202 | |
---|
203 | boolean needs_zeroed; /* TRUE if next pass must zero histogram */ |
---|
204 | |
---|
205 | /* Variables for Floyd-Steinberg dithering */ |
---|
206 | FSERRPTR fserrors; /* accumulated errors */ |
---|
207 | boolean on_odd_row; /* flag to remember which row we are on */ |
---|
208 | int * error_limiter; /* table for clamping the applied error */ |
---|
209 | } my_cquantizer; |
---|
210 | |
---|
211 | typedef my_cquantizer * my_cquantize_ptr; |
---|
212 | |
---|
213 | |
---|
214 | /* |
---|
215 | * Prescan some rows of pixels. |
---|
216 | * In this module the prescan simply updates the histogram, which has been |
---|
217 | * initialized to zeroes by start_pass. |
---|
218 | * An output_buf parameter is required by the method signature, but no data |
---|
219 | * is actually output (in fact the buffer controller is probably passing a |
---|
220 | * NULL pointer). |
---|
221 | */ |
---|
222 | |
---|
223 | METHODDEF(void) |
---|
224 | prescan_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf, |
---|
225 | JSAMPARRAY output_buf, int num_rows) |
---|
226 | { |
---|
227 | my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; |
---|
228 | register JSAMPROW ptr; |
---|
229 | register histptr histp; |
---|
230 | register hist3d histogram = cquantize->histogram; |
---|
231 | int row; |
---|
232 | JDIMENSION col; |
---|
233 | JDIMENSION width = cinfo->output_width; |
---|
234 | |
---|
235 | for (row = 0; row < num_rows; row++) { |
---|
236 | ptr = input_buf[row]; |
---|
237 | for (col = width; col > 0; col--) { |
---|
238 | /* get pixel value and index into the histogram */ |
---|
239 | histp = & histogram[GETJSAMPLE(ptr[0]) >> C0_SHIFT] |
---|
240 | [GETJSAMPLE(ptr[1]) >> C1_SHIFT] |
---|
241 | [GETJSAMPLE(ptr[2]) >> C2_SHIFT]; |
---|
242 | /* increment, check for overflow and undo increment if so. */ |
---|
243 | if (++(*histp) <= 0) |
---|
244 | (*histp)--; |
---|
245 | ptr += 3; |
---|
246 | } |
---|
247 | } |
---|
248 | } |
---|
249 | |
---|
250 | |
---|
251 | /* |
---|
252 | * Next we have the really interesting routines: selection of a colormap |
---|
253 | * given the completed histogram. |
---|
254 | * These routines work with a list of "boxes", each representing a rectangular |
---|
255 | * subset of the input color space (to histogram precision). |
---|
256 | */ |
---|
257 | |
---|
258 | typedef struct { |
---|
259 | /* The bounds of the box (inclusive); expressed as histogram indexes */ |
---|
260 | int c0min, c0max; |
---|
261 | int c1min, c1max; |
---|
262 | int c2min, c2max; |
---|
263 | /* The volume (actually 2-norm) of the box */ |
---|
264 | INT32 volume; |
---|
265 | /* The number of nonzero histogram cells within this box */ |
---|
266 | long colorcount; |
---|
267 | } box; |
---|
268 | |
---|
269 | typedef box * boxptr; |
---|
270 | |
---|
271 | |
---|
272 | LOCAL(boxptr) |
---|
273 | find_biggest_color_pop (boxptr boxlist, int numboxes) |
---|
274 | /* Find the splittable box with the largest color population */ |
---|
275 | /* Returns NULL if no splittable boxes remain */ |
---|
276 | { |
---|
277 | register boxptr boxp; |
---|
278 | register int i; |
---|
279 | register long maxc = 0; |
---|
280 | boxptr which = NULL; |
---|
281 | |
---|
282 | for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) { |
---|
283 | if (boxp->colorcount > maxc && boxp->volume > 0) { |
---|
284 | which = boxp; |
---|
285 | maxc = boxp->colorcount; |
---|
286 | } |
---|
287 | } |
---|
288 | return which; |
---|
289 | } |
---|
290 | |
---|
291 | |
---|
292 | LOCAL(boxptr) |
---|
293 | find_biggest_volume (boxptr boxlist, int numboxes) |
---|
294 | /* Find the splittable box with the largest (scaled) volume */ |
---|
295 | /* Returns NULL if no splittable boxes remain */ |
---|
296 | { |
---|
297 | register boxptr boxp; |
---|
298 | register int i; |
---|
299 | register INT32 maxv = 0; |
---|
300 | boxptr which = NULL; |
---|
301 | |
---|
302 | for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) { |
---|
303 | if (boxp->volume > maxv) { |
---|
304 | which = boxp; |
---|
305 | maxv = boxp->volume; |
---|
306 | } |
---|
307 | } |
---|
308 | return which; |
---|
309 | } |
---|
310 | |
---|
311 | |
---|
312 | LOCAL(void) |
---|
313 | update_box (j_decompress_ptr cinfo, boxptr boxp) |
---|
314 | /* Shrink the min/max bounds of a box to enclose only nonzero elements, */ |
---|
315 | /* and recompute its volume and population */ |
---|
316 | { |
---|
317 | my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; |
---|
318 | hist3d histogram = cquantize->histogram; |
---|
319 | histptr histp; |
---|
320 | int c0,c1,c2; |
---|
321 | int c0min,c0max,c1min,c1max,c2min,c2max; |
---|
322 | INT32 dist0,dist1,dist2; |
---|
323 | long ccount; |
---|
324 | |
---|
325 | c0min = boxp->c0min; c0max = boxp->c0max; |
---|
326 | c1min = boxp->c1min; c1max = boxp->c1max; |
---|
327 | c2min = boxp->c2min; c2max = boxp->c2max; |
---|
328 | |
---|
329 | if (c0max > c0min) |
---|
330 | for (c0 = c0min; c0 <= c0max; c0++) |
---|
331 | for (c1 = c1min; c1 <= c1max; c1++) { |
---|
332 | histp = & histogram[c0][c1][c2min]; |
---|
333 | for (c2 = c2min; c2 <= c2max; c2++) |
---|
334 | if (*histp++ != 0) { |
---|
335 | boxp->c0min = c0min = c0; |
---|
336 | goto have_c0min; |
---|
337 | } |
---|
338 | } |
---|
339 | have_c0min: |
---|
340 | if (c0max > c0min) |
---|
341 | for (c0 = c0max; c0 >= c0min; c0--) |
---|
342 | for (c1 = c1min; c1 <= c1max; c1++) { |
---|
343 | histp = & histogram[c0][c1][c2min]; |
---|
344 | for (c2 = c2min; c2 <= c2max; c2++) |
---|
345 | if (*histp++ != 0) { |
---|
346 | boxp->c0max = c0max = c0; |
---|
347 | goto have_c0max; |
---|
348 | } |
---|
349 | } |
---|
350 | have_c0max: |
---|
351 | if (c1max > c1min) |
---|
352 | for (c1 = c1min; c1 <= c1max; c1++) |
---|
353 | for (c0 = c0min; c0 <= c0max; c0++) { |
---|
354 | histp = & histogram[c0][c1][c2min]; |
---|
355 | for (c2 = c2min; c2 <= c2max; c2++) |
---|
356 | if (*histp++ != 0) { |
---|
357 | boxp->c1min = c1min = c1; |
---|
358 | goto have_c1min; |
---|
359 | } |
---|
360 | } |
---|
361 | have_c1min: |
---|
362 | if (c1max > c1min) |
---|
363 | for (c1 = c1max; c1 >= c1min; c1--) |
---|
364 | for (c0 = c0min; c0 <= c0max; c0++) { |
---|
365 | histp = & histogram[c0][c1][c2min]; |
---|
366 | for (c2 = c2min; c2 <= c2max; c2++) |
---|
367 | if (*histp++ != 0) { |
---|
368 | boxp->c1max = c1max = c1; |
---|
369 | goto have_c1max; |
---|
370 | } |
---|
371 | } |
---|
372 | have_c1max: |
---|
373 | if (c2max > c2min) |
---|
374 | for (c2 = c2min; c2 <= c2max; c2++) |
---|
375 | for (c0 = c0min; c0 <= c0max; c0++) { |
---|
376 | histp = & histogram[c0][c1min][c2]; |
---|
377 | for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS) |
---|
378 | if (*histp != 0) { |
---|
379 | boxp->c2min = c2min = c2; |
---|
380 | goto have_c2min; |
---|
381 | } |
---|
382 | } |
---|
383 | have_c2min: |
---|
384 | if (c2max > c2min) |
---|
385 | for (c2 = c2max; c2 >= c2min; c2--) |
---|
386 | for (c0 = c0min; c0 <= c0max; c0++) { |
---|
387 | histp = & histogram[c0][c1min][c2]; |
---|
388 | for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS) |
---|
389 | if (*histp != 0) { |
---|
390 | boxp->c2max = c2max = c2; |
---|
391 | goto have_c2max; |
---|
392 | } |
---|
393 | } |
---|
394 | have_c2max: |
---|
395 | |
---|
396 | /* Update box volume. |
---|
397 | * We use 2-norm rather than real volume here; this biases the method |
---|
398 | * against making long narrow boxes, and it has the side benefit that |
---|
399 | * a box is splittable iff norm > 0. |
---|
400 | * Since the differences are expressed in histogram-cell units, |
---|
401 | * we have to shift back to JSAMPLE units to get consistent distances; |
---|
402 | * after which, we scale according to the selected distance scale factors. |
---|
403 | */ |
---|
404 | dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE; |
---|
405 | dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE; |
---|
406 | dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE; |
---|
407 | boxp->volume = dist0*dist0 + dist1*dist1 + dist2*dist2; |
---|
408 | |
---|
409 | /* Now scan remaining volume of box and compute population */ |
---|
410 | ccount = 0; |
---|
411 | for (c0 = c0min; c0 <= c0max; c0++) |
---|
412 | for (c1 = c1min; c1 <= c1max; c1++) { |
---|
413 | histp = & histogram[c0][c1][c2min]; |
---|
414 | for (c2 = c2min; c2 <= c2max; c2++, histp++) |
---|
415 | if (*histp != 0) { |
---|
416 | ccount++; |
---|
417 | } |
---|
418 | } |
---|
419 | boxp->colorcount = ccount; |
---|
420 | } |
---|
421 | |
---|
422 | |
---|
423 | LOCAL(int) |
---|
424 | median_cut (j_decompress_ptr cinfo, boxptr boxlist, int numboxes, |
---|
425 | int desired_colors) |
---|
426 | /* Repeatedly select and split the largest box until we have enough boxes */ |
---|
427 | { |
---|
428 | int n,lb; |
---|
429 | int c0,c1,c2,cmax; |
---|
430 | register boxptr b1,b2; |
---|
431 | |
---|
432 | while (numboxes < desired_colors) { |
---|
433 | /* Select box to split. |
---|
434 | * Current algorithm: by population for first half, then by volume. |
---|
435 | */ |
---|
436 | if (numboxes*2 <= desired_colors) { |
---|
437 | b1 = find_biggest_color_pop(boxlist, numboxes); |
---|
438 | } else { |
---|
439 | b1 = find_biggest_volume(boxlist, numboxes); |
---|
440 | } |
---|
441 | if (b1 == NULL) /* no splittable boxes left! */ |
---|
442 | break; |
---|
443 | b2 = &boxlist[numboxes]; /* where new box will go */ |
---|
444 | /* Copy the color bounds to the new box. */ |
---|
445 | b2->c0max = b1->c0max; b2->c1max = b1->c1max; b2->c2max = b1->c2max; |
---|
446 | b2->c0min = b1->c0min; b2->c1min = b1->c1min; b2->c2min = b1->c2min; |
---|
447 | /* Choose which axis to split the box on. |
---|
448 | * Current algorithm: longest scaled axis. |
---|
449 | * See notes in update_box about scaling distances. |
---|
450 | */ |
---|
451 | c0 = ((b1->c0max - b1->c0min) << C0_SHIFT) * C0_SCALE; |
---|
452 | c1 = ((b1->c1max - b1->c1min) << C1_SHIFT) * C1_SCALE; |
---|
453 | c2 = ((b1->c2max - b1->c2min) << C2_SHIFT) * C2_SCALE; |
---|
454 | /* We want to break any ties in favor of green, then red, blue last. |
---|
455 | * This code does the right thing for R,G,B or B,G,R color orders only. |
---|
456 | */ |
---|
457 | #if RGB_RED == 0 |
---|
458 | cmax = c1; n = 1; |
---|
459 | if (c0 > cmax) { cmax = c0; n = 0; } |
---|
460 | if (c2 > cmax) { n = 2; } |
---|
461 | #else |
---|
462 | cmax = c1; n = 1; |
---|
463 | if (c2 > cmax) { cmax = c2; n = 2; } |
---|
464 | if (c0 > cmax) { n = 0; } |
---|
465 | #endif |
---|
466 | /* Choose split point along selected axis, and update box bounds. |
---|
467 | * Current algorithm: split at halfway point. |
---|
468 | * (Since the box has been shrunk to minimum volume, |
---|
469 | * any split will produce two nonempty subboxes.) |
---|
470 | * Note that lb value is max for lower box, so must be < old max. |
---|
471 | */ |
---|
472 | switch (n) { |
---|
473 | case 0: |
---|
474 | lb = (b1->c0max + b1->c0min) / 2; |
---|
475 | b1->c0max = lb; |
---|
476 | b2->c0min = lb+1; |
---|
477 | break; |
---|
478 | case 1: |
---|
479 | lb = (b1->c1max + b1->c1min) / 2; |
---|
480 | b1->c1max = lb; |
---|
481 | b2->c1min = lb+1; |
---|
482 | break; |
---|
483 | case 2: |
---|
484 | lb = (b1->c2max + b1->c2min) / 2; |
---|
485 | b1->c2max = lb; |
---|
486 | b2->c2min = lb+1; |
---|
487 | break; |
---|
488 | } |
---|
489 | /* Update stats for boxes */ |
---|
490 | update_box(cinfo, b1); |
---|
491 | update_box(cinfo, b2); |
---|
492 | numboxes++; |
---|
493 | } |
---|
494 | return numboxes; |
---|
495 | } |
---|
496 | |
---|
497 | |
---|
498 | LOCAL(void) |
---|
499 | compute_color (j_decompress_ptr cinfo, boxptr boxp, int icolor) |
---|
500 | /* Compute representative color for a box, put it in colormap[icolor] */ |
---|
501 | { |
---|
502 | /* Current algorithm: mean weighted by pixels (not colors) */ |
---|
503 | /* Note it is important to get the rounding correct! */ |
---|
504 | my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; |
---|
505 | hist3d histogram = cquantize->histogram; |
---|
506 | histptr histp; |
---|
507 | int c0,c1,c2; |
---|
508 | int c0min,c0max,c1min,c1max,c2min,c2max; |
---|
509 | long count; |
---|
510 | long total = 0; |
---|
511 | long c0total = 0; |
---|
512 | long c1total = 0; |
---|
513 | long c2total = 0; |
---|
514 | |
---|
515 | c0min = boxp->c0min; c0max = boxp->c0max; |
---|
516 | c1min = boxp->c1min; c1max = boxp->c1max; |
---|
517 | c2min = boxp->c2min; c2max = boxp->c2max; |
---|
518 | |
---|
519 | for (c0 = c0min; c0 <= c0max; c0++) |
---|
520 | for (c1 = c1min; c1 <= c1max; c1++) { |
---|
521 | histp = & histogram[c0][c1][c2min]; |
---|
522 | for (c2 = c2min; c2 <= c2max; c2++) { |
---|
523 | if ((count = *histp++) != 0) { |
---|
524 | total += count; |
---|
525 | c0total += ((c0 << C0_SHIFT) + ((1<<C0_SHIFT)>>1)) * count; |
---|
526 | c1total += ((c1 << C1_SHIFT) + ((1<<C1_SHIFT)>>1)) * count; |
---|
527 | c2total += ((c2 << C2_SHIFT) + ((1<<C2_SHIFT)>>1)) * count; |
---|
528 | } |
---|
529 | } |
---|
530 | } |
---|
531 | |
---|
532 | cinfo->colormap[0][icolor] = (JSAMPLE) ((c0total + (total>>1)) / total); |
---|
533 | cinfo->colormap[1][icolor] = (JSAMPLE) ((c1total + (total>>1)) / total); |
---|
534 | cinfo->colormap[2][icolor] = (JSAMPLE) ((c2total + (total>>1)) / total); |
---|
535 | } |
---|
536 | |
---|
537 | |
---|
538 | LOCAL(void) |
---|
539 | select_colors (j_decompress_ptr cinfo, int desired_colors) |
---|
540 | /* Master routine for color selection */ |
---|
541 | { |
---|
542 | boxptr boxlist; |
---|
543 | int numboxes; |
---|
544 | int i; |
---|
545 | |
---|
546 | /* Allocate workspace for box list */ |
---|
547 | boxlist = (boxptr) (*cinfo->mem->alloc_small) |
---|
548 | ((j_common_ptr) cinfo, JPOOL_IMAGE, desired_colors * SIZEOF(box)); |
---|
549 | /* Initialize one box containing whole space */ |
---|
550 | numboxes = 1; |
---|
551 | boxlist[0].c0min = 0; |
---|
552 | boxlist[0].c0max = MAXJSAMPLE >> C0_SHIFT; |
---|
553 | boxlist[0].c1min = 0; |
---|
554 | boxlist[0].c1max = MAXJSAMPLE >> C1_SHIFT; |
---|
555 | boxlist[0].c2min = 0; |
---|
556 | boxlist[0].c2max = MAXJSAMPLE >> C2_SHIFT; |
---|
557 | /* Shrink it to actually-used volume and set its statistics */ |
---|
558 | update_box(cinfo, & boxlist[0]); |
---|
559 | /* Perform median-cut to produce final box list */ |
---|
560 | numboxes = median_cut(cinfo, boxlist, numboxes, desired_colors); |
---|
561 | /* Compute the representative color for each box, fill colormap */ |
---|
562 | for (i = 0; i < numboxes; i++) |
---|
563 | compute_color(cinfo, & boxlist[i], i); |
---|
564 | cinfo->actual_number_of_colors = numboxes; |
---|
565 | TRACEMS1(cinfo, 1, JTRC_QUANT_SELECTED, numboxes); |
---|
566 | } |
---|
567 | |
---|
568 | |
---|
569 | /* |
---|
570 | * These routines are concerned with the time-critical task of mapping input |
---|
571 | * colors to the nearest color in the selected colormap. |
---|
572 | * |
---|
573 | * We re-use the histogram space as an "inverse color map", essentially a |
---|
574 | * cache for the results of nearest-color searches. All colors within a |
---|
575 | * histogram cell will be mapped to the same colormap entry, namely the one |
---|
576 | * closest to the cell's center. This may not be quite the closest entry to |
---|
577 | * the actual input color, but it's almost as good. A zero in the cache |
---|
578 | * indicates we haven't found the nearest color for that cell yet; the array |
---|
579 | * is cleared to zeroes before starting the mapping pass. When we find the |
---|
580 | * nearest color for a cell, its colormap index plus one is recorded in the |
---|
581 | * cache for future use. The pass2 scanning routines call fill_inverse_cmap |
---|
582 | * when they need to use an unfilled entry in the cache. |
---|
583 | * |
---|
584 | * Our method of efficiently finding nearest colors is based on the "locally |
---|
585 | * sorted search" idea described by Heckbert and on the incremental distance |
---|
586 | * calculation described by Spencer W. Thomas in chapter III.1 of Graphics |
---|
587 | * Gems II (James Arvo, ed. Academic Press, 1991). Thomas points out that |
---|
588 | * the distances from a given colormap entry to each cell of the histogram can |
---|
589 | * be computed quickly using an incremental method: the differences between |
---|
590 | * distances to adjacent cells themselves differ by a constant. This allows a |
---|
591 | * fairly fast implementation of the "brute force" approach of computing the |
---|
592 | * distance from every colormap entry to every histogram cell. Unfortunately, |
---|
593 | * it needs a work array to hold the best-distance-so-far for each histogram |
---|
594 | * cell (because the inner loop has to be over cells, not colormap entries). |
---|
595 | * The work array elements have to be INT32s, so the work array would need |
---|
596 | * 256Kb at our recommended precision. This is not feasible in DOS machines. |
---|
597 | * |
---|
598 | * To get around these problems, we apply Thomas' method to compute the |
---|
599 | * nearest colors for only the cells within a small subbox of the histogram. |
---|
600 | * The work array need be only as big as the subbox, so the memory usage |
---|
601 | * problem is solved. Furthermore, we need not fill subboxes that are never |
---|
602 | * referenced in pass2; many images use only part of the color gamut, so a |
---|
603 | * fair amount of work is saved. An additional advantage of this |
---|
604 | * approach is that we can apply Heckbert's locality criterion to quickly |
---|
605 | * eliminate colormap entries that are far away from the subbox; typically |
---|
606 | * three-fourths of the colormap entries are rejected by Heckbert's criterion, |
---|
607 | * and we need not compute their distances to individual cells in the subbox. |
---|
608 | * The speed of this approach is heavily influenced by the subbox size: too |
---|
609 | * small means too much overhead, too big loses because Heckbert's criterion |
---|
610 | * can't eliminate as many colormap entries. Empirically the best subbox |
---|
611 | * size seems to be about 1/512th of the histogram (1/8th in each direction). |
---|
612 | * |
---|
613 | * Thomas' article also describes a refined method which is asymptotically |
---|
614 | * faster than the brute-force method, but it is also far more complex and |
---|
615 | * cannot efficiently be applied to small subboxes. It is therefore not |
---|
616 | * useful for programs intended to be portable to DOS machines. On machines |
---|
617 | * with plenty of memory, filling the whole histogram in one shot with Thomas' |
---|
618 | * refined method might be faster than the present code --- but then again, |
---|
619 | * it might not be any faster, and it's certainly more complicated. |
---|
620 | */ |
---|
621 | |
---|
622 | |
---|
623 | /* log2(histogram cells in update box) for each axis; this can be adjusted */ |
---|
624 | #define BOX_C0_LOG (HIST_C0_BITS-3) |
---|
625 | #define BOX_C1_LOG (HIST_C1_BITS-3) |
---|
626 | #define BOX_C2_LOG (HIST_C2_BITS-3) |
---|
627 | |
---|
628 | #define BOX_C0_ELEMS (1<<BOX_C0_LOG) /* # of hist cells in update box */ |
---|
629 | #define BOX_C1_ELEMS (1<<BOX_C1_LOG) |
---|
630 | #define BOX_C2_ELEMS (1<<BOX_C2_LOG) |
---|
631 | |
---|
632 | #define BOX_C0_SHIFT (C0_SHIFT + BOX_C0_LOG) |
---|
633 | #define BOX_C1_SHIFT (C1_SHIFT + BOX_C1_LOG) |
---|
634 | #define BOX_C2_SHIFT (C2_SHIFT + BOX_C2_LOG) |
---|
635 | |
---|
636 | |
---|
637 | /* |
---|
638 | * The next three routines implement inverse colormap filling. They could |
---|
639 | * all be folded into one big routine, but splitting them up this way saves |
---|
640 | * some stack space (the mindist[] and bestdist[] arrays need not coexist) |
---|
641 | * and may allow some compilers to produce better code by registerizing more |
---|
642 | * inner-loop variables. |
---|
643 | */ |
---|
644 | |
---|
645 | LOCAL(int) |
---|
646 | find_nearby_colors (j_decompress_ptr cinfo, int minc0, int minc1, int minc2, |
---|
647 | JSAMPLE colorlist[]) |
---|
648 | /* Locate the colormap entries close enough to an update box to be candidates |
---|
649 | * for the nearest entry to some cell(s) in the update box. The update box |
---|
650 | * is specified by the center coordinates of its first cell. The number of |
---|
651 | * candidate colormap entries is returned, and their colormap indexes are |
---|
652 | * placed in colorlist[]. |
---|
653 | * This routine uses Heckbert's "locally sorted search" criterion to select |
---|
654 | * the colors that need further consideration. |
---|
655 | */ |
---|
656 | { |
---|
657 | int numcolors = cinfo->actual_number_of_colors; |
---|
658 | int maxc0, maxc1, maxc2; |
---|
659 | int centerc0, centerc1, centerc2; |
---|
660 | int i, x, ncolors; |
---|
661 | INT32 minmaxdist, min_dist, max_dist, tdist; |
---|
662 | INT32 mindist[MAXNUMCOLORS]; /* min distance to colormap entry i */ |
---|
663 | |
---|
664 | /* Compute true coordinates of update box's upper corner and center. |
---|
665 | * Actually we compute the coordinates of the center of the upper-corner |
---|
666 | * histogram cell, which are the upper bounds of the volume we care about. |
---|
667 | * Note that since ">>" rounds down, the "center" values may be closer to |
---|
668 | * min than to max; hence comparisons to them must be "<=", not "<". |
---|
669 | */ |
---|
670 | maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT)); |
---|
671 | centerc0 = (minc0 + maxc0) >> 1; |
---|
672 | maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT)); |
---|
673 | centerc1 = (minc1 + maxc1) >> 1; |
---|
674 | maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT)); |
---|
675 | centerc2 = (minc2 + maxc2) >> 1; |
---|
676 | |
---|
677 | /* For each color in colormap, find: |
---|
678 | * 1. its minimum squared-distance to any point in the update box |
---|
679 | * (zero if color is within update box); |
---|
680 | * 2. its maximum squared-distance to any point in the update box. |
---|
681 | * Both of these can be found by considering only the corners of the box. |
---|
682 | * We save the minimum distance for each color in mindist[]; |
---|
683 | * only the smallest maximum distance is of interest. |
---|
684 | */ |
---|
685 | minmaxdist = 0x7FFFFFFFL; |
---|
686 | |
---|
687 | for (i = 0; i < numcolors; i++) { |
---|
688 | /* We compute the squared-c0-distance term, then add in the other two. */ |
---|
689 | x = GETJSAMPLE(cinfo->colormap[0][i]); |
---|
690 | if (x < minc0) { |
---|
691 | tdist = (x - minc0) * C0_SCALE; |
---|
692 | min_dist = tdist*tdist; |
---|
693 | tdist = (x - maxc0) * C0_SCALE; |
---|
694 | max_dist = tdist*tdist; |
---|
695 | } else if (x > maxc0) { |
---|
696 | tdist = (x - maxc0) * C0_SCALE; |
---|
697 | min_dist = tdist*tdist; |
---|
698 | tdist = (x - minc0) * C0_SCALE; |
---|
699 | max_dist = tdist*tdist; |
---|
700 | } else { |
---|
701 | /* within cell range so no contribution to min_dist */ |
---|
702 | min_dist = 0; |
---|
703 | if (x <= centerc0) { |
---|
704 | tdist = (x - maxc0) * C0_SCALE; |
---|
705 | max_dist = tdist*tdist; |
---|
706 | } else { |
---|
707 | tdist = (x - minc0) * C0_SCALE; |
---|
708 | max_dist = tdist*tdist; |
---|
709 | } |
---|
710 | } |
---|
711 | |
---|
712 | x = GETJSAMPLE(cinfo->colormap[1][i]); |
---|
713 | if (x < minc1) { |
---|
714 | tdist = (x - minc1) * C1_SCALE; |
---|
715 | min_dist += tdist*tdist; |
---|
716 | tdist = (x - maxc1) * C1_SCALE; |
---|
717 | max_dist += tdist*tdist; |
---|
718 | } else if (x > maxc1) { |
---|
719 | tdist = (x - maxc1) * C1_SCALE; |
---|
720 | min_dist += tdist*tdist; |
---|
721 | tdist = (x - minc1) * C1_SCALE; |
---|
722 | max_dist += tdist*tdist; |
---|
723 | } else { |
---|
724 | /* within cell range so no contribution to min_dist */ |
---|
725 | if (x <= centerc1) { |
---|
726 | tdist = (x - maxc1) * C1_SCALE; |
---|
727 | max_dist += tdist*tdist; |
---|
728 | } else { |
---|
729 | tdist = (x - minc1) * C1_SCALE; |
---|
730 | max_dist += tdist*tdist; |
---|
731 | } |
---|
732 | } |
---|
733 | |
---|
734 | x = GETJSAMPLE(cinfo->colormap[2][i]); |
---|
735 | if (x < minc2) { |
---|
736 | tdist = (x - minc2) * C2_SCALE; |
---|
737 | min_dist += tdist*tdist; |
---|
738 | tdist = (x - maxc2) * C2_SCALE; |
---|
739 | max_dist += tdist*tdist; |
---|
740 | } else if (x > maxc2) { |
---|
741 | tdist = (x - maxc2) * C2_SCALE; |
---|
742 | min_dist += tdist*tdist; |
---|
743 | tdist = (x - minc2) * C2_SCALE; |
---|
744 | max_dist += tdist*tdist; |
---|
745 | } else { |
---|
746 | /* within cell range so no contribution to min_dist */ |
---|
747 | if (x <= centerc2) { |
---|
748 | tdist = (x - maxc2) * C2_SCALE; |
---|
749 | max_dist += tdist*tdist; |
---|
750 | } else { |
---|
751 | tdist = (x - minc2) * C2_SCALE; |
---|
752 | max_dist += tdist*tdist; |
---|
753 | } |
---|
754 | } |
---|
755 | |
---|
756 | mindist[i] = min_dist; /* save away the results */ |
---|
757 | if (max_dist < minmaxdist) |
---|
758 | minmaxdist = max_dist; |
---|
759 | } |
---|
760 | |
---|
761 | /* Now we know that no cell in the update box is more than minmaxdist |
---|
762 | * away from some colormap entry. Therefore, only colors that are |
---|
763 | * within minmaxdist of some part of the box need be considered. |
---|
764 | */ |
---|
765 | ncolors = 0; |
---|
766 | for (i = 0; i < numcolors; i++) { |
---|
767 | if (mindist[i] <= minmaxdist) |
---|
768 | colorlist[ncolors++] = (JSAMPLE) i; |
---|
769 | } |
---|
770 | return ncolors; |
---|
771 | } |
---|
772 | |
---|
773 | |
---|
774 | LOCAL(void) |
---|
775 | find_best_colors (j_decompress_ptr cinfo, int minc0, int minc1, int minc2, |
---|
776 | int numcolors, JSAMPLE colorlist[], JSAMPLE bestcolor[]) |
---|
777 | /* Find the closest colormap entry for each cell in the update box, |
---|
778 | * given the list of candidate colors prepared by find_nearby_colors. |
---|
779 | * Return the indexes of the closest entries in the bestcolor[] array. |
---|
780 | * This routine uses Thomas' incremental distance calculation method to |
---|
781 | * find the distance from a colormap entry to successive cells in the box. |
---|
782 | */ |
---|
783 | { |
---|
784 | int ic0, ic1, ic2; |
---|
785 | int i, icolor; |
---|
786 | register INT32 * bptr; /* pointer into bestdist[] array */ |
---|
787 | JSAMPLE * cptr; /* pointer into bestcolor[] array */ |
---|
788 | INT32 dist0, dist1; /* initial distance values */ |
---|
789 | register INT32 dist2; /* current distance in inner loop */ |
---|
790 | INT32 xx0, xx1; /* distance increments */ |
---|
791 | register INT32 xx2; |
---|
792 | INT32 inc0, inc1, inc2; /* initial values for increments */ |
---|
793 | /* This array holds the distance to the nearest-so-far color for each cell */ |
---|
794 | INT32 bestdist[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS]; |
---|
795 | |
---|
796 | /* Initialize best-distance for each cell of the update box */ |
---|
797 | bptr = bestdist; |
---|
798 | for (i = BOX_C0_ELEMS*BOX_C1_ELEMS*BOX_C2_ELEMS-1; i >= 0; i--) |
---|
799 | *bptr++ = 0x7FFFFFFFL; |
---|
800 | |
---|
801 | /* For each color selected by find_nearby_colors, |
---|
802 | * compute its distance to the center of each cell in the box. |
---|
803 | * If that's less than best-so-far, update best distance and color number. |
---|
804 | */ |
---|
805 | |
---|
806 | /* Nominal steps between cell centers ("x" in Thomas article) */ |
---|
807 | #define STEP_C0 ((1 << C0_SHIFT) * C0_SCALE) |
---|
808 | #define STEP_C1 ((1 << C1_SHIFT) * C1_SCALE) |
---|
809 | #define STEP_C2 ((1 << C2_SHIFT) * C2_SCALE) |
---|
810 | |
---|
811 | for (i = 0; i < numcolors; i++) { |
---|
812 | icolor = GETJSAMPLE(colorlist[i]); |
---|
813 | /* Compute (square of) distance from minc0/c1/c2 to this color */ |
---|
814 | inc0 = (minc0 - GETJSAMPLE(cinfo->colormap[0][icolor])) * C0_SCALE; |
---|
815 | dist0 = inc0*inc0; |
---|
816 | inc1 = (minc1 - GETJSAMPLE(cinfo->colormap[1][icolor])) * C1_SCALE; |
---|
817 | dist0 += inc1*inc1; |
---|
818 | inc2 = (minc2 - GETJSAMPLE(cinfo->colormap[2][icolor])) * C2_SCALE; |
---|
819 | dist0 += inc2*inc2; |
---|
820 | /* Form the initial difference increments */ |
---|
821 | inc0 = inc0 * (2 * STEP_C0) + STEP_C0 * STEP_C0; |
---|
822 | inc1 = inc1 * (2 * STEP_C1) + STEP_C1 * STEP_C1; |
---|
823 | inc2 = inc2 * (2 * STEP_C2) + STEP_C2 * STEP_C2; |
---|
824 | /* Now loop over all cells in box, updating distance per Thomas method */ |
---|
825 | bptr = bestdist; |
---|
826 | cptr = bestcolor; |
---|
827 | xx0 = inc0; |
---|
828 | for (ic0 = BOX_C0_ELEMS-1; ic0 >= 0; ic0--) { |
---|
829 | dist1 = dist0; |
---|
830 | xx1 = inc1; |
---|
831 | for (ic1 = BOX_C1_ELEMS-1; ic1 >= 0; ic1--) { |
---|
832 | dist2 = dist1; |
---|
833 | xx2 = inc2; |
---|
834 | for (ic2 = BOX_C2_ELEMS-1; ic2 >= 0; ic2--) { |
---|
835 | if (dist2 < *bptr) { |
---|
836 | *bptr = dist2; |
---|
837 | *cptr = (JSAMPLE) icolor; |
---|
838 | } |
---|
839 | dist2 += xx2; |
---|
840 | xx2 += 2 * STEP_C2 * STEP_C2; |
---|
841 | bptr++; |
---|
842 | cptr++; |
---|
843 | } |
---|
844 | dist1 += xx1; |
---|
845 | xx1 += 2 * STEP_C1 * STEP_C1; |
---|
846 | } |
---|
847 | dist0 += xx0; |
---|
848 | xx0 += 2 * STEP_C0 * STEP_C0; |
---|
849 | } |
---|
850 | } |
---|
851 | } |
---|
852 | |
---|
853 | |
---|
854 | LOCAL(void) |
---|
855 | fill_inverse_cmap (j_decompress_ptr cinfo, int c0, int c1, int c2) |
---|
856 | /* Fill the inverse-colormap entries in the update box that contains */ |
---|
857 | /* histogram cell c0/c1/c2. (Only that one cell MUST be filled, but */ |
---|
858 | /* we can fill as many others as we wish.) */ |
---|
859 | { |
---|
860 | my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; |
---|
861 | hist3d histogram = cquantize->histogram; |
---|
862 | int minc0, minc1, minc2; /* lower left corner of update box */ |
---|
863 | int ic0, ic1, ic2; |
---|
864 | register JSAMPLE * cptr; /* pointer into bestcolor[] array */ |
---|
865 | register histptr cachep; /* pointer into main cache array */ |
---|
866 | /* This array lists the candidate colormap indexes. */ |
---|
867 | JSAMPLE colorlist[MAXNUMCOLORS]; |
---|
868 | int numcolors; /* number of candidate colors */ |
---|
869 | /* This array holds the actually closest colormap index for each cell. */ |
---|
870 | JSAMPLE bestcolor[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS]; |
---|
871 | |
---|
872 | /* Convert cell coordinates to update box ID */ |
---|
873 | c0 >>= BOX_C0_LOG; |
---|
874 | c1 >>= BOX_C1_LOG; |
---|
875 | c2 >>= BOX_C2_LOG; |
---|
876 | |
---|
877 | /* Compute true coordinates of update box's origin corner. |
---|
878 | * Actually we compute the coordinates of the center of the corner |
---|
879 | * histogram cell, which are the lower bounds of the volume we care about. |
---|
880 | */ |
---|
881 | minc0 = (c0 << BOX_C0_SHIFT) + ((1 << C0_SHIFT) >> 1); |
---|
882 | minc1 = (c1 << BOX_C1_SHIFT) + ((1 << C1_SHIFT) >> 1); |
---|
883 | minc2 = (c2 << BOX_C2_SHIFT) + ((1 << C2_SHIFT) >> 1); |
---|
884 | |
---|
885 | /* Determine which colormap entries are close enough to be candidates |
---|
886 | * for the nearest entry to some cell in the update box. |
---|
887 | */ |
---|
888 | numcolors = find_nearby_colors(cinfo, minc0, minc1, minc2, colorlist); |
---|
889 | |
---|
890 | /* Determine the actually nearest colors. */ |
---|
891 | find_best_colors(cinfo, minc0, minc1, minc2, numcolors, colorlist, |
---|
892 | bestcolor); |
---|
893 | |
---|
894 | /* Save the best color numbers (plus 1) in the main cache array */ |
---|
895 | c0 <<= BOX_C0_LOG; /* convert ID back to base cell indexes */ |
---|
896 | c1 <<= BOX_C1_LOG; |
---|
897 | c2 <<= BOX_C2_LOG; |
---|
898 | cptr = bestcolor; |
---|
899 | for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++) { |
---|
900 | for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++) { |
---|
901 | cachep = & histogram[c0+ic0][c1+ic1][c2]; |
---|
902 | for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++) { |
---|
903 | *cachep++ = (histcell) (GETJSAMPLE(*cptr++) + 1); |
---|
904 | } |
---|
905 | } |
---|
906 | } |
---|
907 | } |
---|
908 | |
---|
909 | |
---|
910 | /* |
---|
911 | * Map some rows of pixels to the output colormapped representation. |
---|
912 | */ |
---|
913 | |
---|
914 | METHODDEF(void) |
---|
915 | pass2_no_dither (j_decompress_ptr cinfo, |
---|
916 | JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows) |
---|
917 | /* This version performs no dithering */ |
---|
918 | { |
---|
919 | my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; |
---|
920 | hist3d histogram = cquantize->histogram; |
---|
921 | register JSAMPROW inptr, outptr; |
---|
922 | register histptr cachep; |
---|
923 | register int c0, c1, c2; |
---|
924 | int row; |
---|
925 | JDIMENSION col; |
---|
926 | JDIMENSION width = cinfo->output_width; |
---|
927 | |
---|
928 | for (row = 0; row < num_rows; row++) { |
---|
929 | inptr = input_buf[row]; |
---|
930 | outptr = output_buf[row]; |
---|
931 | for (col = width; col > 0; col--) { |
---|
932 | /* get pixel value and index into the cache */ |
---|
933 | c0 = GETJSAMPLE(*inptr++) >> C0_SHIFT; |
---|
934 | c1 = GETJSAMPLE(*inptr++) >> C1_SHIFT; |
---|
935 | c2 = GETJSAMPLE(*inptr++) >> C2_SHIFT; |
---|
936 | cachep = & histogram[c0][c1][c2]; |
---|
937 | /* If we have not seen this color before, find nearest colormap entry */ |
---|
938 | /* and update the cache */ |
---|
939 | if (*cachep == 0) |
---|
940 | fill_inverse_cmap(cinfo, c0,c1,c2); |
---|
941 | /* Now emit the colormap index for this cell */ |
---|
942 | *outptr++ = (JSAMPLE) (*cachep - 1); |
---|
943 | } |
---|
944 | } |
---|
945 | } |
---|
946 | |
---|
947 | |
---|
948 | METHODDEF(void) |
---|
949 | pass2_fs_dither (j_decompress_ptr cinfo, |
---|
950 | JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows) |
---|
951 | /* This version performs Floyd-Steinberg dithering */ |
---|
952 | { |
---|
953 | my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; |
---|
954 | hist3d histogram = cquantize->histogram; |
---|
955 | register LOCFSERROR cur0, cur1, cur2; /* current error or pixel value */ |
---|
956 | LOCFSERROR belowerr0, belowerr1, belowerr2; /* error for pixel below cur */ |
---|
957 | LOCFSERROR bpreverr0, bpreverr1, bpreverr2; /* error for below/prev col */ |
---|
958 | register FSERRPTR errorptr; /* => fserrors[] at column before current */ |
---|
959 | JSAMPROW inptr; /* => current input pixel */ |
---|
960 | JSAMPROW outptr; /* => current output pixel */ |
---|
961 | histptr cachep; |
---|
962 | int dir; /* +1 or -1 depending on direction */ |
---|
963 | int dir3; /* 3*dir, for advancing inptr & errorptr */ |
---|
964 | int row; |
---|
965 | JDIMENSION col; |
---|
966 | JDIMENSION width = cinfo->output_width; |
---|
967 | JSAMPLE *range_limit = cinfo->sample_range_limit; |
---|
968 | int *error_limit = cquantize->error_limiter; |
---|
969 | JSAMPROW colormap0 = cinfo->colormap[0]; |
---|
970 | JSAMPROW colormap1 = cinfo->colormap[1]; |
---|
971 | JSAMPROW colormap2 = cinfo->colormap[2]; |
---|
972 | SHIFT_TEMPS |
---|
973 | |
---|
974 | for (row = 0; row < num_rows; row++) { |
---|
975 | inptr = input_buf[row]; |
---|
976 | outptr = output_buf[row]; |
---|
977 | if (cquantize->on_odd_row) { |
---|
978 | /* work right to left in this row */ |
---|
979 | inptr += (width-1) * 3; /* so point to rightmost pixel */ |
---|
980 | outptr += width-1; |
---|
981 | dir = -1; |
---|
982 | dir3 = -3; |
---|
983 | errorptr = cquantize->fserrors + (width+1)*3; /* => entry after last column */ |
---|
984 | cquantize->on_odd_row = FALSE; /* flip for next time */ |
---|
985 | } else { |
---|
986 | /* work left to right in this row */ |
---|
987 | dir = 1; |
---|
988 | dir3 = 3; |
---|
989 | errorptr = cquantize->fserrors; /* => entry before first real column */ |
---|
990 | cquantize->on_odd_row = TRUE; /* flip for next time */ |
---|
991 | } |
---|
992 | /* Preset error values: no error propagated to first pixel from left */ |
---|
993 | cur0 = cur1 = cur2 = 0; |
---|
994 | /* and no error propagated to row below yet */ |
---|
995 | belowerr0 = belowerr1 = belowerr2 = 0; |
---|
996 | bpreverr0 = bpreverr1 = bpreverr2 = 0; |
---|
997 | |
---|
998 | for (col = width; col > 0; col--) { |
---|
999 | /* curN holds the error propagated from the previous pixel on the |
---|
1000 | * current line. Add the error propagated from the previous line |
---|
1001 | * to form the complete error correction term for this pixel, and |
---|
1002 | * round the error term (which is expressed * 16) to an integer. |
---|
1003 | * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct |
---|
1004 | * for either sign of the error value. |
---|
1005 | * Note: errorptr points to *previous* column's array entry. |
---|
1006 | */ |
---|
1007 | cur0 = RIGHT_SHIFT(cur0 + errorptr[dir3+0] + 8, 4); |
---|
1008 | cur1 = RIGHT_SHIFT(cur1 + errorptr[dir3+1] + 8, 4); |
---|
1009 | cur2 = RIGHT_SHIFT(cur2 + errorptr[dir3+2] + 8, 4); |
---|
1010 | /* Limit the error using transfer function set by init_error_limit. |
---|
1011 | * See comments with init_error_limit for rationale. |
---|
1012 | */ |
---|
1013 | cur0 = error_limit[cur0]; |
---|
1014 | cur1 = error_limit[cur1]; |
---|
1015 | cur2 = error_limit[cur2]; |
---|
1016 | /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE. |
---|
1017 | * The maximum error is +- MAXJSAMPLE (or less with error limiting); |
---|
1018 | * this sets the required size of the range_limit array. |
---|
1019 | */ |
---|
1020 | cur0 += GETJSAMPLE(inptr[0]); |
---|
1021 | cur1 += GETJSAMPLE(inptr[1]); |
---|
1022 | cur2 += GETJSAMPLE(inptr[2]); |
---|
1023 | cur0 = GETJSAMPLE(range_limit[cur0]); |
---|
1024 | cur1 = GETJSAMPLE(range_limit[cur1]); |
---|
1025 | cur2 = GETJSAMPLE(range_limit[cur2]); |
---|
1026 | /* Index into the cache with adjusted pixel value */ |
---|
1027 | cachep = & histogram[cur0>>C0_SHIFT][cur1>>C1_SHIFT][cur2>>C2_SHIFT]; |
---|
1028 | /* If we have not seen this color before, find nearest colormap */ |
---|
1029 | /* entry and update the cache */ |
---|
1030 | if (*cachep == 0) |
---|
1031 | fill_inverse_cmap(cinfo, cur0>>C0_SHIFT,cur1>>C1_SHIFT,cur2>>C2_SHIFT); |
---|
1032 | /* Now emit the colormap index for this cell */ |
---|
1033 | { register int pixcode = *cachep - 1; |
---|
1034 | *outptr = (JSAMPLE) pixcode; |
---|
1035 | /* Compute representation error for this pixel */ |
---|
1036 | cur0 -= GETJSAMPLE(colormap0[pixcode]); |
---|
1037 | cur1 -= GETJSAMPLE(colormap1[pixcode]); |
---|
1038 | cur2 -= GETJSAMPLE(colormap2[pixcode]); |
---|
1039 | } |
---|
1040 | /* Compute error fractions to be propagated to adjacent pixels. |
---|
1041 | * Add these into the running sums, and simultaneously shift the |
---|
1042 | * next-line error sums left by 1 column. |
---|
1043 | */ |
---|
1044 | { register LOCFSERROR bnexterr, delta; |
---|
1045 | |
---|
1046 | bnexterr = cur0; /* Process component 0 */ |
---|
1047 | delta = cur0 * 2; |
---|
1048 | cur0 += delta; /* form error * 3 */ |
---|
1049 | errorptr[0] = (FSERROR) (bpreverr0 + cur0); |
---|
1050 | cur0 += delta; /* form error * 5 */ |
---|
1051 | bpreverr0 = belowerr0 + cur0; |
---|
1052 | belowerr0 = bnexterr; |
---|
1053 | cur0 += delta; /* form error * 7 */ |
---|
1054 | bnexterr = cur1; /* Process component 1 */ |
---|
1055 | delta = cur1 * 2; |
---|
1056 | cur1 += delta; /* form error * 3 */ |
---|
1057 | errorptr[1] = (FSERROR) (bpreverr1 + cur1); |
---|
1058 | cur1 += delta; /* form error * 5 */ |
---|
1059 | bpreverr1 = belowerr1 + cur1; |
---|
1060 | belowerr1 = bnexterr; |
---|
1061 | cur1 += delta; /* form error * 7 */ |
---|
1062 | bnexterr = cur2; /* Process component 2 */ |
---|
1063 | delta = cur2 * 2; |
---|
1064 | cur2 += delta; /* form error * 3 */ |
---|
1065 | errorptr[2] = (FSERROR) (bpreverr2 + cur2); |
---|
1066 | cur2 += delta; /* form error * 5 */ |
---|
1067 | bpreverr2 = belowerr2 + cur2; |
---|
1068 | belowerr2 = bnexterr; |
---|
1069 | cur2 += delta; /* form error * 7 */ |
---|
1070 | } |
---|
1071 | /* At this point curN contains the 7/16 error value to be propagated |
---|
1072 | * to the next pixel on the current line, and all the errors for the |
---|
1073 | * next line have been shifted over. We are therefore ready to move on. |
---|
1074 | */ |
---|
1075 | inptr += dir3; /* Advance pixel pointers to next column */ |
---|
1076 | outptr += dir; |
---|
1077 | errorptr += dir3; /* advance errorptr to current column */ |
---|
1078 | } |
---|
1079 | /* Post-loop cleanup: we must unload the final error values into the |
---|
1080 | * final fserrors[] entry. Note we need not unload belowerrN because |
---|
1081 | * it is for the dummy column before or after the actual array. |
---|
1082 | */ |
---|
1083 | errorptr[0] = (FSERROR) bpreverr0; /* unload prev errs into array */ |
---|
1084 | errorptr[1] = (FSERROR) bpreverr1; |
---|
1085 | errorptr[2] = (FSERROR) bpreverr2; |
---|
1086 | } |
---|
1087 | } |
---|
1088 | |
---|
1089 | |
---|
1090 | /* |
---|
1091 | * Initialize the error-limiting transfer function (lookup table). |
---|
1092 | * The raw F-S error computation can potentially compute error values of up to |
---|
1093 | * +- MAXJSAMPLE. But we want the maximum correction applied to a pixel to be |
---|
1094 | * much less, otherwise obviously wrong pixels will be created. (Typical |
---|
1095 | * effects include weird fringes at color-area boundaries, isolated bright |
---|
1096 | * pixels in a dark area, etc.) The standard advice for avoiding this problem |
---|
1097 | * is to ensure that the "corners" of the color cube are allocated as output |
---|
1098 | * colors; then repeated errors in the same direction cannot cause cascading |
---|
1099 | * error buildup. However, that only prevents the error from getting |
---|
1100 | * completely out of hand; Aaron Giles reports that error limiting improves |
---|
1101 | * the results even with corner colors allocated. |
---|
1102 | * A simple clamping of the error values to about +- MAXJSAMPLE/8 works pretty |
---|
1103 | * well, but the smoother transfer function used below is even better. Thanks |
---|
1104 | * to Aaron Giles for this idea. |
---|
1105 | */ |
---|
1106 | |
---|
1107 | LOCAL(void) |
---|
1108 | init_error_limit (j_decompress_ptr cinfo) |
---|
1109 | /* Allocate and fill in the error_limiter table */ |
---|
1110 | { |
---|
1111 | my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; |
---|
1112 | int * table; |
---|
1113 | int in, out; |
---|
1114 | |
---|
1115 | table = (int *) (*cinfo->mem->alloc_small) |
---|
1116 | ((j_common_ptr) cinfo, JPOOL_IMAGE, (MAXJSAMPLE*2+1) * SIZEOF(int)); |
---|
1117 | table += MAXJSAMPLE; /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */ |
---|
1118 | cquantize->error_limiter = table; |
---|
1119 | |
---|
1120 | #define STEPSIZE ((MAXJSAMPLE+1)/16) |
---|
1121 | /* Map errors 1:1 up to +- MAXJSAMPLE/16 */ |
---|
1122 | out = 0; |
---|
1123 | for (in = 0; in < STEPSIZE; in++, out++) { |
---|
1124 | table[in] = out; table[-in] = -out; |
---|
1125 | } |
---|
1126 | /* Map errors 1:2 up to +- 3*MAXJSAMPLE/16 */ |
---|
1127 | for (; in < STEPSIZE*3; in++, out += (in&1) ? 0 : 1) { |
---|
1128 | table[in] = out; table[-in] = -out; |
---|
1129 | } |
---|
1130 | /* Clamp the rest to final out value (which is (MAXJSAMPLE+1)/8) */ |
---|
1131 | for (; in <= MAXJSAMPLE; in++) { |
---|
1132 | table[in] = out; table[-in] = -out; |
---|
1133 | } |
---|
1134 | #undef STEPSIZE |
---|
1135 | } |
---|
1136 | |
---|
1137 | |
---|
1138 | /* |
---|
1139 | * Finish up at the end of each pass. |
---|
1140 | */ |
---|
1141 | |
---|
1142 | METHODDEF(void) |
---|
1143 | finish_pass1 (j_decompress_ptr cinfo) |
---|
1144 | { |
---|
1145 | my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; |
---|
1146 | |
---|
1147 | /* Select the representative colors and fill in cinfo->colormap */ |
---|
1148 | cinfo->colormap = cquantize->sv_colormap; |
---|
1149 | select_colors(cinfo, cquantize->desired); |
---|
1150 | /* Force next pass to zero the color index table */ |
---|
1151 | cquantize->needs_zeroed = TRUE; |
---|
1152 | } |
---|
1153 | |
---|
1154 | |
---|
1155 | METHODDEF(void) |
---|
1156 | finish_pass2 (j_decompress_ptr cinfo) |
---|
1157 | { |
---|
1158 | /* no work */ |
---|
1159 | } |
---|
1160 | |
---|
1161 | |
---|
1162 | /* |
---|
1163 | * Initialize for each processing pass. |
---|
1164 | */ |
---|
1165 | |
---|
1166 | METHODDEF(void) |
---|
1167 | start_pass_2_quant (j_decompress_ptr cinfo, boolean is_pre_scan) |
---|
1168 | { |
---|
1169 | my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; |
---|
1170 | hist3d histogram = cquantize->histogram; |
---|
1171 | int i; |
---|
1172 | |
---|
1173 | /* Only F-S dithering or no dithering is supported. */ |
---|
1174 | /* If user asks for ordered dither, give him F-S. */ |
---|
1175 | if (cinfo->dither_mode != JDITHER_NONE) |
---|
1176 | cinfo->dither_mode = JDITHER_FS; |
---|
1177 | |
---|
1178 | if (is_pre_scan) { |
---|
1179 | /* Set up method pointers */ |
---|
1180 | cquantize->pub.color_quantize = prescan_quantize; |
---|
1181 | cquantize->pub.finish_pass = finish_pass1; |
---|
1182 | cquantize->needs_zeroed = TRUE; /* Always zero histogram */ |
---|
1183 | } else { |
---|
1184 | /* Set up method pointers */ |
---|
1185 | if (cinfo->dither_mode == JDITHER_FS) |
---|
1186 | cquantize->pub.color_quantize = pass2_fs_dither; |
---|
1187 | else |
---|
1188 | cquantize->pub.color_quantize = pass2_no_dither; |
---|
1189 | cquantize->pub.finish_pass = finish_pass2; |
---|
1190 | |
---|
1191 | /* Make sure color count is acceptable */ |
---|
1192 | i = cinfo->actual_number_of_colors; |
---|
1193 | if (i < 1) |
---|
1194 | ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, 1); |
---|
1195 | if (i > MAXNUMCOLORS) |
---|
1196 | ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS); |
---|
1197 | |
---|
1198 | if (cinfo->dither_mode == JDITHER_FS) { |
---|
1199 | size_t arraysize = (size_t) ((cinfo->output_width + 2) * |
---|
1200 | (3 * SIZEOF(FSERROR))); |
---|
1201 | /* Allocate Floyd-Steinberg workspace if we didn't already. */ |
---|
1202 | if (cquantize->fserrors == NULL) |
---|
1203 | cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large) |
---|
1204 | ((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize); |
---|
1205 | /* Initialize the propagated errors to zero. */ |
---|
1206 | jzero_far((void FAR *) cquantize->fserrors, arraysize); |
---|
1207 | /* Make the error-limit table if we didn't already. */ |
---|
1208 | if (cquantize->error_limiter == NULL) |
---|
1209 | init_error_limit(cinfo); |
---|
1210 | cquantize->on_odd_row = FALSE; |
---|
1211 | } |
---|
1212 | |
---|
1213 | } |
---|
1214 | /* Zero the histogram or inverse color map, if necessary */ |
---|
1215 | if (cquantize->needs_zeroed) { |
---|
1216 | for (i = 0; i < HIST_C0_ELEMS; i++) { |
---|
1217 | jzero_far((void FAR *) histogram[i], |
---|
1218 | HIST_C1_ELEMS*HIST_C2_ELEMS * SIZEOF(histcell)); |
---|
1219 | } |
---|
1220 | cquantize->needs_zeroed = FALSE; |
---|
1221 | } |
---|
1222 | } |
---|
1223 | |
---|
1224 | |
---|
1225 | /* |
---|
1226 | * Switch to a new external colormap between output passes. |
---|
1227 | */ |
---|
1228 | |
---|
1229 | METHODDEF(void) |
---|
1230 | new_color_map_2_quant (j_decompress_ptr cinfo) |
---|
1231 | { |
---|
1232 | my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; |
---|
1233 | |
---|
1234 | /* Reset the inverse color map */ |
---|
1235 | cquantize->needs_zeroed = TRUE; |
---|
1236 | } |
---|
1237 | |
---|
1238 | |
---|
1239 | /* |
---|
1240 | * Module initialization routine for 2-pass color quantization. |
---|
1241 | */ |
---|
1242 | |
---|
1243 | GLOBAL(void) |
---|
1244 | jinit_2pass_quantizer (j_decompress_ptr cinfo) |
---|
1245 | { |
---|
1246 | my_cquantize_ptr cquantize; |
---|
1247 | int i; |
---|
1248 | |
---|
1249 | cquantize = (my_cquantize_ptr) |
---|
1250 | (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, |
---|
1251 | SIZEOF(my_cquantizer)); |
---|
1252 | cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize; |
---|
1253 | cquantize->pub.start_pass = start_pass_2_quant; |
---|
1254 | cquantize->pub.new_color_map = new_color_map_2_quant; |
---|
1255 | cquantize->fserrors = NULL; /* flag optional arrays not allocated */ |
---|
1256 | cquantize->error_limiter = NULL; |
---|
1257 | |
---|
1258 | /* Make sure jdmaster didn't give me a case I can't handle */ |
---|
1259 | if (cinfo->out_color_components != 3) |
---|
1260 | ERREXIT(cinfo, JERR_NOTIMPL); |
---|
1261 | |
---|
1262 | /* Allocate the histogram/inverse colormap storage */ |
---|
1263 | cquantize->histogram = (hist3d) (*cinfo->mem->alloc_small) |
---|
1264 | ((j_common_ptr) cinfo, JPOOL_IMAGE, HIST_C0_ELEMS * SIZEOF(hist2d)); |
---|
1265 | for (i = 0; i < HIST_C0_ELEMS; i++) { |
---|
1266 | cquantize->histogram[i] = (hist2d) (*cinfo->mem->alloc_large) |
---|
1267 | ((j_common_ptr) cinfo, JPOOL_IMAGE, |
---|
1268 | HIST_C1_ELEMS*HIST_C2_ELEMS * SIZEOF(histcell)); |
---|
1269 | } |
---|
1270 | cquantize->needs_zeroed = TRUE; /* histogram is garbage now */ |
---|
1271 | |
---|
1272 | /* Allocate storage for the completed colormap, if required. |
---|
1273 | * We do this now since it is FAR storage and may affect |
---|
1274 | * the memory manager's space calculations. |
---|
1275 | */ |
---|
1276 | if (cinfo->enable_2pass_quant) { |
---|
1277 | /* Make sure color count is acceptable */ |
---|
1278 | int desired = cinfo->desired_number_of_colors; |
---|
1279 | /* Lower bound on # of colors ... somewhat arbitrary as long as > 0 */ |
---|
1280 | if (desired < 8) |
---|
1281 | ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, 8); |
---|
1282 | /* Make sure colormap indexes can be represented by JSAMPLEs */ |
---|
1283 | if (desired > MAXNUMCOLORS) |
---|
1284 | ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS); |
---|
1285 | cquantize->sv_colormap = (*cinfo->mem->alloc_sarray) |
---|
1286 | ((j_common_ptr) cinfo,JPOOL_IMAGE, (JDIMENSION) desired, (JDIMENSION) 3); |
---|
1287 | cquantize->desired = desired; |
---|
1288 | } else |
---|
1289 | cquantize->sv_colormap = NULL; |
---|
1290 | |
---|
1291 | /* Only F-S dithering or no dithering is supported. */ |
---|
1292 | /* If user asks for ordered dither, give him F-S. */ |
---|
1293 | if (cinfo->dither_mode != JDITHER_NONE) |
---|
1294 | cinfo->dither_mode = JDITHER_FS; |
---|
1295 | |
---|
1296 | /* Allocate Floyd-Steinberg workspace if necessary. |
---|
1297 | * This isn't really needed until pass 2, but again it is FAR storage. |
---|
1298 | * Although we will cope with a later change in dither_mode, |
---|
1299 | * we do not promise to honor max_memory_to_use if dither_mode changes. |
---|
1300 | */ |
---|
1301 | if (cinfo->dither_mode == JDITHER_FS) { |
---|
1302 | cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large) |
---|
1303 | ((j_common_ptr) cinfo, JPOOL_IMAGE, |
---|
1304 | (size_t) ((cinfo->output_width + 2) * (3 * SIZEOF(FSERROR)))); |
---|
1305 | /* Might as well create the error-limiting table too. */ |
---|
1306 | init_error_limit(cinfo); |
---|
1307 | } |
---|
1308 | } |
---|
1309 | |
---|
1310 | #endif /* QUANT_2PASS_SUPPORTED */ |
---|