From:	CRC          "Craig Cockburn" 23-DEC-1986 15:48
To:	JHB
Subj:	Interesting thinning algorithm

From:	N%"rbf@edai" 23-DEC-1986 12:51
To:	crc@uk.ac.ed.ecsvax
Subj:	

Date:	Mon, 22 Dec 86 18:15:24 gmt
From:	Bob Fisher <rbf@uk.ac.ed.edai>

craig: try this. reference below for where it came from. I have a copy
	of the paper. not a brilliant algorithm, butt i don't know
	the details of others. bob

/*

Program:	thin

Function: This program thins a picture. It makes a binary picture
		from all pixels with value above zero, and thins that.
		This picture is then used to mask the original picture.
Algorithm:
		Adapted from that given (in parallel form) in:
		Levialdi, S., Maggiolo-Schettini, A., Napoli, M.,
		Tortora, G., Uccella, G., "On the Design and
		Implementation of PIXAL, a Language for Image
		Processing", in Duff and Levialdi (eds), Languages
		and Architectures for Image Processing, Academic
		Press, 1981.

Invocation:	type 'thin <inpicname> <outpicname>'

Parameters:
		<inpicname> - input picture <inpicname>.pic
		<outpicname> - output picture <outpicname>.pic

Misc: The program allows any size picture.

Use of program:	Just as invoked. Various errors are reported.

Construction: cc -O thin.c alib -o thin

*/
#include <stdio.h>
#include "pic.h"	/* temp link *** */
#include "vislib.h" /* temp link *** */
int buffer;		/* temporary buffer switch */
int p0,p1,p2,p3,p4,p5,p6,p7,p8;
PICDESC pdo,pdi;		/* picture file descriptors (out,in) */
int pica[256][256],picb[256][256];
int pici[256][256],pico[256][256];
main(argc,argv)
int argc;		/* number of arguments */
char *argv[];		/* argument strings */
{
struct pichead inph;		/* picture header record */
int hsize,vsize;	/* horizontal, vertical sizes */
int i,j,data,one,zero,notdone;
char infn[25],outfn[25];

/* check parameters */
if (argc != 3)
    {printf("Use is thin <inpic> <outpic>\n");
	exit(1); };

/* get picture files */
strcpy(infn,argv[1]);
strcat(infn,".pic");
pdi = openpic(infn,OP_READ_ONLY,NO_SZ,&inph);
if (pdi == -1) {printf("Unable to open source picture"); exit(1);};

/* calculate picture sizes */
/*hsize = (inph.right - inph.left + 1)/inph.hor;		/* old size */
/*vsize = (inph.bottom - inph.top + 1)/inph.ver;*/
hsize=vsize=256;	/* *** temps *** */

/* copy binary picture */
data = 0;
one = 1;
for (j=0; j<vsize; j++)
    for (i=0; i<hsize; i++)
	{getcell(pdi,i,j,&data);
	 pici[j][i] = data;
	 if (data) pica[j][i] = one;
	};
closepic(pdi);

/* make new picture */
strcpy(outfn,argv[2]);
strcat(outfn,".pic");
pdo = makepic(outfn,0666,hsize,vsize,1,8,INT_UTYPE);
if (pdo == -1) {printf("Unable to make output picture");exit(1);};

/* do thinning */
buffer = 1;
data = 0;
zero=0;
one=1;
p0=p1=p2=p3=p4=p5=p6=p7=p8=0;
do {
    notdone=0;

    /* do one thinning iteration */
    for (j=0; j<vsize; j++)
	for (i=0; i<hsize; i++)
	    {
	     tgetcell(i,j,&data);
	     if (data && (j>0) && (j<vsize-1) && (i>0) && (i<hsize-1))
		{ /* consider thinning */
		 tgetwind(i,j);
		 if (!p0 && !p1 && !p3 && p5 && p7 && p8) goto dothin;
		 if (!p1 && !p2 && p3 && !p5 && p7 && p6) goto dothin;
		 if (p1 && p3 && !p5 && !p7 && !p8 && p0) goto dothin;
		 if (p1 && !p3 && p5 && !p6 && !p7 && p2) goto dothin;
		 if (!p0 && !p1 && !p2 && p3 && !p5 && !p6 && p7 && p8)
			goto dothin;
		 if (!p0 && p1 && !p2 && !p3 && p5 && !p6 && !p7 && p8)
			goto dothin;
		 if (!p0 && p1 && !p2 && p3 && !p5 && p6 && !p7 && !p8)
			goto dothin;
		 if (!p0 && p1 && p2 && p3 && !p5 && !p6 && !p7 && !p8)
			goto dothin;
		 if (p0 && p1 && p2 && p3 && p5 && !p6 && !p7 && !p8)
			goto dothin;
		 if (p0 && p1 && !p2 && p3 && !p5 && p6 && p7 && !p8)
			goto dothin;
		 tputcell(i,j,&one);	/* no thin, so just keep the one */
		 goto next;
dothin:
		 tputcell(i,j,&zero);
		 notdone=1;
		 goto next;
		};
	    tputcell(i,j,&data);
next:
	    zero=0;
	    };

    /* switch buffers */
    buffer = 1-buffer;
    } while (notdone);

/* create output picture */
for (j=1; j<vsize-1; j++)
    for (i=1; i<hsize-1; i++)
	{tgetcell(i,j,&data);
	 if (data)
		   {data = pici[j][i];
		    putcell(pdo,i,j,&data);};
	};

/* clean up */
closepic(pdo);
return;};

/* get cell from current input binary */
tgetcell(i,j,data)
int i,j;
int *data;
{

if (buffer) *data = pica[j][i];
		else *data = picb[j][i];
};

/* put cell to alternate output binary */
tputcell(i,j,data)
int i,j;
int *data;
{

if (buffer) picb[j][i] = *data;
		else pica[j][i] = *data;

};

/* get window about current point */
tgetwind(i,j)
int i,j;
{

if (buffer)
	{p0 = pica[j-1][i-1];
	 p1 = pica[j-1][i];
	 p2 = pica[j-1][i+1];
	 p3 = pica[j][i-1];
	 p5 = pica[j][i+1];
	 p6 = pica[j+1][i-1];
	 p7 = pica[j+1][i];
	 p8 = pica[j+1][i+1];
	 }
    else
	{p0 = picb[j-1][i-1];
	 p1 = picb[j-1][i];
	 p2 = picb[j-1][i+1];
	 p3 = picb[j][i-1];
	 p5 = picb[j][i+1];
	 p6 = picb[j+1][i-1];
	 p7 = picb[j+1][i];
	 p8 = picb[j+1][i+1];
	 };
};