image.c

Hausdorff Distance for Image Recognition

 *	to which the pointer refers; imPtrDown increments it. imPtrLeft and
 *	imPtrRight decrement and increment respectively the x component.
 *
 * imPtrEq compares two pointers for equality, returning TRUE if they are,
 *	FALSE if they are not. The pointers must refer to pixels in the
 *	same Image. The use of this allows more efficient image operations.
 *
 * Some of these are implemented partially as macros for strange reasons.
 * As a result, they may not be entirely safety-checked. If you want to
 * have safety-checking in place, at a cost in speed and code size, put
 * -DIMAGE_CHECKALL on your gcc line, or add
 * #define IMAGE_CHECKALL
 * to your code somewhere before you include image.h.
 * This only works if you're compiling with gcc.
 *
 */

#include "misc.h"
#include "image.h"
#include <ctype.h>
#include <stdio.h>

/* File tags */
/* Standard pbmplus tags */
#define	TAG_BINARY_COOKED	"P1"
#define	TAG_GRAY_COOKED		"P2"
#define	TAG_RGB_COOKED		"P3"
#define	TAG_BINARY		"P4"
#define	TAG_GRAY		"P5"
#define	TAG_RGB			"P6"
/* Nonstandard wjr tags */
#define	TAG_FLOAT	"Q1"
#define	TAG_DOUBLE	"Q2"
#define	TAG_LONG	"Q3"
#define	TAG_SHORT	"Q4"

/* Maximum line length in a non-raw P?M file */
#define	PBM_MAX_LINELEN	70

/* How big a comment buffer we'll have for reading files */
#define	LOAD_COMMENT_MAX	8192

static char incomment[LOAD_COMMENT_MAX];
static int incommentsize;

static void *readBinaryCooked(FILE *inFile, ImageHeader **readimHeader);
static void *readGrayCooked(FILE *inFile, ImageHeader **readimHeader);
static void *readRGBCooked(FILE *inFile, ImageHeader **readimHeader);
static void *readBinary(FILE *inFile, ImageHeader **readimHeader);
static void *readGray(FILE *inFile, ImageHeader **readimHeader);
static void *readRGB(FILE *inFile, ImageHeader **readimHeader);
static void *readFloat(FILE *inFile, ImageHeader **readimHeader);
static void *readDouble(FILE *inFile, ImageHeader **readimHeader);
static void *readLong(FILE *inFile, ImageHeader **readimHeader);
static void *readShort(FILE *inFile, ImageHeader **readimHeader);

/*
 * Here begins file magic: list of tags with associated file types and
 * reading functions.
 */
static struct {
    char *filetag;
    ImageType filetype;
    void * (*readfunc)(FILE *inFile, ImageHeader **readimHeader);
    } fileReaders[] = {
	{ TAG_BINARY_COOKED, IMAGE_BINARY, readBinaryCooked },
	{ TAG_GRAY_COOKED, IMAGE_GRAY, readGrayCooked },
	{ TAG_RGB_COOKED, IMAGE_RGB, readRGBCooked },
	{ TAG_BINARY, IMAGE_BINARY, readBinary },
	{ TAG_GRAY, IMAGE_GRAY, readGray },
	{ TAG_RGB, IMAGE_RGB, readRGB },
	{ TAG_FLOAT, IMAGE_FLOAT, readFloat },
	{ TAG_DOUBLE, IMAGE_DOUBLE, readDouble },
	{ TAG_LONG, IMAGE_LONG, readLong },
	{ TAG_SHORT, IMAGE_SHORT, readShort }
	};
#define	NREADERS	(sizeof(fileReaders) / sizeof(fileReaders[0]))

