scale-h.c

Hausdorff Distance for Image Recognition

    BFS(image, model, revstyle, findFracCompare, findFracMatch);

    if (model->trans == NULLLIST) {
	/* Failed */
	return;
	}

    /*
     * Similar to above, except check via the fracs.
     * 
     * We also have to think about the forward_val values: some of them may
     * have been computed based on a different model_frac than the one that
     * we ended up using, and so may need to be recomputed. Now, since
     * we're dealing with stransvals, and not spqHooks, there aren't any
     * fields for the model_frac and model_thresh entries. However, we
     * arranged for the match function to store these values in
     * t->reverse_frac and t->reverse_val, which is a bit of a hack.
     */
    for (ln = liFirst(model->trans); ln != NULLLISTNODE; ) {
	t = (stransval *)liGet(ln);
	assert(t != (stransval *)NULL);

	assert(t->reverse_val == model->model_thresh);
	assert(t->reverse_frac <= model->model_frac);

	if (t->reverse_frac != model->model_frac) {
	    /* This one was calculated with different parameters. */
	    if (t->forward_val == model->model_thresh) {
		/* No recalc needed - it happened to work */
		assert(t->forward_frac == t->forward_frac2);
		}
	    else {
		/* We need to recalc the values */
		if (!checkOneSTransMtoI(image, model, t)) {
		    goto bailout;
		    }
		}

	    if (t->forward_frac < model->model_frac) {
		/* Kill it */
		free_strans(t);
		ln = liRemAndNext(ln);
		}
	    else {
		ln = liNext(ln);
		}
	    }
	else if (t->forward_frac < model->model_frac) {
	    /* This one didn't work */
	    free_strans(t);
	    ln = liRemAndNext(ln);
	    }
	else {
	    /* This one gets kept */
	    ln = liNext(ln);
	    }
	}

    return;

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

    return;
    }

/*
 * This is where the search is actually done. How it works:
 * Start by subdividing the transformation space, exactly as in
 * findSTransMtoI. This gives the top level. Scan all the cells there.
 * This generates a list of matching cells, at the current parameter
 * settings. Put these onto a priority queue, using cmpfunc to make
 * sure the "best" cells at the current parameters are used. Now,
 * scan the first few cells of the priority queue; this gives us
 * a bunch of cells at the next level, and so on.
 * When we get to the bottom level, what we are finding are actual
 * matches; we call matchfunc on each of those. If matchfunc returns
 * TRUE any time, we abort the search. This will happen in the FORWARD_ONE
 * case when a match is found, and also in the other cases if something fails
 * (memory allocation etc) during the match.
 */
static void
BFS(simage_info *image, smodel_info *model, int revstyle,
    boolean (*cmpfunc)(void *pqh1, void *pqh2),
    boolean (*matchfunc)(simage_info *image, smodel_info *model,
			 int revstyle, spqHook *hook))
{
    int lowX, highX, stepX;
    int lowY, highY, stepY;
    int lowScaleX, highScaleX, stepScaleX;
    int lowScaleY, highScaleY, stepScaleY;
    List trans = NULLLIST;
    PriQ lowpq = NULLPRIQ;
    unsigned box_width, box_height;
    boolean needdata;

    assert(image != (simage_info *)NULL);
    assert(model != (smodel_info *)NULL);
    assert(model->pts != (point *)NULL);
    assert(image->dtrans != (LongImage)NULL);
    assert(model->stepx > 0);
    assert(model->stepy > 0);
    assert(cmpfunc != (boolean (*)(void *pqh1, void *pqh2))NULL);
    assert(matchfunc != (boolean (*)(simage_info *image, smodel_info *model,
				     int revstyle, spqHook *hook))NULL);

    trans = liNew();
    if (trans == NULLLIST) {
	goto bailout;
	}
    model->trans = trans;

    /* Get rid of an annoying case */
    if (model->npts == 0) {
	return;		/* No transformations */
	}

    /* Now figure out what step size we're using at the lowest resolution */

    calcLowCells(image, model,
		 &lowX, &highX, &stepX, &lowY, &highY, &stepY,
		 &lowScaleX, &highScaleX, &stepScaleX,
		 &lowScaleY, &highScaleY, &stepScaleY);

    /* Allocate the lowest resolution priority queue */
    lowpq = pqNew(cmpfunc);
    if (lowpq == NULLPRIQ) {
	goto bailout;
	}

    /* Get the top-level box sizes */
    calcBoxes(model, stepX, stepY, stepScaleX, stepScaleY,
	      &box_width, &box_height);

    /* and make the boxdtrans */
    if (!ensure_sdtrans(image, box_width, box_height, model->model_thresh)) {
	goto bailout;
	}

    /* Initially, expand the top level into lowpq */

    /* Determine if we're in highest res yet. */
    if ((stepX == model->stepx) && (stepY == model->stepy) &&
	(stepScaleX == model->stepx) && (stepScaleY == model->stepy)) {
	needdata = TRUE;
	}
    else {
	needdata = FALSE;
	}

    /* Get the coarsest-resolution scan */
    if (!findSTransMtoISampled(image, model,
			       lowX, highX, stepX,
			       lowY, highY, stepY,
			       lowScaleX, highScaleX, stepScaleX,
			       lowScaleY, highScaleY, stepScaleY,
			       lowpq, model->model_thresh, needdata)) {
	/* Failed. Bah. */
	goto bailout;
	}

    if (!needdata) {
	/* OK - we're set to begin the actual search */
	(void)bfsrecur(image, model, lowpq, cmpfunc, matchfunc, revstyle,
		       lowX, highX, stepX,
		       lowY, highY, stepY,
		       lowScaleX, highScaleX, stepScaleX,
		       lowScaleY, highScaleY, stepScaleY, BEAMWIDTH);
	}
    else {
	/*
	 * We're basically done. We haven't really done the search they
	 * wanted though. Pity. FIX?
	 */
	}
	   

    /* We're done - clean up and return */
    free_spqHooklist(lowpq);

    return;

  bailout:

    if (lowpq != NULLPRIQ) {
	free_spqHooklist(lowpq);
	}

    if (trans != NULLLIST) {
	free_stranslist(trans);
	}

    model->trans = NULLLIST;

    return;

    }

