readme

Hausdorff Distance for Image Recognition

This directory contains the code to compute the rasterised Hausdorff
distance under translation.

The files are:
driver.c: main() routine which loads up images, computes the Hausdorff
distance, and prints the results

r-h.c: the actual Hausdorff distance computation code

trans.c, transhash.c: some support code.

Makefile: the Makefile.

Putting it together, you get the program "r-h". This program has
parameters:
	-f forward_thresh forward_frac
	-r reverse_thresh reverse_frac
	imagepoints [modelpoints...]
where
	forward_thresh is the threshold to be used in the forward
(model-to-image) distance computation. It is an integer, and scaled by 100
(i.e. a value of 141 means a distance of 1.41 pixels).
	forward_frac is the fraction to be used in this computation.
	reverse_thresh is the threshold to be used in the reverse
(image-to-model) distance computation.
	reverse_frac is the fraction to be used in this computation.
	imagepoints is a PBM file containing the image.
	modelpoints is a PBM file containing the model. Several models can
be given; each will be matched against the image.

As an example,
r-h -f 141 .9 -r 200 .8 im.pbm mod.pbm
means:
	find all translations where
		1) at least 90% of all the model points (non-zero pixels)
are within 1.41 pixels of some image point, and
		2) at least 80% of the image points lying under the
translated model are within 2 pixels of some model point.

This will produce some output like:
Translations for "mod.pbm"
( 100,  90) = (141, .953), (100, .87)
...
Each line after the first contains information on one match. The line given
as an example means:
	If mod.pbm is translated by 100 pixels in X and 90 pixels in Y,
then
		1) The 90th percentile value of the list of model point to
closest image point distances is 1.41 pixels (.9 is the model_frac
parameter),
		2) 95.3% of the model points are within 1.41 pixels of some
image point,
		3) The 80th percentile value of the list of image point to
closest model point values is 1 pixel, and
		4) 87% of the image points underlying the translated model
are within 2 pixels of some model point (the 2 pixels is the reverse_thresh
parameter).

Note well the distinction between 3 and 4. A translation will be rejected
unless the 80th percentile value of the list of image point to closest
model point values is 2 pixels or less (i.e. 80% of the image points
underlying the translated model must be within 2 pixels of some model
point). What is reported is the actual 80th percentile value (known to be 2
or less) and the actual fraction of the points that were under 2 pixels
(87% in this case, known to be 80% or more).

The main entry point to the code is
findTransAllModels(image_info *image, model_info *models, unsigned nmodels,
		   int revstyle);

The parameters:
	image:	an image_info *, pointing to a structure defining the
image.
	models: a model_info *, pointing to an array of model_info
structures, each defining a single model.
	nmodels: how many models there are in this array.
	revstyle: something determining how the reverse (image-to-model)
distance computation will be done. Possible values are:
		REVERSE_BOX: Compute the image-to-model distance values
based only on those image points which underly the translated model. This
is the style used by driver.c.
		REVERSE_ALLIMAGE: Compute the image-to-model distance
values based on *all* the image points.
		REVERSE_NONE: Skip the image-to-model distance computation
entirely. The values returned in the reverse distance fields will be
undefined.

What this does:
	Each model is considered separately. Let model_info *model be one
of them.
	If model->trans is initially NULLLIST, then it will search the
space of all possible translations (within the provided bounds, see below)
and set model->trans to a List, each ListNode of which will have a
transval * pointer as its userdata (see list.c for an explanation of this).
Each transval will represent a valid translation.
	If model->trans is not initially NULLLIST, then it will assume that
it contains a list, each node of which contains a transval *. It will
look at each of these, and consider the translation in each one's transpos
field. It then determines which of these translations are valid (satisfy
the various threshold and fraction parameters). If one is not valid, it
will delete it from the list and free it. If one is valid, then the rest of
the fields in the transval will be filled out (the reverse_* fields will be
filled out according to the current revstyle; if this is REVERSE_NONE, they
will be unaffected).

