utility.c

Hausdorff Distance for Image Recognition

/*
 *
 * $Header: /usr/u/wjr/vision/scale-h/RCS/utility.c,v 1.15 1994/09/01 23:17:04 wjr Exp $
 *
 * Copyright (c) 1993, 1994 Cornell University.  All Rights Reserved.  
 *  
 * Use, reproduction, preparation of derivative works, and distribution
 * of this software is permitted.  Any copy of this software or of any
 * derivative work must include both the above copyright notice of
 * Cornell University and this paragraph.  Any distribution of this
 * software or derivative works must comply with all applicable United
 * States export control laws.  This software is made available AS IS,
 * and CORNELL UNIVERSITY DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED,
 * INCLUDING WITHOUT LIMITATION THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE, AND NOTWITHSTANDING ANY OTHER
 * PROVISION CONTAINED HEREIN, ANY LIABILITY FOR DAMAGES RESULTING FROM
 * THE SOFTWARE OR ITS USE IS EXPRESSLY DISCLAIMED, WHETHER ARISING IN
 * CONTRACT, TORT (INCLUDING NEGLIGENCE) OR STRICT LIABILITY, EVEN IF
 * CORNELL UNIVERSITY IS ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
 */

static char rcsid[] = "@(#)$Header: /usr/u/wjr/vision/scale-h/RCS/utility.c,v 1.15 1994/09/01 23:17:04 wjr Exp $";

/*
 * This file has some utility routines to fill in and free bits of stuff
 * that get attached to smodel_info and simage_info structures.
 */

#include "scale-h.h"
#include "list.h"
#include "image.h"
#include "immax.h"

static void clear_smodeldtcache(smodel_info *model);

/* Maximum number of cached dtrans entries */
#define	MAXCACHE	10

/*
 * This routine fills in NULLs in all the places that they should be in
 * a (typically) newly generated smodel_info structure. It only fiddles
 * the stuff which is labeled as "generated from all that"; it doesn't
 * touch the matching parameters or the model image or pointlist or
 * userdata or anything like that.
 */
void
clear_smodinfo(smodel_info *model)
{
    assert(model != (smodel_info *)NULL);

    model->scaled_x = model->scaled_y = (int **)NULL;
    model->nscaled_x = model->nscaled_y = 0;
    model->modeldtcache = (smodeldt_info *)NULL;
    model->ncached = 0;
    model->trans = NULLLIST;
    }

/*
 * This routine frees all the bits which might have been allocated by
 * the scale-h code and attached to a smodel_info structure. As with
 * clear_smodinfo, it does not touch the fields which actually contain the
 * model image and pointlist. It does free the translist. For convenience,
 * and safety, it clears (to NULL) the fields that it freed stuff from.
 */
void
free_smodinfo_bits(smodel_info *model)
{
    int i;

    assert(model != (smodel_info *)NULL);

    if (model->scaled_x != (int **)NULL) {
	/* There may be things hooked into this */
	for (i = 0; i < model->nscaled_x; i++) {
	    if (model->scaled_x[i] != (int *)NULL) {
		free((void *)model->scaled_x[i]);
		}
	    }
	free((void *)model->scaled_x);
	model->scaled_x = (int **)NULL;
	}
    model->nscaled_x = 0;

    if (model->scaled_y != (int **)NULL) {
	/* There may be things hooked into this */
	for (i = 0; i < model->nscaled_y; i++) {
	    if (model->scaled_y[i] != (int *)NULL) {
		free((void *)model->scaled_y[i]);
		}
	    }
	free((void *)model->scaled_y);
	model->scaled_y = (int **)NULL;
	}
    model->nscaled_y = 0;

    clear_smodeldtcache(model);

    if (model->trans != NULLLIST) {
	free_stranslist(model->trans);
	model->trans = NULLLIST;
	}
    }

/*
 * This routine does the same thing as clear_smodinfo but for simage_info
 * structures.
 */
void
clear_siminfo(simage_info *im)
{
    assert(im != (simage_info *)NULL);

    im->dtrans = (LongImage)NULL;
    im->box_dtrans = (LongImage)NULL;
    im->box_maxdtrans = (LongImage)NULL;
    im->boxdtcache = (sboxdt_info *)NULL;
    im->ncached = 0;
    }

void
free_siminfo_bits(simage_info *im)
{
    assert(im != (simage_info *)NULL);

    if (im->dtrans != (LongImage)NULL) {
	imFree(im->dtrans);
	im->dtrans = (LongImage)NULL;
	}

    /*
     * The box_dtrans and box_maxdtrans (if INSTRUMENT) are always
     * just copies of pointers from the cache - they should never be freed
     * by themselves.
     */
    if (im->boxdtcache != (sboxdt_info *)NULL) {
	assert(im->box_dtrans != (LongImage)NULL);
	clear_sboxdtcache(im);
	}
    }

void
clear_sboxdtcache(simage_info *im)
{
    int i;

    if (im->boxdtcache != (sboxdt_info *)NULL) {
	assert(im->ncached > 0);

	for (i = 0; i < im->ncached; i++) {
	    if (im->boxdtcache[i].box_dtrans != (LongImage)NULL) {
		imFree(im->boxdtcache[i].box_dtrans);
		}

	    if (im->boxdtcache[i].box_maxdtrans != (LongImage)NULL) {
		imFree(im->boxdtcache[i].box_maxdtrans);
		}
	    }
	free((void *)im->boxdtcache);
	im->boxdtcache = (void *)NULL;
	im->ncached = 0;
	im->box_dtrans = im->box_maxdtrans = (LongImage)NULL;
	}
    }

