home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD1.iso / CDRom / PHOTOC12.LZX / src / ppm2aga / ppmcolorlib.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-04-15  |  12.1 KB  |  481 lines
  1. /* pbm color utility library
  2. **
  3. ** Copyright (C) 1988 by Jef Poskanzer.
  4. **
  5. ** Permission to use, copy, modify, and distribute this software and its
  6. ** documentation for any purpose and without fee is hereby granted, provided
  7. ** that the above copyright notice appear in all copies and that both that
  8. ** copyright notice and this permission notice appear in supporting
  9. ** documentation.  This software is provided "as is" without express or
  10. ** implied warranty.
  11. */
  12.  
  13. /* modified by Günther Röhrich */
  14. /* WARNING: This file is not for use with normal pbm programs */
  15.  
  16. /* support functions for the ppm color stuff */
  17.  
  18. #include "ppm.h"
  19. #include "ppm2AGA.h"
  20. #include "libpbm.h"
  21. #include "libppm.h"
  22. #include "libpgm.h"
  23.  
  24.  
  25. #define HASH_SIZE 20023
  26.  
  27. #ifdef PPM_PACKCOLORS
  28. #define ppm_hashpixel(p) ( ( (int) (p) & 0x7fffffff ) % HASH_SIZE )
  29. #else /*PPM_PACKCOLORS*/
  30. #define ppm_hashpixel(p) ( ( ( (long) (PPM_GETR(p)>>cluster) * 33023\
  31.  + (long) (PPM_GETG(p)>>cluster) * 30013 +\
  32.  ((long) PPM_GETB(p)>>cluster) * 27011 ) & 0x7fffffff ) % HASH_SIZE )
  33.  
  34. #endif /*PPM_PACKCOLORS*/
  35.  
  36. #define C_EQUAL(p,q) ( ((p).r>>cluster==(q).r>>cluster) &&\
  37. ((p).g>>cluster==(q).g>>cluster) && ((p).b>>cluster==(q).b>>cluster) )
  38.  
  39. extern int AbortCheck(void);
  40.  
  41. typedef struct box* box_vector;
  42.  
  43. struct box
  44.     {
  45.     int ind;
  46.     int colors;
  47.     int sum;
  48.     };
  49.  
  50. static int
  51. redcompare( ch1, ch2 )
  52.     colorhist_vector ch1, ch2;
  53.     {
  54.     return (int) PPM_GETR( ch1->color ) - (int) PPM_GETR( ch2->color );
  55.     }
  56.  
  57. static int
  58. greencompare( ch1, ch2 )
  59.     colorhist_vector ch1, ch2;
  60.     {
  61.     return (int) PPM_GETG( ch1->color ) - (int) PPM_GETG( ch2->color );
  62.     }
  63.  
  64. static int
  65. bluecompare( ch1, ch2 )
  66.     colorhist_vector ch1, ch2;
  67.     {
  68.     return (int) PPM_GETB( ch1->color ) - (int) PPM_GETB( ch2->color );
  69.     }
  70.  
  71. static int
  72. sumcompare( b1, b2 )
  73.     box_vector b1, b2;
  74.     {
  75.     return b2->sum - b1->sum;
  76.     }
  77.  
  78. colorhist_vector
  79. ppm_fcomputecolorhist(FILE *pixels, int cols, int rows,
  80.                   int maxcolors, int *colorsP, int ColorShift, int cluster)
  81.     {
  82.     colorhash_table cht;
  83.     colorhist_vector chv;
  84.  
  85.     cht = ppm_fcomputecolorhash( pixels, cols, rows, maxcolors,
  86.                                  colorsP, ColorShift, cluster);
  87.     if ( cht == (colorhash_table) 0 )
  88.     return (colorhist_vector) 0;
  89.     chv = ppm_fcolorhashtocolorhist( cht, maxcolors, cluster);
  90.     ppm_freecolorhash( cht );
  91.     return chv;
  92.     }
  93.  
  94.  
  95. colorhash_table
  96. ppm_fcomputecolorhash(FILE *pixels, int cols, int rows, 
  97.                       int maxcolors, int *colorsP, int ColorShift, int cluster)
  98.   {
  99.     colorhash_table cht;
  100.     register pixel* pP;
  101.     colorhist_list chl;
  102.     int col, row, hash;
  103.  
  104.     cht = ppm_alloccolorhash( );
  105.     *colorsP = 0;
  106.  
  107.     /* Go through the entire image, building a hash table of colors. */
  108.     for ( row = 0; row < rows; ++row )
  109.     {
  110.       if(AbortCheck())
  111.       {
  112.         ppm_freecolorhash(cht);
  113.         pm_error("^C\n");
  114.       }
  115.       for ( col = 0, pP = next_pixrow(pixels, row, ColorShift); col < cols; ++col, ++pP )
  116.       {            
  117.         hash = ppm_hashpixel( *pP );
  118.     for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
  119.       if ( C_EQUAL( chl->ch.color, *pP ) ) break;
  120.     if ( chl != (colorhist_list) 0 )
  121.           ++(chl->ch.value);
  122.     else
  123.     {
  124.       if ( ++(*colorsP) > maxcolors )
  125.       {
  126.         ppm_freecolorhash( cht );
  127.         return (colorhash_table) 0;
  128.       }
  129.       chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
  130.       if ( chl == 0 )
  131.           {
  132.             ppm_freecolorhash(cht);
  133.         pm_error( "out of memory computing hash table\n" );
  134.           }
  135.       chl->ch.color = *pP;
  136.       chl->ch.value = 1;
  137.       chl->next = cht[hash];
  138.       cht[hash] = chl;
  139.     }
  140.       }
  141.     }
  142.     return cht;
  143.   }
  144.  
  145. colorhash_table
  146. ppm_alloccolorhash( )
  147.     {
  148.     colorhash_table cht;
  149.     int i;
  150.  
  151.     cht = (colorhash_table) malloc( HASH_SIZE * sizeof(colorhist_list) );
  152.     if ( cht == 0 )
  153.     pm_error( "out of memory allocating hash table\n" );
  154.  
  155.     for ( i = 0; i < HASH_SIZE; ++i )
  156.     cht[i] = (colorhist_list) 0;
  157.  
  158.     return cht;
  159.     }
  160.  
  161. colorhist_vector
  162. ppm_fcolorhashtocolorhist(colorhash_table cht,int  maxcolors,int cluster)
  163.     {
  164.     colorhist_vector chv;
  165.     colorhist_list chl;
  166.     int i, j;
  167.  
  168.     /* Now collate the hash table into a simple colorhist array. */
  169.     chv = (colorhist_vector) malloc( maxcolors * sizeof(struct colorhist_item) );
  170.     /* (Leave room for expansion by caller.) */
  171.     if ( chv == (colorhist_vector) 0 )
  172.         {
  173.         ppm_freecolorhash(cht);
  174.     pm_error( "out of memory generating histogram\n" );
  175.         }
  176.  
  177.     /* Loop through the hash table. */
  178.     j = 0;
  179.     for ( i = 0; i < HASH_SIZE; ++i )
  180.     for ( chl = cht[i]; chl != (colorhist_list) 0; chl = chl->next )
  181.         {
  182.         /* Add the new entry. */
  183.         chv[j] = chl->ch;
  184.         ++j;
  185.         }
  186.  
  187.     /* All done. */
  188.     return chv;
  189.     }
  190.  
  191. void
  192. ppm_freecolorhist( chv )
  193.     colorhist_vector chv;
  194.     {
  195.     free( (char*) chv );
  196.     }
  197.  
  198. void
  199. ppm_freecolorhash( cht )
  200.     colorhash_table cht;
  201.     {
  202.     int i;
  203.     colorhist_list chl, chlnext;
  204.  
  205.     for ( i = 0; i < HASH_SIZE; ++i )
  206.     for ( chl = cht[i]; chl != (colorhist_list) 0; chl = chlnext )
  207.         {
  208.         chlnext = chl->next;
  209.         free( (char*) chl );
  210.         }
  211.     free( (char*) cht );
  212.     }
  213.  
  214.  
  215.  
  216. int
  217. ppm_lookupcolor( cht, colorP )
  218.     colorhash_table cht;
  219.     pixel* colorP;
  220.     {
  221.     int hash;
  222.     colorhist_list chl;
  223.     int cluster = 0;
  224.  
  225.     hash = ppm_hashpixel( *colorP );
  226.     for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
  227.     if ( PPM_EQUAL( chl->ch.color, *colorP ) )
  228.         return chl->ch.value;
  229.  
  230.     return -1;
  231.     }
  232.  
  233. int
  234. ppm_addtocolorhash( cht, colorP, value )
  235.     colorhash_table cht;
  236.     pixel* colorP;
  237.     int value;
  238.     {
  239.     register int hash;
  240.     register colorhist_list chl;
  241.     int cluster = 0;
  242.  
  243.     chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
  244.     if ( chl == 0 )
  245.     return -1;
  246.     hash = ppm_hashpixel( *colorP );
  247.     chl->ch.color = *colorP;
  248.     chl->ch.value = value;
  249.     chl->next = cht[hash];
  250.     cht[hash] = chl;
  251.     return 0;
  252.     }
  253.  
  254.  
  255. /*
  256. ** Here is the fun part, the median-cut colormap generator.  This is based
  257. ** on Paul Heckbert's paper "Color Image Quantization for Frame Buffer
  258. ** Display", SIGGRAPH '82 Proceedings, page 297.
  259. */
  260.  
  261. colorhist_vector
  262. mediancut( colorhist_vector chv, int colors, int sum, pixval maxval, int newcolors )
  263.     {
  264.     colorhist_vector colormap;
  265.     box_vector bv;
  266.     register int bi, i;
  267.     int boxes;
  268.  
  269.     bv = (box_vector) malloc( sizeof(struct box) * newcolors );
  270.     colormap =
  271.     (colorhist_vector) malloc( sizeof(struct colorhist_item) * newcolors );
  272.     if ( bv == (box_vector) 0 || colormap == (colorhist_vector) 0 )
  273.     pm_error( "out of memory" );
  274.     for ( i = 0; i < newcolors; ++i )
  275.     PPM_ASSIGN( colormap[i].color, 0, 0, 0 );
  276.  
  277.     /*
  278.     ** Set up the initial box.
  279.     */
  280.     bv[0].ind = 0;
  281.     bv[0].colors = colors;
  282.     bv[0].sum = sum;
  283.     boxes = 1;
  284.  
  285.     /*
  286.     ** Main loop: split boxes until we have enough.
  287.     */
  288.     while ( boxes < newcolors )
  289.     {
  290.     register int indx, clrs;
  291.     int sm;
  292.     register int minr, maxr, ming, maxg, minb, maxb, v;
  293.     int halfsum, lowersum;
  294.  
  295.     /*
  296.     ** Find the first splittable box.
  297.     */
  298.     for ( bi = 0; bi < boxes; ++bi )
  299.         if ( bv[bi].colors >= 2 )
  300.         break;
  301.     if ( bi == boxes )
  302.         break;    /* ran out of colors! */
  303.     indx = bv[bi].ind;
  304.     clrs = bv[bi].colors;
  305.     sm = bv[bi].sum;
  306.  
  307.     /*
  308.     ** Go through the box finding the minimum and maximum of each
  309.     ** component - the boundaries of the box.
  310.     */
  311.     minr = maxr = PPM_GETR( chv[indx].color );
  312.     ming = maxg = PPM_GETG( chv[indx].color );
  313.     minb = maxb = PPM_GETB( chv[indx].color );
  314.     for ( i = 1; i < clrs; ++i )
  315.         {
  316.         v = PPM_GETR( chv[indx + i].color );
  317.         if ( v < minr ) minr = v;
  318.         if ( v > maxr ) maxr = v;
  319.         v = PPM_GETG( chv[indx + i].color );
  320.         if ( v < ming ) ming = v;
  321.         if ( v > maxg ) maxg = v;
  322.         v = PPM_GETB( chv[indx + i].color );
  323.         if ( v < minb ) minb = v;
  324.         if ( v > maxb ) maxb = v;
  325.         }
  326.  
  327.     /*
  328.     ** Find the largest dimension, and sort by that component.  I have
  329.     ** included two methods for determining the "largest" dimension;
  330.     ** first by simply comparing the range in RGB space, and second
  331.     ** by transforming into luminosities before the comparison.  You
  332.     ** can switch which method is used by switching the commenting on
  333.     ** the LARGE_ defines at the beginning of this source file.
  334.     */
  335. #ifdef LARGE_NORM
  336.     if ( maxr - minr >= maxg - ming && maxr - minr >= maxb - minb )
  337.         qsort(
  338.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  339.         redcompare );
  340.     else if ( maxg - ming >= maxb - minb )
  341.         qsort(
  342.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  343.         greencompare );
  344.     else
  345.         qsort(
  346.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  347.         bluecompare );
  348. #endif /*LARGE_NORM*/
  349. #ifdef LARGE_LUM
  350.     {
  351.     pixel p;
  352.     float rl, gl, bl;
  353.  
  354.     PPM_ASSIGN(p, maxr - minr, 0, 0);
  355.     rl = PPM_LUMIN(p);
  356.     PPM_ASSIGN(p, 0, maxg - ming, 0);
  357.     gl = PPM_LUMIN(p);
  358.     PPM_ASSIGN(p, 0, 0, maxb - minb);
  359.     bl = PPM_LUMIN(p);
  360.  
  361.     if ( rl >= gl && rl >= bl )
  362.         qsort(
  363.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  364.         redcompare );
  365.     else if ( gl >= bl )
  366.         qsort(
  367.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  368.         greencompare );
  369.     else
  370.         qsort(
  371.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  372.         bluecompare );
  373.     }
  374. #endif /*LARGE_LUM*/
  375.     
  376.     /*
  377.     ** Now find the median based on the counts, so that about half the
  378.     ** pixels (not colors, pixels) are in each subdivision.
  379.     */
  380.     lowersum = chv[indx].value;
  381.     halfsum = sm / 2;
  382.     for ( i = 1; i < clrs - 1; ++i )
  383.         {
  384.         if ( lowersum >= halfsum )
  385.         break;
  386.         lowersum += chv[indx + i].value;
  387.         }
  388.  
  389.     /*
  390.     ** Split the box, and sort to bring the biggest boxes to the top.
  391.     */
  392.     bv[bi].colors = i;
  393.     bv[bi].sum = lowersum;
  394.     bv[boxes].ind = indx + i;
  395.     bv[boxes].colors = clrs - i;
  396.     bv[boxes].sum = sm - lowersum;
  397.     ++boxes;
  398.     qsort( (char*) bv, boxes, sizeof(struct box), sumcompare );
  399.     }
  400.  
  401.     /*
  402.     ** Ok, we've got enough boxes.  Now choose a representative color for
  403.     ** each box.  There are a number of possible ways to make this choice.
  404.     ** One would be to choose the center of the box; this ignores any structure
  405.     ** within the boxes.  Another method would be to average all the colors in
  406.     ** the box - this is the method specified in Heckbert's paper.  A third
  407.     ** method is to average all the pixels in the box.  You can switch which
  408.     ** method is used by switching the commenting on the REP_ defines at
  409.     ** the beginning of this source file.
  410.     */
  411.     for ( bi = 0; bi < boxes; ++bi )
  412.     {
  413. #ifdef REP_CENTER_BOX
  414.     register int indx = bv[bi].ind;
  415.     register int clrs = bv[bi].colors;
  416.     register int minr, maxr, ming, maxg, minb, maxb, v;
  417.  
  418.     minr = maxr = PPM_GETR( chv[indx].color );
  419.     ming = maxg = PPM_GETG( chv[indx].color );
  420.     minb = maxb = PPM_GETB( chv[indx].color );
  421.     for ( i = 1; i < clrs; ++i )
  422.         {
  423.         v = PPM_GETR( chv[indx + i].color );
  424.         minr = min( minr, v );
  425.         maxr = max( maxr, v );
  426.         v = PPM_GETG( chv[indx + i].color );
  427.         ming = min( ming, v );
  428.         maxg = max( maxg, v );
  429.         v = PPM_GETB( chv[indx + i].color );
  430.         minb = min( minb, v );
  431.         maxb = max( maxb, v );
  432.         }
  433.     PPM_ASSIGN(
  434.         colormap[bi].color, ( minr + maxr ) / 2, ( ming + maxg ) / 2,
  435.         ( minb + maxb ) / 2 );
  436. #endif /*REP_CENTER_BOX*/
  437. #ifdef REP_AVERAGE_COLORS
  438.     register int indx = bv[bi].ind;
  439.     register int clrs = bv[bi].colors;
  440.     register long r = 0, g = 0, b = 0;
  441.  
  442.     for ( i = 0; i < clrs; ++i )
  443.         {
  444.         r += PPM_GETR( chv[indx + i].color );
  445.         g += PPM_GETG( chv[indx + i].color );
  446.         b += PPM_GETB( chv[indx + i].color );
  447.         }
  448.     r = r / clrs;
  449.     g = g / clrs;
  450.     b = b / clrs;
  451.     PPM_ASSIGN( colormap[bi].color, r, g, b );
  452. #endif /*REP_AVERAGE_COLORS*/
  453. #ifdef REP_AVERAGE_PIXELS
  454.     register int indx = bv[bi].ind;
  455.     register int clrs = bv[bi].colors;
  456.     register long r = 0, g = 0, b = 0, sum = 0;
  457.  
  458.     for ( i = 0; i < clrs; ++i )
  459.         {
  460.         r += PPM_GETR( chv[indx + i].color ) * chv[indx + i].value;
  461.         g += PPM_GETG( chv[indx + i].color ) * chv[indx + i].value;
  462.         b += PPM_GETB( chv[indx + i].color ) * chv[indx + i].value;
  463.         sum += chv[indx + i].value;
  464.         }
  465.     r = r / sum;
  466.     if ( r > maxval ) r = maxval;    /* avoid math errors */
  467.     g = g / sum;
  468.     if ( g > maxval ) g = maxval;
  469.     b = b / sum;
  470.     if ( b > maxval ) b = maxval;
  471.     PPM_ASSIGN( colormap[bi].color, r, g, b );
  472. #endif /*REP_AVERAGE_PIXELS*/
  473.     }
  474.  
  475.     /*
  476.     ** All done.
  477.     */
  478.     return colormap;
  479.     }
  480.  
  481.