li_recognizer.c

神龙卡开发原代码

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] = NULL;
    }
}


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

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

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

    /* Check for tap. */
    {
/*
	pen_point *startpt = &stroke->pts[0];
	pen_point *endpt = &stroke->pts[stroke->npts - 1];
	int dt = endpt->time - startpt->time;
	int dx = endpt->x - startpt->x;
	int dy = endpt->y - startpt->y;
	int magsq = dx * dx + dy * dy;
*/

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

	/* 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 == NULL) 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 != NULL && curr_dompts != NULL;
	  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)
	    fprintf(stderr, "(%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)
	fprintf(stderr, "\n");

    /* No errors. */
    name = best_name;

done:
    delete_examples(input_dompts);
    /*    (void)gettimeofday(&etv, NULL);
	  elapsed = (1000 * (etv.tv_sec - stv.tv_sec)) + ((etv.tv_usec - stv.tv_usec + 500) / 1000);
	  fprintf(stderr, "elapsed = %d\n", elapsed);
     */
    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;
	fprintf(stderr, "After pre-processing:   %d %d %d %d\n",
		minx, miny, maxx, maxy);
	for (i = 0; i < points->npts; i++)
	    fprintf(stderr, "      (%d %d)\n",
		    points->pts[i].x, points->pts[i].y);
	fflush(stderr);
    }

    return(0);
}


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

    /* Interpolate points. */
    ipts = lialg_interpolate_points(points);
    if (ipts == NULL) return(NULL);
    if (lidebug) {
	int j;
	fprintf(stderr, "After interpolation:  %d ipts\n", ipts->npts);
	for (j = 0; j < ipts->npts; j++) {
	    fprintf(stderr, "  (%d, %d), %ld\n",
		    ipts->pts[j].x, ipts->pts[j].y, ipts->pts[j].chaincode);
	}
	fflush(stderr);
    }

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

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

    /* Delete region data structure. */
    {
	region_list *curr, *next;
	for (curr = regions; curr != NULL; ) {
	    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 = allocate(1, point_list);
    newpts->pts = make_pen_point_array(maxpts);
    if (newpts->pts == NULL) {
	free(newpts);
	return(NULL);
    }
    newpts->npts = maxpts;
    newpts->next = NULL;

    /* 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 */
		P+=dPru;	/* increment decision (for up) */
	    }
	    else {		/* is the pixel just going right? */
		Ax+=Xincr;	/* increment independent variable */
		P+=dPr;		/* increment decision (for right) */
	    }
	}
    }
    else {		    /* if Y is the independent variable */
	int dPr	= dX<<1;	    /* amount to increment decision if right is chosen (always) */
	int dPru = dPr - (dY<<1);   /* amount to increment decision if up is chosen */
	int P  = dPr - dY;	    /* decision variable start value */

	/* process each point in the line one at a time (just use dY) */
	for (; dY>=0; dY--) {
	    newpts->pts[*j].x = Ax;
	    newpts->pts[*j].y = Ay;
	    (*j)++;

	    if (P > 0) {	/* is the pixel going up AND right? */
		Ax+=Xincr;	/* increment dependent variable */
		Ay+=Yincr;	/* increment independent variable */
		P+=dPru;	/* increment decision (for up) */
	    }
	    else {		/* is the pixel just going up? */
		Ay+=Yincr;	/* increment independent variable */
		P+=dPr;		/* increment decision (for right) */
	    }
	}
    }
}


static void lialg_compute_chain_code(point_list *pts) {
    int i;

    for (i = 0; i < (pts->npts - 1); i++) {
	pen_point *startpt = &(pts->pts[i]);
	pen_point *endpt = &(pts->pts[i+1]);
	int dx = endpt->x - startpt->x;
	int dy = endpt->y - startpt->y;
/*
	int tmp	= rint(4.0 * atan2((double)dx, (double)dy) / M_PI);
	int dircode = (10 + tmp) % 8;
*/
	int tmp = quadr(likeatan(dy, dx));
	int dircode = (12 - tmp) % 8;

	startpt->chaincode = dircode;
    }
}


static void lialg_compute_unit_chain_code(point_list *pts) {
    int i;

    for (i = 0; i < (pts->npts - 1); i++) {
	pen_point *startpt = &(pts->pts[i]);
	pen_point *endpt = &(pts->pts[i+1]);
	int dx = endpt->x - startpt->x;
	int dy = endpt->y - startpt->y;
	int dircode = lialg_dctbl[dx+1][dy+1];

/*	assert(dircode < 8);*/
	startpt->chaincode = dircode;
    }
}