The main structures this used:

typedef struct {
    long x;
    long y;
    } point;
This represents a point in the plane.

typedef struct {
    point transpos;
    long forward_val;
    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 represents a translation of the model with respect to the image. The
fields have the following meanings:
    transpos: the translation itself.
    forward_val: the forward distance value, as in the output of r-h above
    forward_frac: the forward fraction
    long reverse_val: the reverse distance value
    float reverse_frac: the reverse fraction
    long reverse_num: The number of image points were used to compute the
reverse distance. If revstyle is REVERSE_BOX, this will be the number of
image points that actually lie under the translated model; if it is
REVERSE_ALLIMAGE, it will be the total number of image points.

transval structures are *not* allocated using the standard malloc() call.
Instead, malloc_trans() is used to allocate them, and free_trans() to free
them.

typedef struct {
    unsigned xsize;
    unsigned ysize;
    unsigned npts;
    point *pts;
    BinaryImage im;
    double model_frac;
    long model_thresh;
    double image_frac;
    long image_thresh;
    int leftborder;
    int topborder;
    int rightborder;
    int bottomborder;
    int stepx;
    int stepy;
    LongImage dtrans;
    List trans;
    void *userdata;
    } model_info;

These fields mean:
    Fields determining the model itself:
    	xsize: this is the width of the box containing the model. All
points in the model must have X coordinates >= 0 and < xsize.
	ysize: similarly for the height of the box.
	npts: the number of model points.
	pts: a pointer to an array of all the model points.
	im: a BinaryImage of the model. This must be an image xsize by
ysize, and must be consistent with npts and pts.

    Fields determining how the model is matched against the image:
	model_frac, model_thresh, image_frac, image_thresh: these are the
parameters to the matching algorithm, as given to the -f and -r
command-line parameters of the r-h program.
	leftborder, topborder, rightborder, bottomborder: These fields
limit the range of translations. Any translation where the entire model
fits into the image expanded by these borders is considered; those where
the model box lies completely or partially outside this range are not. If
these are all zero, then only translations where the entire model lies
entirely inside the image are considered; increasing one will increase this
range. Note that negative values can be used; for example, setting
leftborder to -3 means that if a translation brings the model closer than 3
pixels to the left edge of the image, then that translation will not be
considered.
	stepx, stepy: It is sometimes not necessary to consider every
possible translation in the range being searched. If you want to consider
only every other translation in X, say, set stepx to 2 (normally it is 1).

    Fields generated from this:
	dtrans: This contains the distance transform of the model. It
should initially be (LongImage)NULL. It will be filled out if it is
required. Note that any further calls to findTransAllModels() will use the
value of this field if it is not NULL; this avoids unnecessary
recalculation. If it is no longer needed, it should be freed.
	trans: As noted above, this is a List of transval * values.

    Misc fields:
	userdata: this is a void * field which may be set by the user. It
is not used at all in the r-h code.

typedef struct {
    unsigned xsize;
    unsigned ysize;
    unsigned npts;
    point *pts;
    BinaryImage im;
    unsigned xborder;
    unsigned yborder;
    LongImage dtrans;
    long dtrans_thresh;
    ShortImage plusx_dtrans;
    void *userdata;
    } image_info;

These fields mean:
    Fields determining the image itself:
    	xsize, ysize, npts, pts, im: these have the same meanings as in a
model_info structure.

    Fields generated:
	xborder, yborder: These are derived from the model borders.
	dtrans: This is the image's distance transform. It should initially
be (LongImage)NULL, as in model_info. It should also be kept if the
image_info might be re-used, and freed if not.
	dtrans_thresh: an internal field, used to maintain consistency.
	plusx_dtrans: This is another of these re-usable fields. Again, it
should initially be NULL, and will be set as required, and re-used if the
image_info is re-used. Note that if the image changes at all, all of these
re-usable fields should be freed and set to NULL.

    Misc fields:
	userdata: this is a void * field which may be set by the user. It
is not used at all in the r-h code.