home *** CD-ROM | disk | FTP | other *** search
/ Encyclopedia of Graphics File Formats Companion / GFF_CD.ISO / software / unix / saoimage / sao1_07.tar / histeql.c < prev    next >
C/C++ Source or Header  |  1990-04-20  |  6KB  |  174 lines
  1. #ifndef lint
  2. static char SccsId[] = "%W%  %G%";
  3. #endif
  4.  
  5. /* Module:    histeql.c (Histogram Equalize)
  6.  * Purpose:    Fill the scalemap by histogram equalization
  7.  * Subroutine:    histogram_equalize()        returns: void
  8.  * Copyright:    1989 Smithsonian Astrophysical Observatory
  9.  *        You may do anything you like with this file except remove
  10.  *        this copyright.  The Smithsonian Astrophysical Observatory
  11.  *        makes no representations about the suitability of this
  12.  *        software for any purpose.  It is provided "as is" without
  13.  *        express or implied warranty.
  14.  * Modified:    {0} Michael VanHilst    initial version          30 May 1989
  15.  *        {n} <who> -- <does what> -- <when>
  16.  */
  17.  
  18. #include <stdio.h>
  19. #include "hfiles/histeq.h"        /* define SubrangeLink */
  20.  
  21. /*
  22.  * Subroutine:    histogram_equalize
  23.  * Purpose:    Create a scaling map which equalizes image cells per
  24.  *        output level optimization accounts for large cell counts
  25.  *        for single levels (e.g. half of all pixels with value 0)
  26.  */
  27. void histogram_equalize ( scalemap, histogram, area, pmin, pmax,
  28.               color_levels, pixels )
  29.      unsigned char *scalemap;    /* i/o: scalemap (for signed indexing) */
  30.      int *histogram;        /* i: histogram (for signed indexing) */
  31.      int area;            /* i: area in pixels when histogram was made */
  32.      int pmin, pmax;        /* i: min and max values in histogram */
  33.      int color_levels;        /* i: number of levels in color map */
  34.      unsigned long *pixels;    /* i: map to hardware entries */
  35. {
  36.   SubrangeLink *linklist;    /* l: beginning of subrange linklist */
  37.   int average_area;        /* l: average area covered by each level */
  38.   int pixel_area;
  39.   int map_levels;
  40.   int nz_entries;        /* l: non-zero entries in histogram */
  41.   int empties;            /* l: subranges with no alloted levels */
  42.   char *calloc_errchk();
  43.   int distribute_levels();
  44.   void generate_scalemap(), scan_histogram_for_peaks(), resolve_zeroes();
  45.   static int count_nonzero_histogram_entries(), rescan_histogram();
  46.   static void unmark_peak_links();
  47.  
  48.   /* initialize link list */
  49.   linklist = (SubrangeLink *)calloc_errchk(10, sizeof(int), "HElink");
  50.   linklist->next = 0;
  51.   linklist->low = pmin;
  52.   linklist->high = pmax;
  53.   linklist->range = (pmax - pmin) + 1;
  54.   linklist->pixel_area = area;
  55.   linklist->max_entry = 0;
  56.   /* if not enough non-zero entries to make distribution, bypass work */
  57.   nz_entries = count_nonzero_histogram_entries(histogram, pmin, pmax);
  58.   if( nz_entries <= color_levels ) {
  59.     linklist->color_levels = color_levels;
  60.     linklist->nz_entries = nz_entries;
  61.     generate_scalemap(histogram, linklist, scalemap, pixels);
  62.     return;
  63.   }
  64.   /* initialize count and level variables */
  65.   pixel_area = area;
  66.   map_levels = color_levels;
  67.   /* desired number of pixels at each level */
  68.   /* average is rounded strongly upward to be stingy with levels */
  69.   average_area = (pixel_area / map_levels) + 1;
  70.   /* go through histogram seeking histogram entries above the map mean */
  71.   scan_histogram_for_peaks(linklist, histogram,
  72.                &pixel_area, &map_levels, &average_area);
  73.   /* repeat scans until no more treetops emerge */
  74.   while( rescan_histogram(linklist, histogram,
  75.               &pixel_area, &map_levels, &average_area) != 0 );
  76.   /* allocate levels */
  77.   empties =
  78.     distribute_levels(linklist, pixel_area, map_levels,
  79.               pmin, pmax, color_levels);
  80.   /* make peak and valley links look the same (peaks have range 1) */
  81.   unmark_peak_links(linklist, color_levels);
  82.   if( empties > 0 ) {
  83.     resolve_zeroes(linklist, empties);
  84.   }
  85.   /* make map and free memory */
  86.   generate_scalemap(histogram, linklist, scalemap, pixels);
  87. }
  88.  
  89. /*
  90.  * Subroutine:    rescan_histogram
  91.  * Purpose:    Repeat scanning for large count levels as saturation level
  92.  *        is modified.  Repeats until all large count levels are
  93.  *        marked and residual is stable
  94.  * Returns:    1 if a range was modified, 0 if nothing was changed
  95.  */
  96. static int rescan_histogram ( subrange, histogram,
  97.                   pixel_area, map_levels, average_area )
  98.      SubrangeLink *subrange;
  99.      int *histogram;
  100.      int *pixel_area;
  101.      int *map_levels;
  102.      int *average_area;
  103. {
  104.   int process;
  105.   void scan_histogram_for_peaks();
  106.  
  107.   process = 0;
  108.   while( subrange != 0 ) {
  109.     /* if subrange has values that exceed current average */
  110.     if( (subrange->range > 1) && (subrange->max_entry >= *average_area) ) {
  111.       scan_histogram_for_peaks(subrange, histogram,
  112.                    pixel_area, map_levels, average_area);
  113.       /* indicate that additional processing has taken place */
  114.       process = 1;
  115.     }
  116.     subrange = subrange->next;
  117.   }
  118.   return( process );
  119. }
  120.  
  121. /*
  122.  * Subroutine:    unmark_peak_links
  123.  * Purpose:    Make singularity links non_uniquely marked (range > 0) and
  124.  *        check count against reference
  125.  * Called by:    histogram_equalize() above
  126.  */
  127. static void unmark_peak_links ( subrange, nlevels )
  128.      SubrangeLink *subrange;
  129.      int nlevels;
  130. {
  131. #ifdef DEBUG
  132.   int levels = 0;
  133. #endif
  134.  
  135.   while( subrange != 0 ) {
  136.     if( subrange->range <0 ) {
  137.       subrange->range = -subrange->range;
  138.     }
  139. #ifdef DEBUG
  140.     if( (subrange->next != 0) &&
  141.     (subrange->next->low != (subrange->high + 1)) )
  142.       (void)fprintf(stderr, "Missing Link in list.\n");
  143.     if( subrange->color_levels > subrange->range )
  144.       (void)fprintf(stderr, "Excess levels in a Link.\n");
  145.     levels += subrange->color_levels;
  146. #endif
  147.     subrange = subrange->next;
  148.   }
  149. #ifdef DEBUG
  150.   if( levels != nlevels ) {
  151.     (void)fprintf(stderr, "Levels = %d\n",levels);
  152.   }
  153. #endif
  154. }
  155.  
  156. /*
  157.  * Subroutine:    count_nonzero_histogram_entries
  158.  * Called by:    histogram_equalize() in HistEqual.c
  159.  */
  160. static int count_nonzero_histogram_entries ( histogram, pmin, pmax )
  161.      register int *histogram;
  162.      int pmin;
  163.      register int pmax;
  164. {
  165.   register int i, npix;
  166.  
  167.   npix = 0;
  168.   for( i = pmin; i <= pmax; i++ ) {
  169.     if( histogram[i] > 0 )
  170.       ++npix;
  171.   }
  172.   return( npix );
  173. }
  174.