static region_list *lialg_compute_regions(point_list *pts) {
    region_list *regions = NULL;
    region_list *curr_reg = NULL;
    int *R[2 + LP_FILTER_ITERS];
    int *junk;
    int *curr, *next;
    int i, j;

    /* Initialize low-pass filter parameters if necessary. */
    if (lialg_lpfconst == -1)
	lialg_compute_lpf_parameters();

    /* Allocate a 2 x pts->npts array for use in computing the (filtered) Angle set, A_n. */
    /*    junk = (int *)safe_malloc((2 + LP_FILTER_ITERS) * pts->npts * sizeof(int)); */
    junk = allocate((2 + LP_FILTER_ITERS) * pts->npts, int);
    for (i = 0; i < (2 + LP_FILTER_ITERS); i++)
	R[i] = junk + (i * pts->npts);
    curr = R[0];

    /* Compute the Angle set, A, in the first element of array R. */
    /* Values in R are in degrees, x 100. */
    curr[0] = 18000;				/* a_0 */
    for (i = 1; i < (pts->npts - 1); i++) {
	int d_i = pts->pts[i].chaincode;
	int d_iminusone = pts->pts[i-1].chaincode;
	int a_i;

	if (d_iminusone < d_i)
	    d_iminusone += 8;

	a_i = (d_iminusone - d_i) % 8;

	/* convert to degrees, x 100 */
	curr[i] = ((12 - a_i) % 8) * 45 * 100;
    }
    curr[pts->npts - 1]	= 18000;		/* a_L-1 */

    /* Perform a number of filtering iterations. */
    next = R[1];
    for (j = 0; j < LP_FILTER_ITERS; j++, curr = R[j], next = R[j+1]) {
	for (i = 0; i < pts->npts; i++) {
	    int k;

	    next[i] = 0;

	    for (k = i - LP_FILTER_WIDTH; k <= i + LP_FILTER_WIDTH; k++) {
		int oldval = (k < 0 || k >= pts->npts) ? 18000 : curr[k];
		next[i]	+= oldval * lialg_lpfwts[k - (i	- LP_FILTER_WIDTH)];	/* overflow? */
	    }

	    next[i] /= lialg_lpfconst;
	}
    }

    /* Do final thresholding around PI. */
    /* curr and next are set-up correctly at end of previous loop! */
    for (i = 0; i < pts->npts; i++) {
	next[i] = (abs(curr[i] - 18000) < LP_FILTER_THLD)
	  ? 18000
	  : curr[i];
    }
    curr = next;

    /* Debugging. */
    if (lidebug > 1) {
	for (i = 0; i < pts->npts; i++) {
	    fprintf(stderr, "%3d:  (%3d, %3d)  %ld  ",
		    i, pts->pts[i].x, pts->pts[i].y, pts->pts[i].chaincode);
	    for (j = 0; j < 2 + LP_FILTER_ITERS; j++)
		fprintf(stderr, "%d  ", R[j][i]);
	    fprintf(stderr, "\n");
	}
    }

    /* Do the region segmentation. */
    {
	int start, end;
	int currtype;

#define	RGN_TYPE(val)\
    (((val) == 18000)\
	? RGN_PLAIN\
	: ((val) < 18000 ? RGN_CONCAVE : RGN_CONVEX))

	start = 0;
	currtype = RGN_TYPE(curr[0]);
	/*	regions = (region_list *)safe_malloc(sizeof(region_list));*/
	regions = allocate(1, region_list);
	curr_reg = regions;
	curr_reg->start = start;
	curr_reg->end = 0;
	curr_reg->type = currtype;
	curr_reg->next = NULL;
	for (i = 1; i < pts->npts; i++) {
	    int nexttype = RGN_TYPE(curr[i]);

	    if (nexttype != currtype) {
		region_list *next_reg = NULL;

		end = i - 1;
		curr_reg->end = end;
		if (lidebug > 1)
		    fprintf(stderr, "  (%d, %d), %d\n", start, end, currtype);

		start = i;
		currtype = nexttype;
		/* next_reg = (region_list *)safe_malloc(sizeof(region_list));*/
		next_reg = allocate(1, region_list);
		next_reg->start = start;
		next_reg->end = 0;
		next_reg->type = nexttype;
		next_reg->next = NULL;

		curr_reg->next = next_reg;
		curr_reg = next_reg;
	    }
	}
	end = i - 1;
	curr_reg->end = end;
	if (lidebug > 1)
	    fprintf(stderr, "  (%d, %d), %d\n", start, end, currtype);

	/* Filter out convex/concave regions that are too short. */
	for (curr_reg = regions; curr_reg; curr_reg = curr_reg->next)
	    if (curr_reg->type == RGN_PLAIN) {
		region_list *next_reg;

		for (next_reg = curr_reg->next;
		     next_reg != NULL &&
		       (next_reg->end - next_reg->start) < LP_FILTER_MIN;
		     next_reg = curr_reg->next) {
		    /* next_reg must not be plain, and it must be followed by a plain */
		    /* assert(next_reg->type != RGN_PLAIN); */
		    /* assert(next_reg->next != NULL && (next_reg->next)->type == RGN_PLAIN); */

		    curr_reg->next = (next_reg->next)->next;
		    curr_reg->end = (next_reg->next)->end;

		    free(next_reg->next);
		    free(next_reg);
		}
	    }

	/* Add-in pseudo-extremes. */