li_recognizer.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

	}
	if( nret == nil) {
				li_err_msg = "Invalid parameters: nret";
				return(-1);
	}
	if( ret == nil) {
				li_err_msg = "Invalid parameters: ret";
				return(-1);
	}

	/*
	 * Go through the stroke array and recognize. Since this is a single
	 *   stroke recognizer, each stroke is treated as a separate
	 *   character or gesture. We allow only characters or gestures
	 *   to be recognized at one time, since otherwise, handling
	 *   the display of segmentation would be difficult. 
	*/
	clss = recognize_internal(rc,tps,&conf);
	if (clss == nil) {
				*nret = 1;
				return(0);
	}

	/*Return values.*/
	*nret = 1;
	return(*clss);
}


static rec_fn*
li_recognizer_get_extension_functions(recognizer rec)
{
	rec_fn* ret;

	/*Check for LI recognizer.*/

	if( !CHECK_LI_MAGIC(rec->recognizer_specific) ) {
				li_err_msg = "Not a LI recognizer";
				return(nil);
	}

	ret = make_rec_fn_array(LI_NUM_EX_FNS);

/* ari -- clearState & getClasses are mine */
	ret[LI_GET_CLASSES] =	(rec_fn)recognizer_getClasses;
	ret[LI_CLEAR] =			(rec_fn)recognizer_clearState;
	ret[LI_ISA_LI] =		(rec_fn)isa_li;
	ret[LI_TRAIN] =			(rec_fn)recognizer_train;

	return(ret);
}

static char**
li_recognizer_get_gesture_names(recognizer)
{
		/*This operation isn't supported by the LI recognizer.*/
		li_err_msg = "Gestures are not supported by the LI recognizer";
		return nil;
}

static xgesture
li_recognizer_set_gesture_action(recognizer, char*, xgesture, void*)
{
		/*This operation isn't supported by the LI recognizer.*/
		li_err_msg = "Gestures are not supported by the LI recognizer";
		return nil;
}

/*
 * Exported Functions
*/

/*RECOGNIZER_INITIALIZE-Initialize the recognizer.*/

/* note from ari:  this expands via pre-processor to
 *
 * recognizer __recognizer_internal_initialize(rec_info* ri)
 */

