/*******************************************************************************
* Program: component
* Purpose: This program can count the number of discrete objects in an image
* that are brighter than a threshold value. Eight way connectivity of pixels
* that make up objects is assumed. The code is incomplete because the functions
* to perform the connected components on a graph are not supplied. Their
* function definitions are in the file named ccfunct.c. The bodies for these
* functions must be supplied by the student.
* Name: Michael Heath, University of South Florida
* Date: 2/11/2000
* To Compile:    gcc -o component component.c mycomps.c imageio.c
*******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "imageio.h"
#include "component.h"

#define TESTMODE 1
#define LINKEDLIST 2
#define DISJOINTFOREST 3

int main(int argc, char *argv[])
{
   unsigned char **image = NULL, **ccimage = NULL;
   unsigned long int **cculongimage = NULL;
   int rows, cols, threshold = 128;
   struct VERTEX *graph = NULL;
   int numberofvertices=0;
   int r, c, i, mode = LINKEDLIST;
   char *input_filename=NULL, output_filename[100];
   int debugmode = 0;
   unsigned long int minimum, maximum, average;
   clock_t begint, endt;

   /****************************************************************************
   * Some function prototypes.
   ****************************************************************************/
   void thresholdimage(unsigned char **image, int rows, int cols, int threshold);
   int mkgraph(unsigned char **image, int rows, int cols, struct VERTEX **graph,
      int *numberofvertices, int connectivity);
   void cc_linkedlist(struct VERTEX *graph, int numberofvertices);
   void cc_disjointforest(struct VERTEX *graph, int numberofvertices);
   void label_image_ll(unsigned long int **image, struct VERTEX *graph, int numberofvertices);
   void label_image_df(unsigned long int **image, struct VERTEX *graph, int numberofvertices);
   void print_help(char *filename);
   void stats_ulong(unsigned long int **image, int rows, int cols,
       unsigned long int *minimum, unsigned long int *maximum, unsigned long int *average);
   unsigned long int **allocate_ulong_image(int rows, int cols);
   void free_ulong_image(unsigned long int **image, int rows);

   /****************************************************************************
   * Get the command line parameters. Supply help if it is needed.
   ****************************************************************************/
   if(argc == 1) print_help(argv[0]);
   for(i=1;i<argc;i++){
      if(strcmp(argv[1], "-debug") == 0){
         debugmode = 1;
      }
      if(strcmp(argv[i], "-ll") == 0){
         mode = LINKEDLIST;
      }
      if(strcmp(argv[i], "-df") == 0){
         mode = DISJOINTFOREST;
      }
      if(strcmp(argv[i], "-i") == 0){
         input_filename = argv[i+1];
         i++;
      }
      if(strcmp(argv[i], "-t") == 0){
         threshold = atoi(argv[i+1]);
         i++;
      }
   }

   /****************************************************************************
   * Check the validity of the supplied command line arguments.
   ****************************************************************************/
   if(!((debugmode) || (((mode == LINKEDLIST) || (mode == DISJOINTFOREST)) &&
       (input_filename != NULL)))){
      print_help(argv[0]);
   }
   if((threshold < 0) || (threshold > 255)){
      fprintf(stderr, "The threshold must be in the range 0->255.\n");
      exit(1);
   }
   if(debugmode){
      printf("Running in degub mode using a ");
      if(mode == LINKEDLIST) printf("linked list");
      if(mode == DISJOINTFOREST) printf("disjoint forest");
      printf(" representation for the connected component algorithm.\n");
      if(input_filename != NULL)
         printf("Ignoring the input filename.\n");
   }

   /****************************************************************************
   * If the user specified that they wanted to run the program in debug mode
   * we will use a very small synthetic image. This makes it much easier to
   * debug the program because we can see the values in the image.
   ****************************************************************************/
   if(debugmode){

      /*************************************************************************
      * Some function prototypes we will use only in the debug mode.
      *************************************************************************/
      void syntheticimage(unsigned char ***imageptr, int *rows, int *cols);
      void showimage(unsigned char **image, int rows, int cols);
      void showgraph(struct VERTEX *graph, int numberofvertices);

      /*************************************************************************
      * Create a small synthetic image and then display it to the screen.
      *************************************************************************/
      syntheticimage(&image, &rows, &cols);
      printf("\nThe synthetic image is:\n");
      showimage(image, rows, cols);

      /*************************************************************************
      * Threshold the image and display it to the screen.
      *************************************************************************/
      printf("Thresholding the image at a value of %d.\n", threshold);
      thresholdimage(image, rows, cols, threshold);
      printf("The thresholded synthetic image is:\n");
      showimage(image, rows, cols);

      /*************************************************************************
      * Create a graph of the pixels that are above the threshold. Display the
      * graph to the screen.
      *************************************************************************/
      if(mkgraph(image, rows, cols, &graph, &numberofvertices, CONNECTMODE) == 0) exit(1);
      printf("The graph is:\n");
      showgraph(graph, numberofvertices);

      /*************************************************************************
      * Compute the connected components in the graph.
      *************************************************************************/
      if(mode == LINKEDLIST) cc_linkedlist(graph, numberofvertices);
      else cc_disjointforest(graph, numberofvertices);

      /*************************************************************************
      * Make an image to display the connected components. Then display the
      * connected components image to the screen. The connected components are
      * first written to an unsigned long int image. Then they are copied into
      * an unsigned character image. In this copy, any values greater than 255
      * are set to 255.
      *************************************************************************/
      ccimage = allocate_image(rows, cols);
      cculongimage = allocate_ulong_image(rows, cols);
      if(mode == LINKEDLIST) label_image_ll(cculongimage, graph, numberofvertices);
      else label_image_df(cculongimage, graph, numberofvertices);

      /*************************************************************************
      * Copy the unsinged long integer image to the unsigned char image. Clip
      * pixel values at 255. 
      *************************************************************************/
      for(r=0;r<rows;r++){
         for(c=0;c<cols;c++){
            if(cculongimage[r][c] <= 255)
               ccimage[r][c] = (unsigned char)cculongimage[r][c];
	    else ccimage[r][c] = (unsigned char)255;
         }
      }

      printf("\nThe connected component labeled image is:\n");
      showimage(ccimage, rows, cols);

      /*************************************************************************
      * Free the memory used to store the images.
      *************************************************************************/
      free_image(image, rows);
      free_image(ccimage, rows);
      free_ulong_image(cculongimage, rows);
   }

   /****************************************************************************
   * If the program is not being run in debug mode, the image is read from
   * a file, the connected components are computed and the connected component
   * image is written out to a file.
   ****************************************************************************/
   else{
      int numberofedges = 0;

      int countedges(struct VERTEX *graph, int numberofvertices);

      if(read_pgm_image(input_filename, &image, &rows, &cols) == 0) exit(1);

      thresholdimage(image, rows, cols, threshold);

      sprintf(output_filename, "t%03d.pgm", threshold);
      if(write_pgm_image(output_filename, image, rows, cols, NULL, 255) == 0) exit(1);

      if(mkgraph(image, rows, cols, &graph, &numberofvertices, CONNECTMODE) == 0) exit(1);

      begint = clock();
      if(mode == LINKEDLIST){
         cc_linkedlist(graph, numberofvertices);
      }
      else{
         cc_disjointforest(graph, numberofvertices);
      }
      endt = clock();

      ccimage = allocate_image(rows, cols);
      cculongimage = allocate_ulong_image(rows, cols);
      if(mode == LINKEDLIST) label_image_ll(cculongimage, graph, numberofvertices);
      else label_image_df(cculongimage, graph, numberofvertices);

      for(r=0;r<rows;r++){
         for(c=0;c<cols;c++){
            if(cculongimage[r][c] <= 255)
               ccimage[r][c] = (unsigned char)cculongimage[r][c];
	    else ccimage[r][c] = (unsigned char)255;
         }
      }

      sprintf(output_filename, "t%03dcomp.pgm", threshold);
      if(write_pgm_image(output_filename, ccimage, rows, cols, NULL, 255) == 0) exit(1);

      stats_ulong(cculongimage, rows, cols, &minimum, &maximum, &average);

      numberofedges = countedges(graph, numberofvertices);

      free_image(image, rows);
      free_image(ccimage, rows);
      free_ulong_image(cculongimage, rows);

      if(mode == LINKEDLIST) printf("Using LL");
      else if(mode == DISJOINTFOREST) printf("Using DF");

      printf(" on image %s using a threshold of %d, %lu connected components\n",
         input_filename, threshold, maximum);
      printf("were found in a graph of size (%d,%d) in %f seconds.\n",
         numberofvertices, numberofedges, (endt - begint)/ (float)CLOCKS_PER_SEC);

   }
}