/* Here are all the conversion routines */
static void                  *pG2F(void *im), *pG2R(void *im), *pG2D(void *im);
static void *dG2B(void *im), *pG2L(void *im), *pG2S(void *im);
static void *dF2G(void *im),                  *dF2R(void *im), *pF2D(void *im);
static void *dF2B(void *im), *dF2L(void *im), *dF2S(void *im);
static void *dR2G(void *im), *dR2F(void *im),                  *dR2D(void *im);
static void *dR2B(void *im), *dR2L(void *im), *dR2S(void *im);
static void *dD2G(void *im), *dD2F(void *im), *dD2R(void *im)                 ;
static void *dD2B(void *im), *dD2L(void *im), *dD2S(void *im);
static void *pB2G(void *im), *pB2F(void *im), *pB2R(void *im), *pB2D(void *im);
static void                  *pB2L(void *im), *pB2S(void *im);
static void *dL2G(void *im), *dL2F(void *im), *dL2R(void *im), *pL2D(void *im);
static void *dL2B(void *im),                  *dL2S(void *im);
static void *dS2G(void *im), *pS2F(void *im), *dS2R(void *im), *pS2D(void *im);
static void *dS2B(void *im), *pS2L(void *im)                 ;

/*
 * Here's the table of conversions.
 * convertTable[type1][type2] tells how we convert from an image of type1
 * to an image of type2.
 */
static struct {
    boolean isPromotion;
    double slope;
    double offset;
    void * (*convertFunc)(void *im);
    } convertTable[IMAGE_SHORT + 1][IMAGE_SHORT + 1] = {
	{	/* Invalid image type */
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL},
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL},
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL} },

	{	/* GrayImage */
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL}, { TRUE , 1, 0, pG2F},
	{ TRUE , 1, 0, pG2R}, { TRUE , 1, 0, pG2D}, { FALSE, 0, 0, dG2B},
	{ TRUE , 1, 0, pG2L}, { FALSE, 0, 0, NULL}, { TRUE , 1, 0, pG2S} },

	{	/* FloatImage */
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, dF2G}, { FALSE, 0, 0, NULL},
	{ FALSE, 0, 0, dF2R}, { TRUE , 1, 0, pF2D}, { FALSE, 0, 0, dF2B},
	{ FALSE, 0, 0, dF2L}, { FALSE, 0, 0, NULL}, { FALSE, 0, 0, dF2S} },

	{	/* RGBImage */
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, dR2G}, { FALSE, 0, 0, dR2F},
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, dR2D}, { FALSE, 0, 0, dR2B},
	{ FALSE, 0, 0, dR2L}, { FALSE, 0, 0, NULL}, { FALSE, 0, 0, dR2S} },

	{	/* DoubleImage */
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, dD2G}, { FALSE, 0, 0, dD2F},
	{ FALSE, 0, 0, dD2R}, { FALSE, 0, 0, NULL}, { FALSE, 0, 0, dD2B},
	{ FALSE, 0, 0, dD2L}, { FALSE, 0, 0, NULL}, { FALSE, 0, 0, dD2S} },

	{	/* BinaryImage */
	{ FALSE, 0, 0, NULL}, { TRUE , 1-COLRNG, COLRNG-1, pB2G}, { TRUE , 1, 0, pB2F},
	{ TRUE , 1-COLRNG, COLRNG-1, pB2R}, { TRUE , 1, 0, pB2D}, { FALSE, 0, 0, NULL},
	{ TRUE , 1-COLRNG, COLRNG-1, pB2L}, { FALSE, 0, 0, NULL}, { TRUE , 1-COLRNG, COLRNG-1, pB2S} },
	
	{	/* LongImage */
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, dL2G}, { FALSE, 0, 0, dL2F},
	{ FALSE, 0, 0, dL2R}, { TRUE , 1, 0, pL2D}, { FALSE, 0, 0, dL2B},
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL}, { FALSE, 0, 0, dL2S} },

	{	/* PtrImage */
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL},
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL},
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL} },

	{	/* ShortImage */
	{ FALSE, 0, 0, NULL}, { FALSE, 0, 0, dS2G}, { TRUE , 1, 0, pS2F},
	{ FALSE, 0, 0, dS2R}, { TRUE , 1, 0, pS2D}, { FALSE, 0, 0, dS2B},
	{ TRUE , 1, 0, pS2L}, { FALSE, 0, 0, NULL}, { FALSE, 0, 0, NULL} }
	};

