/*  PROGRAM TO COUNT THE NUMBER OF HOLES IN A BINARY IMAGE.
    -------------------------------------------------------
    This program was developed using gcc version 2.7.2; only the
    use of String.h might give trivial portability problems.

    Execute this program via  prompt>holecounting < inputimagefile
                          or  prompt>a.out < inputimagefile

    It is assumed that the image border is all '1's and that
    the holes are connected regions of '0's inside the '1's.

    This program scans through a simple ascii image whose pixels are  
    stored as characters '0' or '1'. The image file is assumed
    to have  1) a one line character string giving the image title
             2) the number of rows and columns of the image
             3) the image pixels by row then column.
    An error exit is taken if the image array bounds are violated.

    An EXAMPLE inputimagefile IS AS BELOW:
very_simple_test_image_for_hole_counting_program
  4  10 
1111111111
1100000011
1111001111
1111111111


    Version V1 written June 95 by GCS for HS95 program.
    Version V2 updated Feb 97 by GCS.
*/

#include <String.h>  
#include <stdlib.h>
/* handles images up to size MAXROW rows and MAXCOL columns;
   for a different (larger) size, change the values with your editor
   and recompile the program */
#define MAXROW 200
#define MAXCOL 200   

main() {
  String imagetitle;   // title should have no blanks (whitespace)
  int numberofrows,numberofcolumns,row,col;
  int external,internal; /* number of such corners*/

  char image[MAXROW][MAXCOL];

  cout << "\n\n=======HOLECOUNTING PROGRAM:V2======GCS,Feb97====\n\n";

  /* Read and echo the header information from the image file  */
  cin >> imagetitle; 
  cout << " Image is : " << imagetitle << endl << endl;
  cin >> numberofrows >> 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 to it." << endl;
  
       else  /* =====process the image for the user===== */

           { /* ========read in the image=========== */
              for(row=0; row<numberofrows; row++)  
                for(col=0; col<numberofcolumns; col++)
                   cin >> image[row][col];
 
            /* =======show the image to the user======= */
            cout << endl;  cout << endl;
            cout << "The image is as follows: " << endl;
              for(row=0; row<numberofrows; row++)  
                { for(col=0; col<numberofcolumns; col++)
                     cout << image[row][col];
                  cout << endl;
                 }
              cout << endl;

            /* =====count the number of external and internal corners====
               and from them compute the number of holes, which are
               connected regions of "0"s surrounded by "1"s. This loop
               checks all 2 x 2 neighborhoods for corner patterns in a
               very obvious manner.
            */
            external = 0;      internal = 0;
            for(int r=0; r<(numberofrows-1); r++)
              for(int c=0; c<(numberofcolumns-1); c++)
               /* if an external corner pattern exists, count it */
               {if ( (image[r][c]=='1' && image[r][c+1]=='1'
                       && image[r+1][c]=='1' && image[r+1][c+1]=='0') ||
                     (image[r][c]=='1' && image[r][c+1]=='1'
                       && image[r+1][c]=='0' && image[r+1][c+1]=='1') ||
                     (image[r][c]=='1' && image[r][c+1]=='0'
                       && image[r+1][c]=='1' && image[r+1][c+1]=='1') ||
                     (image[r][c]=='0' && image[r][c+1]=='1'
                       && image[r+1][c]=='1' && image[r+1][c+1]=='1') 
                   ) external = external + 1;

               /* if an internal corner pattern exists, count it */
                if ( (image[r][c]=='0' && image[r][c+1]=='0'
                       && image[r+1][c]=='0' && image[r+1][c+1]=='1') ||
                     (image[r][c]=='0' && image[r][c+1]=='0'
                       && image[r+1][c]=='1' && image[r+1][c+1]=='0') ||
                     (image[r][c]=='1' && image[r][c+1]=='0'
                       && image[r+1][c]=='0' && image[r+1][c+1]=='0') ||
                     (image[r][c]=='0' && image[r][c+1]=='1'
                       && image[r+1][c]=='0' && image[r+1][c+1]=='0') 
                   ) internal = internal + 1;
	      }
            cout << " Number of external corners = " << external << endl;
            cout << " Number of internal corners = " << internal << endl;
            cout << " Number of holes = " << (external - internal)/4 << endl;

	    } /* end of image processing else statement */
}