/*******************************************************************************
* Function: countedges
* Purpose: This function counts the number of edges in a graph.
* Name: Michael Heath, University of South Florida
* Date: 2/16/2000
*******************************************************************************/
int countedges(struct VERTEX *graph, int numberofvertices)
{
   struct EDGE *edgeptr = NULL;
   int numberofedges=0, v;

   for(v=0;v<numberofvertices;v++){
      edgeptr = graph[v].edge;
      while(edgeptr != NULL){
         numberofedges++;
         edgeptr = edgeptr->nextedge;
      }
   }

   return(numberofedges/2);  /* Divide by two because edges are counted in */
                             /* each direction.                            */
}

/*******************************************************************************
* Function: syntheticimage
* Purpose: To create a little synthetic image for algorithm development and
* testing. This image will be 5 rows by 10 columns. It will look like the
* following (but X will have a value between 130 and 255.
* 0000XXXX00
* 0000XXXX00
* 000000X0X0
* 0XXX00XX00
* 0XXX00000X
* Name: Michael Heath, University of South Florida
* Date: 2/11/2000
*******************************************************************************/
void syntheticimage(unsigned char ***imageptr, int *rows, int *cols)
{
   unsigned char **image = NULL;
   int r, c;

   *rows = 5;
   *cols = 10;

   image = allocate_image(*rows, *cols);
   *imageptr = image;

   for(r=0;r<(*rows);r++){
      for(c=0;c<(*cols);c++){
         image[r][c] = (unsigned char)(127 * drand48());
      }
   }

   image[0][4] = 200;
   image[0][5] = 198;
   image[0][6] = 255;
   image[0][7] = 211;
   image[1][4] = 240;
   image[1][5] = 137;
   image[1][6] = 203;
   image[1][7] = 130;
   image[2][6] = 186;
   image[2][8] = 156;
   image[3][6] = 200;
   image[3][7] = 189;
   image[3][1] = 142;
   image[3][2] = 160;
   image[3][3] = 173;
   image[4][1] = 250;
   image[4][2] = 188;
   image[4][3] = 168;
   image[4][9] = 211;
}

