home *** CD-ROM | disk | FTP | other *** search
/ Encyclopedia of Graphics File Formats Companion / GFF_CD.ISO / software / unix / saoimage / sao1_07.tar / histdist.c < prev    next >
C/C++ Source or Header  |  1990-04-20  |  7KB  |  258 lines
  1. #ifndef lint
  2. static char SccsId[] = "%W%  %G%";
  3. #endif
  4.  
  5. /* Module:    histdist.c (Histogram Equalize Distribute)
  6.  * Subroutine:    distribute_levels()            returns: int
  7.  * Copyright:    1989 Smithsonian Astrophysical Observatory
  8.  *        You may do anything you like with this file except remove
  9.  *        this copyright.  The Smithsonian Astrophysical Observatory
  10.  *        makes no representations about the suitability of this
  11.  *        software for any purpose.  It is provided "as is" without
  12.  *        express or implied warranty.
  13.  * Modified:    {0} Michael VanHilst    initial version          30 May 1989
  14.  *        {1} MVH fixed bug in range_zgroup           7 Dec 1989
  15.  *        {n} <who> -- <does what> -- <when>
  16.  */
  17.  
  18. #include <stdio.h>
  19. #include "hfiles/histeq.h"        /* define SubrangeLink */
  20.  
  21. /*
  22.  * Subroutine:    distribute_levels
  23.  * Purpose:    Distribute the levels among histogram sub-groups
  24.  * Returns:    number of groups with no assigned color levels
  25.  */
  26. int distribute_levels ( linklist, pixel_area, color_levels,
  27.                 pmin, pmax, ncolor )
  28.      SubrangeLink *linklist;
  29.      int pixel_area, color_levels;
  30.      int pmin, pmax, ncolor;
  31. {
  32.   int average;
  33.   int threshold;
  34.   int excess;
  35.   int levels, zeroes;
  36.   int max_z_excess, max_nz_excess, max_z_range;
  37.   SubrangeLink *subrange;
  38. #ifdef DEBUG
  39.   int census = 0;
  40. #endif
  41.   static int excess_zgroup(), excess_nzgroup(), range_zgroup();
  42.  
  43.   /* if all one group (no strong peaks), allocation is simple */
  44.   if( linklist->next == 0 ) {
  45.     linklist->color_levels = ncolor;
  46.     return( 0 );
  47.   }
  48.   /* average is rounded strongly upward to be stingy with levels */
  49.   average = (pixel_area / color_levels) + 1;
  50.   subrange = linklist;
  51.   zeroes = 0;
  52.   max_z_excess = max_nz_excess = 0;
  53.   max_z_range = 0;
  54.   /* first pass, simple assignment and some note taking */
  55.   while( subrange != 0 ) {
  56.     if( subrange->range > 0 ) {
  57.       levels = subrange->pixel_area / average;
  58.       excess = subrange->pixel_area - (levels * average);
  59.       if( levels >= subrange->range ) {
  60.     levels = subrange->range;
  61.     subrange->range = -subrange->range;
  62.       } else {
  63.     if( levels == 0 ) {
  64.       zeroes++;
  65.       if( excess > max_z_excess )
  66.         max_z_excess = excess;
  67.       if( subrange->range > max_z_range )
  68.         max_z_range = subrange->range;
  69.     } else {
  70.       if( excess > max_nz_excess )
  71.         max_nz_excess = excess;
  72.     }
  73.       }
  74.       subrange->color_levels = levels;
  75.       subrange->excess_pixels = excess;
  76.       color_levels -= levels;
  77. #ifndef DEBUG
  78.     }
  79. #else
  80.       census += levels;
  81.     } else
  82.       ++census;
  83. #endif
  84.     subrange = subrange->next;
  85.   }
  86.   /* second pass groups with no levels and vals or ranges above limits */
  87.   if( zeroes > 0 ) {
  88.     /* groups with counts above 1/4 of average */
  89.     threshold = average / 4;
  90.     while( (zeroes > 0) && (color_levels > 0) && (max_z_excess > threshold) ) {
  91.       if( excess_zgroup(linklist, &max_z_excess, &max_z_range, average) ) {
  92.     zeroes--;
  93.     color_levels--;
  94. #ifndef DEBUG
  95.       }
  96. #else
  97.     census++;
  98.       } else
  99.         (void)fprintf(stderr, "Failed to find excess zero.\n");
  100. #endif
  101.     }
  102.     /* groups with range above 2 * unequalized distribution */
  103.     threshold = MAX(((pmax - pmin) / 8) , 4);
  104.     while( (zeroes > 0) && (color_levels > 0) && (max_z_range > threshold) ) {
  105.       if( range_zgroup(linklist, &max_z_excess, &max_z_range, average) ) {
  106.     zeroes--;
  107.     color_levels--;
  108. #ifndef DEBUG
  109.       }
  110. #else
  111.     census++;
  112.       } else
  113.         (void)fprintf(stderr, "Failed to find range zero.\n");
  114. #endif
  115.     }
  116.   }
  117.   /* third pass, give away any remaining levels by highest excess */
  118. #ifdef DEBUG
  119.   if( color_levels != (ncolor - census) ) {
  120.     (void)fprintf(stderr, "Allocation waste: %d level(s)\n",
  121.             (ncolor - census) - color_levels);
  122.   }
  123. #endif
  124.   while( color_levels > 0 ) {
  125.     if( (zeroes > 0) && (max_z_excess > max_nz_excess) ) {
  126.       if( excess_zgroup(linklist, &max_z_excess, &max_z_range, average) ) {
  127.     zeroes--;
  128.     color_levels--;
  129.       }
  130. #ifdef DEBUG
  131.       else (void)fprintf(stderr, "Failed to find excess zero.\n");
  132. #endif
  133.     } else {
  134.       if( excess_nzgroup(linklist, &max_nz_excess, average) )
  135.     color_levels--;
  136. #ifdef DEBUG
  137.       else (void)fprintf(stderr, "Failed to find excess.\n");
  138. #endif
  139.     }
  140.   }
  141.   return( zeroes );
  142. }
  143.  
  144. /*
  145.  * Subroutine:    excess_zgroup
  146.  * Purpose:    Find subrange with zero allotted levels and specified excess.
  147.  *        Assign it one level
  148.  */
  149. static int excess_zgroup ( subrange, excess, range, average )
  150.      SubrangeLink *subrange;
  151.      int *excess, *range;
  152.      int average;
  153. {
  154.   int max_excess, looking;
  155.  
  156.   max_excess = -32700;
  157.   looking = 1;
  158.   while( subrange != 0 ) {
  159.     if( (subrange->color_levels == 0) && (subrange->range > 0) ) {
  160.       if( looking && (subrange->excess_pixels == *excess) ) {
  161.     if( subrange->range > 1 ) {
  162.       subrange->color_levels = 1;
  163.     } else {
  164.       subrange->color_levels = 1;
  165.       subrange->range = -1;
  166.     }
  167.     subrange->excess_pixels -= average;
  168.     looking = 0;
  169.       } else {
  170.     if( subrange->excess_pixels > max_excess )
  171.       max_excess = subrange->excess_pixels;
  172.     if( subrange->range > *range )
  173.       *range = subrange->range;
  174.       }
  175.     }
  176.     subrange = subrange->next;
  177.   }
  178.   *excess = max_excess;
  179.   return( !looking );
  180. }
  181.  
  182. /*
  183.  * Subroutine:    range_zgroup
  184.  * Purpose:    Find group with zero allotted levels and specified range.
  185.  *        Assign it one level.
  186.  */
  187. static int range_zgroup (subrange, excess, range, average)
  188.      SubrangeLink *subrange;
  189.      int *excess, *range;
  190.      int average;
  191. {
  192.   int max_range, looking;
  193.  
  194.   max_range = 0;
  195.   looking = 1;
  196.   while( subrange != 0 ) {
  197.     if( (subrange->color_levels == 0) && (subrange->range > 0) ) {
  198.       if( looking && (subrange->range == *range) ) {
  199.     if( subrange->range > 1 ) {
  200.       subrange->color_levels = 1;
  201.     } else {
  202.       subrange->color_levels = 1;
  203.       subrange->range = -1;
  204.     }
  205.     subrange->excess_pixels -= average;
  206.     looking = 0;
  207.       } else {
  208.     if( subrange->excess_pixels > *excess )
  209.       *excess = subrange->excess_pixels;
  210.     if( subrange->range > max_range )
  211.       max_range = subrange->range;
  212.       }
  213.     }
  214.     subrange = subrange->next;
  215.   }
  216.   *range = max_range;
  217.   return( !looking );
  218. }
  219.  
  220. /*
  221.  * Subroutine:    excess_nzgroup
  222.  * Purpose:    Find group with non-zero allotted levels and specified
  223.  *        excess value.  Assign it one additional level.
  224.  */
  225. static int excess_nzgroup ( subrange, excess, average )
  226.      SubrangeLink *subrange;
  227.      int *excess;
  228.      int average;
  229. {
  230.   int looking, max_excess;
  231.  
  232.   looking = 1;
  233.   max_excess = -32767;
  234.   while( subrange != 0 ) {
  235.     if( (subrange->color_levels > 0) && (subrange->range > 1) ) {
  236.       if( looking && (subrange->excess_pixels == *excess) &&
  237.       (subrange->color_levels < subrange->range) ) {
  238.     subrange->color_levels += 1;
  239.     subrange->excess_pixels -= average;
  240.     if( subrange->color_levels == subrange->range ) {
  241.       subrange->color_levels = subrange->range;
  242.       subrange->range = -subrange->range;
  243.     } else {
  244.       if( subrange->excess_pixels > max_excess )
  245.         max_excess = subrange->excess_pixels;
  246.     }
  247.     looking = 0;
  248.       } else {
  249.     if( subrange->excess_pixels > max_excess )
  250.       max_excess = subrange->excess_pixels;
  251.       }
  252.     }
  253.     subrange = subrange->next;
  254.   }
  255.   *excess = max_excess;
  256.   return( !looking );
  257. }
  258.