RECOGNIZER_INITIALIZE(ri)
{
	recognizer r;
	li_recognizer* rec;
	int i;

	/*Check that locale matches.*/

	if( strcmp(ri->ri_locale,LI_SUPPORTED_LOCALE) != 0 ) {
		li_err_msg = "Not a supported locale";
/* fprint(2, "Locale error.\n");*/
		return(nil);
	}

	/*
	 * Check that character sets match. Note that this is only approximate,
	 * since the classifier file will have more information.
	*/

	if( ri->ri_subset != nil ) {
	  for(i = 0; ri->ri_subset[i] != nil; i++ ) {

		if( strcmp(ri->ri_subset[i],UPPERCASE) != 0 &&
			strcmp(ri->ri_subset[i],LOWERCASE) != 0  &&
			strcmp(ri->ri_subset[i],DIGITS) != 0 &&
			strcmp(ri->ri_subset[i],GESTURE) != 0 ) {
		  li_err_msg = "Not a supported character set";
/* fprint(2, "charset error.\n"); */

		  return(nil);
		}
	  }
	}
			 
/* ari */
	r = make_recognizer(ri);
/* fprint(2, "past make_recognizer.\n"); */

	if( r == nil ) {
		li_err_msg = "Can't allocate storage";

		return(nil);
	}

	/*Make a LI recognizer structure.*/


	/* rec = (li_recognizer*)safe_malloc(sizeof(li_recognizer))) == nil ); */

	rec = malloc(sizeof(li_recognizer));

	r->recognizer_specific = rec;

	rec->li_rc.file_name = nil;
	rec->li_rc.nclasses = 0;

	/*Initialize the recognizer struct.*/

	r->recognizer_load_state = li_recognizer_load;
	r->recognizer_save_state = li_recognizer_save;
	r->recognizer_load_dictionary = li_recognizer_load_dictionary;
	r->recognizer_save_dictionary = li_recognizer_save_dictionary;
	r->recognizer_free_dictionary = li_recognizer_free_dictionary;
	r->recognizer_add_to_dictionary = li_recognizer_add_to_dictionary;
	r->recognizer_delete_from_dictionary = li_recognizer_delete_from_dictionary;
	r->recognizer_error = li_recognizer_error;
	r->recognizer_translate = li_recognizer_translate;
	r->recognizer_get_context = li_recognizer_get_context;
	r->recognizer_set_context = li_recognizer_set_context;
	r->recognizer_get_buffer = li_recognizer_get_buffer;
	r->recognizer_set_buffer = li_recognizer_set_buffer;
	r->recognizer_clear = li_recognizer_clear;
	r->recognizer_get_extension_functions = 
	  li_recognizer_get_extension_functions;
	r->recognizer_get_gesture_names = li_recognizer_get_gesture_names;
	r->recognizer_set_gesture_action = 
	  li_recognizer_set_gesture_action;

	/*Initialize LI Magic Number.*/

	rec->li_magic = LI_MAGIC;

	/*Initialize rClassifier.*/

	rec->li_rc.file_name = nil;

	for( i = 0; i < MAXSCLASSES; i++ ) {
		rec->li_rc.ex[i] = nil;
		rec->li_rc.cnames[i] = nil;
	}

	lialg_initialize(&rec->li_rc);

	/*Get rid of error message. Not needed here.*/
	li_err_msg = nil;

	return(r);
}

/*free_rClassifier-Free the rClassifier.*/

static void
free_rClassifier(rClassifier* rc)
{
	int i;

	if( rc->file_name != nil) {
		free(rc->file_name);
	}

	for( i = 0; rc->ex[i] != nil; i++) {
		delete_examples(rc->ex[i]);
		free(rc->cnames[i]);
	}

}

/*RECOGNIZER_FINALIZE-Deallocate the recognizer, finalize.*/

RECOGNIZER_FINALIZE(r)
{
		li_recognizer* rec = (li_recognizer*)r->recognizer_specific;

		/*Make sure this is a li_recognizer first*/
		if( !CHECK_LI_MAGIC(rec) ) {
				li_err_msg = "Not a LI recognizer";
				return(-1);
	}

		/*Deallocate rClassifier resources.*/

		free_rClassifier(&(rec->li_rc));

		/*Deallocate the li_recognizer struct.*/
		free(rec);

		/*Deallocate the recognizer*/
		delete_recognizer(r);

		return(0);
}


/* **************************************************

  Implementation of the Li/Yeung recognition algorithm

************************************************** */

#define	WORST_SCORE	0x7fffffff

/* Dynamic programming parameters */
#define	DP_BAND		3
#define	MIN_SIM		0
#define	MAX_DIST	0x7fffffff
#define	SIM_THLD	60	/* x 100 */
#define	DIST_THLD	3200	/* x 100 */

/* Low-pass filter parameters -- empirically derived */
#define	LP_FILTER_WIDTH	6
#define	LP_FILTER_ITERS	8
#define	LP_FILTER_THLD	250	/* x 100 */
#define	LP_FILTER_MIN	5

/* Pseudo-extrema parameters -- empirically derived */
#define	PE_AL_THLD	1500	/* x 100 */
#define	PE_ATCR_THLD	135	/* x 100 */

/* Contour-angle derivation parameters */
#define	T_ONE		1
#define	T_TWO		20

/* Pre-processing and canonicalization parameters */
#define	CANONICAL_X	108
#define	CANONICAL_Y	128
#define	DIST_SQ_THRESHOLD   (3*3)	/* copied from fv.h */
#define	NCANONICAL	50

