home *** CD-ROM | disk | FTP | other *** search
/ Encyclopedia of Graphics File Formats Companion / GFF_CD.ISO / software / unix / saoimage / sao1_07.tar / histmap.c < prev    next >
C/C++ Source or Header  |  1990-04-20  |  8KB  |  247 lines
  1. #ifndef lint
  2. static char SccsId[] = "%W%  %G%";
  3. #endif
  4.  
  5. /* Module:    histmap.c (Histogram Map)
  6.  * Subroutine:    make_HE_scalemap()        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.  *        {n} <who> -- <does what> -- <when>
  15.  */
  16.  
  17. #include <stdio.h>
  18. #include "hfiles/histeq.h"        /* define SubrangeLink, List */
  19.  
  20. /*
  21.  * Subroutine:    generate_scalemap
  22.  * Purpose:    Make scalemap, applying standard histgoram equalization
  23.  *        one subrange group at a time
  24.  * Note:    Value range was broken into groups with an assigned number
  25.  *        of levels for each group.  Each group is either a single
  26.  *        value or a range of values with no excessive peaks, such that
  27.  *        standard (non-optimizing) histogram equaliztion algorithm can
  28.  *        safely be applied.
  29.  * Note:    The original link-list of groups is freed.
  30.  */
  31. void generate_scalemap ( hist, subrange, scalemap, pixels )
  32.      int *hist;                /* i: histogram (for signed offsets) */
  33.      SubrangeLink *subrange;    /* i: linklist of subranges */
  34.      unsigned char *scalemap;        /* i: scalemap (for signed indexing) */
  35.      unsigned long *pixels;        /* i: map to hardware entries */
  36. {
  37.   int baselevel;
  38.   SubrangeLink *trash;
  39.   static void make_subrange_scalemap();
  40.  
  41.   baselevel = 0;
  42.   while( subrange != 0 ) {
  43.     make_subrange_scalemap(hist, subrange, scalemap, baselevel, pixels);
  44.     if( subrange->color_levels > 0 )
  45.       baselevel += subrange->color_levels;
  46.     trash = subrange;
  47.     subrange = subrange->next;
  48.     free((char *)trash);
  49.   }
  50. }
  51.  
  52. /*
  53.  * Subroutine:    make_subrange_scalemap
  54.  * Purpose:    Make a section of scale map using histgroup link as guide 
  55.  * Called by:    make_HE_scalemap() in HistEqual.c
  56.  */
  57. static void
  58.   make_subrange_scalemap ( histogram, subrange, scalemap, baselevel, pixels )
  59.      int *histogram;
  60.      SubrangeLink *subrange;
  61.      unsigned char *scalemap;        /* scalemap (for signed indexing) */
  62.      int baselevel;
  63.      unsigned long *pixels;        /* i: map to hardware entries */
  64. {
  65.   int i, color_levels;
  66.   SubrangeList *list;
  67.   unsigned char dispval;
  68.   char *calloc_errchk();
  69.   void make_equalized_list();
  70.   static void make_gapped_list(), list_to_map();
  71.  
  72.   /* if only one level, make map section */
  73.   if( subrange->color_levels <= 1 ) {
  74.     dispval = pixels[baselevel];
  75.     for( i = subrange->low; i <= subrange->high; i++ ) {
  76.       scalemap[i] = dispval;
  77.     }
  78.     return;
  79.   }
  80.   color_levels = subrange->color_levels;
  81.   /* allocate excess space as initial efforts may overshoot number of levels */
  82.   list = (SubrangeList *)
  83.     calloc_errchk(2 * color_levels, sizeof(SubrangeList), "HistList");
  84.   /* if normal processing will not work, choose special */
  85.   if( color_levels < subrange->nz_entries ) {
  86.     make_equalized_list(histogram, list, subrange->low, subrange->high,
  87.             subrange->pixel_area, color_levels);
  88.   } else {
  89.     make_gapped_list(histogram, list, subrange->low, subrange->high,
  90.              color_levels);
  91.   }
  92. #ifdef DEBUG
  93.   /* check work done */
  94.   if( list[color_levels - 1].last != subrange->high ) {
  95.     (void)fprintf(stderr, "ERROR: histogram list not right\n");
  96.     (void)fprintf(stderr, "levels: %d, list: %d, link: %d\n",
  97.           color_levels, list[color_levels - 1].last, subrange->high);
  98.   }
  99. #endif
  100.   /* make section of map as defined by list */
  101.   list_to_map(scalemap, list, baselevel, color_levels, pixels);
  102.   /* free the list space */
  103.   free( (char *)list );
  104. }
  105.  
  106. /*
  107.  * Subroutine:    list_to_map
  108.  * Purpose:    Make section of map as defined by list
  109.  * Called by:    make_subrange_scalemap() above
  110.  */
  111. static void list_to_map ( scalemap, histlist, baselevel, levels, pixels )
  112.      unsigned char *scalemap;        /* scalemap (for signed indexing) */
  113.      SubrangeList *histlist;
  114.      int baselevel, levels;
  115.      unsigned long *pixels;        /* i: map to hardware entries */
  116. {
  117.   int i, level;
  118.   int first, last, imageval;
  119.   unsigned char dispval;
  120.  
  121.   level = baselevel;
  122.   for( i = 0; i < levels; i++ ) {
  123.     first = histlist[i].first;
  124.     last = histlist[i].last;
  125.     dispval = pixels[level];
  126.     for( imageval = first; imageval <= last; imageval++ ) {
  127.       scalemap[imageval] = dispval;
  128.     }
  129.     level++;
  130.   }
  131. }
  132.  
  133. /*
  134.  * Subroutine:    make_gapped_list
  135.  * Purpose:    Allocate levels for a histogram subrange.  Special process
  136.  *         for situation when more levels than actually used values.
  137.  */
  138. static void make_gapped_list ( histogram, list, low, high, levels )
  139.      int *histogram;
  140.      SubrangeList *list;
  141.      int low, high, levels;
  142. {
  143.   int range_j, max_range;
  144.   int levels_used;
  145.   static int first_shortlist_pass();
  146.   static void add_level_to_short_list();
  147.  
  148.   levels_used =
  149.     first_shortlist_pass(histogram, list, low, high, levels,
  150.              &max_range, &range_j);
  151.   while( levels_used < levels ) {
  152.     add_level_to_short_list(list, levels_used - 1, &max_range, &range_j);
  153.     ++levels_used;
  154.   }
  155. }
  156.  
  157. /*
  158.  * Subroutine:    first_shortlist_pass
  159.  * Purpose:    Make a list to describe map allocation using special
  160.  *        allocation method.  Fill the list with each entry ending
  161.  *        at the next actually used value.
  162.  */
  163. static int
  164.   first_shortlist_pass ( histogram, list, low_entry, high_entry, levels,
  165.              max_range, range_j )
  166.      int *histogram;
  167.      SubrangeList *list;
  168.      int low_entry, high_entry, levels;
  169.      int *range_j, *max_range;
  170. {
  171.   int i, area, level;
  172.  
  173.   /* initialize parameters (index starts at 0) */
  174.   level = 0;
  175.   area = 0;
  176.   *max_range = -1;
  177.   list[level].first = low_entry;
  178.   /* first pass, assign levels by simple method */
  179.   for( i = low_entry; i <= high_entry; i++ ) {
  180.     area += histogram[i];
  181.     /* while levels last, scan till value which is used */
  182.     if( (area > 0) || (i == high_entry) ) {
  183.       list[level].last = i;
  184.       list[level].pixel_area = area;
  185.       list[level].shrink_entry = (i - list[level].first) + 1;
  186.       /* find the lowest entry with the highest range */
  187.       if( list[level].shrink_entry > *max_range ) {
  188.     *max_range = list[level].shrink_entry;
  189.     *range_j = level;
  190.       }
  191.       if( i < high_entry ) {
  192.     /* start for next group */
  193.     list[++level].first = i + 1;
  194. #ifdef DEBUG
  195.     if( level > levels ) {
  196.       (void)fprintf(stderr, "Actual exceeds levels\n");
  197.       level--;
  198.     }
  199. #endif
  200.       } else if (level >= levels) {
  201.     list[level - 1].last = i;
  202.       }
  203.       area = 0;
  204.     }
  205.   }
  206.   return( level+1 );
  207. }
  208.  
  209. /*
  210.  * Subroutine:    add_level_to_short_list
  211.  */
  212. static void add_level_to_short_list ( list, top, max_range, range_j )
  213.      SubrangeList *list;
  214.      int top;
  215.      int *max_range, *range_j;
  216. {
  217.   int i, j, mark;
  218.  
  219.   mark = *range_j;
  220.   *max_range = -1;
  221.   for( i = top, j = top + 1; j > mark; i--, j-- ) {
  222.     list[j].first = list[i].first;
  223.     list[j].last = list[i].last;
  224.     list[j].pixel_area = list[i].pixel_area;
  225.     list[j].shrink_entry = list[i].shrink_entry;
  226.     /* find the lowest entry with the highest range */
  227.     if( list[j].shrink_entry >= *max_range ) {
  228.       *max_range = list[j].shrink_entry;
  229.       *range_j = j;
  230.     }
  231.   }
  232.   i++;
  233.   j++;
  234.   list[i].last = list[i].first + ((list[i].shrink_entry / 2) - 1);
  235.   list[j].first = list[i].last + 1;
  236.   list[i].pixel_area = 0;
  237.   list[i].shrink_entry = (list[i].last - list[i].first) + 1; 
  238.   list[j].shrink_entry = (list[j].last - list[j].first) + 1; 
  239.   for( ; j >= 0; j-- ) {
  240.     /* find the lowest entry with the highest range */
  241.     if( list[j].shrink_entry >= *max_range ) {
  242.       *max_range = list[j].shrink_entry;
  243.       *range_j = j;
  244.     }
  245.   }
  246. }
  247.