home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsv / ch6_2 / halfadap.c
Encoding:
C/C++ Source or Header  |  1995-04-04  |  6.9 KB  |  190 lines
  1. /*==========================================================================*
  2.  * Halftoning using Space Filling Curve with adaptive clustering and        *
  3.  * selective precipitation                                                  *
  4.  *                                                                          *
  5.  * Limitation:                                                              *
  6.  * Only process image with size 2^n x 2^n where n is positive integer.      *
  7.  *==========================================================================*/
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10.  
  11. unsigned char **path;       /* space filling curve path */
  12. /*
  13.  * path[] is a global array storing the information to move along
  14.  *        the space filling curve.
  15.  * genspacefill() is a function to generate the information in path[].
  16.  *        This function is implemented based on a gem in Graphics Gems II,
  17.  *        Ken Musgrave, "A Peano Curve Generation Algorithm".
  18.  * move() is a macro to move along the space filling curve using the
  19.  *        the information stored in path[].
  20.  */
  21. extern genspacefill();
  22.  
  23. #define TRUE    1
  24. #define FALSE   0
  25. #define BLACK   255
  26. #define WHITE   0
  27. #define LEFT    0
  28. #define RIGHT   1
  29. #define UP      2
  30. #define DOWN    3
  31. #define END     255
  32. #define move(x,y)  switch (path[x][y])          \
  33.                    {                            \
  34.                      case UP:   y++; break;     \
  35.                      case DOWN: y--; break;     \
  36.                      case LEFT: x--; break;     \
  37.                      case RIGHT:x++; break;     \
  38.                    }
  39.  
  40. /*
  41.  * Description of parameters:
  42.  *   picture,         2D array holding the grayscale image.
  43.  *   out,             2D array holding the dithered image.
  44.  *   maxclustersize,  Max cluster size, N.
  45.  *   thresh,          Edge detection threshold T.
  46.  *   do_sp,           Flag to switch on/off selective precipitation.
  47.  *                    To switch off the selective precipitation,
  48.  *                    set do_sp = FALSE.
  49.  *   do_ac,           Flag to switch on/off adaptive clustering.
  50.  *                    To switch off the adaptive clustering, set do_ac=FALSE
  51.  */
  52. void spacefilterwindow(int **picture, int **out, int maxclustersize,
  53.                        int thresh, char do_sp, char do_ac)
  54. {
  55.   char edge;             /* Flag indicate sudden change detected */
  56.   char ending;              /* flag indicates end of space filling curve */
  57.   int accumulator;       /* Accumulate gray value */
  58.   int currclustersize;   /* Record size of current cluster */
  59.   int frontx, fronty;    /* Pointer to the front of the cluster */
  60.   int windowx, windowy;  /* Pointer to first pixel applied with filter */
  61.   int clusterx, clustery;/* Pointer to first pixel in current cluster */
  62.   int windowlen;         /* Size of the moving window */
  63.   int winsum;            /* Current moving window's sum */
  64.   int maxsum;            /* Maximum moving window's sum recorded */
  65.   int rightplace;        /* Position of the moving window with max sum */
  66.   int *cluster;          /* An array hold the pixel of current cluster */
  67.   int last, i, tempx, tempy, currx, curry;    /* temp variables */
  68.   long filter[7] = {-1, -5, 0, 13, 0, -5, -1};  /* 1D -ve Lap. Gauss. filter */
  69.   long convolution;      /* Convolution value in this turn */
  70.   long lastconvolution;  /* Convolution value in last turn */
  71.   /*
  72.    * Description of the pointer along the space filling curve.
  73.    *
  74.    * clusterx,                          windowx,    currx,     frontx,
  75.    * clustery                           windowy     curry      fronty
  76.    *    |                                  |          |           |
  77.    *    v                                  v          v           v
  78.    *   +----------------------------------------------------------+
  79.    *   |                        Cluster                           |
  80.    *   +----------------------------------------------------------+
  81.    *                                       |                      |
  82.    *                                       |                      |
  83.    *                                       |          /\          |
  84.    *                                       |        /    \        |
  85.    *                                       |___   /        \   ___|
  86.    *                                       |    \/           \/   |
  87.    *                                  -ve Laplacian of Gaussian Filter
  88.    */
  89.  
  90.   if ((cluster=(int*)malloc(sizeof(int)*maxclustersize))==NULL)
  91.   {
  92.     fprintf(stderr,"not enough memory for cluster\n");
  93.     return;
  94.   }
  95.   genspacefill();    /* generates the spacefilling path */
  96.   
  97.   convolution=0;
  98.   currclustersize=0;
  99.   accumulator=0;
  100.   for (frontx=0, fronty=0, i=0 ; i<7 ; i++)
  101.   {
  102.     if (i<3)
  103.     {
  104.       cluster[currclustersize] = picture[frontx][fronty];
  105.       accumulator += cluster[currclustersize];
  106.       currclustersize++;
  107.     }
  108.     if (i==3)
  109.     {  currx = frontx;  curry = fronty;  }
  110.     convolution += filter[i]*(long)(picture[frontx][fronty]);
  111.     move(frontx,fronty);  /* assume the image at least has 7 pixels */
  112.   }
  113.   lastconvolution = convolution;
  114.   clusterx=0;   clustery=0;
  115.   windowx=0;    windowy=0;
  116.   edge=FALSE;
  117.   ending=FALSE;
  118.  
  119.   while (TRUE)
  120.   {
  121.     if (do_ac) /* switch on/off adaptive clustering */
  122.     {
  123.       /* do convolution */
  124.       convolution = 0;
  125.       for (tempx=windowx, tempy=windowy, i=0 ; i<7 ; i++)
  126.       {
  127.         convolution += filter[i]*picture[tempx][tempy];
  128.         move(tempx,tempy);
  129.       }
  130.  
  131.       /* detect sudden change */
  132.       if ( (convolution >= 0 && lastconvolution <=0 
  133.             && abs(convolution-lastconvolution)>thresh)
  134.          ||(convolution <= 0  && lastconvolution >=0 
  135.             && abs(convolution-lastconvolution)>thresh)) 
  136.         edge=TRUE; /* force output dots */
  137.     }    
  138.  
  139.     /* Output dots if necessary */
  140.     if (edge || currclustersize >= maxclustersize || ending)
  141.     {
  142.       edge=FALSE;
  143.       
  144.       /* Search the best position within cluster to precipitate */
  145.       rightplace = 0;
  146.       if (do_sp) /* switch on/off selective precipitation */
  147.       {
  148.         windowlen = accumulator/BLACK;
  149.         winsum = 0;
  150.         for (i=0; i<windowlen; i++)
  151.           winsum += cluster[i];
  152.         for (maxsum=winsum, last=0; i<currclustersize; i++, last++)
  153.         {
  154.           winsum+= cluster[i] - cluster[last];
  155.           if (winsum > maxsum)
  156.           {
  157.             rightplace=last+1;
  158.             maxsum=winsum;
  159.           }
  160.         }
  161.       }
  162.  
  163.       /* Output dots */
  164.       for (i=0 ; currclustersize!=0 ; currclustersize--, i++)
  165.       {
  166.         if (accumulator>=BLACK && i>=rightplace)  /* precipitates */
  167.         {
  168.           out[clusterx][clustery]=BLACK;
  169.           accumulator-=BLACK;
  170.         }
  171.         else
  172.           out[clusterx][clustery]=WHITE;
  173.         move(clusterx,clustery)
  174.       } /* for */
  175.  
  176.       if (ending)
  177.         break;
  178.     } /* if */
  179.  
  180.     cluster[currclustersize] = picture[currx][curry];
  181.     accumulator += cluster[currclustersize];
  182.     currclustersize++;
  183.     if (path[currx][curry]==END)
  184.       ending = TRUE;
  185.     move(currx,curry);
  186.     move(windowx,windowy);
  187.     move(frontx,fronty);
  188.   } /* while */
  189. }
  190.