0N/A * reserved comment block 0N/A * DO NOT REMOVE OR ALTER! 0N/A * Copyright (C) 1991-1996, Thomas G. Lane. 0N/A * This file is part of the Independent JPEG Group's software. 0N/A * For conditions of distribution and use, see the accompanying README file. 0N/A * This file contains 1-pass color quantization (color mapping) routines. 0N/A * These routines provide mapping to a fixed color map using equally spaced 0N/A * color values. Optional Floyd-Steinberg or ordered dithering is available. 0N/A * The main purpose of 1-pass quantization is to provide a fast, if not very 0N/A * high quality, colormapped output capability. A 2-pass quantizer usually 0N/A * gives better visual quality; however, for quantized grayscale output this 0N/A * quantizer is perfectly adequate. Dithering is highly recommended with this 0N/A * quantizer, though you can turn it off if you really want to. 0N/A * In 1-pass quantization the colormap must be chosen in advance of seeing the 0N/A * image. We use a map consisting of all combinations of Ncolors[i] color 0N/A * values for the i'th component. The Ncolors[] values are chosen so that 0N/A * their product, the total number of colors, is no more than that requested. 0N/A * (In most cases, the product will be somewhat less.) 0N/A * Since the colormap is orthogonal, the representative value for each color 0N/A * component can be determined without considering the other components; 0N/A * then these indexes can be combined into a colormap index by a standard 0N/A * N-dimensional-array-subscript calculation. Most of the arithmetic involved 0N/A * can be precalculated and stored in the lookup table colorindex[]. 0N/A * colorindex[i][j] maps pixel value j in component i to the nearest 0N/A * representative value (grid plane) for that component; this index is 0N/A * multiplied by the array stride for component i, so that the 0N/A * index of the colormap entry closest to a given pixel value is just 0N/A * sum( colorindex[component-number][pixel-component-value] ) 0N/A * Aside from being fast, this scheme allows for variable spacing between 0N/A * representative values with no additional lookup cost. 0N/A * If gamma correction has been applied in color conversion, it might be wise 0N/A * to adjust the color grid spacing so that the representative colors are 0N/A * equidistant in linear space. At this writing, gamma correction is not 0N/A * implemented by jdcolor, so nothing is done here. 0N/A/* Declarations for ordered dithering. 0N/A * We use a standard 16x16 ordered dither array. The basic concept of ordered 0N/A * dithering is described in many references, for instance Dale Schumacher's 0N/A * chapter II.2 of Graphics Gems II (James Arvo, ed. Academic Press, 1991). 0N/A * In place of Schumacher's comparisons against a "threshold" value, we add a 0N/A * "dither" value to the input pixel and then round the result to the nearest 0N/A * output value. The dither value is equivalent to (0.5 - threshold) times 0N/A * the distance between output values. For ordered dithering, we assume that 0N/A * the output colors are equally spaced; if not, results will probably be 0N/A * worse, since the dither may be too much or too little at a given point. 0N/A * The normal calculation would be to form pixel value + dither, range-limit 0N/A * this to 0..MAXJSAMPLE, and then index into the colorindex table as usual. 0N/A * We can skip the separate range-limiting step by extending the colorindex 0N/A * table in both directions. 0N/A/* NB: if ODITHER_SIZE is not a power of 2, ODITHER_MASK uses will break */ 0N/A /* Bayer's order-4 dither array. Generated by the code given in 0N/A * Stephen Hawley's article "Ordered Dithering" in Graphics Gems I. 0N/A * The values in this array must range from 0 to ODITHER_CELLS-1. 0N/A { 0,
192,
48,
240,
12,
204,
60,
252,
3,
195,
51,
243,
15,
207,
63,
255 },
0N/A {
128,
64,
176,
112,
140,
76,
188,
124,
131,
67,
179,
115,
143,
79,
191,
127 },
0N/A {
32,
224,
16,
208,
44,
236,
28,
220,
35,
227,
19,
211,
47,
239,
31,
223 },
0N/A {
160,
96,
144,
80,
172,
108,
156,
92,
163,
99,
147,
83,
175,
111,
159,
95 },
0N/A {
8,
200,
56,
248,
4,
196,
52,
244,
11,
203,
59,
251,
7,
199,
55,
247 },
0N/A {
136,
72,
184,
120,
132,
68,
180,
116,
139,
75,
187,
123,
135,
71,
183,
119 },
0N/A {
40,
232,
24,
216,
36,
228,
20,
212,
43,
235,
27,
219,
39,
231,
23,
215 },
0N/A {
168,
104,
152,
88,
164,
100,
148,
84,
171,
107,
155,
91,
167,
103,
151,
87 },
0N/A {
2,
194,
50,
242,
14,
206,
62,
254,
1,
193,
49,
241,
13,
205,
61,
253 },
0N/A {
130,
66,
178,
114,
142,
78,
190,
126,
129,
65,
177,
113,
141,
77,
189,
125 },
0N/A {
34,
226,
18,
210,
46,
238,
30,
222,
33,
225,
17,
209,
45,
237,
29,
221 },
0N/A {
162,
98,
146,
82,
174,
110,
158,
94,
161,
97,
145,
81,
173,
109,
157,
93 },
0N/A {
10,
202,
58,
250,
6,
198,
54,
246,
9,
201,
57,
249,
5,
197,
53,
245 },
0N/A {
138,
74,
186,
122,
134,
70,
182,
118,
137,
73,
185,
121,
133,
69,
181,
117 },
0N/A {
42,
234,
26,
218,
38,
230,
22,
214,
41,
233,
25,
217,
37,
229,
21,
213 },
0N/A {
170,
106,
154,
90,
166,
102,
150,
86,
169,
105,
153,
89,
165,
101,
149,
85 }
0N/A/* Declarations for Floyd-Steinberg dithering. 0N/A * Errors are accumulated into the array fserrors[], at a resolution of 0N/A * 1/16th of a pixel count. The error at a given pixel is propagated 0N/A * to its not-yet-processed neighbors using the standard F-S fractions, 0N/A * We work left-to-right on even rows, right-to-left on odd rows. 0N/A * We can get away with a single array (holding one row's worth of errors) 0N/A * by using it to store the current row's errors at pixel columns not yet 0N/A * processed, but the next row's errors at columns already processed. We 0N/A * need only a few extra variables to hold the errors immediately around the 0N/A * current column. (If we are lucky, those variables are in registers, but 0N/A * even if not, they're probably cheaper to access than array elements are.) 0N/A * The fserrors[] array is indexed [component#][position]. 0N/A * We provide (#columns + 2) entries per component; the extra entry at each 0N/A * end saves us from special-casing the first and last pixels. 0N/A * Note: on a wide image, we might not have enough room in a PC's near data 0N/A * segment to hold the error array; so it is allocated with alloc_large. 0N/A/* Private subobject */ 0N/A /* Initially allocated colormap is saved here */ 0N/A /* colorindex[i][j] = index of color closest to pixel value j in component i, 0N/A * premultiplied as described above. Since colormap indexes must fit into 0N/A * JSAMPLEs, the entries of this array will too. 0N/A /* Variables for ordered dithering */ 0N/A int row_index;
/* cur row's vertical index in dither matrix */ 0N/A /* Variables for Floyd-Steinberg dithering */ 0N/A * Policy-making subroutines for create_colormap and create_colorindex. 0N/A * These routines determine the colormap to be used. The rest of the module 0N/A * only assumes that the colormap is orthogonal. 0N/A * * select_ncolors decides how to divvy up the available colors 0N/A * among the components. 0N/A * * output_value defines the set of representative values for a component. 0N/A * * largest_input_value defines the mapping from input values to 0N/A * representative values for a component. 0N/A * Note that the latter two routines may impose different policies for 0N/A * different components, though this is not currently done. 0N/A/* Determine allocation of desired colors to components, */ 0N/A/* and fill in Ncolors[] array to indicate choice. */ 0N/A/* Return value is total number of colors (product of Ncolors[] values). */ 0N/A /* We can allocate at least the nc'th root of max_colors per component. */ 0N/A /* Compute floor(nc'th root of max_colors). */ 0N/A /* Must have at least 2 color values per component */ 0N/A /* Initialize to iroot color values for each component */ 0N/A for (i = 0; i <
nc; i++) {
0N/A /* We may be able to increment the count for one or more components without 0N/A * exceeding max_colors, though we know not all can be incremented. 0N/A * Sometimes, the first component can be incremented more than once! 0N/A * (Example: for 16 colors, we start at 2*2*2, go to 3*2*2, then 4*2*2.) 0N/A * In RGB colorspace, try to increment G first, then R, then B. 0N/A for (i = 0; i <
nc; i++) {
0N/A /* calculate new total_colors if Ncolors[j] is incremented */ 0N/A break;
/* won't fit, done with this pass */ 0N/A/* Return j'th output value, where j will range from 0 to maxj */ 0N/A/* The output values must fall in 0..MAXJSAMPLE in increasing order */ 0N/A /* We always provide values 0 and MAXJSAMPLE for each component; 0N/A * any additional values are equally spaced between these limits. 0N/A * (Forcing the upper and lower values to the limits ensures that 0N/A * dithering can't produce a color outside the selected gamut.) 0N/A/* Return largest input value that should map to j'th output value */ 0N/A/* Must have largest(j=0) >= 0, and largest(j=maxj) >= MAXJSAMPLE */ 0N/A /* Breakpoints are halfway between values returned by output_value */ 0N/A * Create the colormap. 0N/A /* Select number of colors for each component */ 0N/A /* Report selected color counts */ 0N/A /* Allocate and fill in the colormap. */ 0N/A /* The colors are ordered in the map in standard row-major order, */ 0N/A /* i.e. rightmost (highest-indexed) color changes most rapidly. */ 0N/A /* blksize is number of adjacent repeated entries for a component */ 0N/A /* blkdist is distance between groups of identical entries for a component */ 0N/A /* fill in colormap entries for i'th color component */ 0N/A /* Compute j'th output value (out of nci) for component */ 0N/A /* Fill in all colormap entries that have this value of this component */ 0N/A /* fill in blksize entries beginning at ptr */ 0N/A /* Save the colormap in private storage, 0N/A * where it will survive color quantization mode changes. 0N/A * Create the color index table. 0N/A /* For ordered dither, we pad the color index tables by MAXJSAMPLE in 0N/A * each direction (input index values can be -MAXJSAMPLE .. 2*MAXJSAMPLE). 0N/A * This is not necessary in the other dithering modes. However, we 0N/A * flag whether it was done in case user changes dithering mode. 0N/A /* blksize is number of adjacent repeated entries for a component */ 0N/A /* fill in colorindex entries for i'th color component */ 0N/A /* adjust colorindex pointers to provide padding at negative indexes. */ 0N/A /* in loop, val = index of current output value, */ 0N/A /* and k = largest j that maps to current val */ 0N/A while (j > k)
/* advance val if past boundary */ 0N/A /* premultiply so that no multiplication needed in main processing */ 0N/A /* Pad at both ends if necessary */ 0N/A * Create an ordered-dither array for a component having ncolors 0N/A * distinct output values. 0N/A /* The inter-value distance for this color is MAXJSAMPLE/(ncolors-1). 0N/A * Hence the dither value for the matrix cell with fill order f 0N/A * (f=0..N-1) should be (N-1-2*f)/(2*N) * MAXJSAMPLE/(ncolors-1). 0N/A * On 16-bit-int machine, be careful to avoid overflow. 0N/A /* Ensure round towards zero despite C's lack of consistency 0N/A * about rounding negative values in integer division... 0N/A * Create the ordered-dither tables. 0N/A * Components having the same number of representative colors may 0N/A * share a dither table. 0N/A for (j = 0; j < i; j++) {
0N/A * Map some rows of pixels to the output colormapped representation. 0N/A/* General case, no dithering */ 0N/A/* Fast path for out_color_components==3, no dithering */ 0N/A/* General case, with ordered dithering */ 0N/A int *
dither;
/* points to active row of dither matrix */ 0N/A /* Initialize output values to 0 so can process components separately */ 0N/A /* Form pixel value + dither, range-limit to 0..MAXJSAMPLE, 0N/A * select output value, accumulate into output code for this pixel. 0N/A * Range-limiting need not be done explicitly, as we have extended 0N/A * the colorindex table to produce the right answers for out-of-range 0N/A * inputs. The maximum dither is +- MAXJSAMPLE; this sets the 0N/A * required amount of padding. 0N/A /* Advance row index for next row */ 0N/A/* Fast path for out_color_components==3, with ordered dithering */ 0N/A int *
dither0;
/* points to active row of dither matrix */ 0N/A/* General case, with Floyd-Steinberg dithering */ 0N/A int dir;
/* 1 for left-to-right, -1 for right-to-left */ 0N/A /* Initialize output values to 0 so can process components separately */ 0N/A /* work right to left in this row */ 0N/A /* work left to right in this row */ 0N/A /* Preset error values: no error propagated to first pixel from left */ 0N/A /* and no error propagated to row below yet */ 0N/A /* cur holds the error propagated from the previous pixel on the 0N/A * current line. Add the error propagated from the previous line 0N/A * to form the complete error correction term for this pixel, and 0N/A * round the error term (which is expressed * 16) to an integer. 0N/A * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct 0N/A * for either sign of the error value. 0N/A * Note: errorptr points to *previous* column's array entry. 0N/A /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE. 0N/A * The maximum error is +- MAXJSAMPLE; this sets the required size 0N/A * of the range_limit array. 0N/A /* Select output value, accumulate into output code for this pixel */ 0N/A /* Compute actual representation error at this pixel */ 0N/A /* Note: we can do this even though we don't have the final */ 0N/A /* pixel code, because the colormap is orthogonal. */ 0N/A /* Compute error fractions to be propagated to adjacent pixels. 0N/A * Add these into the running sums, and simultaneously shift the 0N/A * next-line error sums left by 1 column. 0N/A /* At this point cur contains the 7/16 error value to be propagated 0N/A * to the next pixel on the current line, and all the errors for the 0N/A * next line have been shifted over. We are therefore ready to move on. 0N/A /* Post-loop cleanup: we must unload the final error value into the 0N/A * final fserrors[] entry. Note we need not unload belowerr because 0N/A * it is for the dummy column before or after the actual array. 0N/A * Allocate workspace for Floyd-Steinberg errors. 0N/A * Initialize for one-pass color quantization. 0N/A /* Install my colormap. */ 0N/A /* Initialize for desired dithering mode. */ 0N/A /* If user changed to ordered dither from another mode, 0N/A * we must recreate the color index table with padding. 0N/A * This will cost extra space, but probably isn't very likely. 0N/A /* Create ordered-dither tables if we didn't already. */ 0N/A /* Allocate Floyd-Steinberg workspace if didn't already. */ 0N/A /* Initialize the propagated errors to zero. */ 0N/A * Finish up at the end of the pass. 0N/A /* no work in 1-pass case */ 0N/A * Switch to a new external colormap between output passes. 0N/A * Shouldn't get to this module! 0N/A * Module initialization routine for 1-pass color quantization. 0N/A /* Make sure my internal arrays won't overflow */ 0N/A /* Make sure colormap indexes can be represented by JSAMPLEs */ 0N/A /* Create the colormap and color index table. */ 0N/A /* Allocate Floyd-Steinberg workspace now if requested. 0N/A * We do this now since it is FAR storage and may affect the memory 0N/A * manager's space calculations. If the user changes to FS dither 0N/A * mode in a later pass, we will allocate the space then, and will 0N/A * possibly overrun the max_memory_to_use setting. 0N/A#
endif /* QUANT_1PASS_SUPPORTED */