 /*
  * Khoros: $Id: lvfractal.c,v 1.2 1992/03/20 23:05:27 dkhoros Exp $
  */

#if !defined(lint) && !defined(SABER)
static char rcsid[] = "Khoros: $Id: lvfractal.c,v 1.2 1992/03/20 23:05:27 dkhoros Exp $";
#endif

 /*
  * $Log: lvfractal.c,v $
 * Revision 1.2  1992/03/20  23:05:27  dkhoros
 * VirtualPatch5
 *
  */ 

/*
 *----------------------------------------------------------------------
 *
 * Copyright 1991, University of New Mexico.  All rights reserved.
 * Permission to copy and modify this software and its documen-
 * tation only for internal use in your organization is hereby
 * granted, provided that this notice is retained thereon and
 * on all copies.  UNM makes no representations as too the sui-
 * tability and operability of this software for any purpose.
 * It is provided "as is" without express or implied warranty.
 * 
 * UNM DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FIT-
 * NESS.  IN NO EVENT SHALL UNM BE LIABLE FOR ANY SPECIAL,
 * INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY OTHER DAMAGES WHAT-
 * SOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
 * IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PER-
 * FORMANCE OF THIS SOFTWARE.
 * 
 * No other rights, including for example, the right to redis-
 * tribute this software and its documentation or the right to
 * prepare derivative works, are granted unless specifically
 * provided in a separate license agreement.
 *---------------------------------------------------------------------
 */

#include "unmcopyright.h"        /* Copyright 1991 by UNM */

/*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>  <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 >>>>
 >>>>         File Name: lvfractal.c
 >>>>
 >>>>      Program Name: vfractal
 >>>>
 >>>> Date Last Updated: Tue Mar  5 22:26:30 1991 
 >>>>
 >>>>          Routines: lvfractal - the library call for vfractal
 >>>>
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>   <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/


#include "vinclude.h"


/* -library_includes */
/* -library_includes_end */


/****************************************************************
*
* Routine Name: lvfractal - library call for vfractal
*
* Purpose:
*    
*    Fractal feature extraction of an image  via  calculation  of
*    the fractal dimension.
*    
*    
* Input:
*    
*    img            xvimage structure
*    
*    region         region window size argument
*    
*    lo_size        starting size of sliding window
*    
*    step           step size or increment of sliding window
*    
*    
* Output:
*    
*     img           holds the resulting feature of the image.  img  is
*                   used  for both the input xvimage structure and the
*                   resulting output xvimage structure.
*    
*    
*
* Written By: Charlie Gage
*    
*    3/19/90  Charlie Gage - updated for processing speed.
*    
*    
****************************************************************/


/* -library_def */
int
lvfractal(img, region, lo_size, step)
struct xvimage *img;
int region, lo_size, step;
/* -library_def_end */

