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