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