readme

Hausdorff Distance for Image Recognition

This code is very similar to the translation-only code; see README in the
r-h directory for details. This file describes the differences only.

driver.c, scale-h.c, trans.c: These have much the same
purposes as the corresponding files in the r-h directory.

utility.c: This has some routines that make dealing with smodel_info and
simage_info structures easier.

There are quite a few additional parameters to the scale-h program:
    -s minXscale minYscale maxskew
	minXscale specifies the minimum X scale of the model that should be
considered. It is a floating point number.
	minYscale does the same for the Y scale.
	maxskew specifies the maximum aspect ratio distortion allowed. It
is a floating point number >= 1.

    -S maxXscale maxYscale
	allows specification of the maximum X and Y scales; these are 1 if
not specified.

    -o
	This tells the program to termimate the search when it finds
*anything* satisfying the criteria, rather than finding everything
satisfying them. This is useful in "presence-or-absence" tests.

    -bf
	This tells the program to find, and report, only the best
transformation satisfying the criteria, where "best" means "having the
largest forward fraction" (the second number in the evaluation
results). This can often be done more quickly than finding every
transformation satisfying the criteria.

    -bd
	This tells the program to find, and report, only the
transformations having the best (lowest) forward distance.

    -e
	This tells the program to expect a list of transformations on its
standard input, in the same format as it produces them. It will evaluate
these transformations according to the parameters it is given, and write
out the evaluations.

    -p scale offset
	This is used in combination with -bf or -bd. These modes can be
thought of as finding the optimum value of one of the parameters specified
with "-f". Adding "-p" means that the corresponding reverse ("-r")
parameter will also be determined. For example, in combination with -bf,
	-p 0.8 0.1
	means that, if the best match's forward distance and fraction are
determined, by evaluation, to be (141, 0.9), then the reverse_frac
paramter, specified by -r, is essentially 0.82: 0.8 * 0.9 + 0.1.

    -allborders, -metric, -hillclimb
	Ignore these options - they don't really work.

For example,
scale-h -bf -f 200 .8 -r 200 0 -s .8 .7 1.1 -S 1.2 1.3 -p 0.8 0.1 im.pbm mod.pbm
means:
	find all the transformations (translations and (X,Y) scaling) where
		1) the scaled model matches the image to within the given
thresholds and fractions (as in the r-h code)
		2) the X scale is between .8 and 1.2
		3) the Y scale is between .7 and 1.3
		4) the X scale is no more than 1.1 times the Y scale
		5) the Y scale is no more than 1.1 times the X scale.
	From all these transformations, pick the ones with the best forward
fraction, and ensure that they also have a reverse fraction which is >=
(0.8*ff + 0.1), where ff is the transformation's forward fraction. Note
that the reverse_frac parameter was specified, on the command line, as "0"
- since it is derived from the results of the search, its initial value is
not important. Actually, it can be important: its initial value will never
be lowered, no matter the results of the search, so it specifies a floor
for the quality of the match.

The format of the output is:
Translations for "mod.pbm"
( 100,  90) (0.873, 0.852) = (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 scaled by 0.873 in X and 0.852 in Y, then translated
by 100 pixels in X and 90 pixels in Y, (i.e. a point (x,y) is mapped to
(round(0.873 * x + 100), round(0.852 * y + 90))), then
		1) The 90th percentile value of the list of transformed
model point to closest image point distances is 1.41 pixels (.9 is the
model_frac parameter),
		2) 95.3% of the transformed model points are within 1.41
pixels of some image point,
		3) The 80th percentile value of the list of image point to
closest transformed model point values is 1 pixel, and
		4) 87% of the image points underlying the transformed model
are within 2 pixels of some model point (the 2 pixels is the reverse_thresh
parameter).

The main entry point to the code is
findSTransAllModels(simage_info *image, smodel_info *models, unsigned nmodels,
		    int forwstyle, int revstyle);
	image, models and nmodels have the same meanings as in the r-h code.
	forwstyle can take on the values FORWARD_ALL, FORWARD_ONE,
FORWARD_BESTFRAC and FORWARD_BESTDIST. These correspond to the default
mode, and the -o, -bf and -bd modes.
	revstyle can only take on the values REVERSE_BOX and REVERSE_NONE
(i.e. REVERSE_ALLIMAGE is not fully supported).
	model->trans acts the same way.

The structures are:

typedef struct {
    point transpos;
    double scalex;
    double scaley;
    long forward_val;
    double forward_frac;
    double forward_frac2;
    long reverse_val;
    double reverse_frac;
    double reverse_frac2;
    long reverse_num;
    } stransval;