/*
 * This routine allocates a rectangular area of width*height*el_size bytes
 * (suitable for holding width*height elements of el_size size), and
 * initialises it to zero. It then allocates and sets up an array of
 * height pointers into this, each one pointing to a row (width*el_size bytes).
 *
 * Each pointer is offset by xbase elements, and the returned pointer is
 * offset by ybase rows; this means that the first element in this array
 * is accessed by array[ybase][xbase]. Note that xbase and ybase may be
 * negative.
 *
 * Note that this isn't really type-safe: it takes this (void **) pointer
 * which will get cast, for example, into a (float **) pointer, which isn't
 * really legit. On machines where all pointers have the same format,
 * it will work. The problem is also that dereferencing a (float **)
 * should get you a (float *), but will actually point to the bit-pattern
 * of a (void *), which could be cast into that (float *) with no problems,
 * but which might not work if it is simply *treated* as a (float *)
 * without the cast. Bah. Doing it right would be too horrendous for words.
 * C just can't handle generics very well...
 */
static void **
allocImage(unsigned width, unsigned height, int xbase, int ybase,
	   unsigned el_size)
{
    register int i;
    register void *mainArea;
    register void **ptrArea;
    register char *p;
    register void **q;

    /* Allocate the actual image data area */
    mainArea = calloc(height, width*el_size);
    if (mainArea == (void *)NULL) {
	return((void **)NULL);
	}

    /* Allocate a pointer for each row */
    ptrArea = (void **)malloc(height * sizeof(void *));
    if (ptrArea == (void **)NULL) {
	free(mainArea);
	return((void **)NULL);
	}

    /* Set up the row pointers to point to the (offset) rows */
    for (i = 0, q = ptrArea, p = (char *)mainArea;
	 i < height;
	 i++, q++, p += width*el_size) {
	*q = (void *)(p - xbase * (int)el_size);
	}

    /* and return the (offset) row pointer area */
    return(ptrArea - ybase);
    }

/*
 * This routine gets rid of a memory block allocated by allocImage above.
 */
static void
freeImage(void **ptr, int xbase, int ybase, unsigned el_size)
{
    /* Free the memory block. This should give the first element. */
    free((void *)((char *)(*(ptr + ybase)) + xbase * (int)el_size));
    /* and the pointer block */
    free((void *)(ptr + ybase));
    }

/*
 * Root through the image's header to find its type, and get the appropriate
 * base pointer of the data area, and the element size.
 */
static void
getAreaAndSize(void *im, ImageHeader *header,
	       void ***areaPtr, unsigned *el_size)
{
    assert(im != (void *)NULL);
    assert(header != (ImageHeader *)NULL);
    assert(areaPtr != (void ***)NULL);
    assert(el_size != (unsigned *)NULL);

    switch(header->tag) {
      case IMAGE_GRAY: {
	*areaPtr = (void **)(((GrayImage)im)->data);
	*el_size = sizeof(unsigned char);
	break;
	}
	
      case IMAGE_FLOAT: {
	*areaPtr = (void **)(((FloatImage)im)->data);
	*el_size = sizeof(float);
	break;
	}
	
      case IMAGE_RGB: {
	*areaPtr = (void **)(((RGBImage)im)->data);
	*el_size = sizeof(RGB);
	break;
	}

      case IMAGE_DOUBLE: {
	*areaPtr = (void **)(((DoubleImage)im)->data);
	*el_size = sizeof(double);
	break;
	}

      case IMAGE_BINARY: {
	*areaPtr = (void **)(((BinaryImage)im)->data);
	*el_size = sizeof(char);
	break;
	}

      case IMAGE_LONG: {
	*areaPtr = (void **)(((LongImage)im)->data);
	*el_size = sizeof(long);
	break;
	}

      case IMAGE_PTR: {
	*areaPtr = (void **)(((PtrImage)im)->data);
	*el_size = sizeof(void *);
	break;
	}

      case IMAGE_SHORT: {
	*areaPtr = (void **)(((ShortImage)im)->data);
	*el_size = sizeof(short);
	break;
	}

      default: {
	panic("bad image tag");
	}
      }
    }