/* Tap-handling parameters */
#define	TAP_CHAR	"."
#define	TAP_TIME_THLD	150	    /* msec */
#define	TAP_DIST_THLD	75	    /* dx * dx + dy * dy */
#define	TAP_PATHLEN	1000	    /* x 100 */


/* region types */
#define	RGN_CONVEX  0
#define	RGN_CONCAVE 1
#define	RGN_PLAIN   2
#define	RGN_PSEUDO  3


typedef struct RegionList {
	int start;
	int end;
	int type;
	struct RegionList *next;
} region_list;


/* direction-code table; indexed by dx, dy */
static int lialg_dctbl[3][3] = {{1, 0, 7}, {2, 0x7FFFFFFF, 6}, {3, 4, 5}};

/* low-pass filter weights */
static int lialg_lpfwts[2 * LP_FILTER_WIDTH + 1];
static int lialg_lpfconst = -1;


static int lialg_preprocess_stroke(point_list *);
static point_list *lialg_compute_dominant_points(point_list *);
static point_list *lialg_interpolate_points(point_list *);
static void lialg_bresline(pen_point *, pen_point *, point_list *, int *);
static void lialg_compute_chain_code(point_list *);
static void lialg_compute_unit_chain_code(point_list *);
static region_list *lialg_compute_regions(point_list *);
static point_list *lialg_compute_dompts(point_list *, region_list *);
static int *lialg_compute_contour_angle_set(point_list *, region_list *);
static void lialg_score_stroke(point_list *, point_list *, int *, int *);
static int lialg_compute_similarity(point_list *, point_list *);
static int lialg_compute_distance(point_list *, point_list *);

static int lialg_read_classifier_digest(rClassifier *);

static int lialg_canonicalize_examples(rClassifier *);
static int lialg_canonicalize_example_stroke(point_list *);
static int lialg_compute_equipoints(point_list *);

static int lialg_compute_pathlen(point_list *);
static int lialg_compute_pathlen_subset(point_list *, int, int);
static int lialg_filter_points(point_list *);
static int lialg_translate_points(point_list *, int, int, int, int);
static void lialg_get_bounding_box(point_list *, int *, int *, int *, int *);
static void lialg_compute_lpf_parameters();
static int isqrt(int);
static int likeatan(int, int);
static int quadr(int);


/*************************************************************

  Core routines for the Li/Yeung recognition algorithm

 *************************************************************/

static void lialg_initialize(rClassifier *rec) {
	int i;

	/* Initialize the dompts arrays. */
	for (i = 0; i < MAXSCLASSES; i++) {
		rec->dompts[i] = nil;
	}
}


/*
 *  Main recognition routine -- called by HRE API.
 */
static char *lialg_recognize_stroke(rClassifier *rec, point_list *stroke) {
		int i;
		char *name = nil;
		point_list *input_dompts = nil;
		char *best_name = nil;
		int best_score = WORST_SCORE;
		char *curr_name;
		point_list *curr_dompts;

		/*    (void)gettimeofday(&stv, nil);*/

		if (stroke->npts < 1) goto done;

		/* Check for tap. */

		/* First thing is to filter out ``close points.'' */
		if (lialg_filter_points(stroke) != 0) return(nil);

		/* Unfortunately, we don't have the actual time that each point */
		/* was recorded (i.e., dt is invalid).  Hence, we have to use a */
		/* heuristic based on total distance and the number of points. */
		if (stroke->npts == 1 || lialg_compute_pathlen(stroke) < TAP_PATHLEN)
			return(TAP_CHAR);

		/* Pre-process input stroke. */
		if (lialg_preprocess_stroke(stroke) != 0) goto done;

		/* Compute its dominant points. */
		input_dompts = lialg_compute_dominant_points(stroke);
		if (input_dompts == nil) goto done;

		/* Score input stroke against every class in classifier. */
		for (i = 0, curr_name = rec->cnames[i], curr_dompts = rec->dompts[i];
				i < MAXSCLASSES && curr_name != nil && curr_dompts != nil;
				i++, curr_name = rec->cnames[i], curr_dompts = rec->dompts[i]) {
				int sim;
				int dist;
				int curr_score;

				lialg_score_stroke(input_dompts, curr_dompts, &sim, &dist);
				curr_score = dist;

				if (lidebug && curr_score < DIST_THLD)
				fprint(2, "(%s, %d, %d) ", curr_name, sim, dist);

				/* Is it the best so far? */
				if (curr_score < best_score && curr_score <= DIST_THLD) {
				best_score = curr_score;
				best_name = curr_name;
				}
		}

		if (lidebug)
				fprint(2, "\n");

		/* No errors. */
		name = best_name;

done:
		delete_examples(input_dompts);
		return(name);
}