/*******************************************************************************
* Function: showimage
* Purpose: This function will print the pixel values in an image to the
* screen.
* Name: Michael Heath, University of South Florida
* Date: 2/11/2000
*******************************************************************************/
void showimage(unsigned char **image, int rows, int cols)
{
   int r, c;

   printf("      ");
   for(c=0;c<cols;c++) printf("%5d", c);
   printf("\n");
   for(r=0;r<rows;r++){
      printf("%5d ", r);
      for(c=0;c<cols;c++){
         if(image[r][c] == ZERO) printf("[ 0 ]");
         else printf("[%03d]", image[r][c]);
      }
      printf("\n");
   }
   printf("\n");
}

/*******************************************************************************
* Function: thresholdimage
* Purpose: This function will threshold an image. All pixels less than the value
* of threshold will be set to ZERO while all other pixels are set to NONZERO.
* Name: Michael Heath, University of South Florida
* Date: 2/11/2000
*******************************************************************************/
void thresholdimage(unsigned char **image, int rows, int cols, int threshold)
{
   int r, c;

   for(r=0;r<rows;r++){
      for(c=0;c<cols;c++){
         if(image[r][c] < threshold) image[r][c] = ZERO;
	 else image[r][c] = NONZERO;
      }
   }
}

/*******************************************************************************
* Function: mkgraph
* Purpose: This function will make a graph from an image. All pixels with the
* value NONZERO are to be considered nodes (vertices) of a graph, and all
* adjacent pixels (that are 8-connected) that are also nodes will define
* an edge in the graph. Edges will be specified from each vertex. Thus there
* will be twice as many edges in the representation of the graph than there
* actually are in the graph.
* Name: Michael Heath, University of South Florida
* Date: 2/11/2000
*******************************************************************************/
int mkgraph(unsigned char **image, int rows, int cols, struct VERTEX **graph,
   int *numberofvertices, int connectivity)
{
   struct VERTEX ***vertexptrimage = NULL;
   struct EDGE *newedge = NULL;
   /* int xdir[] = {1, 0, 1, 1}; */
   /* int ydir[] = {0, 1, -1, 1}; */
   int xdir[] = {1, -1, 0,  0,  1, -1, 1, -1};
   int ydir[] = {0,  0, 1, -1, -1,  1, 1, -1};
   int r, c, d, rr, cc, v=0;

   /****************************************************************************
   * Check to see that the user entered either 4 of 8 connectivity.
   ****************************************************************************/
   if(!((connectivity == 4) || (connectivity == 8))){
      fprintf(stderr, "Error in mkgraph()! The connectivity wan neither 4 nor 8.\n");
      return(0);
   }

   /****************************************************************************
   * Make one pass through the image to determine the number of pixels that 
   * have a value other than ZERO. This will be the number of vertices in the
   * graph.
   ****************************************************************************/
   *numberofvertices = 0;
   for(r=0;r<rows;r++){
      for(c=0;c<cols;c++) if(image[r][c] != ZERO) (*numberofvertices)++;
   }

   /****************************************************************************
   * Allocate an array of vertices to hold the nodes of the graph.
   ****************************************************************************/
   if(((*graph) = (struct VERTEX *) calloc((*numberofvertices), sizeof(struct VERTEX))) == NULL){
      fprintf(stderr, "Calloc error in mkgraph()! Exiting!\n");
      return(0);
   }

   /****************************************************************************
   * Create an array with the length of the number of rows in the image where
   * each element can store an array of pointers to VERTEX structures. This will
   * aid us in creating a graph of the image. We will use it to know where the
   * vertex for a pixel is located in the linked list. We will only need to have
   * at most, 3 of these arrays of pointers to VERTEX structures allocated at
   * one time. Using only three at a time will help keep down the amount of
   * memory that is required because each pointer takes 4 bytes of memory.
   ****************************************************************************/
   vertexptrimage = (struct VERTEX ***) calloc(rows, sizeof(struct VERTEX **));

   /****************************************************************************
   * Scan through the image.
   ****************************************************************************/
   for(r=0;r<2;r++){
      vertexptrimage[r] = (struct VERTEX **) calloc(cols, sizeof(struct VERTEX *));
   }
   for(r=0;r<rows;r++){
      for(c=0;c<cols;c++){

         /**********************************************************************
         * If we encounter a NONZERO pixel value we need to have a vertex for
         * this pixel. 
         **********************************************************************/
         if(image[r][c] == NONZERO){

            /*******************************************************************
            * If there is no vertex for this pixel, we create one. It is
            * allocated and placed at the head of the linked list (because it
            * is easiest to place it there.
            *******************************************************************/
	    if(vertexptrimage[r][c] == NULL){
               (*graph)[v].row = r;
               (*graph)[v].col = c;
               vertexptrimage[r][c] = (*graph)+v;
               v++;
            }

            /*******************************************************************
            * Check all of the immediate neighbors of this pixel. We are using
            * 4-connectivity so there are 4 of them. We are making a
            * (nondirected) graph so we only want one edge (a<->b). We can use
            * either ab or ba. We will accomplish only getting one edge by only
            * looking (right and down) in the image matrix for edges.
            *******************************************************************/
            for(d=0;d<connectivity;d++){
               rr = r + ydir[d];
               cc = c + xdir[d];
               if((rr>=0)&&(rr<rows)&&(cc>=0)&&(cc<cols)){
	          if(image[rr][cc] == image[r][c]){
	             if(vertexptrimage[rr][cc] == NULL){
                        (*graph)[v].row = rr;
                        (*graph)[v].col = cc;
                        vertexptrimage[rr][cc] = (*graph)+v;
                        v++;
		     }
                     newedge = (struct EDGE *) calloc(1, sizeof(struct EDGE));
                     newedge->neighbor = vertexptrimage[rr][cc];
                     newedge->nextedge = vertexptrimage[r][c]->edge;
                     vertexptrimage[r][c]->edge = newedge;
                     newedge = NULL;
                  }
               }
            }
	 }
      }
      if((r+2) < rows){
         vertexptrimage[r+2] = (struct VERTEX **) calloc(cols, sizeof(struct VERTEX *));
      }
      if((r-1) >= 0){
         free(vertexptrimage[r-1]);
      }
   }

   free(vertexptrimage[rows-1]);
   free(vertexptrimage);
   
   return(1);
}