All these fields have the same meaning as in the transval structures. The
new fields contain the X and Y scales that (along with the translation in
transpos) led to these forward and reverse distance values and fractions.
The _frac2 values are new, and have different meanings from the
corresponding _frac values. Basically,
	stransval.forward_val is the model_frac'th percentile value of the
model point distances for this transformation
	stransval.forward_frac is the fraction of the distances that are <=
model_thresh
	stransval.forward_frac2 is the fraction of the distances that are
<= stransval.forward_val - i.e. in relation to this transformation's
evaluated distance.

Again, these structures are *not* allocated using malloc(); malloc_strans()
and free_strans() must be used.

typedef struct {
    unsigned xsize;
    unsigned ysize;
    unsigned npts;
    point *pts;
    BinaryImage im;

    double model_frac;
    long model_thresh;
    double image_frac;
    long image_thresh;
    double reverse_scale;
    double reverse_offset;

    int leftborder;
    int topborder;
    int rightborder;
    int bottomborder;
    int stepx;
    int stepy;
    int mintransx;
    int mintransy;
    int maxtransx;
    int maxtransy;
    double minscalex;
    double minscaley;
    double maxscalex;
    double maxscaley;
    double maxskew;

    int maxx;
    int maxy;
    int ntickX;
    int ntickY;
    double scaleStepX;
    double scaleStepY;
    int **scaled_x;
    int **scaled_y;
    int nscaled_x;
    int nscaled_y;
    smodeldt_info *modeldtcache;	/* The dtrans cache */
    int ncached;			/* and how many are in it */

    List trans;

    void *userdata;
    } smodel_info;

This is the equivalent to the translation-only code's model_info.
	xsize, ysize, npts, pts, im, model_frac, model_thresh,
	image_frac, image_thresh, leftborder, topborder, rightborder,
	bottomborder, stepx, stepy: These have the same meanings as in the
translation-only code. stepx and stepy control the resolution
of the sampling in both the translation and scale spaces.

	minscalex, minscaley, maxskew: these are the parameters to the
matching algorithm as given to the -s command-line parameters of the
scale-h program.

	maxscalex, maxscaley: these are the -S parameters.

	mintransx, maxtransx, mintransy, maxtransy: these allow the user to
limit the range of translations which will be searched.

	trans: This has a similar meaning to the trans field in the
translation-only model_info. It is a List of stransval * values.
	userdata: This is another user-only field.

	The fields from maxx to ncached: You don't want to know what these
values are; never read or write these fields. They can be cleared by a call
to clear_smodinfo() and the storage hanging off them can be reclaimed by a
call to free_smodinfo_bits(). Note that clear_smodinfo() also clears the
trans field. Also, free_smodinfo_bits() frees the trans list; since this
list may be required, the trans field should be set to NULL before calling
free_smodinfo_bits() if you do not want it freed. So the way a smodel_info
should be treated is:
	Allocate a smodel_info somehow; say it's called "model".
	Call clear_smodinfo to clear all the fields you don't know about.
	Set up all the rest of the fields.
	Call findSTransAllModels().
	If you want to, change some of the parameters, and call it again;
if you do this, then it doesn't recalculate the things that it already had,
saving time (this is what is stored in those extra fields). Be aware that
*you* control the contents of the trans field, and this being NULLLIST or
not makes a difference to what the search code does - if you want a
completely new search, do
	free_stranslist(model.trans);
	model.trans = NULLLIST;
	before calling findSTransAllModels() again.
	When you're done with searching using this model, call
free_smodinfo_bits() to get rid of the extra storage. Remember that this
also clobbers model.trans, so if you want to keep the list, just do
	safetrans = model.trans;
	model.trans = NULLLIST;
	before free_smodinfo_bits(); remember that you're now responsible
for eventually calling free_stranslist(safetrans).

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 */

    unsigned box_w, box_h;	/* The box used to generate */
    LongImage box_dtrans;	/* the box-min dtrans */
    LongImage box_maxdtrans;	/* the box-max dtrans */

    sboxdt_info *boxdtcache;	/* Cache for old box dtranses */
    int ncached;		/* How many are in the cache */

    void *userdata;
    } simage_info;

This is similar to the translation-only simage_info. clear_siminfo() and
free_siminfo_bits() do the appropriate things, as with smodel_infos, for
the fields you don't want to know about (everything from dtrans to
ncached).

If you're in doubt about this stuff, read through driver.c - it does a
pretty general job of setting up the appropriate fields, and allocating and
freeing things when they need to be.