static void
clear_smodeldtcache(smodel_info *model)
{
    int i;

    if (model->modeldtcache != (smodeldt_info *)NULL) {
	assert(model->ncached > 0);

	for (i = 0; i < model->ncached; i++) {
	    if (model->modeldtcache[i].dtrans != (LongImage)NULL) {
		imFree(model->modeldtcache[i].dtrans);
		}
	    }
	free((void *)model->modeldtcache);
	model->modeldtcache = (void *)NULL;
	model->ncached = 0;
	}
    }

/*
 * Make sure that the image's box transforms exist
 * and are based on the correct thresholds. FALSE if failed.
 *
 * Maintain the boxdtrans cache. This is a cache of MAXCACHE entries,
 * allocated as needed, with random replacement once the cache is full.
 * (Yeah, it's not great, but it's cheap, and the cache is supposed to be
 * big enough to hold everything). image->ncached says how many are
 * present in the cache.
 *
 * image->box_dtrans and image->boxmaxdtrans are always just copies of
 * some entry in the cache.
 *
 * We want to avoid nasty states which could occur if something failed to
 * get allocated, but they keep on calling us.
 */
boolean
ensure_sdtrans(simage_info *image, unsigned box_width, unsigned box_height,
	       long thresh)
{
    int i;
    int slot;

    assert(image->dtrans != (LongImage)NULL);

    if ((image->box_dtrans == (LongImage)NULL) ||
	(box_width != image->box_w) ||
	(box_height != image->box_h)) {
	/* Need to rebuild the box dtrans */

	/* Search the cache for it. */
	if (image->boxdtcache != (sboxdt_info *)NULL) {
	    assert(image->ncached > 0);
	    for (i = 0; i < image->ncached; i++) {
		if ((image->boxdtcache[i].box_w == box_width) &&
		    (image->boxdtcache[i].box_h == box_height) &&
		    (image->boxdtcache[i].box_dtrans != (LongImage)NULL)) {
		    /* Found it. */
		    image->box_dtrans = image->boxdtcache[i].box_dtrans;
		    image->box_maxdtrans = image->boxdtcache[i].box_maxdtrans;
		    image->box_w = box_width;
		    image->box_h = box_height;

		    return(TRUE);
		    }
		}
	    /* Not present in the cache. */
	    if (image->ncached < MAXCACHE) {
		/* Allocate a new slot. */
		slot = image->ncached++;
		}
	    else {
		/* Kill an old slot */
		slot = random() % MAXCACHE;
		if (image->boxdtcache[slot].box_dtrans != (LongImage)NULL) {
		    imFree(image->boxdtcache[slot].box_dtrans);
		    }

		if (image->boxdtcache[slot].box_maxdtrans != (LongImage)NULL) {
		    imFree(image->boxdtcache[slot].box_maxdtrans);
		    }
		}
	    }
	else {
	    /* The cache isn't present at all. Create it. */
	    assert(image->ncached == 0);
	    image->boxdtcache =
		(sboxdt_info *)malloc(MAXCACHE * sizeof(*image->boxdtcache));
	    if (image->boxdtcache == (sboxdt_info *)NULL) {
		return(FALSE);
		}

	    slot = 0;
	    image->ncached = 1;
	    }

	/* Clear the slot we're about to write into, in case of failure. */
	image->boxdtcache[slot].box_dtrans = (LongImage)NULL;
	image->boxdtcache[slot].box_maxdtrans = (LongImage)NULL;

	/* Fill the slot */
	image->boxdtcache[slot].box_dtrans =
	    imMin(image->dtrans, box_width, box_height);
	if (image->boxdtcache[slot].box_dtrans == (LongImage)NULL) {
	    return(FALSE);
	    }

#ifdef	INSTRUMENT
	image->boxdtcache[slot].box_maxdtrans =
	    imMax(image->dtrans, box_width, box_height);
	if (image->boxdtcache[slot].box_maxdtrans == (LongImage)NULL) {
	    imFree(image->boxdtcache[slot].box_dtrans);
	    image->boxdtcache[slot].box_dtrans = (LongImage)NULL;
	    return(FALSE);
	    }
#else
	image->boxdtcache[slot].box_maxdtrans = (LongImage)NULL;
#endif
    
	/* Load the current values from the cache */
	image->box_dtrans = image->boxdtcache[slot].box_dtrans;
	image->box_maxdtrans = image->boxdtcache[slot].box_maxdtrans;
	image->box_w = image->boxdtcache[slot].box_w = box_width;
	image->box_h = image->boxdtcache[slot].box_h = box_height;
	
	}

    return(TRUE);
    }

/*
 * Generate a model distance transform. Basically, use xs and ys
 * to look up the point x and y values in scaledpts, and then
 * stick them together to get a scaled model, which you call dtrans on.
 * Return the dtrans if you can, NULL if not.
 *
 * N.B. The called *must not* try to free the value they get back from this.
 *
 */
LongImage
get_smodel_dtrans(smodel_info *model, int xs, int ys)
{
    return(get_smodel_dtrans_padded(model, xs, ys, 0));
    }

/*
 * Generate a model distance transform. Basically, use xs and ys
 * to look up the point x and y values in scaledpts, and then