/*
 * The recursive part of the best-first (beam) search.
 *
 * We are called with an image, a model, and a list of cells to expand
 * (in lowpq). The cells sizes and range are given by the low, high, step
 * parameters (i.e. the cells represented in lowpq have those step sizes).
 *
 * We expand up to curbeam of the cells in lowpq into highpq. If we're
 * not at the lowest level, then we call ourselves recursively on highpq.
 * If that call returns TRUE (i.e. search successful), we clean up and
 * return TRUE.
 * If not, we expand curbeam*BEAMSPREAD and try again. Continued failures
 * make the beam width continue to expand. Our child starts their beam width
 * off at our current width.
 *
 * When we've cleaned lowpq out, we return FALSE.
 *
 * If we are at the lowest level, then we take the list of matches which
 * we have in highpq, and call matchfunc() on each of them. If it returns
 * TRUE on any, then we clean up and return TRUE. Otherwise, we keep trying
 * until we run out of entries in lowpq. matchfunc will do things like
 * updating model->model_thresh (in the case of ...BestDist) and so on. It
 * will also do reverse matching if required, and will hook good matches
 * onto model->trans. It doesn't free the hook it is passed, though.
 *
 * Note that it isn't possible to distinguish between matchfunc() returning
 * TRUE because the search has succeeded, and it returning TRUE because it
 * failed in some memory allocation. Our cleanup routine must take this into
 * account.
 */
static boolean
bfsrecur(simage_info *image, smodel_info *model,
	 PriQ lowpq,
	 boolean (*cmpfunc)(void *pqh1, void *pqh2),
	 boolean (*matchfunc)(simage_info *image, smodel_info *model,
			      int revstyle, spqHook *hook), int revstyle,
	 int lowX, int highX, int stepX,
	 int lowY, int highY, int stepY,
	 int lowScaleX, int highScaleX, int stepScaleX,
	 int lowScaleY, int highScaleY, int stepScaleY,
	 int curbeam)
{
    int newStepX, newStepY, newStepScaleX, newStepScaleY;    
    unsigned box_width, box_height;
    PriQ highpq = NULLPRIQ;
    PriQNode pqn;
    spqHook *hook;
    boolean bottom;

    assert(image != (simage_info *)NULL);
    assert(model != (smodel_info *)NULL);
    assert(lowpq != NULLPRIQ);
    assert(cmpfunc != (boolean (*)(void *pqh1, void *pqh2))NULL);
    assert(matchfunc != (boolean (*)(simage_info *image, smodel_info *model,
				     int revstyle, spqHook *hook))NULL);

    /* Find out how big cells we should be generating */
    updateCellSteps(model, stepX, stepY, stepScaleX, stepScaleY,
		    &newStepX, &newStepY,
		    &newStepScaleX, &newStepScaleY);

    /* Update the threshold */
    calcBoxes(model, newStepX, newStepY, newStepScaleX, newStepScaleY,
	      &box_width, &box_height);

    /* Are we at the bottom yet? */
    bottom = ((newStepX == model->stepx) && (newStepY == model->stepy) &&
	      (newStepScaleX == model->stepx) &&
	      (newStepScaleY == model->stepy));

    /* Allocate the new priority queue */
    highpq = pqNew(cmpfunc);
    if (highpq == NULLPRIQ) {
	goto bailout;
	}
    
    /* Expand everything in lowpq, a bit at a time */
    while (pqFirst(lowpq) != NULLPRIQNODE) {
	
	/* Make sure that the right dtrans is loaded */
	if (!ensure_sdtrans(image, box_width, box_height, model->model_thresh)) {
	    goto bailout;
	    }

	/* Pick out regions */
	if (!probeRegions(image, model, lowpq, highpq,
			  lowX, highX, newStepX, stepX,
			  lowY, highY, newStepY, stepY,
			  lowScaleX, highScaleX, newStepScaleX, stepScaleX,
			  lowScaleY, highScaleY, newStepScaleY, stepScaleY,
			  model->model_thresh, bottom, curbeam)) {
	    goto bailout;
	    }
	
	if (bottom) {
	    /*
	     * At the bottom level, we need to scan through all the
	     * matches that probeRegions generated, and call matchfunc
	     * on each one. matchfunc will know what to do...
	     */
	    for (pqn = pqFirst(highpq);
		 pqn != NULLPRIQNODE;
		 pqn = pqFirst(highpq)) {
		hook = (spqHook *)pqGet(pqn);
		assert(hook != (spqHook *)NULL);
		pqRem(pqn);

		if ((*matchfunc)(image, model, revstyle, hook)) {
		    /* A match detected - bomb out */
		    free_spqHook(hook);
		    goto bailout;
		    }
		free_spqHook(hook);
		}
	    }
	else {
	    /* Recurse down the search */
	    if (bfsrecur(image, model, highpq, cmpfunc, matchfunc, revstyle,
			 lowX, highX, newStepX,
			 lowY, highY, newStepY,
			 lowScaleX, highScaleX, newStepScaleX,
			 lowScaleY, highScaleY, newStepScaleY, curbeam)) {
		/* Something was found down the line - cleanup and return */
		goto bailout;
		}
	    else {
		/* They must have exhausted highpq */
		assert(pqFirst(highpq) == NULLPRIQNODE);
		}
	    }

	/* We didn't find it - expand the beam and try again. */
	curbeam *= BEAMSPREAD;
	}

    /* We exhausted lowpq - search failed */
    assert(pqFirst(highpq) == NULLPRIQNODE);	/* Nothing left for downsearch */
    pqFree(highpq);
    return(FALSE);

  bailout:

    /* The search is over... clean up */
    if (highpq != NULLPRIQ) {
	free_spqHooklist(highpq);
	}

    return(TRUE);

    }

