Logo ROOT  
Reference Guide
gifquantize.c
Go to the documentation of this file.
1/* @(#)root/x11:$Id$ */
2/* Author: Fons Rademakers 04/11/98*/
3/*****************************************************************************
4* Module to quantize high resolution image into lower one. You may want to *
5* peek into the following article this code is based on: *
6* "Color Image Quantization for frame buffer Display", by Paul Heckbert *
7* SIGGRAPH 1982 page 297-307. *
8*****************************************************************************/
9
10#include <stdio.h>
11#include <stdlib.h>
12
13typedef unsigned char byte;
14typedef struct GifColorType {
15 byte Red, Green, Blue;
17
18#define ABS(x) ((x) > 0 ? (x) : (-(x)))
19
20#define GIF_ERROR 0
21#define GIF_OK 1
22
23/* The colors are stripped to 5 bits per primary color */
24#define COLOR_ARRAY_SIZE 32768
25#define BITS_PER_PRIM_COLOR 5
26#define MAX_PRIM_COLOR 0x1f
27
28
29static int SortRGBAxis;
30
31typedef struct QuantizedColorType {
32 byte RGB[3];
33 byte NewColorIndex;
34 long Count;
35 struct QuantizedColorType *Pnext;
37
38typedef struct NewColorMapType {
39 byte RGBMin[3], RGBWidth[3];
40 unsigned int NumEntries; /* # of QuantizedColorType in linked list below. */
41 long Count; /* Total number of pixels in all the entries. */
42 QuantizedColorType *QuantizedColors;
44
45static int SubdivColorMap(NewColorMapType *NewColorSubdiv,
46 unsigned int ColorMapSize,
47 unsigned int *NewColorMapSize);
48static int SortCmpRtn(const void *Entry1, const void *Entry2);
49
50
51/******************************************************************************
52* Quantize high resolution image into lower one. Input image consists of a *
53* 2D array for each of the RGB colors with size Width by Height. There is no *
54* Color map for the input. Output is a quantized image with 2D array of *
55* indexes into the output color map. *
56* Note input image can be 24 bits at the most (8 for red/green/blue) and *
57* the output has 256 colors at the most (256 entries in the color map.). *
58* ColorMapSize specifies size of color map up to 256 and will be updated to *
59* real size before returning. *
60* Also non of the parameter are allocated by this routine. *
61* This function returns GIF_OK if successful, GIF_ERROR otherwise. *
62******************************************************************************/
63int GIFquantize(unsigned int Width, unsigned int Height, int *ColorMapSize,
64 byte *RedInput, byte *GreenInput, byte *BlueInput,
65 byte *OutputBuffer, GifColorType *OutputColorMap)
66{
67 unsigned int Index, NumOfEntries, newsize;
68 int i, j, MaxRGBError[3];
69 int NewColorMapSize;
70 long Red, Green, Blue;
71 NewColorMapType NewColorSubdiv[256];
72 QuantizedColorType *ColorArrayEntries, *QuantizedColor;
73
74 if ((ColorArrayEntries = (QuantizedColorType *)
75 malloc(sizeof(QuantizedColorType) * COLOR_ARRAY_SIZE)) == NULL) {
76 fprintf(stderr, "QuantizeBuffer: not enough memory\n");
77 return GIF_ERROR;
78 }
79
80 for (i = 0; i < COLOR_ARRAY_SIZE; i++) {
81 ColorArrayEntries[i].RGB[0]= i >> (2 * BITS_PER_PRIM_COLOR);
82 ColorArrayEntries[i].RGB[1] = (i >> BITS_PER_PRIM_COLOR) & MAX_PRIM_COLOR;
83 ColorArrayEntries[i].RGB[2] = i & MAX_PRIM_COLOR;
84 ColorArrayEntries[i].Count = 0;
85 }
86
87 /* Sample the colors and their distribution: */
88 for (i = 0; i < (int)(Width * Height); i++) {
89 Index = ((RedInput[i] >> (8 - BITS_PER_PRIM_COLOR))
90 << (2 * BITS_PER_PRIM_COLOR)) +
91 ((GreenInput[i] >> (8 - BITS_PER_PRIM_COLOR))
93 (BlueInput[i] >> (8 - BITS_PER_PRIM_COLOR));
94 ColorArrayEntries[Index].Count++;
95 }
96
97 /* Put all the colors in the first entry of the color map, and call the */
98 /* recursive subdivision process. */
99 for (i = 0; i < 256; i++) {
100 NewColorSubdiv[i].QuantizedColors = NULL;
101 NewColorSubdiv[i].Count = NewColorSubdiv[i].NumEntries = 0;
102 for (j = 0; j < 3; j++) {
103 NewColorSubdiv[i].RGBMin[j] = 0;
104 NewColorSubdiv[i].RGBWidth[j] = 255;
105 }
106 }
107
108 /* Find the non empty entries in the color table and chain them: */
109 for (i = 0; i < COLOR_ARRAY_SIZE; i++)
110 if (ColorArrayEntries[i].Count > 0) break;
111 QuantizedColor = NewColorSubdiv[0].QuantizedColors = &ColorArrayEntries[i];
112 NumOfEntries = 1;
113 while (++i < COLOR_ARRAY_SIZE)
114 if (ColorArrayEntries[i].Count > 0) {
115 QuantizedColor -> Pnext = &ColorArrayEntries[i];
116 QuantizedColor = &ColorArrayEntries[i];
117 NumOfEntries++;
118 }
119 QuantizedColor -> Pnext = NULL;
120
121 NewColorSubdiv[0].NumEntries = NumOfEntries;/* Different sampled colors. */
122 NewColorSubdiv[0].Count = ((long) Width) * Height; /* Pixels. */
123 newsize = 1;
124 if (SubdivColorMap(NewColorSubdiv, *ColorMapSize, &newsize) != GIF_OK) {
125 free((char *) ColorArrayEntries);
126 return GIF_ERROR;
127 }
128 NewColorMapSize = (int)newsize;
129 if (NewColorMapSize < *ColorMapSize) {
130 /* And clear rest of color map: */
131 for (i = NewColorMapSize; i < *ColorMapSize; i++)
132 OutputColorMap[i].Red =
133 OutputColorMap[i].Green =
134 OutputColorMap[i].Blue = 0;
135 }
136
137 /* Average the colors in each entry to be the color to be used in the */
138 /* output color map, and plug it into the output color map itself. */
139 for (i = 0; i < NewColorMapSize; i++) {
140 if ((j = NewColorSubdiv[i].NumEntries) > 0) {
141 QuantizedColor = NewColorSubdiv[i].QuantizedColors;
142 Red = Green = Blue = 0;
143 while (QuantizedColor) {
144 QuantizedColor -> NewColorIndex = i;
145 Red += QuantizedColor -> RGB[0];
146 Green += QuantizedColor -> RGB[1];
147 Blue += QuantizedColor -> RGB[2];
148 QuantizedColor = QuantizedColor -> Pnext;
149 }
150 OutputColorMap[i].Red = (Red << (8 - BITS_PER_PRIM_COLOR)) / j;
151 OutputColorMap[i].Green = (Green << (8 - BITS_PER_PRIM_COLOR)) / j;
152 OutputColorMap[i].Blue= (Blue << (8 - BITS_PER_PRIM_COLOR)) / j;
153 }
154 else
155 fprintf(stderr, "Null entry in quantized color map - thats weird.");
156 }
157
158 /* Finally scan the input buffer again and put the mapped index in the */
159 /* output buffer. */
160 MaxRGBError[0] = MaxRGBError[1] = MaxRGBError[2] = 0;
161 for (i = 0; i < (int)(Width * Height); i++) {
162 Index = ((RedInput[i] >> (8 - BITS_PER_PRIM_COLOR))
163 << (2 * BITS_PER_PRIM_COLOR)) +
164 ((GreenInput[i] >> (8 - BITS_PER_PRIM_COLOR))
166 (BlueInput[i] >> (8 - BITS_PER_PRIM_COLOR));
167 Index = ColorArrayEntries[Index].NewColorIndex;
168 OutputBuffer[i] = Index;
169 if (MaxRGBError[0] < ABS(OutputColorMap[Index].Red - RedInput[i]))
170 MaxRGBError[0] = ABS(OutputColorMap[Index].Red - RedInput[i]);
171 if (MaxRGBError[1] < ABS(OutputColorMap[Index].Green - GreenInput[i]))
172 MaxRGBError[1] = ABS(OutputColorMap[Index].Green - GreenInput[i]);
173 if (MaxRGBError[2] < ABS(OutputColorMap[Index].Blue - BlueInput[i]))
174 MaxRGBError[2] = ABS(OutputColorMap[Index].Blue - BlueInput[i]);
175 }
176
177#ifdef DEBUG
178 fprintf(stderr,
179 "Quantization L(0) errors: Red = %d, Green = %d, Blue = %d.\n",
180 MaxRGBError[0], MaxRGBError[1], MaxRGBError[2]);
181#endif /* DEBUG */
182
183 free((char *) ColorArrayEntries);
184
185 *ColorMapSize = NewColorMapSize;
186
187 return GIF_OK;
188}
189
190/******************************************************************************
191* Routine to subdivide the RGB space recursively using median cut in each *
192* axes alternatingly until ColorMapSize different cubes exists. *
193* The biggest cube in one dimension is subdivide unless it has only one entry.*
194* Returns GIF_ERROR if failed, otherwise GIF_OK. *
195******************************************************************************/
196static int SubdivColorMap(NewColorMapType *NewColorSubdiv,
197 unsigned int ColorMapSize,
198 unsigned int *NewColorMapSize)
199{
200 int MaxSize;
201 unsigned int i, j, Index = 0, NumEntries, MinColor, MaxColor;
202 long Sum, Count;
203 QuantizedColorType *QuantizedColor, **SortArray;
204
205 while (ColorMapSize > *NewColorMapSize) {
206 /* Find candidate for subdivision: */
207 MaxSize = -1;
208 for (i = 0; i < *NewColorMapSize; i++) {
209 for (j = 0; j < 3; j++) {
210 if (((int) NewColorSubdiv[i].RGBWidth[j]) > MaxSize &&
211 NewColorSubdiv[i].NumEntries > 1) {
212 MaxSize = NewColorSubdiv[i].RGBWidth[j];
213 Index = i;
214 SortRGBAxis = j;
215 }
216 }
217 }
218
219 if (MaxSize == -1)
220 return GIF_OK;
221
222 /* Split the entry Index into two along the axis SortRGBAxis: */
223
224 /* Sort all elements in that entry along the given axis and split at */
225 /* the median. */
226 if ((SortArray = (QuantizedColorType **)
227 malloc(sizeof(QuantizedColorType *) *
228 NewColorSubdiv[Index].NumEntries)) == NULL)
229 return GIF_ERROR;
230 for (j = 0, QuantizedColor = NewColorSubdiv[Index].QuantizedColors;
231 j < NewColorSubdiv[Index].NumEntries && QuantizedColor != NULL;
232 j++, QuantizedColor = QuantizedColor -> Pnext)
233 SortArray[j] = QuantizedColor;
234 qsort(SortArray, NewColorSubdiv[Index].NumEntries,
235 sizeof(QuantizedColorType *), SortCmpRtn);
236
237 /* Relink the sorted list into one: */
238 for (j = 0; j < NewColorSubdiv[Index].NumEntries - 1; j++)
239 SortArray[j] -> Pnext = SortArray[j + 1];
240 SortArray[NewColorSubdiv[Index].NumEntries - 1] -> Pnext = NULL;
241 NewColorSubdiv[Index].QuantizedColors = QuantizedColor = SortArray[0];
242 free((char *) SortArray);
243
244 /* Now simply add the Counts until we have half of the Count: */
245 Sum = NewColorSubdiv[Index].Count / 2 - QuantizedColor -> Count;
246 NumEntries = 1;
247 Count = QuantizedColor -> Count;
248 while (QuantizedColor -> Pnext != NULL &&
249 QuantizedColor -> Pnext -> Pnext != NULL &&
250 (Sum -= QuantizedColor -> Pnext -> Count) >= 0) {
251 QuantizedColor = QuantizedColor -> Pnext;
252 NumEntries++;
253 Count += QuantizedColor -> Count;
254 }
255 /* Save the values of the last color of the first half, and first */
256 /* of the second half so we can update the Bounding Boxes later. */
257 /* Also as the colors are quantized and the BBoxes are full 0..255, */
258 /* they need to be rescaled. */
259 MaxColor = QuantizedColor -> RGB[SortRGBAxis];/* Max. of first half. */
260 if (QuantizedColor -> Pnext) MinColor = QuantizedColor -> Pnext -> RGB[SortRGBAxis];/* of second. */
261 else MinColor = 0;
262 MaxColor <<= (8 - BITS_PER_PRIM_COLOR);
263 MinColor <<= (8 - BITS_PER_PRIM_COLOR);
264
265 /* Partition right here: */
266 NewColorSubdiv[*NewColorMapSize].QuantizedColors =
267 QuantizedColor -> Pnext;
268 QuantizedColor -> Pnext = NULL;
269 NewColorSubdiv[*NewColorMapSize].Count = Count;
270 NewColorSubdiv[Index].Count -= Count;
271 NewColorSubdiv[*NewColorMapSize].NumEntries =
272 NewColorSubdiv[Index].NumEntries - NumEntries;
273 NewColorSubdiv[Index].NumEntries = NumEntries;
274 for (j = 0; j < 3; j++) {
275 NewColorSubdiv[*NewColorMapSize].RGBMin[j] =
276 NewColorSubdiv[Index].RGBMin[j];
277 NewColorSubdiv[*NewColorMapSize].RGBWidth[j] =
278 NewColorSubdiv[Index].RGBWidth[j];
279 }
280 NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] =
281 NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] +
282 NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] -
283 MinColor;
284 NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] = MinColor;
285
286 NewColorSubdiv[Index].RGBWidth[SortRGBAxis] =
287 MaxColor - NewColorSubdiv[Index].RGBMin[SortRGBAxis];
288
289 (*NewColorMapSize)++;
290 }
291
292 return GIF_OK;
293}
294
295/******************************************************************************
296* Routine called by qsort to compare to entries. *
297******************************************************************************/
298static int SortCmpRtn(const void *Entry1, const void *Entry2)
299{
300 return (* ((QuantizedColorType **) Entry1)) -> RGB[SortRGBAxis] -
301 (* ((QuantizedColorType **) Entry2)) -> RGB[SortRGBAxis];
302}
#define free
Definition: civetweb.c:1539
#define malloc
Definition: civetweb.c:1536
T Sum(const RVec< T > &v)
Sum elements of an RVec.
Definition: RVec.hxx:758
RooCmdArg Index(RooCategory &icat)
unsigned char byte
Definition: gifquantize.c:13
struct NewColorMapType NewColorMapType
struct GifColorType GifColorType
int GIFquantize(unsigned int Width, unsigned int Height, int *ColorMapSize, byte *RedInput, byte *GreenInput, byte *BlueInput, byte *OutputBuffer, GifColorType *OutputColorMap)
Definition: gifquantize.c:63
struct QuantizedColorType QuantizedColorType
#define COLOR_ARRAY_SIZE
Definition: gifquantize.c:24
#define BITS_PER_PRIM_COLOR
Definition: gifquantize.c:25
static int SortRGBAxis
Definition: gifquantize.c:29
static int SubdivColorMap(NewColorMapType *NewColorSubdiv, unsigned int ColorMapSize, unsigned int *NewColorMapSize)
Definition: gifquantize.c:196
#define GIF_OK
Definition: gifquantize.c:21
#define ABS(x)
Definition: gifquantize.c:18
static int SortCmpRtn(const void *Entry1, const void *Entry2)
Definition: gifquantize.c:298
#define GIF_ERROR
Definition: gifquantize.c:20
#define MAX_PRIM_COLOR
Definition: gifquantize.c:26