r-h.h

Hausdorff Distance for Image Recognition

/*
 *
 * $Header: /usr/u/wjr/vision/r-h/RCS/r-h.h,v 2.5 1993/08/23 21:51:52 wjr Exp $
 *
 * Copyright (c) 1990, 1991, 1992, 1993 Cornell University.  All Rights
 * Reserved.  
 *  
 * Copyright (c) 1991, 1992 Xerox Corporation.  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 notices of
 * Cornell University and Xerox Corporation 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 XEROX CORPORATION 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 XEROX CORPORATION IS ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGES.
 */

#ifndef R_H_H
#define R_H_H

#include "misc.h"
#include "image.h"
#include "list.h"
#include "dtrans.h"
#include "readpts.h"
#include "pick.h"

typedef struct {
    point transpos;
    long forward_val;	/* The model_frac'th percentile value */
    float forward_frac;	/* What fraction are actually <= model_thresh */
    long reverse_val;	/* Ditto for image */
    float reverse_frac;
    long reverse_num;	/* How many image pixels lie under the model */
    } transval;

/*
 * This structure holds all that there is to know about a model:
 * what it is and what to do with it. It also holds a bunch of stuff that
 * is derived from the model at various stages in the processing.
 * The basic rule followed by the r-h code is:
 * If it is derived from the model, and if it is non-null, use it.
 * Otherwise, if you need it, generate it.
 *
 * The stuff that is derived is:
 * dtrans (always needed)
 * trans (derived based on the model-image matching).
 *
 * If trans is NULL initially, a complete match will be done, and trans
 * will be filled out.
 *
 * If trans is non-NULL initially, then the translations which are present
 * in trans will be verified: if the translation gives rise to a match
 * satisfying the model and image thresholds and fractions, then the
 * forward and reverse value fields will be filled in, and the translation
 * will be present in trans when it is returned; if the translation does
 * not give rise to such a match, then the translation will be deleted.
 *
 * The *border fields allow you to specify what range of translations should
 * be considered. The process used for this is:
 * Take the image box. Expand (or shrink) it by the various border values.
 * This will give you a new box. Consider every translation for which the
 * entire model box fits inside this new box.
 *
 * The step{x,y} fields allow you to specify some level of "downsampling"
 * of the translations you get: translations considered will be separated by
 * some multiple of stepx in X, and stepy in Y. Setting these to (1, 1)
 * results in considering every translation, (2, 2) means every other one
 * in each X and Y (so 1/4 as many in all), etc. These do not apply if
 * a non-NULL trans has been passed in, since that explicitly specifies
 * which translations to consider.
 *
 * If you want to consider every translation where the model box overlaps
 * with the original image box, then use
 * leftborder = rightborder = xsize - 1
 * topborder = bottomborder = ysize - 1
 * Negative *border values cause the image box to be shrunk; positive cause
 * it to be expanded.
 *
 * N.B. Using negative border values *can change the answers given*: the
 * image distance transform is calculated using only those portions of the
 * image which fit into the box; portions outside that are ignored. This
 * means that they will not be considered in computing the distance transforms.
 * For typical images (fairly high edge density), this will not make much
 * difference.
 *
 * userdata is a hook that the code owning this structure can use.
 */
typedef struct {
    /* Bits to do with the size of the model */
    unsigned xsize; 	/* Width of the model box */
    unsigned ysize; 	/* Height of the model box */

    /* The model points themselves */
    unsigned npts;	/* Number of model points */
    point *pts;		/* The model points */

    /* The model points themselves, in another format */
    BinaryImage im;	/* The model bitmap */

    /* Stuff to do with how to compare this against the image */
    double model_frac;		/* The fraction of model pixels to consider */
    long model_thresh;		/* and the threshold they must lie under */
    double image_frac;		/* Ditto for */
    long image_thresh;		/* the image */
    int leftborder;		/* How many pixels to expand the image by */
    int topborder;		/* to get the box that we slide the model */
    int rightborder;		/* around inside */
    int bottomborder;
    int stepx;			/* What stride to use in X */
    int stepy;			/* and Y */

    /* Some stuff that is generated from all that */
    LongImage dtrans;	/* The model's distance transform */

    /* The translations that are generated */
    List trans;

    void *userdata;
    } model_info;

/*
 * Similar to model_info, but for images.
 *
 * The dtrans here is built using the given borders. This
 * means that if these are to be changed, the dtrans must be rebuilt.
 * (Actually, it only really needs to be rebuilt if one of them decreases).
 * plusx_dtrans depends on dtrans, and also on image_thresh, so if image_thresh
 * changes, it must also be rebuilt.
 *
 * userdata is a hook that the code owning this structure can use.
 */
typedef struct {
    unsigned xsize;		/* The image width */
    unsigned ysize;		/* and height */
    unsigned npts;		/* How many points */
    point *pts;			/* and the points themselves */
    
    /* The image, in another format */
    BinaryImage im;		/* The image bitmap */

    /* Derived stuff */
    int leftborder;		/* Borders used for the following */
    int topborder;
    int rightborder;		/* distance transforms */
    int bottomborder;
    LongImage dtrans;		/* The image's distance transform */

    long dtrans_thresh;		/* The threshold used to generate */
    ShortImage plusx_dtrans;	/* the image's +x dt */

    void *userdata;
    } image_info;

/* from r-h.c */
/* The reverse matching styles */
#define	REVERSE_BOX		1
#define	REVERSE_ALLIMAGE	2
#define	REVERSE_NONE		4

extern void findTransAllModels(image_info *image,
			       model_info *models, unsigned nmodels,
			       int revstyle);

/* from trans.c */
extern transval *malloc_trans();
extern void free_trans(transval *tv);
extern void free_translist(List l);

#endif