/*******************************************************************************
* Function: showgraph
* Purpose: This function will display the contents of a graph to the screen.
* Name: Michael Heath, University of South Florida
* Date: 2/11/2000
*******************************************************************************/
void showgraph(struct VERTEX *graph, int numberofvertices)
{
   int v;
   struct EDGE *edgeptr = NULL;

   for(v=0;v<numberofvertices;v++){   
      printf("(%3d,%3d) -> {", graph[v].row, graph[v].col);
      edgeptr = graph[v].edge;
      while(edgeptr != NULL){
         printf("(%3d,%3d)", edgeptr->neighbor->row, edgeptr->neighbor->col);
         edgeptr = edgeptr->nextedge;
      }
      printf("}\n");
   }
}

/*******************************************************************************
* Function: label_image_ll
* Purpose: This function will label the connected components in an image. The
* connected components must already be stored in the graph. This function just
* labels the pixels in an image with those connected component values.
* Name: Michael Heath, University of South Florida
* Date: 2/11/2000
*******************************************************************************/
void label_image_ll(unsigned long int **image, struct VERTEX *graph, int numberofvertices)
{
   int v;
   unsigned long int nextlabel = 1;
   int row, col, sourcerow, sourcecol;

   for(v=0;v<numberofvertices;v++){
      row = graph[v].row;
      col = graph[v].col;

      sourcerow = graph[v].representative->row;
      sourcecol = graph[v].representative->col;

      if(image[sourcerow][sourcecol] == 0){
         image[sourcerow][sourcecol] = nextlabel;
         nextlabel++;
      }

      image[row][col] = image[sourcerow][sourcecol];
   }
}

