/* kfill.c */
/* filling salt and pepper noise */
#include <stdio.h>
#include <stdlib.h>
#include "mypgm.h"

#define BLACK 0
#define WHITE 255

void k_fill()
     /* filling salt and pepper noise using k x k window */
{
  int x, y;             /* X/Y coordinates of boundary point */
  int k;                /* k-filling parameter */
  int xs, xe, ys, ye;   /* window edge points */
  int npc, npp;         /* number of core and perimeter points */
  int i, j;
  int * data;           /* on/off values of surrounding points */
  int count;            /* number of changes in a cycle */
  int sum, cross, corner;
  
  /* outermost lines are cleared */
  for (x = 0; x < x_size1; x++) {
    image1[0][x] = WHITE;
    image1[y_size1 - 1][x] = WHITE;
  }
  for (y = 0; y < y_size1; y++) {
    image1[y][0] = WHITE;
    image1[y][x_size1 - 1] = WHITE;
  }
  
  /* initialization of output image */
  x_size2 = x_size1;
  y_size2 = y_size1;
  for (y = 0; y < y_size2; y++) {
    for (x = 0; x < x_size2; x++) {
      image2[y][x] = image1[y][x];
    }
  }
  
  /* iterative reduction of pepper and salt noise */
  printf("k-filling is applied to binary image.\n");
  while (1) {
    printf("\nPlease input the window size of k (>= 3): ");
    scanf("%d", &k);
    if (k >= 3) break;
  }
  npc = (k - 2) * (k - 2);
  npp = 4 * (k - 1);
  data = (int *)malloc(npp * sizeof(int));
  xs = ys = k%2 == 0 ? k/2 - 1 : k/2;
  xe = ye = k/2;
  
  do {
    count = 0;
    for (y = 0; y < y_size1; y++) {
      for (x = 0; x < x_size1; x++) {
	image1[y][x] = image2[y][x];
      }
    }
    
    /* White filling */
    for (y = ys; y < y_size1 - ye; y++) {
      for (x = xs; x < x_size1 - xe; x++) {
	sum = 0;
	for (j = -ys + 1; j <= ye - 1; j++) {
	  for (i = -xs + 1; i <= xe - 1; i++) {
	    if (image1[y + j][x + i] == WHITE) sum++;
	  }
	}
	if (sum != npc) continue;
	i = 0;
	for (j = 0; j >= - ys; j--) {
	  data[i++] = image1[y + j][x + xe] == BLACK ? 1 : 0;
	}
	for (j = xe - 1; j >= - xs; j--) {
	  data[i++] = image1[y - ys][x + j] == BLACK ? 1 : 0;
	}
	for (j = - ys + 1; j <= ye; j++) {
	  data[i++] = image1[y + j][x - xs] == BLACK ? 1 : 0;
	}
	for (j = - xs + 1; j <= xe; j++) {
	  data[i++] = image1[y + ye][x + j] == BLACK ? 1 : 0;
	}
	for (j = ye - 1; j > 0; j--) {
	  data[i++] = image1[y + j][x + xe] == BLACK ? 1 : 0;
	}
	sum = 0;
	cross = 0;
	for (i = 0; i < npp; i++) {
	  sum += data[i];
	  cross += abs(data[(i + 1)%npp] - data[i]);
	}
	cross /= 2;
	corner = data[ys] + data[ys + k - 1]
	  + data[ys + 2*(k - 1)] + data[ys + 3*(k - 1)];
	if ((cross <= 1) && (sum > (3*k - 4) || 
			     (sum == 3*k - 4 && corner == 2))) {
	  for (j = -ys + 1; j <= ye - 1; j++) {
	    for (i = -xs + 1; i <= xe - 1; i++) {
	      image2[y + j][x + i] = BLACK;
	    }
	  }
	  count++;
	}
      }
    }
    
    /* Black filling */
    for (y = ys; y < y_size1 - ye; y++) {
      for (x = xs; x < x_size1 - xe; x++) {
	sum = 0;
	for (j = -ys + 1; j <= ye - 1; j++) {
	  for (i = -xs + 1; i <= xe - 1; i++) {
	    if (image1[y + j][x + i] == BLACK) sum++;
	  }
	}
	if (sum != npc) continue;
	i = 0;
	for (j = 0; j <= ys; j++) {
	  data[i++] = image1[y - j][x + xe] == WHITE ? 1 : 0;
	}
	for (j = - xe + 1; j <= xs; j++) {
	  data[i++] = image1[y - ys][x - j] == WHITE ? 1 : 0;
	}
	for (j = - ys + 1; j <= ye; j++) {
	  data[i++] = image1[y + j][x - xs] == WHITE ? 1 : 0;
	}
	for (j = - xs + 1; j <= xe; j++) {
	  data[i++] = image1[y + ye][x + j] == WHITE ? 1 : 0;
	}
	for (j = ye - 1; j > 0; j--) {
	  data[i++] = image1[y + j][x + xe] == WHITE ? 1 : 0;
	}
	sum = 0;
	cross = 0;
	for (i = 0; i < npp; i++) {
	  sum += data[i];
	  cross += abs(data[i] - data[(i + 1)%npp]);
	}
	cross /= 2;
	corner = data[ys] + data[ys + k - 1]
	  + data[ys + 2*(k - 1)] + data[ys + 3*(k - 1)];
	if ((cross <= 1) && (sum > (3*k - 4) || 
			     (sum == 3*k - 4 && corner == 2))) {
	  for (j = -ys + 1; j <= ye - 1; j++) {
	    for (i = -xs + 1; i <= xe - 1; i++) {
	      image2[y + j][x + i] = WHITE;
	    }
	  }
	  count++;
	}
      }
    } 
  } while (count);
  free(data);
}


main( )
{
  load_image_data( ); /* loading image1 */
  k_fill( );          /* salt and pepper noise reduction */
  save_image_data( ); /* saving image2 */
  return;
}