www.pudn.com > giflib12.zip > QUANTIZE.C
/***************************************************************************** * "Gif-Lib" - Yet another gif library. * * * * Written by: Gershon Elber IBM PC Ver 0.1, Jun. 1989 * ****************************************************************************** * Module to quatize high resolution image into lower one. You may want to * * peek into the following article this code is based on: * * "Color Image Quantization for frame buffer Display", by Paul Heckbert * * SIGGRAPH 1982 page 297-307. * ****************************************************************************** * History: * * 5 Jan 90 - Version 1.0 by Gershon Elber. * *****************************************************************************/ #ifdef __MSDOS__ #include#include #include #include #endif /* __MSDOS__ */ #include #include "gif_lib.h" #define PROGRAM_NAME "GIF_LIBRARY" #define ABS(x) ((x) > 0 ? (x) : (-(x))) /* The colors are stripped to 5 bits per primary color if non MSDOS system */ /* or to 4 (not enough memory...) if MSDOS as first step. */ #ifdef __MSDOS__ #define COLOR_ARRAY_SIZE 4096 #define BITS_PER_PRIM_COLOR 4 #define MAX_PRIM_COLOR 0x0f #else #define COLOR_ARRAY_SIZE 32768 #define BITS_PER_PRIM_COLOR 5 #define MAX_PRIM_COLOR 0x1f #endif /* __MSDOS__ */ extern int _GifError; #ifdef SYSV static char *VersionStr = "Gif library module,\t\tGershon Elber\n\ (C) Copyright 1989 Gershon Elber, Non commercial use only.\n"; #else static char *VersionStr = PROGRAM_NAME " IBMPC " GIF_LIB_VERSION " Gershon Elber, " __DATE__ ", " __TIME__ "\n" "(C) Copyright 1989 Gershon Elber, Non commercial use only.\n"; #endif /* SYSV */ static int SortRGBAxis; typedef struct QuantizedColorType { GifByteType RGB[3]; GifByteType NewColorIndex; long Count; struct QuantizedColorType *Pnext; } QuantizedColorType; typedef struct NewColorMapType { GifByteType RGBMin[3], RGBWidth[3]; unsigned int NumEntries;/* # of QuantizedColorType in linked list below. */ long Count; /* Total number of pixels in all the entries. */ QuantizedColorType *QuantizedColors; } NewColorMapType; static int SubdivColorMap(NewColorMapType *NewColorSubdiv, unsigned int ColorMapSize, unsigned int *NewColorMapSize); #ifdef __MSDOS__ static int SortCmpRtn(const VoidPtr Entry1, const VoidPtr Entry2); #else static int SortCmpRtn(VoidPtr Entry1, VoidPtr Entry2); #endif /* __MSDOS__ */ /****************************************************************************** * Quantize high resolution image into lower one. Input image consists of a * * 2D array for each of the RGB colors with size Width by Height. There is no * * Color map for the input. Output is a quantized image with 2D array of * * indexes into the output color map. * * Note input image can be 24 bits at the most (8 for red/green/blue) and * * the output has 256 colors at the most (256 entries in the color map.). * * ColorMapSize specifies size of color map up to 256 and will be updated to * * real size before returning. * * Also non of the parameter are allocated by this routine. * * This function returns GIF_OK if succesfull, GIF_ERROR otherwise. * ******************************************************************************/ int QuantizeBuffer(unsigned int Width, unsigned int Height, int *ColorMapSize, GifByteType *RedInput, GifByteType *GreenInput, GifByteType *BlueInput, GifByteType *OutputBuffer, GifColorType *OutputColorMap) { unsigned int i, j, Index, NewColorMapSize, NumOfEntries, MaxRGBError[3]; long Red, Green, Blue; NewColorMapType NewColorSubdiv[256]; QuantizedColorType *ColorArrayEntries, *QuantizedColor; if ((ColorArrayEntries = (QuantizedColorType *) malloc(sizeof(QuantizedColorType) * COLOR_ARRAY_SIZE)) == NULL) { _GifError = E_GIF_ERR_NOT_ENOUGH_MEM; return GIF_ERROR; } for (i = 0; i < COLOR_ARRAY_SIZE; i++) { ColorArrayEntries[i].RGB[0]= i >> (2 * BITS_PER_PRIM_COLOR); ColorArrayEntries[i].RGB[1] = (i >> BITS_PER_PRIM_COLOR) & MAX_PRIM_COLOR; ColorArrayEntries[i].RGB[2] = i & MAX_PRIM_COLOR; ColorArrayEntries[i].Count = 0; } /* Sample the colors and their distribution: */ for (i = 0; i < Width * Height; i++) { Index = ((RedInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << (2 * BITS_PER_PRIM_COLOR)) + ((GreenInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << BITS_PER_PRIM_COLOR) + (BlueInput[i] >> (8 - BITS_PER_PRIM_COLOR)); ColorArrayEntries[Index].Count++; } /* Put all the colors in the first entry of the color map, and call the */ /* recursive subdivision process. */ for (i = 0; i < 256; i++) { NewColorSubdiv[i].QuantizedColors = NULL; NewColorSubdiv[i].Count = NewColorSubdiv[i].NumEntries = 0; for (j = 0; j < 3; j++) { NewColorSubdiv[i].RGBMin[j] = 0; NewColorSubdiv[i].RGBWidth[j] = 255; } } /* Find the non empty entries in the color table and chain them: */ for (i = 0; i < COLOR_ARRAY_SIZE; i++) if (ColorArrayEntries[i].Count > 0) break; QuantizedColor = NewColorSubdiv[0].QuantizedColors = &ColorArrayEntries[i]; NumOfEntries = 1; while (++i < COLOR_ARRAY_SIZE) if (ColorArrayEntries[i].Count > 0) { QuantizedColor -> Pnext = &ColorArrayEntries[i]; QuantizedColor = &ColorArrayEntries[i]; NumOfEntries++; } QuantizedColor -> Pnext = NULL; NewColorSubdiv[0].NumEntries = NumOfEntries;/* Different sampled colors. */ NewColorSubdiv[0].Count = ((long) Width) * Height; /* Pixels. */ NewColorMapSize = 1; if (SubdivColorMap(NewColorSubdiv, *ColorMapSize, &NewColorMapSize) != GIF_OK) { free((char *) ColorArrayEntries); return GIF_ERROR; } if (NewColorMapSize < *ColorMapSize) { /* And clear rest of color map: */ for (i = NewColorMapSize; i < *ColorMapSize; i++) OutputColorMap[i].Red = OutputColorMap[i].Green = OutputColorMap[i].Blue = 0; } /* Average the colors in each entry to be the color to be used in the */ /* output color map, and plug it into the output color map itself. */ for (i = 0; i < NewColorMapSize; i++) { if ((j = NewColorSubdiv[i].NumEntries) > 0) { QuantizedColor = NewColorSubdiv[i].QuantizedColors; Red = Green = Blue = 0; while (QuantizedColor) { QuantizedColor -> NewColorIndex = i; Red += QuantizedColor -> RGB[0]; Green += QuantizedColor -> RGB[1]; Blue += QuantizedColor -> RGB[2]; QuantizedColor = QuantizedColor -> Pnext; } OutputColorMap[i].Red = (Red << (8 - BITS_PER_PRIM_COLOR)) / j; OutputColorMap[i].Green = (Green << (8 - BITS_PER_PRIM_COLOR)) / j; OutputColorMap[i].Blue= (Blue << (8 - BITS_PER_PRIM_COLOR)) / j; } else GIF_MESSAGE("Null entry in quantized color map - thats weird."); } /* Finally scan the input buffer again and put the mapped index in the */ /* output buffer. */ MaxRGBError[0] = MaxRGBError[1] = MaxRGBError[2] = 0; for (i = 0; i < Width * Height; i++) { Index = ((RedInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << (2 * BITS_PER_PRIM_COLOR)) + ((GreenInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << BITS_PER_PRIM_COLOR) + (BlueInput[i] >> (8 - BITS_PER_PRIM_COLOR)); Index = ColorArrayEntries[Index].NewColorIndex; OutputBuffer[i] = Index; if (MaxRGBError[0] < ABS(OutputColorMap[Index].Red - RedInput[i])) MaxRGBError[0] = ABS(OutputColorMap[Index].Red - RedInput[i]); if (MaxRGBError[1] < ABS(OutputColorMap[Index].Green - GreenInput[i])) MaxRGBError[1] = ABS(OutputColorMap[Index].Green - GreenInput[i]); if (MaxRGBError[2] < ABS(OutputColorMap[Index].Blue - BlueInput[i])) MaxRGBError[2] = ABS(OutputColorMap[Index].Blue - BlueInput[i]); } #ifdef DEBUG fprintf(stderr, "Quantization L(0) errors: Red = %d, Green = %d, Blue = %d.\n", MaxRGBError[0], MaxRGBError[1], MaxRGBError[2]); #endif /* DEBUG */ free((char *) ColorArrayEntries); *ColorMapSize = NewColorMapSize; return GIF_OK; } /****************************************************************************** * Routine to subdivide the RGB space recursively using median cut in each * * axes alternatingly until ColorMapSize different cubes exists. * * The biggest cube in one dimension is subdivide unless it has only one entry.* * Returns GIF_ERROR if failed, otherwise GIF_OK. * ******************************************************************************/ static int SubdivColorMap(NewColorMapType *NewColorSubdiv, unsigned int ColorMapSize, unsigned int *NewColorMapSize) { int MaxSize; unsigned int i, j, Index = 0, NumEntries, MinColor, MaxColor; long Sum, Count; QuantizedColorType *QuantizedColor, **SortArray; while (ColorMapSize > *NewColorMapSize) { /* Find candidate for subdivision: */ MaxSize = -1; for (i = 0; i < *NewColorMapSize; i++) { for (j = 0; j < 3; j++) { if (((int) NewColorSubdiv[i].RGBWidth[j]) > MaxSize && NewColorSubdiv[i].NumEntries > 1) { MaxSize = NewColorSubdiv[i].RGBWidth[j]; Index = i; SortRGBAxis = j; } } } if (MaxSize == -1) return GIF_OK; /* Split the entry Index into two along the axis SortRGBAxis: */ /* Sort all elements in that entry along the given axis and split at */ /* the median. */ if ((SortArray = (QuantizedColorType **) malloc(sizeof(QuantizedColorType *) * NewColorSubdiv[Index].NumEntries)) == NULL) return GIF_ERROR; for (j = 0, QuantizedColor = NewColorSubdiv[Index].QuantizedColors; j < NewColorSubdiv[Index].NumEntries && QuantizedColor != NULL; j++, QuantizedColor = QuantizedColor -> Pnext) SortArray[j] = QuantizedColor; qsort(SortArray, NewColorSubdiv[Index].NumEntries, sizeof(QuantizedColorType *), SortCmpRtn); /* Relink the sorted list into one: */ for (j = 0; j < NewColorSubdiv[Index].NumEntries - 1; j++) SortArray[j] -> Pnext = SortArray[j + 1]; SortArray[NewColorSubdiv[Index].NumEntries - 1] -> Pnext = NULL; NewColorSubdiv[Index].QuantizedColors = QuantizedColor = SortArray[0]; free((char *) SortArray); /* Now simply add the Counts until we have half of the Count: */ Sum = NewColorSubdiv[Index].Count / 2 - QuantizedColor -> Count; NumEntries = 1; Count = QuantizedColor -> Count; while ((Sum -= QuantizedColor -> Pnext -> Count) >= 0 && QuantizedColor -> Pnext != NULL && QuantizedColor -> Pnext -> Pnext != NULL) { QuantizedColor = QuantizedColor -> Pnext; NumEntries++; Count += QuantizedColor -> Count; } /* Save the values of the last color of the first half, and first */ /* of the second half so we can update the Bounding Boxes later. */ /* Also as the colors are quantized and the BBoxes are full 0..255, */ /* they need to be rescaled. */ MaxColor = QuantizedColor -> RGB[SortRGBAxis];/* Max. of first half. */ MinColor = QuantizedColor -> Pnext -> RGB[SortRGBAxis];/* of second. */ MaxColor <<= (8 - BITS_PER_PRIM_COLOR); MinColor <<= (8 - BITS_PER_PRIM_COLOR); /* Partition right here: */ NewColorSubdiv[*NewColorMapSize].QuantizedColors = QuantizedColor -> Pnext; QuantizedColor -> Pnext = NULL; NewColorSubdiv[*NewColorMapSize].Count = Count; NewColorSubdiv[Index].Count -= Count; NewColorSubdiv[*NewColorMapSize].NumEntries = NewColorSubdiv[Index].NumEntries - NumEntries; NewColorSubdiv[Index].NumEntries = NumEntries; for (j = 0; j < 3; j++) { NewColorSubdiv[*NewColorMapSize].RGBMin[j] = NewColorSubdiv[Index].RGBMin[j]; NewColorSubdiv[*NewColorMapSize].RGBWidth[j] = NewColorSubdiv[Index].RGBWidth[j]; } NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] = NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] + NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] - MinColor; NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] = MinColor; NewColorSubdiv[Index].RGBWidth[SortRGBAxis] = MaxColor - NewColorSubdiv[Index].RGBMin[SortRGBAxis]; (*NewColorMapSize)++; } return GIF_OK; } /****************************************************************************** * Routine called by qsort to compare to entries. * ******************************************************************************/ #ifdef __MSDOS__ static int SortCmpRtn(const VoidPtr Entry1, const VoidPtr Entry2) #else static int SortCmpRtn(VoidPtr Entry1, VoidPtr Entry2) #endif /* __MSDOS__ */ { return (* ((QuantizedColorType **) Entry1)) -> RGB[SortRGBAxis] - (* ((QuantizedColorType **) Entry2)) -> RGB[SortRGBAxis]; }