/*
 * Given an Image's type, find its header
 */
ImageHeader *
getHeader(void *im, ImageType type)
{
    ImageHeader *header;

    assert(im != (void *)NULL);

    switch(type) {
	case IMAGE_GRAY: {
	    header = ((GrayImage)im)->header;
	    break;
	    }
	
	case IMAGE_FLOAT: {
	    header = ((FloatImage)im)->header;
	    break;
	    }
	
	case IMAGE_RGB: {
	    header = ((RGBImage)im)->header;
	    break;
	    }
	
	case IMAGE_DOUBLE: {
	    header = ((DoubleImage)im)->header;
	    break;
	    }
	
	case IMAGE_BINARY: {
	    header = ((DoubleImage)im)->header;
	    break;
	    }
	
	case IMAGE_LONG: {
	    header = ((LongImage)im)->header;
	    break;
	    }
	
	case IMAGE_PTR: {
	    header = ((PtrImage)im)->header;
	    break;
	    }
	
	case IMAGE_SHORT: {
	    header = ((ShortImage)im)->header;
	    break;
	    }
	
	default: {
	    panic("bad image tag");
	    }
	}

    return(header);
    }
    

/*
 * Get a single positive integer from f. Eat a single character of whitespace
 * following the integer. The integer must be terminated by whitespace or
 * EOF. Nothing else (except for a comment) is allowed. Accumulate comments
 * in incomment.
 */
static int
gettoken(FILE *f, boolean *failed)
{
    int val;
    int c;

    assert(failed != (boolean *)NULL);

    /* Skip over whitespace and comments */
    while (TRUE) {
	do {
	    c = getc(f);
	    if (c == EOF) {
		*failed = TRUE;
		return(0);
		}
	    } while (isspace(c));

	if (c == '#') {
	    /* A comment - skip to the newline */
	    do {
		c = getc(f);
		if (c == EOF) {
		    *failed = TRUE;
		    return(0);
		    }
		if (incommentsize < LOAD_COMMENT_MAX - 1) {
		    incomment[incommentsize++] = c;
		    }
		} while (c != '\n');
	    }
	else {
	    break;
	    }
	}

    assert(!isspace(c));
    /* Accumulate the digits */
    val = 0;
    while (isdigit(c)) {
	val = 10 * val + c - '0';
	c = getc(f);
	if (c == EOF) {
	    /* Number terminated by EOF */
	    *failed = FALSE;
	    return(val);
	    }
	}

    if (!isspace(c)) {
	/* Number terminated by something which isn't whitespace */
	*failed = TRUE;
	return(0);
	}

    /* Number terminated by whitespace */
    *failed = FALSE;
    return(val);
    }

/*
 * Get a 1 or 0 from f. Eat whitespace before the character, if any.
 * Nothing else (except for a comment) is allowed. Accumulate comments
 * in incomment.
 */
static int
getpbmtoken(FILE *f, boolean *failed)
{
    int c;

    assert(failed != (boolean *)NULL);

    /* Skip over whitespace and comments */
    while (TRUE) {
	do {
	    c = getc(f);
	    if (c == EOF) {
		*failed = TRUE;
		return(0);
		}
	    } while (isspace(c));

	if (c == '#') {
	    /* A comment - skip to the newline */
	    do {
		c = getc(f);
		if (c == EOF) {
		    *failed = TRUE;
		    return(0);
		    }
		if (incommentsize < LOAD_COMMENT_MAX - 1) {
		    incomment[incommentsize++] = c;
		    }
		} while (c != '\n');
	    }
	else {
	    break;
	    }
	}

    assert(!isspace(c));

    *failed = FALSE;
    if (c == '0') {
	return(0);
	}
    else if (c == '1') {
	return(1);
	}
    else {
	*failed = TRUE;