static int lialg_preprocess_stroke(point_list *points) {
	int minx, miny, maxx, maxy, xrange, yrange, scale, xoff, yoff;

	/* Filter out points that are too close. */
	/* We did this earlier, when we checked for a tap. */
/*
	if (lialg_filter_points(points) != 0) return(-1);
*/

/*    assert(points->npts > 0);*/

	/* Scale up to avoid conversion errors. */
	lialg_get_bounding_box(points, &minx, &miny, &maxx, &maxy);
	xrange = maxx - minx;
	yrange = maxy - miny;
	scale = ( ((100 * xrange + CANONICAL_X / 2) / CANONICAL_X) > 
			  ((100 * yrange + CANONICAL_Y / 2) / CANONICAL_Y))
	  ? (100 * CANONICAL_X + xrange / 2) / xrange
	  : (100 * CANONICAL_Y + yrange / 2) / yrange;
	if (lialg_translate_points(points, minx, miny, scale, scale) != 0)
		return(-1);

	/* Center the stroke. */
	lialg_get_bounding_box(points, &minx, &miny, &maxx, &maxy);
	xrange = maxx - minx;
	yrange = maxy - miny;
	xoff = -((CANONICAL_X - xrange + 1) / 2);
	yoff = -((CANONICAL_Y - yrange + 1) / 2);
	if (lialg_translate_points(points, xoff, yoff, 100, 100) != 0) return(-1);

	/* Store the x and y ranges in the point list. */
	xrange = maxx - minx;
	yrange = maxy - miny;
	points->xrange = xrange;
	points->yrange = yrange;

	if (lidebug) {
		int i;
		fprint(2, "After pre-processing:   %d %d %d %d\n",
				minx, miny, maxx, maxy);
		for (i = 0; i < points->npts; i++)
			fprint(2, "      (%P)\n", points->pts[i].Point);
		fflush(stderr);
	}

	return(0);
}


static point_list *lialg_compute_dominant_points(point_list *points) {
	point_list *ipts;
	region_list *regions;
	point_list *dpts;

	/* Interpolate points. */
	ipts = lialg_interpolate_points(points);
	if (ipts == nil) return(nil);
	if (lidebug) {
				int j;
				fprint(2, "After interpolation:  %d ipts\n", ipts->npts);
				for (j = 0; j < ipts->npts; j++) {
					fprint(2, "  (%P), %lud\n", ipts->pts[j].Point, ipts->pts[j].chaincode);
				}
				fflush(stderr);
	}

	/* Compute regions. */
	regions = lialg_compute_regions(ipts);
/*    assert(regions != nil);*/

	/* Compute dominant points. */
	dpts = lialg_compute_dompts(ipts, regions);
	if (lidebug) {
				int j;
				fprint(2, "Dominant points:  ");
				for (j = 0; j < dpts->npts; j++) {
					fprint(2, "%P (%lud)  ", dpts->pts[j].Point, dpts->pts[j].chaincode);
				}
				fprint(2, "\n");
				fflush(stderr);
	}

	/* Delete region data structure. */
	{
				region_list *curr, *next;
				for (curr = regions; curr != nil; ) {
					next = curr->next;
					free(curr);
					curr = next;
				}
	}
	delete_examples(ipts);
	return(dpts);
}