/* -library_code */
{
  int row,            /* points to image row */
      col,            /* points to image col */
      r_row,          /* points to fractal region row */
      r_col,          /* points to fractal region col */
      offset,         /* window offset in the image */
      xend,           /* step in img up to here */
      yend,           /* step in img up to here */
      r_end,          /* step in region up to here */
      nc,             /* column size of image */
      nr,             /* row size of image */
      reg_size,       /* size of fractal region */
      lo_window,      /* starting size of sliding window */
      hi_window,      /* final size of sliding window */
      win_size,       /* current size of sliding window */
      dim,            /* dimension of arrays */
      i,              /* general counters */
      j,
      k,
      p,
      index,
      left,
      right,
      top,
      bottom,
      num_pts;

float
      x;             /* points to current pixel value */

double
      max_inten,     /* holds maximum intensity value of sliding window */
      min_inten;     /* holds minimum intensity value of sliding window */

double
      tmp_slope,             /* variables used to calculate least square fit */
      tmp,
      sum_sqr,
      sum_x,
      avg,
      ave_range,     /* average range of intensity values in window */
      hurst,         /* hurst coefficient used to calculate fractal dim */
      fract_dim;     /* calculated fractal dimension of window */

float  *result;      /* pointer to resulting image */

double
       *h,           /* pointer to hurst coefficients */
       *w,           /* pointer to abcissa for least square fit calculations */
       *row_range,   /* pointer to row range values */
       *col_range;   /* pointer to col range values */

int    *count;       /* count number of windows in region for each win_size */

float  *fptr,        /* pointer to image data - type is FLOAT */
       **ptr;        /* pointer to 2-D working array */

 nr = img->col_size;              /* number of rows in image */
 nc = img->row_size;              /* number of cols in image */

 reg_size = region;               /* get dimension of fractal window */
 lo_window = lo_size;             /* get starting size of sliding window */
 hi_window = (reg_size / 3);      /* find final size of sliding window */
 dim = (hi_window - lo_window)+1;  /* find dimension of arrays used to
                                      calculate fractal dimension. */

    /* Check for proper input image type */
 if ((img->data_storage_type) != VFF_TYP_FLOAT)
  {
    (void) fprintf(stderr,"lvfractal: Error, Input image must be of data type FLOAT\n");
    return(0);
  }

    /* check for odd size of fractal region */
 if((reg_size % 2) == 0)
  {
    (void) fprintf(stderr,"lvfractal: Error, region size must be odd\n");
    return(0);
  }

    /* Ensure that region size does not exceed image size */
 if ((reg_size > nr) || (reg_size > nc))
  {
    (void) fprintf(stderr,"lvfractal: Error, region size exceeds image size\n");
    (void) fprintf(stderr,"Image size is %d by %d\n", nr, nc);
    return(0);
  }

    /* Ensure that region size does not drop below minimum of 9 x 9 */
 if (reg_size < 9)
  {
    (void) fprintf(stderr,"lvfractal: Error, region size too small to compute fractal dimension\n");
    (void) fprintf(stderr,"Minimum region size is 9 x 9\n");
    return(0);
  }

    /* Ensure that lo_window size does not exceed fractal region size */
    /* Need at least two points to define the slope */
 if ((dim < 2) || (lo_window < 2))
  {
    (void) fprintf(stderr,"lvfractal: Error, lo window size exceeds limits.\n");
    (void) fprintf(stderr,"Valid range is 2 to %d\n", (hi_window - 1));
    return(0);
  }

    /* Ensure that step size is not too great */
 if ((lo_window + step) > hi_window)
  {
    (void) fprintf(stderr,"lvfractal: Error, step size exceeds bounds for this image.\n");
    (void) fprintf(stderr,"Valid range is 1 to %d.\n", (hi_window-lo_window));
    return(0);
  }

                 /* Assign input image data address to ptr */
 fptr = (float *)img->imagedata;

                 /* Allocate space for 2-D working array */
 ptr = (float **) malloc((unsigned int) nr * sizeof(float));
 if (ptr == NULL){
    (void)fprintf(stderr,"\nERROR: lvfractal - insufficient memory available!");
    return(0);
 }
 for (i = 0; i < nr; i++)
 {
  ptr[i] = (float *) malloc((unsigned int) nc * sizeof(float));
  if (ptr[i] == NULL)
  {
   (void) fprintf(stderr,"\nERROR: lvfractal - insufficient memory available!");
   return(0);
  }
 }

         /* Zero out 2-D working array */
 for (i = 0; i < nr; i++)
 {
  for (j = 0; j < nc; j++)
  {
   ptr[i][j] = 0.0;
  }
 }

         /* Assign input image data to 2-D working array */
 for (i = 0; i < nr; i++)
 {
  for (j = 0; j < nc; j++)
  {
   ptr[i][j] = fptr[nc * i + j];
  }
 }

   /* Allocate space for resulting image --- of type FLOAT */
 result = (float *) malloc((unsigned int) nc * nr * sizeof(float));
 if (result == NULL){
    (void)fprintf(stderr,"\nERROR: lvfractal - insufficient memory available!");
    return(0);
 }

   /* Allocate space for data arrays */
 h = (double *) malloc((unsigned int) dim * sizeof(double));
 if (h == NULL){
    (void)fprintf(stderr,"\nERROR: lvfractal - insufficient memory available!");
    return(0);
 }
 w = (double *) malloc((unsigned int) dim * sizeof(double));
 if (w == NULL){
    (void)fprintf(stderr,"\nERROR: lvfractal - insufficient memory available!");
    return(0);
 }
 count = (int *) malloc((unsigned int) dim * sizeof(int));
 if (count == NULL){
    (void)fprintf(stderr,"\nERROR: lvfractal - insufficient memory available!");
    return(0);
 }
 row_range = (double *) malloc((unsigned int) dim * sizeof(double));
 if (row_range == NULL){
    (void)fprintf(stderr,"\nERROR: lvfractal - insufficient memory available!");
    return(0);
 }
 col_range = (double *) malloc((unsigned int) dim * sizeof(double));
 if (col_range == NULL){
    (void)fprintf(stderr,"\nERROR: lvfractal - insufficient memory available!");
    return(0);
 }


   /* Zero out space for resulting image */
 bzero((float *) result, nc * nr * sizeof(float));

 offset = reg_size / 2;   /* Find window offset from center of region */
 xend = nc - reg_size + 1;   /* step in image (x-dir) up to here */
 yend = nr - reg_size + 1;   /* step in image (y-dir) up to here */

   /* Initialize variables */
 p = 0;
 k = 0;
 bzero((int *) count, dim * sizeof(int));
 bzero((double *) row_range, dim * sizeof(double));
 bzero((double *) col_range, dim * sizeof(double));

 /*--------------------------------------------------------------------
  *   load range arrays with intensity values of first "region"
  *   in the image.
  *--------------------------------------------------------------------*/

 for (win_size = lo_window; win_size <= hi_window; (win_size += step))
  {
    r_end = reg_size - win_size + 1;
    for (r_row =0; r_row < r_end; r_row++)
    {
     for (r_col = 0; r_col < r_end; r_col++)
     {
      max_inten = (double) ptr[r_row][r_col];
      min_inten = max_inten;
          /* find range of intensities in sliding window */
      for (i = 0; i < win_size; i++)
      {
       for (j = 0; j < win_size; j++)
       {
        x = ptr[r_row + i][r_col + j];
        if (x > max_inten)
           max_inten = (double)x;
        if (x < min_inten)
           min_inten = (double)x;
       }
      }
      col_range[k] += (double)(max_inten - min_inten);
      row_range[k] += (double)(max_inten - min_inten);
      count[k]++;           /* count number of windows in region */
     }                      /*  for current window size.   */
    }
    k += step;
 
  } /* End of win_size loop */
  k = 0;

 /*---------------------------------------------------------------------
  *         perform fractal analysis of an image 
  *--------------------------------------------------------------------*/

     /*-------- loop through ROWS of image -- (y-direction) ---------*/
 for (row = 0 ; row < yend; row++)
 {
      /*-------- loop through COLS of image -- (x-direction) ---------*/
  for (col = 0 ; col < xend; col++)
  {
   /*--------------------------------------------------------------------
    *    perform fractal analysis of region by looping through 
    *    all window sizes up to one-third of fractal region.
    *     ie.  L <= 1/3(extent)
    *-------------------------------------------------------------------*/
   for (win_size = lo_window; win_size <= hi_window; (win_size += step))
   {
    r_end = reg_size - win_size + 1;      /* determine loop limits */

       /* Don't subtract first column if col = 0 */
    if (col != 0)
    {
     /*--------------------  Subtract LEFT side ------------*/
     for (left = 0; left < r_end; left++)
     {
      index = col-1;
      max_inten = (double)ptr[left + row][index];
      min_inten = max_inten;
      for (i = 0; i < win_size; i++)
      {
       for (j = 0; j < win_size; j++)
       {
        x = ptr[left + i + row][index + j];
        if (x > max_inten)
           max_inten = (double)x;
        if (x < min_inten)
           min_inten = (double)x;
       }
      }
      col_range[k] -= (double)(max_inten - min_inten);
     }
     /*--------------------  Add RIGHT side ----------------*/
     for (right = 0; right < r_end; right++)
     {
      index = col + r_end -1;
      max_inten = (double)ptr[right + row][index];
      min_inten = max_inten;
      for (i = 0; i < win_size; i++)
      {
       for (j = 0; j < win_size; j++)
       {
        x = ptr[right + i + row][index + j];
        if (x > max_inten)
           max_inten = (double)x;
        if (x < min_inten)
           min_inten = (double)x;
       }
      }
      col_range[k] += (max_inten - min_inten);
     }

    }  /*----  End of col != 0 ----*/

    /* find average range for current window size in the region */
    ave_range = (double) col_range[k] / count[k];
    if (ave_range <= 0.0)
       h[k] = 0.0;
    else
       h[k] = log10((double) ave_range);
    w[k] = log10((double) win_size);
    k += step;
  }  /*--- End of loop through all window sizes ---*/

  /*---------------------------------------------------------------
   *   find H of fractal region by performing least squares fit 
   *   of the average ranges over various window sizes.
   *---------------------------------------------------------------*/
   tmp_slope = 0.0;
   sum_x = 0.0;
   sum_sqr = 0.0;
   num_pts = 0;

   for (i = 0; i < dim; (i += step)){
       sum_x += w[i];
       num_pts++;
   }
   avg = sum_x / (double)num_pts;
   for (i = 0; i < dim; (i += step)){
       tmp = w[i] - avg;
       sum_sqr += tmp * tmp;
       tmp_slope += tmp * h[i];
   }
   hurst = tmp_slope / sum_sqr;    /* find slope of best fit line */
                                   /* slope is Hurst coefficient */
   fract_dim = 3.0 - hurst;        /* calculate fractal dimension */

           /* update center pixel of region using fractal dimension */
   result[nc * (row + offset) + offset + p] = (float)fract_dim;

                   /* reset variables and increment place counter */
   k = 0;
   p++;

 }  /*-------- End of COL loop ------------*/

if ((yend - row) > 1)
{
 /*-------------------------------------------------------------------
  *     update range arrays for next loop thru columns of image 
  *-------------------------------------------------------------------*/
 for (win_size = lo_window; win_size <= hi_window; (win_size += step))
 {
  r_end = reg_size - win_size + 1;
  /*-----------------  Subtract TOP row from region ------------*/
  for (top = 0; top < r_end; top++)
  {
   max_inten = (double)ptr[row][top];
   min_inten = max_inten;
   for (i = 0; i < win_size; i++)
   {
    for (j = 0; j < win_size; j++)
    {
     x = ptr[row + i][top + j];
     if (x > max_inten)
        max_inten = (double)x;
     if (x < min_inten)
        min_inten = (double)x;
    }
   }
   row_range[k] -= (double)(max_inten - min_inten);
  }
  /*----------------  Add BOTTOM row to region  ---------------*/
  for (bottom = 0; bottom < r_end; bottom++)
  {
   index = row + r_end;
   max_inten = (double)ptr[index][bottom];
   min_inten = max_inten;
   for (i = 0; i < win_size; i++)
   {
    for (j = 0; j < win_size; j++)
    {
     x = ptr[index + i][bottom + j];
     if (x > max_inten)
        max_inten = (double)x;
     if (x < min_inten)
        min_inten = (double)x;
    }
   }
   row_range[k] += (double)(max_inten - min_inten);
  }
                       /* update col_range array for next pass */
  col_range[k] = row_range[k];
  k += step;
 }   /*-----  End of win_size loop  -----*/

}   /*----  End of if statement  -------*/

 p = 0;       /* reset place counter */
 k = 0;
}   /*-------- End of ROW loop ------------*/

                       /* release memory from input image */
(void) free (img->imagedata);
                       /* adjust header in the output image */
img->data_storage_type = VFF_TYP_FLOAT;
img->imagedata = (char *) result;
img->num_data_bands = 1;

return(1);

}  /****  End of lvfractal  ****/
/* -library_code_end */