/*******************************************************************************
* Function: label_image_df
* Purpose: This function will label the connected components in an image. The
* connected components must already be stored in the graph. This function just
* labels the pixels in an image with those connected component values.
* Name: Michael Heath, University of South Florida
* Date: 2/11/2000
*******************************************************************************/
void label_image_df(unsigned long int **image, struct VERTEX *graph, int numberofvertices)
{
   int v;
   unsigned long int nextlabel = 1;
   int row, col, sourcerow, sourcecol;

   for(v=0;v<numberofvertices;v++){

      row = graph[v].row;
      col = graph[v].col;

      sourcerow = (find_set_df(graph[v].parent))->row;
      sourcecol = (find_set_df(graph[v].parent))->col;

      if(image[sourcerow][sourcecol] == 0){
         image[sourcerow][sourcecol] = nextlabel;
         nextlabel++;
      }

      image[row][col] = image[sourcerow][sourcecol];
   }
}

/*******************************************************************************
* Function: print_help
* Purpose: To print out a line of help information to tell a user what arguments
* they can use when they run the program.
* Name: Michael Heath, University of South Florida
* Date: 2/14/2000
*******************************************************************************/
void print_help(char *filename)
{

   printf("\n********************************************************************************\n");
   printf("This program will compute the connected components of the pixels greater than\n");
   printf("or equal to a threshold value in an image. The -debug flag can be used to\n");
   printf("run the program on an internally stored small synthetic image. The connected\n");
   printf("components can be computed using either a linked list or a disjoint forest\n");
   printf("representation. The mode of operation is controlled with the flag -ll or -df\n");
   printf("for linked list or disjoint forest respectivly. The default is -ll. When the\n");
   printf("program is operated without the -debug flag an image and threshold value must\n");
   printf("be specified. The program will output two image files (t%%d.pgm and t%%dcomp.pgm)\n");
   printf("where %%d is used to print the threshold value. The first file will store the\n");
   printf("thresholded image and the other will store a connected component labeled image.\n");
   printf("The number of connected components and the time used to compute the connected\n");
   printf("components are printed to the screen. Any components with a label greater\n");
   printf("than 255 will be given the label 255 because the image is 8-bits per pixel.\n");
   printf("********************************************************************************\n");

   printf("\n<USAGE> %s [-debug]  [-ll | -df] -i inputimage.pgm -t thresholdvalue\n\n", filename);
   exit(1);
}