/* Input points are assumed to be integer-valued! */
static point_list *lialg_interpolate_points(point_list *points) {
	int i, j;
	int maxpts;
	point_list *newpts;

	/* Compute an upper-bound on the number of interpolated points. */
	maxpts = 0;
	for (i = 0; i < (points->npts - 1); i++) {
				pen_point *pta = &(points->pts[i]);
				pen_point *ptb = &(points->pts[i+1]);
				maxpts += abs(pta->x - ptb->x) + abs(pta->y - ptb->y);
	}

	/* Allocate an array of the requisite size. */
	maxpts += points->npts;
	/* newpts = (point_list *)safe_malloc(sizeof(point_list)); */
	newpts = malloc(sizeof(point_list));
	newpts->pts = mallocz(maxpts*sizeof(pen_point), 1);
	if (newpts->pts == nil) {
				free(newpts);
				return(nil);
	}
	newpts->npts = maxpts;
	newpts->next = nil;

	/* Interpolate each of the segments. */
	j = 0;
	for (i = 0; i < (points->npts - 1); i++) {
				pen_point *startpt = &(points->pts[i]);
				pen_point *endpt = &(points->pts[i+1]);

				lialg_bresline(startpt, endpt, newpts, &j);

				j--;	/* end point gets recorded as start point of next segment! */
	}

	/* Add-in last point. */
	newpts->pts[j++] = points->pts[points->npts - 1];
	newpts->npts = j;

	/* Compute the chain code for P (the list of points). */
	lialg_compute_unit_chain_code(newpts);

	return(newpts);
}


/* This implementation is due to Kenny Hoff. */
static void lialg_bresline(pen_point *startpt, pen_point *endpt,
							point_list *newpts, int *j) {
	int Ax, Ay, Bx, By, dX, dY, Xincr, Yincr;

	Ax = startpt->x;
	Ay = startpt->y;
	Bx = endpt->x;
	By = endpt->y;

	/* INITIALIZE THE COMPONENTS OF THE ALGORITHM THAT ARE NOT AFFECTED */
	/* BY THE SLOPE OR DIRECTION OF THE	LINE */
	dX = abs(Bx-Ax);	/* store the change in X and Y of the line endpoints */
	dY = abs(By-Ay);

	/* DETERMINE "DIRECTIONS" TO INCREMENT X AND Y (REGARDLESS OF DECISION) */
	if (Ax > Bx) { Xincr=-1; } else { Xincr=1; }    /* which direction in X? */
	if (Ay > By) { Yincr=-1; } else { Yincr=1; }    /* which direction in Y? */

	/* DETERMINE INDEPENDENT VARIABLE (ONE THAT ALWAYS INCREMENTS BY 1 (OR -1) ) */
	/* AND INITIATE APPROPRIATE LINE DRAWING ROUTINE (BASED ON FIRST OCTANT */
	/* ALWAYS). THE X AND Y'S MAY BE FLIPPED IF Y IS THE INDEPENDENT VARIABLE. */
	if (dX >= dY) {	    /* if X is the independent variable */
				int dPr	= dY<<1;	    /* amount to increment decision if right is chosen (always) */
				int dPru = dPr - (dX<<1);   /* amount to increment decision if up is chosen */
				int P =	dPr - dX;	    /* decision variable start value */
		
				/* process each point in the line one at a time (just use dX) */
				for (; dX>=0; dX--) {
					newpts->pts[*j].x = Ax;
					newpts->pts[*j].y = Ay;
					(*j)++;
		
					if (P > 0) {	/* is the pixel	going right AND	up? */
								Ax+=Xincr;	/* increment independent variable */
								Ay+=Yincr;	/* increment dependent variable */