/*  Connected Components or COLORING program for identifying
    ----------------------------------------
    objects which are connected "blobs" of '1's in a background of '0's.
    Program is written with clarity for beginners as the prime concern.

    The program will prompt for an image file name and 4 or 8 connectivity.

    1) First, a binary image of '0's and '1's is input and echoed.
    2) This char image is scanned top-to-bottom and left-to-right
       to find any 1 pixel indicating the presence of a blob.
       2.1) When a 1 pixel is found, it is assigned a new color, 2 or >.
       2.2) All 1 pixels connected to this pixel are then given the
            same color: connected pixels are located using a
            depth-first scan implemented via recursive function
            calls. All neighbors of all connecting pixels are checked;
            recursion stops when a neighbor is a color other than 1.
    3) After all separate objects have separate colors assigned,
       additional passes through the image compute the centroid and
       bounding box of each object(blob). This inefficient, but obvious
       technique requires #objects passes through the entire image.

    V1.0 written 3 July 95 by GCS for HS95.
    V2.0 written Feb 97 by GCS.
    program tested using g++ version 2.7.2
*/

#include <String.h>
#include <fstream.h>
#include <stdio.h>
/* handles up to MAXROW x MAXCOL images; for larger images enlarge these
   bounds and recompile the program. For more objects, increase the
   size of the colortable according to MAXOBJECTS. */
#define MAXROW 200
#define MAXCOL 200
#define MAXOBJECTS 70 /*can't increase without increasing colortable */

/* Global image and object data used by all procedures */
  String imagetitle;
  int numberofrows, numberofcolumns;
  int numberofobjects, connectivity;

  char image[MAXROW][MAXCOL];          /* input binary image to be colored */

  /* colortable converts integer object number into printable character */
  static  char colortable[MAXOBJECTS] = 
               {' ','1','2','3','4','5','6','7','8','9',
                'a','b','c','d','e','f','g','h','i','j',
                'l','m','n','o','p','q','r','s','t','u',
                'w','x','y','z','A','B','C','D','E','F',
                'G','H','I','J','K','L','M','N','O','P',
                'Q','R','S','T','U','V','W','X','Y','Z',
                '@','#','$','%','&','*','+','~','?','^'};

/*==========================INPUT_IMAGE================================*/
int input_image ()  // returns 0 if all is OK and 1 if insufficient storage
{
  fstream Infile;
  String filename;
/* This procedure inputs the image and checks for errors in its size */
 
  int row, col;
  cout << "Please give name of file containing the input image: " << endl;
  cin >> filename;
  Infile.open ( filename, ios::in );
  Infile >> imagetitle;   
  cout << " Image is : " << imagetitle << endl << endl;
  Infile >> numberofrows;  Infile >> numberofcolumns;
  cout << " The image size is " << numberofrows 
           << " x " << numberofcolumns << endl;
  
  /* make sure that array is in storage bounds before reading image data */
  if ( numberofrows>MAXROW || numberofcolumns>MAXCOL)
       { cout << " Image is too large for storage allocated." << endl;
         Infile.close ();  return(1); }
       else  /* read in the image */
           {  for(row=0; row<numberofrows; row++)  
               { for(col=0;col<numberofcolumns;col++)  
                      Infile >> image[row][col];
               }
              Infile.close();
              return(0); } // end else
} 

/*==========================OUTPUT_IMAGE================================*/
void output_image ()

/* This procedure prints the character image for the user to see */
{   int row,col;
    cout << endl;  cout << endl;
    cout << "Your image is as follows: " << endl << endl;
          
    for(row=0; row<numberofrows; row++)  
      { for(col=0; col<numberofcolumns; col++)
          cout << image[row][col]; // might change 'o's to blanks here
        cout << endl;
      }
      cout << endl;
}

/*==============================PROPAGATE_COLOR=======================*/

void propagate_color(int r, int c, char color)

