/* labeling.c */
/* binary image labeling algorithm */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "mypgm.h"

#define L_BASE  100       /* minimum label */
#define BLACK 0
#define WHITE 255

int labeling();
void labelset(int xs, int ys, int label);

int labeling()
{
  int i, j, label;
  
  x_size2 = x_size1;
  y_size2 = y_size1;
  for (j = 0; j < y_size1; j++) {
    for (i = 0; i < x_size1; i++) {
      image2[j][i] = image1[j][i];
    }
  }
  label = L_BASE;
  for (j = 0; j < y_size2; j++) {
    for (i = 0; i < x_size2; i++) {
      if (image2[j][i] == BLACK) {
	if (label >= WHITE) {
	  printf("-- Error! too many labels.\n\n");
	  return (-1);
	}
	labelset(i, j, label++);
      }
    }
  }
  printf("Number of labels = %d\n", label - L_BASE);
  return (0);
}


void labelset(int xs, int ys, int label)
{
  int i, j, cnt, im, ip, jm, jp;
  
  image2[ys][xs] = label;
  for (;;) {
    cnt = 0;
    for (j = 0; j < y_size2; j++) {
      for (i = 0; i < x_size2; i++) {
	if (image2[j][i] == label) {
	  im = i - 1 < 0 ? 0 : i - 1;
	  ip = i + 1 > x_size2 - 1 ? x_size1 - 1 : i + 1;
	  jm = j - 1 < 0 ? 0 : j - 1;
	  jp = j + 1 > y_size2 - 1 ? y_size1 - 1 : j + 1;
	  if (image2[j][ip] == BLACK) {
	    image2[j][ip] = label;
	    cnt++;
	  }
	  if (image2[jm][ip] == BLACK) {
	    image2[jm][ip] = label;
	    cnt++;
	  }
	  if (image2[jm][i] == BLACK) {
	    image2[jm][i] = label;
	    cnt++;
	  }
	  if (image2[jm][im] == BLACK) {
	    image2[jm][im] = label;
	    cnt++;
	  }
	  if (image2[j][im] == BLACK) {
	    image2[j][im] = label;
	    cnt++;
	  }
	  if (image2[jp][im] == BLACK) {
	    image2[jp][im] = label;
	    cnt++;
	  }
	  if (image2[jp][i] == BLACK) {
	    image2[jp][i] = label;
	    cnt++;
	  }
	  if (image2[jp][ip] == BLACK) {
	    image2[jp][ip] = label;
	    cnt++;
	  }
	}
      }
    }
    if (cnt == 0) break;
  }
}


main( )
{
  load_image_data( ); /* loading image1 */
  labeling();         /* binary image labeling */
  save_image_data( ); /* saving image2 */
  return;
}