/*
 * A direction array used for hillclimbing. There are NDIR directions.
 * This has the property that delta[x] is the opposite of
 * delta[(x + NDIR/2) % NDIR].
 */
static int delta[][4] =
{
    { 1, 0, 0, 0}, { 0, 1, 0, 0}, { 0, 0, 1, 0}, { 0, 0, 0, 1},
    {-1, 0, 0, 0}, { 0,-1, 0, 0}, { 0, 0,-1, 0}, { 0, 0, 0,-1}
    };

#define	NDIR	8

/*
 * This routine looks at the matches in model->trans and attempts to
 * improve on each of them. For each match, it evaluates it, and then
 * evaluates its neighbours. If it is "better" than all of its neighbours,
 * then it returns. Otherwise, it continues searching from the best
 * neighbour. Of course, neighbours must qualify in the reverse direction
 * as well.
 *
 * Once it has found a better neighbour, that establishes a search line
 * direction. It keeps going in that direction until the matches stop
 * improving, at which point it does a complete neighbour-scan again, etc.
 *
 * This guarantees that it will end up at *a* local maximum. Note that it
 * might not end up at the best connected local maximum: there may be
 * a local maximum which is reachable from the initial match by passage
 * through good-match-space which it will not reach.
 *
 * Neighbours are the 16-connected (i.e. +-1 in one of the 4 dimensions)
 * neighbours of the match. It takes steps of size model->step[xy],
 * of course.
 */
static void
hillclimb(simage_info *image, smodel_info *model, int revstyle)
{
    int x, y;
    int xs, ys;
    int nx, ny;
    int nxs, nys;
    boolean goodrev;
    long curdist;
    double curfrac;
    double curfrac2;
    long newdist;
    double newfrac;
    double newfrac2;
    int curdir;
    ListNode ln;
    stransval *t;
    boolean done;
    int i;

    int stepx;
    int stepy;

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

    assert(model->trans != NULLLIST);

    stepx = model->stepx;
    stepy = model->stepy;

    foreach (ln, model->trans) {
	t = (stransval *)liGet(ln);
	assert(t != (stransval *)NULL);

	x = t->transpos.x;
	y = t->transpos.y;
	/* Convert the X and Y scale values to integers... */
	xs = (int)(t->scalex / model->scaleStepX + 0.5);
	ys = (int)(t->scaley / model->scaleStepY + 0.5);

	/* Get the current values */
	curdist = t->forward_val;
	curfrac = t->forward_frac;
	curfrac2 = t->forward_frac2;

	/* OK. Start the search... */
	assert(inrange(image, model, x, y, xs, ys));

	while (TRUE) {
	    /* Do a full scan */
	    curdir = -1;
	    for (i = 0; i < NDIR; i++) {
		nx = x + delta[i][0] * stepx;
		ny = y + delta[i][1] * stepy;
		nxs = xs + delta[i][2] * stepx;
		nys = ys + delta[i][3] * stepy;

		if (inrange(image, model, nx, ny, nxs, nys)) {
		    if (!evalOneSTransMtoI(image, model, nx, ny, nxs, nys,
					   &ne