home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 4 / DATAFILE_PDCD4.iso / utilities / utilsm / netpbmsca / ppm / c / ppmquant < prev    next >
Encoding:
Text File  |  1993-10-04  |  16.8 KB  |  620 lines
  1. /* ppmquant.c - quantize the colors in a pixmap down to a specified number
  2. **
  3. ** Copyright (C) 1989, 1991 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. #include "ppm.h"
  14. #include "ppmcmap.h"
  15.  
  16. #define MAXCOLORS 32767
  17.  
  18. /* #define LARGE_NORM */
  19. #define LARGE_LUM
  20.  
  21. /* #define REP_CENTER_BOX */
  22. /* #define REP_AVERAGE_COLORS */
  23. #define REP_AVERAGE_PIXELS
  24.  
  25. typedef struct box* box_vector;
  26. struct box
  27.     {
  28.     int ind;
  29.     int colors;
  30.     int sum;
  31.     };
  32.  
  33. static colorhist_vector mediancut ARGS(( colorhist_vector chv, int colors, int sum, pixval maxval, int newcolors ));
  34. static int redcompare ARGS(( colorhist_vector ch1, colorhist_vector ch2 ));
  35. static int greencompare ARGS(( colorhist_vector ch1, colorhist_vector ch2 ));
  36. static int bluecompare ARGS(( colorhist_vector ch1, colorhist_vector ch2 ));
  37. static int sumcompare ARGS(( box_vector b1, box_vector b2 ));
  38.  
  39. int
  40. main( argc, argv )
  41.     int argc;
  42.     char* argv[];
  43.     {
  44.     FILE* ifp;
  45.     pixel** pixels;
  46.     pixel** mappixels;
  47.     register pixel* pP;
  48.     int argn, rows, cols, maprows, mapcols, row;
  49.     register int col, limitcol;
  50.     pixval maxval, newmaxval, mapmaxval;
  51.     int newcolors, colors;
  52.     register int ind;
  53.     colorhist_vector chv, colormap;
  54.     colorhash_table cht;
  55.     int floyd;
  56.     int usehash;
  57.     long* thisrerr;
  58.     long* nextrerr;
  59.     long* thisgerr;
  60.     long* nextgerr;
  61.     long* thisberr;
  62.     long* nextberr;
  63.     long* temperr;
  64.     register long sr, sg, sb, err;
  65. #define FS_SCALE 1024
  66.     int fs_direction;
  67.     char* usage = "[-floyd|-fs] <ncolors> [ppmfile]\n                 [-floyd|-fs] -map mapfile [ppmfile]";
  68.  
  69.  
  70.     ppm_init( &argc, argv );
  71.  
  72.     argn = 1;
  73.     floyd = 0;
  74.     mappixels = (pixel**) 0;
  75.  
  76.     while ( argn < argc && argv[argn][0] == '-' && argv[argn][1] != '\0' )
  77.     {
  78.     if ( pm_keymatch( argv[argn], "-fs", 2 ) ||
  79.          pm_keymatch( argv[argn], "-floyd", 2 ) )
  80.         floyd = 1;
  81.     else if ( pm_keymatch( argv[argn], "-nofs", 2 ) ||
  82.          pm_keymatch( argv[argn], "-nofloyd", 2 ) )
  83.         floyd = 0;
  84.     else if ( pm_keymatch( argv[argn], "-map", 2 ) )
  85.         {
  86.         ++argn;
  87.         if ( argn == argc )
  88.         pm_usage( usage );
  89.         ifp = pm_openr( argv[argn] );
  90.         mappixels = ppm_readppm( ifp, &mapcols, &maprows, &mapmaxval );
  91.         pm_close( ifp );
  92.         if ( mapcols == 0 || maprows == 0 )
  93.         pm_error( "null colormap??" );
  94.         }
  95.     else
  96.         pm_usage( usage );
  97.     ++argn;
  98.     }
  99.  
  100.     if ( mappixels == (pixel**) 0 )
  101.     {
  102.     if ( argn == argc )
  103.         pm_usage( usage );
  104.     if ( sscanf( argv[argn], "%d", &newcolors ) != 1 )
  105.         pm_usage( usage );
  106.     if ( newcolors <= 1 )
  107.         pm_error( "number of colors must be > 1" );
  108.     ++argn;
  109.     }
  110.  
  111.     if ( argn != argc )
  112.     {
  113.     ifp = pm_openr( argv[argn] );
  114.     ++argn;
  115.     }
  116.     else
  117.     ifp = stdin;
  118.  
  119.     if ( argn != argc )
  120.     pm_usage( usage );
  121.  
  122.     /*
  123.     ** Step 1: read in the image.
  124.     */
  125.     pixels = ppm_readppm( ifp, &cols, &rows, &maxval );
  126.     pm_close( ifp );
  127.  
  128.  
  129.     if ( mappixels == (pixel**) 0 )
  130.     {
  131.     /*
  132.     ** Step 2: attempt to make a histogram of the colors, unclustered.
  133.     ** If at first we don't succeed, lower maxval to increase color
  134.     ** coherence and try again.  This will eventually terminate, with
  135.     ** maxval at worst 15, since 32^3 is approximately MAXCOLORS.
  136.     */
  137.     for ( ; ; )
  138.         {
  139.         pm_message( "making histogram..." );
  140.         chv = ppm_computecolorhist(
  141.         pixels, cols, rows, MAXCOLORS, &colors );
  142.         if ( chv != (colorhist_vector) 0 )
  143.         break;
  144.         pm_message( "too many colors!" );
  145.         newmaxval = maxval / 2;
  146.         pm_message(
  147.       "scaling colors from maxval=%d to maxval=%d to improve clustering...",
  148.             maxval, newmaxval );
  149.         for ( row = 0; row < rows; ++row )
  150.         for ( col = 0, pP = pixels[row]; col < cols; ++col, ++pP )
  151.             PPM_DEPTH( *pP, *pP, maxval, newmaxval );
  152.         maxval = newmaxval;
  153.         }
  154.     pm_message( "%d colors found", colors );
  155.  
  156.     /*
  157.     ** Step 3: apply median-cut to histogram, making the new colormap.
  158.     */
  159.     pm_message( "choosing %d colors...", newcolors );
  160.     colormap = mediancut( chv, colors, rows * cols, maxval, newcolors );
  161.     ppm_freecolorhist( chv );
  162.     }
  163.     else
  164.     {
  165.     /*
  166.     ** Alternate steps 2 & 3 : Turn mappixels into a colormap.
  167.     */
  168.     if ( mapmaxval != maxval )
  169.         {
  170.         if ( mapmaxval > maxval )
  171.         pm_message( "rescaling colormap colors" );
  172.         for ( row = 0; row < maprows; ++row )
  173.         for ( col = 0, pP = mappixels[row]; col < mapcols; ++col, ++pP )
  174.             PPM_DEPTH( *pP, *pP, mapmaxval, maxval );
  175.         mapmaxval = maxval;
  176.         }
  177.     colormap = ppm_computecolorhist(
  178.         mappixels, mapcols, maprows, MAXCOLORS, &newcolors );
  179.     if ( colormap == (colorhist_vector) 0 )
  180.         pm_error( "too many colors in colormap!" );
  181.     ppm_freearray( mappixels, maprows );
  182.     pm_message( "%d colors found in colormap", newcolors );
  183.     }
  184.  
  185.     /*
  186.     ** Step 4: map the colors in the image to their closest match in the
  187.     ** new colormap, and write 'em out.
  188.     */
  189.     pm_message( "mapping image to new colors..." );
  190.     cht = ppm_alloccolorhash( );
  191.     usehash = 1;
  192.     ppm_writeppminit( stdout, cols, rows, maxval, 0 );
  193.     if ( floyd )
  194.     {
  195.     /* Initialize Floyd-Steinberg error vectors. */
  196.     thisrerr = (long*) pm_allocrow( cols + 2, sizeof(long) );
  197.     nextrerr = (long*) pm_allocrow( cols + 2, sizeof(long) );
  198.     thisgerr = (long*) pm_allocrow( cols + 2, sizeof(long) );
  199.     nextgerr = (long*) pm_allocrow( cols + 2, sizeof(long) );
  200.     thisberr = (long*) pm_allocrow( cols + 2, sizeof(long) );
  201.     nextberr = (long*) pm_allocrow( cols + 2, sizeof(long) );
  202.     srandom( (int) ( time( 0 ) ^ getpid( ) ) );
  203.     for ( col = 0; col < cols + 2; ++col )
  204.         {
  205.         thisrerr[col] = random( ) % ( FS_SCALE * 2 ) - FS_SCALE;
  206.         thisgerr[col] = random( ) % ( FS_SCALE * 2 ) - FS_SCALE;
  207.         thisberr[col] = random( ) % ( FS_SCALE * 2 ) - FS_SCALE;
  208.         /* (random errors in [-1 .. 1]) */
  209.         }
  210.     fs_direction = 1;
  211.     }
  212.     for ( row = 0; row < rows; ++row )
  213.     {
  214.     if ( floyd )
  215.         for ( col = 0; col < cols + 2; ++col )
  216.         nextrerr[col] = nextgerr[col] = nextberr[col] = 0;
  217.     if ( ( ! floyd ) || fs_direction )
  218.         {
  219.         col = 0;
  220.         limitcol = cols;
  221.         pP = pixels[row];
  222.         }
  223.     else
  224.         {
  225.         col = cols - 1;
  226.         limitcol = -1;
  227.         pP = &(pixels[row][col]);
  228.         }
  229.     do
  230.         {
  231.         if ( floyd )
  232.         {
  233.         /* Use Floyd-Steinberg errors to adjust actual color. */
  234.         sr = PPM_GETR(*pP) + thisrerr[col + 1] / FS_SCALE;
  235.         sg = PPM_GETG(*pP) + thisgerr[col + 1] / FS_SCALE;
  236.         sb = PPM_GETB(*pP) + thisberr[col + 1] / FS_SCALE;
  237.         if ( sr < 0 ) sr = 0;
  238.         else if ( sr > maxval ) sr = maxval;
  239.         if ( sg < 0 ) sg = 0;
  240.         else if ( sg > maxval ) sg = maxval;
  241.         if ( sb < 0 ) sb = 0;
  242.         else if ( sb > maxval ) sb = maxval;
  243.         PPM_ASSIGN( *pP, sr, sg, sb );
  244.         }
  245.  
  246.         /* Check hash table to see if we have already matched this color. */
  247.         ind = ppm_lookupcolor( cht, pP );
  248.         if ( ind == -1 )
  249.         { /* No; search colormap for closest match. */
  250.         register int i, r1, g1, b1, r2, g2, b2;
  251.         register long dist, newdist;
  252.         r1 = PPM_GETR( *pP );
  253.         g1 = PPM_GETG( *pP );
  254.         b1 = PPM_GETB( *pP );
  255.         dist = 2000000000;
  256.         for ( i = 0; i < newcolors; ++i )
  257.             {
  258.             r2 = PPM_GETR( colormap[i].color );
  259.             g2 = PPM_GETG( colormap[i].color );
  260.             b2 = PPM_GETB( colormap[i].color );
  261.             newdist = ( r1 - r2 ) * ( r1 - r2 ) +
  262.                   ( g1 - g2 ) * ( g1 - g2 ) +
  263.                   ( b1 - b2 ) * ( b1 - b2 );
  264.             if ( newdist < dist )
  265.             {
  266.             ind = i;
  267.             dist = newdist;
  268.             }
  269.             }
  270.         if ( usehash )
  271.             {
  272.             if ( ppm_addtocolorhash( cht, pP, ind ) < 0 )
  273.             {
  274.             pm_message(
  275.            "out of memory adding to hash table, proceeding without it");
  276.             usehash = 0;
  277.             }
  278.             }
  279.         }
  280.  
  281.         if ( floyd )
  282.         {
  283.         /* Propagate Floyd-Steinberg error terms. */
  284.         if ( fs_direction )
  285.             {
  286.             err = ( sr - (long) PPM_GETR( colormap[ind].color ) ) * FS_SCALE;
  287.             thisrerr[col + 2] += ( err * 7 ) / 16;
  288.             nextrerr[col    ] += ( err * 3 ) / 16;
  289.             nextrerr[col + 1] += ( err * 5 ) / 16;
  290.             nextrerr[col + 2] += ( err     ) / 16;
  291.             err = ( sg - (long) PPM_GETG( colormap[ind].color ) ) * FS_SCALE;
  292.             thisgerr[col + 2] += ( err * 7 ) / 16;
  293.             nextgerr[col    ] += ( err * 3 ) / 16;
  294.             nextgerr[col + 1] += ( err * 5 ) / 16;
  295.             nextgerr[col + 2] += ( err     ) / 16;
  296.             err = ( sb - (long) PPM_GETB( colormap[ind].color ) ) * FS_SCALE;
  297.             thisberr[col + 2] += ( err * 7 ) / 16;
  298.             nextberr[col    ] += ( err * 3 ) / 16;
  299.             nextberr[col + 1] += ( err * 5 ) / 16;
  300.             nextberr[col + 2] += ( err     ) / 16;
  301.             }
  302.         else
  303.             {
  304.             err = ( sr - (long) PPM_GETR( colormap[ind].color ) ) * FS_SCALE;
  305.             thisrerr[col    ] += ( err * 7 ) / 16;
  306.             nextrerr[col + 2] += ( err * 3 ) / 16;
  307.             nextrerr[col + 1] += ( err * 5 ) / 16;
  308.             nextrerr[col    ] += ( err     ) / 16;
  309.             err = ( sg - (long) PPM_GETG( colormap[ind].color ) ) * FS_SCALE;
  310.             thisgerr[col    ] += ( err * 7 ) / 16;
  311.             nextgerr[col + 2] += ( err * 3 ) / 16;
  312.             nextgerr[col + 1] += ( err * 5 ) / 16;
  313.             nextgerr[col    ] += ( err     ) / 16;
  314.             err = ( sb - (long) PPM_GETB( colormap[ind].color ) ) * FS_SCALE;
  315.             thisberr[col    ] += ( err * 7 ) / 16;
  316.             nextberr[col + 2] += ( err * 3 ) / 16;
  317.             nextberr[col + 1] += ( err * 5 ) / 16;
  318.             nextberr[col    ] += ( err     ) / 16;
  319.             }
  320.         }
  321.  
  322.         *pP = colormap[ind].color;
  323.  
  324.         if ( ( ! floyd ) || fs_direction )
  325.         {
  326.         ++col;
  327.         ++pP;
  328.         }
  329.         else
  330.         {
  331.         --col;
  332.         --pP;
  333.         }
  334.         }
  335.     while ( col != limitcol );
  336.  
  337.     if ( floyd )
  338.         {
  339.         temperr = thisrerr;
  340.         thisrerr = nextrerr;
  341.         nextrerr = temperr;
  342.         temperr = thisgerr;
  343.         thisgerr = nextgerr;
  344.         nextgerr = temperr;
  345.         temperr = thisberr;
  346.         thisberr = nextberr;
  347.         nextberr = temperr;
  348.         fs_direction = ! fs_direction;
  349.         }
  350.  
  351.     ppm_writeppmrow( stdout, pixels[row], cols, maxval, 0 );
  352.     }
  353.  
  354.     pm_close( stdout );
  355.  
  356.     exit( 0 );
  357.     }
  358.  
  359. /*
  360. ** Here is the fun part, the median-cut colormap generator.  This is based
  361. ** on Paul Heckbert's paper "Color Image Quantization for Frame Buffer
  362. ** Display", SIGGRAPH '82 Proceedings, page 297.
  363. */
  364.  
  365. #if __STDC__
  366. static colorhist_vector
  367. mediancut( colorhist_vector chv, int colors, int sum, pixval maxval, int newcolors )
  368. #else /*__STDC__*/
  369. static colorhist_vector
  370. mediancut( chv, colors, sum, maxval, newcolors )
  371.     colorhist_vector chv;
  372.     int colors, sum, newcolors;
  373.     pixval maxval;
  374. #endif /*__STDC__*/
  375.     {
  376.     colorhist_vector colormap;
  377.     box_vector bv;
  378.     register int bi, i;
  379.     int boxes;
  380.  
  381.     bv = (box_vector) malloc( sizeof(struct box) * newcolors );
  382.     colormap =
  383.     (colorhist_vector) malloc( sizeof(struct colorhist_item) * newcolors );
  384.     if ( bv == (box_vector) 0 || colormap == (colorhist_vector) 0 )
  385.     pm_error( "out of memory" );
  386.     for ( i = 0; i < newcolors; ++i )
  387.     PPM_ASSIGN( colormap[i].color, 0, 0, 0 );
  388.  
  389.     /*
  390.     ** Set up the initial box.
  391.     */
  392.     bv[0].ind = 0;
  393.     bv[0].colors = colors;
  394.     bv[0].sum = sum;
  395.     boxes = 1;
  396.  
  397.     /*
  398.     ** Main loop: split boxes until we have enough.
  399.     */
  400.     while ( boxes < newcolors )
  401.     {
  402.     register int indx, clrs;
  403.     int sm;
  404.     register int minr, maxr, ming, maxg, minb, maxb, v;
  405.     int halfsum, lowersum;
  406.  
  407.     /*
  408.     ** Find the first splittable box.
  409.     */
  410.     for ( bi = 0; bi < boxes; ++bi )
  411.         if ( bv[bi].colors >= 2 )
  412.         break;
  413.     if ( bi == boxes )
  414.         break;    /* ran out of colors! */
  415.     indx = bv[bi].ind;
  416.     clrs = bv[bi].colors;
  417.     sm = bv[bi].sum;
  418.  
  419.     /*
  420.     ** Go through the box finding the minimum and maximum of each
  421.     ** component - the boundaries of the box.
  422.     */
  423.     minr = maxr = PPM_GETR( chv[indx].color );
  424.     ming = maxg = PPM_GETG( chv[indx].color );
  425.     minb = maxb = PPM_GETB( chv[indx].color );
  426.     for ( i = 1; i < clrs; ++i )
  427.         {
  428.         v = PPM_GETR( chv[indx + i].color );
  429.         if ( v < minr ) minr = v;
  430.         if ( v > maxr ) maxr = v;
  431.         v = PPM_GETG( chv[indx + i].color );
  432.         if ( v < ming ) ming = v;
  433.         if ( v > maxg ) maxg = v;
  434.         v = PPM_GETB( chv[indx + i].color );
  435.         if ( v < minb ) minb = v;
  436.         if ( v > maxb ) maxb = v;
  437.         }
  438.  
  439.     /*
  440.     ** Find the largest dimension, and sort by that component.  I have
  441.     ** included two methods for determining the "largest" dimension;
  442.     ** first by simply comparing the range in RGB space, and second
  443.     ** by transforming into luminosities before the comparison.  You
  444.     ** can switch which method is used by switching the commenting on
  445.     ** the LARGE_ defines at the beginning of this source file.
  446.     */
  447. #ifdef LARGE_NORM
  448.     if ( maxr - minr >= maxg - ming && maxr - minr >= maxb - minb )
  449.         qsort(
  450.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  451.         redcompare );
  452.     else if ( maxg - ming >= maxb - minb )
  453.         qsort(
  454.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  455.         greencompare );
  456.     else
  457.         qsort(
  458.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  459.         bluecompare );
  460. #endif /*LARGE_NORM*/
  461. #ifdef LARGE_LUM
  462.     {
  463.     pixel p;
  464.     float rl, gl, bl;
  465.  
  466.     PPM_ASSIGN(p, maxr - minr, 0, 0);
  467.     rl = PPM_LUMIN(p);
  468.     PPM_ASSIGN(p, 0, maxg - ming, 0);
  469.     gl = PPM_LUMIN(p);
  470.     PPM_ASSIGN(p, 0, 0, maxb - minb);
  471.     bl = PPM_LUMIN(p);
  472.  
  473.     if ( rl >= gl && rl >= bl )
  474.         qsort(
  475.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  476.         redcompare );
  477.     else if ( gl >= bl )
  478.         qsort(
  479.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  480.         greencompare );
  481.     else
  482.         qsort(
  483.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  484.         bluecompare );
  485.     }
  486. #endif /*LARGE_LUM*/
  487.     
  488.     /*
  489.     ** Now find the median based on the counts, so that about half the
  490.     ** pixels (not colors, pixels) are in each subdivision.
  491.     */
  492.     lowersum = chv[indx].value;
  493.     halfsum = sm / 2;
  494.     for ( i = 1; i < clrs - 1; ++i )
  495.         {
  496.         if ( lowersum >= halfsum )
  497.         break;
  498.         lowersum += chv[indx + i].value;
  499.         }
  500.  
  501.     /*
  502.     ** Split the box, and sort to bring the biggest boxes to the top.
  503.     */
  504.     bv[bi].colors = i;
  505.     bv[bi].sum = lowersum;
  506.     bv[boxes].ind = indx + i;
  507.     bv[boxes].colors = clrs - i;
  508.     bv[boxes].sum = sm - lowersum;
  509.     ++boxes;
  510.     qsort( (char*) bv, boxes, sizeof(struct box), sumcompare );
  511.     }
  512.  
  513.     /*
  514.     ** Ok, we've got enough boxes.  Now choose a representative color for
  515.     ** each box.  There are a number of possible ways to make this choice.
  516.     ** One would be to choose the center of the box; this ignores any structure
  517.     ** within the boxes.  Another method would be to average all the colors in
  518.     ** the box - this is the method specified in Heckbert's paper.  A third
  519.     ** method is to average all the pixels in the box.  You can switch which
  520.     ** method is used by switching the commenting on the REP_ defines at
  521.     ** the beginning of this source file.
  522.     */
  523.     for ( bi = 0; bi < boxes; ++bi )
  524.     {
  525. #ifdef REP_CENTER_BOX
  526.     register int indx = bv[bi].ind;
  527.     register int clrs = bv[bi].colors;
  528.     register int minr, maxr, ming, maxg, minb, maxb, v;
  529.  
  530.     minr = maxr = PPM_GETR( chv[indx].color );
  531.     ming = maxg = PPM_GETG( chv[indx].color );
  532.     minb = maxb = PPM_GETB( chv[indx].color );
  533.     for ( i = 1; i < clrs; ++i )
  534.         {
  535.         v = PPM_GETR( chv[indx + i].color );
  536.         minr = min( minr, v );
  537.         maxr = max( maxr, v );
  538.         v = PPM_GETG( chv[indx + i].color );
  539.         ming = min( ming, v );
  540.         maxg = max( maxg, v );
  541.         v = PPM_GETB( chv[indx + i].color );
  542.         minb = min( minb, v );
  543.         maxb = max( maxb, v );
  544.         }
  545.     PPM_ASSIGN(
  546.         colormap[bi].color, ( minr + maxr ) / 2, ( ming + maxg ) / 2,
  547.         ( minb + maxb ) / 2 );
  548. #endif /*REP_CENTER_BOX*/
  549. #ifdef REP_AVERAGE_COLORS
  550.     register int indx = bv[bi].ind;
  551.     register int clrs = bv[bi].colors;
  552.     register long r = 0, g = 0, b = 0;
  553.  
  554.     for ( i = 0; i < clrs; ++i )
  555.         {
  556.         r += PPM_GETR( chv[indx + i].color );
  557.         g += PPM_GETG( chv[indx + i].color );
  558.         b += PPM_GETB( chv[indx + i].color );
  559.         }
  560.     r = r / clrs;
  561.     g = g / clrs;
  562.     b = b / clrs;
  563.     PPM_ASSIGN( colormap[bi].color, r, g, b );
  564. #endif /*REP_AVERAGE_COLORS*/
  565. #ifdef REP_AVERAGE_PIXELS
  566.     register int indx = bv[bi].ind;
  567.     register int clrs = bv[bi].colors;
  568.     register long r = 0, g = 0, b = 0, sum = 0;
  569.  
  570.     for ( i = 0; i < clrs; ++i )
  571.         {
  572.         r += PPM_GETR( chv[indx + i].color ) * chv[indx + i].value;
  573.         g += PPM_GETG( chv[indx + i].color ) * chv[indx + i].value;
  574.         b += PPM_GETB( chv[indx + i].color ) * chv[indx + i].value;
  575.         sum += chv[indx + i].value;
  576.         }
  577.     r = r / sum;
  578.     if ( r > maxval ) r = maxval;    /* avoid math errors */
  579.     g = g / sum;
  580.     if ( g > maxval ) g = maxval;
  581.     b = b / sum;
  582.     if ( b > maxval ) b = maxval;
  583.     PPM_ASSIGN( colormap[bi].color, r, g, b );
  584. #endif /*REP_AVERAGE_PIXELS*/
  585.     }
  586.  
  587.     /*
  588.     ** All done.
  589.     */
  590.     return colormap;
  591.     }
  592.  
  593. static int
  594. redcompare( ch1, ch2 )
  595.     colorhist_vector ch1, ch2;
  596.     {
  597.     return (int) PPM_GETR( ch1->color ) - (int) PPM_GETR( ch2->color );
  598.     }
  599.  
  600. static int
  601. greencompare( ch1, ch2 )
  602.     colorhist_vector ch1, ch2;
  603.     {
  604.     return (int) PPM_GETG( ch1->color ) - (int) PPM_GETG( ch2->color );
  605.     }
  606.  
  607. static int
  608. bluecompare( ch1, ch2 )
  609.     colorhist_vector ch1, ch2;
  610.     {
  611.     return (int) PPM_GETB( ch1->color ) - (int) PPM_GETB( ch2->color );
  612.     }
  613.  
  614. static int
  615. sumcompare( b1, b2 )
  616.     box_vector b1, b2;
  617.     {
  618.     return b2->sum - b1->sum;
  619.     }
  620.