scale-h.h

两幅图像匹配算法

/*
 *
 * $Header: /usr/u/wjr/vision/scale-h/RCS/scale-h.h,v 1.23 1994/02/21 21:46:34 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	SCALE_H_H

#define	SCALE_H_H

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

/*
 * Information about a match */
typedef struct {
    point transpos;
    double scalex;
    double scaley;
    long forward_val;	/* The model_frac'th percentile value */
    double forward_frac;	/* What fraction are actually <= model_thresh */
    double forward_frac2;/* What fraction are actually <= forward_val */
    long reverse_val;	/* Ditto for image */
    double reverse_frac;
    double reverse_frac2;
    long reverse_num;	/* How many image pixels lie under the model */
    } stransval;

/*
 * Information about a cell, internally
 */
typedef struct {
    int x, y, scaleX, scaleY;	/* The coords of this transformation */
    long model_thresh;		/* The thresh */
    double model_frac;		/* and frac that were used to evaluate it */
    long forward_val;		/* and the results of the evaluation. */
    double forward_frac;
    double forward_frac2;
    } spqHook;

/*
 * Some information about a boxdtrans
 */
typedef struct {
    unsigned box_w, box_h;	/* The box size */
    LongImage box_dtrans;	/* and the dtrans */
    LongImage box_maxdtrans;	/* and the max-dtrans */
    } sboxdt_info;

/*
 * Some information about a model dtrans
 */
typedef struct {
    unsigned xs, ys;		/* The scale params */
    int nbord;			/* and border used to generate */
    LongImage dtrans;		/* the model dtrans */
    } smodeldt_info;

/*
 * 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)
 * maxx, maxy, inflate_x, inflate_y (always needed)
 * ntickx, nticky, scaleStepX, scaleStepY, scaled_x, scaled_y (always needed)
 * trans (derived based on the model-image matching).
 * modeldtcache (a cache for model dtranses)
 *
 * 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.
 *
 * For the modes where a forward parameter is altered (FORWARD_BESTFRAC
 * and FORWARD_BESTDIST), the corresponding reverse parameter may also be
 * altered. This alteration is determined by reverse_scale and reverse_offset:
 * reverse_val = reverse_scale * forward_val + reverse_offset.
 *
 * 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. Setting all the border values to 0 causes it to
 * search for translations where the scaled model box fits inside the image.
 *
 * 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.
 *
 * {min,max}trans{x,y} control the range of translations to be searched.
 * Note that this control is in addition to the border control above.
 * It is different because this restricts the translation search range
 * independent of the scale search; with the border control, they are
 * coupled (i.e. a given translation with one scale might be in the valid
 * search range, but outside it with another scale). These bounds are
 * *inclusive*. To effectively deactivate them, set the min bounds to a
 * very small number (-MAXINT) should do) and the max bounds to a very
 * large number (MAXINT should do there too).
 *
 * minscalex and minscaley tell us what the smallest value we should use to
 * scale in x and y is. maxskew says that the scale value of X cannot
 * exceed the scale value of Y by more than this factor; it must be >= 1.
 * Setting it to 1 implies that transformations where scalex == scaley are
 * the only valid ones. maxscalex and maxscaley likewise control the largest
 * x and y scale value. Note than there is an implicit cap of 1 on all
 * scales: setting maxscalex or maxscaley to > 1 will have no effect.
 *
 * 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 */
    double reverse_scale;	/* For dependent reverse matching, the scale */
    double reverse_offset;	/* and offset of the dependence */
    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 */

    /* Bounds on the translation range to be searched */
    int mintransx;
    int mintransy;
    int maxtransx;
    int maxtransy;

    /* Bounds on the scale range to be searched */
    double minscalex;		/* How low can you go? */
    double minscaley;		/* in both directions */
    double maxscalex;		/* How high can you go? */
    double maxscaley;		/* in both directions */
    double maxskew;		/* How badly skewed can it get? */

    /* Some stuff that is generated from all that */
    int maxx;		/* Largest X value */
    int maxy;		/* Largest Y value */
    int ntickX;		/* Number of X scale ticks */
    int ntickY;		/* and Y scale ticks */
    double scaleStepX;	/* Size of an X scale tick, in scale space */
    double scaleStepY;	/* and a Y scale tick */
    int **scaled_x;	/* Scaled X values */
    int **scaled_y;	/* and Y values */
    int nscaled_x;	/* and how large the arrays are */
    int nscaled_y;

    smodeldt_info *modeldtcache;	/* The dtrans cache */
    int ncached;			/* and how many are in it */

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

    /* and a hook */
    void *userdata;
    } smodel_info;

/*
 * Similar to smodel_info, but for images.
 *
 * The dtrans here is built using xborder and yborder on each edge. 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).
 * box_dtrans depends on dtrans, and also on box_w and box_h.
 * boxdtcache is a cache of old box dtranses: since the search code may go
 * up and down between levels quickly, and we don't want to recalculate the
 * boxdtrans every time it does this, we cache them away; ensure_dtrans takes
 * care of this caching.
 *
 * 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 */

    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;

/* The forward matching styles */
#define	FORWARD_ALL		1
#define	FORWARD_ONE		2
#define	FORWARD_BESTDIST	4
#define	FORWARD_BESTFRAC	8
#define	FORWARD_HILLCLIMB	16

/* The reverse matching styles */
#define	REVERSE_BOX		1
#define	REVERSE_ALLIMAGE	2
#define	REVERSE_NONE		4

/* from scale-h.c */
extern void findSTransAllModels(simage_info *image,
				smodel_info *models, unsigned nmodels,
				int forwstyle, int revstyle);

/* from trans.c */
extern stransval *malloc_strans(void);
extern void free_strans(stransval *tv);
extern void free_stranslist(List l);
extern spqHook *malloc_spqHook(void);
extern void free_spqHook(spqHook *pqh);
extern void free_spqHooklist(PriQ pq);

/* from utility.c */
extern void clear_smodinfo(smodel_info *model);
extern void free_smodinfo_bits(smodel_info *model);
extern void clear_siminfo(simage_info *im);
extern void free_siminfo_bits(simage_info *im);
extern boolean ensure_sdtrans(simage_info *image,
			      unsigned box_width, unsigned box_height,
			      long thresh);
extern void clear_sboxdtcache(simage_info *image);
extern LongImage get_smodel_dtrans(smodel_info *model, int xs, int ys);
extern LongImage get_smodel_dtrans_padded(smodel_info *model, int xs, int ys,
					  int nbord);
boolean ensure_xscales(smodel_info *model, int xscale);
boolean ensure_yscales(smodel_info *model, int yscale);

#endif