/* Hilditch.c */
/* Hilditch's thinning algorithm */
#include <stdio.h>
#include <stdlib.h>
#include "mypgm.h"
#define BLACK 0
#define WHITE 255
#define GRAY 128

int func_nc8(int *b)
     /* connectivity detection for each point */ 
{
  int n_odd[4] = { 1, 3, 5, 7 };  /* odd-number neighbors */
  int i, j, sum, d[10];           /* control variable */
  
  for (i = 0; i <= 9; i++) {
    j = i;
    if (i == 9) j = 1;
    if (abs(*(b + j)) == 1) {
      d[i] = 1;
    } else {
      d[i] = 0;
    }
  }
  sum = 0;
  for (i = 0; i < 4; i++) {
    j = n_odd[i];
    sum = sum + d[j] - d[j] * d[j + 1] * d[j + 2];
  }
  return (sum);
}

void hilditch( )
     /* thinning of binary image by Hilditch's algorithm */
     /* WHITE --> 0, GRAY --> -1, BLACK --> 1 */
     /* input image1[y][x] ===> output image2[y][x] */
{
  int offset[9][2] = {{0,0},{1,0},{1,-1},{0,-1},{-1,-1},
		      {-1,0},{-1,1},{0,1},{1,1} }; /* offsets for neighbors */
  int n_odd[4] = { 1, 3, 5, 7 };      /* odd-number neighbors */
  int px, py;                         /* X/Y coordinates  */
  int b[9];                           /* gray levels for 9 neighbors */
  int condition[6];                   /* valid for conditions 1-6 */
  int counter;                        /* number of changing points  */
  int i, x, y, copy, sum;             /* control variable          */
  
  printf(" Hilditch's thinning starts now.\n");
  /* initialization of arrays */
  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];
    }
  }
  /* processing starts */
  do {
    counter = 0;
    for (y = 0; y < y_size1; y++) {
      for (x = 0; x < x_size1; x++) {
	/* substitution of 9-neighbor gray values */
	for (i = 0; i < 9; i++) {
	  b[i] = 0;
	  px = x + offset[i][0];
	  py = y + offset[i][1];
	  if (px >= 0 && px < x_size1 &&
	      py >= 0 && py < y_size1) {
	    if (image2[py][px] == BLACK) {
	      b[i] = 1;
	    } else if (image2[py][px] == GRAY) {
	      b[i] = -1;
	    }
	  }
	}
	for (i = 0; i < 6; i++) {
	  condition[i] = 0;
	}
	
	/* condition 1: figure point */
	if (b[0] == 1) condition[0] = 1;
	
	/* condition 2: boundary point */
	sum = 0;
	for (i = 0; i < 4; i++) {
	  sum = sum + 1 - abs(b[n_odd[i]]);
	}
	if (sum >= 1) condition[1] = 1;
	
	/* condition 3: endpoint conservation */
	sum = 0;
	for (i = 1; i <= 8; i++) {
	  sum = sum + abs(b[i]);
	}
	if (sum >= 2) condition[2] = 1;
	
	/* condition 4: isolated point conservation */
	sum = 0;
	for (i = 1; i <= 8; i++) {
	  if (b[i] == 1) sum++;
	}
	if (sum >= 1) condition[3] = 1;
	
	/* condition 5: connectivity conservation */
	if (func_nc8(b) == 1) condition[4] = 1;
	
	/* condition 6: one-side elimination for line-width of two */
	sum = 0;
	for (i = 1; i <= 8; i++) {
	  if (b[i] != -1) {
	    sum++;
	  } else {
	    copy = b[i];
	    b[i] = 0;
	    if (func_nc8(b) == 1) sum++;
	    b[i] = copy;
	  }
	}
	if (sum == 8) condition[5] = 1;
	
	/* final decision */
	if (condition[0] && condition[1] && condition[2] &&
	    condition[3] && condition[4] && condition[5]) {
	  image2[y][x] = GRAY; /* equals -1 */
	  counter++;
	}
      } /* end of x */
    } /* end of y */
    
    if (counter != 0) {
      for (y = 0; y < y_size1; y++) {
	for (x = 0; x < x_size1; x++) {
	  if (image2[y][x] == GRAY) image2[y][x] = WHITE;
	}
      }
    }
  } while (counter != 0);
}


main( )
{
  load_image_data( ); /* loading image1 */
  hilditch( );        /* Hilditch's thinning operation */
  save_image_data( ); /* storing image2 */
  return 0;
}