/*******************************************************************************
* Function: stats_ulong
* Purpose: To compute the minimum, maximum and avergae pixel values.
* Name: Michael Heath, University of South Florida
* Date: 1/10/2000
*******************************************************************************/
void stats_ulong(unsigned long int **image, int rows, int cols, unsigned long int *minimum, 
   unsigned long int *maximum, unsigned long int *average)
{
   int r, c;
   unsigned long int min, max;
   unsigned long int sum;

   /****************************************************************************
   * Scan through the image. Find the minimum, and maximum. Also summ all of
   * the pixel values.
   ****************************************************************************/
   min = max = image[0][0];
   sum = 0;
   for(r=0;r<rows;r++){
      for(c=0;c<cols;c++){
         sum += image[r][c];
         if(image[r][c] < min) min = image[r][c];
         else if(image[r][c] > max) max = image[r][c];
      }
   }

   *minimum = min;
   *maximum = max;
   *average = sum / (rows*cols); 
}

/*******************************************************************************
* Function: allocate_ulong_image
* Purpose: This function allocates an image. The image is an array of pointers
* to arrays. The array of pointers will have a length of the number of rows,
* and each of these pointers will point to a separate one dimensional array
* whose length is the number of columns in the image. This scheme was used
* because it allows the image to be accessed using the syntax image[r][c]
* yet still allow the image to be any size.
* Name: Michael Heath, University of South Florida
* Date: 3/6/2000
*******************************************************************************/
unsigned long int **allocate_ulong_image(int rows, int cols)
{
   unsigned long int **image=NULL;
   int r, br;

   /****************************************************************************
   * Allocate an array of pointers of type (unsigned long int *). The array is
   * allocated to have a length of the number of rows.
   ****************************************************************************/
   if((image = (unsigned long int **) calloc(rows, sizeof(unsigned long int *)))==NULL){
      fprintf(stderr, "Error allocating the array of pointers in allocate_ulong_image().\n");
      return((unsigned long int **)NULL);
   }

   /****************************************************************************
   * For each row, allocate an array of type (unigned long int).
   ****************************************************************************/
   for(r=0;r<rows;r++){
      if((image[r] = (unsigned long int *) calloc(cols, sizeof(unsigned long int)))==NULL){
         fprintf(stderr, "Error allocating an array in allocate_ulong_image().\n");
         for(br=0;br<r;br++) free(image[br]);
         free(image);
         return((unsigned long int **)NULL);
      }
   }

   return(image);
}

/*******************************************************************************
* Function: free_ulong_image
* Purpose: This function frees the memort that was previously allocated to
* store an unsigned long integer image.
* Name: Michael Heath, University of South Florida
* Date: 3/6/2000
*******************************************************************************/
void free_ulong_image(unsigned long int **image, int rows)
{
   int r;

   /****************************************************************************
   * Free each row of the image.
   ****************************************************************************/
   for(r=0;r<rows;r++) free(image[r]);

   /****************************************************************************
   * Free the array of pointers.
   ****************************************************************************/
   free(image);
}