/* r and c MUST be within the image array bounds AND image MUST
   have a border of all zeros. This function calls itself back to
   color the neighbors of neighbors, etc. until background is reached.
   connectivity should be either 4 or 8; but, not 4 is taken to be 8 */

{  if (image[r][c] != '1') return; /* if background or already colored */
   image[r][c] = color;  /* color the center pixel itself */
   /* now color all of the neighbors recursively */
   // propagate through the 4-neighbors
   propagate_color(r-1,c,color);
   propagate_color(r,c-1,color);    
   propagate_color(r,c+1,color);
   propagate_color(r+1,c,color);
   if ( connectivity == 4 ) return; // recall connectivity is global variable 
   // propagate through the 8-neighbors as well
   propagate_color(r-1,c-1,color);
   propagate_color(r-1,c+1,color);
   propagate_color(r+1,c-1,color);
   propagate_color(r+1,c+1,color);
 }

/*==========================COLOR_IMAGE================================*/

int color_image ( )

/* Colors the individual objects of the image */
{  int row, col;
   numberofobjects = 1;  // actually start with object color = 2, not 1

  cout << " Coloring using recursive depth-first propagation to neighbors."
       << endl;
  cout << " What connectivity should be used? ( 4 or 8 )- " << endl;
  cin  >> connectivity;

/* check all non border pixels and propagate object color */

   for(row=1; row<(numberofrows-1); row++)  
       for(col=1; col<(numberofcolumns-1); col++)
          if (image[row][col] == '1')  /* new uncolored object found */
            { if(numberofobjects == MAXOBJECTS) return(1);
                 numberofobjects++;  /* get new object color */
                 propagate_color(row, col, colortable[numberofobjects]); }
    return(numberofobjects);  
}

/*======================REPORT_OBJECT_FEATURES========================*/
void report_object_features ()
/*
   scans through the image for each object and computes centroid and bbox
*/
{
   int r, c, Ncolor;
   int number_of_pixels, low_r, high_r, low_c, high_c;
   float rowsum, colsum;

   cout << endl << endl;
   cout << " Object   Area    Centroid      Bounding  Box " << endl;
   cout << "=================================================" << endl;

   for(Ncolor=2; Ncolor<=numberofobjects; Ncolor++)
     {  /* initialize data for object of this color */
        number_of_pixels = 0;  rowsum = 0.0; colsum = 0.0;
        low_r = MAXROW; high_r = -1; low_c = MAXCOL; high_c = -1;
     
     /* scan image and account for all pixels of this color */
     for(r=0; r<numberofrows; r++)
       for(c=0; c<numberofcolumns; c++)
         if(image[r][c] == colortable[Ncolor])
	   { number_of_pixels++;
             rowsum = rowsum + r;  colsum = colsum + c;
             if(r<low_r) low_r = r;  if(r>high_r) high_r = r;
             if(c<low_c) low_c = c;  if(c>high_c) high_c = c;
           }
     /* print out summary features of object of this color */
     cout.width(5); cout << "    " << colortable[Ncolor];
     cout.width(8); cout << number_of_pixels << "   (";
     cout.width(5);cout.precision(3); cout << rowsum/number_of_pixels 
            << " , " << colsum/number_of_pixels << ")";
     cout.width(4); cout.precision(4);
     cout << " [ (" << low_r << ", " << low_c << ") (" << high_r << ", "
          << high_c << ") ]" << endl;
      } /* end of for color loop */
}
/*============================MAIN PROGRAM============================*/
main () 
{
  int error_code, objectcount;

  error_code = input_image ();
  if( error_code != 0 ) { cout << " ERROR EXIT " << endl; return(0); } 

  output_image();
  cout << " Recall that image MUST have a border of all '0's " << endl;

  /* Now color each object with a different color(pixel value). */
  objectcount = color_image( );
  cout << " Number of objects = " << objectcount-1 << endl;
  cout << " Recall that no object has color label = 1 " << endl;
  output_image();
  
  /* scan the colored image to compute the centroid and bounding boxes */
  report_object_features();
}