Logo ROOT   6.12/07
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 
13 typedef unsigned char byte;
14 typedef struct GifColorType {
15  byte Red, Green, Blue;
16 } GifColorType;
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 
29 static int SortRGBAxis;
30 
31 typedef struct QuantizedColorType {
32  byte RGB[3];
33  byte NewColorIndex;
34  long Count;
35  struct QuantizedColorType *Pnext;
37 
38 typedef 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 
45 static int SubdivColorMap(NewColorMapType *NewColorSubdiv,
46  unsigned int ColorMapSize,
47  unsigned int *NewColorMapSize);
48 static 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 ******************************************************************************/
63 int 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))
165  << 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 ******************************************************************************/
196 static 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 ******************************************************************************/
298 static int SortCmpRtn(const void *Entry1, const void *Entry2)
299 {
300  return (* ((QuantizedColorType **) Entry1)) -> RGB[SortRGBAxis] -
301  (* ((QuantizedColorType **) Entry2)) -> RGB[SortRGBAxis];
302 }
#define GIF_ERROR
Definition: gifquantize.c:20
#define COLOR_ARRAY_SIZE
Definition: gifquantize.c:24
static int SortRGBAxis
Definition: gifquantize.c:29
#define ABS(x)
Definition: gifquantize.c:18
#define malloc
Definition: civetweb.c:818
static int SubdivColorMap(NewColorMapType *NewColorSubdiv, unsigned int ColorMapSize, unsigned int *NewColorMapSize)
Definition: gifquantize.c:196
#define GIF_OK
Definition: gifquantize.c:21
#define MAX_PRIM_COLOR
Definition: gifquantize.c:26
unsigned char byte
Definition: gifdecode.c:10
struct QuantizedColorType QuantizedColorType
RooCmdArg Index(RooCategory &icat)
static int SortCmpRtn(const void *Entry1, const void *Entry2)
Definition: gifquantize.c:298
#define free
Definition: civetweb.c:821
struct NewColorMapType NewColorMapType
unsigned char byte
Definition: gifquantize.c:13
int GIFquantize(unsigned int Width, unsigned int Height, int *ColorMapSize, byte *RedInput, byte *GreenInput, byte *BlueInput, byte *OutputBuffer, GifColorType *OutputColorMap)
Definition: gifquantize.c:63
#define BITS_PER_PRIM_COLOR
Definition: gifquantize.c:25
struct GifColorType GifColorType